平面簡單閉合曲線離散采樣與重建算法

范麗鵬， 王麗英， 龐明勇

(南京師范大學(xué)教育技術(shù)系，江蘇 南京 210097)

平面簡單閉合曲線離散采樣與重建算法

范麗鵬， 王麗英， 龐明勇

(南京師范大學(xué)教育技術(shù)系，江蘇 南京 210097)

提出一種魯棒的平面簡單閉合曲線離散采樣與重建算法。算法分為采樣過程和重建過程兩部分。采樣部分首先對平面閉合曲線均勻取點(diǎn)，然后計(jì)算各點(diǎn)到曲線所圍平面區(qū)域中軸的最近距離，最后根據(jù)所求距離確定采樣間隔，獲取采樣點(diǎn)集；重建部分首先構(gòu)建采樣點(diǎn)集的Delaunay三角剖分，然后從得到的三角形中選擇邊構(gòu)建初始化圖形，最后通過修改該圖形獲得重建圖形。實(shí)驗(yàn)表明算法得到的采樣點(diǎn)較少且能反映曲線的局部幾何特性，重建圖形能夠較好地表示原閉合曲線的形狀及走向。

曲線重建；離散采樣；無序點(diǎn)集；平面圖形

在圖形建模與幾何處理領(lǐng)域中，有關(guān)三維形體離散采樣與曲面重建的研究已開展得非常深入[1-2]。相對而言，平面曲線采樣與重建的研究工作大多集中于傳統(tǒng)的樣條曲線方法[3-4]，而基于計(jì)算幾何方法的研究文獻(xiàn)相對較少；另一方面，在圖形圖像技術(shù)的現(xiàn)實(shí)應(yīng)用中，有許多操作涉及對各類曲線進(jìn)行采樣與重建等計(jì)算[5]。因此對基于計(jì)算幾何方法的曲線采樣與重建進(jìn)行研究，具有重要的意義。

目前，對平面曲線進(jìn)行離散采樣的方法主要有3種：①柵格法[6]，首先將曲線所在的平面區(qū)域柵格

化，然后將曲線與柵格線的交點(diǎn)作為離散采樣點(diǎn)。由此得到的采樣點(diǎn)通常數(shù)據(jù)量較大，且采樣點(diǎn)集不能很好地反映曲線的局部幾何特性；②預(yù)測投影法[7]，即從曲線的某點(diǎn)開始，根據(jù)曲線在該點(diǎn)處的曲率大小，沿該點(diǎn)的切線方向前進(jìn)一小段得到預(yù)測點(diǎn)，然后將預(yù)測點(diǎn)投影到曲線上得到采樣點(diǎn)。由于該方法包括了一個(gè)投影過程，所以計(jì)算量較大；③ε-采樣法[8]，其處理對象為平面閉合曲線，采樣條件為：設(shè)曲線上一點(diǎn)到采樣點(diǎn)的最近距離為 d1，到曲線所圍平面區(qū)域中軸的最近距離為 d2。若一采樣點(diǎn)集使曲線上任意一點(diǎn)滿足 d1＜ε× d2，則其為所求點(diǎn)集，ε取值范圍為 0 ＜ε＜ 1。由于該方法設(shè)定了參數(shù)ε，對于不同的圖形均需要找到合適的ε值，才能滿足采樣條件，因此獲取的采樣點(diǎn)集充滿了不確定性。

