謝 天，李精忠

武漢大學資源與環(huán)境科學學院，湖北 武漢 430079

隨著網(wǎng)絡技術(shù)的發(fā)展，地圖服務需要滿足不同層次用戶個性化需求，在地圖內(nèi)容上提供任意尺度的表達，這需要連續(xù)地圖綜合技術(shù)的支持［1］?；趫D像融合中的morphing技術(shù)，其形狀漸變特性符合空間數(shù)據(jù)多尺度表達與漸進式綜合的技術(shù)需求，故成為實現(xiàn)連續(xù)地圖綜合技術(shù)的重要方法。morphing變換通常包含兩個基本過程，即特征匹配和形狀插值［2］。目前，大多 morphing算法都針對這兩個基本過程研究，如文獻［3］基于優(yōu)化技術(shù)實現(xiàn)的線狀要素morphing變換方法，文獻［4—7］基于BLG和層次彎曲結(jié)構(gòu)實現(xiàn)的線狀河流及道路要素的morphing變換方法，文獻［8］研究基于同構(gòu)平面三角網(wǎng)格的多邊形保凸morphing變形方法，文獻［9］提出的一種基于類正切空間的多邊形漸變方法等，是針對特征匹配過程的研究；而文獻［10］提出的常用線性插值方法，文獻［11］提出的基于目標邊界插值的morphing方法，文獻［12—13］提出的顧及目標內(nèi)部區(qū)域插值的morphing方法，文獻［14］提出的基于四元素插值的空間曲線邊界約束變形方法等，是針對形狀插值研究。就空間數(shù)據(jù)而言，這些方法往往從純幾何特征入手展開匹配和插值，沒有顧及地理要素幾何細節(jié)背后所隱含的地理特征，如居民地要素的類直角邊界特征。而顧及要素的地理特征近年來成為連續(xù)地圖綜合技術(shù)的重要要求，如文獻［15］提出顧及研究對象所處的環(huán)境和背景進行地圖綜合選取，文獻［16］提出的面向多重空間的解決地圖綜合中移位沖突的移位場模型，文獻［17］提出顧及地理特征保持的溺谷海岸線化簡算法，文獻［18］提出保持道路目標stroke特征的道路網(wǎng)自動綜合方法，文獻［19］提出的考慮建筑物輪廓形態(tài)和面積保持的建筑物多邊形化簡方法。顧及要素的地理特征是應用morphing技術(shù)實現(xiàn)連續(xù)地圖綜合的重要挑戰(zhàn)。

目前沒有顧及居民地要素類直角化特征的morphing算法。在已發(fā)表的morphing算法中，或產(chǎn)生具有平滑邊界特征的中間系列圖形，不符合居民地要素空間表達和認知的基本規(guī)律；或不適用于居民地要素的連續(xù)漸變，如文獻［6］提出的基于彎曲結(jié)構(gòu)的morphing算法因居民地不存在文中所述的典型彎曲而不適用，文獻［7］提出的更充分利用獨立彎曲結(jié)構(gòu)的morphing算法因居民地不存在文中所述層次彎曲而不適用。本文提出一種基于轉(zhuǎn)向角函數(shù)的morphing方法，其基本思想是將同名要素在空間域的坐標串表達形式轉(zhuǎn)換為轉(zhuǎn)向角函數(shù)，通過特征點約束下的邊的方位角匹配找出兩個不同尺度下圖形的轉(zhuǎn)向角函數(shù)的變化規(guī)律，按此規(guī)律得到的任意中間尺度下的轉(zhuǎn)向角函數(shù)，函數(shù)展開后可獲得對應中間尺度下插值形狀，且保持原多邊形類直角化邊界特征，從而實現(xiàn)居民地多邊形的連續(xù)綜合與多尺度表達。

1 原 理

1.1 概念模型

對于不同尺度下的對應同名居民地實體，設大比例尺Ta下的居民地要素為a，小比例尺Tb下的居民地要素為b，中間比例尺TMid下的居民地要素為Mid，a較之b具有更詳細的表達，Mid表達的詳略介于a、b之間，則morphing變換問題轉(zhuǎn)換為對居民地要素a和b進行形狀插值。設morphing變換模型表示為 Mid＝f（a，b，g），其中f是通過轉(zhuǎn)向角函數(shù)建立的morphing形狀表達函數(shù)，f（a，b）為在轉(zhuǎn)向角表達形式下對a、b完成的特征匹配，g為一個決定morphing變換程度的參數(shù)，f（a，b，g）為通過以參數(shù)g為位移路徑完成形狀插值。對于任意0≤g≤1，Mid關(guān)于g單調(diào)連續(xù)：當g＝1時，Mid＝a；當g＝0時，Mid＝b；當0＜g＜1時，Mid為介于a與b之間的表達。在一定程度上，參數(shù)g可以表征內(nèi)插圖形與a、b的相似程度；g與比例尺有關(guān)，表示內(nèi)插結(jié)果隨比例尺的不同而變化，g與其對應的Mid所在比例尺TMid的關(guān)系如下

