Object recognition with co-occurrence histograms and false alarm probability analysis for choosing optimal object recognition process parameters

• US 6,477,272 B1
• Filed: 06/18/1999
• Issued: 11/05/2002
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chang, Peng, Krumm, John
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): LE, BRIAN Q
• Application Number:
  US09/336,274
• Time in Patent Office: 1,236 Days
• Field of Search: 382/165, 382/168, 382/170, 382/194, 382/217, 382/218, 382/224, 382/305
• US Class Current: 382/170
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching

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.

Claims

1. A computer-implemented process for determining optimal search parameters for use in an object recognition procedure designed to find an object in a search image, said 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, 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;

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; and

wherein,

said series of pixel characteristic ranges, said series of distance ranges, and the size of the search windows constitute search parameters which are optimized by ensuring these parameters are large enough to minimize the processing required to compute and assess the similarity of the model image and search window CHs, while at the same time producing an acceptable risk of a false designation that a search window potentially contains the object being sought.

2. The process of claim 1, wherein the act of optimizing the search parameters comprises the acts of:

modeling the probability that a random background region of the search image will be characterized by a particular model image CH;

deriving a numerical algorithm from said probability model that approximates the probability that a search window CH associated with the background region will match the model image CH, thereby constituting a false match, whenever a particular set of said search parameters are employed;

computing the probability of a false match for a plurality of different values of a first of said search parameters using the numerical algorithm, while keeping the values of a second and a third of said search parameters constant at a prescribed value;

determining the particular value of the first search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than a prescribed false alarm threshold; and

designating said particular value of the first search parameter as a potential optimal first search parameter.

3. The process of claim 2, wherein the act of optimizing the search parameters further comprises the acts of:

computing the probability of a false match for a plurality of different values of the second of said search parameters using the numerical algorithm, while using the particular value of the first search parameter designated as being the potential optimal first search parameter and keeping the value of the third of said search parameters constant at a prescribed value;

determining the particular value of the second search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

designating said particular value of the second search parameter as a potential optimal second search parameter.

4. The process of claim 3, wherein the act of optimizing the search parameters further comprises the acts of:

computing the probability of a false match for a plurality of different values of the third of said search parameters using the numerical algorithm, while employing the particular values of the first and second search parameters designated as being the potential optimal first search parameter and potential optimal second search parameter, respectively;

determining the particular value of the third search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

designating said particular value of the third search parameter as a potential optimal third search parameter.

5. The process of claim 4, further comprising the act of designating the potential optimal first, second and third search parameters as actual optimal parameters.

6. The process of claim 4, further comprising the acts of:

(a) re-computing the probability of a false match for a plurality of different values of the first of said search parameters using the numerical algorithm, while employing the particular values of the second and third search parameters designated as being the potential optimal second and third search parameters, respectively;

(b) re-determining the particular value of the first search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold;

(c) designating said re-determined value of the first search parameter as the current potential optimal third search parameter;

(d) re-computing the probability of a false match for a plurality of different values of the second of said search parameters using the numerical algorithm, while employing current values of the first and third search parameters designated as being the potential optimal first and third search parameters, respectively;

(e) re-determining the particular value of the second search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold;

(f) designating said re-determined value of the second search parameter as the current potential optimal third search parameter;

(g) re-computing the probability of a false match for a plurality of different values of the third of said search parameters using the numerical algorithm, while employing current values of the first and second search parameters designated as being the potential optimal first and second search parameters, respectively;

(h) re-determining the particular value of the third search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

(i) designating said re-determined value of the third search parameter as the current potential optimal third search parameter;

(j) repeating acts (a) through (i) until a change in the designated current potential optimal first, second and third search parameter values has not varied substantially from the immediately preceding designated values for these search parameters; and

(k) declaring the last designated values of the first, second and third search parameters as actual optimal first, second and third search parameters, respectively.

7. The process of claim 1, wherein the act of optimizing the search parameters comprises the acts of:

modeling the probability that a random background region of the search image will be characterized by a particular model image CH;

deriving a numerical algorithm from said probability model that approximates the probability that a search window CH associated with the background region will match the model image CH, thereby constituting a false match, whenever a particular set of said search parameters are employed;

computing the probability of a false rmatch for a substantial number of combinations of candidate search parameters using the numerical algorithm;

determining the particular combination of search parameters that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than a prescribed false alarm threshold; and

designating said particular combination of search parameters as an optimal set of search parameters.

