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

A Fast Run-Based Two-Pass Algorithm for Connected Components Labeling

作　　者：吕常魁[1] 徐岩[1] 罗冰心 LYU Chang-kui XU Yan LUO Bing-xin(College of Mechanical and Electrical Engineering, Nanjing University of Aeronautics and Astronautics,Nanjing 210016, Jiangsu, China)

机构地区：[1]南京航空航天大学机电学院,江苏南京210016

出　　处：《华南理工大学学报（自然科学版）》2017年第7期84-89,共6页Journal of South China University of Technology(Natural Science Edition)

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

摘　　要：为提高二值图像连通区域标记(CCL)的计算效率,提出快速游程标记(FRL)算法,对基于游程的两次扫描算法中的传统游程连通检测算法进行了优化;然后介绍了基于FRL与并查集的整体算法;最后对FRL的计算效率进行了实验验证,并将整体算法与RTS与SAUF两种典型的两次扫描CCL算法进行了比对分析.结果表明:FRL算法省去了行间游程不必要的后续比对,使得比对形式接近于链式,大幅度提高了游程标记的计算效率,时间复杂度由传统RL算法的O(mn)降为O(m+n-1),执行时间降为与并查集运算环节同一量级;整体算法的性能明显优于RTS算法,总体上略优于SAUF算法.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 algo-rithm 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 algo-rithms （namely RTS and SAUF） . The results demonstrate th a t , 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 conventional O（mn） to O（m＋n-1）, and the execution time decreases to the same level as the union find algorithm mod-ule. Moreover, it is found that the proposed general algorithm greatly outperforms RTS but is slightly better than SAUF in general.

关 键 词：连通区域标记 两次扫描算法 连通检测算法 游程标记 并查集 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]