平面隱式曲線的Hermite插值逼近

魏 利，趙晶潔，黃慧敏

?

平面隱式曲線的Hermite插值逼近

魏 利，趙晶潔，黃慧敏

(南京師范大學(xué)教育信息工程研究所，江蘇 南京210097)

隱式曲線在醫(yī)學(xué)圖像處理、地理信息系統(tǒng)、數(shù)值場(chǎng)可視化等領(lǐng)域中有著重要應(yīng)用。在分析點(diǎn)采樣和曲線逼近理論的基礎(chǔ)上，提出一種運(yùn)用Hermite插值方法逼近平面隱式曲線的算法。首先將曲線繪制區(qū)域網(wǎng)格化，在網(wǎng)格單元各邊中通過線性插值計(jì)算曲線采樣點(diǎn)；其次通過計(jì)算采樣點(diǎn)精簡前后構(gòu)成的曲線段之間產(chǎn)生的誤差優(yōu)化采樣點(diǎn)；最后通過Hermite插值法逼近隱函數(shù)曲線。實(shí)驗(yàn)表明，通過該算法繪制出的曲線在采樣點(diǎn)數(shù)量較少的情況下，其光滑度和準(zhǔn)確度仍較高。

圖形繪制；隱式曲線；Hermite插值；采樣點(diǎn)優(yōu)化

隱式曲線是計(jì)算機(jī)輔助幾何設(shè)計(jì)和計(jì)算機(jī)圖形學(xué)的重要研究內(nèi)容[1-2]，因其可描述平面上任意不規(guī)則的形狀，且在離散采樣曲線重建過程中，具有自動(dòng)過濾數(shù)據(jù)噪聲的優(yōu)點(diǎn)，在生物學(xué)[3-4]、氣象學(xué)[5]、地理學(xué)[6]、石油勘探及物探[7]等領(lǐng)域有著廣泛且重要的應(yīng)用。

目前，國內(nèi)外學(xué)者主要采用連續(xù)跟蹤法[2]和細(xì)分法[8]繪制隱式曲線。連續(xù)跟蹤法是從曲線上某一點(diǎn)開始借助一定的規(guī)則連續(xù)跟蹤繪制曲線，如TN法[9]、正負(fù)法[10-11]和短線截交法[12]等。這類方法原理簡單，容易實(shí)現(xiàn)，但其難點(diǎn)在于很難選擇一個(gè)優(yōu)化的起始點(diǎn)。細(xì)分法是一種常用的隱式曲線繪制方法[13]，該方法首先需要估計(jì)其繪制區(qū)域，然后排除無關(guān)區(qū)域，并對(duì)有關(guān)區(qū)域不斷細(xì)分，直到該區(qū)域達(dá)到一個(gè)像素大小為止，再將其繪制出來。該方法雖能繪制出曲線，但是由于該方法無法優(yōu)化采樣點(diǎn)的分布[14]，因此會(huì)生成“胖”曲線[15]。文獻(xiàn)[15]對(duì)細(xì)分法進(jìn)行了改進(jìn)，并將自動(dòng)微分技術(shù)與泰勒方法引入其中，該方法可繪制任意復(fù)雜的隱式曲線，但其效率(CPU占用時(shí)間)有待提升。

繪制平面隱式曲線的方法雖各有不同，但其包含了相同的過程，即獲取采樣點(diǎn)和曲線折線化。本文參照上述過程并結(jié)合已有研究，提出一種新的隱式曲線繪制方法，借鑒移動(dòng)立方體(marching cubes, MC)方法[16]對(duì)繪制區(qū)域網(wǎng)格化獲取采樣點(diǎn)；為減少數(shù)據(jù)量，提高曲線繪制質(zhì)量和逼近精度，對(duì)采樣點(diǎn)數(shù)量進(jìn)行了優(yōu)化處理；曲線折線化則通過分段Hermite插值實(shí)現(xiàn)。實(shí)驗(yàn)表明，相比其他隱式曲線繪制方法，本文方法既能減少數(shù)據(jù)量，同時(shí)還可保證曲線準(zhǔn)確性和光滑度。

1 Hermite插值

