郭趙陽, 李水艷

(河海大學(xué) 理學(xué)院, 江蘇 南京 211100)

0 引言

曲線重構(gòu)作為計算機輔助圖形學(xué)應(yīng)用中的核心技術(shù),在虛擬視覺、場景建模、目標識別、工業(yè)設(shè)計與制造等領(lǐng)域發(fā)揮著極其重要的作用.近年來,激光掃描技術(shù)的快速發(fā)展,使人們可以快速地獲取圖形邊界的散亂點云數(shù)據(jù)[1].基于采樣點,通過建立模型可以反求出目標圖形輪廓,這是對圖形進行計算、分析和繪制的重要依據(jù),極大地促進了計算機圖形學(xué)領(lǐng)域中逆向工程問題的解決.實際上,獲得的數(shù)據(jù)往往分布不均勻、數(shù)量不足且含有噪聲,目標曲線又普遍存在許多細節(jié)特征,而當前技術(shù)處理過程中往往會模糊特征,甚至放大噪聲樣本,這嚴重影響了重構(gòu)曲線的實用程度,因此受到了眾多專家學(xué)者的廣泛關(guān)注.

曲線重構(gòu)問題的研究已取得了一定進展.Hoppe H等[2]對于帶符號的距離函數(shù)進行了局部估計,對不規(guī)則離散點集邊界卻無法自動地進行處理.劉斌等[3]運用移動最小二乘法做細化處理，得到稀疏的有序點云,再采用B樣條函數(shù)進行重構(gòu)，此方法計算效率較高,但重構(gòu)出的曲線不能較好地反映尖銳的特征部位.Ji H等[4]提出運用簡單的平移不變空間,結(jié)合小波變換進行給定數(shù)據(jù)點的擬合,不過這種方法只能對特定的采樣點進行重構(gòu),而對一般的散亂點集卻沒有普適的模型,因此有著較大的局限性.隨后,由于Cai J F等[5]嚴格地建立了基于小波的圖像恢復(fù)模型與變分模型之間的聯(lián)系,給散亂點重構(gòu)問題帶來了新的思路.Dong B等[6]初步建立了這種基于小波框架的變分模型,根據(jù)緊小波框架的多層次性,不同的差分算子可以自適應(yīng)地應(yīng)用到圖形的幾何結(jié)構(gòu)中,但是當采樣點數(shù)量較少時,重構(gòu)出的特征區(qū)域準確度不高,重構(gòu)結(jié)果也不夠符合人類視覺原理.最近,朱云云等[7]提出對Heaviside函數(shù)[8,9]進行改進,使得初始水平集更加收斂于目標輪廓,該算法計算量較大,計算效率低.

文中采用基于小波框架方法的散亂點曲線重構(gòu)方法,增加了去噪的思想[10],使其圖形邊緣更加清晰.去噪后的圖像用小波緊框架對微分算子進行標準有限差分離散化,模型使用交替方向乘子法(ADMM算法)[11-13]進行求解,最終得到重構(gòu)結(jié)果的隱式表示.本文提出的重構(gòu)方法有效地降低了噪聲對重構(gòu)的影響,又使所得的曲線輪廓更接近真實圖形.Matlab模擬實驗表明：存在某些高斯噪音的情況下,該方法能夠有效地重構(gòu)散亂點,并保留大量細節(jié)特征.

1 背景知識

1.1 小波緊框架

可數(shù)集X?L2(R)被稱為L2(R)的緊框架,如果

其中〈·,·〉是L2(R)中的內(nèi)積.

對于給定的

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

由Ψ生成的小波系統(tǒng)

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

是L2(R)的緊框架時,則X(Ψ)被稱為緊小波框架,其中

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

在離散設(shè)置中,離散圖像u是s維數(shù)組.使用W表示快速緊框架分解,并使用WT表示快速重建.由酉擴張原理[14]WTW=I,對于任意圖像u都有

