Pattern classification methods in navigation and object recognition

This thesis is concerned with pattern classification problems in vision-guided robot navigation and in model-based object recognition. In each of these domains, a variety of pattern classification problems arises, and because the domains are so different, different methods are needed to solve these problems.; Pattern classification is the basis for most methods of model-based object recognition. Typically, point-like features extracted from images are used; we show that classical point-pattern matching methods can be extended to allow both point-like and line-like features. In this connection, we employ a method of matching based on a quadratic algorithm called "relaxation," using a simple, linear evidence combination scheme. It has been suggested that a more sophisticated scheme, using the evidence combination calculus of Dempster and Shafer, could be employed which would allow integration of belief and uncertainty from disparate sources. We illustrate this possibility by demonstrating how the Dempster-Shafer calculus can be used to combine evidence from point feature and line feature comparisons.; Patterns of features can also be used for navigation. A navigating agent can classify its environment on the basis of statistical properties of feature populations. We address three related examples of this type of classification. We first show that a robotic agent can improve the efficiency with which it performs navigational tasks in city street networks by classifying the "randomness" of the network--that is, the variability of the distances between street intersections. We then examine the efficiency with which a robotic agent can classify the terrain across which it is navigating as either "rugged" or "smooth," depending on the degree to which the terrain elevation varies from point to point. Finally, we show how a novel "velocity histogramming" technique can be used to classify the environment's height distribution when the agent is an aerial observer looking down at the ground.