基于游程的连通区域标记两次扫描快速算法*

吕常魁 徐岩 罗冰心

(南京航空航天大学 机电学院， 江苏 南京 210016)

基于游程的连通区域标记两次扫描快速算法*

吕常魁 徐岩 罗冰心

(南京航空航天大学 机电学院， 江苏 南京 210016)

为提高二值图像连通区域标记(CCL)的计算效率，提出快速游程标记(FRL)算法，对基于游程的两次扫描算法中的传统游程连通检测算法进行了优化；然后介绍了基于FRL与并查集的整体算法；最后对FRL的计算效率进行了实验验证，并将整体算法与RTS 与SAUF 两种典型的两次扫描CCL算法进行了比对分析.结果表明：FRL算法省去了行间游程不必要的后续比对，使得比对形式接近于链式，大幅度提高了游程标记的计算效率，时间复杂度由传统RL算法的O(mn)降为O(m+n-1)，执行时间降为与并查集运算环节同一量级；整体算法的性能明显优于RTS算法，总体上略优于SAUF算法.

连通区域标记；两次扫描算法；连通检测算法；游程标记；并查集

连通区域标记(CCL)是机器视觉、模式识别等领域的重要底层基础算法之一.CCL以像素或游程为基本处理单元，检测二值图像中属于同一连通区域的所有单元并进行区域标记.CCL按扫描模式主要可分为多次扫描算法[1- 2]、两次扫描算法[3- 12]和一次扫描算法[13- 14].常用的CCL算法以两次扫描算法为主.两次扫描算法一般分为3个阶段：① 扫描图像，检测单元间连通性，赋予各单元临时标记并记录单元间等价标记信息；② 处理等价对表，获得各临时标记的最终标记；③二次扫描各单元，赋予各单元最终标记.现代两次扫描算法多基于传统算法，在加快等价对处理速度[4- 5,10,12- 13]、减少近邻搜索次数[7,11]、并行计算[8- 9]等方面对算法进行优化.

基于游程的两次扫描算法是现代主流算法之一.游程指二值图像行序列中由连续的、具有相同灰度级的像素(一般指前景像素)构成的线片段.以游程作为基本处理单元，消除了像素级处理中行间像素的阶梯形邻接产生等价对的现象，有效减少了等价对数量[15].现代算法多在提升等价标记处理效率方面开展研究[4- 5,10,12]，而在第一环节的行间游程连通性检测中，多采用双层循环遍历比对的传统模式.研究发现，基于游程的CCL算法较为耗时的往往是第一个环节.本研究首先提出快速游程标记(FRL)算法，该算法对传统游程连通性检测算法进行了优化；然后介绍了基于FRL与并查集的整体算法，整体算法应用高效的并查集算法RemSP[16]进行等价标记处理；最后，对FRL的计算效率进行了实验验证，并将整体算法与RTS[5]、SAUF[7]这两种典型的两次扫描CCL算法进行了实验比对分析.

1 FRL算法描述

采用结构R(Row，StartCol，EndCol，Label) 表示游程，4个参数依次为游程的行号、起始列标、终止列标与临时标记号.设当前行Xi+1游程为Ri+1，上一行Xi游程为Ri，按8连通判断规则，则Ri+1与Ri连通的充要条件为：Ri+1·StartCol ≤Ri·EndCol+1且Ri+1·EndCol ≥Ri·StartCol-1.假设Ri已被标记，则Xi+1游程标记和等价对生成的一般规则如下：

① 如果Ri+1与Ri连通且Ri+1未标记，则Ri+1·Label←Ri·Label；② 如果Ri+1与Ri连通，而Ri+1已标记，且Ri+1与Ri标记号不相同，则生成等价对Ri+1·Label,Ri·Label；③ 如果Ri+1与上一行所有游标均不连通，则赋予Ri+1新标记.

传统游程标记算法按从左到右顺序，将Xi+1每一游程与Xi所有游程两两比对，进行连通状态检测与游程标记.设Xi与Xi+1游程个数分别为m和n，则Xi+1所有游程标记算法时间复杂度为O(mn).为便于说明，称该算法为RL.研究发现，利用游程间的位置关系，可以省去不必要的后续比对，将算法时间复杂度降为O(m+n-1).将上下行游程间位置关系定义为图1所示的4种基本类型.

图1 游程间4种基本位置关系