分段三次Hermite插值是函數(shù)擬合和插值的基本方法[17]。對(duì)于給定+1個(gè)插值點(diǎn)0<1…<x和這些插值點(diǎn)上關(guān)于函數(shù)()的函數(shù)值0，1，2，…，y及導(dǎo)數(shù)值0，1，…，m，對(duì)任意=0，1，2，…，在區(qū)間[x，x+1]構(gòu)造次數(shù)不大于3的多項(xiàng)式的分段插值，且有(x)=y和′(x)=m，那么函數(shù)()即為插值點(diǎn)(0,0)，(1,1)，…，(x,y)的分段三次Hermite插值函數(shù)。

若已知兩點(diǎn)01及其切向矢量0′、1′，即可根據(jù)兩點(diǎn)構(gòu)成的三次Hermite參數(shù)方程求出插值點(diǎn)進(jìn)而描述點(diǎn)01間的曲線。

為推導(dǎo)出三次Hermite參數(shù)方程[18]，首先假設(shè)平面上一條三次參數(shù)曲線表達(dá)式為

根據(jù)式(1)，設(shè)該曲線的矢量表達(dá)式為

其一階求導(dǎo)式為

最后將式(4)中的各系數(shù)值帶入式(2)中即可得三次Hermite插值參數(shù)函數(shù)一般式

本算法中即采用三次Hermite插值參數(shù)函數(shù)即式(5)計(jì)算采樣點(diǎn)間的插值點(diǎn)進(jìn)而逼近隱式曲線。

2 算法梗概

本文平面隱式曲線Hermite插值逼近算法的處理過程分為3步：網(wǎng)格化獲取采樣點(diǎn)、優(yōu)化采樣點(diǎn)和曲線折線化。

(1) 網(wǎng)格化獲取采樣點(diǎn)。首先將曲線繪制區(qū)域網(wǎng)格化，再在網(wǎng)格單元各邊中通過線性插值計(jì)算曲線采樣點(diǎn)。

(2) 優(yōu)化采樣點(diǎn)。為減少數(shù)據(jù)量，提高繪制質(zhì)量和逼近精度，本算法對(duì)采樣點(diǎn)進(jìn)行了優(yōu)化處理，優(yōu)化前判斷采樣點(diǎn)能否被精簡，即計(jì)算采樣點(diǎn)精簡前后構(gòu)成的曲線之間產(chǎn)生的誤差是否符合優(yōu)化要求，若符合優(yōu)化要求則其可被精簡。

(3) 曲線折線化。對(duì)于優(yōu)化后的采樣點(diǎn)通過Hermite插值逼近隱函數(shù)曲線。

3 算法步驟

3.1 網(wǎng)格化獲取采樣點(diǎn)

本算法借鑒MC方法，通過網(wǎng)格離散化后獲取曲線采樣點(diǎn)。MC算法是一種經(jīng)典的基于體元構(gòu)造等值面的算法，其主要思想是將三維構(gòu)造空間劃分為一定數(shù)量的體元，再將體元的每個(gè)頂點(diǎn)進(jìn)行分類標(biāo)記，然后對(duì)頂點(diǎn)標(biāo)記互異的邊通過插值法求出采樣點(diǎn)，最后用三角面片逼近等值面。該方法也可降維應(yīng)用于二維等值線的繪制(稱其為二維MC算法)，具體內(nèi)容為將繪制區(qū)域網(wǎng)格離散化，并對(duì)每個(gè)網(wǎng)格單元頂點(diǎn)分類標(biāo)記，然后對(duì)頂點(diǎn)標(biāo)記互異的邊通過插值法求出采樣點(diǎn)，最后在對(duì)采樣點(diǎn)不做任何處理的情況下將其連接起來，從而繪制出曲線。雖然MC算法中采樣點(diǎn)連接存在復(fù)雜的二義性問題，但是該算法原理簡單、容易實(shí)現(xiàn)，因此得到了廣泛的應(yīng)用。

