System and process for optimizing false alarm probability for histogram matching

• US 6,788,818 B1
• Filed: 04/15/2000
• Issued: 09/07/2004
• Est. Priority Date: 04/15/2000
• 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): Mehta, Bhavesh M.
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/549,077
• Time in Patent Office: 1,606 Days
• Field of Search: 382/159, 382/160, 382/170, 382/171, 382/172, 382/190, 382/191, 382/194, 382/206, 382/207, 382/209, 382/217, 382/218, 382/219, 382/220, 382/224, 382/278, 382/282, 382/303, 348/179, 348/180, 348/181, 348/185, 702/2, 702/3, 702/19, 702/32, 340/506, 340/507, 340/292, 340/297, 340/304
• US Class Current: 382/209
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G06V 10/56 relating to colour

Abstract

A system and process that computes the probability of histogram matching false alarms for different settings of a histogram matching algorithm'"'"'s parameters is presented. This allows the parameters to be adjusted to produce the optimum object finding capability with the lowest possible false alarm rate. Generally, a prototype histogram is generated from a model of an item being sought in an environment. The set of all possible test histograms that can be formed from the environment given a prescribed number of bins and a maximum count for the bins is then determined. Once this is accomplished a subset of test histograms from the set of all possible test histograms which will cause a false alarm is found. Then the probability of occurrence of each individual test histogram that will cause a false alarm in the subset is determined and summed to establish the overall false alarm probability.

Claims

1. A process for determining the overall false alarm probability when using histogram matching comprising the process actions of:

generating a prototype histogram from a model of an item being sought in an environment;

determining the set of all possible test histograms that can be formed from the environment given a prescribed number of bins and a maximum count for the bins;

determining the subset of test histograms from said set of all possible test histograms, which will cause a false alarm, said false alarm occurring when a histogram formed from the environment matches the prototype histogram when that histogram does not actually represent the model of the item being sought;

determining the probability of occurrence of each individual test histogram that will cause a false alarm in said subset; and

summing the individual false alarm probabilities of occurrence of all histograms in said subset of test histograms which will cause a false alarm to establish the overall false alarm probability.

2. The process of claim 1 wherein the process action of determining the set of all possible histograms, comprises the process actions of:

determining the number of all possible histograms; and

listing all the possible histograms.

3. The process of claim 2 wherein the process action of determining the number of all possible histograms further comprises the process actions of:

generating a first term by multiplying together a set of numbers derived by respectively adding an index value varying from 1 to a value equal to the number of bins minus 1, to the maximum count;

generating a second term by taking the inverse of the factorial of the number of bins minus 1; and

multiplying the first term by the second term to determine the number of all of the possible histograms.

4. The process of claim 2 wherein the process action of listing all the possible histograms comprises a process action of generating a list of all the possible combinations of the counts in each bin.

5. The process of claim 1, wherein the process action of determining the subset of said set of all possible test histograms that will cause a false alarm, comprises an action of determining the similarity between all test histograms and the prototype histogram.

6. The process of claim 5 wherein the process action of determining the similarity further comprises the actions of:

determining how many counts in the prototype histogram the test histogram accounts for; and

if the counts in the prototype histogram that the test histogram accounts for exceeds a prescribed threshold then the prototype histogram and the test histogram are considered similar enough to declare said item being sought in said environment to be found.

7. The process of claim 6 wherein the prescribed threshold is exceeded when said test histogram accounts for a substantial fraction of the counts in the prototype histogram.

8. The process of claim 7 wherein a false alarm occurs when the prescribed threshold is exceeded and the item being sought does not really exist in said test histogram.

9. The process of claim 1, wherein the environment is made up of elements that are independent from each other and identically distributed.

10. The process of claim 9 wherein the process action of determining the probability of occurrence of each individual test histogram that will cause a false alarm comprises the process actions of:

approximating the probability of occurrence of each histogram in the environment given the prescribed number of bins and a maximum count for the bins using a multinomial distribution analysis; and

assigning the probability of occurrence determined for each histogram in the environment as the probability of occurrence of each of the histograms that were determined to cause a false alarm.

11. The process of claim 9 wherein the process action of determining the probability of occurrence of each individual test histogram further comprises:

approximating the probability of occurrence of each histogram in the environment given the prescribed number of bins and a maximum count for the bins by integrating a multivariate normal; and

assigning the probability of occurrence determined for each histogram in the environment as the probability of occurrence of each of the histograms that were determined to cause a false alarm.

12. The process of claim 1 further comprising a process action of adjusting the number of bins and maximum count parameters to create the test histograms to optimize the overall false alarm probability.

13. A system for optimizing the overall false alarm probability when using histogram matching to recognize an object in an image of a scene comprising:

at least one general purpose computing device; and

a computer program comprising program modules executable by the at least one computing device, wherein the at least one computing device is directed by the program modules of the computer program to,

compute the false alarm rate for a given set of parameters, wherein said computation comprises,

generating a prototype histogram from a model image depicting an object being sought in an image,

determining the set of all possible test histograms that can be formed from a background image of the scene given a prescribed number of bins and a maximum pixel count for the bins,

determining the subset, of test histograms from said set of all possible test histograms, which will cause a false alarm, said false alarm occurring when a histogram formed from the background image matches the prototype histogram when that histogram does not actually represent the object being sought,

