Exhaustive hierarchical near neighbor operations on an image

• US 5,305,395 A
• Filed: 06/08/1990
• Issued: 04/19/1994
• 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: Clemens, David T., Mahoney, James V.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/535,438
• Time in Patent Office: 1,411 Days
• Field of Search: 382/27, 382/37, 382/55
• US Class Current: 382/205
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

Near neighbor data is produced hierarchically for each pixel of an image. Each pixel'"'"'s near neighbor data indicates the presence of an approximate near neighbor pixel in each of four quadrants with respect to the pixel, and can also indicate distance and orientation to the near neighbor pixel. The near neighbor data can be produced by parallel processing units, with each processing unit producing, for a respective pixel, a near neighbor data item at every level of the hierarchy. Each near neighbor data item can indicate the presence of an approximate near neighbor in a respective region of the image. A near neighbor data item for a higher level region can be produced by selecting between near neighbor pixels indicated by near neighbor data items for subregions at the next lower level, by choosing the near neighbor pixel that is nearer. The quadrants can be asymmetric so that each pixel is not included in any of its four quadrants and so that the quadrants do not overlap. To provide accurate near neighbor data for a black pixel, the near neighbor data can be shifted to the black pixel from the adjacent pixels, each at the origin of one of its quadrants. Offsets in the near neighbor data can also be adjusted accordingly. Each processing unit can store a bit vector such that the bit vectors together indicate the paths between neighbor pixels and owner pixels, to facilitate subsequent communication between owners and neighbors. Each bit of the bit vector can indicate, for each level of the hierarchy, which of the processing unit'"'"'s children is on the path at the next lower level. A path defined in this manner can be followed to shift focus from a current focus pixel to one of its near neighbors.

Claims

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

storing in the memory a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; and

operating the processor to produce, for each of the pixels, a respective set of near neighbor data items by operating on the data items in the body of data;

each near neighbor data item of each pixel indicating a near neighbor attribute of a respective one of a plurality of zones of orientation extending from the pixel to the edge of the image, the respective zones together including all orientations with respect to the pixel;

the near neighbor attribute of each zone of orientation indicating whether the zone of orientation includes a pixel that meets a near neighbor criterion;

the near neighbor attribute of a first one of the zones of orientation for a first one of the pixels indicating that the first zone includes a second pixel that meets the near neighbor criterion, the second pixel being at a distance from the first pixel, the distance from the first pixel to the second pixel being greater than one pixel.

2. The method of claim 1 in which each of the respective zones of orientation covers an equal range of orientations.

3. The method of claim 2 in which each respective zone of orientation is a quadrant.

4. The method of claim 1 in which the first pixel has four sides and has a respective neighboring pixel on each of the four sides;

each respective zone of orientation is a quadrant;

each of the zones of orientation including a respective one of the first pixel'"'"'s neighboring pixels;

none of the zones of orientation including the first pixel.

5. The method of claim 1 in which the pixel values are binary values, each having one of first and second values, one of the first and second values indicating that the respective pixel is white and the other of the first and second values indicating that the respective pixel is black;

the near neighbor pixel in each zone of orientation meeting the near neighbor criterion if the respective pixel value has the first value.

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

storing in the memory a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; and

operating the processor to produce a hierarchy of levels of near neighbor data items by operating on the pixel values in the body of data;

each level including a respective near neighbor data item for each pixel of the image;

each pixel'"'"'s respective near neighbor data item at each level indicating a near neighbor attribute for the pixel;

each pixel'"'"'s respective near neighbor data item at each level of the hierarchy including distance data for indicating a distance from the pixel to a respective near neighbor pixel that meets a near neighbor criterion in a respective region of the image;

the levels include a lowest level and a sequence of higher levels, each of the higher levels having a respective next lower level in the hierarchy;

the step of operating the processor comprising substeps of;

operating on each of the pixel values in the body of data to produce a respective starting near neighbor data item for each pixel, the respective starting near neighbor data item including starting data indicating whether the pixel meets the near neighbor criterion;

the lowest level of the hierarchy including the respective starting near neighbor data items; and

for each of the higher levels, producing each near neighbor data item of the level by operating on a respective set of the near neighbor data items of the respective next lower level, each pixel'"'"'s respective near neighbor data item at each of the higher levels indicating the near neighbor attribute for a respective region of the image;

the substep of producing each pixel'"'"'s respective near neighbor data item at each of the higher levels comprising a substep of operating on the distance data of the near neighbor data items in the respective set to select the near neighbor data item whose distance data indicates a smallest distance to the respective near neighbor pixel.

7. The method of claim 6 in which the indicated near neighbor attribute for the pixel is the presence in the respective region of the image of a near neighbor pixel meeting the near neighbor criterion.

8. The method of claim 6 in which the pixel values are binary values, each having one of first and second values, one of the first and second values indicating that the respective pixel is white and the other of the first and second values indicating that the respective pixel is black;

the substep of operating on each of the pixel values to produce a respective starting near neighbor data item comprising a substep of determining that each pixel meets the near neighbor criterion if the respective pixel value has the first value.

