GDI+命中测试的效率[r]

问题的提出：
摄像头的分辨率从30万一直到700万，成本不停地降低，性能不停地提高，在项目开发过程中碰到这样的问题，为了将提高精度，使用700万的摄像头来进行微距拍摄，因此带来最直接的问题是相同的颗粒需要处理的像素多了很多多多多。
在低分辨率图像中，像素少，整体的处理时间也不多。但是一旦使用高分辨率的图像，为便于用户全局观察，图像显示时缩小了，对用户来说并未感觉到选择区域的变化，可是需要处理的像素增加了，处理时间则呈平方倍数增加，就会明显地察觉到停顿。为此，我们需要找到原来的程序的速度瓶颈，进行优化。

问题的分析：
在不改变算法逻辑的前提下，我们对程序的各部分的时间耗费进行了分析和测试。最后发现程序中有两中功能的代码应该还可以改进，减少所需的时间。
一个是对图像像素值的读写，也就是通过坐标(x,y)对像素的寻址定位，一般的方法就是通过
p = y*width + x; 
来换算像素值在线形内存地址中的位置，这样的做法简单且直观，容易理解，但是每访问一个就需要进行1次乘法和1次加法。如果单个像素使用多个字节存储（一般24位3个字节），则还需要额外的乘法和加法。因此我们希望可以改变地址计算的方法，按照像素的存储顺序进行扫描，避免不必要的乘法运算。

另外一方面，就是判断坐标为(x,y)的像素是否在选择的区域内。因为程序所使用的检测算法对杂质的影响非常敏感，已经定好的解决方案是让用户自己圈定一个区域进行检测，因此在对图像进行处理时就需要判断点是否在区域内，是的话则进行统计并处理，否则放弃。原来的程序是基于GDI的，使用CRgn类创建多边形区域，使用CRgn::PtInRegion(x,y)函数判断命中。测试发现，对矩形区域（不判断）和对一个多边形区域进行处理，在代码中就是将判断命中的if语句注销掉和不去掉一行的差别，处理时间相差甚多。
我们使用了GDI+中的Region对象及Region::IsVisible(x,y)函数替代，处理时间有所缩短，但是，因为处理的像素实在太多（选择图像的一半就有350万个像素），判断和不判断区域命中的时间差距仍然比较多。因此开始怀疑GDI+的Region::IsVisible(x,y)函数的判断算法的效率有问题，于是决定自己实现这个判断的功能。实现的基本思想就是用空间来换时间。

问题的解决方案：

首先是扫描线问题，这个比较简单，按行扫描则符合像素的存储顺序。图中兰色代表扫描的区域，红色是扫描的顺序也就是地址的递增操作，需要注意的是每行扫描结束后需要增加offx，以跳到下一行行首地址，值应该为 w - right ，一般right都为选择区域内的最右边像素x坐标的再往右一个像素的坐标。

命中测试问题用FastHitTest类来解决，初始化时创建一个选定区域的外接矩形大小的位图，并记录矩形的左上坐标，然后将位图先全部涂成指定的背景色，然后在选定的区域中涂上用指定的前景色。判定的时候，只要检查这个位图对应点是否前景色，是则在区域内，否则在区域外。在外接矩形外的点不需要判断了，直接否定。在FastHitTest，记录了三种区域，如图中白色区域为外接矩形外的区域，通过左上坐标和位图大小来确定；兰色为指定的背景色，为选择区域的外接矩形；红色为指定的前景色，为所选择的区域。空间耗费就为位图所占用的空间，单次区域内判断的时间耗费就仅为查询位图内指定坐标的点的颜色。

项目中实际使用过的代码，集合放到IPLab程序中了，是VC6下直接链接gdiplus.lib库，可以直接编译运行，在这里下载。程序运行后打开工程文件夹下的700万（3072*2304）像素的图片，显示默认缩放为原图的15%，然后应该按住鼠标选定一块区域，快捷按钮1-5的功能分别为：1对全图进行反色处理；2、3、4都对选定的局部区域进行反色处理，但是判断命中的方式分别为CRgn方式、Region方式和FastHitTest方式，处理结束后分别给出处理时间；5将选择区域（记录了鼠标的划过的路径），用DrawPath和Fill两种方式画出来以比较路径和区域的差异。

贴出关键代码的全文。

图像反色算法函数：

