This paper describes a position identification method to precisely estimate the relative movement onboard of an autonomous explorer in such natural terrain as Moon or Mars. This paper proposes a new map matching scheme that registers the visual information of consecutive robot positions and expresses the robot displacement in a common coordinate system. Local elevation maps of the environment are therefore retrieved from the 3D perception of a stereo camera. The proposed scheme consists of three main steps: feature point extraction from map data, matching of features points using triangle configurations and a voting procedure, and direct calculation of the robot displacement in six degrees of freedom using quaternions. The effectiveness of the proposed method is confirmed by computer simulations with synthetic terrain and experiments with stereo perception.