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

Abstract

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. Introduction We present here a quantitative analysis of the amount of information required for Model-based object recognition. Taking a statistical approach, we ...