平面曲線間Hausdorff距離計算

曹利新，董 雷，曹京京

（大連理工大學 機械工程學院，遼寧 大連 116024）

0 引 言

幾何對象間距離的計算是工程領(lǐng)域中經(jīng)常用到的一種幾何操作，如幾何建模與模式識別中對幾何對象的分析與比較［1］；機器人路徑規(guī)劃、CAD／CAM 和觸覺仿真中，對物體間的碰撞干涉檢測和反饋力的計算［2］.曲線、曲面逼近中構(gòu)造優(yōu)化目標和評價逼近程度［3］等眾多工程應(yīng)用領(lǐng)域，都涉及幾何對象間距離的計算.在不同的距離測度中，尤以歐幾里得最小距離和Hausdorff距離受到幾何建模、計算幾何和計算機圖形學等研究領(lǐng)域?qū)W者的格外關(guān)注.

幾何對象間最小距離的計算問題，就是在兩個幾何對象間求解對應(yīng)距離最小的一對點.當需要比較兩個對象間的相似程度時，則常采用Hausdorff距離.Hausdorff距離是由現(xiàn)代拓撲學的奠基人之一德國數(shù)學家Hausdorff 首先提出［4］，廣泛用于衡量兩個集合之間差別的度量.早期的Hausdorff距離計算主要出現(xiàn)在模式識別、圖像處理領(lǐng)域，為了對兩幅圖像進行匹配或比較，通常對兩幅圖像首先進行邊緣提取、距離變換等預處理；然后將預處理后的圖像像素看作兩個集合，通過對兩集合間Hausdorff距離的計算，進而對兩圖像間的相似度進行評價；對其中一幅圖像進行仿射變換，使變換后圖像與目標模板圖像間的Hausdorff距離達到最小，若該距離小于給定的公差，則表示兩幅圖像獲得了匹配，這一方法目前已廣泛用于人臉、指紋、字符、筆跡、汽車車牌等的識別［5－6］.

與圖像領(lǐng)域中Hausdorff距離的計算和應(yīng)用研究形成鮮明對比的是，針對連續(xù)幾何對象間的Hausdorff距離的計算研究則相對較少，截至目前，只有少數(shù)學者［1－3，7－8］針對自由曲線或曲面間的Hausdorff距離的精確計算進行過研究.2008年，Alt等［1］證明了兩C1連續(xù)的平面曲線間單向Hausdorff距離h（A，B）會出現(xiàn)4 種情況，即Hausdorff距離可能發(fā)生在：曲線A的一個端點和它在曲線B上的垂足點之間、曲線B的一個端點和它在曲線A上的垂足點之間、雙垂足點間、一曲線自身的中線與另一曲線的交點之間，并給出了4種情況分別對應(yīng)的非線性約束方程組，最終借助標準的代數(shù)方程組求解器獲得了平面曲線間的Hausdorff距離.同年，Elber等［2］將平面C1連續(xù)曲線Hausdorff距離出現(xiàn)4種情況這一結(jié)論推廣到空間曲線／曲面間，并利用作者自己開發(fā)的代數(shù)方程組求解器獲得了相應(yīng)的Hausdorff距離，同時以平面曲線為例給出了Hausdorff距離的幾何含義：A對B的單向Hausdorff距離，可看作是對曲線B進行等距變換，當曲線A恰好完全包含在曲線B的等距線內(nèi)時，此時的等距距離為A對B的 單 向Hausdorff距 離.2010 年，Chen等［3］針對文獻［1－2］中非線性方程組求根方法的不足，研究了計算兩B 樣條曲線間Hausdorff距離的幾何裁剪方法，算法給出了Hausdorff距離出現(xiàn)在曲線端點的充分條件，利用曲線分割技術(shù)和滾動圓裁剪方法，將兩曲線的Hausdorff距離計算問題轉(zhuǎn)化為點和曲線的最小或最大距離計算問題，從而提高了算法的穩(wěn)定性和計算效率.同年，Kim 等［7］針對兩平面自由曲線提出了一種精確計算Hausdorff距離的實時算法.首先采用G1連續(xù)的雙圓弧，在給定公差下對自由曲線進行逼近；進而對這些圓弧進行距離映射并保存到圖形硬件深度緩沖器；并對大部分多余的圓弧段進行裁剪，從而提高了Hausdorff距離的計算效率.2011年，Bai等［8］提出了計算平面曲線間Hausdorff距離的折線方法，該方法首先根據(jù)給定容差將連續(xù)曲線離散為折線段，進而將曲線間的Hausdorff距離計算轉(zhuǎn)化為連續(xù)折線段間的Hausdorff距離計算，同時針對無用的折線段給出了兩種裁剪策略，極大地提高了這一復雜問題的計算效率.2013年，Ko［9］從理論上深入分析了平面曲線間Hausdorff距離計算的復雜性問題.

