ON THE VERIFICATION OF HYPOTHESIZED MATCHES IN MODEL-BASED RECOGNITION

Model-based recognition methods generally use ad hoc techniques to decide whether or not a model of an object matches a given scene. The most common such technique is to set an empirically determined threshold on the fraction of model features that must be matched to data features. In this paper, we instead rigorously derive conditions under which to accept a match as correct. Our analysis is based on modeling the recognition process as a statistical occupancy problem. This model makes the assumption that pairings of object and data features can be characterized as a random process with a uniform distribution. We present a number of examples illustrating that real image data are well approximated by such a random process. Using a statistical occupancy model, we derive an expression for the probability that a randomly occurring match will account for a given fraction of the features of a particular object. This expression is a function of the number of model features, the number of data features, and bounds on the degree of sensor noise. It provides a means of setting a threshold such that the probability of a random match is very small. One implication of our analysis is that thresholds for recognition systems should be a function of the complexity of the image as well as the model. In contrast, current recognition methods generally associate a fixed threshold with each model.