顧及空間分布與注記相關(guān)性的點要素注記配置算法

曹 聞，彭斐琳，童曉沖，戴浩然，張 勇

1. 鄭州大學(xué)地球科學(xué)與技術(shù)學(xué)院，河南 鄭州 450000； 2. 信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450001； 3. 鄭州眾合景軒信息技術(shù)有限公司，河南 鄭州 450000

隨著大數(shù)據(jù)時代的到來，人們對大數(shù)據(jù)中所蘊含的內(nèi)在機理和高價值信息有著迫切的需求和期待，數(shù)據(jù)可視化成為大數(shù)據(jù)分析不可缺少的工具[1-2]。在數(shù)據(jù)可視化中，各行業(yè)數(shù)據(jù)經(jīng)常利用地理信息技術(shù)將其整合到地理空間上進行分析和表達，因此，地理空間數(shù)據(jù)可視化是大數(shù)據(jù)分析的重要基礎(chǔ)，通常以地圖的形式展示[3-4]。注記作為可視化產(chǎn)品中重要組成部分，是最直觀傳遞信息的要素[5]，由此，提升注記質(zhì)量成了研究的熱點和難點。

數(shù)據(jù)可視化中的空間對象分為點、線、面、體等形式[6-9]，其中，點要素注記的自動配置問題(point-feature label placement problem,PFLP)最為復(fù)雜，已被證明是NP-hard問題[10]。為了解決在龐大規(guī)模的組合優(yōu)化問題中尋找最優(yōu)解的難題，國內(nèi)外學(xué)者對此進行了大量的研究。元啟發(fā)式算法是一種使用高級策略來探索空間的方法[11]，能在有限的時間內(nèi)找到一個較好的近似最優(yōu)解，目前已被廣泛應(yīng)用到點要素注記配置問題的研究中，如禁忌搜索、模擬退火算法、遺傳算法和蟻群算法等[12-15]。大部分學(xué)者通常以改進元啟發(fā)算法為主，將所有點要素視為一個整體進行解算，并未考慮到點要素之間的獨立性，而隨著點要素數(shù)量的增多，組合優(yōu)化的規(guī)模呈爆炸式增長，導(dǎo)致算法求解的效率極低及求解質(zhì)量不佳。因此，有部分學(xué)者利用點要素的空間分布特征來指導(dǎo)注記配置問題的解算，主要分為兩類：一是采用聚類分組的方法對點要素進行分析和求解。文獻[16]提出利用最短距離聚類的方式分析點要素空間分布特征的設(shè)想。文獻[17—18]通過構(gòu)建點要素沖突圖和拉格朗日松弛法進行聚類，將其劃分為多個數(shù)據(jù)簇進行求解。文獻[19]利用基于密度的聚類方法(density-based spatial clustering of applications with noise，DBSCAN)將問題空間劃分成多個子問題空間，進而利用蟻群算法對子問題進行求解。該類算法雖然有效地縮短了注記配置的計算時間，提高了注記效率，但其聚類的過程忽略了點要素注記之間的影響，從而導(dǎo)致聚類得到的不同子數(shù)據(jù)集之間的獨立性方面存在著模糊性和粗差。二是通過規(guī)劃注記次序指導(dǎo)注記配置過程的方式來優(yōu)化注記配置結(jié)果。文獻[20]指出利用Voronoi圖描述點要素的空間分布特征和要素在注記配置過程中的相互影響性，通過規(guī)劃自由度來指導(dǎo)注記配置沿著簡單、高效和高質(zhì)量的方向進行。文獻[21]提出周圍要素較為密集且注記候選區(qū)域面積較小的點要素優(yōu)先注記，對注記配置的順序進行了優(yōu)化。該類算法利用注記次序指導(dǎo)了注記配置過程，雖然能在一定程度上提高注記配置質(zhì)量，但在空間分布稠密的情況下易受到點要素注記間強干擾性的影響，從而導(dǎo)致算法求解更易落入局部最優(yōu)陷阱。

針對上述問題，本文通過挖掘點要素數(shù)據(jù)集的整體空間分布特征、局部空間分布特征和注記相關(guān)性，提出了一種顧及空間分布和注記相關(guān)性的點要素注記配置算法，并通過試驗證明該算法的有效性。

1 算法原理

