To address the matching challenge between the High Resolution Imaging Science Experiment (HiRISE) Digital Elevation Model (DEM) and the Mars Orbiter Laser Altimeter (MOLA) DEM, we propose a terrain matching framework based on the combination of point cloud coarse alignment and fine alignment methods. Firstly, we achieved global coarse localization of the HiRISE DEM through nearest neighbor matching of key Intrinsic Shape Signatures (ISS) points in the Fast Point Feature Histograms (FPFH) feature space. We introduced a graph matching strategy to mitigate gross errors in feature matching, employing a numerical method of non-cooperative game theory to solve the extremal optimization problem under Karush–Kuhn–Tucker (KKT) conditions. Secondly, to handle the substantial resolution disparities between the MOLA DEM and HiRISE DEM, we devised a smoothing weighting method tailored to enhance the Voxelized Generalized Iterative Closest Point (VGICP) approach for fine terrain registration. This involves leveraging the Euclidean distance between distributions to effectively weight loss and covariance, thereby reducing the results’ sensitivity to voxel radius selection. Our experiments show that the proposed algorithm improves the accuracy of terrain registration on the proposed Curiosity landing area’s, Mawrth Vallis, data by nearly 20%, with faster convergence and better algorithm robustness.