﻿ 大角度立体像对相对定向的混合共轭梯度算法
 文章快速检索 高级检索

1. 昆明理工大学国土资源工程学院, 云南 昆明 650093;
2. 昆明理工大学云南省高校高原山区空间信息测绘技术应用工程研究中心, 云南 昆明 650093

A hybrid conjugate gradient algorithm for solving relative orientation of big rotation angle stereo pair
LI Jiatian1,2, WANG Congcong1,2, JIA Chenglin1,2, NIU Yiru1,2, WANG Yu1,2, ZHANG Wenjing1,2, WU Huajing1,2, LI Jian1,2
1. Faculty of Land Resource Engineering, Kunming University of Science and Technology, Kunming 650093, China;
2. Surveying and Mapping Geo-Informatics Technology Research Center on Plateau Mountains of Yunnan Higher Education of Kunming University of Science and Technology, Kunming 650093, China
Foundation support: The National Natural Science Foundation of China (Nos. 41561082; 41161061)
First author: LI Jiatian(1975—), male, PhD, professor, majors in numerical optimization method and machine scene understanding.E-mail:ljtwcx@163.com
Corresponding author: WANG Congcong, E-mail: 1083719493@qq.com
Abstract: The fast convergence without initial value dependence is the key of large angle relative directional solution. Therefore, a hybrid conjugate gradient algorithm is proposed in this paper. The concrete process is:① stochastic hill climbing(SHC) algorithm is used to make random disturbance to the given initial value of the relative directional element, and the new value to guarantee the optimization direction is generated; ② In local optimization, super-linear convergent conjugate gradient method is used to replace the steepest descent method in relative orientation to improve its convergence rate; ③ The global convergence condition is that the calculation error is less than the prescribed limit error. The comparison experiment shows that the method proposed in this paper is independent of initial value, has higher accuracy and fewer iterations.
Key words: relative orientation     big rotation angle     global convergence     stochastic hill climbing algorithm     conjugate gradient algorithm

1 混合共轭梯度法解算大角度相对定向 1.1 相对定向模型

 图 1 相对定向示意图 Fig. 1 Schematic diagram of relative orientation

(1)

(2)

(3)

(1) 立体像对像片间的旋偏角较大，式(3)的简化模型不再适用。

(2) 最速下降法具有线性收敛速度，因此，收敛速率方面仍有改进的空间。

(3) 最速下降法是局部收敛算法，在相对定向元素初值难以获取的情况下，计算会陷入局部极值，甚至不收敛。

1.2 混合共轭梯度法

SHC算法是一种改进后的模拟退火法，同样具有全局收敛的性质，它通过对模拟退火算法中新的待估参数产生过程和概率重新修改，获得比模拟退火法更快的收敛速度。设待估参数当前值和新值分别为XkXk+1f为目标函数，则其只接受f(Xk+1) < f(Xk)的参数，并由下式产生新的待估参数[22]

(4)

 图 2 混合共轭梯度法 Fig. 2 Hybrid conjugate gradient

(1) 按式(4)扰动当前待估参数值来产生新值。

(2) 判断产生的新值是否符合要求。

(3) 若符合要求，则接受新值，并以新值为初值进行共轭梯度法迭代，否则，返回步骤(1)继续扰动产生新值。

(4) 判断是否满足全局收敛条件，满足则结束计算，否则，则返回(1)。

(1) 采用具有全局收敛性的SHC算法进行全局搜索，为局部搜索提供迭代初值。

(2) 不采用小角度μν近似，BX已知的简化模型，而直接对BXBYBZφωκ这6个相对定向元素求导。

(3) 采用共轭梯度法代替最速下降法，加快局部搜索的收敛速度。

1.3 共轭梯度法

(5)

(6)

(7)
(8)

(9)

(10)

(11)

1.4 SHC算法[25]

(1) 已知左右像片n对同名像点坐标和摄影机焦距f，给定相对定向元素初值pk

(2) 由式(2)计算左右像对同名像点在各自像空间辅助坐标系的坐标(X1, Y1, Z1)和(X2, Y2, Z2)。

(3) 由式(1)、式(5)计算得到H(pk)。

(4) 按式(4)修改当前相对定向元素pk以产生新的相对定向元素pnew，计算得到ΔH=H(pnew)-H(pk)。

(5) 若ΔH>0，则拒绝pnew，返回步骤(4)；否则接受pnew，即pk=pnew，并以更新后的pk作为初值按共轭梯度法进行相对定向元素计算，直至收敛于局部极值，设收敛的局部极值为pk*，对应的目标函数值为H(pk*)。

(6) 用收敛的局部极值pk*更新当前相对定向元素，即pk=pk*。若未达到全局收敛条件(若真值p*已知，则全局收敛条件为H(pk)=H(p*)；若真值未知，则为算法是否达到指定的迭代次数或规定的限差)，则返回步骤(3)继续执行；否则计算结束，此时的pk即为所求的相对定向元素。

2 试验与分析

2.1 模拟试验

 基线向量/mm 旋转角度/rad BX BY BZ φ ω κ 0.989 7 -0.086 5 0.195 2 0.808 5 -0.483 3 0.675 1 -0.956 2 -0.097 5 -0.186 2 0.390 6 -0.204 8 -0.903 6 0.975 3 0.070 3 -0.245 9 -0.949 1 -0.501 3 -0.661 8

 像对编号 算法 基线向量/mm 旋转角度/rad BX BY BZ φ ω κ 左-右1 本文算法 0.989 6 -0.086 4 0.195 1 0.808 4 -0.483 3 0.675 2 最速下降法 0.989 6 -0.086 3 0.195 0 0.808 4 -0.483 2 0.675 2 算法3 0.989 5 -0.086 1 0.194 8 0.808 3 -0.483 1 0.675 4 左-右2 本文算法 -0.956 3 -0.097 4 -0.186 2 0.390 6 -0.204 8 -0.903 6 最速下降法 -0.956 3 -0.097 5 -0.186 1 0.390 6 -0.204 8 -0.903 6 算法3 -0.956 0 -0.097 6 -0.186 0 0.390 7 -0.204 6 -0.903 7 左-右3 本文算法 0.975 2 0.070 3 -0.245 8 -0.949 1 -0.501 2 -0.661 7 最速下降法 0.975 2 0.070 3 -0.245 8 -0.949 2 -0.501 3 -0.661 8 算法3 0.975 5 0.070 4 -0.246 1 -0.948 9 -0.501 2 -0.661 6

 像对编号 算法 迭代次数 左-右1 本文算法 45 算法3 56 左-右2 本文算法 40 算法3 62 左-右3 本文算法 43 算法3 60

2.2 实测试验

 图 3 像片序列 Fig. 3 Sequence of images

 立体像对 算法 BX/mm BY/mm BZ/mm φ/rad ω/rad κ/rad 精度/μm 像片2/像片1 最速下降法 -1.367 5 -0.016 2 0.052 4 -1.064 7 0.069 8 -1.570 8 2.1 算法3 -1.367 4 -0.016 2 0.052 1 -1.064 5 0.069 8 -1.570 6 2.4 本文算法 -1.367 5 -0.016 3 0.052 5 -1.064 8 0.069 9 -1.570 7 2.2 像片3/像片1 最速下降法 -1.391 1 0.024 5 0.041 1 -1.029 7 0.025 4 0.043 6 1.8 算法3 -1.391 0 0.024 5 0.041 3 -1.029 6 0.025 4 0.043 8 2.1 本文算法 -1.391 1 0.024 4 0.041 0 -1.029 7 0.025 5 0.043 7 1.8

 立体像对 算法 迭代次数 像片2/像片1 本文算法 58 算法3 67 像片3/像片1 本文算法 54 算法3 61

3 结论

﻿

 [1] 张剑清, 潘励, 王树根. 摄影测量学原理[M]. 2版. 武汉: 武汉大学出版社, 2009. ZHANG Jianqing, PAN Li, WANG Shugen. The principles of photogrammetry[M]. 2nd ed. Wuhan: Wuhan University Press, 2009. [2] 王之卓. 摄影测量原理[M]. 武汉: 武汉大学出版社, 2007. WANG Zhizhuo. The principles of photogrammetry[M]. Wuhan: Wuhan University Press, 2007. [3] 张永军, 胡丙华, 张剑清. 基于多种同名特征的相对定向方法研究[J]. 测绘学报, 2011, 40(2): 194–199. ZHANG Yongjun, HU Binghua, ZHANG Jianqing. Relative orientation based on multiple conjugate features[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(2): 194–199. [4] 张祖勋, 张剑清. 数字摄影测量学[M]. 2版. 武汉: 武汉大学出版社, 2012. ZHANG Zuxun, ZHANG Jianqing. Digital photogrammetry[M]. 2nd ed. Wuhan: Wuhan University Press, 2012. [5] 袁亚湘, 孙文瑜. 最优化理论与方法[M]. 北京: 科学出版社, 1997. YUAN Yaxiang, SUN Wenyu. Optimal theories and methods[M]. Beijing: Science Press, 1997. [6] 张光澄. 非线性最优化计算方法[M]. 高等教育出版社, 2005. ZHANG Guangcheng. Computational methods for nonlinear optimization[M]. Beijing: Higher Education Press, 2005. [7] 李巍, 董明利, 孙鹏, 等. 大尺寸摄影测量局部参数优化相对定向方法[J]. 仪器仪表学报, 2014, 35(9): 2053–2060. LI Wei, DONG Mingli, SUN Peng, et al. Relative orientation method for large-scale photogrammetry with local parameter optimization[J]. Chinese Journal of Scientific Instrument, 2014, 35(9): 2053–2060. [8] TRIGGS B, MCLAUCHLAN P F, HARTLEY R I, et al. Bundle adjustment-a modern synthesis[M]. Berlin: Springer, 2000: 298-372. [9] STEWÉNIUS H, ENGELS C, NISTÉR D. Recent developments on direct relative orientation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2006, 60(4): 284–294. DOI:10.1016/j.isprsjprs.2006.03.005 [10] 陈义, 陆珏, 郑波. 近景摄影测量中大角度问题的探讨[J]. 测绘学报, 2008, 37(4): 458–463, 468. CHEN Yi, LU Yu, ZHENG Bo. Research on close-range photogrammetry with big rotation angle[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(4): 458–463, 468. DOI:10.3321/j.issn:1001-1595.2008.04.010 [11] 陆珏, 陈义, 郑波. 多基线近景摄影测量连续像对相对定向[J]. 同济大学学报(自然科学版), 2010, 38(3): 442–447. LU Jue, CHEN Yi, ZHENG Bo. Research on dependent relative orientation in multi-baseline close-range photogrammetry[J]. Journal of Tongji University (Natural Science), 2010, 38(3): 442–447. [12] NIST D. An efficient solution to the five-point relative pose problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 26(6): 756–770. [13] 于起峰, 尚洋. 摄像测量学原理与应用研究[M]. 北京: 科学出版社, 2009. YU Qifeng, SHANG Yang. Videometrics:principles and researches[M]. Beijing: Science Press, 2009. [14] KUKELOVA Z, BUJNAK M, PAJDLA T. Polynomial eigenvalue solutions to minimal problems in computer vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(7): 1381–1393. DOI:10.1109/TPAMI.2011.230 [15] WANG Wenbin, LIU Guihua, LIU Xianyong, et al. Two removal tactics of pseudo solutions for essential matrix five-point algorithm[J]. Opto-Electronic Engineering, 2010, 37(8): 46–52. [16] 张征宇, 朱龙, 黄叙辉, 等. 基于前方交会的5点相对定向[J]. 光学学报, 2015, 35(1): 231–238. ZHANG Zhengyu, ZHU Long, HUANG Xuhui, et al. Five-point relative orientation based on forward intersection[J]. Acta Optica Sinica, 2015, 35(1): 231–238. [17] 袁修孝, 陈时雨, 钟灿. 基于基础矩阵的倾斜航摄影像相对定向方法[J]. 武汉大学学报(信息科学版), 2016, 41(8): 995–1000. YUAN Xiuxiao, CHEN Shiyu, ZHONG Can. Oblique aerial image relative orientation based on fundamental matrix[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 995–1000. [18] ZHANG Yongjun, HUANG Xu, HU Xiangyun, et al. Direct relative orientation with four independent constraints[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2011, 66(6): 809–817. DOI:10.1016/j.isprsjprs.2011.09.006 [19] WANG J, LIN Z, REN C. Relative orientation in low altitude photogrammetry survey[J]. ISPRS International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2012(1): 463–467. [20] 杨阿华, 李学军, 刘涛, 等. 基于直接解算与迭代优化的相对定向方法[J]. 计算机应用, 2014, 34(6): 1706–1710. YANG Ahua, LI Xuejun, LIU Tao, et al. Relative orientation approach based on direct resolving and iterative refinement[J]. Journal of Computer Applications, 2014, 34(6): 1706–1710. DOI:10.3969/j.issn.1001-3695.2014.06.024 [21] 周拥军, 邓才华. 利用HGA和单位四元数的相对定向解法[J]. 武汉大学学报(信息科学版), 2011, 36(6): 670–673. ZHOU Yongjun, DENG Caihua. A new method for relative orientation with hybrid genetic algorithm and unit quaternion[J]. Geomatics and Information Science of Wuhan University, 2011, 36(6): 670–673. [22] HUANG Xuri, KELKAR M. Performance comparison of heuristic combinatorial alorithms for seismic inversion[C]//Proceedings of 1995 SEG Annual Meeting. Houston, Texas: Society of Exploration Geophysicists, 1995: 1025-1027. [23] 席少霖. 非线性最优化方法[M]. 北京: 高等教育出版社, 1992. XI Shaolin. The method of nonlinear optimization[M]. Beijing: Higher Education Press, 1992. [24] POLYAK B T. The conjugate gradient method in extremal problems[J]. USSR Computational Mathematics and Mathematical Physics, 1969, 9(4): 94–112. DOI:10.1016/0041-5553(69)90035-4 [25] 涂进.基于模拟退火算法的聚类分析在数据挖掘中的应用[D].重庆: 重庆大学, 2003. TU Jin. Study on clustering analysis in data mining based on simulated annealing algorithm[D]. Chongqing: Chongqing University, 2003. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y795265
http://dx.doi.org/10.11947/j.AGCS.2019.20170672

0

#### 文章信息

LI Jiatian, WANG Congcong, JIA Chenglin, NIU Yiru, WANG Yu, ZHANG Wenjing, WU Huajing, LI Jian

A hybrid conjugate gradient algorithm for solving relative orientation of big rotation angle stereo pair

Acta Geodaetica et Cartographica Sinica, 2019, 48(3): 322-329
http://dx.doi.org/10.11947/j.AGCS.2019.20170672