【综述专栏】点云距离度量：完全解析EMD距离(Earth Mover's Distance)

在科学研究中，从方法论上来讲，都应“先见森林，再见树木”。当前，人工智能学术研究方兴未艾，技术迅猛发展，可谓万木争荣，日新月异。对于AI从业者来说，在广袤的知识森林中，系统梳理脉络，才能更好地把握趋势。为此，我们精选国内外优秀的综述文章，开辟“综述专栏”，敬请关注。

作者：刘昕宸

地址：https://www.zhihu.com/people/liu-xin-chen-64

01

我们为什么需要度量点云距离

EMD距离度量两个分布之间的距离。这里的分布当然可以是点云。

意义：

在传统机器学习任务中，我们常用L1范数、L2范数来计算表征之间的距离。

在图像领域，我们可以使用pixel-wise的差异来计算图像之间的距离。

但是对于点云这种数据结构，距离度量需要对点的排布具有不变性。那么应该怎么设计呢？EMD距离就是适用点云的度量方式之一。

有了距离度量方式，我们就能够通过实现反向传播，来实现深度学习任务中必需的loss function设计

有了loss function，我们就可以将其应用到点云上采样、补全、重建等多种生成式任务中，来实现形状和几何的约束

举个例子：

下图是点云补全网络PCN的网络结构图（挖个坑：PCN这篇论文，我后面会介绍）

可以看到下面绿框的decoder部分，Coarse output和Coarse ground truth之间的CD/EMD，Detailed output和Ground truth之间的CD，就是点云处理的深度学习任务中常用于约束形状的loss。

这里CD和EMD的目的基本是等价的，都是为了约束生成点云的形状尽可能接近ground truth。

CD就是指Chamfer Distance，也是一种点云之间差异的度量方式，本文最后会有介绍。

02

EMD距离是怎么做的

2.1 从运输问题说起

某公司从两个产地  将物品运往三个销地  ，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：

问应如何调运，使得总运输费最小？

解：

产地： 

销地： 

总产量和总销量一样。

设  表示从产地  调运到  的运输量（  ）

因此可建立数学模型：

约束条件：

2.2 线性规划

我们已经将一个非常实际的运输问题，建模成了一个数学模型。

解决这个数学模型，我们需要使用线性规划。

线性规划及其解法单纯形算法不是本文的重点讨论对象，感兴趣的朋友可以参考大佬的文章：

线性规划：

https://www.zhihu.com/question/320977814/answer/673901696

解决线性规划的单纯形算法：

https://zhuanlan.zhihu.com/p/31644892

2.3 EMD距离建模

EMD距离用于衡量（在某一特征空间下）两个多维分布之间的dissimilarity

其中具体single features之间的距离度量方式是需要给定的，EMD的目标是"lifts" this distance from individual features to full distributions.

EMD的idea：

给定两个分布，将一个看成是在空间中适当分布的土堆，将另一个看成是在空间中适当分布的洞，EMD距离测量的就是用这些土堆填满这些洞，所需要的最小工作量。（这是不是和我们上面介绍的运输问题特别相似？？？！！！）

单位工作量为：运输从土堆到洞单位距离的单位土堆

因此顾名思义：Earth Mover's Distance

EMD建模：

分布可以由一组cluster表示，每个cluster由其均值以及属于该cluster的一部分表示。

这种表示分布的方式我们称为分布的signature（比如我们可以理解成“直方图”）

EMD的计算方式是基于著名的运输问题的。

第1个signature(m clusters)：

第2个signature(n clusters)： 

 表示距离矩阵，  表示  和  之间的距离

我们目标找到一个flow  使得下面目标函数最小：

约束条件：

第1个约束：使得flow只能P到Q，而不能反向。

第2、3个约束：限制supply的量，需要满足不大于各个weight

第4个约束：保证了合理运输的最大值（即总产量和总销量中小的那一个）

以上运输问题通过线性规划解决之后，我们可以得到  ，我们可据此计算EMD（也就是将上面的  归一化）：

是不是感觉上面写的挺抽象的？不是很好理解？那我们整点具体的！

类比运输问题：

我们将上面的公式和2.1中的运输问题具体例子做个一一对应，应该理解起来就清楚多了。

 表示产地集合，  表示  个产地，  表示每个产地的产量

 表示销地集合，  表示  个销地，  表示每个销地的销量

 表示从第  个产地到第  个销地（单位运输量的）运输花销

 表示从第  个产地到第  个销地的规划运输量

那么此时，  就表示将  物资运输到  的总运输费

 就表示使得总运输费最小的调度方式

类比点云距离度量：

 表示第一个点云，  表示  个点（三维坐标表示），  表示每个点的权重（可以理解为数量，这里都为1）

 表示第二个点云，  表示  个点（三维坐标表示），  表示每个点的权重（可以理解成数量，这里都为1）

表示从  第  个点到  第  个点的距离（比如直接用欧式距离）

 内容为0/1，表示是否将  第  个点移动到第  个点

那么此时，  就表示将  中所有点移动到  中所有点位置的总花费

 就表示使得总移动花费最小的调度方式

03

EMD距离的优势

为什么要费这么大劲弄出来EMD距离呢？其homepage上列了6个原因：

• Naturally extends the notion of a distance between single elements to that of a distance between sets, or distributions, of elements.
• Can be applied to the more general variable-size signatures, which subsume histograms. Signatures are more compact, and the cost of moving "earth" reflects the notion of nearness properly, without the quantization problems of most other measures.
• Allows for partial matches in a very natural way. This is important, for instance, for image retrieval and in order to deal with occlusions and clutter.
• Is a true metric if the ground distance is metric and if the total weights of two signatures are equal. This allows endowing image spaces with a metric structure.
• Is bounded from below by the distance between the centers of mass of the two signatures when the ground distance is induced by a norm. Using this lower bound in retrieval systems significantly reduced the number of EMD computations.
• Matches perceptual similarity better than other measures, when the ground distance is perceptually meaningful. This was shown by[2] for color- and texture-based image retrieval.

04

其他度量方式

4.1 CD(Chamfer Distance)

计算点云  和  的CD：

计算配对  中每个点与其距离最近的  中点的距离，并将它们相加：

对称版本CD：

4.2 HD(Hausdorff Disance)

• directed distance

• distance(symmetry)

05

参考资料

https://wenku.baidu.com/view/4bcdc4273b68011ca300a6c30c2259010302f343.html

http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RUBNER/emd.htm

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

直播预告

“综述专栏”历史文章

更多综述专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！