二值圖像連通域標(biāo)記算法與代碼_收藏

1、二值圖像連通域標(biāo)記算法與代碼 收藏 10:19:42二值圖像連通域標(biāo)記算法與代碼這里列舉二值圖像連通域標(biāo)記算法包括直接掃描標(biāo)記算法和二值圖像連通域標(biāo)記快速算法一、直接掃描標(biāo)記算法把連續(xù)區(qū)域作同一個(gè)標(biāo)記，常見(jiàn)的四鄰域標(biāo)記算法和八鄰域標(biāo)記算法。1、 四鄰域標(biāo)記算法：1） 判斷此點(diǎn)四鄰域中的最左，最上有沒(méi)有點(diǎn)，如果都沒(méi)有點(diǎn)，則表示一個(gè)新的區(qū)域的開(kāi)始。2） 如果此點(diǎn)四鄰域中的最左有點(diǎn)，最上沒(méi)有點(diǎn)，則標(biāo)記此點(diǎn)為最左點(diǎn)的值；如果此點(diǎn)四鄰域中的最左沒(méi)有點(diǎn)，最上有點(diǎn)，則標(biāo)記此點(diǎn)為最上點(diǎn)的值。3） 如果此點(diǎn)四鄰域中的最左有點(diǎn)，最上都有點(diǎn)，則標(biāo)記此點(diǎn)為這兩個(gè)中的最小的標(biāo)記點(diǎn)，并修改大標(biāo)記為小標(biāo)記。2、 八鄰域標(biāo)記

2、算法：1） 判斷此點(diǎn)八鄰域中的最左，左上，最上，上右點(diǎn)的情況。 如果都沒(méi)有點(diǎn)，則表示一個(gè)新的區(qū)域的開(kāi)始。2） 如果此點(diǎn)八鄰域中的最左有點(diǎn)，上右都有點(diǎn)，則標(biāo)記此點(diǎn)為這兩個(gè)中的最小的標(biāo)記點(diǎn)，并修改大標(biāo)記為小標(biāo)記。3） 如果此點(diǎn)八鄰域中的左上有點(diǎn)，上右都有點(diǎn)，則標(biāo)記此點(diǎn)為這兩個(gè)中的最小的標(biāo)記點(diǎn)，并修改大標(biāo)記為小標(biāo)記。4） 否則按照最左，左上，最上，上右的順序，標(biāo)記此點(diǎn)為四個(gè)中的一個(gè)。代碼實(shí)現(xiàn)：#include <list>#include <vector>#include <algorithm>/連通區(qū)域?qū)傩越Y(jié)構(gòu)typedef struct tagMarkRegi

3、onstd:list<POINT> MarkPointList;/點(diǎn)列表RECT rect;MarkRegion; /定義MarkMap 結(jié)構(gòu)，用來(lái)存放等價(jià)對(duì)typedef struct tagEqualMark int MarkValue1; /標(biāo)記值int MarkValue2; /標(biāo)記值 EqualMark; /定義MarkMapping 結(jié)構(gòu)，用來(lái)存放標(biāo)記映射關(guān)系typedef struct tagMarkMapping int nOriginalMark; /第一次掃描的標(biāo)記int nMappingMark; /等價(jià)整理之后對(duì)應(yīng)標(biāo)記 MarkMapping; /*功能說(shuō)明

4、：八連通標(biāo)記參數(shù)說(shuō)明：I，表示圖像數(shù)據(jù)指針 ImageWidth,表示圖像寬 ImageHeight，表示圖像高 off，表示偏移量 nFlag,表示指定標(biāo)記 iColorType，表示顏色類型，（黑點(diǎn)，白點(diǎn)） markInfo，表示連通區(qū)域?qū)傩孕畔⒎祷刂担哼B通點(diǎn)數(shù)量，int類型*/int FillAreaFlag33(LPINT I,int ImageWidth,int ImageHeight,long off,int nFlag,int iColorType,MarkRegion &markInfo) bool bNew; RECT rect; int m,n,i,j,k,nDot

5、=1,offset,offtemp,yMin; int dxy8,x,y; dxy0=-ImageWidth-1; dxy1=-ImageWidth; dxy2=-ImageWidth+1; dxy3=-1; dxy4=1; dxy5=ImageWidth-1; dxy6=ImageWidth; dxy7=ImageWidth+1; rect.left=65535; rect.right=-1; rect.bottom=65535; rect.top=-1; markInfo.MarkPointList.clear(); POINT ptTmp; if(Ioff=iColorType &

6、;& Ioff!=nFlag)/黑點(diǎn)同時(shí)未被標(biāo)記的情況 Ioff=nFlag; x=off%ImageWidth; y=off/ImageWidth; ptTmp.x = x; ptTmp.y = y; markInfo.MarkPointList.push_back(ptTmp); if(x<rect.left) rect.left=x; if(x>rect.right) rect.right=x; if(y<rect.bottom) rect.bottom=y; if(y>rect.top) rect.top=y; else return 0; for(i=

7、y; i<ImageHeight; i+) bNew=false; yMin=i; for(j=0; j<ImageWidth; j+) offset=i*ImageWidth+j; if(Ioffset=nFlag) for(k=0; k<8; k+)/八鄰域搜索 if(i=0 && k<=2) continue; if(i=ImageHeight-1 && k>=5) continue; if(j=0 && (k=0 | k=3 | k=5) continue; if(j=ImageWidth-1 &&a

8、mp; (k=2 | k=4 | k=7) continue; offtemp=offset+dxyk; if(Iofftemp=iColorType && Iofftemp!=nFlag) Iofftemp=nFlag; nDot+; m=offtemp/ImageWidth; n=offtemp%ImageWidth; ptTmp.x = n; ptTmp.y = m; markInfo.MarkPointList.push_back(ptTmp); if(n < rect.left) rect.left=n; if(n > rect.right) rect.r

9、ight=n; if(m < rect.bottom) rect.bottom=m; if(m > rect.top) rect.top=m; y=offtemp/ImageWidth; if(y<=yMin) yMin=y; if(!bNew) bNew=true; if(bNew) i=yMin-1; markInfo.rect.left = rect.left; markInfo.rect.right = rect.right; markInfo.rect.top = rect.top; markInfo.rect.bottom = rect.bottom; retur

10、n nDot; /*功能說(shuō)明：四連通標(biāo)記參數(shù)說(shuō)明：I，表示圖像數(shù)據(jù)指針I(yè)mageWidth,表示圖像寬ImageHeight，表示圖像高off，表示偏移量nFlag,表示指定標(biāo)記iColorType，表示顏色類型，（黑點(diǎn)，白點(diǎn)）markInfo，表示連通區(qū)域?qū)傩孕畔⒎祷刂担哼B通點(diǎn)數(shù)量，int類型*/int FillAreaFlag22(LPINT I,int ImageWidth,int ImageHeight,long off,int nFlag,int iColorType,MarkRegion &markInfo) bool bNew; RECT rect; int m,n,i,

11、j,k,nDot=1,offset,offtemp,yMin; int dxy4,x,y; dxy0=-ImageWidth; dxy1=1; dxy2=ImageWidth; dxy3=-1; rect.left=65535; rect.right=-1; rect.bottom=65535; rect.top=-1; markInfo.MarkPointList.clear(); POINT ptTmp; if(Ioff=iColorType && Ioff!=nFlag)/黑點(diǎn)同時(shí)未被標(biāo)記的情況 Ioff=nFlag; x=off%ImageWidth; y=off/Im

12、ageWidth; ptTmp.x = x; ptTmp.y = y; markInfo.MarkPointList.push_back(ptTmp); if(x<rect.left) rect.left=x; if(x>rect.right) rect.right=x; if(y<rect.bottom) rect.bottom=y; if(y>rect.top) rect.top=y; else return 0; for(i=y; i<ImageHeight; i+) bNew=false; yMin=i; for(j=0; j<ImageWidth;

13、 j+) offset=i*ImageWidth+j; if(Ioffset=nFlag) for(k=0; k<4; k+)/四鄰域搜索 if(i=0 && k=0) continue; if(i=ImageHeight-1 && k=2) continue; if(j=0 && k=3) continue; if(j=ImageWidth-1 && k=1) continue; offtemp=offset+dxyk; if(Iofftemp=iColorType && Iofftemp!=nFlag)

14、Iofftemp=nFlag; nDot+; m=offtemp/ImageWidth; n=offtemp%ImageWidth; ptTmp.x = n; ptTmp.y = m; markInfo.MarkPointList.push_back(ptTmp); if(n < rect.left) rect.left=n; if(n > rect.right) rect.right=n; if(m < rect.bottom) rect.bottom=m; if(m > rect.top) rect.top=m; y=offtemp/ImageWidth; if(y

15、<=yMin) yMin=y; if(!bNew) bNew=true; if(bNew) i=yMin-1; markInfo.rect.left = rect.left; markInfo.rect.right = rect.right; markInfo.rect.top = rect.top; markInfo.rect.bottom = rect.bottom; return nDot; 二、二值圖像連通域標(biāo)記快速算法算法描述首先，在進(jìn)行標(biāo)記算法以前，利用硬件開(kāi)辟獨(dú)立的圖像標(biāo)記緩存和連通關(guān)系數(shù)組，接著在視頻流的采集傳輸過(guò)程中，以流水線的方式按照視頻傳輸順序?qū)D像進(jìn)行逐行像素掃描

16、，然后對(duì)每個(gè)像素的鄰域分別按照逆時(shí)針?lè)较蚝退椒较蜻M(jìn)行連通性檢測(cè)和等價(jià)標(biāo)記關(guān)系合并，檢測(cè)出的結(jié)果對(duì)標(biāo)記等價(jià)數(shù)組和標(biāo)記緩存進(jìn)行更新，在一幀圖像采集傳輸結(jié)束后，得到圖像的初步標(biāo)記結(jié)果以及初步標(biāo)記之間的連通關(guān)系，最后，根據(jù)標(biāo)號(hào)對(duì)連通關(guān)系數(shù)組從小到大的傳遞過(guò)程進(jìn)行標(biāo)號(hào)的歸并，利用歸并后的連通關(guān)系數(shù)組對(duì)圖像標(biāo)記緩存中的標(biāo)號(hào)進(jìn)行替換，替換后的圖像為最終標(biāo)記結(jié)果，并且連通域按照掃描順序被賦予唯一的連續(xù)自然數(shù)。圖 1 標(biāo)記算法流程本文快速二值圖像連通域標(biāo)記算法分為三個(gè)環(huán)節(jié)：1.圖像初步標(biāo)記：為每個(gè)像素賦予臨時(shí)標(biāo)記，并且將臨時(shí)標(biāo)記的等價(jià)關(guān)系記錄在等價(jià)表中2.整理等價(jià)表：這一環(huán)節(jié)分為兩個(gè)步驟： （1）將具有等價(jià)關(guān)

