Skyline based terrain matching

Skyline-based terrain matching, a new method for locating the vantage point of stereo camera or laser range-finding measurements on a global map previously prepared by satellite or aerial mapping is described. The orientation of the vantage is assumed known, but its translational parameters are determined by the algorithm. Skylines, or occluding contours, can be extracted from the sensory measurements taken by an autonomous vehicle. They can also be modeled from the global map, given a vantage estimate from which to start. The two sets of skylines, represented in cylindrical coordinates about either the true or the estimated vantage, are employed as 'features' or reference objects common to both sources of information. The terrain matching problem is formulated in terms of finding a translation between the respective representations of the skylines, by approximating the two sets of skylines as identical features (curves) on the actual terrain. The search for this translation is based on selecting the longest of the minimum-distance vectors between corresponding curves from the two sets of skylines. In successive iterations of the algorithm, the approximation that the two sets of curves are identical becomes more accurate, and the vantage estimate continues to improve. The algorithm was implemented and evaluated on a simulated terrain. Illustrations and examples are included.