兩條參數(shù)曲線間的Hausdorff距離的研究

李英明，李旭健

（1．萊蕪職業(yè)技術(shù)學(xué)院 信息工程系，山東 萊蕪 271100；2．山東科技大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266510）

兩條參數(shù)曲線間的Hausdorff距離的研究

李英明1＊，李旭健2

（1．萊蕪職業(yè)技術(shù)學(xué)院 信息工程系，山東 萊蕪 271100；2．山東科技大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266510）

在幾何設(shè)計中，兩個幾何體間的Hausdorff距離是一種非常有用的度量方式，但是其計算通常而言相當(dāng)耗時．本文找到了一種有效快捷的計算二維平面或三維空間中兩條參數(shù)曲線的Hausdorff距離的新算法，并通過若干例子展示了它的有效性．

Hausdorff距離；參數(shù)曲線；算法

兩條曲線間的Hausdorff距離被廣泛應(yīng)用于幾何設(shè)計當(dāng)中，如樣條曲線曲面的近似隱式化，代數(shù)曲線曲面近似參數(shù)化，代數(shù)曲線曲面擬合、以及圖像匹配識別等［1－2］．然而，Hausdorff距離的計算卻相當(dāng)困難，并且通常相當(dāng)費(fèi)時，它的研究也只局限在某些特定的場合下．Sedergerg［3］提出了兩條平面曲線的Hausdorff距離的范圍的計算方法．在此基礎(chǔ)上，Jüttler將其拓展到可以計算兩條平面隱式或參數(shù)曲線間 Hausdorff距離的范圍．文獻(xiàn)［4－7］中提出了圓錐曲線與參數(shù)有理Bézier曲線間近似Hausdorff誤差的方法．目前，兩條二維或三維空間中曲線間近似Hausdorff距離的算法的研究卻很少．為了提高Hausdorff距離的計算效率，減少計算時間，本文提出了一種有效的計算兩條二維或三維空間中曲線間近似Hausdorff距離的算法．與精確計算方法相比，該近似算法效率高，速度快，計算精度可控，滿足實(shí)用要求．

1 Hausdorff距離的定義及幾何意義

給定兩條參數(shù)曲線P（s），Q（t），t0≤t≤t1，假設(shè)兩條參數(shù)曲線的末端端點(diǎn)重合，即

為了計算它們之間的Hausdorff距離，定義一個兩條曲線間距離函數(shù)的平方項的映射，如公式2所示：

對于兩條正則參數(shù)曲線P（s）以及Q（t），有兩個原因使得

fs（s，t）＝0，即

1）P（s）＝Q（t），即兩條曲線相交；

2）Ps（s）垂直于P（s）－Q（t）．

類似地，同樣有兩點(diǎn)使得ft（s，t）＝0，即

1）P（s）＝Q（t），兩條曲線相交；

2）Qt（t）垂直于P（s）－Q（t）．

下面的引理1是簡化Hausdorff距離的計算．

引理1 兩條曲線P（s）及Q（t）間的Hausdorff距離可以通過兩條曲線fs（s，t）＝0和ft（s，t）＝0間的交點(diǎn)求出，即

證明 等式fs（s，t）＝0隱式定義了s－t平面上的一條曲線．假設(shè)這條曲線的顯式表達(dá)式為

s＝s（t），t0≤t≤t1，且s0＝s（t0），s1＝s（t1）．

約束方程（2），即f（s，t），在上述曲線fs（s，t）＝0上，可以得到單變量t的函數(shù)，也就是f（s（t），t），t0≤t≤t1，固定t＝＾t，使

由于在兩個端點(diǎn)，有f（s（t0），t0）＝f（s（t1），t1）＝0，以及f（s，t≥0），0，（s，t∈ ［s0，s1］× ［t0，t1］），所以函數(shù)f（s（t），t）的最大值點(diǎn)必然出現(xiàn)在其局部極值點(diǎn)，即

因?yàn)楹瘮?shù)f（s，t）限制在曲線fs（s，t）＝0（公式（6））上，所以可以得到

引理1意味著，如果兩條曲線P（s）與Q（t）之間的Hausdorff距離可以在它們的交點(diǎn)（sa，ta）處達(dá)到，那么有向量P（sa）－Q（ta）同時垂直于向量P＇（sa）與向量Q＇（ta）（參見圖1）．

圖1 Hausdorff距離Fig．1 Hausdorff distance

圖1中如果｜P（sa）－Q（ta））｜為 Hausdorff距離，則向量｜P（sa）－Q（ta））｜同時垂直于向量P＇（sa）與向量Q＇（ta）．

2 簡化與運(yùn)算

曲線fs（s，t）＝0以及ft（s，t）＝0均為隱式的．在通常情況下，它們的形狀非常復(fù)雜，所以它們的交點(diǎn)也同樣非常復(fù)雜．但大多數(shù)情況下兩條曲線P（s）以及Q（t）都滿足一條簡單的性質(zhì)，而這條性質(zhì)使得fs（s，t）＝0與ft（s，t）＝0的求交運(yùn)算變得較為容易．這種性質(zhì)可表示成如下引理2．

