基于建筑结构分布规律的点云孔洞修补*

罗德安 张腾波 廖丽琼

(北京建筑大学测绘工程系，北京 100044)

1 引言

因数据缺失而产生的孔洞在地面激光雷达(TLS，Terrestrial Laser Scanner)扫描点云中是广泛存在的，导致数据缺失的因素较多，主要有扫描环境中非关注目标的遮挡、扫描设备视线高度限制、扫描对象的反射特性影响、特征边沿效应及扫描对象的自身闭塞环境影响等。这些孔洞对后续的点云数据处理、分析及模型重建将产生消极作用，影响建模的精度及质量，所以，在进一步进行点云数据处理之前，需要对这些孔洞进行必要的修复与补全。目前大多数点云孔洞及缝隙的修补算法［1－7］，能够解决局部小范围缺失信息的修补问题，对于缺失范围较大的情形，由于不满足数据平滑及外推的前提条件，所以相应的修复算法都无法使用。少数能够对大范围缺失数据进行修复的方法也需要借助额外的影像数据来实现［8］，并且具有过程复杂，效率较低等不利因素。因此，发展能够对大范围缺失数据进行高效修复的方法便成为点云数据处理中亟待解决的关键性技术难题之一。

从现有文献来看，针对较大范围或是具有高曲率变化的孔洞修复算法还相对较少。李海亮等［8］提出的基于摄影测量的方式修复大范围数据缺失的方法较为有效，但该方法过程复杂，效率相对较低;Sharf 等［9］提出了一种由粗到精的点云样本表面孔洞填充的方式，获得了可接受的结果，但也存在一些问题，在三维环境中对齐两个面片集具有大量的自由度，建立数据处理的参照坐标系存在困难，重建曲面上的孔洞边界也存在错误定义的可能;Park 等［10］扩展了上述工作，引入了关联的颜色信息，在最后一步，通过采用柔性变换，一个高程域和Poission 等式用来解决拷贝曲面块与孔洞的平滑接合问题。Becker 等［11］提出了直接拷贝3D 曲面块修补3D 孔洞的方法，但该算法修复的点云无法保证产生出符合原始扫描仪透视关系的、合理的深度图像。

本文也采用了一种类似从场景的其他区域拷贝结构到孔洞区域的修补方式，不同的是，为了避免三维空间搜索巨大的时间及空间代价，针对建筑立面涉及的孔洞修复，我们将建筑部件分布规律(如对称性及重复性)等先验知识引入到算法中，同时在交互环境下作适当的人工诱导，使得算法的实用性及效率得到了显著的提高。

2 缺失点云修复方法

2.1 基本思想

算法首先需要获得建筑立面的主平面，后续的多项操作将以此为参照。接下来对建筑立面上孔洞类型按照修补方式分为部件相关类孔洞及部件无关类孔洞。对于涉及具体部件的孔洞，找到其相同的部件及其邻域，将其副本拷贝到孔洞区域，通过ICP实现与该孔洞局部环境的配准，再作点云局部融合即可实现孔洞修复;而对于非部件类孔洞，多数出现在主体墙面上或其边沿，对于前者，直接通过主体墙面(一般为平面)模型离散化即可实现修补，对于后者可以相邻的墙面按实际需要进行延展来实现，相交部分为墙面边沿特征线，再对延展出来的局部平面实施离散化操作即可实现孔洞修补。

算法的使用存在一定的前提条件:1)约定同类重复性结构体具有相同的几何属性;2)算法不适用于因透射产生的孔洞修复。此外，算法只具备部分自动数据处理能力，算法实现过程中的参照对象选取等操作，需要适当的人工干预与诱导。

2.2 算法流程

1)数据预处理

原始点云需要进行必要的预处理后才能进行后续的数据处理与分析，主要包括剔出粗差及不相关的点云数据，数据配准与融合，以及适当的数据简化处理;

2)主体墙面的提取

每一个建筑立面总是包含多个主体墙面，而窗体、阳台以及其他建筑部件往往附着在这些主体墙面上，为了点云修补及后续重建建筑立面模型，首先需要将其主体墙面提取出来。目前，从点云中识别及重建平面特征的算法已极为成熟。这里我们采用区域生长算法重建建筑立面的主平面，因为该算法复杂度较低并具有较高的执行效率;

3)建筑立面孔洞分类

按照修补方式将孔洞分为部件相关类孔洞及部件无关类孔洞，如图1(a)所示。图中由于树的遮挡造成建筑立面部分区域存在点云缺失，包括主体墙面及窗体上。对于主体墙面孔洞区域，修补相对容易，如涉及建筑部件(如窗、阳台等)，由于部件自身的复杂性，其修补将变得相对困难。

