边缘检测和轮廓提取方法和VC--程序.doc

边沿检测和轮廓提取方法和程序
1 边沿检测
我们给出一个模板 和一幅图象 。不难发现原图中左边暗，右边亮，中间存在着一条明显的边界。进行模板操作后的结果如下： 。
可以看出，第3、4列比其他列的灰度值高很多，人眼观察时，就能发现一条很明显的亮边，其它区域都很暗，这样就起到了边沿检测的作用。
为什么会这样呢？仔细看看那个模板就明白了，它的意思是将右邻点的灰度值减左邻点的灰度值作为该点的灰度值。在灰度相近的区域内，这么做的结果使得该点的灰度值接近于0；而在边界附近，灰度值有明显的跳变，这么做的结果使得该点的灰度值很大，这样就出现了上面的结果。
这种模板就是一种边沿检测器，它在数学上的涵义是一种基于梯度的滤波器，又称边沿算子，你没有必要知道梯度的确切涵义，只要有这个概念就可以了。梯度是有方向的，和边沿的方向总是正交(垂直)的，例如，对于上面那幅图象的转置图象，边是水平方向的，我们可以用梯度是垂直方向的模板 检测它的边沿。
例如，一个梯度为45度方向模板 ，可以检测出135度方向的边沿。
1.         Sobel算子
在边沿检测中，常用的一种模板是Sobel 算子。Sobel 算子有两个，一个是检测水平边沿的 ；另一个是检测垂直平边沿的 。与 和 相比，Sobel算子对于象素的位置的影响做了加权，因此效果更好。
Sobel算子另一种形式是各向同性Sobel(Isotropic Sobel)算子，也有两个，一个是检测水平边沿的 ，另一个是检测垂直平边沿的 。各向同性Sobel算子和普通Sobel算子相比，它的位置加权系数更为准确，在检测不同方向的边沿时梯度的幅度一致。
下面的几幅图中，图7.1为原图；图7.2为普通Sobel算子处理后的结果图；图7.3为各向同性Sobel算子处理后的结果图。可以看出Sobel算子确实把图象中的边沿提取了出来。

图7.1     原图

图7.2     普通Sobel算子处理后的结果图

图7.3     各向同性Sobel算子处理后的结果图
在程序中仍然要用到第3章介绍的通用3×3模板操作函数TemplateOperation，所做的操作只是增加几个常量标识及其对应的模板数组，这里就不再给出了。
2.         高斯拉普拉斯算子
由于噪声点(灰度与周围点相差很大的点)对边沿检测有一定的影响，所以效果更好的边沿检测器是高斯拉普拉斯(LOG)算子。它把我们在第3章中介绍的高斯平滑滤波器和拉普拉斯锐化滤波器结合了起来，先平滑掉噪声，再进行边沿检测，所以效果会更好。
常用的LOG算子是5×5的模板，如下所示 。到中心点的距离与位置加权系数的关系用曲线表示为图7.4。是不是很象一顶墨西哥草帽？所以，LOG又叫墨西哥草帽滤波器。

图7.4     LOG到中心点的距离与位置加权系数的关系曲线
图7.5为图7.1用LOG滤波器处理后的结果。

图7.5     图7.1用LOG滤波器处理后的结果图
LOG的算法和普通模板操作的算法没什么不同，只不过把3×3改成了5×5，这里就不再给出了。读者可以参照第3章的源程序自己来完成。
7.2 Hough变换
Hough变换用来在图象中查找直线。它的原理很简单：假设有一条与原点距离为s，方向角为θ的一条直线，如图7.6所示。

图7.6    一条与原点距离为s，方向角为θ的一条直线
直线上的每一点都满足方程

(7.1)
利用这个事实，我们可以找出某条直线来。下面将给出一段程序，用来找出图象中最长的直线(见图7.7)。找到直线的两个端点，在它们之间连一条红色的直线。为了看清效果，将结果描成粗线，如图7.8所示。

图7.7 原图

