-
无论是遥感影像还是无人机影像，都存在一定程度的重叠。在最终的镶嵌结果中，重叠区的每一个像素只能用一幅影像表示，因此需要在重叠区内定义一条接缝线，以决定该像素属于哪幅影像[1]。目前，在规模影像镶嵌研究中，比较普遍的研究思路是：首先生成全局的初始接缝线网络，然后基于网络结点进行局部优化[1-7]。初始接缝线网络是接缝线局部寻优的前提和基础，网络的复杂程度对接缝线优化有直接影响。
目前，主流的初始接缝线网络生成方法是基于几何的方法，相比基于像素的方法[8]，它的优点是生成效率高、易于实现。在基于几何的方法中，Hsu等[9]采用常规Voronoi图的方法来生成初始接缝线，但其不能保证生成的接缝线一定在相邻正射影像重叠区内，可能导致镶嵌结果存在空洞。针对文献[9]方法的不足，潘俊等[1]提出了一种顾及重叠的面Voronoi图(area Voronoi diagram with overlap, AVDO)方法，AVDO方法对Voronoi图思想进行了扩展，用面集代替点集来进行空间划分，提出了一种理想的接缝线生成思路。但文献[1]假设正射影像的有效范围都可以用四边形表示或者近似表示，其重叠部分仍然是四边形，因此只考虑了凸四边形重叠区接缝线生成方法的具体实现，而对非四边形重叠区没有给出解决方案。Yang等[10]试图弥补这一不足，提出一种复杂多边形重叠区接缝线解决方法，但其方法仍没有摆脱正射影像有效区域为四边形的假设。Pan等[3]在2013年给出任意凸多边形的解决方案，但未涉及凹多边形重叠区的情形。Mills等[11]也移除了四边形重叠区这一假设，通过优化顶点的位置来优化接缝线网络，但其采用传统Voronoi图划分方法构造的初始接缝线网络不一定能完全位于重叠区内。Wan等[12]在构造初始接缝线网络时，先对重叠区进行了限定的Delaunay三角剖分，然后提取骨架作为接缝线，该方法适用于任意的简单多边形重叠区，但构造算法较为复杂。Song等[6]也采用Voronoi图来构造初始接缝线网络，并给出一种用初始镶嵌多边形进行迭代裁切的策略，很好地解决了空洞问题。本文提出了一种基于影像重叠程度(overlap degree of image，ODI)的初始接缝线网络自动生成方法，能很好地适应包括凹多边形在内的复杂多边形重叠区的接缝线的自动生成。它同样利用了影像的几何信息，但强调的是对重叠区域的重叠程度信息的利用，而不是简单地对邻接拓扑信息的利用，比特运算用于接缝线和有效多边形的自动生成，算法简单、高效。
HTML
-
如图 1所示，正射影像Ⅰ、Ⅱ、Ⅲ相互重叠，它们的有效区域边界将平面空间划分成不同的部分。为了论述方便，对本文所涉及的关键术语进行事先定义。
Figure 1. Overlapping Images
边界连接点(border connection point, BCP)：点W是边界连接点，当且仅当点W是影像轮廓边界的交点并且位于最终完整镶嵌影像的外边界。如点R、M、Q为边界连接点，而点O、N、P则不是(尽管它们也是影像轮廓边界的交点)。
关联标志(association flag, AF)：平面中几何要素(点、线或简单封闭区域)的一种属性，表示该几何要素与全体影像之间的平面关联关系。关联标志用比特数组描述，数组长度为影像的数量，比特位的值表示该几何要素是否与对应影像有关。例如，点A为影像Ⅰ的轮廓角点，它与影像Ⅱ、Ⅲ均无关系，则其关联标志为100；而边界连接点R的关联标志为101，表示该点与影像Ⅰ、Ⅲ有关(实际是影像Ⅰ和Ⅲ的轮廓边界交点)；同理，多边形区域PJQH的关联标志为011，表示该区域与影像Ⅱ和Ⅲ平面相关(实际是影像Ⅱ和Ⅲ的平面重叠区域)。
关联掩码(association mask, AM)：初始影像有效范围的一种属性，与关联标志相似，关联掩码也用比特数组描述，数组长度为影像的数量，不同的是关联标志只有一个比特位为1，它的位置正好是该影像在初始影像序列中的位置。如影像Ⅰ的关联标志为100，影像Ⅲ的关联标志为001。
重叠程度(overlap degree, OD)：平面封闭区域的一种属性，表示该区域的重叠影像的数量。例如，区域PJON的重叠程度为3，表示该区域为3幅影像的重叠区域；而多边形区域ABMEPR的重叠程度为1。相应地，重叠程度为n的区域被称为n度重叠区。显然，区域重叠程度等于该区域关联标志中比特位值为1的数量，该数学关系记为：OD=count(AF)，函数count()用于统计关联标志中比特位为真值的数量。
-
接缝线与重叠区是两种不同类型的几何要素，它们的空间关系总是符合两个原则：①如果两幅影像重叠，则接缝线必存在于重叠区内; ②如果两个重叠区再次发生重叠，则接缝线必经过再重叠区。
如果使用术语重叠程度，上述原则可被统一描述成：对于任意的n>0，两个重叠程度为n重叠区再次重叠形成重叠程度为n+1的重叠区，若接缝线网络是连通的，则接缝线必经过该n+1度重叠区。
根据以上原则，本文设计了一个非常简洁的接缝线自动生成算法。
算法1 接缝线自动生成
1) 提取影像有效区域的轮廓边界(假定影像有效区域的轮廓边界为多边形)，对所有轮廓边界进行空间关联并运算，确定最终完整镶嵌影像的外边界∂，该边界可以用平面区域上的简单多边形(由单个不自交的、封闭的多边形链所围出的区域)描述。
2) 对于镶嵌边界多边形上的任意一点p，计算该点的关联标志AFp。若count(AFp)≥2，则该点标记为边界连接点。
3) 对影像轮廓边界两两进行空间求交运算，计算影像重叠区域和相应的关联标志。
4) 对重叠程度大于1的任意两个重叠区域i和j，i≠j，令AFTemp=AFi & AFj，运算符 & 表示比特“按位与”操作，若AFTemp= AFi，则重叠区域i标记为无效重叠区域；若AFTemp=AFj，则重叠区域j标记为无效重叠区域。
5) 消除所有无效重叠区域，剩余重叠区域标记为有效重叠区域。
6) 若有效重叠区数量大于1，则对有效重叠区域进行连接。对重叠程度大于1的任意两个有效重叠区域i和j，i≠j，若count(AFi & AFj)> 1，则重叠区域i和j之间存在一条接缝线。
7) 有效重叠区域与边界连接点连接。对于任意的有效重叠区域i和任意的边界连接点p，若count(AFi & AFp)=2，则重叠区域i和边界连接点p存在一条接缝线。
按照上述算法步骤，图 1中的最终接缝线生成结果如图 2所示。图中黑色粗实线为接缝线，实心圆点为有效重叠区的连接锚点，空心圆点为边界连接点，阴影区为有效重叠区。此例中有效重叠区只有一个，因此只需要将其与边界连接点相连即完成接缝线的生成。无论是有效重叠区之间的连接，还是它与边界连接点连接，有效重叠区都要抽象为一种具体的连接形式(步骤6)和步骤7))。图 2中有效重叠区为凸四边形，本文直接采用其质心作为连接锚点，对于包括凹多边形在内的更复杂的重叠区情形，本文将在§3详细介绍其具体的连接形式。
Figure 2. Seamlines of Fig. 1 Generated by ODI-Based Method
-
目前为止，所有初始接缝线已经生成，但它们之间相互独立并不关联，需要进一步建立它们之间的空间连接关系，即生成有效镶嵌多边形，具体生成算法描述如下。
算法2 有效镶嵌多边形自动生成
1) 收集镶嵌多边形有效边。构造边总集Eall，集合元素包括根据算法1生成的所有接缝线和最终镶嵌结果边界多边形∂上的所有边。
2) 计算边的关联标志。对边总集中的每一边e，假设p1和p2为该边的两个端点，则该边的关联标志AFe=AFp1 & AFp2。
3) 为每一幅正射影像构造镶嵌多边形边子集。对于每一幅正射影像i，初始化其边子集Ei为空集。对于边总集中的每一个边e，若AFi & AFe=AMi，则将边e加入边子集Ei。
4) 构造有效镶嵌多边形。对于每一边子集Ei，简单的端对端连接即可完成有效镶嵌多边形EMPi的构造。
算法2以一种简洁的形式完成了有效镶嵌多边形的构造，针对图 1中的例子及对应的图 2中的接缝线生成结果，表 1给出一个对有效镶嵌多边形构造过程更直观的理解。有效镶嵌多边形非常重要，它决定每一幅正射影像对最终镶嵌结果的贡献程度。所有的有效镶嵌多边形构成了对镶嵌全域的一个有效划分。
影像 边集与相应的关系标志 关联掩码与边子集 有效镶嵌多边形 Ⅰ AB(100), BM(100),
MF(010), FG(010),
GQ(010), QK(001),
KL(001), LI(001),
IR(001), RA(100),
SR(101), SM(110),
SQ(011)100(AB, BM, RA, SR, SM) AB, BM, MS, SR, RA Ⅱ 010(MF, FG, GQ, SM, SQ) MF, FG, GQ, QS, SM Ⅲ 001(QK, KL, LI, IR, SR, SQ) QK, KL, LI, IR, RS, SQ Table 1. Process of Generating Effective Mosaic Polygons
1.1. 术语与定义
1.2. 接缝线生成
1.3. 镶嵌多边形生成
-
在接缝线生成算法中，有效重叠区需要抽象为一种具体的连接形式，这与重叠区的形态直接相关。本文对重叠区的形态没有严格限制，可以为任意的简单多边形，即由单个不自交的、封闭的多边形链所围出的区域，如图 3所示。
Figure 3. Four Cases of Non-quadrilateral Intersection
对有效多边形重叠区采用的抽象形式分为两种情形：
若有效重叠区域为凸多边形，可直接将其抽象为一个点作为连接锚点，本文采用凸多边形的质心作为该重叠区的连接锚点。如图 3(a)~3(c)的凸多边形重叠情形，以质心作为连接锚点，并与各边界连接点连接即可形成新的接缝线，如图 4(a)~4(c)所示。
Figure 4. Seamlines of Fig. 3 Based on ODI Method
若有效重叠区域为凹多边形，情况要复杂一些，单纯地采用质心作为锚点可能产生空洞。对于凹多边形重叠区，本文将其抽象为一根连接轴，连接轴的端点可作为连接锚点参与连接。首先，将凹多边形重叠区离散化，将其划分为若干三角形。根据计算几何知识可知，任何简单多边形都至少存在一个三角划分；若其顶点数目为n，则它的每个三角划分都恰好包含n-2个三角形。对简单多边形的三角划分可在线性时间内完成[13]。然后，在凹多边重叠区三角划分的基础上，完成连接轴的构造，具体的构造算法描述如下。
算法3 凹多边形重叠区连接轴生成
1)将凹多边重叠区三角划分结果中非重叠区边界上的三角边标记为新增三角边。
2) 以任意一条新增三角边的中点为起点分别向两侧追踪。若共享该边的三角形的另外两边中有新增三角边，则连接起点与新增三角边的中点构成一条子轴，并以新的中点为起点，继续追踪；若共享该边的三角形的另外两边中没有新增三角边，则结束追踪。
3) 端对端连接所有子轴即构成完整的连接轴，连接轴的两个端点成为连接锚点。
图 5给出了凹多边形重叠区连接轴生成的示意图，边界连接点或其他锚点选择与连接轴的两个锚点中距离最近的锚点相连即可形成新的接缝线(图 4(d))。图 6(a)展示了针对图 3(d)的情形，若直接采用质心会造成最终镶嵌结果中出现空洞。将凹多边形重叠区抽象为连接轴能有效防止空洞产生，如图 6(b)所示。因为连接轴是由离散的三角形新增边的中点连接生成，它必定位于多边形内部，相当于凹多边形重叠区内的一条分割线，有效地避开了凹多边形的凹角，连接轴仅通过两个端点与外部相连，从而能防止空洞的产生。
Figure 5. Generation of Connected Pivot
Figure 6. Use Connected Pivot to Prevent Holes
-
在卫星遥感影像处理中，非四边形重叠的情形比较普遍，如图 7(a)展示了48幅高分1号卫星影像的覆盖和重叠情况，图中的3处放大细节A、B、C与图 3(a)~3(c)的非四边形重叠情形基本对应。AVDO方法具有坚实的理论基础，理论上要寻找重叠区的中心线，但文献[3]没有给出非四边形重叠区接缝线的具体实现，因此对第一组实验也无法给出有效的解决方案。相比而言，ODI方法更为有效，对重叠区形状能更好地适应。图 7(b)展示了基于ODI方法生成的接缝线网络。因为出现了高度重叠区，使得低度重叠区变为无效重叠区(算法1中的步骤4)和步骤5))，不参与接缝线的连接，因此对于放大细节处生成的接缝线并不像图 4所展示的一样。
Figure 7. Seamline Network Based on ODI Method
图 8则显示了一个凹多边形重叠区的具体实例。其中，图 8(a)是一幅已经镶嵌好的影像产品，需要在其基础上追加镶嵌一幅影像图 8(b)，它们有效范围的空间位置关系如图 8(c)所示。图 9给出了基于ODI方法生成的凹多边形重叠区的接缝线(见图 9(a))、有效镶嵌多边形(见图 9(b))和最终镶嵌结果(见图 9(c))。
Figure 8. Case with Concave Polygon Overlapping Area
Figure 9. Seamline and Mosaicking Result Based on ODI Method
本文进一步对比了两种方法的接缝线和有效镶嵌多边形生成效率。实验分为两组，影像分别为高分1号49景和高分2号53景，分辨率分别为0.8 m和2 m，影像重叠区均为四边形。实验的基本硬件环境为：8核i7处理器，主频3.4 GHz，8 GB内存，硬盘7 200转，64 MB缓存。实验结果如表 2所示，处理时间仅包括接缝线和有效镶嵌多边形生成的时间。可以看出，本文方法的生成效率上要优于AVDO方法。分析原因主要包括两点：一是ODI方法采用了高效的位运算；二是ODI方法参与最终接缝生成的只有有效重叠区。
卫星与影像数量 方法 生成时间/ ms GF1 (49) AVDO 135 ODI 96 GF2 (53) AVDO 171 ODI 125 Table 2. Comparison of AVDO Method with ODI Method
-
本文提出了一种新颖的初始接缝线网络生成方法，它利用了影像的重叠拓扑信息而不是单纯的空间拓扑信息。重叠拓扑信息包括重叠发生的主体和重叠的程度，因为接缝线总是发生在重叠区域内，所以对重叠拓扑信息的挖掘有助于更好发现接缝之间的连接关系，进而有效地建立接缝线网络和有效镶嵌多边形。在具体的实现形式上，采用了比特数组来描述重叠拓扑信息，它可以被视为一种高效的数据结构，既降低了算法的复杂程度，也提高了算法的计算效率。与AVDO相比，本文方法主要有以下优势：
1) 更好的鲁棒性，能很好地处理包括凹多边形在内的复杂多边形重叠区情形。
2) 更高效的接缝线生成效率。
本文的研究仅涉及初始接缝线网络的生成，基于该网络接缝线局部优化是未来研究的工作。
DownLoad:
