二值图像连通域标记算法与代码_收藏

1、二值图像连通域标记算法与代码 收藏 10:19:42二值图像连通域标记算法与代码这里列举二值图像连通域标记算法包括直接扫描标记算法和二值图像连通域标记快速算法一、直接扫描标记算法把连续区域作同一个标记，常见的四邻域标记算法和八邻域标记算法。1、 四邻域标记算法：1） 判断此点四邻域中的最左，最上有没有点，如果都没有点，则表示一个新的区域的开始。2） 如果此点四邻域中的最左有点，最上没有点，则标记此点为最左点的值；如果此点四邻域中的最左没有点，最上有点，则标记此点为最上点的值。3） 如果此点四邻域中的最左有点，最上都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。2、 八邻域标记

2、算法：1） 判断此点八邻域中的最左，左上，最上，上右点的情况。 如果都没有点，则表示一个新的区域的开始。2） 如果此点八邻域中的最左有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。3） 如果此点八邻域中的左上有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。4） 否则按照最左，左上，最上，上右的顺序，标记此点为四个中的一个。代码实现：#include <list>#include <vector>#include <algorithm>/连通区域属性结构typedef struct tagMarkRegi

3、onstd:list<POINT> MarkPointList;/点列表RECT rect;MarkRegion; /定义MarkMap 结构，用来存放等价对typedef struct tagEqualMark int MarkValue1; /标记值int MarkValue2; /标记值 EqualMark; /定义MarkMapping 结构，用来存放标记映射关系typedef struct tagMarkMapping int nOriginalMark; /第一次扫描的标记int nMappingMark; /等价整理之后对应标记 MarkMapping; /*功能说明

4、：八连通标记参数说明：I，表示图像数据指针 ImageWidth,表示图像宽 ImageHeight，表示图像高 off，表示偏移量 nFlag,表示指定标记 iColorType，表示颜色类型，（黑点，白点） markInfo，表示连通区域属性信息返回值：连通点数量，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)/黑点同时未被标记的情况 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; /*功能说明：四连通标记参数说明：I，表示图像数据指针ImageWidth,表示图像宽ImageHeight，表示图像高off，表示偏移量nFlag,表示指定标记iColorType，表示颜色类型，（黑点，白点）markInfo，表示连通区域属性信息返回值：连通点数量，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)/黑点同时未被标记的情况 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; 二、二值图像连通域标记快速算法算法描述首先，在进行标记算法以前，利用硬件开辟独立的图像标记缓存和连通关系数组，接着在视频流的采集传输过程中，以流水线的方式按照视频传输顺序对图像进行逐行像素扫描

16、，然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并，检测出的结果对标记等价数组和标记缓存进行更新，在一帧图像采集传输结束后，得到图像的初步标记结果以及初步标记之间的连通关系，最后，根据标号对连通关系数组从小到大的传递过程进行标号的归并，利用归并后的连通关系数组对图像标记缓存中的标号进行替换，替换后的图像为最终标记结果，并且连通域按照扫描顺序被赋予唯一的连续自然数。图 1 标记算法流程本文快速二值图像连通域标记算法分为三个环节：1.图像初步标记：为每个像素赋予临时标记，并且将临时标记的等价关系记录在等价表中2.整理等价表：这一环节分为两个步骤： （1）将具有等价关

17、系的临时标记全部等价为其中的最小值； （2）对连通区域以自然数顺序重新编号，得到临时标记与最终标记之间的等价关系。3.图像代换：对图像进行逐像素代换，将临时标记代换为最终标记经过3个环节处理后，算法输出标记后的图像，图像中连通域按照由上到下，由左至右出现的顺序被标以连续的自然数。代码实现：#include <list>#include <vector>#include <algorithm>/连通区域属性结构typedef struct tagMarkRegionstd:list<POINT> MarkPointList;/点列表RECT rec

18、t;MarkRegion;/定义MarkMap 结构，用来存放等价对typedef struct tagEqualMark int MarkValue1; /标记值int MarkValue2; /标记值 EqualMark;/定义MarkMapping 结构，用来存放标记映射关系typedef struct tagMarkMapping int nOriginalMark; /第一次扫描的标记int nMappingMark; /等价整理之后对应标记 MarkMapping; /*功能说明：将所选出的等价关系，attach到list上里参数说明： pEqualMark 等价关系 num1 新

19、的等价关系1 num2 新的等价关系2 nEqualNum 等价数组的个数 plEqualMark 存放等价数组的list返回值：无*/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; /插入到数组中 pEqualNum+; plEqualMark.push_back(pEqualMark); /num2小的情况 else if ( pEqualMark.MarkValue2 != num1 | pEqualMark.MarkValue1 != num2 ) pEqualMark.MarkValue1=num2; pEqualMark.MarkValue2=num1; /插

