Abstract | ||
---|---|---|
This paper presents a run-based one-scan algorithm for labeling connected components in a binary image. Our algorithm is different with conventional raster-scan label-equivalence-based algorithms in two ways: (1) to complete connected component labeling, all conventional label-equivalence-based algorithms scan a whole image two or more times, our algorithm scans a whole image only once; (2) all conventional label-equivalence-based algorithms assign each object pixel a provisional label in the first scan and rewrite it in later scans, our algorithm does not assign object pixels but runs provisional labels. In the scan, our algorithm records all run data in an image in a one-dimensional array and assigns a provisional label to each run. Any label equivalence between runs is resolved whenever it is found in the scan, where the smallest label is used as their representative label. After the scan finished, all runs that belong to a connected component will hold the same representative label. Then, using the recorded run data, each object pixel of a run is assigned the representative label corresponding to the run without rewriting the values (i.e., provisional labels) of object pixels and scanning any background pixel again. Experimental results demonstrate that our algorithm is extremely efficient on images with long runs or small number of object pixels. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-02611-9_10 | ICIAR |
Keywords | Field | DocType |
smallest label,conventional raster-scan label-equivalence-based algorithm,algorithm record,object pixel,label equivalence,conventional label-equivalence-based algorithm,connected component,provisional label,representative label,run-based one-scan,whole image,raster scan,connected components,pattern recognition,run length encoding,binary image | Computer vision,Pattern recognition,Computer science,Queue,Algorithm,Run-length encoding,Raster scan,Artificial intelligence,Connected component,Pixel | Conference |
Volume | ISSN | Citations |
5627 | 0302-9743 | 9 |
PageRank | References | Authors |
0.70 | 21 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lifeng He | 1 | 441 | 40.97 |
Yuyan Chao | 2 | 315 | 24.07 |
Kenji Suzuki | 3 | 505 | 38.99 |
Hidenori Itoh | 4 | 368 | 252.31 |