Browse Prior Art Database

Method for Reusing Nonactive Labels in Object Labeling in a Black/White Pel Array

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

Publishing Venue

IBM

Related People

Dinstein, I: AUTHOR [+2]

Abstract

This invention relates to a method for reusing nonactive labels in the component labeling of objects in a black/white pel (picture element) array. New labels are assigned to nonconnected pels as a window scans the array in row major order. The method steps include classifying a label as nonactive if it was assigned to some pels in a previous scan line but is not assigned to any pel in a current line. The label will not be assigned if none of the pels having this label can be adjacent to any pel in the next line. The nonlabels are in effect stored and releasable for reuse while the labeling operation continues in one mode. The concept of active and nonactive labels is now defined. Suppose a certain label was assigned to some pixels in previous lines, but it is not assigned to any pixel in the current line.

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

Method for Reusing Nonactive Labels in Object Labeling in a Black/White Pel Array

This invention relates to a method for reusing nonactive labels in the component labeling of objects in a black/white pel (picture element) array. New labels are assigned to nonconnected pels as a window scans the array in row major order. The method steps include classifying a label as nonactive if it was assigned to some pels in a previous scan line but is not assigned to any pel in a current line. The label will not be assigned if none of the pels having this label can be adjacent to any pel in the next line. The nonlabels are in effect stored and releasable for reuse while the labeling operation continues in one mode. The concept of active and nonactive labels is now defined. Suppose a certain label was assigned to some pixels in previous lines, but it is not assigned to any pixel in the current line. This label will not be assigned any more since none of the pixels having this label can be adjacent to any pixel in the next line. Such labels are referred to as nonactive labels. Labels that are assigned to pixels of the current line are said to be active labels since they may still be used in the following lines. Based on the above discussion, the sum of active and nonactive labels within any pair of consecutive lines is at most N/2 . There are two modes in which this reuse of storage can be implemented, an interrupted and a noninterrupted mode. When the interrupted mode is used, the number of nonactive labels is checked at the end of each line. If this number exceeds a prespecified parameter M, the labeling is interrupted and the storage of nonactive labels is released for reuse. When the noninterrupted mode is implemented, the storage of nonactive labels is released while the labeling operation continues. A block diagram for the procedure is shown in the figure. The Label Address FIFO, the Flag Buffer, and the Label and Feature Memory are [N/2] + M locations deep. The FIFO is initialized to contain the value i in its ith location, for 0 < i < [N/2] + M - 1. The FIFO (first-in, first-out) is used as a reservoir of addresses for the Label and Feature Memory (LFM). The Flag Buffer is initialized to zero. Whenever a new label is required by the Labeling Logic, a new label is generated by the Label Generator, and stored in the Label and Feature Memory at the next available address, which is provided by the Label Address FIFO. At the same time, flag F1 at the corresponding address of the Flag Buffer is set to 1. The ...