綜合現(xiàn)有文獻來看，針對連續(xù)曲線或曲面間的Hausdorff距離計算問題，近年來受到幾何建模、計算幾何、計算機圖形學等領(lǐng)域?qū)W者的關(guān)注，同時也是Hausdorff距離在工程界獲得廣泛應(yīng)用的瓶頸所在.目前的研究工作存在如下問題：（1）針對連續(xù)幾何對象間Hausdorff 距離計算的研究相對較少，尤其是針對自由曲線或曲面間的Hausdorff距離計算更少；（2）大多學者通過對代數(shù)方程組的求解獲得Hausdorff距離，并將代數(shù)方程組的求解當作了一個黑箱或采用標準求解器求解，未給出太多有參考價值的解算方法；（3）C1連續(xù)平面曲線間的單向Hausdorff距離會出現(xiàn)4種情況，由于4種情況對應(yīng)的非線性方程組并不相同，需要利用代數(shù)方程組求解器對4種情況對應(yīng)的非線性方程組分別進行求解，這將嚴重影響曲線間Hausdorff距離的計算效率.

本文僅討論平面連續(xù)曲線間Hausdorff距離的計算問題，算法分兩步對平面曲線間的單向Hausdorff距離進行計算，最終選擇優(yōu)化結(jié)果中的最大值作為兩平面曲線間的單向Hausdorff距離.

1 平面曲線間Hausdorff距離對應(yīng)點的分類

Hausdorff距離分單向和雙向兩種，對于兩個非空的緊致集合A與B，集合A中一個對象相對于集合B中所有對象的最小距離的最大值，稱為集合A到集合B的單向Hausdorff距離，表示為

式中：d（a，b）為點a和點b間的歐幾里得距離.同理，集合B到集合A的單向Hausdorff距離可表示為

單向Hausdorff距離通常用來表示一個集合相對于另一個集合的最大偏差.兩個單向Hausdorff距離中的大者稱為集合A與B的雙向Hausdorff距離，簡稱Hausdorff距離，用來表示集合A、B間的最大偏差，亦可用來表示集合A與B的相似度.雙向Hausdorff距離通常表示為

從Hausdorff距離的定義可以看出，最小距離的確定是計算Hausdorff距離的基礎(chǔ).由于雙向Hausdorff距離與單向Hausdorff距離的算法相似，下面僅進行h（A，B）的計算討論.

文獻［1］對C1連續(xù)的平面曲線間可能對應(yīng)單向Hausdorff距離的點進行如下分類：

A 類端點：即曲線A對曲線B的單向Hausdorff距離h（A，B），出現(xiàn)在曲線A的一個端點和其在曲線B上的法向映射點或曲線B的一個端點處，如圖1（a）所示.

B類端點：h（A，B）出現(xiàn)在曲線B的一個端點和它在曲線A上的法向映射點處，如圖1（b）所示.

雙垂足點：當h（A，B）的對應(yīng)點發(fā)生在兩條曲線內(nèi)部，且對應(yīng)點為一一對應(yīng)時，即出現(xiàn)如圖1（c）所示的雙垂足點情形，因?qū)?yīng)點均為垂足點，故稱為雙垂足點.根據(jù)曲線間距離函數(shù)取得極值的必要條件，可以將曲線間雙垂足點對應(yīng)的約束方程表示為

圖1 平面曲線間Hausdorff距離對應(yīng)點的分類Fig.1 Hausdorff distance between two planar curves and corresponding points

式中：rA、rB分別表示曲線A、B上對應(yīng)點的矢徑；r′A、r′B分別表示曲線A、B在對應(yīng)點的切矢.上式表明兩曲線在對應(yīng)點處的切線平行，即存在公法線.

一對二點：當h（A，B）的對應(yīng)點發(fā)生在兩條曲線內(nèi)部，且曲線A上一點對應(yīng)曲線B上兩點時，則出現(xiàn)如圖1（d）所示的一對二點情形.一對二點也可以看作是曲線A與曲線B的中軸線的交點，以及中軸變換圓與曲線B的兩個切點的總稱.一對二點對應(yīng)的約束方程可表示為