17、系的臨時(shí)標(biāo)記全部等價(jià)為其中的最小值； （2）對(duì)連通區(qū)域以自然數(shù)順序重新編號(hào)，得到臨時(shí)標(biāo)記與最終標(biāo)記之間的等價(jià)關(guān)系。3.圖像代換：對(duì)圖像進(jìn)行逐像素代換，將臨時(shí)標(biāo)記代換為最終標(biāo)記經(jīng)過(guò)3個(gè)環(huán)節(jié)處理后，算法輸出標(biāo)記后的圖像，圖像中連通域按照由上到下，由左至右出現(xiàn)的順序被標(biāo)以連續(xù)的自然數(shù)。代碼實(shí)現(xiàn)：#include <list>#include <vector>#include <algorithm>/連通區(qū)域?qū)傩越Y(jié)構(gòu)typedef struct tagMarkRegionstd:list<POINT> MarkPointList;/點(diǎn)列表RECT rec

18、t;MarkRegion;/定義MarkMap 結(jié)構(gòu)，用來(lái)存放等價(jià)對(duì)typedef struct tagEqualMark int MarkValue1; /標(biāo)記值int MarkValue2; /標(biāo)記值 EqualMark;/定義MarkMapping 結(jié)構(gòu)，用來(lái)存放標(biāo)記映射關(guān)系typedef struct tagMarkMapping int nOriginalMark; /第一次掃描的標(biāo)記int nMappingMark; /等價(jià)整理之后對(duì)應(yīng)標(biāo)記 MarkMapping; /*功能說(shuō)明：將所選出的等價(jià)關(guān)系，attach到list上里參數(shù)說(shuō)明： pEqualMark 等價(jià)關(guān)系 num1 新

19、的等價(jià)關(guān)系1 num2 新的等價(jià)關(guān)系2 nEqualNum 等價(jià)數(shù)組的個(gè)數(shù) plEqualMark 存放等價(jià)數(shù)組的list返回值：無(wú)*/template<typename elemType> void AttachEqualMark(EqualMark &pEqualMark,elemType num1, elemType num2, int & pEqualNum, std:list< EqualMark> & plEqualMark) /num1小的情況 if ( num1 < num2 ) if ( pEqualMark.MarkVa

20、lue1 != num1 | pEqualMark.MarkValue2 != num2 ) pEqualMark.MarkValue1=num1; pEqualMark.MarkValue2=num2; /插入到數(shù)組中 pEqualNum+; plEqualMark.push_back(pEqualMark); /num2小的情況 else if ( pEqualMark.MarkValue2 != num1 | pEqualMark.MarkValue1 != num2 ) pEqualMark.MarkValue1=num2; pEqualMark.MarkValue2=num1; /插

