基于多视几何的重叠点云删除算法

郭 进，袁建英，陈小宁

（1.西南财经大学 天府学院，四川 绵阳621000；2.西南交通大学 机械学院，四川 成都610000；3.昆明学院 自动控制与机械工程学院，云南 昆明650214）

0 引 言

多频相移的结构光三维测量系统需要进行多次拼接测量，才能得到大范围物体的全局点云，当把多次视图下测量获得的多片点云拼接成一个完整点云时［1］，拼接后两次点云的重叠区域会产生大量的冗余点。冗余点云的数据量也会随拼接次数的增多越来越大，进而影响后期三维点云数据的处理，降低三维建模的速度和精度。

重叠区域的冗余点删除一般都是三维点云的后处理，梁新合等人采用法向约束的点云融合方法，但该方法对种子点依赖大［2］，曹巨明等采用移动最小二乘进行多视点云数据融合，不过他们的算法时间代价依旧不小［3］；杜晓晖采用混合模式精简点云［4］；杨斌采用多分辨率简化算法［5］，算法的计算量都十分大；Nira Dyn等［6］构造了一个非负函数用于度量数，根据点的重要性，然后采用基于迭代的方法对点云进行简化，但速度不快。根据点的重要性，采用基于迭代的方法对点云进行简化，黄文明等人采用计算样点对最小二乘移动曲面的影响大小，简化点云，但涉及非线性优化计算过程复杂［7］。以上方法都是从三维点云的角度出发，采用八叉树等数据结构［8］，通过计算点云的曲率，密度等信息来删除多余的点云，这些方法的计算量大，效率低，无法保证原始扫描数据等信息。

本文避开传统的点云后处理方法，利用测量对象物点的唯一性原理，以及三维点云与多视图中二维图像之间的对应关系，在拼接测量中自动计算出每一次拼接与前面多次测量中的重叠区域，对于重叠区域内的二维点就不在进行匹配重构计算，从根源上避免了重叠区域内冗余点数据的产生。

1 冗余点删除算法

基于双目视觉的结构光三维测量系统，测量前先用张正友平板标定对成交姿状态的相机进行标定，得到相机的内外参数，世界坐标系建立在左摄像机上，与左相机的坐标系重合［9］。每次扫描中左右摄像机内部参数一致，外部参数所在坐标系都不统一。可根据在物体上粘贴标记或者无标记拼接的方式计算两次测量之间的变换矩阵，这样可以把多次扫描的相机外参数统一到一个坐标系下，利用光束法平差对外参数进行优化，根据多极线约束删除冗余点。

如图1 所示，有统一的世界坐标系OXYZ，P1L 和P1R 为第一次测量左右相机对空间中P 点的像点，P2L 和P2R 为第二次测量左右相机对空间中同一P 点的像点，由空间三角几何关系以及相机标定参数，由第一次的像点P1L（x1L，y1L）和P1L（x1R，y1R）可以求解出P 点的三维坐标（xpypzp），同理由第二次的像点P2L（x2L，y2L）和P2L（x2R，y2R）和可以求解出P点的三维坐标（x′py′pz′p）。两次测量都是同一空间点P，因此计算出的（xpypzp）和（x′py′pz′p）产生了冗余点，相机成像光线具有可逆性，把（x′py′pz′p）点向第一次左相机做反投影，如果反投影点落在成像平面上，并且该点在第一次测量中已经计算过，则该点为冗余点可以删除，对于曲率变化大的区域采用计算比较反投影残差大小进去取舍和保留。

1.1 多视相机外参坐标系统一

由SVD 分解求解出两视之间的变换矩阵M，第一次测量下坐标系为O1X1Y1Z1，左右相机的投影矩阵分别为PM1L和PM1R，第二次测量下坐标系为O2X2Y2Z2，左右相机的投影矩阵分别为PM2L和PM2R，由SVD 奇异值分析［10］可以求得两次测量之间的变换矩阵M

把第二次的投影矩阵变换到O1X1Y1Z1下

则由PM′2L和PM′2R计算出来的点云坐标系统一到了O1X1Y1Z1下。

1.2 重叠区域内三维点计算

