This paper presents an efficient run-based algorithm for labeling connected components in a binary image. By means of two tables called index table and equivalent information table respectively, the algorithm assign labels only to run sets which are composed of a series of runs connected to each other in adjacent scan rows, then the same index in equivalent information table can be assigned to all runs of a set in index table at one time. Further, the algorithm organizes all equivalence information in equivalent information table in a tree structure, and employee the union-find technique to merge connected components rapidly. The algorithm is very simple, and fewer operations are needed to check and to label runs of a connected branch. Furthermore, it is not necessary to calculate the minimum label while combining two runs, and is able to construct a union-find tree with smaller height. Thus the algorithm is able to provide a high speed to label connected components for general images.
RosenfeldA., Connectivity in digital pictures, Journal of the ACM17(1) (1970), 146–160.
2.
HecquardJ. and AcharyaR., Connected component labeling with linear octree, Pattern Recognition24(6) (1991), 515–531.
3.
DillencourtM., SametH. and TamminenM., General approach to connected-component labeling for arbitrary image representations, Journal of the ACM39(2) (1992), 253–280.
4.
FiorioC. and GustedtJ., Two linear time union-find strategies for image processing, Theoretical Computer Science154(2) (1996), 165–181.
5.
FlattH., BlumeS., HesselbarthS., et al., A parallel hardware architecture for connected component labeling based on fast label merging, Proceeding of Application-Specific Systems, Architectures and Processors (2008), 144–149.
6.
ChenP., ZhaoH.L., TaoC., et al., Block-run-based connected component labelling algorithm for GPGPU using shared memory, Electronics Letters47(24) (2011), 1309–1311.
7.
JungI. and JeongC., Parallel connected-component labeling algorithm for GPGPU applications, Communications and Information Technologies (ISCIT) (2010), 1149–1153.
8.
ZhaoF.,
ZhangL.,
ZhangZ., et al., A hardware acceleration based algorithm for real-time binary image connected-component labelling, J Electronics & Information Technology33(5) (2011), 1069–1075.
9.
ItoY. and NakanoK., Low-latency connected component labeling using an FPGA, International Journal of Foundations of Computer Science21(3) (2010), 405–425.
10.
ItoY., NakanoK., andK. and PanY., Optimized component labeling algorithm for using in medium sized FPGAs, Proceedings of Ninth International Conference on Parallel and Distributed Computing, Applications and Technologies (2008), 171–176.
11.
GranaC., BorghesaniD. and CucchiaraR., Connected component labeling techniques on modern architectures, Lecture Notes in Computer Science5716 (2009), 816–824.
12.
LeeD., JinS., ThienP., et al., FPGA based connected component labeling, Proceedings of International Conference on Control, Automation and Systems (2007), 2313–2317.
13.
Calvo-GallegoE., CabreraA.A., BroxP., et al., Real-time FPGA connected component labeling system, Proceedings of 19th IEEE International Conference on Electronics, Circuits and Systems (2012), 593–596.
14.
SuzukiK., HoribaI. and SugieN., Linear-time connected-component labeling based on sequential local operations, Computer Vision and Image Understanding89(1) (2003), 1–23.
15.
WangH., LuoC., WangY., et al., New algorithm for binary connected-component labeling based on run-length encoding and union-find sets, Journal of Beijing Institute of Technology19(1) (2010), 71–75.
16.
LacassagneL. and ZavidoviqueB., Light speed labeling: Efficient connected component labeling on RISC architectures, J Real-Time Image Processing6(2) (2011), 117–135.
17.
De BockJ. and
PhilipsW., Fast and memory efficient 2-D connected components using linked lists of line Segments, IEEE Transactions on Image Processing19(12) (2010), 3222–3231.
18.
SutheebanjardP. and PremchaiswadiW., Efficient scan mask techniques for connected components labeling algorithm, Proceedings of EURASIP J on Image and Video Processing (2011), 14–20.
19.
YeongL., AngL. and SengK., Efficient connected component labeling using multiple-bank memory storage, Proceedings of 3rd IEEE International Conference on Computer Science and Information Technology (2010), 75–79.
20.
HeL., ChaoY. and
SuzukiK., A run-based two-scan labeling algorithm, IEEE Transactions on Image Processing17(5) (2008), 749–756.
21.
HeL.,
ChaoY. and SuzukiK., A new first-scan method for two-scan labeling algorithms, IEICE Transactions on Information and SystemsE95D(8) (2012), 2142–2145.
22.
HeL., ChaoY., SuzukiK., et al., A high-speed run-based two-scan labeling algorithm, J the Institute of Image Information and Television Engineers62(9) (2008), 1461–1465.
23.
HeL., ChaoY. and Ieee, A linear-time two-scan labeling algorithm, IEEE International Conference on Image Processing5(5) (2007), 241–244.
24.
WuK., OtooE. and SuzukiK., Optimizing two-pass connected-component labeling algorithms, Pattern Analysis and Applications12(2) (2009), 117–135.
25.
GranaC., BorghesaniD. and CucchiaraR., Optimized block-based connected components labeling with decision trees, IEEE Transactions on Image Processing19(6) (2010), 1596–1609.
26.
HeL., ChaoY. and SuzukiK., Two efficient label-equivalence-based connected-component labeling algorithms for 3-D binary images, IEEE Transactions on Image Processing20(8) (2011), 2122–2134.
27.
HeL., ChaoY., SuzukiK., et al., Fast connected-component labeling [J], Pattern Recognition42(9) (2009), 1977–1987.
28.
ParalicM., Fast connected component labeling in binary images, Proceedings of the 35th International Conference on Telecommunications and Signal Processing131(5) (2012), 706–709.
29.
HuQ., QianG. and NowinskiW., Fast connected-component labelling in three-dimensional binary images based on iterative recursion, Computer Vision and Image Understanding99(3) (2005), 414–434.
30.
ChangF., SinicaA. and ChenC., A component-labeling algorithm using contour tracing technique, Computer Vision & Image Understanding93(2) (2003), 206–220.
31.
YapaR. and KoichiH., A connected component labeling algorithm for grayscale images and application of the algorithm on mammograms, Proceedings of the ACM Symposium on Applied Computing (2007), 146–152.
32.
GuQ., TakakiT. and IshiiI., A fast multi-object extraction algorithm based on cell-based connected components labelling, IEICE Transactions on Information and SystemsE95D(2) (2012), 636–645.
33.
ChangF., ChenC. and LuC., A linear-time component-labeling algorithm using contour tracing technique, Computer Vision and Image Understanding93(2) (2004), 206–220.
34.
BaiL., ZhangY., HaiZ., et al., A new linear-time component-labeling algorithm, Proceedings of the 2nd International Conference on Software Technology and Engineering (2010), 1150–1153.
35.
AbubakerA., QahwajiR., IpsonS., et al., One scan connected component labeling technique, Proceedings of IEEE International Conference on Signal Processing and Communications (2007), 1283–1286.
36.
HeL., ChaoY. and ItohH., A run-based one-scan labeling algorithm, Lecture Notes in Computer Science5627 (2009), 93–102.
37.
HeL., ChaoY. and SuzukiK., A run-based one-and-a-half-scan connected-component labeling algorithm, International Journal of Pattern Recognition and artificial Intelligence24(4) (2010), 557–579.
38.
AlstrupS., Ben-AmramA. and RauheT., Worst-case and amortised optimality in Union-Find, Proceedings of the thirty-first annual ACM Symposium on Theory of Computing (1999), 499–506.
39.
ZhaoX., HeL., YaoB., et al., A new connected-component labeling algorithm, IEICE Transactions on Information & SystemsE98.D(11) (2015), 2013–2016.
