# HiGoReg: A Hierarchical Grouping Strategy for Point Cloud Registration
## 1 Introduction
\begin{table}
\begin{tabular}{l l l l} \hline \hline
**Method** & **Model** & **Time Complexity** & **Data Assumptions and Constraints** \\ \hline ICP [21; 50; 51] & \(\sum\|\mathbf{q}-(\mathbf{R}\mathbf{p}+\mathbf{T})\|^{2}=\min\) & \(\mathcal{O}(n^{3})\) & \begin{tabular}{l} Requires significant overlap and good initial transformation; sensitive to outliers; may fall into local minima. \\ \end{tabular} \\ LS3D [30; 31] & \(\mathbf{L}=\mathbf{A}\mathbf{\xi}+\mathbf{e}\) & \(\mathcal{O}(n^{3})\) & \begin{tabular}{l} Assumes Gaussian noise only in target cloud; source cloud is noise-free; may lead to biased, asymmetric estimation. \\ \end{tabular} \\ EIV [52; 53; 54] & \(\mathbf{L}=(\mathbf{A}-\mathbf{E}_{A})\mathbf{\xi}+\mathbf{e}\) & \(\mathcal{O}(n^{3})\) & \begin{tabular}{l} Total Least Squares; Gaussian noise in both point clouds; risk of singular or unstable coefficient matrix. \\ \end{tabular} \\ GH-LS3D [34; 35; 37] & \(\mathbf{f}(x,y,z)+\mathbf{e}_{f}(x,y,z)=\) & \(\mathcal{O}(n^{3})\) & \begin{tabular}{l} Symmetric error modeling; multivariate Gaussian noise; nonlinear model; needs iterative linearization; sensitive to initial values; high-dimensional computational matrices. \\ \end{tabular} \\ RGH [36] & \(\begin{cases}\mathbf{h}(I_{k}+\mathbf{v}_{k},\mathbf{\xi}_{k})=0\\ \mathbf{d}=D\mathbf{\xi}_{k}+\mathbf{v}_{d,k}\end{cases}\) & \(\mathcal{O}\left(\dfrac{n^{3}+m\cdot r^{3}}{m^{2}}\right)\) & \
\begin{tabular}{l} Assumes independent Gaussian process and measurement noise; requires well-set process noise to avoid divergence; complex computation steps. \\ \end{tabular} \\ HiGoReg (ours) & \(\mathbf{f}_{k}-\mathbf{T}-\mathbf{R}\mathbf{g}_{k}=0\) & \(\mathcal{O}\left(\dfrac{n^{3}}{m^{2}}\right)\) &
\begin{tabular}{l} Group-based recursive estimation; assumes Gaussian noise; high computational efficiency; optimal grouping with around 100 points in each group. \\ \end{tabular} \\ \hline \hline \end{tabular} For variable definitions, refer to the original literature. Here, \(n\) denotes the total number of points in the cloud and \(m\) is the number of groups.  
\end{table} 
Table 1: A comparison of 3D point cloud registration function models covering mathematical formulations, time complexity, and application constraints. is significantly reduced, large dimensional matrix operations are avoided. But do more groups yield more benefits? By investigating different grouping sizes, we explored the mystery of \"moderate grouping\" and endeavored to find the optimal spot for balancing accuracy and efficiency. In summary, our main contributions include the following:  
1. The random errors present in all measurements are taken into account in the functional model, resulting in a more rigorous treatment of the observations with higher robustness. 2. Compared with the batch solution, the proposed PCR method based on the hierarchical grouping strategy substantially improves the efficiency of parameter estimation while ensuring consistent parameter estimation results. 3. The effects of two commonly used stochastic models on parameter estimation accuracy and computational efficiency are explored. 4. We introduce the concept of optimal grouping, and give the value of the number of groups under the minimum computation time through plentiful experiments. This paper is structured as follows: Section 2 introduces HiGoReg, detailing its mathematical foundations, key formulas, and computational process. Section 3 presents experiments of the algorithm using simulated and measured data. In Section 4, we present the computational results of the proposed method in comparison with existing approaches. Section 5 further analyzes these results to explore underlying patterns and method characteristics, while Section 6 summarizes findings and addresses limitations.