Computer Science & Technology

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

Expand
  • College of Mechanical and Electrical Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,Jiangsu,China
吕常魁( 1971-) ,男,博士,副教授,主要从事机器视觉及其工业检测研究.

Received date: 2016-10-09

  Revised date: 2017-03-26

  Online published: 2017-06-01

Supported by

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

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.

Cite this article

LYU Chang-kui XU Yan LUO Bing-xin . A Fast Run-Based Two-Pass Algorithm for Connected Components Labeling[J]. Journal of South China University of Technology(Natural Science), 2017 , 45(7) : 84 -89 . DOI: 10.3969/j.issn.1000-565X.2017.07.012

Outlines

/