一種參數(shù)曲線間Hausdorff距離的計算方法

林 意，薛思騏，郭婷婷

(江南大學(xué)數(shù)字媒體學(xué)院，江蘇 無錫 214122)

Hausdorff距離在幾何設(shè)計、圖像匹配、圖像識別中有廣泛應(yīng)用[1-2]，但是現(xiàn)階段關(guān)于參數(shù)曲線間Hausdorff距離[3]的研究較少，計算仍有一定難度，無法通過其定義直接計算獲得。Scharf等[4-5]提出了在自由曲線上可能產(chǎn)生Hausdorff距離的4種情況：產(chǎn)生在端點處、極值點處、共線法向點處或是平分線交點處，并給出了對應(yīng)的求解方程或方程組[6-7]。雖然通過方程組計算Hausdorff距離產(chǎn)生的結(jié)果比較精確，但是對于參數(shù)曲線來說，求解方程組的復(fù)雜度很高，計算較為困難。因此，Chen等[8-10]從幾何角度提出了曲線間Hausdorff距離的計算方法，通過不斷減小半徑的圓弧來排除無效曲線段，直至最后收斂于一個確定的值。這種方法需要計算距離方差，雖然計算量比前種方法小，但仍然不是很方便。此外，在進(jìn)行圓弧剪枝時，如何判斷曲線段是否在圓弧外也較困難。白彥冰[11]將曲線在給定誤差下離散成折線，然后在Scharf[12]提出的基于Voronoi圖性質(zhì)的單向Hausdorff距離計算方法的基礎(chǔ)上計算折線間的Hausdorff距離，以近似獲得曲線間的Hausdorff距離。這種方法無需計算方程，但Voronoi圖的構(gòu)建比較復(fù)雜，且在進(jìn)行曲線離散時采用遞歸分割的方法，需另外采取節(jié)點插入算法，比較繁瑣。

本文將曲線繪制過程中產(chǎn)生的折線作為曲線離散折線，然后將曲線間的Hausdorff距離轉(zhuǎn)化為折線間的Hausdorff距離并進(jìn)一步轉(zhuǎn)化為點到線段間的距離進(jìn)行計算，并加以必要的剪枝策略[13]以提高計算效率。

1 Hausdorff距離的定義

Hausdorff距離是描述兩組點集之間相似程度的一種量度，它是兩個點集之間距離的一種定義形式，它具有方向性。假設(shè)有兩個點集A和B，a和b分別為A和B中任意一點，則點集A到B的單向Hausdorff距離指點集A中每個點到點集B的最小距離中的最大距離，可以表示為：

同理，可以表示出點集B到點集A的單向Hausdorff距離h(B,A)。則點集A與點集B之間的Hausdorff距離定義為：

2 參數(shù)曲線間Hausdorff距離的計算與優(yōu)化

2.1 曲線離散

在計算機(jī)進(jìn)行曲線繪制時，通常采用下面算法分段繪制：

也就是說，以折線來近似代替原曲線，而且，折線可以按變量e的改變，很好的逼近曲線，現(xiàn)在，微軟的畫圖軟件、AutoCAD等公司均采用這種方法畫曲線。

根據(jù)這一思想，本文將曲線繪制過程中產(chǎn)生的折線作為曲線離散折線，然后將曲線間的Hausdorff距離轉(zhuǎn)化為折線間的Hausdorff距離并進(jìn)一步轉(zhuǎn)化為點到線段間的距離進(jìn)行計算，并加以必要的剪枝策略以提高計算效率。

當(dāng)然，會不會折線近似代替曲線后的Hausdorff距離誤差依舊很大呢？

假設(shè)兩條曲線分別為r1，r2，相應(yīng)的離散后的折線為d1，d2，r1與d1的最大誤差為ε1，r2與d2的最大誤差為ε2。即|r1-d1|≤ε1，|r2-d2|≤ε2。用H(r,d)=|r-d|表示r與d之間的Hausdorff距離，由此可得：

因此，H(r1,r2) -H(d1,d2)≤ε1+ε2

可見，曲線間的Hausdorff距離與離散折線間的Hausdorff距離的誤差具有可控性。由于d1越逼近r1，則ε1越?。煌?，d2越逼近r2，則ε2越小。進(jìn)一步就是，d1與d2的Hausdorff距離越接近r1與r2的Hausdorff距離。所以，曲線間的Hausdorff距離可以近似用離散折線的Hausdorff距離來計算。

2.2 折線間的Hausdorff距離計算

