Method and means for efficiently handling boundary conditions in connected component labeling

• US 4,791,676 A
• Filed: 01/22/1988
• Issued: 12/13/1988
• Est. Priority Date: 09/12/1985
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ali Mohiuddin, Kottappuram M., Flickner, Myron D.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US07/148,169
• Time in Patent Office: 326 Days
• Field of Search: 382/26, 382/41, 382/48, 382/19, 382/22, 382/25, 382/9, 382/27, 358/107
• US Class Current: 382/204
• CPC Class Codes: G06T 7/00 Image analysis
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

A method and means for analyzing and labeling picture elements ( pixels) in a raster-scanned image includes utilizing a fixed pixel labeling priority rule that takes into account near-neighbor frame border pixels that are not included in the currently-viewed portion of the image by substituting the inverse of the value of the current image pixel being labeled in place of undefined border pixels outside the viewed image portion.

Claims

1. In a method of labeling the components of a black/white raster-scanned image frame in which the color of a component to be labeled is analyzed with respect to the colors of its causal neighbors contained in a fixed-sized window and components are labeled sequentially in response to a color valve match analysis of a sequence of windows, the improvement comprising:

identifying a frame boundary in a fixed-sized window, said frame boundary including undefined neighbor components of the component being analyzed for labeling; and

in response to said identification and to the color value of the component being analyzed, substituting the inverse of the color value of the component being analyzed in the places of said undefined neighbor components.

2. The method of claim 1 wherein said step of identifying includes identifying a first boundary, said first boundary including a sequence of undefined components outside of said image frame and adjacent an edge of said image frame.

3. The method of claim 2 wherein said step of identifying further includes identifying an extreme boundary, said extreme boundary including a second sequence of undefined components outside of said image from and separated by said first boundary from said edge.

4. The method of claim 1 wherein said step of identifying includes identifying respective intersecting boundaries in said window.

5. In a system for sequentially labeling the pixels of a black/white raster-scanned frame image in response to the color values of pixels contained in a sequence of fixed-sized windows defined in said image, the improvement comprising:

a boundary detection circuit which responds to said raster-scanned image frame by providing a signal identifying a frame boundary contained in one of said sequence of fixed-sized windows, said frame boundary including undefined boundary pixels contained in said window; and

a pixel value selection circuit which responds to said signal and to said color values of said pixels by assigning to said undefined pixels the inverse color value of a pixel contained in said fixed-sized window and which is next to be labeled.

6. The improvement of claim 5 wherein said frame boundary includes a sequence of undefined pixels outside of and adjacent to an edge of said raster-scanned image.

7. The improvement of claim 5 wherein said frame boundary is an extreme frame boundary, said extreme frame boundary including a first column of undefined pixels outside of said raster-scanned image and separated from an edge of said raster-scanned image by a near frame boundary, said near frame boundary including a second column of undefined pixels outside of and abutting an edge of said raster-scanned image.

8. In the analysis of a fixed-sized frame of black/white raster-scanned images, a method for connected component labeling of said frame in a sequential manner utilizing a predetermined fixed priority rule, comprising the steps:

analyzing the connectivity of each component in each of the black/white images by assessing a color value match of each component with respect to its causal neighbors within a fixed-sized window;

labeling each analyzed component based upon its connectivity with a connected group of components within the frame, any given component being labeled according to the fixed priority rule in the event that at least two of its causal neighbors have the same color value.

identifying a frame boundary in a fixed-size frame, said frame boundary including undefined neighbor components of a component being labeled; and

in response to said identification and to the color value of the component being labeled, substituting the inverse of the color value of said component being labeled in the places of said undefined neighbor components.

9. The method of claim 8 wherein said components are pixels occurring in a raster-scanned sequence synchronized by a pixel clock signal having a predetermined pixel frequency and said steps are performed for each of said pixels within the cycle of said pixel clock signal during which the pixel occurs.

10. An apparatus for sequentially analyzing the connectivity of pixels in a raster-scanned image frame according to a predetermined labeling priority rule, comprising:

window register means responsive to a sequence of color-valued pixels that form a raster-scanned image frame for associating each pixel in said sequence to causal pixel neighbors by a fixed-sized window containing the pixel and its causal neighbors;

labeling means responsive to each fixed-sized window for analyzing the connectivity of each pixel to other pixels in the sequence based upon a color value match of the pixel with respect to its causal neighbors and for labeling each pixel based upon its connectivity with a connected group of components within the frame;

a frame boundary means responsive to said image frame for recognizing a frame boundary contained in a fixed-sized window, said frame boundary including undefined neighbor pixels of a pixel being labeled; and

value substitution means connected to said window means, said frame boundary means, and said labeling means and responsive to said frame boundary recognition and to the color value of the pixel labeled for substituting the inverse of the color value of said pixel being labeled in the places of its undefined pixel neighbors.

11. The apparatus of claim 10 wherein said labeling means includes an addressable storage device having pixel label selection signals stored at locations addressed by color values of pixels in said fixed-size windows.

12. The apparatus of claim 11 wherein said fixed-size window pixel color values include said inverted values substituted in the places of undefined pixels contained in said fixed-size windows adjacent the boundaries of said image frame.

13. The apparatus of claim 10 wherein said value substitution means includes programmable logic circuitry.