探測信息模型支持下的點注記配置方法

喬俊軍，胡馮偉，張海文,2

(1. 武漢大學測繪學院，湖北 武漢 430079； 2. 深圳市勘察研究院有限公司，廣東 深圳 518026)

?

探測信息模型支持下的點注記配置方法

喬俊軍1，胡馮偉1，張海文1,2

(1. 武漢大學測繪學院，湖北 武漢 430079； 2. 深圳市勘察研究院有限公司，廣東 深圳 518026)

摘要：針對點注記自動配置問題，首先對注記備選位置及其優先級進行了分析與研究，提出了一種自主探測算法，該方法的探測信息模型顧及了背景要素壓蓋、注記的指代明確、配置均勻，以及盡量配置到所屬的行政區劃等原則；在此基礎上，通過初始配置獲得全局較優注記位置，再配置獲得局部最優注記位置，沖突壓蓋檢測獲得全局最優注記位置；對兩個試驗樣區進行了注記配置試驗，結果表明在注記難度增加的情況下，該方法仍能獲得較好的注記效果。

關鍵詞：壓蓋權重；備選位置；探測信息量；探測區；注記配置

隨著國家1∶100萬、1∶50萬、1∶25萬基礎地理信息數據庫建設完畢，為自動生產等比例尺或通過制圖綜合生產小比例尺地圖創造了有利條件。然而注記配置尤其是點注記配置制約了地圖的生產效率。究其原因，一是注記配置的工作量很大，約占整個地圖生產的59%[1];二是注記配置看似是一項再簡單不過的工作，但隨著對問題認識的深入，其配置過程中的復雜性、多變性、實施的靈活性及得到滿意成果的困難性成為了制圖自動化的難點之一。因此注記自動配置便成為制圖自動化的一個亟待解決的問題。

20世紀70年代，Yoeli最先開展了注記自動配置研究[2]，40多年來，國內外學者針對注記自動配置研究已經取得了不少研究成果。在點注記配置方面，游漣根據最小注記尺寸，將整個地圖空間分成若干地圖子空間，巧妙地將注記之間的壓蓋問題轉化為子空間的重疊問題，使得注記配置的質量優于當時所見的文獻[3]。樊紅基于神經網絡模型求取點要素注記配置的最優解，有效克服了傳統沖突-回溯法效率不高的問題[4]。Yammoto成功地將禁忌搜索(TS)算法應用于點注記自動配置的過程，并取得了較好的注記效果[5]。鄭春燕通過引入地圖目標等級，加入注記本文不能壓蓋點要素這一限制條件，建立了一個更為完善的目標函數，對TS算法進行了完善，并通過試驗證明了TS算法比當時的一些智能優化算法效果顯著[6]。彭珊鸰將蟻群算法引入到點注記配置的過程中，并證明了此法具有較高的搜索效率，基本解決了注記的沖突問題。

但目前所見的點注記配置算法，包括目前最好的maplex智能標注系統，都較少考慮注記的指代明確、配置均勻及注記盡量配置到所屬的行政區劃內等規則。因此，本文提出一種自主探測算法，該方法的探測信息模型可顧及背景要素壓蓋、注記的指代明確、配置均勻及盡量配置到所屬的行政區劃等原則；通過利用該模型，計算各備選位置的探測信息量，結合備選位置的優先級，確定最終注記位置。

一、點注記配置理論

關于點注記配置規則，文獻[7—8]已進行了詳細介紹，下面重點探討注記備選位置及其優先級問題。

1. 注記備選位置

Francois[8]將注記配置算法的流程分為3步：①搜索注記備選位置；②對注記備選位置進行評價；③選擇最優注記位置。從這3步中可以看出，注記備選位置直接關系到注記質量的優劣。

若注記備選位置與點要素可接受的最近距離為r1，可接受的最遠距離為r2，則形成的備選區如圖1所示。

圖1　注記備選區

