3-Points Convex Hull Matching (3PCHM) for fast and robust point set registration

Point set registration plays a crucial role in numerous computer vision applications. This paper proposes a novel and general approach called three-point convex hull matching (3PCHM) for registering two point sets with similarity transform. First, convex hulls are extracted from both point sets. Triangular patches on the surface of convex hulls are specified by predefining their normal vectors, thus guaranteeing that all points are located on the same side of any randomly selected triangle plane. Second, the potential similar triangle pair set is obtained by comparing the length ratio of the edges on the two extracted convex hulls. Thereafter, the transformation parameters for each pairwise triangle are calculated by minimizing the Euclidean distance between the corresponding vertex pairs. Furthermore, a k-dimensional (k-d) tree is used to accelerate the closest point search for the whole point sets. Third, outliers that may lead to significant errors are discarded by integrating the random sample consensus algorithm for global optimization. Experiments show that the proposed 3PCHM is robust even with the existence of noise and outliers and is effective in cases of part-to-part registration and part-to-whole registration.