第8章 图象的检测及模板匹配 图象的分割与检测(识别)实际上是一项非常困难的工作。很难说清楚为什么图象应该分割成这样而不是那样。人类的视觉系统是非常优越的，它不仅包含了双眼，还包括了大脑，可以从很复杂的景物中分开并识别每个物体，甚至可以毫不费力地跟上每秒好几十帧变化的图象。举两个例子来说明一下人类视觉系统的优越性。  图8.1??? 单词THE  图8.2??? 看不见的三角  图8.1是单词THE，这一点很容易看出来，但仔细观察一下，就会发现，图中少了很多线条。在我们人类看来很简单的一件事，让计算机来做就很困难了。 图8.2中尽管没有任何线条，但我们还是可以很容易的看出中间存在着一个白色三角形。计算机却很难发现。 由于人类在观察图象时适用了大量的知识，所以没有任何一台计算机在分割和检测真实图象时，能达到人类视觉系统的水平。正因为如此，对于大部分图象应用来说，自动分割与检测还是一个将来时。目前只有少数的几个领域(如印刷体识别OCR)自动识别达到了实用的水平。 也许算是题外话，我们可以憧憬这样一种应用：基于内容的搜索。在一场足球比赛的录象中，用户可以输入命令，由计算机自动搜索出所有射门的镜头并显示在屏幕上。目前，我们能从一幅图象中获得的信息只是每个象素的颜色或灰度值，除此以外别无其它，完成上述功能实在是太困难了。所以说解决图象分割和检测最根本的方法是在编码(成象)时就给予考虑。这也正是MPEG4及未来的视频压缩编码标准的主要工作。 正因为有上述的困难，所以我们今天要介绍的只是一些最基本，最简单的算法和思想，针对也只能是一些具体(而不是通用)的应用。算法共有三个：投影法、差影法和模板匹配。 8.1 投影法 在介绍投影法之前，我先出一道题目，下面的这幅照片是著名的华盛顿纪念碑(我记得在“阿甘正传”中曾经看到过它)，怎样从图中自动检测到水平方向上纪念碑的位置。 仔细观察，不难发现，纪念碑上象素的灰度都差不多而且与众不同，如果我们选取合适的阈值，做削波处理(这里选175到220)，将该图二值化，如图8.3所示：  图8.3??? 华盛顿纪念碑  图8.4??? 削波处理，将图8.3二值化  由于纪念碑所在的那几列的白色点比起其他列多很多，如果把该图在垂直方向做投影，如图8.5所示。  图8.5???? 图8.4做垂直方向投影 其中，黑色线条的高度代表了该列上白色点的个数。图中间的高峰部分就是我们要找的水平方向上纪念碑所在的位置，这就是投影法。 可以看出投影法是一种很自然的想法，有点象灰度直方图。为了得到更好的效果，投影法经常和阈值化一起使用。由于噪声点对投影有一定的影响，所以处理前最好先做一次平滑，去除噪声。 以下是投影法的源程序，第二个参数是个BOOL变量，为真时表示在水平方向上做投影，否则在垂直方向上做投影。要注意的是，我们针对的虽然是二值图，但为了处理的方便，用的是256级灰度图，不过只用到了0和255两种灰度级。 BOOL Projection(HWND hWnd,BOOL Hori) { ?????? DWORD ????????????? OffBits,BufSize; LPBITMAPINFOHEADER??? lpImgData; ?????? LPSTR? ????????????? ?????????????? lpPtr; ?????? HLOCAL??? ??????? ?????????? hTempImgData; ?????? LPBITMAPINFOHEADER??? lpTempImgData; ?????? LPSTR ???????? ????????????? ???? lpTempPtr; ?????? HDC ??????????? ????????????? ????????????? hDc; ?????? HFILE??????????? ??????????? ????? hf; ?????? LONG?????????????? ????? x,y; ?????? int???????????????????????? ?? ??????? ?????? num; //用的是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); ?????? if(Hori) ?????? { //水平投影 ????????????? for(y=0;y<bi.biHeight;y++){ ???????????????????? lpPtr=(char *)lpImgData+(BufSize-LineBytes-y*LineBytes); ???????????????????? num=0; //计数器初始化为0 ???????????????????? for(x=0;x<bi.biWidth;x++) ??????????????????????????? if(*(lpPtr++)!=0) //是白点 ?????????????????????????????????? num++; //计数器加1 ???????????????????? lpTempPtr=(char *)lpTempImgData+(BufSize-LineBytes-y*LineBytes); ???????????????????? for(x=0;x<num;x++) ??????????????????????????? *(lpTempPtr++)=0; //在新图中，该行中共有num个黑点 ????????????? } ?????? } ?????? else{ //垂直投影 ????????????? for(x=0;x<bi.biWidth;x++){ ???????????????????? num=0; //计数器初始化为0 ???????????????????? lpPtr=(char *)lpImgData+(BufSize-LineBytes)+x; ???????????????????? for(y=0;y<bi.biHeight;y++){ ??????????????????????????? if(*lpPtr!=0) ?????????????????????????????????? num++; //计数器加1 ??????????????????????????? lpPtr-=LineBytes; ???????????????????? } ???????????????????? lpTempPtr=(char *)lpTempImgData+OffBits+x; ???????????????????? for(y=0;y<num;y++){ ??????????????????????????? *lpTempPtr=0; //在新图中，该列中共有num个黑点 ??????????????????????????? lpTempPtr+=LineBytes; ???????????????????? } ????????????? } ?????? } 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); ?????? //起不同的结果文件名 ?????? if(Hori) ????????????? hf=_lcreat("c:\\hproject.bmp",0); ?????? else ????????????? hf=_lcreat("c:\\vproject.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; } 8.2 差影法 差影法的原理非常简单：将前后两幅图象相减，得到的差作为结果结果图象。图8.6、图8.7、图8.8能够说明差影法的原理。  图8.6???? 前景+背景  图8.7???? 背景  图8.8 图8.6、图8.7 相减的结果  图8.6是前景图(猫)加背景图(木星)。图8.7是背景图。图8.6减图8.7的结果如图8.8所示，这样就得到了前景(不完全是前景，因为背景的灰度值并不为零，但至少可以得到前景的形状)。 差影法是非常有用的，比如说可以用在监控系统中。在银行金库内，摄像头每隔一小段时间，拍摄一幅图，与上一幅图做差影；如果差别超过了预先设置的阈值，说明有人，这时就应该拉响警报。 我们在介绍灰度窗口变换时，曾经提到了电影“阿甘正传”特技中应用了“蓝幕”技术，其实也包含了差影法的原理。 以下是差影法的源程序。要注意的是，第一幅图的文件名为c:\test.bmp，第二幅图的文件名是c:\backgnd.bmp。它们有着相同的灰度值和调色板。执行时，这两个文件都已经准备好。我们针对的虽然是二值图，但为了处理的方便，用的是256级灰度图，不过只用到了0和255两种灰度级。 BOOL Subtraction(HWND hWnd) { ?????? DWORD??????? ????? ??? ?????? OffBits,BufSize; LPBITMAPINFOHEADER??? lpImgData; ?????? LPSTR????????????? ?????? ?????? lpPtr; ?????? HGLOBAL?????? ?????????? hSecond; ?????? LPBITMAPINFOHEADER??? lpSecondImgData; ?????? LPSTR????????????? ?????? ?????? lpSecondPtr; ?????? HLOCAL???????????? ????? ?????? hTempImgData; ?????? LPBITMAPINFOHEADER??? lpTempImgData; ?????? LPSTR????????????? ?????? ?????? lpTempPtr; ?????? HDC??????????????? ?????? ?????? hDc; ?????? HFILE????????????? ?????? hf; ?????? LONG?????? ????????????? ?????? x,y; ?????? int??????????????? ?????????? num,pos; //用的是256级灰度图，不过只用到了0和255两种灰度级。 ?????? if( NumColors!=256){ MessageBox(hWnd,"Must be a mono bitmap with grayscale palette!", "Error Message",MB_OK|MB_ICONEXCLAMATION); return FALSE; } ?? ? if((hf=_lopen("c:\\backgnd.bmp",OF_READ))==HFILE_ERROR){ //背景图没找到 ???? ???? MessageBox(hWnd,"File c:\\backgnd.bmp not found!","Error Message", MB_OK|MB_ICONEXCLAMATION); return FALSE; } //到位图数据的偏移值 ?????? OffBits=bf.bfOffBits-sizeof(BITMAPFILEHEADER); ?????? //缓冲区大小 ?????? BufSize=OffBits+bi.biHeight*LineBytes; ?????? //为背景图的数据分配内存 ?????? if((hSecond=GlobalAlloc(GHND,BufSize))==NULL) ?? ? { ?????? MessageBox(hWnd,"Error alloc memory!","Error Message", MB_OK|MB_ICONEXCLAMATION); ????????????? _lclose(hf); ?????? ? return FALSE; } //指向该内存指针 lpSecondImgData=(LPBITMAPINFOHEADER)GlobalLock(hSecond); //文件指针指到BITMAPINFOHEADER结构开始的地方 ?????? _llseek(hf,sizeof(BITMAPFILEHEADER),FILE_BEGIN); ?????? //读入头信息和位图数据 ?????? _lread(hf,(LPSTR)lpSecondImgData,BufSize); ?????? _lclose(hf); ?????? //为结果图缓冲区分配内存 ?????? if((hTempImgData=LocalAlloc(LHND,BufSize))==NULL) { ?????? MessageBox(hWnd,"Error alloc memory!","Error Message", MB_OK|MB_ICONEXCLAMATION); ????????????? GlobalUnlock(hSecond); ????????????? GlobalFree(hSecond); return FALSE; } ?? ? lpImgData=(LPBITMAPINFOHEADER)GlobalLock(hImgData);??? ?????? lpTempImgData=(LPBITMAPINFOHEADER)LocalLock(hTempImgData); ?????? //新图缓冲区初始化为255 memset(lpTempImgData,(BYTE)255,BufSize); //拷贝头信息 ?????? memcpy(lpTempImgData,lpImgData,OffBits); ?????? for(y=0;y<bi.biHeight;y++){ ????????????? pos=(BufSize-LineBytes-y*LineBytes); ????????????? //lpPtr指向第一幅图，lpSecondPtr指向第二幅图，lpTempPtr指向结果图 ????????????? lpPtr=(char *)lpImgData+pos; ????????????? lpSecondPtr=(char *)lpSecondImgData+pos; ????????????? lpTempPtr=(char *)lpTempImgData+pos; ????????????? for(x=0;x<bi.biWidth;x++){ ???????????????????? num=(unsigned char)*(lpPtr++); ???????????????????? num-=(unsigned char)*(lpSecondPtr++); ???????????????????? *(lpTempPtr++)=(unsigned char)fabs(num); //两者相减取绝对值，存入新图中 ????????????? } ?????? } ?? ? 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:\\subtract.bmp",0); ?????? _lwrite(hf,(LPSTR)&bf,sizeof(BITMAPFILEHEADER)); ?????? _lwrite(hf,(LPSTR)lpTempImgData,BufSize); ?????? _lclose(hf); ?????? //释放内存和资源 ????? ReleaseDC(hWnd,hDc); ?????? GlobalUnlock(hSecond); ?????? GlobalFree(hSecond); ?????? LocalUnlock(hTempImgData); ?????? LocalFree(hTempImgData); ?????? GlobalUnlock(hImgData); ?????? return TRUE; } 8.3 模板匹配 利用模板匹配可以在一幅图象中找到已知的物体。比如抓拍到了一张射门的照片，要在该照片中找到足球的位置。这时就可以采用模板匹配的方法。所谓模板匹配，其实想法很简单：拿已知的模板(在本例中为足球的图象)，和原图象中同样大小的一块区域去对。 最开始时，模板的左上角点和图象的左上角点是重合的，拿模板和原图象中同样大小的一块区域去对比，然后平移到下一个象素，仍然进行同样的操作，……所有的位置都对完后，差别最小的那块就是我们要找的物体。 我们用平方误差之和来衡量原图中的块和模板之间的差别。假设模板的大小为m×n(宽×高)；图象的大小为Width×Height。模板中的某点坐标为(x0,y0)，该点的灰度为U(x0,y0)；与之重合的图象中的点坐标为(X0-x0,Y0-y0)，该点的灰度为V(X0-x0,Y0-y0)。则一次匹配的结果为：  全部图象都匹配后，找到最小的即为结果。可以看到模板匹配的运算量是惊人的。一次匹配都要做m×n次减法，m×n次平方，m×n-1次加法，整个图象要匹配(Width-m+1) ×(Height-n+1)次。 源程序不再给出，有兴趣的读者可以自己完成。 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