边沿检测与提取,轮廓跟踪与Hough变换

1、边沿检测与提取，轮廓跟踪首先,引入了模板操作。边沿检测我们给出一个模板 和一幅图象 。不难发现原图中左边暗，右边亮，中间存在着一条明显的边界。进行模板操作后的结果如下： 。可以看出，第3、4列比其他列的灰度值高很多，人眼观察时，就能发现一条很明显的亮边，其它区域都很暗，这样就起到了边沿检测的作用。为什么会这样呢？仔细看看那个模板就明白了，它的意思是将右邻点的灰度值减左邻点的灰度值作为该点的灰度值。在灰度相近的区域内，这么做的结果使得该点的灰度值接近于0；而在边界附近，灰度值有明显的跳变，这么做的结果使得该点的灰度值很大，这样就出现了上面的结果。这种模板就是一种边沿检测器，它在数学上的涵义是一种

2、基于梯度的滤波器，又称边沿算子，你没有必要知道梯度的确切涵义，只要有这个概念就可以了。梯度是有方向的，和边沿的方向总是正交(垂直)的，例如，对于上面那幅图象的转置图象，边是水平方向的，我们可以用梯度是垂直方向的模板 检测它的边沿。例如，一个梯度为45度方向模板 ，可以检测出135度方向的边沿。1. Sobel算子在边沿检测中，常用的一种模板是Sobel 算子。Sobel 算子有两个，一个是检测水平边沿的 ；另一个是检测垂直平边沿的 。与 和 相比，Sobel算子对于象素的位置的影响做了加权，因此效果更好。Sobel算子另一种形式是各向同性Sobel(Isotropic Sobel)算子，也有两

3、个，一个是检测水平边沿的 ，另一个是检测垂直平边沿的 。各向同性Sobel算子和普通Sobel算子相比，它的位置加权系数更为准确，在检测不同方向的边沿时梯度的幅度一致。下面的几幅图中，图7.1为原图；图7.2为普通Sobel算子处理后的结果图；图7.3为各向同性Sobel算子处理后的结果图。可以看出Sobel算子确实把图象中的边沿提取了出来。图7.1 原图图7.2 普通Sobel算子处理后的结果图图7.3 各向同性Sobel算子处理后的结果图在程序中仍然要用到第3章介绍的通用33模板操作函数TemplateOperation，所做的操作只是增加几个常量标识及其对应的模板数组，这里就不再给出了。

4、2. 高斯拉普拉斯算子由于噪声点(灰度与周围点相差很大的点)对边沿检测有一定的影响，所以效果更好的边沿检测器是高斯拉普拉斯(LOG)算子。它把我们在第3章中介绍的高斯平滑滤波器和拉普拉斯锐化滤波器结合了起来，先平滑掉噪声，再进行边沿检测，所以效果会更好。常用的LOG算子是55的模板，如下所示 。到中心点的距离与位置加权系数的关系用曲线表示为图7.4。是不是很象一顶墨西哥草帽？所以，LOG又叫墨西哥草帽滤波器。图7.4 LOG到中心点的距离与位置加权系数的关系曲线图7.5为图7.1用LOG滤波器处理后的结果。图7.5 图7.1用LOG滤波器处理后的结果图LOG的算法和普通模板操作的算法没什么不同

5、，只不过把33改成了55，这里就不再给出了。读者可以参照第3章的源程序自己来完成。Hough变换Hough变换用来在图象中查找直线。它的原理很简单：假设有一条与原点距离为s，方向角为的一条直线，如图7.6所示。图7.6 一条与原点距离为s，方向角为的一条直线直线上的每一点都满足方程(7.1)利用这个事实，我们可以找出某条直线来。下面将给出一段程序，用来找出图象中最长的直线(见图7.7)。找到直线的两个端点，在它们之间连一条红色的直线。为了看清效果，将结果描成粗线，如图7.8所示。图7.7 原图图7.8 Hough变换的结果可以看出，找到的确实是最长的直线。方法是，开一个二维数组做为计数器，第一

