曹利新，董 雷，曹京京

（大連理工大學(xué) 機(jī)械工程學(xué)院，遼寧 大連 116024）

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 曲線間單向Hausdorff距離的近似計(jì)算

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

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

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

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

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

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

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

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

將式（8）、（9）代入式（7），由文獻(xiàn)［10］，可得

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

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

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

式中：（i／mci）T為控制點(diǎn).

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

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

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

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

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

3 曲線間Hausdorff距離的精確計(jì)算

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

圖2 雙垂足點(diǎn)的計(jì)算Fig.2 Computation of antipodal points

3.1 雙垂足點(diǎn)的計(jì)算

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

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

3.2 一對(duì)二點(diǎn)的計(jì)算

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

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

圖3 一對(duì)二點(diǎn)的計(jì)算Fig.3 Computation of intersection point between one curve and self－bisector of other curve

3.3 A 類端點(diǎn)與B類端點(diǎn)的計(jì)算

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

4 數(shù)值算例

通過兩個(gè)算例來驗(yàn)證上述算法的可行性.

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

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

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

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

5 結(jié) 論

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

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

［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ù)多項(xiàng)式曲線細(xì)分重構(gòu)與插值細(xì)分曲面快速計(jì)算［D］.大連：大連理工大學(xué)，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.