平面曲線重建算法主要包括：文獻(xiàn)[9]提出了基于最小二乘法的平滑曲線重建，該方法通過對噪聲采樣點(diǎn)集進(jìn)行濾噪來實(shí)現(xiàn)平滑曲線的重建，其主要關(guān)注點(diǎn)是如何過濾采集數(shù)據(jù)中的噪聲；Amenta等[8]提出了基于β骨架與Voronoi圖的Crust算法，該算法先求取原始點(diǎn)集的Voronoi圖頂點(diǎn)，再對原始點(diǎn)集以及得到的頂點(diǎn)集進(jìn)行Delaunay三角剖分，最后通過選取三角剖分中三角形的邊來進(jìn)行曲線重建。該方法對原始點(diǎn)集的密度要求嚴(yán)格；Dey等[10]對該算法進(jìn)行了改進(jìn)，降低了對原始點(diǎn)集密度的要求。上述算法的重建對象是簡單的閉合光滑曲線，Althaus和Mehlhorn[11]進(jìn)一步對算法進(jìn)行了擴(kuò)展，使之能夠處理開放曲線，Dey和Wenger在文獻(xiàn)[12]中給出一種能夠處理多尖角圖形的算法變種。上述算法均需設(shè)定采樣參數(shù)，即對于不同的圖形均需找到合適的參數(shù)值，才能獲得適合其重建算法的采樣點(diǎn)集。

本文給出一種針對平面簡單閉合曲線的采樣與重建算法。其中采樣過程不需要設(shè)定參數(shù)，并且所得采樣點(diǎn)集較少且能較好地重建原始曲線。

1 算法梗概

本文算法由采樣與重建構(gòu)成。采樣過程是由平面簡單閉合曲線(圖1(a))得到表示該曲線的稀疏點(diǎn)集(圖1(b))；重建則由上述采樣過程所得到的采樣點(diǎn)集重建逼近原曲線的重構(gòu)圖形(圖1(c))。

采樣過程的主要步驟：

(1) 計(jì)算曲線所圍平面區(qū)域的中軸。中軸上任意一點(diǎn)，與被采樣曲線均存在兩個(gè)或兩個(gè)以上距離相等的點(diǎn)[13]。

(2) 對曲線均勻取點(diǎn)，并計(jì)算各點(diǎn)的局部特征大小。所謂的局部特征大小，是指點(diǎn)到中軸的最近距離[14]，如圖2(a)、(b)所示。

圖1 曲線的采樣與重建

圖2 矩形與圓的中軸、特征大小及采樣點(diǎn)

(3) 獲取采樣點(diǎn)。依據(jù)上述所求的局部特征大小，確定采樣間隔，獲取采樣點(diǎn)集，圖2(c)中圓心點(diǎn)即為采樣點(diǎn)。

(4) 添加采樣點(diǎn)。圖2(c)中兩圓相交點(diǎn)為可增加點(diǎn)。最終所得采樣點(diǎn)集只需從可增加點(diǎn)中選擇部分點(diǎn)添加到上述采樣點(diǎn)集中即可。

曲線重建過程的主要步驟：

(1) 逐次連接采樣點(diǎn)集(圖3(a))中距離最近的點(diǎn)，使其連成一個(gè)閉合圖形，并且使得該圖形中每個(gè)點(diǎn)至少連接兩條邊，如圖3(b)所示。

(2) 求點(diǎn)集的凸包，如圖3(c)所示，并求取圖3(b)的邊界，如圖3(d)中實(shí)線所示。其中，虛線為刪除的上述圖形(圖3(b))中的邊，實(shí)線為所求邊界；邊界內(nèi)部的點(diǎn)，即圖3(d)中兩條虛線相交的點(diǎn)，不屬于邊界點(diǎn)。

圖3 曲線重構(gòu)示意圖

(3) 修改上述邊界中鄰邊個(gè)數(shù)大于2的點(diǎn)，使得其鄰邊個(gè)數(shù)為2或0，如圖3(e)所示。圖3(d)中圓內(nèi)的點(diǎn)即為鄰邊個(gè)數(shù)大于2的點(diǎn)。

(4) 將鄰邊個(gè)數(shù)為0的點(diǎn)連接到修改后的邊界中，使其鄰邊個(gè)數(shù)為2，如圖3(f)所示。圖3(e)中圓內(nèi)的點(diǎn)即為鄰邊個(gè)數(shù)為0的點(diǎn)。

2 采樣過程

2.1 計(jì)算中軸

