arXiv:2401.07378v3 宣告类型: 替换-交叉 摘要: 土推移距离（EMD）是两个分布之间重要相似性度量，在计算机视觉和其他许多应用领域中都有应用。然而，其精确计算在计算和内存方面都极其耗时和耗资源，这阻碍了其在大规模问题中的可扩展性和适用性。已经提出了多种大约 EMD 算法以减少计算成本，但这些方法在准确性和可能需要额外内存使用或手动参数调整方面存在不足。在本文中，我们提出了一种新的方法 NNS-EMD，通过最近邻搜索（NNS）来近似 EMD，以实现高精度、低时间复杂度和高内存效率。NNS 操作减少了每次 NNS 迭代中比较的数据点数量，并为并行处理提供了机会。我们还通过 GPU 向量化进一步加速了 NNS-EMD，这对大型数据集尤为有益。我们比较了 NNS-EMD 与 EMD 的精确实现和最先进的大约 EMD 算法在图像分类和检索任务中的性能。我们还使用 NNS-EMD 计算运输映射，并在图像之间实现色彩转移。NNS-EMD 相对于精确 EMD 实现可以快 44 到 135 倍，并在对比现有的大约 EMD 方法时展现出卓越的准确度、加速和内存效率。