Rotation and scale invariant image finder

• US 6,272,247 B1
• Filed: 05/18/1999
• Issued: 08/07/2001
• Est. Priority Date: 05/18/1998
• Status: Active Grant

• Current Assignee: Scott D ROTH
• Original Assignee: Datacube, Inc.
• Inventors: Manickam, Swaminathan, Bushman, Thomas W., Roth, Scott D.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/314,730
• Time in Patent Office: 812 Days
• Field of Search: 382/217, 382/155, 382/159, 382/209, 382/215, 382/216, 382/218, 382/296, 382/297, 382/298
• US Class Current: 382/217
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A system for digital image recognition which combines sparse correlation with image pyramiding to reduce the number of pixels used in correlation provides effective recognition of a reference image template without exhaustive correlation of all pixels in the reference image template. An optimal sparse pixel set is selected from the pixels of the reference image template by correlating the reference image template against a search image scene which is to be searched. Such a sparse pixel set includes those pixels which are optimal in defining the correlation sensitive features of the reference image template. By terminating the accumulation of sparse pixels at an optimal point, performance is maximized without compromising accuracy of recognition. The resultant optimal sparse pixel set is then correlated against the pixels in the search image scene through a series of transformations to find a match of the reference image template within the search image scene.

Claims

1. A method of computing an optimal sparse pixel set indicative of a reference image template and adapted for grayscale correlation based digital image pattern matching comprising:

computing an initial sparse pixel set from a subset of said pixels in said reference image template;

initializing, by storing in an optimal pixel accumulator set, said initial sparse pixel set;

correlating said optimal pixel accumulator set with said reference image template and said search image scene to determine a candidate optimal pixel based on a correlation score from the subset of pixels of said reference image template not already in said optimal pixel accumulator set;

storing, in said optimal pixel accumulator set, said candidate optimal pixel if said candidate optimal pixel is highly influential on said correlation score;

building, from among the remaining pixels of said reference image template, said optimal pixel accumulator set by repeating said correlating and said storing;

terminating said building when said accumulator sparse pixel set contains an optimal set of pixels according to predetermined accumulation optimization logic; and

storing, in said optimal sparse pixel set said optimal pixel accumulator set.

2. The method of claim 1 wherein said computing of said initial sparse pixel set is preceded by translating said reference image template and said search image scene into an image pyramid form.

3. The method of claim 1 wherein said predetermined accumulation optimization logic further comprises determining which of said pixels are more significant to said correlation score than other pixels already accumulated in said set optimal pixel accumulator set.

4. The method of claim 3 wherein said predetermined accumulation optimization logic further comprises determining when an average of said correlation score changes by a predetermined amount.

5. The method of claim 4 wherein said predetermined accumulation optimization logic further comprises determining when a summation of said correlation scores from among pixels selected for said storing and pixels not selected for said storing increases by a predetermined amount.

6. The method of claim 5 wherein said predetermined amount is about 0.001.

7. The method of claim 1 wherein said pixels having a highly indicative score is determined by pixels having a greater correlation score than other pixels already accumulated in said optimal pixel accumulator set.

8. The method of claim 1 wherein said correlating further comprises transforming said reference image template through a predetermined series of transformations.

9. The method of claim 8 wherein said transforming further comprises rotating and scaling.

11. The method of claim 1 wherein said correlating further includes scanning said reference image template pixel by pixel.

29. The method as in claim 1 wherein said correlation score is a high false positive score.

30. The method as in claim 1 wherein said predetermined accumulation optimization logic comprises determining when adding additional pixels to said optimal pixel accumulator set does not further discriminate said reference image template from said search image scene.

31. The method as in claim 29 wherein said predetermined accumulation optimization logic comprises determining when said high false positive score exhibits an increasing trend.

32. The method as in claim 9 wherein said transforming further comprises adjusting for perspective distortion.

33. The method as in claim 32 wherein said transforming further comprises horizontal and vertical shifting pixel by pixel.