本文采用文獻(xiàn)[15]的方法提取平面封閉區(qū)域的中軸。該方法提出了一種基于Voronoi圖[16]的中軸提取方法，利用Voronoi圖頂點(diǎn)的連線模擬中軸。由于Voronoi圖的頂點(diǎn)為圖中邊的交點(diǎn)，且邊為曲線上相鄰點(diǎn)連線的垂直平分線，所以Voronoi圖頂點(diǎn)屬于中軸點(diǎn)。進(jìn)而將平面閉合曲線看作是一些點(diǎn)的集合，當(dāng)點(diǎn)集足夠密時(shí)，其Voronoi圖頂點(diǎn)的連線即可逼近曲線所圍區(qū)域的中軸。

2.2 計(jì)算局部特征大小

對原始曲線(圖4(a))均勻取點(diǎn)，然后計(jì)算各點(diǎn)到曲線所圍平面區(qū)域的中軸(圖4(b)中紫線)的最近距離，并將該距離記為該點(diǎn)的局部特征大小。由圖2(c)所示，在曲線上曲率較大的地方，點(diǎn)的局部特征較小，而在曲線較為平滑的地方局部特征較大。因此，根據(jù)曲線上所取各點(diǎn)的局部特征大小可獲得較少且能表示曲線局部幾何特性的采樣點(diǎn)集。

2.3 獲取采樣點(diǎn)

2.4 增加采樣點(diǎn)

由于所得采樣點(diǎn)不能較好地重建曲線，因此需要添加采樣點(diǎn)。添加條件：以任意采樣點(diǎn)p為圓心，以該點(diǎn)到其相鄰采樣點(diǎn)的距離為半徑畫圓，若在圓內(nèi)或圓上存在與p不相鄰的采樣點(diǎn)q，則在點(diǎn)p與該相鄰采樣點(diǎn)之間添加可增加點(diǎn)。為了使得添加的點(diǎn)數(shù)量較少，可通過設(shè)置一個(gè)數(shù)值，使得當(dāng)p與q之間的采樣點(diǎn)與可增加點(diǎn)的個(gè)數(shù)小于該數(shù)值時(shí)，不執(zhí)行操作。若該數(shù)值設(shè)置過大，則使得添加點(diǎn)過少，而不能重建圖形，若該數(shù)值設(shè)置過小，則會添加多余的點(diǎn)。因此需要不斷測試尋找到一個(gè)合適的數(shù)值，測試方法：首先設(shè)數(shù)值為1，即 q點(diǎn)不存在，然后獲取采樣點(diǎn)集，再對采樣點(diǎn)集進(jìn)行重建，若重建圖形能夠很好地逼近原曲線，則繼續(xù)增加數(shù)值，直到所生成的采樣點(diǎn)集不能很好地重建曲線為止，則取前一數(shù)值為所求數(shù)值。由于文中采樣算法和重建算法是順次執(zhí)行的，因此對于不同圖形，可由計(jì)算機(jī)自動地判定合適的取值大小。實(shí)驗(yàn)表明，多數(shù)圖形的數(shù)值可取6，且所得到的采樣點(diǎn)集更為稀疏且能很好地重建原曲線，圖4(e)中紅色的點(diǎn)即為所增加的點(diǎn)。

圖4 采樣過程

3 重建過程

3.1 構(gòu)建初始化圖

首先構(gòu)建采樣點(diǎn)集的Delaunay三角剖分[17]，由于得到的Delaunay三角形集合中存在較多的邊，所以需要從中選取部分邊來連接采樣點(diǎn)集進(jìn)而重建圖形。依據(jù)格式塔[18]的連續(xù)性和近似性原理可知，重建圖形為閉合圖形，每個(gè)點(diǎn)鄰邊個(gè)數(shù)均為2，且所有邊長的和最小。在構(gòu)建采樣點(diǎn)集的初始化圖過程中，涉及到閉合回路的問題，因此在圖5(a)中，展示了非閉合回路的示意圖，圖5(b)中展示了閉合回路的示意圖。

初始狀態(tài)時(shí)，所有采樣點(diǎn)均沒有相鄰邊，如圖6(a)所示。首先從Delaunay三角形集合(圖6(b))中選擇長度最短的邊，若該邊存在鄰邊個(gè)數(shù)小于2的端點(diǎn)，則選擇該邊來連接相應(yīng)的采樣點(diǎn)，否則舍棄；然后再從剩余邊中選擇長度最短的邊進(jìn)行上述判

