摘 要：提出了一种确定图片重叠区域的通用算法。首先将两幅图片重叠部分的顶点存入一个交点数组，然后再分别将两幅图像的顶点与交点数组中的点进行比较，若交点数组中的点完全是其中一幅图的顶点，则该图即为重叠区域；否则，必须按照一定的算法来确定重叠区域。实验结果表明，该算法在易于编程实现的同时，也能很好地确定出影像间的重叠区域，并且适合确定多张影像的重叠区域。
关键词：重叠区域；求交；多边形；数组；图像

　图像拼接技术是将一组存在重叠部分的图像序列进行空间匹配对准，经重采样融合后形成一幅包含各图像序列信息的宽视角场景、完整、高清晰的新图像的技术[1]。该技术广泛应用在摄影测量学、虚拟现实技术、遥感影像处理、医学图像分析和计算机图形学等领域。
　一般来说，图像拼接流程包括图像预处理、图像配准和图像合成三个步骤。在进行多幅图像的拼接时，首先应确定标准像幅，标准像幅往往选择处于研究区中央的图像，以后的拼接工作都以此图像作为基准进行；其次确定拼接的顺序，即以标准像幅为中心，由中央向四周逐步进行。值得注意的是，拼接工作的着眼点是全部待拼接的图像，而落脚点却总是两幅相邻图像间的拼接。遥感图像拼接工作主要是基于相邻图像的重叠区，无论是色调调整还是几何镶嵌，都是将重叠区域作为基准进行的。重叠区域的确定是否准确，直接影响拼接的效果[2]。本文结合计算机图形学的知识，提出了一种确定自由像片重叠区域的算法。实验结果表明，该算法适合对多张影像进行重叠区域的确定。
1 图像配准
　图像配准主要指对参考图像和待拼接图像中的匹配进行提取，在提取出的信息中寻找最佳的匹配，完成图像间的对齐[1]。
　本文通过仿射变换进行图像配准，配准后自由像片重叠区域的确定问题就转化为多边形重叠区域的确定问题，即两个或多个面求交集的问题。因摄影过程中像片的自由度较大，重叠部分可能是三边形、四边形，甚至是八边形，故确定多边形的重叠区域将是一个较为复杂的过程，同时也增加了数据处理的难度。下面结合计算机图形学的知识研究有关该问题的一种通用算法[3]。
2 确定多边形重叠区域的理论基础
　简单多边形的一般定义是指不自相交的多边形，它可以包含0个或多个空洞。确定两个任意多边形交、并、差的问题既是计算几何和计算机图形学的基本问题，也是遥感影像处理、GIS叠加分析的理论基础[4]。本文讨论的是比较简单的凸多边形的情况。
在几何造型中，通常利用集合运算(交、并、差运算)实现复杂形体的构造，而集合运算需要大量的求交运算。求交时所用到的几何元素大致可分为三类：点、线、面。故在求交算法中，求交方法分为点点、点线、点面、线线、线面、面面六种。常用的求交有线与线的求交、线与面的求交和面与面的求交。多边形与多边形，即面与面之间的求交是最为复杂的一种。面与面求交的基本方法主要有代数方法、几何方法、离散方法和跟踪方法四种[5]。本文主要运用跟踪方法来实现多边形的求交。该方法是通过先求出初始交点，然后从已知的初始交点出发，相继跟踪计算出下一交点，从而求出整条交线的方法。其中，跟踪法的初始交点通常采用离散方法求得。
3 确定多边形重叠区域的算法流程
　自由像片重叠区域的确定为以后进行图像拼接奠定了良好的基础。因此有必要对多边形重叠区域的确定问题进行详细的研究。图像的重叠部分可以是规则的，也可以是不规则的，可以是由三条边所围成的图像，也可以是由四条边甚至更多条边所围成的图像。为了确定多边形的重叠区域，本文以相对比较简单且规则的四边形为例来进行讨论。设有两个四边形A={a1，a2，a3，a4}，B={b1，b2，b3，b4}，其中ai、bi(i=1、2、3、4)分别为四边形A与B的顶点。两顶点间的直线分别用Li、Ri表示(i为较小顶点标号)，两个四边形边的交点表示为Pij，其中i为左线段序号，j为右线段序号。两四边形的交集为P=A∩B={k|k∈A∧k∈B}，此交集即为重叠区域。
通过分析，对由两幅图像的重叠部分所构成的多边形区域进行以下几种情况的讨论，重叠区域的顶点坐标可通过计算获得，并存储在交点数组P[n]中。
　(1)所构成的多边形区域只包含图A的顶点。此时，P[n]中的点完全属于图A的顶点，则图B完全覆盖图A，图A为所求的重叠区域，如图1所示。