以图2为例，按8连通判断规则，说明这4种基本类型的处理规则：① 按从左到右顺序，首先将Xi第一个游程Ri(1)与Xi+1第一个游程Ri+1(1)进行比对.Ri(1)与Ri+1(1)不连通，且Ri(1)·EndColRi+1(1)·EndCol +1，属图1(b)中类型，该情况下，Ri(2)后续游程均不可能与Ri+1(1)连通，故Ri+1(1)退出比对序列，取Ri+1(1)下一游程Ri+1(2)，与Ri(2)继续比对；③Ri(2)与Ri+1(2)连通，且Ri(2)·EndCol≤Ri+1(2)·EndCol，属图1(c)中类型，该情况下，Ri+1(2)后续游程均不可能与Ri(2)连通，则Ri(2) 不再参与比对，对Ri+1(2)进行标记或生成等价对后，取Ri(2)下一游程Ri(3)，与Ri+1(2)继续比对；④Ri(3)与Ri+1(2)连通，且Ri(3)·EndCol>Ri+1(2)·EndCol，属图1(d)中类型，该情况下，Ri(3)后续游程均不可能与Ri+1(2)连通，故Ri+1(2)不再参与比对，对Ri+1(2)进行标记或生成等价对后，取Ri+1(2)下一游程Ri+1(3)，与Ri(3)继续比对.

考虑一般情况，行间每两个游程按上述规则比对结束后，其间必有一个游程因不可能与比对行后续游程连通而退出比对，则其所属行下一游程继续加入比对.这种比对过程接近于链式，设上下行游程个数分别为m和n，则比对过程时间复杂度为O(m+n-1).算法实现要点如下：① 以Xi游程作为比对参考游程，仍按双重循环形式与Xi+1游程比对(Xi游程为外循环，Xi+1游程为内循环)，进入内循环前，如果Xi当前游程尚未标记，则进行标记；② 基于上文规则，按从左到右顺序比对Xi与Xi+1间游程，设当前比对游程为Ri(a)与Ri+1(b)，则：若Ri+1(b)退出比对，则继续内循环，取Xi+1下一游程Ri+1(b+1)与Ri(a)继续比对；若Ri(a)退出比对，则跳出内循环，继续外循环，取Xi下一游程Ri(a+1)与Ri+1(b)及其后续游程继续比对；③ 对于当前行Xi+1游程 ，只对与Xi游程有连通关系的进行标记.

设Xi+1为当前行，搜索Xi+1获得游程集合{Ri+1(b)}，b{0,1,…,n-1}，游程Label参数值均

图2 行间游程位置关系及比对形式示例

置为-1，表示未标记；设上一行Xi游程集合为{Ri(a)}，a←{0,1,…,m-1}，当前最大临时标记表示为MaxLabel.将该算法命名为FRL，伪码如下：

算法1 Procedure FRL (Ri,Ri+1)

输入:Xi游程集合{Ri(a)}；Xi+1游程集合{Ri+1(b)}；当前最大临时标记MaxLabel.

结果: 标记Xi+1中与Xi有连通关系的游程，标记Xi中未标记的游程；生成等价对.

1k←0;

2fora←0 tom-1do

3begin

4ifRi(a). Label=-1then∥标记Xi中未标记的游程

5begin

6 MaxLabel←MaxLabel+1;

7Ri(a)·Label←MaxLabel;

8end;

9forb←kton-1do

10begin

11k←b;

12ifRi(a)·EndCol

thenbreak; ∥类型a

13ifRi(a)·StartCol >Ri+1(b)·EndCol +1

thencontinue; ∥类型b

14ifRi+1(b)·Label=-1thenRi+1(b)·Label←Ri(a)·Label

15elseifRi(a)·Label≠Ri+1(b)·Labelthen处理等价对Ri(a)·Label,Ri+1(b)·Label;

16 ifRi(a)·EndCol≤Ri+1(b)·EndColthenbreak;∥类型c；类型d则继续内循环

17end;

18end;

2 基于FRL与并查集的整体算法描述

整体算法分为游程搜索与存储、游程标记与等价对生成、等价对合并、游程最终标记4个基本环节.设二值图像大小为w×h(宽度×高度)，则其最大可能游程个数为w×h/2，最大可能连通区域个数为w×h/4.建立尺寸为w×h/2的一维数组A，用以存储临时标记号的最终标记.鉴于本研究应用并查集算法进行等价对合并操作，根据并查集算法思想，首先按各临时标记均为孤立节点状态对A进行初始化：A[m]←m，m←{0,1,…，wh/2-1}.

