一種構建復雜平面圖形中軸的方法

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

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

一種構建復雜平面圖形中軸的方法

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

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

提出了中軸矢量逼近構建任意復雜平面中軸的方法。以一種簡單、有效、穩定的構建任意平面圖形中軸的方法為例，采用不同密度的點逼近原始圖形邊界，構建這些點集的約束Delaunay三角網，然后構建Delaunay三角網的三角形外接圓圓心，圓心的軌跡即是原始圖形的中軸。數值實驗表明，約束Delaunay三角網方法可以實現對各種復雜平面圖形中軸的良好逼近，并且隨著目標圖形邊界上的點密度增加，得到的中軸越來越逼近精確中軸。

復雜平面圖形；約束Delaunay三角網；三角形外接圓圓心；中軸

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

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

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

1 方法描述

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

1.1 約束Delaunay三角網

Delaunay三角網是Voronoi圖的對偶圖，是將Voronoi圖中各多邊形單元的內點（或稱為發生點）連接后得到一個布滿整個區域而又互不重疊的三角網結構。與其他三角網相比，Delaunay三角網具有如下性質：

1）三角網外圍邊界構建的多邊形為點集的凸殼。

2）任意三角形的外接圓內不包含其他點（這個性質是Delaunay三角網的定義也稱為空外接圓規則）。

3）三角形最大程度地保持了均衡，避免狹長形三角形的出現（最大最小角規則）。如果將三角網中的每個三角形的最小角進行升序排列，則Delaunay三角網的排列得到的數值最大，從這個意義上講，Delaunay三角網是“最接近于規則化”的三角網。

4）性質2）和3）保證了Delaunay三角網是最接近等角或等邊的三角網。

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

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

1.2 約束Delaunay三角網方法對中軸的逼近

按照中軸的定義，平面幾何圖形的中軸是指內切于幾何圖形邊界至少兩點的最大圓圓心的軌跡（圖 1a）。基于約束Delaunay三角網構建多邊形中軸線的基本原理是將復雜多邊形邊界線進行離散化采樣，再以這些采樣點為基礎，構建邊界約束Delaunay三角網（圖1b）。對三角網中的每個三角形單元作外接圓并定位其圓心。實際上，圖形的邊界約束Delaunay三角網的三角形外接圓圓心軌跡是圖形理論中軸的逼近（圖1d）。

2 結果與討論

2.1 約束Delaunay三角網與柵格方法中軸的對比

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

圖2 中軸示意圖

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

圖3是采用434個點逼近邊界時產生的約束Delaunay三角網、三角形外接圓圓心與中軸，圖4是采用1 639個點逼近邊界時產生的約束Delaunay三角網、三角形外接圓圓心與中軸。對比這2個圖中的中軸發現，隨著圖形邊界點密度的增加，圖形邊界的約束Delaunay三角網的三角形外接圓圓心軌跡越來越逼近圖形的精確中軸，但會產生更多的中軸細分支，可以理解為噪聲。

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

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

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

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

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

圖6 自由形狀的中軸

3 結 語

構建中軸的矢量逼近方法是簡單、有效、可行的，可以實現各種復雜平面圖形中軸的構建；在數字環境下，曲線不是由顯式數學函數來表示，而是由離散坐標點來表示。隨著圖形邊界點密度的增加，在圖形邊界部分必然呈現更多的邊界約束Delaunay三角形，必然產生眾多細節分支的中軸，這種情況是符合中軸定義的。由于我們通常需要的是主干中軸，這些毛細中軸可以通過修剪去除。自動修剪的方法則是未來進一步研究的內容之一。

[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]. 北京理工大學學報, 2000, 20(6): 708-711

[5] 胡鵬, 王海軍, 邵春麗. 論多邊形中軸問題和算法[J].武漢大學學報：信息科學版，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結構的街道中軸線提取及網絡模型建立[J].測繪學報，2000,29(4): 348-354

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

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

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

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

[22] 孫曉峰，李英成，王淼，等. 一種改進的約束Delaunay三角網構建算法及其在快速立體解譯平臺中的應用[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

王曉燕，碩士，研究方向為GIS在城市與區域規劃中的應用。

2014-09-23。

項目來源：國家自然科學基金資助項目（41071240）。