连通分量标记算法

淩亂°似流年 2022-08-21 07:46 161阅读 0赞

## 引言 ##

图像分割领域中一个重要步骤是求取图像的连通区域，后续图像轮廓理解的基石。  
Matlab图像工具箱函数bwlabel函数，就是对二值图像连通区域进行标记的函数。

> **bwlabel**  
> Label connected components in 2-D binary image。  
> **Syntax**  
> L = bwlabel(BW, n)  
> \[L, num\] = bwlabel(BW, n)  
> **Description**  
> L = bwlabel(BW, n) returns a matrix L, of the same size as BW, containing labels for the connected objects in BW. The variable n can have a value of either 4 or 8, where 4 specifies 4-connected objects and 8 specifies 8-connected objects. If the argument is omitted, it defaults to 8.

该函数返回一个与原图大小一致的标记图像矩阵。冈萨雷斯书中只介绍了其使用方法，没有介绍其实现原理等，OpenCV也有connectedComponents函数。有必要造轮子，理解步骤。

## Two-pass算法 ##

这里我实现的是Two Pass算法，四邻域。该算法对二值图像扫描两次：

1.  当前像素点若是前景（非零），判断其已扫描过的邻接节点（上邻像素，左邻像素）有无已标记的。若仅有一个含有标记值，则将该标记赋予该位置，若两个都含有标记值，将最小标记赋予当前值，并将这两个标记值合并（Union），归为同一类；若无，新增标记赋予当前值，即label++。
2.  对上述含有标记的像素，查找其集合的根节点(Find)，用根节点对当前值赋值。

执行动态图如下（该图是盗网友的，上面有logo的）。

![并查集][20160423123223224]

这里使用了一种并查集的数据结构，可以看作数组方式实现的树结构。该结构主要含有两个操作：

*  快速对集合元素合并归类
 *  快速查找一个元素的根节点

这在严蔚敏的数据结构书中有介绍过的。看一下下图，希望能赶紧回忆起来吧。

![并查集][20160423121950581]  
  
这个并查集数组，初始化的时候全为0，即每个都是根节点。然后我们发现有些元素属于同一类，就将其一个节点作为另一个节点的孩子，合并为同一个树。最后，我们都用每个集合的根节点的作为该集合的标志。

## 代码 ##

#define MAXLABEL 500
    uchar parent[MAXLABEL] = {
       0};
    
    int Find(uchar x, uchar parent[]) 
    {
        int i = x;
        while (0 != parent[i])
            i = parent[i];
        return i;
    }
    
    void Union(uchar big, uchar small, uchar parent[]) 
    {
        uchar i = big;
        uchar j = small;
        while (0 != parent[i])
            i = parent[i];
        while (0 != parent[j])
            j = parent[j];
        if (i != j)
            parent[i] = j;
    }
    
    Mat Label(Mat &I)
    {
        /// first pass
        int label = 0;
    
        Mat dst = Mat::zeros(I.size(), I.type());
        for (int nY = 0; nY < I.rows; nY++)
        {
            for (int nX = 0; nX < I.cols;nX++)
            {
                if (I.at<uchar>(nY,nX) != 0)
                {
                    uchar left = nX - 1<0?0:dst.at<uchar>(nY, nX - 1);
                    uchar up = nY - 1<0?0:dst.at<uchar>(nY - 1, nX);
    
                    if (left != 0 || up != 0)
                    {
                        if (left != 0 && up != 0)
                        {
                            dst.at<uchar>(nY, nX) = min(left, up);
                            if(left < up)
                                Union(up,left,parent);
                            else if(up<left)
                                Union(left, up, parent);
                        }
                        else
                            dst.at<uchar>(nY, nX) = max(left, up);
                    }
                    else
                    {
                        dst.at<uchar>(nY, nX) = ++label;
    
                    }
                }
            }
        }
    
        /// second pass 
        for (int nY = 0; nY < I.rows; nY++)
        {
            for (int nX = 0; nX < I.cols; nX++)
            {
                if (I.at<uchar>(nY, nX) == 1)
                    dst.at<uchar>(nY, nX) = Find(dst.at<uchar>(nY, nX), parent);
            }
        }
        return dst;
    }

## 效果 ##

为了显示好看，我将连通区域着色，这里使用哈希函数，将每个标记乘以一个素数对256求余，这样可以将颜色散列开来。

![并查集][20160423130013784] ![并查集][20160423130059776]

## 更多阅读 ##

George Stockman and Linda G. Shapiro. 2001. Computer Vision (1st ed.). Prentice Hall PTR, Upper Saddle River, NJ, USA. Chapter 3.

[20160423123223224]: /images/20220724/c9476f45ebe44b34a87eecfc730392fd.png
[20160423121950581]: /images/20220724/8fee2d56a9474498bf58499959fb12a3.png
[20160423130013784]: https://img-blog.csdn.net/20160423130013784
[20160423130059776]: /images/20220724/393aa1a91ec14da884806a1e93307115.png