Abstract | ||
---|---|---|
Unlike conventional raster-scan based connected-component labeling algorithms which detect the connectivity of object pixels
by processing pixels in an image one by one, this paper presents an efficient run-based two-scan labeling algorithm: the run
data obtained during the scan are recorded in a queue, and are used for detecting the connectivity later. Moreover, unlike
conventional label-equivalence-based algorithms which resolve label equivalences between provisional labels that are assigned
during the first scan, our algorithm resolve label equivalences between the representative labels of equivalent provisional
label sets. In our algorithm, at any time, all provisional labels that are assigned to a connected component are combined
in a set, and the smallest label is used as the representative label. The corresponding relation of a provisional label to
its representative label is recorded in a table. Whenever different connected components are found to be connected, all provisional
label sets concerned with these connected components are merged together, and the smallest provisional label is taken as the
representative label. When the first scan is finished, all provisional labels that were assigned to each connected component
in the given image will have a unique representative label. During the second scan, we need only to replace each provisional
label with its representative label. Experimental results on various types of images demonstrate that our algorithm is the
fastest of all conventional labeling algorithms.
|
Year | DOI | Venue |
---|---|---|
2008 | 10.1109/TIP.2008.919369 | IEEE transactions on image processing : a publication of the IEEE Signal Processing Society |
Keywords | Field | DocType |
smallest provisional label,label equivalence,smallest label,unique representative label,run-based two-scan,connected component,different connected component,representative label,provisional label,resolve label equivalence,provisional label set,encoding,image processing,documentation,artificial intelligence,connected component labeling,helium,pattern analysis,labeling,algorithm,pattern recognition,computer vision,pixel,algorithms,connected components,image recognition,run length encoding,binary image | Computer science,Binary image,Image processing,Run-length encoding,Artificial intelligence,Computer vision,Pattern recognition,Algorithm,Raster scan,Pixel,Connected component,Connected-component labeling,Encoding (memory) | Journal |
Volume | Issue | ISSN |
17 | 5 | 1057-7149 |
ISBN | Citations | PageRank |
3-540-74258-1 | 93 | 3.36 |
References | Authors | |
33 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lifeng He | 1 | 441 | 40.97 |
Yuyan Chao | 2 | 315 | 24.07 |
Kenji Suzuki | 3 | 505 | 38.99 |