Robustness in primitive extraction and correspondence computation
Gerhard Roth, Martin D. Levine · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1992
Two related and important problems in the field of model-based computer vision are the extraction of predefined primitives from geometric data, and the computation of correspondences among such primitives. We show that both problems are equivalent to the optimization of a cost function, which often has very many local minima. One implication of this model is that a robust algorithm for these problems must find the global minimum of the associated cost function from among the local minima. The minimal subset principle states that a small subset of a set is often able to encode the characteristics of the entire set. For primitive extraction a minimal subset is the smallest number of points necessary to define a geometric primitive. Similarly, for correspondence computation a minimal subset is the smallest number of correspondences between geometric and model primitives necessary to define a pose (position and orientation) of the model. Randomly choosing such minimal subsets and evaluating them by using a cost function is a general and robust way to perform primitive extraction and correspondence computation. The main difficulty with this approach is that sometimes a large number of random samples (and therefore cost function evaluations) are necessary. We use a genetic algorithm to decrease the number of random samples significantly, and therefore to decrease the execution time. Some approaches to speeding up minimal subsets using algorithms on different parallel architectures are also described.