（地图学与地理信息系统专业论文）多幅遥感图像自动裁剪镶嵌与色彩均衡研究.pdf

摘要 遥感图像镶嵌技术将两幅或多幅遥感图像拼接在一起合成为全景图像，以满 足宽幅图像的应用需求。 国内现有多款遥感图像处理软件，其中的图像镶嵌模块功能简单，缺乏友好 性。为提高遥感图像镶嵌模块的实用性，我们对已有的遥感图像镶嵌算法进行了 研究，并提出了改进的方法，在此基础上形成遥感图像镶嵌系统。本文介绍了图 像镶嵌基本的算法和成果，主要包括： l 、分析并设计了多幅遥感图像镶嵌图像自动裁剪和拼接算法，实现对矩形和非 矩形多边形图像间镶嵌自动进行裁剪和拼接。 2 、利用图像相交区域的补偿算法均衡镶嵌图像色彩差异，可有效用于多波段图 像镶嵌色彩均衡中。 3 、设计了遥感图像镶嵌系统模块结构和流程图。 其中部分算法和技术已经应用到新版遥感图像处理软件i r s a 中。 关键词：图像镶嵌自动裁剪拼接色彩均衡 系统设计 a b s t r a c t ( as t u d y a n d d e s i g n o nm o r er e m o t e s e n s i n gi m a g e sm o s a i c i n gs y s t e m ) w r i t t e n b yj i a n gh o n g c h e n g ，d i r e c t e db y z h a oz h o n g m i n g m o s a i c i n gt e c h n i q u ei n t e g r a t e st w oo rm o r ed i f f e r e n tr e m o t es e n s i n g i m a g e si n t oo n ew h o l ep a n o r a m i ci m a g ef o rt h ea p p l i c a t i o no fl a r g ei m a g e i nc h i n aw eh a v es e v e r a lr e m o t es e n s i n gi m a g ep r o c e s s i n gs o f t w a r e s n o w a d a y s ，i n w h i c ha l lh a v em o s a i c i n gm o d u l e ，b u tt h e y h a v ec o m m o n s h o r t a g e s ：s i m p l e f u n c t i o na n dl a c ko ff r i e n d l yi n t e r f a c e t oi m p r o v e p r a c t i c a b i l i t y o fm o s a i c s o f t w a r e s ，w e r e s e a r c he x i s t i n gm o s a i c i n g a l g o r i t h m sa n db r i n gf o r w a r dn e wa l g o r i t h m s ，a n db a s eo fw h i c ht h ep a p e r d e s i g n si m a g e sm o s a i c i n gs y s t e m m ym a i n r e s u l t sa r el i s t e db e l o w ： i a n a l y s i s e s a n d g i v e sa l g o r i t h m s f o ra u t o m a t i c l yc l i p p i n g a n d s p e l l i n gr e c t a n g l ea n dn o n r e c t a n g l es h a p et or e a l i z em o r ei m a g e s m o s a i c i n g 2 b a s e do ni m a g eo v e r l a pa r e a sw eu s ec o m p e n s a t i n ga l g o r i t h m b a l a n c e i m a g e c o l o rd i f f e r e n c e ，w h i c h c o u l du s e dt oe l i m i n a t e c o l o r d i f f e r e n c eo fm u l t i s p e c t r u mi m a g e sm o s a i c i n ge f f e c t i v e l y 3 w ed e s i g ni m a g e sm o s a i c i n gs y s t e mm o d u l ea n dm o s a i c i n g f l o wc h a r t p a no f t h e s e a l g o r i t h m s a n dt e c h n o l o g i e sr e f e r r e da b o v eh a v eb e e na p p l i e d t ot h e l a t e s tv e r s i o no f r e m o t es e n s i n gs o f t w a r ei r s a k e y w o r d s ：i m a g em o s a i c i n g a u t o m a t i c l yc l i p p i n g a n ds p e l l i n g c o l o rb a l 撇 s y s t e md e s i g n 第一章引言 第一章引言 1 1 镶嵌技术在遥感图像处理中的应用 1 9 8 6 年法国发射s p o t 系列高分辨率观测卫星，1 9 9 9 年美国s p a c e i m a g e 公 司发射i k o n o s 高分辨率商用卫星，近年中国和巴西联合研制的资源一号、二号 卫星发射成功，可为我国提供高分辨率卫星图像，越来越多的高分辨图像获得广 泛应用。但由于一幅卫星图像只能覆盖某一范围，需要将多幅图像无缝拼接成一 幅完整地图像，于是数字镶嵌技术发展起来了。7 0 年代中期，m i l g r a m 提出根据 某种误差准则( 如最小灰差和、最小代价途径原则) 来逐行( 列) 选择接缝位置开 创了数字镶嵌技术。到了8 0 年代，a l 佐席里斯特等提出了陆地卫星数字镶嵌 的基本概念，并进行了镶嵌实验。 遥感图像镶嵌是将两幅或多幅遥感图像( 这些图像可能是在不同的成像条 件下获取的) 拼接在一起构成一幅整体图像的过程，这个过程通常先对每幅图像 进行几何纠正，将他们划归到统一的坐标系中，然后对他们进行裁剪，去掉重叠 的部分，再将裁剪后的多幅图像镶嵌在一起，最后消除色彩差异，形成一幅宽幅 的图像。 本人在硕士阶段的三年时间中先后参与了国家8 6 3 计划资助的课题项目 “r s i m 5 2 遥感图像处理系统”和军方某工程项目遥感图像处理软件开发工作。 “r s i i 5 2 遥感图像处理”软件及其后升级版本“i r s a 6 0 遥感图像处理”软件 是国家遥感应用工程技术中心拥有的自主知识产权的多功能遥感图像处理软件。 分别与2 0 0 1 年9 月份和2 0 0 2 年9 月份参加国家科技部组织的国产优秀遥感软件 测评，两次都被评为国产优秀遥感软件。其中“图像镶嵌”模块在裁剪自动设置 接边线时候，来提供多幅图像同时自动裁剪拼接，对于多幅图像的色彩差异处理 不是很理想。正是基于改进此模块为出发点本人开始对图像镶嵌技术进行了研 究，此项研究和设计的成果将提供高效完整的镶嵌系统，提高镶嵌模块的通用性 与实用性。 多幅遥感凰像自动裁剪镶嵌与色彩均衡研究 1 2 遥感图像镶嵌技术现状 遥感图像镶嵌效果直接取决于原始图像精度，各类遥感图像都存在几何校 正的问题，图像的几何校正是指从具有几何畸变的图像中消除边形的过程。在图 像几何纠正研究领域各种文献阐述了多种纠正方式。本文不阐述几何纠正的详细 算法，但是几何纠正是原始图像利用的很重要一环，现在大多数数据提供商在提 供图像时一般都做了几何粗校正或精校正。进行校正的方法有重采样和内插和多 项式校正，前者又细分为三次卷积法、双线性内插法、线性内插法等。镶嵌原始 图像数据纠正还要统一到同一坐标空间系中。 镶嵌中重叠区域拼接存在的问题之一是多幅图像交叠区域确定裁剪线，现在 的技术主要考虑两两图像镶嵌，而且在镶嵌过程中，未考虑更大限度保留图像中 间部分，去除边缘部分，这方面文献并不多，另外用计算机确定多边形重叠区域 是其中一个主要难点。 对于多幅图像镶嵌来说。多幅图像拍摄曝光参数不一样的，使镶嵌的图像看 起来像补丁状，显示出明显的拼接线，这一问题主要是色调不均匀引起的。对于 图像色调平衡问题，有基于小波变换的拼接线消除算法，但是在实际应用中算法 过于复杂，处理时间较长，编程难以实现。本文采用直方图规定化和重叠区域色 彩补偿进行色彩平衡，取得较好效果。 1 3 研究思路 目前流行的国产遥感软件在交互性和功能上比较单一，国外软件中e r i ) a s 软 件的效率和功能是最强大的，软件的交互性和实时可视性也是最强的。因此本系 统将其作为目标，通过分析其优点，提出从如下方面提高i r s a 镶嵌模块： 提高镶嵌界面交互性和友好性。分析并设计了多幅遥感图像镶嵌i 虱像自动 裁剪和拼接算法，能够提供界面化的镶嵌图像的示意图模式，能自动对矩形和 非矩形多边形图像间镶嵌进行裁剪和拼接。 采用重叠区域色彩补偿算法均衡统一镶嵌图像色彩。利用图像相交区域的 补偿算法均衡镶嵌图像色彩差异，使最后图像显示更和谐。而且重叠区域色彩 补偿算法可应用于多波段遥感图像中，不受图像波段数限制。 第一章引言 设计遥感图像镶嵌系统模块结构框架。改进镶嵌流程图，可使镶嵌模块更 具有实用性。 1 4 全文组织结构 本论文一共分六章： 第一章为引言部分，主要介绍了镶嵌技术在遥感图像处理的应用，指出遥感 图像镶嵌技术的研究意义、研究内容、现状以及研究的基本思路。 第二章和第三章是本文的主要部分。第二章介绍了遥感图像镶嵌技术中多幅 图像裁剪和拼接算法。首先介绍了计算机图形学中多边形裁剪的拓扑算法， 在此基础上将其运用到镶嵌图像间的自动裁剪中，经过裁剪确定相交区域， 本章提出并阐述了相交区域拼接线确定算法。 第三章介绍了遥感图像镶嵌后各幅图像问的色彩均衡算法。首先介绍了图 像的色彩模型和图像处理色彩的经典算法：直方图匹配。其次，由于直方 图匹配的存在缺点，本文提出了相交区域色彩补偿算法作为补充，较好地 解决了图像色彩差异问题。 第四章介绍了实验结果和工程应用。实验了图像裁剪拼接算法和色彩均衡 算法的可行性。 第五章设计遥感镶嵌系统的结构，阐述了镶嵌系统的模块和流程图r 提出 了可行和实用的方案。 第六章对本文的算法的优点和缺点进行了总结，提出了有待改进的侧重点 并对以后的工作进行了展望。 第二章多幅图像裁剪与拼接 2 1 引言 第二章多幅图像裁剪与拼接 很多情况下图像镶嵌都是以两幅图像图为基础，没有考虑多幅图像同时进 行镶嵌。卫星图像或者航掐图像镶嵌前做纠正后，图像中有用部分可能并不是 矩形。如下图2 一卜1 和图2 - 1 - 1 ( s u p p o r t e db ye r d a ss o f t w a r e ) 所示：图像因 为几何纠正而旋转了，而且整幅像片四周是无效区域，有用区域是中间的矩形 部分。 图2 - 1 1 待镶嵌图像1 圈2 - 1 2待镶嵌图像2 原始图像之间都是有重叠区域，如下图2 一卜3 为图像1 和图像2 的镶嵌图，图像 2 叠加在图像1 之上。 图2 - 1 3 图像1 和图像2 镶嵌图 白色矩形框是两幅图像叠合区域，以矩形框对角线( 粗的斜白色线) 为拼接 多幅遥感图像自动裁剪镶嵌与色彩均衡研究 线，镶嵌时白色矩形中对角线右上方区域采用图像1 的像素，矩形对角线左下面 区域采用图像2 的像素。这种拼接方式在色彩平衡时，会将无效黑色区域( 白色 矩形左右侧) 也考虑在内，会影响平衡效果。本文改进后的镶嵌方式思路如下： 首先记录图像l 和2 的有效区域，图像1 和2 记录区域如图2 一卜4 和图2 一卜5 所示 图2 - 1 4 图像1 有效区域图2 - 1 5 图像2 有效区域 白色多边形记录了有效镶嵌区域，即只有多边形区域中的像素参与镶嵌合 成。同样记录图像2 的有效区域。那么镶嵌时候两幅图像有效区域相交如图2 - 1 6 所示， 图2 - 1 6 图像1 和2 相交区域 其中图像l 和图像2 镶嵌区域只限于有效区域，两个有效区域的重叠区域 为白色多边形裁剪拼接后，如果需要做色彩平衡，仅仅在图像1 和图像2 标出 的有效区域( 即白色多边形区域) 像素参与，这样可避免无效区域( 黑色部分) 的图 像，拼接线的确定也做了改进，改成了折线，最大限度利用原始图像中心区域。 镶嵌后图像1 和图像2 的外围多边形区域并的新多边形( 如图2 一卜7 ) 和将和下一 6 第二章多幅图像裁剪与拼接 张图像待镶嵌图进行镶嵌。 图2 - 1 7 图像1 和2 镶嵌合成后有效区域( 白色多边形) 上述过程为图像镶嵌过程。在这过程中，需要解决3 个难点：怎样记录有效 区域，怎样确定拼接线，本章将解决这两个问题。 2 2 确定镶嵌图像的有效区域 记录镶嵌图像的区域是作为交互式可视化镶嵌的基础，将所有待镶嵌图像 用几何图像示意图表示，同时记录原有地理坐标等地理信息。在交互式系统中， 如果直接读取原始图像将大幅增加计算机处理时问。降低效率，同时不能反映镶 嵌区域，用示意图的方式，可提高处理效率，清晰标志图像的叠放顺序，重叠区 域，计算显示相交区域等。如图2 - 1 1 是图像1 和图像2 的示意图( s u p p o r t e db y e r d a ss o f t w a r e ) ： 图2 - 2 一l 图像1 和图像2 示意图 7 多幅遥感圈像自动裁剪镶嵌与色彩均衡研究 从原始图像生成示意图可以称为原始图像的模板文档，模板不记录像素值， 而记录原始图像名称、坐标系类型、地理坐标值、有效区域多边形顶点地理坐标。 模板文档是可视化交互式镶嵌的基础。 2 2 1 多边形有效区域 多边形是记录原始图像有效区域的有效几何表现方法，对于一幅给定的图 像怎样确定有效区域，可通过绘制有效区域边缘闭合成多边形实现。多边形中的 四边形是常用图形，一般是经过几何纠正后，图像旋转了某个角度，需要这种记 录模板格式( 如上述图像1 和图像2 ) ，或者图像未旋转，但是边缘像素值不适合 参与镶嵌可用四边形将其标识在外。 2 2 2 矩形有效区域 对于直接应用原始图像的矩形区域是比较简单的镶嵌方式，不需要绘制有 效区域，可将原始图像区域作为整个有效区域，如图2 - 2 2 所示，图像1 和图 像2 有效区域等于原始图像的区域。 戮； 燃羹 2 尊嚣爱端：尊 舔搿擀蔓洋s ：畿矾 图2 2 2 图像l 和图像2 简单镶嵌示意图 2 3 镶嵌裁剪 2 3 1 多幅图像镶嵌 对于多幅图像镶嵌而言，多幅图像按照顺序镶嵌，已经镶嵌完成的和下一幅 第二章多幅图像裁剪与拼接 继续镶嵌。例如有9 幅图像，按照镶嵌顺序分别是卜 2 一 3 一 4 一 5 一 6 一 7 一 8 一 9 。 善冀￥簦蒜：；3 鞫 _ 6 9 图2 - 3 一l多幅图像镶嵌示意圈( s u p p o r t e db ye r d a ss o w a r e ) 如图2 - 3 1 所示9 幅待镶嵌图像的有效区域都是各自原始图像区域。图像1 和图像2 镶嵌的结果和图像3 镶嵌，镶嵌的结果即图像1 、2 、3 的镶嵌图和图像 4 进行镶嵌，依次类推，最后图像1 到8 镶嵌的结果与图像9 镶嵌。在这过程中 镶嵌需要考虑怎样确定拼接线，而确定拼接线首先要确定相交区域，即多边形裁 剪。图像1 和图像2 相交区域即确定图像1 区域被图像2 裁剪的部分，图像1 和图像2 镶嵌后相并的多边形被图像3 裁剪的部分。图像1 、2 、3 镶嵌后相并的 多边形被图像4 裁剪的区域，直至最后图像1 到8 镶嵌后相并的多边形被图像9 裁剪的区域。只有在确定了待相交的两个多边形相交区域，才能进行切割确定拼 接线，然后进行镶嵌合成。本章将重点阐述多边形的区域自动裁剪算法。 2 3 2 多边形裁剪 识别指定区域内或区域外的图形部分的过程称为裁剪算法，简称裁剪 ( c l i p p i n g ) 。在图形系统中，二维裁剪是最为基础、最为常用的操作之一。用来 裁剪对象的区域称为裁剪窗口。裁剪一般分为：点的裁剪，线段的裁剪，区域的 裁剪已经曲线和文字的裁剪。对裁剪算法的研究主要集中在裁剪直线和裁剪多边 形两方面在实用中，多边形裁剪与线剪裁相比具有更高的使用率。多边形裁剪用 多幅遥感圈像自动裁剪镶嵌与色彩均衡研究 于裁剪掉被裁剪多边形( 又称为实体多边形) 位于窗口( 又称为裁剪多边形) 之外 的部分多边形愈复杂，其裁剪算法就愈难以实现现有的解决方案或者局限于某 一类多边形，或者结构复杂、时间消耗大对于特殊情况已有几种有效的算 法：s u t h e r l a n d l t o d g e m a n 、梁一b a r s k y 等算法要求裁剪多边形是矩形的而在实际 中，只有对于一般多边形的裁剪才有普遍意义，而且更实用m o n t a n i 和r e p p a p o r t 以及s e c h r e s t 和g r e e n g b e r g 等人曾提出过对于一般多边形的裁剪算法，其中有些 算法允许多边形具有孔洞( 孤岛) 。而普遍认为，在这类算法中只有w e il e r 算法和 近年出现的v a t t i 算法及g r e i n e r h o r m a n n 算法可以在合理的时间内处理一般的 情况其中，w e i l e r 算法使用的是树形数据结构，而v a t t i 算法和g r e i n e r h o r m a f l f l 算法使用的是双线性链表数据结构，所以后两者在复杂性及运行速度方面都优于 前者。 本文的多边形裁剪算法中裁剪多边形为不规则多边形( 未考虑孔洞) ，而裁 剪实体一般为矩形或凸四边形。对于一个多边形裁剪另一个多边形的过程。就是 求两个多边形的相交区域( 我们称其为结果多边形或输出多边形) 。结果多边形是 由实体多边形位于裁剪多边形内的边界和裁剪多边形位于实体多边形内的边界 组成的。 2 3 3 多边形裁剪算法 o s u t h e r l a n d - h o d g e u a n 算法 s u t h e r l a n d - h o d g e m a n 多边形裁剪算法裁剪窗l z l 为矩形，将多边形边界作为 一个整体，并根据窗口的每一条边进行裁剪，可以得到裁剪区域。通过依次按照 裁剪矩形的各边界来处理所有多边形的顶点，可以实现这种操作。如图2 3 2 ， 在对多边形的顶点集进行初始化后，首先用矩形左边界裁剪多边形，从而产生新 的顶点序列。这些新的顶点集可以依次传给右边界，下边界和上边界进行处理。 在每一步产生的新的输出顶点序列，将传递到下一个窗口边界的裁剪程序。 第二章多幅图像裁剪与拼接 原始多边形 裁剪左边裁剪右边裁剪底边裁剪顶边 图2 3 2用窗口边界依次裁剪多边形 沿着多边形依次处理顶点会遇到四种情况。在将相邻的一队多边形顶点传到 窗口的边界裁剪程序时，可以进行下了测试：( 1 ) 如果第一点在窗口边界外而第 二点在窗口边界内，则将多边形的这条边与窗口边界的交点和第二。( 2 ) 如果两 顶点都在窗口边界内，则只有第二点加到输出顶点表中。( 3 ) 如果第一点在窗口 边界内而第二点在窗口外，则只有与窗口边界的交点加到输出顶点表中。( 4 ) 如 果两个点都在窗口边界外，那么输出顶点表中不增加任何顶点。图2 3 3 所示给 出了多边形相邻两顶点的这四种情况。在窗口的一条裁剪边界上处理完所有的顶 点后，其输出顶点表将按照窗口的下一条边界继续裁剪。 v 外， 内 保存v 1 v 2 内- 内 保存v 2 内 外 保存v l 外 外 不保存 图2 3 3 按照窗口左边界连续处理多边形顶点对 按照窗口左边界说明处理如图2 3 4 所示区域。顶点l 、2 在边界的外面，而 多幅遥感图像自动裁剪镶嵌与色彩均衡研究 点2 到点3 的直线上，点3 在窗口内，因此计算出交点并且保存交点和点3 。点4 、5 则确定在窗口内，所以都要保存。第6 点和最后一点位于窗口的外部，所以要计 算点5 、6 的直线与左边界的交点并将其保存。这五个保存的点按照窗口的下边 界重复进行处理。 窗口 2 图2 - 3 - 4从顶点1 开始，使窗口的左边界裁剪多边形， 带撇号的数字用于标识输出顶点表中的点 要实现上述的算法，就要为窗口各边界裁剪的多边形存储顶点的输出表。 s u t h e r l a n d - h o d g e m a n 多边形裁剪算法要求裁剪窗口是矩形，裁剪凸多边形可以 获得正确的裁剪结果，对于凹多边形的裁剪将会出现两个被裁剪处理的区域有一 条多余的直线相连。因为只有一个输出顶点表，所以表中最后一个顶点总是连着 第一个顶点。修改s u t h e r l a n d h o d g e m a n 算法，使用更一般的多边形裁剪算法。 g r e i n e r - h o r m a n n 算法 为了便于对非规则多边形裁剪算法的理解，首先介绍有关多边形裁剪的一些 基本概念及术语。 ( 1 ) 多边形的边的方向与内外区域的关系。 如果多边形的边的方向是顺时针的( 即多边形的顶点是以顺时针的顺序输入 的) 。则在沿着多边形的边走时，右侧区域为多边形的内部。相反，如果多边形的 边的方向是逆时针的则在沿着多边形的边走时，左侧区域为多边形的内部对于 具有孔洞的多边形。只要把内孔边界和外边界以相反的方向表示，由上面的规则 判断多边形的内部仍然适用。 璺l 塑墼塑 c l ( 2 ) 进点和出点的定义 ，兰竺耋边形卿啪一个交点如果船着啪边界的方向在脯从粥外部进入 曼? 篓棚。尊功对于啪个进点反之，如果赃晡从啪内部出到啪夕：i i i 称助对于街一个出点。 ” 例如，对于如图2 3 5 所示的多边形卿趿其交点若钧方向为逆时针方向 5 1 韶一韶一岛两，则，5 ，】，3 是对于啪进点，4l 厶是对于瑚出点。如果s 的方向为顺时针方向贷一秘一品一& 一| 5 l ，则对于球说，：，。，。是迸点， ( 3 ) 进点和出点的判定 假设多边形s 的一条边蛳l 与另一多边形洧交点当点。钳是罐9 外点时，则 沿着鳓走向，边瓣1 与啪第一个交点秘是啪进点：而当5 德( 白g 内点时： 是缃出点由于沿着5 的边界对于礅进点和出点是交替出现的( 硪多边形的边重 合或者两多边形在顶点处相交的情况除外。这类特殊情况的处理将在后面进行讨 论) ，所以，只需判断第1 个交点是进点还是出点，其他交点的进出性则可依次确 如果两个相交多边形的边的取向相同( 均为顺时针或逆时针方向) ，则对一个 多幅遥感图像自动裁剪镶嵌与色彩均衡研究 ( a ) s e 和c e 的夹角在o 。1 8 0 。之间( b ) s e 和c e 的夹角在1 8 0 。、3 6 0 。之间 图2 - 3 6 当两个多边形的相交边s e 和c e 的取向均为顺时针 方向时，对一个多边形是进点的交点对另一个多边形必是出 点( 阴影表示多边形内侧) 如图2 3 6 中，设鲐边的方向是从左向右固定不变的，如果国的正向与曲的正 向的夹角在0 0 1 8 0 。之间从下向上穿过船( 图( a ) 的情况) ) ，则由图显然可见， 经过交点从多边形呐走向矽 。即该交点是对于多边形s 的出点；而另一方面，船 则是经过该交点从多边形纱 走向纳，即该交点是对于多边形瑚进点。如果 的正向与5 蝴正向的夹角在1 8 0 ”3 6 0 。之间( 即凸从上向下穿过s e ( 图( b ) 所示) ， 则由图显然可见，该交点对于多边形踞进点。而对于多边形c n 是出点。 对于两个相交多边形的边的取向均为逆时针方向的情况相同。因此对其中一 个多边形求出一个进点或出点以后，在两个多边形方向相同的情况下，其对另一 个多边形的进出性也就确定了。这样如果两个多边形的方向相同则在求出交点 时只需判断和标记它对其中一个多边形是进点还是出点。它对另一个多边形的进 出性则相反。 g r e i n e r h o r m a n n 算法中每个多边形由一个双向链表来表示。每找到一个交点 就将其分别插入到实体多边形和裁剪多边形的两个双向链表中。 g r e i n e r h o r m a n n 算法建立两个交点类型的结点，然后将每一个插入到一个多边 形的链表中。而插入到两个链表中的这两个交点类型的结点之间也要用指针域 n e i g h b o r 彼此相连：如图2 3 7 所示： 1 4 第二章 多幅图像裁剪与拼接 裁剪多边形c 裁剪实体s 图2 - 3 - 7g r e i n e r h o r m a n n 算法数据结构 2 3 4 镶嵌多边形裁剪交和并算法 交互式镶嵌过程中对于镶嵌示意图裁剪，每次两幅图像镶嵌即求这两幅图 像示意图的并。求得并后的大图像和下一幅原始图像镶嵌，计算出相交区域，确 定拼接线后，大图像和被镶嵌的图像并，得到一幅更大的图像，如此反复，因此 多边形的裁剪过程既需要求交，还需要求并。改进后的多边形裁剪的有效算法可 以方便的实现两个多边形的交和并区域。其中的裁剪多边形和被裁剪多边形都可 以是一般多边形。既可以是凹多边形，也可以是有内孔的多边形。该算法只使用单 线性链表数据结构，所以具有数据结构简单、占用空间少的特点，而且无须事先规 定以什么方向输入图形的顶点。算法最终通过简单的遍历线性链表。可以得到每 一个输出多边形。 1 、算法的数据结构 多边形裁剪算法需要一个适当的数据结构来存储多边形及交点并能够在其 上进行正确的操作本文豹算法采用单链表来表示所有的多边形( 输入和输出) ， 与g r e i n e r h o r m a n n 算法的双向链表结构相比，不仅由于少用了一个指针域而节 省了存储空间而且还进一步降低了数据结构的复杂性我们知道，在插入一个交 多蝠遥感图像自动裁剪镶嵌与色彩均衡研究 点时，双向链表所需修改的指针数是单链表的2 倍，因此，对单链表的操作不仅简 单。而且也省时。 算法的每个多边形由一个单链表来表示单链表的每一个结点按序( 多边形顶 点输入的顺序) 存储着多边形的一个顶点最后一个结点的指针指向第1 个结点 ( 循环单链表) 每个链表由一个头指针指向其第1 个结点，实体多边形链表的第1 个结点由头指针h e a d s 指示：裁剪多边形链表的第一个结点由头指针h e a d c 指示 结点的结构定义如下( 其中c o o r d i n a t e s 表示坐标类型，用于存储顶点或交点的坐 标值：p o i n t e r 表示指针类型) ： v e r t e x = x ，y ：c o o r d i n a t e s ： i n t e r s ，u s e d ：b o o l e a n ： n e x t ：p o i n t e r ： ) 交点的数据结构如下： i n t e r s e c t i o n = x ，y ：c o o r d i n a t e s ； i n t e r s ，u s e d ：b o o l e a n ； n e x t l ，n e x t 2 ：p o i n t e r ： 其中的指针域用于将交点分别插入到两个多边形的单链表中，第l 指针域n e x t l 用 于插入实体多边形链表：第2 个指针域n e x t 2 用于插入裁剪多边形链表。这样的数 据结构定义使算法在求出一个交点时只需建立1 个i n t e r s e c t i o n ( 交点) 类型的结 点，并分别插入到两个多边形的单链表中，而不像g r e i n e r _ h o 瑚a n n 算法那样，要 建立两个交点类型的结点，然后将每一个插入到一个多边形的链表中，而插入到 两个链表中的这两个交点类型的结点之间也要用指针域n e i g h b o r 彼此相连。 应该注意的是，实体多边形链表中的交点的进出性是对裁剪多边形而言的，雨 裁剪多边形链表中的交点的进出性则是对实体多边形而言的 在这两个数据结构的定义中，布尔类型域i n t e r s 用于区分该结点是否 i n t e r s e c t i o n ( 交点) 类型的结点：u s e d 域用于有多个输出多边形时所有交点的 u s e d 域的初值都为o ，当一个交点被输出时，其u s e d 域被置为1 裁剪结果可能得到多个分立的输出多边形，因此需要设立一个指针链表0 u t ， 1 6 第二章 多幅固像裁剪与拼接 其每个结点有一个指针域p o l y g o n 指向一个输出多边形链表的第一个结点该指 针链表的结点结构如下： o u t = p o l y g o n ：p o i n t e r ： n e x t ：p o i n t e r ： ， 下图2 3 8 给出了改进算法所使用的数据结构。可见，新算法的数据结构要比 g r e i n e r h o r m a n n 算法简单得多。 2 - 3 8 改进算法后的数据结构 2 、算法 算法分为3 个阶段。第1 个阶段，判断及计算第1 个交点，并由其进出性判断两个 多边形是否同向。如果不同向，则将裁剪多边形链表反向，然后将该交点插入到两 个多边形的链表中第2 阶段，依次以实体多边形的每一个边对裁剪多边形进行直 线裁剪操作，判断及计算其余交点，并以正确的顺序插入到两个多边形的链表中 第3 阶段，遍历整个链表，输出最终结果。 判断多边形的方向是否相同 对于两个镶嵌示意圈多边形，多边形的顶点是用单链表表示的，如上节中图 2 - 3 - 5 的初始顶点存储链表如下图2 3 9 ： 1 7 多幅遥感图像目动裁剪镶嵌与色彩均衡研究 图2 - 3 9裁剪多边形和裁剪实体的顶点存储链表 根据 9 判断两个多边形是否同向，是通过判断一个交点( 如第1 个交点) 对于 两个多边形的进出性来完成的。如果该点对于实体多边形的进出性与对于裁剪多 边形的进出性不同，则可知两个多边形取向相同：否则，两个多边形的取向相反。 如果不同向，则将裁剪多边形链表反向，可使两个多边形的方向相同。 当一个多边形的一个边对另一个多边形进行直线裁剪操作之后，如果有交点， 即可根据交点在这个边上的排序的奇偶性来确定交点对另一个多边形的进出性 这样在计算交点的同时也确定了该交点的进出性。 例如，从图中很容易看出裁剪多边形和裁剪实体的走向相同，都为顺时针方 向。计算机实现时，首先计算出实体多边形s 的边和裁剪多边形c 的第一个交点1 6 ， 1 6 所在的边s i s 5 和c 共有两个交点1 6 和1 3 。链表的存储顺序表示了多边形取向， 交点中1 6 在s i s 5 上顺序是奇数( 第1 个) ，表示进点。那么1 6 同时也是c 上的边c i c 2 上的点，计算出c i c 2 和s 所有的交点1 6 、1 5 。交点中1 6 在c i c 2 j ：顺序是偶数( 第2 个) ，表示出点。由此可判断c 和s 两个多边形的方向相同。 第1 阶段 下面是算法的第l 阶段的形式描述，其中指针变量p s $ 1 i p c 分别指向实体多边形 链表和裁剪多边形链表中正在被处理的当前结点。另外，我们把由结点p sf 和其 下一个结点p sf n e x tf 定义的边简称为由p s 指向的边。 p s = h e a d s ： r e p e a t 以p s 指向的边与裁剪多边形进行直线裁剪操作( 即求交点的操作) ： i f ( 上述直线裁剪操作有交点) t h e n 第二章 多幅图像裁剪与拼接 将每个交点( 可能有多个) 按其在该边上的顺序插入到实体多边形链表和裁 剪多边形链表的对应相交边的两个结点之间： 由s i n 标记插入到实体多边形链表中的第1 个交点对于裁剪多边形的进出 性，s i r f l 表示进； 令p f 指向第1 个交点结点，以备算法的第3 阶段使用： 将p c 指向该交点在裁剪多边形上的对应边： 以p c 指向的边与实体多边形进行直线裁剪操作： 求出上述第1 个交点对于实体多边形的进出性- i f 上述第1 个交点对于实体多边形和裁剪多边形的进出性相同t h e n 逆转裁 剪多边形的链表： 令p s 指向实体多边形的下一个边； 转到算法的第2 阶段： ) 令p s 指向实体多边形的下一个边： u n t i lp s = h e a d s ： 两个多边形无交点，算法结束： 第2 阶段 在第2 阶段，算法从第1 阶段求出交点的那个实体多边形边的下一个边开始，用 每一个实体多边形边与裁剪多边形求交点，并如图2 所示，给每个交点建立一个包 含该交点坐标的新的交点结点，然后将其插入到实体多边形链表和裁剪多边形链 表的对应相交边的两个结点之间。例如，个交点是由结点p sf 和其下一个结点 p st n e x tt 所定义的实体多边形的边与由结点p ef 和其下一个结点p cf n e x t f 所定义的裁剪多边形的边相交形成的，那么该交点结点就应该被插入到实体多 边形链表的结点p st 和其下一个结点p s n e x tt 之间，同时被插入到裁剪多边 形链表的结点p cf 和其下一个结点p cf n e x tf 之间。当一个边上有多个交点时， 则以该边的方向为序将这些交点插入其中。例如，如果该边的方向是从左向右的 斜线，则可按交点的矬标的大小顺序插入这些交点。 在这个阶段，算法不需要标记交点的进出性，因为如前所述，算法只需在第1 阶 段用变量盯磔标记实体多边形链表中的第1 个交点对于裁剪多边形的进出性其 多幅遥感图像自动裁剪镶嵌与色彩均衡研究 余交点对于两个多边形的迸出性便由如前所述的规律可知下面是算法的第2 部 分的形式描述。 r e p e a t 以p s 指向的边与裁剪多边形进行直线裁剪操作： i f ( 上述直线裁剪操作有交点) t h e n 将每个交点按其在该边上的顺序插入 到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间： 令p s 指向实体多边形的下一个边： u n t i lp s - h e a d s ： 转到算法的第3 阶段： 第3 阶段 在算法的第3 阶段，通过遍历己插入交点结点的实体多边形和裁剪多边形链表 来跟踪结果多边形的边界，最后产生输出多边形链表。 跟踪一个结果多边形的边界是以实体多边形链表中的一个进点( 对于裁剪多 边形) 开始的。从该进点到实体多边形链表中的下一个交点( 记为n 1 ) 之间的实体 多边形的边界全部是结果多边形的边界。n 1 既是对于裁剪多边形的出点也是对于 实体多边形的进点，因此从n 1 点开始到裁剪多边形链表中的下一个交点之间的裁 剪多边形的边界全部是结果多边形的边界( 如图所示) 。输出这些边界重复此过 程，一直到回到实体多边形链表中的开始进点为止，便跟踪输出了一个结果多边 形。在上述过程中，实体多边形链表中的进点( 对于裁剪多边形) 的u s e d 域被标记 为l ，以表明从它开始的边界已经被输出过。“u s e d 域”用于有多个结果多边形的 情况。 算法第3 阶段的遍历是以实体多边形链表的顺序进行的。从实体多边形链表中 的第1 个进点开始，如果该进点( 当前进点) 的u s e d 域为o ( 表明它未被输出过) ，则 将其置为1 ，并执行上一段所述的跟踪过程输出一个结果多边形：如果该进点的 u s e d 域为l ，则走到实体多边形链表的下一个进点，即该进点的下一个交点的下一 个交点( 如前所述，在多边形链表中交点的进出性是相隔分布的。以下一个进点为 当前进点，重复此过程，一直到回到实体多边形链表中的第1 个进点为止。所有的 进点都被访问过，所有的结果多边形也都被输出。至此，算法结束。下面是算法第 3 阶段的形式描述 第二章 多幅图像裁剪与拼接 i fs r f - ot h e n 令p f 指向实体多边形链表中的下一个交点结点，以确保p f 指 向第1 个迸点： p p = p f ： r e p e a t i fp p 所指的交点结点的u s e d 域为0t h e n p o = p p ： 建立一个新的输出多边形链表，并将指向该链表的头指针加入到指针链表 o u t 的最后( 在p o l y g o n 域当中) ： r e p e a t 将p 0 所指的交点结点( 一定是进点) 的u s e d 域置为l ： 将从p o 所指的交点结点开始( 用n e x t l 指针域) 到下一个交点结点( 记为n i ) 之前的实体多边形链表中的结点加入到输出多边形链表的最后，并使p o 指 向n 1 ： 将从p 0 所指的交点结点开始( 用n e x t 2 指针域) 到下一个交点结点( 记为n 2 ) 之前的裁剪多边形链表中的结点加入到输出多边形链表的最后，并使p o 指 向n 2 ： u n t i lp o = - p p ) e l s e 使p p 指向实体多边形链表中的下一个进点结点( 即下一个交点结点的 下一个交点结点) ： u n t i lp p = p f ： 算法结束，输出多边形链表由指针链表o u t 的p o l y g o n 域指出。 求多边形的并需要修改第3 阶段遍历算法，第1 和第2 部分相同。在输出多边形 从出点到入点的边( 而不是上述的从入点到出点) 即可得到多边形的“并”区域a 下面是求多边形并的算法形式描述 i f 融萨lt h e n 令p f 指向实体多边形链表中的下一个交点结点，以确保p f 指 向第1 个出点： p p = p f ： 多幅遥感图像自动裁剪镶嵌与色彩均衡研究 r e p e a t i fp p 所指的交点结点的u s e d 域为0t h e n 【p o ：p p ： 建立一个新的输出多边形链表，并将指向该链表的头指针加入到指针链表 o u t 的最后( 在p o l y g o n 域当中) ： r e p e a t 将p o 所指的交点结点( 定是出点) 的u s e d 域置为1 ； 将从p o 所指的交点结点开始( 用n e x t l 指针域) 到下一个交点结点( 记为n 1 ) 之前的实体多边形链表中的结点加入到输出多边形链表的最后，并使p o 指 向n 1 ： 将从p o 所指的交点结点开始( 用n e x t 2 指针域) 到下一个交点结点( 记为n 2 ) 之前的裁剪多边形链表中的结点加入到输出多边形链表的最后，并使p o 指 向n 2 ： u n t i lp o = p p ) e l s e 使p p 指向实体多边形链表中的下一个进点结点( 即下一个交点结点的 下一个交点结点) ； u n t i lp p = p f ： 算法结束，输出多边形链表由指针链表o u t 的p o l y g o n 域指出。 对于有内孔的多边形，只要把内孔边界和外边界以相反的方向表示，则上述的 多边形的边的方向与内外区域的关系仍然适用。这种情况在镶嵌中是特殊情况， 郢一幅镶嵌图像包含另外一幅图像，几乎不会出现。此时。只判断实体多边形和 裁剪多边形的外边界方向即可：若方向相同，则不必调整：若方向相反，则把裁剪 多边形的链表反向然后，分别求出实体多边形的内、外边界与裁剪多边形的内、 外边界的交点，劳把交点插入到相应的数据结构中。最后遍历所有交点求出输出 结果多边形。 两多边形的边重合或者两多边形在顶点处相交的特殊情况的处理： 到此为止我们假设两多边形的边不重合并且两多边形不在顶点处相交。两多 第i 一章多幅图像裁剪与拼接 边形的边重合或者两多边形在顶点处相交的特殊情况虽然出现的可能性很小，但 必须妥善处理。当前，处理这类特殊情况主要有两种方法第1 种方法是文献 1 4 等描述的精确的处理方法，这种方法将上述的特殊情况分解成各种子情况分别进 行处理，通过在链表上增加或减少交点来保持进点和出点是交替出现的：第2 种方 法是由文献 1 5 提出来的：当遇到上述的特殊情况时，则对重台边的一个顶点或 与交点相同的顶点进行很小的移动来避免特殊情况。 上述第1 种方法虽然很精确，但其处理过程比较复杂，且计算量较大第2 种方 法的过程简单，且计算量较小，但是不如第1 种方法精确。然而，由于裁剪算法使用 的是浮点数操作，而显示器上的像素却只有整数坐标，所以在显示器上显示的图 形实际上就已经具有了一定的误差该误差一般是小于或等于o 5 这样，第2 种方 法对顶点进行很小的移动，比如移动的距离是一台计算机所能表示的最小的浮点 数( 对于单精度浮点类型可取1 0 。7 ) ，则不会对算法的结果产生影响因此，我们 的新算法使用第2 种方法，只是对其进行了两点改进 第1 点改进是只对出现特殊情况的当前边临时改变顶点( 对其他边则仍是原顶 点) ，而不像原方法那样永久性地改变该顶点。永久性地改变顶点的方法将可能产 生较大的累计误差，因为如果处理后面的边时对于永久性改变了的该顶点又出现 了特殊情况，则该顶点就在以前改变的基础上再一次改变，因而可能产生较大的 误差而改进之后该顶点的每一次改变都是在原始顶点的基础上的改变，因雨不 会产生大的累计误差。第2 点改进针对顶点的移动方向。文献 1 5 中没有具体说 明如何选择移动顶点的方向。其实如何没有确定的规贝j j 而是随意地移动顶点，则 移动后的顶点可能仍然没有离开与其重合的边我们的方法是，如果重合顶点属 于裁剪多边形，则只将该顶点的挫标加( 或减) 一个i j 、量使该顶点上下移动，因为 实体多边形的当前边已经错切变换成了水平线，所以不会仍然重合：如果重合顶 点属于实体多边形，则只将该顶点的挫标加( 或减) 一个小量使该顶点左右移动 便可避开裁剪多边形的边。 2