折線d1和d2間的Hausdorff距離可以通過計算兩次折線到折線的單向Hausdorff距離來獲得。計算d1到d2的單向Hausdorff距離時，可以分別計算d1上所有線段到d2的單向Hausdorff距離，然后取其中的最大者作為d1到d2的單向Hausdorff距離。因為d2也是線段的集合，因此根據(jù)Hausdorff距離的定義，在計算d1線段到d2的Hausdorff距離時，可以分別計算線段到d2上所有線段的最小距離，然后取其中的最大者作為線段到d2的單向Hausdorff距離。這就將計算折線到折線的單向Hausdorff距離轉(zhuǎn)化為了計算線段到線段的單向最小距離。那么d1到d2的單向Hausdorff距離可以寫成如下形式：

我們知道，線段s1到線段s2的最小距離只會產(chǎn)生在s1的某個端點處。

圖1 線段間最小距離示意圖

如圖1所示，過s1的一端點O1作s2的垂線，有兩種情況，分別為垂足P落在線段s2內(nèi)和線段s2外。若垂足落在s2內(nèi)，則s1到s2的最小距離為s1的一端點與它到s2的垂足之間的距離O1P；若垂足落在s2外，則s1到s2的最小距離為s1的一端點與s2的一端點間的距離O1Q1。因此，在求線段到線段的單向最小距離時只要求線段的端點到另一線段的最小距離即可。計算折線到折線的Hausdorff距離就轉(zhuǎn)化為了計算點到線段的距離。

2.3 剪枝策略

參數(shù)曲線離散成為折線后，包含大量線段，而最后結(jié)果實際只產(chǎn)生在某兩條線段中，若依次迭代所有線段進(jìn)行計算，效率很低。因此本文采用一定的剪枝策略來提高計算效率。剪枝方法分為2個步驟：①畫折線中每條相鄰線段的角平分線，并計算角平分線與另一折線的交點來代替Voronoi圖，因為線段集的Voronoi圖是由這些角平分線與線段組成的，同時采用增量式算法將另一折線上的線段進(jìn)行再分割，而每條線段的端點則作為計算的采樣點；②判斷每個采樣點與角平分線交點的位置關(guān)系，找到對應(yīng)的線段，計算時只需計算每個點到對應(yīng)線段的距離，其他線段可作為無效線段排除。

2.3.1 排除d2上無效線段

在計算點到線段的距離時，為了找到與點相對應(yīng)的距離最短的線段，需利用Voronoi圖。根據(jù)Voronoi圖的定義可知，在平面內(nèi)折線d的Voronoi圖劃分的n個區(qū)域內(nèi)，每個區(qū)域內(nèi)包含d的一條線段，該區(qū)域內(nèi)點到該線段的距離均不超過到其他線段的距離。但是由于線段集的Voronoi圖的構(gòu)建很復(fù)雜，因此，本文只求出d2上相鄰線段的角平分線與折線d1的交點，并輔以增量式算法來定位對應(yīng)線段，因為線段集的Voronoi圖是由這些角平分線與線段構(gòu)成的。d1中線段的端點出現(xiàn)在哪兩條角平分線中間，該點對應(yīng)的線段即為該兩角平分線中間所夾的線段，計算時只要計算該點與該線段之間的最短距離，d2上其余線段可以排除。

該判斷方法如圖2所示，ss1與ss2的角平分線為t1,ss2與ss3的角平分線為t2,s1的端點O1在t1和t2之間，所以點O1對應(yīng)的線段是ss2。只需計算點O1到線段ss2的最短距離，ss1和ss3被排除，不需要參與計算。

下面將介紹計算相鄰線段的角平分線的具體方法。如圖3所示，AB,AC是兩條相鄰線段，A,B,C的坐標(biāo)已知，D是∠BAC的角平分線與BC的交點，DP,DQ分別是AB,AC上過點D的垂線，要求角平分線上點D的坐標(biāo)(x，y)。

圖3 角平分線算法示意圖

將k帶入v，可得

圖4 增量式算法示意圖

2.3.2 排除d1上無效點

在計算d1到d2單向Hausdorff距離的算法中，以d1中所有線段的端點為采樣點，從d1的一端開始依次計算每個點到d2上相對應(yīng)線段的最短距離。將d1上經(jīng)過前i個點的折線記為d1(i)，根據(jù)Hausdorff的定義可知下列關(guān)系成立：

將h(d1(i),d2)記為lowerBound。接下來繼續(xù)考察第i+1個點Pi+1，若d(Pi+1,d2)≤lowerBound，則第i+1個點Pi+1可被排除，h(d1(i+1),d2)仍然等于h(d1(i),d2)，即 lowerBound的值不變；若d(Pi+1,d2)>lowerBound，則lowerBound被重新賦值為d(Pi+1,d2)。這個過程實際是不斷提升下界lowerBound的過程，直至lowerBound正好等于h(d1,d2)。

3 實驗結(jié)果

