Labeling pixels of an image based on near neighbor attributes

• US 5,239,596 A
• Filed: 06/08/1990
• Issued: 08/24/1993
• Est. Priority Date: 06/08/1990
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Mahoney, James V.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/535,089
• Time in Patent Office: 1,173 Days
• Field of Search: 382/16, 382/30, 382/34, 382/40, 382/27
• US Class Current: 382/180
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

Pixels within an image are labeled based on near neighbor attributes. The attributes may be attributes for a near neighbor link or for a near neighbor pixel to which the link leads. The near neighbor attribute data for a pixel may indicate attributes for plural near neighbor links, and a link relationship criterion may be applied to determine whether the links are related in a manner that meets the criterion. For example, a pixel may be labeled only if its near neighbor links include a pair with relative orientation difference of approximately 180°, both of which have been previously labeled or are links to a boundary; this criterion is useful in labeling a partially bounded region. A distance independent connected component labeling criterion may be applied during parallel labeling of pixels for rapid connected component labeling. Labeling based on a near neighbor labeling criterion may be iterated until a component or region is completely labeled.

Claims

1. A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of:

for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels;

operating the processor to produce, for a first one of the pixels, near neighbor attribute data;

the near neighbor attribute data indicating a first attribute for a first near neighbor link of the first pixel and indicating a second attribute for a second near neighbor link of a second one of the pixels; and

operating the processor to use the near neighbor attribute data of the first pixel to determine whether the first near neighbor link of the first pixel is a link to the second pixel and the second near neighbor link of the second pixel is a link to the first pixel and, if so, setting the first pixel'"'"'s pixel set data to indicate that the first pixel is in the indicated set of pixels.

2. The method of claim 1 in which the near neighbor attribute data indicate a first quadrant and a first offset for the first near neighbor link and a second quadrant and a second offset for the second near neighbor link;

the step of operating the processor to use the near neighbor attribute data comprising substeps of;

determining whether the first and second quadrants are opposite; and

if the first and second quadrants are opposite, determining whether the first and second offsets are equal in magnitude.

3. The method of claim 1 in which the near neighbor attribute data indicate a link orientation and a distance for the first near neighbor link, the method further comprising a step of operating the processor to use the near neighbor attribute data of the first pixel to determine whether the first pixel and the second pixel are in a group, comprising substeps of:

obtaining a minimum of a maximum distance and the distance for the first near neighbor link;

using the minimum to obtain a proportion of a maximum orientation difference;

obtaining a difference between the link orientation for the first near neighbor link and an independent orientation for the first pixel; and

comparing the proportion of the maximum orientation difference with the difference between the link orientation for the first near neighbor link and the independent orientation for the first pixel.

4. The method of claim 1 in which the first attribute is a first length and the second attribute is a second length;

the step of operating the processor to use the near neighbor attribute data including a substep of comparing the first and second lengths.

5. The method of claim 1 in which the first attribute is a first link orientation and the second attribute is a second link orientation;

the step of operating the processor to use the near neighbor attribute data including a substep of comparing the first and second link orientations.

6. The method of claim 1 in which the near neighbor attribute data further indicate a third attribute for the first near neighbor link and indicate a fourth attribute for the second near neighbor link;

the first attribute being a first length;

the second attribute being a second length;

the third attribute being a first link orientation;

the fourth attribute being a second link orientation;

the step of operating the processor to use the near neighbor attribute data including substeps of;

comparing the first and second link orientations; and

comparing the first and second lengths.

7. A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of:

for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels;

operating the processor to produce, for a first one of the pixels, near neighbor attribute data;

the near neighbor attribute data indicating a first relative orientation from the first pixel to a first near neighbor pixel and indicating a second relative orientation from the first pixel to a second near neighbor pixel; and

operating the processor to use the near neighbor attribute data of the first pixel to determine whether the difference between the first and second relative orientations is approximately 180° and

, if so, setting the first pixel'"'"'s pixel set data to indicate that the first pixel is in the indicated set of pixels.

8. The method of claim 7 in which, if the difference between the first and second relative orientations is approximately 180°

, the step of operating the processor to use the near neighbor attribute data further includes a substep of determining whether the respective pixel set data of each of the first and second near neighbor pixels indicate that the first and second near neighbor pixels are in the indicated set.

9. The method of claim 7 in which the near neighbor attribute data indicate whether the first near neighbor pixel is a boundary pixel;

