Comparison of image shapes based on near neighbor data

• US 5,255,354 A
• Filed: 06/08/1990
• Issued: 10/19/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): Herndon, Heather R.
• Assistant Examiner(s): JANKUS, ALMIS R
• Application Number:
  US07/535,091
• Time in Patent Office: 1,229 Days
• Field of Search: 395/133, 395/141, 395/128-130, 395/133-135
• US Class Current: 382/203
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 7/564 from contours
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

Shapes are compared by obtaining a measure of dissimilarity based on near neighbor data. First, an image of one shape is analyzed to obtain, for each pixel position, a distance to the nearest pixel that meets a criterion, such as a black pixel. Then, a sum of distances is obtained by totalling the distances of the pixel positions at which an image of another shape meets the criterion. The sum indicates dissimilarity. The near neighbor distances and sum can be obtained by hierarchical operations.

Claims

1. A method of operating a system that includes memory and a processor, the processor including a plurality of processing units, each processing unit being connected for accessing data stored in the memory, the method comprising steps of:

for a first 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 first image pixel value;

the respective data item of each pixel in the first image being stored so that a respective processing unit for the pixel can access the pixel'"'"'s respective data item;

operating the processing units to produce, for each of the pixels in the first image, near neighbor distance data for the pixel, the near neighbor distance data indicating a distance to a near neighbor pixel whose first image pixel value meets a criterion;

each pixel'"'"'s processing unit producing the near neighbor distance data by operating on the pixel'"'"'s respective data item;

the step of operating the processing units to produce near neighbor distance data comprising substeps of;

finding, for each pixel in the first image, a set of near neighbor pixels that includes the near neighbor pixel; and

performing a hierarchical operation to produce, for each pixel'"'"'s set of near neighbor pixels, a set of distance values indicating the distances to the near neighbor pixels;

for a second image that includes a plurality of pixels, each mapping to a respective pixel of the first image, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including a second image pixel value;

the respective data item of each pixel in the second image being stored so that it can be accessed by a respective processing unit for the pixel;

each pixel in the second image and the respective pixel of the first image both having the same respective processing unit;

the pixels of the second image including a set of pixels whose pixel values meet the criterion; and

operating the processor to produce a measure of dissimilarity between the first and second images;

the step of operating the processor to produce the measure of dissimilarity comprising a substep of producing, for the set of pixels of the second image whose pixel values meet the criterion, a sum of distances, the distances being the distances indicated by the near neighbor distance data of the respective pixels of the first image.

2. The method of claim 1 in which the step of operating the processing units to produce the near neighbor distance data further comprises a substep of performing operations with the respective processing unit of each pixel of the first image to produce the pixel'"'"'s near neighbor distance data.

3. The method of claim 2 in which the step of operating the processor to produce a measure of dissimilarity further comprises a substep of performing a hierarchical operation that adds the near neighbor distance data produced by the respective processing units of the set of pixels of the second image.

4. The method of claim 1 in which the near neighbor distance data of each pixel in the first image indicate a distance to one of the set of near neighbor pixels that is nearest to the pixel.

5. The method of claim 1 in which each pixel value is binary, having either a first value indicating a white pixel or a second value indicating a black pixel, the criterion being that the pixel value have the second value, indicating a black pixel.

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

for a first 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 first image pixel value;

operating the processor to produce, for each of the pixels in the first image, near neighbor distance data for the pixel, the near neighbor distance data indicating a distance to a near neighbor pixel whose first image pixel value meets a criterion;

the processor producing the near neighbor distance data by operating on the first image pixel values;

operating the processor to produce, for each of the pixels in the first image, near neighbor attribute data for the pixel'"'"'s near neighbor pixel;

for a second image that includes a plurality of pixels, each mapping to a respective pixel of the first image, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including a second image pixel value;

the pixels of the second image including a set of pixels whose pixel values meet the criterion; and

operating the processor to produce a measure of dissimilarity between the first and second images;

the step of operating the processor to produce a measure of dissimilarity comprising substeps of;

producing, for the set of pixels of the second image whose pixel values meet the criterion, a sum of distances, the distances being the distances indicated by the near neighbor distance data of the respective pixels of the first image;

