一種構(gòu)建復(fù)雜平面圖形中軸的方法

王曉燕，羅 靜，郭光毅，王新生，李朋澤

（1.華中師范大學(xué) 城市與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079；2.湖北大學(xué) 資源環(huán)境學(xué)院，湖北 武漢 430062）

一種構(gòu)建復(fù)雜平面圖形中軸的方法

王曉燕1，羅 靜1，郭光毅2，王新生2，李朋澤2

（1.華中師范大學(xué) 城市與環(huán)境科學(xué)學(xué)院，湖北 武漢 430079；2.湖北大學(xué) 資源環(huán)境學(xué)院，湖北 武漢 430062）

提出了中軸矢量逼近構(gòu)建任意復(fù)雜平面中軸的方法。以一種簡(jiǎn)單、有效、穩(wěn)定的構(gòu)建任意平面圖形中軸的方法為例，采用不同密度的點(diǎn)逼近原始圖形邊界，構(gòu)建這些點(diǎn)集的約束Delaunay三角網(wǎng)，然后構(gòu)建Delaunay三角網(wǎng)的三角形外接圓圓心，圓心的軌跡即是原始圖形的中軸。數(shù)值實(shí)驗(yàn)表明，約束Delaunay三角網(wǎng)方法可以實(shí)現(xiàn)對(duì)各種復(fù)雜平面圖形中軸的良好逼近，并且隨著目標(biāo)圖形邊界上的點(diǎn)密度增加，得到的中軸越來越逼近精確中軸。

復(fù)雜平面圖形；約束Delaunay三角網(wǎng)；三角形外接圓圓心；中軸

中軸是空間圖形一種降維表達(dá)方法，能夠保留圖形的空間拓?fù)浣Y(jié)構(gòu)和幾何特征信息，并去除冗余信息。它同時(shí)也是平移、旋轉(zhuǎn)和尺度變換的不變量，因此被廣泛應(yīng)用于科學(xué)和工程領(lǐng)域，包括地理信息系統(tǒng)、人臉識(shí)別、圖像處理、計(jì)算機(jī)視覺和格網(wǎng)構(gòu)建等[1-5]。目前，有多種方法提取空間圖形的中軸[6-16]，但概括起來大致可以分為精確算法和逼近算法兩類。精確算法以圖形邊界曲線的方程表達(dá)式為基礎(chǔ)，通過空間幾何計(jì)算獲取中軸點(diǎn)坐標(biāo)以構(gòu)建中軸方程[7-9]。精確算法具有嚴(yán)格的空間幾何學(xué)基礎(chǔ)，是中軸算法理論的基石。但是一般來說，精確算法是較難實(shí)現(xiàn)的，主要原因是實(shí)際中的圖形無法嚴(yán)格使用數(shù)學(xué)表達(dá)式表達(dá)。因此，有些拓展的精確算法，在前處理中會(huì)首先將復(fù)雜的幾何對(duì)象化簡(jiǎn)并分解為簡(jiǎn)單幾何對(duì)象，然后構(gòu)建簡(jiǎn)單幾何對(duì)象的中軸，最后通過各部分中軸融合為最終的總中軸[9]。另外，精確算法對(duì)于洞的處理都比較復(fù)雜，其穩(wěn)健性和運(yùn)算效率等都是這種算法難以廣泛應(yīng)用的限制因素[2]。

在精確算法理論研究的基礎(chǔ)上，實(shí)際自然圖形中軸計(jì)算主要采用逼近算法，包括Voronoi圖方法[11-13]、Delaunay三角網(wǎng)方法[17,18]和柵格方法[5,19,20]等。柵格方法獲得的圖形中軸具有較高的精度，但需要較多的計(jì)算資源，包括數(shù)據(jù)存儲(chǔ)空間和CPU處理時(shí)間。Voronoi圖方法和Delaunay三角網(wǎng)方法以多邊形幾何為基礎(chǔ)，對(duì)于地理信息系統(tǒng)中用連續(xù)折線來表達(dá)圖形的數(shù)據(jù)結(jié)構(gòu)，具有良好的適用性。Voronoi圖和Delaunay三角網(wǎng)互為對(duì)偶，是空間幾何中的等價(jià)對(duì)象（圖1b、c），因此Voronoi圖方法和Delaunay三角網(wǎng)方法本質(zhì)上是一樣的。然而，對(duì)于地理科學(xué)中常見的復(fù)雜圖形，例如包括多種不規(guī)則洞，仍然缺乏一個(gè)快速簡(jiǎn)便的中軸構(gòu)建方法。

