A terrain-matching algorithm that makes possible a passive aircraft navigation system is presented. A sequence of aerial images is matched to a reference to a digital map of the 3-D terrain. Stereo analysis of successive images results in a recovered elevation map. A cliff map is then used as a novel, compact representation of the 3-D surfaces. The position and heading of the aircraft are determined via a terrain-matching algorithm that locates the unknown cliff map within the reference cliff map. The robustness of the matching algorithm is demonstrated by experimental results using real terrain data.