基于最小二乘的建筑物多边形的化简与直角化.pdf

第3 7 卷第5 期 2 0 0 8 年9 月 基于最 - - - L 中国矿业大学学报 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y V 0 1 ．3 7N o ．5 S e p ．2 0 0 8 乘的建筑物多边形的化简与直角化 刘鹏程，艾廷华，邓吉芳 武汉大学资源与环境科学学院，湖北武汉4 3 0 0 7 9 摘要依据建筑物多边形的图形特点分析了其在地图综合中两类处理模型化简与直角化．在视 觉的“自然法则”下，设定建筑物多边形在不同尺度下的凹陷与突出的长度阅值，并在此阈值下将 建筑物多边形的点进行分组，进而在最小二乘平差模型下直线拟合组内各点以实现对其化简．针 对直角化问题，提出了限制条件下的不等权直角化平差模型，即在多边形相邻的两边相互垂直的 条件下使各点改正距离的加权平方和达到最小，保证了建筑物的整体位移较小，从而最大可能地 避免了与其相邻地物的位置冲突．该模型已成功用于大比例尺综合缩编软件G e n T o o l ，在地图综 合生产中获得了较为实用的效果． 关键词地图综合；最小二乘平差；特征点；线性拟合；直角化 中图分类号P2 8 5 ．3文献标识码A文章编号1 0 0 0 1 9 6 4 2 0 0 8 0 5 0 6 9 9 - 0 6 S i m p l i f i c a t i o na n dR e c t a n g u l a r i t yo f B u i l d i n g P o l y g o nB a s e do nL e a s tS q u a r e sA d ju s t m e n t L I UP e n g c h e n g ，A IT i n g h u a ，D E N Gj i f a n g S c h o o lo fR e s o u r c ea n dE n v i r o n m e n tS c i e n c e ，W u h a nU n i v e r s i t y ，W u h a n ，H u b e i4 3 0 0 7 9 ，C h i n a A b s t r a c t B a s e do nf i g u r ec h a r a c t e r i s t i c so fb u i l d i n g - p o l y g o n ，t w om o d e l so fs i m p l i f i c a t i o na n d r e c t a n g u l a r i t yo fb u i l d i n g p o l y g o ni nm a pg e n e r a l i z a t i o nw e r ep r e s e n t e di nt h ep a p e r ．A c c o r d i n gt ot h ev i s u a l “n a t u r a lp r i n c i p l e ”。f i r s t l yt h ed i s t a n c et h r e s h o l do fc o n v e xa n dc o n c a v eo f b u i l d i n g p o l y g o na t d i f f e r e n ts c a l ew a ss e t ，t h e na l lp o i n t so fb u i l d i n g p o l y g o nb a s e do nt h e t h r e s h o l dg r o u p e d ，f i n a l l yt h eL e a s tS q u a r e sA d ju s t m e n te m p l o y e dt ol i n e a r i z ea l lt h ep o i n t so f e a c hg r o u ps ot h es i m p l i f i c a t i o no ft h eb u i l d i n g p o l y g o na t t a i n e d ．A st or e c t a n g u l a r i t yo fb u i l d i n g - p o l y g o n ．au n e q u a l w e i g h tr e c t a n g u l a ra d ju s t m e n tm o d e lw i t hl i m i t e dc o n d i t i o nw a sp r o p o s e d ．T h em o d e lg u a r a n t e e ds u mo fw e i g h ts q u a r e so fd i s p l a c i n ga m o u n to fe a c hp o i n ti sm i n i m u mu p o nc o n d i t i o nt h a tt w on e i g h b o r i n ge d g e so fb u i l d i n g - p o l y g o na r ep e r p e n d i c u l a re a c h o t h e r ．T h et w om o d e l sh a v eb e e np r o v e dp r a c t i c a li nG e n T 0 0 1 ．al a r g e - s c a l em a pg e n e r a l i z a t i o n s o f t w a r e ． K e yw o r d s m a pg e n e r a l i z a t i o n ；L e a s tS q u a r e sA d ju s t m e n t ；c h a r a c t e r i s t i cp o i n t ；1 i n e a r i z a t i o n ； r e c t a n g u l a r i t y G I S 表达的地理要素可以区分为两类一类 自然形成的，如湖泊、山脉、植被；另一类是人造 ，如道路、建筑物、管线等．人造地物是根据设计 师、规划师预先制定的设计方案生成的，往往具有 特定的几何特征、规范的结构模式和艺术化的人文 特色．针对人造地物的G I S 存储与加工处理应充 收稿日期2 0 0 7 1 1 1 3 基金项目国家高技术研究发展计划 8 6 3 项目 2 0 0 7 A A l 2 2 2 0 9 } 国家科技支撑计划项目，教育部新世纪优秀人才支持计划项目 N C E T 0 5 0 6 2 3 ；国家自然科学基金项目 5 0 3 7 6 0 7 0 作者简介刘鹏程 1 9 6 8 一 ，男，湖北省潜江市人，工程师，博士研究生，从事地图综合与G I S 可视化表达方面的研究． E - m a i l l i u p c 3 0 0 0 t o m ．c o r nT e l ；0 2 7 8 7 6 6 1 4 2 6 ，1 3 8 0 7 1 1 2 7 6 9 是的 万方数据 7 0 0中国矿业大学学报第3 7 卷 分顾及这些特征，在数据采集与建库中要尽量保持 它们原有的特征．建筑物多边形的边正交特征便是 一个典型的例子，现有的大比例尺数字地图，往往 是通过野外数字测绘的方式直接生产，或者是在原 有纸张地图、航摄图基础上数字化而来，由于误差 的出现，图形的内角与房屋的实际直角产生偏差， 因而建筑物多边形的直角化处理成为G I S 数据处 理的重要内容之一． 相对于水系、植被等自然地理要素而言，建筑 物多边形有如下特点1 形状一般不为狭长的带 状，各点相对较为集中且点间距相对均衡；2 大 部分多边形的内角为直角，通常至少有2 个内角是 直角；3 其最小外接矩形的面积与其本身的面积 差较小，多边形凸率接近于1 ；4 有些建筑物的形 状呈现阶梯状分布，不宜采用D o u g l a s P e u c k e r 法 进行化简．针对这些特点，本文采用最d x - - 乘平差 模型对建筑物多边形进行化简，对凹陷与凸起部分 通过特征点的识别进行分组，进而直线拟合各组的 点以完成其形状的化简，同时利用最小二乘平差模 型对建筑物多边形进行直角化处理． 在大比例尺地形图 尤其是1 5 0 0 ～1 1 万 城镇地区的地形图 中，建筑物多边形无论在地图 的数值载负量，还是在地图的面积载负量中均占很 大的比重，因而建筑物多边形的化简是大比例尺地 图综合的重要内容．长期以来，很多研究地图综合 的学者都对多边形的化简进行了研究文献[ 1 ] 研 究了基于栅格结构和数学形态学滤波方法的多边 形的移位，主要通过多次运用数学形态学腐蚀、膨 胀等算子对栅格数据进行处理，其运算量较大，针 对的是栅格数据；文献[ 2 ] 提出了矩阵差分组合进 行建筑物的化简，其流程包括旋转多边形至水平 方向、栅格化、分解成多个矩形、化简，最后旋转到 原来的方向；文献[ 3 ] 根据点位的夹角与前后边的 长度关系探讨了最小二乘方法进行建筑物的化简 与移位，具有一定的实用价值，但主要针对直角多 边形；文献[ 4 3 提出了渐进式建筑物多边形化简的 方法，对建筑物多边形的一些特例进行了分析，并 给出了具体综合的方法；文献[ 5 - 6 ] 利用带约束 D e l a u n a y 三角网探测和化简多边形，其针对的是 自然地理要素．总之，这些化简处理方法只考虑了 地图综合的单个约束指标，即形状的化简和定位精 度的化解．本文采用最小二乘原理将这2 个指标综 合起来考虑，在保证形状得到简化表达的同时，使 得定位精度程度保持最大． 1 基于最小二乘的建筑物多边形的化简 1 ，1 建筑物多边形特征点的探测 建筑物多边形主要是由相互垂直的弧段构成， 一般可分解成多个大小不一的矩形心] ．对其化简的 目的是在保持多边形整体轮廓一致的前提下，删除 若干个小的凸起矩形，补平若干个凹陷矩形．在多 边形的点集中，总存在若干能控制多边形整体轮廓 的点，这些点相对其它点而言，化简后位移距离较 小，本文称这些点为建筑物多边形的特征点．特征 点的探测是本算法的第一步，实际的计算中是将多 边形的所有边进行分组，各组的两端点即为特征 点． 对常规的地图，可根据比例尺计算出最小可视 距离，但在多尺度地图综合中最小可视的实地距离 不仅与目标比例尺有关，而且与源地图的比例尺有 关．这里按“自然规律”的综合法则来计算[ 7 ] F S 。D [ 1 一S 。／S 。] ， 式中F 为目标比例尺下图上最小可视距离对应 的实地距离；S 。为目标比例尺分母；D 为最小可视 的距离，取值为0 ．3 ～0 ．6m m ；S 。为源数据比例 尺分母． 在源比例尺为1 20 0 0 、目标比例尺为1 l 万，取最小可视距离D 一0 ．4m m ，计算得F 3 ．2 m ．本文以F 作为凸起和凹陷的距离阈值来探测多 边形的各点并进行分组． 建筑物分组的具体步骤 1 将多边形的坐标点按逆时针方向排序；N 为多变形点的总数．设置4 个变量A ，B ，E ，F 表 示当前要判断边的点号，其中A ，B 用于顺时针方 向搜索，E ，F 用于反时针方向搜索．设置变量S 表 示第1 组的起点． 2 找到最长的一条边，该边两个端点的序号 为n ，n 1 ，初始化一个整数链表L I S T ，将n ，花 1 插入该链表．令A E 一咒，B _ - - F n 1 ． 3 沿A 向顺时针方向搜索两个点，其点号A A 一2 ％N ，B 一 B 一2 ％N ． 4 在L I S T 对应的点构成的弧段中，存在若 干与A B 平行 包括近似 的弧段，计算A B 到这 些弧段的最大距离d ，以及A B 到“ 一九 1 的夹 角a ． 5 如果d F 或者d F 或者d F ，终止 第1 组顺时针方向的搜寻，设起点S 一1 ；按逆时针 搜寻2 点的下两点3 ，4 ；此时与组内起始边近似平 行弧段仍只有1 2 ，计算3 到1 2 边的垂距d 。。 和1 2 到3 4 的夹角a ，存在d 一 i 0 ． 即对多边形的任意一点，其权为与之相关的两 弧段长度和的平均值与多边形的周长的比值．其理 由i 在野外测量及栅格矢量化采集的数据中，建 筑多边形长边相对短边精度高，因而长边对应的点 权应较大；2 在直角化的化简中，除了应考虑点位 的变化外，还应使多边形的面积变化尽可能小．面 积的变化与点位位移的大小和点位对应边长的长 度有关，对相同的点位位移，如果与之相连的边长 越长，面积变化则越大 如图4 ．在如图4 a ，b 中A 与A 有相同的位移，但A ，B 。，A ，D ，却长于A z B 2 ， A 。D 。，因此，面积的变化 阴影部分 图4 a 大于图 4 b ．为了使直角化后面积增量尽可能小，长边对应 的点位移距离应小于短边对应的点；即长边对应的 点坐标的权应大于短边对应的点坐标的权．表1 反 映了等权与不等权直角化处理后，建筑多边形面积 的变化，显然经过不等权直角化处理后的面积变化 较小． 图4 点位移动引起面积变化 F i g ．4 A r e ac h a n g i n gc a u s e db yp o i n td i s p l a c e m e n t 表1等权与不等权直角化后面积变化的比较 T a b l e1 C o m p a r i s o no fa l o f tb e t w e e ne q u a l - w e i g h t a n du n e q u a l - w e i g h tr e c t a n g u l a r i t y m 2 2 ．2 基于最小二乘平差直角化模型 由于并非所有建筑物的内角均应为直角，且其 长边与短边在直角化处理中影响力 权 不同，因 此，提出了带限制条件的建筑物多边形不等权的局 部直角化的最小二乘算法． 根据最小二乘平差模型，本问题中观测值与待 求未知数均是多边形各点的坐标，为了与最／b - - 乘 平差模型的一般式相符，对于点i ，原始坐标为 工；，y ； ，假定坐标观测值的改正数为 u ．，口，． ，坐 标未知数的改正值为 也．，屯． ，坐标的近似值为当 前坐标 o ；，y 。 押 1 i 0 ，，l 为多边形点的个 数 ，则其误差为 万方数据 第5 期 刘鹏程等基于最小二乘的建筑物多边形的化简与直角化7 0 3 髓“ O a r i ≥j 对所有点的误差方程用矩阵形式表示为 V B X l ， 式中V [ 巩，％，⋯‰口，。] - ； x 一[ 疋。屯。⋯疋。艿，．] j l t ； 厂1 0⋯001 01⋯00 B 1 ． ．． ．I ； l f L00⋯01J2 。孙 正的范围内，不作直角化处理，点1 ，4 ，5 ，6 ，7 均被 直角化，各点的移动相对较小．实验证明，运用该方 法实现房屋直角化的效果十分理想．图4 即为对地 1 图上某一块居民地的房屋进行直角化前后的形状 对照，可以看出，经过直角化处理后的房屋，其各个 拐角已经很好的逼近了直角．图6 是直角化后的整 体效果． 下面给出未知参数的限制条件多边形点i 校 正后为直角，则对应的两边相互垂直，则其两直线 斜率的乘积为一1 即k 卜。k ； 一1 ，则i 点对应的 直角限制条件为 五 疋．一z 卜1 一以， x ．- x 啦 】一z i 一疋。 弘 屯；一Y 卜l 一或。 y i 1 啦 l Y { 一啦 0 ． 线性化处理后得 x i X i 1 疋。。 Y i y 斗1 屯，。 z 斗1 z 扣l 一2 x f 疋 y 件1 Y 扣l 一2 y f ＆ z f z 卜1 疋。 Y i Z ／- - 1 屯“1 z f z 卜1 z 斗l X f y i Y 卜1 j ，f l Y f 0 ． 由于建筑物多边形存在非直角的情况，对于 任意一角口，当且仅当7 0 。 口 1 1 0 。或2 5 0 。 口 2 9 0 。，进行直角化处理，即存在限制条件．将所有 点的限制条件用矩阵形式表示，则有 A n 2 。X W 烈1 0 ． 2 由式 1 ， 2 ，在满足加权观测值改正值的平方和 为最小时，即V 1 P Y m i n ，得其法方程‘8 1 f B l P B X A 7 K B 7 P ／ 0 ， 2 3 I A X W 0 ， 式中K [ 志，足z ⋯五J ] 聂。，k 』为附加的待求实参 数，歹为限制条件的个数． 解式 3 易得各个坐标点的改正值，进而得到 所有点直角化后的坐标． 图5 为建筑物多边形直角化过程，反映了多边 形直角化的效果，其中点2 ，3 其对应的点位不在校 a 多边形原图 b 直角化点位的位移 c 直角化后多边形 图5 建筑物多边形直角化过程 F i g ．5B u i l d i n gp o l y g o nr e c t a n g u l a r i t yp r o c e s s i n g a 直角化处理前 b 直角化处理后 图6 直角化处理整体效果 F i g ．6P o s t r e c t a n g u l a r i t yw h o l ee f f e c t i v eg r a p h 3 结论 本文介绍了在大比例尺的地图综合中，利用最 小二乘平差模型对建筑物多边形进行化简和直角 化的方法，并结合实际进行了分析．基于弧段分组 的最小二乘线性拟合模型基本能解决直角建筑物 多边形的化简，但需要人为的设定其化简的阈值， 对长度有较大变化的多边形还需重新设定阈值，因 此，这一算法还需进一步研究．而对于不等权最小 二乘多边形直角化模型，已较为彻底的解决了建筑 物多边形的纠正，具有较好的应用价值． 参考文献 [ 1 ]S UB ，L IZ h i - l i n ．L O D W I C KG ，e ta 1 ．A l g e b r a i c m o d e l sf o rt h ea g g r e g a t i o no fa r e af e a t u r e sb a s e do n m o r p h o l o g i c a lo p e r a t o r s [ J 3 ．I n t e r n a t i o n a lJ o u r n a lo f G e o g r a p h i c a lI n f o r m a t i o nS c i e n c e ，1 9 9 7 ，1 1 3 2 3 3 2 4 6 ． [ 2 ] 郭仁忠，艾廷华．制图综合中建筑物的合并与化简 [ J ] ．武汉测绘科技大学学报，2 0 0 0 ，2 5 1 2 5 2 9 ． ． G U OR e n - z h o n g ，A Iq ‘i n g - h u a ．S i m p l i f i c a t i o na n d a g g r e g a t i o no fb u i l d i n gp o l y g o ni n a u t o m a t i cm a p g e n e r a l i z a t i o n [ J ] ．J o u r n a lo fW u h a nT e c h n i c a lU n i 。 v e r s i t yo fS u r v e y i n ga n dM a p p i n g ，2 0 0 0 ，2 5 1 2 5 2 9 ． [ 3 3S E T E RM ．G e n e r a l i z a t i o nb a s e do nl e a s ts q u a r e sa d j u s t m e n t [ c ] ／／I n t e r n a t i o n a lA r c h i v e so fP h o t o g r a m 万方数据 7 0 4中国矿业大学学报 第3 7 卷 [ 4 ] [ 5 ] [ 6 ] m e t r yA n dR e m o t eS e n s i n g ．A m s t e r d a m [ s ．n ．] ， 2 0 0 0 9 3 1 - 9 3 8 ． 郭庆胜．地图自动综合理论与方法[ M ] ．北京；测绘 出版社，2 0 0 2 1 2 4 1 2 8 ． 艾廷华，郭仁忠，陈晓东．D e l a u n a y 三角网支持下的 多边形化简与合并[ J ] ．中国图像图形学报，2 0 0 1 ，6 7 7 0 3 7 0 9 ． A IT i n g - h u a ，G U OR e n - z h o n g ，C H E NX i a o - d o n g ． S i m p l i f i c a t i o na n da g g r e g a t i o no fp o l y g o no b j e c ts u p p o r t e db yD e l a u n a yt r i a n g u l a t i o ns t r u c t u r e [ J ] ．J o u r - h a lo fI m a g ea n dG r a p h i c s ，2 0 0 1 ，6 7 7 0 3 7 0 9 ． 张晶，周烨，刘瑜．S D S 模型化简合并多边形 的一个改进算法研究[ J ] ．中国图像图形学报，2 0 0 6 ， 1 1 7 1 0 1 I - 1 0 1 6 ． Z H A N GJ i n g ，Z H O UY e 。L I UY u ．A ni m p r o v e da l - g o r i t h mf o rs d sm o d e lb a s e dp o l y g o ns i m p l i f i c a t i o n [ 7 ] [ 8 ] [ 9 ] a n da g g r e g a t i o n [ J ] ．J o u r n a lo fI m a g ea n dG r a p h i c s ， 2 0 0 6 ，1 1 7 1 0 1 1 - 1 0 1 6 ． L IZL ，o P E N S H O WS ．A l g o r i t h m sf o ra u t o m a t e d l i n eg e n e r a l i z a t i o nb a s e do nan a t u r a lp r i n c i p l eo fo b - j e c t i v eg e n e r a l i z a t i o n [ J ] ．I n t e r n a t i o n a lJ o u r n a l o f G e o g r a p h i c a lI n f o r m a t i o nS y s t e m s 。1 9 9 2 ，6 5 3 7 3 3 8 9 ． 於宗焘，鲁成林．测量平差基础[ M ] ．北京测绘出 版社，1 9 9 4 3 5 5 0 ． 刘大杰，盂晓林．直角与直角元素数字化的数据处 理[ J ] ．武汉测绘科技大学学报，1 9 9 7 ，2 2 2 ；1 2 5 1 2 8 ． L I UD a j i e ，M E N GX i a o - l i n ．D a t aq u a l i t yo fl i n ea n d r e c t a n g l ef e a t u r ei ng i ss p a t i a ld a t a b a s e [ J ] ．J o u r n a l o fW u h a nT e c h n i c a lU n i v e r s i t yo fS u r v e y i n ga n d M a p p i n g 。1 9 9 7 ，2 2 2 1 2 5 1 2 8 ． 责任编辑邓群 上接第6 9 3 页 [ 8 ] P E N GY u x i n g ，Z H UZ h e n - c a i ，C H E NG u o - a n ，e t a 1 ．E f f e c to ft e n s i o no nf r i c t i o nc o e f f i c i e n tb e t w e e n l i n i n ga n dw i r er o p ew i t hl o ws p e e ds l i d i n g [ J ] ．J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y ． 2 0 0 7 ，1 7 3 4 0 9 4 1 3 ． [ 9 ] J B ／T 1 0 3 4 7 2 0 0 2 ．摩擦式提升机摩擦衬垫[ s ] ．北 京机械工业出版社，2 0 0 2 ． [ 1 0 ] 张继礼，楚广成．G M - 3 新型高性能衬垫研制[ J ] ． 有色矿山。2 0 0 2 ，3 1 2 3 5 - 3 8 ． Z H A N GJ i - l i ，C H UG u a n g - c h e n g ．R e s e a r c ha n d d e v e l o p m e n to fG M - 3n e wt y p el i n i n gm a t e r i a l [ J ] ． N o n f e r r o u sM i n e s ，2 0 0 2 ，3 1 2 3 5 3 8 ． [ 1 1 ] 温诗铸．摩擦学原理[ M ] ．北京清华大学出版社， [ 1 2 ] [ 1 3 ] 2 0 0 2 ． D e e pM i n e dC o a lI n d u s t r yA d v i s o r yC o m m i t t e e ．G u i d a n c eo nt h es e l e c t i o n ，i n s t a l l a t i o n ，m a i n t e n a n c e a n du s eo fs t e e lw i r eh a u l a g er o p e sa tm i n e s [ M ] ． U K H e rM a j e s t y sS t a t i o n e r yO f f i c e ，2 0 0 4 ． 葛世荣，王军祥．G F 增强尼龙1 0 1 0 复合材料的摩 擦学性能研究[ J ] ．中国矿业大学学报，2 0 0 1 ，3 0 2 1 1 4 - 1 1 7 ． G ES h i - r o n g 。W A N GJ u n - x i a n g ．S t u d yo nt r i b o l o g i e a lb e h a v i o r so fg l a s sf i b e rr e i n f o r c e dn y l o n1 0 1 0 b a s e dc o m p o s i t e s [ J ] ．J o u r n a lo fC h i n aU n i v e r s i t yo f M i n i n g T e c h n o l o g y ，2 0 0 1 ，3 0 2 1 1 4 1 1 7 ． 责任编辑姚志昌 万方数据