郭赵阳, 李水艳

(河海大学 理学院, 江苏 南京 211100)

0 引言

曲线重构作为计算机辅助图形学应用中的核心技术,在虚拟视觉、场景建模、目标识别、工业设计与制造等领域发挥着极其重要的作用.近年来,激光扫描技术的快速发展,使人们可以快速地获取图形边界的散乱点云数据[1].基于采样点,通过建立模型可以反求出目标图形轮廓,这是对图形进行计算、分析和绘制的重要依据,极大地促进了计算机图形学领域中逆向工程问题的解决.实际上,获得的数据往往分布不均匀、数量不足且含有噪声,目标曲线又普遍存在许多细节特征,而当前技术处理过程中往往会模糊特征,甚至放大噪声样本,这严重影响了重构曲线的实用程度,因此受到了众多专家学者的广泛关注.

曲线重构问题的研究已取得了一定进展.Hoppe H等[2]对于带符号的距离函数进行了局部估计,对不规则离散点集边界却无法自动地进行处理.刘斌等[3]运用移动最小二乘法做细化处理，得到稀疏的有序点云,再采用B样条函数进行重构，此方法计算效率较高,但重构出的曲线不能较好地反映尖锐的特征部位.Ji H等[4]提出运用简单的平移不变空间,结合小波变换进行给定数据点的拟合,不过这种方法只能对特定的采样点进行重构,而对一般的散乱点集却没有普适的模型,因此有着较大的局限性.随后,由于Cai J F等[5]严格地建立了基于小波的图像恢复模型与变分模型之间的联系,给散乱点重构问题带来了新的思路.Dong B等[6]初步建立了这种基于小波框架的变分模型,根据紧小波框架的多层次性,不同的差分算子可以自适应地应用到图形的几何结构中,但是当采样点数量较少时,重构出的特征区域准确度不高,重构结果也不够符合人类视觉原理.最近,朱云云等[7]提出对Heaviside函数[8,9]进行改进,使得初始水平集更加收敛于目标轮廓,该算法计算量较大,计算效率低.

文中采用基于小波框架方法的散乱点曲线重构方法,增加了去噪的思想[10],使其图形边缘更加清晰.去噪后的图像用小波紧框架对微分算子进行标准有限差分离散化,模型使用交替方向乘子法(ADMM算法)[11-13]进行求解,最终得到重构结果的隐式表示.本文提出的重构方法有效地降低了噪声对重构的影响,又使所得的曲线轮廓更接近真实图形.Matlab模拟实验表明：存在某些高斯噪音的情况下,该方法能够有效地重构散乱点,并保留大量细节特征.

1 背景知识

1.1 小波紧框架

可数集X⊂L2(R)被称为L2(R)的紧框架,如果

其中〈·,·〉是L2(R)中的内积.

对于给定的

Ψ:={ψ1,…,ψr}⊂L2(R),

由Ψ生成的小波系统

X(Ψ):={ψl,j,k:1≤l≤r;j,k∈Z}

是L2(R)的紧框架时,则X(Ψ)被称为紧小波框架,其中

Ψl,j,k:=2j/2Ψl(2j.-k).

在离散设置中,离散图像u是s维数组.使用W表示快速紧框架分解,并使用WT表示快速重建.由酉扩张原理[14]WTW=I,对于任意图像u都有

WTWu=u.

进一步表示u的L级框架分解

Wu={Wi,ju:0≤l≤L-1,j∈I},

I表示所有小波带的索引集.更多关于框架变换离散算法的细节可以在文献[15,16]中找到.

1.2 水平集方法

在图形数据处理的研究中,水平集演化方法有着重要的应用.

设u:A→R,A⊆Rn.对于常数c,集合{x∈A|u(x)=c}称为u的⊆水平集.若A是二维的,一般来说它是一条曲线.

X=(x1,x2,…,xn)⊂R2是未知曲线S上的采样点集,S*是经过重构得到的曲线.根据采样点集X找到近似于S的S*,需要将函数与给定的曲线相关联.将S*隐式地定义为u的水平集,即S*∶={x:u(x)=0}.然后最小化基于微分算子的变分模型,重构出零水平集近似于未知曲线的u.

2 算法模型

2.1 L0范数最小化去噪

L0范数用来度量向量中非零元素的个数,即

‖x‖0=#(i|xi≠0) ,

其中x=(x1,x2,…,xn),#是计数算子.

使用L0范数确定L层小波框架分解的系数,可以保留和增强所有突出边缘(包括主要和次要细节),并去除低振幅结构(噪声)[17].通过Fast Marching方法[18],利用散乱点与距其最近的网格点的距离生成水平集函数,由于实际操作时采集的散乱点一般都含有噪声,所以此时的边界并不清晰,会干扰重构效果.

因此,本文采用基于小波框架的L0范数最小化方法来进行去噪处理,得到新的水平集函数,其目的是为了突出边缘并且降低噪声.去噪模型为

在上式中，d为Fast Marching方法生成的初始水平集函数.根据平均双增广拉格朗日(MDAL)算法,此优化模型可以转化为