式中，h為一個由實際制圖綜合中Mid與TMid的約定關(guān)系決定的函數(shù)，當TMid為Ta時，g＝1＝h（0），當TMid為Tb時，g＝0＝h（1）。故轉(zhuǎn)換關(guān)系滿足約束條件

h使得g轉(zhuǎn)換為TMid，morphing變換程度由TMid決定?；谵D(zhuǎn)向角函數(shù)的morphing算法由3個步驟組成：①將同名實體圖形轉(zhuǎn)為轉(zhuǎn)向角函數(shù)表達形式；②在轉(zhuǎn)向角函數(shù)表達形式下完成對圖形的特征匹配；③通過改變參數(shù)得到中間狀態(tài)圖形系列。

1.2 矢量圖形的轉(zhuǎn)向角函數(shù)表達

在圖1中，設a的各條邊相等且皆為一個單位，以點I為起始點，沿逆時針方向遍歷所有頂點，將圖形a的轉(zhuǎn)向角函數(shù)反映到直角坐標系中。轉(zhuǎn)向角函數(shù)僅能表達類直角的特性限定了本文方法的適用尺度：僅適用于類直角邊界特征的居民地要素，而不適用于居民地融合產(chǎn)生非直角形狀的情況。鑒于居民地融合大多出現(xiàn)在尺度小于1∶25萬的地圖上，本文方法的適用尺度應大于1∶25萬。

圖1 圖形的轉(zhuǎn)向角函數(shù)Fig.1 Steering angle function of polygon

1.3 基于轉(zhuǎn)向角函數(shù)的邊特征匹配

將同名實體圖形轉(zhuǎn)為轉(zhuǎn)向角函數(shù)的表達形式后，對不同實體的不同轉(zhuǎn)向角函數(shù)表達形式在頻率域進行比較，以發(fā)現(xiàn)二者轉(zhuǎn)向角函數(shù)間的共性與差異，得到二者轉(zhuǎn)向角函數(shù)的變化規(guī)律，進而引入?yún)?shù)表征該變化規(guī)律，用于進行第3步的形狀插值，這即是同名實體的轉(zhuǎn)向角函數(shù)匹配。但不同實體往往具有不等的周長，故對應的轉(zhuǎn)向角函數(shù)具有不同的定義域，導致無法進行對比。如圖2，設圖形a、b各邊長相等，分別為1和3，二者的定義域分別為［0，12］和［0，20］，故轉(zhuǎn)向角函數(shù)無法在區(qū)間［12，20］內(nèi)進行對比。為此，需要首先統(tǒng)一定義域，然后進行邊特征匹配。以圖形周長作歸一化，將轉(zhuǎn)向角函數(shù)定義域統(tǒng)一為［0，1］，轉(zhuǎn)向角函數(shù)轉(zhuǎn)換為

圖2 圖形轉(zhuǎn)向角函數(shù)的直接匹配Fig.2 Direct matching of polygon based on steering angle function

1.3.1 邊特征分析

統(tǒng)一定義域后圖3內(nèi)初始多邊形a的邊中，唯有［0，0.05］、［0.15，0.2］、［0.3，0.35］、［0.4，0.45］、［0.55，0.6］、［0.65，0.7］、［0.8，0.85］、［0.95，1］為同邊，其余均是異邊。a到b的變化，在轉(zhuǎn)向角函數(shù)形式下表現(xiàn)為轉(zhuǎn)向角不變，異邊減短至0，同邊增長了異邊的長度。本文稱此變化方式為同增異減。

實際應用中，不同尺度下的同名實體可能有不同的制圖精度，同邊之間的方位角不一定完全相等，故差值在一定范圍內(nèi)的即可劃定為同邊，否則為異邊。同邊的劃定條件改為

將異邊的劃定條件改為

式中，δ為匹配誤差。匹配誤差據(jù)實際情況而定，其值決定同名圖形轉(zhuǎn)向角函數(shù)匹配精度。