注記備選區可看成由無數個圓組成的集合，這些圓又稱為備選圓。在計算機中，與利用有限個點描述一段光滑曲線的原理相似，本文也利用有限個備選位置來描述備選圓，如圖2所示。

2. 備選位置優先級

一個備選圓可由多個備選位置來描述，備選位置越多，備選圓描述得越精確。傳統的8個備選位置較難精確描述備選圓，本文對其進行了擴展。以3字數注記為例，用40個備選位置來描述備選圓，其優先級順序如圖2所示。

圖2　備選位置優先級

圖2(b)中，(5)～(12)備選位置是在圖2(a)(2)、(3)備選位置的基礎上進行水平平移的結果，每次平移半個字符。各備選位置的優先級遵循以下原則：

1) 半徑小的備選圓上的備選位置優先級高于半徑大的備選圓，因為前者的備選位置與點要素距離更近，指代性更好。

2) 在同一備選圓上，備選位置與基本備選位置越近，優先級越高，如(13)和(21)備選位置，因(13)更接近第一備選位置，因此(13)的優先級更高。

3) 在同一備選圓上，假設存在兩個備選位置B1和B2，基本備選位置J1和J2，并且B1與J1的接近程度和B2與J2的接近程度相同，若J1的優先級高于J2，那么B1的優先級高于B2。如圖2中(13)和(15)備選位置。

4) 在同一備選圓上，若兩個備選位置與同一基本備選位置的接近程度一樣，那么看其與其他基本備選位置的接近程度，如(13)、(14)備選位置，兩者與第一基本備選位置的接近程度一樣，但由于(13)更接近第二基本備選位置，因此(13)的優先級更高。

二、自主探測算法

1. 地圖要素空間分布量化

根據注記規則，在保證注記指代清晰的前提下，絕大部分要考慮注記與要素的壓蓋問題。因此，本文以賦予壓蓋權重的方式將地圖各要素的重要性進行量化。假設經緯線要素的壓蓋權重W=1，省界的壓蓋權重W=10，那么注記與10條經緯線壓蓋等同于與1條省界壓蓋，這表明壓蓋了10條以下經緯線的注記位置要優于壓蓋了1條省界的注記位置。當某個要素的壓蓋權重為0時，注記可以任意壓蓋該要素。

地圖類型不同，則權重設置有所不同，同一地圖，不同的壓蓋權重，其注記質量也會不同。因此，如何給每個圖種確定唯一的權重，以及如何實現注記質量的最大化，假設最大權重為Wmax，最小權重為Wmin，權重設置應符合以下原則：

1) 對于絕對不能壓蓋的要素，其壓蓋權重應設為最高Wmax。

2) 對于需要考慮壓蓋的，且重要性最低的要素，其壓蓋權重應設為最低Wmin。

3) 其他需要考慮壓蓋的要素權重，應介于Wmax與Wmin之間，具體數值依賴于制圖目的、要素內容等條件。

2. 探測信息模型

(1) 注記初始配置的探測信息模型

假設以某一點要素P為中心，以R為搜索半徑，搜索到n個點要素，P點到這n個點的距離分別為si(i=1,2,…,n)，如圖3(a)所示。同時P點第j個備選位置(矩形)的幾何中心到這n個點的距離分別為li，如圖3(b)所示。那么該備選位置的探測信息量(detection information)DIj為

(1)

式中，WP為搜索到點的壓蓋權重；K為備選位置探測到的注記種類數；mZ,i為備選位置探測到的第i類注記的數量；W為相應的壓蓋權重。

圖3　初始配置的探測信息量

(2) 注記再配置的探測信息模型

假設存在一點要素P，點P的第j個備選位置上存在第一、二、三探測區A、B、C，A探測非注記要素，B探測注記要素，C探測點要素，如圖4所示(夸張顯示)。則該備選位置的探測信息量DIj為

(2)

圖4　三探測區

