基于滿意度移動模型的點(diǎn)軍標(biāo)顯示自動避讓方法

黃亞鋒，張航峰

(南京電子技術(shù)研究所，南京 210039)

0 引 言

基于數(shù)據(jù)自動生成要圖是要圖標(biāo)繪的發(fā)展趨勢?；跀?shù)據(jù)自動生成要圖涉及一對基本矛盾，即有限的要圖表示空間與可以無限細(xì)致劃分的戰(zhàn)場空間信息的矛盾。體現(xiàn)這對矛盾的一個典型案例是點(diǎn)軍標(biāo)顯示占位沖突，即在要圖表達(dá)空間不變的前提下，當(dāng)點(diǎn)軍標(biāo)顯示過于密集時將產(chǎn)生符號間間隔小于視覺可辨間隔甚至符號間相互疊置等現(xiàn)象。而解決點(diǎn)軍標(biāo)顯示占位沖突的有效途徑之一是采用避讓標(biāo)繪方式，將沖突軍標(biāo)移位在附近圖面空白區(qū)域并用指引線指向配置位置。

由于軍標(biāo)避讓標(biāo)繪方法的重要性，在態(tài)勢智能化顯示領(lǐng)域，該問題的研究一直是研究熱點(diǎn)問題。在概念層次上，文獻(xiàn)［1］指出軍標(biāo)自動避讓是態(tài)勢智能顯示的關(guān)鍵技術(shù)，是實(shí)現(xiàn)態(tài)勢圖無極縮放的技術(shù)基礎(chǔ)。在算法層次上，文獻(xiàn)［2］提出了基于模擬退火的軍標(biāo)自動避讓算法，該算法將軍標(biāo)位置重疊度作為評價軍標(biāo)備選位置的優(yōu)劣的評價函數(shù)，通過隨機(jī)尋優(yōu)的方式尋求優(yōu)化解。文獻(xiàn)［3］提出了基于密度方法的軍標(biāo)聚類方法，該算法基本思路是尋找大于密度閾值的空間沖突軍標(biāo)群，利用新的軍標(biāo)繼承被代替存在沖突的標(biāo)號。

以上點(diǎn)狀軍標(biāo)自動避讓算法重點(diǎn)考慮了軍標(biāo)覆蓋面積、分布密度對點(diǎn)軍標(biāo)避讓方案選擇的影響。然而點(diǎn)狀軍標(biāo)自動避讓是個復(fù)雜空間思維過程，它需要通過盡可能小的點(diǎn)軍標(biāo)移動達(dá)到最少的軍標(biāo)重疊區(qū)域的目標(biāo)，如何對這一個復(fù)雜的問題建模值得進(jìn)一步研究。在總結(jié)點(diǎn)軍標(biāo)標(biāo)繪規(guī)則基礎(chǔ)上，借鑒社會活動中的滿意度移動模型，將點(diǎn)軍標(biāo)自動避讓當(dāng)作空間競爭問題求解，以軍標(biāo)重疊區(qū)域大小為軍標(biāo)滿意度主要判斷依據(jù)，并綜合考慮點(diǎn)軍標(biāo)移動距離、配置位置對避讓方案的影響，通過多次迭代導(dǎo)出最終標(biāo)繪結(jié)果。

1 點(diǎn)狀軍標(biāo)避讓標(biāo)繪原則

點(diǎn)軍標(biāo)標(biāo)繪原則是人工制圖經(jīng)驗(yàn)的總結(jié)，也是計(jì)算機(jī)環(huán)境下自動避讓標(biāo)繪算法設(shè)計(jì)時需要遵循的規(guī)則。在總結(jié)文獻(xiàn)［2 ～4］工作基礎(chǔ)上，將點(diǎn)軍標(biāo)避讓標(biāo)繪原則總結(jié)如下。

①點(diǎn)軍標(biāo)標(biāo)繪尺寸視覺可辨;

②點(diǎn)軍標(biāo)顯示不相互重疊;

③點(diǎn)軍標(biāo)間隔大于視覺可辨最小距離;

④當(dāng)多個點(diǎn)軍標(biāo)顯示存在占位沖突時，將點(diǎn)軍標(biāo)移位至附近圖面空白區(qū)域并用指引線指向配置位置。

