Quantifying the reliability of feature-based object recognition

We propose a technique for predicting the number of features that should be extracted from an image to guarantee reliable recognition in various feature-based recognition tasks. Our technique relies on the tools from learning theory, namely, the PAC learning framework and VC-dimension analysis. We derive the upper bounds on the required number of feature measurements for recognition tasks over the affine transformation space. These derivations can be readily applied to less general transformations. According to our predictions, more feature measurements are required for successful recognition when the objects involved are similar and when the hypothesized objects are complex. We present experimental results that qualitatively confirm these predictions