Keypoint domain triangular features for fast initial alignment of 3D point clouds

Paper

Existing initial alignment algorithms usually suffer from the limited computational efficiency. The core reason is that existing local geometric features are mainly computed in the point cloud domain, although the raw point clouds are of great redundancy.

a point cloud P and keypoint set K
keypoints are extracted from P by Harris 3D detector (H3D)
every keypoint p_i has two nearest neighbors (p_iⁿⁿ¹ and p_iⁿⁿ²), and these three points forms a triangle
KDT feature:
- f_KDT(p_i) = {l₁, l₂, l₃, idx(p_i), idx(p_iⁿⁿ¹), idx(p_iⁿⁿ²)}
- l₁ = dist(p_i, p_iⁿⁿ¹), l₂ = dist(p_i, p_iⁿⁿ²), l₃ = dist(p_iⁿⁿ¹, p_iⁿⁿ²)
- idx is the index of the point in P
- idx will be used to recall the vertexes of the triangle in the transformation estimation step for acceleration
KDT correspondence:
- soucre feature set Fs = {f₁^s, f₂^s, …}, target feature set Ft = {f₁^t, f₂^t, …}
- for every f_i^s in Fs, search the most similar f_i^t in Ft (use KD tree)
- correspondence c_i is obtained after found the feature pair
- correspondence set C is then be generated {c₁. c₂, …}
- sort the C in ascending order, and take the top-K candidates as reduced set C’
transformation estimation via 1P-SAC (1 point-based sample consensus)
- randomly select correspondence c in C’ (size of C’ is k)
- calculate the transformation T_i, and find the number of inliers T_i^inlier
- after k iterations, the resultant transformation is T with the largest number of inliers
- reduce the computational complexity from O(n³) to O(n)

keypoints detected by H3D, KPQ, and ISS
- around 1100 keypoints per point cloud yield the best performance
compared to fast point feature histograms (FPFH)-based method, the local feature statistics histograms (LFSH)-based method, and Go-ICP approach
sufficient consistent correspondences have been found and all point cloud pairs are accurately aligned
RMSE of bunny, dragon, chef, and chicken are 1.272, 4.271, 1.673, and 0.95, respectively