基于约束Delaunay三角形的多视3D重建

冯文雯 陈珝玥 余虹亮 欧元汉

1(广西大学计算机与电子信息学院 广西 南宁 530004)2(南宁有无科技有限公司 广西 南宁 530007)



基于约束Delaunay三角形的多视3D重建

冯文雯1陈珝玥2余虹亮1欧元汉1

1(广西大学计算机与电子信息学院 广西 南宁 530004)2(南宁有无科技有限公司 广西 南宁 530007)

为解决多视立体重建的表面模型扭曲变形，建筑物平面凹凸不平进而造成纹理贴图出现错误和拉花的问题，提出一种加入直线约束的城市建筑三维重建方法。该方法使用无人机获得的一系列图片作为输入，首先通过直线检测器和超级像素提取图像直线段和边缘，经边缘多边形简化，再通过2D约束德劳内三角化得到单视图2D三角格网。然后根据密集点云回算2D三角格网顶点三维位置，得到单视图3D格网模型，最后多视图合并得到场景完整3D模型。实验结果表明，算法表现出较好的性能、稳定性和可扩展性，并且具有较高精确性和有效性。

约束Delaunay三角形 LSD 超级像素 多边形精简 多视立体重建

0 引 言

大规模城市场景3D重建在计算机视觉和图形学领域一直以来都有着迫切的需求并应用于城市规划、导航、文化遗产等领域。谷歌、微软和苹果的地图产品已相继开始提供部分城市级别的3D模型数据，这都得益于多视立体三维重建MVS(Multiple View Stereo) 技术的迅速发展。MVS重建流程通常由运动获取结构SFM(Structure From Motion)计算相机位置参数、密集点云生成和表面模型重建3个步骤组成，其重建精度接近激光雷达[1]，但模型的视觉效果还存在许多改善的空间[2]。当应用于真实城市场景建模时由于大量平面缺乏纹理使得MVS点云重建的误差增大，进而导致表面模型扭曲变形，造成纹理贴图出现错误和拉花现象。

观察到城市场景中存在大量直线段，直线的断续和扭曲是重建模型视觉效果变差的主要原因，若能在3D重建过程中加入直线段约束将会显著改善上述问题。城市场景三维线段重建已有一些工作[3-5]，但其所得三维直线只是作为中间数据，而非完整的三维表面重建结果，也无纹理贴图。

本文以大范围城市场景三维建模为应用背景，针对MVS模型扭曲变形的问题以重现城市建筑模型线条美为目标，基于图像的直线段建立2D约束德劳内三角格网2D CDT(2D Constraint Delaunay Triangle)[6]，结合三维点云构造单幅视图的3D CDT，再使用图割优化方法选取表面模型对应的最佳视图，最终合并生成完整三维格网模型。

1 相关工作

MVS三维重建的研究多是针对单个物件，近十年出现了不少出色的成果[1]，但仍然面临许多挑战，视觉效果不佳是其中迫切需要解决的难题。目前标准的MVS流程是以文献[7]为代表的PMVS+PSR方案，即通过多视密集匹配生成三维点云，再基于点云使用泊松重构求解表面模型。该类方法得到的模型精度处于领先地位，但模型视觉效果并不理想，无法适用于城市建筑的重建。为得到更好的城市三维效果，对模型进行曼哈顿约束[8]能够得到建筑模型横平竖直的重建效果，但欠缺通用性。对模型进行平面提取等后处理[9]考虑了建筑物多平面的特征，但对于城市植被的重建效果欠佳。

PMVS+PSR流程的关键是精确、完整的密集点云生成，与此不同的另一类方法是快速生成不精确但足够完整的点云。先构造初始化粗糙Mesh，再根据多视重投影误差最小化进一步精细化初始模型[10]。这类方法是目前精度和视觉效果兼顾最好的，法国Acute3D公司的Smart3DCpature(后简称S3D)是领先的MVS建模软件，其核心算法也属于此类，但计算量大，且由于SFM过程的相机参数回算不够准确，Mesh精细化过程会对三角面片进行误差分配，造成模型的扭曲和起伏。沿用Mesh精细化的思路，Takayuki Sugiura等[11]加入3D直线改善模型效果，缺点是重建3D线段增加了复杂性和局限性。

