资源三号卫星是中国高分辨率立体测图卫星，用于1:5万测绘产品生产和1:2.5万及更大比例尺地图的修测和更新^{[1, 2]}。2012-01-09发射的资源三号01星是中国第一颗民用高分辨率光学传输型测绘卫星，搭载了2台分辨率优于3.5 m、幅宽优于50 km的前后视全色CCD(charge coupled device)相机，1台分辨率优于2.1 m、幅宽优于50 km的正视全色CCD相机和1台分辨率优于5.8 m的多光谱相机^[3]。资源三号02星于2016-05-30发射。发射后，与在轨工作的01星形成有效互补，双星在轨稳定运行，及时获取高分辨率影像数据，实现了高分影像数据覆盖全国，并按需求获取境外重点关注区域数据^{[4, 5]}。

进行目标地理区域的立体测图^[6]及数字高程模型(digital elevation model，DEM)^[7]生产时，在满足同轨立体的前提下，需要尽可能完全覆盖目标空间区域的影像，且在满足影像拼接的前提下，尽可能降低相邻影像的空间重复覆盖范围，即影像数量尽量少。如何从大量重复覆盖的数据中获取满足条件的尽可能少的数据，是数据生产前期迫切要解决的问题。数据生产及分发人员只能通过人工挑选的方式，从多张重叠的影像中挑选出目标影像，当目标地理区域范围较大时，人工挑选工作量较大，或者基本不可能实现。

资源三号卫星立体影像区域覆盖问题主要是对资源三号的传感器校正产品、几何校正数据等影像产品数据进行一定条件下的去重挑选，剥离出单纯的属性查询问题(如数据的采集时间、影像质量、云量等纯粹属性的查询问题^[8])，再利用算法满足以下需求：所查询到的数据是一组同轨立体像对组; 查询出来的影像数据要尽可能地完全覆盖目标地理区域; 相邻轨道的影像的重叠度要达到25%以上，方便相邻影像的拼接; 影像的数量尽可能少。

影像最优区域覆盖是一种集合覆盖问题(set covering problem，SCP)。是运筹学研究中典型的组合优化问题^[9]。经典SCP可以描述为：给定两个集合E和S，元素的集合E和E的子集的集合S，求出S的子集C，使得C中所有集合的并等于E，同时使得|C|最小。经典SCP最先被证明为多项式复杂程度的非确定性问题，随后给出一个多项式时间贪心近似算法，近似比为Inn，继而该算法又推广到带权的集合覆盖问题。由于集合覆盖问题的困难程度，近年来大量研究转移到其各种变体^[10]。

在遥感影像的生产过程中没有成熟的算法能够解决影像最优区域覆盖问题。但是智能机器人领域的全覆盖遍历路径规划(complete coverage path planning，CCPP)提供了新的解决方法^[11]，常见的算法有随机覆盖策略、单元分解法、基于模板的方法、基于传感器的覆盖方法等。其中，单元分解法是目前区域覆盖算法中应用较广泛的方法之一。它将目标区域分解为一些互不重叠的单元，由于单元中不包含任何障碍物，机器人可用简单地往返运动实现单元覆盖，区域的最优覆盖就转变为从一个单元到另一个单元的运动规划^[12]。另外，在无人机拍摄路径规划方面也有类似于CCPP的问题，覆盖搜索要求无人机在一定的约束条件下能够将待搜索区域无遗漏地遍历搜索，常见的搜索算法有随机搜索、平行搜索、网格搜索等^[13]。于驷男等^[14]还研究了多无人机对区域分割覆盖的算法，将研究区划分为多个子区域进行单机覆盖搜索算法设计，实现了区域的100%覆盖。

本文提出了一种区域最优覆盖算法，来解决获取目标区域立体影像数据集的问题。本研究中的区域最优覆盖算法为经典SCP的变体，给定空间范围区域A，查询得到所有覆盖A的数据集合E，E的子集的集合组成S，求S的子集C，使得C完全覆盖A，且C的元素个数最少。本文与CCPP研究的相同点是都是对目标区域实现全覆盖，主要差别是CCPP的机器人路径定义相对灵活，而本文的全覆盖算法中，卫星飞行轨道是固定的，所以影像的覆盖范围也是固定的。因此，本文研究的区域全覆盖问题不能采用CCPP问题的解决方法，但是本文仍然借鉴CCPP对目标研究区进行分割的方法，以覆盖区域为研究对象，用已有影像对目标区域进行连续切割，直至目标区域面积变为0。

1 影像最优区域覆盖算法设计

算法设计思路如下：首先，利用空间查询获取A内满足属性条件的影像数据集S；然后，以目标区域A的外接矩形A′₁左下角点M₁为坐标原点，x轴平行于赤道，y轴垂直于x轴指向北方向，建立平面直角坐标系。以S中的影像I_x(x=1, 2, 3, …)的内接矩形I′_x作为影像的有效区域，以M₁为起始点进行搜索，搜索覆盖点M₁且覆盖目标区域最大的影像I₁，利用I₁对A′₁裁切得到A′₂，再以A′₂右下角M₂为起点搜索覆盖目标区域最大的影像I₂，利用I₂再对A′₂进行裁切，直至目标区域的外界矩形被完全切割完毕，获得初步筛选影像集S_S。S_S中可能有一部分影像覆盖的查询区域被包含在其他几幅影像覆盖查询区域的并集中，这部分影像是多余的，再逐个影像遍历删除这部分影像。遍历完成时算法结束。

研究区地图采用2000国家大地坐标系的高斯投影。算法步骤如下：

