Recognition of 3 - D objects by forward checking constrained tree search

Abstract

In this thesis, attempts to recognize 3-D objects from range images are described. Objects are represented by surface patches obtained by segmenting image at depth or orientation discontinuity. Given model objects and a scene object, recognition process is defined as the process to find the best matching pairs between model surface patches (MSP``s) and scene surface patches (SSP``s). The best matching pairs are usually searched by sequential constrained tree search (SCTS) method. It is known to be effective for recognizing an isolated object, but less effective for object occluded by themselves and other objects. It is because many SSP``s are not shown from current model object or seriously deformed by occlusion. We observed that obtaining partial matching pairs may drastically reduce the number of candidate MSP``s matchable to unexplored SSP``s. It is because objects we are dealing are all rigid. If the partial matching pair is a part of a real solution path, a few MSP``s becomes candidates of unexplored SSP``s (As the depth is deeper, the number of candidates becomes one). Otherwise, i.e., if the partial matching pair is not a part of a real solution path, no candidate is available for the SSP``s. To utilize these observation, we augment a forward checking mechanism to this SCTS. The forward checking operation checks geometric constraints between current partial matching pairs and unexplored possible pairs and drastically reduces the number of candidates MSP``s matchable to unexplored SSP``s. Furthermore, the number of unexplored SSP``s having at least one candidate MSP``s after forward checking yields powerful search termination criteria. As an alternative to the sequential search method, we also applied the optimal search algorithm ($A^*$) using a cost function which consists of the geometrical discrepancy of current matching pairs and that of the remaining one. The latter is approximated by the number of alive unexplored SSP``s. To verify advantages of the...