单次扫描完成二值图连通区域标记

from：
http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591477.html

连通区域标记算法




        二值图像的连通区域标记过程：从仅由”1”像素(前景点)和”0”像素(背景点)组成的一幅点阵图像中，将相互邻接的”1”值像素组合成区域，并用边界信息来描述每个连通区域。

传统的连通区域标记方法通常要对二值图像执行两次扫描。第一次扫描通过逐行逐列扫描像素。判断像素之间的相邻关系，对属于同一连通区域的像素赋予相同的连通标号，实现连通标识。这种逐行逐列的次序扫描的结果，通常会产生同一像素点被重复标记的现象，同一连通区域的不同子区域被赋予了不同的标记号。因此，需要执行第二次扫描来消除重复的标记，合并属于同一连通区域但是具有不同标记号的子区域。

传统方法的效率比较低，尤其是在重复性标记发生率高的情况下。本文方法受“并查集”(Union-Find Set)思想的启发，设计了一种高效的算法，该算法只需要一次扫描便能完成二值图像的连通区域标记过程。
等价类和并查集

UnionFind（合并查找）集可以实现等价类描述。假设一组元素，其中元素分为等价类。等价类满足以下性质：

（1）每一个元素只能属于一个等价类；

（2）等价类的同属关系具有传递性。

对于第二个性质，设顶点vi与vk属于同一等价类，顶点vk与vr属于同一等价类，则顶点vi和vk与vr都属于同一等价类。

这里我们关心等价类的合并(Union)和任意元素所属等价类名称的返回(Find)这两个操作。定义等价类的名称为类中某个特定的元素，由于每个元素只可能属于一个等价类，所以每个等价类的名称一定是唯一的，我们称之为这个等价类的根(Root)。

除等价类根以外的每个元素都有一个父节点元素（表示为Parent），同一等价类中元素（除根外）的根节点相同，根的父节点标注为-1。合并两个等价类时，可以分别指定两个等价类中任意元素与，首先返回这两个等价类的根, ，然后重置其中一个根节点的父节点，如Parent，将对应的等价类中元素合并至对应的等价类中。

如图3-7所示为以和为根节点的两个等价类，分别指定等价类中和，合并这两个等价类Union()。如图(a)所示。首先分别寻找(Find)到和的根节点和，并对集合的结构做调整，从而降低树结构的深度，提高寻找节点的效率，如图(b)所示；最后将的根节点重置为，完成两个集合的合并，如图(c)所示。





图中x表示节点为，其父节点y。



连通区域标记算法描述


    本文中借助并查集设计二值图的连通区域标记算法，其中, 。初始化阶段，将二值图每个像素点视为单独的连通区域，并分别对应一个等价类，形成等价类，。例如，位置对应等价类，该等价类对应连通区域的边界信息为：
    (top, down, left, right)=(y, y, x, x).
经过一次扫描，实现二值图中连通区域标记的算法流程如下：
 
复制代码
    Step1 初始化变量 i=1；
    Step2 寻找二值图中第一个位于背景中的像素位置，对应等价类记为背景等价类；
    Step3 遍历第个位置；
    Step4 若位于背景中，则将其对应等价类与背景等价类归并，跳转至Step9；否则，继续Step5；
    Step5 若位于前景中，则检测其左上、正上、右上和正左方四个位置，分别对应等价类的标号：，对应等价类，选择其中位于前景中的位置对应的等价类，组成集合：
   
    Step6 若为空，则跳至Step9；否则继续Step7；
    Step7 将中等价类归并为一个等价类，对应连通区域的边界信息：
    Step8 将对应等价类与归并，利用与Step7中相同的方法更新归并后的等价类对应的连通区域的边界信息；
    Step9 i=i+1，若i<=k，则跳转至Step3，否则算法结束。
复制代码

      除了背景等价类外，最终留下的等价类对应二值图中的连通区域。算法流程中Step5中对当前位置的四个邻点对应的连通区域进行合并。例如下图(a, b)，当前位置的左上点和正左点同属于等价类，对应区域边界信息为；正上点属于背景等价类；右上点属于等价类，对应边界信息为。首先由位于前景中的等价类组成集合，归并中等价类和等价类，形成等价类，然后归并当前位置对应的等价类与，并等价类对应边界区域信息更新。

     从流程图中可以发现，算法通过一次扫描便完成了连通区域标记过程。在合并像素点与其相邻区域时该算法只关心四个相邻点的所在的区域，这极大地提高了算法执行效率，算法复杂度为线性的。