基于高斯牛顿法的dem匹配算法-张同刚.pdf

《基于高斯牛顿法的dem匹配算法-张同刚.pdf》由会员分享，可在线阅读，更多相关《基于高斯牛顿法的dem匹配算法-张同刚.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第52卷第3期2017年6月西南交通大学学报JOURNAL OF SOUTHWEST JIAOTONG UNIVERSITYV0152 No3Jun2017文章编号：0258-2724(2017)03-0584-09 IN)I：103969jissn0258-2724201703020基于高斯牛顿法的DEM匹配算法张同刚1”， 王昆仑3， 金国清4(1西南交通大学地球科学与环境工程学院，四川成都610031；2西南交通大学高速铁路运营安全空间信息技术国家地方联合工程实验室，四川成都610031；3四川省水利水电勘测设计研究院，四川成都610072；4中铁第五勘测设计院集团有限公司，北京1026

2、00)摘要：为提升DEM(digital elevation model)匹配效率，建立了一种基于高斯牛顿法的快速DEM匹配算法该算法采用高斯牛顿法替代最小二乘法来进行DEM匹配模型的目标方程求解，加速了目标方程求解的迭代过程新算法匹配过程中，匹配参数沿梯度最大方向逼近目标值，迭代次数大幅度减少，具有更稳定的迭代收敛性，显著提高了算法的执行效率通过多组模拟试验对新算法进行了测试，并与具有代表性的最近点迭代算法进行了比较结果表明：新算法对匹配参数的收敛速率平均提高了421，完成匹配所需的总时间平均减少了749关键词：DEM匹配；算法；高斯牛顿法；迭代收敛性；执行效率中图分类号：P2251 文献标

3、志码：ADEM Co-registration Algorithm Based on GaussNewton MethodZHANG Tonggan91”， WANG Kunlun3，JIN Guoqin94(1Faculty of Geosciences and Environmental EngineeringSouthwest Jiaotong University，Chengdu 610031，China；2StateProvince Joint Engineering Laboratory in Spatial Information Technology for HighSpeed

4、 Railway Safety，Southwest Jiaotong University，Chengdu 610031，China；3Sichuan Water Conservancy and Hydropower Survey andDesign Research Institute，Chengdu 610072，China；4China Railway Fifth Survey and Design Institute Group Co，Ltd，Beijing 102600，China)Abstract：To improve the efficiency of DEM(digital e

5、levation model)coregistration，a fast algorithmbased on GaussNewton method was proposedThis algorithm uses GaussNewton method instead of theleast squares method，to solve the objective equation of the DEM coregistration model，and greatlyaccelerates the iterative convergenceDuring the iterations of the

6、 new algorithm，matching parametersapproach the target values by following the direction of maximal gradient，which significantly reducesthe number of iterationsMoreover，the iterative convergence is more stable and the algorithmoperation efficiency is greatly enhancedThe new algorithm was tested with

7、several groups of simulateddatasets，and compared with the representative iterative closest points(ICP)algorithmTheexperimentM results show that the average convergence rate of the proposed algorithm is improved by421and the computation time for matching is reduced by about 749Key words：DEM coregistr

8、ation；algorithm；GaussNewton method；convergence rate；performanceefficiency收稿日期：2016-03-02基金项目：长江学者和创新团队发展计划资助项目(IRTl3092)作者简介：张同刚(1977一)，男，副教授，博士，研究方向为无控制点DEM表面匹配及差异探测、三维激光雷达数据处理、高速铁路精密测量技术，E-mail：swjtuztgfoxmailcorn引文格式：张同刚，王昆仑，金国清基于高斯牛顿法的DEM匹配算法J西南交通大学学报，2017，52(3)：584-592ZHANG Tonggang，WANG Kunlun

9、，JIN Guoqing，et a1DEM coregistration algorithm based OU GaussNewton methodJJournalof Southwest Jiaotong University，2017，52(3)：584-592万方数据第3期 张同刚，等：基于高斯牛顿法的DEM匹配算法 585激光扫描技术迅速发展，在诸多领域u刮得以应用，获取的同一地区不同时间的DEM(digitalelevation model)精度和效率也均得到了大幅度提高，通过DEM匹配技术可以对不同时期DEM分析，确定相应时间范围内如冰川3-4、滑坡7 o等地质灾害引起的地面变化幅