基于双目相机的结构光测量中，对空间被测量对象采样越高，获取的三维点就越稠密，可以更好反应物体细节，但是当拼接测量过程中，相机的拍摄角度关系，会出现两次测量过程对同一空间的采样率不同，而出现空间两点甚至多点在某一次图像的反投影上映射到一个点的情况，实际上空间中缺间隔一段距离。因此，在计算图像重叠区域内三维点时，需要保留空间采样率大的图像计算三维点，保证细节不丢失。另外，当空间采样率接近时，重叠区域在不同视图下计算的三维点精度不同，为了提高冗余点删除后点云的精度，需要比较反投影残差从两次扫描中保留精度较高的点，高曲率和高精度点处理算法设计如下。

定义物体表面的单位平面为一个边长为ε的正方形。其中，ε为正向扫描平面时，像平面中心区域对应的三维点点距均值，在本文中ε取0.02mm。定义像平面单位平面为一个边长为e的正方形，其中，e取1，即表示单位像素。令第一次扫描左图像上的像点P11，相应的三维点位P′1，反投影残差为e1，第二次扫描左图像上的像点P21，相应的三维点为P″1，反投影残差为e2，将P″1反投影到第一次扫描左右图像上，反投像点坐标为P′11，若‖P11－P′11‖≤e且‖P′1－P″1‖≥ε，则表示计算出P′1和P″1的像点像素距离不超过e，但是这两个点位于物体上不同单位平面，都要保留。若‖P11－P′11‖≤e且‖P′1－P″1‖＜ε，则表示P′1和P″1属于同一单位平面内相距很近的两点，故只需保留一个。为保留精度较高者，判断e1，e2 大小，若e1＜e2，保留P′1，反之保留P″1。

1.3 多次扫描重叠区冗余点去除算法流程

对较大物体进行全局拼接扫描，随着扫描次数增加，公共区域冗余点云也会增加，重叠区域冗余点去查算法流程如下：

步骤1 第1次测量，不需要进行冗余点删除，计算投影矩阵PM1L和PM1R，得到三维点云，标记第1次参与运算的点Mask［i］［u］［v］表示第i次扫描左图像坐标为（u，v）的点是否参与过三维点计算，第1次测量i＝1。

步骤2 第2次拼接测量开始，匹配标记三维标记点，计算当次变换矩阵M2。

步骤3 由变换矩阵对第2次测量的左右相机投影矩阵进行坐标系统一，得到PM′2L和PM′2R。

步骤4 由投影矩阵PM′2L和PM′2R计算当次三维点云数据Q2（x，y，z），然后把三维点云数据向第1次左相机进行反投影，采用1.3所述方法进去计算，标记第2 次参与运算的点Mask［i］［u′］［v′］。

步骤5 第i次拼接测量开始重复步骤2～步骤4，第i次向前1，2，3….i－1次进行反投影。

1.4 本文算法具有以下优点

（1）可以自动识别拼接测量中的重叠区域，仅对重叠区域冗余点进行处理而不破坏非重叠区域点的测量精度和采样密度。在重叠部分，定义单位空间，对单位空间内的三维点仅保留一个，即只进行了一次计算。由于在计算三维点时，算法并没有改变相机参数，也没有改变原始的图像匹配关系，因此所计算的三维点值和原始点云中某个点的值一致，即不会破坏原始点云质量。

（2）能提高点云整体精度。在结构光扫描系统中，点云的精度受相机标定精度、图像点匹配精度等影响。双目反投影残差可以定量衡量双相机像平面上像点、光心、物点构成三角形的误差，也就从理论上可以衡量各种误差对重建的综合影响。在本文算法中，用这一指标来去除重合区域内精度较低的点，保留精度较高的点，因此从理论上提高了点云的整体质量。实现了冗余点删除效率的最大化。从图像上将两次扫描点云划分开，在单位平面内选择精度较高者保留。

（3）本文算法核心点有两个，一是找出重叠区域，二是对重叠区域内进行单次物点计算。两个核心点计算过程都需要每次扫描时双相机在全局坐标系下的投影矩阵。而不管哪种拼接方法，要实现坐标系的统一，都需要计算当前视图像在全局坐标系下的投影矩阵，所以本文算法对常见的拼接方式均适用。针对结构光测量的特性，该方法还可以应用于大型物体如汽车等的测量，配合摄影测量系统，把单次点云配准到全局标记点的时候，避免重叠点云的产生，大大减少冗余数据，提高了三维建模效率。

