Polynomial-Time Object Recognition in the Presence of Clutter, Occlusion, and Uncertainty

Abstract

We consider the problem of object recognition via local geometric feature matching in the presence of sensor uncertainty, occlusion, and clutter. We present a general formulation of the problem and a polynomial-time algorithm which guarantees finding all geometrically feasible interpretations of the data, modulo uncertainty, in terms of the model. This formulation applies naturally to problems involving both 2D and 3D objects. The primary contributions of this work are the presentation of a robust, provably correct, polynomial-time approach to this class of recognition problems and a demonstration of its practical application; and the development of a general framework for understanding the fundamental nature of the geometric feature matching problem. This framework provides insights for analyzing and improving previously proposed recognition approaches, and enables the development of new algorithms.