獲取采樣點(diǎn)的思路為：設(shè)隱函數(shù)(,)=0，在平面上均勻地構(gòu)造×個(gè)網(wǎng)格單元，并獲取每個(gè)網(wǎng)格單元頂點(diǎn)的坐標(biāo)及函數(shù)值，若函數(shù)值大于或等于0的頂點(diǎn)標(biāo)記為“+”，小于0則標(biāo)記為“–”。假設(shè)采樣點(diǎn)在網(wǎng)格單元內(nèi)是線性變化，那么可推斷，網(wǎng)格中存在兩端點(diǎn)標(biāo)記分別為“+”和“–”的邊上存在采樣點(diǎn)，便可通過線性插值確定該點(diǎn)。但是算法中可能出現(xiàn)二義性，圖1中的網(wǎng)格單元邊存在采樣點(diǎn)、、、，其連接順序即會(huì)出現(xiàn)圖1中(a)和(b)兩種情況。為解決此問題，本算法首先計(jì)算出每個(gè)網(wǎng)格單元中心點(diǎn)坐標(biāo)、函數(shù)值和標(biāo)記，進(jìn)而在每個(gè)網(wǎng)格單元中構(gòu)造4個(gè)三角形如圖2(a)所示，以Δ012為例，采樣點(diǎn)的情況將會(huì)有圖2(b)~(e) 4種情況(圖中的點(diǎn)1、2為獲取的采樣點(diǎn))，如此便可避開圖1中可能出現(xiàn)的二義性。

圖1 二義性情況

圖2 網(wǎng)格單元及采樣情況

3.2 優(yōu)化采樣點(diǎn)

為減少數(shù)據(jù)量，本算法對(duì)采樣點(diǎn)進(jìn)行了優(yōu)化。判斷采樣點(diǎn)能否被精簡的要求是：采樣點(diǎn)精簡前后構(gòu)成的曲線之間產(chǎn)生的誤差大小。如圖3所示，設(shè)待精簡采樣點(diǎn)、、、、5點(diǎn)連接而成的原始折線段Line，由Hermit插值法計(jì)算出、之間的插值點(diǎn)、、、構(gòu)成的折線段來逼近Line。不難發(fā)現(xiàn)采樣點(diǎn)精簡前后產(chǎn)生的誤差可由圖中陰影部分的面積表示。假設(shè)允許誤差不能超過，若≤，滿足優(yōu)化要求，即可精簡、、3點(diǎn)，反之則不能精簡。那么計(jì)算出陰影面積即成為采樣點(diǎn)優(yōu)化的關(guān)鍵。本算法通過求兩條折線段的交點(diǎn)和計(jì)算多邊形面積兩步完成陰影面積的計(jì)算。

圖3 誤差示例圖

交點(diǎn)計(jì)算方法以圖3中與兩折線段為例，設(shè)其交點(diǎn)為。設(shè)線段、的矢量方程分別為

其中，0、1為定比參數(shù)。假設(shè)兩折線段有交點(diǎn)，聯(lián)立式(6)、(7)可得

計(jì)算可得0、1的解。若0、1有無窮解，則兩線段關(guān)系為平行或重合；若0、1有唯一解，且0、1的值均在(0, 1)，即可判定兩線段有且只有一個(gè)交點(diǎn)，將其代入式(6)或式(7)可求出交點(diǎn)。

誤差面積計(jì)算方法以圖3中多邊形面積為例。其計(jì)算方法為在平面內(nèi)任取一點(diǎn)，如圖4所示，通過三角形向量面積公式計(jì)算出Δ、Δ、Δ的面積，其和的絕對(duì)值為Δ面積，即S=|S+S+S|。依次類推，計(jì)算出圖3中所有多邊形面積之和為=|S+S1+S1|，即為折線段Line精簡前后的誤差。判斷與的大小關(guān)系，即可判斷采樣點(diǎn)能否優(yōu)化。

圖4 多邊形NDP

3.3 曲線折線化

對(duì)于精簡后的采樣點(diǎn)集，分別計(jì)算出各點(diǎn)切向，通過三次Hermite參數(shù)函數(shù)式(5)按點(diǎn)序分段插值逼近隱式曲線，其中插值點(diǎn)數(shù)量根據(jù)實(shí)際曲線光滑度要求進(jìn)行設(shè)置。

4 實(shí)驗(yàn)與數(shù)據(jù)

利用本算法在PC機(jī)上基于Windows平臺(tái)和OpenGL圖形設(shè)備接口及Visual C++6.0實(shí)現(xiàn)了如下隱式函數(shù)曲線的繪制

