基于多尺度特征提取的3D点云匹配的4PCS算法
|
摘要
近年来,三维曲面重建技术在医学影像、文物复原等领域得到了广泛的应用。至今为止,三维模型的准确重建依然存着许多技术性难题,例如3D点云匹配问题。
Dior Arger等人针对此问题提出了四点快速鲁棒匹配算法(即4PCS算法),该方法不需要初始迭代估计,且对含噪声和扰动的数据有很好的效果,不过在实际应用中它的速度和匹配效果经常不尽人意。
本文针对4PCS算法提出了一个改进方案,将基于曲面变分的多尺度特征提取方法作为一个预处理步骤,使得点云数据具有多尺度特征,并可根据由此提取出有效的特征点集,再在特征点集上应用4PCS算法进行匹配。这一改进的优点是:
1.降低了搜索算法和匹配算法的时间复杂度,提高了算法效率;
2.提高了匹配的准确度;
3.新算法鲁棒性好,且能检测出曲率非常低的粗尺度特征。
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 transformation
5. 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.
Dior Arger等人针对此问题提出了四点快速鲁棒匹配算法(即4PCS算法),该方法不需要初始迭代估计,且对含噪声和扰动的数据有很好的效果,不过在实际应用中它的速度和匹配效果经常不尽人意。
本文针对4PCS算法提出了一个改进方案,将基于曲面变分的多尺度特征提取方法作为一个预处理步骤,使得点云数据具有多尺度特征,并可根据由此提取出有效的特征点集,再在特征点集上应用4PCS算法进行匹配。这一改进的优点是:
1.降低了搜索算法和匹配算法的时间复杂度,提高了算法效率;
2.提高了匹配的准确度;
3.新算法鲁棒性好,且能检测出曲率非常低的粗尺度特征。
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 transformation
5. 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.
引文
[1] AGARWAL, P, K., AND SHARIR, M. 2002. The number of congruent simplices in a point set. In Discrete comput. Geometry, vol.39, 123-150,
[2] BALLARD, D. H. 1987. Generalizing the hough transform to detect arbitrary shapes. Readings in computer vision: issues, problems, principles, and paradigms, 714–725.
[3] BESL,P.H., AND MCKAY, N. D. 1992. A method for registration of 3-d shapes. IEEE Trans. On Pattern Analysis and Machine Intelligence 14, 2, 239-256 .
[4] Dror Aiger ,Niloy J. Mitra,Daniel Cohen-or,4-Points Congruent Sets for Robust Pairwise Surface Registration
[5] Edelsbrunner, H., Letscher, D., Zamorodian, A. Topological Persistence and Simplificiation. Discrete and Computational Geometry, Springer, 2002
[6] FISCHLER, M. A., AND BOLLES, R. C. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6,381–395.
[7] FROME, A., HUBER, D., KOLLURI, R., BULOW, T., AND MALIK, J. 2004. Recognizing objects in range data using regional point descriptors. In Proceedings of the European Conference on Computer Vision (ECCV).
[8] GAL, R., AND COHEN-OR, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Trans. Gr. 25, 1,130–150.
[9] GERMAIN, R. S., CALIFANO, A., AND COLVILLE, S. 1997. Fingerprint matching using transformation parameter clustering. IEEE Comput. Sci. Eng. 4, 4, 42–49.
[10] GOODRICH,M. T., MITCHELL. J. S. B., AND ORLETSKY. M. W. 1994. Practical methods for approximate geometric pattern matching under rigid motions. In symp. On Computational Geometry, 103-112
[11] Gumhold, S., Wang, X., McLeod, R. Feature Extraction from Point Clouds. Proc. 10th Int. Meshing Roundtable, 2001.
[12] Hall, P.M., Marshall, A.D., Martin, R.R. Incremental Eigenanalysis forClassification. Proc. of the British Machine Vision Conference 1998, Vol. 1., 1998
[13] HORN, B. K. 1987. Closed-form solution of absolute orientation using unit quaternions. In Journal of the Optical Society of America, vol. 4, 629–642.
[14] HUTTENLOCHER, D.P., 1991. Fast affine point matching: An output-sensitive method. Tech.rep.,Cornell, CS department.
[15] Hubeli, A., Gross, M. Multiresolution Feature Extraction from Unstructured Meshes. IEEE Visusualization 01, 2001
[16] INDYK,P., MOTWANI, R., AND VENKATASUBRAMANIAN,S. 1999. Geometric matching under noise: combinatorial bounds and algorithms. In Symposium on Discrete algorithms, 457-465.
[17] IRANI, S., AND RAGHAVAN, P. 1996. Combinatorial and experimental results for randomized point matching algorithms. In Symp. on Computational Geometry, 68–77.
[18] JOHNSON, A. 1997. Spin-Images: A Representation for 3-D Surface Matching. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
[19] Jolliffe, I. Principle Component Analysis. Springer-Verlag, 1986
[20] Kobbelt, L. Botsch, M., Schwanecke, U., Seidel, H. Feature Sensitive Surface Extraction from Volume Data. SIGGRAPH 01, 2001
[21] Mark, Richard Keiser, Markus Gross, Multi-scale Feature Extraction on Point-sampled Surfaces. EUROGRAPHICS 2003/ P.Brunet and D.Fellner, 2003
[22] MITRA, N. J., GUIBAS, L., GIESEN, J., AND PAULY, M. 2006. Probabilistic fingerprints for shapes. In Proc. Symp. Geometry Processing, 121–130.
[23] MORI, M.-G., BELONGIE, M.-S., AND MALIK, S. M.-J. 2005. Efficient shape matching using shape contexts. IEEE Trans. On Pattern Analysis and Machine Intelligence 27, 11, 1832–1837.
[24] Pauly, M., Gross, M. Spectral Processing of Point-Sampled Geometry, SIGGRAPH 01, 2001
[25] POTTMANN, H., WALLNER, J., YANG, Y.-L., LAI, Y.-K., AND HU, S.-M. 2007. Principal curvatures from the integral invariant viewpoint. Comput. Aided Geom. Des. 24, 8-9, 428–442.
[26] WOLFSON, H. J., AND RIGOUTSOS, I. 1997. Geometric hashing:An overview. IEEE Comput. Sci. Eng. 4, 4, 10–21
[2] BALLARD, D. H. 1987. Generalizing the hough transform to detect arbitrary shapes. Readings in computer vision: issues, problems, principles, and paradigms, 714–725.
[3] BESL,P.H., AND MCKAY, N. D. 1992. A method for registration of 3-d shapes. IEEE Trans. On Pattern Analysis and Machine Intelligence 14, 2, 239-256 .
[4] Dror Aiger ,Niloy J. Mitra,Daniel Cohen-or,4-Points Congruent Sets for Robust Pairwise Surface Registration
[5] Edelsbrunner, H., Letscher, D., Zamorodian, A. Topological Persistence and Simplificiation. Discrete and Computational Geometry, Springer, 2002
[6] FISCHLER, M. A., AND BOLLES, R. C. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6,381–395.
[7] FROME, A., HUBER, D., KOLLURI, R., BULOW, T., AND MALIK, J. 2004. Recognizing objects in range data using regional point descriptors. In Proceedings of the European Conference on Computer Vision (ECCV).
[8] GAL, R., AND COHEN-OR, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Trans. Gr. 25, 1,130–150.
[9] GERMAIN, R. S., CALIFANO, A., AND COLVILLE, S. 1997. Fingerprint matching using transformation parameter clustering. IEEE Comput. Sci. Eng. 4, 4, 42–49.
[10] GOODRICH,M. T., MITCHELL. J. S. B., AND ORLETSKY. M. W. 1994. Practical methods for approximate geometric pattern matching under rigid motions. In symp. On Computational Geometry, 103-112
[11] Gumhold, S., Wang, X., McLeod, R. Feature Extraction from Point Clouds. Proc. 10th Int. Meshing Roundtable, 2001.
[12] Hall, P.M., Marshall, A.D., Martin, R.R. Incremental Eigenanalysis forClassification. Proc. of the British Machine Vision Conference 1998, Vol. 1., 1998
[13] HORN, B. K. 1987. Closed-form solution of absolute orientation using unit quaternions. In Journal of the Optical Society of America, vol. 4, 629–642.
[14] HUTTENLOCHER, D.P., 1991. Fast affine point matching: An output-sensitive method. Tech.rep.,Cornell, CS department.
[15] Hubeli, A., Gross, M. Multiresolution Feature Extraction from Unstructured Meshes. IEEE Visusualization 01, 2001
[16] INDYK,P., MOTWANI, R., AND VENKATASUBRAMANIAN,S. 1999. Geometric matching under noise: combinatorial bounds and algorithms. In Symposium on Discrete algorithms, 457-465.
[17] IRANI, S., AND RAGHAVAN, P. 1996. Combinatorial and experimental results for randomized point matching algorithms. In Symp. on Computational Geometry, 68–77.
[18] JOHNSON, A. 1997. Spin-Images: A Representation for 3-D Surface Matching. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
[19] Jolliffe, I. Principle Component Analysis. Springer-Verlag, 1986
[20] Kobbelt, L. Botsch, M., Schwanecke, U., Seidel, H. Feature Sensitive Surface Extraction from Volume Data. SIGGRAPH 01, 2001
[21] Mark, Richard Keiser, Markus Gross, Multi-scale Feature Extraction on Point-sampled Surfaces. EUROGRAPHICS 2003/ P.Brunet and D.Fellner, 2003
[22] MITRA, N. J., GUIBAS, L., GIESEN, J., AND PAULY, M. 2006. Probabilistic fingerprints for shapes. In Proc. Symp. Geometry Processing, 121–130.
[23] MORI, M.-G., BELONGIE, M.-S., AND MALIK, S. M.-J. 2005. Efficient shape matching using shape contexts. IEEE Trans. On Pattern Analysis and Machine Intelligence 27, 11, 1832–1837.
[24] Pauly, M., Gross, M. Spectral Processing of Point-Sampled Geometry, SIGGRAPH 01, 2001
[25] POTTMANN, H., WALLNER, J., YANG, Y.-L., LAI, Y.-K., AND HU, S.-M. 2007. Principal curvatures from the integral invariant viewpoint. Comput. Aided Geom. Des. 24, 8-9, 428–442.
[26] WOLFSON, H. J., AND RIGOUTSOS, I. 1997. Geometric hashing:An overview. IEEE Comput. Sci. Eng. 4, 4, 10–21