本文主要分析約束Delaunay三角網(wǎng)方法逼近圖形中軸的可靠性和算法效率。針對(duì)不同復(fù)雜圖形，以柵格方法獲得的圖形中軸為對(duì)照，對(duì)比約束Delaunay三角網(wǎng)方法得到的中軸與柵格方法得到的中軸的相合程度，并討論圖形邊界采樣密度對(duì)約束Delaunay三角網(wǎng)逼近中軸的影響。

1 方法描述

在圖形的離散化過程中，圖形的邊界通常采樣為二維平面上點(diǎn)的序列，也就是用點(diǎn)集來逼近圖形邊界線。由此，平面圖形所反映的結(jié)構(gòu)信息可以采用邊界點(diǎn)集的約束Delaunay三角網(wǎng)來表達(dá)[21]。

1.1 約束Delaunay三角網(wǎng)

Delaunay三角網(wǎng)是Voronoi圖的對(duì)偶圖，是將Voronoi圖中各多邊形單元的內(nèi)點(diǎn)（或稱為發(fā)生點(diǎn)）連接后得到一個(gè)布滿整個(gè)區(qū)域而又互不重疊的三角網(wǎng)結(jié)構(gòu)。與其他三角網(wǎng)相比，Delaunay三角網(wǎng)具有如下性質(zhì)：

1）三角網(wǎng)外圍邊界構(gòu)建的多邊形為點(diǎn)集的凸殼。

2）任意三角形的外接圓內(nèi)不包含其他點(diǎn)（這個(gè)性質(zhì)是Delaunay三角網(wǎng)的定義也稱為空外接圓規(guī)則）。

3）三角形最大程度地保持了均衡，避免狹長(zhǎng)形三角形的出現(xiàn)（最大最小角規(guī)則）。如果將三角網(wǎng)中的每個(gè)三角形的最小角進(jìn)行升序排列，則Delaunay三角網(wǎng)的排列得到的數(shù)值最大，從這個(gè)意義上講，Delaunay三角網(wǎng)是“最接近于規(guī)則化”的三角網(wǎng)。

4）性質(zhì)2）和3）保證了Delaunay三角網(wǎng)是最接近等角或等邊的三角網(wǎng)。

Delaunay三角網(wǎng)具有良好的特性，由于其最大程度地保持了均衡、避免狹長(zhǎng)形三角形的出現(xiàn)，是給定區(qū)域點(diǎn)集的最佳三角剖分[22]。本文提到的約束Delaunay三角網(wǎng)是指邊界約束的Delaunay三角網(wǎng)（圖 1b），增加的約束可能會(huì)破壞嚴(yán)格定義的Delaunay三角網(wǎng)性質(zhì)，例如出現(xiàn)狹長(zhǎng)三角形。但這一約束仍保持性質(zhì)1）和2）的成立，并且與Voronoi圖對(duì)偶的性質(zhì)不發(fā)生變化。因此約束Delaunay三角網(wǎng)方法被應(yīng)用于構(gòu)建圖形中軸[17]。

圖1 圖形中軸的算法原理示意圖[23]

1.2 約束Delaunay三角網(wǎng)方法對(duì)中軸的逼近

按照中軸的定義，平面幾何圖形的中軸是指內(nèi)切于幾何圖形邊界至少兩點(diǎn)的最大圓圓心的軌跡（圖 1a）?；诩s束Delaunay三角網(wǎng)構(gòu)建多邊形中軸線的基本原理是將復(fù)雜多邊形邊界線進(jìn)行離散化采樣，再以這些采樣點(diǎn)為基礎(chǔ)，構(gòu)建邊界約束Delaunay三角網(wǎng)（圖1b）。對(duì)三角網(wǎng)中的每個(gè)三角形單元作外接圓并定位其圓心。實(shí)際上，圖形的邊界約束Delaunay三角網(wǎng)的三角形外接圓圓心軌跡是圖形理論中軸的逼近（圖1d）。

2 結(jié)果與討論

2.1 約束Delaunay三角網(wǎng)與柵格方法中軸的對(duì)比