式中：s、t分別為曲線B上兩個對應(yīng)點的曲線參數(shù)值；式（5a）表示曲線A上的點N到曲線B上點P和點Q的距離相等，式5（b）、（c）表示向量PN和QN分別與曲線B上P、Q兩點處的切線垂直.

從平面曲線間單向Hausdorff距離對應(yīng)的4種可能點來分析，對于參數(shù)曲線，前兩種情況均可看作是h（A，B）的對應(yīng)點的曲線參數(shù)為曲線參數(shù)域的邊界，只有當曲線為開曲線時才會出現(xiàn)這種情況.當h（A，B）的對應(yīng)點均為各自曲線的內(nèi)部點，若對應(yīng)點為一一對應(yīng)時，則為雙垂足點情形；若曲線A上一點對應(yīng)曲線B上兩點時，則為一對二點情形.此時用曲線B的等距線包容曲線A時，等距線自身必發(fā)生自交現(xiàn)象，自交點即為點N.上面所討論的4種情形均是非退化時的情況，若考慮到退化情況會更復雜.例如，一對二點情形中的P點剛好是曲線B上的一個曲率極值點時，此時曲線B上的對應(yīng)點退化為一個，但又不同于雙垂足點情形.

上面給出了平面曲線間單向Hausdorff距離對應(yīng)的4種類型可能點，對于工程中遇到的實際曲線，曲線上局部滿足4種類型點所對應(yīng)約束條件的點有多個，通常需要分別計算所有可能點，并從中選取最大距離點作為h（A，B）.由于雙垂足點和一對二點所對應(yīng)的約束方程不同，通常需要對曲線A和B分別按照約束方程（4）和（5）進行計算，再從中選取最大值作為曲線A對B的單向Hausdorff距離.這樣的計算顯然效率并不高，因為同樣的步驟，如曲線分段、求解約束方程組等，均需要進行兩次計算.為此本文下面分兩步對平面曲線間的Hausdorff距離進行計算.

2 曲線間單向Hausdorff距離的近似計算

為了計算曲線A到曲線B的單向Hausdorff距離，本文首先對曲線A進行離散化處理，獲取曲線A上的n個離散點.由于僅需要獲得兩曲線間h（A，B）的近似解，最終的計算精度取決于下一節(jié)的精確計算，故離散間隔不必太小.對曲線A的離散化處理可以簡單地按照等參數(shù)間隔進行，也可考慮曲線A的曲率特點，在曲率較大的位置設(shè)置較多的離散點，在曲率較小的位置設(shè)置較少的離散點.然后分別計算各個離散點到曲線B的最短距離，選取若干個距離較大，且滿足曲線A上相鄰點到曲線B的距離呈“小大小”的點對，作為曲線間單向Hausdorff距離的近似解.這樣，平面曲線間單向Hausdorff距離的近似計算就轉(zhuǎn)化為點到曲線間最短距離的計算問題.

設(shè)平面內(nèi)一定點P和一條曲線C：r＝r（t），t∈ ［0 ，1］ ，t為曲線的一般參數(shù).點P到曲線C（t）的歐幾里得距離可表示為

對距離函數(shù)式（6）求導并令其為零，可得距離函數(shù)取得極值的必要條件為

上面距離函數(shù)取得極值的必要條件，對應(yīng)著點P到曲線C局部的距離最大值和最小值.該式表明在距離函數(shù)取得極值時，定點P與它在曲線C上的對應(yīng)點的連線必與曲線C在該點的切矢正交.從所有這些極值中選出最小值，即為點P到曲線C的全局最小距離.問題的關(guān)鍵是如何快速、穩(wěn)定地求解非線性式（7）.該方程的計算方法通?？梢苑譃榫植繑?shù)值迭代和全局計算方法兩大類.局部迭代方法包括常用的牛頓迭代法、二分法、黃金分割法等.局部迭代方法需要為每個根提供較好的初值點，且在有些情況下可能產(chǎn)生振蕩，因此很難適用于不便提供初值的多值計算問題.全局計算方法通常有代數(shù)與混合技術(shù)、同倫方法和細分方法［10］，其中細分方法由于其在多值問題、穩(wěn)定性和效率方面的優(yōu)點，受到國內(nèi)外學者的廣泛關(guān)注.本文采用細分方法計算點到曲線間的最短距離.