引理2 1）穿過任意點(diǎn)Q（t）并且垂直于該點(diǎn)的切向Q＇（t）的直線，如果其與曲線P（s）僅相交于唯一點(diǎn)，那么在區(qū)域［s0，s1］× ［t0，t1］，存在曲線ft（s，t）＝0的非自交連續(xù)分支，并且該分支包含（s0，t0）以及（s1，t1）；

2）穿過任意點(diǎn)P（s）并且垂直于該點(diǎn)的切向P＇（s）的直線，如果其與曲線Q（t）僅相交于唯一點(diǎn)，那么在區(qū)域［s0，s1］×［t0，t1］，存在曲線fs（s，t）＝0的非自交連續(xù)分支，并且該分支包含（s0，t0）以及（s1，t1）．

證明 這里僅證明1），2）的證明與1）是完全相似的．引理中的條件，即穿過任意點(diǎn)Q（t）并且垂直于該點(diǎn)的切向Q＇（t）的，且與曲線P（s）僅相交于唯一點(diǎn)的直線，意味著，對于任意直線t＝ta，ta∈［t0，t1］與曲線ft（s，t）＝0，（s，t）∈ ［s0，s1］× ［t0，t1］相交于唯一點(diǎn)．另一方面，因?yàn)镻（s0）＝Q（t0）以及P（s1）＝Q（t1），ft（s0，t0）＝ft（s1，t1）＝0，也就是，點(diǎn)（s0，t0）和（s1，t1）均落在曲線 ft（s，t）＝0上．

下面，利用反證法證明曲線ft（s，t）＝0在分支為連續(xù)的．

假設(shè)曲線ft（s，t）＝0，（s，t）∈ ［s0，s1］×［t0，t1］在上述定義域中非連續(xù)．非連續(xù)性會導(dǎo)致兩種情況，或者直線t＝ta與曲線ft（s，t）＝0（參見圖2（a））無交點(diǎn)，或者兩者之間多于一個相交點(diǎn)（參見圖2（b），2（c））．第一種情況意味著穿過點(diǎn)Q（ta）且垂直于與該點(diǎn)的切向Q＇（ta）的直線，與曲線P（s）無交點(diǎn)．第二種情況則意味著直線將會與曲線P（s）有多于一個交點(diǎn)．兩種情況都將導(dǎo)致矛盾的產(chǎn)生．所以假設(shè)不成立．即曲線的連續(xù)性得到證明．

然后，假設(shè)曲線ft（s，t）＝0在［s0，s1］× ［t0，t1］分支是自交的．參照圖2（d），這種自相交的情況會使得穿過點(diǎn)Q（ta）且垂直于該點(diǎn)切向Q＇（ta）的直線，與曲線P（s）有多于一個交點(diǎn)．這同樣會導(dǎo)致矛盾．

圖2 不連續(xù)性與自交Fig．2 Discontinuity and intersects with itself

因此，在區(qū)域［s0，s1］× ［t0，t1］，存在一個連接點(diǎn)（s0，t0）與點(diǎn)（s1，t1）的曲線ft（s，t）＝0的非自交連續(xù)分支，引理2得證．

根據(jù)引理1，兩條曲線 P（s）與 Q（t）間的Hausdorff距離可以在曲線l1：fs（s，t）＝0與l2：ft（s，t）＝0的交點(diǎn)處達(dá)到．如果兩條曲線P（s）與Q（t）滿足引理2的條件，則存在l1與l2在（s0，t0）以及（s1，t1）上的非自交連續(xù)分支，因此，l1與l2的交點(diǎn)可通過追蹤它們其中的一條計算求得．

算法1：計算兩條曲線間的Hausdorff距離輸入：兩條曲線P（s）以及Q（t），追蹤步長ε．輸出：P（s）與Q（t）間的近似Hausdorff距離．1：當(dāng)追蹤隱式曲線fs（s，t）＝0，可以得到一個點(diǎn)集序列｛（si，ti），i＝0，1…，n｝；2：for i＝0to n－1do 3：用 P1＝ （si－1；ti－1）和 P2＝ （si，ti）代入ft（s，t）；4：if ft（s；t）的符號變化 （說明這兩點(diǎn)之間有交點(diǎn)）then 5：選擇P1，P2，P1＋P22 三者之一作為交點(diǎn)，在該點(diǎn)處f2s（s，t）＋f2t（s，t）取最小值；6：end if 7：end for 8：將所有的交點(diǎn)代入f（s，t），最大值可被認(rèn)為是近似的Hausdorff距離．

追蹤隱式曲線的方法有多種［9］，這里選擇正負(fù)法［10］．

下面來分析這種近似估算Hausdorff距離的精確程度．假設(shè)近似的Hausdorff距離出現(xiàn)在點(diǎn)A＝（sa，ta）處，而真實(shí)的Hausdorff距離出現(xiàn)在點(diǎn)B＝ （sb，tb）處，連接這兩點(diǎn)間的線段被記為L，即

其中，ξ∈ ［0，1］，算法1輸入的追蹤步長ε可被認(rèn)為（9）式中的h，用于估計近似Hausdorff距離的精確程度．