2 实验验证

本文中搭建的三维光学测量系统由一个光栅投射器（三菱公司DX－320型号的投影仪，分辨率1024＊768，亮度2500流明）和两个大恒的工业摄像机及施耐德镜头组成（分辨率1280＊1024，焦距12mm），标定板和计算机以及三脚架组成。

首先对三维测量系统进行标定［11］，得到摄像机的内部参数和外部参数，利用粘贴的圆心标记点，对坛子进行两次拼接测量，测量方式采用多频外差原理［12］，点云相位求解采用负指数序列展开［13，14］，匹配圆心标记点由SVD 法计算得到M 矩阵，利用本文的算法对重叠区域的标记点进行识别删除。如图2（a）为两次测量点云重叠部分放大示意图，从图中可以看出在标记圆的周围深色部分为拼接后点云重叠部分，产生了大量冗余点云。从图2（b）为本文算法处理后删除了重叠区域冗余点的示意图，从图2（b）中可以看出冗余点的删除达到了最大化。上述实验验证了算法对重叠区域冗余点删除的有效性。对比图2点云仍可很好描述物体三维形貌。

图2 多视图几何关系约束

为了更进一步验证本文算法性能，取重叠区域的一块点云，对比传统冗余点云删除算法和本文算法处理后效果。将本文的处理结果与逆向软件Geomagic Studio中的统一采样和曲率采样进行了比较分析，取被测量坛子曲率变化最大的区域进行了三角化比较，由表1可以看出，本文算法相比统一采样和曲率采样［15］达到了冗余点删除了效率最大化。图3（a）为原始点云，原始点云中存在很多冗余点，三角化后冗余三角片也较多如图4（a），图3（b）和图3（c）分别为采用统一采样和曲率采样后点云效果图，冗余点虽然已经减少，但是不能彻底消除，图4（b）和图4（c）分别为三角化结果，经过这两种算法处理后的点云不再光顺，图3（d）是经本文算法处理后的点云，从表1也可知本文冗余点删除效率较高，图4（d）为本文算法后三角化效果，不管是从光顺度，还是点密度以及细节表现能力上都非常接近。图5为被测量物体采用本文算法删除冗余点云后的三角化结果，点云表面光顺。综上，本文所提出的算法能在冗余点删除效率与删除后点云质量之间保持平衡，既有较大的删除效率，又能保持物体原始细节信息。

表1 本文算法与其它算法的对比结果

图3 不同算法曲率较大处点云对比

图4 不同算法曲率较大处三角化对比

图5 删除重叠点云后三角化

3 结束语

传统点云处理算法一般都是在生成点云后期进行，包括点云去噪平滑，删除重叠点云，以及三角化等，需要对点云建立拓扑结构，算法往往消耗的时间也较长。本文提出的重叠点云删除算法是在结构光测量系统得到三维点云之前，利用多视图约束以及物点唯一性的原理，从根源上对重叠点云进行了删除，避免了冗余点的产生，实验证明了该方法在多次拼接测量中，在保证单次测量精度和点云密度的情况下，无论是平面还是曲面都可以有效是去除冗余点，更好保留物体细节。

［1］YANG Yingbao，LIU Xianyong，YANG Junping.Pointclouds registration algorithm based on improve projection ［J］.Application Research of Computers，2011，28 （10）：3954－3956 （in Chinese）. ［杨英保，刘先勇，杨俊平.一种基于改进投影方法的点云拼接算法 ［J］.计算机应用研究，2011，28（10）：3954－3956.］

［2］LIANG Xinhe，LIANG Jin，GUO Cheng，et al.Multi range images integration algorithm based on normal constraint ［J］.Journal of Xi’an Jiao Tong University，2009，43 （5）：71－75（in Chinese）.［梁新合，梁晋，郭成，等.法向约束的多幅点云数据融合算法 ［J］.西安交通大学学报，2009，43 （5）：71－75.］