using the near neighbor attribute data for the respective first image pixels of the set of second image pixels to produce the measure of dissimilarity.

7. The method of claim 6 in which each first image pixel'"'"'s near neighbor attribute data indicates an orientation at the pixel'"'"'s near neighbor pixel.

8. The method of claim 6 in which each first image pixel'"'"'s near neighbor attribute data indicates a curvature at the pixel'"'"'s near neighbor pixel.

9. A method of operating a system that includes memory and a processor, the processor including a plurality of processing units, each processing unit being connected for accessing data stored in the memory, the method comprising acts of:

for a first 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 first image pixel value;

the respective data item of each pixel in the first image being stored so that a respective processing unit for the pixel can access the pixel'"'"'s respective data item;

operating the processing units to produce, for each of the pixels in the first image, near neighbor distance data for the pixel, the near neighbor distance data indicating a distance to a near neighbor pixel whose first image pixel value meets a criterion;

each pixel'"'"'s processing unit producing the near neighbor distance data by accessing and operating on the pixel'"'"'s respective data item;

the step of operating the processing units to produce near neighbor distance data comprising substeps of;

finding, for each pixel in the first image, a set of near neighbor pixels that includes the near neighbor pixel; and

performing a hierarchical operation to produce, for each pixel'"'"'s set of near neighbor pixels, a set of distance values indicating the distances to the near neighbor pixels;

for a second image that includes a plurality of pixels, each mapping to a respective pixel of the first image, storing in the memory a respective data item for each pixel, each pixel'"'"'s respective data item including a second image pixel value;

the respective data item of each pixel in the second image being stored so that it can be accessed by a respective processing unit for the pixel;

each pixel in the second image and the respective pixel of the first image both having the same respective processing unit;

the pixels of the second image including pixels whose pixel values meet the criterion; and

operating the processor to produce dissimilarity data indicating a measure of dissimilarity between the first and second images by accessing and operating on the second image pixel values and the near neighbor distance data;

the act of operating the processor to produce dissimilarity data comprising producing sum data indicating a sum of distances, the distances in the sum including the distance indicated by the near neighbor distance data of the respective pixel of the first image for each pixel in the second image whose pixel value meets the criterion.

10. A method of operating a computer that includes memory and a processor, the processor including a plurality of processing units, each processing unit being connected for accessing data stored in the memory, the method comprising acts of:

obtaining first image data defining a first image that includes a plurality of pixels;

the first image data including a respective data item for each pixel, each pixel'"'"'s respective data item including a first image pixel value;

storing the first image data in the memory;

the respective data item of each pixel in the first image being stored so that a respective processing unit for the pixel can access the pixel'"'"'s respective data item;

operating the processing units to produce, for each of the pixels in the first image, near neighbor distance data for the pixel, the near neighbor distance data indicating a distance to a near neighbor pixel whose first image pixel value meets a criterion;

each pixel'"'"'s processing unit producing the near neighbor distance data by accessing and operating on the pixel'"'"'s respective data item;

the step of operating the processing units to produce near neighbor distance data comprising substeps of;

finding, for each pixel in the first image, a set of near neighbor pixels that includes the near neighbor pixel; and

performing a hierarchical operation to produce, for each pixel'"'"'s set of near neighbor pixels, a set of distance values indicating the distances to the near neighbor pixels;

obtaining second image data defining a second image that includes a plurality of pixels, each mapping to a respective pixel of the first image;

the second image data including a respective data item for each pixel, each pixel'"'"'s respective data item including a second image pixel value;

the pixels of the second image including pixels whose pixel values meet the criterion;

storing the second image data in the memory;

the respective data item of each pixel in the second image being stored so that it can be accessed by a respective processing unit for the pixel;

each pixel in the second image and the respective pixel of the first image both having the same respective processing unit; and

operating the processor to produce dissimilarity data indicating a measure of dissimilarity between the first and second images by accessing and operating on the second image pixel values and the near neighbor distance data;

the act of operating the processor to produce dissimilarity data comprising producing sum data indicating a sum of distances, the distances in the sum including the distance indicated by the near neighbor distance data of the respective pixel of the first image for each pixel in the second image whose pixel value meets the criterion.