Efficient search for a gray-level pattern in an image using ranges of sums

• US 6,310,983 B1
• Filed: 06/16/1998
• Issued: 10/30/2001
• Est. Priority Date: 06/16/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Rucklidge, William J.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/097,724
• Time in Patent Office: 1,232 Days
• Field of Search: 382/276, 382/169, 382/170, 382/168, 382/172, 382/274, 382/275, 382/277, 382/293, 382/295, 382/309, 345/147, 398/298
• US Class Current: 382/275
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration

Abstract

The present invention is directed to a system for finding a transformation of a gray level pattern in an image. The system recursively searches a transformation space in a multi-resolution manner. At each resolution, the transformation space is divided into groups of translations. For each group, a set of difference values are computed and compared against a previously known best difference value. If any of the computed difference values are greater than the previously known best difference value, the corresponding group of translations is removed from further consideration.

Claims

1. A method for finding a transformation of a gray level pattern in an image, comprising the steps of:

dividing a transformation space into a plurality of groups of translations;

creating one or more image arrays, each image array includes one or more sums of pixels of a region of said image;

creating one or more pattern arrays, each pattern array includes one or more sums of pixels of a region of said pattern;

creating one or more minimum arrays based on said image arrays, wherein said minimum arrays contain the minimum value of a portion of said image arrays;

creating one or more maximum arrays based on said image arrays, wherein said maximum arrays contain the maximum value of a portion of said image arrays;

determining a first difference value for each group, each first difference value based on a first pattern array, a first minimum array corresponding to said first image array and a first maximum array corresponding to said first image array;

discarding translations in one or more groups having a first difference value greater than a previously determined best known difference value, wherein the best known difference value corresponds to a first difference value for a previously considered group; and

determining which translation that has not been discarded has an optimal difference value, said translation having said optimal difference value is said transformation of said gray level pattern in said image.

2. A method according to claim 1, further including the steps of:

receiving said pattern; and

receiving said image.

3. A method according to claim 2, further including the step of:

reporting said translation having said optimal difference value.

4. A method according to claim 1, wherein:

each group includes a reference transformation; and

said step of determining a difference value includes using said reference transformations to index said first minimum array and said first maximum array.

5. A method according to claim 1, wherein:

each minimum array includes a set of minimum values of portions of a corresponding image array.

6. A method according to claim 1, wherein:

each maximum array includes a set of maximum values of portions of a corresponding image array.

7. A method according to claim 1, further including the steps of:

determining a second difference value for at least a subset of remaining groups, each second difference value based on a second pattern array corresponding to a second image array, a second minimum array corresponding to said second image array and a second maximum array corresponding to said second image array; and

discarding translations in one or more groups having a second difference value greater than said previously determined best known difference value.

8. A method according to claim 7, further including the steps of:

determining a third difference value for at least a subset of remaining groups, each third difference value based on a third pattern array corresponding to a third image array, a third minimum array corresponding to said third image array and a third maximum array corresponding to said third image array; and

discarding translations in one or more groups having a third difference value greater than said previously determined best known difference value.

9. A method according to claim 8, wherein:

said step of determining a second difference value uses four values from said pattern array; and

said step of determining a third difference value uses sixteen values from said pattern array.

10. A method according to claim 7, wherein:

said step of determining a second difference value uses four values from said pattern array; and

said step of determining a first difference value uses one value from said pattern array.

11. A method according to claim 7, wherein:

said step of determining a second difference value uses four values from said pattern array, four values from said maximum array and four values from said minimum array.

12. A method according to claim 1, wherein said step of determining which translation includes the steps of:

subdividing a group of translations that has a first difference value less than or equal to said best known difference value, said step of subdividing creates a new set of groups having a new group size;

creating a new set of minimum arrays and maximum arrays based said new group size; and

repeating said steps of determining a first difference value and discarding translations using said new set of minimum arrays and maximum arrays.

13. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for discarding incorrect transformations when trying to find an optimal transformation of a gray level pattern in an image, the method comprising the steps of:

dividing a transformation space into a plurality of groups of translations;

creating one or more image arrays, each image array includes one or more sums of pixels of a region of said image;

creating one or more pattern arrays, each pattern array includes one or more sums of pixels of a region of said pattern;

creating one or more minimum arrays based on said image arrays, wherein said minimum arrays contain the minimum value of a portion of said image arrays;

creating one or more maximum arrays based on said image arrays, wherein said maximum arrays contain the maximum value of a portion of said image arrays;

determining a first difference value for each group, each first difference value based on a first pattern array, a first minimum array corresponding to said first image array and a first maximum array corresponding to said first image array; and

