计算 3D 点云的 EMD 非常慢
Calculating EMD for 3D point-clouds is very SLOW
我想使用 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))
截至 SciPy 1.4.0（2019 年 12 月发布），随着 this pull request 的工作，linear_sum_assignment 的实施速度大大加快。特别是，在过时的笔记本电脑上可以在不到 10 秒的时间内解决 2000x2000 几何实例；查看拉取请求和相关线程中的一些基准。
自 SciPy 1.6.0（2020 年 12 月发布）起，还有 scipy.sparse.csgraph.min_weight_full_bipartite_matching，可用作 linear_sum_assignment 的直接替代品；顾名思义，它旨在与稀疏输入一起使用；你的当然是稀疏的一切，对于几何输入它会 generally be slower，但在某些情况下它也值得研究。
我想使用 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))
截至 SciPy 1.4.0（2019 年 12 月发布），随着 this pull request 的工作，linear_sum_assignment 的实施速度大大加快。特别是，在过时的笔记本电脑上可以在不到 10 秒的时间内解决 2000x2000 几何实例；查看拉取请求和相关线程中的一些基准。
自 SciPy 1.6.0（2020 年 12 月发布）起，还有 scipy.sparse.csgraph.min_weight_full_bipartite_matching，可用作 linear_sum_assignment 的直接替代品；顾名思义，它旨在与稀疏输入一起使用；你的当然是稀疏的一切，对于几何输入它会 generally be slower，但在某些情况下它也值得研究。