圖3 定義域統(tǒng)一后的轉(zhuǎn)向角函數(shù)匹配Fig.3 Matching of steering angle function unified domain

1.3.2 邊匹配

在統(tǒng)一定義域的基礎上轉(zhuǎn)向角函數(shù)匹配可能存在以下兩個問題：①如圖4中，a的某些邊不能滿足同異邊劃定條件ta?tb，因而無法劃定該邊是同邊還是異邊；②從a到b的變化中，邊t未發(fā)生改變，但在轉(zhuǎn)向角函數(shù)匹配中被劃定為異邊。造成此問題的根本原因在于：圖形轉(zhuǎn)向角函數(shù)定義域的一致性與邊長的差異性之間的矛盾。為此，僅僅統(tǒng)一定義域是不夠的，在此基礎上須進一步進行邊匹配。

圖4 特殊圖形的匹配偏離Fig.4 Matching deviation of particular polygon

圖5 邊分割算法Fig.5 Algorithm of segmentation condition

1.4 基于轉(zhuǎn)向角函數(shù)的形狀插值

在a到b的同增異減變換模型中，異邊表現(xiàn)為連續(xù)縮短直至消失，其縮減力度與參數(shù)g相關(guān)，故有

式中，S為a分割邊集中同邊的總數(shù)，t同總為a分割邊集中同邊的總和。Δt同總表征了分割邊集內(nèi)同邊的變化，含同邊越多的分割子集變化越小。此特性要求面向分割邊集求同邊增量，而非面向單個同邊，亦非整個圖形。異邊的減量與邊長成比例，同增異減變化可理解為異邊轉(zhuǎn)為同邊，故同邊的增量必與邊長成比例

綜上，同名多邊形的同增異減變換模型，也即morphing變換模型，也即Mid的轉(zhuǎn)向角函數(shù)構(gòu)建為

Mid的圖形形狀由a、b和g共同決定。

圖6 同邊的增量Fig.6 Increment of uniform sides

2 試驗分析

為了說明本文方法的可行性和有效性，基于C＋＋語言使用MFC構(gòu)建試驗平臺，于深圳市1∶1萬和1∶5萬居民地地圖中截取部分真實地圖作為試驗數(shù)據(jù)，該數(shù)據(jù)包含文獻［20］提出的建筑物模式數(shù)據(jù)庫中的所有模式，且部分數(shù)據(jù)間具有常見的共邊等拓撲關(guān)系。數(shù)據(jù)的始末狀態(tài)（也即g＝1和g＝0下的圖形）如圖7所示，圖中黑點表示試驗選取的起始點。如1.2節(jié)所述，起始點的選擇對轉(zhuǎn)向角函數(shù)形式下的表達至關(guān)重要，圖7所示試驗數(shù)據(jù)的起始點根據(jù)以下原則進行選擇，可通過試驗證明該選擇原則是否可行：①須選取a、b間距離最近的點作為起始點，距離越近，出現(xiàn)誤匹配的可能性越小，如圖形a—h起始點的選擇；②若存在多對距離最近的點，可在其中選取可決定圖形位置的點作為起始點，如圖形a、b、c、d起始點的選擇；③若存在多對距離最近的點，可在其中選取顧及周圍其他居民地的拓撲結(jié)構(gòu)的點作為起始點，如圖形e、f、g、h、i、j起始點的選擇；④具備距離最近的基本條件，又能顧及圖形位置和拓撲結(jié)構(gòu)的點，是最優(yōu)的起始點，如圖形i、j起始點的選擇。

圖7 試驗數(shù)據(jù)的始末狀態(tài)Fig.7 Beginning and end state of the experimental data

分別令g等于0.9、0.8、0.7、0.6、0.5、0.4、0.3、0.2、0.1，借助試驗平臺繪制出如圖8所示的中間狀態(tài)居民地漸變圖系列。由圖8可知：①本文所述方法適用于所有建筑物模式，整個漸變過程均勻連續(xù)，保持了圖形的重要特征，具有較好的效果。②上述的起始點選擇原則是可行的，試驗結(jié)果效果較好。本文算法中起始點的位置在整個morphing過程始終保持不變，且僅對邊長進行插值，不改變轉(zhuǎn)向角，因而也不存在旋轉(zhuǎn)變化。如圖形a、b、c、d在整個morphing過程中始終保持方形的布局；圖形e、f、g、h、i、j在整個 morphing過程中始終保持與鄰接圖形的共邊、包含的拓撲關(guān)系；圖形k、l盡管相隔較近，在整個morphing過程中并未出現(xiàn)相交或分離。③通過選擇合適的起始點，本文算法可以較好地維護居民地間拓撲關(guān)系的一致性。

