Bounds on shape recognition performance

The localization and the recognition tasks are analyzed here relying on a probabilistic model, and independently of the recognition method used. Rigorous upper and lower bounds on the probability that a set of measurements is sufficient to localize an object within a certain precision, are derived. The bounds quantify the difficulty of the localization task regarding many of its aspects, including the number of measurements, the uncertainty in their position, the information they reveal, and the “ability of the objects to confuse the recognizer”. Similar results are obtained for the recognition task. The asymptotic difficulty of recognition/localization tasks is characterized by a single parameter, thus making it possible to compare between different tasks. The bounds provide a theoretical benchmark to which experimentally measured performance of localization/recognition methods can be compared