基于拓?fù)浣Y(jié)構(gòu)的等值線修正方法*

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

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

?

基于拓?fù)浣Y(jié)構(gòu)的等值線修正方法*

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

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

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

等值線; 三角剖分；拉普拉斯

引用格式：代曦，李騫，顧大權(quán)，等. 基于拓?fù)浣Y(jié)構(gòu)的等值線修正方法[J].微型機(jī)與應(yīng)用，2016,35(11)：18-21.

0　引言

等值線是將數(shù)據(jù)某一數(shù)量指標(biāo)值相等的各點(diǎn)連成的平滑曲線，它具有連續(xù)性、不相交等特點(diǎn)。現(xiàn)有等值線分析主要分為手工分析和軟件自動(dòng)分析兩種，其中手工分析相對(duì)復(fù)雜、耗時(shí)較長，但此方法優(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)的主要問題表現(xiàn)在：訂正結(jié)果不能滿足等值線網(wǎng)格局部的拓?fù)浣Y(jié)構(gòu)需求；修正等值線時(shí)容易出現(xiàn)等值線相交的情況；只能實(shí)現(xiàn)對(duì)單條等值線進(jìn)行修改，如對(duì)多條線進(jìn)行修改，需要反復(fù)操作，效率低。

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

本文提出方法的流程如圖1所示。

圖1　方法流程圖

1　三角剖分

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

圖2　德勞內(nèi)三角剖分流程

首先建立凸殼，包含了所有的離散點(diǎn)，然后向其中插入一點(diǎn)，該點(diǎn)與包含它的三角形三個(gè)頂點(diǎn)相連，形成三個(gè)新的三角形，然后逐個(gè)對(duì)它們進(jìn)行空外接圓檢測(cè)，同時(shí)用Lawson設(shè)計(jì)的局部優(yōu)化過程LOP進(jìn)行優(yōu)化，即通過交換對(duì)角線的方法來保證所形成的是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)格

μ=(V,E,F)

(1)

μ表示已知的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)表示。

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

(2)

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

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

(3)

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

L=I-D-1A

(4)

定義：

Ls=DL=D-A

(5)

那么，

(6)

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é)合。從差分幾何角度來看，δ坐標(biāo)系被視作離散化的連續(xù)拉普拉斯貝爾特拉米算子。

(7)

(2)三維仿射變換

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

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

(8)

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

(9)

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

3　能量方程的求解

通過網(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è)位置約束的形式為：

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

(10)

(11)

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

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

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

為了驗(yàn)證方法的可行性，本文分別使用仿真數(shù)據(jù)和2011年數(shù)據(jù)庫中選取的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é)果

通過上文提到的兩個(gè)過程，用戶交互編輯修改點(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)格。

圖4　局部數(shù)據(jù)編輯結(jié)果

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

圖5　全球數(shù)據(jù)編輯結(jié)果

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

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

[2] 中國氣象局.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.

[4] 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.

[5] 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.

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

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

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

[10] 王勇.基于流形學(xué)習(xí)的分類與聚類方法及其應(yīng)用研究[D].長沙：國防科學(xué)技術(shù)大學(xué), 2011.

The correcting method of isoline based on topology structure

Dai Xi, Li Qian, Gu Daquan，Huang Yan

(Institute of Marine Meteorological, PLAUST, Nanjing 211101, China)

The edit of curves is an essential procedure to modify the automatic extraction isoline manually, and it’s a necessary supplement to get more accurate isoline results. The existed edit methods have many problems, such as couldn’t satisfy the no crossing principle, and complicate to manipulate. To solve these problems, this paper proposes a new alternating edit method of curves based on Laplacian coordinate system. The experiment results show that the edited results has efficaciously maintained the topology structure of original isoline, and the manual manipulate is more simple. Hence, the proposed correcting method could satisfy alternating edit requirement of professional application.

isoline; triangulation; Laplacian

國家自然科學(xué)基金項(xiàng)目資助(41305138，41174164)

TP399

A

10.19358/j.issn.1674- 7720.2016.11.006

2016-03-07)

代曦(1991-)，男，碩士研究生，主要研究方向：計(jì)算機(jī)圖形學(xué)。

李騫(1980-)，男，博士，講師，主要研究方向：視頻處理，模式識(shí)別，科學(xué)計(jì)算可視化。

顧大權(quán)(1959-)，男，碩士生導(dǎo)師，教授，主要研究方向：可視化技術(shù)，人工智能。