基于最优RANSAC算法的非增加式多视图三维重建

基于最优RANSAC算法的非增加式多视图三维重建

管秋1，金俊杰1，张剑华1，李德明2

(1.浙江工业大学 计算机科学与技术学院，浙江 杭州 310023；2.浙江商业职业技术学校 应用工程学院，浙江 杭州310018)

摘要：非增加式的多视图三维重建算法不依赖于初始重建，而是首先求解全部的摄像机参数，然后一次性重建所有三维点，其难点在于如何精确的求得全局旋转矩阵和全局平移向量.针对摄像机旋转矩阵计算的问题，引入最优RANSAC算法来稳定剔除错误的二视图关系，避免了人为设定阈值的不可靠性，提高了全局旋转矩阵的计算精度.针对摄像机平移向量计算的问题，结合了黄金分割方法与线性规划来精确计算三视图相对平移向量，提高了相对平移向量计算的精度，从而提高了最终全局平移向量的精度.实验结果表明，设计的算法能有效的提高三维重建精度.

关键词：非增加式；多视图；三维重建；随机抽样一致性；黄金分割

收稿日期：2015-04-21

基金项目：国家自然科学基金资助项目(61103140)

作者简介：管秋(1972—)，女，浙江瑞安人，教授，研究方向为计算机视觉和医学图像处理，E-mail：gq@zjut.edu.cn.

中图分类号：TP391.4

文献标志码：A

文章编号：1006-4303(2015)05-0473-06

Abstract:Non-sequential multi-view 3D reconstruction algorithm does not depend on the initial reconstruction. Firstly,the compute camera matrix of all views are solved, then all 3D points are reconstructed at once. The difficulty of non-sequential method is to compute the global rotations and global translations accurately. As to the computation of the global rotations, a robust algorithm is designed to remove the outliers of pairwise geometric relations base on “a contrario” formulation of RANSAC, which avoid from setting an unreliable threshold, so it can increase the accuracy of the global rotations. As to computation of the global translations, an algorithm combined golden section with linear programming is proposed to accurately compute the relative translations vector in triple of views, so it can be used to improve the accuracy of global translations. Testing results shows that our algorithm can effectively improve the accuracy of the 3D reconstruction.

Keywords:non-sequential; SFM; 3D reconstruction; AC-RANSAC; golden section

Non-sequential multi-view 3D reconstruction base on ac-ransac

GUAN Qiu1, JIN Junjie1, ZHANG Jianhua1, LI Deming2

(1.College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China；

2.College of Application Engineering, Zhejiang Business College, Hangzhou 310018, China)

三维重建是计算机视觉的重要研究领域，与人脸识别[1]和目标跟踪[2]一样具有重要的应用价值.其方法经历了从基于双目立体匹配[3]的重建到基于多视图的重建的过程.传统增加式的多视图的重建方法[4-5]一方面过度依赖于初始重建的结果，导致精确较低；另一方面，多次捆集调整[6]也使得算法的执行效率低，当视图数量越多时其低效性表现的越显著[7].相比之下，非增加式的方法，既不依赖初始重建，又无需进行多次捆集调整，其精确和速度都优于增加式的方法，因此成为近几年多视图三维重建领域的研究热点.

引入了最优RANSAC算法来稳定剔除错误的二视图关系，避免了现有方法需要人为指定阈值的缺陷，实现了稳定的剔除错误二视图关系的目的，保证了全局旋转矩阵计算的精度.结合了黄金分割搜索方法来精确求解三视图之间的相对平移向量，提高了平移向量计算的精度，最终实现了高精度的非增加式三维重建.

1非增加式三维重建中的关键计算

基于多视图的三维重建的主要步骤为：图像特征提取与匹配、摄像机参数的计算、三维点云的计算与捆集调整[6]等.其中，摄像机参数的计算是非增加式重建方法与增加式方法的不同之处.非增加式三维重建的关键是利用相对旋转矩阵和相对平移向量来计算全局旋转矩阵与全局平移向量.由于相对旋转矩阵不受基线宽度的影响，其可靠性更高，而二视图平移向量受基线影响大，精度较低[8].因此，通常首先计算全局旋转矩阵，然后再在已知全局旋转矩阵的情况下计算全局平移向量.图1为非增加式多视图三维重建的流程图.

图1　非增加式三维重建流程图 Fig.1　Process of non-sequential 3D reconstruction

1.1全局旋转矩阵的计算

全局旋转矩阵的计算所用利的公式为

Rj=RijRi

(1)

式中：Rij为已知的相对旋转矩阵；Ri，Rj为待求的全局旋转矩阵.