圖2左圖是采用柵格方法計(jì)算得出的精準(zhǔn)中軸，圖中的亮白色部分即是圖形精確中軸。圖2右圖是本文的約束Delaunay三角網(wǎng)方法得到的中軸（紅線）。比較圖2中左圖和右圖，可以看出它們之間存在良好的契合，說明對(duì)不同復(fù)雜程度的圖形約束Delaunay三角網(wǎng)方法得到的中軸都是圖形實(shí)際中軸的有效逼近。

圖2 中軸示意圖

2.2 圖形邊界采樣密度對(duì)中軸逼近精度的影響

圖3是采用434個(gè)點(diǎn)逼近邊界時(shí)產(chǎn)生的約束Delaunay三角網(wǎng)、三角形外接圓圓心與中軸，圖4是采用1 639個(gè)點(diǎn)逼近邊界時(shí)產(chǎn)生的約束Delaunay三角網(wǎng)、三角形外接圓圓心與中軸。對(duì)比這2個(gè)圖中的中軸發(fā)現(xiàn)，隨著圖形邊界點(diǎn)密度的增加，圖形邊界的約束Delaunay三角網(wǎng)的三角形外接圓圓心軌跡越來越逼近圖形的精確中軸，但會(huì)產(chǎn)生更多的中軸細(xì)分支，可以理解為噪聲。

圖3 粗采樣情形下自由圖形的約束Delaunay三角網(wǎng)（左）、三角形外接圓圓心（中）與中軸（右）

圖4 加密采樣情形下自由圖形的約束Delaunay三角網(wǎng)（左）、三角形外接圓圓心（中）與中軸（右）

2.3 圖形邊界采樣密度變化引起的中軸噪聲及其去除

在數(shù)字環(huán)境下，曲線不是由顯式數(shù)學(xué)函數(shù)來表達(dá)的，而是由離散坐標(biāo)點(diǎn)來表示的。為了使本文提出的方法能夠構(gòu)建更精確的中軸，必然要增加圖形邊界點(diǎn)密度，這樣在圖形邊界部分會(huì)呈現(xiàn)更多的邊界Delaunay三角形。例如，當(dāng)對(duì)圖3中目標(biāo)圖形的邊界選取434個(gè)點(diǎn)時(shí)（圖3，圖5a），在目標(biāo)圖形的一個(gè)凸角邊界處存在3個(gè)邊界三角形，存在3個(gè)三角形外接圓圓心，連接3個(gè)外接圓圓心時(shí)即存在1條中軸線（圖 5a）。但當(dāng)邊界上存在1 639個(gè)點(diǎn)時(shí)（圖4，圖5b），則在該凸角邊界處存在眾多的邊界三角形，也存在眾多的外接圓圓心，存在眾多細(xì)節(jié)分支中軸（圖6a）。按照中軸的定義，圖形中軸是與圖形不同邊（或邊的延長(zhǎng)線）上的兩個(gè)或兩個(gè)以上點(diǎn)等距離的點(diǎn)的軌跡，所以出現(xiàn)了眾多細(xì)小中軸。一般只需要提取主干中軸，這些毛細(xì)中軸（噪聲）需要在后處理中去除（圖6b）。

圖5 邊界三角形、邊界三角形外接圓圓心與中軸實(shí)例示意圖

圖6 自由形狀的中軸

3 結(jié) 語

構(gòu)建中軸的矢量逼近方法是簡(jiǎn)單、有效、可行的，可以實(shí)現(xiàn)各種復(fù)雜平面圖形中軸的構(gòu)建；在數(shù)字環(huán)境下，曲線不是由顯式數(shù)學(xué)函數(shù)來表示，而是由離散坐標(biāo)點(diǎn)來表示。隨著圖形邊界點(diǎn)密度的增加，在圖形邊界部分必然呈現(xiàn)更多的邊界約束Delaunay三角形，必然產(chǎn)生眾多細(xì)節(jié)分支的中軸，這種情況是符合中軸定義的。由于我們通常需要的是主干中軸，這些毛細(xì)中軸可以通過修剪去除。自動(dòng)修剪的方法則是未來進(jìn)一步研究的內(nèi)容之一。

[1] Blum H. A Transformation for Extracting New Descriptors of Shape. //Wathen-Dunn W. Models for the Perception of Speech and Visual form[M]. Cambridge: MIT Press, 1967

