Underwater terrain-aided navigation is used to complement traditional inertial navigation employed by autonomous underwater vehicles during lengthy missions. It can provide fixed estimations by matching real-time depth data with a digital terrain map. This study presents the concept of using image processing techniques in the underwater terrain matching process. A traditional gray-scale histogram of an image is enriched by incorporation with spatial information in pixels. Edge corner pixels are then defined and used to construct an edge corner histogram, which it employs as a template to scan the digital terrain map and estimate the fixes of the vehicle by searching the correlation peak. Simulations are performed to investigate the robustness of the proposed method, particularly in relation to its sensitivity to background noise, the scale of real-time images, and the travel direction of the vehicle. At an image resolution of 1 m2/pixel, the accuracy of localization is more than 10 meters.