分析以上標(biāo)繪規(guī)則，原則①可以看作點(diǎn)軍標(biāo)避讓標(biāo)繪預(yù)處理環(huán)節(jié)，可通過以點(diǎn)坐標(biāo)定位點(diǎn)為不變點(diǎn)的仿射變換實(shí)現(xiàn)，暫不討論。原則②、③是點(diǎn)軍標(biāo)應(yīng)用避讓方法的適用條件的總結(jié)。利用形式化方式進(jìn)行描述，對于態(tài)勢圖任一點(diǎn)軍標(biāo)集合S = {JB1，JB2，……，JBn}，n 為點(diǎn)軍標(biāo)的個數(shù)，將點(diǎn)軍標(biāo)JBi、JBj(i，j≤n)間最短距離記作dis(JBi，JBj)，點(diǎn)軍標(biāo)JBi、JBj(i，j≤n)間覆蓋面積記作lap(JBi，JBj)，若d為點(diǎn)軍標(biāo)間視覺可辨最小間隔，則點(diǎn)軍標(biāo)避讓的適用條件為

原則④是具體避讓標(biāo)繪方法的總結(jié)。點(diǎn)軍標(biāo)JBi移位配置后對應(yīng)點(diǎn)軍標(biāo)記作JBi′，將點(diǎn)軍標(biāo)JBi的定位點(diǎn)記作ZJBi，點(diǎn)軍標(biāo)避讓標(biāo)繪后滿足點(diǎn)軍標(biāo)移位最小、軍標(biāo)間無沖突的要求即

2 基于滿意度的點(diǎn)軍標(biāo)顯示避讓模型

在對點(diǎn)軍標(biāo)集合進(jìn)行避讓條件判斷后(即判斷是否滿足式(1)的條件)，如何將點(diǎn)軍標(biāo)的避讓過程建模，使避讓后軍標(biāo)集合滿足式(2)的要求是其中難點(diǎn)問題，它需要在一定模型基礎(chǔ)上定量給出各點(diǎn)軍標(biāo)可選配置位置及各可選位置點(diǎn)軍標(biāo)沖突程度，并綜合考慮以上因素導(dǎo)出最優(yōu)的點(diǎn)軍標(biāo)避讓標(biāo)繪方法。通過借鑒社會活動中的滿意度移動模型，在該模型基礎(chǔ)上給出軍標(biāo)個體滿意度、軍標(biāo)群滿意度定義，經(jīng)過多次點(diǎn)軍標(biāo)移動達(dá)到點(diǎn)軍標(biāo)滿意度最大、位移最小的目標(biāo)。

滿意度模型［5］由Dewdney 觀察人群內(nèi)部活動得到社會動力學(xué)模型。該模型認(rèn)為不同的人與人之間的吸引力或排斥力是不相同的，在進(jìn)行例如聚會等局限于一定固定封閉空間內(nèi)部的社會活動時，每個參加聚會的個體都在試圖尋求他在聚會人群中的合理定位，尋求他與其他個體間的最佳距離。為了達(dá)到滿意度最大的目標(biāo)，個體總在他的附近不停尋找可選位置，以接近他所喜歡的個體(具有吸引力的個體)，遠(yuǎn)離他所厭惡的個體(具有排斥力的個體)。在算法層次上，滿意度移動模型利用規(guī)則格網(wǎng)對聚會進(jìn)行的封閉空間進(jìn)行劃分，由個體與其他個體距離矩陣確定其滿意度大小，將個體所處3 ×3 矩陣作為個體移位備選位置，依次考慮每個個體滿意度并將該個體移位至其滿意度最高的備選位置，經(jīng)過數(shù)次迭代后，每個聚會的個體都會需要找一個達(dá)到他滿意度最大的位置，使整個聚會空間達(dá)到穩(wěn)定的狀態(tài)。

滿意度移動模型是進(jìn)行多個目標(biāo)移位操作的有力工具，該模型已應(yīng)用至社會活動建模、地圖綜合等多個領(lǐng)域［5，6］。滿意度移動模型與其他移動方法相比，具有計(jì)算效率高、魯棒性強(qiáng)等優(yōu)點(diǎn)。這里，應(yīng)用滿意度模型解決點(diǎn)軍標(biāo)避讓標(biāo)繪問題，將避讓標(biāo)繪可以看作是在一定封閉的地圖空間內(nèi)，點(diǎn)軍標(biāo)相互空間競爭、尋求最佳位置的過程。

下面從點(diǎn)軍標(biāo)顯示滿意度、可選移動位置、避讓流程和參數(shù)設(shè)置等方面介紹基于滿意度移動模型的點(diǎn)軍標(biāo)自動避讓算法。

(1)點(diǎn)軍標(biāo)顯示滿意度