1.2全局平移向量的计算

全局平移向量的计算需要利用二视图相对平移向量，最直接的方法是利用本质矩阵分解[14]得到相对平移向量.然而，由于本质矩阵分解的平移向量受基线影响大，且尺度不统一，所以给全局平移向量的计算增加了困难.GOVINDU[15]利用向量积与迭代计算方法解决了尺度不统一的问题，但仍存在相对平移向量精度低的问题.WILSON等[16]利用非线性优化方法首先计算出每幅视图的摄像机位置，然后再平移向量，该方法也未解决相对平移向量精度低问题.SIM等[17]利用更紧凑的三焦点张量来得到相对平移向量，但该方法忽略了三视图匹配之间存在误匹配的情况.MOULON等[13]则在已知全局旋转矩阵的情况下利用一种线性规划计算三视图相对平移向量，该方法通过指定目标函数最小值来将原非线性模型变为线性模型，提高了计算效率，但同时牺牲了精度.

2全局旋转矩阵的稳定计算

全局旋转矩阵计算难点在于如何稳定的剔除错误的二视图关系，为此，引入最优RANSAC算法来达到稳定地剔除错误的二视图关系的目的，该算法是a contrario思想与RANSAC算法的结合，其首先被命名为OPSA[18](最优RANSAC)，随后又被重命名为AC-RANSAC[19].经典的RANSAC算法依赖于一个固定的阈值参数，最后选择保留样本数量最多的模型为正确的模型，然而不同的阈值参数选择往往会造成结果的差别较大[20].最优RANSAC算法则避免了设定固定阈值，而是通过计算一个表达式NFA(Number of false alarms)的值来评价当前模型的可靠性，并将使NFA值最小的模型作为最可靠的模型.NFA的计算公式为

(2)

式中：M为当前计算出的模型参数;k为当前假设的正确样本的数量;n为总样本的数量;ns为用于计算模型参数M的最少样本数量;ek(M)为所有样本关于模型M的误差中的第k小误差;α0为随机误差为1的概率.

将最优RANSAC算法应用于错误的二视图关系的剔除上来，则式(2)中M则表示由随机生成树计算出的初始的全局旋转矩阵；n和ns则分别表示总共的二视图关系数量以及随机生成树上的边的条数；α0则表示随机误差为1°的概率(算法中取1/180).任意样本的误差计算方法为相对旋转矩阵与全局旋转矩阵的角度差值，其公式为

E=D(Rj,RijRi)

(3)

式中：D(a,b)为向量a和b的夹角；Ri与Rj为全局旋转矩阵；Rij为相对旋转矩阵.

在准确的剔除了错误的二视图关系之后，全局旋转矩阵的计算采用旋转矩阵分列求解后融合的算法[9].

表1为剔除错误二视图关系的结果对比图，用于测试的数据集有经典的三维重建数据集以及利用航拍获取的数据集.其中，第1列为数据集(“CastlaP30”表示图像名称为“Castle”视图数量为30张)，第2列为经过特征匹配后初始的二视图关系(边)数量，第3列为不同算法剔除的边的数量和所占的比例.从表1中可看出：在“CastleP30”、“图书馆P68”与钟楼“P104”上，三种算法的结果差别不大，剔除边的数量基本相同，但在“清华学堂P76”数据集上，2°检测算法[13]与经典RANSAC算法[10]都剔除了大量的二视图关系，而最优RANSAC算法则保留了更多的二视图关系，图4为在“清华学堂P76”的最终重建结果，图4可以看出：由于笔者方法能保留更多的可靠二视图关系，从而其重建出的模型的几何精确度明显高于另外两种方法.

表1　剔除错误二视图关系结果

3全局平移向量的精确计算

为了提高平移向量的精度，利用联系更紧凑的三视图关系来计算相对平移向量，然后再计算全局平移向量.

利用三视图之间的重投影误差最小化的约束来计算三视图之间的相对平移向量[13]，同时加入黄金分割方法来逐步搜索目标函数的最小值.在已知全局旋转矩阵的情况下，重投影误差的计算方法为

(4)

(5)

式中：第二条约束为保证所有三维点都在摄像机前方，第三条约束为将第一个摄像机的坐标系指定为世界坐标系，第四条约束为重投影误差必须大于零.由于目标函数γ与Xj，ti均为未知，因此第一条约束为非线性约束，该模型为非线性模型，MOULON[13]通过指定γ为一个较小的值(0.5)，从而将第一条约束降低为线性约束，进而将模型变换为线性模型，利用线性规划的函数库可以快速求解此类模型.然而，指定γ的值为0.5缺乏说服力.通过利用黄金分割搜索方法来精确定位γ的最小值，其过程可分为5步过程.

