Applying VC-Dimension Analysis to 3D Object Recognition from Perspective Projections

Michael Lindenbaum, Shai Ben-David

We analyze the amount of information needed to carry out model-based recognition tasks, in the context of a probabilistic data collection model, and independently of the recognition method employed. We consider the very rich class of semi-algebraic 3D objects, and derive an upper bound on the number of data features that (provably) suffice for localizing the object with some pre-specified precision. Our bound is based on analysing the combinatorial complexity of the hypotheses class that one has to choose from, and quantifying it using a VC-dimension parameter. Once this parameter is found, the bounds are obtained by drawing relations between recognition and learning, and using well-known results from computational learning theory. It turns out that this bounds grow logarithmically in the algebraic complexity of the objects.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.