代曦,，李騫,，顧大權(quán)，黃巖

　　(解放軍理工大學(xué) 氣象海洋學(xué)院,，江蘇 南京 211101)

　　摘要：等值線編輯是對(duì)各形勢(shì)場(chǎng)等值線自動(dòng)化分析結(jié)果的人工修正,，是對(duì)提取準(zhǔn)確等值線結(jié)果的必要補(bǔ)充。針對(duì)已有等值線交互編輯方法難以滿足不相交約束,、操作復(fù)雜等問(wèn)題,，提出一種基于拉普拉斯坐標(biāo)系的等值線交互編輯方法。實(shí)驗(yàn)結(jié)果表明,，編輯結(jié)果有效保持了原有等值線的形狀拓?fù)?，且人工操作更少，可滿足業(yè)務(wù)應(yīng)用中等值線交互編輯需求,。

　　關(guān)鍵詞：等值線; 三角剖分,；拉普拉斯

0引言

　　*基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目資助（41305138，41174164）等值線是將數(shù)據(jù)某一數(shù)量指標(biāo)值相等的各點(diǎn)連成的平滑曲線,，它具有連續(xù)性,、不相交等特點(diǎn)。現(xiàn)有等值線分析主要分為手工分析和軟件自動(dòng)分析兩種,，其中手工分析相對(duì)復(fù)雜,、耗時(shí)較長(zhǎng)，但此方法優(yōu)勢(shì)在于可融合預(yù)報(bào)人員經(jīng)驗(yàn)與其氣象要素信息,；自動(dòng)分析采用網(wǎng)格追蹤等方法對(duì)格點(diǎn)數(shù)據(jù)進(jìn)行跟蹤,，分析速度快，但與手工分析結(jié)果存在一定差距,，不能很好地滿足業(yè)務(wù)需求,。當(dāng)前大多數(shù)可視化及氣象分析軟件已實(shí)現(xiàn)等值線的自動(dòng)分析功能，SURFER,、Micaps、Grads,、MATLAB,、ARCGIS、Tecplot等均有等值線分析模塊［12］,。上述系統(tǒng)的主要問(wèn)題表現(xiàn)在：訂正結(jié)果不能滿足等值線網(wǎng)格局部的拓?fù)浣Y(jié)構(gòu)需求,；修正等值線時(shí)容易出現(xiàn)等值線相交的情況；只能實(shí)現(xiàn)對(duì)單條等值線進(jìn)行修改,，如對(duì)多條線進(jìn)行修改,，需要反復(fù)操作，效率低,。

　　針對(duì)上述問(wèn)題,，本文提出了一種基于拓?fù)浣Y(jié)構(gòu)的等值線修正方法,。首先對(duì)已有的等值線數(shù)據(jù)進(jìn)行三角剖分，依據(jù)剖分結(jié)果識(shí)別等值線間的拓?fù)潢P(guān)系,，并對(duì)剖分結(jié)果建立Laplacian坐標(biāo)系［34］,。然后由用戶交互輸入修改意圖，在交互修改過(guò)程中通過(guò)Laplacian坐標(biāo)對(duì)等值線修改移動(dòng)部分進(jìn)行約束,，同時(shí)通過(guò)笛卡爾坐標(biāo)約束固定點(diǎn),，通過(guò)最小二乘法求解移動(dòng)點(diǎn)和固定點(diǎn)雙重約束下的線性系統(tǒng)，從而重新修改移動(dòng)點(diǎn)［56］,。通過(guò)上述方法,，可以實(shí)現(xiàn)在保持等值線集合拓?fù)浣Y(jié)構(gòu)的前提下對(duì)等值線進(jìn)行修改。

　　本文提出方法的流程如圖1所示,?！　?/p>

1三角剖分

　　三角剖分是計(jì)算機(jī)輔助幾何設(shè)計(jì)、幾何造型及計(jì)算機(jī)圖形學(xué)中研究的重要內(nèi)容之一,。本文將等值線集合進(jìn)行離散化并對(duì)得到的離散點(diǎn)進(jìn)行三角剖分得到三角網(wǎng)格,。目前，三角剖分可以通過(guò)動(dòng)態(tài)規(guī)劃［7］和德勞內(nèi)三角剖分算法［8］實(shí)現(xiàn),，但動(dòng)態(tài)規(guī)劃算法主要是通過(guò)計(jì)算最短邊來(lái)排除病態(tài)的三角網(wǎng)格,。而在等值線族中，由于等值線彎曲變化,，部分等值線在某一個(gè)區(qū)域內(nèi)較為集中,，通過(guò)動(dòng)態(tài)規(guī)劃算法來(lái)實(shí)現(xiàn)三角剖分可能丟失等值線間的拓?fù)潢P(guān)系。因此,，本文采用德勞內(nèi)三角剖分算法,。其主要流程如圖2所示。

