计算 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(2019 年 12 月发布(开始，通过此拉取请求的工作，linear_sum_assignment的实施速度大大加快。特别是，在过时的笔记本电脑上可以在不到 10 秒的时间内解决 2000x2000 个几何实例;请参阅拉取请求和相关线程中的一些基准。

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