稠密型點要素的注記自動配置問題主要受限于注記效率和質(zhì)量，針對該問題，本文考慮到點數(shù)據(jù)集的空間分布特征和注記間的相關(guān)性，設(shè)計了一種注記關(guān)聯(lián)度模型，繼而對點要素數(shù)據(jù)集進行空間聚類分析和注記次序規(guī)則制定，最后采用多層次元啟發(fā)算法求解注記配置問題的近似最優(yōu)解。

1.1 注記關(guān)聯(lián)度模型

1.1.1 注記候選位置模型

注記候選位置模型的選擇是注記配置的重要基礎(chǔ)之一[22-23]，直接影響著注記配置的質(zhì)量和效率。為了增加固定位置模型的靈活性和降低滑動模型的運算量，采用文獻[19]提出的多級多方位模型，如圖1所示，可通過細(xì)化參數(shù)半徑r和等分角θ兩個參數(shù)提升空間利用率，但勢必帶來較大的運算量而降低注記效率。因此，綜合考慮注記配置質(zhì)量和運算時間兩方面的平衡，本文選擇等分角θ為45°，并使用優(yōu)先級度量構(gòu)建8位置模型。其中，圖1中的數(shù)字從小至大表示注記位置優(yōu)先級由強至弱的程度，同時為了注記美觀性，將點要素的符號外接圓加入多級多方位模型中，即要求點要素符號化區(qū)域半徑r1要小于注記多級半徑r，實線橢圓和虛線矩形分別為不同位置、字符高度、字符串長度所形成的外接橢圓和最小外接矩形。

圖1 多級多方位注記候選模型Fig.1 The multi-levels and multi-orientations label candidate location model

點要素注記自動配置算法通常是以某種規(guī)則選擇不同的注記候選位置得到近似最優(yōu)解，在此過程中每個已注記點要素的位置會直接影響到隨后點要素的注記位置，因此如何利用其多樣性和互干擾性指導(dǎo)算法求解是值得重點關(guān)注的問題。

1.1.2 注記關(guān)聯(lián)度規(guī)則

在點要素注記配置問題的求解過程中，注記間的干擾會導(dǎo)致算法極易陷入局部最優(yōu)陷阱和求解效率低下。由于注記最小候選外接矩形包括了點要素所有的候選位置，因此可根據(jù)注記最小候選外接矩形為計算基礎(chǔ)設(shè)計相應(yīng)的注記關(guān)聯(lián)度規(guī)則量化不同點要素在注記配置過程的相互干擾關(guān)系。

假設(shè)圖面待配置點要素的集合為P={p1,p2,…,pN}，點要素pi和pj的最小候選外接矩形分別為Ri和Rj，定義一個二進制變量αij表示點pi和pj之間是否存在相互干擾性。若αij=0，表示點要素pi和pj在注記配置過程中不存在干擾性，即Ri∩Rj=φ，不需考慮二者注記的先后順序；若αij=1，表示點要素pi和pj間具有干擾性，需考慮二者具體注記對注記配置的影響，如圖2中點要素pi和pj，Ri∩Rj≠φ，表示其最小候選外接矩形存在相交的部分，則該相交部分定義為注記影響面Aij，即Aij=Ri∩Rj。顯然，二進制變量α和注記影響面A均具有對稱性，即αij=αji和Aij=Aji。

圖2 注記影響面Fig.2 Label influence surface pattern

考慮到點要素間的干擾性將直接影響到注記配置的效率和質(zhì)量，依據(jù)點要素最小注記外接矩形之間的關(guān)系，定義注記支持度η和注記關(guān)聯(lián)度ξ兩個變量對點要素注記間的干擾程度進行量化描述，以此挖掘點要素數(shù)據(jù)集合的局部空間分布特性和注記相關(guān)性。

1.1.2.1 注記支持度ηi

注記支持度是指任一點要素pi在注記配置過程中與其注記最小候選外接矩形相關(guān)的其他點要素的個數(shù)，記為ηi

(1)

注記支持度ηi反映了點要素pi注記后影響到數(shù)據(jù)集中其他點要素的個數(shù)，數(shù)值越大說明更多的點要素需根據(jù)pi的注記位置進行調(diào)整，以避免注記出現(xiàn)重疊和沖突問題。根據(jù)注記支持度ηi的物理意義，可將所有參與注記配置的點要素概括為獨立點、直接關(guān)聯(lián)點和間接關(guān)聯(lián)點3類。

