The Estimation Algorithm

 

Given the bearings, we must generate estimates of position. Two decisions must be made. First, what is the space in which we conduct the search. Second, how to establish a convenient figure of merit to evaluate the possible estimates of position.

The search for best estimates can be conducted in the space of interpretations [17], but only when using few peaks and image features; otherwise too many interpretations have to be visited. Use of few features compromises accuracy, which requires the use of large and small peaks in the horizon. Another search strategy is to look at the space of possible renderings of the map [13]. In order to conduct such a search, speed-up techniques like quantization must be used, again causing a loss of accuracy.

A more promising approach is to search the space of positions. To handle a USGS topographic quadrangle, we need to go through 410⁴ positions and establish a figure of merit for each. This seemingly daunting task has been pursued by Talluri and Aggarwal [16]; 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. In real images such a simplified figure of merit is unrealistic, since it does not take into account the noise and artifacts of real images.

We search in the position space, but we construct a figure of merit that reflects the various disturbances in the image and can also include prior knowledge about position. The key idea to speed-up our algorithm 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 need only 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.

Our estimation objective is to maximize the posterior probability of position given the bearings, p(x, y | R). Position is discretized in intervals of 30 meters, agreeing with the discretization of Digital Elevation Maps. At first, we must specify a prior density for position, p(x, y). Currently we use a uniform distribution to signify absence of prior knowledge. Secondly, we must specify likelihood of bearings (the measurements) given position, p(R | x, y). This distribution is constructed by assuming independence of bearings given a particular interpretation, and Gaussian distributions for the distribution of bearings [2]. Error that exceed 18 degrees are discarded as mistakes and assumed distributed uniformly on the interval [0, 360] degrees. We construct the posterior distribution by using Bayes rule on these models. Since bearings do not need to be associated to all possible mountains, the posterior distribution can be quickly calculated. As an example, computation of the posterior probability for the more than 310⁴ positions in the Pittsburgh map of Figure 2 takes 3 seconds running in an Impact SGI workstation.