8. The process of claim 1, wherein the prescribed pixel characteristic is the pixel color.

9. The process of claim 1, wherein the prescribed false alarm threshold is chosen to be as large as possible, while still providing an acceptable degree of risk of a false match.

10. A system for determining optimal search parameters for use in an object recognition procedure designed to find an object 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;

generate a plurality of search windows each comprising a portion of the search image;

compute 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 potentially containing the object being sought; and

wherein,

said series of pixel characteristic ranges, said series of distance ranges, and the size of the search windows constitute search parameters which are optimized by ensuring these parameters are large enough to minimize the processing required to compute arid assess the similarity of the model image and search window CHs, while at the same time producing an acceptable risk of a false designation that a search window potentially contains the object being sought.

11. The system of claim 10, wherein thea program module for optimizing the search parameters comprises sub-modules for:

modeling the probability that a random background region of the search image will be characterized by a particular model image CH;

deriving a numerical algorithm from said probability model that approximates the probability that a search window CH associated with the background region will match the model image CH, thereby constituting a false match, whenever a particular set of said search parameters are employed;

computing the probability of a false match for a plurality of different values of a first of said search parameters using the numerical algorithm, while keeping the values of a second and a third of said search parameters constant at a prescribed value;

determining the particular value of the first search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than a prescribed false alarm threshold; and

designating said particular value of the first search parameter as a potential optimal first search parameter.

12. The system of claim 11, wherein the program module for optimizing the search parameters further comprises sub-modules for:

computing the probability of a false match for a plurality of different values of the second of said search parameters using the numerical algorithm, while using the particular value of the first search parameter designated as being the potential optimal first search parameter and keeping the value of the third of said search parameters constant at a prescribed value;

determining the particular value of the second search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

designating said particular value of the second search parameter as a potential optimal second search parameter.

13. The system of claim 12, wherein the program module for optimizing the search parameters further comprises sub-modules for:

computing the probability of a false match for a plurality of different values of the third of said search parameters using the numerical algorithm, while employing the particular values of the first and second search parameters designated as being the potential optimal first search parameter and potential optimal second search parameter, respectively;

determining the particular value of the third search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

designating said particular value of the third search parameter as a potential optimal third search parameter.

14. The system of claim 13, further comprising a program module for designating the potential optimal first, second and third search parameters as actual optimal parameters.

15. The system of claim 13, further comprising program modules for:

(a) re-computing the probability of a false match for a plurality of different values of the first of said search parameters using the numerical algorithm, while employing the particular values of;

the second and third search parameters designated as being the potential optimal second and third search parameters, respectively;

(b) re-determining the particular value of the first search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold;

(c) designating said re-determined value of the first search parameter as the current potential optimal third search parameter;

(d) re-computing the probability of;

a false match for a plurality of different values of the second of said search parameters using the numerical algorithm, while employing current values of the first and third search parameters designated as being the potential optimal first and third search parameters, respectively;

(e) re-determining the particular value of the second search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold;

(f) designating said re-determined value of the second search parameter as the current potential optimal third search parameter;

(g) re-computing the probability of a false match for a plurality of different values of the third of said search parameters using the numerical algorithm, while employing current values of the first and second search parameters designated as being the potential optimal first and second search parameters, respectively;

(h) re-determining the particular value of the third search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

(i) designating said re-determined value of the third search parameter as the current potential optimal third search parameter;

(j) repeating acts (a) through (i) until a change in the designated current potential optimal first, second and third search parameter values has not varied substantially from the immediately preceding designated values for these search parameters; and

(k) declaring the last designated values of the first, second and third search parameters as actual optimal first, second and third search parameters, respectively.

16. The system of claim 10, wherein the program module for optimizing the search parameters comprises sub-modules for:

modeling the probability that a random background region of the search image will be characterized by a particular model image CH;

deriving a numerical algorithm from said probability model that approximates the probability that a search window CH associated with the background region will match the model image CH, thereby constituting a false match, whenever a particular set of said search parameters are employed;

computing the probability of a false match for a substantial number of combinations of candidate search parameters using the numerical algorithm;

determining the particular combination of search parameters that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than a prescribed false alarm threshold; and

designating said particular combination of search parameters as an optimal set of search parameters.

17. The system of claim 10, wherein the prescribed pixel characteristic is the pixel color.

18. The system of claim 10, wherein the prescribed false alarm threshold is chosen to be as large as possible, while still providing an acceptable degree of risk of a false match.