步骤1设定γ的上下界分别为γdown=0,γup=1.

步骤2将当前γup代入式(5)中进行求解.

步骤3若式(5)无解则直接退出，否则利用黄金比例分割搜索区间得到分割点γ1和γ2.

步骤4将γ1代入式(5)中，若有解则更新γup=γ1，否则更新γdown=γ1并将γ2代入式(5)中求解，若有解则更新γup=γ2，否则更新γdown=γ2.

步骤5重复步骤3和4，直到γup-γdown的值小于给定值(设定为1×10-4).

在精确计算了三视图相对平移向量之后，采用线性规划模型[13]来计算全局的平移向量.

表2为上不同数据集上利用黄金分割方法结合式(5)后得到的目标函数γ的最小值的平均值，相比于直接设定γ=0.5，加入黄金分割方法后能更精确的定位γ的最小值.

图2为在“CastlaP30”数据集上所有三视图之间重投影误差的平均值的对比图，在其余三个数据集上也有相同的结果.其中，纵坐标为重投影误差，横坐标为三视图关系的编号，星线为指定γ=0.5的结果，圈线为加入黄金分割方法后的结果.可以明显看出：圈线总是处于星线下方，且在大量三视图关系中纵坐标的差值较大(部分超过了0.5个像素)，说明了加入黄金分割方法之后三视图关系中的重投影误差有了显著的减小，相对平移向量的精度有了显著提高.

表2　式(5)中γ的最小值的平均值

图2　CastleP30三视图重投影误差 Fig.2　Reprojection error of “CastleP30”

4重建系统实现与实验分析

实验环境为ubuntu14.04，编程语言为C++和Python，所用外部函数库为OpenCV，三维重建基础框架为OpenMVG，将最优RANSAC算法和黄金分割结合线性规划的方法融入OpenMVG框架，形成了实验用的三维重建系统.

图3为在“钟楼P104”上稀疏重建加上稠密重建[21]的重建结果对比，从左到右分别为在剔除的二视图关系上采用不同算法，但在重建算法的其余模块采用OpenMVG中的算法的结果.可以看出三种方法的重建结果无明显差别，均能正确的重建出场景的结构，类似的在“CastleP30”与“图书馆P68”两个数据集上也得出了相似的重建结果.图4为在“清华学堂P76”数据集上的重建结果对比，其中第一行为正面视角的效果图，第二行为垂直视角的效果图.从图4可以看出：图4(a)中的重建墙面结构更精确，而图4(b)中墙面则出现断裂(方框1所示)，图4(c)中则只重建出一部分墙面(方框2所示为缺失部分).可以说明，引入最优RANSAC算法后，最终的重建结果精度在此数据集上有明显的提高.在四个数据集上的测试结果表明，算法总是能得到与同类算法相同或更好的重建结果，因此说明了算法具有更好的稳定性.

图5为算法与经典的增加式Bundler重建算法在“CastleP30”上的重建效果对比图.从图5中可以看出：方框1，2所示的区域右图区域的稠密度更高，方框3所示的区域右图的几何结构更精确(左图中的墙面出现了明显的不连续，右图则给出了正确的结果).图6为在“钟楼P104”的重建结果对比图，可以看出：Bundler算法重建出的钟楼出现了明显的误差，出现了两个钟楼，而笔者算法则得出了结构正确的重建结果.充分体现了算法相比于传统增加式方法的优势.

图3　“钟楼P104”重建结果 Fig.3　Reconstruction of “zhonglouP104”

图4　“清华学堂P76”重建结果 Fig.4　Reconstruction of “qinghuaxuetangP76”

图5　CastleP30重建效果对比 Fig.5　Reconstruction of CastleP30

图6　“钟楼P104”重建效果对比 Fig.6　Reconstruction of “zhonglouP104”

5结论

针对非增加三维重建过程旋转和平移向量的计算精度问题，设计了一种基于最优RANSAC算法的错误二视图关系剔除算法，提高了旋转矩阵计算的稳定性；提出了一种基于黄金分割与线性规划方法的平移向量计算的改进算法，提高了平移向量的计算精度.实验结果表明：算法相比于同类算法能得到相同或更好的重建结果，体现了更好的稳定性，同时也明显优于传统增加式的算法.

参考文献：

[1]汤一平，严海东．非约束环境下人脸识别技术的研究[J]．浙江工业大学学报，2010，38(2):155-161.