式中，K1為A探測到的線、面(不包括行政區劃)種類數之和；mi為相應的第i類要素的個數；K2為B探測到的注記種類數；mB,i為相應的第i類注記的個數；K3為A探測到的點種類數；K4為C探測到的點種類數；mA,i和mC,i分別為相應的第i類點要素的個數；W為相應要素類的壓蓋權重，其中Warea為行政區劃的壓蓋權重；d為降權系數，d>1；Sj為A與當前點要素所在的行政區劃相交的面積；SA為A的面積；[]表示是否添加該項值。d值作用如圖5所示。

圖5　d值的作用

p1、p2、p3為同類點要素，圖5(a)中的兩個圖形為p1點第二備選位置上的A、C探測區，圖5(b)中的兩個圖形為p1點第一備選位置上的A、C探測區。若d≤1，則DI1≤DI2，則p1點的第一備選位置為最優注記位置，致使p1點的注記壓蓋p3點，如圖5(b)所示。這是不允許的。因此令d>1，即降低C探測區探測到的點要素壓蓋權重，則DI1>DI2，從而能夠使p1點的注記配置到第二備選位置上，避免壓蓋點要素。

3. 自主探測算法

算法的基本思想是二次配置加一次檢測。

初始注記配置即根據式(1)計算各備選位置的探測信息量，確定初始注記位置。由式(1)可知，li越小，DIj就越大，因此初始注記配置可使得注記最大程度地遠離密集的點要素，從而提供了一個較好的初始注記位置。

注記再配置即根據式(2)計算各備選位置的探測信息量，確定局部最優注記位置，其中第一探測區探測非注記要素，范圍最小，其主要作用是顧及要素壓蓋，保證圖面清晰；第二探測區探測注記要素，范圍較大，其主要作用是確保注記不擁擠，如圖6所示，如果圖6(a)中“灣里區”位置的第二探測區探測到其下方很近的距離存在其他注記，從而能夠避免圖6(a)實現圖6(b)的注記效果；第三探測區探測點要素，范圍最大，其主要作用是確保注記指代準確，如果圖6(c)中“金城鎮”位置的第三探測區探測到其右側很近的距離存在其他點要素，從而能夠避免圖6(c)實現圖6(d)的注記效果。

由于點要素密集程度未知，注記再配置并不能完全保證零沖突及注記不壓蓋點要素，因此還需進行沖突壓蓋檢測。

自主探測算法流程如下：

1) 選擇考慮壓蓋的地圖要素，并根據壓蓋權重的設置原則進行權重設置。

圖6　第二、三探測區作用

2) 設置探測參數：一是點符號尺寸，這與地圖設計有關；二是注記初始配置中的搜索半徑R；三是注記再配置中的d值。

3) 注記初始配置：首先選取第一個點要素，根據備選位置的優先級，在第一備選位置上只生成第一探測區，第一探測區的尺寸由下式計算得到(單位為m)

(3)

式中，H為探測區的高度；W為探測區的寬度；3.527 78×10-4為ArcGIS中1∶1比例尺的字號為1的文字的高度；z為注記字大；scale為地圖比例尺;n為注記字數。

然后根據搜索半徑R搜索點要素，并利用式(1)計算當前備選位置的探測信息量。當計算出當前點要素所有備選位置的探測信息量后，選取其中最小值。若該值唯一，相應的備選位置就是初始注記位置；若不唯一，相應優先級最高的備選位置就是初始注記位置。其他點要素依次類推。

4) 注記再配置：首先選取第一個點要素，并刪除該點要素的初始注記。然后根據備選位置的優先級，在第一備選位置上生成第一、二、三探測區，接著通過空間分析探測地圖要素，并利用式(2)計算當前備選位置的探測信息量。當計算出當前點要素所有備選位置的探測信息量后，選取其中最小值。若該值唯一，相應的備選位置就是局部最優注記位置；若不唯一，相應優先級最高的備選位置就是局部最優注記位置。3個探測區的形狀如圖7所示(夸張顯示)。其中,D為最小點符號的外接圓直徑，其他點要素依次類推。

