计算三维点云的EMD速度非常慢。

Question

计算三维点云的EMD速度非常慢。

pythonscipydistancepoint-cloudsearth-movers-distance

3

我想使用以下代码计算至少有 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))

- mlghost

如果没有关于我们处理的数据集的详细信息，就很难从这里进行优化。（假设这是完整的代码）因此，请考虑提供更多详细信息，以帮助他人解决您的问题。 - mishsx

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fuglede · Accepted Answer

自 SciPy 1.4.0（于2019年12月发布）起，有了这个 pull request的工作，linear_sum_assignment的实现速度得到了显著提高。特别是，可以在一台旧笔记本电脑上不到10秒内解决2000x2000几何实例问题；请参阅该 pull request 和相关线程中的一些基准测试。

自 SciPy 1.6.0（于2020年12月发布）起，还有 scipy.sparse.csgraph.min_weight_full_bipartite_matching 可以用作 linear_sum_assignment 的替代品；顾名思义，它旨在处理稀疏输入；您的输入当然是所有元素都非零的，对于几何输入来说它通常会比较慢，但在某些情况下也值得考虑。