WTWu=u.

進一步表示u的L級框架分解

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

I表示所有小波帶的索引集.更多關(guān)于框架變換離散算法的細節(jié)可以在文獻[15,16]中找到.

1.2 水平集方法

在圖形數(shù)據(jù)處理的研究中,水平集演化方法有著重要的應(yīng)用.

設(shè)u:A→R,A?Rn.對于常數(shù)c,集合{x∈A|u(x)=c}稱為u的?水平集.若A是二維的,一般來說它是一條曲線.

X=(x1,x2,…,xn)?R2是未知曲線S上的采樣點集,S*是經(jīng)過重構(gòu)得到的曲線.根據(jù)采樣點集X找到近似于S的S*,需要將函數(shù)與給定的曲線相關(guān)聯(lián).將S*隱式地定義為u的水平集,即S*∶={x:u(x)=0}.然后最小化基于微分算子的變分模型,重構(gòu)出零水平集近似于未知曲線的u.

2 算法模型

2.1 L0范數(shù)最小化去噪

L0范數(shù)用來度量向量中非零元素的個數(shù),即

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

其中x=(x1,x2,…,xn),#是計數(shù)算子.

使用L0范數(shù)確定L層小波框架分解的系數(shù),可以保留和增強所有突出邊緣(包括主要和次要細節(jié)),并去除低振幅結(jié)構(gòu)(噪聲)[17].通過Fast Marching方法[18],利用散亂點與距其最近的網(wǎng)格點的距離生成水平集函數(shù),由于實際操作時采集的散亂點一般都含有噪聲,所以此時的邊界并不清晰,會干擾重構(gòu)效果.

因此,本文采用基于小波框架的L0范數(shù)最小化方法來進行去噪處理,得到新的水平集函數(shù),其目的是為了突出邊緣并且降低噪聲.去噪模型為

在上式中，d為Fast Marching方法生成的初始水平集函數(shù).根據(jù)平均雙增廣拉格朗日(MDAL)算法,此優(yōu)化模型可以轉(zhuǎn)化為

2.2 基于小波框架的CV重構(gòu)模型

與其他圖像問題的變分模型類似,定義一個用于重建的一般變分模型：

其中V是凸集,D:={Dj:1≤|j|≤s}是一個s階微分算子,H(u,f)是光滑凸函數(shù),f是由散亂點集(如圖1(a)所示)獲得的給定函數(shù),即初始的近似邊界,如圖1(b)所示,通常稱其為掩膜[19],且定義如下范數(shù)

vj是預(yù)先選定的與距離函數(shù)相關(guān)的權(quán)重,距離函數(shù)定義如下:

Ω是根據(jù)圖像大小生成的網(wǎng)格點集.

在連續(xù)情況下,

而在離散的情況下,

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

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

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

由于采集到的散亂點是離散數(shù)據(jù),且φ(x)也是離散的,因此需要進行離散化.采用小波框架來代替微分算子,利用其多分辨率結(jié)構(gòu),在給定圖像的不同區(qū)域自適應(yīng)地選擇合適的微分算子,比標準離散化方法更具有優(yōu)勢.此時優(yōu)化問題將變成

其中

根據(jù)ADMM算法,該問題相當于求解:

將基于小波框架的去噪和重構(gòu)模型相結(jié)合,最終算法流程如下:

步驟1輸入散亂點集X,由距離函數(shù)φ(x)生成網(wǎng)格點集Ω上的初始水平集函數(shù)d.

步驟2輸入d,設(shè)定