1) 利用目标区域A的空间范围和属性条件查询到满足条件的影像数据集S。

2) 以目标区域A的外界矩形A′₁左下角M₁点为坐标原点，x轴平行于赤道，y轴垂直于x轴指向北方向，建立平面直角坐标系。

3) 以S中的影像I_x(x=1, 2, 3, …)的内接矩形I′_x作为影像的有效区域，I′_x组成的集合为S′。取影像的内接矩形，虽然缩小了一幅影像用作覆盖时的面积的大小，但是，影像的有效部分都是与坐标系平行的矩形，可以简化计算。

4) 以M₁为参考点，利用参考点进行搜索。选择影像的条件：M₁落在的影像有效区域I′_x内(本步如果查询到0张影像，则直接继续)，并且影像I′_x左下角点与参考点之间距离最近，记录本影像为I₁。

5) 利用I₁对A′₁进行裁切，获取裁切后的多边形，记为A′₂。

6) 取A′₂的节点中Y坐标最小的那一点为参考点，如果有2个或以上的点Y坐标都最小，则取其中最左边的点为参考点。重复步骤4)、步骤5)的查询过程，直到目标区域面积被裁切成0为止，得到的影像集合记为S_S。

7) 获取的S_S中，可能有一部分影像覆盖的查询区域被包含在其他几幅影像覆盖查询区域的并集中，这部分影像是多余的，需要删除。按照影像的采集时间顺序遍历S_S中的影像，查询与I_r相交的所有影像S_Sr，获取S_Sr的覆盖区域A_r，若A_r完全包含I_r，则删除I_r，直至所有S_S中的影像遍历完毕。

上述算法以影像的有效范围替代影像进行覆盖查询，对影像的空间范围损失较大。本文考虑将坐标系进行顺时针旋转，减小影像的底部与X轴的夹角，旋转坐标系后取得的内接矩形的面积更大，影像的有效范围更接近影像的实际范围，而且内接矩形边长仍与坐标轴保持平行。经试验对比，当坐标轴顺时针旋转6°时，取得的影像有效区域面积较大。

2 实验分析 2.1 实验条件

利用资源三号卫星传感器校正产品进行实验。目标空间范围为陕西省省级行政区划范围，并设定传感器类型为正视相机，设置数据采集日期为2012-01-09~2013-07-25，设置云量范围为0~20%，进行全覆盖查询。只在属性查询条件的约束下，陕西省范围内查询到影像数约1 500景。

2.2 实验结果分析

1) 算法坐标旋转角度实验分析。根据目标区域的影像轨道与坐标系的夹角情况，对坐标顺时针旋转3°~7°进行实验，查看获取的结果中的影像数量情况(在满足影像拼接需求的情况下，影像数量越少，结果越优)，取部分具有代表性的实验结果如表 1所示。

从表 1得出，当坐标顺时针旋转6°时，结果中影像数量最少，经验证结果影像能满足影像的拼接重叠度要求，所以改进算法中坐标旋转度数采用6°。

2) 影像最优区域覆盖结果分析。实验前影像的覆盖情况、坐标旋转前的影像覆盖情况及坐标旋转6°后的影像覆盖情况如图 1所示。

坐标旋转前的算法耗时及旋转6°后的算法耗时如表 2所示。坐标旋转前，平均耗时50.82″；坐标旋转6°后，平均耗时49.49″。

3) 实验总结。由图 1可知，在算法坐标旋转对比实验中：①坐标旋转前，筛选出的165景影像全部覆盖目标区域，平均耗时50.82″; ②坐标旋转6°后，最终筛选出132景影像全部覆盖目标区域，平均耗时49.49″。

实验验证了本算法实现了对目标空间区域的最优覆盖影像集的挑选。经过对比分析，同样的目标空间区域(陕西省)，不旋转坐标系，要165幅影像完全覆盖目标区域；当坐标系旋转6°后，需要最少132幅影像可完全覆盖目标区域。坐标旋转6°后的算法从获得的影像数量上有明显优势，算法运算速度上有优势。

3 结束语

本文研究了资源三号影像最优区域覆盖影像集的获取问题，与相关研究中的CCPP问题都是为了实现对目标区域实现全覆盖，最主要的差别是CCPP问题的机器人路径是相对灵活定义的，而本文的全覆盖问题，影像的覆盖范围也是固定的。因此，研究的区域全覆盖问题虽不能采用CCPP问题的解决方法，但CCPP问题中对目标研究区进行分割的思想为本文问题的解决带来了启发。本文提出的最优区域覆盖算法，采用了空间切割方式，利用影像有效空间范围将目标研究区域连续地切割，直到目标区域被完全切割完，获取最优影像集合。

本文通过实验验证了本算法的有效性，能够大大降低人工手动挑选数据的复杂度，大幅度提高影像挑选效率。原算法对影像数据本身的限制较少，在资源三号01星、02星的数据分发挑选中适用，同样适用于其他立体测图卫星影像的挑选；采用坐标旋转改进后的算法，在其他卫星影像使用过程中，需要根据卫星轨道参数、目标区域空间位置、相邻轨道影像拼接等要求对坐标旋转角度进行适应性调整。

本算法仍然存在一些待改进的方面：在实现影像挑选的过程中，没有考虑属性条件的对比；另外，仅仅依靠本算法有时无法满足用户对单张影像内部特定区域关注度高的需求。后续研究一方面从属性角度考虑算法的改进；另一方面，也可以在程序中提供手动挑选的接口，采用人机交互方式优化挑选结果。