第1环节负责搜索图像各行游程，生成并存储游程数据结构.为便于下文说明，命名该计算环节为RS.将图像左右边缘置为背景点，设二值图像背景、前景灰度值分别为vb和vo，令v←voxorvb，则当前行Xi中满足Xi[i]xorXi[i+1]=v的像素即为各游程的起始像素或中止像素.对图像进行光栅扫描，获取各行游程，将所有游程数据结构存于一维动态数组容器RVector中，以便于后续的连通区域特征计算.游程数据结构Label参数值均置为-1，表示未标记.

第2环节应用FRL算法对RVector中行间游程进行比对，判断其连通性，按上文所述规则，赋予RVector中未标记游程临时标记号(Label参数)，并生成等价对表.这里可以应用游程数据结构的Row参数来判断游程所属行，从而获取相邻两行的游程.此外，FRL计算结束后，需继续扫描图像最后一行的游程，将其中Label参数为-1的游程按上文规则赋予临时标记号.

第3环节应用并查集算法对等价对表中的所有等价对进行合并，目的是根据等价对所反映的临时标记间的动态连通关系构建并查集树.在游程标记过程中，每生成一个等价对，即基于数组A所反映的临时标记间动态父子关系，对等价对两个临时标记分别进行根节点搜索操作，合并两个临时标记所属支路，将较大根节点的父节点指向较小根节点，这里将A数组中以较大根节点序号为下标的元素值置为较小根节点序号.为提高后续根节点搜索效率，通常需要对支路进行路径压缩.图像游程等价对形成的支路一般高度较低，如果路径压缩过程中存在过多中间数组操作，反而会降低计算效率.根据Patwary研究成果[16]，采用较为高效的RemSP算法.RemSP算法不刻意进行根节点搜索，以快速进行支路合并为目的，巧妙运用插接(SPlicing，SP)方法，便搜索边合并，直至到达某一支路的根节点.

第4环节的目的是确定并更新所有临时标记的最终标记.全部等价对合并操作结束后，形成并查集森林.对并查集森林进行基于PH算法[16]的Find运算，按由大到小顺序进行临时标记的根节点搜索，并进行最终路径压缩操作，将每一临时标记的父节点标记号置为其所属并查集树根节点标记号.二次扫描RVector，赋予各游程最终标记号.对于游程R，其最终标记为：R·Label←A[R·Label].

3 实验结果分析

测试所用PC机配置如下：CPU为Intel Core(TM)2 Quad，主频2.66 GHz，内存3.0 GB，操作系统为 Windows XP.算法均用Pascal语言实现.实验图像含随机图像与真实图像两类.随机图像尺寸为1 024×1 024，按从1×1到10×10的10种粒度，分别随机生成前景像素比例范围为1%～99%的二值图像序列(见图3).真实图像源自南加州大学信号图像处理研究所的SIPI图库[17]，在SIPI两个子库Textures与Aerials中，各选取了25幅尺寸均为1 024×1 024的图像.应用Otsu算法对图像进行二值化，采用取多次重复运算均值的方式获取相应运算环节的执行时间.

图3 前景像素比例为50%的不同粒度随机图像

Fig.3 Random images with a percentage of object pixels 50 %at different granularities

为检验FRL算法性能，同时观察各环节占整体执行时间的比重，首先对整体算法各环节独立进行执行时间测试实验，这需要在第2环节生成等价对表，在第3环节对等价表进行批处理.根据测试结果，第4环节耗时量级一般远小于其他环节，故将第3、第4环节纳为一个环节进行测试.实验同时测试了RL算法，并与FRL进行比对.5×5粒度随机图像序列不同前景像素比例下的测试结果如图4所示，真实图像测试结果如表1所示.

表1 真实图像测试中各环节执行时间的最大值、均值与最小值

Table 1 Maximum，mean and minimum execution times of diffe-rent algorithm modules for real images

图库表征参数执行时间/msRSRLFRLRemSP+FindTextures最大值12.251.14.01.6均值7.715.11.50.7最小值2.92.40.30.004Aerials最大值10.130.63.01.7均值8.317.82.01.1最小值7.411.51.60.005