(1) 獨立點。對于點要素pi，如果相對于其他任意點要素pj(i≠j)均存在Ri∩Rj=φ，則稱pi為獨立點，如圖2中pt和ps。獨立點形成的數(shù)據(jù)集合稱為獨立點集，記為ΩI(ΩI?P)。在注記配置的過程中，獨立點注記位置的隨機性選擇會降低算法尋優(yōu)速度，因此可根據(jù)注記位置的優(yōu)先性和圖面美觀性直接注記。

注記支持度ηi通過統(tǒng)計點要素pi直接關(guān)聯(lián)點的個數(shù)來描述其局部空間分布特性，數(shù)值越大表示其局部空間分布越稠密，將其視為優(yōu)先注記點就意味著其他關(guān)聯(lián)點要素注記位置的可選擇性將減小，導(dǎo)致注記配置質(zhì)量不佳。

1.1.2.2 注記關(guān)聯(lián)度ξi

注記支持度ηi雖然描述了點要素的局部空間分布特征，但忽略了存在關(guān)聯(lián)性點要素間的相關(guān)性，點要素pi和pj間注記影響面Aij和Aji相等，由于兩點注記最小候選外接矩形不同，因此二者的互干擾程度也將不同。如圖3(a)所示，點要素pj優(yōu)先注記后，注記影響面Aij覆蓋點要素pi候選區(qū)域中的8個區(qū)塊；而圖3(b)中點要素pi優(yōu)先注記后，注記影響面Aji覆蓋點要素pj候選區(qū)域中的4個區(qū)塊。因此需引入注記關(guān)聯(lián)度ξi描述點要素注記間的相關(guān)性。

圖3 注記關(guān)聯(lián)度原理Fig.3 Label relevance principle

假設(shè)點要素pi優(yōu)先注記對點要素pj的后續(xù)注記位置的干擾概率Pij可定義為

(2)

(3)

式中，ωk表示干擾概率Pij等間隔區(qū)間對應(yīng)的權(quán)值，其中0<ω1<…<ωk<…<ωM。注記關(guān)聯(lián)度ξi描述了點要素pi優(yōu)先注記后對其局部區(qū)域內(nèi)其他點要素的干擾程度，量化了注記間的相關(guān)性。

綜上所述，通過注記支持度ηi和注記關(guān)聯(lián)度ξi兩個參數(shù)制定點要素pi的注記關(guān)聯(lián)規(guī)則，以此描述點要素pi的局部空間分布特征和注記互相關(guān)性，從而為注記配置求解提供先驗輔助決策信息。

1.2 基于注記關(guān)聯(lián)度模型的空間分布特征分析

稠密型點要素數(shù)據(jù)集的空間分布是較為復(fù)雜的，會存在一定數(shù)量的獨立點或不相關(guān)的多個子數(shù)據(jù)集，而這些點要素和子集在整體答解時，會引入較大的模糊性和干擾性，同時注記候選位置模型的多樣性會使注記組合規(guī)模隨點要素數(shù)量的增加呈指數(shù)型增長，從而導(dǎo)致算法求解質(zhì)量不佳和效率降低等問題，其根本原因在于忽略了點要素數(shù)據(jù)集的整體空間分布特征。

