Skull registration is one of the important steps in the process of craniofacial restoration. The accuracy of skull registration directly affects the outcome of craniofacial restoration. In order to improve the registration accuracy and convergence speed of skull point cloud model, a registration algorithm based on the hierarchical optimization strategy is proposed. The registration process is divided into two processes, coarse registration and fine registration. The different optimization strategies are used for optimization. Firstly, the geometric features are extracted based on the neighborhood of points, and then the eigenvectors consisting of mean curvature, Gauss curvature, normal vector angle, and principal curvature are obtained. Further, the feature similarity is calculated by distance function to establish matching point pairs, and k-means algorithm is used to eliminate the mismatching point pairs. Then the quaternion method is used to calculate the rigid body transformation relationship between the skull point clouds to achieve skull coarse registration. Finally, the improved iterative closest point (ICP) algorithm is improved by the introducing k-d tree and geometric feature constraints. The improved ICP algorithm is used to achieve accurate skull registration. The experimental results show that it is effective to use the k-means algorithm to eliminate the mismatched point pair optimization strategy. It is also effective to add the k-d tree and geometric feature constraint optimization strategy to the fine registration process. Compared with ICP algorithm, the matching rate and registration accuracy of this algorithm are improved by 17% and 51%, respectively, and the time-consuming is reduced by 31%. Compared with other classical registration algorithms and improved ICP algorithm, the efficiency of the proposed algorithm is the best. In order to verify the universality of the algorithm, the terra cotta warriors fragment data is also used to verify, and the proposed algorithm achieves good results and optimal performance. Therefore, the proposed algorithm is an effective point cloud registration method.