摘要
从二维(Two-dimensional,2D)图像中重建场景的三维(Three-dimensional,3D)几何结构是计算机视觉中的基本研究课题。尽管相关的理论和应用研究已经经历了数十年,近年来仍不断涌现出许多基于图像的三维重建的新成果,这表明该课题仍然是一个相当活跃的热门研究方向。基于图像的三维重建是图像获取的逆过程,其本质是从二维图像观察中估计全部(或者部分)相机参数以及场景点的三维坐标。由于图像数据不可避免的受噪声和外点(Outlier)的干扰,使得上述逆过程面临诸多挑战。
本论文关注基于图像点特征的、没有任何场景先验知识的三维重建问题,深入研究从两视图到多视图、从陆上到水下环境等四类典型的三维重建问题的建模及求解方法。本论文旨在提高三维重建算法的鲁棒性、精度和效率,论文的创新点和主要贡献概括如下:
将非定标两视图三维重建问题转化为一个新的、鲁棒的带约束优化问题,该带约束优化问题综合考虑了图像噪声、外点以及两视图三维重建中的含糊性等因素。提出一个基于改进的ε约束自适应差分进化(ε ConstrainedAdaptive Differential Evolution, εADE)方法的混合优化框架对上述问题有效求解。该混合优化框架中提出了新的、具有几何意义的操作算子,使得算法的稳定性和收敛性能均明显提升,且三维重建精度显著优于现有方法;
提出一种混合优化框架下基于最优内点选取和三维结构求精的、鲁棒的多视图二范数(L2)三角化方法。本文推导了对极转移(Epipolar Transfer)协方差矩阵的解析计算方法,并在此基础上提出一种基于残差一致性(Residual-consensus)的图像噪声强度估计,为图像观察内点的选取提供重要依据。此外,提出了两种三维结构误差边界计算方法,极大的缩小了三维结构求精的搜索范围。与同类最新算法相比,本文三角化方法可获得包含更多三维点的、更加精确的三维结构,并提高了大规模实验数据的处理效率;
对于水下成像系统,由于相机与被观察物体处于不同的介质(空气、水)中,当光线通过不同介质的交界面时会发生折射现象,从而导致图像折射变形(Refractive Distortion)。针对包含两个相机(每个相机均放置在单独的、有透明平面窗口的防水外壳中)的一般水下成像系统,本文提出一种基于折射相机模型(Refractive Camera Model)的水下两视图三维重建方法。上述方法首次实现了无需定标物的高精度水下两视图三维重建;
本文首次对折射变形对基于传统透视相机模型的水下多视图三维重建质量的影响进行了理论分析和系统、定量的实验研究。该研究结果揭示了一个非常实用、但尚未在学术界引起广泛注意的事实,即当成像系统参数满足一定条件时,透视相机模型结合镜头径向畸变(Lens Radial Distortion)矫正和焦距调节,可以有效消除折射变形对多视图水下三维重建的影响。上述研究为水下三维成像系统参数的选择,以及基于透视相机模型的多视图水下三维重建方法的应用提供了重要的理论和实验依据。综上所述,本论文深入研究并提出了多个可以提升基于图像点特征的三维重建质量的新方法。本文方法理论的正确性和应用的可行性均在完整的三维重建系统中进行了广泛的实验验证,其性能的优越性在与最新相关方法的对比中得到了印证。
Reconstructingthethree-dimensional(3D)structureofascenefromtwo-dimensional(2D) images is a fundamental problem in computer vision. After decades’ of extensivestudy of image-based3D reconstruction, this topic remains quite active as evidenced bycontinued rapid progress being made in the last decade. The task of image-based3D re-construction is the reverse process of image capturing, which corresponds to estimatingall (or some) camera parameters and3D locations of the scene points from their2D ob-servations. This problem poses many challenges due to unavoidable noise and outliers inthe data.
Thisthesisstudiestheproblemof3Dreconstructionwithoutpriorsofscenestructurebasedonimagefeaturepoints,concentratingonfourtypicaltopicsrangingfromtwo-viewto multi-view scenarios and from land-based system to underwater environment. Aimingat improving the robustness, accuracy and efficiency of3D reconstruction, this thesismakes the following original contributions:
The problem of3D reconstruction from two uncalibrated images is recast as a ro-bust single constrained optimization problem, which can be efficiently solved bya new hybrid optimization framework based on the modified ε Constrained Adap-tive Differential Evolution (εADE), within which both stability and convergencerate have been significantly improved by incorporating novel geometrically mean-ingful evolutionary operations. The above constrained optimization formulation isable to handle noise and outliers in image observations properly and to avoid geo-metric ambiguity in the reconstruction. Moreover, the above method considerablyoutperforms existing algorithms in terms of the accuracy of3D reconstruction.
A new robust hybrid optimization framework for multi-view L2triangulation basedon optimal inlier selection and3D structure refinement is developed. In order to es-timate the scale of noise in image measurements, a new residual-consensus schemewithinwhichtheuncertaintyofepipolartransferisanalyticallycharacterizedbyde-riving its closed-form covariance is proposed. As for3D structure refinement, twonovel error bounding algorithms are proposed to significantly reduce the searchspace. Compared with state-of-the-art triangulation methods, the proposed frame-workisabletoobtainreconstructionresultswithmore3Dpointsofhigheraccuracy.The computational efficiency is also noticeably improved as validated by experi- mental results on large scale datasets.
For an underwater imaging system, a refractive interface is introduced when a cam-era looks into the water-based environment, resulting in object space distortion inimage due to refraction. This thesis proposes a novel method for two-view under-water3D reconstruction based on refractive camera model, dealing with a generalunderwater imaging setup using two cameras, of which each camera is placed in aseparate waterproof housing with a flat window. To the best of our knowledge, theproposedframeworkisthefirstonecapableofperforminghighlyaccuratetwo-viewunderwater3D reconstruction without using any calibration object.
This thesis for the first time presents theoretical analysis and also systematicallyquantitative evaluation of the influence of refraction on multi-view underwater3Dreconstruction based on perspective camera model. The results reveal a rather sur-prising and useful yet overlooked fact that the traditional perspective camera modelwithlensradialdistortioncorrectionandfocallengthadjustmentcancompensateforrefraction distortion, as long as system parameters satisfy some loose requirements.This research not only justifies the use of perspective camera model in multi-viewunderwater3D reconstruction, but also provides theoretical and practical supportfor the design of underwater3D imaging system.
To summarize, thisthesisdevelopsanumberofnewapproachestoimprovethequal-ity of image-based3D reconstruction. The proposed methods have been evaluated withina complete3D reconstruction pipeline and their superior performance is verified by ex-tensive experiments and comparison with related state-of-the-art methods.
引文
[1]马颂德,张正友.计算机视觉——计算理论与算法基础(第二版)[M].北京:科学出版社,2003.
[2] Shapiro L G, Stockman G C. Computer vision [M]. Prentice Hall,2001.
[3] Marr D. Vision: a computational investigation into the human representation andprocessing of visual information [M]. W.H. Freeman and Company,1982.
[4] Baer A, Eastman C, Henrion M. Geometric modelling: a survey [J]. Computer-Aided Design.1979,11(5):253–272.
[5] Fruh C, Zakhor A.3D model generation for cities using aerial photographs andground level laser scans [C]. In Proceedings of IEEE Conference on ComputerVision and Pattern Recognition (CVPR).2001:31–38.
[6] Milgram P, Kishino A F. Taxonomy of mixed reality visual displays [J]. IEICETransactions on Information and Systems.1994, E77-D (12):1321–1329.
[7] Hartley R, Zisserman A. Multiple view geometry in computer vision [M].2nd ed.Cambridge University Press,2004.
[8] Szeliski R. Computer vision: algorithms and applications [M].1st ed. Springer,2010.
[9] Tuytelaars T, Mikolajczyk K. Local invariant feature detectors: a survey [J]. Foun-dations and Trends in Computer Graphics and Vision.2008,3(3):177–280.
[10] Lowe D G. Distinctive image features from scale-invariant keypoints [J]. Interna-tional Journal of Computer Vision.2004,60(2):91–110.
[11] Zhang Z, Deriche R, Faugeras O, et al. A robust technique for matching two un-calibrated images through the recovery of the unknown epipolar geometry [J]. Ar-tificial Intelligence.1995,78(1-2):87–119.
[12] Loop C, Zhang Z. Computing rectifying homographies for stereo vision [C]. InProceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR).1999:125–131.
[13] Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereocorrespondence algorithms [J]. International Journal of Computer Vision.2002,47(1-3):7–42.
[14] Mikolajczyk K, Schmid C. A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis and Machine Intelligence.2005,27(10):1615–1630.
[15] Ke Y, Sukthankar R. PCA-SIFT: a more distinctive representation for local im-age descriptors [C]. In Proceedings of IEEE Conference on Computer Vision andPattern Recognition (CVPR).2004:506–513.
[16] Bay H, Ess A, Tuytelaars T, et al. SURF: speeded pp robust features [J]. ComputerVision and Image Understanding.2008,110(3):346–359.
[17] Fan B, Wu F, Hu Z. Rotationally Invariant Descriptors using Intensity Order Pool-ing [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence.2012,34(10):2031–2045.
[18] Hua G, Brown M, Winder S. Discriminant embedding for local image descrip-tors [C]. In Proceedings of IEEE International Conference on Computer Vision(ICCV).2007:1–8.
[19] Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hash-ing [C]. In Proceedings of International Conference on Very Large Data Bases(VLDB).1999:518–529.
[20] Shakhnarovich G, Viola P, Darrell T. Fast pose estimation with parametersensitivehashing[C].InProceedingsofIEEEInternationalConferenceonComputerVision(ICCV).2003:750–757.
[21] Torralba A, Weiss Y, Fergus R. Small codes and large databases of images forobject recognition [C]. In Proceedings of IEEE Conference on Computer Visionand Pattern Recognition (CVPR).2008:1–8.
[22] Muja M, Lowe D G. Fast approximate nearest neighbors with automatic algorithmconfiguration[C].InProceedingsofthe4thInternationalConferenceonComputerVision Theory and Applications (VISAPP).2009:331–340.
[23] Snavely N, Seitz S M, Szeliski R. Modeling the world from internet photo collec-tions [J]. International Journal of Computer Vision.2008,80(2):189–210.
[24] Tsai R. An efficient and accurate camera calibration technique for3D machinevision [C]. In Proceedings of IEEE Conference on Computer Vision and PatternRecognition (CVPR).1986:364–374.
[25] Zhang Z. A flexible new technique for camera calibration [J]. IEEE Transactionson Pattern Analysis and Machine Intelligence.2000,22(11):1330–1334.
[26] Meng X Q, Li H, Hu Z Y. A new camera calibration technique based on circularpoints [C]. In Proceedings of British Machine Vision Conference (BMVC).2000:496–505.
[27] Wu Y, Zhu H, Hu Z, et al. Camera Calibration from the quasi-affine invarianceof two parallel circles [C]. In Proceedings of European conference on Computervision (ECCV).2004:190–202.
[28] Faugeras O D, Luong Q T, Maybank S J. Camera self-calibration: theory andexperiments [C]. In Proceedings of European conference on Computer vision(ECCV).1992:321–334.
[29] Maybank S J, Faugeras O. A theory of self-calibration of moving camera [J]. In-ternational Journal of Computer Vision.1992,8(2):123–151.
[30] Hartley R. Kruppa’s equations derived from the fundamental matrix [J]. IEEE-TransactionsonPatternAnalysisandMachineIntelligence.2001,27(5):621–630.
[31]雷成,吴福朝,胡占义.Kruppa方程与摄像机自标定[J].自动化学报.2001,27(5):621–630.
[32] Ma Y, Vidal R, Kosecka J, et al. Kruppa equation revisited: its renormalizationand degeneracy [C]. In Proceedings of European conference on Computer vision(ECCV).2000:561–577.
[33] Pollefeys M, Gool L V. Stratified self-calibration with the modulus constraint [J].IEEE Transactions on Pattern Analysis and Machine Intelligence.1999,21(8):707–724.
[34] Heyden A, Astrom K. Euclidean reconstruction from image sequences with vary-ing and unknown focal length and principle point [C]. In Proceedings of IEEEConferenceonComputerVisionandPatternRecognition(CVPR).1997:438–443.
[35] Heyden A, Astrom K. Flexible calibration: minimal cases for auto-calibration [C].In Proceedings of IEEE International Conference on Computer Vision (ICCV).1999:350–355.
[36] Pollefeys M, Koch R, Gool L V. Self-calibration and metric reconstruction in spiteof Varying and unknown internal camera parameters [J]. International Journal ofComputer Vision.1999,32(1):7–25.
[37]孟晓桥,胡占义.摄像机自标定方法的研究与进展[J].自动化学报.2003,29(1):110–124.
[38] Longuet-Higgins H C. A computer algorithm for reconstructing a scene from twoprojections [J]. Nature.1982,293:133–135.
[39] Tomasi C, Kanade T. Shape and motion from image streams under orthography:a factorization method [J]. International Journal of Computer Vision.1992,9(2):137–154.
[40] Spetsakis M, Aloimonos J Y. A multi-frame approach to visual motion percep-tion [J]. International Journal of Computer Vision.1991,6(3):245–255.
[41] Szeliski R, Kang S B. Recovering3D shape and motion from image streams usingnonlinear least squares [J]. Journal of Visual Communication and Image Repre-sentation.1994,5(1):10–28.
[42] Oliensis J. A multi-frame structure-from-motion algorithm under perspective pro-jection [J]. International Journal of Computer Vision.1997,34(2):34–2.
[43] Schaffalitzky F, Zisserman A. Multi-view matching for unordered image sets, or“How do I organize my holiday snaps?”[C]. In Proceedings of European Confer-ence on Computer Vision (ECCV).2002:414–431.
[44] Vergauwen M, Van Gool L. Web-based3D reconstruction service [J]. MachineVision and Applications.2006,17(2):321–329.
[45] Brown M, Lowe D. Unsupervised3D object recognition and reconstruction in un-ordered datasets [C]. In Proceedings of International Conference on3-D DigitalImaging and Modeling.2005:56–63.
[46] Triggs B, Mclauchlan P, Hartley R, et al. Bundle adjustment: a modern synthe-sis [C]. In Vision Algorithms: Theory and Practice, LNCS.2000:298–375.
[47] Lourakis M I A, Argyros A A. SBA: a software package for generic sparse bundleadjustment [J]. ACM Transactions on Mathematical Software.2009,36(1):1–30.
[48] Rousseeuw P. Least median of squares regression [J]. Journal of the AmericanStatistical Association.1984,79:871–880.
[49] Olsson C, Eriksson A, Hartley R I. Outlier removal using duality [C]. In Proceed-ings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR).2010:1450–1457.
[50] Li H. A practical algorithm for L∞triangulation with outliers [C]. In Proceedingsof IEEE Conference on Computer Vision and Pattern Recognition (CVPR).2007:1–8.
[51] Agarwal S, Snavely N, Simon I, et al. Building Rome in a day [C]. In Proceedingsof IEEE International Conference on Computer Vision (ICCV).2009:72–79.
[52] Agarwal S, Snavely N, Seitz S M, et al. Bundle adjustment in the large [C]. InProceedings of European conference on Computer vision (ECCV): Part II.2010:29–42.
[53] Wu C, Agarwal S, Curless B, et al. Multicore bundle adjustment [C]. In Proceed-ings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR).2011:3057–3064.
[54] Fitzgibbon A W, Zisserman A. Automatic camera recovery for closed or open im-age sequences [C]. In Proceedings of European Conference on Computer Vision(ECCV).1998:311–326.
[55] R Gherardi A F, M Farenzena. Improving the efficiency of hierarchical structure-and-motion [C]. In Proceedings of IEEE Conference on Computer Vision and Pat-tern Recognition (CVPR).2010:1594–1600.
[56] Farenzena M, Fusiello A, Gherardi R. Structure-and-motion pipeline on a hierar-chical cluster tree [C]. In Proceedings of IEEE International Conference on Com-puter Vision (ICCV) Workshops.2009:1489–1496.
[57] Seitz S M, Curless B, Diebel J, et al. A comparison and evaluation of multi-viewdtereoreconstructionalgorithms[C].InProceedingsofIEEEConferenceonCom-puter Vision and Pattern Recognition (CVPR).2006:519–528.
[58] Seitz S, Dyer C. Photorealistic scene reconstruction by voxel coloring [J]. Interna-tional Journal of Computer Vision.1999,35(2):151–173.
[59] Treuille A, Hertzmann A, Seitz S M. Example-based stereo with generalBRDFs [C]. In Proceedings of European conference on Computer vision (ECCV).2004:457–469.
[60] Roy S, Cox I. A maximum-flow formulation of the N-camera stereo correspon-denceproblem[C].InProceedingsofIEEEInternationalConferenceonComputerVision (ICCV).1998:492–499.
[61] Vogiatzis G, Torr P H S, Cipolla R. Multi-view stereo via volumetric graph-cuts [C]. In Proceedings of IEEE Conference on Computer Vision and PatternRecognition (CVPR).2005:391–398.
[62] Sinha S, Pollefeys M. Multi-view reconstruction using photo-consistency and ex-act silhouette constraints: a maximum-flow formulation [C]. In Proceedings ofIEEE International Conference on Computer Vision (ICCV).2005:349–356.
[63] Kolmogorov V, Zabih R. Multi-camera scene reconstruction via graph cuts [C].In Proceedings of European Conference on Computer Vision (ECCV)-Part III.2002:82–96.
[64] Kutulakos K N, Seitz S M. A theory of shape by space carving [J]. InternationalJournal of Computer Vision.2000,38(3):199–218.
[65] KutulakosKN.Approximaten-viewStereo[C].InProceedingsofEuropeanCon-ference on Computer Vision (ECCV)-Part I.2000:67–83.
[66] Bhotika R, Fleet D J, Kutulakos K N. A probabilistic theory of occupancy andemptiness [C]. In Proceedings of European Conference on Computer Vision(ECCV)-Part III.2002:112–132.
[67] Slabaugh G G, Culbertson W B, Malzbender T, et al. Methods for volumetric re-construction of visual scenes [J]. International Journal of Computer Vision.2003,57(3):179–199.
[68] Zeng G, Paris S, Quan L, et al. Progressive surface reconstruction from imagesusing a local prior [C]. In Proceedings of IEEE International Conference on Com-puter Vision (ICCV).2005:1230–1237.
[69] Saito H, Kanade T. Shape reconstruction in projective grid space from large num-ber of images [C]. In Proceedings of IEEE Conference on Computer Vision andPattern Recognition (CVPR).1999:49–54.
[70] YangR,PollefeysM,WelchG.Dealingwithtexturelessregionsandspecularhigh-lights-a progressive space carving scheme using a novel photo-consistency mea-sure [C]. In Proceedings of IEEE International Conference on Computer Vision(ICCV).2003:576–584.
[71] Fua P, Leclerc Y G. Object-centered surface reconstruction: combining multi-image stereo and shading [J]. International Journal of Computer Vision.1995,16(1):35–55.
[72] Rockwood A P, Winget J. Three-dimensional object reconstruction from two-dimensional images [J]. Computer-Aided Design.1997,29(4):279–285.
[73] Isidoro J, Sclaroff S. Stochastic refinement of the visual hull to satisfy photometricand silhouette consistency constraints [C]. In Proceedings of IEEE InternationalConference on Computer Vision (ICCV).2003:1335–1342.
[74] Esteban C, Schmitt F. Silhouette and stereo fusion for3D object modeling [C]. InProceedings of International Conference on3-D Digital Imaging and Modeling.2003:46–53.
[75] Narayanan P J, Rander P W, Kanade T. Constructing virtual worlds using densestereo [C]. In Proceedings of IEEE International Conference on Computer Vision(ICCV).1998:3–10.
[76] Liu Y, Cao X, Dai Q, et al. Continuous depth estimation for multi-view stereo [C].In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR) Workshops.2009:2121–2128.
[77] Furukawa Y, Ponce J. Accurate, dense, and robust multiview stereopsis [J]. IEEETransactions on Pattern Analysis and Machine Intelligence.2010,32(8):1362–1376.
[78] Lhuillier M, Quan L. A Quasi-Dense Approach to Surface Reconstruction fromUncalibrated Images [J]. IEEE Transactions on Pattern Analysis and Machine In-telligence.2005,27(3):418–433.
[79] Zhang G, Jia J, Wong T-T, et al. Consistent Depth Maps Recovery from a VideoSequence [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence.2009,31(6):974–988.
[80] Liu Y, Dai Q, Xu W. A point-cloud-based multi-view stereo algorithm for free-viewpoint video [J]. IEEE Transactions on Visualization and Computer Graphics.2010,16(3):407–418.
[81] Middlebury multi-view stereo evaluation. http://vision.middlebury.edu/mview/.
[82] Strecha C, von Hansen W, Van Gool L, et al. On benchmarking camera calibrationand multi-view stereo for high resolution imagery [C]. In Proceedings of IEEEConference on Computer Vision and Pattern Recognition (CVPR).2008:1–8.
[83] Chari V, Sturm P. Multiple-view geometry of the refractive plane [C]. In Proceed-ings of British Machine Vision Conference (BMVC).2009:1–11.
[84] Chang Y, Chen T. Multi-view3D reconstruction for scenes under the refractiveplanewithknownverticaldirection[C].InProceedingsofIEEEInternationalCon-ference on Computer Vision (ICCV).2011:351–358.
[85] Chang P C Y, Flitton J C, Hopcraft K I, et al. Improving visibility depth in pas-sive underwater imaging by use of polarization [J]. Applied Optics.2003,42(15):2794–2803.
[86] Hou W, Woods S, Jarosz E, et al. Optical turbulence on underwater image degra-dation in natural environments [J]. Applied Optics.2012,51(14):2678–2686.
[87] Queiroz-Neto J P, Carceroni R, Barros W, et al. Underwater Stereo [C]. In CGIP,XVII Brazilian Symposium.2004.
[88] R Ferreira J P C. Stereo reconstruction of a submerged scene [C]. In Proceedingsof Pattern Recognition and Image Analysis: Second Iberian Conference (IbPRIA).2005:102–109.
[89] Pizarro O, Eustice R, Singh H. Relative pose estimation for instrumented, cali-brated imaging platforms [C]. In Proceedings of Digital Image Computing Tech-niques and Applications(DICTA).2003:601–612.
[90] Lavest J M, Rives G, Laprest′e J T. Underwater camera calibration [C]. In Proceed-ings of European conference on Computer vision (ECCV).2000:654–668.
[91] Treibitz T, Schechner Y Y, Singh H. Flat refractive geometry [C]. In Proceedingsof IEEE Conference on Computer Vision and Pattern Recognition (CVPR).2008:1–8.
[92] Agrawal A, Ramalingam S, Taguchi Y, et al. A theory of multi-layer flat refractivegeometry[C].InProceedingsofIEEEConferenceonComputerVisionandPatternRecognition (CVPR).2012:3346–3353.
[93] Sedlazeck A, Koch R. Calibration of housing parameters for underwater stereo-camera rigs [C]. In Proceedings of British Machine Vision Conference (BMVC).2011:1–11.
[94] Hartley R, Sturm P. Triangulation [J]. Computer Vision and Image Understand.1997,68(2):164–157.
[95] Stewenius H, Schaffalitzky F, Nister D. How hard is3-view triangulation re-ally?[C]. In Proceedings of IEEE International Conference on Computer Vision(ICCV).2005:686–693.
[96] Hartley R, Kahl F. Optimal algorithms in multiview geometry [C]. In Proceedingsof Asian conference on Computer vision (ACCV).2007:13–34.
[97] Lourakis M I. Sparse non-linear least squares optimization for geometric vi-sion [C]. In Proceedings of European conference on Computer vision (ECCV).2010:43–56.
[98] Konolige K. Sparse sparse bundle adjustment [C]. In Proceedings of British Ma-chine Vision Conference (BMVC).2010:1–11.
[99] Furukawa Y, Ponce J. Accurate camera calibration from multi-view stereo andbundle adjustment [J]. International Journal of Computer Vision.2009,84(3):257–268.
[100] Avanish Kushal S A. Visibility based preconditioning for bundle adjustment [C].In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR).2012:1442–1449.
[101] Wu F C, Zhang Q, Hu Z Y. Efficient suboptimal solutions to the optimal triangu-lation [J]. International Journal of Computer Vision.2011,91(1):77–106.
[102] Hartley R, Schaffalitzky F. L∞minimization in geometric reconstruction prob-lems [C]. In Proceedings of IEEE Conference on Computer Vision and PatternRecognition (CVPR).2004:504–509.
[103] Kahl F, Hartley R. Multiple view geometry under the L∞-norm [J]. IEEE Trans-actions on Pattern Analysis and Machine Intelligence.2008,30(9):1603–1617.
[104] Kahl F, Agarwal S, Chandraker M K, et al. Practical global optimization formultiview geometry [J]. International Journal of Computer Vision.2008,79(3):271–284.
[105] Sim K, Hartley R. Removing outliers ssing the L∞norm [J]. Proceedings of IEEEConferenceonComputerVisionandPatternRecognition(CVPR).2006:485–494.
[106] Seo Y, Lee H, Lee S W. Outlier removal by convex optimization for L∞ap-proaches [C]. In Proceedings of Pacific-Rim Symposium on Image and VideoTechnology (PSIVT).2009:203–214.
[107] Price K, Storn R M, Lampinen J A. Differential evolution: a practical approach toglobal optimization [M]. Springer-Verlag New York, Inc.,2005.
[108] de la Fraga L G, Silva I V. Direct3D metric reconstruction from two views us-ing differential evolution [C]. In Proceedings of IEEE Congress on EvolutionaryComputation (CEC).2008:3266–3273.
[109] de la Fraga L G, Silva I V. Direct3D metric reconstruction from multiple viewsusingdifferentialevolution[C].InApplicationsofEvolutionaryComputing.2008:341–346.
[110] de la Fraga L. Self-calibration from planes using differential evolution [C]. InProgress in Pattern Recognition, Image Analysis, Computer Vision, and Appli-cations.2009:724–731.
[111] de la Fraga L, Schu¨tze O. Direct calibration by fitting of cuboids to a single imageusing differential evolution [J]. International Journal of Computer Vision.2009,81(2):119–127.
[112] Lafarge F, Keriven R, Br′edif M, et al. Hybrid multi-view reconstruction by Jump-Diffusion[C].InProceedingsofIEEEConferenceonComputerVisionandPatternRecognition (CVPR).2010:350–357.
[113] Boyd S, Vandenberghe L. Convex optimization [M]. Cambridge University Press,2004.
[114] Triggs B, Mclauchlan P F, Hartley R I, et al. Bundle adjustment: a modern syn-thesis [C]. In Proceedings of IEEE International Conference on Computer Vision(ICCV) Workshops.1999:298–372.
[115] Nister D. An efficient solution to the five-point relative pose problem [J]. IEEETransactionsonPatternAnalysisandMachineIntelligence.2004,26(6):756–777.
[116] Kanatani K, Matsunaga C. Closed-form expression for focal lengths from the fun-damental matrix [C]. In Proceedings of Asian Conference on Computer Vision(ACCV).2000:128–133.
[117] Bougnoux S. From projective to euclidean space under any practical situation, acriticism of self calibration [C]. In Proceedings of IEEE International Conferenceon Computer Vision (ICCV).1998:790–796.
[118] Lourakis M, Deriche R. Camera self-calibration using the singular value decom-position of the fundamental matrix [C]. In Proceedings of Asian Conference onComputer Vision (ACCV).2000:403–408.
[119] Hartley R, Silpa-Anan C. Reconstruction from two views using approximate cal-ibration [C]. In Proceedings of Asian Conference on Computer Vision (ACCV).2002:388–343.
[120] Sturm P. On focal length calibration from two views [C]. In Proceedings of IEEEConferenceonComputerVisionandPatternRecognition(CVPR).2001:145–150.
[121] SturmaP,ChengZ,ChencP,etal.Focallengthcalibrationfromtwoviews:methodand analysis of singular cases [J]. Computer Vision and Image Understanding.2005,99(1):58–95.
[122] Bujnak M, Kukelova Z, Pajdla T.3D reconstruction from image collections witha single known focal length [C]. In Proceedings of IEEE International Conferenceon Computer Vision (ICCV).2009:1803–1810.
[123] Ueshiba T, Tomita F. Self-calibration from two perspective views under variousconditions: closed-form solutions and degenerate configurations [C]. In Proceed-ingsof Australia-JapanAdvancedWorkshoponComputerVision.2003:118–125.
[124] Li H. A simple solution to the six-point two-view focal-length problem [C]. InProceedingsofEuropeanconferenceonComputervision(ECCV).2006:200–213.
[125] Shoemake K. Animating rotation with quaternion curves [C]. In Proceedings ofACM SIGGRAPH.1985:245–254.
[126] Kanatani K, Sugaya Y, Niitsuma H. Triangulation from two views revisited:Hartley-Sturm vs. optimal correction [C]. In Proceedings of British Machine Vi-sion Conference (BMVC).2008:173–182.
[127] FischlerMA,BollesRC.Randomsampleconsensus:aparadigmformodelfittingwith applications to image analysis and automated cartography [J]. Communica-tions of the ACM.1981,24(6):381–395.
[128] Torr P. Bayesian model estimation and selection for epipolar geometry and genericmanifoldfitting[J].InternationalJournalofComputerVision.2002,50(1):35–61.
[129] TakahamaT,SakaiS.Efficientconstrainedoptimizationbytheεconstrainedadap-tive differential evolution [C]. In Proceedings of IEEE Congress on EvolutionaryComputation (CEC).2010:2052–2059.
[130] TakahamaT,SakaiS.Fastandstableconstrainedoptimizationbytheεconstraineddifferential evolution [J]. Pacific Journal of Optimization.2009,5(2):261–282.
[131] C implementation of εADE. http://www.ints.info.hiroshima-cu.ac.jp/~takahama/eng/.
[132] Digital bunny model. http://graphics.stanford.edu/data/.
[133] Demˇsar J. Statistical comparisons of classifiers over multiple data sets [J]. Journalof Machine Learning Research.2006,7:1–30.
[134] Martine D, Pajdla T. Robust rotation and translation estimation in multiview re-construction [C]. In Proceedings of IEEE Conference on Computer Vision andPattern Recognition (CVPR).2007:1–8.
[135] Ke Q, Kanade T. Quasiconvex optimization for robust geometric reconstruc-tion [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence.2007,29(10):1834–1847.
[136] Lu F, Hartley R. A fast optimal algorithm for L2triangulation [C]. In Proceedingsof Asian Conference on Computer Vision (ACCV)-Part II.2007:279–288.
[137] Agarwal S, Snavely N, Seitz S M. Fast algorithms for L∞problems in multiviewgeometry.2008.
[138] Byrod M, Josephson K. Fast optimal three view triangulation [C]. In Proceedingsof Asian Conference on Computer Vision (ACCV).2007:549–559.
[139] Olsson C, Kahl F. Generalized convexity in multiple view geometry [J]. Journalof Mathematical Imaging and Vision.2010,38(1):35–51.
[140] Li H. Efficient reduction of L-infinity geometry problems [C]. In Proceedings ofIEEE Conference on Computer Vision and Pattern Recognition (CVPR).2009:2695–2702.
[141] Dalalyan A, Keriven R. L1-penalized robust estimation for a class of inverse prob-lems arising in multiview geometry [C]. In Proceedings of Advances in NeuralInformation Processing Systems22.2009:441–449.
[142] YuX,BuiTD,KrzyzakA.Robustestimationforrangeimagesegmentationandre-construction [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence.1994,16(5):530–538.
[143] WangH,SuterD.Robustadaptive-scaleparametricmodelestimationforcomputervision [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence.2004,26(11):1459–1474.
[144] Lavine M. Introduction to statistical thought [M]. University Press of Florida,2009.
[145] Silverman B W. Density estimation: for statistics and data analysis [M].1st ed.Chapman and Hall/CRC,1986.
[146] Rousseeuw P J, Leroy A M. Robust regression and outlier detection [M]. JohnWiley&Sons, Inc.,1987.
[147] FarenzenaM,FusielloA.Reconstructionwithintervalconstraintspropagation[C].In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition(CVPR).2006:1185–1190.
[148] Moore R E. Interval analysis [M]. Prentice-Hall,1966.
[149] Sturm J F. Using SeDuMi1.02, a MATLAB toolbox for optimization over sym-metric cones [J]. Optimization Methods and Software.1999,11(1):625–653.
[150] Andersen E D, Andersen K D. The MOSEK interior point optimization for lin-ear programming: an implementation of the homogeneous algorithm [M]. In HighPerformance Optimization. Kluwer Academic Publishers,1999:197–232.
[151] Toh K C, Todd M, T¨ut¨unc¨u R H. SDPT3-a MATLAB software package forsemidefinite programming [J]. Optimization Methods and Software.1999,11(1):545–581.
[152] Lu C-P, Hager G D, Mjolsness E. Fast and globally convergent pose estimationfrom video images [J]. IEEE Transactions on Pattern Analysis and Machine Intel-ligence.2000,22(6):610–622.
[153] GlaeserG,SchrockerH-P.Reflectionsonrefractions[J].JournalforGrometryandGraphics.2000,4(1):1–18.
[154] Edelman A, Murakami H. Polynomial roots from companion matrix eigenval-ues [J]. Mathematics of Computation.1995,64(210):763–776.
[155] The MOSEK optimization software. http://www.mosek.com/.
[156] POVRay. http://www.povray.org/.
[157] Snavely N, Seitz S M, Szeliski R. Photo tourism: exploring photo collections in3D [C]. In Proceedings of ACM SIGGRAPH.2006:835–846.
[158] Kunz C, Singh H. Hemispherical refraction and camera calibration in underwatervision [C]. In Proceedings of OCEANS.2008:1–7.
[159] Telem G, Filin S. Photogrammetric modeling of underwater environments [J]. IS-PRS Journal of Photogrammetry and Remote Sensing.2010,65(5):433–444.
[160] Horn B K P. Closed-form solution of absolute orientation using unit quater-nions [J]. Journal of the Optical Society of America A.1987,4(4):629–642.
[161] D Chetverikov D S, D Svirko, Krsek P. The trimmed iterative closest point al-gorithm [C]. In Proceedings of International Conference on Pattern Recognition(ICPR).2002:545–548.
[162] Lei C. A cluster based free viewpoint video system using region-tree based scenereconstruction [D]. Canada: Department of Computing Science, University of Al-berta,2009.
[163] DaiY,LiH,HeM.Asimpleprior-freemethodfornon-rigidstructure-from-motionfactorization [C]. In Proceedings of IEEE Conference on Computer Vision andPattern Recognition (CVPR).2012:2018–2025.
[164] Clark J H. Hierarchical geometric models for visible surface algorithms [J]. Com-munications of the ACM.1976,19(10):547–554.
[165] Liu C, Yuen J, Torralba A. SIFT flow: dense correspondence across scenes and itsapplications [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence.2011,33(5):978–994.
[166] Tola E, Lepetit V, Fua P. DAISY: an efficient dense descriptor applied to wide-baseline stereo [J]. IEEE Transactions on Pattern Analysis and Machine Intelli-gence.2010,32(5):815–830.