4 Points Fast Matching Algorithm For 3D Data Based On Multi-Scale Feature Exaction

Three-dimensional shape matching has a very wide range of applications such as reverse engineering, robotics, medical image registration, as well as industrial and many other areas. It is an important research topic in computer graphics. The key of three-dimensional shape matching is the surface matching.In recent years, with the rapid development of three-dimensional scanning device, matching methods based on point cloud surface are paid more and more attention. For complicated surface topology, point cloud can well indicate the surface shape information. Therefore, surface matching based on the discrete surface point cloud is a new topic in the computer graphics that has a very important theoretical and practical significance.The basic problem of the topic is to find the optimal transformation between the two three-dimensional surface point cloud data with arbitrary initial positions, multi-scanned by the same object. And after applying the transformation to one of them, the difference between the two objectives should be zero. The choice of surface matching algorithms depends largely on the way by which the surface is represented. In computer graphics, there are two ways of discrete surface representation, point cloud and triangle meshes. Raw data that three-dimensional laser scanner obtains is represented by point cloud, which is simple and flexible. Our work is to match 3-D surfaces based on point cloud data.Dior Arger et al [4] in 2008 proposed a robust four-point fast matching algorithm (4-Points Congruent Sets for Robust Pairwise Surface Registration, referred to as 4PCS algorithm). Instead of choosing three points from the whole surface to be a match base set as traditional methods do, 4PCS method choose four, which are coplanar. The algorithm can be used without any initial iteration estimation, and can automatically match a pair of surfaces with noise. But in practice, it is found that its effect is not very satisfactory, and time complexity is still very large.In this paper, we make an improvement to 4PCS algorithm by using multi-scale extraction skills as a pre-processing step to the algorithm. We first use a multi-scale analysis to extract 3D feature points set, using different neighborhood size as a scale parameter, and then we use the 4PCS algorithm to the feature point's sets that is exacted.This can reduce the complexity of searching for four-point set of coplanar points of 4PCS algorithm to a large extent, which can greatly improve the matching efficiency, and make the matching to be more obvious because of that the matching step is based on points that have stronger features, thereby increasing the match accuracy.Therefore, for all the points on the two 3-dimensional point surface set P and Q with arbitrary initial position, the whole matching process is divided into five steps:1. Design k-neighborhood search algorithm, for each point on the P and Q, the algorithm can find its k-neighbor points, where k is an arbitrary number.2. Using k as a scale parameter, for each point, compute its surface variation under best-scale ,see it as eigenvalue, then extract the set of feature points and Q by the eigenvalue of each point as the basis set of the matching P′′3. Search a set of 4 coplanar points from P′as matching base B.4. Search for all subsets of 4-points from Q′that are approximately congruent to B using affine invariant. By approximate congruence, we mean that the two 4-points sets can be aligned, up to some allowed tolerance, using rigid transformation5. Then compute each transformation between each 4-points and B. Each aligning transform is assigned a score based on the number of points that are brought into alignment up to a threshold . Over all such trials, we select the transform with the best score..The key point of this work is to apply multi-scale feature extraction method based on surface variation as a pretreatment step for matching algorithm. First extract all the feature points from the objects, and then apply matching algorithm to the feature points sets. This makes many advantages:First, the applying of the multi-scale feature extraction algorithm greatly reduced the four-point search algorithm's time complexity, thus greatly reduced the time complexity of matching.Second, due to the feature point set as a basis for matching point sets, the choice of 4 points are all made from the points set in which every point has significant features, thus allowing more precise match.Third, as a result of applying multi-scale feature extraction preprocessing steps, the scale of points makes a smoothing effect: increasing the size of the local neighborhood is similar to applying a smoothing filter. This becomes intuitively clear if we look at the way the covariance matrix is defined as sums of squared distances from the neighbor-hood's centroid point. If we increase the neighborhood size, each individual point contributes less to the surface variation estimate. Hence high-frequency oscillations are attenuated, analogous to standard low-pass filter behavior. Thus making the algorithm allow registering raw noisy data, possibly contaminated with outliers, without pre-filtering or denoising the data.In addition, in multi-scale feature extraction step, this paper proposes a simple and feasible k-neighborhood searching algorithm, compared with traditional simple search algorithm, its efficiency has improved substantially. In multi-scale three-dimensional object feature extraction algorithm, it plays a very good effect.