由图4及表1可以看出，传统游程标记算法模式下，RL环节较为耗时，运行时间随游程数量的增加呈指数级增长；RS环节次之，但其耗时与RL属同一数量级；并查集运算环节(RemSP+Find)耗时最少，一般情况下要比RL与RS至少低一个数量级.应用FRL算法替代RL算法，取得了非常理想的结果，近似链式的比对方式使得游程标记环节计算耗时大幅度降低，降为与并查集运算环节同一量级.由图4可以看出，随着随机图像前景像素比的增加，虽然游程数量呈二次曲线形式变化，但FRL曲线仍保持了良好的线性.

图4 随机图像序列前景像素比例变化时游程标记信息与各环节执行时间

Fig.4 Execution times of the every algorithm module and the run-length labeling information versus object pixels percentage of random image sequences

将整体算法(RS+FRL+ RemSP+Find)与RTS、SAUF算法进行了计算耗时比对.RTS与SAUF是CCL二次扫描算法中较为高效的代表性算法.RTS以游程为基本处理单元，以传统RL方法进行游程搜索，以数组式链表的方式进行等价标记合并，每次合并都对被合并链表中的标记进行一次最终标记更新操作；SAUF算法则以像素为基本处理单元，应用决策树算法快速进行像素的近邻搜索、标记与等价对生成操作，应用优化的并查集算法进行等价标记处理.随机图像与真实图像的比对结果分别如图5、表2所示.

图5 随机图像序列前景像素比例变化时各CCL算法执行时间对比

Fig.5 Comparative execution times of different CCL algorithms versus object pixels percentage of random image sequences

表2 真实图像测试中各CCL算法执行时间的最大值、均值与最小值

Table 2 Maximum，mean and minimum execution times of different CCL algorithms for real images

图库表征参数执行时间/msRTSSAUFRS+FRL+RemSP+FindTextures最大值70.617.617.3均值 21.612.39.1最小值3.52.92.5Aerials最大值48.916.516.4均值 29.014.211.7最小值9.912.05.9

由图5可以看出，对于RTS算法，基于 RL的游程搜索耗时随游程数量增长以二次曲线形式急剧增加；在等价标记处理阶段，数组式链表长度的不断增长降低了后续等价对的处理效率.故随着游程数量与等价对数量的增加，RTS算法执行效率明显下降.SAUF算法则相对比较稳定，决策树算法的应用使得其在图像连通情况较为复杂的情况下，搜索与标记效率往往要高于基于游程的RS+RL算法.图5同时表明，等价标记处理阶段中，在等价对数量较大情况下，经路径压缩优化的并查集算法比RTS数组式链表合并方法具有更好的鲁棒性.

文中算法在游程标记阶段应用FRL算法替代传统RL算法，在等价标记处理阶段则采用了效率较高的RemSP并查集算法，这两个环节均优于RTS；与SAUF比较，虽然在等价标记处理环节均采用了并查集优化算法，但在单元搜索与标记阶段， FRL对该环节执行效率的大幅度提升使得 RS+FRL方法总体上一般要优于SAUF中的决策树算法模式.由表2中的统计数据也可以看出，文中算法明显优于RTS算法，总体上略优于SAUF算法.

4 结论

(1)FRL算法省去了行间游程不必要的后续比对，使得比对形式接近于链式，时间复杂度由传统RL算法的O(mn)降为O(m+n-1)，执行时间降为与并查集运算环节同一量级.

(2)整体算法的性能明显优于RTS算法，总体上略优于SAUF算法.

[1] HARALICK R M，SHAPIRO L G.Computer and robot vision(Volume 1) [M].Boston: Addison Wesley，1992.

[2] SUZUKI K，HORIBA I，SUGIE N.Linear-time connected-component labeling based on sequential local operations [J].Computer Vision & Image Understanding，2003，89(1): 1- 23.

[3] ROSENFELD A，PLATZ J.Sequential operator in digital pictures processing [J].Journal of ACM，1966,13(4):471- 494.

[4] LACASSAGNE L，ZAVIDOVIQUE B.Light speed labeling: efficient connected component labeling on RISC architectures [J].Journal of Real Time Image Processing,2011，6(2):117- 135.

[5] HE L，CHAO Y，SUZUKI K.A run-based two-scan labeling algorithm [J].IEEE Transactions on Image Processing，2008，17(5): 749- 756.

[6] FIORIO C，GUSTEDT J.Two linear time union-find stra-tegies for image processing [J].Theoretical Computer Science,1996,154(2):165- 181.