本文方法是提取图像的超级像素并获取场景细分平面利用超级像素边缘作为三角面片的边，同时加入直线约束，能够应对人工建筑或自然景观等多种场景。方法受到文献[2,12]的启发，与前者相比，并非将每个超级像素直接去回算3D空间的一个平面，而是将超级像素边缘作为三角面片的边，不再需要对平面做进一步的表面模型求解；与后者相比，引用了直线约束而非单纯使用超级像素，这样的改变对城市建筑重建效果的改善起着关键作用，如图1所示。

图1 提出方法的概述

本文方法有3个特点。首先，单视图足够表示其主要可视场景，并能够使模型在对应视角观察的视觉最大化接近照片效果。虽然通过多视图优化能小幅提高重建精度，却因为需在各视图中平均分配误差，造成直线的变形。其次，单视图重建再合并的技术路线本质上是一种低耦合的轻量并行思想，非常适合大范围城市三维重建。最后，表面模型的三角面片直接来源于图像的2D CDT，图像中的直线段构成三角面片的边不会造成断续、扭曲，能够改善重建模型的视觉效果。

2 基于CDT的三维格网重建

本文方法包含3个步骤:(1) 基于图像线段的二维约束德劳内三角化；(2) 单视图三维Mesh重建；(3) 多视图Mesh合并。

2.1 2D约束德劳内三角化

本文方法的关键在于将图像中的直线约束加入到表面模型的三角格网中，并尽可能让三角格网的边与图像中的边缘对应起来以改善MVS表面模型中的扭曲变形。因此，采用的约束德劳内三角化方法是基于图像直线段和边缘构造2D三角格网。对于线段和点的输入集合，约束德劳内三角化以输入线段作为三角格网的边，输入点作为三角格网顶点，构造德劳内三角格网，称为约束德劳内三角格网，即CDT。

2.1.1 直线提取

直线提取可以采用经典的Hough变换方法，考虑到大场景二维线段提取，本文采用LSD(line segment detector)[13]方法对图像进行直线检测。LSD是一种高效、无参数的直线检测方法，能对具有同一梯度方向的像素几何应用最小二乘法估计线段的方向和端点能够对高分辨率图像提取直线段，适合针对大场景的线段提取。如图2(a)所示。

图2 线段LSD及超级像素

2.1.2 超级像素

图像中的边缘位置通常对应场景深度的断续，因此将Mesh的边落在图像的边缘能够改善3D模型的准确度和视觉效果。边缘提取有许多经典算法，如sobel、canny等，考虑到大范围城市场景的数据源多为超高分辨率的航拍照片，边缘提取效率是需要首先考虑的因素，因此本文采用GPU超级像素GSLIC[14]方法，获取图像边缘点，如图2(b)所示。

2.1.3 边缘多边形简化

超级像素能够快速提取图像中的边缘点，Mesh的边是线段，两者要对应起来，需要对超级像素边界进行多边形简化。Douglas-Peucker[15]算法通过计算顶点到边的距离，以确定哪些点能够简化为一条边，得到简化多边形，图3是使用5个像素容忍度的超级像素边缘多边形简化结果。

图3 超级像素边缘简化

2.1.4 2D CDT

直线段和超级像素边缘往往会有重合需要进行去冗余处理并保证直线约束的优先级，即删除距离直线段太近的多边形顶点。此处以直线为中轴外扩4个像素的矩形范围内的顶点做删除得到直线段和最终参与构造CDT的顶点，如图4(a)所示。

约束德劳内三角化是对包含n个顶点和非交叉边按以下约束进行三角化：(1) 预先指定的边包含在三角划分中，(2) 尽可能接近德劳内三角剖分，即CDT是加了约束条件(预先指定的点和线)的德劳内三角形。上述过程中提取的线段和去冗余后多边形的顶点作为输入得到2D CDT如图4(b)所示。

图4 通过所得直线段及顶点构造2D CDT

2.2 单视图三维Mesh重建

(1)

(2)

这是一个稀疏线性V×V系统(V是顶点数目)，通过常规线性系统求解方法即可高效得解，所得3D Mesh如图5所示。

图5 3D Mesh及其贴图

2.3 多视图Mesh合并

