快速连通域分析算法及其实现

《快速连通域分析算法及其实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第16卷第1期模式识别与人工智能V01．16No．12003年3月PR&AIMarch2003快速连通域分析算法及其实现孔斌(中国科学技术大学自动化系合肥230027)(中国科学院合肥智能机械研究所合肥230031)摘要本文提出一种快速连通域分析算法，它对像素的行程进行操作，并将标号作为行程及连通域的特征之一，特征通过数据结构的指针与行程及连通域相联系．该算法运用了两个关键技术，一是设计了一种链式机制来表示和实现标号的等价关系，二是通过指针的传递来实现标号及其它特征的向下传递和逆向传播，特征在标号过程中动态修改．这样甚至能实现

2、仅对图像一遍扫描便能完成连通域标记和常用特征量的计算．实验表明了本文算法的有效性．关键词连通域分析，连通域标记，行程，链式等价机制，指针中图法分类号TP3911引言性能和配置的提高，算法对存储空间的要求已较容易满足，算法运行时间也大大降低了．但是对于实际应用常常具有的实时要求，现有算法一般仍不能满在许多计算机视觉应用中，常常需要进行连通足．所以，寻求快速算法仍是研究者的目标．域分析(CCA，ConnectedComponentAnalysis)．它包本文提出的算法，不仅能很快得到连通域的标括了三部分操作内容：(1)连通域标记(CCL，Con—号，而且也能在标号的过程中方便地

3、计算连通域的nectedComponentLabeling)，即在规定的连通性定多种常用的灰度和形状特征，标号完成时也得到各义下，给每一个物体或目标(即所谓的连通域)分配种特征统计值．因此称该算法为快速连通域分析算一个唯一的非零标号；(2)计算每一个连通域的形法(而不仅仅是快速连通域标号算法)．文中将详细状特征；(3)计算每一个连通域的灰度特征．其中连介绍该算法的决窍，并通过将其标号部分与三种著通域标记是后两部分计算的基础．如果设定标号为名的连通域标号算法的实验比较和分析来说明本文连续自然数，那么最后所得到的最大的连通域标号方法的高效性．就是图像中所有的连通域的总数．对连通

4、域进行标记的一种直接而简单的方法包2快速连通域分析算法含搜索和传递两个步骤⋯1．该方法虽然简单，但极费时，因此研究者们提出了许多改进的方法_2-4j．可以文献[1]指出，加速连通域标号执行过程的一种说，到上世纪80年代，连通域标记算法已经成熟；但常用方法是对目标像素的行程(run—length)而不是是，近十多年来仍不断能见到与其有关的杂志及会对每个像素本身进行标号．快速连通域分析算法(下议论文_5-1．这主要是因为大多数算法需花费较多文中简称为FCCA算法)吸收了这一思想，针对目标的时间和俄存储空间，使其实际应用受到限制；另像素的行程进行标号和等价类分析．这个算法的关一方

5、面是它经常被用于在多处理器系统中研究并行键之处是把行程的标号作为行程的一个特征来处算法及性能[，0一．理，行程的特征通过结构指针与行程段相联系，并且近年来，随着电子技术的发展以及计算机整体令属于同一个连通域的所有行程段拥有同一个特征收稿日期：2001—10—13；修回日期：2002—10—28维普资讯http://www.cqvip.com1期孔斌：快速连通域分析算法及其实现数据块．这样可以通过指针的传递来实现标号及其过结构指针的指示都拥有共同的特征块，这一步隐式地实现它特征的传递．并且，设计了一种链式机制使等价关了标号的传递和逆向传播．]系的表示和记录在1维数组中就能实现

6、，也易于进STEP8如有必要，根据等价数组将行程标号改为连续自然数，或进行行程解码(run—lengthdecoding)得到标号图行等价类划分．像◇下面先给出本文的FCCA算法步骤的描述，并可以对本算法标号的正确性进行证明，它与稍加解释．Lumia算法的证明l_2J类似．区别在于，本算法利用指FCCA算法：针使所有属于同一个连通域的行程都有共同的特征假设已对输入图像进行了编码(run-lengthencoding)．STEP1创建并初始化等价数组．并设LABEL=1，行块，通过指针的传递隐式地实现了标号的传递、等价程指针指向第一个行程段．和逆向传播过程．这里不再给出详细证

7、明．STEP2如果行程指针指示图像行程结束，GOTOFCCA算法的另一个重要特点和优点，是它能STEP8．很容易地在标号过程中同时把连通域的常用灰度、STEP3如果当前行程THIS在前一行中没有相邻接形状特征计算出来．这就是不把它仅仅称为快速连的行程，通域标号算法，而是称为快速连通域分析算法的原3．1为THIS创建一个新的特征块；因．另外，如果一边扫描图像获得行程编码，一边便3．2把LABEL赋给THIS，并计算THIS的其它特征；对所获得的行程进行标号和特征计算，那么甚至能3．3L=LABEL+1，行程指针加1，