推土距离 The Earth Mover's Distance
Last updated
Last updated
参考：
在传统机器学习任务中，我们常用L1范数、L2范数来计算表征之间的距离。
在图像领域，我们可以使用pixel-wise的差异来计算图像之间的距离。
但是对于点云这种数据结构，距离度量需要对点的排布具有不变性。那么应该怎么设计呢？EMD距离就是适用点云的度量方式之一。
EMD距离，表示了两个点云A和B，把点云A的点移动到点云B中，使得总移动花费最小的调度方式
地球移动距离（EMD）是一种衡量两个多维分布差异的方法。它考虑了特征空间中的基本距离，并将其应用到完整的分布上。
简单来说，给定两个分布，一个可以想象成空间里分布的土堆，另一个是同一空间里的洞。
EMD就是测量用土填满洞所需的最少工作量。这里的工作量就是指将一单位的土通过一单位的距离进行运输。
分布可以用一组簇来表示，每个簇有其均值（或众数）和所属分布的比例。我们称之为分布表示。两个分布表示的大小可以不同，简单分布的表示比复杂分布的表示短。
计算EMD实际上是解决运输问题。设想有多个供应商向多个消费者供货，每个消费者都有一定的需求。对于每对供应商和消费者，给出运输商品的成本。运输问题就是找到满足消费者需求的最低成本的商品流。我们可以将一个分布表示视为供应商，另一个分布表示视为消费者，然后计算供应商和消费者之间的成本。最后，解决方案就是将一个分布表示转换为另一个分布表示所需的最小工作量。
这可以形式化为以下线性规划问题：设
为具有m个簇的第一个分布表示，其中pi是簇代表，w{pi}是簇的权重
是具有n个簇的第二个分布表示
D是基本距离矩阵，其中dij是簇pi和簇qj之间的基本距离。
我们希望找到一个流量矩阵
其中fij表示pi与qj之间的流量，以使得总成本最小化：
簇代表（cluster representative）是指在一个簇（cluster）内部，用来代表该簇特征的点。在处理数据时，我们通常希望用较为简洁的方式来表示数据集的特征，因此会将数据划分为若干个簇。每个簇内的数据点在特征空间中相对较为接近。
簇代表通常是通过计算簇内数据点的均值（mean）或众数（mode）得到的。这个代表性点可以反映簇内数据的主要特征，有时也称为簇的质心（centroid）。通过使用簇代表，我们可以用较少的信息来近似描述整个数据集的特征，从而简化计算和分析过程。
类比运输问题：
我们将上面的公式和2.1中的运输问题具体例子做个一一对应，应该理解起来就清楚多了。
P表示产地集合， {p1, p2 ... pm} 表示 m个产地， {wp1, wp2 ... wpm} 表示每个产地的产量
Q表示销地集合， {q1, q2 ... qn} 表示 n个销地， {wq1, wq2 ... wqn} 表示每个销地的销量
D=[dij] 表示从第 i 个产地到第 j 个销地（单位运输量的）运输花销
F=[fij] 表示从第 i 个产地到第 j 个销地的规划运输量
那么此时， WORK(P, Q, F) 就表示将 P 物资运输到 Q 的总运输费
F∗=argmaxF WORK(P, Q, F) 就表示使得总运输费最小的调度方式
以下约束条件需要满足：
第一个约束条件允许从P向Q移动“供应”，而不是反过来。 接下来的两个约束条件限制了P中簇可以发送的供应量不超过其权重，Q中簇接收的供应量也不超过其权重； 最后一个约束条件要求移动尽可能多的供应量。我们称这个数量为总流量。 一旦解决了运输问题并找到了最优流量矩阵F，EMD距离就被定义为归一化的工作量与总流量之比：
引入归一化因子是为了避免在部分匹配情况下偏好较小的分布表示。EMD具有以下优点：
自然地将单个元素之间的距离概念扩展到元素集合或分布之间的距离。
可以应用于更通用的可变大小分布表示，这些表示包含了直方图。分布表示更紧凑，移动“土壤”的成本正确地反映了接近程度的概念，而没有大多数其他度量的量化问题。
以非常自然的方式允许部分匹配。这在图像检索和处理遮挡和杂乱等问题中非常重要。
如果基本距离是度量且两个分布表示的总权重相等，则EMD是真正的度量。这允许为图像空间赋予度量结构。
当基本距离由范数引导时，EMD的下界为两个分布表示的质心之间的距离。在检索系统中使用这个下界显著减少了EMD计算的次数。
当基本距离在感知上有意义时，EMD比其他度量更能匹配感知相似性。这已经在[2]中基于颜色和纹理的图像检索中得到证实。 有关EMD的更多细节可以在[2]中找到。