　　首先建立凸殼,，包含了所有的離散點(diǎn),，然后向其中插入一點(diǎn)，該點(diǎn)與包含它的三角形三個(gè)頂點(diǎn)相連,，形成三個(gè)新的三角形,，然后逐個(gè)對(duì)它們進(jìn)行空外接圓檢測(cè)，同時(shí)用Lawson設(shè)計(jì)的局部?jī)?yōu)化過(guò)程LOP進(jìn)行優(yōu)化,，即通過(guò)交換對(duì)角線的方法來(lái)保證所形成的是Delaunay三角網(wǎng),。

2拓?fù)浣Y(jié)構(gòu)識(shí)別與Laplacian坐標(biāo)系建立

　　Laplacian坐標(biāo)表示方法又稱為微分坐標(biāo)方法或δ坐標(biāo)［9］，或局部平均曲率法線,。在網(wǎng)格頂點(diǎn)處應(yīng)用Laplacian算子,，可用于表征局部曲面的幾何特征。建立拓?fù)浣Y(jié)構(gòu)后，將笛卡爾坐標(biāo)系轉(zhuǎn)換為差分的拉普拉斯坐標(biāo)系,。主要針對(duì)修改范圍內(nèi)的點(diǎn),，為下一步能量方程求解提供依據(jù)。

　　根據(jù)設(shè)定的修改范圍,，從用戶選中的坐標(biāo)點(diǎn)出發(fā),，廣度搜索出一系列鄰接點(diǎn)，根據(jù)差分坐標(biāo)公式求出每點(diǎn)的δ坐標(biāo),。得到的坐標(biāo)存儲(chǔ)在鏈表中,。本文為了建立拉普拉斯坐標(biāo)系進(jìn)行如下定義：

　　(1)拉普拉斯網(wǎng)格

　　μ表示已知的N個(gè)點(diǎn)組成的三角網(wǎng)格。V表示節(jié)點(diǎn),，E表示邊,，F(xiàn)表示平面。每個(gè)i∈μ表示笛卡爾坐標(biāo)系中的節(jié)點(diǎn)用vi=(xi,yi,zi)表示,。

　　首先通過(guò)中心和與它直接相連的節(jié)點(diǎn)定義差分坐標(biāo)系：

　　其中,，N(i)={j|(i,j)∈E}，表示與i節(jié)點(diǎn)相鄰節(jié)點(diǎn)的個(gè)數(shù),。

　　從絕對(duì)笛卡爾坐標(biāo)系到差分坐標(biāo)系的轉(zhuǎn)換可以表示為一個(gè)矩陣：

　　令D是一個(gè)對(duì)角陣,，Dii=di，矩陣從絕對(duì)坐標(biāo)系轉(zhuǎn)換到關(guān)系坐標(biāo)系：

　　L=I－D－1A（4）

　　定義：

　　Ls=DL=D－A（5）

　　那么,，

　　Lsx=Dδ(x),Lsy=Dδ(y),Lsz=Dδ(z)

　　其中x是n個(gè)向量包含x的絕對(duì)坐標(biāo)的所有頂點(diǎn),。

　　矩陣Ls被稱為拓?fù)淅绽咕W(wǎng)格。圖形表示的拉普拉斯廣泛地應(yīng)用在代數(shù)和圖形學(xué)原理中,，最主要的原因是因?yàn)樗拇鷶?shù)特性能很好地與圖形表示相結(jié)合,。從差分幾何角度來(lái)看，δ坐標(biāo)系被視作離散化的連續(xù)拉普拉斯貝爾特拉米算子,。

　　(2)三維仿射變換

　　常見(jiàn)的三維變換包括平移變換,、旋轉(zhuǎn)變換、縮放變換,、反射變換和錯(cuò)切變換,。若取齊次坐標(biāo)來(lái)表示三維空間中的點(diǎn)，三維變換可表示為4×4的變換矩陣,。

　　記(Tx,Ty,Tz)為平移向量,， 繞x軸旋轉(zhuǎn)θ角的旋轉(zhuǎn)變換矩陣為：

　　同樣可以獲得繞y軸、z軸旋轉(zhuǎn)的變換矩陣,?？s放矩陣為：

　　其中,，(Sx,Sy,Sz)為縮放因子,。

3能量方程的求解

　　通過(guò)網(wǎng)格模型的笛卡爾坐標(biāo)構(gòu)造其Laplacian坐標(biāo)。由于變換矩陣L（或Ls）為奇異矩陣［10］，不存在可逆矩陣,，因此不能使用V′=L－1δ重建模型,。

　　由于Laplacian坐標(biāo)存在平移不變性，因此變換矩陣L的秩為n-1,。為了能夠唯一地重構(gòu)笛卡爾坐標(biāo)系中的網(wǎng)格模型,，需要求解一個(gè)滿秩的線性方程組，因此需要指定更多的變形特征頂點(diǎn)的笛卡爾坐標(biāo)為約束條件,。令空間中位置已知頂點(diǎn)的索引值集合為C,，有|C|個(gè)位置約束的形式為：

　　V′j=cj,j∈C

　　如果記C={1,2,...,m}，則需要求解的線性方程組表示如下：