对每个视图重构得到的3D Mesh进行合并得到完整的三维表面模型。基于图像加入直线约束并拟合GCP得到的3D Mesh很好地表现了建筑物的直线条，并抑制了常用泊松表面重构算法对模型的平滑。此处直接将所有单视图3D Mesh的顶点合并如图6所示，采用文献[16]的方法，先对三维顶点集合构造德劳内四面体，再使用图割优化[17]标记出内外两类四面体，内、外四面体交界处，即为最终的表面模型。

图6 单视图顶点及多视图合并顶点

3 实验与结果分析

本文使用C++编程实现基于约束德劳内三角形的多视三维重建方法，涉及的开源库包括OpenCV、CGAL、boost和Eigen。其中，OpenCV用于图像读取基本操作、直线提取，使用boost进行多边形精简，CGAL构造2D CDT及相关mesh操作，Eigen求解线性系统。硬件环境为Intel(R) Xeon(R)CPU E5-16200 V3 @3.50 GHz，16 GB内存的台式机上，编程环境是Visual Studio 2013。

本文方法针对城市规模场景，实验数据集选用无人机获取的55张2 400万像素航拍照片。SFM相机自检校过程使用VisualSFM[18]，PMVS[19]密集点云生成，然后使用本文方法得到三维表面模型，结果如图7所示，单视图重建主要步骤(单张平均)耗时见表1所示。

图7 本文方法得到3D模型过程

输入数据GSLICLSD2DCDT3DCDT耗时/s5.22.31.76.1

图8是本文方法与常用重建方法PMVS+PSR的结果对比，可以看出后者对城市建筑产生了过平滑，细节缺失，而本文方法则有了较好的改善。

图8 本文方法与PMVS+PSR对比

S3D是当前公认效果最好的商业软件，此处以同样的数据集，使用S3D最高精度选项进行对比实验，如图9所示。实验结果表明本文方法与S3D的结果已经相当接近，而对于纹理贴图模型可以看到本文结果的扭曲、拉花缺陷略少。

图9 S3D方法与本文方法对比

我们使用30张像素为2 400万的照片作为输入获得密集点云，对软件S3D进行最高精度设置建立基准模型。通过本文方法和泊松重构获得的模型分别与基准模型进行精度测量。如图10中(a)、(b)分别为本文建模和泊松重构精度测量结果，(c)表示颜色误差分布，颜色越深误差越大，明显看出本文建模算法效果高于传统泊松重构效果；(d)是本文方法和泊松重构误差分布情况，横坐标是误差，纵坐标是误差点数占总点数的百分比。本文方法全部点最大误差在0.1 m左右范围内这体现了本方法的完整性和精确性，而泊松重构70%以上的点误差大于1.5 m。事实证明本文重建模型比传统泊松重构建模效果更好。

图10 本文方法和泊松重构效果对比

此外，针对城市建筑，还使用本文方法进行了多个数据集的实验，照片像素均为2 400万，如图11所示。

图11 两个数据集重建结果图

4 结 语

本文针对城市建筑物3D模型重建提出与传统三维建模(输入航拍图片-SFM相机姿态估计-密集点云重建-表面重建得到表面网格模型-贴图)不同思路的三维建模方式，其基于约束Delaunay三角形的多视图3D重建算法。该算法经2D约束Delaunay三角化获得单视图2D CDT，降低了复杂度且提高了模型重建精度，通过密集点云回算2D CDT顶点三维信息得到单视图3D格网，最后通过多视图合并构建城市建筑3D模型。实验结果表明，本文重建模型有较好的适用性和可扩展性，与传统方法相比改善了视觉效果。在后续工作中，我们将对建筑物2D和3D Mesh进一步优化调整，期待得到速度更快、视觉效果更好的格网模型。

[1] Seitz S M,Curless B,Diebel J,et al.A comparison and evaluation of multi-view stereo reconstruction algorithms[C]//Computer vision and pattern recognition,2006 IEEE Computer Society Conference on.IEEE,2006,1:519-528.

[3] 欧元汉,黄鸿,陆宇海.基于密集点云重投影的三维线段模型重建算法[J].计算机工程与设计,2015(12):3291-3296.

[4] 罗宇,宋歌,杨红雨.基于图像识别的建筑物三维重建[J].计算机工程与设计,2015,36(1):191-196.