discarding translations in one or more groups having a first difference value greater than a previously determined best known difference value, wherein the best known difference value corresponds to a first difference value for a previously considered group.

14. A processor readable storage medium according to claim 13, wherein said method further includes the step of:

determining which translation that has not been discarded has an optimal difference value, said translation having said optimal difference value is said best transformation of said gray level pattern in said image.

15. A processor readable storage medium according to claim 14, wherein said step of determining which translation includes the steps of:

subdividing a group of translations that has a first difference value less than or equal to said best known difference value, said step of subdividing creates a new set of groups having a new group size;

creating a new set of minimum arrays and maximum arrays based said new group size; and

repeating said steps of determining a first difference value and discarding translations using said new set of minimum arrays and maximum arrays.

16. A processor readable storage medium according to claim 13, wherein:

each group includes a reference transformation; and

said step of determining a difference value includes using said reference transformations to index said first minimum array and said first maximum array.

17. A processor readable storage medium according to claim 13, wherein:

each minimum array includes a set of minimum values of portions of a corresponding image array.

18. A processor readable storage medium according to claim 13, wherein said method further includes the step of:

determining a second difference value for at least a subset of remaining groups, each second difference value based on a second pattern array corresponding to a second image array, a second minimum array corresponding to said second image array and a second maximum array corresponding to said second image array; and

discarding translations in one or more groups having a second difference value greater than said previously determined best known difference value.

19. A processor readable storage medium according to claim 18, wherein said method further includes the step of:

determining a third difference value for at least a subset of remaining groups, each third difference value based on a third pattern array corresponding to a third image array, a third minimum array corresponding to said third image array, a third maximum array corresponding to said third image array; and

discarding translations in one or more groups having a third difference value greater than said previously determined best known difference value.

20. A processor readable storage medium according to claim 19, wherein:

said step of determining a second difference value uses four values from said pattern array; and

said step of determining a third difference value uses sixteen values from said pattern array.

21. A processor readable storage medium according to claim 18, wherein:

said step of determining a second difference value uses four values from said pattern array; and

said step of determining a first difference value uses one value from said pattern array.

22. An apparatus for finding a transformation of a gray level pattern in an image, comprising:

an input device;

a display for showing said image;

a processing unit in communication with said input device and said display; and

a processor readable storage device in communication with said processing unit, said processor readable storage device storing processor readable code, said processor readable code for programming said processing unit to perform a method comprising the steps of;

dividing a transformation space into a plurality of groups of translations,

creating one or more image arrays, each image array includes one or more sums of pixels of a region of said image,

creating one or more pattern arrays, each pattern array includes one or more sums of pixels of a region of said pattern,

creating one or more minimum arrays based on said image arrays, wherein said minimum arrays contain the minimum value of a portion of said image arrays,

creating one or more maximum arrays based on said image arrays, wherein said maximum arrays contain the maximum value of a portion of said image arrays,

determining a first difference value for each group, each first difference value based on a first pattern array, a first minimum array corresponding to said first image array and a first maximum array corresponding to said first image array,

discarding translations in one or more groups having a first difference value greater than a previously determined best known difference value, wherein the best known difference value corresponds to a first difference value for a previously considered group, and

determining which translation that has not been discarded has an optimal difference value, said translation having said optimal difference value is said best transformation of said gray level pattern in said image.

23. An apparatus according to claim 22, wherein:

said input device is a video camera capable of capturing video images; and

said method capable of finding transformations of said pattern in successive video images captured by said video camera.

24. A method according to claim 22, wherein:

each group includes a reference transformation; and

said step of determining a difference value includes using said reference transformations to index said first minimum array and said first maximum array.

25. A method according to claim 22, wherein said method further includes the steps of:

determining a second difference value for at least a subset of remaining groups, each second difference value based on a second pattern array corresponding to a second image array, a second minimum array corresponding to said second image array and a second maximum array corresponding to said second image array; and

discarding translations in one or more groups having a second difference value greater than said previously determined best known difference value.

26. A method according to claim 25, wherein:

said step of determining a second difference value uses four values from said pattern array; and

said step of determining a first difference value uses one value from said pattern array.

27. A method according to claim 22, wherein said step of determining which translation includes the steps of:

subdividing a group of translations that has a first difference value less than or equal to said best known difference value, said step of subdividing creates a new set of groups having a new group size;

creating a new set of minimum arrays and maximum arrays based said new group size; and

repeating said steps of determining a first difference value and discarding translations using said new set of minimum arrays and maximum arrays.