一種提取彎曲單元對稱軸的方法

吳 凱 馬藝文 張曉莉

(1. 濟南市勘察測繪研究院, 山東 濟南 250013; 2. 武漢市國土資源和規劃信息中心, 湖北 武漢 430014)

0 引言

線狀要素和面狀要素都是地圖內容的最重要的組成部分。多邊形面狀目標,由于其結構的特殊性,可以看作是一種閉合曲線。而曲線的結構化信息主要是通過彎曲特征來表現的。曲線彎曲的特性研究已有多種方法：羅廣祥[1]利用坐標單調性劃分彎曲段;艾廷華、羅廣祥、翟仁健[2-4]利用Delaunay三角網模型進行彎曲特征研究;李洪省[5]提出基于迭代刪除法的彎曲層次關系建立方法;周培德[6]利用計算幾何研究凸多邊形軸線問題等。實際上對于彎曲單元特性的研究中,彎曲對稱軸是一個十分重要的特征參量,彎曲對稱軸的長度在某種意義上可以理解為彎曲單元的深度,而彎曲深度是彎曲特征的一個重要指標。

1 彎曲單元的劃分

根據Gestalt心理學原理,人們對彎曲形狀的空間認知具有對稱性、層次性原則,在深度上表現為典型的大彎曲套小彎曲層次結構,線狀地物的結構化綜合表現為彎曲由底層到高層的化簡、合并、刪除,從而保證目標的主體結構不致破壞,而低層次的細節部分又得到化簡[7]。

現有的彎曲單元劃分方法一般是基于彎曲的拐點[8],因為在拐點處曲線的單調性發生改變,因此這種方法也就是按照坐標的單調性進行彎曲單元劃分。然而,基于拐點劃分彎曲單元忽略了彎曲劃分的一個重要原則：對稱性。并且基于拐點的彎曲單元劃分都只是對節點進行的操作,而彎曲節點和彎曲曲線本身還是有很大的不同,用彎曲上的節點來代表彎曲曲線還是有很多不足之處。除此之外,基于拐點的彎曲單元劃分方法對于彎曲深度、對稱軸的提取也是基于彎曲節點實現：彎曲的最深點多利用Douglas-Peucker算法實現;彎曲深度采用彎曲最大垂距的定義,即某一彎曲上除起點和終點之外的點與起點和終點連線之間的最大距離。但是這種方法對于特殊形態的彎曲,例如螺旋型、偽對稱、迂回型彎曲,不具有通用性。黎茂則針對Douglas-Peucker算法沒有考慮大彎曲的形狀,對大小彎曲采用同樣的處理手段、U型彎曲在化簡后變成V型彎曲的問題,提出采用斜拉式彎曲劃分的方法[9],但這種方法仍然沒有考慮彎曲的對稱性原則。

一條曲線可以劃分為多個彎曲單元,如果一個彎曲單元內部還嵌套有若干彎曲單元則稱其為復合型彎曲;如果一個彎曲單元內部不再嵌套有彎曲單元則稱其為簡單型彎曲。對于彎曲對稱軸的提取可以先對簡單彎曲單元進行操作,復合型彎曲的對稱軸則是多個簡單型彎曲單元對稱軸的集合。

實際上,彎曲的劃分受觀察尺度的影響,本文對于彎曲單元的劃分采用距離變換的方法,因而彎曲對稱軸的詳細程度可以由距離變換的尺度來控制。基本原理為：對原始彎曲單元進行某一尺度的內距變換,對得到的內距變換圖再進行相同尺度的外距變換即實現了這一尺度下的粘連變換,粘連變換的結果與原始彎曲單元疊加便可得到這一尺度對應的所有彎曲單元。選擇多個距離變換尺度,進行上述操作便得到不同尺度下的彎曲單元。不同尺度下的彎曲單元詳細程度不同,所對應的彎曲對稱軸的詳細程度也就不同。

2 彎曲對稱軸的基本概念

中軸(Medial Axis)可以認為是精確定義的骨架。一塊連續二值圖的骨架概念首先由Blum提出,當時他稱骨架為Medial Axis,后來稱為對稱軸(Symmetric Axis)[10]。

中軸在二維平面上兩點之間的中軸是到兩點距離相等的點的集合,是兩點連線的垂直平分線;同理,兩線間的中軸是到兩線距離相等的點的軌跡,兩線平行時中軸是兩線之間到兩線距離相等的點集組成的平行線,兩線相交時則為兩線夾角的角平分線;點與線的中軸是以點為焦點,以線為準線的拋物線[11]。在以上情況中都有距離歸屬的概念,中軸將平面一分為二,與點、線分別相鄰接的半平面為到其距離最小的點的集合,在距離變換的角度,就是兩個半平面分別歸屬于各自的距離發生源。這些都是平面幾何或解析幾何的內容,是進一步研究的基礎。彎曲對稱軸有時也稱為彎曲骨架線,骨架能簡單直觀地描述物體的拓撲和形狀信息,是一種性能優良的幾何特征。一般而言,二維圖形的骨架由曲線連接而成[12-13]。

本文在綜合中軸和骨架線的概念之上,提出彎曲對稱軸的定義：彎曲對稱軸就是彎曲單元內部到彎曲輪廓線距離相等的所有點的集合。

