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

女爷i 2022-05-27 12:08 215阅读 0赞

[原文链接][Link 1]

这里列举二值图像连通域标记算法包括直接扫描标记算法和二值图像连通域标记快速算法

一、直接扫描标记算法把连续区域作同一个标记，常见的四邻域标记算法和八邻域标记算法。

1、四邻域标记算法：

1）判断此点四邻域中的最左，最上有没有点，如果都没有点，则表示一个新的区域的开始。

2）如果此点四邻域中的最左有点，最上没有点，则标记此点为最左点的值；如果此点四邻域中的最左没有点，最上有点，则标记此点为最上点的值。

3）如果此点四邻域中的最左有点，最上都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。

2、八邻域标记算法：

1）判断此点八邻域中的最左，左上，最上，上右点的情况。如果都没有点，则表示一个新的区域的开始。

2）如果此点八邻域中的最左有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。

3）如果此点八邻域中的左上有点，上右都有点，则标记此点为这两个中的最小的标记点，并修改大标记为小标记。

4）否则按照最左，左上，最上，上右的顺序，标记此点为四个中的一个。

代码实现：

#include <list>
    #include <vector>
    #include <algorithm>
    //连通区域属性结构
    typedef struct tagMarkRegion
    {
    std::list<POINT> MarkPointList;//点列表
    RECT rect;
    }MarkRegion;
     
    //定义MarkMap 结构，用来存放等价对
    typedef struct tagEqualMark
    {    int MarkValue1;    //标记值
    int MarkValue2;    //标记值
    } EqualMark;
     
    //定义MarkMapping 结构，用来存放标记映射关系
    typedef struct tagMarkMapping
    {    int nOriginalMark;   //第一次扫描的标记
    int nMappingMark;  //等价整理之后对应标记
    } MarkMapping;
     
    /*
    功能说明：八连通标记
    参数说明：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=1,offset,offtemp,yMin;
         int dxy[8],x,y;
         dxy[0]=-ImageWidth-1;     dxy[1]=-ImageWidth;                  dxy[2]=-ImageWidth+1;
         dxy[3]=-1;                                                                                     dxy[4]=1;
         dxy[5]=ImageWidth-1;       dxy[6]=ImageWidth;          dxy[7]=ImageWidth+1;
         rect.left=65535; rect.right=-1;
         rect.bottom=65535;   rect.top=-1;
        markInfo.MarkPointList.clear();
         POINT ptTmp;
         if(I[off]==iColorType && I[off]!=nFlag)//黑点同时未被标记的情况
         {
             I[off]=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=y; i<ImageHeight; i++)
         {
             bNew=false;
             yMin=i;
             for(j=0; j<ImageWidth; j++)
             {
                  offset=i*ImageWidth+j;
                  if(I[offset]==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 && (k==2 || k==4 || k==7))
                                continue;
                           offtemp=offset+dxy[k];
                           if(I[offtemp]==iColorType && I[offtemp]!=nFlag)
                           {
                                I[offtemp]=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<=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;
    }
     
    /*
    功能说明：四连通标记
    参数说明：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,j,k,nDot=1,offset,offtemp,yMin;
         int dxy[4],x,y;
         dxy[0]=-ImageWidth;     dxy[1]=1;                
         dxy[2]=ImageWidth;      dxy[3]=-1;
         rect.left=65535; rect.right=-1;
         rect.bottom=65535;   rect.top=-1;
         markInfo.MarkPointList.clear();
         POINT ptTmp;
         if(I[off]==iColorType && I[off]!=nFlag)//黑点同时未被标记的情况
         {
             I[off]=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=y; i<ImageHeight; i++)
         {
             bNew=false;
             yMin=i;
             for(j=0; j<ImageWidth; j++)
             {
                  offset=i*ImageWidth+j;
                  if(I[offset]==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+dxy[k];
                           if(I[offtemp]==iColorType && I[offtemp]!=nFlag)
                           {
                                I[offtemp]=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<=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;
    }
     
     
    二、二值图像连通域标记快速算法
    算法描述
    　　首先，在进行标记算法以前，利用硬件开辟独立的图像标记缓存和连通关系数组，接着在视频流的采集传输过程中，以流水线的方式按照视频传输顺序对图像进行逐行像素扫描，然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并，检测出的结果对标记等价数组和标记缓存进行更新，在一帧图像采集传输结束后，得到图像的初步标记结果以及初步标记之间的连通关系，最后，根据标号对连通关系数组从小到大的传递过程进行标号的归并，利用归并后的连通关系数组对图像标记缓存中的标号进行替换，替换后的图像为最终标记结果，并且连通域按照扫描顺序被赋予唯一的连续自然数。
     
     
      
    图 1 标记算法流程
     
    　　本文快速二值图像连通域标记算法分为三个环节：
    　　1.图像初步标记：为每个像素赋予临时标记，并且将临时标记的等价关系记录在等价表中
    　　2.整理等价表：这一环节分为两个步骤：
         （1）将具有等价关系的临时标记全部等价为其中的最小值；
         （2）对连通区域以自然数顺序重新编号，得到临时标记与最终标记之间的等价关系。
    　　3.图像代换：对图像进行逐像素代换，将临时标记代换为最终标记．经过3个环节处理后，算法输出标记后的图像，图像中连通域按照由上到下，由左至右出现的顺序被标以连续的自然数。
    代码实现：
    #include <list>
    #include <vector>
    #include <algorithm>
    //连通区域属性结构
    typedef struct tagMarkRegion
    {
    std::list<POINT> MarkPointList;//点列表
    RECT rect;
    }MarkRegion;
     
    //定义MarkMap 结构，用来存放等价对
    typedef struct tagEqualMark
    {    int MarkValue1;    //标记值
    int MarkValue2;    //标记值
    } EqualMark;
     
    //定义MarkMapping 结构，用来存放标记映射关系
    typedef struct tagMarkMapping
    {    int nOriginalMark;   //第一次扫描的标记
    int nMappingMark;  //等价整理之后对应标记
    } MarkMapping;
     
    /*
    功能说明：将所选出的等价关系，attach到list上里
    参数说明：
         pEqualMark   等价关系
         num1         新的等价关系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.MarkValue1 != 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;
                  //插入到数组中
                  pEqualNum++;      
                  plEqualMark.push_back(pEqualMark);
             }
         }
     
    }
     
    /*
      功能说明：快速二值图像连通域标记
      参数说明：lpImgBits，表示图象数据区指针
                  nMarkNumbers，表示标记数量
                  iColorType，表示被标记颜色的值（，）
                  nImageWidth，表示图象的宽
                  nImageHeight，表示图象的高
      返回值：BOOL类型，TRUE，表示成功；FLASE，表示失败
    */
    BOOL MarkImage(BYTE * lpImgBits,int & nMarkNumbers,int iColorType,long nImageWidth,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 int[lSize+1];
         lpMarkMove=lpMark;
         ::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;
     
         //初始化图像移动指针
         lpImgBitsMove = lpImgBits;
     
         /*进行第一次扫描，将所得的等价对(EqualMark类型)加到lEqualMark链表中。
         使用nMarkValue来进行每一次新的标记，标记之后将其值加。
     
         Note1：图像的四周像素并不会有个相邻的像素。这时就要根据上、下、左、
         右四种不同的情况做不同的寻找等价对的判断。
         Note2：可以先对等价对进行排序，每次都保证MarkValue1<MarkValue2，
         这样易于管理等价对。
         Note3：在实际工作中，连续寻找出的等价对很容易重复，将本次找出的等价对
         和链表中保存的最后一个等价对相比较，如果不相等的话再存入等价对链表，
         这样可以大大降低链表中等价对的重复。
         Note4：第一次扫描之后，nMarkValue-1即为nMaxMarkValue。*/
     
         /************************************************************************/
         //下面为补充代码,完成对图像的第一次扫描
     
         //初始化图像数组和标识数组的指针
         int nEqualNum=0;
         EqualMark tempEqualMark;    //用以暂时存放每次找到的等价关系
         lpMarkMove=lpMark;
         lpImgBitsMove = lpImgBits;
     
     
         //标记图像的第一行、第一列的像素(只有这一个像素)
         if ( *lpImgBitsMove==iColorType )
         {
             *lpMarkMove=nMarkValue++;
         }
         lpMarkMove++;
         lpImgBitsMove++;
     
         //标记图像的第一行，此时不会出现等价的情况
         for ( i=1; i < nImageWidth; i++)
         {
             //需要标记的情况
             if ( *lpImgBitsMove==iColorType )
             {   
                  //前面没有被标记过，则开始一个新的标记
                  if ( *(lpMarkMove-1)==(!iColorType))
                  {
                       *lpMarkMove=nMarkValue++;
                  }
                  //前面被标记过，则跟随前一个标记
                  else
                  {
                       *lpMarkMove=*(lpMarkMove-1);
                  }
             }
             lpMarkMove++;
             lpImgBitsMove++;
         }
     
         //除第一行之外的标记，此时会出现等价的关系
         for ( j=1; j < nImageHeigt; j++ )
         {
             lpImgBitsMove=lpImgBits+j*nImageWidth;
             lpMarkMove=lpMark+j*nImageWidth;
     
             //对每行的第一个点做处理，总体就是对图像的最左列做处理
             //只需要检视上，右上两个点
             if ( *lpImgBitsMove==iColorType )
             {   
                  //<上>位置被标记过
                  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);
                       }
     
                  }
                  //<上>没有标记，此时一定不会存在等价关系
                  else
                  {
                       if ( *(lpMarkMove-nImageWidth+1)!=0 )
                       {
                           *lpMarkMove=*(lpMarkMove-nImageWidth+1);   //跟随<右上>标记
                       }
                       //<上>、<右上>都没有标记，则开始新的标记
                       else
                       {
                           *lpMarkMove=nMarkValue++;
                       }
                  }
             }
             lpMarkMove++;
             lpImgBitsMove++;
     
             //对每行的中间点做标记处理，此时存在<左>、<左上>、<上>、<右上> 4种情况
             for ( i=1; i<=nImageWidth-1; i++ )
             {   
                  //需要标记
                  if ( (*lpImgBitsMove)==iColorType )
                  {   
                       //<左>被标记过
                       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 ( *(lpMarkMove-1)!=*(lpMarkMove-nImageWidth) && *(lpMarkMove-nImageWidth)!=0)
                           {
                                //标记<左>、<上>等价
                                AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark);
                           }
     
                           if ( *(lpMarkMove-1)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0)
                           {
                                //标记<左>、<右上>等价
                                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) && *(lpMarkMove-nImageWidth)!=0)
                                {
                                     //标记<左上>、<上>等价
                                     AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark);
                                }
     
                                if ( *(lpMarkMove-nImageWidth-1)!=*(lpMarkMove-nImageWidth+1) && *(lpMarkMove-nImageWidth+1)!=0)
                                {
                                     //标记<左上>、<右上>等价
                                     AttachEqualMark(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);
                                     }
                                }
                                //<左>、<左上>、<上>未标记过，此时不存在等价关系
                                else
                                {
                                     if (*(lpMarkMove-nImageWidth+1)!=0)
                                     {
                                         *lpMarkMove=*(lpMarkMove-nImageWidth+1);       //跟随<右上>标记
                                     }
                                     //<左>、<左上>、<上>、<右上>未标记过，则开始新的标记值
                                     else
                                     {
                                         *lpMarkMove=nMarkValue++;
                                     }
     
                                }    //<左>、<左上>、<上>未标记过结束
                           }   //<左>、<左上>未标记过结束
                       }  //<左>未被标记过结束
                  }     // else 不需要标记
     
                  lpMarkMove++;
                  lpImgBitsMove++;
             }       //中间点处理的结束
     
             //对每行的最后一个点做处理，总体就是对图像的最左列做处理
             //此时存在<左>、<左上>、<上> 3种情况
     
             //需要标记
             if ( (*lpImgBitsMove)==iColorType )
             {   
                  //<左>被标记过
                  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 ( *(lpMarkMove-1)!=*(lpMarkMove-nImageWidth) && *(lpMarkMove-nImageWidth)!=0)
                       {
                           //标记<左>、<上>等价
                           AttachEqualMark(tempEqualMark,*(lpMarkMove-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark);
                       }
     
                  }
                  //<左>未被标记过
                  else
                  {
                       if ( *(lpMarkMove-nImageWidth-1)!=0 )
                       {
                           *lpMarkMove=*(lpMarkMove-nImageWidth-1);    //跟随<左上>
     
                           if ( *(lpMarkMove-nImageWidth-1)!=*(lpMarkMove-nImageWidth) && *(lpMarkMove-nImageWidth)!=0)
                           {
                                //标记<左上>、<上>等价
                                AttachEqualMark(tempEqualMark,*(lpMarkMove-nImageWidth-1),*(lpMarkMove-nImageWidth),nEqualNum,lEqualMark);
                           }
     
                       }
                       //<左>、<左上>未标记过
                       else
                       {
                           if ( *(lpMarkMove-nImageWidth)!=0 )
                           {
                                *lpMarkMove=*(lpMarkMove-nImageWidth);   //跟随<上>标记
                           }
                           //<左>、<左上>、<上>未标记过,则开始新的标记值
                           else
                           {
                                *lpMarkMove=nMarkValue++;
                           }
     
                       }
                  }
             }  //对每行的最后一个点做处理，总体就是对图像的最左列做处理
     
         }     //"除第一行之外的标记"的结束
     
         //因为在每次标记完之后，nMarkValue都会自动++
         //所以要通过（-1）操作来记录所标记的最大的个数
     
         nMaxMarkValue=nMarkValue-1;
         /************************************************************************/
         /* 定义双层链表的外层链表，它的元素是一个指向内层链表的指针。
         内层链表的型别也是CptrList，其元素是标记值。*/
         CPtrList exList;
         CPtrList * pInnerList;
         POSITION posExElem;   
     
         if ( lEqualMark.size() !=0 )
         {
             // pInnerListAdd，每次向exList中添加的新元素
             CPtrList * pInnerListAdd=new CPtrList;    
             ASSERT ( pInnerListAdd != NULL );
     
             /* 添加第一个等价对到exList的第一个元素所指向的InnerList中。 */
             pInnerListAdd->AddTail( (void *)lEqualMark.front().MarkValue1);
             pInnerListAdd->AddTail( (void *)lEqualMark.front().MarkValue2);
             exList.AddTail( (void *)pInnerListAdd );
             lEqualMark.pop_front();
     
             /* 定义pFindValue1和pFindValue2，存放在所有内层链表中找到特定值
             的某个内层链表的头指针，也就是外层链表的某个元素值。*/
             CPtrList * pFindValue1=NULL;
             CPtrList * pFindValue2=NULL;
     
             //整理剩余的等价对
             while ( !lEqualMark.empty() )
             {   
                  posExElem=exList.GetHeadPosition();
                  pFindValue1=NULL;
                  pFindValue2=NULL;
     
                  while ( posExElem )
                  {
                       pInnerList=(CPtrList *)exList.GetAt(posExElem);
                       if ( pInnerList->Find( (void *)lEqualMark.front().MarkValue1) )
                       {   
                           pFindValue1=pInnerList;
                       }
                       if( pInnerList->Find( (void *)lEqualMark.front().MarkValue2) )
                       {   
                           pFindValue2=pInnerList;
                       }
                       exList.GetNext(posExElem);
                  }
     
                  //该等价对中两个值都在已经整理过的等价关系中
                  if ( pFindValue1 && pFindValue2 )
                  {   
                       //当两个地址不一样时，对链表进行调整
                       if ( pFindValue1!=pFindValue2 )
                       {       
                           pFindValue1->AddTail(pFindValue2);
                           /* 清除链表元素，通过new得到的CptrList 类型，
                           必须采用delete进行删除，否则会造成内存泄露。*/
                           POSITION posDelete = exList.Find((void *)pFindValue2);
                           pFindValue2->RemoveAll();
                           delete pFindValue2;
                           exList.RemoveAt( posDelete );
                       }
                  }
                  /* 只在已经整理过的等价关系中找到Value1，
                  那么将Vaule2加到Value1所在的链表中。*/
                  else if ( pFindValue1 )
                  {
                       pFindValue1->AddTail((void *)lEqualMark.front().MarkValue2 );
                  }
                  else if ( pFindValue2)
                  {
                       pFindValue2->AddTail( (void *)lEqualMark.front().MarkValue1 );
                  }
                  /* 等价对中两个值在整理过的等价关系中都
                  没有找到，则在exList中增加新元素。*/
                  else
                  {
                       CPtrList * pInnerListAdd=new CPtrList;
                       pInnerListAdd->AddTail( (void *)lEqualMark.front().MarkValue1 );
                       pInnerListAdd->AddTail( (void *)lEqualMark.front().MarkValue2 );
                       exList.AddTail((void *)pInnerListAdd);
                  }            
                  //去掉此时等价对的头元素
                  lEqualMark.pop_front();
             }  // while ( !lEqualMark.IsEmpty() )循环结束
         }  // if ( lEqualMark.GetCount() !=0 )语句结束
         else  
         {
             /* 等价对链表大小为0，说明第一次扫描之后没有产生等价对，标记已经完成。*/
         int nMarkRegion=0;   //图像中连通区域个数
      //记录连通区域的个数
      nMarkRegion = nMarkValue-1;
      nMarkNumbers = nMarkRegion;
      if(nMarkRegion==0)
       return FALSE;
      //统计连通域属性信息
      MarkRegion *pRegionData = new MarkRegion[nMarkNumbers+1];
      for (int MarkNo = 0; MarkNo<nMarkNumbers;MarkNo++)
      {
       pRegionData[MarkNo].rect.left   = -1;
       pRegionData[MarkNo].rect.right  = -1;
       pRegionData[MarkNo].rect.bottom = -1;
       pRegionData[MarkNo].rect.top    = -1;
       pRegionData[MarkNo].MarkPointList.clear();
      }
    
      for ( j=0;j<nImageHeigt;j++ )
      {
       lpMarkMove=lpMark + j*nImageWidth; 
       for ( i=0;i<nImageWidth;i++ )
       {
        if ( *lpMarkMove > 0 )
        {
         if (pRegionData[*lpMarkMove-1].rect.left == -1)
         {
          pRegionData[*lpMarkMove-1].rect.left   = i;
          pRegionData[*lpMarkMove-1].rect.right  = i;
          pRegionData[*lpMarkMove-1].rect.bottom = j;
          pRegionData[*lpMarkMove-1].rect.top    = j;
          POINT ptInsert;
          ptInsert.x = i;
          ptInsert.y = j;
          pRegionData[*lpMarkMove-1].MarkPointList.push_back(ptInsert);
         }
         else
         {
          POINT ptInsert;
          ptInsert.x = i;
          ptInsert.y = j;
          pRegionData[*lpMarkMove-1].MarkPointList.push_back(ptInsert);
          if (pRegionData[*lpMarkMove-1].rect.left>i)
          {
           pRegionData[*lpMarkMove-1].rect.left = i;
          }
          if (pRegionData[*lpMarkMove-1].rect.right<i)
          {
           pRegionData[*lpMarkMove-1].rect.right = i;
          }
          if (pRegionData[*lpMarkMove-1].rect.top<j)
          {
           pRegionData[*lpMarkMove-1].rect.top = j;
          }
          if (pRegionData[*lpMarkMove-1].rect.bottom>j)
          {
           pRegionData[*lpMarkMove-1].rect.bottom = j;
          }
         }
        }
        lpMarkMove++;
       }
      }
      for(i=0;i<nMarkNumbers;i++)
      {
       listMarkData.push_back(pRegionData[i]);
      }
      if(pRegionData)
      {
       delete []pRegionData;
       pRegionData = NULL;
      }
             return TRUE;
         }       
     
         /*等价关系整理完成，下面建立第一次扫描的标记值和
         第二次扫描的标记值之间的映射关系。*/
     
         int nTotalEqualNum=0; //列入等价关系的标记个数
         int nMarkRegion=0;   //图像中连通区域个数
     
         posExElem=exList.GetHeadPosition();
         while ( posExElem )
         {   
             pInnerList=(CPtrList *)exList.GetAt(posExElem);
             nTotalEqualNum += pInnerList->GetCount();
             exList.GetNext(posExElem);
         }
         nMarkRegion=nMaxMarkValue-nTotalEqualNum+exList.GetCount();
     
         /* 定义第一次扫描和第二次扫描之间的映射向量，要使用vector，
         应该#include <vector>并且使用std命名空间。*/
         std::vector<MarkMapping> vMarkMap(nMaxMarkValue);
     
         //初始化映射向量，令其做自身映射
         for ( i=0;i<nMaxMarkValue;i++ )
         {   
             vMarkMap[i].nOriginalMark=i+1;
             vMarkMap[i].nMappingMark=i+1;
         }
     
         POSITION posInnerElem; //InnerList中元素的位置
         int nMin;              //InnerList中最小值
         int nIndex=0;
     
         posExElem=exList.GetHeadPosition();
         /* while循环实现了如下功能：找到每个等价组中最小的标记值，
         然后将映射向量中nMappingMark设定为其所在等价组的最小的标记值。*/
         while ( posExElem )
         {   
             pInnerList=(CPtrList *)exList.GetAt(posExElem);
             nMin=(int)pInnerList->GetHead();
             posInnerElem=pInnerList->GetHeadPosition();
             pInnerList->GetNext(posInnerElem);
     
             while ( posInnerElem )
             {
                  if ( (int)pInnerList->GetAt(posInnerElem)<nMin )
                  {   
                       nMin=(int)pInnerList->GetAt(posInnerElem);
                  }
                  pInnerList->GetNext(posInnerElem);
             }
     
             /* 根据每组等价关系中的最小的标记值对Mapping向量做出调整。*/
             posInnerElem=pInnerList->GetHeadPosition();
             while ( posInnerElem )
             {
                  nIndex=(int)pInnerList->GetAt(posInnerElem)-1;
                  vMarkMap[ nIndex ].nMappingMark=nMin;
                  pInnerList->GetNext(posInnerElem);
             }
             exList.GetNext(posExElem);
         }
     
         /* 将映射向量nMappingMark中不重复的部分找出并对其进行排序。
         使用find()和sort()这两种泛型算法，应该#include <algorithm>。*/
         std::vector <int> vSortMark(nMarkRegion); //排序向量
         nIndex=0;
     
         for ( i=0; i<nMaxMarkValue; i++ )
         {
             if  ( find( vSortMark.begin(),vSortMark.end(), vMarkMap[i].nMappingMark )
                  ==vSortMark.end() )
             {
                  vSortMark[nIndex++]= vMarkMap[i].nMappingMark;
             }
         }
         sort ( vSortMark.begin(),vSortMark.end() );
     
         /* 根据排序后的标记在vSortMark向量中的位置，对映射向量做出重新调整。*/
         std::vector<int>::iterator itFind;
         std::vector<int>::iterator itBegin;
         itBegin=vSortMark.begin();
     
         for (i=0;i<nMaxMarkValue;i++ )
         {
             itFind = find ( vSortMark.begin(),vSortMark.end(), vMarkMap[i].nMappingMark );
             vMarkMap[i].nMappingMark= ( itFind-itBegin + 1);
         }
     
         //根据映射向量对标记数组进行调整
         for ( j=0;j<nImageHeigt;j++ )
         {
             lpMarkMove=lpMark + j*nImageWidth;
             for ( i=0;i<nImageWidth;i++ )
             {
                  if ( *lpMarkMove != 0 )
                  {
                       *lpMarkMove = vMarkMap[ *lpMarkMove-1].nMappingMark;
                  }
                  lpMarkMove++;
             }
         }
     
         //删除链表结构中通过new得到的元素
         posExElem = exList.GetHeadPosition();
         while( posExElem )
         {
             pInnerList = (CPtrList *)exList.GetAt( posExElem );
             pInnerList->RemoveAll();
             delete pInnerList;
             exList.GetNext( posExElem );
         }
         exList.RemoveAll();
     
         //记录连通区域的个数
         nMarkNumbers = nMarkRegion;
     
         if(nMarkRegion==0)
             return FALSE;
     
         //统计连通域属性信息
         MarkRegion *pRegionData = new MarkRegion[nMarkNumbers+1];
         for (int MarkNo = 0; MarkNo<nMarkNumbers;MarkNo++)
         {
             pRegionData[MarkNo].rect.left   = -1;
             pRegionData[MarkNo].rect.right  = -1;
             pRegionData[MarkNo].rect.bottom = -1;
             pRegionData[MarkNo].rect.top    = -1;
             pRegionData[MarkNo].MarkPointList.clear();
         }
     
         //long offset = 0;
         for ( j=0;j<nImageHeigt;j++ )
         {
             lpMarkMove=lpMark + j*nImageWidth;  
             for ( i=0;i<nImageWidth;i++ )
             {
                  //offset = j*nImageWidth+i;
                  //lpMarkMove = lpMark+offset;   
                  if ( *lpMarkMove > 0 )
                  {
                       if (pRegionData[*lpMarkMove-1].rect.left == -1)
                       {
                           pRegionData[*lpMarkMove-1].rect.left   = i;
                           pRegionData[*lpMarkMove-1].rect.right  = i;
                           pRegionData[*lpMarkMove-1].rect.bottom = j;
                           pRegionData[*lpMarkMove-1].rect.top    = j;
                           POINT ptInsert;
                           ptInsert.x = i;
                           ptInsert.y = j;
                           pRegionData[*lpMarkMove-1].MarkPointList.push_back(ptInsert);
                       }
                       else
                       {
                           POINT ptInsert;
                           ptInsert.x = i;
                           ptInsert.y = j;
                           pRegionData[*lpMarkMove-1].MarkPointList.push_back(ptInsert);
                           if (pRegionData[*lpMarkMove-1].rect.left>i)
                           {
                                pRegionData[*lpMarkMove-1].rect.left = i;
                           }
                           if (pRegionData[*lpMarkMove-1].rect.right<i)
                           {
                                pRegionData[*lpMarkMove-1].rect.right = i;
                           }
                           if (pRegionData[*lpMarkMove-1].rect.top>j)
                           {
                                pRegionData[*lpMarkMove-1].rect.top = j;
                           }
                           if (pRegionData[*lpMarkMove-1].rect.bottom<j)
                           {
                                pRegionData[*lpMarkMove-1].rect.bottom = j;
                           }
                       }
                  }
                  lpMarkMove++;
             }
         }
         for(i=0;i<nMarkNumbers;i++)
         {
             listMarkData.push_back(pRegionData[i]);
         }
        if(pRegionData)
         {
             delete []pRegionData;
             pRegionData = NULL;
         }
         return TRUE;
     
    }

