Registering highly efficient and accurate point clouds with strong noise and inhomogeneous density remains a challenging task. In this paper, we propose a point cloud registration algorithm based on keypoint extraction and the improved iterative closest point (ICP). In coarse registration, we first fused the voxel grid filtering and normal distance keypoint extraction and then computed the fast point feature histogram of keypoints for feature matching. Then the random sampling consistency (RANSAC) algorithm was estimated and optimized by correspondent relation for eliminating mismatches. In fine registration, we implemented the best bin first (BBF) algorithm to search for the nearest point of k-d tree and set the dynamic threshold to eliminate wrong point pairs. Finally, we used the improved accelerated ICP algorithm based on the “point-to-triangle plane” model to obtain the registration vector. By registering the model point cloud and building point cloud, we compared the proposed algorithm with other commonly used algorithms. The results demonstrate that the proposed algorithm is robust against noise, and in particular, the running speed and registration accuracy are enhanced.