21、入到数组中 pEqualNum+; plEqualMark.push_back(pEqualMark); /* 功能说明：快速二值图像连通域标记 参数说明：lpImgBits，表示图象数据区指针 nMarkNumbers，表示标记数量 iColorType，表示被标记颜色的值（，） 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，表示图象数据区偏移指针 int * lpMark= NULL;/lpMark，表示标记数据指针 int * lpMarkMove = NULL;/lpMarkMove，表示标记数据偏移指针 /iColorType为目标的图像值 long lSize = nImageWidth*nImageHeigt; lpMark= new intlSize+1; lpMarkMove=lpMark;

23、 :memset(lpMark,0,(lSize+1)*sizeof(int); int nMarkValue=1; /* 每次标识的值，nMarkValue会在后边递增， 来表示不同的区域，从开始标记。*/ int nMaxMarkValue=0; /记录最大的标识的值 int i,j; /循环控制变量 /* 定义存放等价对的链表，其元素是EqualMark类型， 定义list是为了节约存储空间。要使用Clist， 应该#include <Afxtempl.h>。 */ std:list<EqualMark> lEqualMark; /初始化图像移动指针 lpImgB

24、itsMove = lpImgBits; /*进行第一次扫描，将所得的等价对(EqualMark类型)加到lEqualMark链表中。 使用nMarkValue来进行每一次新的标记，标记之后将其值加。 Note1：图像的四周像素并不会有个相邻的像素。这时就要根据上、下、左、 右四种不同的情况做不同的寻找等价对的判断。 Note2：可以先对等价对进行排序，每次都保证MarkValue1<MarkValue2， 这样易于管理等价对。 Note3：在实际工作中，连续寻找出的等价对很容易重复，将本次找出的等价对 和链表中保存的最后一个等价对相比较，如果不相等的话再存入等价对链表， 这样可以大大降

25、低链表中等价对的重复。 Note4：第一次扫描之后，nMarkValue-1即为nMaxMarkValue。*/ /*/ /下面为补充代码,完成对图像的第一次扫描 /初始化图像数组和标识数组的指针 int nEqualNum=0; EqualMark tempEqualMark; /用以暂时存放每次找到的等价关系 lpMarkMove=lpMark; lpImgBitsMove = lpImgBits; /标记图像的第一行、第一列的像素(只有这一个像素) if ( *lpImgBitsMove=iColorType ) *lpMarkMove=nMarkValue+; lpMarkMove+;

26、 lpImgBitsMove+; /标记图像的第一行，此时不会出现等价的情况 for ( i=1; i < nImageWidth; i+) /需要标记的情况 if ( *lpImgBitsMove=iColorType ) /前面没有被标记过，则开始一个新的标记 if ( *(lpMarkMove-1)=(!iColorType) *lpMarkMove=nMarkValue+; /前面被标记过，则跟随前一个标记 else *lpMarkMove=*(lpMarkMove-1); lpMarkMove+; lpImgBitsMove+; /除第一行之外的标记，此时会出现等价的关系 fo

27、r ( j=1; j < nImageHeigt; j+ ) lpImgBitsMove=lpImgBits+j*nImageWidth; lpMarkMove=lpMark+j*nImageWidth; /对每行的第一个点做处理，总体就是对图像的最左列做处理 /只需要检视上，右上两个点 if ( *lpImgBitsMove=iColorType ) /<上>位置被标记过 if ( *(lpMarkMove-nImageWidth)!=0 ) /跟随<上>标记 *lpMarkMove=*(lpMarkMove-nImageWidth); if ( *(lpMar

28、kMove-nImageWidth)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0) /<上><右上>等价标记 AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<上>没有标记，此时一定不会存在等价关系 else if ( *(lpMarkMove-nImageWidth+1)!=0 ) *lpMar

29、kMove=*(lpMarkMove-nImageWidth+1); /跟随<右上>标记 /<上>、<右上>都没有标记，则开始新的标记 else *lpMarkMove=nMarkValue+; lpMarkMove+; lpImgBitsMove+; /对每行的中间点做标记处理，此时存在<左>、<左上>、<上>、<右上> 4种情况 for ( i=1; i<=nImageWidth-1; i+ ) /需要标记 if ( (*lpImgBitsMove)=iColorType ) /<左>被标

30、记过 if ( *(lpMarkMove-1)!=0 ) *lpMarkMove=*(lpMarkMove-1); /跟随<左> if ( *(lpMarkMove-1)!=*(lpMarkMove-nImageWidth-1) && *(lpMarkMove-nImageWidth-1)!=0 ) /标记<左>、<左上>等价 AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth-1),nEqualNum,lEqualMark); if ( *(lpMar

31、kMove-1)!=*(lpMarkMove-nImageWidth) && *(lpMarkMove-nImageWidth)!=0) /标记<左>、<上>等价 AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark); if ( *(lpMarkMove-1)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0) /标记<左&g

32、t;、<右上>等价 AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<左>未被标记过 else /<左上>被标记过 if ( *(lpMarkMove-nImageWidth-1)!=0 ) *lpMarkMove=*(lpMarkMove-nImageWidth-1); if ( *(lpMarkMove-nImageWidth-1)!=*(lpMarkMove-nImageWidth) &&

33、*(lpMarkMove-nImageWidth)!=0) /标记<左上>、<上>等价 AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark); if ( *(lpMarkMove-nImageWidth-1)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0) /标记<左上>、<右上>等价 Attac

34、hEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth-1),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<左>、<左上>未标记过 else if ( *(lpMarkMove-nImageWidth)!=0 ) *lpMarkMove=*(lpMarkMove-nImageWidth); /跟随<上>标记 if ( *(lpMarkMove-nImageWidth)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0 ) /标记<上>和<右上>等价 AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth),*(lpMarkMove-nImageWidth+1),nEqualNum,lEqualMark); /<左>、<左上