On three-dimensional object recognition and pose determination: An abstraction-based approach.

Abstract

This thesis advances an abstraction-based paradigm which makes explicit the process of imposing assumptions on data. The units of abstraction are models whose levels of abstraction are determined by the degree of assumption necessary for their application. A general to specific refinement process provides a mechanism to proceed gracefully through the abstraction hierarchy. The task of object recognition and pose determination becomes one of making stronger and stronger assumptions about the data. These assumptions yield model hypotheses which may then be applied and tested. This process of assumption and abstraction furnishes a path between symbolic descriptors of objects in the scene to their numeric specification. Throughout the process, abstractions are made to better interpret the original data to which the hypothesized models are fitted/computed. The strategy is thus data-bound. This strategy was applied to the recognition and pose determination of objects comprising cylindrical and planar surfaces in dense range data. A method of computing reliable Gaussian and mean curvature sign-map descriptors from the polynomial approximations of surfaces was demonstrated. Such descriptors which are invariant under perspective variation are suitable for hypothesis generation. A means for determining the pose of constructed geometric forms whose algebraic surface descriptions are non-linear in terms of their orienting parameters was developed. This was done by means of linear functions which are capable of approximating non-linear forms and determining their parameters. It was shown that biquadratic surfaces are suitable companion-linear forms for cylinder approximation and parameter estimation. The estimates provided the initial parametric approximations necessary for a non-linear regression stage to fine tune the estimates by fitting the actual non-linear form to the data. A hypothesis-based split-merge algorithm for extraction and pose determination of cylinders and planes which merge smoothly into other surfaces was developed. It was shown that all split-merge algorithms are hypothesis-based. A finite-state algorithm for the extraction of the boundaries of run-length regions was developed. The computation takes advantage of the run list topology and boundary direction constraints implicit in the run-length encoding.