冯 卡门第33卷第2期
2008年3月
测绘科学
Science of Surveying and M app ing
Vol 133No 12
Mar 1
作者简介：吴小芳(19792)，女，湖北荆州人，讲师，博士，现从事地图制图学和地理信息系统理论与方法研究。E 2mail:s ome wxf@1631com 收稿日期:2007201210
基金项目：华南农业大学校长基金项目(S600-K06162)
吴小芳①
，杜清运②
，胡月明①
，黄茂军
③
(①华南农业大学信息学院地理信息系统教研室，广州 510642;②武汉大学地理信息系统教育部
重点实验室，武汉 430079;③江西财经大学用友软件学院，南昌 330013)
【摘 要】本文首先对移位算法的发展史进行简要介绍，然后，在其基础上，根据各移位算法的思想特征，对各
移位算法进行归纳，将其划分为七类，并对每一类算法的核心思想进行详细论述，最后，对各类移位算法进行评价，分析其优缺点，总结各类算法中的可借鉴思想，为更好地实现移位奠定基础。【关键词】制图综合；移位;Snake 模型；有限元法【中图分类号】P282 【文献标识码】A 【文章编号】100922307(2008)022*******DO I:1013771/j 1issn 1100922307120081021041
1 引言
移位算法，最初起因于为了解决地图综合中比例尺缩放和符号化后引起的要素空间冲突，而产生的算法。制图综合中，对于要素间的各种空间冲突，主要是通过移动相邻的对象以解决空间冲突，满足对象之间的最小间隔要求，并保持要素之间的邻近空间关系。W eibel 和Buttenfield (1988)给出移位的定义:“D is p lace ment concerns the res olu 2ti on of s patial conficts bet w een ma Pele ments in order t o maintain s patial relati on,p r ovide clarity,or fit other ele ments on the map ”，指出移位是解决要素之间的空间冲突，保持要素之间的空间关系，以及要素的清晰易辨性的重要手段。 2 移位算法概述
移位算法的应用发展经历了一个很长的时间，它随着计算机的发展，其算法方式亦发生着很大的变化。从最开始1976年L ichtner 提出的由于直线型道路符号扩张的影响而产生的点移位方程，到80、90年代基于栅格数据结构为主的制图移位方法(Jager,1991)，以及至90年代，随着计算机硬件的飞速发展、内存容量的不断扩充，基于矢量数据结构的制图移位成为主要发展趋势(Bader,1997)，之后，随着制图专家们不断地研究，各种数学思想、力学、物理方法、几何算法不断地引入到制图移位，出现了基于Snake 模型的移位方法(Burghardt,1997)，基于弹簧模型的移位方法(Bobrich,1996)，基于有限元法的移位方法(Hojholt,1998)，基于最小能量的移位方法(Bader,2001)，基于场论的移位方法(艾廷华,2004)，基于Delaunay 三角网移位方法(Ruas,1998)，基于全局平差的移位方法(Harrie,1999)，以及基于矢栅混合的人工模拟移位方法等等(费立凡,2004)。各种方法纷繁叠出，说明了移位算法受到了越来越多专家学者的关注，同时也表明制图移位是一个难以解决的问题，需要各个学科算法思想的交叉融汇来共同解决这个难题。下面就以上的各类移位算法进行详细的分类与介绍。
211 基本的几何方法
L ichtner (1976)通过考虑直线型道路符号扩张的影响因素，提出点移位方程，此方程适用于单条直线型道路符号扩张所引起的点的移位，如图1所示，其中,b A 和b F 分别为原图和缩编图道路符号所代表的实际宽度;m A 和m F 分别为原图和缩编图的比例尺分母;V 0为初始移位量。S i 为移位前某点到道路轴线的距离;V i 为该点应有的移位量,P i 为原图上的某点, P i 为缩编图上P i 移位为后的位置。然而，
在现实问题的处理中，点的移位往往会受到多条方向各异的道路符号扩张的同时影响；而且，若把一栋建筑物多边形的每个转折点分别用此法移位，不能保证所构成的新多边形还保持着原多边形的重要几何特征。
L ichtner (1979)中提出的线移位方法，其基本观点是将移位向量应用到线的每一个节点上。为了确保线之间的最小间距，必须考虑确定线上哪些点需要移位，向哪个方向移位，移多少等问题。为了解决这些问题，该方法引入制图推理知识解决冲突。同时为了回避要素形状的扭曲，将移位传播引入到线的移位中。
N ickers on (1988)在以上方法的基础上，继续深入研究，他发现在移位操作中道路交叉点的重要性，因此，他将道路间的冲突进行分类，着重考虑道路交叉口处的冲突环境。而且用三角过滤(triangle filter )光滑移位以便减少形状的扭曲。几年来,N ickers on 的算法成为道路移位中较好的算法，它很适合平行线的移位，但对于由多条线组成的空间冲突情况，此算法并不能很好地解决这类问题。主要原因是该算法限制了冲突的邻近性，没有考虑多条线的冲突情况，此外，该算法没有考虑线的曲线形态特征。212 栅格方法
Jager E 1(1991)等人提出了基于栅格数据结构的制图移位方法，其特点是处理程序在计算机内存中专门开辟了一个足够大的二维数组，其每个元素由几个字节组成。按照线状制图目标的优先级次序，将
轴线矢量转换为所需的制图符号或与此符号等宽的栅格实线，存入上述数组，并根据最大梯度方向及与此线划轴线的距离，为每条栅格线划的两侧建立一个移位方向垂直于线状符号、移位量由大变小的缓冲带，从而形成栅格式的“移位山”，如图2所示，其中每个栅格像元记录了所需移位的方向和距离。通过栅格数据的探测可知，当有空间冲突发生时，根据所在位置原有栅格所指示的方向和移位大小，对栅格或矢量数据进行移位。
栅格移位方法的优点是计算机能很大程度上探测空间冲突及避免空间冲突的出现，缺点是移位算法的精度和栅格数据的分辨率密切相关，实用上对内存量有较高的要求。
测绘科学 第33卷
另外，它们主要适合于对点状或线状要素的移位
。
213 力学及物理学方法
Bobrich (1996)提出了基于弹簧模型的移位方法，即在各要素点之间建立压力弹簧模型并在次要要素各点间另建扭力弹簧模型，如图3所示，其中,S P 表示位置的精度，即移位前后点的位置变化,S e 表示各段的延长、拉伸,S t 表示各段曲率的变化。根据要素的几何特征设置弹簧的韧性、可变形程度等参数，假定在原始数据情况下，压力弹簧和扭力弹簧的总应力(内部势能)为最小。当道路符号被夸大后，用栅格数据探测空间冲突，加权后的空间冲突的严重性被称为外部势能。改变次要要素的各点位，就会同时改变内、外部势能。用迭代法取得总势能最小为目的，来确定各次要要素的新点位。
Burghardt (1997)采用Snake (active s p lines )方法，其基本思想是将外部能量与内部能量和最小化。当线段的某一部分与另一条线段离得太近，外部能量产生作用。当线段中的某一部分被扭曲了，内部能量产生作用。实际算法处理中，将空间冲突看成是外部能量，将曲线的一阶导数和二阶导数的变化看成是内部能量，并建立数学模型，利用变分法，通过迭代，逐渐改变原来存在空间冲突的、周边次要要素的点位，使得总能量达到最小，如图4所示。此方法主要适用于线状要素的移位。
Hojholt (1998)将地图看成可以形变的材料，采用了结构力学中有限元法(finite ele ment method )，将地图平面划分为多个连续的单元，对每一单元进行移位变形处理。具体操作是，对区域构建约束Delaunay 三角网，将平面划分为多个三角形。然后根据对象要素的属性及可变形的程度，设置不同的
三角网的边值、韧性、及边界条件，即建筑物不允许变形，道路不允许偏移，道路要求等宽；最后，运用FE M 思想解决符号的扩宽引起的空间冲突问题。然而当三角形变形很大时，三角形的一个顶点甚至可能会穿越另一条边而产生三角形的叠置，破坏了拓扑性，可引入了低松弛的迭代程序(Hojholt,2000)解决该问题
。
溶血栓疗法
图5 道路和建筑物冲突的移位结构图Matthias Bader (2001)用最小能量法解决要素移位，其中主要采用Snake 和Elastic Beam 解决道路要素之间的空间冲突，运用限制Delau 2nay 三角网解决建筑物的移位，其中各算法中均利用了有限元的思想对制图移位进
行求解，如图5所示。
214 D el aunay 三角网方法
Bundy,Jone &Furse
(1995)提出，地形图要素可以通过建立简单元数据结构来表示。对二维地图来说，可用三角形作为简单元，因此,
在原始矢量数据的基础上，建立受限的Delaunay 三角网,
得到目标之间的拓扑关系，利用三角网去觉察和解决近似冲突，实现制图移位操作。
Ruas (1998)的算法也是充分利用三角网进行移位，但其算法与Jones 存在差别，其差别表现在Ruas 为了减少构网代价，仅用每个对象的中心点作为三角形的角点，而Jones 是每个对象的节点坐标作为三角形的角点，建立限制Delaunay 三角网。另一个差别是，运用制图推理知识指导移位时,Jones 仅考虑了对象的几何特征，而Ruas 考虑了每个建筑物对邻近要素的不同影响权重的复杂处理过程，允许要素进行移位传播，以便保持对象的空间关系。215 全局平差法
Harrie (1999)用几何、拓扑限制条件解决道路和街区的冲突。它根据对象的类型、对象可否移动、可否改变几何形状等属性来确定移位过程中的不同的要素移位类型，对于每种移位类型，分别指定一系列的约束条件，并根据移位约束重要性的不同，为每一个约束设置不同的权重因子，然后，使用线性函数综合考虑这些约束，将限制约束条件转换为数学语言，以矩阵方程的方式参与运算，利用了最小
二乘平差法(LS A )求得最佳移位结果，保证以最小的几何变形为基础解决空间冲突。此算法需要改进的是将限制条件转换为数学语言需要做更多的研究。
Sarjakoski and Kil palainen (1999)详细的阐明并发展了Hojholt (1998)和Harrie (1999)提出的方法，并重点将这些方法与LS A 的一般理论和实践相连接。同步解决了过程中数据集的所有形变和移动，另外还采用迭代共轭梯度法(CG M )解决最小二次平差的线性方程系统。然而这种方法还不够成熟，有待改善。
Sester (2000)提出了将制图综合中简化和舍弃操作与LS A 相结合。对所有的对象点建立基于单元数据结构的约束Delaunay 三角网(Bundy,Jone&Furse,1995)来识别冲突，考虑由制图目标的几何特征所构成的内部限制，以及由各制图目标之间的规定距离所决定的外部限制条件，利用最小二乘平差方法解决内部限制和外部限制问题，来处理对象的移位。
全局平差法的优点是，通过一次性平差，可以同时解决制图综合中的一系列问题(包括移位)，其结果就是由权矩阵决定的各种要求之间的妥协方案，缺点是计算量较大。其次，移位后的结果往往与经典制图的结果不太一致，如被移位的建筑物面积普遍会变小。这在一个街区内(不包括路面)虽较好地维持了黑白对比(建筑与非建筑面积之比)，但对整幅图来说，却缩小了黑白对比。216 论场论方法
W illia m A 1Mackaness (1993)讨论了冲突的本质，驳斥了仅对处于冲突中的两个对象进行同时移位
的思想。其算法是通过聚类分析，识别产生空间冲突的对象，然后将对象作为一个整体进行移位操作，而不是对产生冲突的两个对象进行移位处理，以保证对象之间的拓扑关系(空间关系)。它是以对象中某一个点作为中心点，采用等比例的射线算法进行移位，如图6所示。实际运用中，可根据中对象的定位优先级，设置不同的移位权重，将定位等级最高的点作为中心点，以保持定位等级最高的点尽量不移位，然后使用改进后的修正比率的射线移位法(modi 2fied p r oporti onal radial dis p lace ment )去解决空间冲突，实现制图移位。
艾廷华(2004)采用场论分析的移位思想，解决因街道拓宽后与街区产生的空间冲突。它考虑了街道拓宽对不同建筑物之间作用力的衰减性，认为街区块多边形边界的收缩产生向街区块内部逐步传递并衰减的作用力，从而促进建筑物多边形的空间位置的移动。在移位场中目标的运动
8
11
第2期期 吴小芳等
制图综合中移位算法概述分析图6 等比例射线算法移位方向与运动距离由矢量和运算及梯度衰减函数计算完成。其算法思想是基于Del aunay 三角网建立了类似于Voronoi 图的建筑物剖分结构，用于表达移位场模型的“等距离关系曲线”，然后利用矢量和运算及梯度衰减函数计算移位场中目标的运动方向与运动距离。217 矢量栅格结合方法
费立凡(2004)主要研究符
号化后道路与建筑物的空间冲突问题，采用矢栅混合的数据
模型，利用栅格数据模型发现冲突，矢量数据模型解决冲突。在解决建筑物与道路的冲突，根据建筑物受不同道路符号扩张的影响，对建筑物进行分类，对于每一类采用不同的移位方法解决冲突。此外，该算法思想中模拟了人工制图中处理移位的原则方式，考虑了人的视觉感受等影响因素，共同解决制图移位，以便移位后图形显示满足常规地图的显示效果，更符合人的视觉感受需求。
3 移位算法评价与分析
通过对以上的各类移位算法进行分析，发现各类算法均有各自的优缺点，对各类移位算法的具体评价如表1所示:
表1 移位算法比较与评价
移位方法核心思想
优点
缺点
解决复杂
冲突情况适合算法的要素密集程度
基本的几何方法
先判断空间冲突，然后计算冲突中的点、
线节点的位移矢量来达到移位的目的
计算公式简单，计算量较小，可保证解决最初的冲突问题缺乏从整体的角度考虑和
控制图形的空间冲突。未
考虑引发新问题的处理弱
低
基于力学及物理学方法
将对象的内部几何特征以及对象之间的空
比基尼主播
间冲突表示为力学中内能和外能，其中，外能作用产生移位，内能作用保持几何外形，当内能与外能之和最小，实现移位的最佳结果
以单个空间冲突问题为出发点，以解决整体的冲突问题考虑整体的冲突问题，最终结果并不能保证最初的空间冲突问题得以解决强中
全局平差法
综合考虑对象的约束限制条件，将其转换为数学的表达形式，然后采用了最小二乘平差的方法，解决整体问题一次性可以同时考虑制图
综合中的一系列问题
计算量大，另外将约束条
件转化为数学语言还需做
更多研究较强中
基于三角网的方法
通过三角网建立几何要素之间的空间关系、拓扑关系的联系，然后利用要素之间的三角网，发现空间冲突，控制移位后的后继冲突，实现移位保证制图要素间的拓扑关系不易受到破坏预先、全面建立受限Delaunay 三角网代价太大，并不能简化移位和变形所要解决的问题强高
论和场论方法将产生冲突的对象作为研究对象，从整
体的角度研究内各对象的移位方向、移
位距离，解决空间冲突
保证各对象之间的空间关系以及整体空间布局不变对象的建立以及场的传
播范围难以准确控制
较强中
矢量栅格混合
将矢量和栅格数据进行优势互补，利用栅
格探测空间冲突，利用矢量数据进行移位
计算
提高了检测空间冲突的速度，加速制图移位矢量和栅格两套数据消耗
更多的内存
强高
因此，从以上的方法比较中，我们可以得出以下结论:
1)移位算法中可辅助利用栅格数据快速探测空间冲突因为栅格数据构建简单、快捷，而且通过栅格数据只需判断两要素是否位于同一栅格内，即可快速探测要素之间的是否可能产生空间冲突。
2)运用论及场论思想解决对象之间空间冲突时，能有效地保证要素之间的空间关系及空间布局
论及场论思想将产生冲突的对象作为研究对象，从整体的角度研究内各对象的移位方向、移位距离，解决空间冲突。它能弥补常规方法中以两个冲突要素为研究单元，导致多个对象整体的空间布局及相互空间关系可能发生变化的缺陷，有效地保证各对象之间的空间关系以及整体空间布局不变，维护要素之间的相对位置关系,
3)Snake 、Elastic bea m 方法适合于解决线状要素之间的空间冲突
Snake 、Elastic bea m 方法是借助力学和物理学的思想，将对象的内部几何特征以及对象之间的空间冲突表示为力学中内能和外能，其中，外能作用产生移位，内能作用保持几何外形，当内能与外能之
原子核物理学和最小，即总能量达到最小状态，实现移位。它能较好地模拟要素上某一点的移位对邻近点的影响情况，反映要素内部相互关联性，因此多适合线状要素的移位。
4)基本的几何方法有利于解决要素之间简单空间冲突
基本的几何方法多考虑单条直线型道路符号扩张所引起的点的移位，它先判断空间冲突，然后计算冲突中的点、线节点的位移矢量来达到移位的目的，其计算公式较简单、易理解和计算量较小。该思想能保证解决最初的冲突问题，适用于处理简单冲突的情况。
5)三角网可辅助移位中空间关系的维护
三角网在维护空间关系方面，其具有独特的优势。首先利用三角网可快速获取要素之间的空间拓扑关系，然后通过移位后要素之间的三角网变化，可快速觉察和解决近似冲突，控制后继冲突，保证要素间的拓扑关系不易受到破坏。
4 小结
分析以上诸多移位算法，我们可以发现，移位是一个难题，如何解决好制图移位，仍需要不断地努力、完善，目前，移位至今仍由制图人员交互实施，完全的自动移位算法仍没有实现，仍需要各个学科算法思想的交叉融汇来共同解决这个难题。
参考文献
[1]
Bader M ,W eibel R 1Detecting and Res olving Size and Pr oxi m ity Conflicts in the Generalizati on of Polygonal Map s [C ]//18th Conference of the I CA 11997:1525-
9
11
测绘科学 第33卷
1534,St ockhol m1
[2]Burghardt D,M eier S1Cart ographic D is p lace ment using
the Snakes Concep t[C]//Se mantic Modeling for the
Acquisiti on of T opografic I nf or mati on fr om I m ages and M ap s119971
[3]Harrie L E1The Constraint Method for Solving Spatial
Conflicts in Cart ographic Generalizati on[J].Cart ography
and Geographic I nf or mati on Science,1999,26(1)1 [4]Hojholt P1S olving Local and Gl obal Space Conflicts inM a
PGeneralizati on U sing a Finite Ele ment Method Adap ted
fr om Structural M echanics[C]//Pr oceedings8th I nter2
nati onal Sy mposiu m on Spatial Data Handling,1998:679
-689,Vancouver,Canada1
[5]Hojholt P1S olving Space Conflicts in M a PGeneralizati on:
U sing a Finite Ele ment M ethod[J].Cart ography and
Geographic I nf or mati on Science,2000,27(1):65-741[6]Jones C B,Bundy G1L,W are J M1Ma PGeneralizati on
安徽地方志
with a Triangulated Data Structure[J].Cart ography and
Geographic I nfor mati on Syste m s,1995,22(4)1
[7]李娜，杜清运，等1制图综合中道路与建筑物的移位
研究[J].测绘科学,2006,31(4)1
我的新校园[8]Sarjakoski T,Kil pel ainen T1Holistic Cart ographic Gen2
eralizati on by Least Squares Adjust m ent f or Large Data
Sets[C]//Pr oceedings of the19th I C A/AC I Confer2
ence,1999,O ttawa1
[9]SesterM1Generalizati on based on Least Squares Adjust2
ment[J].Pr oceedings of the19st I nternati onal Cart og2
raphic Conference(I CC),1999,O ttawa1
[10]艾廷华1基于场论分析的建筑物的移位[J].测绘
学报,2004,33(1):89-941
[11]费立凡1用计算机模拟人类制图员解决地图缩编中的图形
冲突[J].武汉大学学报・信息科学版,2004,29(5)1
Su mmary and ana lysis of d ispl ace m en t a lgor ith m i n cartograph i c genera li za ti on Abstract:I n the paper,the devel opment course of dis p lace ment algorith m is illustrated firstly1Then,on the basis of analyzing all kind of dis p lace ment algorith m s,the algorith m are reduced and divided int o seven classes1A s t o every class of alg orith m,its main thought is illustrated in detail1A t last,every class of algorith m is analyzed and evaluated,and its advantages and disadvantages are lis2 ted out1The good algorith m and thought are su mmed u Pin order t o i m p r ove the devel opment of dis p lacement1 Key words:cart ography generalizati on;dis p lace ment;Snake model;finite ele ment method(FE M)
WU X iao2fang①,DU Q ing2yun②,HU Yue2m ing①,HUAN G M ao2jun③(①College of I nf or mati on,S outh China Agricultural Uni2 versity,Guangzhou510642,China;②Key Laborat ory of GI S,M inistry of Educati on,W uhan University,W uhan430079,China;
③School of Soft w are,J iangxi Finance&Econom ics University,Nanchang330013,China)
(上接第106页)
4 结束语
1)实际试验结果表明,S WDC24数码航空相机的高程精度最高可达1/10000以上，达到了与平面精度相当的水平，这是传统胶片相机和国外同类型面阵相机目前所不能及的，说明拼接模型是稳定可靠的，相机设计也是合理的。
2)理论精度与实际精度相吻合，从理论上证明了S WDC系统设计的科学性和可行性。
3)由于理论的不严密性(线性平移)引起的误差很小，一般情况下可以忽略。
4)高冗余影像资料(航向80%-90%重叠，旁向60%重叠)精度略高于常规摄影影像资料(航向60%重叠，旁向30%重叠)的精度，在精度可靠性方面可提高1倍。
参考文献
[1]牛瑞，方勇1航测相机的发展[N].中国测绘报,
2007,(69)1
[2]张祖勋1航空数码相机及其有关问题[J].测绘工
程,2004,13(2):1251
[3]Leberl F,et al1The U ltraCa m Large For mat Aerial D igital
Ca mera Syste m[J].Pr oceedings of the American Socie2
ty ForPhot ogrammetry&Re mote Sensing,Anchorage,
A laska,20032051
[4]王之卓1摄影测量原理[M].北京：测绘出版
社,19791
[5]冯文灏1近景摄影测量[M].北京：武汉大学出版
社,20022021
[6]Tang L,D rstel C,Jacobsen K,Hei pke C,H inz A1Ge2
ometric accuracy potential of the D igital Modular Camera
[J].Pr oc1I A PRS,Vol1XXX III,Am sterda m,20001 [7]R A lamus,W Kornus,J Talaya1Studies on DMC geome2
try[J].I SPRS Journal of Phot ogra mmetry&Remote
Sensing2006,60:37523861
M os a i c m odel of S WDC24l arge for ma t aer i a l d i g it a l cam era and accuracy ana lysis of stereo mapp i n g Abstract:S WDC24is an aerial digital ca mera that integrated by four non2metric cameras and has a large f or mat1The main char2 acteristic is that it has high accuracy on height p recisi on,can be more than1/10000at most1This paper discusses the generati on p rin2 ci p le of virtual i m age and de monstrates the results of GPS2supported aerial triangulati on on the test bl ock of Beijing1Fr om the vie w of convergent phot ography,the geometric err or and accuracy of stereo mapp ing are analyzed in detail,which p r ovides a theoretical basis for op ti m izing on perf or mance,analyzing of err or and s olving of p r oble m in p ractice1
Key words:S WDC24;aerial digital camera;virtual i m age;convergent phot ography;nor mal phot ography
L I J ian①②,L I U X ian2lin②,L I U Feng2de②,ZHAO L i2ping②,L I J ing②,L I U L ei③(①School of I nf or mati on Engineering in Re2 mote Sensing,W uhan430079,China;②Chinese Academy of Surveying and Mapp ing,Beijing100039,China;③Geoinf or mati on Science and Engineering College,Shan Dong University of Science and Technol ogy,Q ingdao266510,China) 021
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议