第7章 边沿检测与提取，轮廓跟踪 我们在第三章介绍平滑与锐化时引入了模板操作，今天还要用到它。 7.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; } 如果 是给定的，用上述方法，我们可以找到该方向上最长的直线。 其实Hough变换能够查找任意的曲线，只要你给定它的方程。这里，我们就不详述了。 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; } 7.4 种子填充 种子填充算法用来在封闭曲线形成的环中填充某中颜色，在这里我们只填充黑色。 种子填充其实上是图形学中的算法，其原理是：准备一个堆栈，先将要填充的点push进堆栈中；以后，每pop出一个点，将该点涂成黑色，然后按左上右下的顺序查看它的四个相邻点，若为白(表示还没有填充)，则将该邻点push进栈。一直循环，直到堆栈为空。此时，区域内所有的点都被涂成了黑色。 这里，我们自己定义了一些堆栈的数据结构和操作，实现了堆栈的初始化、push、pop、判断是否为空、及析构。 //堆栈结构 typedef struct{ ????????????? ? HGLOBAL hMem; //堆栈全局内存句柄 ? ?????????? ??POINT *lpMyStack; //指向该句柄的指针 ????????????? ? LONG? ElementsNum; //堆栈的大小 ????????????? ? LONG? ptr; //指向栈顶的指针 ????????????? ? }MYSTACK; //初始化堆栈的操作，第二个参数指定堆栈的大小 BOOL InitStack(HWND hWnd,LONG StackLen) { ?????? SeedFillStack.ElementsNum=StackLen; //将堆栈的大小赋值 ?????? if((SeedFillStack.hMem=GlobalAlloc(GHND,SeedFillStack.ElementsNum* sizeof(POINT)))==NULL) ?????? { ????????????? //内存分配错误，返回FALSE; ?? ? MessageBox(hWnd,"Error alloc memory!","ErrorMessage",MB_OK| MB_ICONEXCLAMATION); ????????????? return FALSE; ?????? } ?????? SeedFillStack.lpMyStack=(POINT *)GlobalLock(SeedFillStack.hMem); ?????? //缓冲区全部清零 memset(SeedFillStack.lpMyStack,0,SeedFillStack.ElementsNum* sizeof(POINT)); //堆顶指针为零 ?????? SeedFillStack.ptr=0; ?????? //成功，返回TRUE ?????? return TRUE; } //析构函数 void DeInitStack() { ?????? //释放内存，重置堆栈大小及栈顶指针。 ?????? GlobalUnlock(SeedFillStack.hMem); ?????? GlobalFree(SeedFillStack.hMem); ?????? SeedFillStack.ElementsNum=0; ?????? SeedFillStack.ptr=0; } //push操作 BOOL MyPush(POINT p) { ?????? POINT *TempPtr; ?????? if(SeedFillStack.ptr>=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.ptr<=0) ????????????? return InvalidP; //栈为空，返回无效点 ?????? SeedFillStack.ptr--; //栈顶指针减1 ?????? //返回栈顶点 ?????? return *(SeedFillStack.lpMyStack+SeedFillStack.ptr); } //判断堆栈是否为空 BOOL IsStackEmpty() { ?????? return (SeedFillStack.ptr==0)?TRUE:FALSE; } 如果读者对堆栈的概念还不清楚，请参阅有关数据结构方面的书籍，这里就不详述了。 要注意的是：(1)要填充的区域是封闭的；(2)我们处理的虽然是二值图，但实际上是256级灰度图，不过只用到了0和255两种颜色；(3)在菜单中选择种子填充命令时，提示用户用鼠标点取一个要填充区域中的点，处理是在WM_LBUTTONDOWN中。 MYSTACK SeedFillStack; BOOL SeedFill(HWND hWnd) { DWORD?? ? ????????????? OffBits,BufSize; ?? ? LPBITMAPINFOHEADER??? lpImgData; ?????? HLOCAL???????????? ???? hTempImgData; ?????? LPBITMAPINFOHEADER??? lpTempImgData; ?????? LPSTR????????????? ???? lpTempPtr,lpTempPtr1; ?????? HDC????? ?????????? ????????????? ?????? hDc; ?????? HFILE????????????? ????? hf; ?????? POINT????????????? ???? CurP,NeighborP; //我们处理的实际上是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); ?????? if(!InitStack(hWnd,(LONG)bi.biHeight*bi.biWidth)){? //初始化堆栈 ????????????? //若失败，释放内存，返回 ????????????? LocalUnlock(hTempImgData); ????????????? LocalFree(hTempImgData); ????????????? GlobalUnlock(hImgData); ????????????? return FALSE; ?????? } ?????? lpTempPtr=(char*)lpTempImgData+ (BufSize-LineBytes-SeedPoint.y*LineBytes)+SeedPoint.x; ?????? if(*lpTempPtr==0){ ????????????? //鼠标点到了黑点上，提示用户不能选择边界上的点，返回FALSE MessageBox(hWnd,"The point you select is a contour point!", "Error Message",MB_OK|MB_ICONEXCLAMATION); ????????????? LocalUnlock(hTempImgData); ????????????? LocalFree(hTempImgData); ????????????? GlobalUnlock(hImgData); ????????????? DeInitStack(); return FALSE; ?????? } ?????? //push该点(用户用鼠标选择的，处理是在WM_LBUTTONDOWN中 ?????? MyPush(SeedPoint); ?????? while(!IsStackEmpty()) //堆栈不空则一直处理 ?????? { ????????????? CurP=MyPop(); //pop栈顶的点 ????????????? lpTempPtr=(char*)lpTempImgData+ (BufSize-LineBytes-CurP.y*LineBytes)+CurP.x; ????????????? //将该点涂黑 ????????????? *lpTempPtr=(unsigned char)0; ????????????? //左邻点 ????????????? if(CurP.x>0) //注意判断边界 ????????????? { ???????????????????? NeighborP.x=CurP.x-1; ???????????????????? NeighborP.y=CurP.y; ???????????????????? lpTempPtr1=lpTempPtr-1; ???????????????????? if(*lpTempPtr1!=0) //如果为白，表示还没有填，进栈 ??????????????????????????? MyPush(NeighborP); ????????????? } //上邻点 ????????????? if(CurP.y>0) //注意判断边界 ????????????? { ???????????????????? NeighborP.x=CurP.x; ???????????????????? NeighborP.y=CurP.y-1; ???????????????????? lpTempPtr1=lpTempPtr+LineBytes; ???????????????????? if(*lpTempPtr1!=0) //如果为白，表示还没有填，进栈 ??????????????????????????? MyPush(NeighborP); ????????????? } //右邻点 ????????????? if(CurP.x<bi.biWidth-1) //注意判断边界 ????????????? { ???????????????????? NeighborP.x=CurP.x+1; ???????????????????? NeighborP.y=CurP.y; ???????????????????? lpTempPtr1=lpTempPtr+1; ???????????????????? if(*lpTempPtr1!=0) //如果为白，表示还没有填，进栈 ??????????????????????????? MyPush(NeighborP); ????????????? } ????????????? //下邻点 ????????????? if(CurP.y<bi.biHeight-1) //注意判断边界 ????????????? { ???????????????????? NeighborP.x=CurP.x; ???????????????????? NeighborP.y=CurP.y+1; ???????????????????? lpTempPtr1=lpTempPtr-LineBytes; ???????????????????? if(*lpTempPtr1!=0) //如果为白，表示还没有填，进栈 ??????????????????????????? MyPush(NeighborP); ????????????? } ?????? } ?????? //析构堆栈，释放内存 ?????? 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=_lcreat("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.5 轮廓跟踪 轮廓跟踪，顾名思义就是通过顺序找出边缘点来跟踪出边界。图7.9经轮廓跟踪后得到的结果如图7.11所示。  图7.11??? 图7.9轮廓跟踪后的结果 一个简单二值图象闭合边界的轮廓跟踪算法很简单：首先按从上到下，从左到右的顺序搜索，找到的第一个黑点一定是最左上方的边界点，记为A。它的右，右下，下，左下四个邻点中至少有一个是边界点，记为B。从开始B找起，按右，右下，下，左下，左，左上，上，右上的顺序找相邻点中的边界点C。如果C就是A点，则表明已经转了一圈，程序结束；否则从C点继续找，直到找到A为止。判断是不是边界点很容易：如果它的上下左右四个邻居都是黑点则不是边界点，否则是边界点。源程序如下，其中函数IsContourP用来判断某点是不是边界点。 BOOL Contour(HWND hWnd) { ?????? DWORD? ??????????????????? ?????? OffBits，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?????? direct[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; //我们处理的实际上是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=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); ?????? //新图缓冲区初始化为255 ?????? memset(lpTempImgData,(BYTE)255,BufSize); ?????? //拷贝头信息 ?????? memcpy(lpTempImgData,lpImgData,OffBits); ?????? //找到标志置为假 ?????? found=FALSE; ?????? for (y=0;y<bi.biHeight && !found; y++){ ????????????? lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes); ????????????? for (x=0;x<bi.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.y; ????????????? lpPtr=(char *)lpImgData+(BufSize-LineBytes-CurP.y*LineBytes)+CurP.x; ????????????? if(*lpPtr!=0){ //若右邻点为白，则找右下邻点 ?????? ?? ???????? CurP.x=StartP.x+1; ???????????????????? CurP.y=StartP.y+1; ???????????????????? lpPtr=(char*)lpImgData+ (BufSize-LineBytes-CurP.y*LineBytes)+CurP.x; ???????????????????? if(*lpPtr!=0){ //若仍为白，则找下邻点 ?????? ?? ??????????????? CurP.x=StartP.x; ??????????????????????????? CurP.y=StartP.y+1; ???????????????????? } ???????????????????? else{ //若仍为白，则找左下邻点 ?????? ?? ??????????????? CurP.x=StartP.x-1; ??????????????????????????? CurP.y=StartP.y+1; ???????????????????? } ????????????? } ????????????? while (! ( (CurP.x==StartP.x) &&(CurP.y==StartP.y))){ //知道找到起始点， //循环才结束 ???????????????????? lpTempPtr=(char*)lpTempImgData+ (BufSize-LineBytes-CurP.y*LineBytes)+CurP.x; ???????????????????? *lpTempPtr=(unsigned char)0; ???????????????????? for(i=0;i<8;i++){ //按右，右上，上，左上，左，左下，下，右下的顺序找相邻点 //direct[i]中存放的是该方向x,y的偏移值 ??????????????????????????? x=CurP.x+direct[i][0]; ??????????????????????????? y=CurP.y+direct[i][1]; ????????????? //lpPtr指向原图数据，lpTempPtr指向新图数据 ??????????????????????????? lpTempPtr=(char*)lpTempImgData+ (BufSize-LineBytes-y*LineBytes)+x; ??????????????????????????? lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes)+x; ??????????????????????????? if(((*lpPtr==0)&&(*lpTempPtr!=0))|| ((x==StartP.x)&&(y==StartP.y))) ??????????????????????????? //原图中为黑点，且新图中为白点(表示还没搜索过)时才处理 ??????????????????????????? //另一种可能是找到了起始点 ??????????????????????????? ?????? if(IsContourP(x,y,lpPtr)){ //若是个边界点 ?????????????????????????????????? ?????? //记住当前点的位置 ??????????????????????????? CurP.x=x; ????????????????????????????????????????? CurP.y=y; ????????????????????????????????????????? break; ?????????????????????????????????? } ???????????????????? } ????????????? } ?????? } ? ??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:\\contour.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; } //判断某点是不是边界点，参数x,y 为该点坐标，lpPtr为指向原数据的指针 BOOL IsContourP(LONG x,LONG y, char *lpPtr) { ?????? int??? num,n,w,e,s; ?????? n=(unsigned char)*(lpPtr+LineBytes); //上邻点 ?????? w=(unsigned char)*(lpPtr-1); //左邻点 ?????? e=(unsigned char)*(lpPtr+1); //右邻点 ?????? s=(unsigned char)*(lpPtr-LineBytes); //下邻点 ?????? num=n+w+e+s; ?????? if(num==0) //全是黑点，说明是个内部点而不是边界点 ????????????? return FALSE; ?????? return TRUE; } The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees