首页 关于本刊 编 委 会 期刊动态 作者中心 审者中心 读者中心 下载中心 联系我们 English
 自动化学报  2018, Vol. 44 Issue (3): 506-516 PDF

1. 解放军信息工程大学 郑州 450000;
2. 国防信息学院 武汉 430000

An Improved Method for Camera Location Estimation Through Convex Optimization
XIE Li-Xiang1, WAN Gang1, CAO Xue-Feng1, WANG Qing-He1, WANG Long2
1. PLA Information Engineering University, Zhengzhou 450000;
2. National Defense Information College, Wuhan 430000
Manuscript received : September 7, 2016, accepted: January 16, 2017.
Foundation Item: Supported by National Natural Science Foundation of China (41301428, 4110143), Open Research Fund of State Key Laboratory of Geographical Information Engineering (SKLGIE2016-M-3-4)
Corresponding author. WAN Gang Professor at PLA Information Engineering University. He received his Ph. D. degree in cartography and GIS from PLA Information Engineering University in 2006. His research interest covers UAV surveying and mapping, virtual geographic environment. Corresponding author of this paper
Recommended by Associate Editor JIA Yun-De
Abstract: As a core module of structure from motion (SfM), location estimation of cameras in a global framework has been a research hotspot of computer version. State-of-the-art methods for location estimation are sensitive to outliers, especially for large scale, unordered images. The incremental SfM reduces the influence of outliers through an iterative optimization. The global SfM does not have an efficient strategy to remove mismatch, so the result of estimation is influenced deeply by outliers. Therefore, we introduce an improved method for location estimation. First, combined with the epipolar constraint we propose a new pairwise direction estimation algorithm. Then, we make the problem well-posed by introducing a new preprocessing method based on parallel rigidity. Finally, we propose a robust linear estimation model based on convex programing. We can get a global optimum solution by resolving this model. The method can integrate well with state-of-art global SfM pipeline. Multiple group experiments have proved the robustness of our methods without any loss of efficiency and common precision.
Key words: Structure from motion (SfM)     global position estimating     parallel rigidity     convex optimization     epipolar geometry

1 全局式SfM算法简介

 图 1 融合本文改进的全局式SfM算法流程图 Figure 1 The processing pipeline of global SfM fusion our modifying
2 基于极线约束的相对平移方向估计

 图 2 本文改进的相对平移方向估计算法流程 Figure 2 The processing pipeline of relative translation estimation based on our modifying

 $\pmb P_i=R_i({\pmb P}-{\pmb t_i})=(X_i, Y_i, Z_i)^{\rm T}$ (1)
 $\pmb p_i=(f_i/Z_i){\pmb P_i}=(x_i, y_i, f_i)^{\rm T}$ (2)

 图 3 图像之间的极线关系 Figure 3 Epipolar relationship between image pairs

 $$${\pmb p}_i^{\rm T} E_{ij} {\pmb p_j} = 0$$$ (3a)

$(p_i'=(x_i, y_i)^{\rm T})$表示三维点投影到第 $i$ 个像平面上的平面坐标, 则(3a)可改写为

 $$$\left[ \begin{array}{c} \dfrac{x_i}{f_i} \\[4mm] \dfrac{y_i}{f_i} \\ 1 \\ \end{array} \right] E_{ij} \left[ \begin{array}{c} \dfrac{x_j}{f_j} \\[4mm] \dfrac{y_j}{f_j} \\ 1 \\ \end{array} \right] = 0$$$ (3b)
 $$$\left[ \begin{array}{c} \dfrac{p_i'}{f_i} \\ 1 \\ \end{array} \right] E_{ij} \left[ \begin{array}{c} \dfrac{p_j'}{f_j} \\ 1 \\ \end{array} \right] = 0$$$ (3c)

 \begin{align} {\pmb p}_i^{\rm T} E_{ij} {\pmb p_j} &= {\pmb p}_i^{\rm T} [R_i^{\rm T}({\pmb t_i}-{\pmb t_j})]_{\times}R_i^{\rm T} R_j {\pmb p_j} =\nonumber \\ & {\pmb p}_i^{\rm T} R_i^{\rm T}(({\pmb t_i}-{\pmb t_j})_ {\times}R_j {\pmb p_j})= \nonumber \\ &(R_i{\pmb p_i}{\times}R_j {\pmb p_j})^{\rm T}({\pmb t_i}- {\pmb t_j})=0 \nonumber \\ \Longleftrightarrow \quad& \pmb v_{ij}^{\rm T}(\pmb t_i-{\pmb t_j}) = 0 \nonumber \\ \Longleftrightarrow \quad& \pmb v_{ij}^{\rm T} {\pmb \gamma}_{ij} = 0 \nonumber \\ {\pmb v}_{ij} &= (R_i {\pmb p_i}{\times}R_j {\pmb p_j}) =\nonumber \\ & \left[ \left( R_i \left[ \begin{array}{c} \dfrac{p_i'}{f_i} \\[2mm] 1 \end{array} \right] \right) \right] {\times} \left[ \left( R_j \left[ \begin{array}{c} \dfrac{p_j'}{f_j} \\[2mm] 1 \end{array} \right] \right) \right] \end{align} (4)

 \begin{align} \mathop {\rm minimize}_{\{\pmb \gamma_{ij}'\}_{ij}}&\sum\limits_{k=1}^{m_{ij}}\delta \nonumber \\ \mbox{subject to} \quad& |(\pmb \gamma_{ij}')^{\rm T} {\pmb v}_{ij}^k| \le \delta, \quad \forall i, j \nonumber \\ &||\pmb \gamma_{ij}'||=1, \quad \forall i, j \end{align} (5)

 $$$\pmb \gamma_{ij} = s{\pmb \gamma'_{ij}}, \quad s \in \{-1, +1\}$$$ (6)

3 基于凸优化的鲁棒性全局位置估计

 图 4 相对平移方向和相机全局位置 Figure 4 Relative translation direction and cameras' global position
 图 5 平行刚体示例 Figure 5 An example of parallel rigid
3.1 平行刚体

 $$$|D'| \le {d|V(D')|-(d+1)}$$$ (7)

3.2 鲁棒性全局位置估计

 $$$\pmb \gamma_{ij}=\frac{\pmb t_i-{\pmb t_j}}{||\pmb t_i-{\pmb t_j}||}$$$ (8)

 $$$\pmb \gamma_{ij}=\frac{\pmb t_i-{\pmb t_j}}{||\pmb t_i-{\pmb t_j}||}+\pmb \varepsilon_{ij}$$$ (9)

 $$$\pmb \varepsilon_{ij}'=\pmb t_i-{\pmb t_j}-{\pmb \lambda_{ij}}{\pmb \gamma_{ij}}$$$ (10)

 \begin{align} &\mathop{\rm minimize}_{\{\pmb t_i\}_i, \{\lambda_{ij}\}_{ij}, \{\pmb \varepsilon_{ij}'\}_{ij}} \sum\limits_{(i, j) \in E_l}{\pmb \varepsilon_{ij}'} \nonumber \\ &\mbox{subject to}\ ||\pmb t_i-{\pmb t_j}-\lambda_{ij}{\pmb \gamma_{ij}}|| \le \pmb \varepsilon_{ij}' \nonumber \\ &\qquad\sum\limits_{i \in V_l}{\pmb t_i}=0 \nonumber \\ &\qquad\lambda_{ij}=||\pmb t_i-{\pmb t_j}|| \ge c, \forall (i, j) \in E_l \end{align} (11)

 \begin{align} &\mathop{\rm minimize}_{\{\pmb t_i\}_i, \{\lambda_{ij}\}_{ij}, \{\pmb \varepsilon_{ij}'\}_{ij}} \sum\limits_{(i, j) \in E_l}{\pmb \varepsilon_{ij}'} \nonumber \\ &\mbox{subject to}\ ||\pmb t_i-{\pmb t_j}-\lambda_{ij}{\pmb \gamma_{ij}}|| \le \pmb \varepsilon_{ij}' \nonumber \\ &\qquad \sum\limits_{i \in V_l}{\pmb t_i}=0 \nonumber \\ &\qquad \lambda_{ij} \ge c, \forall (i, j) \in E_l \end{align} (12)

IRLS主要思想是:对目标模型进行迭代求解, 在每次迭代过程中更新观测值权重.权重的大小取决于上一次迭代结果的残差, 对残差贡献小的观测值给于更高的权重, 反之更低.当应用于本节中相机全局位置估计问题时, 如下式(13)所示.

 $$$\mathop{\rm minimize}\limits_{\{\pmb t_i\}_i, \{\lambda_{ij}\}_{ij}, \{\gamma_{ij}\}_{ij}} \sum\limits_{(i, j) \in E_l}w_{ij}||\pmb t_i-{\pmb t_j}-\lambda_{ij}{\pmb \gamma_{ij}}||$$$ (13)

4 实验

4.1 实验结果

 图 11 利用本文算法对8组公开数据集处理获取的场景三维稀疏结构 Figure 11 The experimental result with 8 groups of datasets based on our method

4.2 结果分析

 图 6 相机全局位置散点图(数据Vienna, 相机个数821) Figure 6 Global location of cameras represented by scatter diagram
 图 7 BA优化后本文同1DSfM实验结果平均值比较图 Figure 7 Comparison result of mean between our method and 1DSfM after BA
 图 8 BA优化后本文同文献[20]实验结果中位数比较图 Figure 8 Comparison result of median between our method and [20] after BA
 图 9 BA优化前本文同1DSfM实验结果中位数比较图 Figure 9 Comparison result of median between our method and 1DSfM before BA
 图 10 BA优化后本文同1DSfM实验结果中位数比较图 Figure 10 Comparison result of median between our method and 1DSfM after BA

5 结论

 1 Triggs B, McLauchlan P, Hartley R I, Fitzgibbon A W. Bundle adjustment-a modern synthesis. Vision Algorithms: Theory and Practice: Lecture Notes in Computer Science. Berlin, Heidelberg: Springer, 1999. 298-372 http://rd.springer.com/book/10.1007/3-540-44480-7 2 Zhang Z Y, Shan Y. Incremental Motion Estimation Through Local Bundle Adjustment. Technical Report MSR-TR-01-54, Microsoft Research, Redmond, WA, 2001. 3 Snavely N, Seitz S M, Szeliski R. Photo tourism:exploring photo collections in 3D. ACM Transactions on Graphics, 2006, 25(3): 835-846. DOI:10.1145/1141911 4 Snavely N, Seitz S M, Szeliski R. Skeletal graphs for efficient structure from motion. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, USA: IEEE, 2008. 1-8 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=4587678 5 Havlena M, Torii A, Knopp J, Pajdla T. Randomized structure from motion based on atomic 3D models from camera triplets. In: Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Miami, USA: IEEE, 2009. 2874-2881 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5206677 6 Furukawa Y, Curless B, Seitz S M, Szeliski R. Towards internet-scale multi-view stereo. In: Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, USA: IEEE, 2010. 1434-1441 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5539802 7 Sinha S N, Steedly D, Szeliski R. A multi-stage linear approach to structure from motion. In: Proceedings of the 11th European Conference on Trends and Topics in Computer Vision. Berlin, Heidelberg: Springer, 2010. 267-281 https://link.springer.com/chapter/10.1007%2F978-3-642-35740-4_21 8 Kneip L, Chli M, Siegwart R Y. Robust real-time visual odometry with a single camera and an IMU. In: Proceedings of the 22nd British Machine Vision Conference. Scotland, UK: BMVA, 2011. http://dx.doi.org/10.3929/ethz-a-010025746 9 Tomasi C, Kanade T. Shape and motion from image streams under orthography:a factorization method. International Journal of Computer Vision, 1992, 9(2): 137-154. DOI:10.1007/BF00129684 10 Moulon P, Monasse P, Marlet R. Global fusion of relative motions for robust, accurate and scalable structure from motion. In: Proceedings of the 2013 IEEE International Conference on Computer Vision. Sydney, AU: IEEE, 2013. 3248-3255 http://ieeexplore.ieee.org/document/6751515/ 11 Govindu V M. Lie-algebraic averaging for globally consistent motion estimation. In: Proceedings of the 2004 IEEE Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2004. 684-691 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=1315098 12 Martinec D, Pajdla T. Robust rotation and translation estimation in multiview reconstruction. In: Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition. Minnesota, USA: IEEE, 2007. 1-8 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=4270140 13 Hartley R, Aftab K, Trumpf J. L1 rotation averaging using the Weiszfeld algorithm. In: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA: IEEE, 2011. 3041-3048 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5995745 14 Fredriksson J, Olsson C. Simultaneous multiple rotation averaging using lagrangian duality. In: Proceedings of the 11th Asian Conference on Computer Vision. Berlin, Heidelberg: Springer, 2012. 245-258 https://link.springer.com/chapter/10.1007%2F978-3-642-37431-9_19 15 Chatterjee A, Govindu V M. Efficient and robust large-scale rotation averaging. In: Proceedings of the 2013 IEEE International Conference on Computer Vision. Sydney, AU: IEEE, 2013. 521-528 http://ieeexplore.ieee.org/document/6751174/ 16 Brand M, Antone M, Teller S. Spectral solution of large-scale extrinsic camera calibration as a graph embedding problem. In: Proceedings of the 8th European Conference on Computer Vision. Berlin, Heidelberg: Springer, 2004. 262-273 http://www.springerlink.com/content/0bx5vqf0688nxcw3 17 Arie-Nachimson M, Kovalsky S Z, Kemelmacher-Shlizerman I, Singer A, Basri R. Global motion estimation from point matches. In: Proceedings of the 2nd International Conference on 3D Imaging, Modeling, Processing, Visualization and Transmission. Zurich, Switzerland: IEEE, 2012. 81-88 http://ieeexplore.ieee.org/document/6374980/ 18 Sim K, Hartley R. Recovering camera motion using L∞ minimization. In: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, NY, USA: IEEE, 2006. 1230-1237 19 Kahl F, Hartley R. Multiple-view geometry under the L∞-norm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(9): 1603-1617. DOI:10.1109/TPAMI.2007.70824 20 Govindu V M. Combining two-view constraints for motion estimation. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Kauai, HI, USA: IEEE, 2001. 218-225 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=990963 21 Tron R, Vidal R. Distributed image-based 3-D localization of camera sensor networks. In: Proceedings of the 48th IEEE Conference on Decision and Control. Shanghai, China: IEEE, 2009. 901-908 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5400405 22 Li H D. Multi-view structure computation without explicitly estimating motion. In: Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, CA: IEEE, 2010. 2777-2784 23 Wilson K, Snavely N. Robust global translations with 1DSfM. In: Proceedings of the 13th European Conference on Computer Vision. Berlin, Heidelberg: Springer, 2014. 61-75 https://link.springer.com/chapter/10.1007%2F978-3-319-10578-9_5 24 Daubechies I, Devore R, Fornasier M, Güntürk C S. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics, 2010, 63(1): 1-38. DOI:10.1002/cpa.v63:1 25 Andrew A M. Multiple view geometry in computer vision. Kybernetes, 2001, 30(9-10): 1333-1341. 26 Jiang N J, Cui Z P, Tan P. A global linear method for camera pose registration. In: Proceedings of the 2013 IEEE Conference on Computer Vision. Sydney, NSW: IEEE, 2013. 481-488 http://ieeexplore.ieee.org/document/6751169/ 27 Whiteley W. A matroid on hypergraphs, with applications in scene analysis and geometry. Discrete & Computational Geometry, 1989, 4(1): 75-95. 28 Whiteley W. Parallel redrawing of configurations in 3-space. 1986. 29 Servatius B, Whiteley W. Constraining plane configurations in computer-aided design:combinatorics of directions and lengths. SIAM Journal on Discrete Mathematics, 1999, 12(1): 136-153. DOI:10.1137/S0895480196307342 30 Eren T, Whiteley W, Belhumeur P N. Using angle of arrival (bearing) information in network localization. In: Proceedings of the 45th IEEE Conference on Decision and Control. San Diego, CA: IEEE, 2006. 4676-4681 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4177903 31 Eren T, Whiteley W, Morse A S, Belhumeur P N, Anderson B D O. Sensor and network topologies of formations with direction, bearing, and angle information between agents. In: Proceedings of the 42nd IEEE Conference on Decision and Control. Maui, HI: IEEE, 2003. 3064-3069 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1273093 32 Jackson B, Jordán T. Graph theoretic techniques in the analysis of uniquely localizable sensor networks. 2009. 33 Jacobs D J, Hendrickson B. An algorithm for two-dimensional rigidity percolation:the pebble game. Journal of Computational Physics, 1997, 137(2): 346-365. DOI:10.1006/jcph.1997.5809 34 Kennedy R, Daniilidis K, Naroditsky O, Taylor C J. Identifying maximal rigid components in bearing-based localization. In: Proceedings of the 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. Vilamoura-Algarve, Portugal: IEEE, 2012. 194-201 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6386132