細分方法起源于通過多邊形割角（corner cutting）獲得光滑曲線的樸素思想，Chaikin［11］在1974年Utah大學舉行的CAGD 國際會議上給出了一種基于割角思想快速生成曲線的算法.之后Riesenfeld和Forrest從理論上證明了這種細分極限曲線的數(shù)學本質(zhì)是均勻二次B樣條曲線，由此揭開了均勻B樣條與細分這個新興理論的聯(lián)系［12］.

此處，曲線C采用Bezier形式.若曲線為B樣條、NURBS或其他參數(shù)多項式曲線，均可轉(zhuǎn)化為Bezier曲線形式.設(shè)曲線C為n次Bezier曲線，其表達式為

式中：多項式系數(shù)bi為控制點；Bi，n（t）為Bernstein基函數(shù)；Cin為組合數(shù)；t為曲線參數(shù).

曲線C關(guān)于t的一階導數(shù)可表示為

將式（8）、（9）代入式（7），由文獻［10］，可得

式（9）、（10）表明，Bezier曲線的一階導數(shù)，以及兩個Bezier曲線的乘積仍為Bezier曲線，只是該多項式曲線的次數(shù)和系數(shù)（即控制點）發(fā)生了變化.將式（10）簡寫為

式中：m＝2n－1；ci＝由于Bernstein多項式具有線性精度特性，式（11）中的參數(shù)t可以表示為系數(shù)在［0，1］上均勻分布的m次Bernstein多項式的加權(quán)和，即

以參數(shù)t為水平軸，函數(shù)f（t）為垂直軸，則可構(gòu)造出如下曲線：

式中：（i／mci）T為控制點.

至此，多項式求根問題即轉(zhuǎn)化為一個Bezier曲線與其參數(shù)軸求交這樣一個幾何問題.本文采用文獻［10］中的PP 算法對式（13）進行求解，該算法主要依賴于Bernstein形式的多變元多項式細分算法和二維點集的凸殼算法，算法主要包含如下3個步驟：

①首先需要構(gòu)造Bezier曲線的凸殼，并計算凸殼與參數(shù)軸的交點；

②利用de Casteljau 細分算法，剔除參數(shù)域中不含有根的區(qū)域；

③若剩余的參數(shù)域足夠小，則返回該參數(shù)作為一個根.若經(jīng)多次剔除不含有根的參數(shù)域后，參數(shù)域仍非足夠小，則表明該參數(shù)域中包含一個以上的根，需要利用de Casteljau 細分算法將該參數(shù)域一分為二后重新返回步驟①.

利用上面點到曲線最短距離的算法，可以獲得曲線A上各離散點到曲線B的最短距離.選擇其中距離較大，且滿足曲線A上相鄰點到曲線B的距離呈“小大小”的點對作為近似解.

3 曲線間Hausdorff距離的精確計算

將前面獲得的若干距離較大，且滿足曲線A上相鄰點到曲線B的距離呈“小大小”的點對作為初始點，根據(jù)初始點附近曲線的形狀與位置特點，構(gòu)造相應(yīng)的Hausdorff距離的精確算法.如圖2所示，設(shè)P、Q分別為曲線A和B上的關(guān)于h（A，B）的一組對應(yīng)點，假設(shè)前面對曲線A的離散化處理遵循數(shù)據(jù)采樣中的采樣定理［13］，則精確的Hausdorff距離對應(yīng)點一定會出現(xiàn)在初始解附近，并隨著兩曲線的形狀與位置不同，表現(xiàn)出多種形式：雙垂足點、一對二點、A 類端點和B 類端點，下面分別討論這4種情形.

圖2 雙垂足點的計算Fig.2 Computation of antipodal points

3.1 雙垂足點的計算

雙垂足點包含兩曲線間距離的局部最大值和最小值所對應(yīng)的點對，由于前面的初步計算中僅選取了距離較大的點作為初始點，此處不會出現(xiàn)最小距離所對應(yīng)的雙垂足點.如圖2所示，點P、Q分別為曲線A、B上近似的Hausdorff距離對應(yīng)點對，t、s分別為曲線A、B的參數(shù).P1（t1）、P2（t2）為曲線A上點P的左右相鄰離散點，T1、T2為兩點處曲線的單位切矢，Q1（s1）、Q2（s2）為它們在曲線B上的最短距離對應(yīng)點，且滿足“小大小”約束所對應(yīng)的不等式：P1Q1≤PQ≥P2Q2.R1＝P1－Q1、R2＝P2－Q2為兩曲線上對應(yīng)點間的矢量，α1、α2分別為矢量R1、R2與矢量T1、T2之間的夾角，從圖2可以看出α1和α2中一個為銳角，另一個為鈍角.若Q1和Q2兩點間的距離Q1Q2或它們的參數(shù)間隔小于某個預先設(shè)定的常數(shù)，則可認為曲線A、B間單向Hausdorff距離的對應(yīng)點為雙垂足點.以P1、P2兩點的曲線參數(shù)t1、t2為初值，構(gòu)造函數(shù)