下面用兩個實(shí)例來解釋說明算法1的效率．

例1 如圖3所示，計算兩個平面Bézier曲線P（s）以及Q（t）間的Hausdorff距離．兩個平面三次Bézier曲線的控制頂點(diǎn)如下：

P（t）：（0，0），（1，1），（2，1），（3，0）；

Q（s）：（0，0），（1，2），（2，2），（3，0）；

通過算法1，可以得到這兩條三次曲線的近似的Hausdorff距離，也就是0．75，在曲線P（s）上點(diǎn)（1．5，0．75），與曲線Q（t）上點(diǎn)（1．5，1．5）之間．這個例子的計算時間為0．1749s．

圖3 計算兩條平面三次Bézier曲線間的Hausdorff距離Fig．3 Calculation of theHausdorff distance between two planar cubic Bézier curves

例2 如圖4所示，要處理兩條空間四次Bézier曲線P（s）以及Q（t）．其控制頂點(diǎn)如下：

P（s）：（0，0，0），（1，1，－1），（2，1，1），（3，－1，－1），（4，0，0）；

Q（t）： （0，0，0）， （1，0．5，－ 0，5）， （1．5，－0．5，0．5），（3，－1，－0．5），（4，0，0）．

兩條曲線間的近似Hausdorff距離是0．7141，對應(yīng) 于 曲 線 P（s）上 的 點(diǎn) （1．6818，－0．2614，－0．0641）， 以 及 曲 線 Q（t） 上 的 點(diǎn) （2．000，0．3750，－0．1250）．在這個例子中，算法1需要的時間為0．1969s．

圖4 計算兩條空間四次Bézier曲線間的Hausdroff距離Fig．4 Calculation of the Hausdorff distance between two space quartic Bézier curves

3 結(jié)束語

本文提出了一種計算兩條平面或者空間曲線的近似Hausdorff距離的方法．構(gòu)造了兩條曲線間的距離函數(shù)，并且證明了兩條曲線間的Hausdorff距離一定會在這兩條曲線的偏導(dǎo)曲線的交點(diǎn)上達(dá)到．然后，通過追蹤一條偏導(dǎo)曲線來尋找交點(diǎn)，確定近似Hausdorff距離達(dá)到的點(diǎn)的位置，并通過若干個例子驗(yàn)證了本文算法的效率與準(zhǔn)確性．此算法為Hausdorff距離的應(yīng)用提供了新的思路．

［1］J?uttler B．Bounding the Hausdorff distance of implicitly defined and／or parametric curves［C］／／Lyche T，Schumaker L L．Mathematical Methods in CAGD：Oslo 2000．Nashville：Vanderbilt University Press，2001：223－232．

［2］劉嘉敏，王 玲，蘭逸君，等．基于外耳輪廓邊緣信息的人耳識別［J］．計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2008，20（3）：337－342．

［3］Sederberg T W．Planar piecewise algebraic curves［J］．Computer Aided Geometric Design，1984，1：241－255．

［4］Ahn Y J．Conic approximation of planar curves［J］．Computer Aided Design，2001，33（12）：867－872．

［5］Ahn Y J．Helix approximations with conic and quadratic bézier curves［J］．Computer Aided Geometric Design，2005，22：551－565．

［6］Floater M．High order approximation of conic sectons by quadratic splines［J］．Computer Aided Geometric Design，1995，12：617－637．

［7］Floater M．An O（h2n）Hermite approximation for conic sectons［J］．Computer Aided Geometric Design，1997，14：135－151．

［8］Degen W L F．Best approximations of parametric curves by spline［C］／／Lyche T，Schumaker L L．Mathematical Methods in CAGD II．New York：Academic Press，1992：171－184．

［9］Shou H，Shen J，Yoon D．Robust plotting of polar algebraic curves［J］．Space Algebraic Curves，and Offsets of Planar Algebraic Curves Reliable Computing，2006，12（4）：323－335．

［10］Yu Z，Cai Y，OH M，et al．An efficient method for tracing planar implicit curves［J］．Journal of Zhejiang University SCIENCE，2006，A7：1115－1123．

Abstract：In geometric design，the Hausdorff distance between two geometric entities is a useful measurement，while its computation is usually very time consuming．This paper，presents a new effective method to compute the Hausdorff distance between two parametric curves in 2Dplane or 3Dspace，and shows its effectiveness by some examples．

Key words：Hausdorff distance；parametric curve；algorithm

The study of the Hausdorff distance between two parametric curves

LI Yingming1，LI Xujian2
（1．Department of Information Engineering，Laiwu Vocational and Technical College，Laiwu，Shandong 271100；2．College of Informatics Science ＆Engineering，Shandong University of Science and Technology，Qingdao，Shandong 266510）

TP301

A

1000－1190（2012）03－0270－05

2011－09－07．

國家863重點(diǎn)課題基金項目（2009AA062701）；山東省高等學(xué)校優(yōu)秀青年教師國內(nèi)訪問學(xué)者項目經(jīng)費(fèi)資助；萊蕪職業(yè)技術(shù)學(xué)院項目經(jīng)費(fèi)資助．

＊E－mail：lwaming＠163．com．