4)孔洞分类修补

对于部件无关的孔洞修复(如图1(b)红色框外部分)，首先需要拟合出主体墙面的平面模型，而后根据孔洞附近的点云分布情况对孔洞区域平面模型进行离散化处理，保持离散化后获得点云分布规律(如排列方向、点云密度等)和邻近区域一致即可。图1(c)即为修复后的情况;

图1 孔洞修复Fig.1 Repairing holes and gaps

对于部件相关的孔洞如图1(c)红色框内部分，由于涉及很多部件细节部分，孔洞并不在同一平面上，上述的模型离散化方法显然是无效的。这里将以建筑部件(如窗)作为一个独立修复单元，首先找到和该部件相同的其他具有完整扫描点云信息的部件，获取其完整副本，而后通过ICP 算法将其与待修复窗体进行配准，配准完成后，需要移去原有的相关点云数据，并用先前获得的具有完整点云数据的拷贝副本替换它，进行必要的边界数据融合，从而实现有孔洞部件对象的完整修复(图1(d))。

5)大范围数据缺失的修补

对于存在规律性的大范围数据缺失，可以借助部件分布的规律性(如重复性、对称性)来实现相应的孔洞修复。如图2(a)所示，由于地面物体近距离遮挡，即使多次设站，仍旧无法获取左下角的点云数据，造成相应的数据缺失。该缺失数据涉及到一楼的一个完整小窗体和一个大窗体的部分信息，以及主体墙面的部分信息。主体墙面的数据缺失及大窗体部分数据缺失仍旧可以采用步骤4)中的相关算法进行修复，而对于整体缺失的小窗体，上述算法显然无法实现。要实现该类缺失信息的修复，首先须获取其同类部件的分布规律(包括布局形态、窗体分隔间距等)，接下来选择一个完整的同类窗体的拷贝副本作为参考，根据先前获得分布规律参数(如分布间距)，通过三维仿射变换将完整同类部件的拷贝映射到正确位置，从而实现缺失部件的修复。在该过程中需要适当的人工干预及诱导，尤其是在分布规律的获取过程中，适度人工干预及诱导显著提高了算法效率。

图2 利用重复性规律实现大范围缺失修复Fig.2 Repairing large holes by repeated structure pattern

3 算法实现与实验

为验证上述算法，利用C + +开发了一个基于可视化工具库VTK(Visualization Toolkit)的简单应用，点云相关的各种函数及操作(如法矢计算、曲率计算、三维仿射变换、ICP 操作等)以及本文算法相关的操作与函数都予以实现，这些函数大多能够独立运行，也可以组合运行，使得程序应用极为灵活。

为了验证算法的有效性及可操作性，选定某居民楼的一个建筑立面作为样本(图3)，该点云数据包含2 站测量数据，由点云图可以发现建筑立面包含具有规律性分布的窗体和阳台。原始点云含有大量无关数据和粗差(如激光穿越玻璃窗体打在室内的物体将产生了大量的粗差)，在进行后续数据处理前，需要将粗差从原始扫描数据中剔除，以达到提高数据处理效率的目的。

利用我们提出的算法，分别进行主体墙面修复及部件修复，在算法实现过程中需要适当的人工干预及诱导，以便快速实现部件分布规律的获取、关键性参数的设置及参照对象的选取等，在这些先验信息的辅助下，通过编制的算法软件即可在交互环境下快速实现点云缺失数据的修复。图4(a)的图是建筑立面的局部，已经去掉了主要的无关数据与粗差，缺失数据主要包括左下角的小窗体及树木对主体墙面及窗体的影响，图4(b)为修复后的点云图。

图3 某建筑立面点云图Fig.3 Point cloud of a building facade

图4 缺失数据补全与修复(局部截图)Fig.4 Repairing and completing lost point cloud data of a building facade(Partial)

建筑立面的点云数据包含多个孔洞及缝隙，目前还没一种统一的算法能够完全覆盖不同的孔洞类型并实现全自动孔洞修复。小孔洞及缝隙的修复基本可以借助平滑外推快速完成，具备一定的自动化水平，而对于面积较大的孔洞，现有的平滑外推类算法无法实现修复，目前较为有效的方法是借助近景摄影测量方法来实现。为验证所提方案的效率，将摄影测量修复方法和本文方法做了一个对比试验，运行机器为联想Think Centre M6400t，配置Intel CoreTMi5-3470 CPU，主频3.2G，内存4G，采用64 位windows 操作系统。近景摄影测量的影像匹配和点云获取采用开源软件包Bundler 和Clustering Views for Multi-view Stereo(CMVS)，前者实现光束平差及稀疏点云获取，后者实现稠密点云获取，本文算法的实现采用了自行开发的软件包，实验结果表1 所示。