19. A computer-readable memory for determining optimal search parameters for use in an object recognition procedure designed to find an object 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;

generate a plurality of search windows each comprising a portion of the search image;

compute 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 potentially containing the object being sought; and

wherein,

said series of pixel characteristic ranges, said series of distance ranges, and the size of the search windows constitute search parameters which are optimized by ensuring these parameters are large enough to minimize the processing required to compute and assess the similarity of the model image and search window CHs, while at the same time producing an acceptable risk of a false designation that a search window potentially contains the object being sought.

20. The computer-readable memory of claim 19, wherein the program module for optimizing the search parameters comprises sub-modules for:

modeling the probability that a random background region of the search image will be characterized by a particular model image CH;

deriving a numerical algorithm from said probability model that approximates the probability that a search window CH associated with the background region will match the model image CH, thereby constituting a false match, whenever a particular set of said search parameters are employed;

computing the probability of a false match for a plurality of different values of a first of said search parameters using the numerical algorithm, while keeping the values of a second and a third of said'"'"'search parameters constant at a prescribed value;

determining the particular value of the first search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than a prescribed false alarm threshold; and

designating said particular value of the first search parameter as a potential optimal first search parameter.

21. The computer-readable memory of claim 20, wherein the program module for optimizing the search parameters further comprises sub-modules for:

computing the probability of a false match for a plurality of different values of the second of said search parameters using the numerical algorithm, while using the particular value of the first search parameter designated as being the potential optimal first search parameter and keeping the value of the third of said search parameters constant at a prescribed value;

determining the particular value of the second search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

designating said particular value of the second search parameter as a potential optimal second search parameter.

22. The computer-readable memory of claim 21, wherein the program module for optimizing the search parameters further comprises sub-modules for:

computing the probability of a false match for a plurality of different values of the third of said search parameters using the numerical algorithm, while employing the particular values of the first and second search parameters designated as being the potential optimal first search parameter and potential optimal second search parameter, respectively;

determining the particular value of the third search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

designating said particular value of the third search parameter as a potential optimal third search parameter.

23. The computer-readable memory of claim 22, further comprising a program module for designating the potential optimal first, second and third search parameters as actual optimal parameters.

24. The computer-readable memory of claim 22, further comprising program modules for:

(a) re-computing the probability of a false match for a plurality of different values of the first of said search parameters using the numerical algorithm, while employing the particular values of the second and third search parameters designated as being the potential optimal second and third search parameters, respectively;

(b) re-determining the particular value of the first search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold;

(c) designating said re-determined value of the first search parameter as the current potential optimal third search parameter;

(d) re-computing the probability of a false match for a plurality of different values of the second of said search pararmeters using the numerical algorithm, while employing current values of the first and third search parameters designated as being the potential optimal first and third search parameters, respectively;

(e) re-determining the particular value of the second search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold;

(f) designating said re-determined value of the second search parameter as the current potential optimal third search parameter;

(g) re-computing the probability of a false match for a plurality of different values of the third of said search parameters using the numerical algorithm, while employing current values of the first and second search parameters designated as being the potential optimal first and second search parameters, respectively;

(h) re-determining the particular value of the third search parameter that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than the prescribed false alarm threshold; and

(i) designating said re-determined value of the third search parameter as the current potential optimal third search parameter;

(j) repeating acts (a) through (i) until a change in the designated current potential optimal first, second and third search parameter values has not varied substantially from the immediately preceding designated values for these search parameters; and

(k) declaring the last designated values of the first, second and third search parameters as actual optimal first, second and third search parameters, respectively.

25. The computer-readable memory of claim 19, wherein the program module for optimizing the search parameters comprises sub-modules for:

modeling the probability that a random background region of the search image will be characterized by a particular model image CH;

deriving a numerical algorithm from said probability model that approximates the probability that a search window CH associated with the background region will match the model image CH, thereby constituting a false match, whenever a particular set of said search parameters are employed;

computing the probability of a false match for a substantial number of combinations of candidate search parameters using the numerical algorithm;

determining the particular combination of search parameters that will result in the most efficient processing of the object recognition procedure while at the same time having a false match probability that is less than a prescribed false alarm threshold; and

designating said particular combination of search parameters as an optimal set of search parameters.

26. The computer-readable memory of claim 19, wherein the prescribed pixel characteristic is the pixel color.

27. The computer-readable memory of claim 19, wherein the prescribed false alarm threshold is chosen to be as large as possible, while still providing an acceptable degree of risk of a false match.