3 基于障礙距離變換的彎曲單元對稱軸提取方法

距離變換是將包含實體特征和空間背景兩種像元的二值圖像轉變為距離圖像的變換。在距離圖像中,每一個像素值表示該像素到其最近的一個實體像素的距離,具體體現為每個實體的距離波不斷地往外空間進行擴張,直到與鄰近實體的距離波相遇。當考慮障礙空間問題時,上述距離變換則應擴展為障礙距離變換(distance transformation with obstacles,DTO),即在障礙空間中進行距離變換。空間中有生成元還有若干障礙,生成元傳播的距離波需要繞過障礙進行傳播。由以上定義可知,一般意義上的距離變換可以看作是障礙物個數為零的障礙距離變換[14-15]。

3.1 方法原理

基于DTO方法提取彎曲對稱軸本質上是等距點的軌跡問題,這是與距離問題相對應并廣泛運用的一類重要問題。地理空間中點、線、面實體之間的等距點軌跡按實體作用范圍劃分整個二維平面,這個作用范圍實際上是V圖。而這些等距點的軌跡就是這些多邊形的邊界。在此問題中,倘若有一些自然的或者人為的障礙,那么上述的Voronoi多邊形及其邊界就該避讓開它們,即形成有條件的Voronoi多邊形及其邊界,也稱為障礙Voronoi多邊形及其邊界。

因此求解彎曲對稱軸,也就是求解等距點的軌跡,首先應將彎曲單元劃分為兩部分,然后求這兩部分在彎曲單元內部的等距點軌跡,這就涉及彎曲單元劃分的分界點問題,彎曲對稱軸確定的關鍵即是尋找彎曲的合理分界點,理論上來講這個分界點應該取彎曲單元的最深點。對于彎曲最深點的定義一般采用最大垂距點的定義,這種方法實際上運用的是道格拉斯算法[1,5],具體實施過程為：對每一個彎曲單元的首末點虛連一條線,如圖1所示,在圖1(a)中連接AB,求彎曲上所有點與直線AB的距離,得到最大距離值對應的點P,顯然點P為彎曲最大垂距點。這種方法對于一般的彎曲來講是可行的,但是對于特殊形狀的彎曲,如螺旋型、迂回型、偽對稱型等,彎曲最深點用最大垂距點定義并不理想。圖1(b)所示的螺旋型彎曲,若按照最大垂距點定義彎曲最深點即為P點,但從人眼識別的結果應為點O。

(a)彎曲最大垂距點 (b)螺旋型彎曲最大垂距點和最深點

綜合一般彎曲和特殊彎曲的形態特征,我們發現彎曲最深點也可以理解為到彎曲基線即彎曲首末點連線距離最遠的點,基于此原理,本文提出了利用DTO來求取彎曲最深點的方法。以彎曲單元基線作為距離變換的生成元,彎曲單元內部設為距離變換的空間,外部設為障礙空間,則距離波傳播的最遠位置即為距離最大值點,也即彎曲最深點。然后以識別出的彎曲最深點為分界點,將彎曲單元劃分為左右兩部分,對左右兩部分實施距離變換,彎曲單元內部兩個距離波的沖擊處即為等距點軌跡,也即彎曲對稱軸。

3.2 具體步驟

利用DTO提取彎曲對稱軸的流程如圖2所示,主要包括以下5個步驟：

以螺旋型彎曲提取對稱軸為例,如圖3所示。

(1)連接彎曲單元的兩端點得到彎曲基線,如圖3(a)所示。

(2)彎曲基線和原始彎曲線得到閉合曲線,將此閉合曲線轉換成面,并進行柵格化。將得到的柵格形式的彎曲單元區域進行柵格重分類：彎曲單元內部設為距離變換空間,值為1;彎曲單元外部設為障礙空間,值為NoData。如圖3(b)即為柵格重分類的結果圖,黑色區域為彎曲外部,即障礙。

(3)將重分類后的柵格圖層作為成本柵格數據(CostRaster),將輔助基線作為DTO的生成元(Source),進行DTO,結果如圖6(c)所示,DTO的結果也是一個柵格圖,彎曲內部的距離值隨著顏色的加深越來越大,即靠近基線AB處距離值最小。

(4)提取DTO結果的最大值點,如圖3(d)所示。然后用距離最大值點打斷原始彎曲單元線。

(5)建立彎曲兩側線段的V圖,提取V圖的邊界即得到彎曲單元的對稱軸。如圖3(e)所示。

圖2 DTO算法提取彎曲對稱軸流程圖

利用DTO的方法還可以很方便地提取迂回型和偽對稱型彎曲的對稱軸,結果如圖4和圖5所示。

(a)DTO圖 (b)最深點和對稱軸

(a)DTO圖 (b)最深點和對稱軸

4 結束語

本文通過障礙距離變換實現了彎曲對稱軸的提取。實驗證明,利用DTO方法提取彎曲對稱軸能保證彎曲的對稱性、層次性特點;曲線彎曲的結構表達在制圖綜合中也具有重要的意義;并且根據對稱軸和中軸的相似性,此方法還可以推廣到多邊形中軸線的提取以及各種幾何體的中軸提取中。