With the emergence of keypoint matching technology, the correspondence-based point cloud registration (PCR) method has gained increasing attention. However, the correspondences generated by keypoint matching technology contain extremely high outlier rates, resulting in the correspondence-based PCR method facing issues of high computational complexity and low precision registration. We propose a correspondence-based PCR method using a coarse-to-fine outlier removal strategy with O ( N ) complexity. First, we propose a coarse outlier removal module based on linearly related properties, i.e., we build a deviation matrix that can measure each correspondence deviation the degree away from the ideal inlier. The module can reduce the number of correspondences and the outlier rates. Then, we propose a fine outlier removal module that adopts each correspondence to identify outlier based on the spatial geometric mapping invariance. Finally, to increase registration accuracy, we introduce a graduated non-convexity with Tukey’s biweight method. It can avoid the solution falling into the local minimum and better reduce the influence of outliers. Experimental results show that the proposed method is robust at outlier rates above 99% and is faster than state-of-the-art methods.