21、入到數(shù)組中 pEqualNum+; plEqualMark.push_back(pEqualMark); /* 功能說(shuō)明：快速二值圖像連通域標(biāo)記 參數(shù)說(shuō)明：lpImgBits，表示圖象數(shù)據(jù)區(qū)指針 nMarkNumbers，表示標(biāo)記數(shù)量 iColorType，表示被標(biāo)記顏色的值（，） nImageWidth，表示圖象的寬 nImageHeight，表示圖象的高 返回值：BOOL類型，TRUE，表示成功；FLASE，表示失敗*/BOOL MarkImage(BYTE * lpImgBits,int & nMarkNumbers,int iColorType,long nImageWidth

22、,long nImageHeigt,std:list< MarkRegion> &listMarkData) BYTE * lpImgBitsMove=NULL;/lpImgBitsMove，表示圖象數(shù)據(jù)區(qū)偏移指針 int * lpMark= NULL;/lpMark，表示標(biāo)記數(shù)據(jù)指針 int * lpMarkMove = NULL;/lpMarkMove，表示標(biāo)記數(shù)據(jù)偏移指針 /iColorType為目標(biāo)的圖像值 long lSize = nImageWidth*nImageHeigt; lpMark= new intlSize+1; lpMarkMove=lpMark;

23、 :memset(lpMark,0,(lSize+1)*sizeof(int); int nMarkValue=1; /* 每次標(biāo)識(shí)的值，nMarkValue會(huì)在后邊遞增， 來(lái)表示不同的區(qū)域，從開(kāi)始標(biāo)記。*/ int nMaxMarkValue=0; /記錄最大的標(biāo)識(shí)的值 int i,j; /循環(huán)控制變量 /* 定義存放等價(jià)對(duì)的鏈表，其元素是EqualMark類型， 定義list是為了節(jié)約存儲(chǔ)空間。要使用Clist， 應(yīng)該#include <Afxtempl.h>。 */ std:list<EqualMark> lEqualMark; /初始化圖像移動(dòng)指針 lpImgB

24、itsMove = lpImgBits; /*進(jìn)行第一次掃描，將所得的等價(jià)對(duì)(EqualMark類型)加到lEqualMark鏈表中。 使用nMarkValue來(lái)進(jìn)行每一次新的標(biāo)記，標(biāo)記之后將其值加。 Note1：圖像的四周像素并不會(huì)有個(gè)相鄰的像素。這時(shí)就要根據(jù)上、下、左、 右四種不同的情況做不同的尋找等價(jià)對(duì)的判斷。 Note2：可以先對(duì)等價(jià)對(duì)進(jìn)行排序，每次都保證MarkValue1<MarkValue2， 這樣易于管理等價(jià)對(duì)。 Note3：在實(shí)際工作中，連續(xù)尋找出的等價(jià)對(duì)很容易重復(fù)，將本次找出的等價(jià)對(duì) 和鏈表中保存的最后一個(gè)等價(jià)對(duì)相比較，如果不相等的話再存入等價(jià)對(duì)鏈表， 這樣可以大大降

25、低鏈表中等價(jià)對(duì)的重復(fù)。 Note4：第一次掃描之后，nMarkValue-1即為nMaxMarkValue。*/ /*/ /下面為補(bǔ)充代碼,完成對(duì)圖像的第一次掃描 /初始化圖像數(shù)組和標(biāo)識(shí)數(shù)組的指針 int nEqualNum=0; EqualMark tempEqualMark; /用以暫時(shí)存放每次找到的等價(jià)關(guān)系 lpMarkMove=lpMark; lpImgBitsMove = lpImgBits; /標(biāo)記圖像的第一行、第一列的像素(只有這一個(gè)像素) if ( *lpImgBitsMove=iColorType ) *lpMarkMove=nMarkValue+; lpMarkMove+;

26、 lpImgBitsMove+; /標(biāo)記圖像的第一行，此時(shí)不會(huì)出現(xiàn)等價(jià)的情況 for ( i=1; i < nImageWidth; i+) /需要標(biāo)記的情況 if ( *lpImgBitsMove=iColorType ) /前面沒(méi)有被標(biāo)記過(guò)，則開(kāi)始一個(gè)新的標(biāo)記 if ( *(lpMarkMove-1)=(!iColorType) *lpMarkMove=nMarkValue+; /前面被標(biāo)記過(guò)，則跟隨前一個(gè)標(biāo)記 else *lpMarkMove=*(lpMarkMove-1); lpMarkMove+; lpImgBitsMove+; /除第一行之外的標(biāo)記，此時(shí)會(huì)出現(xiàn)等價(jià)的關(guān)系 fo

27、r ( j=1; j < nImageHeigt; j+ ) lpImgBitsMove=lpImgBits+j*nImageWidth; lpMarkMove=lpMark+j*nImageWidth; /對(duì)每行的第一個(gè)點(diǎn)做處理，總體就是對(duì)圖像的最左列做處理 /只需要檢視上，右上兩個(gè)點(diǎn) if ( *lpImgBitsMove=iColorType ) /<上>位置被標(biāo)記過(guò) if ( *(lpMarkMove-nImageWidth)!=0 ) /跟隨<上>標(biāo)記 *lpMarkMove=*(lpMarkMove-nImageWidth); if ( *(lpMar

28、kMove-nImageWidth)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0) /<上><右上>等價(jià)標(biāo)記 AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<上>沒(méi)有標(biāo)記，此時(shí)一定不會(huì)存在等價(jià)關(guān)系 else if ( *(lpMarkMove-nImageWidth+1)!=0 ) *lpMar

29、kMove=*(lpMarkMove-nImageWidth+1); /跟隨<右上>標(biāo)記 /<上>、<右上>都沒(méi)有標(biāo)記，則開(kāi)始新的標(biāo)記 else *lpMarkMove=nMarkValue+; lpMarkMove+; lpImgBitsMove+; /對(duì)每行的中間點(diǎn)做標(biāo)記處理，此時(shí)存在<左>、<左上>、<上>、<右上> 4種情況 for ( i=1; i<=nImageWidth-1; i+ ) /需要標(biāo)記 if ( (*lpImgBitsMove)=iColorType ) /<左>被標(biāo)

30、記過(guò) if ( *(lpMarkMove-1)!=0 ) *lpMarkMove=*(lpMarkMove-1); /跟隨<左> if ( *(lpMarkMove-1)!=*(lpMarkMove-nImageWidth-1) && *(lpMarkMove-nImageWidth-1)!=0 ) /標(biāo)記<左>、<左上>等價(jià) AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth-1),nEqualNum,lEqualMark); if ( *(lpMar

31、kMove-1)!=*(lpMarkMove-nImageWidth) && *(lpMarkMove-nImageWidth)!=0) /標(biāo)記<左>、<上>等價(jià) AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark); if ( *(lpMarkMove-1)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0) /標(biāo)記<左&g

32、t;、<右上>等價(jià) AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<左>未被標(biāo)記過(guò) else /<左上>被標(biāo)記過(guò) if ( *(lpMarkMove-nImageWidth-1)!=0 ) *lpMarkMove=*(lpMarkMove-nImageWidth-1); if ( *(lpMarkMove-nImageWidth-1)!=*(lpMarkMove-nImageWidth) &&

33、*(lpMarkMove-nImageWidth)!=0) /標(biāo)記<左上>、<上>等價(jià) AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark); if ( *(lpMarkMove-nImageWidth-1)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0) /標(biāo)記<左上>、<右上>等價(jià) Attac

34、hEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth-1),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<左>、<左上>未標(biāo)記過(guò) else if ( *(lpMarkMove-nImageWidth)!=0 ) *lpMarkMove=*(lpMarkMove-nImageWidth); /跟隨<上>標(biāo)記 if ( *(lpMarkMove-nImageWidth)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0 ) /標(biāo)記<上>和<右上>等價(jià) AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<左>、<左上