High speed algorithm for component labeling

The authors have developed an algorithm for component labeling amenable to pipelining and video-rate processing. This operation, which classifies the connected components of images, is widely used in various fields: medical image processing, visual inspection and other computer visions. However, the conventional algorithms have a serious problem that the amount of operations rapidly increases as the shapes of components become more complex. In this paper, the authors propose a method of reducing the number of provisional labels by expanding the components of images to simplify their shapes. They also propose a classification method for provisional labels which enables processing in time proportional to only the first power of the labels. These methods can reduce the amount of the operations and enable realizing high speed processing. Experiments using computer simulation, verify that by the proposed algorithm 512×512×8 bit images can be processed in pipeline at video-rate with dedicated hardware. [In Japanese.]