In a small computer science department without a graduate program, it is sometimes difficult to attract research students. This is particularly true for research in computer vision, since it is built upon a substantial body of knowledge, including considerable mathematics, that most undergraduates are not familiar with. My approach to encouraging students to take part in this research starts by introducing computation with images in early programming classes. Students become comfortable working with images in a structured framework, where they are not exposed to excessive underlying details. The students that become interested in working with images can take my computer vision class. This course is taught in a way that students can understand the material without having a deep background in mathematics. Students that are successful in this class are ready for (and encouraged to) work on undergraduate research projects and perform internships in computer vision research. While my strategy focuses on computer vision, similar approaches could be used for other research areas.

In order to perform localization and navigation over significant distances (up to a few kilometers), it is important to be able to accurately map the terrain to be traversed. Local methods, such as conventional stereo, do not scale well to large distances and prevent long-range planning. In this paper, we discuss wide-baseline stereo techniques for rovers. In wide-baseline stereo, the image pair is captured with the same camera, but at different positions of the rover. While the larger baseline allows improved accuracy for more distant terrain, stereo matching is more difficult for two reasons. First, odometry errors result in uncertain knowledge of the relative positions of the cameras when the images are captured. Second, the change in perspective makes stereo matching difficult, since image landmarks no longer has the same appearance in both images. We address these problems and show test results on real images.

Image-matching applications, such as tracking and stereo, commonly use the sum-of-squared-difference (SSD) measure to determine the best match. However, this measure is sensitive to outliers and is not robust to template variations. Alternative measures have also been proposed that are more robust to these issues. We improve upon these using a probabilistic formulation for image matching in terms of maximum-likelihood estimation that can be used for both edge template matching and gray-level image matching. This formulation generalizes previous edge-matching methods based on distance transforms. We apply the techniques to stereo matching and feature tracking. Uncertainty estimation techniques allow feature selection to be performed by choosing features that minimize the localization uncertainty.

Maximization of mutual information is a powerful method for registering images (and other data) captured with different sensors or under varying conditions, since the technique is robust to variations in the image formation process. On the other hand, the high level of robustness allows false positives when matching over a large search space and also makes it difficult to formulate an efficient search strategy for this case. We describe techniques to overcome these problems by aligning image entropies, which are robust to illumination variation and can be applied to multi-sensor registration. This results in a lower rate of false positives and a more efficient method to search an image for the matching position. The techniques are applied to real imagery and compared to methods based on mutual information and gradients to demonstrate their effectiveness.

In the exploration of the other planets of our solar system, images taken during a lander's descent to the surface of a planet provide a critical link between orbital images and surface images. The descent images not only allow us to locate the landing site in a global coordinate frame, but also provide progressively higher-resolution maps for mission planning. The paper addresses the generation of depth maps from the descent images. Our approach has two steps: motion refinement and depth recovery. During motion refinement, we use an initial motion estimate in order to avoid the intrinsic ambiguity in descending motions. The objective of the motion refinement step is to adjust the motion parameters such that the epipolar constraints are valid between adjacent frames. The depth recovery step correlates adjacent frames to match pixels for triangulation. Due to the descending motion, the conventional rectification process is replaced by a set of anti-aliasing image warpings corresponding to a set of virtual parallel planes. We demonstrate experimental results on synthetic and real descent images.

Robust navigation for mobile robots over long distances requires an accurate method for tracking the robot position in the environment. Techniques for position estimation by determining the camera ego-motion from monocular or stereo sequences have been previously described. However, long-distance navigation requires a very high level of robustness and a very low rate of error growth. In this paper, we describe a methodology for long-distance rover navigation that meets these goals using robust estimation. We show that a system based on only camera ego-motion estimates will accumulate errors with super-linear growth in the distance travelled, owing to increasing orientation errors. When an absolute orientation sensor is incorporated, the error growth can be reduced to a linear function of the distance travelled. We tested these techniques using both extensive simulation and hundreds of real rover images and achieved a low, linear rate of error growth.

In image matching applications such as tracking and stereo matching, it is common to use the sum-of-squared-differences (SSD) measure to determin the best match for an image template. However, this measure is sensitive to outliers and is not robust to template variations. We describe a robust measure and efficient search strategy for template matching with a binary or greyscale temolate using a maximum-likelihood formulation. In addition to subpixel localization and uncertainty estimation, these techniques allow optimal feature selection based on minimizing the localization uncertainty. We examine the use of these techniques for object recognition, stereo matching, feature selection and tracking.

Several methods for computing observer motion from monocular and stereo image sequences have been proposed. However, accurate positioning over long distances requires a higher level of robustness than previously achieved. This paper describes several mechanisms for improving robustness in the context of a maximum-likelihood stereo ego-motion method. We demonstrate that even a robust system will accumulate super-linear error in the distance traveled due to increasing orientation errors. However, when an absolute orientation sensor is incorporated, the growth is reduced to linear in the distance traveled, grows much more slowly in practice. Our experiments, including a trial with 210 stereo pairs, indicate that these techniques can achieve errors below 1% of the distance traveled. This method has been implemented to run on-board a prototype Mars rover.