[7] WU K S，OTOO E，SUZUKI K.Optimizing two-pass connected component labeling algorithms [J].Pattern Analysis and Applications，2009，12(2): 117- 135.

[8] SOH Y，ASHRAF H，HAE Y，et al.A hybrid approach to parallel connected component labeling using cuda [J].International Journal of Signal Processing Systems，2013,1(2):130- 135.

[9] GUPTA S，PALSETIA D，PATWARY MMA，et al.A new parallel algorithm for two-pass connected component labeling [J].Parallel & Distributed Processing Symposium Wokshops,2014,778(1):1355- 1362.

[10] GHARASUIE MM，GAFFARI A.An efficient run-based method for connected component labeling [C]∥9th Iranian Conference on Machine Vision and Image Processing(ICMVIP 2015).Tehran:Shahid Beheshti University，2015:100- 104.

[11] CHANG W Y，CHIU C C，Yang J H. Block-based connected-component labeling algorithm using binary decision trees [J].Sensors，2015，15(9):23763- 23787.

[12] 牛连强，彭敏，孙忠礼，等.利用游程集合的标号传播实现快速连通域标记 [J].计算机辅助设计与图形学学报，2015 (1) :128- 135.

NIU Lian-qiang，PENG Min，SUN Zhong-li,et al.Fast connected components labeling by propagating labels of run sets [J].Journal of Computer-Aided Design & Computer Graphic，2015 (1) :128- 135.

[13] CHANG F，CHEN C.A linear-time component-labeling algorithm using contour tracing technique [J].Computer Vision and Image Understanding，2004,93(2):206- 220.

[14] JEONG J W ，LEE G B ，LEE M J，et al.A single-pass connected component labeler without label merging period [J].Journal of Signal Processing Systems,2016,84(2):211- 223.

[15] 冯海文，牛连强，刘晓明.高效的一遍扫描式连通区域标记算法 [J].计算机工程与应用，2014，50(23)：31- 35.

FENG Hai-wen，NIU Lian-qiang，LIU Xiao-ming.Efficient one-scan algorithm for labeling connected component [J].Computer Engineering and Applications，2014，50(23)：31- 35.

[15] CABARET L，LACASSAGNE L.What Is the world’s fastest connected component labeling [C]∥IEEE Workshop on Signal Processing Systems(SiPS 2014).Belfast:IEEE，2014:1- 6.

[16] PATWARY M M A，BLAIR J，MANNE F.Experiments on union-find algorithms for the disjoint-set data structure [C]∥International Conference on Experimental Algorithms.Naples:Springer,2010:411- 423.

[17] Signal and Image Processing Institute，USC Viterbi.USI-SIPI image database [EB/OL].(2010- 12- 22)[2016- 06- 25].http:∥sipi.usc.edu/services/database/index.html.

AFastRun-BasedTwo-PassAlgorithmforConnectedComponentsLabeling

LYUChang-kuiXUYanLUOBing-xin

(College of Mechanical and Electrical Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, Jiangsu, China)

In order to improve the calculation efficiency of connected component labeling (CCL) algorithms of binary images, firstly, an algorithm named FRL, which optimizes the conventional overlapping runs detection algorithm for run-based two-pass labeling algorithms, is proposed. Secondly, a general algorithm on the basis of FRL and union find is introduced. Then, some experiments are carried out to verify the computational efficiency of FRL. Finally, a comparative analysis is made between the general algorithm and other two typical two-pass CCL algorithms (namely RTS and SAUF). The results demonstrate that, as FRL saves unnecessary subsequent connectivity checks on runs between adjacent rows, the connectivity detection process is optimized into a chain-like mode, the calculation efficiency of run length labeling process improves greatly, the time complexity reduces from conventionalO(mn) toO(m+n-1), and the execution time decreases to the same level as the union find algorithm module. Moreover, it is found that the proposed general algorithm greatly outperforms RTS but is slightly better than SAUF in general.

connected component labeling; two-pass algorithm; connectivity detection algorithm; run length labeling; union find

2016- 11- 10

国家自然科学基金资助项目(51375238)

*Foundationitem： Supported by the National Natural Science Foundation of China(51375238)

吕常魁(1971-)，男，博士，副教授，主要从事机器视觉及其工业检测研究.E-mail:maillck@nuaa.edu.cn

1000- 565X(2017)07- 0084- 06

TP 391

10.3969/j.issn.1000-565X.2017.07.012