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

魏 利，趙晶潔，黃慧敏

?

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

魏 利，趙晶潔，黃慧敏

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

隱式曲線在醫學圖像處理、地理信息系統、數值場可視化等領域中有著重要應用。在分析點采樣和曲線逼近理論的基礎上，提出一種運用Hermite插值方法逼近平面隱式曲線的算法。首先將曲線繪制區域網格化，在網格單元各邊中通過線性插值計算曲線采樣點；其次通過計算采樣點精簡前后構成的曲線段之間產生的誤差優化采樣點；最后通過Hermite插值法逼近隱函數曲線。實驗表明，通過該算法繪制出的曲線在采樣點數量較少的情況下，其光滑度和準確度仍較高。

圖形繪制；隱式曲線；Hermite插值；采樣點優化

隱式曲線是計算機輔助幾何設計和計算機圖形學的重要研究內容[1-2]，因其可描述平面上任意不規則的形狀，且在離散采樣曲線重建過程中，具有自動過濾數據噪聲的優點，在生物學[3-4]、氣象學[5]、地理學[6]、石油勘探及物探[7]等領域有著廣泛且重要的應用。

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

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

1 Hermite插值

分段三次Hermite插值是函數擬合和插值的基本方法[17]。對于給定+1個插值點0<1…<x和這些插值點上關于函數()的函數值0，1，2，…，y及導數值0，1，…，m，對任意=0，1，2，…，在區間[x，x+1]構造次數不大于3的多項式的分段插值，且有(x)=y和′(x)=m，那么函數()即為插值點(0,0)，(1,1)，…，(x,y)的分段三次Hermite插值函數。

若已知兩點01及其切向矢量0′、1′，即可根據兩點構成的三次Hermite參數方程求出插值點進而描述點01間的曲線。

為推導出三次Hermite參數方程[18]，首先假設平面上一條三次參數曲線表達式為

根據式(1)，設該曲線的矢量表達式為

其一階求導式為

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

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

2 算法梗概

本文平面隱式曲線Hermite插值逼近算法的處理過程分為3步：網格化獲取采樣點、優化采樣點和曲線折線化。

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

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

(3) 曲線折線化。對于優化后的采樣點通過Hermite插值逼近隱函數曲線。

3 算法步驟

3.1 網格化獲取采樣點

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

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

圖1 二義性情況

圖2 網格單元及采樣情況

3.2 優化采樣點

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

圖3 誤差示例圖

交點計算方法以圖3中與兩折線段為例，設其交點為。設線段、的矢量方程分別為

其中，0、1為定比參數。假設兩折線段有交點，聯立式(6)、(7)可得

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

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

圖4 多邊形NDP

3.3 曲線折線化

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

4 實驗與數據

利用本算法在PC機上基于Windows平臺和OpenGL圖形設備接口及Visual C++6.0實現了如下隱式函數曲線的繪制

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

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

表1 不同允許誤差m情況下采樣點個數及壓縮率比較

注：A表示優化后數據點個數，B表示優化率

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

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

圖7 二維MC算法與本文算法允許誤差為m≤10-6情況下采樣點數量對比圖

5 結束語

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

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

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

[3] 張三元, 孫守遷, 蔣方炎, 等. 數字化仿真人體模型的設計方法[J]. 系統仿真學報, 2000, 12(1): 49-50.

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

[5] 趙偉, 趙卓寧, 李五生. 一種有效的離散數據場等值線生成方法[J]. 成都信息工程學院學報, 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]//第一屆全國幾何設計與計算學術會議論文集. 東營: 中國石油大學出版社, 2002: 579-582.

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

[11] 蔡耀志. 正負法數控繪圖[J]. 工程圖學學報, 1984, 5(Z1): 3-9.

[12] 吳堅, 張接信, 蔡宗琰. 用短線截交法繪制隱式曲線[J]. 機械科學與技術, 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] 壽華好, 何蘋, 繆永偉. 自動微分在隱式曲線繪制中的應用[J]. 計算機工程與應用, 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] 李洪發. 分段三次Hermite插值的同時逼近[J]. 天津師范大學學報: 自然版, 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

全國教育科學“十三五”規劃2017年教育部重點課題(DCA170302)

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