9. The method of claim 6 in which the processor includes, for each pixel, a respective processing unit;

each pixel'"'"'s respective processing unit producing the pixel'"'"'s respective starting near neighbor data item at the lowest level and the pixel'"'"'s respective near neighbor data item at each higher level.

10. The method of claim 6 in which the image is a two-dimensional image, each of the respective regions being rectangular, the distance data being for indicating a distance from a corner of the respective region to the respective near neighbor pixel.

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

storing in the memory a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; and

operating the processor to produce, for a first one of the pixels, a set of near neighbor data items by operating on the data items in the body of data;

each near neighbor data item indicating a near neighbor attribute of a respective zone of orientation with respect to the first pixel, the respective zones together including all orientations in the image with respect to the first pixel;

the respective zones of orientation with respect to the first pixel include first and second zones;

the first zone and second zone each adjoining a ray of pixels that includes and extends from the first pixel, the first zone including all of the pixels in the ray except the first pixel, the second zone including none of the pixels in the ray.

12. The method of claim 11 in which the first zone includes an adjacent pixel adjacent to the first pixel and a near neighbor pixel meeting a near neighbor criterion with respect to the adjacent pixel;

the step of operating the processor to produce the near neighbor data items comprising substeps of;

producing first offset data indicating a first offset from the adjacent pixel to the near neighbor pixel; and

producing second offset data indicating a second offset from the first pixel to the near neighbor pixel by operating on the first offset data.

13. The method of claim 12 in which the near neighbor pixel is the adjacent pixel, the second offset being from the first pixel to the adjacent pixel.

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

storing in the memory a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; and

operating the processor to produce, for each of the pixels, a respective set of near neighbor data items by operating on the data items in the body of data;

each near neighbor data item of each pixel indicating a near neighbor attribute of a respective one of a plurality of zones of orientation with respect to the pixel, the respective zones together including all orientations in the image with respect to the pixel;

the near neighbor attribute of each zone of orientation being a distance between the pixel and a near neighbor pixel in the zone of orientation that meets the near neighbor criterion.

15. The method of claim 14, further comprising a step of operating the processor to produce, for each pixel, a respective combined near neighbor data item by combining the pixel'"'"'s respective set of near neighbor data items.

16. A method of operating a system that includes memory and a processor connected for accessing the memory;

the method comprising steps of;

storing in the memory a respective pixel data item for each pixel of an image that includes a plurality of pixels, each pixel'"'"'s respective pixel data item being stored at a respective location, each pixel'"'"'s respective pixel data item including a respective value for the pixel; and

operating the processor to produce a hierarchy of near neighbor data items, each near neighbor data item indicating whether a pixel meeting a near neighbor criterion is in a respective region of the image, each near neighbor data item being at the respective location of a respective one of the pixels;

the hierarchy including a lowest level and a plurality of higher levels of near neighbor data items, each higher level having a respective next lower level;

the step of producing the hierarchy comprising substeps of;

operating the processor to produce a first one of the near neighbor data items at a first one of the higher levels by selecting one of a respective set of the near neighbor data items at the next lower level;

the first near neighbor data item being stored at a first pixel'"'"'s respective location, the selected near neighbor data item at the next lower level being at a second pixel'"'"'s respective location; and

operating the processor to store at the first pixel'"'"'s respective location path data indicating the second pixel'"'"'s respective location.

17. The method of claim 16 in which the path data is a single bit that can have one of first and second values, the first value indicating the second pixel'"'"'s respective location.

18. The method of claim 16 in which the processor comprises a respective processing unit for each of the pixels, the memory including respective local memory for each processing unit, each pixel'"'"'s respective location being in the respective local memory of the respective processing unit, the processing units being connected for communicating data;

the path data indicating the second pixel'"'"'s respective processing unit.

19. A method of operating a system that includes a plurality of processing units and, for each processing unit, respective local memory, each processing unit being connected for accessing its respective local memory;

the method comprising steps of;

storing in the respective local memory of each of the processing units a respective pixel data item, the pixel data items together forming a body of data defining an image that includes a plurality of pixels, each pixel data item indicating a value of a respective one of the pixels; and

producing a hierarchy of near neighbor data items, each near neighbor data item indicating whether a pixel meeting a near neighbor criterion is in a respective region of the image;

the hierarchy including a lowest level and a plurality of higher levels of near neighbor data items, each higher level having a respective next lower level;

the step of producing the hierarchy comprising substeps of;

operating each of the processing units to produce a respective starting near neighbor data item for each pixel by operating on the respective pixel data item, the respective starting near neighbor data item indicating whether the pixel meets the near neighbor criterion;

the lowest level of the hierarchy including the respective starting near neighbor data items; and

for each of the higher levels, operating each of the processing units to produce a respective near neighbor data item of the higher level by combining a respective set of the near neighbor data items of the respective next lower level;

a first one of the processing units producing a respective one of the near neighbor data items at each level by selecting one of the near neighbor data items in the respective set of the respective next lower level;

