Labeling And Simultaneous Feature Extraction In One Pass
Pieter Vuylsteke, A. Oosterlinck, Herman VAN DEN BERGHE · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1982
The labeling process of connected regions is a typical recursive procedure, requiring backtracks at each point where regions are found to recombine. Backtracks can be carried out by using a second pass through the complete image. The algorithm discussed in this paper combines in a single pass the labeling of connected regions with the generation of a data structure containing global features like area, first order moments, perimeter, circumscribed rectangle, of all labeled regions. Backtracks take advantage of indirect adressing in order to restrict each region merging to just a few memory transfers. The problem of chaining encountered in more complex image configurations requires backtrack from the merging point to more than one previously labeled domain. As the use of associative memories to deal with this problem is still of theoretical interest, a completely different approach using only random accessible memories is described in this paper. The information concerning either multiple or single backtracks is build up in a compact data structure consisting of two linked lists, set up interactively, the first pointing forwards, the other backwards. Moreover, a separate data structure, lists for each coherent region the labels of its inclusions. Two connected linked lists are sufficient to represent these hierarchical-tree-like relations within the complete image. The algorithm is inten-ded to be implemented in hardware, operating at realtime TV scan speed. This requirement can be met using a buffer FIFO memory, because the algorithm is active only at critical points. In this way the resulting global cycle time is expected to slightly exceed one image frame time. Memory requirements are rather small as runs are the smallest elements instead of pixels, and as the number of list entries to labels, inclusions and features are limited to the maximal expected number of (a priori) connected regions.