[2]杨东勇，冯形松．采用形态学算子的运动目标检测跟踪方法研究及实现[J]．浙江工业大学学报，2010，38(2):149-154.

[3]汤一平，庞成俊，周宗思，等．双目全方位视觉传感器及其极线校正方法[J]．浙江工业大学学报，2011，39(1):86-91.

[4]POLLEFEYSM,VANGOOLL,VERGAUWENM,etal.Visualmodelingwithahand-heldcamera[J].InternationalJournalofComputerVision,2004,59(3):207-232.

[5]SNAVELYN,SEITZSM,SZELISKIR.Phototourism:exploringphotocollectionsin3D[C]//ACM.TransactionsonGraphics(TOG).NewYork：ACM,2006,25(3):835-846.

[6]TRIGGSB,MCLAUCHLANPF,HARTLEYRI,etal.Bundleadjustment-amodernsynthesis[C]//VisionAlgorithms:TheoryandPractice.Corfu,Greece：SpringerBerlinHeidelberg,2000:298-372.

[7]CORNELISK,VERBIESTF,VANGL.Driftdetectionandremovalforsequentialstructurefrommotionalgorithms[J].PatternAnalysisandMachineIntelligence,IEEETransactionson,2004,26(10):1249-1259.

[8]ENQVISTO,KAHLF,OLSSONC.Non-sequentialstructurefrommotion[C]//ComputerVisionWorkshops(ICCVWorkshops).IEEEInternationalConferenceonComputerVision.Barcelona,Spain：IEEE,2011:264-271.

[9]MARTINECD,PAJDLAT.Robustrotationandtranslationestimationinmultiviewreconstruction[C]//CVPR.IEEEConferenceonComputerVisionandPatternRecognition.Minneapolis,Minnesota：IEEE,2007:1-8.

[10]GOVINDUVM.Robustnessinmotionaveraging[C]//ComputerVision-ACCV2006.Hyderabad,India:SpringerBerlinHeidelberg,2006:457-466.

[11]OLSSONC,ENQVISTO.Stablestructurefrommotionforunorderedimagecollections[C]//SCIA.ImageAnalysis.Ystad,Sweden：SpringerBerlinHeidelberg,2011:524-535.

[12]ZACHC,KLOPSCHITZM,POLLEFEYSM.Disambiguatingvisualrelationsusingloopconstraints[C]//CVPR.IEEEConferenceonComputerVisionandPatternRecognition.SanFrancisco,CA,USA:IEEE,2010:1426-1433.

[13]MOULONP,MONASSEP,MARLETR.Globalfusionofrelativemotionsforrobust,accurateandscalablestructurefrommotion[C]//ComputerVision(ICCV).IEEEInternationalConferenceonComputerVision.Sydney：IEEE,2013:3248-3255.

[14]HARTLEYR,ZISSERMANA.计算机视觉中的多视图几何[M]．韦穗，杨尚骏，章权兵，等译.1版.合肥：安徽大学出版社，2002：173-175.

[15]GOVINDUVM.Combiningtwo-viewconstraintsformotionestimation[C]//CVPR.IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.Kauai,HI,USA：IEEE,2001:218-225.

[16]WILSONK,SNAVELYN.Robustglobaltranslationswith1DSfM[C]//ECCV.ComputerVision.Zurich,Switzerland：SpringerInternationalPublishing,2014:61-75.

[17]SIMK,HARTLEYR.Recoveringcameramotionusinglinftyminimization[C]//CVPR.IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.NewYork,NY,USA：IEEE,2006:1230-1237.

[18]MOISANL,STIVALB.Aprobabilisticcriteriontodetectrigidpointmatchesbetweentwoimagesandestimatethefundamentalmatrix[J].InternationalJournalofComputerVision,2004,57(3):201-218.

[19]RABINJ,DELONJ,GOUSSEAUY,etal.MAC-RANSAC:arobustalgorithmfortherecognitionofmultipleobjects[C]//FifthInternationalSymposiumon3DDataProcessing,VisualizationandTransmission(3DPTV2010).Paris,France：3DPTV，2010:51.

[20]MOULONP,MONASSEP,MARLETR.AdaptiveStructurefromMotionwithacontrariomodelestimation[C]//ComputerVision-ACCV2012.Daejeon,Korea：SpringerBerlinHeidelberg,2013:257-270.

[21]FURUKAWAY,PONCEJ.Accurate,dense,androbustmultiviewstereopsis[J].PatternAnalysisandMachineIntelligence,IEEETransactionson,2010,32(8):1362-1376.

(责任编辑：刘岩)