兩條參數曲線間的Hausdorff距離的研究

李英明，李旭健

（1．萊蕪職業技術學院 信息工程系，山東 萊蕪 271100；2．山東科技大學 信息科學與工程學院，山東 青島 266510）

兩條參數曲線間的Hausdorff距離的研究

李英明1＊，李旭健2

（1．萊蕪職業技術學院 信息工程系，山東 萊蕪 271100；2．山東科技大學 信息科學與工程學院，山東 青島 266510）

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

Hausdorff距離；參數曲線；算法

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

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

給定兩條參數曲線P（s），Q（t），t0≤t≤t1，假設兩條參數曲線的末端端點重合，即

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

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

fs（s，t）＝0，即

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

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

類似地，同樣有兩點使得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間的交點求出，即

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

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

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

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

因為函數f（s，t）限制在曲線fs（s，t）＝0（公式（6））上，所以可以得到

引理1意味著，如果兩條曲線P（s）與Q（t）之間的Hausdorff距離可以在它們的交點（sa，ta）處達到，那么有向量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 簡化與運算

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

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

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

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

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

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

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

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

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

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

算法1：計算兩條曲線間的Hausdorff距離輸入：兩條曲線P（s）以及Q（t），追蹤步長ε．輸出：P（s）與Q（t）間的近似Hausdorff距離．1：當追蹤隱式曲線fs（s，t）＝0，可以得到一個點集序列｛（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）的符號變化 （說明這兩點之間有交點）then 5：選擇P1，P2，P1＋P22 三者之一作為交點，在該點處f2s（s，t）＋f2t（s，t）取最小值；6：end if 7：end for 8：將所有的交點代入f（s，t），最大值可被認為是近似的Hausdorff距離．

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

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

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

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

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

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）上點（1．5，0．75），與曲線Q（t）上點（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）．其控制頂點如下：

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，對應 于 曲 線 P（s）上 的 點 （1．6818，－0．2614，－0．0641）， 以 及 曲 線 Q（t） 上 的 點 （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 結束語

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

［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］．計算機輔助設計與圖形學學報，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重點課題基金項目（2009AA062701）；山東省高等學校優秀青年教師國內訪問學者項目經費資助；萊蕪職業技術學院項目經費資助．

＊E－mail：lwaming＠163．com．