10. The method of claim `wherein said rotating and scaling occur at predetermined intervals along a predetermined range.

12. A computer program product for use in a computer system adapted for pattern matching of a digital reference image template comprising:

a computer useable medium having computer readable program code adapted for computing an optimal sparse pixel set indicative of a reference image template embodied thereon, said computer program product further including;

computer readable program code for computing an initial sparse pixel set from a subset of said pixels in said reference image template;

computer readable program code for initializing, by storing in an optimal pixel accumulator set, said initial sparse pixel set;

computer readable program code for correlating said optimal pixel accumulator set with said reference image template and said search image scene to determine a candidate optimal pixel based on a correlation score from the subset of pixels of said reference image template not already in said optimal pixel accumulator set;

computer readable program code for storing, in said optimal pixel accumulator set, said candidate optimal pixel if said candidate optimal pixel is highly influential on said correlation score;

computer readable program code for building, from among the remaining pixels of said reference image template, said optimal pixel accumulator set by repeating said correlating and said storing;

computer readable program code for terminating said building when said accumulator sparse pixel set contains an optimal set of pixels according to predetermined accumulation optimization logic; and

computer readable program code for storing, in said optimal sparse pixel set said optimal pixel accumulator set.

13. The computer program product of claim 12 wherein said program code further includes code for translating said reference image template and said search image scene into an image pyramid form.

14. The computer program product of claim 12 wherein said program code for predetermined accumulation optimization logic further comprises program code for determining which of said pixels are more significant to said correlation score than other of said pixels already accumulated in said optimal pixel accumulator set.

15. The computer program product of claim 14 wherein said program code for predetermined accumulation optimization logic further comprises program code for determining when a summation of said correlation scores changes by a predetermined amount.

16. The computer program product of claim 15 wherein said program code for predetermined accumulation optimization logic further comprises program code for determining when the average of said correlation score from among pixels selected for said storing and pixels not selected for said storing increases by a predetermined amount.

17. The computer program product of claim 16 wherein said predetermined amount is about 0.001.

18. The computer program product of claim 12 wherein said program code for determining pixels having a highly indicative score determines pixels having a greater correlation score than other pixels already accumulated in said optimal pixel accumulator set.

19. The computer program product of claim 12 wherein said program code for correlating further comprises program code for transforming said reference image template through a predetermined series of transformations.

20. The computer program product of claim 19 wherein said program code for transforming further comprises program code for rotating and scaling said reference image template.

21. The computer program product of claim 20 wherein said rotating and scaling occur at predetermined intervals along a predetermined range.

22. The computer program product of claim 19 wherein said program code for correlating further includes scanning said reference image template pixel by pixel.

23. A method of digital image recognition for finding a reference image template in a search image scene through grayscale correlation matching comprising the steps of:

providing a reference image template represented as a pixelated grayscale digital image;

providing a search image scene represented as a pixelated grayscale digital image;

computing an optimal sparse pixel set indicative of said reference image template by the further steps of;

computing an initial sparse pixel set from a subset of said pixels in said reference image template;

initializing, by storing in an optimal pixel accumulator set, said initial sparse pixel set;

correlating said optimal pixel accumulator set with said reference image template and said search image scene to determine a candidate optimal pixel based on a correlation score from the subset of pixels of said reference image template not already in said optimal pixel accumulator set;

storing, in said optimal pixel accumulator set, said candidate optimal pixel if said candidate optimal pixel is highly correlation sensitive;

building, from among the remaining pixels of said reference image template, said optimal pixel accumulator set by repeating said correlating and said storing steps;

terminating said building when said accumulator sparse pixel set contains an optimal set of pixels according to predetermined accumulation optimization logic; and

storing, in said optimal sparse pixel set, said optimal pixel accumulator set;

locating, within said search image scene, said reference image template by correlating said optimal sparse pixel set with said search image scene.

24. The method as in claim 23 wherein said locating includes scanning said search image scene pixel by pixel.

25. The method as in claim 24 wherein said locating further includes selecting an additional subset of accuracy pixels from said reference image template for inclusion in said optimal sparse pixel set.

26. A computer apparatus for pattern matching of pixelated digital images comprising:

a reference image memory for storing a pixelated reference image template comprising a plurality of pixels in a matrix; and

a search scene memory for storing a pixelated search image template comprising a plurality of pixels in a matrix, wherein each of said pixels has a grayscale and a position;

an optimal sparse pixel memory adapted to store a subset of said pixels of said reference image template; and

a processor adapted to determine a correlation score of a plurality of pixels, wherein said correlation results are indicative of a pattern match between said reference image template and said search scene image, said correlation results being determined by sequentially copying a plurality of said pixels from said optimal sparse pixel memory and a plurality of said pixels from said search image memory into said processor for comparing said grayscale values and said positions,

wherein said pixels are selectively stored in said optimal sparse pixel memory as a result of a correlation score which is highly influential in determining said pattern match.

27. The computer apparatus as in claim 26 wherein said reference image memory and said search scene memory further comprise pyramid image memory adapted to store said pixels in a multilevel pyramid wherein each level of said pyramid has a varying resolution.

28. The computer apparatus as in claim 26 wherein said selective storing of said pixels in said optimal sparse pixel memory is determined by pixels affecting said correlation score such that said pixels are more likely than said pixels in said reference image memory to determine said pattern match.