On the Verification of Hypthesized Matches in Model-Based Recognition

Abstract

Model-based recognition methods often use ad hoc techniques to decide if a match of data to a model is correct. Generally an empirically determined threshold is placed on the fraction of model features that must be matched. We instead rigorously derive conditions under which to accept a match. We obtain an expression relating the probability of a match occurring at random to the fraction of model features accounted for by the match, as a function of the number of model features, the number of image features, and a bound on the degree of sensor noise. Our analysis implies that a proper matching threshold must vary with the number of model and data features, and thus should be set as a function of a particular matching problem rather than using a predetermined value. We analyze some existing recognition systems and find that our method predicts thresholds similar those determined empirically, supporting the technique's validity.