定義點(diǎn)軍標(biāo)個體的滿意度是基于滿意度的點(diǎn)軍標(biāo)避讓算法的基礎(chǔ)。在避讓標(biāo)繪問題中，點(diǎn)軍標(biāo)的滿意度越高就意味著點(diǎn)軍標(biāo)與其他軍標(biāo)的沖突越小。同時結(jié)合式(1)給出的點(diǎn)軍標(biāo)沖突定義，可推論出點(diǎn)軍標(biāo)的滿意度與點(diǎn)軍標(biāo)間最短距離、點(diǎn)軍標(biāo)間覆蓋面積有關(guān)。然而需要注意的是，由于點(diǎn)軍標(biāo)內(nèi)部幾何圖形通常較為復(fù)雜，計(jì)算大量的復(fù)雜幾何圖形間覆蓋面積與最短距離的計(jì)算代價很高，因此從計(jì)算效率角度看式(1)的直接定義無法直接定義點(diǎn)軍標(biāo)的滿意度。

為解決上述問題，考慮到點(diǎn)軍標(biāo)外接矩形是對點(diǎn)軍標(biāo)外形的一種概括，將點(diǎn)軍標(biāo)滿意度定義為點(diǎn)軍標(biāo)外接矩形覆蓋面積和的反比。對于任一軍標(biāo)JBi，其外接矩形為MBR(JBi)，則JBi的滿意度Happiness(JBi)，

式中，i，j≤n;ε 為常數(shù)。

(2)點(diǎn)軍標(biāo)配置位置

在避讓標(biāo)繪問題中，首先點(diǎn)軍標(biāo)的備選配置受標(biāo)繪圖幅大小的限制，點(diǎn)軍標(biāo)避讓標(biāo)繪位置不能位于地圖圖幅之外;再次點(diǎn)軍標(biāo)的備選配置要顧及讀圖者閱讀習(xí)慣的影響;其次點(diǎn)軍標(biāo)備選配置數(shù)目的多少對避讓算法運(yùn)算效率有直接影響，算法需要依次計(jì)算圖幅各軍標(biāo)各備選位置的滿意度，故算法效率與備選位置數(shù)目呈反比關(guān)系。

綜合考慮上述因素，將點(diǎn)軍標(biāo)原有配置位置及離點(diǎn)軍標(biāo)原有位置距離r 處的四方向鄰域(右上、左上、左下、右下)位置作為點(diǎn)軍標(biāo)移位的備選位置如圖1所示，圖1(a)所示的軍標(biāo)1 含有1 －5 的備選位置。地圖圖廓線附近的點(diǎn)軍標(biāo)移位位置為圖幅范圍內(nèi)的鄰域位置，圖1(b)所示的右上圖廓附近的軍標(biāo)1 備選位置為1、2。另外，在各點(diǎn)軍標(biāo)滿意度相同的情況下，各備選位置的優(yōu)先級是不盡相同的，從避讓標(biāo)繪習(xí)慣看存在這從中間、右上、左上、左下、右下優(yōu)先級逐步遞減的規(guī)律，圖1 中用數(shù)字標(biāo)繪方式給出各位置的配置優(yōu)先級，圖中數(shù)字越小該位置優(yōu)先級越高。

圖1 點(diǎn)軍標(biāo)可選配置位置

(3)避讓標(biāo)繪流程

基于滿意度模型的點(diǎn)軍標(biāo)避讓標(biāo)繪問題中，系統(tǒng)初始輸入條件為存在空間沖突的點(diǎn)軍標(biāo)集合，系統(tǒng)為集合內(nèi)部各點(diǎn)軍標(biāo)元素依次在可選配置位置集合中尋找最優(yōu)配置位置，通過多次迭代后當(dāng)每個軍標(biāo)的滿意度都不能再增加時，系統(tǒng)達(dá)到穩(wěn)定狀態(tài)，系統(tǒng)的輸出為移位后具有穩(wěn)定狀態(tài)的點(diǎn)軍標(biāo)集合。

基于滿意度模型的點(diǎn)軍標(biāo)避讓標(biāo)繪的詳細(xì)流程如下。

①系統(tǒng)輸入初始軍標(biāo)集合S0= {JB1、JB2、……、JBn}，計(jì)算集合S0各軍標(biāo)滿意度用Happiness(S0)表示，Happiness(S0)={Happiness(JB1)、Happiness(JB2)、……、Happiness(JBn)}。

②對集合內(nèi)軍標(biāo)進(jìn)行滿意度移位，由下列過程組成:

a)為集合內(nèi)軍標(biāo)設(shè)置移位標(biāo)志位flag(JBi)，flag(JBi)=0;

b)選取flag(JBi)=0 而且滿意度最小的軍標(biāo)為待移位軍標(biāo)JBM;

