基于關(guān)系探測聚類的圖形自動接邊算法

2011-05-31 11:11:08周麗珠劉富東周義軍王光昇

城市勘測 2011年6期

周麗珠，劉富東，周義軍，王光昇

(1.天津市測繪院，天津 300381;2.天津市市政工程建設(shè)公司，天津 300100)

1 引言

地理信息是圖形信息和屬性信息兩類信息的集成，地理要素是地理信息的載體。現(xiàn)實中，所有的地理要素都是完整的個體。由于傳統(tǒng)習慣和用戶的需求，數(shù)字測圖仍采用分幅的圖幅設(shè)計方法，將連續(xù)的地表空間劃分為若干子空間，將圖幅邊線處完整的地理實體分割后放置在相鄰的圖幅中。而實際應用中，所需的數(shù)據(jù)中地理要素應為一個完整的個體，因此，數(shù)據(jù)的圖幅接邊不可避免，如何精確高效地解決圖幅接邊問題成為測圖領(lǐng)域中的一個研究課題，同樣也是GIS應用領(lǐng)域的一個研究課題。為此，筆者設(shè)計了一種基于關(guān)系探測聚類的圖幅自動接邊算法，并利用ArcGIS Engine 9.3二次開發(fā)組件實現(xiàn)了此算法，提高了接邊效率和準確度。

2 自動接邊關(guān)鍵技術(shù)

2.1 地物匹配

接邊線兩側(cè)的地物自動匹配是自動接邊算法的核心所在，本文從如下三個方面提高匹配的準確度:類別匹配，圖形匹配和屬性匹配。

(1)類別匹配，只有同類的地物才進行匹配。在數(shù)據(jù)表現(xiàn)上，以圖層為劃分單位。

(2)圖形匹配，一般以距離為指標，距離在閾值范圍內(nèi)的圖形要素才進行匹配。但是，面要素應排除點連接的情況，只保留線連接情況，如圖1所示。

(3)屬性匹配，綜合考慮屬性結(jié)構(gòu)和屬性值這兩類因素，完全相同，則匹配成功，否則失敗。

這三方面，每一方面都獨立于其他兩方面存在，假設(shè)每方面的匹配錯誤概率都為10%，那么，綜合考慮三方面后的匹配錯誤率為P，則P在區(qū)間［0，10%］內(nèi)，由“中心極限定理”可知，如果一個量是由許多微小的獨立隨機因素影響的結(jié)果，那么這個量就可看成符合正態(tài)分布的，可見這種匹配系統(tǒng)是可行且有效的。

圖1 面要素連接的兩種方式

2.2 空間聚類

空間聚類是將空間對象幾何劃分為由相似對象組成的多個簇的過程。同簇內(nèi)的對象之間具有盡可能大的相似性，而不同簇的對象之間則具有較大的差異性，從而有助于人們認識現(xiàn)象的整體分布模式。在GIS研究中，學者們將計算幾何技術(shù)、圖論方法與傳統(tǒng)的聚類分析方法結(jié)合提出了面向空間目標的空間聚類方法。

本文基于空間聚類方法的思想，聯(lián)系自動接邊的實際需求，設(shè)計出基于關(guān)系探測聚類的圖形自動接邊算法，方便接邊檢查，提高了運算效率。

2.3 合并要素

合并要素是將某類幾何要素合成一體，并保證其屬性不變。在理論上，這些幾何要素應完全吻合，實際中，由于數(shù)據(jù)的誤差，常常做不到這一點。如圖2所示，線要素間存在錯位和面要素間存在縫隙。這時，就需要采取一些方法來將幾何要素接合起來，使得圖形完全吻合［1］。

圖2 合并要素錯誤

解決這個問題通常有三種方式［2］:

(1)平均法

平均法是取圖形兩邊待接點的坐標均值作為接邊后的點的坐標。該方法簡單易行，適用于接邊誤差在精度允許范圍內(nèi)的各種直線、折線的接邊處理，容易實現(xiàn)接邊的全自動批量處理。

(2)強制法

強制法是把一條待接邊的待接點強制附和到另一條待接邊的待接點上。該方法主要用于用戶能明顯判斷出哪一條待接邊比另一條待接邊更準確、可靠，適合交互式的接邊處理。

(3)優(yōu)化法

無論采用平均法還是強制法，在邊界處都要產(chǎn)生一個拐點。一般拐點的拐角很小。但是如果待接邊明顯是一條直線邊的話，這個很小的拐角也影響圖形美觀。因此應考慮接邊后兩端線段仍要在一條直線上，既要共點，也要共線。

以上三種方式各有優(yōu)缺點，可根據(jù)實際情況決定采用哪種方式。本文采用了平均法的方式處理圖形誤差，實現(xiàn)自動接邊算法。而且線要素和面要素可以統(tǒng)一為一種方式進行處理，以面要素為例，如圖2中的面要素縫隙所示。

首先，找出面A上與接邊線距離在閾值范圍內(nèi)的點的集合Q={點a，點b}，同理，面B的點集合為W={點 c，點 d}。

其次，針對點集Q和W中的點元素進行匹配，如點a和點c分屬點集Q和W，并且點a和點c之間的距離在閾值范圍內(nèi)，則匹配成功。

最后，對匹配成功的點對，用平均法進行處理，之后進行要素合并。

3 自動接邊的邏輯思維

