Browse Prior Art Database

Single Pass Method for Labeling Black/White Image Objects

IP.com Disclosure Number: IPCOM000042021D
Original Publication Date: 1984-Mar-01
Included in the Prior Art Database: 2005-Feb-03
Document File: 3 page(s) / 41K

Publishing Venue

IBM

Related People

Ni, LM: AUTHOR [+3]

Abstract

This invention is related to a single pass method for assigning a unique label to each maximally connected group of same color valued (black) pels (picture elements) in a black/white pel image array. The method steps include (a) scanning the array in row major order with a local window; (b) assigning a new label to a center pel within the window if the pel is not connected or a label previously assigned if the pel is connected; (c) stack recording as equivalent, pairs of labels provisionally assigned to disparate elements of a subsequently identified unitary object; and (d) stack recording labels for nested objects.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Single Pass Method for Labeling Black/White Image Objects

This invention is related to a single pass method for assigning a unique label to each maximally connected group of same color valued (black) pels (picture elements) in a black/white pel image array. The method steps include (a) scanning the array in row major order with a local window; (b) assigning a new label to a center pel within the window if the pel is not connected or a label previously assigned if the pel is connected; (c) stack recording as equivalent, pairs of labels provisionally assigned to disparate elements of a subsequently identified unitary object; and (d) stack recording labels for nested objects. The method preferably is executed on a pipeline processor having provision for stack recording of anomalies such as nested objects which are amenable to subsequent processing and thus avoiding perturbing the pipeline. One of the major tasks in automatic image inspection is to identify the number of isolated objects as well as holes within each object from an inspected binary image. The goal of component labeling is to assign a unique label to each maximally connected group of 1's (object) in a binary image. Component labeling can be done by scanning each line of the image from left to right and from top to bottom on a pixel basis. One pixel is examined at a time. Either a new label is generated or an old label is used depending on its neighboring pixels. The conventional approach of component labeling either requires more than one pass to scan the image or is not suitable for real-time hardware implementation. The proposed new component labeling architecture shown in the figure can label the pixel in the input rate and provide many other unique features: 1. Label selection follows a fixed sequence. The figure shows a 3x3 window for a target pixel P. Assuming 8-adjacency, i.e., all 8 neighboring pixels around P are adjacent to P. When P is to be labeled, pixels A, B, C, and D have been labeled and stored in the label buffer. The label buffer will hold one line of labels. In the conventional approach, the smallest label is selected among those different neighboring labels, if they exist. In our design, a fixed selection sequence, A>B>C>D, is used. That is, label A has the highest priority to be selected if A=1. A simp...