由于f1·f2＜0，可通過二分算法來計算兩曲線間精確的局部最大距離所對應(yīng)的雙垂足點.

3.2 一對二點的計算

參考圖3，若點P、Q分別為曲線A、B上近似的Hausdorff距離對應(yīng)點對，且其鄰近離散點滿足不等式P1Q1≤PQ≥P2Q2約束，但Q1和Q2兩點間的距離Q1Q2或它們的參數(shù)間隔Δs大于預先設(shè)定的常數(shù)，則可認為曲線A、B間Hausdorff距離的對應(yīng)點為一對二點.仍以P1、P2兩點的曲線參數(shù)t1、t2為初值，構(gòu)造函數(shù)

式中：sgn［x］為符號函數(shù)，根據(jù)x的正負取“＋”或“－”；d11、d12為點P1到曲線B的最短和次最短距離；d21、d22為點P2到曲線B的最短和次最短距離.由于f1·f2＜0，可通過二分算法來計算兩曲線間精確的局部最大距離所對應(yīng)的一對二點.最終精確的Hausdorff距離的對應(yīng)點一定會表現(xiàn)為曲線A上的一個點P對應(yīng)曲線B上的兩個垂足點Q1、Q2，且PQ1＝PQ2.

圖3 一對二點的計算Fig.3 Computation of intersection point between one curve and self－bisector of other curve

3.3 A 類端點與B類端點的計算

若曲線A或B為開曲線，最終的Hausdorff距離可能發(fā)生在曲線的端點.為此，可直接利用第2章關(guān)于點到曲線最短距離的算法，計算開曲線的兩個端點到另一曲線的最短距離.至此，利用本章算法可實現(xiàn)平面曲線間Hausdorff距離計算中出現(xiàn)的各種形式點的精確計算，與第2章算法結(jié)合，則可形成平面曲線間Hausdorff距離的完整算法.

4 數(shù)值算例

通過兩個算例來驗證上述算法的可行性.

例1 曲線A為Bezier開曲線；曲線B為三次均勻B 樣條表示的封閉曲線，控制點個數(shù)為90.現(xiàn)在要計算曲線A到B的單向Hausdorff距離h（A，B）.計算過程分兩個步驟：首先進行h（A，B）的近似計算，將曲線A按照其參數(shù)進行均勻十等分離散化處理，利用文獻［14］的算法將曲線B由B 樣條形式轉(zhuǎn)換為三次分段Bezier曲線，然后利用第2章的方法計算各離散點到曲線B的最短距離；從11 個最短距離中選取距離較大，且滿足“小大小”特點的點，利用第3章的算法進行Hausdorff距離的精確計算，計算精度為10－10.計算結(jié)果如圖4所示.圖4（a）給出了曲線A上的11個離散點，以及與第2個離散點對應(yīng)的曲線B上的14個距離極值點；圖4（b）給出了曲線A上11個離散點中與曲線B最小距離較大，且滿足“小大小”特征的兩個點和曲線B上對應(yīng)的垂足點；圖4（c）表達了經(jīng)過Hausdorff距離的精確計算后對應(yīng)點的分布，兩個距離分別為66.019 839mm 和54.720 453mm，開曲線A的兩端點到曲線B的最短距離分別為27.011 021 mm 和13.104 928mm；對圖4（c）中的兩個距離以及開曲線的兩端點到曲線B的最短距離進行比較，最后的單向Hausdorff距離為66.019 839 mm，對應(yīng)點如圖4（d）所示.

