next up previous
Next: Comparing Position Estimates Up: The Estimation Algorithm Previous: The Estimation Algorithm

Searching for Position

Previous approaches to outdoor pose estimation differ in how they conduct the search for estimates. Thompson and his group [14] search position plus yaw angle by generating a sequence of interpretations for the bearings. Since there are too many interpretations (nm for m bearings and n peaks), they apply an alignment technique to prune the search; they also concentrate the search on a few peaks of high saliency. But high saliency peaks are generally large and far away; estimates produced from detection of such peaks are bound to have large errors, on the order of kilometers. Good accuracy requires the use of large and small peaks in the horizon.

A different approach, which can handle large and small map features, is adopted by Stein and Medioni [11]: they search in the space of possible renderings of the map. The size of this space is also large since each position leads to a different rendered horizon. To reduce the size of this space, Stein and Medioni quantize the rendered horizons and pre-compute large look-up hash tables containing the quantized horizons. The performance of their approach depends on the quantization; to attain realistic speeds, they report quantizations that yield a minimum possible error of 300 meters.

Given the enormous number of correspondences between images and map, a better approach is to search in the space of positions. Consider a Digital Elevation Map gridded at 30 meters, covering a square of 6x6 kilometers. To handle the full resolution of the map, we need to go through 40000 positions and establish a figure of merit for each one of them. This seemingly daunting task has been pursued by Talluri and Aggarwal [13]; to speed up the search, they have used a single point in the image as a measure of ``goodness of fit'' between image and map. Although easy to calculate, this is a unrealistic figure of merit since images tend to have noise and, worse still, spurious features like rocks or shadows.

We propose a new approach to this search problem that improves ideas reviewed above. We search in the position space, but we construct a figure of merit (the posterior probability described in Section 4.2) that reflects the various disturbances in the image and can also include prior knowledge about position. The key idea is to simplify the search procedure by pre-computing virtually all the calculations that must be performed during search. We automatically create (off-line) a table containing all the peaks that can be found in the map. We also create (off-line) a table containing all the peaks that are visible from every possible position. During search, we only have to access the latter table for retrieving the index of visible peaks, access the former table for retrieving characteristics of the peaks, and compute the posterior probability for position. As an example, computation of the posterior probability for the more than 30000 positions in the Pittsburgh map of Figure 2 takes 3 seconds in a Sun Sparc20.


next up previous
Next: Comparing Position Estimates Up: The Estimation Algorithm Previous: The Estimation Algorithm

Fabio G. Cozman