為驗證模型的尺度相關(guān)性，以area（a）表示初始狀態(tài)下實體a的面積，以a∩b表示a與最終狀態(tài)下實體b的重合部分，則定義Mid與a的相似度a＿degree為

定義Mid與b的相似度為b＿degree

式中，均減去a、b的重合部分是為了消除a、b本身的相似性對相似度造成的影響。表1列出了不同g值下的內(nèi)插圖形與實體始末狀態(tài)的相似度，可見g值越大（即比例尺越大）中間狀態(tài)Mid與a的重疊度a＿degree越大，與b的重疊度b＿degree越小，故模型參數(shù)g具有尺度相關(guān)性。本文算法的時間復雜度為O（N2），其中，第1步將同名實體圖形轉(zhuǎn)為轉(zhuǎn)向角函數(shù)表達形式的復雜度為O（N）；第2步圖形的特征匹配的復雜度為O（N2）；第3步得到中間狀態(tài)圖形系列的復雜度為O（N）。

表1 內(nèi)插圖形與實體始末狀態(tài)的相似度Tab.1 Similarity of shape at intermediate scale with beginning and end state of polygon

3 總 結(jié)

本文提出了一種利用轉(zhuǎn)向角函數(shù)的面狀居民地morphing方法，該方法將圖形的矢量坐標串的表達形式轉(zhuǎn)換為轉(zhuǎn)向角函數(shù)表達形式，再利用轉(zhuǎn)向角函數(shù)的特性，經(jīng)過邊匹配分析大小比例尺下的兩組圖形的共性邊與差異邊，得到了任意中間尺度的轉(zhuǎn)向角函數(shù)，并構(gòu)建同增異減模型以實現(xiàn)矢量多邊形的morphing變化。本方法經(jīng)試驗驗證適用于多種表達形式的居民地。不足之處在于：在比例尺跨度較大的情況下，居民地的綜合不僅局限于邊界化簡，可能存在居民地合并，本研究只考慮一對一的居民地漸變，沒有考慮居民地合并的情形，后繼將進一步研究適用于一對多的居民地morphing算法。

圖8 建筑物的morphing變換Fig.8 Morphing of building

［1］ JONES C B，WARE J M.Map Generalization in the Web Age［J］.International Journal of Geographical Information Science，2005，19（8－9）：859－870.

［2］ LI Hua，ZHU Guangxi，ZHU Yaoting.A Survey of Object Metamorphosis［J］.Journal of Image and Graphics，2002，7（8）：745－751.（李華，朱光喜，朱耀庭.物體漸變技術(shù)現(xiàn)狀與發(fā)展［J］.中國圖象圖形學報，2002，7（8）：745－751.）

［3］ N?LLENBURG M，MERRICK D，WOLFF A，et al.Morphing Polylines：A Step towards Continuous Generalization［J］.Computers，Environment and Urban Systems，2008，32（4）：248－260.

［4］ PENG Dongliang.A Methodology of Morphing Transformation of Linear Features for Map Continuous Generalization［D］.Changsha：Central South University，2012.（彭東亮.面向地圖連續(xù)綜合的線狀要素Morphing變換方法研究［D］.長沙：中南大學，2012.）

［5］ PENG Dongliang，DENG Min，XU Feng.Morphing Linear Features Considering Their BLG－tree Structures［J］.Geomatics and Information Science of Wuhan University，2012，37（9）：1120－1125.（彭東亮，鄧敏，徐楓.顧及BLG樹結(jié)構(gòu)特征的線狀要素Morphing變換方法［J］.武漢大學學報：信息科學版，2012，37（9）：1120－1125.）

［6］ DENG Min，PENG Dongliang，XU Zhen，et al.A Morphing Method Based on Bend Structures for Linear Features［J］.Journal of Central South University：Science and Technology，2012，43（7）：2674－2682.（鄧敏，彭東亮，徐震，等.一種基于彎曲結(jié)構(gòu)的線狀要素 Morphing方法［J］.中南大學學報：自然科學版，2012，43（7）：2674－2682.）

［7］ PENG Dongliang，DENG Min，LIU Huimin.Morphing Transformation of Linear Features by Using Independent Bend Structures More Sufficiently［J］.Acta Geodaetica et Cartographica Sinica，2014，43（6）：637－644，652.（彭東亮，鄧敏，劉慧敏.更充分利用獨立彎曲結(jié)構(gòu)的線狀要素Morphing變換方法［J］.測繪學報，2014，43（6）：637－644，652.）

