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_9: How an object appears in an image is determined in part by interactions with other objects in the scene. Occlusion is the most obvious from of interaction. Here we present a system which uses 3D CAD models in combination with optical and range data to recognize partially occluded objects. Recognition uses a hypothesize, perturb, render, and match cycle to arrive at a scene-optimized prediction of model appearance. This final scene-optimized prediction is based upon an iterative search algorithm converging to the optimal 3D pose of the object. During recognition, evidence of terrain occlusion in range imagery is mapped through the model into the optical imagery in order to explain the absence of model features. A similar process predicts the structure of occluding contours. Highly occluded military vehicles are successfully matched using this approach.
summary: The philosophy of the Render, Match and Refine (RMR) approach proposed by Stevens and Beveridge @cite_9 motivates our work. RMR explicitly models interaction between objects by rendering the scene and uses occlusion data to inform measurement of similarity between the rendered and observed scenes. It then uses a global optimization procedure to iteratively improve the rendered scene to match the observed one. PERCH, our proposed algorithm, operates on a similar philosophy but differs in several details. The explanation cost' we use to compare the rendered and observed scene is based purely on 3D sensor data, as opposed to the 2D edge-feature and per-pixel depth differences used in RMR that make it vulnerable to offset errors between the rendered and observed 2D scenes. Moreover, the explanation cost we propose can be decomposed over the objects in the scene, thereby obviating the need for exhaustive search over the joint object poses.