激光三维扫描仪获取的三维数据点数量巨大, 且往往带有噪声和冗余点, 给后续的数据存储和模型重建造成负担。因此必须在保持被测物体几何特征的前提下, 对测量点云进行预处理, 预处理过程通常分为两步, 即先对原始点云数据去噪[1], 然后再简化[2]。点云去噪的目标是去掉离群点、保留主体点云, 而简化的目标则是去除点云主体中的重复点和冗余点。由于两者的去除目标不同, 因而用一种参数选择法很难做到三维点云去噪和简化同时进行。
关于点云的简化算法有很多, 如2002年Hur等[3]提出的Delaunay三角化点云简化，2014年李国俊等[4]基于Delaunay三角化的噪声点云非均匀采样, 以及Lichti等[5]提出的非均匀网格方法点云简化；2011年张有亮等[6]提出了扇形网格法点云简化算法。这种基于网格的点云简化方法, 可以实现较大区域的点云简化, 但在边界区域或突变区域简化效果会受到很大的影响。为减少简化对边界点的影响, 2004年Oshima[7]提出了基于迭代的非边界点简化法, 但由于涉及到迭代, 所以影响了简化的速度。郑德华[8]在2005年提出了通过设定数据重采样间隔对点云进行直接缩减, 该方法可以快速实现点云的简化, 但是均匀简化无法保留突变区域较多的点。黄国珍等[9]将两种非均匀网格方法用于逆向工程点云的简化, 实现了突变区域的保留, 但没有考虑突变区域点云不一致的影响。对此, 2006年Sihvo等[10]对二维(2D)均匀网格法进行了改进, 提出了三维(3D)网格简化方法；2007年Wentzlaff等[11]根据曲率对点云进行了简化；2009年Sareen等[12]提出了仅适用于样条曲面模型重建的点云简化算法。这三种方法对曲面区域有比较好的简化效果, 但需要消耗较多的时间, 在曲面区域比较适用, 不过在同时存在曲面和平面的区域简化精度和速度都会受到影响。2012年杜晓晖[13]通过计算点p与其邻域点主曲率的Hausdorff距离作为衡量参数改进了Kim等[14]提出的曲面离散曲率算法, 这两个离散曲率算法均需要用二次抛物曲面拟合的方法估算所有点的主曲率, 运算量较大。效果较好且运算量适中的是2010年黄文明等[15]的保留边界的点云简化方法, 该算法是在点云简化前利用Pauly等[16]提出的一种可以直接从散乱点云计算曲面弯曲程度的度量指标——曲面变分, 检测出所有的边界点, 简化过程中保留所有边界点, 对非边界点, 则根据曲面变分及邻近点保留情况进行散乱点云的简化。该算法判断某一点是否为边界点, 只是查看该点处的曲面变分是否大于事先设定的阈值。如果阈值较大, 则会将弯曲程度较大的曲面和平面一样进行简化, 造成曲面的信息丢失; 若阈值较小, 又会使弯曲程度较大的曲面得不到简化, 使简化率下降。
关于点云的去噪算法同样很多, 如2011年聂建辉等[17]借助曲面变化度(即文献[15-16]中的曲面变分)的定义提出了基于曲面变化度的局部离群系数(Surface Variation based Local Outlier Factor, SVLOF), 利用SVLOF对散乱点云的近离群点进行识别, 去噪效果良好。本文作者在前期研究[18]中发现, SVLOF在曲面变化度很大的地方, 特别是在三维实体锐利的棱边和棱角处具有反常现象, 因此对SVLOF作了重新定义, 称其为扩展的SVLOF(Extended SVLOF, ESVLOF)。利用ESVLOF作为近离群点的识别参数, 既能识别平滑曲面上的离群点, 又能识别三维实体的棱边或棱角点处的离群点, 同时仍然保留SVLOF原有的足够宽泛的阈值选取空间。SVLOF和ESVLOF在离群点的判断上具有很高的灵敏度, 但该参数的计算耗时较多, 如果对原始点云先作去噪处理再作简化操作, 必将增加预处理时间, 降低三维模型的重建效率。能否通过一次ESVLOF参数的计算, 做到离群点识别和点云简化呢?本文通过对ESVLOF定义的分析, 给出了ESVLOF的性质, 并利用ESVLOF去噪过程中计算的曲面变化度和预设的相似度系数, 构造出了随曲面变化度增大而减小的局部阈值, 在利用ESVLOF进行点云去噪的过程中完成了点云的非均匀简化, 使三维点云的预处理时间约等于点云的去噪时间。
1 ESVLOF性质及简化条件 1.1 ESVLOF定义[18]| $ ESVLOF\left( p \right) = \left\{ \begin{array}{l} \frac{{\sigma _{sk}^\beta \left( p \right)}}{{\sigma _{sk}^\alpha \left( p \right)}}, \;\;\;\;\;\sigma _{sk}^\beta \left( p \right) \ge \sigma _{sk}^\alpha \left( p \right)\\ {\left( {\frac{{\sigma _{sk}^\beta {\rm{(}}p{\rm{)}}}}{{\sigma _{sk}^\alpha {\rm{(}}p{\rm{)}}}}} \right)^\sigma }, \sigma \le - 2, \sigma _{sk}^\beta \left( p \right){\rm{ < }}\sigma _{sk}^\alpha \left( p \right) \end{array} \right. $ | (1) |
其中:σ称为曲面变化度[17](或称为曲面变分[15-16]), 它被定义为p点及其邻域点构成的协方差矩阵C的最小特征值λ0与所有特征值之和的比值, 它表示了该点处曲面的弯曲程度。
σskβ(p)是定义在饱和类k邻域(即包含p点的类k邻域)上的曲面变化度, σskα(p)是定义在欠类k邻域(即不包含p点的类k邻域)上的曲面变化度, 当k不是很小时, σskβ(p)和σskα(p)都能够反映出p点处曲面的弯曲程度, 而σskβ(p)/σskα(p)则反映了p点对曲面的影响程度。若p点是曲面上的点, 则有σskβ(p)/σskα(p)≈1;若p点不是曲面上的点, 必有σskβ(p)/σskα(p)>>1。因此可将σskβ(p)/σskα(p)定义为基于曲面变化度的局部离群系数SVLOF[17], SVLOF的这种定义是基于曲面法矢量方向基本不变的前提。在光滑曲面上, 曲面法矢量的方向基本不变, 因此SVLOF对光滑曲面上的近离群点能够很好地识别。然而, 在三维实体的棱边或棱角附近, 曲面法矢量的方向发生了较大的变化, SVLOF会出现反常现象, 使σskβ(p)≤σskα(p), p点距离主体点云越远, σskβ(p)相对于σskα(p)越小。为了克服SVLOF的局限性, 文献[18]给出了新的定义, 并称为ESVLOF。
在光滑曲面上, ESVLOF与SVLOF具有同样的定义; 在三维实体的棱边或棱角处, 由于σskβ(p)≤σskα(p), 为了取得同样的阈值来识别离群点, 将ESVLOF定义为σskβ(p)/σskα(p)的负指数形式, 使ESVLOF(p)≥1, 且与曲面的弯曲程度无关。若ESVLOF(p)>th(其中th>>1), 表示p点不是曲面上的数据点, 它应该是噪声点(即文献[17-18]中所述的近离群点); 若ESVLOF(p)=1, 则表示p点是曲面上的重复点, 去掉p点后曲面不会发生变化; 若1 < ESVLOF(p)≤th, 表示p点是曲面上的有效数据点, 去掉该点, 会对曲面产生一定的影响, p点对曲面的影响程度可由ESVLOF(p)来度量, ESVLOF(p)越小表示p点对曲面的影响越小。
1.2 数据点可去掉的条件远离群点是必须要去掉的, 可同文献[17-18]一样通过聚类方式来完成, 本文所研究的对象是不包含远离群点的主体点云。
首先, 噪声点(即近离群点)是要去掉的。由文献[18]可知, 它满足ESVLOF(p)>th(th>>1)。由于ESVLOF(p)≥1, 所以不含噪声的点云满足1 < ESVLOF(p)≤th。
其次, 对曲面变化度无影响或影响较小的数据点是可去掉的。即可去掉的点应满足ESVLOF(p) < 1+γ, 其中γ≥0是一个设定的误差项。
若将误差项γ设置为一固定值, 将会执行类似均匀的简化[9], 均匀简化不能保留突变区域较多的点。在曲面上, 突变区域就是曲面变化度σskβ(p)较大的区域, 由于0≤σskβ(p)≤1/3, 所以, 可定义:
| $ \gamma = \varepsilon \left( {1/3 - \sigma _{sk}^\beta \left( p \right)} \right) $ | (2) |
其中:ε是一个略大于0的误差项, 称为相似系数。若给定一个相似系数ε, 则被简化掉的点数将随着曲面突变度的增大而减小。由此可得数据点可去掉的条件是:
| $ \left\{ \begin{array}{l} ESVLOF{\rm{(}}p{\rm{) < 1 + }}\varepsilon {\rm{(1/3}} - \sigma _{sk}^\beta {\rm{(}}p{\rm{))}}\\ ESVLOF{\rm{(}}p{\rm{) > }}th{\rm{;}}\;\;\;\;\;\;th \gg 1 \end{array} \right. $ | (3) |
为防止平面及近似平面的过度简化, 需要限制类k邻域的搜索半径, 按文献[18]中的式(10) 确定类k邻域的最大搜索半径阈值rth, 对点云中的p点计算类k邻域Nbskβ(p)、欠类k邻域Nbskα(p)及类k邻域点数m, 然后作如下处理:
1) 若m < 0.7k，表示点p周围rth范围内数据点数已经很少, 则不作任何处理。
2) 若m≥0.7k，表示点p周围rth范围内数据点较多, 需要作适当的简化, 则按式(1) 计算ESVLOF(p)(其中负指数系数σ按文献[18]选择为-4), 并按式(3) 处理点p:
a)若ESVLOF(p)>th，表示p点为近离群点, 则删除p点；
b)若ESVLOF(p) < 1+ε(1/3-σskβ(p))，表示p点对曲面变化度无影响或影响较小, 则删除p点。
3 实验与分析本文算法用VC + +6.0语言实现, 并在启天M1750商用计算机(Pentium Dual-core CPU, 主频3.06 GHz, 内存2 GB)上进行测试。
由于本文算法具有去噪和简化的双重功能, 已有单纯去噪算法和单纯简化算法都不能直接与之对比。分析式(3) 被简化掉数据点满足的条件，可以看出, 本文运算量主要集中在曲面变化度σskβ(p)和σskα(p)的计算上, 而曲面变化度计算的快慢与k邻域的计算方法有关。式(3) 中去掉满足ESVLOF(p)>th条件的点, 实际上, 就是文献[18]的核心算法；而1+ε(1/3-σskβ(p))的计算，只是利用了ESVLOF(p)计算过程中的中间结果σskβ(p)而进行的简单计算。如果采用文献[18]中所用的k邻域计算方法, 其效率必定与文献[18]相似, 且去噪效果相同，因此, 后续的所有实验均不考虑噪声的滤除, 只进行简化效果的比较。
对于同样的点云数据, 三维重建的直观效果与所用的算法有关。Ball Pivoting算法[19]具有较高的运算效率, 但自身具有较强的曲面平滑作用, 使重建后的三维实体缺少锐利的棱边。Hoppe等[20]根据稠密的散乱点集自动计算法矢信息, 用切平面线性逼近待重建曲面的局部形状, 然后利用实现等值面抽取的步进立方体算法输出曲面的三角化模型。该算法自动化程度高, 能够识别曲面边界, 但对于曲面边界以及尖锐棱边部分的重建效果仍不够理想。周儒荣等[21]对Hoppe提出的三角网格面重建算法进行了改进, 能更好地进行有界曲面以及带尖锐棱边曲面的重建, 且效率较高。因此, 实验中均选择周儒荣算法[21]输出三维实体的三角网格。
3.1 仿真验证首先利用Matlab的peaks函数产生如下仿真数据:在以点(-3, -3, 0)、(3, 3, 0) 为对角线的正方形平面内产生3 721个数据点, 然后增加1%, 幅度不大于30%的随机噪声, 利用随机函数均匀获取2 076个点作为仿真点云数据。取k=15, th=1.5, 相似系数度ε取不同值进行实验, 统计结果如表 1所示, 简化后的部分三维点云与三角网格如图 1所示。
|
表 1 peaks仿真数据简化统计(点云个数=2 076, k=15, th=1.5) Table 1 Simplification statistics of peaks simulated data (Number of point cloud=2 076, k=16, th=1.5) |
|
图 1 peaks简化后的点云及网格 Figure 1 Simulated point clouds and meshes of peaks |
由于实际数据量比较大, 为提高算法效率, 可适当减小类k邻域的大小。本文实验中选择k=10, th=2.5, 相似度系数取不同值, 对bunny点云和horse点云进行简化实验。实验开始前, 先用聚类方法将原始点云中的远离群点去掉, 实验过程中仅对包含近离群点的原始点云进行简化。bunny简化前后的点云如图 2所示, 图 2(c)是基于两点之间距离的均匀简化的情况。由于在二维空间观察三维点云不够直观, 因而后面的简化效果比较不再给出简化后的点云图, 只给出简化后重构的三角网格, 如图 3~4。图 4为点数与图 3相当的均匀简化后输出的三角网格。对于图 2(a)的bunny点云, 算法的简化率及耗时统计如表 2。horse点云的简化结果如图 5所示。
|
图 2 bunny简化前后的点云图 Figure 2 Map of bunny point cloud before and after simplification |
|
图 3 本文算法简化后输出的三角网格 Figure 3 Output simplified triangular mesh by the proposed method |
|
图 4 采用均匀简化输出的部分三角网格(bunny) Figure 4 Output simplified triangular mesh by uniform simplification method (bunny) |
|
|
表 2 两种算法对bunny数据简化统计(k=10, th=2.5) Table 2 Simplification statistics of bunny data(k=10, th=2.5) |
|
图 5 两种方法对horse点云的简化结果 Figure 5 Simplification results of horse point cloud by the proposed method and uniform simplification method |
从表 1的仿真数据和表 2的实测数据统计来看, 对于同一种点云数据, 相似系数ε越大, 简化掉的点数越多, 简化率越高, 当ε趋近于0时(如ε=0.000 1时), 几乎失去了简化效果。实际上当ε=0时, 只去掉了点云中的近离群点, 本文算法退化为ESVLOF去噪算法。从图 1中ε=0.02到0.08的三角网格, 可以明显看出几何特征被完整地保留了下来, 保留下的数据点主要集中曲面的突变区域, 平坦区域的点个数较少, 且曲面越平坦保留的点越少; 当相似系数很大时(ε=0.08), 较为平坦的曲面变为平面, 几何特征有所丢失, 说明此时点云被过度简化, 因而实际应用中, 为防点云被过度简化, 相似系数不能选择过大。进一步对比图 3和图 4, 明显可以看出本文简化后输出的三角网格图 3比较光滑, 采用均匀简化的图 4则表面有小的凸起, 说明本文算法可以滤除点云噪声, 去噪和简化可同时进行。同样的问题也出现在图 5中, 图 5(b)的马脖子上方也有小的凸起。对比图 3(d)和图 4(d), 可以发现当精简率过高时, bunny耳朵处的数据出现了问题, 图 4(d)丢失边缘, 而图 3(d)的边缘仍能保留, 这说明本文算法可以较好地保留模型的边界数据。同时，图 5(d)的马耳朵明显比图 5(b)真实。表 2中的耗时比约等于1, 说明本文算法与文献[18]的独立点云去噪算法具有同等的运算效率。这说明本文算法可将点云的预处理(即点云去噪和点云简化)效率提高一倍。
4 结语本文通过对ESVLOF定义的分析, 给出了ESVLOF的性质, 并利用ESVLOF去噪过程中的中间结果——曲面变化度σskβ(p), 和预设的相似度系数ε构造出随曲面变化度增大而减小的局部阈值γ, 将ESVLOF小于阈值γ的数据点去除, 可在几乎不增加时间开销的情况下, 同时做到点云去噪与点云的非均匀简化。通过仿真和实际数据实验可知, 本文算法不但可以保留原始数据的几何特征, 还可将三维点云的预处理效率提高近一倍。
| [1] | WANG J, HAN J, PEI J. CLOSET+: searching for the best strategies for mining frequent closed item sets [C]//KDD 2003: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 236-245. |
| [2] | 陈西江, 章光, 花向红. 于法向量夹角信息熵的点云简化算法[J]. 中国激光, 2015, 42(8): 336-344. (CHEN X J, ZHANG G, HUA X H. Point cloud simplification based on the information entropy of normal vector angle[J]. Chinese Journal of Lasers, 2015, 42(8): 336-344.) |
| [3] | HUR S M, KIM H C, LEE S H. STL file generation with data reduction by the delaunay triangulation method in reverse engineering[J]. The International Journal of Advanced Manufacturing Technology, 2002, 19(9): 669-678. DOI:10.1007/s001700200112 |
| [4] | 李国俊, 李宗春, 侯东兴. 基于Delaunay三角化的噪声点云非均匀采样[J]. 计算机应用, 2014, 34(10): 2922-2924, 2929. (LI G J, LI Z C, HOU D X. Delaunay-based non-uniform sampling for noisy point cloud[J]. Journal of Computer Applications, 2014, 34(10): 2922-2924, 2929. DOI:10.11772/j.issn.1001-9081.2014.10.2922) |
| [5] | LICHTI D D, GORDON S J. Error propagation in directly georeferenced terrestrial laser scanner point clouds for cultural heritage recording[EB/OL]. [2017-01-10]. https://www.fig.net/resources/proceedings/fig_proceedings/athens/papers/wsa2/WSA2_6_Lichti_Gordon.pdf. |
| [6] | 张有亮, 刘建永, 付成群, 等. 新的点云数据简化存储方法[J]. 计算机应用, 2011, 31(5): 1255-1257. (ZHANG Y L, LIU J Y, FU C Q, et al. New method for point cloud data reduction[J]. Journal of Computer Applications, 2011, 31(5): 1255-1257.) |
| [7] | OSHIMA T. Modern survey of large bridge and tunnel project for their construction control[EB/OL]. [2017-01-10]. https://www.fig.net/resources/proceedings/fig_proceedings/korea/abstracts/pdf/session17/oshima-abs.pdf. |
| [8] | 郑德华. 点云数据直接缩减方法及缩减效果研究[J]. 测绘工程, 2006, 15(4): 27-30. (ZHENG D H. The data reduction of point cloud and analysis of reduction effect[J]. Engineering of Surveying and Mapping, 2006, 15(4): 27-30.) |
| [9] | 黄国珍, 卢章平. 面向逆向工程的点云数据简化方法[J]. 机械设计与研究, 2005, 21(31): 59-61. (HUANG G Z, LU Z P. Method of point cloud data reduction for reverse engineering[J]. Machine Design and Research, 2005, 21(31): 59-61.) |
| [10] | SIHVO T, NIITTYLAHTI J. A low cost solution for 2D memory access[C]//MWSCAS 2006: Proceedings of the 49th IEEE International Midwest Symposium on Circuits and Systems. Piscataway, NJ: IEEE, 2006: 123-127. |
| [11] | WENTZLAFF D, GRIFFIN P. On-chip interconnection architecture of the tile processor[J]. IEEE Micro, 2007, 27(5): 15-31. DOI:10.1109/MM.2007.4378780 |
| [12] | SAREEN K K, KNOPF G K, CANAS R. Contour-based 3D point cloud simplification for modeling freeform surfaces[C]//Proceedings of the 2009 IEEE Toronto International Conference on Science and Technology for Humanity. Piscataway, NJ: IEEE, 2009: 381-386. |
| [13] | 杜晓晖. 一种无记忆点云迭代简化算法[J]. 计算机工程与应用, 2012, 48(3): 182-184. (DU X H. Memoryless iterative point cloud simplification algorithm[J]. Computer Engineering and Applications, 2012, 48(3): 182-184.) |
| [14] | KIM S-J, KIM C-H, LEVIN D. Surface simplification using a discrete curvature norm[J]. Computer & Graphics, 2002, 26(5): 657-663. |
| [15] | 黄文明, 肖朝霞, 温佩芝, 等. 保留边界的点云简化方法[J]. 计算机应用, 2010, 30(2): 348-384. (HUANG W M, XIAO Z X, WEN P Z, et al. Point cloud simplification with boundary points reservation[J]. Journal of Computer Applications, 2010, 30(2): 348-384.) |
| [16] | PAULY M, GROSS M, KOBBELT L P. Efficient simplification of point-sampled surfaces [C]//VIS 2002: Proceedings of the 2002 IEEE Conference on Visualization. Washington, DC: IEEE Computer Society, 2002: 163-170. |
| [17] | 聂建辉, 胡英, 马孜. 散乱点云离群点的分类识别算法[J]. 计算机辅助设计与图形学学报, 2011, 23(9): 1526-1532. (NIE J H, HU Y, MA Z. Outlier detection of scattered point cloud by classification[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(9): 1526-1532.) |
| [18] | 赵京东, 杨凤华, 刘爱晶. 散乱点云近离群点识别算法[J]. 计算机应用, 2015, 35(4): 1089-1092, 1128. (ZHAO J D, YANG F H, LIU A J. Near outlier detection of scattered point cloud[J]. Journal of Computer Applications, 2015, 35(4): 1089-1092, 1128. DOI:10.11772/j.issn.1001-9081.2015.04.1089) |
| [19] | BERNARDINI F, MITTLEMAN J, RUSHMEIER H, et al. The ball pivoting algorithm for surface reconstruction[J]. IEEE Transactions on Visualization and Computer Graphics, 1999, 5(4): 349-359. DOI:10.1109/2945.817351 |
| [20] | HOPPE H, DE ROSE T, DUCHAMP T, et al. Surface reconstruction from unorganized points[J]. Computer Graphics, 1992, 26(2): 71-78. DOI:10.1145/142920 |
| [21] | 周儒荣, 张丽艳, 苏旭, 等. 海量散乱点的曲面重建算法研究[J]. 软件学报, 2001, 12(2): 249-255. (ZHOU R R, ZHANG L Y, SU X, et al. Algorithmic research on surface reconstruct ion from dense scattered points[J]. Journal of Software, 2001, 12(2): 249-255.) |