本文所提出的方法適用于所有參數(shù)曲線，在此處將其分別應(yīng)用于B樣條曲線和NURBS曲線并進(jìn)行了實驗。圖5顯示了參數(shù)變化量e分別為0.02,0.005和0.002的3組B樣條曲線，并顯示了曲線r1和r2間產(chǎn)生Hausdorff距離的點的位置以及該點所對應(yīng)的線段，其中r1經(jīng)過實心黑點，r2經(jīng)過空心黑點，紫色圓點表示曲線上產(chǎn)生Hausdorff距離的點的位置以及該點所對應(yīng)的線段。表1給出了對應(yīng)的近似Hausdorff距離的計算結(jié)果，同時還給出了與未采用剪枝策略的計算方法在時間上的比較。

圖5 B樣條曲線實驗結(jié)果對比圖

表1 3組不同參數(shù)變化量的B樣條曲線間的近似Hausdorff距離

圖6顯示了參數(shù)變化量e分別為0.02,0.005和0.002的3組NURBS曲線，并顯示了曲線r1和r2間產(chǎn)生Hausdorff距離的點的位置及該點所對應(yīng)的線段，其中曲線上第i個控制頂點的加權(quán)值取i除以5的余數(shù)，r1經(jīng)過實心黑點，r2經(jīng)過空心黑點，紫色圓點表示曲線上產(chǎn)生Hausdorff距離的點的位置以及該點所對應(yīng)的線段。表2給出了對應(yīng)的近似Hausdorff距離的計算結(jié)果，以及與未采用剪枝策略的計算方法在時間上的比較。

圖6 NURBS曲線實驗結(jié)果對比圖

表2 3組不同參數(shù)變化量的NURBS曲線間的近似Hausdorff距離

從上面的實驗結(jié)果可以看出，采用本文所介紹的角平分線與增量式算法相結(jié)合的剪枝策略，在計算Hausdorff距離時與未采用剪枝策略的計算方法相比，計算時間大大減少了。在參數(shù)變化量e越小時，即折線越逼近曲線時，速度優(yōu)勢體現(xiàn)的越為明顯。

4 結(jié)論

本文首先從理論上論證了算法的合理性，并且對所有連續(xù)的參數(shù)曲線都是有效的，實驗表明，本方法計算速度快，逼近度高，基本解決了參數(shù)曲線的Hausdorff距離的計算問題，可以在幾何設(shè)計、圖像匹配、圖像識別等領(lǐng)域中廣泛應(yīng)用。

[1]Ahn Y J.Hausdorff distance between the offset curve of quadratic Bézier curve and its quadratic approximation [J].Communications-Korean Mathematical Society, 2007,22(4): 641-648.

[2]壽華好, 黃永明, 閆欣雅, 繆永偉, 王麗萍.兩條代數(shù)曲線間Hausdorff距離的計算[J].浙江工業(yè)大學(xué)學(xué)報,2013, 41(5): 574-577.

[3]李英明, 李旭健.兩條參數(shù)曲線間的Hausdorff距離的研究[J].華中師范大學(xué)學(xué)報(自然科學(xué)版), 2012, 46(3):270-274.

[4]Scharf L.Computing the Hausdorff distance between sets of curves [D].Diplomarbeit, Freie Universit?t Berlin,2003.

[5]Alt H, Scharf L.Computing the Hausdorff distance between curved objects [J].International Journal of Computational Geometry & Applications, 2008, 18(4):307-320.

[6]Elber G, Grandine T.Hausdorff and minimal distances between parametric freeforms in R2 and R3 [M].Springer Berlin Heidelberg, 2008: 191-204.

[7]Kim Y J, Oh Y T, Yoon S H, Kim M S, Elber G.Precise Hausdorff distance computation for planar freeform curves using biarcs and depth buffer [J].The Visual Computer, 2010, 26(6-8): 1007-1016.

[8]Chen Xiaodiao, Ma Weiyin, Xu Gang, Paul J C.Computing the Hausdorff distance between two B-spline curves [J].Computer Aided Design, 2010, 42(12):1197-1206.

[9]Chen Xiaodiao, Chen Linqiang, Wang Yigang, Xu Gang,Yong Junhai, Paul J C.Computing the minimum distance between two Bézier curves [J].Journal of Computational and Applied Mathematics, 2009, 229(1): 294-301.

[10]Chen Xiaodiao, Yong Junhai, Wang Guozhao, Paul J C,Xu Gang.Computing the minimum distance between a point and a NURBS curve [J].Computer-Aided Design,2008, 40(10): 1051-1054.

[11]白彥冰.自由曲線到自由曲線曲面Hausdorff距離近似值的計算[D].北京: 清華大學(xué), 2011.

[12]Johnson D E, Cohen E.A framework for efficient minimum distance computations [C]//1998 IEEE International Conference on Robotics and Automation,Leuven, Belgium, 1998: 3678-3684.

[13]Belogay E, Cabrelli C, Molter U, Shonkwiler R.Calculating the Hausdorff distance between curves [J].Information Processing Letters, 1997, 64(1): 17-22.