图7.8 Hough变换的结果
可以看出，找到的确实是最长的直线。方法是，开一个二维数组做为计数器，第一维是角度，第二维是距离。先计算可能出现的最大距离为 ，用来确定数组第二维的大小。对于每一个黑色点，角度的变化范围从00到1780(为了减少存储空间和计算时间，角度每次增加20而不是10)，按方程(7.1)求出对应的距离s来，相应的数组元素[s][ ]加1。同时开一个数组Line，计算每条直线的上下两个端点。所有的象素都算完后，找到数组元素中最大的，就是最长的那条直线。直线的端点可以在Line中找到。要注意的是，我们处理的虽然是二值图，但实际上是256级灰度图，不过只用到了0和255两种颜色。
BOOL Hough(HWND hWnd)
{
//定义一个自己的直线结构
    typedef struct{
                           int topx; //最高点的x坐标
                           int topy; //最高点的y坐标
                           int botx; //最低点的x坐标
                           int boty; //最低点的y坐标
                           }MYLINE;
       DWORD                             OffBits,BufSize;
     LPBITMAPINFOHEADER    lpImgData;
       LPSTR                     lpPtr;
       HDC                        hDc;
LONG                                  x,y;
       long                         i,maxd;
       int                           k;
       int                           Dist,Alpha;
HGLOBAL                  hDistAlpha,hMyLine;
     Int                                         *lpDistAlpha;
       MYLINE                             *lpMyLine,*TempLine,MaxdLine;
     static LOGPEN                rlp={PS_SOLID,1,1,RGB(255,0,0)};
     HPEN                              rhp;
//我们处理的实际上是256级灰度图，不过只用到了0和255两种颜色。
if( NumColors!=256){
       MessageBox(hWnd,"Must be a mono bitmap with grayscale palette!",
"Error Message",MB_OK|MB_ICONEXCLAMATION);
return FALSE;
}
//计算最大距离
       Dist=(int)(sqrt((double)bi.biWidth*bi.biWidth+
(double)bi.biHeight*bi.biHeight)+0.5);
       Alpha=180 /2 ;  //0 到 to 178 度，步长为2度
       //为距离角度数组分配内存
if((hDistAlpha=GlobalAlloc(GHND,(DWORD)Dist*Alpha*
sizeof(int)))==NULL){
MessageBox(hWnd,"Error alloc memory!","Error Message",
MB_OK|MB_ICONEXCLAMATION);
return FALSE;
    }
       //为记录直线端点的数组分配内存
      if((hMyLine=GlobalAlloc(GHND,(DWORD)Dist*Alpha*
sizeof(MYLINE)))==NULL){
            GlobalFree(hDistAlpha);
           return  FALSE;
       }
       OffBits=bf.bfOffBits-sizeof(BITMAPFILEHEADER);
//BufSize为缓冲区大小
       BufSize=OffBits+bi.biHeight*LineBytes;
     lpImgData=(LPBITMAPINFOHEADER)GlobalLock(hImgData);
     lpDistAlpha=(int *)GlobalLock(hDistAlpha);
       lpMyLine=(MYLINE *)GlobalLock(hMyLine);
for (i=0;i<(long)Dist*Alpha;i++){
              TempLine=(MYLINE*)(lpMyLine+i);
              (*TempLine).boty=32767; //初始化最低点的y坐标为一个很大的值
       }
       for (y=0;y<bi.biHeight;y++){
              //lpPtr指向位图数据
              lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes);
              for (x=0;x<bi.biWidth;x++)
                     if(*(lpPtr++)==0) //是个黑点
                            for (k=0;k<180;k+=2){
                                   //计算距离i
                              i=(long)fabs((x*cos(k*PI/180.0)+y*sin(k*PI/180.0)));
                                   //相应的数组元素加1
                              *(lpDistAlpha+i*Alpha+k/2)=*(lpDistAlpha+i*Alpha+k/2)+1;
                                   TempLine=(MYLINE*)(lpMyLine+i*Alpha+k/2);
                                   if(y> (*TempLine).topy){
                                          //记录该直线最高点的x,y坐标
                                          (*TempLine).topx=x;
                                          (*TempLine).topy=y;
                                   }
                                   if(y< (*TempLine).boty){
                                          //记录该直线最低点的x,y坐标
                                          (*TempLine).botx=x;
                                          (*TempLine).boty=y;
                                   }
                            }
}
       maxd=0;
       for (i=0;i<(long)Dist*Alpha;i++){
              TempLine=(MYLINE*)(lpMyLine+i);
              k=*(lpDistAlpha+i);
              if(k > maxd){
                     //找到数组元素中最大的，及相应的直线端点
                     maxd=k;
                     MaxdLine.topx=(*TempLine).topx;
                     MaxdLine.topy=(*TempLine).topy;
                     MaxdLine.botx=(*TempLine).botx;
                     MaxdLine.boty=(*TempLine).boty;
              }
       }
       hDc = GetDC(hWnd);
       rhp = CreatePenIndirect(&rlp);
       SelectObject(hDc,rhp);
       MoveToEx(hDc,MaxdLine.botx,MaxdLine.boty,NULL);
       //在两端点之间画一条红线用来标识
       LineTo(hDc,MaxdLine.topx,MaxdLine.topy);
      DeleteObject(rhp);                      
      ReleaseDC(hWnd,hDc);
       //释放内存及资源
       GlobalUnlock(hImgData);