空間聚類算法能夠發(fā)現(xiàn)空間實體對象的空間聚集模式，通常被用來揭示其內(nèi)部分布規(guī)律和空間結(jié)構(gòu)特征，在地理空間數(shù)據(jù)挖掘領(lǐng)域得到了廣泛應(yīng)用。其中，DBCSAN算法能較好地應(yīng)用于點要素注記配置研究中[19]，有效降低問題求解的復(fù)雜度和提升注記配置的效率。DBSCAN空間聚類算法是通過判斷點是否落在另一點搜索鄰域范圍內(nèi)確定兩點之間是否存在關(guān)聯(lián)性，其關(guān)鍵在于搜索半徑和核心點判斷閾值兩個參數(shù)的確定，在注記配置問題中的搜索半徑和核心點判斷閾值通常選擇點要素注記的候選區(qū)域和1。如圖4(a)所示，點4、6、7、8被歸為獨立點，但實際其注記存在互相干擾性，容易出現(xiàn)注記疊加的現(xiàn)象。為了適應(yīng)點要素注記配置的特點，利用注記關(guān)聯(lián)度模型中的直接關(guān)聯(lián)點和間接關(guān)聯(lián)點兩個集合進行遞歸類推最終得到互不關(guān)聯(lián)的獨立點集ΩI和M個子數(shù)據(jù)集Ωk,k∈[1,M]，繼而消除具有獨立性點集對注記配置求解產(chǎn)生的模糊性和干擾性，如圖4(b)所示，獨立點集可根據(jù)注記位置優(yōu)先性和圖面美觀性直接注記，而關(guān)聯(lián)點集則視為一個局部整體進行問題求解，從而全局問題轉(zhuǎn)換為多個局部問題提升注記配置解算效率和注記質(zhì)量。

圖4 空間聚類算法Fig.4 Spatial clustering based on association model

空間聚類算法主要是對點數(shù)據(jù)集的空間聚集性進行數(shù)據(jù)挖掘和分析，雖然降低了互不關(guān)聯(lián)的數(shù)據(jù)集對注記配置解算的干擾性和模糊性，但由于沒有充分利用子集中內(nèi)部點要素間的干擾性，將導(dǎo)致無法獲得更佳的注記質(zhì)量。

1.3 基于注記關(guān)聯(lián)度模型的次序規(guī)則

對關(guān)聯(lián)點子數(shù)據(jù)集進行注記配置是旨在有限的空間內(nèi)獲取最大化可注記數(shù)量，而點要素注記之間的干擾性其實反映的是這些點要素之間的空間競爭關(guān)系，因此該注記配置求解問題也可被視為注記的取舍問題。在注記配置求解過程中，點要素注記的取舍是根據(jù)之前的注記結(jié)果來判斷是否存在合適的空間配置注記，同時該注記也會影響到之后點要素能否注記。注記配置算法通常以隨機次序進行注記，忽略了點要素數(shù)據(jù)集的內(nèi)在空間結(jié)構(gòu)和秩序信息，從而無法得到更加合理的注記結(jié)果。

注記關(guān)聯(lián)度模型通過定義注記支持度ηi和注記關(guān)聯(lián)度ξi兩個參數(shù)分別描述點要素pi的局部空間分布特征和其直接關(guān)聯(lián)點注記間的相關(guān)性，本文依次按照兩個參數(shù)值增序?qū)c要素進行排序，構(gòu)建基于增序注記關(guān)聯(lián)度模型的次序規(guī)則，其中，注記支持度ηi對點要素間的干擾程度具有強相關(guān)性，而注記關(guān)聯(lián)度ξi具有弱相關(guān)性，因此基于增序注記關(guān)聯(lián)度次序可表示為：對于不同規(guī)模的點要素集合，先以注記支持度ηi從小到大對所有點要素進行排序；然后對相同注記支持度ηi的點要素再按照注記關(guān)聯(lián)度ξi從小到大排序；最后對兩個參數(shù)均相同的點要素按照隨機的方式進行排序。如圖5所示，增序注記關(guān)聯(lián)度模型較降序注記關(guān)聯(lián)度模型的注記次序規(guī)則，可以有效降低優(yōu)先注記點要素對后續(xù)待注記點要素的干擾性，指導(dǎo)著注記配置過程，提高算法的尋優(yōu)速率，從而使近似最優(yōu)解更加逼近最優(yōu)解。

圖5 不同次序規(guī)則結(jié)果Fig.5 Labeling cases for different labeling orders

1.4 基于注記關(guān)聯(lián)度模型框架的注記自動配置

注記關(guān)聯(lián)度模型框架(annotation association model framework，AAMF)是通過基于注記關(guān)聯(lián)度模型的DBSCAN空間聚類算法和次序規(guī)則挖掘點要素的空間分布信息和注記相關(guān)性，進而對注記配置算法求解進行指導(dǎo)?；谧⒂涥P(guān)聯(lián)度模型框架下的注記配置通過制定注記質(zhì)量評價函數(shù)、沖突檢測方法和多層次元啟發(fā)算法等環(huán)節(jié)獲取更具合理性的注記配置結(jié)果。