［8］ SONG Weijie，JIANG Dawei，HUA Huichun，et al.Convexity－preserving Method for Morphing Compatible Planar Triangulations［J］.Journal of Computer－aided Design ＆ Computer Graphics，2005，17（6）：1252－1257.（宋偉杰，蔣大為，華回春，等.同構(gòu)平面三角網(wǎng)格的保凸變形方法［J］.計算機輔助設計與圖形學學報，2005，17（6）：1252－1257.）

［9］ HE Lei，JIANG Dawei，ZHANG Yongfeng，et al.Shape Blending Based on Representation of Simplified Polygons in the Similar Tangent Space［J］.Journal of Computeraided Design ＆ Computer Graphics，2007，19（3）：304－310.（何磊，蔣大為，張永鋒，等.基于簡化多邊形類正切空間表示的圖形漸變算法［J］.計算機輔助設計與圖形學學報，2007，19（3）：304－310.）

［10］ SEDERBERG T W，GAO P S，WANG G J，et al.2－D Shape Blending：An Intrinsic Solution to the Vertex Path Problem［C］∥Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques.New York：ACM，1993：15－18.

［11］ GOTSMAN C，SURAZHSKY V.Guaranteed Intersection Free Polygon Morphing［J］.Computers and Graphics，2001，25（1）：67－75.

［12］ SHAPIRA M，RAPPOPORT A.Shape Blending Using the Star－skeleton Representation［J］.IEEE Computer Graphics and Application，1995，15（2）：44－50.

［13］ CECCONI A，GALANDA M.Adaptive Zooming in Web Cartography［J］.Computer Graphics Forum，2002，21（4）：787－799.

［14］ LEI Kaibin，YANG Xianze，LI Bo，et al.3D－curves Shape Blending with Constrained Boundary Based on Quaternion Interpolation［J］.Journal of Computer Applications，2007，27（9）：2131－2133，2136.（雷開彬，楊憲澤，李播，等.基于四元素插值的空間曲線邊界約束變形方法［J］.計算機應用，2007，27（9）：2131－2133，2136.）

［15］ YANG Min.Research on Feature Selection Considering Spatial Context in Map Generalization and Its Application［J］.Acta Geodaetica et Cartographica Sinica，2014，43（8）：877.（楊敏.顧及上下文特征的地圖綜合選取方法與應用研究［J］.測繪學報，2014，43（8）：877.）

［16］ ZHOU Qi，AI Tinghua，ZHANG Xiang.A Displacement Field Model to Resolve Multiple Spatial Conflicts［J］.Acta Geodaetica et Cartographica Sinica，2013，42（4）：615－620.（周啟，艾廷華，張翔.面向多重空間沖突解決的移位場模型［J］.測繪學報，2013，42（4）：615－620.）

［17］ HUANG Yafeng，AI Tinghua，LIU Yaolin，et al.Geographic Feature Oriented Ria Coastline Simplification［J］.Acta Geodaetica et Cartographica Sinica，2013，42（4）：595－601.（黃亞鋒，艾廷華，劉耀林，等.顧及地理特征保持的溺谷海岸線化簡算法［J］.測繪學報，2013，42（4）：595－601.）

［18］ YANG Min，AI Tinghua，ZHOU Qi.A Method of Road Network Generalization Considering Stroke Properties of Road Object［J］.Acta Geodaetica et Cartographica Sinica，2013，42（4）：581－587.（楊敏，艾廷華，周啟.顧及道路目標Stroke特征保持的路網(wǎng)自動綜合方法［J］.測繪學報，2013，42（4）：581－587.）

［19］ XU Wenshuai，LONG Yi，ZHOU Tong，et al.Simplification of Building Polygon Based on Adjacent Four－point Method［J］.Acta Geodaetica et Cartographica Sinica，2013，42（6）：929－936.（許文帥，龍毅，周侗，等.基于鄰近四點法的建筑物多邊形化簡［J］.測繪學報，2013，42（6）：929－936.）

［20］ ZHAO Jie，LI Guangyao，PANG Chihai.Research on Building Recognition from Satellite Remote Sensing Image Based on Wavelet［J］.Computer Technology and Development，2008，18（11）：243－246.（趙潔，李光耀，龐池海，等.基于小波變換的衛(wèi)星遙感地圖中建筑物識別［J］.計算機技術(shù)與發(fā)展，2008，18（11）：243－246.）