10、度和范围目前，无控制点DEM匹配技术是基于刚体转换模型，并采用最小二乘技术，通过多次迭代求解表面之间的转换参数，从而将不同时期DEM纳入统一的坐标系统旧圳的，其中最具代表性的算法是最近点迭代(iterative closest point，icP)算法”“1随着DEM空间和时间分辨率越来越高，其包含的数据量也随之越来越大，对多时相DEM分析过程中匹配算法的效率提出了很高的要求根据DEM匹配模型的理论分析，其中耗时较多的步骤是对应关系的建立和匹配参数求解的过程目前的研究主要从这二者出发对DEM匹配算法进行优化第一类算法主要侧重对构建对应关系的过程进行优化(1)通过提高对应点搜索效率来改善匹配算法

11、效率在搜索对应点过程中引入附加条件，从而提高对应点搜索效率Zhu等。1副提出采用近似最近节点与邻近拓扑曲面相结合的原则来加快对应点的搜索；徐万鑫等1141和戴静兰等纠提出采用KD树和曲率特征点相结合的方式加速对应点搜索这些方法对匹配算法效率有一定的改善(2)改进对应关系的构建策略Rusinkiewicz等叫和韦盛斌等刊提出在匹配过程中以点到面最近建立对应；张同刚等副提出了法向距离最近的对应准则，可以提高迭代收敛性第二类主要是改善匹配参数求解的效率(1)采用并行计算来提高算法效率Jiang等纠和Robertson等3在三维影像配准中均采用并行遗传算法来提高匹配速度，但精度低(2)通过采用不同的参

12、数优化方法来提高匹配效率左志权等心m21提出按非线性最小二乘匹配模型进行匹配参数优化，虽然这些算法的迭代收敛性有所改善，但单次迭代的运算效率低，对整个匹配过程的效率改善不显著；Silva等旧埘。提出在三维序列影像匹配过程中采用遗传算法进行参数优化，并引入爬山策略以加快收敛，但此算法只顾及了旋转变化；郭慧等心刮提出适用于点云配准的基于多种群遗传算法，该方法虽提高了匹配效率，但该算法只是提供初始匹配，后续还需采用ICP算法进行精匹配高斯牛顿法具有收敛速度快、迭代次数少等心7伪1优点，从而能够加速DEM匹配参数求解过程，进而可以提升算法的执行效率该方法已经在影像匹配30别和参数表面匹配1中得到了一些

13、应用，显著改善了匹配效率本文根据DEM数据的特点，推导了高斯牛顿法迭代形式中的梯度函数，替代通常的最小二乘技术来完成DEM匹配参数的求解，建立了基于高斯牛顿法的DEM匹配算法(DEM matching algorithm using GaussNewtonmethod，MGNM)通过多组模拟试验对MGNM算法进行测试，并和基于最小二乘技术的最近点迭代(ICP)算法进行比较1 基于高斯牛顿法的DEM匹配算法原理11匹配算法基于高斯牛顿法的DEM匹配算法的主要过程如下：(1)建立表面间的对应关系后，根据七参数空间刚体转换模型建立匹配目标函数，如式(1)以Q)=lIm墨p。+，一叠i112， (1)