斷；最后重復(fù)執(zhí)行上述操作，直到所有采樣點(diǎn)鄰邊個(gè)數(shù)均不小于2為止。此時(shí)，所得圖形中不存在鄰邊個(gè)數(shù)小于2的點(diǎn)，但是該圖形可能為非閉合圖形，如圖5(a)所示，因此需要再次添加邊，操作步驟為：先從Delaunay三角形集合中選擇長度最短的邊，若該邊連接兩個(gè)不連接的閉合回路(圖5(b)中最長的線)，則將該邊添加到上述非閉合圖形，并判斷連接后所得圖形是否為閉合圖形，若不是，則繼續(xù)選擇剩余邊中最短的邊，并重復(fù)執(zhí)行上述操作，直到整個(gè)圖形為閉合圖形為止，如圖5(b)所示。將所得圖形記為圖形A，如圖6(c)中陰影部分所圍圖形所示。

圖5 非閉合和閉合圖形示意圖

3.2 構(gòu)建初始化圖的邊界

由于圖形A中存在鄰邊個(gè)數(shù)大于2的點(diǎn)，因此需要對其進(jìn)行修改。為了更好地解決這個(gè)問題，可以先修改圖形A的邊界，然后再修改其內(nèi)部的點(diǎn)。通過刪除圖形A外部的Delaunay三角形可以求得圖形A的邊界，圖6(c)中空白區(qū)域的三角形即為圖形A外部的三角形。

為了找到圖形A外部的Delaunay三角形，可以先求得圖形A的凸包，即一個(gè)最小的多邊形，其所有點(diǎn)集均在該多邊形內(nèi)部或邊上，并且點(diǎn)集中任意兩點(diǎn)之間的連線均在多邊形內(nèi)部或邊上[19]，如圖6(d)中實(shí)線所示。獲得采樣點(diǎn)集的凸包后，逐一刪除凸包內(nèi)部包含凸包的邊或新添加的且不為圖形A的邊的三角形，可獲得圖形A的邊界圖形B，如圖6(e) 中陰影部分所圍圖形所示。

3.3 修改邊界上的點(diǎn)

由于圖形B中可能存在鄰邊個(gè)數(shù)大于2的點(diǎn)，如圖6(e)所示，所以需要對圖形B進(jìn)行修改，使得圖形B中所有點(diǎn)的鄰邊個(gè)數(shù)為2或0。

首先找到位于圖形B外部且包含鄰邊個(gè)數(shù)大于2的點(diǎn)的Delaunay三角形，記為集合T2。對于圖3(c)中的點(diǎn)來說，圖7(a)中包含邊為虛線的三角形即為T2中的三角形。由于存在多個(gè)這樣的三角形，且添加三角形的先后順序會影響重建的最終效果，因此可通過對T2中的每個(gè)三角形計(jì)算被添加后圖形B中所有邊的長度和的變化量，進(jìn)而確定T2中三角形被添加的先后順序。通常優(yōu)先添加變化量最小的三角形。添加三角形的過程如圖7(a)～(c)所示。添加三角形后，可能會出現(xiàn)3種情況：①不滿足T2要求的三角形仍然在集合T2中；②滿足T2要求的三角形不在集合T2中；③T2中一些三角形的變化量發(fā)生了變化。所以要分別對這3種情況進(jìn)行分析，并針對相應(yīng)的情況對T2進(jìn)行刪除、添加或修改的操作，直到集合T2為空為止。所得圖形記為圖形C，如圖6(f)中陰影部分所圍圖形所示。

3.4 修改邊界內(nèi)部的點(diǎn)

由于圖形C以及圖形B的內(nèi)部存在鄰邊個(gè)數(shù)為0的點(diǎn)，所以需要對其進(jìn)行修改，使其鄰邊個(gè)數(shù)為2。