1.4.1 注記質(zhì)量評價函數(shù)

注記配置旨在獲得最大化清晰、美觀和可讀的無沖突注記數(shù)目，因此本文參照文獻[24—25]中的方法以無沖突的注記數(shù)因子Fo、注記位置的優(yōu)先性因子Fp和注記的關(guān)聯(lián)性因子Fa構(gòu)建注記質(zhì)量評價函數(shù)F

F=λ1Fo+λ2Fp+λ3Fa

(4)

式中，λ1、λ2、λ3分別為各因子對注記質(zhì)量影響力的占比系數(shù)，一般而言λ1=0.5，λ2=0.3，λ3=0.2，但其中關(guān)聯(lián)性與人眼能識別出的最小距離有關(guān)，不能準(zhǔn)確衡量歧義距離，因此設(shè)置λ3=0。設(shè)質(zhì)量評價函數(shù)較小對應(yīng)著較好的注記配置結(jié)果，因此點要素注記配置的目標(biāo)是獲得最小化質(zhì)量評價函數(shù)值。

1.4.2 注記沖突檢測

點要素注記配置過程中，要求注記之間不可出現(xiàn)重疊或壓蓋現(xiàn)象，因此，在注記配置的過程中需制定注記沖突檢測方法加以解決。目前常用的空間索引方法主要有R樹空間索引和格網(wǎng)空間填充等多種方法[26-27]。R樹索引是以規(guī)則矩形的方式進行碰撞檢測，對于不規(guī)則的地物要素與存在旋轉(zhuǎn)等情況存在著查詢不準(zhǔn)確的缺點，浪費大量的圖面空間。格網(wǎng)空間填充索引是使用一種行排序的空間曲線填充方式進行編碼[28]，原理簡單易懂，在沖突碰撞檢測過程中只需要判斷某點注記所在位置的格網(wǎng)是否被占用，相當(dāng)于一個局部小范圍的遍歷尋址，同時對于不規(guī)則的地物要素有較強的適應(yīng)性和穩(wěn)健性。因此，本文考慮到矢量背景要素符號的不規(guī)則性及點狀要素的注記旋轉(zhuǎn)等因素，采用格網(wǎng)空間填充的索引方式進行沖突檢測。

1.4.3 多層次元啟發(fā)式算法

點數(shù)據(jù)集的空間分布通常疏密不均，經(jīng)空間聚類后關(guān)聯(lián)點子數(shù)據(jù)集中的點要素數(shù)量不均勻。蟻群算法、模擬退火算法和遺傳算法常應(yīng)用于解決點要素注記配置問題，但當(dāng)關(guān)聯(lián)點集中點要素數(shù)量較少時，直接求解則會導(dǎo)致容易陷入局部最優(yōu)等問題，因此需要針對不同數(shù)量的點要素數(shù)據(jù)集設(shè)計多層次元啟發(fā)算法提升其普適性和穩(wěn)健性。

多層次元啟發(fā)算法是依據(jù)關(guān)聯(lián)點集的大小采用不同搜索策略的元啟發(fā)式算法進行求解。首先根據(jù)數(shù)據(jù)集中點要素的數(shù)量定義一級、二級和三級3種等級的數(shù)據(jù)集，同時設(shè)置兩個閾值分別為：低閾值δ1和高閾值δ2(δ1,δ2∈N+,δ1<δ2)，當(dāng)點要素數(shù)量n<δ1(δ1∈[1，10])，即為一級數(shù)據(jù)集。利用注記無沖突性的要求，采用文獻[14]中注記沖突調(diào)整的方式進行注記配置。針對具有注記沖突的點要素更新注記方向的選擇，能更快地獲得較優(yōu)的注記結(jié)果。點要素數(shù)量δ1δ2，即為三級數(shù)據(jù)集，依據(jù)文獻[14]中精英保留策略進行問題求解。而模擬退火算法與蟻群算法對二級和三級數(shù)據(jù)集解算方式相同，分別參考文獻[14]和文獻[19]的方法進行迭代尋優(yōu)。3種元啟發(fā)式算法試驗參數(shù)取值見表1。

表1 元啟發(fā)式參數(shù)Tab.1 Metaheuristic parameter

2 試驗與分析