14、式中：g。=菇i。 Yi。 。为基准DEM上任意一点；pi=x中 Y妒三咖r为q。在待匹配DEM上的对应点；2=9，(t。t，t： mT为转换参数；m为比例缩放因子；T=t。t，t：1为3个frn12 1s坐标轴的平移向量；R=J r：。r：r：。J为对应于L_r，。 r，： r，j3个坐标轴旋转参数(IJ、9、，c的旋转矩阵(2)将式(1)在俄处按泰勒公式展开，并略去二阶及其高次项，得以lf2)可1时迭代发散；当C1时迭代收敛，且C值越小，迭代收敛越快MGNM算法和ICP算法进行匹配迭代过程中收敛速率(CR。和C)的变化曲线分别如图3和图4所示从图3和图4中可以看出，3组试验中迭代收敛速率(

15、c。和C)的变化趋势基本一致，在整个迭代过程中，ICP算法对旋转参数和平移参数的迭代收敛速率随着迭代的进行变化显著，而MGNM算法的c。和c均保持在05附近MGNM算法迭代收敛速率稳定快速的原因在于匹配过程中，当匹配参数的迭代初始值未充分接近参数的平差值时，仍然可以在参数空间中沿着梯度最大的方向逐渐靠近目标值(见图5)，而在相同条件下采用最小二乘既不能快速收敛到极值，同时还容易受由线性近似产生的模型误差影响m万方数据第3期 张同刚，等：基于高斯牛顿法的DEM匹配算法 589(a)DEM 1迭代次数次(b)DEM 2一蕾GNM ICP图3 匹配过程中旋转参数迭代收敛速率变化曲线Fig3 Curv

16、e of the convergence rate of rotation parameters during iteration(C)DEM 3(a)DEM 1 (b)DEM 2 (c)DEM 3一【GNM ICP图4匹配过程中平移参数迭代收敛速率变化曲线Fig4 Curve of the convergence rate of translation parameters during iteration注：o一转换参数的目标值；n。一第i次迭代之后所求得的转换参数图5 匹配参数的收敛轨迹Fig5 Track of the coregistration parametersICP算法对迭代

17、收敛速率(c。和C)在迭代初期略小于1，迭代收敛速率很慢，到迭代末期c值迅速减小到略大于O5，迭代收敛速率加快，直到匹配完成在迭代末期迭代收敛速率慢于MGNM算法由于MGNM算法迭代收敛速率较快，并且比较稳定，因而其完成DEM匹配所需的迭代次数显著小于ICP算法242平均收敛速率迭代过程中所有C的平均值称为平均收敛速率A，i iCRot(m) c(m)钆t=盟丁，ATra。=盟了j一(8)C给出了迭代过程中每一次迭代收敛快慢的详细信息，而A则是评价整体迭代过程快慢的指标3组DEM试验中两种匹配算法的平均收敛速率(AR。和A，。)在图6中给出从图6来看，无论是旋转参数A。还是平移参数A，MGNM

18、算法的均比ICP算法的小，这表明MGNM算法整体迭代收敛速率优于ICP算法，MGNM算法旋转参数和平移参数的迭代收敛速率比ICP算法平均改善了421综合迭代收敛速率和平均收敛速率两方面的影响，MGNM算法的迭代收敛性显著优于ICP算法25执行效率匹配算法的执行效率用完成匹配所消耗的时万方数据590 西 南 交 通 大 学 学 报 第52卷间来衡量DEM匹配算法消耗的时间主要在匹配表面间对应关系的建立和转换参数的迭代计算步骤上试验执行环境为Inter Core(TM)i3-2350M，CUP230 GHz，40 GB内存1。8O6毒04。200DEMl DEM 2 DEM3DEM(a)旋转参数平

19、均迭代收敛速率10O806l弋 O4O2001)EMl DEM 2 DEM 3DEM(b)平移参数平均迭代收敛速率图6两种匹配算法的转换参数平均迭代收敛速率Fig6 Average convergence rate ofthe transformation parameters oftwo DEM COregistration algorithms为了便于比较，引入高斯牛顿法来改善转换参数求解过程对算法效率的影响，两种DEM匹配算法采用相同的对应准则来建立DEM表面对应关系在试验过程中，分别统计两个方法每次迭代消耗的时间，完成匹配过程中每次迭代消耗的平均时间和迭代次数列于表4表4两种匹配算法的

20、迭代求解过程消耗的平均时间和迭代次数Tab4 Mean time and number ofiterations of two algorithms由表4可以看出，每次迭代过程中高斯牛顿法求解转换参数耗费的时间远小于ICP算法采用的最小二乘技术，所需时间平均为后者的056MGNM算法完成匹配所需迭代次数比ICP算法平均减少了756综合考虑每次迭代时间和迭代次数等二个方面，MGNM算法完成执行效率显著优于ICP算法，完成匹配的总时间比ICP算法平均减少了7493 结 论本文提出了DEM匹配的高斯牛顿算法，引人高斯牛顿法替代传统最dx-乘技术求解DEM匹配模型中的转换参数通过模拟试验，从匹配精度、

21、拉人范围、迭代收敛性和执行效率等4方面对算法性能进行测试，并与具有代表性的最dx-乘DEM匹配算法ICP算法进行了比较MGNM算法能够正确完成DEM匹配，其匹配精度略优于ICP算法，拉入范围明显大于ICP算法MGNM算法对旋转参数的拉入范围平均提高了26倍，对平移参数的拉人范围平均提高了33倍MGNM算法的迭代收敛性和执行效率有了显著改善，与ICP算法相比，收敛速率平均提高了421，完成匹配所需的总时间平均减少了749参考文献：1 李彩林，郭宝云，季铮多视角三维激光点云全局优化整体配准算法J测绘学报，2015，44(2)：183189LI Cailin，GUO Baoyun，JI ZhengG