［3］CAO Juming，WU SHOUR－Slam，LIANG Jin，et al.Moving least squares based incremental multi－view range images integration algorithm ［J］.Journal of Xi’an Jiao Tong University，2009，43 （9）：46－50 （in Chinese）.［曹巨明，吾守尔·斯拉木，梁晋，等.移动最小二乘增量式多视点云数据融合算法［J］.西安交通大学学报，2009，43 （9）：46－50.］

［4］DU Xiaohui，YIN Baocai，KONG Dehui.Mixed simplification algorithm of point clouds［J］.Computer Engineering and Applications，2007，43 （34）：43－45 （in Chinese）.［杜晓晖，尹宝才，孔德慧.一种点云混合简化算法 ［J］.计算机工程与应用，2007，43 （34）：43－45.］

［5］YANG Bin，FAN Yuanyuan，WANG Jidong.Multi－resolution simplification algorithm for point cloud ［J］.Journal of Computer Applications，2011，31 （10）：2717－2720 （in Chinese）.［杨斌，范媛媛，王继东.点云模型的多分辨率简化算法 ［J］.计算机应用，2011，31 （10）：2717－2720.］

［6］Dyn N，Iske A，Wendland H.Meshfree thinning of 3Dpoint clouds ［J］.Foundations of Computational Mathematics，2008，8 （4）：409－425.

［7］HUANG Wenming，PENG Xiwei，WEN Peizhi，et al.Simplification of scattered point cloud with geometric feature reservation ［J］.Computer Engineering and Applications，2009，45（28）：168－170 （in Chinese）.［黄文明，彭希为，温佩芝，等.保留几何特征的散乱点云简化方法 ［J］.计算机工程与应用，2009，45 （28）：168－170.］

［8］WANG Hongtao，ZHANG Liyan，DU Ji，et al.Simplification and error analysis based on implicit surface for measuring point－sets［J］.Journal of Image and Graphics，2007，12（11）：2114－2118 （in Chinese）.［王宏涛，张丽艳，杜佶，等.测量点集的简化及其隐式曲面重建误差分析 ［J］.中国图象图形学报，2007，12 （11）：2114－2118.］

［9］CHEN Xiabo，XI Juntong，YE Jin.Accurate calibration for a camera－projector measurement system based on structured light projection ［J］.Optics and Lasers in Engineering，2009，47（3－4）：310－319.

［10］GUO Jin，LIU Xianyong，CHEN Xiaoning，et al.An unmarked 3Dpoint cloud automatic registration technology ［J］.Computer Applications and Software，2012，29 （4）：144－147 （in Chinese）.［郭进，刘先勇，陈小宁，等.一种无标记点三维点云自动拼接技术 ［J］.计算机应用与软件，2012，29 （4）：144－147.］

［11］ZHANG Z，MA H，ZHANG S，et al.Simple calibration of aphase－based 3Dimaging system based on uneven fringe projection ［J］.Optics Letters，2011，36 （5）：627－629.

［12］LI Lulu，SU Xianyu，DOU Yunfu，et al.Error analysis and algorithm design of temporal phase unwrapping ［J］.Journal of Sichuan University （Natural Science Edition），2012，49（1）：102－108 （in Chinese）. ［李璐璐，苏显渝，窦蕴甫，等.时间相位展开的误差分析与算法设计 ［J］.四川大学学报 （自然科学版），2012，49 （1）：102－108.］

［13］XU Wei，CHEN Xiaobo，XI Juntong.A method of phase error compensation for structural light measurement［J］.Acta Optica Sinica，2011，31 （3）：1－6 （in Chinese）.［许伟，陈晓波，习俊通.结构光测量相位波动误差补偿方法研究 ［J］.光学学报，2011，31 （3）：1－6.］

［14］Feipeng Da，Hao Huang.A fast，accurate phase unwrapping method for wavelet－transform profilometry ［J］.Optics Communications，2012，285 （4）：421－432.

［15］LIN Xiufang.Study on data sampling algorithm of reverse engineering ［J］.Electronic Design Engineering，2012，20（11）：23－26 （in Chinese）. ［林秀芳.逆向工程中的点云采样算法研究 ［J］.电子设计工程，2012，20 （11）：23－26.］