A consensus approach to primitive extraction

This thesis applies the consensus paradigm to an important problem in model-based vision, that of primitive extraction. Primitive extraction is the process of finding geometric primitives in geometric data. Such data are obtained directly by active sensors such as laser rangefinders, by processes that operate on passive sensor data to create depth information such as stereo vision, or by simple edge detection and thresholding of intensity images. A geometric primitive is a curve or surface which can be described by an implicit function. We show that the best solution to this problem is at the global optimum of a cost function which often has very many local optima.;This global optimum represents the best consensus in the data with regard to the extraction problem. The consensus paradigm attempts to find this global optimum by randomly choosing small subsets of the data and evaluating the cost function for each subset. We apply the consensus paradigm to this problem by randomly sampling minimal subsets. This is a simple and general way of finding the best consensus. For primitive extraction a minimal subset is the smallest number of points necessary to define a geometric primitive. The issues of how to choose the appropriate cost function, how to decide on the number of random samples, and how to convert between a minimal subset and the parameter vector that defines the primitive are explored in detail.;While effective, the consensus approach using random sampling often requires a large number of random samples, and therefore a large number of cost function evaluations. We address this problem by combining the consensus paradigm with a genetic algorithm that uses the minimal subset representation. A genetic algorithm is an optimization method based on the evolutionary metaphor. It has been successfully applied to difficult optimization problems, where the cost function is noisy, multi-dimensional, and has many local minima. In our applications the genetic algorithm is able to use local geometric information to produce a global solution in a way that usually avoids the problem of premature commitment. The resulting method often requires far fewer cost function evaluations than the random sampling approach. Some ways of implementing these algorithms on different parallel architectures are described.