## 5 Our Solver: ICOS
### ICOS for Rotation Search  
For addressing the rotation search problem, we render the pseudocode of ICOS in Algorithm 1 and the description for each part as follows. ```
Input : correspondences \(\mathcal{N}=\{(\mathbf{u}_{i},\mathbf{v}_{i})\}_{i=1}^{N}\);  minimum number of 3-COS \(X\); Output : optimal \(\hat{\mathbf{R}}\);  inlier set \(\mathcal{N}^{In}\);
1 whiletruedo
2\(\mathcal{N}^{In}\leftarrow\varnothing\), \(pass\gets 0\), \(count\gets 0\);
3 for\(itr_{1}=1:maxitr_{1}\)do
4 Randomly select \(\mathcal{R}=\{(\mathbf{u}_{i},\mathbf{v}_{i})\}_{i=1}^{2}\subset\mathcal{N}\);
5 if\(\mathcal{R}\) satisfies Constraint (13)then
6 Solve \(\mathbf{R}_{12}\) with \(\mathcal{R}\) using (15);
7\(pass\gets 1\);
8 break
9 end if
10
11 end for
12 if\(pass=1\)then
13 for\(itr_{3}=1:maxitr_{3}\)do
14 checkSampling;
15 Randomly select \((\mathbf{u}_{k},\mathbf{v}_{k})\in\mathcal{N}\), and construct a 3-COS with \(\mathcal{R}\);
16 ifthis3-COS satisfies (17)-(19)then
17\(count\gets count+1\);
18\(\mathcal{N}^{In}\leftarrow\mathcal{N}^{In}\cup\{(\mathbf{u}_{k},\mathbf{v}_{k})\}\);
19
20 end if
21 if\(count\geq X\)then
22\(\mathcal{N}^{In}\leftarrow\mathcal{N}^{In}\cup\mathcal{R}\);
23 break
24
25 end if
26
27 end for
28
29 end for
30 Solve \(\hat{\mathbf{R}}\) with set \(\mathcal{N}^{In}\) using (8);
31 Compute the residual errors \(r_{i}\) (\(i=1,2,\ldots,N\)) for all the correspondences in \(\mathcal{N}\); if \(r_{i}\leq 5.2\sigma\), then add it to \(\mathcal{N}^{In}\);
32 Solve optimal \(\hat{\mathbf{R}}\) with \(\mathcal{N}^{In}\) using (8);
33 return optimal \(\hat{\mathbf{R}}\) and the inlier set \(\mathcal{N}^{In}\);
```  
**Algorithm 1**ICOS for rotation search  
**Lines 2-10**: ICOS initiates with random sampling. However, different from ordinary random sampling procedures, we impose constraints on each random sample selected. When picking one random subset \(\mathcal{R}\) of 2 correspondences, we immediately check the length-based invariant (13). If it can be satisfied, we solve the raw rotation with this 2-COS \(\mathcal{R}\) and then allow it to proceed to the next step, which is operated by setting \(pass=1\); if not, we start over from the sampling process. **Lines 11-25**: If we manage to obtain an eligible 2-COS, say \(\mathcal{R}\), we can then seek new correspondences to build a 3-COS, also by constrained sampling, where we select and test the correspondence samples one at a time. If one correspondence can satisfy Constraints (17)-(19), indicating that it can form an eligible 3-COS with \(\mathcal{R}\), we add it to the inlier set and make \(count\) increase by 1. Once we collect enough 3-COS (\(count\geq X\)), we stop sampling and return the \(X+2\) inliers in total. During this process, we supplement an important subroutine: _checkSampling_, in order to boost time efficiency, which is designed to timely break from the sampling if the obtained 2-COS (\(\mathcal{R}\)) does not seem to be inliers, and this operation could be realized by regularly checking the number of 4-COS formed according to the iteration number, as demonstrated in Algorithm 2. To be specific, as long as the correspondences in set \(\mathcal{R}\) are both inliers, at least one inlier correspondence ought to be sampled after a sufficient number of iterations that can be computed from (37) by setting a high confidence; conversely, if the latter condition cannot be satisfied, we have every reason to suppose that set \(\mathcal{R}\) contains at least one outlier. ```
Input :\(X\), \(\mathit{itr}_{3}\), \(\mathit{count}\), and label \(\gets 0\); Output :break or do nothing;
1 forit=1:\(X\)do
2 if\(\mathit{itr}_{3}\geq it\cdot max\mathit{itr}_{4}\), and \(count<it\)then
3\(label\gets 1\);
4 break
5 end if
6
7 end for
8 iflabel \(=1\)then
9 break
10 end if
```  
**Algorithm 2**_checkSampling_ (subroutine of ICOS)  
**Lines 26-28**: We first compute the rotation with the \(X\)+2 inliers and then consider all correspondences whose residual errors satisfy \(r_{i}\leq 5.2\sigma\) as the ultimate inliers.