[http://comic.sjtu.edu.cn/thucs/GD\_jsj\_027y/text/chapter2/section5/part01/l1\_bq2.htm][http_comic.sjtu.edu.cn_thucs_GD_jsj_027y_text_chapter2_section5_part01_l1_bq2.htm]

2) 种子填充算法  
　　种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。  
种子填充算法常用四连通域和八连通域技术进行填充操作。  
　　从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。  
　　从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。  
　　一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图2.4a所示的区域的内部，而四向连通填充算法只能完成如图2.4b的部分填充。  
  
![tushi.gif][] 图2.4 四向连通填充算法

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div> 
     <img src="http://comic.sjtu.edu.cn/thucs/GD_jsj_027y/images/pic/chap02/image122.gif" alt="" height="185" width="210"> 
    </div> </td> 
   <td> 
    <div> 
     <img src="http://comic.sjtu.edu.cn/thucs/GD_jsj_027y/images/pic/chap02/image122_2.gif" alt="" height="185" width="206"> 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      a) 连通域及其内点 
    </div> </td> 
   <td> 
    <div>
      b) 填充四连通域 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

四向连通填充算法：  
a） 种子像素压入栈中；  
b） 如果栈为空，则转e)；否则转c)；  
c） 弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；  
d） 转b）；  
e） 结束。  
四向连通填充方法可以用递归函数实现如下：

