|
|
|
Fast Object Recognition by Selectively Examining Hypotheses
Clark F. Olson Ph. D. Thesis, University of California at Berkeley, 1994. Download (2978 K) Several systems have been proposed to recognize three-dimensional objects in (two-dimensional) intensity images by computer. A problem that has plagued most object recognition systems for this problem is the low rate at which images are processed unless the problem is constrained, due to the vast number of hypothetical matches between sets of image features and sets of model features. Hypothetical poses can be determined from a small number of model features appearing in the image. The number of correct matches between these small sets of model features and image features (and thus correct hypotheses) is combinatorial in the number of model features appearing in the image. Since, ideally, only one of these correct hypotheses needs to be found to recognize the object, an exhaustive examination of all hypothetical matches is not necessary. I describe techniques to obtain fast object recognition through the selective examination of the possible hypotheses. First, I describe how the pose clustering method of object recognition can be decomposed into subproblems of much smaller size. In addition, I show that only a small fraction of these subproblems need to be examined to recognize objects with a negligible probability of introducing a false negative. This allows us to reduce the computational complexity of the algorithm, as well as reducing the amount of space necessary. I show how the clusters of poses that indicate a good hypothesis can be found quickly in a space efficient manner. A noise analysis and experiments on real images indicate that this system has good performance. Next, I describe a probabilistic indexing system to determine which of the initial hypothesized matches between three model points and three image points are most likely to be correct. This system takes advantage of the probabilistic peaking effect, which implies that if all viewing directions are equally likely, the distribution of angles and ratios of distances in the image will have a sharp peak at the model value. This effect can be used to select hypotheses to examine that are more likely to be correct than others. The probabilistic indexing system is used with noise criteria to obtain a speedup of two orders of magnitude in the alignment method. It is expected that these techniques will also result in a significant speedup when applied to pose clustering. The implementation of these ideas in a connectionist framework is discussed. While alignment and pose clustering methods can be implemented in this framework, the best approach for this case is to use election methods. Such methods allow much of the computation to be performed off-line, thus simplifying the processing elements required. Election methods use indexing to generate hypothesized matches between groups of points. Voting is then performed to determine which objects have the most support in the image. My analysis shows that model-based object recognition can be performed extremely quickly given a large number of simple processing elements. These techniques vastly improve the speed at which model-based object recognition algorithms can be performed. |