自動接邊算法實質(zhì)為確定其邏輯順序的過程，而自動接邊的邏輯思維大體可分為兩類，一是循環(huán)邏輯思維，一是階段性邏輯思維。

3.1 循環(huán)邏輯思維

循環(huán)邏輯思維是抽出具有共性的過程作為基本單元，循環(huán)基本單元，直到滿足臨界條件為止。現(xiàn)有的自動接邊算法大多采用循環(huán)邏輯思維，如圖3所示，設(shè)線要素1與線要素2接邊為一個過程A，即為接邊過程的基本單元。過程A通常包含“地物匹配”和“合并要素”兩個步驟，通過這兩個步驟可得到線要素1'，將線要素1'取代線要素1和2加入到選擇集中，更新地物和選擇集。重復過程A直到所有地物接邊完成。

圖3 循環(huán)邏輯思維

3.2 階段性邏輯思維

階段性邏輯思維是將過程分成各個階段，每個階段完成后才進行下一階段的操作。本文從實際應用出發(fā)，采用了這種邏輯思維方式進行自動接邊算法設(shè)計。利用關(guān)系探測聚類的方法，將自動接邊過程分成“地物聚類”和“合并地物”兩個階段。

地物聚類是將接邊線兩側(cè)需要接邊的圖形要素聚集成n個子類，如圖4所示，線段1、線段2和線段3為一個子類;線段4和線段5為另一個子類。

合并地物是依據(jù)地物聚類后的結(jié)果，利用ArcGIS Engine組件中 ITopologicalOperator接口的ConstructU-nion方法分別對各個子類中的圖形要素進行合并操作，得到接邊后的結(jié)果。

圖4 順序邏輯思維

3.3 兩種邏輯思維的比較

在自動接邊算法上，階段性邏輯思維與循環(huán)邏輯思維相比，具有兩種優(yōu)勢。

第一，在同一圖層數(shù)據(jù)的接邊中，“地物匹配”和“合并要素”徹底分離開來，也即將接邊檢查和實際接邊操作分離開來，接邊檢查只需進行地物聚類過程，提高了接邊檢查的速度。

第二，減少更新圖形數(shù)據(jù)和數(shù)據(jù)選擇集的次數(shù)，提高了算法的效率，而且選擇集中的要素數(shù)量越多，算法效率提升得越明顯。

4 基于關(guān)系探測聚類的自動接邊算法設(shè)計

本文按照階段性邏輯思維，融合空間聚類的思想，設(shè)計出基于關(guān)系探測聚類的自動接邊算法，其算法具體步驟如圖5所示。

4.1 算法流程

通過接邊線建立接邊要素的選擇集，對選擇集中的要素通過關(guān)系探測方法進行聚類，得到子類1，子類2，…，子類n，這其中，只有一個地理要素的子類屬于接邊錯誤，輸出到錯誤報表。之后分別對需要接邊的子類進行合并要素操作，得到接邊完成的數(shù)據(jù)。

圖5 自動接邊算法流程

4.2 關(guān)系探測聚類

(1)關(guān)系聚類算法設(shè)計

本文中，空間對象的相似性可理解為空間對象之間的關(guān)系定義，這種關(guān)系定義決定了聚類的結(jié)果。基于此，本文提出了一種關(guān)系探測聚類方法。根據(jù)實際需要定義關(guān)系函數(shù)，依據(jù)關(guān)系函數(shù)初始化關(guān)系鏈，再通過探測各個關(guān)系鏈達到聚類目的。

算法步驟如下:

輸入:幾何要素集 δ={幾何要素 a，b，c，d，e，……}

輸出:幾何要素子集 A，B，C，……

步1:根據(jù)實際要求，定義關(guān)系函數(shù)f(x，y)，f(x，y)表示幾何要素x與y的關(guān)系。

步2:對幾何要素集δ中每一個幾何要素都產(chǎn)生一個關(guān)系集 S(a)，S(a)定義如下式子，S(a)={x|f(x，a)=1，x∈δ}，其中 a 為幾何要素集 δ中任意一個幾何要素。

步3:關(guān)系探測得到一個聚類結(jié)果——幾何要素子集A。

搜索 S(a)，設(shè) S(a)={x，y，z，……}，此時子集A為空集，所以幾何要素 x，y，z，……都不屬于子集A，則將幾何要素 x，y，z，……加入到子集 A中，循環(huán)搜索對應于幾何要素 x，y，z，……的關(guān)系集 S(x)，S(y)，S(z)，……。如果S(x)中存在幾何要素α不屬于子集A，則將幾何要素α加入到幾何要素集A中，更新子集A，接著搜索S(a)，搜索過程同S(a)。關(guān)系集S(x)(x∈δ)完成搜索的標志為——幾何要素集A的個數(shù)不再增加。

步4:循環(huán)探測，得到所有聚類后的幾何要素子集。

設(shè)幾何要素b屬于幾何要素集δ，但幾何要素b對應的關(guān)系集沒有被探測，即不屬于任何一個現(xiàn)有的幾何要素子集A，B，C，……。用幾何要素b代替步4中的幾何要素a，重復步3，直到所有的幾何要素的關(guān)系集都被探測，得到最后聚類的結(jié)果——幾何要素子集A，B，C，……。

(2)定義自動接邊的聚類關(guān)系函數(shù)

根據(jù)本文所提的地物匹配原則，具體定義關(guān)系函數(shù) f(x，y)，如圖6所示。