《Remote Sensing》：A Discrete Grid-Based Approach for Efficient Near-Optimal Coverage Selection in a Large-Scale Remote Sensing Image Dataset
编辑推荐：
区域影像覆盖检索是大规模遥感数据处理中的关键问题。然而，传统的基于向量拓扑的方法在处理海量且高度重叠的数据集时，计算成本急剧增加。该研究提出了一种基于离散全球网格系统（Discrete Global Grid System, DGGS）的覆盖检索方法，将几何拓
区域影像覆盖检索是大规模遥感数据处理中的关键问题。然而，传统的基于向量拓扑的方法在处理海量且高度重叠的数据集时，计算成本急剧增加。该研究提出了一种基于离散全球网格系统（Discrete Global Grid System, DGGS）的覆盖检索方法，将几何拓扑操作转化为网格编码集合操作，从而在空间索引框架下重构覆盖计算过程。通过整合启发式贪心策略实现高效覆盖选择。实验结果表明，所提出的基于DGGS的方法实现了约1.5倍至11倍的加速比，具体取决于数据集规模与覆盖度。网格级别分析表明，7级网格通常在近完整覆盖检索中提供了空间精度与计算效率之间的良好平衡，而6级网格则为快速覆盖估计与稀疏覆盖场景提供了更具计算效率的替代方案，仅带来边缘精度损失。此外，该方法随数据量增加表现出近线性可扩展性，并在不完整覆盖场景下保持稳定性能。结果证实，基于DGGS的离散建模在保持空间可靠性的同时显著降低了计算复杂度，为PB级遥感数据处理提供了高效且可扩展的解决方案。
该研究针对大规模遥感影像覆盖优化中传统向量拓扑方法计算效率低下的问题，提出了一种基于离散全球网格系统（Discrete Global Grid System, DGGS）的区域影像覆盖检索框架。研究背景源于当前地球观测卫星数量的快速增长——全球已有超过2340颗民用地球观测卫星在轨运行，持续产生海量数据。尽管USGS Earth Explorer、NASA Earthdata、欧洲航天局哥白尼数据空间及中国国家 Earth Observation 数据中心等平台提供了基础数据检索功能，但面向土地利用变化分析、非正规聚落监测、作物产量预测、病虫害监测及水资源评估等具体应用时，仍需从候选数据集中选取最优影像子集以实现目标区域完整覆盖，同时最小化影像数量并最大化数据质量（如更新近的获取时间、更高的空间分辨率、更低的云量）。该问题可形式化为区域遥感影像覆盖优化问题，本质上是经典集合覆盖问题（Set Covering Problem, SCP）的变体，已知为NP-hard问题，计算复杂度随候选集规模急剧增长。
现有方法主要依赖基于向量的几何操作（如求交、并集、差集）来判定影像与目标区域间的覆盖关系，虽确保高几何精度，但频繁的拓扑操作导致高昂计算成本。随着候选影像数量增加，重复的多边形叠加与裁剪操作严重降低效率，制约了其在实时检索与大规模覆盖分析中的应用。为此，该研究采用DGGS作为核心空间表达框架，将覆盖关系表示为网格编码字符串集合，把计算密集型的几何拓扑操作转化为高效的基于集合的比较运算，确保多尺度空间一致性的同时显著提升计算效率。
研究采用的技术方法主要包括：基于H3算法的六边形网格离散化，将目标区域与影像足迹转化为指定分辨率的网格单元集合；构建融合时间相关性、空间分辨率与云量的多准则启发式函数，指导贪心影像选择策略；设计基于网格的覆盖更新机制与迭代优化流程，实现候选影像的高效筛选与近最优覆盖结果获取。实验样本队列来源包括：北京市行政区数据集（751景，来自吉林一号与天府星座，2023年8月）、陕西省行政区数据集（9524景，来自吉林一号与天府星座，2023年7-9月），以及日本区域四个不同覆盖度的数据集（210-1464景，来自GF-2，2015-2023年）。
实验一（全覆盖场景）在北京数据集上比较了DGGS方法（7级网格）与传统向量拓扑方法。结果表明，向量方法耗时6109 ms，选取109景影像实现100%覆盖；DGGS方法耗时3882 ms，选取105景影像，覆盖率达99.9889%，相对误差仅0.0111%，计算时间降低约36%。DGGS方法通过有效处理边缘边界与高重叠区域，以更少影像实现近完整覆盖——向量方法将小面积未覆盖多边形碎片视为需补偿的空隙，而DGGS将覆盖聚类为离散网格单元，吸收这些碎片，消除了对边际贡献影像的需求。
实验二（参数敏感性）在同一数据条件下开展5-8级网格的对比实验。结果显示，随网格级别增加，覆盖率单调提升但趋于饱和，7级以上仅约0.01%改善；计算时间呈非线性增长，8级时因网格单元数急剧增加导致复杂度显著上升。影像选择方面，5级网格因分辨率不足导致选取影像数明显偏少，6-7级趋于稳定，8级较7级仅增选1景。综合精度与效率，7级网格实现最佳平衡，6级网格在快速覆盖估计与稀疏覆盖场景中更具计算效率。
实验三（可扩展性）在陕西9524景大规模高重叠数据集上验证。7级DGGS方法覆盖率达99.9065%，与向量方法相差仅0.0935%；计算效率方面，6级DGGS提速约98.6%，7级达90.8%（约10.9倍加速）。7级方法较向量方法少选43景影像（约3.2%），在高度重叠条件下有效识别冗余影像。传统向量方法处理该数据集时，复杂多边形交互及大量顶点显著增加几何运算成本，而网格编码集合操作消除几何关系判定需求，优势在高重叠冗余数据中更为突出。
实验四（稳健性）以日本区域为研究区，构建覆盖度18.27%-95.49%的四组数据集。结果表明，不同覆盖度与数据规模下，6级与7级网格的覆盖率与实际覆盖度高度一致，误差可控，方法在稀疏与不完全覆盖场景下保持稳定性能。随覆盖度和数据规模增加，估计覆盖度稳定但存在轻微系统性低估；7级网格在高覆盖条件下精度略有提升但整体增益有限，辨识度收益递减。6级网格在多数应用场景中以显著降低的计算成本实现可靠覆盖估计。
讨论部分指出，基于DGGS的离散网格检索方法能够大幅降低计算时间同时保持高空间覆盖率。向量拓扑方法将大量时间耗费于几何运算，而DGGS将覆盖问题从复杂几何操作转化为基于网格编码的集合运算，降低计算复杂度。尽管引入小量覆盖误差，但效率提升显著，适用于高计算效率需求而非严格完整覆盖的场景，如大面积土地覆盖变化分析、作物产量估计、害虫迁徙趋势分析及气候变化研究等。
网格级别直接影响覆盖精度与计算时间，性能对网格级别选择敏感。更高网格级别提供更精细离散化与边界精度，但增加计算成本；更低级别降低计算量以轻微近似误差为代价。该参数可调，用户可根据应用精度需求与计算资源选择适当网格级别。未来可探索自适应网格级别选择策略以增强自动化与泛化能力。
方法加速比在不同数据集间变化明显（北京1.57倍至陕西10.9倍），范围约1.5-11倍，这可通过算法计算复杂度解释。方法主要迭代候选影像集与网格单元集合执行集合操作更新覆盖，整体时间复杂度大致可近似为O(n·|G
z|)。较小或稀疏覆盖数据集上操作开销占主导，加速有限；较大数据集或高度重叠数据可高效避免冗余计算，实现更高加速。这与实验中观察到的计算时间近线性增长一致，证明方法随数据集规模和覆盖密度增加而有效扩展。
在覆盖选择紧凑性方面，DGGS方法一致选取较向量方法更少的影像，同时维持几乎相同的覆盖率。这源于DGGS离散空间表征：向量方法以精确多边形操作评估覆盖关系，即使边界最小未覆盖部分也需增选影像；而DGGS框架中，碎片化边界区域与边际空间差异被吸收至邻近网格单元，高度重叠或仅具边际覆盖贡献的多幅影像常对应相同网格集合，从而实现更紧凑的影像选择。这种紧凑性以边界轻微近似误差为代价，但误差局部且可控，不损害整体覆盖效果。对于边界精度要求极高的应用，可提高网格分辨率或采用更精确的覆盖算法。
研究结论部分表明，该研究提出的基于DGGS的区域影像覆盖检索框架，将传统依赖向量的几何拓扑覆盖计算转化为网格编码集合操作，结合启发式引导的贪心选择策略，实现高计算效率与强可扩展性，同时保持空间一致性。综合实验从覆盖精度、计算效率、网格级别敏感性、大规模数据集可扩展性及稀疏覆盖稳健性等多角度验证了方法性能。结果证明，在全覆盖场景下，该方法与传统拓扑方法结果高度一致，同时显著降低计算时间，效率提升约1.5倍至11倍，数据规模越大优势越明显。适宜DGGS级别取决于应用场景：7级网格更适用于高精度区域覆盖优化任务，6级网格为快速覆盖估计与稀疏覆盖应用提供更高效替代方案。大规模高重叠数据条件下，方法计算增长稳定可预测，展现出强可扩展性；稀疏与不完全覆盖场景下，估计覆盖度与实际覆盖度高度一致，离散化误差可控且不引入系统性偏差。总体而言，网格化空间建模在保持覆盖结果可靠性的同时大幅提升计算效率。该研究证实，将DGGS与覆盖优化模型相结合，为大规模遥感影像覆盖检索提供了高效且结构简化的解决方案，可扩展替代传统拓扑方法，尤其适用于大规模遥感影像管理与快速覆盖分析等应用。
