L0范数最小化方法及其在网格光顺算法中的应用

【摘要】网格光顺算法已经广泛应用于工业控制和娱乐生活中。本文提出了一种基于L0范数网格光顺方法。提出了一种针对网格边界的微分算子，并且将L0范数最小化方法来优化光顺方程。引入新的参量，将非凸的方程转化为可迭代求解的目标方程，并获得了较好的光顺效果。经过实际的测试，本文采用的L0光顺算法能较好的滤除高斯噪声，并较好地保持三维模型的特征。

【关键词】网格光顺；L0范数；微分算子；迭代优化

1.引言

在实践中，很多信号都是可压缩的，可以用稀疏信号来近似表示。L0范数可以非常方便的计算信号的稀疏程度，因此，L0范数广泛用于压缩感知，模式识别和图像处理领域。给定一个输入信号y和原始信号x，且信号x是稀疏可压缩的。因此，可以采用下述方式进行优化：

其中：

且。

其中，若假如。

由于目标方程是NP-难的，因此很难直接求解得到。需要采用组合数学方法进行稀疏近似。近年来，求L0范数最小化方法一般有几种方式，即凸松弛方法（Convex relaxation）[1]，非凸优化方法（Nonconvex optimization）[2]，贝叶斯方法（Bayesian framework）[3]，贪婪算法[4]（即正交匹配追踪和迭代算法）和单匹配算法[5]（Brute Force算法）。其中，贝叶斯方法和非凸优化方法还未有完备的理论框架；Brute-Force算法仅能针对一小部分问题；凸松弛方式和贪婪算法适合计算机迭代计算，可以获得更高的效率。相比较而言，凸松弛方法能获得更为精确的近似结果，但算法实现更为复杂。而贪婪算法近似精度并不是太高。

本文主要研究L0范数最小化在网格光顺算法中的应用。利用三维网格模型的定点和边的拓扑关系，将方程表示成为相互独立的参数表示。分别求解参数最小化并进行迭代以此获得一个精度可控的近似解，以此对模型表面进行光顺处理。

2.网格光顺的表达形式

2.1 相关工作

一般而言，网格光顺算法包含两方面：网格光顺和平滑。在抽象意义上，网格光顺针对的是三维网格光顺方程的处理。而网格光顺处理主要用来消除光顺方程中的高频噪声。在大多数情况下，表征的是网格定点的位置的坐标。由于该坐标可能受到噪声污染，因此需要将输入数据分解，其中为噪声，为顶点的原始坐标。然而，去除噪声和保持几何细节是相互矛盾的。因此，需要加以特殊处理，否则明显细节就会在光顺过程中模糊。

假设给定一个三角剖分流行M及其顶点。对流行曲面进行光顺时，假设输出网格模型顶点和输出网格顶点。需要保证的是输入输出在形式上是匹配的，即：

（1）

在图像处理中，为获得一种清晰的图像边缘，可以通过限制图像边缘梯度非零的个数，即像素点的范数[6]。在进行网格光顺处理时，也可以采用类似的思想，即构建一个边界算子对网格化的边界进行光顺。为保证曲面在翻转和平移之后曲面的高阶微分特性（Frenet标架）不受影响，需要在优化目标函数时使用二阶以上的微分算子。在数字几何理论中，拉普拉斯算子[7]可以很好的满足该项要求，然而基于拉普拉斯算子的滤波器为各向同性的，并不能很好的保持细节同时光顺曲面表面。下文构建了一类边界微分算子，可以很好的满足实际需要。

2.2 边界微分算子

在网格光顺算法中，网格化模型表面的光顺特性仅和曲面坐标点的拓扑特性有光。因此需要考虑边界微分算子也仅和曲面坐标点的相对位置的关系。因此，假定边界微分算子用顶点表示。考虑重心坐标系（Baryc-entric Coordinates）的求解方法[8]，三角网格中的任何一点的位置都可以使用三角定点线性得到。重心坐标系需要满足以下几个条件：

（2）

利用上述限制条件来构建离散微分算子。应用曲面论中散度定理可以得到：对一个封闭形状的外面法线进行积分，其结果为零。可以考虑将外法线向量设置为新的权重因子图1左侧表示一个中心定点邻接的单个三角网格的外面发线向量。由于该向量作为权重因子为矢量，且向量长度等于对应的三角网格边的长度。因此需要修改条件2，得到：

（3）

并且有：

（4）

可以验证满足条件3。将这种构建方式应用到网格边界上，见图1右侧。可以得到边界微分算子：

（5）

因此，可以构筑目标函数：

（6）

图1

3.算子优化

目标方程（7）求解时，仅有一个方程并且有两个参数，不能获得准确结果。此处采用一种特殊的迭代优化近似方法来求解目标方程[9]。引入辅助参量δ，则目标函数可以修改为：

（7）

此处R（D）表示局部微分算子矩阵，矩阵第i行对应第i条边的微分算子。

首先固定p*优化，得到方程：

（8）

后将求得的δ带入目标方程，并优化p*，得到方程：

（9）

整个算法流程如下：

图2

算法中，β用来自动控制算法（6）和算法（7）的近似程度，当β足够大时，方程（7）就无限趋近与方程（6）。因此在实际处理中，首先设置β的初始值设置为接近于零，使得方程（6）和方程（7）的近似程度很差，在循环过程中不断增大β的值，使得两个表达式越来越近似。设定阈值，当β大于阈值时循环中止。算法中μ用于控制算法的速度。增大μ的值，则算法的循环速度相应增加。同时会保持更为细致的特征。

4.光顺结果

在结果验证时，采用Stanford Bunny模型（包含34834个点，104288条边界以及69451个三角网格）进行验证。图2（a）为原始的模型，对（a）模型中的每个顶点的法向添加高斯噪声的效果如（b）。通过对（b）进行拉普拉斯光顺后获得的效果后为（c），而采用本文的光顺算法，获得的效果为图（d）。通过对比两种光顺算法，本文采用的离散微分边界算子可以较好的对三维模型进行光顺去噪并获得较好的效果。

参考文献

[1]Chen S S，Donoho D L，Saunders M A.Atomic decom-position by basis pursuit[J].SIAM Rev，2001，43（1）：1129-159.

[2]Mallat S，Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transaction.Signal Processing.1993，41 （12）：3397-3415.

[3]Wipf D，Bao B.Sparse Bayesian Learning for Basis Selections[J].IEEE Transaction on Signal process.2004， 52（8）：2153-2164.

[4]Chartrand R.Exact reconstruction of sparse signal via nonconvex minimization[J].IEEE Transaction on signal process.2007，14（10）：707-710.

[5]Miller A J.Subset Selections in Rogression 2nd[M].London，UK：Chapman and Hall，2002.

[6]Xu L，Lu C，Xu Y，Jia J.Image smoothing via L0 gradient minimization[J].ACM Transactions on Computer Graphics，2011，10（3）：252-265.

[7]Taubin G.A signal processing approach to fair surface design[J].ACM SIGGRAPH，1995，351-358.

[8]Floater M S，Hormann K，Kos G.A general construction of barycentric coordinates over convex polygons[J].Advances in Computer.2006，Math 24：311-331.

[9]Wang Z，Bovik A C，Sheikh H R，Simoncelli E P.Image quality assessment：from error visibility to structural similarity[J].IEEE Traction on Image processing，2004，13（4）：600-612.