[5] Hofer M,Wendel A,Bischof H.Line-based 3D reconstruction of wiry objects[C]//Computer Vision Winter Workshop (CVWW),2013.

[6] Qi M,Cao T T,Tan T S.Computing 2D constrained Delaunay triangulation using the GPU[J].Visualization and Computer Graphics,IEEE Transactions on,2013,19(5):736-748.

[7] Furukawa Y,Ponce J.Accurate,dense,and robust multiview stereopsis[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2010,32(8):1362-1376.

[8] Furukawa Y,Curless B,Seitz S M,et al.Reconstructing building interiors from images[C]//Computer Vision,2009 IEEE 12th International Conference on.IEEE,2009:80-87.

[9] Gallup D,Frahm J M,Mordohai P,et al.Real-time plane-sweeping stereo with multiple sweeping directions[C]//Computer Vision and Pattern Recognition,2007.CVPR’07.IEEE Conference on.IEEE,2007:1-8.

[10] Vu H H,Labatut P,Pons J P,et al.High accuracy and visibility-consistent dense multiview stereo[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2012,34(5):889-901.

[11] Sugiura T,Torii A,Okutomi M.3D surface reconstruction from point-and-line cloud[C]//3D Vision (3DV),2015 International Conference on.IEEE,2015:264-272.

[12] Bódis-Szomorú A,Riemenschneider H,Van Gool L.Superpixel meshes for fast edge-preserving surface reconstruction[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,2015:2011-2020.

[13] Gioi R G V,Jakubowicz J,Morel J M,et al.LSD:A line segment detector[J].Image Processing on Line,2012,2(4):35-55.

[14] Ren C Y,Reid I.gSLIC:a real-time implementation of SLIC superpixel segmentation[R].University of Oxford,Department of Engineering,Technical Report,2011.

[15] Park J H,Jang B J,Kwon O J,et al.Vector Map Data compression based on Douglas Peucker Simplification Algorithm and Bin Classification[J].Journal of Korea Multimedia Society,2015,18(3):298-311.

[16] Jancosek M,Pajdla T.Exploiting visibility information in surface reconstruction to preserve weakly supported surfaces[J].International Scholarly Research Notices,2014,2014:1-20.

[17] Sinha S N,Mordohai P,Pollefeys M.Multi-view stereo via graph cuts on the dual of an adaptive tetrahedral mesh[C]//Computer Vision,2007.ICCV 2007.IEEE 11th International Conference on.IEEE,2007:1-8.

[18] Wu C.VisualSFM:A visual structure from motion system[Z].2011.

[19] Li Z,Wang K,Zuo W,et al.Detail-preserving and Content-aware Variational Multi-view Stereo Reconstruction[J].Image Processing,IEEE Transactions on,2016,25(2):864-877.

MULTI-VIEW 3D RECONSTRUCTION BASED ON CONSTRAINT DELAUNAY TRIANGLE

Feng Wenwen1Chen Xuyue2Yu Hongliang1Ou Yuanhan1

1(CollegeofComputerScienceandElectronicInformation,GuangxiUniversity,Nanning530004,Guangxi,China)2(YouWuCo.,Ltd,Nanning530007,Guangxi,China)

In order to solve the problem that the surface model of multi-view-stereo reconstruction is distorted and the plane of the building is uneven, which causes the error of texture mapping and garland, a method of 3D reconstruction of urban buildings with linear constraint is proposed. The method uses a series of pictures obtained by the UAV as input. Firstly, straight line segment and edge are extracted by line segment detector and super-pixel. After the polygon simplified, 2D single triangle 2D mesh is obtained by 2D constrained Delaunay triangulation. Then, according to the dense point cloud, the 3D position of 2D triangular mesh vertex is back-calculated, and the single view 3D mesh model is obtained. Finally, the multi-view merges to obtain the complete scene 3D model. The experimental results show that the proposed algorithm has good performance, stability and expansibility, and has high accuracy and efficiency.

Constraint Delaunay triangle LSD Super-pixel Polygon simplification Multi-view stereo reconstruction

2016-07-13。冯文雯，硕士，主研领域：计算机视觉。陈珝玥，硕士。余虹亮，硕士。欧元汉，副教授。

TP391

A

10.3969/j.issn.1000-386x.2017.07.023