由表1 可以看出，本文算法的总体耗时仅为摄影测量修补方法的1/16 ～1/18，这还不包括获取影像所需的时间支出，近景摄影测量最大的时间成本在于基于影像的点云获取，特别是其中的稠密点云获取尤其耗时，本文算法最耗时之处在于获取待修复部件的位置，两种方法的其余耗时(如点云配准与边界融合等)并无显著性差异。应当指出的是，基于影像的点云获取所消耗时间还和获取点云范围的大小以及图像像素密度有关联，范围越大或像素密度越大都会增加其时间支出。

表1 孔洞修复方法比较Tab.1 Comparison of two algorithms repairing hole

4 结论及讨论

针对大范围缺失数据的修复及补全，本文提出的方法能够充分利用已有的先验知识及在交互环境下的适度人工诱导，准确快速地实现大范围缺失数据的修复。实际使用证明，尽管算法不具备全自动化数据处理能力，但却具有较高的可操作性及生产效率，能够有效解决因遮挡及自闭塞而产生的大范围点云数据缺失的修复问题，为快速重建城市虚拟场景中的建筑模型提供了有力支持。

对于因透射(如玻璃窗)、全反射等原因产生的点云缺失，现存的算法都无法直接修复其产生的数据缺失。作为解决窗体透射产生数据缺失的方案之一，可在模型重建阶段，通过人工交互先重建出一个完整窗体模型，而后再依据窗体的对称性及重复性分布规律，借助窗体框架等特征，通过模型配准来实现同类型窗体的快速重建［12］。

1 Tao J.Fixing geometric errors on polygonal models［J］.Journal of Computer Science Technology ，2009，24(1):19－29.

2 Nooruddin F S and Turk G.Simplification and repair of polygonal models using volumetric techniques［J］.IEEE Transactions on Visualization and Computer Graphics，2003，9(2):191－205.

3 Bischoff S，Pavi D and Kobbelt L.Automatic restoration of polygon models［J］.ACM Transactions on Graphics，2005，24(4):1 332－1 352.

4 谢倩茹，耿国华.三维模型孔洞修补方法的研究［J］.计算机应用研究，2013，30(10):3 175－3 177.(Xie Qianru and Geng Guohua.Study on the method of repairing hole with a 3D model［J］.Reserch of Computer Application，2013，30(10):3 175－3 177)

5 Leong K F，Chua C K and Ng Y M.A study of stereo lithography file error s and repair.Part 2:Special cases［J］.International Journal of Advanced Manufacturing Technology，1996，(12):415－422.

6 Pfeifle R and Seide1 H P.Trriangular B-splines for blending and filling of polygonal holes［A］.Proceedings of Graphics Interface［C］.Toronto:Canadian Information Processing Society Press，1996:186－193.

7 张丽艳，周儒荣，周来水.三角网格模型孔洞修补算法研究［J］.应用科学学报，2002，20(3):221－224.(Zhang Yanli，Zhou Rurong and Zhou Laishui.Study on algorithm repairing holes with a triangle network model［J］.Journal of Applied Science，2002，20(3):221－224)

8 李海亮，邓非，李刚.摄影测量激光点云孔洞修补［J］.测绘科学，2010，30(5):101－102.(Li Hailiang，Deng Fei and Li Gang.Repairing holes of laser point cloud with photomeasurement［J］.Suevey Science，2010，30(5):101－102)

9 Sharf A，Alexa M and Cohen-Or D，Context-based surface completion［EB/OL］.http://www.cs.bgu.ac.il/ ～asharf/Projects/SCOM/SurfaceCompletion.pdf.

10 Park S，et al.Shape and appearance repair for incomplete point surfaces［EB/OL］.http://cvc.cs.stonybrook.edu/Publications/2005/PGSQ05/85seyoun_xguo_iccv05-final.pdf.

11 Becker J，Stewart C and Radke R J.LiDAR inpainting from a single image［EB/OL］.http://www.ecse.rpi.edu/ ～rjradke/papers/becker3dim09.pdf.

12 Dean Luo and Liqiong Liao.Rapid reconstruct 3d building models from point cloud［J］.Applied Mechanics and Materials，2013，303:2 317－2 320.