c)計(jì)算JBM的備選配置位置，將其移動至滿意度最高且配置優(yōu)先級最高的備選位置;

d)flag(JBM)=1，更新軍標(biāo)集狀態(tài)，判斷集合狀態(tài)若滿足條件?flag(JBi)=1，則轉(zhuǎn)至步驟③，否則轉(zhuǎn)至步驟②a)。

③軍標(biāo)集狀態(tài)由Sn變更為Sn+1，計(jì)算Happiness(Sn+1)，若條件Happiness(Sn+1)= Happiness(Sn)存在則轉(zhuǎn)至步驟④，否則轉(zhuǎn)至步驟②;

④Sn+1為避讓后的軍標(biāo)集合，輸出軍標(biāo)集合Sn+1。

某次迭代過程中軍標(biāo)JB1的避讓過程如圖2 所示，圖2(a)為初始點(diǎn)軍標(biāo)集合，點(diǎn)軍標(biāo)JB1與JB2、JB3間存在占位沖突，圖2(b)為利用最小外接矩形計(jì)算JB1滿意度的過程，其中矩形重疊部分Ⅰ、Ⅱ、Ⅲ為沖突部分，分別計(jì)算軍標(biāo)JB1的五個備選配置的滿意度，通過計(jì)算可知左上方位的滿意度最大，圖2(c)為將左上位置作為移位位置后的避讓標(biāo)繪結(jié)果。

圖2 軍標(biāo)JB1 的自動避讓過程

(4)參數(shù)設(shè)置

3 實(shí)驗(yàn)與討論

基于上述方法采用模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn)如圖5 所示。圖5(a)為實(shí)驗(yàn)數(shù)據(jù)，包含點(diǎn)軍標(biāo)42 個，其中后方指揮所、專項(xiàng)指揮所各21 個;圖5(b)為采用基于滿意度移位模型的軍標(biāo)結(jié)果，模型移位參數(shù)r 設(shè)置為軍標(biāo)外接矩形短半徑的1/4，所需迭代次數(shù)為4。采用目視判別的方法對實(shí)驗(yàn)結(jié)果進(jìn)行比照分析，發(fā)現(xiàn)該避讓方法的結(jié)果圖5(b)能夠較好地解決圖5(a)中A、B、C 等處點(diǎn)軍標(biāo)占位矛盾。然而分析圖5(b)，發(fā)現(xiàn)算法在有效解決點(diǎn)軍標(biāo)的占位矛盾的同時也使點(diǎn)軍標(biāo)分布密度趨于一致，也就是無法有效保持各區(qū)域點(diǎn)軍標(biāo)分布密度的對比情況(如圖5(a)A、D 處在避讓前A 處明顯大于D 處，而在避讓后的A、D 處點(diǎn)軍標(biāo)分布密度相差不大)。這是本算法存在的不足之處。

圖5 基于滿意度移位的軍標(biāo)避讓算法

為解決上述不足，基于滿意度移動模型的避讓算法的改進(jìn)可從如下方面進(jìn)行:①改進(jìn)軍標(biāo)滿意度計(jì)算模型，綜合考慮點(diǎn)軍標(biāo)分布密度對比對軍標(biāo)避讓操作的影響;②當(dāng)軍標(biāo)分布過于密集時，結(jié)合選擇/刪除操作、避讓移位、同類軍標(biāo)聚合等多種操作解決點(diǎn)軍標(biāo)沖突。多種操作的集成涉及到何種條件下對何處目標(biāo)選擇何種操作，并實(shí)施到何種操作程度問題，這屬于高層次的空間決策問題。后繼研究將著手解決該問題。

［1］曾軍，王飛. 計(jì)算機(jī)輔助標(biāo)圖發(fā)展研究［J］.測繪學(xué)院學(xué)報(bào)，2000，17(3):224-231.

［2］陳文凱，曹澤文.基于模擬退火算法的部署圖點(diǎn)軍標(biāo)自動避讓［J］.兵工自動化，2009，28(3):35-37.

［3］趙恩來，郝文寧，趙水寧，韓憲勇.改進(jìn)的基于密度方法的態(tài)勢聚類顯示算法［J］.計(jì)算機(jī)工程，2010，36(18):35-37.

［4］夏仕保.實(shí)用要圖標(biāo)繪［M］.北京:軍事科學(xué)出版社，2004.

［5］DEWDNEY A K. Computer Recreations:Diverse Personalities Search for Social Equilibrium at a Computer Party［J］. Scientific American，1987(9):104-107.

［6］ MACKANESS W A，PURVES R S. Automated Displacement for Large Numbers of Discrete Map Objects［J］.Algorithmica，2001(30):302-311.