Labeling And Simultaneous Feature Extraction In One Pass

P. Vuylsteke; A. Oosterlinck; H. Van den Berghe

doi:10.1117/12.932626

23 July 1982 Labeling And Simultaneous Feature Extraction In One Pass

P. Vuylsteke, A. Oosterlinck, H. Van den Berghe

Proceedings Volume 0301, Design of Digital Image Processing Systems; (1982) https://doi.org/10.1117/12.932626
Event: 25th Annual Technical Symposium, 1981, San Diego, United States

Abstract

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.

Citation Download Citation

P. Vuylsteke, A. Oosterlinck, and H. Van den Berghe "Labeling And Simultaneous Feature Extraction In One Pass", Proc. SPIE 0301, Design of Digital Image Processing Systems, (23 July 1982); https://doi.org/10.1117/12.932626

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available