the step of operating the processor to use the near neighbor attribute data including, if the difference between the first and second relative orientations is approximately 180°

, a substep of determining whether the near neighbor attribute data indicate that the first near neighbor pixel is a boundary pixel and, if so, determining whether the pixel set data of the second near neighbor pixel indicate that the second near neighbor pixel is in the indicated set.

10. A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of:

for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including pixel set data indicating whether the pixel is in an indicated set of pixels;

a first one of the pixel'"'"'s pixel set data indicating that the pixel is in the indicated set of pixels; and

for each of a series of steps, operating the processor to set the pixel set data of a number of additional ones of the pixels until a final step in which the number of additional pixels is not sufficient to justify another step;

each of the steps of operating the processor to set the pixel set data of additional pixels comprising substeps of;

producing, for each pixel, near neighbor attribute data indicating an attribute of a near neighbor pixel of the pixel, the attribute being whether the near neighbor pixel'"'"'s pixel set data indicates that the pixel is in the indicated set of pixels; and

for each pixel whose near neighbor attribute data indicates that the near neighbor pixel is in the indicated set of pixels, applying a labeling criterion to determine whether to set the pixel'"'"'s pixel set data to indicate that the pixel is in the set of pixels and, if so, setting the pixel'"'"'s pixel set data accordingly.

11. The method of claim 10 in which the number of additional pixels is not sufficient to justify another step when the number of additional pixels is zero.

12. The method of claim 10 in which the labeling criterion is whether the pixel'"'"'s near neighbor attribute data indicates that the near neighbor pixel is in the indicated set of pixels.

13. The method of claim 10 in which, after the final step, the indicated set of pixels defines a region of the image.

14. A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of:

for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels;

operating the processor to produce, for a first one of the pixels, near neighbor attribute data indicating an attribute for a plurality of near neighbor links; and

operating the processor to apply a link relationship criterion to the near neighbor attribute data of the first pixel to determine whether the plurality of near neighbor links are related in a manner that meets the link relationship criterion and, if so, setting the first pixel'"'"'s pixel set data to indicate that the first pixel is in the indicated set of pixels;

the near neighbor attribute data indicating a distance between the first pixel and a second pixel;

the step of operating the processor to apply the link relationship criterion comprising a substep of varying the criterion with the distance indicated by the near neighbor attribute data.

15. A method of operating a system that includes memory and a processor connected for accessing the memory, the method comprising steps of:

for an image that includes a plurality of pixels, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including respective value data for the pixel and pixel set data indicating whether the pixel is in an indicated set of pixels;

operating the processor to produce, for each of a plurality of the pixels, near neighbor attribute data that indicate a first attribute for a first near neighbor link of the pixel and that indicate a second attribute for a second near neighbor link of the pixel; and

operating the processor to apply a link relationship criterion to the near neighbor attribute data of each of the plurality of the pixels to determine whether the first and second near neighbor links of each pixel are related to each other in a manner that meets the link relationship criterion and, if so, setting the pixel'"'"'s pixel set data to indicate that the pixel is in the indicated set of pixels.

16. The method of claim 15 in which the first attribute is a first length and the second attribute is a second length, the link relationship criterion comparing the first length and the second length.

17. The method of claim 15 in which the first attribute is a first orientation and the second attribute is a second orientation, the link relationship criterion comparing the first orientation and the second orientation.

18. The method of claim 15 in which the near neighbor attribute data indicate a first length for the first near neighbor link and a second length for the second near neighbor link, the link relationship criterion determining whether the first length is much longer than the second length.

19. The method of claim 18 in which the step of operating the processor to apply the link relationship criterion comprises substeps of:

obtaining a square of a difference between the first and second lengths;

obtaining a sum of the first and second lengths; and

obtaining a ratio of the square of the difference to the sum.

20. The method of claim 15 in which the near neighbor attribute data indicate a first orientation for the first near neighbor link and a second orientation for the second near neighbor link, the link relationship criterion determining whether the first and second orientations are sufficiently aligned.

21. The method of claim 20 in which the near neighbor attribute data further indicate a first distance for the first near neighbor link and a second distance for the second near neighbor link, the step of operating the processor to apply the link relationship criterion comprising substeps of:

obtaining a greater one of the first and second distances;

obtaining a minimum of a maximum distance and the greater one of the first and second distances; and

using the minimum to obtain a proportion of a maximum orientation difference.