5) 沖突壓蓋檢測：首先選取第一個注記，通過空間分析判斷該注記是否存在沖突或壓蓋了點要素。如果存在，則刪除該注記，對相應的點要素進行注記再配置，過程同步驟4)；如果不存在，則保留該注記。直到對所有的注記都進行了沖突壓蓋檢測。

圖7　第一、二、三探測區

三、試驗結果與分析

本文在ArcGIS Engine環境下對自主探測算法進行了試驗。選擇了兩個試驗樣區，由于不同的選取資格，試驗樣區1注記保留到縣級行政中心；試驗樣區2注記保留到鎮級行政中心，且道路的分類更多。因此，隨著試驗注記密集程度的增大及注記環境的復雜，致使試驗樣區2的注記配置難度高于試驗樣區1。

試驗中令最大壓蓋權重為100，最小壓蓋權重為2，具體見表1、表2。

表1　試驗樣區1的要素壓蓋權重

表2　試驗樣區2的要素壓蓋權重

注：經緯線的壓蓋權重為2。

1. 配置試驗

(1) 試驗樣區1注記配置試驗

試驗樣區位于108°06′E—116°24′E，28°39′N—33°40′N，比例尺為1∶210萬，點要素及注記信息見表3。

表3　點要素及注記信息

試驗目的主要是在考慮注記盡量配置到所屬的行政區劃內的條件下，將自主探測算法與maplex智能標注系統進行對比，配置結果如圖8、圖9所示。

圖8　maplex智能標注系統的注記結果

圖9　自主探測算法的注記結果

(2) 試驗樣區2注記配置試驗

試驗樣區位于114°44′E—119°40′E，29°12′N—37°47′N，比例尺為1∶64萬，點要素及注記信息見表4。

表4　點要素及注記信息

試驗目的是在考慮注記指代明確、配置均勻的規則下，將自主探測算法與maplex智能標注系統進行對比，配置結果如圖10、圖11所示。

圖10　maplex智能標注系統的注記結果

圖11　自主探測算法的注記結果

2. 結果分析

1) 就試驗樣區1而言，相比于maplex智能標注系統的注記結果，自主探測算法能夠盡量保證注記配置到所屬的行政區劃。以黃石市為例，作為地級行政中心，本應配置到所屬的行政區劃內，但maplex卻配置到了黃岡市的區劃內，這是不允許的；而自主探測算法做到了這一點，不僅配置到所屬的行政區劃內，還保證了最小程度的背景要素壓蓋，這使得注記配置較為合理。

在保證上述原則的基礎上，該方法還能夠使注記配置盡量均勻。以蔡甸區為例，作為武漢市中的一個縣級行政中心，maplex的注記結果使得蔡甸區有近一半配置到了漢川市區劃內，而且兩縣級行政中心注記顯得較為擁擠，而自主探測算法就解決得較好。

2) 就試驗樣區2而言，相比于maplex智能標注系統的注記結果，自主探測算法能夠盡量保證注記指代清晰，即注記與相應點要素的距離最近，且遠離其他點要素，從而視覺上能夠迅速分辨出哪個注記指代哪個點要素，從而達到指代清晰的目的。以對比區域中瓜洲鎮和世業鎮為例，在maplex的注記結果中，兩注記與其之間的點要素的接近程度差不多，較難迅速分辨所屬關系，致使注記配置的指代性不明確，注記質量不高。而自主探測算法就解決得較好，很容易分辨注記的所屬關系，而且避免了背景要素壓蓋，使得其指代較為明確，注記質量較高。

