以多幅图像非几何约束线段匹配重建建筑物外立面三维线段模型

张琳彦，朱利

（1. 西安交通大学电子与信息工程学院，710049，西安；2. 西安交通大学软件学院，710049，西安）

传统上基于图像的建筑物外立面三维重建得到的是三维点云模型，但点特征却缺乏描述场景整体结构的能力[1-2]。人工建筑物场景的框架主要由线段构成，建筑物外立面三维线段重建，就是通过获取建筑物外立面的二维线段在空间中的三维信息得到其三维线段模型。如图 1所示，该建筑物的三维点云模型在缺少纹理的地方重建精度较差，而三维线段模型却能提供更充分的结构信息，反映场景的几何拓扑关系[3]。

建筑物外立面三维线段重建大体分为 3步，首先提取图像中的特征线段，再匹配特征线段，最后根据匹配线段之间的对应关系重建出目标建筑物的三维线段模型。

图1 三维点云模型与三维线段模型

特征线段的提取主要针对构成建筑物结构信息的边界。，LSD(Line Segment Detector)[4]是目前较稳定的线段提取算法，该算法具有错误控制功能，保证了线段检测结果的正确性。

特征线段匹配是在提取到的特征线段中，寻找同一条空间线段在不同成像图像上的投影。特征线段具有首末端点不易界定的特点，且同一条空间线段在不同图像中的投影线段之间缺乏很强的约束[5]。应用较广的传统特征线段匹配算法一般是依据图像间预先获知的对极几何约束，只能匹配两幅或三幅图像间的线段[5-6]。近年来提出的不单纯利用几何约束的线段匹配算法[7-9]，虽然在一定程度上克服了纯几何约束的缺点，但只能匹配两幅图像间的线段。由文献[5]扩展的算法[10]和 lmatch算法[11]对多幅图像间线段的匹配效果虽然都较好，但都要预先获取对极几何知识，求解过程较繁琐。

得到多幅图像之间线段的对应关系后，即可重建出建筑物的三维线段结构。Hartley等提出的平面交线法[12]，求解过程受到特征线段首尾端点提取不准确的干扰。Werner也使用平面交线法重建三维线段，但要求输入图像必须含有三个相互正交的主方向[13]，现实中并不是所有的建筑物图像都能满足此要求。

针对上述问题，本文提出了一种改进算法。在特征线段匹配时，结合稳定性更高的双视图匹配算法，参照lmatch算法[11]的框架，进行多幅图像间的线段匹配。随后采用拼接的方式对匹配线段组进行三维线段重建，将每一条特征线段对应的空间线段片段连缀成一条完整的空间线段，并筛除部分空间线段，得到简洁的建筑物三维线段模型。

1 算法

1.1 多幅图像间的特征线段匹配

1.1.1 初始匹配线段组设输入M幅图像，第m幅图像用LSD算法[4]提取Jm条线段，m= 1 ,2,…M，其第j条线段记为l={(xs,ys),(xe,ye)}，j= 1 ,2,…J，

mjmjmjmjmjm

(xs,ys)和(xe,ye)分别是线段l的首尾坐标。摄像

mjmjmjmjmj

机矩阵P3×4已知，通过SVD分解可计算得到相应光心，光心距离是两个光心向量之间的欧氏距离。

根据输入图像光心之间的距离，均匀选取光心距离最近的若干组图像对作为基础图像对，记为(mp,mq)，p,q∈ [1,M]。(mp,mq)中两幅图像的特征线段匹配采用点线相结合的算法[9]，产生的匹配线段集合记为Spq，Spq中任一组匹配线段si={lpj,lqb}的相似度为ri=SimL(lpj,lqb)，i= 1 ,2,… ,Ipq，Ipq为Spq中匹配线段组的总数。记k(Spq)为基础图像对图像p,q，k＇ (Spq)为未与p,q匹配的图像，Θ为计算得到的所有匹配线段组的集合。

对每一组基础图像对(mp,mq)，都重复下列步骤。

步骤1更新Θ为Θ:=Θ∪Spq。

步骤 2根据光心距离，由式(1)计算k＇ (Spq)中与k(Spq)图像距离最近的图像mp

