Translator Disclaimer
14 October 1987 A New Component Labelling And Merging Algorithm
Author Affiliations +
Proceedings Volume 0804, Advances in Image Processing; (1987)
Event: Fourth International Symposium on Optical and Optoelectronic Applied Sciences and Engineering, 1987, The Hague, Netherlands
Component labelling is an important part of region analysis in image processing. Component labelling consists of assigning labels to pixels in the image such that adjacent pixels are given the same labels. There are various approaches to component labelling. Some require random access to the processed image; some assume special structure of the image such as a quad tree. Algorithms based on sequential scan of the image are attractive to hardware implementation. One method of labelling is based on a fixed size local window which includes the previous line. Due to the fixed size window and the sequential fashion of the labelling process, different branches of the same object may be given different labels and later found to be connected to each other. These labels are con-sidered to be equivalent and must later be collected to correctly represent one single object. This approach can be found in [F,FE,R]. Assume an input binary image of size NxM. Using these labelling algorithms, the number of equivalent pair generated is bounded by O(N*M). The number of distinct labels is also bounded by O(N*M). There is no known algorithm that merge the equivalent label pairs in time linear to the number of pairs, that is in time bounded by O(N*M). We propose a new labelling algorithm which interleaves the labelling with the merging process. The labelling and the merging are combined in one algorithm. Merged label information is kept in an equivalent table which is used to guide the labelling. In general , the algorithm produces fewer equivalent label pairs. The combined labelling and merging algorithm is O(N*M), where NxM is the size of the image. Section II describes the algorithm. Section III gives some examples We discuss implementation issues in section IV and further discussion and conclusion are given in Section V.
© (1987) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Amelia Fong Lochovsky "A New Component Labelling And Merging Algorithm", Proc. SPIE 0804, Advances in Image Processing, (14 October 1987);


Fast algorithm for calculation of linear variations
Proceedings of SPIE (September 28 2016)
Image Processing System Interfaces
Proceedings of SPIE (July 22 1985)
Image vectorization in digital image watermarking
Proceedings of SPIE (June 23 2003)
Strokes-matting method based on sample search
Proceedings of SPIE (June 08 2012)

Back to Top