python - 计算 3D 点云的 EMD 非常慢

Question

我想使用 Earth Mover's Distance 和以下代码计算两个至少有 2000 个点的 3D 点云之间的距离，但是它太慢并且无法正常工作。那么，有什么方法可以更快地计算出近似值吗？

    from scipy.spatial.distance import cdist
    from scipy.optimize import linear_sum_assignment

    def emd(self):
        d = cdist(self.X, self.Y)
        assignment = linear_sum_assignment(d)
        return d[assignment].sum() / min(len(self.X), len(self.Y))

Answer 1

从 SciPy 1.4.0（2019 年 12 月发布）开始，借助此 pull request的工作，实施linear_sum_assignment速度大大加快。特别是，在一台过时的笔记本电脑上，2000x2000 几何实例可以在不到 10 秒的时间内解决；查看拉取请求和相关线程中的一些基准。

从 SciPy 1.6.0（2020 年 12 月发布）开始，还有scipy.sparse.csgraph.min_weight_full_bipartite_matching; 可以直接替代linear_sum_assignment; 顾名思义，它旨在与稀疏输入一起使用；当然，你的一切都是稀疏的，对于几何输入，它通常会比较慢，但在某些情况下，它也值得研究。