Three-dimensional pose estimation is the process of estimating an object’s position and orientation relative to an observer. Real-time pose estimation algorithms based on visual information that are both accurate and robust to sensor noise and scene clutter are required to enable robotic systems to mimic a human’s ability to interact with its environment, whether that environment is static or dynamic. Of the three-dimensional pose estimation algorithms based on visual information that are available in the literature, the spin-image pose estimation algorithm has been demonstrated to be both accurate and robust. However, this algorithm’s computation time is significant, making it impractical for applications that require interaction with a dynamic environment. This thesis introduces three modifications that significantly increase the speed of the spin-image algorithm. These three modifications extend the use of the spin-image algorithm towards real-time applications.
The original spin-image algorithm can be segmented into six portions: spin-image generation, spin-image matching, geometric consistency filtering, spin-image grouping, pose determination, and pose verification. The modifications introduced here optimize the grouping portion, add a new filtering technique that is used prior to the matching portion, and introduce a parallel implementation of the matching portion utilizing a graphics processing unit (GPU).
Unlike the original algorithm, the modified grouping method proposed here does not guarantee that the highest accuracy pose estimate will be produced from the available data. However, it guarantees, in a probabilistic sense, that a grouping resulting in a pose error below a specified threshold will be generated with the least computations. The resulting performance improvement is a function of the object of interest. In practice, this method produces orders of magnitude of speed-up for various test objects.
The filtering technique introduced here uses a reduced-order representation of the spin-image to restrict the search space of possible solutions when performing spin-image matching by introducing the c*-image. Fuzzy clusters are identified in the database of reference spin-images that represent the object’s surface, and the resulting degrees of membership for a spin-image in the clusters comprise the c*-image. This reduced-order representation allows for quick discrimination between spin-images, and allows the database to be pruned considerably before the matching phase. Like the grouping operation, the resulting performance improvement depends upon the object of interest. For surface models considered in this thesis, the search space is reduced by 78% to 87%, resulting in algorithm speed-ups between 2.7x and 5.2x.
The suggested parallel implementation utilizing the GPU exploits the fact that the spin-image matching portion can be performed in parallel, regardless of the order of computation. This fact, and the massively parallel hardware architecture of the GPU, result in speed-ups in the matching portion of up to 515x and a total algorithm speed-up of 24x relative to a previous MATLAB implementation.