為方便說明和比較，本文中的曲線均在30×30的網(wǎng)格中獲取采樣點(diǎn)繪制曲線，表1為各曲線在不同允許誤差的情況下采樣點(diǎn)優(yōu)化情況，從表1可知，允許誤差越大，優(yōu)化率越大，優(yōu)化后采樣點(diǎn)個(gè)數(shù)越少；反之允許誤差越小，其優(yōu)化率越小，優(yōu)化后采樣點(diǎn)個(gè)數(shù)越多。同時(shí)結(jié)合曲線繪制結(jié)果可知同一隱函數(shù)曲線隨著允許誤差逐漸增大，曲線光滑度也隨之變化，其中≤10-6和≤10-5情況下，曲線光滑度較為樂觀，而在≤10-3情況下，曲線光滑度較低(圖5)。表1中，可簡單得出結(jié)論曲線優(yōu)化率與其形狀復(fù)雜度存在關(guān)系；從圖6中可看到，四角星中存在切向矢量值變化較大的4個(gè)角的采樣點(diǎn)，即使經(jīng)過優(yōu)化處理之后，本算法也能保留切向矢量值變化較大的點(diǎn)，從而確保了曲線特征的完整性。

因本算法借鑒了MC算法思路獲取采樣點(diǎn)，并與二維MC算法繪制的隱式曲線情況作了對(duì)比，顯示有一定的可比性，能說明本算法中采樣點(diǎn)優(yōu)化情況。通過實(shí)驗(yàn)可發(fā)現(xiàn)，在同等網(wǎng)格數(shù)量30×30條件下，二維MC算法繪制的隱式曲線光滑度和準(zhǔn)確度與本算法允許誤差≤10-6的情況相似，對(duì)比這兩種情況下繪制隱式曲線的采樣點(diǎn)數(shù)量更有說服力。從圖7中可看出，本算法若要達(dá)到與MC算法同等的光滑度，對(duì)于較簡單的曲線(如圓、圓角矩形等)本算法可通過約其采樣點(diǎn)數(shù)量的1/4即可實(shí)現(xiàn)，對(duì)于特征較多的曲線(如心形曲線、四角星曲線、花形曲線等)，本算法可通過約其采樣點(diǎn)數(shù)量的1/2即可實(shí)現(xiàn)。

表1 不同允許誤差m情況下采樣點(diǎn)個(gè)數(shù)及壓縮率比較

注：A表示優(yōu)化后數(shù)據(jù)點(diǎn)個(gè)數(shù)，B表示優(yōu)化率

圖5 圓角矩形(式(10))曲線在不同允許誤差下的繪制情況

圖6 允許誤差為m≤10-5情況下各隱式曲線繪制情況

圖7 二維MC算法與本文算法允許誤差為m≤10-6情況下采樣點(diǎn)數(shù)量對(duì)比圖

5 結(jié)束語

本文給出的平面隱式曲線的Hermite插值逼近算法，成功地實(shí)現(xiàn)了隱式曲線的繪制。從實(shí)驗(yàn)結(jié)果可看出，采樣點(diǎn)優(yōu)化率可觀，有效地節(jié)省了存儲(chǔ)空間，還可根據(jù)不同誤差要求控制采樣點(diǎn)優(yōu)化數(shù)量和曲線光滑度。雖然此算法能較好地處理切向矢量值變化較大的采樣點(diǎn)，但是其繪制類似四角星4個(gè)角尖點(diǎn)時(shí)光滑度不理想，這將在后續(xù)工作中有待進(jìn)一步探討與改進(jìn)。

[1] 徐國良. CAGD中的隱式曲線與曲面[J]. 數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用, 1997, 18(2): 114-124.

[2] 劉穎. 復(fù)雜的隱式函數(shù)曲線繪制算法的研究[D]. 長春: 長春大學(xué), 2006.

[3] 張三元, 孫守遷, 蔣方炎, 等. 數(shù)字化仿真人體模型的設(shè)計(jì)方法[J]. 系統(tǒng)仿真學(xué)報(bào), 2000, 12(1): 49-50.