為了驗證本文所提注記關(guān)聯(lián)度模型對點要素注記自動配置算法的優(yōu)越性，利用網(wǎng)絡(luò)爬蟲技術(shù)從某地圖網(wǎng)站獲取鄭州市興趣點POI數(shù)據(jù)，以其隨機生成3000和6000點規(guī)模的數(shù)據(jù)集合為試驗數(shù)據(jù)，采用模擬退火算法、蟻群算法和遺傳算法討論和分析反映注記關(guān)聯(lián)度模型框架對提升點要素注記自動配置算法效率和質(zhì)量的意義。試驗與分析中的所有算法均通過Visual C++編程實現(xiàn)，試驗環(huán)境的處理器和內(nèi)存分別為Intel(R) Core(TM) i5-8500 3.0 GHz和8 GB。

2.1 顧及空間分布和注記關(guān)聯(lián)性點要素注記配置對比試驗

點要素注記自動配置的質(zhì)量和效率主要受到點要素數(shù)量和注記方向多樣性的影響。本文依據(jù)數(shù)據(jù)集的空間分布特征與注記相關(guān)性構(gòu)建基于注記關(guān)聯(lián)度模型的算法框架AAMF，并應(yīng)用于元啟發(fā)式算法來進行點要素注記配置試驗，主要包括基于注記關(guān)聯(lián)度模型框架下的模擬退火算法AAMF-SA、遺傳算法AAMF-GA和蟻群算法AAMF-ACA，考慮到數(shù)據(jù)集空間分布的稀疏稠密特征對基于注記關(guān)聯(lián)度模型算法效果的影響，設(shè)計在常用的8種注記密度ρ為5%、10%、15%、20%、25%、30%、35%和40%下,比較AAMF算法與傳統(tǒng)算法的優(yōu)劣性。試驗以所有的點要素視為同一細(xì)節(jié)層級為前提，采用模擬退火算法、遺傳算法和蟻群算法比較隨機次序規(guī)則R1、基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2和基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3的試驗結(jié)果，討論與分析基于注記關(guān)聯(lián)度模型的次序規(guī)則在不同元啟發(fā)式算法下的有效性。每組試驗重復(fù)10次取平均值，點要素數(shù)量低閾值δ1與高閾值δ2分別為7和100，參數(shù)r、r1和注記字體分別設(shè)置為10、5和12像素。記錄每組試驗的耗時T和注記質(zhì)量評價函數(shù)值E，試驗結(jié)果見表2—表7和圖6、圖7。

圖6 算法注記配置結(jié)果Fig.6 Labeling result of algorithm

圖7 注記結(jié)果細(xì)節(jié)對比Fig.7 Detailed comparison of labeling results

表2 注記密度為5%～20%模擬退火算法的試驗結(jié)果統(tǒng)計Tab.2 The statistical results of SA with label density range from 5% to 20%

由表2、表3可知，不同的規(guī)則算法對注記配置結(jié)果產(chǎn)生了較大的影響。首先，從次序規(guī)則上來說，基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3的質(zhì)量評價函數(shù)值相較于隨機次序規(guī)則R1降低3～8.5，相較于基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2降低6～15.8，規(guī)則R3的結(jié)果均優(yōu)于規(guī)則R1和R2；其次，AAMF-SA算法比SA算法求解的效率平均提升16.78%，且評價函數(shù)值降低了12.28；通過試驗分析可以看出，AAMF-SA取得了較好的注記配置結(jié)果和注記效率。

表3 注記密度為25%～40%模擬退火算法的試驗結(jié)果統(tǒng)計Tab.3 The statistical results of SA with label density range from 25% to 40%

由表4、表5可知，基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3比隨機次序規(guī)則R1的質(zhì)量評價函數(shù)值平均降低5.95、比基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2平均降低12.82，由此可見，次序規(guī)則R3優(yōu)于規(guī)則R1和R2，提高了注記配置質(zhì)量。AAMF-GA算法比GA算法求解效率平均提高18.1%；其評價函數(shù)值平均降低9.2。其中，在注記密度為5%下的6000點規(guī)模試驗中，AAMF-GA的評價函數(shù)值比GA降低32.8，注記質(zhì)量大幅度提升，但其注記效率比GA降低了4.97%，這是因為空間聚類算法將大規(guī)模單一數(shù)據(jù)集分成了若干個子數(shù)據(jù)集，減少了要素注記間的干擾性，使得每個子數(shù)據(jù)集求解時不斷地進行迭代優(yōu)化從而提升了注記質(zhì)量，同時也增加了算法的迭代時間，由此損失的效率是可以接受的。