void  CIPLabDoc::IPFuncInvInRegion_F(GraphicsPath *  pWorkingRegion)
{
    if (!pPicture || !pWorkingRegion) {
        return;
    }
    
    BitmapData bitmapData;
    Rect imageRect(0, 0, pPicture->GetWidth(), pPicture->GetHeight());//900,900);
    Rect rect;
    
    pWorkingRegion->GetBounds(&rect);
    rect.Intersect(imageRect);
    
    BYTE inv[256*3];
    int i;
    for(i=0;i<256;i++)
    {
        inv[i+256*0]=255-i;    //b
        inv[i+256*1]=255-i;    //g
        inv[i+256*2]=255-i;    //r
    }
    
    Status status = pPicture->LockBits(
        &rect,
        ImageLockModeRead | ImageLockModeWrite,
        PixelFormat24bppRGB,
        &bitmapData);
    
    if (status != Ok ) {
        return;
    }
    unsigned char* pixels = (unsigned char*)bitmapData.Scan0;
    int x,y;
    int offx = bitmapData.Stride - bitmapData.Width*3;
    BYTE* pHistogramProjection = inv;
    
    FastHitTest fHitTest(pWorkingRegion);
    
    for(y=rect.GetTop();y<rect.GetBottom();y++)
    {
        for(x=rect.GetLeft();x<rect.GetRight();x++)
        {
            if (fHitTest.IsVisible(x,y)) {
                
                //b
                *pixels = pHistogramProjection[*pixels];
                pixels++;
                pHistogramProjection += 256;
                
                //g
                *pixels = pHistogramProjection[*pixels];
                pixels++;
                pHistogramProjection += 256;
                
                //r
                *pixels = pHistogramProjection[*pixels];
                pixels++;
                pHistogramProjection -= 256*2;
            }
            else
            {
                pixels += 3;
            }
        }
        pixels += offx;
    }
    pPicture->UnlockBits(&bitmapData);
    
    UpdateAllViews(NULL);
}

FastHitTest的构造函数：

void  FastHitTest::init( const  GraphicsPath *  pPath,BOOL includeEdge)
{
    pPath->GetBounds(&m_Bounds);

    m_RegionBuffer = new Bitmap(m_Bounds.Width,m_Bounds.Height,PixelFormat32bppRGB);

    Graphics g(m_RegionBuffer);

    SolidBrush backgroundBrush(m_BackgroundColor);
    g.FillRectangle(&backgroundBrush,0,0,m_Bounds.Width,m_Bounds.Height);

    SolidBrush foregroundBrush(m_ForegroundColor);
    Pen foregroundPen(&foregroundBrush);

    GraphicsPath *path = pPath->Clone();
    Matrix mat;

    mat.Translate((float)(-1.0 * m_Bounds.GetLeft()), (float)(-1 * m_Bounds.GetTop()));
    path->Transform(&mat);

    g.FillPath(&foregroundBrush,path);

    //confirm required
    if (includeEdge) {
        g.DrawPath(&foregroundPen,path);
    }

    delete path;
}

判断命中的函数：

BOOL FastHitTest::IsVisible( int  x,  int  y)
{
    if( !m_RegionBuffer )
    {
        return FALSE;
    }

    if ( x < m_Bounds.GetLeft() || x >= m_Bounds.GetRight() 
        || y < m_Bounds.GetTop() || y >= m_Bounds.GetBottom() )
    {
        return FALSE;
    }

    UINT *p = (UINT*)m_Data.Scan0 + m_Data.Stride * (y-m_Bounds.GetTop() ) / 4 + (x - m_Bounds.GetLeft());

    if ( *p == m_ForegroundColor.GetValue() ) {
        return TRUE;
    }

    return FALSE;
}

总结：

当图特别大的时候，处理区域特别大的时候，空间换时间的方式可以将处理时间下降到可以容忍的程度。空间耗费嘛，及时释放的话还是能够忍受的。

如果需要进行多次区域命中判断，整体代价（时间、空间及复杂度等因素）太高时，而且算法跟区域无关时，可以选择对全图进行处理（不判断命中），然后再对结果进行剪切，这样就只需要进行一次命中判断。

除此之外，自己构造的类可以解决一些边缘的问题。无论在GDI或者GDI+中，Rect的边缘（Draw出来的）和内部区域（Fill出来的）都有1个像素的差别，对于多边形区域就更难发现其中的对应关系，如果边缘跟踪出来的颗粒利用区域命中的方法来计算面积，就会和预期的有所差距，特别在颗粒呈细长条状时特别明显。程序中的HitTest按钮将这个差别画出来了，不是很容易观察到，可以剪屏后到画笔中用大尺寸查看。因此FastHitTest的构造参数中有个BOOL变量，来决定是否包括边缘。

原来还希望加入边缘宽度，并以边缘框架的形式来测试命中，这样可以在判断单次点击是否点击命中这个路径时，决定敏感区域的宽窄。但是这个问题并不需要单独出一个类花这么多的空间来完成，直接使用GDI+提供的方法已经足够了。因此也就没有进一步的扩展。

问题还很多，有兴趣或者有相关经验的朋友，不妨一起讨论。兴趣最重要，但是要肯花时间，真诚，不劳而获是可耻的。:-|