　(2)所构成的多边形区域只包含图B的顶点。此时，P[n]中的点完全属于图B，则图A完全覆盖图B，图B为所求的重叠区域，如图1所示。
　(3)所构成的多边形区域由图A和图B边的交点构成。此时，P[n]中的点既有图像A的顶点又有图像B的顶点，还包含有图像A与图像B的边的交点，则按照下述方法来确定重叠区域：首先找出一个交点，然后沿其中一条边(重叠区域边)的方向行进。由L1可以找到顶点a2，再沿着L2找到P24，此时要更换交点的追踪边，然后转换到R4边上，找到b1点。依此进行，直到最后的边R1刚好与P11的R1边连接，形成一个闭合区域，如图2所示。
确定多边形重叠区域的算法流程如图3所示。

4 确定多边形重叠区域的算法描述
　为了查找图A与图B的重叠区域，可以先将两幅图的顶点坐标分别存入数组A-Point[n]和数组B-Point[n]中，并定义一个交点数组P[n]。该数组用来存放由图A和图B所构成的重叠区域的所有交点。其中，存储图A和图B各顶点的横、纵坐标以及交点数组P[n]的横、纵坐标的数据结构可分别设计如下：
Typedef stu{
Int x，y；//图A各顶点的横、纵坐标；
} A-Point；
Typedef stu{
Int x，y； //图B各顶点的横、纵坐标；
} B-Point；
Typedef stu{
Int x，y； //数组P[n]各顶点的横、纵坐标；
} P-Point；
确定图A与图B的重叠区域的算法如下：
If P[n]!=null then
If P[n]中的点都是图像A的顶点 then
Cout<<“图像A为所求的重叠区域”；
//图B完全覆盖图A
Else
If P[n]中的交点都是图像B的顶点 then
Cout<<“图B为所求的重叠区域”；
//图A完全覆盖图B
Else
//图A与图B有交叉，用跟踪方法来确定多边形
//的重叠区域
Do
{ 找出图A与图B的一个交点，然后沿着交点所在边的方向行进顺次找下一个交点，并转换追踪边直至闭合；
}
While (P[n]= =null)
Endif
Endif
Else
Cout<<“图A与图B无重叠区域”；
//图A与图B不相交
Endif
Return 0； //结束
　上述算法中，判断交点数组中的所有点是否完全是图A或图B的顶点的方法大致有两种：
(1)将P[n]中的每个点的横、纵坐标与图A或图B的各个顶点的横、纵坐标相比较，若它们的横、纵坐标值完全相同，则一幅图完全覆盖另一幅图。
　(2)判断交点数组P[n]中的所有点是否是图A或图B的内点。若P[n]中的所有点都是图A的内点，则图A完全覆盖图B，图B为重叠区域；若P[n]中的所有点都是图B的内点，则图B完全覆盖图A，图A为重叠区域(注：因点与多边形的位置关系有三种，即：点在多边形内、点在多边形上、点在多边形外。故本文把在多边形内的点简称为内点，在多边形外的点简称为外点)。
　本文是在计算机图形学的基础上进行研究的，通过对多边形重叠区域的分析总结出图像与图像之间重叠区域的确定问题。该算法已用VC++语言实现，现给出如图4、图5所示的一个算例的执行结果，其中图4为两个四边形图A和图B，图5为图A与图B的重叠区域。

　实践表明，此种确定多边形重叠区域的算法具有很好的实验结果，算法结构清晰易懂，易于编程实现。需要说明的是，该算法虽然也可以同时对多张(大于两张)自由像片的重叠区域进行确定，但随着像片数量的增多，其处理速度也会降低。此问题也有待于今后进一步地探讨和研究。
参考文献
[1] 陈挺.图像拼接算法及实现[EB/OL].http：//www.studa.net/yingyong/090603/1636506.html，2009-06/2010-04.
[2] 黄晓萍.基础地理信息工程[EB/OL].http：//course.cug.edu.cn/cugThird/base_MAPGIS/classroom/5-3-1.htm，2002-3/2010-04.
[3] 王悦，吴云东，张魁珂，等.自由像片重叠区域的确定及拼接[J].海洋测绘，2008，28(5)：1-4.
[4] 朱雅音，王化文，万丰，等．确定两个任意简单多边形交、并、差的算法[J]．计算机研究与发展，2003，40(4)：1-8.
[5] 和青芳.计算机图形学原理及算法教程(Visual C++)[M/CD].http：//wenku.baidu.com/view/bb4117661ed9ad51f01df27d.html， 2010.02.15／2010.04.06.