计算3D点云的EMD非常慢

Question

我想使用下面的代码使用“地球移动器的距离”来计算至少具有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起（即将发布，但相关更改已可从来源获得），尤其是在this pull request的工作下，linear_sum_assignment的实现大大加快了，特别是，使用过时的笔记本电脑，可以在不到10秒的时间内解决2000x2000几何实例；如果您不想构建SciPy并且迫不及待地等待新版本发布，请参阅拉取请求和相关线程中的一些基准，以及查看this answer的注释以了解其他方法。