基于SVM和空间投影的点云空洞修补方法

—269— 基于 SVM 和空间投影的点云空洞修补方法 蒋 刚 (西南科技大学制造科学与工程学院，绵阳 621010) 摘 要：为实现在逆向工程中的点云空洞修复，在理论研究的基础上，通过空间投影获得二维数据，采用支持向量机做回归分析，获得残 缺点的坐标参数，从而完成空洞修补，运用数字实验对该方法的可行性进行验证，仿真实验结果表明，该方法可以获得良好的修补效果， 能够为曲面建模和数控系统 G 代码的生成提供完整的点云数据，具有一定应用价值。 关键词：支持向量机；点云；空洞修补；空间投影 Point Cloud Hole Filling Method Based on SVM and Space Projection JIANG Gang (School of Manufacturing Science & Engineering, Southwest University of Science & Technology, Mianyang 621010) 【Abstract】In order to implement the point cloud hole filling in reverse engineering, this paper adopts space projection technology and Supported Vector Machine(SVM) based on Statistic Learning Theory(SLT). Coordinate value of fragmentary points can be gotten by SVM regression, and the whole filling work can be finished by this method. Some numerical experiments have been applied to verify the feasibility of this method. Simulation experimental results show its good performance, and it can give complete points for curve modeling and G code generation in the next step. It has the application values. 【Key word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 s】Supported Vector Machine(SVM); point cloud; hole filling; space projection 计 算 机 工 程 Computer Engineering 第 35卷 第 22期 Vol.35 No.22 2009 年 11 月 November 2009 ·开发研究与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 技术· 文章编号：1000—3428(2009)22—0269—03 文献标识码：A 中图分类号：TP391 1 概述 近年来，逆向工程中的点云三维曲面重建是研究的热点， 利用三维激光扫描仪获得的稠密点云，细节清楚，受到研究 人员的重视。在扫描过程中，可能因遮档、系统扫描误差等 原因造成点云的残缺。残缺点云形成的空洞直接影响后期的 建模效果，必须修补。 已有较多的研究人员对此进行深入研究。文献[1]通过引 入平均误差及平均曲率影响因子构造连续曲面并计算空洞数 据点。文献[2]提出一种三维残缺数据的多层感知器神经网络 修补方法，具有较高的修补效率和精度。也有学者探讨了将 RBF 神经网络应用于残缺曲面数据修补问题。文献[3]提出并 实现一个散乱点云的三角网格重构算法，取得了较好的修补 效果。 本文在文献[4-7]的基础上，通过三维坐标计算点的相关 度和连接性，并以此为基础对点云完成分层运算，获得纯净 的空洞区域。通过空间映射获得 3 个方向的二维坐标，采用 支持向量机(Supported Vector Machine, SVM)分别对它们进行 回归运算，获得待修补点的三维坐标，从而完成空洞修补。 2 支持向量机简介 给定训练样本集 {( , ), 1,2, , }i ix y i n= " ，其中， Nix R∈ 为 输入； iy 输出，定义 ε 不敏感损失函数： 0 | ( ) | | ( ) | | ( ) | | ( ) | y f y f y f y fε ε ε ε −⎧− = ⎨ − − − >⎩ x x x x ≤ (1) 在线性回归的情况下，预测函数具有如下形式： ( )f b=< ⋅ > +x w x (2) 其中， < ⋅ >w x 为向量内积[7]，优化目标是： 2 , , 1 1min || || ( ) 2 s.t. | | 0, 0, 1,2, , n i iw b i i i i i C y b i n ξ ξ ξ ε ξ ξ ξ ∗ = ∗ + +∑ − < ⋅ > − + = w w x " ≤ ≥ ≥ (3) 其中， ,i iξ ξ ∗ 是松弛变量；C>0 是惩罚系数。引入 Lagrange 乘子把它转化成无约束二次规划： , ,, , , max min ( , , , ) w b L bξα α β β ξ ξ∗ ∗ ∗⎡ ⎤⎡ ⎤⎣ ⎦⎢ ⎥⎣ ⎦w (4) 2 1 1 1 1 1 || || ( ) ( ( )) 2 ( ( )) ( ) n n i i i i i i i i n n i i i i i i i i i i L C y x b y x b ξ ξ α ε ξ α ε ξ β ξ β ξ ∗ = = ∗ ∗ ∗ ∗ = = = + + − + − − < ⋅ > − −∑ ∑ + + − < ⋅ > − − +∑ ∑ w w w 根据鞍点定理，得到对偶问题： } , , , 1 1 1 1 1 1max ( )( ) 2 ( ) ( ) s.t. ( ) 0, 0 ,0 n n i i j j i j i j n n i i i i i i i n i i i i i x x y C C α α β β α α α α ε α α α α α α α α ∗ ∗ ∗ ∗ = = ∗ ∗ = = ∗ ∗ = ⎧ ⎡ ⎤− − − < ⋅ > −∑ ∑⎨ ⎣ ⎦⎩ + + −∑ ∑ − =∑ ≤ ≤ ≤ ≤ (5) 根据 KKT 条件[8]有： [ ( )] 0 [ ( )] 0 i i i i i i i i y x b y x b α ε ξ α ε ξ∗ ∗ + − − < ⋅ > − =⎧⎪⎨ + − − < ⋅ > − =⎪⎩ w w (6) 基金项目：四川省教育厅科研基金资助项目(2006C077)；西南科技 大学引进人才基金资助项目(06zx7110) 作者简介：蒋 刚(1978－)，男，副研究员、博士，主研方向：信号 处理，人工智能 收稿日期：2009-09-10 E-mail：jgg0429@tom.com —270— 不为 0 的α 对应的样本点 ix 称作支持向量，可得： ( ) ( )i i i x SV f x bα α ∗ ∈ = − < ⋅ > +∑x x (7) 在非线性情况下，采用核函数 ( , )i jK x x ，可求得回归估 计函数： ( ) ( ) ( , )i i i x SV f K x bα α ∗ ∈ = − +∑x x (8) 3 空间投影与 SVM 求解算法 给定一条三维空间曲线的采样点序列 P(1)P(2)…P(m)， 该曲线上有部分残缺点 p(n), p(n+1)，如图 1 所示。 Pyz(1) P(1) z Pxz(1) Pxz(n) Pxz(m) P(n) P(m) Pyz(n) Pyz(m) Pxy(1) Pxy(n) Pxy(m) x y 图 1 空间投影与 SVM 修补原理 直接求解三维残缺点 P(n)比较困难。现考虑把 P(1) P(2)…P(m)分别向 xoy, yoz 和 xoz 面投影，可以获得 Pxy(1) Pxy(2)…Pxy(m), Pyz(1)Pyz(2)…Pyz(m)和 Pxz(1)Pxz(2)…Pxz(m) 3 个新的序列，它们均为二维数据。 采用支持向量机分别对 3 个新的序列作回归，通过内插 值的方式可以获得 P(n)点的空间坐标(Pxy(n), Pyz(n), Pxz(n))， 从而完成残缺点的修补。 为了更好地展示这一算法的求解原理，以一个点云实例 予以说明。截取一段残缺点云，向 xoy, yoz 和 xoz 面投影，可 以获得 3 个平面数据集。 采用径向基核 ( )2( , ) exp (( ) / )i iK x x σ= − −x x 作为核函数， 调节因子 C=10, σ=0.02，ε=0.1 时，结果误差 E=0.17。 调节 C, σ 和 ε 的值可以获得更优的精度。此外，如果残 缺点过多，周围能提供有效信息的数据太少，回归精度就会 降低。 为给后面的实验及参数优化提供参考，以这段点云为对 象，分别用线性核 ( , )i iK x x=< ⋅ >x x 、多项式核 ( , )iK x =x ( 1)dix< ⋅ >+x 、多层感知器核 ( , ) tanh( ( , ) )i iK x v x c= < > +x x 、径 向基核 ( )2( , ) exp (( , ) / )i iK x x σ= −x x 进行实验，如表 1 所示。 表 1 不同核函数的求解结果 核函数名称 参数取值 误差/(×10-2 mm) C=10, ε=0.10 0.293 3 线性核 C=12, ε=0.03 0.276 1 C=10, ε=0.10, d=5 0.210 6 多项式核 C=12, ε=0.03, d=7 0.200 9 C=10, ε=0.10, σ=0.02 0.170 1 径向基核 C=12, ε=0.03, σ=0.05 0.010 8 C=10, ε=0.10, c=1.3 0.182 2 多层感知器核 C=12, ε=0.03, c=1.7 0.153 9 从表 1 可以看出，对这类问题的求解，径向基核可获得 更高的精度，下面将以径向基核构建支持向量机。 4 基于 SVM 的空洞修补实验 依托“反求工程与快速制造”四川省重点实验室的工业 型激光三维扫描仪 LSH800PLUS，对一车体模型现场扫描， 获得原始点云。 4.1 数据预处理 原始点云中总是包含一些噪声数据，主要包括支撑平台、 光学投射等原因引起的噪声，通过聚类的方式，根据点与群 体之间的背离因子剔除噪声，结果如图 2 所示。 图 2 去除噪声 在图 2 中有个明显的空洞，用方框指明它所在的区域， 空洞定位采用 KD 树。如果直接把点云向 XOY, YOZ, XOZ 投 影，由于数据层重叠，因此无法提取空洞。 由于各个数据点的空间坐标已知，因此根据各点的坐标 可以计算点与点的空间距离，包括空间直线距离和投影到 X, Y, Z 轴上的距离，计算各点对应的法矢，根据距离可以实现 点云自动分层：假定待求解点为 P(Xn, Ym, Zk)，P 的法矢为 τ， 以 R 为半径作圆球，该球内的数据点将形成连续的微型面片 s，具有法矢 τs，当 R 足够小时 0 lim sR τ→ =τ (10) 实验中取 R=5ε，ε 为 LSH800PLUS 的扫描精度。以法向 矢量的跃变量 К 为指标，对模型中的每个点上色。定义色阶 μ 为 К 的线性函数，且 μ=0.01К-0.002 (11) 分层效果如图 3 所示。 色度 0.000 0.098 0.248 0.399 0.549 0.699 0.850 1.000 图 3 分层效果 4.2 SVM 求解空洞点 实现分层后，操作时以层为处理对象。根据空间投影法， 把该区域向 XOY, YOZ, XOZ 面投影获得平面数据。以空洞区 域最外围为边界构建矩形 R1，然后以 R1 的中心为基点放大 得到矩形 R2，R2 的边长为 R1 的 3 倍，目的是通过曲线两端 的数据来预测中间段数据。 以 R1 的原点 O 开始，步长为扫描仪的精度 ε，分别从 X 和 Y 方向在矩形 R2 内进行扫描，可获得 182 条不完整的曲 线。采用径向基核构建支持向量机，参照第 3 节的算法求解 残缺点的平面坐标值。 从空洞的边缘开始，依次进行修补，上一次求解的结果 视为下一步求解的已知数据，逐步减小空洞面积，最后完成 投影面上空洞的修补。 在 YOZ, XOZ 面内，实验步骤相同，可获得另外 2 个平 面内的坐标，由此求出点的空间三维坐标。对整个空洞按以 上方法求解，可获得的整个区域中残缺点的坐标，从而完成 空洞的修补，效果如图 4 所示。 —271— 图 4 空洞修补效果 4.3 实验结果 为了对比算法的优劣，在同一台电脑上对 2 种算法进行 验证：一种是本文方法，简记为空间投影法；另一种是对空 间曲线直接回归求解残缺点，简记为直接回归法。机器配置、 实验环境和实验结果如下： (1)实验验电脑基本配置：CPU 为 P4 3.4 GHz，双核；硬 盘为 SATA Seagate 7 200 rpm, 160 GB；显卡为 Geforce 128 MB； 内存为 DDR, 2 GB。 (2)实验环境：防火墙关闭，杀毒软件关闭，且没有其他 进程。 (3)空间投影法的实验耗时为 722.47 s，直接回归法的实 验耗时为 961.50 s(10 次实验平均值)。 关于修补精度，目前在反求领域没有统一的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ，由于 没有比较的参考值，因此无法比较算法优劣，只能通过建模 后的视觉效果简单地加以描述。在本文介绍的实验中，从视 觉效果的角度难以看出 2 种算法的优劣，可理解为 2 种算法 的修补精度近似相等。 5 结束语 本文在前期研究工作的基础上，提出通过空间投影获得 平面数据，以点的空间坐标为计算依据完成点云的分层，从 而精确提取出空洞区域。通过支持向量机完成空洞残缺点坐 标的计算，完成整个空洞修补。实验结果表明，采用径向基 核构建 SVM 可获得更高的精度，通过投影获得平面数据， 以平面数据完成修补可以让算法更快收敛，本文算法在实时 性上更具优势，具有一定实用价值。另外，对具有流线型的 空洞区域和含较多棱边的空洞进行修补时，参数优化有差异， 寻找其中规律并量化处理，可提高算法效率。今后的工作是 寻找更优的核函数。 参考文献 [1] 陈志杨, 张三元, 叶修梓. 点云数据中空洞区域的自动补测算 法[J]. 计算机辅助设计与图形学学报, 2005, 17(8): 1793-1797. [2] Xiong Bangshu, He Mingyi. 3D Incomplete Data Repairing Algorithm Based on RBF Neural Network[J]. Journal of System Simulation, 2005: 17(12): 2939-2942. [3] 董洪伟. 散乱点云的三角网格重构[J]. 计算机工程, 2005, 31(15): 30-32. [4] 蒋 刚. 核机器方法若干问题研究[D]. 成都: 西南交通大学, 2006. [5] 蔡 勇. 基于核机器学习方法的点云处理若干方法研究[D]. 成 都: 西南交通大学, 2006. [6] Cai Yong, Xiao Jian, Jiang Gang. Optimized Sub-sample Curve Expression Based on SVM[J]. Information and Control, 2008, 37(1): 108-112. [7] Liu He, Cai Yong, Jiang Gang. Surface Reconstruction Method Based on Support Vector Regression Machine for Point Sets[J]. Machinery Design and Manufacture, 2008, 3: 85-88. [8] Vapnik V N. The Nature of Statistical Learning Theory[M]. New York, USA: Springer, 1995. 编辑 陈 文 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (上接第 268 页) 同样由 sinϕ =v’y 可以得出虚拟人左右方向上的地形坡 度。以上所有矢量运算均由 GPU 高效率地完成，从而以较低 的运算成本实现了虚拟人对虚拟环境地形的感知。 4 结束语 通过虚拟人在行走过程中与地面的碰撞检测，使人体与 地面处于合理的相对位置。实现了虚拟人在行走过程中对其 所处的虚拟世界中环境地形的感知和反应能力，人体动作适 应于环境变化的调整保证了虚拟人运动的真实性，利用动作 融合的方法实现了人体在不同坡度沿不同方向行走时的动作 调整，这些基于 GPU 的矩阵、矢量和三维顶点的计算，也使 多个虚拟人的驱动满足实时性的要求。 参考文献 [1] Thalmann N M, Thalmann D. Virtual Humans: Thirty Years of Research, What Next?[J]. Visual Computer, 2005, 21(11): 997-1015. [2] 柳 辉, 李星新. 基于 Jack 的虚拟人抓握过程的设计及实现[J]. 计算机工程, 2008, 34(8): 238-239. [3] 胡晓雁, 梁晓辉, 赵沁平. 自动匹配虚拟人模型与运动数据[J]. 软件学报, 2006, 17(10): 2181-2191. [4] Esteves C, Arechavaleta G, Laumond J P. Motion Planning for Human-robot Interaction in Manipulation Tasks[C]//Proc. of the IEEE International Conference on Mechatronics & Automation. Niagara Falls, Canada: IEEE Press, 2005: 1766-1771. [5] Aubel A, Boulic R, Thalmann D. Real-time Display of Virtual Humans: Levels of Details and Impostors[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2000, 10(2): 207-217. [6] Sang I P, Shin H J, Kim T H, et al. On-line Motion Blending for Real-time Locomotion Generation[J]. Computer Animation Virtual Worlds, 2004, 15(2): 125-138. [7] Oshita M. Pen-to-mime: Pen-based Interactive Control of a Human Figure[J]. Computers & Graphics, 2005, 29(6): 931-945. [8] Cha M, Yang J, Han S. An Interactive Data-driven Driving Simulator Using Motion Blending[J]. Computers in Industry, 2008, 59(5): 520-531. [9] Mori H, Hoshino J. ICA-based Interpolation of Human Motion[C]// Proc. of IEEE Symposium on Computational Intelligence in Robotics and Automation. Kobe, Japan: IEEE Press, 2003: 453-458. 编辑 任吉慧