## 1 Introduction
### Motivation and Contributions  
**Motivation:** The correspondence-based rotation search and point cloud registration approaches are often confronted with one difficulty: in many real-world scenes, the input correspondences are very likely to be corrupted by outliers; for example, the feature matchers (e.g., SIFT [15] and SURF [16] for 2D images and FPFH [17] for 3D point clouds) may generate mismatched or spurious results owing to noise, repetitive patterns, low-textured scenes, etc. Therefore, in real applications, robust estimation solvers should be of paramount significance. When it comes to robust estimation, RANSAC [18] is a common robust heuristic [19], but it has a critical disadvantage: its runtime increases exponentially with the outlier ratio. Thus, RANSAC could be impractical for use when encountering extreme outlier ratios (e.g., more than 90%). Branch-and-Bound (BnB) is able to search in the rotation (\(SO(3)\)or transformation (\(SE(3)\)) group to globally optimize the objective function, whereas its computational cost grows exponentially with the input correspondence number; hence, it may be too slow for large-sized problems. In addition, the outlier removal method GORE [20; 21], as well as the nonminimal solvers FGR [22], QUASAR [23], and TEASER/TEASER++ [24; 25] have been proposed to deal with the two problems with over 90% outliers. However, for point cloud registration, these solvers can only succeed when the scale between the two point clouds is known and fixed. When the scale varies (e.g., between point clouds formed with different sources), none of these methods could tolerate more than 90% outliers, which indeed necessitates a general solver capable of solving not only the known-scale problems, but also the unknown-scale ones. To handle rotation search problems with high outlier ratios, though GORE [21] is efficient when the problem size is small, it requires more time to remove outliers as the correspondence number increases. Hence, proposing a high-outlier-ratio-tolerant solver that can be efficient regardless of the correspondence number seems rather imperative. **Contributions:** Motivated by these facts, in this paper, we propose a novel highly robust paradigm, named Inlier searching with COmpatible Structures (ICOS), for addressing rotation search and generalized point cloud registration with extreme outlier ratios, as exemplified in Figure 1.  
Figure 1: Rotation search and point cloud registration using ICOS. (**a**) Image stitching. Left: correspondences matched by SURF [16]. Middle: inliers found by ICOS (green lines). Right: stitched images with the rotation estimated by ICOS. The outlier ratio is over 74%, and ICOS can correctly find the inliers. (**b**) Unknown-scale point cloud registration. Left: among the 1000 putative correspondences, there exist 990 outliers (red lines) and merely 10 inliers (green lines). Right: ICOS can still estimate the scale, rotation, and translation robustly and precisely. (**c**) Object localization with an unknown scale in a realistic RGB-D scene [26]. Left: correspondences are built between the object and the scene with over 95% outliers. Right: ICOS can accurately reproject the object back to the scene with the transformation it estimated. To be specific, ICOS aims to seek the correct inliers through the random sample flow (rather than pruning outliers as performed in the previous works [20; 27]), but significantly different from the RANSAC family (e.g., [18; 28; 29]), the sampling and filtering process of ICOS is built upon and also facilitated by the constraints derived from the _compatible structures_ that we define based on the theory of _invariance._  
First, we introduced and constructed a series of _compatible structures_ for the rotation search and generalized point cloud registration problems, with which we were able to \"customize\" special invariant-based constraints that can be used for effectively differentiating inliers from outliers only with simple Boolean conditions (Section 4).