![dingyi.gif][] 算法2.3 四向连通递归填充算法：  
void BoundaryFill4(int x, int y, long FilledColor, long BoundaryColor)  
\{  
　　long CurrentColor;  
　　CurrentColor = GetPixelColor(x,y);  
　　if (CurrentColor != BoundaryColor && CurrentColor != FilledColor)  
　　\{  
　　　SetColor(FilledColor);  
　　　SetPixel (x,y);  
　　　BoundaryFill4(x+1, y, FilledColor, BoundaryColor);  
　　　BoundaryFill4(x-1, y, FilledColor, BoundaryColor);  
　　　BoundaryFill4(x, y+1, FilledColor, BoundaryColor);  
　　　BoundaryFill4(x, y-1, FilledColor, BoundaryColor);  
　　\}  
\}

上述算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。一个改进的方法就是：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。

[Link 1]: http://blog.csdn.net/byxdaz/article/details/4422757
[http_comic.sjtu.edu.cn_thucs_GD_jsj_027y_text_chapter2_section5_part01_l1_bq2.htm]: http://comic.sjtu.edu.cn/thucs/GD_jsj_027y/text/chapter2/section5/part01/l1_bq2.htm
[tushi.gif]: http://comic.sjtu.edu.cn/thucs/GD_jsj_027y/images/but/tushi.gif
[dingyi.gif]: http://comic.sjtu.edu.cn/thucs/GD_jsj_027y/images/but/dingyi.gif