22、lobal optimizationand whole registration algorithm of multi-view 3D laserpoint cloudJActa Geodaetica et CartographicaSinica，2015，44(2)：1831892 周朗明，郑顺义，黄荣永旋转平台点云数据的配准方法J测绘学报，2013，42(1)：73-79ZHOU Langming，ZHENG Shunyi，HUANG RongyongA registration algorithm for point clouds obtained byscanning objects

23、On turntableJActa Geodaetica etCartographiea Sinica，2013，42(1)：73-793DAWN S，SAXENA V，SHARMA B DA novel non-rigid free-form deformation for consistent registration ofdigital elevation modelsCProceedings of the 2014Indian Conference on Computer Vision Graphics andImage ProcessingBangalore：ACM，2014：494

24、DAWN S，SAXENA V，SHARMA B DAdvanced free-form deformation and kuHbacklieblier divergencemeasure for digital elevation model registrationJSignal，Image and Video Processing，2015，9(7)：】6251635万方数据第3期 张同刚，等：基于高斯牛顿法的DEM匹配算法 5915 NOH M J，HOWAT 1 MAutomated coregistration ofrepeat digital elevation models f

25、or surface elevationchange measurement using geometric constraintsJIEEE TransGeosciRemote Sens，2014，52(4)：224722606 张同刚，岑敏仪，冯义从，等采用截尾最小二乘估计的DEM匹配方法J测绘学报，2009，38(2)：144151ZHANG Tonggang，CEN Minyi，FENG Yicong，et a1DEM matching algorithm using least trimmed squaresestimatorJActa Geodaetica et Cartograp

26、hica Sinica，2009，38(2)：1441517千木良雅弘大型深层滑坡灾害及其预测J西南交通大学学报，2016，51(5)：981-986，944，CHIGIRA MDisasters caused by deep seatedcatastrophic landslides and prediction of their potentialsitesJJournal of Southwest Jiaotong University，2016，51(5)：981-986，9448 ZHANG Tonggang，CEN Minyi，REN ZizhenA novelmethod for

27、 improved DEM deformation detectionjEuropean Journal of Remote Sensing，2015，48：71-849 ZHANG Tong,gang，CEN MinyiRobust DEM coregistration method for terrain changes assessment usingleast trimmed squares estimatorJAdvances in SpaceResearch，2008，41(11)：1827183510 ZHANG Zhengyou terative point matching

28、forregistration of freeform curves and surfacesJInternational Journal of Computer Vision，1994，13(2)：119-15211BESL P J，McKAY N DA method for registration of3一D shapesJIEEE Transactions on Pattern Analysisand Machine Intelligence，1992，14(2)：239-25612CHEN Yang，MEDIONI GObject modelling byregistration o

29、f multiple range imagesJImage andVision Computing，1992，10(3)：14515513ZHU Liang，BARHAK J，SRIVATSAN V，et a1Efficient registration for precision inspection of freeform surfacesJInternational Journal of AdvancedManufacturing Technology，2007，32(56)：505-515。14 徐万鑫，许宏丽改进的ICP算法在点云配准中的应用C第14届中国系统仿真技术及其应用学术年会

30、三亚：出版者不详，2012：205-20815戴静兰，陈志杨，叶修梓ICP算法在点云配准中的应用J中国图象图形学报，2007，12(3)：517-521DAI Jinglan，CHEN Zhiyang，YE XiuziTheapplication of ICP algorithm in point cloudalignment【JJournal of Image and Graphics，2007，12(3)：51752116 RUSINKIEWICZ S，LEVOY MEfficient variants ofthe ICP algorithmCProceedings of the 3rdI

31、nternational Conference on 3 D Digital Imaging andModelingQuebec City：sn，2001：145-15217 韦盛斌，王少卿，周常河，等用于三维重建的点云单应性迭代最近点配准算法J光学学报，2015，35(5)：252-258WEI Shengbin，WANG Shaoqing，ZHOU Changhe，et a1An iterative closest point algorithm based onbiunique correspondence of point clouds for 3DreconstructionJAct