　　方程組中的系統(tǒng)矩陣記為L(zhǎng)o,。在本文中,，使用公式作為位置約束條件（或稱為模型約束條件）。權(quán)值ω>0可以用來(lái)調(diào)整位置約束條件的重要性,，每個(gè)約束都應(yīng)該有相應(yīng)的權(quán)值,，可以在Laplacian矩陣上針對(duì)不同行使用不同的權(quán)值。附加的屬性約束條件使線性方程組成為超定方程組,，因此基本上沒(méi)有完全精確的解,，可通過(guò)最小二乘法求解近似解，當(dāng)系統(tǒng)滿秩時(shí)就存在唯一解：

　　式(11)的第一項(xiàng)表示盡可能保持原始網(wǎng)格的Laplacian坐標(biāo)不變,，第二項(xiàng)表示盡可能減少特征頂點(diǎn)處的誤差,。求解值的精確度與現(xiàn)行方程組的約束條件有很大關(guān)系。

　　基于線性邊約束的網(wǎng)格編輯方法在模型重建時(shí),，通過(guò)最小二乘系統(tǒng)求解獲得的模型為近似解,。當(dāng)模型集合細(xì)節(jié)特征較復(fù)雜時(shí)，一次求解不一定能獲得較高質(zhì)量的變形效果,，需要多次迭代求解,，逐漸逼近精確值。

4實(shí)驗(yàn)結(jié)果與分析

　　為了驗(yàn)證方法的可行性,，本文分別使用仿真數(shù)據(jù)和2011年數(shù)據(jù)庫(kù)中選取的4月20日12時(shí)的全球等壓線數(shù)據(jù)進(jìn)行了實(shí)驗(yàn),。仿真數(shù)據(jù)為16條平行線，共510個(gè)采樣點(diǎn),。全球等值線數(shù)據(jù)共有682條等值線,，19 985個(gè)采樣點(diǎn)。

　　圖3仿真數(shù)據(jù)編輯結(jié)果通過(guò)上文提到的兩個(gè)過(guò)程,，用戶交互編輯修改點(diǎn),，使其帶動(dòng)修改范圍內(nèi)的點(diǎn)一起移動(dòng)，從而達(dá)到修改的效果,，實(shí)驗(yàn)結(jié)果如圖3,。其中用戶交互修改的點(diǎn)只有淺色的點(diǎn),，深色的點(diǎn)均根據(jù)淺色點(diǎn)移動(dòng)而改變位置，從而達(dá)到等值線修改范圍內(nèi)自動(dòng)編輯的要求,。

　　本文對(duì)全球數(shù)據(jù)的局部進(jìn)行編輯實(shí)驗(yàn),，根據(jù)修改范圍不同編輯結(jié)果如圖4。圖4的修改范圍為2個(gè)網(wǎng)格,。

　　從實(shí)驗(yàn)結(jié)果可以看出,，不同的修改范圍得到的數(shù)據(jù)編輯結(jié)果是不同的。最后本文對(duì)全球數(shù)據(jù)進(jìn)行了編輯實(shí)驗(yàn),，如圖5所示,。其中用戶選擇的修改范圍在左下角。

　　實(shí)驗(yàn)結(jié)果證明,，采用本文方法對(duì)等值線數(shù)據(jù)進(jìn)行局部自動(dòng)修正是可行性的,。

參考文獻(xiàn)

　　［1］ 王軟宏. 等值線的自動(dòng)繪制方法及在計(jì)算機(jī)上的實(shí)現(xiàn)［D］.吉林：吉林大學(xué)數(shù)學(xué)研究所,，2003.

　?。?］ 中國(guó)氣象局.MICAPS3.2 用戶使用手冊(cè)［Z］. 2012.

　　［3］ SORKINE O,， LIPMAN Y,， COHENOR D， et al. 2004.Laplacian surface editing［C］. In SGP′04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, ACM, New York, USA:175184.

　?。?］ LIPMAN Y, SORKINE O, COHENOR D, et al. Differential coordinates for interactive mesh editing［C］. In Proceedings of Shape Modeling International (2004), IEEE Computer Society Press：181190.

　?。?］ BOTSCH M, BOMMES D, KOBBELT L. Efficient linear system solvers for mesh processing［J］. IMAMathematics of Surfaces XI, Lecture Notes in Computer Science,2005,3604：6283.

　　［6］ FLOATER M S. Mean value coordinates［J］. Computer Aided Geometric Design, 2003,20(1):1927.

　?。?］ 劉晶, 張九龍, 李曄, 等. 基于圖像不變特征與三角剖分的水印算法［J］. 西安理工大學(xué)學(xué)報(bào), 2009, 25(2): 227230.

　?。?］ 余杰, 呂品, 鄭昌文. Delaunay 三角網(wǎng)構(gòu)建方法比較研究［J］. 中國(guó)圖象圖形學(xué)報(bào), 2010, 15(8): 11581167.

　　［9］ 許斌,李忠科,宋大虎.基于支持向量機(jī)的 Laplacian 網(wǎng)格曲面孔洞修補(bǔ)算法［J］.計(jì)算機(jī)工程與設(shè)計(jì), 2014, 35(1): 237242.

　?。?0］ 王勇.基于流形學(xué)習(xí)的分類與聚類方法及其應(yīng)用研究［D］.長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué), 2011.