Military test ranges containing unexploded ordnance due to live-fire testing and training exercises are a significant safety problem in many locations. Automated cleanup of such sites is a challenging goal. This paper describes algorithms to detect a type of ordnance in current usage using color imagery. The techniques are designed to run in real-time using off-the-shelf hardware for use on an unmanned ground vehicle. Our methodology is to quickly detect candidate locations using color and stereo information. Additional processing is then applied to the candidate locations in order to eliminate false alarms. This technique has been tested on a set of imagery from a live-fire test range with outstanding results.

We describe techniques to optimally select landmarks in order to perform mobile robot localization by matching terrain maps. The method is based upon a maximum-likelihood robot localization algorithm that efficiently searches the space of possible robot positions. We use a sensor error model to estimate the probability distribution of the terrain expected to be seen from the current robot position. The estimated distribution is compared to a previously generated map of the terrain and the optimal landmark is selected by minimizing the predicted uncertainty in the localization. This approach can be used to generate a sensor uncertainty field for use by the robot's planning component. Experiments indicate that landmark selection improves not only the localization uncertainty, but also the likelihood of success.

Robust navigation through rocky terrain by small mobile robots is important for maximizing science return from missions to Mars. We are addressing this problem at multiple levels through the development of intelligent sequencing, sensor constrained path planning, natural terrain visual localization, and real-time state estimation. Each of these techniques is described and their complementary aspects discussed. Experimental results are provided from implementation on our Mars rover prototype operating in realistic scenarios.

In edge and corner detection applications, it is typical to examine a single scale without knowing which scale is appropriate for each location in the image. However, many images contain a wide variation in the distance to the scene pixels and, thus, features of the same size can appear at greatly differing scales in the image. We present a method where the scale of the filtering and feature detection is varied locally according to the distance to the scene pixel, which we estimate through stereoscopy. The features that are detected are, thus, at the same scale in the world, rather than at the same scale in the image. This method has been implemented efficiently by filtering the image at a discrete set of scales and performing interpolation to estimate the response at the correct scale for each pixel. The application of this technique to an ordnance recognition problem has resulted in a considerable improvement in performance.

We describe probabilistic self-localization techniques for mobile robots that are based on the principle of maximum-likelihood estimation. The basic method is to compare a map generated at the current robot position with a previously generated map of the environment in order to probabilistically maximize the agreement between the maps. This method is able to operate in both indoor and outdoor environments using either discrete features or an occupancy grid to represent the world map. The map may be generated using any method to detect features in the robot's surroundings, including vision, sonar, and laser range-finder. We perform an efficient global search of the pose space that guarantees that the best position is found according to the probabilistic map agreement measure in a discretized pose space. In addition, subpixel localization and uncertainty estimation are performed by fitting the likelihood function with a parameterized surface. We describe the application of these techniques in several experiments.

We describe techniques for performing mobile robot localization using occupancy grids that allow subpixel localization and uncertainty estimation in the pixelized pose space. The techniques are based on a localization method where matching is performed between the visible landmarks at the current robot position and a previously generated map of the environment. A likelihood function over the space of possible robot positions is formulated as a function of the probability distribution for the map matching error. Subpixel localization and uncertainty estimation are performed by fitting the likelihood function with a parameterized surface. The performance of the method is analyzed using synthetic experiments and an example is given using the Rocky 7 Mars rover prototype.

View-based recognition methods, such as those using eigenspace techniques, have been successful for a number of recognition tasks. Such approaches, however, are somewhat limited in their ability to recognize objects that are partly hidden from view or occur against cluttered backgrounds. In order to address these limitations, we have developed a view matching technique based on an eigenspace approximation to the generalized Hausdorff measure. This method achieves compact storage and fast indexing that are the main advantages of eigenspace view matching techniques, while also being tolerant of partial occlusion and background clutter. The method applies to binary feature maps, such as intensity edges, rather than directly to intensity images.

It is typical in edge detection applications to examine a single scale or to consider some space of scales in the image without knowing which scale is appropriate for each location in the image. However, many images contain a wide variation in the distance to the scene points, and thus objects of the same size can appear at greatly differing scales in the image. We present a method where the scale of the smoothing and edge detection is varied locally according to the distance to the scene point, which we estimate through stereoscopy. The edges that are detected are thus at the same scale in the world, rather than at the same scale in the image. This method has been implemented efficiently by smoothing the image at a discrete set of scales and performing interpolation to estimate the response at the correct scale for each pixel. The application of this technique to an ordnance recognition problem has resulted in a considerable improvement in performance. 1 Introduction Image smoothing ...

