基于结构光扫描仪的数据配准关键技术研究
|
摘要
逆向工程技术是进行产品设计,研究和创新的一项先进技术。从获取的三维点云数据出发,对三维点云数据进行处理是逆向工程领域中的关键技术之一,其中点云数据配准技术是数据处理中的重要组成部分,配准的精度直接决定着三维重建效果。本文对逆向工程技术中,三维点云数据的配准技术作了深入研究,重要过程主要涉及粗配准和精确配准。
本文提出了一种基于标记点的快速点云数据配准技术,包括粗配准和精确配准。测量物体之前,在物体表面上粘贴标记点,利用结构光三维扫描仪对物体进行测量,得到递增式标记点和密集点云三维数据。采用递增式点云数据配准的优点是不要求新测量所得的标记点与前一次之间至少存在3组或3组以上的匹配点对,而是要求与之前所有的测量中所得的标记点存在3组或3组以上的匹配点对即可,此种方法增加了系统测量的灵活性。
采用基于标记点的方法估计出坐标变换参数。首先利用基于定位基准点自适应算法查找至少3对对应点,然后采用四元数法估计变换参数,本文研究并实现了基于标记点的粗配准算法,并用实例进行了实验和验证。
精确配准中,提出一种改进的ICP算法,将粗配准的结果作为精配准的初值,利用k-d树搜索算法确定初始的对应点,然后采用基于预检验的随机抽样一致性算法剔除误匹配点。通过实验证明,该方法在查找初始对应点时大大提高了计算效率,最后的配准精度也有所提高。
As an advanced manufacturing technique, reverse engineering can be applied to product design, development and innovation. Data processing of the point clouds is one of the key technologies in reverse engineering. It's very significant to study on data registration, because the registration accuracy and the number of 3D data point have vital effect on the quality of 3D model reconstruction.3D point clouds registration in reverse engineering are researched in detail in this thesis, which consists of the coarse registration and fine registration.
A rapid method for point clouds registration based on reference points is proposed, which consists of the coarse registration and fine registration. A set of reference points is applied as an assistant utility to measure the object, which is on the surface of the object. The 3D data of the incremental reference points and density point clouds are acquired by a structure light 3D scanner. The advantage of the registration method of incremental point clouds is that the number of corresponding points of the reference points does not be required 3 or above 3 groups between the new measurement and its predecessor, only is required 3 or above 3 groups between the new measurement and before all the times of measurement. This measurement method is very flexible.
In coarse registration, the transformation parameters are estimated by using the reference points only. First, the characteristic of the relative distance between arbitrary two points in the locating points set is used in finding at least three corresponding points. Then, quaternion method is utilized to estimate the transformation parameters. A new coarse registration algorithm based on the reference points is presented and realized.
In fine registration, taking the coarse registration results as the initial value, the improved Interactive Closest Point (ICP) algorithm is used in fine registration. The original corresponding points are established rapidly by using the k-d tree searching algorithm. Finally, Preview Model Parameters Evaluation Random Sample Consensus (PERANSAC) algorithm is utilized to remove outliers. The experimental result shows that this method in finding original corresponding points can greatly improve the computation efficiency and also improve the registration accuracy.
本文提出了一种基于标记点的快速点云数据配准技术,包括粗配准和精确配准。测量物体之前,在物体表面上粘贴标记点,利用结构光三维扫描仪对物体进行测量,得到递增式标记点和密集点云三维数据。采用递增式点云数据配准的优点是不要求新测量所得的标记点与前一次之间至少存在3组或3组以上的匹配点对,而是要求与之前所有的测量中所得的标记点存在3组或3组以上的匹配点对即可,此种方法增加了系统测量的灵活性。
采用基于标记点的方法估计出坐标变换参数。首先利用基于定位基准点自适应算法查找至少3对对应点,然后采用四元数法估计变换参数,本文研究并实现了基于标记点的粗配准算法,并用实例进行了实验和验证。
精确配准中,提出一种改进的ICP算法,将粗配准的结果作为精配准的初值,利用k-d树搜索算法确定初始的对应点,然后采用基于预检验的随机抽样一致性算法剔除误匹配点。通过实验证明,该方法在查找初始对应点时大大提高了计算效率,最后的配准精度也有所提高。
As an advanced manufacturing technique, reverse engineering can be applied to product design, development and innovation. Data processing of the point clouds is one of the key technologies in reverse engineering. It's very significant to study on data registration, because the registration accuracy and the number of 3D data point have vital effect on the quality of 3D model reconstruction.3D point clouds registration in reverse engineering are researched in detail in this thesis, which consists of the coarse registration and fine registration.
A rapid method for point clouds registration based on reference points is proposed, which consists of the coarse registration and fine registration. A set of reference points is applied as an assistant utility to measure the object, which is on the surface of the object. The 3D data of the incremental reference points and density point clouds are acquired by a structure light 3D scanner. The advantage of the registration method of incremental point clouds is that the number of corresponding points of the reference points does not be required 3 or above 3 groups between the new measurement and its predecessor, only is required 3 or above 3 groups between the new measurement and before all the times of measurement. This measurement method is very flexible.
In coarse registration, the transformation parameters are estimated by using the reference points only. First, the characteristic of the relative distance between arbitrary two points in the locating points set is used in finding at least three corresponding points. Then, quaternion method is utilized to estimate the transformation parameters. A new coarse registration algorithm based on the reference points is presented and realized.
In fine registration, taking the coarse registration results as the initial value, the improved Interactive Closest Point (ICP) algorithm is used in fine registration. The original corresponding points are established rapidly by using the k-d tree searching algorithm. Finally, Preview Model Parameters Evaluation Random Sample Consensus (PERANSAC) algorithm is utilized to remove outliers. The experimental result shows that this method in finding original corresponding points can greatly improve the computation efficiency and also improve the registration accuracy.
引文
[1]张顺德,卢秉恒,丁玉成.光学三维型面分区域测量数据的拼接研究[J].中国激光,2001,28(6)：533-536.
[2]S.Ranade, A.Rosenfeld. Point pattern matching by relaxation. Pattern recognition,1980, 12(4):268-275.
[3]P.J. Besl, N.D. Mckay. A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14 (2):239-256.
[4]Chen Y, Medioni G. Object modeling by registration of multiple range images[A]. In:Proceeding of the 1991 IEEE International Conference on Robotics and Automation[C], Sacramento, CA,USA,1991:2724-2729.
[5]Silva J, Matabosch C, Fofi D, et al. A review of recent range image registration methods with accuracy evaluation. Image and Vision Computing,2007,25(5):578-596.
[6]朱延娟,周来水,张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学学报,2006,18(4)：475-481.
[7]BalhuaLi, HorstHolsten. Using k-d trees for robust 3D point pattern matching.3D digital image and modeling,2003:95-102.
[8]Sen Wang, Yang Wang.3D surface matching and recognition using conformal geometry. Computer vision and Pattern recognition,2006,2:2453-2460.
[9]张学昌,习俊通,严隽琪.基于扩张高斯球的点云数据与CAD模型的配准[J].机械工程学报,2007,43,142-148.
[10]Chia-Chun Huang. Efficient Digitizing of Sculptured Surfaces Efficient digitizing of sculptured surfaces using wavelet transform.1997.
[11]解则晓,张成国,张国雄.线结构光测量数据的自动拼合方法[J].中国机械工程,2005,16(9)：775-778.
[12]Varady T, Martin R R, Cox J. Reverse engineering of geometric models-an introduction. Computer-Aided Design,1997,29(4):255-268.
[13]Wang G H, Hu Z Y, Wu F C, et al. Implementation and experimental study on fast object modeling based on multiple structured stripes. Optics and Lasers in Engineering,2004, 42(6):627-638.
[14]Zhao HulJlng, Shibaskl Ryosuke. A robust method for registering ground based laser range images of urban outdoor objects[J]. Photogrammetric Engineering & Remote Sensing(S0099-1112).2001,67(10):1143-1153.
[15]Zhao Huijing, Shibasaki Ryosuke. Reconstructing Urban 3D Model using Vehicle-bome Laser Range Scanner[C]. Proc of 3-D Digital Imaging and Modeling,2001,349-356.
[16]周士侃,娄臻亮,舒世湘.基于Atos&Tritop的点云采集方法[J].模具技术,2004,2：51-54.
[17]Kwang-Ho Bae, Derek D. Lichti. A method for automated registration of unorganized point clouds. Journal of Photogrammetry and Remote Sensing,2008,63(1):36-54.
[18]Kwang-Ho Bae, David Belton, Derek D. Lichti. A Closed-Form Expression of the Positional Uncertainty for 3D Point Clouds, IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(4):577-590.
[19]Kwang-Ho Bae. Automated Registration of Unorganized Point Clouds from Terrestrial Laser Scanners. PhD dissertation, Dept. of Spatial Sciences, Curtin Univ. of Technology,2006.
[20]Sharkarji C M. Least-squares fitting algorithms of the NIST algorithm testing system. Journal of Research of the National Institute of Standard and Technology,1998,103(6):633-641.
[21]Huttenlocher D P, Kladerman G A, Ruckijdgew J. Comparing images using the Hausdorff distance[J]. IEEE Transactions on Pattern Analysis and Machines Intelligence,1993,15(9): 850-863.
[22]刘纯国,刘畅,安百玲.基于遗传算法的三维曲面配准[J].计算机应用,2009,110-113.
[23]Lomonosov E, Chetverikov D, Ekart A. Pre-registration of arbitrarily oriented 3D surfaces using a genetic algorithm[J]. Pattern Recognition Letters,2006,27(11):1201-1208.
[24]Sharp G C, Lee SW, Wehe D K. Toward multiview registration in frame space[C]. Wook H K. In IEEE International Conference on Robotics and Automation. Seoul:IEEE,2001:3542-3547.
[25]Pulli K. Multiview registration for large data sets [C]. Marc Rioux. In International Conference on 3D Digital Imaging and Modeling. Ottawa:IEEE Computer Society,1999:160-168.
[26]Sharp G C, Lee S W, Wehe D K. ICP registration using invariant features. IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(1):90-102.
[27]戴静兰,陈志杨,叶修梓.ICP算法在点云配准中的应用[J].中国图象图形学报,2007,12(3)：517-521.
[28]吴禄慎,孔维敬.基于特征点的改进ICP三维点的配准技术[J].南昌大学学报：工科版,2008,30(3)：294-297.
[29]Zexiao Xie, Shang Xu, Xuyong Li. A high-accuracy method for fine registration of overlapping point clouds. Image and Vision Computing,2010,563-570.
[30]徐尚.三维点数据拼接与精简技术的研究.中国海洋大学,2009.
[31]Kase K, Makinouchi A, Nakagawa T, et al. Shape error evaluation method of free-form surfaces. Computer-Aided Design,1999,31(8):495-505.
[32]韦虎,刘胜兰,张丽艳等.双目立体测量系统中的标记点配准算法研究[J].中国机械工程,2009,20(14)：1736-1740.
[33]Rabbani T,Dijkman S,Heuvel F, et al. An integrated approach for modeling and global registration of point clouds. Journal of Photogrammetry and Remote Sensing,2007,61(6):355-370.
[34]朱延娟,周来水,张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学报,2006,18(4)：475-481.
[35]谢光辉,孙军华,杨珍等.一种自由曲面视觉测量三维数据拼接方法[J].北京航空航天大学学报,2009,315(7)：877-890.
[36]孙军华,张广军,魏振忠.基于平面靶标的多视点云对齐方法[J].北京航空航天大学学报,2006,32(10)：1231-1234.
[37]席少霖.非线性最优化方法[M].北京：高等教育出版社,1992.
[38]许晓栋,赵毅,李从心.结构光测量中多视拼合技术与算法实现[J].机床与液压,2005,10：137-140.
[39]Horn B K P. Closed form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America A,1987,4(4):629-642.
[40]Arun K S, Huang T S, Blostein S D. Least-squares fitting of two 3-D point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence,1987,9(5):698-700.
[41]Horn B K P, Hilden H M, Negahdaripour S. Closed form solution of absolute orientation using orthonormal matrices. Journal of the Optical Society of America A,1988,5(7):1127-1135.
[42]Walker M W, Shao L, Volz R A. Estimating 3-D location parameters using dual number quaternions. Computer Vision and Graph Image Processing:Image Understand,1991, 54(3):358-367.
[43]戴静兰,陈志杨,叶修梓.ICP算法在点云配准中的应用[J].中国图像图形学报,2007,12(3)：517-521.
[44]Blais G, LevineM D. Registering multiview range data to create 3D computer graphics [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17 (8):820-824.
[45]Li Q, Griffiths J G. Iterative closest geometric objects registration [J]. Computers and Mathematics with Applications,2000,40 (10):1171-1188.
[46]Pulli, K. Multiview Registration for Large Data Sets [J].3D Digital Imaging and Modeling, 1999:160-168.
[47]Soon-Yong Park, Murail Subbarao. An Accurate and fast Point-to-Plane Registration Technique. Pattern Recognition Letters,2003,24:2967-2976.
[48]C. Mataboscha, D.Fofib, J. Salvia. Registration of surfaces minimizing error propagation for a one-shot multi-slit hand-held scanner. Pattern Recognition,2008,41:2055-2067.
[49]Okatani I S, Deguchi K. A method for fine registration of multiple viewing range images considering the measurement error properties[J]. Computer Vision and Image Understanding. 2002,87(13):66-77.
[50]Pulli, K. Multiview Registration for Large Data Sets[J].3D Digital Imaging and Modeling, 1999:160-168.
[51]Fischler MA, Bolles RC. Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. ACM Transactions on Communication,1981,24(6):381-395.
[52]Rousseeuw PJ. Robust Regression and Outlier Detection. New York:John Wiley & Sons,1987.
[53]Torr PHS, Murray DW. Outlier detection and motion segmentation. SPIE 93,1993:432-443.
[54]Stewart CV. MINPRAN:A new robust operator for computer vision. IEEE Trans. on Pattern Analysis and Machine Intelligence,1995,17(10):925-938.
[55]Torr PHS, Zisserman A. MLESAC:A new robust estimator with application to estimating image geometry. Computer Vision and Image Understand,2000,78:138-156.
[56]吴福朝.计算机视觉中的数学方法.北京：科学出版社,2008.
[57]Chen CS, Hung YP, Cheng JB. RANSAC-Based DARCES:A New Approach to Fast Automatic Registration of Partially Overlapping Range Images. IEEE Transactions on PAMI.1999,21(11): 1229-1234.
[58]刘宇,熊有伦.基于有界k-d树的最近点搜索算法[J].华中科技大学学报,2008,36(7)：73-76.
[2]S.Ranade, A.Rosenfeld. Point pattern matching by relaxation. Pattern recognition,1980, 12(4):268-275.
[3]P.J. Besl, N.D. Mckay. A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14 (2):239-256.
[4]Chen Y, Medioni G. Object modeling by registration of multiple range images[A]. In:Proceeding of the 1991 IEEE International Conference on Robotics and Automation[C], Sacramento, CA,USA,1991:2724-2729.
[5]Silva J, Matabosch C, Fofi D, et al. A review of recent range image registration methods with accuracy evaluation. Image and Vision Computing,2007,25(5):578-596.
[6]朱延娟,周来水,张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学学报,2006,18(4)：475-481.
[7]BalhuaLi, HorstHolsten. Using k-d trees for robust 3D point pattern matching.3D digital image and modeling,2003:95-102.
[8]Sen Wang, Yang Wang.3D surface matching and recognition using conformal geometry. Computer vision and Pattern recognition,2006,2:2453-2460.
[9]张学昌,习俊通,严隽琪.基于扩张高斯球的点云数据与CAD模型的配准[J].机械工程学报,2007,43,142-148.
[10]Chia-Chun Huang. Efficient Digitizing of Sculptured Surfaces Efficient digitizing of sculptured surfaces using wavelet transform.1997.
[11]解则晓,张成国,张国雄.线结构光测量数据的自动拼合方法[J].中国机械工程,2005,16(9)：775-778.
[12]Varady T, Martin R R, Cox J. Reverse engineering of geometric models-an introduction. Computer-Aided Design,1997,29(4):255-268.
[13]Wang G H, Hu Z Y, Wu F C, et al. Implementation and experimental study on fast object modeling based on multiple structured stripes. Optics and Lasers in Engineering,2004, 42(6):627-638.
[14]Zhao HulJlng, Shibaskl Ryosuke. A robust method for registering ground based laser range images of urban outdoor objects[J]. Photogrammetric Engineering & Remote Sensing(S0099-1112).2001,67(10):1143-1153.
[15]Zhao Huijing, Shibasaki Ryosuke. Reconstructing Urban 3D Model using Vehicle-bome Laser Range Scanner[C]. Proc of 3-D Digital Imaging and Modeling,2001,349-356.
[16]周士侃,娄臻亮,舒世湘.基于Atos&Tritop的点云采集方法[J].模具技术,2004,2：51-54.
[17]Kwang-Ho Bae, Derek D. Lichti. A method for automated registration of unorganized point clouds. Journal of Photogrammetry and Remote Sensing,2008,63(1):36-54.
[18]Kwang-Ho Bae, David Belton, Derek D. Lichti. A Closed-Form Expression of the Positional Uncertainty for 3D Point Clouds, IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(4):577-590.
[19]Kwang-Ho Bae. Automated Registration of Unorganized Point Clouds from Terrestrial Laser Scanners. PhD dissertation, Dept. of Spatial Sciences, Curtin Univ. of Technology,2006.
[20]Sharkarji C M. Least-squares fitting algorithms of the NIST algorithm testing system. Journal of Research of the National Institute of Standard and Technology,1998,103(6):633-641.
[21]Huttenlocher D P, Kladerman G A, Ruckijdgew J. Comparing images using the Hausdorff distance[J]. IEEE Transactions on Pattern Analysis and Machines Intelligence,1993,15(9): 850-863.
[22]刘纯国,刘畅,安百玲.基于遗传算法的三维曲面配准[J].计算机应用,2009,110-113.
[23]Lomonosov E, Chetverikov D, Ekart A. Pre-registration of arbitrarily oriented 3D surfaces using a genetic algorithm[J]. Pattern Recognition Letters,2006,27(11):1201-1208.
[24]Sharp G C, Lee SW, Wehe D K. Toward multiview registration in frame space[C]. Wook H K. In IEEE International Conference on Robotics and Automation. Seoul:IEEE,2001:3542-3547.
[25]Pulli K. Multiview registration for large data sets [C]. Marc Rioux. In International Conference on 3D Digital Imaging and Modeling. Ottawa:IEEE Computer Society,1999:160-168.
[26]Sharp G C, Lee S W, Wehe D K. ICP registration using invariant features. IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(1):90-102.
[27]戴静兰,陈志杨,叶修梓.ICP算法在点云配准中的应用[J].中国图象图形学报,2007,12(3)：517-521.
[28]吴禄慎,孔维敬.基于特征点的改进ICP三维点的配准技术[J].南昌大学学报：工科版,2008,30(3)：294-297.
[29]Zexiao Xie, Shang Xu, Xuyong Li. A high-accuracy method for fine registration of overlapping point clouds. Image and Vision Computing,2010,563-570.
[30]徐尚.三维点数据拼接与精简技术的研究.中国海洋大学,2009.
[31]Kase K, Makinouchi A, Nakagawa T, et al. Shape error evaluation method of free-form surfaces. Computer-Aided Design,1999,31(8):495-505.
[32]韦虎,刘胜兰,张丽艳等.双目立体测量系统中的标记点配准算法研究[J].中国机械工程,2009,20(14)：1736-1740.
[33]Rabbani T,Dijkman S,Heuvel F, et al. An integrated approach for modeling and global registration of point clouds. Journal of Photogrammetry and Remote Sensing,2007,61(6):355-370.
[34]朱延娟,周来水,张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学报,2006,18(4)：475-481.
[35]谢光辉,孙军华,杨珍等.一种自由曲面视觉测量三维数据拼接方法[J].北京航空航天大学学报,2009,315(7)：877-890.
[36]孙军华,张广军,魏振忠.基于平面靶标的多视点云对齐方法[J].北京航空航天大学学报,2006,32(10)：1231-1234.
[37]席少霖.非线性最优化方法[M].北京：高等教育出版社,1992.
[38]许晓栋,赵毅,李从心.结构光测量中多视拼合技术与算法实现[J].机床与液压,2005,10：137-140.
[39]Horn B K P. Closed form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America A,1987,4(4):629-642.
[40]Arun K S, Huang T S, Blostein S D. Least-squares fitting of two 3-D point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence,1987,9(5):698-700.
[41]Horn B K P, Hilden H M, Negahdaripour S. Closed form solution of absolute orientation using orthonormal matrices. Journal of the Optical Society of America A,1988,5(7):1127-1135.
[42]Walker M W, Shao L, Volz R A. Estimating 3-D location parameters using dual number quaternions. Computer Vision and Graph Image Processing:Image Understand,1991, 54(3):358-367.
[43]戴静兰,陈志杨,叶修梓.ICP算法在点云配准中的应用[J].中国图像图形学报,2007,12(3)：517-521.
[44]Blais G, LevineM D. Registering multiview range data to create 3D computer graphics [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17 (8):820-824.
[45]Li Q, Griffiths J G. Iterative closest geometric objects registration [J]. Computers and Mathematics with Applications,2000,40 (10):1171-1188.
[46]Pulli, K. Multiview Registration for Large Data Sets [J].3D Digital Imaging and Modeling, 1999:160-168.
[47]Soon-Yong Park, Murail Subbarao. An Accurate and fast Point-to-Plane Registration Technique. Pattern Recognition Letters,2003,24:2967-2976.
[48]C. Mataboscha, D.Fofib, J. Salvia. Registration of surfaces minimizing error propagation for a one-shot multi-slit hand-held scanner. Pattern Recognition,2008,41:2055-2067.
[49]Okatani I S, Deguchi K. A method for fine registration of multiple viewing range images considering the measurement error properties[J]. Computer Vision and Image Understanding. 2002,87(13):66-77.
[50]Pulli, K. Multiview Registration for Large Data Sets[J].3D Digital Imaging and Modeling, 1999:160-168.
[51]Fischler MA, Bolles RC. Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. ACM Transactions on Communication,1981,24(6):381-395.
[52]Rousseeuw PJ. Robust Regression and Outlier Detection. New York:John Wiley & Sons,1987.
[53]Torr PHS, Murray DW. Outlier detection and motion segmentation. SPIE 93,1993:432-443.
[54]Stewart CV. MINPRAN:A new robust operator for computer vision. IEEE Trans. on Pattern Analysis and Machine Intelligence,1995,17(10):925-938.
[55]Torr PHS, Zisserman A. MLESAC:A new robust estimator with application to estimating image geometry. Computer Vision and Image Understand,2000,78:138-156.
[56]吴福朝.计算机视觉中的数学方法.北京：科学出版社,2008.
[57]Chen CS, Hung YP, Cheng JB. RANSAC-Based DARCES:A New Approach to Fast Automatic Registration of Partially Overlapping Range Images. IEEE Transactions on PAMI.1999,21(11): 1229-1234.
[58]刘宇,熊有伦.基于有界k-d树的最近点搜索算法[J].华中科技大学学报,2008,36(7)：73-76.