首先在圖形C內(nèi)部的Delaunay三角形中找到一邊在C上且該點(diǎn)鄰邊個(gè)數(shù)為0的三角形，記為集合T0，圖7(d)中包含邊為虛線的三角形即為T0中的三角形。由于T0中存在較多的三角形，且刪除T0中三角形的先后順序會影響最終的重建效果，所以需要對T0中的每個(gè)三角形計(jì)算被刪除后圖形C中所有邊的長度和變化量，并依據(jù)變化量的大小確定T0中各三角形被刪除的先后順序。通常優(yōu)先刪除變化量最小的三角形。刪除三角形過程如圖7(d)～(e)所示。刪除三角形后，會出現(xiàn)2種情況：一種是不符合集合T0要求的三角形仍然存在；另一種是符合集合T0要求的三角形不在。所以要分別對這2種情況進(jìn)行分析，并針對上述情況對集合T0進(jìn)行刪除或添加。

當(dāng)集合T0為空時(shí)，即獲得重建圖形，如圖6(g)中陰影部分所圍圖形所示。

圖7 添加和刪除三角形過程

4 實(shí)現(xiàn)與結(jié)果

本算法在PC機(jī)上運(yùn)用VC6.0和OpenGL實(shí)現(xiàn)了采樣過程和曲線重建過程。實(shí)驗(yàn)結(jié)果如圖8所示。其中小松鼠和小白兔在增加采樣點(diǎn)時(shí)，計(jì)算機(jī)判定其最適合的數(shù)值為6，而海豚的數(shù)值為1，它們均展示了由閉合曲線獲得采樣點(diǎn)集，以及由采樣點(diǎn)集重建圖形的過程?？梢钥闯?，圖中的采樣點(diǎn)集能較好地反映原曲線的局部幾何特性，在距離較近但不相連接處采樣比較密集，而在其他處采樣比較稀疏。最終所得圖形均能夠較好地表示原曲線的形狀及走向。

圖8 松鼠、兔子、海豚采樣及重建過程

5 結(jié) 束 語

本文給出的基于平面簡單閉合曲線的采樣與重建算法，成功地實(shí)現(xiàn)了平面簡單閉合曲線的采樣及重建過程。大量實(shí)驗(yàn)表明，該算法能夠獲得更為稀疏且能反映曲線局部幾何特性的采樣點(diǎn)集，并且利用該點(diǎn)集能較好地重建出原曲線。由于本文算法只是針對簡單閉合曲線進(jìn)行采樣與重建，而對于未閉合以及更為復(fù)雜的曲線不具有很好的適用性，因此對于上述類型的曲線以及高維空間曲線的采樣與重建是今后需要考慮的問題。

[1] 厲玉蓉, 張彩明, 董付國. 三角網(wǎng)格上五次齊次代數(shù)曲面的重構(gòu)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2008, 20(9)： 1186-1190.

[2] 龐旭芳, 龐明勇. 點(diǎn)云模型自適應(yīng)增加采樣點(diǎn)算法[J].小型微型計(jì)算機(jī)系統(tǒng), 2010, 11(11)： 2265-2271.

[3] 黃童心, 王文珂, 張 慧, 等. 基于場分布的平面散亂點(diǎn)集B樣條曲線重建算法[J]. 工程圖學(xué)學(xué)報(bào), 2010, 31(2)： 73-83.

[4] 張 嫻, 張志毅, 田素壘, 等. 基于曲率分析的三次Bezier 曲線采樣方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013, 49(5)： 160-162.