[2] Smogavec G, Zalik B. A Fast Algorithm for Constructing Approximate Medial Axis of Polygons, Using Steiner Points[J].Advances in Engineering Software, 2012(52): 1-9

[3] Cao L X, Liu J. Computation of Medial Axis and Offset Curves of Curved Boundaries in Planar Domain[J]. Computer-aided Design, 2008(40):465-475

[4] 周培德, 周忠平. 確定任意多邊形中軸的算法[J]. 北京理工大學(xué)學(xué)報(bào), 2000, 20(6): 708-711

[5] 胡鵬, 王海軍, 邵春麗. 論多邊形中軸問題和算法[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30(10): 853-857

[6] Aichholzer O, Aigner W, Aurenhammer F, et al. Medial Axis Computation for Planar Free-form Shapes[J]. Computer-aided Design, 2009(41): 339-349

[7] Cao L X, Ba W L, Liu J. Computation of the Medial Axis of Planar Domains Based on Saddle Point Programming[J].Computer-aided Design, 2011(43):979-988

[8] Choi W P, Lam K M, Siu W C. Extraction of the Euclidean Skeleton Based on a Connectivity Criterion[J]. Pattern Recognition, 2003, 36(3): 721-729

[9] Dorado R. Medial Axis of a Planar Region by Offset Selfintersections[J]. Computer-aided Design, 2009 (41): 1 050-1 059

[10] Culvera T, Keyser J, Manocha D. Exact Computation of the Medial Axis of a Polyhedron[J]. Computer Aided Geometric Design, 2004(21): 65-98

[11] Dey T K, Zhao W L. Approximate Medial Axis as a Voronoi Subcomplex[J]. Computer-aided Design, 2004(36): 195-202

[12] Dey T K, Zhao W L Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee[J].Algorithmica, 2004(38): 179-200

[13] Fabri R, Estrozi L F, Costa L F. On Voronoi Diagrams and Medial Axes[J]. Journal of Mathematical Imaging and Vision, 2002(17): 27-40

[14] Liu L, Chambers E W, Letscher D, et al. Extended Grassfire Transform on Medial Axes of 2D Shapes[J]. Computer-aided Design, 2011(43): 1 496-1 505

[15] Ramanathan M, Gurumoorthy B. Constructing Medial Axis Transform of Planar Domains with Curved Boundaries[J].Computer-aided Design, 2002(34): 619-632

[16] Remya E, Thiel E. Exact Medial Axis with Euclidean Distance[J].Image and Vision Computing, 2005(23): 167-175

[17] 艾廷華, 郭仁忠. 基于約束Delaunay結(jié)構(gòu)的街道中軸線提取及網(wǎng)絡(luò)模型建立[J].測(cè)繪學(xué)報(bào)，2000,29(4): 348-354

[18] 陳濤, 艾廷華. 多邊形骨架線與形心自動(dòng)搜尋算法研究[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2004, 29(5): 443-446

[19] 潘鵬, 賀三維, 吳艷蘭, 等. 曲邊多邊形中軸提取的新方法[J].測(cè)繪學(xué)報(bào), 2012, 41(2): 278-783

[20] 江嶺, 楊昕, 湯國(guó)安. 基于歐氏區(qū)域分配的面狀河流中軸線提取方法研究[J]. 測(cè)繪通報(bào), 2011(9): 21-24

[21] 潘鵬, 何津, 葉小雷, 等.圖的譜方法的空間目標(biāo)形狀表達(dá)研究[J]. 武漢大學(xué)學(xué)報(bào)：信息科學(xué)版, 2012, 37(11): 1 281-1 284

[22] 孫曉峰，李英成，王淼，等. 一種改進(jìn)的約束Delaunay三角網(wǎng)構(gòu)建算法及其在快速立體解譯平臺(tái)中的應(yīng)用[J]. 遙感信息，2012(1):9-12

[23] Guoy D, Erickson J. Automatic Blocking Scheme for Structured Meshing in 2D Multiphase Flow Simulation[C]. Proceedings of the 13th International Meshing Roundtable,2004

P208

B

1672-4623（2015）04-0120-03

10.3969/j.issn.1672-4623.2015.04.043

王曉燕，碩士，研究方向?yàn)镚IS在城市與區(qū)域規(guī)劃中的應(yīng)用。

2014-09-23。

項(xiàng)目來源：國(guó)家自然科學(xué)基金資助項(xiàng)目（41071240）。