All aircraft rely on on-board sensor systems for navigation. The drawback to inertial sensors is that their position error compounds over time. Global Positioning Systems (GPS) overcome that problem for location but not orientation; also, GPS is sensitive to signal dropout and hostile jamming. In this paper, we present a system capable of estimating the six-degree-of-freedom (6DOF) state (geo-location and orientation) of an air vehicle given digital terrain elevation data (DTED), an estimate of the vehicle's velocity, and a sequence of images from an onboard video camera. This system first reconstructs individual terrain map sections from pairs of images taken by the onboard video camera as it flies over the terrain. The velocity estimate is used to convert the metric units produced by the reconstruction to Euclidean units (such as meters). The individual reconstructed map sections are then stitched together to form a larger terrain map. This reconstructed terrain map is then matched against the DTED to produce an estimate of the 6DOF state of the vehicle.