2.2 基于小波框架的CV重构模型

与其他图像问题的变分模型类似,定义一个用于重建的一般变分模型：

其中V是凸集,D:={Dj:1≤|j|≤s}是一个s阶微分算子,H(u,f)是光滑凸函数,f是由散乱点集(如图1(a)所示)获得的给定函数,即初始的近似边界,如图1(b)所示,通常称其为掩膜[19],且定义如下范数

vj是预先选定的与距离函数相关的权重,距离函数定义如下:

Ω是根据图像大小生成的网格点集.

在连续情况下,

而在离散的情况下,

V={u∈L2(Ω):0≤u≤1},D=,

H(u,f)=〈2f-1,u〉.

(a)原始点集 (b)掩膜

由于采集到的散乱点是离散数据,且φ(x)也是离散的,因此需要进行离散化.采用小波框架来代替微分算子,利用其多分辨率结构,在给定图像的不同区域自适应地选择合适的微分算子,比标准离散化方法更具有优势.此时优化问题将变成

其中

根据ADMM算法,该问题相当于求解:

将基于小波框架的去噪和重构模型相结合,最终算法流程如下:

步骤1输入散乱点集X,由距离函数φ(x)生成网格点集Ω上的初始水平集函数d.

步骤2输入d,设定

(i)更新η

ηk+1=((1+μ+γ)I)-1(Id+γηk+

μWT(αk-vk))

(ii)更新α

αk+1=Hλ,μ,γ(Wηk+1+vk,αk)

(iii)更新vk

vk+1=vk+Wηk+1-αk+1

步骤3输入η,设定e0=c0=0,f=η-ε,其中ε是给定参数,令r=2f-1.

(i)更新u

(ii)更新e

(iii)更新c

ck+1=ck+δ(Wuk-ek)

3 数值实验及比较

为对本研究提出的基于小波框架的散乱点隐式曲线重构算法的可行性和有效性进行验证,调整各参数对图像进行了Matlab仿真模拟.在实际测量环境下,未必能采集到大量散乱点,因此在其他条件相同时,用尽可能少的散乱点来进行重构.本小节从原始点集中取部分点进行数值实验:"star"中随机选取134个点, "leaf "中随机选取252个点, "horse"中随机选取567个点.由于散乱点在采集的过程中经常混有一定程度的噪音,为了更接近真实情形,本节实验在采样点集的基础上增加了均值为0,方差为0.2的高斯白噪声.

由距离函数生成的初始水平集函数图像如图2(a)所示,其边界模糊,对比度较低,将对下一步处理产生较大影响.而经过L0范数最小化去噪后,水平集函数图像边界分明,细节处更有辨识度,有助于下一步的重构,如图2(b)所示.

(a)初始水平集函数图像 (b)去噪后的图像

去噪处理后,利用新的清晰图像进行隐式曲线重构.将其分别与结合TV的方法[20]、D.S方法[6]进行比较,其结果如图3～6所示.

(a)TV方法重构star

(a)D.S方法重构star

(a)本文方法重构star

由图3～6可知,“star”在其他模型下,尖角部分重构效果较差,出现弯曲的状况且与实际形状有较大偏离,而用本文方法所得的曲线整体较为平滑,尖锐部分的重构也较为平直,更加贴合实际;“leaf”中,对于复杂的凹陷部分,其他模型的重构效果不尽如人意, 相比之下本文方法效果良好,更为准确；对于“horse”这组实验,其他两组模型的结果中马蹄处都出现了断裂,然而本文方法较为流畅地连接了这一区域,且非特征区域的重构曲线较为平滑,也更加接近真实图形.

为了对结果进行富有统计学意义的对比,本文选取有代表性的点集horse，采用MSE(Mean Square Error)评价方法来定量评估重构结果,该方法将计算重构曲线与原始点集的接近程度,定义如下:

其中，d1为原始点集经Fast Marching生成的水平集,d2为本文算法输出的水平集,n代表网格点个数, MSE越小,说明重构所得的曲线越接近标准.MSE和运行时长的具体数值如表1所示.

表1 MSE及运行时长比较

由表1可知,本文算法兼顾计算效率与重构精度,相比于其他两种方法,MSE值和运行时长都更小,即重构曲线更加贴合原始点集,且节省了大量时间.

重构曲线对比和数据评估结果说明,在散乱点个数和噪音都相同的情况下,本算法能够较为快速地重构曲线,不仅可以清晰地刻画出尖锐、凹陷等细节特征,更加接近实际情况,整体曲线也更加平滑顺畅,偏差程度小.

4 结论

本文基于小波框架方法,建立图像去噪和重构的变分模型,并通过Matlab仿真模拟,与其他重构方法进行比较.数值实验表明,该方法能够降低噪声的干扰,较精确地重构散乱点,忠实于原始图形,因此在工程应用中,具有一定推广意义.接下来的工作将进一步改进算法,使其能够拓展到三维空间,进行散乱点的曲面重构.