the respective near neighbor data item at each level indicating whether a pixel meeting the near neighbor criterion is in the respective region of the image in accordance with the selected near neighbor data item of the respective next lower level;

the selected near neighbor data item at a first one of the higher levels being produced by a second one of the processing units;

the substep of operating each of the processing units to produce a respective near neighbor data item further comprising, at the first higher level, a substep of operating the first processing unit to store first higher level path data indicating the second processing unit.

20. The method of claim 19 in which the first higher level path data is a single bit that can have one of first and second values, the first value indicating the first processing unit and the second value indicating the second processing unit.

21. The method of claim 19 in which the substep of operating each of the processing units to produce a respective near neighbor data item further comprises, at each level other than the first level, a substep of operating the first processing unit to store respective level path data for the level.

22. The method of claim 21 in which the first level path data and the respective level path data for the levels other than the first level together form a bit vector.

23. The method of claim 19 in which the processing units are connected for communicating data, the method further comprising a step of transmitting first data between processing units along a path through the hierarchy that leads to one of the processing units that produces the respective starting near neighbor data item of the pixel in the respective region of the second processing unit that meets the near neighbor criterion, the path including the first processing unit, the step of following the path further comprising operating the first processing unit to transmit the first data to the second processing unit according to the stored path data.

24. 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 a pixel value for the pixel and current focus data indicating whether the pixel is a current focus pixel;

operating the processor to produce near neighbor attribute data indicating an attribute for each of a set of near neighbor pixels of a first one of the pixels and path data indicating a path from the first pixel to each of the near neighbor pixels in the set;

operating the processor to apply a criterion to the near neighbor attribute data to select one of the near neighbor pixels; and

operating the processor to change the current focus data of the selected near neighbor pixel to indicate that the selected near neighbor pixel is the current focus pixel by following the path from the first pixel to the selected near neighbor pixel as indicated by the path data.

25. The method of claim 24 in which the near neighbor attribute data indicates a respective distance from the first pixel to each of the set of near neighbor pixels, the step of operating the processor to apply the criterion including a substep of selecting the near neighbor pixel whose respective distance is smallest.

26. The method of claim 24 in which the near neighbor attribute data indicates a respective relative orientation from the first pixel to each of the set of near neighbor pixels, the step of operating the processor to apply the criterion including a substep of selecting the near neighbor pixel whose respective relative orientation is closest to a given relative orientation.

27. The method of claim 24 in which the near neighbor attribute data indicates a respective attribute value for each of the set of near neighbor pixels, the first pixel also having a respective attribute value, the step of operating the processor to apply the criterion including a substep of selecting the near neighbor pixel whose respective attribute value is closest to the first pixel'"'"'s respective attribute value.

28. The method of claim 24 in which the step of operating the processor to change the current focus data comprises a substep of performing a hierarchical operation.

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

storing in the memory a body of data defining an image that includes a plurality of pixels, the body of data including a plurality of data items, each including a pixel value for a respective one of the pixels; and

operating the processor to produce, for a first one of the pixels, a set of near neighbor data items by operating on the data items in the body of data;

each near neighbor data item indicating a near neighbor attribute of a respective zone of orientation with respect to the first pixel, the respective zones together including all orientations in the image with respect to the first pixel;

the first pixel having four sides and having a respective neighboring pixel on each of the four sides;

each respective zone of orientation being a quadrant;

each of the zones of orientation including a respective one of the first pixel'"'"'s neighboring pixels;

none of the zones of orientation including the first pixel;

each of the neighboring pixels having a respective offset from the first pixel in only one of x- and y-directions, a first one of the neighboring pixels having a respective positive offset in the x-direction, a second one of the neighboring pixels having a respective positive offset in the y-direction, a third one of the neighboring pixels having a respective negative offset in the x-direction, and a fourth one of the neighboring pixels having a respective negative offset in the y-direction;

each of the zones of orientation including the respective neighboring pixel at a respective origin of the zone of orientation.

30. The method of claim 29 in which the zone of orientation that includes the first neighboring pixel extends from the first neighboring pixel in the positive x- and y-directions, the zone of orientation that includes the second neighboring pixel extends from the second neighboring pixel in the negative x-direction and in the positive y-direction, the zone of orientation that includes the third neighboring pixel extends from the third neighboring pixel in the negative x- and y-directions, and the zone of orientation that includes the fourth neighboring pixel extends from the fourth neighboring pixel in the positive x-direction and in the negative y-direction.

31. The method of claim 29 in which the zone of orientation that includes the first neighboring pixel extends from the first neighboring pixel in the positive x-direction and in the negative y-direction, the zone of orientation that includes the second neighboring pixel extends from the second neighboring pixel in the positive x- and y-directions, the zone of orientation that includes the third neighboring pixel extends from the third neighboring pixel in the negative x-direction and in the positive y-direction, and the zone of orientation that includes the fourth neighboring pixel extends from the fourth neighboring pixel in the negative x- and y-directions.