一种新的测量数据光顺方法(仅供参考).doc

一种新的测量数据光顺方法（仅供参考）

摘要:根据传统Laplacian光顺算法与图像处理中Kuwahara滤波算法的原理,提出了一种新的测量数据光顺方法.方法兼具Laplacian算法与Kuwahara算法的优点,在有效去除噪声,光顺原始数据的同时,使物体表面原有特征得到了很好的保留、调整、甚至加强.
关键词:逆向工程;测量数据;光顺;Laplacian方法;Kuwahara滤波

A Novel Technique for Smoothing of Measured data
SHEN Hui-cun

Abstract:Based on classical Laplacian method and Kuwahara filter, a novel technique for smoothing of measured data is presented. The proposed technique is provided with the advantages both of Laplacian method and Kuwahara filter. Besides denoising and smoothing measured data effectively, it can preserve, regularize and enhance original features of objects the data measured from.
Key words:reverse engineering; measured data; smoothing; Laplacian method; Kuwahara filter
0 引言
实物数据测量是逆向工程领域的重要工作.以Atos为代表的激光扫描仪是目前较为常用的非接触式测量设备,测量数据一般以STL 文件格式给出,体现为三角网格模型形式.本文研究主要针对这类测量数据展开.虽然Atos等测量设备本身已具有高精度,但人为的干扰及扫描仪本身的缺陷难免使得到的数据带有噪声.这些噪声的存在,对数据的后续处理与利用带来不利影响.因此,需对三角网格模型进行光顺处理,以去除噪声,提高模型质量.光顺的过程就是消除三角网格的局部扰动和噪声的过程,其目标是在剔除噪声获取离散曲面更高阶光滑性的同时,保持网格模型的拓扑信息和几何特征不变,比如保证光顺过程模型不收缩和没有过光顺现象等.
国内外许多学者都对三角网格模型数据的光顺做过研究.总体上看,三角网格模型的光顺基本上都是建立在其微分几何特性计算的基础上的.
三角网格模型光顺算法的分类可以有很多标准,根据特征保持性可以分为各向同性算法和各向异性算法.从算法复杂性角度分析,用于三角网格模型光顺的主流算法有两类:能量法和Laplacian光顺法.能量法[1]是一种基于最优化的方法,通过最小化某种能量函数达到光顺的目的,从理论上有效地保证光顺过程中某些几何度量的变形最小化.由于能量法的计算工作量很大,且难以对局部形状进行控制,故其应用远没有Laplacian法广泛.Laplacian(Laplacian)光顺法[2]通过对每个顶点定义一个Laplacian算子来确定调整方向,然后沿此方向以一定的速度移动顶点达到调整网格的目的,具有线性的时间和空间复杂度.该方法能有效调整网格至规则形状,网格密度与形状都趋于均匀.但对于网格分布不均或含有大量不规则三角片的模型,这种均一化的调整往往会导致原始模型的大范围变形.因此,很多学者对普通Laplacian法进行了不同的改进.如Taubin[3]提出了一种加权Laplacian光顺算法,有效抑制了网格噪声,但不能有效控制调整后模型的变形.Desbrun[4]利用平均曲率法在每个顶点的法矢方向按照该点的近似平均曲率值的大小来调整其位置,取得了较好的光顺效果,但对模型上原有特征细节保持不力,且易产生大量不规则三角片.聂军洪[5]将Laplacian算子法向分量用平均曲率算子来代替,而在切平面上仍然根据周围顶点的几何平均值来调整.这种算法取得了较好的光顺性与特征保持性,但在原始模型的平坦处却带来了新的扰动.
1 预备知识
本文方法是根据传统Laplacian光顺算法与图像处理中的Kuwahara滤波算法的原理而提出的,因此有必要对这两种方法作一简要介绍.
1.1 传统Laplacian光顺方法及Taubin的改进方法
又称普通Laplacian光顺法.该方法对每个顶点定义如下的Laplacian算子:
式中,表示顶点的一邻域,如图1(a)所示.为中各点的权重.
将作用于顶点,可得的位置调整公式为:
(1)
其中是由用户给定的一个正的常数,用以控制网格光顺的速度.
传统Laplacian法使顶点有向其邻域形心移动的趋势,能有效调整网格至规则形状,网格密度与形状都趋于均匀.但对于网格分布不均或含有大量不规则三角片的模型,这种均一化的调整往往会导致原始模型的大范围变形.
针对Laplacian法的缺陷,许多学者对其做了改进.如Taubin指出Laplacian算子并不是一个真正的低通滤波器.为构造一个真正的低通滤波器,他引入了一个大于的常数,对(1)式进行如下改进:
(2)
式中,,,
1.2 Kuwahara滤波算法
三维曲面光顺和计算机视觉的二维图像光顺有很多相似之处,目前很多网格模型光顺思想源于图像去噪算法.在图像处理中,Kuwahara滤波算法根据相邻像素之间的灰度信息进行图像的光滑处理,具有很好的边界保留效果.
该算法可以描述如下,如图2所示,将一个(4L+1)*(4L+1)(图中L=1)的正方形窗口分为四个子正方形区域,通过计算每个子区域的平均亮度和亮度变化率,窗口中心像素值等于具有最小变化率的子区域的平均亮度.我们对其加以改进并引入三角网格模型光顺处理中,期望在光顺的同时使模型原有特征得到保留甚至有所加强.
2 算法设计
2.1 基本思想
本文的目标是构造一种整体光顺效果好,且变形小,模型原有特征得到充分保留的三角网格模型光顺方法.具体思路是:光顺性好的三角网格模型中,相邻三角片之间的法矢变化应有一定规律性.或者说,就光顺模型中某个三角片来看,其法矢应满足一定要求.存在噪声的模型中,这种规律性不明显,三角片法矢的变化甚至可能是杂乱无章的.因此可以认为,三角网格模型光顺可以在三角片法矢调整的基础上进行.这种调整,对模型中的特征区域与非特征区域应区别对待.为此,首先需判断出模型中的特征区域与非特征区域,然后分别采用Kuwahara滤波算子与Laplacian算子进行法矢调整.在三角片法矢调整后,再调整顶点位置,即可完成模型光顺过程.
2.2 基于法矢变化率的区域分类
为便于叙述,给出如下符号说明:表示三角网格模型中的一个三角片,表示为的质心,表示的单位法矢,为的面积.表示的三个顶点的一邻域中三角片的集合,为中元素(即顶点的一邻域中三角片)的个数,表示中第个元素(三角片)与之间的法矢夹角.
为中的变化率,小,表明三角片的第个顶点一邻域中三角片之间的法矢变化较小,即该区域较为平坦.每个顶点的按下式计算:
(3)
式中
对三角片,记(4)
若(为给定的阈值),说明模型中与邻近的区域内三角片之间的法矢变化率较大,该区域可能是特征区域,或者含有较大的噪声.此时,采用Kuwahara滤波算子来调整三角片法矢(因该方法具有很强的去噪以及特征保留、调整能力).
若,则表明与邻近的区域内三角片之间的法矢变化率较小,该区域较为平坦,应为模型中的非尖锐特征区域.此时,采用Laplacian算子来调整三角片法矢,以期快速得到需要的整体光顺效果.
这样就结合了两种算子的优点.为了体现两种算子的特点,在后面的实例中将会给出单独运用其中一个算子进行光顺的效果.
2.3三角片法矢的Kuwahara调整
如上所述,对三角片,若,采用Kuwahara法对三角片法矢进行调整.实际应用时,本文对其进行了改进,在计算出三角片的()对应的顶点后,并不如图像处理中Kuwahara滤波一样取最小亮度变化率区域所有像素的平均值,即的法矢不等于的一邻域三角片的法矢平均值,而是引进了加权平均.
对三角片,首先按下式调整三角片的法矢:
(5)
式中,,为一常数,取2为佳.然后,按下式求得三角片调整后的单位法矢:
(6)
上述法矢调整过程中,因为是一个高斯度量函数,式(5)事实上是双边滤波算法[3]的一个特例,所以上述方法中应用到了图像处理中的Kuwahara滤波算法和双边滤波算法.为了叙述方便,将把这种方法简称为Kuwahara方法.该方法应用了法矢的非线性扩散性质[5] ,保持了模型的尖锐特征,如折痕、尖角等.
2.4三角片法矢的Laplacian调整
对三角片,若,我们将普通Laplacian算子做了改进,用于对这种情况的处理.这样既保持了普通Laplacian算子速度快,调整效果明显的特点,又避免了直接对模型顶点施以Laplacian调整所带来变形过大的问题.以表示网格模型中与三角片有共点或共边的所有三角片的集合.对的三角片,按下式调整其法矢:
(7)
式中,为指定的调整速度因子.考虑到与三角片共点和共边的三角片对的法矢的影响程度不同,见图3(b)中的阴影三角片.对权值的设置可以对与共边的三角片赋以较大的权值.在本文中,阴影三角片的权值是非阴影的1.5倍.
调整过程完成后,按下式计算的单位法矢:
(8)
本文后面的叙述中,将把这种方法简称为法矢Laplacian方法.
2.5 顶点位置调整
三角片法矢调整过程完成后,按下式调整三角网格模型中的每个顶点的位置:
(9)
式中的求和需要对顶点一邻域内所有三角片进行,表示三角片中顶点指向质心的连线,是在方向上的投影,即,如图3(a)所示.
2.6 算法流程
①给定最大迭代次数与阈值,迭代次数;
②对模型中每个三角片,按式(3)计算其三个顶点一邻域内所有三角片的法矢变化率;
③按式(4)计算三个顶点的之和;
④若,用Kuwahara法调整三角片法矢,即按式(5)计算;否则,用Laplacian法调整三角片法矢,即按式(7)计算;然后,用式(6)或(8)计算的单位法矢;
⑤按式(9)调整顶点位置;
⑥,若,结束;否则,转②.
2.7 误差估计
考虑到本文提出的方法及几种传统的光顺算法都没有改变网格模型的拓扑结构,即网格顶点的连接情况,我们可以近似地计算出光顺前后两个对应三角片之间的体积以求得两模型的空隙体积.近似空隙体积的误差估算,相比直接计算模型的体积而言,具有更好的可靠性,因为若光顺后模型有相等数量的凸包和低谷变形时,模型的总体积变化可能相对较少,而空隙体积的估算能较精确的计算出光顺前后模型的变化,而且不必考虑模型是否封闭.在计算空隙体积的时候,两个对应的三角片的位置有相交与否两种情况,如图4(a)三棱柱的体积很容易计算,当两三角片相交的时(如图4(b)所示),要精确地计算两三角片之间的体积就比较复杂,这种情形其空隙体积本身就相对较小,本文对其体积做一近似,对换顶点和转换为普通的三棱柱,其空隙体积取为用转换后的三棱柱体积的1/3.空隙体积越小,表明光顺前后模型的形状变化越小.
3 实例与结论
利用本文方法,对几个模型进行了光顺处理,并与其它光顺方法做了比较,结果见表1、表2及图5、图6.由这些图表可知,本文方法将法矢Kuwahara与Laplacian调整相结合,用于三角网格模型的光顺处理,取得了较为理想的光顺效果.不仅有效去除了噪声,且光顺前后模型的变形很小,物体原有特征得到了较好的保持甚至加强.
表1 凹槽模型不同方法光顺后的空隙体积(含有10000个三角片,5002个顶点)
光顺迭代次数 Taubin方法 传统Laplacian方法 本文方法
6 6735.67 20296.89 1270.38
20 23938.25 53738.55 2085.07
50 50969.59 103184.37 2913.57
表2 人脸模型不同方法光顺后的空隙体积(含有13565个三角片,6904个顶点)
光顺迭代次数 Taubin方法 传统Laplacian方法 本文方法
6 2057.6 5804.87 800.45
参考文献
[1] 彭芳瑜,周云飞,周济.基于广义能量法的曲面光顺[J].华中科技大学学报 (自然科学版),2002, 30(2): 5~8
[2] Leif Kobbelt, Swen Campagna, Jens Vorsatz, and Hans-Peter Seidel. Interactive Multi-resolution modeling on arbitrary meshes[A]. In: Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH'98[C], Orlando, 1998: 105~114
[3] G.Taubin. A signal processing approach to fair surface design[A]. In: Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH'95[C], Los Angeles, California, 1995: 351~358
[4] M.Desbrun, M.Meyer, P.schrOder, and A.H.Barr. Anisotropic feature-preserving denoising of height fields and bivariate data[A]. In: Proceedings of the 9th International Meshing Roundtable[C], New Orleans, Louisiana, 2000: 145~152
[5] 聂军洪. 任意拓扑结构三角网格模型优化调整技术研究[D]. 南京:南京航空航天大学,2003