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^{4} 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^{4} positions in the
Pittsburgh map of Figure 2 takes 3 seconds running
in an Impact SGI workstation.

Tue Jun 24 00:46:56 EDT 1997