6、维是角度，第二维是距离。先计算可能出现的最大距离为 ，用来确定数组第二维的大小。对于每一个黑色点，角度的变化范围从00到1780(为了减少存储空间和计算时间，角度每次增加20而不是10)，按方程(7.1)求出对应的距离s来，相应的数组元素s 加1。同时开一个数组Line，计算每条直线的上下两个端点。所有的象素都算完后，找到数组元素中最大的，就是最长的那条直线。直线的端点可以在Line中找到。要注意的是，我们处理的虽然是二值图，但实际上是256级灰度图，不过只用到了0和255两种颜色。BOOL Hough(HWND hWnd)/定义一个自己的直线结构 typedef struct int top

7、x; /最高点的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_

8、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=

9、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(hDistAlph

10、a); 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*

11、)(lpMyLine+i); (*TempLine).boty=32767; /初始化最低点的y坐标为一个很大的值 for (y=0;ybi.biHeight;y+) /lpPtr指向位图数据 lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes); for (x=0;xbi.biWidth;x+) if(*(lpPtr+)=0) /是个黑点 for (k=0;k (*TempLine).topy) /记录该直线最高点的x,y坐标 (*TempLine).topx=x; (*TempLine).topy=y; if(y (*TempLin

12、e).boty) /记录该直线最低点的x,y坐标 (*TempLine).botx=x; (*TempLine).boty=y; maxd=0; for (i=0;i 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); Sel

13、ectObject(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 T

14、RUE;如果 是给定的，用上述方法，我们可以找到该方向上最长的直线。其实Hough变换能够查找任意的曲线，只要你给定它的方程。这里，我们就不详述了。轮廓提取轮廓提取的实例如图7.9、图7.10所示。图7.9 原图图7.10 轮廓提取轮廓提取的算法非常简单，就是掏空内部点：如果原图中有一点为黑，且它的8个相邻点都是黑色时(此时该点是内部点)，则将该点删除。要注意的是，我们处理的虽然是二值图，但实际上是256级灰度图，不过只用到了0和255两种颜色。源程序如下：BOOL Outline(HWND hWnd) DWORD OffBits,BufSize; LPBITMAPINFOHEADER lpI

15、mgData; 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_ICONEXC

16、LAMATION);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=(LPBITMAPINFOHEADE

17、R)GlobalLock(hImgData); lpTempImgData=(LPBITMAPINFOHEADER)LocalLock(hTempImgData);/拷贝头信息和位图数据 memcpy(lpTempImgData,lpImgData,BufSize); for (y=1;ybi.biHeight-1;y+) /注意y的范围是从1到高度-2 /lpPtr指向原图数据，lpTempPtr指向新图数据 lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes); lpTempPtr=(char *)lpTempImgData+(Bu

18、fSize-LineBytes-y*LineBytes); for (x=1;x=SeedFillStack.ElementsNum) return FALSE; /栈已满，返回FALSE /进栈，栈顶指针加1 TempPtr=(POINT *)(SeedFillStack.lpMyStack+SeedFillStack.ptr+); (*TempPtr).x=p.x; (*TempPtr).y=p.y; return TRUE;/pop操作POINT MyPop() POINT InvalidP; InvalidP.x=-1; InvalidP.y=-1; if(SeedFillStack.

19、ptr0) /注意判断边界 NeighborP.x=CurP.x-1; NeighborP.y=CurP.y; lpTempPtr1=lpTempPtr-1; if(*lpTempPtr1!=0) /如果为白，表示还没有填，进栈 MyPush(NeighborP); /上邻点 if(CurP.y0) /注意判断边界 NeighborP.x=CurP.x; NeighborP.y=CurP.y-1; lpTempPtr1=lpTempPtr+LineBytes; if(*lpTempPtr1!=0) /如果为白，表示还没有填，进栈 MyPush(NeighborP); /右邻点 if(CurP.

20、xbi.biWidth-1) /注意判断边界 NeighborP.x=CurP.x+1; NeighborP.y=CurP.y; lpTempPtr1=lpTempPtr+1; if(*lpTempPtr1!=0) /如果为白，表示还没有填，进栈 MyPush(NeighborP); /下邻点 if(CurP.ybi.biHeight-1) /注意判断边界 NeighborP.x=CurP.x; NeighborP.y=CurP.y+1; lpTempPtr1=lpTempPtr-LineBytes; if(*lpTempPtr1!=0) /如果为白，表示还没有填，进栈 MyPush(Neig

21、hborP); /析构堆栈，释放内存 DeInitStack();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=_lcre