表4 注記密度為5%～20%遺傳算法的試驗結(jié)果統(tǒng)計Tab.4 The statistical results of GA with label density range from 5% to 20%

表5 注記密度為25%～40%遺傳算法的試驗結(jié)果統(tǒng)計Tab.5 The statistical results of GA with label density range from 25% to 40%

蟻群算法試驗結(jié)果見表6、表7。首先，AAMF-ACA算法比ACA算法效率平均提升17.70%，評價函數(shù)值平均降低7.71；其次，基于增序注記關(guān)聯(lián)度模型的次序規(guī)則R3比隨機次序規(guī)則R1的質(zhì)量評價函數(shù)值平均降低了8.11，同時，比基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2平均降低15.6。試驗分析表明，AAMF-ACA能有效提升注記配置效率和注記配置質(zhì)量。

表6 注記密度為5%～20%蟻群算法的試驗結(jié)果統(tǒng)計Tab.6 The statistical results of ACA with label density range from 5% to 20%

表7 注記密度為25%～40%蟻群算法的試驗結(jié)果統(tǒng)計Tab.7 The statistical results of ACA with label density range from 25% to 40%

綜上所述，基于注記關(guān)聯(lián)度模型框架能較好地應(yīng)用于模擬退火算法、遺傳算法和蟻群算法，并取得了注記效率和注記質(zhì)量的提高?；谠鲂蜃⒂涥P(guān)聯(lián)度模型的次序規(guī)則R3取得了最好的配置優(yōu)化效果，其次是隨機次序規(guī)則R1，基于降序注記關(guān)聯(lián)度模型的次序規(guī)則R2配置結(jié)果質(zhì)量最差。結(jié)合表2—表7試驗結(jié)果統(tǒng)計進行分析，首先，在注記密度為5%～40%下，規(guī)則R3比規(guī)則R1注記配置的質(zhì)量評價函數(shù)值分別降低3.0～5.7、5.0～8.4、6.9～8.5、4.6～9.2、6.0～8.9、5.2～10.9、5.5～9.8、7.3～9.4，比次序規(guī)則R2降低5.9～10.7、8.6～15.4、13.0～17.5、11.4～18.2、13.1～17.6、13.4～17.3、14.8～17.6、15.1～17.5。數(shù)據(jù)分析表明，隨著注記密度由5%至40%，注記次序規(guī)則R3與R1、R2的差值由小逐漸增大，這是因為當(dāng)數(shù)據(jù)集空間分布較為稀疏時，大部分的點注記候選區(qū)域只影響少量個別其他點注記候選區(qū)域，無論采用哪種注記次序，注記都有較大的可能性找到空間放置，因此，在這種情況下，3種規(guī)則的注記配置結(jié)果區(qū)別較小。當(dāng)數(shù)據(jù)集空間分布較為稠密時，注記間的沖突性和關(guān)聯(lián)性增大，規(guī)劃以增序注記關(guān)聯(lián)度模型的次序令關(guān)聯(lián)性較小的點要素優(yōu)先注記，能大幅度地減少已配置的注記對待配置注記的影響，對注記配置的結(jié)果有著較好的優(yōu)化效果。其次，新算法相較于傳統(tǒng)元啟發(fā)式算法效率平均提高了28.92%、19.23%、16.47%、16.42%、14.30%、14.59%、13.79%、10.41%，且質(zhì)量評價函數(shù)值平均下降了26.5、13.4、8.7、6.1、4.5、4.1、3.5、2.5。由此可見，注記效率和質(zhì)量的提升幅度有著明顯的下滑趨勢，這是因為注記密度變大，數(shù)據(jù)集的空間分布較為集中，空間聚類后獲得最大子集的點要素數(shù)量與整體數(shù)據(jù)集相差無幾，空間聚類算法已經(jīng)不能大幅度地減少干擾性和降低計算復(fù)雜度，同時又增加了聚類這一過程的耗時，從而降低了注記效率和質(zhì)量的提升，因此，當(dāng)點要素空間分布較為稠密時，空間聚類算法對注記配置的作用會減小。

