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),当前位置的左上点和正左点同属于等价类,对应区域边界信息为;正上点属于背景等价类;右上点属于等价类,对应边界信息为。首先由位于前景中的等价类组成集合,归并中等价类和等价类,形成等价类,然后归并当前位置对应的等价类与,并等价类对应边界区域信息更新。
从流程图中可以发现,算法通过一次扫描便完成了连通区域标记过程。在合并像素点与其相邻区域时该算法只关心四个相邻点的所在的区域,这极大地提高了算法执行效率,算法复杂度为线性的。
分享到:
相关推荐
二值图像连通区域的检测和标记在图像分析中是十分重要的步骤,高效的连通区域标记算法能大大提高图像处理速度。针对此,提出一种新的基于游程编码的连通体标记算法。扫描图像,记录所有的游程编码并将等价对添加到...
一次扫描连通区域标记算法C++
使用大津算法来获取最佳阈值来实现二值化后,通过按行两次扫描法进行连通区域标记。
该算法主要采用8邻域搜索及排序队列方式实现,通过一次扫描二值图像即可完成连通区域标记。提出一种新的8邻域搜索策略,可以将邻域搜索次数由八次减少到平均四次以下,从而提高了系统效率。此外,还给出一种排序...
本资源介绍了一种高效的基于二值图像的连通域标记的算法
基于共同连通域数组的二次扫描算法的matlab实现
接着在视频流的采集传输过程中,以流水线的方式按照视频传输顺序对图像进行逐行像素扫描,然后对每个像素的邻域分别按照逆时针方向和水平方向进行连通性检测和等价标记关系合并,检测出的结果对标记等价数组和标记...
基于opencv,通过对二值图片的两次扫描并对其标记,实现连通区域的着色
适合二值图像,通过自动扫描提取种子点,注释详细 参考文献:一种二值图像连通区域标记的新方法 陈柏生著。
针对二值边缘图像目标点较少的特点,提出了基于目标像素邻域的8方向生长区域标记算法。该算法充分利用了边缘图像的走向信息,提高了搜索效率,降低了堆栈空间消耗,消除了邻域反复扫描问题。
区域生长法利用区域生长的思想,一次生长过程可以标记一整个连通区,只需对图像进行一次扫描就能标记出所有连通区。算法描述如下: 输入待标记图像bitmap,初始化一个与输入图像同样尺寸的标记矩阵labelmap,一个...
包含了区域连通标记算法以及扫描法计算二值图像面积代码
在分析已有区域标记算法的基础上,提出了一种新的二值图像连通区域准确标记算法。顺序扫描和标记二值图像的各个像素点,准确判断标记过程中出现的标记冲突,并建立标记冲突的模型,在算法中增加回溯扫描算法,消除...
基于线段扫描法进行二值图像连通域分割时,对数据量较多且形状复杂的遥感二值图像,容易使邻接表存储大量的等价对信息,即浪费存储空间也不利于算法合并处理。针对这一不足,提出了一种基于线段的快速标号算法,采用...
在研究已有算法的基础上,提出一种基于游程递归的标记算法,该算法可以对二值图像实现快速标记。顺序扫描图像,寻找未标记的游程,并递归搜索与之连通的游程,直到一个连通区域生成。在游程搜索过程中,在当前游程的...
用于CT扫描的二值化图像多重分形计算
针对这一问题,提出了一种基于纹理分析的图像二值化方法。该方法在动态阈值的基础上,通过对分块后子图像的纹理特性进行分析,将子图像分成不同的类型,进而对不同类型的子图像进行不同的处理,很好地消除了图像黑边...
针对无行消隐图像不间断输入的高速图像...FPGA仿真结果表明:对连续输入的二值图像进行连通区域标记和特征提取时,运行时间仅由图像输入时间和等价表合并时间组成,明显优于其他方法,可适用于图像的快速识别与跟踪。
这里列举二值图像连通域标记算法包括直接扫描标记算法和二值图像连通域标记快速算法
在STM8S103单片机上使用ADC的单次扫描模式,并开启通道的模拟看门狗功能,扫描2、3、4通道的电压值,同时开启通道4电压采样的模拟看门狗功能,当通道4的电压值低于下限值或者高于上限值时,就会产生模拟看门狗的中断...