32、a Optica Sinica，2015，35(5)：252-25818 张同刚，岑敏仪，吴兴华无控制DEM匹配的最小法向距离算法J自然科学进展，2006，16(7)：868873ZHANG Tonggang，CEN Minyi，WU XinghHaLeastnormal distance algorithm for DEM matchingJProgress in Natural Science，2006，16(7)：868-87319JIANG Tianzi，FAN YongParallel genetic algorithmfor 3D medical image analysisC20

33、02 IEEEInternational Conference on Systems， Man andCyberneticsS1：IEEE，2002：1-620 ROBERTSON C，FISHER R BParallel evolutionaryregistration of range dataJComputer Vision andImage Understanding，2002，87(1)：39-5021 左志权，刘正军，张力基于一阶展开多项式快速趋近的非线性ICP配准理论模型J北京大学学报：自然科学版，2013，49(5)：867872ZUO Zhiquan，LIU Zhengjun

34、，ZHANG LiTheoreticalmodel of non-linear ICP co-registration based on fastapproximation of 1 st polynomials extensionJActaScientiarum Naturalium Universitatis Pekinensis，2013，49(5)：867-87222ZUO Zhiquan，LIU Zhengjun，ZHANG LiGenericmathematical model of least squares threedimensionalsurface matching an

35、d its application on strip adjustmentof airborne LIDAR dataJInternational Journal ofRemote Sensing，2013，17(6)：1546155823SILVA L，BELLON O R P，BOYER K LPrecisionrange image registration using a robust surfaceinterpenetration measure and enhanced geneticalgorithmsJIEEE Transactions on Pattern Analysisa

36、nd Machine Intelligence，2005，27(5)：762-77624SILVA L，BELLON O R P，GOTARDO P F U，et a1Range image registration using enhanced geneticalgorithmsCProceedings 2003 International万方数据592 西 南 交 通 大 学 学 报 第52卷2526272829Conference on Image Processings1：IEEE，2003DOI：101 109ICIP20031246779SILVA L，BELLON O R P，B

37、OYER K LEnhanced，robust genetic algorithms for muhiview range imageregistrationCProceedings Fourth InternationalConference on 3-D Digital Imaging and Modeling，2003s1：IEEE，2003：268-275郭慧，潘家祯，林大钧基于实数编码的多种群遗传算法的点云配准J华东理工大学学报：自然科学版，2007，33(5)：733-736GUO Hui，PAN Jiazhen，LIN DajunRegistration ofpoint clou

38、d data of multipopulation genetic algorithmbased on real codingJJournal of East ChinaUniversity of Science and Technology：Natural ScienceEdition，2007，33(5)：733-736HERNANDEZ M Gauss-Newton inspiredpreconditioned optimization in large deformationdiffeomorphic metric mappingJPhysics in Medicineand Biol

39、ogy，2014，59(20)：6085-6115邓兴升，孙虹虹，汤仲安高斯牛顿迭代法解算非线性Bursa-Wolf模型的精度分析J测绘科学，2014，39(5)：93-95DENG Xingsheng，SUN Honghong，TANG ZhonganPrecision of GaussNewton iterative algorithm forsolving nonlinear Bursawolf modeJScience ofSurveying and Mapping，2014，39(5)：93-95ARGYROS I KHILOUT SOn the GaussNewtonmethodJ

40、Journal of Applied Mathematics&3031323334Computing，2011，35(1)：537-550MUNZ E，MAQUEZNEILA P，BAUMELA LRationalizing efficient compositional imagealignmentJInternational Journal of ComputerVision，2015，112(3)：354-372EBRAHIMI M，LAUSCH A，MARTEL A LA Gauss-Newton approach to joint image registration andinte

41、nsity correctionJ Computer Methods andPrograms in Biomedicine，2013，112(3)：398-406JALLOUL M。BAYDOUN M，AL-ALAOUI M AGauss-Newton image registration with CUDAC1 8th IEEE International Conference on Electronics，Circuits，and SystemsLebanon：IEEE，201 1：305-309TUCKER T M，KURFESS T RNewton methods forparamet

42、ric surface registration，part II：experimentalvalidationJ Computer-Aided Design， 2003，35(1)：115120范东明非线性最小二乘参数平差的非线性规划算法研究J西南交通大学学报，2001，36(5)：476-480FAN DongmingNonlinear programming algorithms fornonlinear least squares adjustment by parametersJJournal of Southwest Jiaotong University，2001，36(5)：476-480(中文编辑：唐晴 英文编辑：周 尧)万方数据