Translator Disclaimer
14 October 1987 A New Component Labelling And Merging Algorithm
Author Affiliations +
Proceedings Volume 0804, Advances in Image Processing; (1987) https://doi.org/10.1117/12.941296
Event: Fourth International Symposium on Optical and Optoelectronic Applied Sciences and Engineering, 1987, The Hague, Netherlands
Abstract
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); https://doi.org/10.1117/12.941296
PROCEEDINGS
5 PAGES


SHARE
Advertisement
Advertisement
RELATED CONTENT

Fast algorithm for calculation of linear variations
Proceedings of SPIE (September 27 2016)
Image Processing System Interfaces
Proceedings of SPIE (July 21 1985)
The Use Of Digital Processors In Image Analysis Systems
Proceedings of SPIE (December 28 1978)

Back to Top