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

Abstract: In order to improve the calculation efficiency of connected component labeling ( CCL) algorithms of bi- nary 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 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 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.

Key words: connected component labeling, two-pass algorithm, connectivity detection algorithm, run length labe- ling, union find