圖6和圖7展示了對6000點要素使用AAMF算法與傳統(tǒng)算法得到的同一區(qū)域注記結(jié)果局部對比圖和細(xì)節(jié)對比圖。在本組注記配置結(jié)果中，AAMF算法獲得的無沖突注記數(shù)總計3218個，在圖6中展示的局部區(qū)域有256個注記，傳統(tǒng)算法獲得的無沖突注記數(shù)總計3065個，在圖6中展示的局部區(qū)域212個注記，AAMF算法取得了153個注記的提升。圖7(a)和7(b)分別是圖6(a)和圖6(b)的典型細(xì)節(jié)注記結(jié)果示例，由該圖可以看出，圖7(a)中的點注記方向和注記數(shù)量更有優(yōu)勢，其基于注記關(guān)聯(lián)度模型的空間聚類算法與注記次序規(guī)則，既降低了組合優(yōu)化問題的復(fù)雜度又提高了每個點要素可注記概率，取得了較好的注記效果。而圖7(b)注記數(shù)目和注記方向較AAMF算法的注記配置結(jié)果有一定的差距，這是因為其整體求解方式不能反映單個點要素或者某塊獨立數(shù)據(jù)集的注記配置的需求，且注記的隨機性無法為配置過程提供先驗輔助決策信息，令注記配置的結(jié)果質(zhì)量不佳。因此，本文提出的AAMF算法相較于傳統(tǒng)算法更有優(yōu)勢。

2.2 與MapLex智能標(biāo)注系統(tǒng)的對比試驗

為了對比新算法與MapLex智能標(biāo)注系統(tǒng)的注記質(zhì)量，采用基于關(guān)聯(lián)度模型框架的模擬退火算法與ArcGIS 10.5版本下的MapLex注記配置進行對比，由于MapLex無法統(tǒng)計注記方向，僅將無沖突注記個數(shù)作為比較標(biāo)準(zhǔn)，試驗統(tǒng)計結(jié)果見表8。試驗參數(shù)r、r1和注記字體分別設(shè)置為2、2和12像素，MapLex系統(tǒng)中r、r1和字體設(shè)置為2、2和9磅。

表8 試驗結(jié)果統(tǒng)計Tab.8 The statistical result of the experimental data

由表8的試驗統(tǒng)計結(jié)果可知，新算法獲得的無沖突注記數(shù)均比MapLex智能標(biāo)注系統(tǒng)多，注記配置質(zhì)量更為合理，但新算法在時間效率方面仍然需要得到進一步提高。

3 結(jié) 論

本文針對稠密型點狀要素注記自動配置問題，通過構(gòu)建注記關(guān)聯(lián)度模型對點要素數(shù)據(jù)集的全局空間分布特征、局部空間分布特征以及注記之間的相關(guān)性進行表達和描述，進而利用基于注記關(guān)聯(lián)度模型的多層次元啟發(fā)式算法求解點要素注記配置的近似最優(yōu)解。其中，用于描述點要素數(shù)據(jù)集整體空間分布特征的空間聚類算法對稀疏性點要素數(shù)據(jù)集的注記配置更具優(yōu)勢，而用于描述局部空間分布特征和注記相關(guān)性的次序規(guī)則對稠密性點要素數(shù)據(jù)集的注記配置更具優(yōu)勢。新算法雖然通過空間數(shù)據(jù)挖掘在注記配置效率和質(zhì)量上得到了明顯提升，但仍然存在不足之處：①注記關(guān)聯(lián)度模型缺乏圖面空白區(qū)域指導(dǎo)點要素具體注記方向的能力，需進一步地提升注記配置算法的效率和質(zhì)量；②新算法使用格網(wǎng)空間填充方法雖然可有效解決不規(guī)則對象和旋轉(zhuǎn)等復(fù)雜環(huán)境下的注記沖突檢測問題，但隨著注記范圍的增大，會產(chǎn)生占用內(nèi)存空間過大和局部尋址效率低下的問題；③需進一步研究如何在質(zhì)量評價函數(shù)中根據(jù)人們視覺制定更為合理的歧義性因子，以增強注記的可讀性和視覺美觀性。