Terrain aided navigation is a supplement to inertial navigation system for vehicles in long-time missions. By matching real-time data with a known reference digital terrain map, the vehicle’s position can be estimated. This paper proposes a novel underwater terrain matching method involving image processing techniques. Traditional gray-scale histogram of images is upgraded by introducing spatial information into it. Edge corner pixel is defined in order to represent the distribution complexity of pixels in the same gray level. This concept is used to calculate the correlation between the real-time data and the reference map. Simulations show that the matching process can give robust estimation of underwater platform’s position in noise background. Accuracy of the results can reach less than 10 pixels with the image resolution at 1 meter/pixel and with various areas of real-time images.