Matching images based on a Hausdorff measure has become popular for computer vision applications. However, no probabilistic model has been used in these applications. This limits the formal treatment of several issues, such as feature uncertainties and prior knowledge. In this paper, we develop a probabilistic formulation of image matching in terms of maximum likelihood estimation that generalizes a version of Hausdorff matching. This formulation yields several benefits with respect to previous Hausdorff matching formulations. In addition, we show that the optimal model position in a discretized pose space can be located efficiently in this formation and we apply these techniques to a mobile robot self-localization problem.

This paper describes maximum likelihood estimation techniques for performing rover localization in natural terrain by matching range maps. An occupancy map of the local terrain is first generated using stereo vision. The position of the rover with respect to a previously generated occupancy map is then computed by comparing the maps using a probabilistic formulation of image matching techniques. Our motivation for this work is the desire for greater autonomy in Mars rovers. These techniques have been applied to data obtained from the Sojourner Mars rover and run on-board the Rocky 7 Mars rover prototype.

Least median of squares (LMS) regression is a robust method to fit equations to observed data (typically in a linear model). This paper describes an approximation algorithm for LMS regression. The algorithm generates a regression solution with median residual no more than twice the optimal median residual. Random sampling is used to provide a simple O(n log2 n) expected time algorithm in the two-dimensional case that is successful with high probability. This algorithm is also extended to arbitrary dimension d with O(nd − 1 log n) worst-case complexity for fixed d > 2.

This paper describes techniques to perform efficient and accurate target recognition in difficult domains. In order to accurately model small, irregularly shaped targets, the target objects and images are represented by their edge maps, with a local orientation associated with each edge pixel. Three dimensional objects are modeled by a set of two-dimensional (2-D) views of the object. Translation, rotation, and scaling of the views are allowed to approximate full three-dimensional (3-D) motion of the object. A version of the Hausdorff measure that incorporates both location and orientation information is used to determine which positions of each object model are reported as possible target locations. These positions are determined efficiently through the examination of a hierarchical cell decomposition of the transformation space. This allows large volumes of the space to be pruned quickly. Additional techniques are used to decrease the computation time required by the method when matching is performed against a catalog of object models. The probability that this measure will yield a false alarm and efficient methods for estimating this probability at run time are considered in detail. This information can be used to maintain a low false alarm rate or to rank competing hypotheses based on their likelihood of being a false alarm. Finally, results of the system recognizing objects in infrared and intensity images are given.

Feature indexing techniques are promising for object recognition since they can quickly reduce the set of possible matches for a set of image features. This work exploits another property of such techniques. They have inherently parallel structure and connectionist network formulations are easy to develop. Once indexing has been performed, a voting scheme such as geometric hashing can be used to generate object hypotheses in parallel. We describe a framework for the connectionist implementation of such indexing and recognition techniques. With sufficient processing elements, recognition can be performed in a small number of time steps. The number of processing elements necessary to achieve peak performance and the fan-in/fan-out required for the processing elements is examined. These techniques have been simulated on a conventional architecture with good results.

Recent papers have indicated that indexing is a promising approach to fast model-based object recognition because it allows most of the possible matches between sets of image features and sets of model features to be quickly eliminated from consideration. This correspondence describes a system that is capable of indexing using sets of three points undergoing 3D transformations and projection by taking advantage of the probabilistic peaking effect. To be able to index using sets of three points, we must allow false negatives. These are overcome by ensuring that we examine several correct hypotheses. The use of these techniques to speed up the alignment method is described. Results are given on real and synthetic data.>

Hierarchical clustering is a common method used to determine clusters of similar data points in multidimensional spaces. O(n2) algorithms are known for this problem [3,4,11,19]. This paper reviews important results for sequential algorithms and describes previous work on parallel algorithms for hierarchical clustering. Parallel algorithms to perform hierarchical clustering using several distance metrics are then described. Optimal PRAM algorithms using n/log n processors are given for the average link, complete link, centroid, median, and minimum variance metrics. Optimal butterfly and tree algorithms using n/log n processors are given for the centroid, median, and minimum variance metrics. Optimal asymptotic speedups are achieved for the best practical algorithm to perform clustering using the single link metric on a n/log n processor PRAM, butterfly, or tree.

This paper shows that the pose clustering method of object recognition can be decomposed into small sub-problems without loss of accuracy. Randomization can then be used to limit the number of sub-problems that need to be examined to achieve accurate recognition. These techniques are used to decrease the computational complexity of pose clustering. The clustering step is formulated as an efficient tree search of the pose space. This method requires little memory since not many poses are clustered at a time. Analysis shows that pose clustering is not inherently more sensitive to noise than other methods of generating hypotheses. Finally, experiments on real and synthetic data are presented.>

The alignment method is a model-based object recognition technique that determines possible object transformations from three hypothesized matches of model and image points. For images and/or models with many features, the running time of the alignment method can be large. Methods of reducing the number of matches that must be examined are presented. The techniques described are the use of the probabilistic indexing system, and the elimination of groups of model points that produce large errors in the transformation determined by the alignment method. Results are presented which show that it is possible to achieve a speedup of over two orders of magnitude while still finding a correct alignment.>