GlobalUnlock(hDistAlpha);
       GlobalFree(hDistAlpha);
     GlobalUnlock(hMyLine);
       GlobalFree(hMyLine);
       return TRUE;
}
如果 是给定的，用上述方法，我们可以找到该方向上最长的直线。
7.3 轮廓提取
轮廓提取的实例如图7.9、图7.10所示。

图7.9     原图

图7.10   轮廓提取
轮廓提取的算法非常简单，就是掏空内部点：如果原图中有一点为黑，且它的8个相邻点都是黑色时(此时该点是内部点)，则将该点删除。要注意的是，我们处理的虽然是二值图，但实际上是256级灰度图，不过只用到了0和255两种颜色。源程序如下：
BOOL Outline(HWND hWnd)
{
       DWORD                             OffBits,BufSize;
     LPBITMAPINFOHEADER    lpImgData;
       LPSTR                   lpPtr;
HLOCAL                             hTempImgData;
       LPBITMAPINFOHEADER    lpTempImgData;
       LPSTR                   lpTempPtr;
       HDC                      hDc;
       HFILE                     hf;
       LONG                    x,y;
       int                                        num;
       int                               nw,n,ne,w,e,sw,s,se;
//我们处理的实际上是256级灰度图，不过只用到了0和255两种颜色。
if( NumColors!=256){
MessageBox(hWnd,"Must be a mono bitmap with grayscale palette!",
"Error Message",MB_OK|MB_ICONEXCLAMATION);
return FALSE;
}
OffBits=bf.bfOffBits-sizeof(BITMAPFILEHEADER);
//BufSize为缓冲区大小
       BufSize=OffBits+bi.biHeight*LineBytes;
       //为新图缓冲区分配内存
       if((hTempImgData=LocalAlloc(LHND,BufSize))==NULL)
   {
            MessageBox(hWnd,"Error alloc memory!","Error Message",MB_OK|
MB_ICONEXCLAMATION);
return FALSE;
    }
     lpImgData=(LPBITMAPINFOHEADER)GlobalLock(hImgData);   
       lpTempImgData=(LPBITMAPINFOHEADER)LocalLock(hTempImgData);
//拷贝头信息和位图数据
       memcpy(lpTempImgData,lpImgData,BufSize);
       for (y=1;y<bi.biHeight-1;y++){ //注意y的范围是从1到高度-2
              //lpPtr指向原图数据，lpTempPtr指向新图数据
              lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes);
              lpTempPtr=(char *)lpTempImgData+(BufSize-LineBytes-y*LineBytes);
              for (x=1;x<bi.biWidth-1;x++){
                     if(*(lpPtr+x)==0){ //是个黑点
                            //查找八个相邻点
                            nw=(unsigned char)*(lpPtr+x+LineBytes-1);
                            n=(unsigned char)*(lpPtr+x+LineBytes);
                            ne=(unsigned char)*(lpPtr+x+LineBytes+1);
                            w=(unsigned char)*(lpPtr+x-1);
                            e=(unsigned char)*(lpPtr+x+1);
                            sw=(unsigned char)*(lpPtr+x-LineBytes-1);
                            s=(unsigned char)*(lpPtr+x-LineBytes);
                            se=(unsigned char)*(lpPtr+x-LineBytes+1);
                            num=nw+n+ne+w+e+sw+s+se;
                            if(num==0) //说明都是黑点
                                   *(lpTempPtr+x)=(unsigned char)255; //删除该黑点
                     }
              }
       }
     if(hBitmap!=NULL)
           DeleteObject(hBitmap);
       hDc=GetDC(hWnd);    
       //创立一个新的位图
       hBitmap=CreateDIBitmap(hDc,(LPBITMAPINFOHEADER)lpTempImgData,
(LONG)CBM_INIT,
(LPSTR)lpTempImgData+
sizeof(BITMAPINFOHEADER)+
NumColors*sizeof(RGBQUAD),
(LPBITMAPINFO)lpTempImgData,
DIB_RGB_COLORS);
hf=_lcreat("c:\\outline.bmp",0);
       _lwrite(hf,(LPSTR)&bf,sizeof(BITMAPFILEHEADER));
       _lwrite(hf,(LPSTR)lpTempImgData,BufSize);
       _lclose(hf);
       //释放内存和资源
      ReleaseDC(hWnd,hDc);
       LocalUnlock(hTempImgData);
       LocalFree(hTempImgData);
       GlobalUnlock(hImgData);
       return TRUE;
}