计算(mp,mp)中所有的匹配线段。若mp中的线段lpa与Spq中的si相对应，如lpa与lpj匹配，则将lpa纳入si中，si:={lpj,lqb,lpa}，ri:=ri+SimL(lpj,lpa)；若lpa与lpc形成了新的匹配线段组sv={lpa,lpc}，则Spq:=Sp∪qs，该组新匹配的相似度为rv=Si(mLl,p，同 时 ，Ipq:=Ipq+1，k＇(Spq):=k＇(Spq)mp。

步骤3重复步骤2，直到k＇ (Spq)中没有图像。

1.1.2 筛选匹配在上述过程结束后，Θ中包含了M幅图像间所有的匹配线段组，但此时Θ中各匹配线段组之间的关系还不准确。两个匹配线段组之间的关系可能会有三种情况：相同匹配（两组匹配包含的数据完全一致）、相容匹配（两组匹配包含的数据不一致，但不存在互相矛盾）和不相容匹配（两组匹配包含的数据互相矛盾，如一幅图中的一条线段与另一幅图中的两条不同线段形成匹配）。

在对各匹配线段组之间关系的分析基础上，对Θ中数据进行筛选和整合，最终的准确数据会存放在Θ*中，具体步骤如下。

步骤 1在Θ中选取相似度最高的匹配线段组si，Θ*:=Θ*∪si，Θ:=Θsi。

步骤 2遍历Θ中的sk，与si比较，若si与sk是相容匹配，则将sk中与si不同的匹配线段合并入si，Θ:=Θsk；若si与sk是完全相同匹配或不相容匹配，则Θ:=Θsk。

步骤 3重复步骤 1和步骤 2，直至Θ中没有匹配线段组。

图2所示为Wadham学院基准图像集[14]中一幅图像的特征线段匹配结果。图2a和图2b分别是本文算法和lmatch算法的结果。上方图像为在输入原图上标注的匹配结果，图中标注有数字的线段属于各匹配线段组；下方图像为局部放大图。由图可见，在本文算法匹配部分的结果中，建筑物外立面中大部分的线段都能在不同的图像中找到正确的匹配，lmatch算法虽然也可以找到正确的匹配结果，但匹配的线段数量较为稀疏，并且基本都是直边缘的线段，大门等存在弧形边缘的部分没有匹配线段结果。因此，本文方法得到的匹配线段组更为细致。

1.2 空间三维线段重建

1.2.1 重建初始三维线段下面以N(N≤M)幅图像重构为例详述平面交线法[12]重构三维线段的过程。假设有一组匹配线段组si= {l1a,l2b,… ,lNd}，N幅图像对应的摄像机矩阵分别为P1，P2，…，PN。

首先重建匹配线段组si对应的空间直线。经过线段的直线记作Imj，由直线反向投影定义的平面是πmj=Imj，为Pm转置。将si中的N条线段按照上述的过程，生成N个相互对应的平面π1a，π2b，…，πNd。

综上，对比两种不同取心钻具所获取的岩心样品质量以及表1所示的岩心采取率，TK-NCC01型钻具的优势极为明显，表现为以下两点：①岩心质量方面，原有超前单动双管钻具获取的岩心较松散；而TK-NCC01型钻具所获取的岩心相对比较完整，而且从图8左图可以看出，岩心样品扰动很小，基本保持了岩心原状。②在同区域相同地层中TK-NCC01型钻具岩心采取率远高于超前单动双管钻具，总进尺6 m，获得岩心5.13 m，平均岩心采取率为85.5%。较超前单动双管钻具增加了52.5%，提高了159%。

N条投影直线I1a、I2b、…、INd是由同一条空间直线W（未知）产生的，所以π1a、π2b、…、πNd交于这条公共的三维直线。这个相交约束可以描述为N×N的矩阵

若AV=0，则点V在该重构直线W上。根据空间直线的平面表示方法[12]，A的秩为2，可推出该重构直线W上的点可表示为V=αξ0+βξ1，其中ξ0和ξ1是A的零空间的标准正交基。

图2 多幅图像特征直线段匹配结果

得到了空间直线上任一点的表达方式，便可据此在重构直线上截取匹配线段组对应的空间线段。传统的做法通过最小化重投影误差之和，对该空间线段首尾端点的确切位置进行最大似然估计。由于不能保证准确提取到线段真实的首末端点，并且计算时存在累积误差，故最大似然估计的结果通常不理想。

针对上述缺陷，本文通过分段的方式得到三维空间线段，具体步骤如下。

步骤 1对一个匹配线段组中的一条线段，按照最大似然准则，求解对应的三维空间子线段。此时每一条三维子线段都不受匹配线段组中其他线段位置的影响，与相应的图像线段是准确对应的。

匹配线段组中任一条线段对应的三维子线段都在W上，故可由W上的两点定义该空间线段的首尾端点。取si中的线段l1a，设l1a对应的三维子线段为W1a={V0,V1}，其中V0=α0ξ0+β0ξ1，V1=α1ξ0+β1ξ1。依据最大似然准则，最小化W1a到图像1的投影与l1a之间的重投影误差，得到每个参数的值。

步骤 2对匹配线段组si中的每一条线段都重复步骤1，直到所有线段都生成对应的空间三维线段。

步骤 3将以上得到的所有三维子线段按照首尾相接的方式连接起来，形成一段完整的与si相对应的空间三维线段，记作W*。

步骤 4对Θ*中的每一个匹配线段组都重复步骤 1~步骤3，直到每一个匹配线段组都得到了其对应的空间三维线段。

得到建筑物三维重建的初始结果。如图3所示，从图中已经可以看到建筑物的整体形状（共 630条线段），但结果中还有一些错误的线段（图3中的黑色线段）需要在后续处理中去除。

图3 建筑物三维重建的初始结果

1.2.2 过滤初始三维线段如图3所示，由于线段提取错误、线段匹配错误等原因，重建出的线段也会有错误，这些错误的线段称为“非期望假设”[15]。本文通过各种约束对其剔除。

长度约束是限制空间线段的长度。有一类“非期望假设”的长度远大于组成建筑物的线段长度，因此可对空间线段的长度进行约束，将大于某一长度d0的线段丢弃。如图4所思，图4a为图3经过长度约束后得到的结果（共473条线段）。

误差约束是控制重投影误差。计算某一匹配线段组对应的空间三维线段与匹配线段组中各线段之间的重投影误差之和，当误差小于阈值d1时，该空间线段才能被保留。

角度约束是限制空间线段与空间平面的夹角大小。一般构建建筑物的线条方向主要集中在某几个方向，而“非期望假设”的方向却通常杂乱无章，可以通过同时约束三维线段到任意两个垂直平面的夹角，进一步剔除“非期望假设”。对夹角值分别进行分段统计，同时保留满足两种夹角值都占优（线段数最多）的空间线段。当加入的分段数目达到设定阈值d3时停止。图4b为图4a经过角度约束后的效果，共410条线段。

图4 长度约束与角度约束后的结果

2 实验结果及分析

实验中的两个图像集均采用手持相机拍摄。角度约束时，两种夹角值都是按照每 15度分一段。lmatch算法的参数DispRange设置为400。

2.1 实验结果

第一组实验重建具有平面状的建筑物外立面。使用西安交通大学化工楼图像集，共33幅大小为1 028×960的图像，如图5所示。图5a为其中一幅图像；图5b和图5c分别为lmatch算法和本文算法的重建结果。实验中d0为2.5，d1为15，d2为2。由图可见，本文算法能清晰显示窗户的单元格构造，且组成建筑物的线段大部分都是相互平行或垂直的，没有过多“非期望假设”。lmatch算法虽然也可以看到建筑物的整体结构，但是由于线段匹配的精确度不高，导致“非期望假设”丛生，在一定程度上掩盖了重建结果的主体结构。

图5 化工楼图像集结果

第二组实验重建具有多外立面的建筑物。使用清华大学理科楼图像集，共49幅大小为1 09 2×728的图像。该楼是一个类U型的建筑物，共有三面，如图6所示。图6a为其中一幅图像，图6b和图6c分别为lmatch算法和本文算法的重建结果，实验中为2.5，d1为22，d2为3。由图可见，本文算法可较好地体现建筑的整体框架，而lmatch算法只重建了建筑物中的两个外立面，建筑物的整体结构都没有得到有效重建。由于图像集中有关左侧建筑部分的图像较多，因此在两种算法中该部分墙面的重建精度都会高一些。

2.2 参数分析

参数影响重建结果的线段数目。参数选择严格时，在剔除“非期望假设”的同时也会损失一部分组成建筑物结构的线段，最终重建结果中的线段数目也会较少。反之，如果约束过于宽松，较完整的三维模型结构也会淹没在杂乱无章的“非期望假设”中。

参数d0和d2是两个较为重要的参数，d0的确定主要依据组成建筑物的线段长短，若建筑物主要由较连贯的、长度较大的线段组成，d0的取值可以稍大；反之，d0的取值稍小为宜。一般情况下d0的取值为2~5之间。如图7所示，以Wadham大学基准图像集为例，显示了d0取值的变化对重建结果的影响，其中n为各重建结果中的线段数目，实验中保持d1=17.5，d2=4不变。该图像集的原始重建结果经过d1和d2的约束得到305条线段，d0的约束会进一步减少这些线段，而随着d0取值的增大，图中水平和竖直线条渐渐增多，房屋的框架、窗体等结构也慢慢清晰。

图6 理科楼图像集结果

图7 d0变化对重建结果的影响

d2的确定依据建筑物的主要结构，若建筑物的构造比较规整，主要由相互垂直的线段组成，d2可设置小一些，以便滤除更多的“非期望假设”；若建筑物中还有较多的曲线、斜线等方向的线条，稍大些的d2可保留更多的建筑物细节线条。d2的取值范围一般是2~4之间的整数。如图8所示，以Wadham大学基准图像集为例，显示了d2取值的变化对重建结果的影响，其中n为各重建结果中的线段数目，实验中保持d0=5，d1=17.5不变。由实验结果可以看出，随着d2取值的增大，角度约束放松，图中斜线增多，右侧墙壁窗子上方的装饰、房顶烟囱的尖顶等都渐渐显现。

图8 d2取值变化对重建结果的影响

若三维重建的效果已经较为满意，则对d1稍加约束即可。该参数对线段数量和建筑物结构的影响没有前两个参数明显。

3 结 论

针对建筑物三维线段模型重建问题，本文结合准确度更高的双视图线段匹配算法，在没有几何先验的条件下，对任意幅输入图像进行更精确的线段匹配，三维线段的重建过程也不再因为匹配线段之间的位置干扰而受到影响。实验结果表明，本文算法对于具有单一平面状外立面及具有多外立面的建筑物，都有良好的重建结果。

[1]CHEN Tingwang, WANG Qing. 3D line segment detection for unorganized point clouds from multi-view stereo[C]//Proceedings of the 10th Asian Conference on Computer Vision. Berlin, Germany：Springer-Verlag, 2011:400-411.

[2]彭亚丽, 刘芳, 刘侍刚.一维子空间的三维重建方法[J].西安交通大学学报, 2009, 43(12):31-34.PENG Yali, LIU Fang, LIU Shigang. 3D reconstruction method with 1D subspace [J]. Journal of Xi’an Jiaotong University, 2009, 43(12):31-34.

[3]PARK J S. Interactive 3D reconstruction from multiple images:a primitive-based approach[J]. Pattern Recognition Letters, 2005, 26(16):2558-2571.

[4]VON GIOI RG, JAKUBOWICZ J, MOREL J M, et al. LSD:a fast line segment detector with a false detection control[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32 (4):722-732.

[5]SCHMID C, ZISSEMAN A. Automatic line matching across views[C]//Proceedings of the 1977 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA:IEEE Computer Society, 1997:666-671.

[6]SCHMID C, ZISSEMAN A. The geometry and matching of lines and curves over multiple views [J]. International Journal of Computer Vision, 2000, 40 (3):199-233.

[7]BAY H, FERRARIS V, VAN GOOL L. Wide-baseline stereo matching with line segments [C]// Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway，NJ，USA：IEEE, 2005:329-336.

[8]WANG Zhiheng, WU Fuchao, HU Zhanyi. MSLD:A robust descriptor for line matching[J]. Pattern Recognition,2009, 42 (5):941-953.

[9]FAN Bin, WU Fuchao, HU Zhanyi. Robust line matching through line-point invariants [J]. Pattern Recognition, 2012,45 (2):794-805.

[10]BAILLARD C, SCHMID C, ZISSEMAN A, et al.Automatic line matching and 3D reconstruction of buildings from multiple views [C]// Proceedings of the ISPRS Conference on Automatic Extraction of GIS Objects from Digital Imagery. Amsterdam, Netherlands,Holland:Elsevier Science,1999:69-80.

[11]WERNER T. LMATCH:matlab toolbox for matching line segments accross multiple calibrated images [EB/OL].(2007-06-01)[2013-06-12].http://cmp.felk.cvut.cz/~werner/software/lmatch/.

[12]HARTLEY R, ZISSEMAN A. Multiple view geometry in computer vision[M]. Cambridge, UK:Cambridge University Press, 2000.

[13]WERNER T, ZISSERMAN A. New techniques for automated architectural reconstruction from photographs[C]// Proceedings of the 7th European Conference on Computer Vision. Berlin, Germany:Springer-Verlag, 2002:541-555.

[14]VERETNIK S. Benchmark data set of Wadham College[DB/OL].(2006-01-01)[2013-6-23].http://www.robots.ox.ac.uk/~vgg/data/datamview.html.

[15]NORONHA S, NEVATIA R. Detection and modeling of buildings from multiple aerial images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2001, 23 (5):501-518.