图象的分割与检测(识别)实际上是一项非常困难的工作。很难说清楚为什么图象应该分割成这样而不是那样。人类的视觉系统是非常优越的，它不仅包含了双眼，还包括了大脑，可以从很复杂的景物中分开并识别每个物体，甚至可以毫不费力地跟上每秒好几十帧变化的图象。举两个例子来说明一下人类视觉系统的优越性。

图8.1是单词THE，这一点很容易看出来，但仔细观察一下，就会发现，图中少了很多线条。在我们人类看来很简单的一件事，让计算机来做就很困难了。

图8.2中尽管没有任何线条，但我们还是可以很容易的看出中间存在着一个白色三角形。计算机却很难发现。

由于人类在观察图象时适用了大量的知识，所以没有任何一台计算机在分割和检测真实图象时，能达到人类视觉系统的水平。正因为如此，对于大部分图象应用来说，自动分割与检测还是一个将来时。目前只有少数的几个领域(如印刷体识别OCR)自动识别达到了实用的水平。

也许算是题外话，我们可以憧憬这样一种应用：基于内容的搜索。在一场足球比赛的录象中，用户可以输入命令，由计算机自动搜索出所有射门的镜头并显示在屏幕上。目前，我们能从一幅图象中获得的信息只是每个象素的颜色或灰度值，除此以外别无其它，完成上述功能实在是太困难了。所以说解决图象分割和检测最根本的方法是在编码(成象)时就给予考虑。这也正是MPEG4及未来的视频压缩编码标准的主要工作。

正因为有上述的困难，所以我们今天要介绍的只是一些最基本，最简单的算法和思想，针对也只能是一些具体(而不是通用)的应用。算法共有三个：投影法、差影法和模板匹配。

投影法

在介绍投影法之前，我先出一道题目，下面的这幅照片是著名的华盛顿纪念碑(我记得在“阿甘正传”中曾经看到过它)，怎样从图中自动检测到水平方向上纪念碑的位置。

仔细观察，不难发现，纪念碑上象素的灰度都差不多而且与众不同，如果我们选取合适的阈值，做削波处理(这里选175到220)，将该图二值化，如图8.3所示：

由于纪念碑所在的那几列的白色点比起其他列多很多，如果把该图在垂直方向做投影，如图8.5所示。

图8.5     图8.4做垂直方向投影

其中，黑色线条的高度代表了该列上白色点的个数。图中间的高峰部分就是我们要找的水平方向上纪念碑所在的位置，这就是投影法。

可以看出投影法是一种很自然的想法，有点象灰度直方图。为了得到更好的效果，投影法经常和阈值化一起使用。由于噪声点对投影有一定的影响，所以处理前最好先做一次平滑，去除噪声。

以下是投影法的源程序，第二个参数是个BOOL变量，为真时表示在水平方向上做投影，否则在垂直方向上做投影。要注意的是，我们针对的虽然是二值图，但为了处理的方便，用的是256级灰度图，不过只用到了0和255两种灰度级。

CODE
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.6、图8.7、图8.8能够说明差影法的原理。

图8.6是前景图(猫)加背景图(木星)。图8.7是背景图。图8.6减图8.7的结果如图8.8所示，这样就得到了前景(不完全是前景，因为背景的灰度值并不为零，但至少可以得到前景的形状)。

差影法是非常有用的，比如说可以用在监控系统中。在银行金库内，摄像头每隔一小段时间，拍摄一幅图，与上一幅图做差影；如果差别超过了预先设置的阈值，说明有人，这时就应该拉响警报。

我们在介绍灰度窗口变换时，曾经提到了电影“阿甘正传”特技中应用了“蓝幕”技术，其实也包含了差影法的原理。

以下是差影法的源程序。要注意的是，第一幅图的文件名为c:\test.bmp，第二幅图的文件名是c:\backgnd.bmp。它们有着相同的灰度值和调色板。执行时，这两个文件都已经准备好。我们针对的虽然是二值图，但为了处理的方便，用的是256级灰度图，不过只用到了0和255两种灰度级。

CODE
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;

}

模板匹配

利用模板匹配可以在一幅图象中找到已知的物体。比如抓拍到了一张射门的照片，要在该照片中找到足球的位置。这时就可以采用模板匹配的方法。所谓模板匹配，其实想法很简单：拿已知的模板(在本例中为足球的图象)，和原图象中同样大小的一块区域去对。

最开始时，模板的左上角点和图象的左上角点是重合的，拿模板和原图象中同样大小的一块区域去对比，然后平移到下一个象素，仍然进行同样的操作，……所有的位置都对完后，差别最小的那块就是我们要找的物体。

我们用平方误差之和来衡量原图中的块和模板之间的差别。假设模板的大小为m×n(宽×高)；图象的大小为Width×Height。模板中的某点坐标为(x₀,y₀)，该点的灰度为U(x₀,y₀)；与之重合的图象中的点坐标为(X₀-x₀,Y₀-y₀)，该点的灰度为V(X₀-x₀,Y₀-y₀)。则一次匹配的结果为：

全部图象都匹配后，找到最小的即为结果。可以看到模板匹配的运算量是惊人的。一次匹配都要做m×n次减法，m×n次平方，m×n-1次加法，整个图象要匹配(Width-m+1) ×(Height-n+1)次。

源程序不再给出，有兴趣的读者可以自己完成。有待优化。。。