例2 曲線A、B均為立方均勻B 樣條表示的封閉曲線，控制點個數(shù)均為90，計算精度為10－10.現(xiàn)在要計算曲線A到B的單向Hausdorff距離h（A，B）.計算過程與例1相同，計算結(jié)果如圖5所示.圖5（a）給出了曲線A上的90個離散點，以及第20個離散點對應(yīng)的曲線B上的10個距離極值點；圖5（b）給出了曲線A上90個離散點中與曲線B最小距離較大，且滿足“小大小”特征的前三個點和曲線B上對應(yīng)的垂足點；圖5（c）表達了精確Hausdorff距離的計算結(jié)果，其中包含一個雙垂足點和兩個一對二點，3個距離（按紅綠藍 順 序）分 別 為77.874 235、70.736 729 和66.611 425mm；對圖5（c）中的3個距離進行比較，最后的單向Hausdorff距離為77.874 235 mm，對應(yīng)點如圖5（d）所示.

圖4 開曲線與封閉曲線間的Hausdorff距離計算Fig.4 Computation of HD between an open curve and a closed curve

圖5 兩封閉曲線間的Hausdorff距離計算Fig.5 Computation of HD between two closed curves

5 結(jié) 論

（1）本文分兩步對平面曲線間單向Hausdorff距離進行計算.第一步將其中一條曲線進行離散處理，并計算各離散點到另一條曲線的最小距離，從中選擇若干個距離較大且滿足“小大小”特征的點對，作為近似的Hausdorff距離對應(yīng)點；第二步以各近似點對作為初值，依據(jù)各點處曲線的特點，建立相應(yīng)的局部優(yōu)化模型并求解，從而獲得平面曲線間精確的Hausdorff距離.該方法克服了傳統(tǒng)的針對4種情況分別求解不同非線性方程組的缺點，簡化了計算過程.

（2）通過近似和精確計算單向Hausdorff距離的兩步算法，將平面曲線間Hausdorff距離的計算轉(zhuǎn)化為點到曲線的最小距離計算問題；同時利用細分算法可以快速、穩(wěn)定地獲得點到曲線的最短距離，提高了計算效率和穩(wěn)定性，數(shù)值算例驗證了本文所提方法的正確性.

［1］ Alt H，Scharf L.Computing the Hausdorff distance between curved objects［J］.International Journal of Computational Geometry ＆ Applications，2008，18（4）：307－320.

［2］ Elber G，Grandine T.Hausdorff and minimal distances between parametric freeforms inR2andR3［J］.Lecture Notes in Computer Science，2008，4975：191－204.

［3］ Chen X D，Ma W Y，Xu G，etal.Computing the Hausdorff distance between two B－spline curves［J］.Computer－Aided Design，2010，42（12）：1197－1206.

［4］ Scholz E.Felix Hausdorff and the Hausdorff edition［J／OL］.［2012－12－09］.http：／／www.math.uni－wuppertal.de／～scholz／preprints／ENLbioHaus.pdf.

［5］ Huttenlocher D P，Kedem K.Computing the minimum Hausdorff distance for point sets under translation［C］／／SCG′90Proceedings of the Sixth Annual Symposium on Computational Geometry.New York：ACM，1990：340－349.

［6］ Huttenlocher D P，Klanderman G A，Rucklidge W J.Comparing images using the Hausdorff distance under translation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1993，15（9）：850－863.

［7］ Kim Y J，Oh Y T，Yoon S H，etal.Precise Hausdorff distance computation for planar freeform curves using biarcs and depth buffer［J］.The Visual Computer，2010，26（6－8）：1007－1016.

［8］ Bai Y B，Yong J H，Liu C Y，etal.Polyline approach for approximating Hausdorff distance between planar free－form curves ［J］.Computer－Aided Design，2011，43（6）：687－698.

［9］ Ko K.On the complexity of computing the Hausdorff distance ［J］.Journal of Complexity，2013，29（3－4）：248－262.

［10］ Patrikalakis N M，Maekawa T.Shape Interrogation for Computer Aided Design and Manufacturing［M］.New York：Springer，2001：73－108.

［11］ Chaikin G M.An algorithm for high speed curve generation ［J］.Computer Graphics and Image Processing，1974，3（4）：346－349.

［12］ 李保軍.指數(shù)多項式曲線細分重構(gòu)與插值細分曲面快速計算［D］.大連：大連理工大學，2009.LI Bao－jun.Construction of exponentials reproducing subdivision schemes and rapid evaluation of interpolatory subdivision surfaces［D］.Dalian：Dalian University of Technology，2009.（in Chinese）

［13］ Castleman K R.Digital Image Processing［M］.New Jersey：Prentice－Hall，1996.

［14］ Piegl L，Tiller W.The NURBS Book［M］.2nd ed.Berlin：Springer，1997：142－228.