22、at(c:seed.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;轮廓跟踪轮廓跟踪，顾名思义就是通过顺序找出边缘点来跟踪出边界。图7.9经轮廓跟踪后得到的结果如图7.11所示。图7.11

23、图7.9轮廓跟踪后的结果一个简单二值图象闭合边界的轮廓跟踪算法很简单：首先按从上到下，从左到右的顺序搜索，找到的第一个黑点一定是最左上方的边界点，记为A。它的右，右下，下，左下四个邻点中至少有一个是边界点，记为B。从开始B找起，按右，右下，下，左下，左，左上，上，右上的顺序找相邻点中的边界点C。如果C就是A点，则表明已经转了一圈，程序结束；否则从C点继续找，直到找到A为止。判断是不是边界点很容易：如果它的上下左右四个邻居都是黑点则不是边界点，否则是边界点。源程序如下，其中函数IsContourP用来判断某点是不是边界点。BOOL Contour(HWND hWnd) DWORD OffBits

24、，BufSize;LPBITMAPINFOHEADER lpImgData; LPSTR lpPtr; HLOCAL hTempImgData; LPBITMAPINFOHEADER lpTempImgData; LPSTR lpTempPtr; HDC hDc; HFILE hf; LONG x,y; POINT StartP,CurP; BOOL found; int i;int direct82=1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1;/我们处理的实际上是256级灰度图，不过只用到了0和255两种颜色。 if( NumColors!=256)Messa

25、geBox(hWnd,Must be a mono bitmap with grayscale palette!,Error Message,MB_OK|MB_ICONEXCLAMATION);return FALSE;/到位图数据的偏移值 OffBits=bf.bfOffBits-sizeof(BITMAPFILEHEADER); /缓冲区大小BufSize=OffBits+bi.biHeight*LineBytes;/为新图缓冲区分配内存 if(hTempImgData=LocalAlloc(LHND,BufSize)=NULL) MessageBox(hWnd,Error alloc m

26、emory!,Error Message,MB_OK|MB_ICONEXCLAMATION);return FALSE; lpImgData=(LPBITMAPINFOHEADER)GlobalLock(hImgData); lpTempImgData=(LPBITMAPINFOHEADER)LocalLock(hTempImgData); /新图缓冲区初始化为255 memset(lpTempImgData,(BYTE)255,BufSize); /拷贝头信息 memcpy(lpTempImgData,lpImgData,OffBits); /找到标志置为假 found=FALSE; for

27、 (y=0;ybi.biHeight & !found; y+) lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes); for (x=0;xbi.biWidth & !found; x+) if (*(lpPtr+) =0) found=TRUE; /找到了最左上的黑点，一定是个边界点 if(found) /如果找到了，才做处理/从循环退出时，x，y坐标都做了加1的操作。在这里把它们减1，得到/起始点坐标StartP StartP.x=x-1; StartP.y=y-1; lpTempPtr=(char*)lpTempImgData+(BufSize-LineBytes-StartP.y*LineBytes)+StartP.x; *lpTempPtr=(unsigned char)0; /起始点涂黑 /右邻点 CurP.x=StartP.x+1; CurP.y=StartP.