Object recognition with occurrence histograms
First Claim
1. A computer-implemented object recognition process for finding an object being sought in a search image, said object recognition process comprising using a computer to perform the following acts:
- capturing model images of the object from a plurality of viewpoints around the object;
computing a co-occurrence histogram (CH) for each model image;
generating a plurality of search windows each comprising a portion of the search image;
computing a CH for each search window;
assessing a degree of similarity between each model image CH and each of the search window CHs; and
designating a search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold as potentially containing the object being sought;
wherein, a CH is computed by generating a count of every possible pair of pixels in an image that exhibit the same combination of a prescribed pixel characteristic and which are separated by the same distance.
3 Assignments
0 Petitions
Accused Products
Abstract
This invention is directed toward an object recognition system and process that identifies the location of a modeled object in a search image. This involves first capturing model images of the object whose location is to be identified in the search image. A co-occurrence histogram (CH) is then computed for each model images. A model image CH is computed by generating counts of every pair of pixels whose pixels exhibit colors that fall within the same combination of a series of pixel color ranges and which are separated by a distance falling within the same one of a series of distance ranges. Next, a series of search windows, of a prescribed size, are generated from overlapping portions of the search image. A CH is also computed for each of these search windows using the pixel color and distance ranges established for the model image CHs. A comparison between each model image CH and each search window CH is conducted to assess their similarity. A search window that is associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold is designated as potentially containing the object being sought. This designation can be presumed final, or further refined. This system and process requires that the size of the search window, color ranges and distance ranges be chosen ahead of time. The choice of these parameters can be optimized via a false alarm analysis.
68 Citations
73 Claims
-
1. A computer-implemented object recognition process for finding an object being sought in a search image, said object recognition process comprising using a computer to perform the following acts:
-
capturing model images of the object from a plurality of viewpoints around the object;
computing a co-occurrence histogram (CH) for each model image;
generating a plurality of search windows each comprising a portion of the search image;
computing a CH for each search window;
assessing a degree of similarity between each model image CH and each of the search window CHs; and
designating a search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold as potentially containing the object being sought;
wherein,a CH is computed by generating a count of every possible pair of pixels in an image that exhibit the same combination of a prescribed pixel characteristic and which are separated by the same distance. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
selecting a series of candidiate separation angles for spacing said viewpoints around the object;
for each candidate separation angle, assessing a degree of similarity between at least one pair of model images having adjacent viewpoints separated by the candidate separation angle;
identifying the largest candidate separation angle associated with the model images which has an assessed degree of similarity exceeding a prescribed model image separation angle threshold; and
designating the identified largest candidate separation angle as the separation angle to be employed in capturing the model images of the object.
-
-
4. The process of claim 1, wherein the act of capturing model images of the object comprises the act of capturing each model image from viewpoints located at the same distance away from the object.
-
5. The process of claim 1, wherein the act of capturing model images of the object comprises the act of capturing multiple model images of the object at each viewpoint around the object, and wherein each model image captured at the same viewpoint is captured at a different distance away from the object.
-
6. The process of claim 5, wherein the act of capturing multiple model images of the object at each viewpoint around the object at a different distance away from the object, comprises the act of capturing each of the multiple model images at the same separation distance from each other.
-
7. The process of claim 6, wherein the act of capturing multiple model images of the object at each viewpoint around the object at a different distance away from the object, comprises the acts of:
-
selecting a series of candidate separation distances for spacing said multiple model images from each other at a particular viewpoint;
for each candidate separation distance, assessing a degree of similarity between at least one pair of adjacent model images separated by the candidate separation distance, identifying the largest candidate separation distance associated with the model images which has an assessed degree of similarity exceeding a prescribed model image separation distance threshold; and
designating the identified largest candidate separation distance as the separation distance to be employed in capturing the model images of the object.
-
-
8. The process of claim 1, wherein the act of computing a CH for each model image, comprises the acts of:
-
determining said prescribed pixel characteristic exhibited by each pixel in the model image;
dividing the overall gamut of said prescribed pixel characteristic into a series of pixel characteristic ranges;
respectively quantizing the prescribed pixel characteristic of each pixel in the model image by assigning the pixel to the pixel characteristic range into which the pixel'"'"'s prescribed characteristic belongs;
identifying every possible unique, non-ordered pair of pixels in the model image;
respectively quantizing the distance separating the two pixels of each identified pixel pair of the model image by assigning the pixel pair to a one of a series of prescribed distance ranges to which its separation distance belongs, wherein said series of prescribed distance ranges is established by selecting a maximum separation distance of interest and dividing it into a number of smaller distance ranges;
categorizing each pixel pair by the assigned pixel characteristic range of each of its respective pixels and the distance range assigned to the pair, wherein the resulting categories are hereinafter referred to as pixel characteristic mix/distance categories; and
establishing a count of the number of pixel pairs belonging to the same pixel characteristic mix/distance category.
-
-
9. The process of claim 8, wherein the act of dividing the overall gamut of said prescribed pixel characteristic into a series of pixel characteristic ranges, comprises the act of dividing the overall gamut into a series of equally-sized pixel characteristic ranges.
-
10. The process of claim 8, wherein the series of distance ranges comprises equally-sized distance ranges.
-
11. The process of claim 8, wherein the prescribed pixel characteristic is the pixel color.
-
12. The process of claim 8, wherein the model image is a depth image and the prescribed pixel characteristic is the pixel depth.
-
13. The process of claim 1, wherein the act of generating the plurality of search windows, comprises the acts of:
-
cordoning off the entire search image into a series of regions having a prescribed size and shape; and
designating each region as a separate search window.
-
-
14. The process of claim 13, wherein the prescribed shape of each region is rectangular, thereby forming rectangular search windows.
-
15. The process of claim 13, wherein each region is of equal size, thereby forming equally-sized search windows.
-
16. The process of claim 13, wherein each region of the search image overlaps all adjacent regions.
-
17. The process of claim 16, wherein each region of the search image overlaps its adjacent regions by one half of its width if the adjacent regions are beside the overlapping region, and by one-half of its height if the adjacent regions are above or below the overlapping region.
-
18. The process of claim 8, wherein the act of computing the CH for each search window, comprises the acts of:
-
respectively quantizing the prescribed pixel characteristic of those pixels of the search window having a prescribed pixel characteristic falling within one of the pixel characteristic ranges by assigning the pixel to the pixel characteristic range into which the pixel'"'"'s prescribed characteristic belongs;
identifying every possible unique, non-ordered pair of pixels in the search window;
respectively quantizing the distance separating the two pixels of those identified pixel pairs of the search window having separation distances that fall within one of the distance ranges by assigning the pixel pair to the distance range to which its separation distance belongs;
categorizing each pixel pair having quantized pixel characteristics and distance by the assigned pixel characteristic range of each of its respective pixels and the distance range assigned to the pair, and establishing a count of the number of categorized pixel pairs having the same pixel characteristic mix/distance category.
-
-
19. The process of claim 18, wherein the act of assessing the degree of similarity between each model image CH and each of the search window CHs comprises, for each model image and search window assessed, the acts of:
-
comparing the count for each pixel characteristic mix/distance category of the model image to the count for the corresponding pixel characteristic mix/distance category of the search window;
identify the smaller of the two counts in each corresponding category; and
add the identified smaller count from each corresponding category together to produce a similarity value.
-
-
20. The process of claim 19, wherein the act of designating a search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold as potentially containing the object being sought, comprises the act of designating a search window as potentially containing the object being sought if the similarity value computed for the search window CH and one of the model image CHs exceeds the prescribed search threshold.
-
21. The process of claim 20, wherein the act of designating a search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold as potentially containing the object being sought, comprises the act of designating each search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds the prescribed search threshold, whenever it is anticipated that there will be more than one of the sought after objects in the search image.
-
22. The process of claim 21, further comprising the act of declaring each search window designated as potentially containing the object being sought as actually containing the object.
-
23. The process of claim 20, wherein the act of designating a search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold as potentially containing the object being sought, comprises the acts of:
-
determining which of the search windows associated with a search window CH having a degree of similarity to one of the model image CHs that exceeds the prescribed search threshold has the largest computed similarity value; and
designating only said search window determined to be associated with the largest similarity value as potentially containing the object being sought.
-
-
24. The process of claim 23, further comprising the act of declaring the sole search window designated as potentially containing the object being sought as actually containing the object.
-
25. The process of claim 1, further comprising, for each search window designated as potentially containing the object being sought, the acts of:
-
(a) naming the search window designated as potentially containing the object being sought the current primary search window;
(b) generating additional search windows having the same shape and size as the current primary search window from portions of the search image which are translated in comparison to the portion of the search image associated with the primary search window;
(c) computing a CH for each of the additional search windows;
(d) assessing the degree of similarity between each additional search window CH and the model image CH associated with the primary search window;
(e) determining whether any of the additional search windows have a higher degree of similarity to the model image CH associated with the primary search window than the primary search window itself;
(f) whenever none of the additional search windows has a higher degree of similarity to the model image CH associated with the primary search window than the primary search window itself, declaring the current primary search window as actually containing the object being sought;
(g) whenever one or more of the additional search windows has a higher degree of similarity to the model image CH associated with the currently named primary search window than that primary search window itself, naming the additional search window having the highest degree of similarity to the model image CH associated with the previously named primary search window as the current primary search window in place of the previously named primary search window; and
(h) repeating acts (b) through (g) for each newly named current primary search window.
-
-
26. The process of claim 25, wherein the act of generating additional search windows comprises the act of using portions of the search image translated in as many of the following directions as possible:
- (i) one pixel row up, (ii) one pixel row down;
(iii) one pixel column to the right; and
(iv) one pixel column to the left.
- (i) one pixel row up, (ii) one pixel row down;
-
27. The process of claim 19, wherein the scale of the search image is different from that of the model image, and wherein the process further comprises:
-
performing, prior to the act of quantizing the separation distances of the pixel pairs, the act of multiplying the distance ranges computed for the model image by a factor representing the ratio of the search image scale to the model image scale; and
whereinthe act of comparing the count for each pixel characteristic mix/distance category of the model image to the count for the corresponding pixel characteristic mix/distance category of the search window comprises comparing the count for each pixel characteristic mix/distance category of the model image to the count for the pixel characteristic mix/distance category of the search window associated with the same mix of pixel characteristic ranges but with a distance range corresponding the distance range of the model image multiplied by the factor representing the ratio of the search image scale to the model image scale.
-
-
28. An object recognition system for finding an object being sought in a search image, comprising:
-
a general purpose computing device;
a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to, capture model images of the object from a plurality of viewpoints around the object;
compute a co-occurrence histogram (CH) for each model image, wherein a model image CH is computed by generating counts of every pair of pixels whose pixels exhibit a prescribed pixel characteristic that fall within the same combination of a series of pixel characteristic ranges and which are separated by a distance falling within the same one of a series of distance ranges;
generating a plurality of search windows each comprising a portion of the search image;
computing a CH for each search window, wherein a search window CH is computed by generating counts of every pair of pixels whose pixels exhibit a prescribed pixel characteristic that fall within the same combination of said series of pixel characteristic ranges and which are separated by a distance falling within the same one of said series of distance ranges;
assess a degree of similarity between each model image CH and each of the search window CHs; and
designate a search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold as containing the object being sought. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50)
selecting a series of candidate separation angles for spacing said viewpoints around the object;
for each candidate separation angle, assessing a degree of similarity between at least one pair of model images having adjacent viewpoints separated by the candidate separation angle;
identifying the largest candidate separation angle associated with the model images which has an assessed degree of similarity exceeding a prescribed model image separation angle threshold; and
designating the identified largest candidate separation angle as the separation angle to be employed in capturing the model images of the object.
-
-
31. The system of claim 28, wherein the program module for capturing model images of the object comprises a sub-module for capturing each model image from viewpoints located at the same distance away from the object.
-
32. The system of claim 28, wherein the program module for capturing model images of the object comprises a sub-module for capturing multiple model images of the object at each viewpoint around the object, and wherein each model image captured at the same viewpoint is captured at a different distance away from the object.
-
33. The system of claim 32, wherein the sub-module for capturing multiple model images of the object at each viewpoint around the object at a different distance away from the object, comprises a sub-module for capturing each of the multiple model images at the same separation distance from each other.
-
34. The system of claim 33, wherein the sub-module for capturing multiple model images of the object at each viewpoint around the object at a different distance away from the object, comprises sub-modules for:
-
selecting a series of candidate separation distances for spacing said multiple model images from each other at a particular viewpoint;
for each candidate separation distance, assessing a degree of similarity between at least one pair of adjacent model images separated by the candidate separation distance;
identifying the largest candidate separation distance associated with the model images which has an assessed degree of similarity exceeding a prescribed model image separation distance threshold; and
designating the identified largest candidate separation distance as the separation distance to be employed in capturing the model images of the object.
-
-
35. The system of claim 28, wherein the program module for computing a CH for each model image, comprises sub-modules for:
-
determining said prescribed pixel characteristic exhibited by each pixel in the model image;
dividing the overall gamut of said prescribed pixel characteristic into a series of pixel characteristic ranges;
respectively quantizing the prescribed pixel characteristic of each pixel in the model image by assigning the pixel to the pixel characteristic range into which the pixel'"'"'s prescribed characteristic belongs;
identifying every possible unique, non-ordered pair of pixels in the model image;
respectively quantizing the distance separating the two pixels of each identified pixel pair of the model image by assigning the pixel pair to a one of a series of prescribed distance ranges to which its separation distance belongs, wherein said series of prescribed distance ranges is established by selecting a maximum separation distance of interest and dividing it into a number of smaller distance ranges;
categorizing each pixel pair by the assigned pixel characteristic range of each of its respective pixels and the distance range assigned to the pair, wherein the resulting categories are hereinafter referred to as pixel characteristic mix/distance categories; and
establishing a count of the number of pixel pairs belonging to the same pixel characteristic mix/distance category.
-
-
36. The system of claim 35, wherein the sub-module for dividing the overall gamut of said prescribed pixel characteristic into said series of pixel characteristic ranges, comprises a sub-module for dividing the overall gamut into a series of equally-sized pixel characteristic ranges.
-
37. The system of claim 35, wherein the series of distance ranges comprises equally-sized distance ranges.
-
38. The system of claim 35, wherein the prescribed pixel characteristic is the pixel color.
-
39. The system of claim 28, wherein the program module for generating the plurality of search windows, comprises sub-modules for:
-
dividing the entire search image into a series of regions having a prescribed size and shape; and
designating each region as a separate search window.
-
-
40. The system of claim 39, wherein the prescribed shape of each region is rectangular, thereby forming rectangular search windows.
-
41. The system of claim 39, wherein each region is of equal size, thereby forming equally-sized search windows.
-
42. The system of claim 39, wherein each region of the search image overlaps all adjacent regions.
-
43. The system of claim 35, wherein the program module for computing the CH for each search window, comprises sub-modules for:
-
respectively quantizing the prescribed pixel characteristic of those pixels of the search window having a prescribed pixel characteristic falling within one of the pixel characteristic ranges by assigning the pixel to the pixel characteristic range into which the pixel'"'"'s prescribed characteristic belongs;
identifying every possible unique, non-ordered pair of pixels in the search window;
respectively quantizing the distance separating the two pixels of those identified pixel pairs of the search window having separation distances that fall within one of the distance ranges by assigning the pixel pair to the distance range to which its separation distance belongs;
categorizing each pixel pair having quantized pixel characteristics and distance by the assigned pixel characteristic range of each of its respective pixels and the distance range assigned to the pair; and
establishing a count of the number of categorized pixel pairs having the same pixel characteristic mix/distance category.
-
-
44. The system of claim 43, wherein the sub-module for assessing the degree of similarity between each model image CH and each of the search window CHs comprises, for each model image and search window assessed, sub-modules for:
-
comparing the count for each pixel characteristic mix/distance category of the model image to the count for the corresponding pixel characteristic mix/distance category of the search window;
identify the smaller of the two counts in each corresponding category, and add the identified smaller count from each corresponding category together to produce a similarity value.
-
-
45. The system of claim 44, wherein the program module for designating a search window as containing the object being sought, comprises a sub-module for designating a search window as potentially containing the object being sought if the similarity value computed for the search window CH and one of the model image CHs exceeds the prescribed search threshold.
-
46. The system of claim 45, wherein the program module for designating a search window as containing the object being sought, further comprises a sub-module for designating each search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds the prescribed search threshold as containing the object being sought, whenever it is anticipated that there will be more than one of the sought after objects in the search image.
-
47. The system of claim 45, wherein the program module for designating a search window as containing the object being sought, comprises the acts of:
-
determining which of the search windows associated with a search window CH having a degree of similarity to one of the model image CHs that exceeds the prescribed search threshold has the largest computed similarity value; and
designating only said search window determined to be associated with the largest similarity value as containing the object being sought.
-
-
48. The system of claim 28, further comprising, for each search window designated as containing the object being sought, a program module for refining the location of the search window in the search image, said program module for refining comprising sub-modules for:
-
(a) naming the search window designated as containing the object being sought the current primary search window, (b) generating additional search windows having the same shape and size as the current primary search window from portions of the search image which are translated in comparison to the portion of the search image associated with the primary search window;
(c) computing a search window CH for each of the additional search windows;
(d) assessing the degree of similarity between each additional search window CH and the model image CH associated with the primary search window;
(e) determining whether any of the additional search windows have a higher degree of similarity to the model image CH associated with the primary search window than the primary search window itself;
(f) whenever none of the additional search windows has a higher degree of similarity to the model image CH associated with the primary search window than the primary search window itself, declaring the current primary search window as representing the exact location n the search image of the object being sought;
(g) whenever one or more of the additional search windows has a higher degree of similarity to the model image CH associated with the currently named primary search window than that primary search window itself, naming the additional search window having the highest degree of similarity to the model image CH associated with the previously named primary search window as the current primary search window in place of the previously named primary search window; and
(h) repeating acts (b) through (g) for each newly named current primary search window.
-
-
49. The system of claim 48, wherein the sub-module for generating additional search windows comprises a sub-module for using portions of the search image translated in as many of the following directions as possible:
- (i) one pixel row up, (ii) one pixel row down;
(iii) one pixel column to the right; and
(iv) one pixel column to the left.
- (i) one pixel row up, (ii) one pixel row down;
-
50. The system of claim 44, wherein the scale of the search image is different from that of the model image, and wherein the system further comprises a program module for:
-
performing, prior to the act of quantizing the separation distances of the pixel pairs, the act of multiplying the distance ranges computed for the model image by a factor representing the ratio of the search image scale to the model image scale; and
whereinthe act of comparing the count for each pixel characteristic mix/distance category of the model image to the count for the corresponding pixel characteristic mix/distance category of the search window comprises comparing the count for each pixel characteristic mix/distance category of the model image to the count for the pixel characteristic mix/distance category of the search window associated with the same mix of pixel characteristic ranges but with a distance range corresponding the distance range of the model image multiplied by the factor representing the ratio of the search image scale to the model image scale.
-
-
51. A computer readable storage medium for storing an executable computer program in a general purpose computer to perform an object recognition procedure for finding an object being sought in a search image, comprising:
-
a computer program comprising program modules stored in a storage medium, wherein the computer is directed by the program modules to, capture model images of the object from a plurality of viewpoints around the object;
compute a co-occurrence histogram (CH) for each model image;
generate a plurality of search windows each comprising a portion of the search image;
compute a CH for each search window;
assess a degree of similarity between each model image CH and each of the search window CHs; and
designate a search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds a prescribed search threshold as containing the object being sought; and
wherein,a CH is computed by generating a count of every possible pair of pixels in an image that exhibit the same combination of a prescribed pixel characteristic and which are separated by the same distance. - View Dependent Claims (52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73)
selecting a series of candidate separation angles for spacing said viewpoints around the object;
for each candidate separation angle, assessing a degree of similarity between at least one pair of model images having adjacent viewpoints separated by the candidate separation angle;
identifying the largest candidate separation angle associated with the model images which has an assessed degree of similarity exceeding a prescribed model image separation angle threshold; and
designating the identified largest candidate separation angle as the separation angle to be employed in capturing the model images of the object.
-
-
54. The computer-readable storage medium of claim 51, wherein the program module for capturing model images of the object comprises a sub-module for capturing each model image from viewpoints located at the same distance away from the object.
-
55. The computer-readable storage medium of claim 51, wherein the program module for capturing model images of the object comprises a sub-module for capturing multiple model images of the object at each viewpoint around the object, and wherein each model image captured at the same viewpoint is captured at a different distance away from the object.
-
56. The computer-readable storage medium of claim 55, wherein the sub-module for capturing multiple model images of the object at each viewpoint around the object at a different distance away from the object, comprises a sub-module for capturing each of the multiple model images at the same separation distance from each other.
-
57. The computer-readable storage medium of claim 56, wherein the sub-module for capturing multiple model images of the object at each viewpoint around the object at a different distance away from the object, comprises sub-modules for:
-
selecting a series of candidate separation distances for spacing said multiple model images from each other at a particular viewpoint;
for each candidate separation distance, assessing a degree of similarity between at least one pair of adjacent model images separated by the candidate separation distance;
identifying the largest candidate separation distance associated with the model images which has an assessed degree of similarity exceeding a prescribed model image separation distance threshold; and
designating the identified largest candidate separation distance as the separation distance to be employed in capturing the model images of the object.
-
-
58. The computer-readable storage medium of claim 51, wherein the program module for computing a CH for each model image, comprises sub-modules for:
-
determining said prescribed pixel characteristic exhibited by each pixel in the model image;
dividing the overall gamut of said prescribed pixel characteristic into a series of pixel characteristic ranges;
respectively quantizing the prescribed pixel characteristic of each pixel in the model image by assigning the pixel to the pixel characteristic range into which the pixel'"'"'s prescribed characteristic belongs;
identifying every possible unique, non-ordered pair of pixels in the model image;
respectively quantizing the distance separating the two pixels of each identified pixel pair of the model image by assigning the pixel pair to a one of a series of prescribed distance ranges to which its separation distance belongs, wherein said series of prescribed distance ranges is established by selecting a maximum separation distance of interest and dividing it into a number of smaller distance ranges;
categorizing each pixel pair by the assigned pixel characteristic range of each of its respective pixels and the distance range assigned to the pair, wherein the resulting categories are hereinafter referred to as pixel characteristic mix/distance categories; and
establishing a count of the number of pixel pairs belonging to the same pixel characteristic mix/distance category.
-
-
59. The computer-readable storage medium of claim 58, wherein the sub-module for dividing the overall gamut of said prescribed pixel characteristic into a series of pixel characteristic ranges, comprises a sub-module for dividing the overall gamut into a series of equally-sized pixel characteristic ranges.
-
60. The computer-readable storage medium of claim 58, wherein the series of distance ranges comprises equally-sized distance ranges.
-
61. The computer-readable storage medium of claim 58, wherein the prescribed pixel characteristic is the pixel color.
-
62. The computer-readable storage medium of claim 51, wherein the program module for generating the plurality of search windows, comprises sub-modules for:
-
dividing the entire search image into a series of regions having a prescribed size and shape; and
designating each region as a separate search window.
-
-
63. The computer-readable storage medium of claim 62, wherein the prescribed shape of each region is rectangular, thereby forming rectangular search windows.
-
64. The computer-readable storage medium of claim 62, wherein each region is of equal size, thereby forming equally-sized search windows.
-
65. The computer-readable storage medium of claim 62, wherein each region of the search image overlaps all adjacent regions.
-
66. The computer-readable storage medium of claim 58, wherein the program module for computing the CH for each search window, comprises sub-modules for:
-
respectively quantizing the prescribed pixel characteristic of those pixels of the search window having a prescribed pixel characteristic falling within one of the pixel characteristic ranges by assigning the pixel to the pixel characteristic range into which the pixel'"'"'s prescribed characteristic belongs;
identifying every possible unique, non-ordered pair of pixels in the search window;
respectively quantizing the distance separating the two pixels of those identified pixel pairs of the search window having separation distances that fall within one of the distance ranges by assigning the pixel pair to the distance range to which its separation distance belongs;
categorizing each pixel pair having quantized pixel characteristics and distance by the assigned pixel characteristic range of each of its respective pixels and the distance range assigned to the pair; and
establishing a count of the number of categorized pixel pairs having the same pixel characteristic mix/distance category.
-
-
67. The computer-readable storage medium of claim 66, wherein the sub-module for assessing the degree of similarity between each model image CH and each of the search window CHs comprises, for each model image and search window assessed, sub-modules for:
-
comparing the count for each pixel characteristic mix/distance category of the model image to the count for the corresponding pixel characteristic mix/distance category of the search window;
identify the smaller of the two counts in each corresponding category; and
add the identified smaller count from each corresponding category together to produce a similarity value.
-
-
68. The computer-readable storage medium of claim 67, wherein the program module for designating a search window as containing the object being sought, comprises a sub-module for designating a search window as potentially containing the object being sought if the similarity value computed for the search window CH and one of the model image CHs exceeds the prescribed search threshold.
-
69. The computer-readable storage medium of claim 68, wherein the program module for designating a search window as containing the object being sought, further comprises a sub-module for designating each search window associated with a search window CH having a degree of similarity to one of the model image CHs which exceeds the prescribed search threshold as containing the object being sought, whenever it is anticipated that there will be more than one of the sought after objects in the search image.
-
70. The computer-readable storage medium of claim 68, wherein the program module for designating a search window as containing the object being sought, comprises the acts of:
-
determining which of the search windows associated with a search window CH having a degree of similarity to one of the model image CHs that exceeds the prescribed search threshold has the largest computed similarity value; and
designating only said search window determined to be associated with the largest similarity value as containing the object being sought.
-
-
71. The computer-readable storage medium of claim 51, further comprising, for each search window designated as containing the object being sought, a program module for refining the location of the search window in the search image, said program module for refining comprising sub-modules for:
-
(a) naming the search window designated as containing the object being sought the current primary search window;
(b) generating additional search windows having the same shape and size as the current primary search window from portions of the search image which are translated in comparison to the portion of the search image associated with the primary search window;
(c) computing a search window CH for each of the additional search windows;
(d) assessing the degree of similarity between each additional search window CH and the model image CH associated with the primary search window;
(e) determining whether any of the additional search windows have a higher degree of similarity to the model image CH associated with the primary search window than the primary search window itself;
(f) whenever none of the additional search windows has a higher degree of similarity to the model image CH associated with the primary search window than the primary search window itself, declaring the current primary search window as representing the exact location n the search image of the object being sought;
(g) whenever one or more of the additional search windows has a higher degree of similarity to the model image CH associated with the currently named primary search window than that primary search window itself, naming the additional search window having the highest degree of similarity to the model image CH associated with the previously named primary search window as the current primary search window in place of the previously named primary search window; and
(h) repeating acts (b) through (g) for each newly named current primary search window.
-
-
72. The computer-readable storage medium of claim 71, wherein the sub-module for generating additional search windows comprises a sub-module for using portions of the search image translated in as many of the following directions as possible:
- (i) one pixel row up, (ii) one pixel row down;
(iii) one pixel column to the right; and
(iv) one pixel column to the left.
- (i) one pixel row up, (ii) one pixel row down;
-
73. The computer-readable storage medium of claim 67, wherein the scale of the search image is different from that of the model image, and wherein the system further comprises a program module for:
-
performing, prior to the act of quantizing the separation distances of the pixel pairs, the act of multiplying the distance ranges computed for the model image by a factor representing the ratio of the search image scale to the model image scale; and
whereinthe act of comparing the count for each pixel characteristic mix/distance category of the model image to the count for the corresponding pixel characteristic mix/distance category of the search window comprises comparing the count for each pixel characteristic mix/distance category of the model image to the count for the pixel characteristic mix/distance category of the search window associated with the same mix of pixel characteristic ranges but with a distance range corresponding the distance range of the model image multiplied by the factor representing the ratio of the search image scale to the model image scale.
-
Specification