與此同時，相比于maplex，自主探測算法的注記結果顯得更為均勻，以永安鎮和真武鎮為例，maplex雖然使得兩注記都避免了背景要素，但較為擁擠，不太美觀。而地圖注記配置并不意味著沒有壓蓋就是最好，還要考慮注記之間的均衡性。自主探測算法的注記結果就較為合理。

同時，試驗結果中也存在個別不理想的注記配置，如圖11中鎮江市與江心鎮相互沖突。

綜上所述，雖然maplex智能標注系統是目前最好的注記配置系統，但仍缺乏考慮一些注記規則，尤其是注記指代清晰、配置均勻、盡量配置到所屬的行政區劃內等規則。而自主探測算法不僅考慮了這些規則，試驗表明其注記質量優于maplex，而且該方法在不同的注記環境下仍可獲得較為滿意的注記結果。

需要說明的是，目前要素壓蓋權重的設置仍依賴于制圖經驗，其科學依據還有待進一步研究，但在同一幅圖上，如果把握了地圖中要素的重要性程度，即使同一要素的權重設置有所差別，其注記結果也不會有太大差別。

四、結束語

本文首先對注記備選位置及其優先級進行了探討和分析，通過試驗證明了顧及背景要素壓蓋、注記指代明確、配置均勻及盡量配置到所屬的行政區劃內等原則的探測信息模型能夠大大提高注記質量；并且隨著注記難度的增加，自主探測算法仍能獲得很好的注記效果，這對數字地圖制圖效率的提高具有一定的理論和實用價值。同時考慮到權重設置的重要性，下一步將研究權重設置的科學依據及其對注記結果的影響。

參考文獻：

[1]杜世宏，王喬，杜道生，等.地名注記自動配置研究[J].地理學與國土研究，2002，18(4)：14-18.

[2]YOELI P. The Logic of Automated Map Lettering[J]. The Cartographic Journal，1972(9):99-108.

[3]游漣，何宏星.地圖點狀符號及注記的自動配置[J].測繪學報，1993，22(4)：304-308.

[4]樊紅，張祖勛，杜道生，等. 基于神經網絡模型求取注記配置最優解[J].武漢測繪科技大學學報，1998，23(1)：32-35.

[5]YAMAMOTO M, CAMARA G, LORENA L A N. Tabu Search Heuristic for Point-Feature Cartographic Label Placement[J]. GeoInformatica， 2002， 6(1):77-90.

[6]鄭春燕，郭慶勝，劉小利.基于禁忌搜索算法的點狀要素注記的自動配置[J].武漢大學學報(信息科學版)，2006，31(5)：428-431.

[7]樊紅，杜道生，張祖勛.地圖注記自動配置規則及其實現策略[J].武漢測繪科技大學學報，1998，24(2)：154-157.

[8]婁倩，張慧霞，郭建忠，等. 地圖注記質量評價模型的建立[J].測繪科學，2012，37(1)：125-127.

[9]張紅武，張友純，謝忠，等.用遺傳算法解決點狀要素的自動注記問題[J].計算機工程與應用，2003(7)：68-71.

[10]IMHOF E. Positioning Names on Maps[J]. The American Cartographer，1975，2(2):128-144.

[11]CHIRIé F. Automated Name Placement with High Cartographic Quality: City Street Maps [J]. Cartography and Geographic Information Science，2000，27(2): 101-110.

Point Annotation Labelling Based on the Model of Detecting Information

QIAO Junjun,HU Fengwei，ZHANG Haiwen

收稿日期：2015-09-02； 修回日期： 2015-11-02

作者簡介：喬俊軍(1961—)，男，高級工程師，主要從事地圖學與地理信息工程方面的教學及研究工作。E-mail：623083313@qq.com

中圖分類號：P28

文獻標識碼：B

文章編號：0494-0911(2016)06-0035-06

引文格式： 喬俊軍，胡馮偉，張海文. 探測信息模型支持下的點注記配置方法[J].測繪通報，2016(6)：35-40.DOI:10.13474/j.cnki.11-2246.2016.0185.