作者:刘昕宸
地址: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.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个原因:
04
其他度量方式
计算点云
和
的CD:
计算配对
中每个点与其距离最近的
中点的距离,并将它们相加:
对称版本CD:
05
参考资料
https://wenku.baidu.com/view/4bcdc4273b68011ca300a6c30c2259010302f343.html
http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RUBNER/emd.htm
本文目的在于学术交流,并不代表本公众号赞同其观点或对其内容真实性负责,版权归原作者所有,如有侵权请告知删除。