第7章边沿检测与提取,轮廓跟踪 我们在第三章介绍平滑与锐化时引入了模板操作,今天还要用到它 71边沿检测 001255254254254 111254253254254 000255255253253 我们给出一个模板[10.1]和幅图象[11025424254254」。不难发 现原图中左边暗,右边亮,中间存在着一条明显的边界。进行模板操作后的结果如下: 「x1255253-10 2532520 x0255255-2-2x x-125325400x 可以看出,第3、4列比其他列的灰度值高很多,人眼观察时,就能发现一条很明显的亮边, 其它区域都很暗,这样就起到了边沿检测的作用 为什么会这样呢?仔细看看那个模板就明白了,它的意思是将右邻点的灰度值减左邻点的灰 度值作为该点的灰度值。在灰度相近的区域内,这么做的结果使得该点的灰度值接近于0; 而在边界附近,灰度值有明显的跳变,这么做的结果使得该点的灰度值很大,这样就出现了 上面的结果。 这种模板就是一种边沿检测器,它在数学上的涵义是一种基于梯度的滤波器,又称边沿算子, 你没有必要知道梯度的确切涵义,只要有这个概念就可以了。梯度是有方向的,和边沿的方 向总是正交(垂直)的,例如,对于上面那幅图象的转置图象,边是水平方向的,我们可以用 梯度是垂直方向的模板L]检测它的边沿 10 例如,一个梯度为45度方向模板01,可以检测出135度方向的边沿。 1.Sobl算子
第 7 章 边沿检测与提取,轮廓跟踪 我们在第三章介绍平滑与锐化时引入了模板操作,今天还要用到它。 7.1 边沿检测 我们给出一个模板 和一幅图象 。不难发 现原图中左边暗,右边亮,中间存在着一条明显的边界。进行模板操作后的结果如下: 。 可以看出,第 3、4 列比其他列的灰度值高很多,人眼观察时,就能发现一条很明显的亮边, 其它区域都很暗,这样就起到了边沿检测的作用。 为什么会这样呢?仔细看看那个模板就明白了,它的意思是将右邻点的灰度值减左邻点的灰 度值作为该点的灰度值。在灰度相近的区域内,这么做的结果使得该点的灰度值接近于 0; 而在边界附近,灰度值有明显的跳变,这么做的结果使得该点的灰度值很大,这样就出现了 上面的结果。 这种模板就是一种边沿检测器,它在数学上的涵义是一种基于梯度的滤波器,又称边沿算子, 你没有必要知道梯度的确切涵义,只要有这个概念就可以了。梯度是有方向的,和边沿的方 向总是正交(垂直)的,例如,对于上面那幅图象的转置图象,边是水平方向的,我们可以用 梯度是垂直方向的模板 检测它的边沿。 例如,一个梯度为 45 度方向模板 ,可以检测出 135 度方向的边沿。 1. Sobel 算子
在边沿检测中,常用的一种模板是 Sobel算子。 Sobel算子有两个,一个是检测水平边沿的 10 20.2 0 121:另一个是检测垂直平边沿的-12 10 10 相比, Sobel算子对于象素的位置的影响做了加权,因此效果更好。 Sobel算子另一种形式是各向同性 Sobel(lsotropic Sobel)算子,也有两个,一个是检测水平边 00 √20√2 1√21 沿的 另一个是检测垂直平边沿的-101 各向同性 Sobel 算子和普通 Sobel算子相比,它的位置加权系数更为准确,在检测不同方向的边沿时梯度的 幅度一致 下面的几幅图中,图71为原图:图72为普通 Sobel算子处理后的结果图:图73为各向同 性 Sobel算子处理后的结果图。可以看出 Sobel算子确实把图象中的边沿提取了出来。 图71原图 图72普通Sobe算子处理后的结果图
在边沿检测中,常用的一种模板是 Sobel 算子。Sobel 算子有两个,一个是检测水平边沿的 ;另一个是检测垂直平边沿的 。与 和 相比,Sobel 算子对于象素的位置的影响做了加权,因此效果更好。 Sobel 算子另一种形式是各向同性 Sobel(Isotropic Sobel)算子,也有两个,一个是检测水平边 沿的 ,另一个是检测垂直平边沿的 。各向同性 Sobel 算子和普通 Sobel 算子相比,它的位置加权系数更为准确,在检测不同方向的边沿时梯度的 幅度一致。 下面的几幅图中,图 7.1 为原图;图 7.2 为普通 Sobel 算子处理后的结果图;图 7.3 为各向同 性 Sobel 算子处理后的结果图。可以看出 Sobel 算子确实把图象中的边沿提取了出来。 图 7.1 原图 图 7.2 普通 Sobel 算子处理后的结果图
图73各向同性 Sobel算子处理后的结果图 在程序中仍然要用到第3章介绍的通用3×3模板操作函数 TemplateOperation,所做的操作 只是增加几个常量标识及其对应的模板数组,这里就不再给出了。 2.高斯拉普拉斯算子 由于噪声点(灰度与周围点相差很大的点)对边沿检测有一定的影响,所以效果更好的边沿检 测器是高斯拉普拉斯(LOG算子。它把我们在第3章中介绍的高斯平滑滤波器和拉普拉斯锐 化滤波器结合了起来,先平滑掉噪声,再进行边沿检测,所以效果会更妇 4080 24.8-24 4080-4 常用的1OG算子是5×5的模板,如下所示[2-4-4-4-2]。到中心点的距 离与位置加权系数的关系用曲线表示为图74。是不是很象一顶墨西哥草帽?所以,LOG又 叫墨西哥草帽滤波器 图74LOG到中心点的距离与位置加权系数的关系曲线 图75为图71用LOG滤波器处理后的结果
图 7.3 各向同性 Sobel 算子处理后的结果图 在程序中仍然要用到第 3 章介绍的通用 3×3 模板操作函数 TemplateOperation,所做的操作 只是增加几个常量标识及其对应的模板数组,这里就不再给出了。 2. 高斯拉普拉斯算子 由于噪声点(灰度与周围点相差很大的点)对边沿检测有一定的影响,所以效果更好的边沿检 测器是高斯拉普拉斯(LOG)算子。它把我们在第 3 章中介绍的高斯平滑滤波器和拉普拉斯锐 化滤波器结合了起来,先平滑掉噪声,再进行边沿检测,所以效果会更好。 常用的 LOG 算子是 5×5 的模板,如下所示 。到中心点的距 离与位置加权系数的关系用曲线表示为图 7.4。是不是很象一顶墨西哥草帽?所以,LOG 又 叫墨西哥草帽滤波器。 图 7.4 LOG 到中心点的距离与位置加权系数的关系曲线 图 7.5 为图 7.1 用 LOG 滤波器处理后的结果
图75图7.1用LOG滤波器处理后的结果图 LOG的算法和普通模板操作的算法没什么不同,只不过把3×3改成了5×5,这里就不再 给出了。读者可以参照第3章的源程序自己来完成。 72 Hough变换 Hough变换用来在图象中查找直线。它的原理很简单:假设有一条与原点距离为s,方向角 为θ的一条直线,如图76所示。 图76一条与原点距离为s,方向角为的一条直线 直线上的每一点都满足方程 s=xcos日+ysin日 利用这个事实,我们可以找出某条直线来。下面将给出一段程序,用来找出图象中最长的直 线(见图77)。找到直线的两个端点,在它们之间连一条红色的直线。为了看清效果,将结 果描成粗线,如图7.8所示
图 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 所示
图77原图 图78 Hough变换的结果 可以看出,找到的确实是最长的直线。方法是,开一个二维数组做为计数器,第一维是角度, 第二维是距离。先计算可能出现的最大距离为√th2+aght2,用来确定数组第二维 的大小。对于每一个黑色点,角度的变化范围从0到178(为了减少存储空间和计算时间, 角度每次增加2而不是1),按方程(71)求出对应的距离s来,相应的数组元素s加1。 同时开一个数组Line,计算每条直线的上下两个端点。所有的象素都算完后,找到数组元 素中最大的,就是最长的那条直线。直线的端点可以在Line中找到。要注意的是,我们处 理的虽然是二值图,但实际上是256级灰度图,不过只用到了0和255两种颜色。 BOOL Hough(HWND hWnd ∥定义一个自己的直线结构 typedef structi nt topx;/最高点的x坐标 nt topy,∥最高点的y坐标 nt botx,∥最低点的ⅹ坐标 nt boty,∥最低点的y坐标 I MYLINE DWORD OffBits BufS ize LPBITMAPINFOHEADER lplmg Data LPSTR HDC LONO HGLOBAL hDist Alpha, h MyLine IpDistalpha
图 7.7 原图 图 7.8 Hough 变换的结果 可以看出,找到的确实是最长的直线。方法是,开一个二维数组做为计数器,第一维是角度, 第二维是距离。先计算可能出现的最大距离为 ,用来确定数组第二维 的大小。对于每一个黑色点,角度的变化范围从 0 0 到 1780 (为了减少存储空间和计算时间, 角度每次增加 2 0 而不是 1 0 ),按方程(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 IpMyLine, TempLine, MaxdLine tic hogPeN rlp=(PS SOLID, 1, 1, RGB(255,0,0)1 HEN ∥我们处理的实际上是256级灰度图,不过只用到了0和255两种颜色。 if( Num Colors!=256)1 Message Box(hWnd, "Must be a mono bitmap with grayscale palette Error Message", MB OKMB ICONEXCLAMATION) return False ∥计算最大距离 Dist=(int (sqrt((double)bi. biwidth*bi bi Width+ (double)bi. biHeight*bi. biHeight)+0.5) Alpha=180/2;∥0到to178度,步长为2度 ∥距离角度数组分配内存 f((hDist Alpha=GlobalAlloc(GHnd, (DWORD)Dist*Alpha* sizeof(int)))=NULL)( Message Box(hWnd, Error alloc memory! " "Error Message" MB OKJMB ICONEXCLAMATION) return False ∥.记录直线端点的数组分配内存 if(hMyLine=GlobalAlloc( GHND, (DWORDDist*Alpha* sizeof(MYLINEDD)==NULL)i return false OffBitsbf. bfOffBits-sizeof(BITMAPFILEHEADER) upSize为缓冲区大小 BufSize=offBits+bi bi Height* Line Bytes Iplmg Data=(LPBITMAPINFOHEADER)GlobalLock(hlmg Data) IpDist alpha=(int)GlobalLock(hDistAlpha) IpMyline=( for(i=0; i<(long)Dist"Alpha, 1++) TempLine=( MYLINE*)(pMyLine-+i); (* Templin),boty=32767,∥初始化最低点的y坐标为一个很大的值 for(y=0; y<bi bi Height; y++)i pPur指向位图数据
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 指向位图数据
IpPtr=(char *)lplmg Data+(BufSize-LineBytes-y*Line Bytes) for(x=0; X("*TempLine) topy)i 记录该直线最高点的x,y坐标 *TempLin).topx-x, (TempLin). topy=y if(y maxd) ∥找到数组元素中最大的,及相应的直线端点 MaxdLine. topx=("TempLine)topx MaxdLine. topy=(*TempLine) topy MaxdLine. botx=("TempLine) botx Line. boty=( TempLine hDc= GetDC(hwnd) rhp= CreatePenIndirect(&rlp) MoveToEx(hDc, MaxdLine botx, MaxdLine. boty, NULL
lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes); for (x=0;x (*TempLine).topy){ //记录该直线最高点的 x,y 坐标 (*TempLine).topx=x; (*TempLine).topy=y; } if(y 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);
∥在两端点之间画一条红线用来标识 Line To(hDc, MaxdLine. topx, MaxdLine. topy) DeleteObject(rhp) Released(hwnd, hDc) ∥释放内存及资源 Global Unlock(hmg Data GlobalUnl suLpha) Global Free(hDist Alpha); GlobalUnlock(hMyLine) Global Free(hMy Line) return TRUe 如果6是给定的,用上述方法,我们可以找到该方向上最长的直线 其实 Hough变换能够查找任意的曲线,只要你给定它的方程。这里,我们就不详述了。 73轮廓提取 轮廓提取的实例如图79、图7.10所示 图79原图 图7.10轮廓提取 轮廓提取的算法非常简单,就是掏空内部点:如果原图中有一点为黑,且它的8个相邻点都 是黑色时(此时该点是内部点),则将该点删除。要注意的是,我们处理的虽然是二值图,但 实际上是256级灰度图,不过只用到了0和255两种颜色。源程序如下 BOOL Outline(HWND hWnd) DWORD OffBits BufSize LPBITMAPINFOHEADER lplmg Data LPSTR IpPr HLOCAL hTemplmg Data LPBITMAPINFOHEADER IpTemplmg Data LPSTR Ip TempPtr
//在两端点之间画一条红线用来标识 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 E LONG num ∥我们处理的实际上是256级灰度图,不过只用到了0和255两种颜色。 if( n Message Box(hWnd, "Must be a mono bitmap with grayscale palette Error Message", MB OK MB ICONEXCLAMATION) OffBits-bf. bfOffBits-sizeof( BITMAPFILEHEADER) BufSize为缓冲区大小 Bufsize=offBits+bi. biHeight" Line Bytes, ∥.新图缓冲区分配内存 if((hTemplmg Data=LocalAlloc(LHND, BufSize)==NULL) Message Box(hWnd, "Error alloc memory! "," Error Message", MB OK MB ICONEXCLAMATION return False lplmg Data=(LPBITMAPINFOHEADER)GlobalLock(hlmg Data) IpTemplmg Data=(LPBITMAPINFOHEADER)LocalLock(hTemplmg Data); ∥拷贝头信息和位图数据 memcpy(lp Templmg Data, lplmg Data, BufSize); for(y=ly<bi. biWeight-ly++){/注意y的范围是从1到高度2 ∥pPr指向原图数据, IpTempPtr指向新图数据 lpPtr=(char *)lplmg Data+( BufSize-LineBytes-y*Line Bytes) lpTempPtr=(char *)p Templmg Data+( BufSize-LineBytes-y*Line Bytes) for(x=1; x<bibi Width-1; x++)i f(*(lpP+x)=0){∥/是个黑点 ∥找八个相邻点 (unsigned char )*(IpPtrx+Line Bytes-1); (unsigned char) *(lpPtr+x+Line Bytes) ne=(unsigned char )(IpPtr+x+LineBytes+1); (unsigned char) *(lpPtr+x-1); w=(unsigned char )*(IpPtr+x-LineBytes-1);
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 )(pPtr+x-Line Bytes) se=(unsigned char)"(pPtr+x-LineBytes+ 1); num=nwtn+ne+w+e+sw+s+se if(num=0)∥说明都是黑点 ( pTempPtr+x)=( unsigned char)255;∥删除该黑点 if(hBitmapl=NULL hDc=GetDC(hWnd) ∥)创立一个新的位图 hBitmap=CreateDIBitmap(hDc, (LPBITMAPINFOHEADER)IpTemplmg Data (LONG)CBM INIT ( LPSTR)lp Templmg Data+ sizeof( BITMAPINFOHEADER)+ Num Colors*sizeof(RGBQUAD) (LPBITMAPINFO)IpTemplmg Data DIB RGB COLORS) hf- Creat("c: \\outline. bmp",0) I write(hf, (LPSTR)&bf, sizeof( BITMAPFILEHEADER)) Iwrite(hf, (LPSTR)IpTemplmg Data, BufSize Iclose(hf) 释放内存和资源 Released(hWnd, hDc) Local Unlock (hTemplmg Data); Local Free(hTemplmg Data) Global Unlock(hmg Data) return tRUe 74种子填充 种子填充算法用来在封闭曲线形成的环中填充某中颜色,在这里我们只填充黑色 种子填充其实上是图形学中的算法,其原理是:准备一个堆栈,先将要填充的点push进堆 栈中;以后,每pop出一个点,将该点涂成黑色,然后按左上右下的顺序查看它的四个相邻 点,若为白(表示还没有填充),则将该邻点push进栈。一直循环,直到堆栈为空。此时, 区域内所有的点都被涂成了黑色
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 进栈。一直循环,直到堆栈为空。此时, 区域内所有的点都被涂成了黑色