(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輸入η,設(shè)定e0=c0=0,f=η-ε,其中ε是給定參數(shù),令r=2f-1.

(i)更新u

(ii)更新e

(iii)更新c

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

3 數(shù)值實驗及比較

為對本研究提出的基于小波框架的散亂點隱式曲線重構(gòu)算法的可行性和有效性進行驗證,調(diào)整各參數(shù)對圖像進行了Matlab仿真模擬.在實際測量環(huán)境下,未必能采集到大量散亂點,因此在其他條件相同時,用盡可能少的散亂點來進行重構(gòu).本小節(jié)從原始點集中取部分點進行數(shù)值實驗:"star"中隨機選取134個點, "leaf "中隨機選取252個點, "horse"中隨機選取567個點.由于散亂點在采集的過程中經(jīng)?；煊幸欢ǔ潭鹊脑胍?為了更接近真實情形,本節(jié)實驗在采樣點集的基礎(chǔ)上增加了均值為0,方差為0.2的高斯白噪聲.

由距離函數(shù)生成的初始水平集函數(shù)圖像如圖2(a)所示,其邊界模糊,對比度較低,將對下一步處理產(chǎn)生較大影響.而經(jīng)過L0范數(shù)最小化去噪后,水平集函數(shù)圖像邊界分明,細節(jié)處更有辨識度,有助于下一步的重構(gòu),如圖2(b)所示.

(a)初始水平集函數(shù)圖像 (b)去噪后的圖像

去噪處理后,利用新的清晰圖像進行隱式曲線重構(gòu).將其分別與結(jié)合TV的方法[20]、D.S方法[6]進行比較,其結(jié)果如圖3～6所示.

(a)TV方法重構(gòu)star

(a)D.S方法重構(gòu)star

(a)本文方法重構(gòu)star

由圖3～6可知,“star”在其他模型下,尖角部分重構(gòu)效果較差,出現(xiàn)彎曲的狀況且與實際形狀有較大偏離,而用本文方法所得的曲線整體較為平滑,尖銳部分的重構(gòu)也較為平直,更加貼合實際;“l(fā)eaf”中,對于復(fù)雜的凹陷部分,其他模型的重構(gòu)效果不盡如人意, 相比之下本文方法效果良好,更為準確；對于“horse”這組實驗,其他兩組模型的結(jié)果中馬蹄處都出現(xiàn)了斷裂,然而本文方法較為流暢地連接了這一區(qū)域,且非特征區(qū)域的重構(gòu)曲線較為平滑,也更加接近真實圖形.

為了對結(jié)果進行富有統(tǒng)計學(xué)意義的對比,本文選取有代表性的點集horse，采用MSE(Mean Square Error)評價方法來定量評估重構(gòu)結(jié)果,該方法將計算重構(gòu)曲線與原始點集的接近程度,定義如下:

其中，d1為原始點集經(jīng)Fast Marching生成的水平集,d2為本文算法輸出的水平集,n代表網(wǎng)格點個數(shù), MSE越小,說明重構(gòu)所得的曲線越接近標準.MSE和運行時長的具體數(shù)值如表1所示.

表1 MSE及運行時長比較

由表1可知,本文算法兼顧計算效率與重構(gòu)精度,相比于其他兩種方法,MSE值和運行時長都更小,即重構(gòu)曲線更加貼合原始點集,且節(jié)省了大量時間.

重構(gòu)曲線對比和數(shù)據(jù)評估結(jié)果說明,在散亂點個數(shù)和噪音都相同的情況下,本算法能夠較為快速地重構(gòu)曲線,不僅可以清晰地刻畫出尖銳、凹陷等細節(jié)特征,更加接近實際情況,整體曲線也更加平滑順暢,偏差程度小.

4 結(jié)論

本文基于小波框架方法,建立圖像去噪和重構(gòu)的變分模型,并通過Matlab仿真模擬,與其他重構(gòu)方法進行比較.數(shù)值實驗表明,該方法能夠降低噪聲的干擾,較精確地重構(gòu)散亂點,忠實于原始圖形,因此在工程應(yīng)用中,具有一定推廣意義.接下來的工作將進一步改進算法,使其能夠拓展到三維空間,進行散亂點的曲面重構(gòu).