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

林 意，薛思騏，郭婷婷

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

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

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

1 Hausdorff距離的定義

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

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

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

2.1 曲線離散

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

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

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

當(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距離來計(jì)算。

2.2 折線間的Hausdorff距離計(jì)算

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

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

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

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

2.3 剪枝策略

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

2.3.1 排除d2上無效線段

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

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

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

圖3 角平分線算法示意圖

將k帶入v，可得

圖4 增量式算法示意圖

2.3.2 排除d1上無效點(diǎn)

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

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

3 實(shí)驗(yàn)結(jié)果

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

圖5 B樣條曲線實(shí)驗(yàn)結(jié)果對比圖

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

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

圖6 NURBS曲線實(shí)驗(yàn)結(jié)果對比圖

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

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

4 結(jié)論

本文首先從理論上論證了算法的合理性，并且對所有連續(xù)的參數(shù)曲線都是有效的，實(shí)驗(yàn)表明，本方法計(jì)算速度快，逼近度高，基本解決了參數(shù)曲線的Hausdorff距離的計(jì)算問題，可以在幾何設(shè)計(jì)、圖像匹配、圖像識別等領(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ì)算[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距離近似值的計(jì)算[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.