[5] 駱 沛, 吳壯志, 夏春和, 等. 基于 e1范數(shù)最小化的非流形曲線族重構(gòu)[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(9)： 1917-1928.

[6] 譚昌柏, 周來水, 安魯陵, 等. 逆向工程中基于密集數(shù)據(jù)點(diǎn)的輪廓線重建技術(shù)[J]. 華南理工大學(xué)學(xué)報(bào), 2005, 33(5)： 32-37.

[7] Akkouche S, Galin E. Adaptive implicit surface polygonization using marching triangles [J]. Computer Graphics Forum, 2001, 20(2)： 67-80.

[8] Amenta N, Bern M, Eppstein D. The crust and the β-skeleton： combinatorial curve reconstruction [J]. Graphical Models and Image Processing, 1998, 60(2)：125-135.

[9] 龐明勇, 盧章平. 局部數(shù)據(jù)集與噪聲數(shù)據(jù)曲線的平滑過濾[J]. 礦山測量, 2001, (4)： 24-27.

[10] Dey T K, Mehlhorn K, Ramos E A. Curve reconstruction：connecting dots with good reason [C]//ACM. SOCG. Hong Kong, China, 2000： 229-244.

[11] Althaus E, Mehlhorn K. TSP-based curve reconstruction in polynomial time [C]//ACM/SIAM. SODA. San Francisco, CA, USA, 2000： 686-695.

[12] Dey T K, Wenger R. Fast reconstruction of curves with sharp corners [J]. International Journal of Computational Geometry & Applications, 2002, 12(5)： 353-400.

[13] Blum H. A transformation for extracting new descriptors of shape [J]. Models for the Perception of Speech and Visual Form, 1967, 19(5)： 362-380.

[14] Ruppert J. A new and simple algorithm for quality 2-dimensional mesh generation [C]//ACM/SIAM. SODA. Austin, USA, 1993： 83-92.

[15] Karimipour F, Ghandehari M. Voronoi-based medial axis approximation from samples： issues and solutions [M]. Transactions on Computational Science XX. Berlin Heidelberg： Springer, 2013： 138-157.

[16] Aurenhammer F. Voronoi diagrams： a survey of a fundamental geometric data structure [J]. ACM Computing Surveys, 1991, 23(3)： 345-405.

[17] 何 俊, 戴 浩, 謝永強(qiáng), 等. 一種改進(jìn)的快速Delaunay三角剖分算法[J]. 系統(tǒng)仿真學(xué)報(bào), 2006, 18(11)： 3055-3057.

[18] Ohrhallinger S, Mudur S P. Interpolating an unorganized 2D point cloud with a single closed shape [J]. Computer-Aided Design, 2011, 43(12)： 1629-1638.

[19] 劉 斌, 王 濤. 一種高效的平面點(diǎn)集凸包遞歸算法[J].自動化學(xué)報(bào), 2012, 38(8)： 1375-1379.

Discretely Sampling and Reconstructing Simple Planar Closed Curves

Fan Lipeng, Wang Liying, Pang Mingyong
(Department of Educational Technology, Nanjing Normal University, Nanjing Jiangsu 210097, China)

A robust algorithm is proposed for discretely sampling continuous planar curves and reconstructing the curves from the sampled point sets. The algorithm covers two processes, sampling and reconstruction. In the sampling part, the points are evenly obtained from a given planar closed curve, and then the distances are calculated between each point and the medial-axis of the planar area surrounded by the closed curve. Subsequently, the sampling intervals are decided by the distances and finds the sampling points. In the reconstruction part, a Delaunay triangulation is first built for the sampled points, and then edges are selected from the triangulation to build the initialize graph. Finally, the reconstructed curve is obtained by modifying the graph to a new version. Experiments show that the point sets sampled by our algorithm are locally adapted to the local geometric characteristics of the curves, and the reconstructed curves can approximate the original curves well.

curve reconstruction; discretely sampling; scattered points; 2D graphics

TP 391. 41

A

2095-302X(2015)04-0511-05

2015-01-14；定稿日期：2015-02-25

國家自然科學(xué)基金資助項(xiàng)目(41271383，60873175)；江蘇省現(xiàn)代教育技術(shù)研究課題資助項(xiàng)目(2014-R-33356)；江蘇省高校自然科學(xué)基金資助項(xiàng)目(11KJB520008)；江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項(xiàng)目

范麗鵬(1993–)，女，河南南陽人，碩士研究生。主要研究方向?yàn)閿?shù)字幾何處理。E-mail：funnypower@126.com

龐明勇(1968–)，男，安徽淮南人，教授，博士。主要研究方向?yàn)閹缀谓Ｅc數(shù)字幾何處理。E-mail：panion@netease.com