text: In many robotic domains such as flexible automated manufacturing or personal assistance, a fundamental perception task is that of identifying and localizing objects whose 3D models are known. Canonical approaches to this problem include discriminative methods that find correspondences between feature descriptors computed over the model and observed data. While these methods have been employed successfully, they can be unreliable when the feature descriptors fail to capture variations in observed data; a classic cause being occlusion. As a step towards deliberative reasoning, we present PERCH: PErception via SeaRCH, an algorithm that seeks to find the best explanation of the observed sensor data by hypothesizing possible scenes in a generative fashion. Our contributions are: i) formulating the multi-object recognition and localization task as an optimization problem over the space of hypothesized scenes, ii) exploiting structure in the optimization to cast it as a combinatorial search problem on what we call the Monotone Scene Generation Tree, and iii) leveraging parallelization and recent advances in multi-heuristic search in making combinatorial search tractable. We prove that our system can guaranteedly produce the best explanation of the scene under the chosen cost function, and validate our claims on real world RGB-D test data. Our experimental results show that we can identify and localize objects under heavy occlusion--cases where state-of-the-art methods struggle.
  @cite_28: Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering, 1963.
  @cite_0: 
  @cite_7: We describe model-based vision systems in terms of four components: models, prediction of image features, description of image features, and interpretation which relates image features to models. We describe details of modelling, prediction and interpretation in an implemented model-based vision system. Both generic object classes and specific objects are represented by volume models which are independent of viewpoint. We model complex real world object classes. Variations of size, structure and spatial relations within object classes can be modelled. New spatial reasoning techniques are described which are useful both for prediction within a vision system, and for planning within a manipulation system. We introduce new approaches to prediction and interpretation based on the propagation of symbolic constraints. Predictions are two pronged. First, prediction graphs provide a coarse filter for hypothesizing matches of objects to image feature. Second, they contain instructions on how to use measurements of image features to deduce three dimensional information about tentative object interpretations. Interpretation proceeds by merging local hypothesized matches, subject to consistent derived implications about the size, structure and spatial configuration of the hypothesized objects. Prediction, description and interpretation proceed concurrently from coarse object subpart and class interpretations of images, to fine distinctions among object subclasses and more precise three dimensional quantification of objects. We distinguish our implementations from the fundamental geometric operations required by our general image understanding scheme. We suggest directions for future research for improved algorithms and representations.
summary: While model-based recognition and pose estimation of objects has been an active area of research for decades in the computer vision community @cite_28 @cite_7 @cite_0 , the proliferation of low-cost depth sensors such as the Microsoft Kinect has introduced a plethora of opportunities and challenges. We describe approaches in vogue for object recognition and localization from 3D sensor data, their limitations, inspirations from early research in vision that motivate our work, and the potential role of contemporary learning-based systems.