DEM Co-registration Algorithm Based on Gauss-Newton Method
ZHANG Tonggang1,2, WANG Kunlun3, JIN Guoqing4
1. Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 610031, China;
2. State-Province Joint Engineering Laboratory in Spatial Information Technology for High-Speed Railway Safety, Southwest Jiaotong University, Chengdu 610031, China;
3. Sichuan Water Conservancy and Hydropower Survey and Design Research Institute, Chengdu 610072, China;
4. China Railway Fifth Survey and Design Institute Group Co., Ltd., Beijing 102600, China
To improve the efficiency of DEM (digital elevation model) co-registration, a fast algorithm based on Gauss-Newton method was proposed. This algorithm uses Gauss-Newton method instead of the least squares method, to solve the objective equation of the DEM co-registration model, and greatly accelerates the iterative convergence. During the iterations of the new algorithm, matching parameters approach the target values by following the direction of maximal gradient, which significantly reduces the number of iterations. Moreover, the iterative convergence is more stable and the algorithm operation efficiency is greatly enhanced. The new algorithm was tested with several groups of simulated datasets, and compared with the representative iterative closest points (ICP) algorithm. The experimental results show that the average convergence rate of the proposed algorithm is improved by 42.1%, and the computation time for matching is reduced by about 74.9%.
张同刚, 王昆仑, 金国清. 基于高斯牛顿法的DEM匹配算法[J]. 西南交通大学学报, 2017, 52(3): 584-592.
ZHANG Tonggang, WANG Kunlun, JIN Guoqing. DEM Co-registration Algorithm Based on Gauss-Newton Method. Journal of SouthWest JiaoTong University, 2017, 52(3): 584-592.
李彩林,郭宝云,季铮. 多视角三维激光点云全局优化整体配准算法[J]. 测绘学报,2015,44(2): 183-189. LI Cailin, GUO Baoyun, JI Zheng. Global optimization and whole registration algorithm of multi-view 3D laser point cloud[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(2): 183-189.
[2]
周朗明,郑顺义,黄荣永. 旋转平台点云数据的配准方法[J]. 测绘学报,2013,42(1): 73-79. ZHOU Langming, ZHENG Shunyi, HUANG Rongyong. A registration algorithm for point clouds obtained by scanning objects on turntable[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(1): 73-79.
[3]
DAWN S, SAXENA V, SHARMA B D. A novel non-rigid free-form deformation for consistent registration of digital elevation models[C]//Proceedings of the 2014 Indian Conference on Computer Vision Graphics and Image Processing. Bangalore: ACM, 2014: 49.
[4]
DAWN S, SAXENA V, SHARMA B D. Advanced free-form deformation and kullback-lieblier divergence measure for digital elevation model registration[J]. Signal, Image and Video Processing, 2015, 9(7): 1625-1635.
[5]
NOH M J, HOWAT I M. Automated coregistration of repeat digital elevation models for surface elevation change measurement using geometric constraints[J]. IEEE Trans. Geosci. Remote Sens, 2014, 52(4): 2247-2260.
[6]
张同刚,岑敏仪,冯义从,等. 采用截尾最小二乘估计的DEM匹配方法[J]. 测绘学报,2009,38(2): 144-151. ZHANG Tonggang, CEN Minyi, FENG Yicong, et al. DEM matching algorithm using least trimmed squares estimator[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2): 144-151.
[7]
千木良雅弘. 大型深层滑坡灾害及其预测[J]. 西南交通大学学报,2016,51(5): 981-986,944. CHIGIRA M. Disasters caused by deep seated catastrophic landslides and prediction of their potential sites[J]. Journal of Southwest Jiaotong University, 2016, 51(5): 981-986,944.
[8]
ZHANG Tonggang, CEN Minyi, REN Zizhen. A novel method for improved DEM deformation detection[J]. European Journal of Remote Sensing, 2015, 48: 71-84.
[9]
ZHANG Tonggang, CEN Minyi. Robust DEM co-registration method for terrain changes assessment using least trimmed squares estimator[J]. Advances in Space Research, 2008, 41(11): 1827-1835.
[10]
ZHANG Zhengyou. Iterative point matching for registration of free-form curves and surfaces[J].International Journal of Computer Vision, 1994, 13(2): 119-152.
[11]
BESL P J, McKAY N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.
[12]
CHEN Yang, MEDIONI G. Object modelling by registration of multiple range images[J]. Image and Vision Computing, 1992, 10(3): 145-155.
[13]
ZHU Liang, BARHAK J, SRIVATSAN V, et al. Efficient registration for precision inspection of free-form surfaces[J]. International Journal of Advanced Manufacturing Technology, 2007, 32(5/6): 505-515.
戴静兰,陈志杨,叶修梓. ICP 算法在点云配准中的应用[J]. 中国图象图形学报,2007,12(3): 517-521. DAI Jinglan, CHEN Zhiyang, YE Xiuzi. The application of ICP algorithm in point cloud alignment[J]. Journal of Image and Graphics, 2007, 12(3): 517-521.
[16]
RUSINKIEWICZ S, LEVOY M. Efficient variants of the ICP algorithm[C]//Proceedings of the 3rd International Conference on 3D Digital Imaging and Modeling. Quebec City:[s.n.], 2001: 145-152.
[17]
韦盛斌,王少卿,周常河,等. 用于三维重建的点云单应性迭代最近点配准算法[J]. 光学学报,2015,35(5): 252-258. WEI Shengbin, WANG Shaoqing, ZHOU Changhe, et al. An iterative closest point algorithm based on biunique correspondence of point clouds for 3D reconstruction[J]. Acta Optica Sinica, 2015, 35(5): 252-258.
[18]
张同刚,岑敏仪,吴兴华. 无控制DEM匹配的最小法向距离算法[J]. 自然科学进展,2006,16(7): 868-873. ZHANG Tonggang, CEN Minyi, WU Xinghua. Least normal distance algorithm for DEM matching[J]. Progress in Natural Science, 2006, 16(7): 868-873.
[19]
JIANG Tianzi, FAN Yong. Parallel genetic algorithm for 3D medical image analysis[C]//2002 IEEE International Conference on Systems, Man and Cybernetics.[S.l.]: IEEE, 2002: 1-6.
[20]
ROBERTSON C, FISHER R B. Parallel evolutionary registration of range data[J]. Computer Vision and Image Understanding, 2002, 87(1): 39-50.
[21]
左志权,刘正军,张力. 基于一阶展开多项式快速趋近的非线性 ICP 配准理论模型[J]. 北京大学学报:自然科学版,2013,49(5): 867-872. ZUO Zhiquan, LIU Zhengjun, ZHANG Li. Theoretical model of non-linear ICP co-registration based on fast approximation of 1st polynomials extension[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2013, 49(5): 867-872
[22]
ZUO Zhiquan, LIU Zhengjun, ZHANG Li. Generic mathematical model of least squares three-dimensional surface matching and its application on strip adjustment of airborne LIDAR data[J]. International Journal of Remote Sensing, 2013, 17(6): 1546-1558.
[23]
SILÜA L, BELLON O R P, BOYER K L. Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(5): 762-776.
[24]
SILÜA L, BELLON O R P, GOTARDO P F U, et al. Range image registration using enhanced genetic algorithms[C]//Proceedings 2003 International Conference on Image Processing.[S.l.]: IEEE, 2003. DOI: 10.1109/ICIP.2003.1246779.
[25]
SILÜA L, BELLON O R P, BOYER K L. Enhanced, robust genetic algorithms for multiview range image registration[C]//Proceedings Fourth International Conference on 3-D Digital Imaging and Modeling, 2003.[S.l.]: IEEE, 2003: 268-275.
[26]
郭慧,潘家祯,林大钧. 基于实数编码的多种群遗传算法的点云配准[J]. 华东理工大学学报:自然科学版,2007,33(5): 733-736. GUO Hui, PAN Jiazhen, LIN Dajun. Registration of point cloud data of multi-population genetic algorithm based on real coding[J]. Journal of East China University of Science and Technology: Natural Science Edition, 2007, 33(5): 733-736.
[27]
HERNANDEZ M. Gauss-Newton inspired preconditioned optimization in large deformation diffeomorphic metric mapping[J]. Physics in Medicine and Biology, 2014, 59(20): 6085-6115.
[28]
邓兴升,孙虹虹,汤仲安. 高斯牛顿迭代法解算非线性 Bursa-Wolf 模型的精度分析[J]. 测绘科学,2014,39(5): 93-95. DENG Xingsheng, SUN Honghong, TANG Zhongan. Precision of Gauss-Newton iterative algorithm for solving nonlinear Bursa-Wolf mode[J]. Science of Surveying and Mapping, 2014, 39(5): 93-95.
[29]
ARGYROS I K, HILOUT S. On the Gauss-Newton method[J]. Journal of Applied Mathematics & Computing, 2011, 35(1): 537-550.
[30]
MUÑZ E, MÁQUEZ-NEILA P, BAUMELA L. Rationalizing efficient compositional image alignment[J]. International Journal of Computer Vision, 2015, 112(3): 354-372.
[31]
EBRAHIMI M, LAUSCH A, MARTEL A L. A Gauss-Newton approach to joint image registration and intensity correction[J]. Computer Methods and Programs in Biomedicine, 2013, 112(3): 398-406.
[32]
JALLOUL M, BAYDOUN M, AL-ALAOUI M A. Gauss-Newton image registration with CUDA[C]//18th IEEE International Conference on Electronics, Circuits, and Systems. Lebanon: IEEE, 2011: 305-309.
[33]
TUCKER T M, KURFESS T R. Newton methods for parametric surface registration, part Ⅱ: experimental validation[J]. Computer-Aided Design, 2003, 35(1): 115-120.
[34]
范东明. 非线性最小二乘参数平差的非线性规划算法研究[J]. 西南交通大学学报,2001,36(5): 476-480. FAN Dongming. Nonlinear programming algorithms for nonlinear least squares adjustment by parameters[J]. Journal of Southwest Jiaotong University, 2001, 36(5): 476-480.
