Image analysis – Pattern recognition – Template matching
Reexamination Certificate
2000-04-15
2004-09-07
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Pattern recognition
Template matching
C382S170000, C382S172000, C382S218000, C340S297000, C340S304000, C340S507000
Reexamination Certificate
active
06788818
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates to a system and method for computing the probability of false alarms when using histogram matching to find objects in images.
2. Background Art
Using histograms for finding objects in images is attractive because histograms are relatively insensitive to an object's pose and scale, background clutter, and partial occlusion. However, this insensitivity is also prone to produce false matches with regions of the background that happen to match the object's histogram well enough, resulting in an algorithm that “finds” an object in an image even when it is not really there. These false alarms can be caused by using too few histogram bins, a subimage for matching so that is too large, or a matching threshold that is too low. Therefore, it is important to be able to quantify the false alarm probability for histogram matching so that intelligent tradeoffs can be made between the aforementioned parameters and the false alarm rate. To date prior histogram matching systems have not had this capability.
It is noted that in the remainder of the specification, the description refers to various individual publications identified by a numeric designator contained within a pair of brackets. For example, such a reference may be identified by reciting, “reference [1]” or simply “[1]”. A listing of the publications corresponding to each designator can be found at the end of the Detailed Description section.
SUMMARY
The present invention overcomes the aforementioned limitations in prior histogram matching systems by a system and method that computes the probability of histogram matching false alarms for different settings of a histogram matching algorithm's parameters. This allows the algorithm's designer to clearly see the tradeoffs and adjust the parameters to produce the optimum capability with the lowest possible false alarm rate. In one embodiment of the present invention, the false alarm rate of histogram matching is exactly computed by listing all the histograms possible as a function of the number of bins and counts, determining those that could cause a false alarm, and summing their probabilities. This exact method is particularly useful because it applies to any method used for comparing histograms. In another embodiment of the system and method according to the present invention, the summed multinomial distribution is approximated by a multivariate normal distribution that is numerically integrated to provide an efficient approximation of the false alarm probability.
The fundamental component of computing a false alarm probability for histogram matching is computing the probability that clutter in a background image will produce a histogram that matches sufficiently well with a model histogram. As will be discussed below, this can be done if an assumption is made about the probability distribution of pixels (or, more generally features) in the background. In particular, it is assumed that the background pixels are independent and identically distributed (iid). Given this assumption, the probability of occurrence of any histogram is given by a multinomial distribution. The system and method according to the present invention provides an exact calculation of false alarm probability for images that are iid, and provides an approximate calculation for image features that are approximately iid.
A histogram may be represented as a vector H=(h
1
, h
2
, . . . , h
m
). This histogram has m different bins, with h
i
being a non-negative integer telling how many counts are in bin i. The bins of the histogram usually represent a set of ranges of pixel values of gray level or color, but they could also be other quantized features. The procedure for computing a histogram is to first quantize the original image into m different values and then histogram this quantized image.
The process of recognizing an object with a histogram starts with a model of the object. A prototype histogram H
p
=(h
p,1
,h
p,2
, . . . , h
m
) is computed from the model image of the object. A test histogram H
t
=(h
t,1
, h
t,2
, . . . , h
t,m
) is computed from an image or subimage that may or may not contain the object. This test histogram may come from a region of the image that is larger, smaller, or the same size as the image used to compute the model histogram. These two histograms are tested for similarity in some way, and if they are similar enough, then the object is declared found in the test image. It is possible to use test images that are the same size as the model images, and therefore only one comparison per image is needed. Or it is possible to scan through the image, extracting several subimages and comparing each of the subimages' histograms to the model histogram. The system and method according to the present invention seeks to compute the probability for matching one of these subimages when that subimage does not represent the object being sought.
There have been several histogram similarity measures proposed. A simple one is the histogram intersection. The intersection tells how many counts in the model histogram the test histogram accounts for. If the intersection exceeds a certain threshold then the histograms are considered similar enough to declare the object found in the image. A convenient threshold is that the test histogram should account for some large fraction of the counts in the model histogram. If the test histogram does account for a large fraction of the counts in the model histogram then the object will be declared found. A false alarm occurs when the intersection equals or exceeds the match threshold when the object does not really exist in the image or portion of the image under consideration. This image or subimage is referred to a background image because it does not contain the object of interest.
The procedure for approximating the false alarm probability is to list the histograms of those background images that cause a false alarm and sum their probabilities of occurrence In order to accomplish this task, it is possible to think of the set of all possible histograms that an image of a given size could produce. Some of these histograms can cause a false alarm. If the total number of possible histograms is small enough, they can all be listed in order to find which ones will cause a false alarm. The probabilities of occurrence of the histograms in this subset can be summed to yield the false alarm probability. For example, every possible histogram computed from an image with n pixels will have n total counts spread among m bins. Each bin will have a nonnegative number of the counts. Thus, for the simple case of a histogram with m=2, the number of possible histograms would be n+1. For example, if the number of pixels n=5, then the six possible histograms are (0,5), (1,4), (2,3), (4,1) and (5,0). For m=3 bins, there are
∑
n
h
1
=
0
∑
n
-
h
1
h
2
=
0
1
=
1
2
(
n
+
1
)
(
n
+
2
)
possible histograms. Note that the index variables are the histogram counts. For n=5, the 21 possible histograms are
(0,0,5)
(1,0,4)
(2,0,3)
(3,0,2)
(4,0,1)
(5,0,0)
(0,1,4)
(1,1,3)
(2,1,2)
(3,1,1)
(4,1,0)
(0,2,3)
(1,2,2)
(2,2,1)
(3,2,0)
(0,3,2)
(1,3,1)
(2,3,0)
(0,4,1)
(1,4,0)
(0,5,0)
In general, the number of distinct possible histograms with m bins and n counts, may be expressed by the equation:
N
(
m
,
n
)
=
1
(
m
-
1
)
l
∏
m
-
1
i
=
1
(
n
+
i
)
and the histograms themselves can be generated from all the index values (h
1
, h
2
, . . . , h
m
) taken on by running through the following nested sums:
∑
n
h
1
=
0
∑
n
-
h
1
h
2
=
0
∑
n
-
h
1
-
h
2
h
3
=
0
…
∑
n
-
h
1
-
h
2
-
…
-
h
m
-
2
h
m
-
1
=
0
with
h
m
=
n
-
h
1
-
h
2
-
…
-
h
m
-
1
.
The paragraphs above gave a technique for listing all possible histograms with m bins and n counts. Next the probability of occurrence of a background histogram (h
1
Chang Peng
Krumm John
Kassa Yosef
Lyon Richard T.
Lyon & Harr LLP
Mehta Bhavesh M.
LandOfFree
System and process for optimizing false alarm probability... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and process for optimizing false alarm probability..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and process for optimizing false alarm probability... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3260805