[4] 溫維亮, 郭新宇, 陸聲鏈, 等. 隱式曲面在三維植物建模中的應(yīng)用研究綜述[J]. 圖學(xué)學(xué)報(bào), 2010, 31(3): 1-10.

[5] 趙偉, 趙卓寧, 李五生. 一種有效的離散數(shù)據(jù)場(chǎng)等值線生成方法[J]. 成都信息工程學(xué)院學(xué)報(bào), 2007, 22(1): 116-121.

[6] SHELBERG M C, MOELLERING H, LAM N. Measuring the fractal dimensions of empirical cartographic curves [C]//Auto-Carto 5. Virginia: American Academy of Photometry and American Congress on Surveying and Mapping, 1982: 481-490.

[7] SUNDARAMOORTHI G, YEZZI A, MENNUCCI A. Coarse-to-fine segmentation and tracking using Sobolev active contours [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2008, 30(5): 851-864.

[8] TAUBIN G. Distance approximations for rasterizing implicit curves [J]. ACM Transactions on Graphics, 1994, 13(1): 3-42.

[9] 童若鋒, 汪國昭, 金通光. 輪廓跟蹤的TN方法[C]//第一屆全國幾何設(shè)計(jì)與計(jì)算學(xué)術(shù)會(huì)議論文集. 東營: 中國石油大學(xué)出版社, 2002: 579-582.

[10] 余正生. 隱式曲面造型與繪制算法研究[D]. 杭州: 浙江大學(xué), 1999.

[11] 蔡耀志. 正負(fù)法數(shù)控繪圖[J]. 工程圖學(xué)學(xué)報(bào), 1984, 5(Z1): 3-9.

[12] 吳堅(jiān), 張接信, 蔡宗琰. 用短線截交法繪制隱式曲線[J]. 機(jī)械科學(xué)與技術(shù), 2006, 25(8): 965-966.

[13] SUFFERN K G. Quadtree algorithms for contouring functions of two variables [J]. Computer Journal, 1990, 33(5): 402-407.

[14] DUFF T. Interval arithmetic recursive subdivision for implicit functions and constructive solid geometry [J]. ACM Computer Graphics, 1992, 26(2): 131-138.

[15] 壽華好, 何蘋, 繆永偉. 自動(dòng)微分在隱式曲線繪制中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 46(1): 150-153.

[16] LORENSEN W E, CLINE H E. Marching cubes: a high resolution 3D surface construction algorithm [J]. ACM Computer Graphics, 1987, 21(4): 163-169.

[17] 李洪發(fā). 分段三次Hermite插值的同時(shí)逼近[J]. 天津師范大學(xué)學(xué)報(bào): 自然版, 2012, 32(2): 38-40.

[18] FUHRMANN S, KAZHDAN M, GOESELE M. Accurate isosurface interpolation with hermite data [C]// 2015 International Conference on 3D Vision. New York: IEEE Press, 2015: 256-263.

Approximating Planar Implicit Curves with Hermite Interpolation

WEI Li, ZHAO Jingjie, HUANG Huimin

(Institute of Educational Information Engineering, Nanjing Normal University, Nanjing Jiangsu 210097, China)

Implicit curves play an important role in medical image processing, geographic information system, and numerical field visualization. On the basis of sampling point analysis and curve approximation method, we introduce an algorithm for approximating planar implicit curves by means of Hermite interpolation. The sampling points were firstly obtained by linearly interpolating each edge of the grid cells distributed uniformly in the grid region. Then, we calculated the error between curve segments before and after optimizing. Once the error meets the optimizing requirements, the sampling points are consequently optimized. Finally, the algorithm approximated the implicit curves by the Hermite interpolation method. Experiments have shown that even when the number of sampling points is small, the curves drawn by the algorithm still have relatively higher smoothness and accuracy.

graph plotting; implicit curve; Hermite interpolation; optimizing sampling point

TP 391.41

10.11996/JG.j.2095-302X.2018040752

A

2095-302X(2018)04-0752-05

2017-10-20；

2017-12-19

全國教育科學(xué)“十三五”規(guī)劃2017年教育部重點(diǎn)課題(DCA170302)

魏 利(1994-)，女，四川綿陽人，碩士研究生。主要研究方向?yàn)閿?shù)字幾何處理。E-mail：wei_li_015@163.com