determining the probability of occurrence of each individual test histogram that will cause a false alarm in said subset, and

summing the individual false alarm probabilities of occurrence of all histograms in said subset of test histograms which will cause a false alarm to establish the overall false alarm probability; and

adjust the parameters to bring the false alarm rate down.

14. The system of claim 13 wherein the sub-module for determining the set of all possible histograms that can be formed from the background image of the scene, comprises sub-modules for:

determining the number of all possible histograms that can be formed from the background image of the scene; and

listing all the possible histograms that can be formed from the background image of the scene that will cause a false alarm.

15. The system of claim 14 wherein the sub-module for determining the number of all possible histograms that can be formed from the background image of the scene further comprises sub-modules for:

generating a first term by multiplying together a set of numbers derived by respectively adding an index value varying from 1 to a value equal to the number of bins minus 1, to the maximum pixel count;

generating a second term by taking the inverse of the factorial of the number of bins minus 1; and

multiplying the first term by the second term to determine all of the possible histograms.

16. The system of claim 14 wherein the sub-module for listing all the possible histograms that can be formed from the background image of the scene further comprises a sub-module for generating a list of all the possible combinations of the counts in each bin.

17. The system of claim 13, wherein the sub-module for determining the subset of said set of all possible test histograms that will cause a false alarm, further comprises a sub-module for determining the similarity between all test histograms and the prototype histogram.

18. The system of claim 17 wherein the sub-module for determining similarity further comprises sub-modules for:

determining how many pixel counts in the prototype histogram the test histogram accounts for via an intersection analysis; and

if the pixel counts in the prototype histogram that the test histogram accounts for exceeds a prescribed threshold then the prototype histogram and the test histogram are considered similar enough to declare the object being sought in said image to be found.

19. The system of claim 18 wherein the prescribed threshold is exceeded when said test histogram accounts for a substantial fraction of the counts in the prototype histogram.

20. The system of claim 18 wherein a false alarm occurs when the prescribed threshold is exceeded and the item being sought does not really exist in said test histogram.

21. The system of claim 13, wherein the image is made up of pixels that are independent from each other and identically distributed.

22. The system of claim 21 wherein the sub-module for determining the probability of occurrence of each individual test histogram that will cause a false alarm comprises sub-modules for:

determining the probability of occurrence of each histogram in the environment given the prescribed number of bins and a maximum pixel count for the bins using a multinomial distribution analysis; and

assigning the probability of occurrence determined for each histogram in the image as the probability of occurrence of each of the histograms that were determined to cause a false alarm.

23. The system of claim 21 wherein the sub-module for determining the probability of occurrence of each individual test histogram further comprises sub-modules for:

determining the probability of occurrence of each histogram in the environment given the prescribed number of bins and a maximum pixel count for the bins by integrating a multivariate normal; and

assigning the probability of occurrence determined for each histogram in the image as the probability of occurrence of each of the histograms that were determined to cause a false alarm.

24. The system of claim 13 further comprising a sub-module for:

adjusting the number of bins and maximum pixel count parameters to create the test histograms to optimize the overall false alarm probability.

25. A computer-readable memory for optimizing the overall false alarm probability when using histogram matching to recognize an object in an image of a scene comprising:

a computer-readable storage medium; and

a computer program comprising program modules stored in the storage medium, wherein the storage medium is so configured by the computer that it causes a computing device to,

distort the pixels of a model image of the scene which contains the object being sought to approximate an image exhibiting substantially independent and identically distributed image,

extract a portion of the distorted model image representing the object to create a distorted model image of the object and a distorted background image of the scene without the object,

generate a prototype histogram from the distorted model image of the object given a prescribed number of bins and a maximum count for the bins,

determine the set of all possible test histograms that can be formed from the distorted background image using the prescribed number of bins and the maximum count for the bins,

determine the subset of test histograms from said set of all possible test histograms which will cause a false alarm, said false alarm occurring when a histogram formed from the distorted background image matches the prototype histogram when that histogram does not actually represent the object,

determine the probability of occurrence of each individual test histogram that will cause a false alarm in said subset, and

sum the individual false alarm probabilities of occurrence of all histograms in said subset of test histograms which will cause a false alarm to establish the overall false alarm probability.

26. The computer-readable memory of claim 25 wherein the program module for distort the pixels of a model image of the scene comprises the sub-modules for:

extracting overlapping windows of a prescribed size from the model image of the scene in a right-to-left, top-to-bottom pattern starting at the upper-left corner of the model image; and

for each extracted window,

sorting the pixel values of the pixels of the window into every possible combination thereof to produce a set of ranking orders,

arbitrarily assigning each ranking order to one of a prescribed number of groups,

assigning a unique identifier value to each group,

identifying which group contains the ranking order matching that of the original extracted window in a right-to-left, top-to-bottom pattern, and

assigning the identifier value associated with the identified group containing the ranking order matching that of the original extracted window to the pixel location in the model image corresponding to the upper-left pixel location of the extracted window.

27. The computer-readable memory of claim 26, wherein the prescribed window size is 2 by 2 pixels and the prescribed number of groups is four, thereby producing a four-value ranked transform version of the model image.