点云距离度量——EMD距离

红太狼 2022-12-19 01:21 185阅读 0赞

https://mp.weixin.qq.com/s/YA8bubqiH6-f1grKlI8vbQ  
https://zhuanlan.zhihu.com/p/270675634  
（超级形象容易理解！）

首发于 小刘学计算机视觉

写文章

![点云距离度量：完全解析EMD距离(Earth Mover's Distance)][EMD_Earth Mover_s Distance]

# 点云距离度量：完全解析EMD距离(Earth Mover's Distance) #

![刘昕宸][v2-921b3954c50cba02fb07d2604346823f_xs.jpg_source_172ae18b]

刘昕宸

[][Link 1]

清华大学 软件学院硕士在读

关注他

8 人 赞同了该文章

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

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，也是一种点云之间差异的度量方式，本文最后会有介绍。

![v2-f62c9f522c0f3f8e50828c0e4a35903a_b.jpg][] ![v2-f62c9f522c0f3f8e50828c0e4a35903a_720w.jpg][]

## 2 EMD距离是怎么做的 ##

## 2.1 从运输问题说起 ##

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

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

**解：**

产地： ![\[公式\]][equation_tex_A_1_2C_A_2_3A_200_2B_300_3D_500]

销地： ![\[公式\]][equation_tex_B_1_2C_B_2_2C_B_3_3A_150_2B_150_2B_200_3D_500]

总产量和总销量一样。

设 ![\[公式\]][equation_tex_x_7Bij_7D] 表示从产地 ![\[公式\]][equation_tex_A_i] 调运到 ![\[公式\]][equation_tex_B_j] 的运输量（ ![\[公式\]][equation_tex_i_3D1_2C2_3B_j_3D1_2C2_2C3] ）

因此可建立数学模型：

![\[公式\]][equation_tex_5Cmin_f_3D_6x_7B11_7D_2B4x_7B12_7D_2B6x_7B13_7D_2B6x_7B21_7D_2B5x_7B22_7D_2B5x_7B23_7D_5C_5C]

约束条件：

![\[公式\]][equation_tex_x_7B11_7D_2Bx_7B12_7D_2Bx_7B13_7D_5Cleq200_5C_5C]

![\[公式\]][equation_tex_x_7B21_7D_2Bx_7B22_7D_2Bx_7B23_7D_5Cleq300_5C_5C]  
![\[公式\]][equation_tex_x_7B11_7D_2B_x_7B21_7D_5Cleq_150_5C_5C]

![\[公式\]][equation_tex_x_7B12_7D_2Bx_7B22_7D_5Cleq_150_5C_5C]

![\[公式\]][equation_tex_x_7B13_7D_2Bx_7B23_7D_5Cleq_200_5C_5C]

![\[公式\]][equation_tex_x_7Bij_7D_5Cgeq_0_5Cquad_28i_3D1_2C2_3B_j_3D_1_2C2_2C3_29_5C_5C]

## 2.2 线性规划 ##

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

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

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

线性规划：

[线性规划是什么。能否详细说明一下？www.zhihu.com![图标][v2-e08bcdacd85c15a96ec60c1f1292c198_ipico.jpg]][www.zhihu.com_v2-e08bcdacd85c15a96ec60c1f1292c198_ipico.jpg]

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

[blue：简单理解线性规划的单纯形算法zhuanlan.zhihu.com![图标][equation_ipico.jpg]][blue_zhuanlan.zhihu.com_equation_ipico.jpg]

## 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)：![\[公式\]][equation_tex_P_3D_5C_7B_28p_1_2C_5Comega_7Bp_1_7D_29_2C_..._2C_28p_m_2C_5Comega_7Bp_m_7D_29_5C_7D]

第2个signature(n clusters)： ![\[公式\]][equation_tex_Q_3D_5C_7B_28q_1_2C_5Comega_7Bq_1_7D_29_2C_..._2C_28q_n_2C_5Comega_7Bq_n_7D_29_5C_7D]

![\[公式\]][equation_tex_D_3D_5Bd_7Bij_7D_5D] 表示距离矩阵， ![\[公式\]][equation_tex_d_7Bij_7D] 表示 ![\[公式\]][equation_tex_p_i] 和 ![\[公式\]][equation_tex_q_j] 之间的距离

我们目标找到一个flow ![\[公式\]][equation_tex_F_3D_5Bf_7Bij_7D_5D] 使得下面**目标函数**最小：

![\[公式\]][equation_tex_F_5E_2A_3D_5Carg_5Cmax_F_WORK_28P_2CQ_2CF_29_3D_5Carg_5Cmax_F_5Cleft_28_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_d_7Bij_7D_5Cright_29_5C_5C]

**约束条件：**

![\[公式\]][equation_tex_f_7Bij_7D_5Cgeq_0_5Cquad_5Cquad_1_5Cleq_i_5Cleq_m_2C_1_5Cleq_j_5Cleq_n_5C_5C]

![\[公式\]][equation_tex_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_5Cleq_5Comega_7Bp_i_7D_2C_5Cquad_5Cquad_1_5Cleq_i_5Cleq_m_5C_5C]

![\[公式\]][equation_tex_5Csum_7Bi_3D1_7D_5Em_f_7Bij_7D_5Cleq_5Comega_7Bq_j_7D_2C_5Cquad_5Cquad_1_5Cleq_i_5Cleq_n_5C_5C]

![\[公式\]][equation_tex_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_3D_5Cmin_28_5Csum_7Bi_3D1_7D_5Em_5Comega_7Bp_i_7D_2C_5Csum_7Bj_3D1_7D_5En_5Comega_7Bq_j_7D_29_5C_5C]

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

第2、3个约束：限制supply的量，需要满足不大于各个weight ![\[公式\]][equation_tex_5Comega]

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

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

![\[公式\]][equation_tex_EMD_28P_2CQ_29_3D_5Cfrac_7B_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_d_7Bij_7D_7D_7B_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_7D_5C_5C]

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

**类比运输问题：**

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

![\[公式\]][equation_tex_P] 表示产地集合， ![\[公式\]][equation_tex_5C_7B_p_1_2C_..._2C_p_m_5C_7D] 表示 ![\[公式\]][equation_tex_m] 个产地， ![\[公式\]][equation_tex_5C_7B_5Comega_7Bp_1_7D_2C_..._2C_5Comega_7Bp_m_7D_5C_7D] 表示每个产地的产量

![\[公式\]][equation_tex_Q] 表示销地集合， ![\[公式\]][equation_tex_5C_7B_q_1_2C_..._2C_q_n_5C_7D] 表示 ![\[公式\]][equation_tex_n] 个销地， ![\[公式\]][equation_tex_5C_7B_5Comega_7Bq_1_7D_2C_..._2C_5Comega_7Bq_n_7D_5C_7D] 表示每个销地的销量

![\[公式\]][equation_tex_D_3D_5Bd_7Bij_7D_5D] 表示从第 ![\[公式\]][equation_tex_i] 个产地到第 ![\[公式\]][equation_tex_j] 个销地（单位运输量的）运输花销

![\[公式\]][equation_tex_F_3D_5Bf_7Bij_7D_5D] 表示从第 ![\[公式\]][equation_tex_i] 个产地到第 ![\[公式\]][equation_tex_j] 个销地的规划运输量

那么此时， ![\[公式\]][equation_tex_WORK_28P_2CQ_2CF_29] 就表示将 ![\[公式\]][equation_tex_P] 物资运输到 ![\[公式\]][equation_tex_Q] 的总运输费

![\[公式\]][equation_tex_F_5E_2A_3D_5Carg_5Cmax_F_WORK_28P_2CQ_2CF_29] 就表示**使得总运输费最小的调度方式**

**类比点云距离度量：**

![\[公式\]][equation_tex_P] 表示第一个点云， ![\[公式\]][equation_tex_5C_7B_p_1_2C_..._2C_p_m_5C_7D] 表示 ![\[公式\]][equation_tex_m] 个点（三维坐标表示）， ![\[公式\]][equation_tex_5C_7B_5Comega_7Bp_1_7D_2C_..._2C_5Comega_7Bp_m_7D_5C_7D] 表示每个点的权重（可以理解为数量，这里都为1）

![\[公式\]][equation_tex_Q] 表示第二个点云， ![\[公式\]][equation_tex_5C_7B_q_1_2C_..._2C_q_n_5C_7D] 表示 ![\[公式\]][equation_tex_n] 个点（三维坐标表示）， ![\[公式\]][equation_tex_5C_7B_5Comega_7Bq_1_7D_2C_..._2C_5Comega_7Bq_n_7D_5C_7D] 表示每个点的权重（可以理解成数量，这里都为1）

![\[公式\]][equation_tex_D_3D_5Bd_7Bij_7D_5D]表示从 ![\[公式\]][equation_tex_P] 第 ![\[公式\]][equation_tex_i] 个点到 ![\[公式\]][equation_tex_Q] 第 ![\[公式\]][equation_tex_j] 个点的距离（比如直接用欧式距离）

![\[公式\]][equation_tex_F_3D_5Bf_7Bij_7D_5D] 内容为0/1，表示是否将 ![\[公式\]][equation_tex_P] 第 ![\[公式\]][equation_tex_i] 个点移动到 ![\[公式\]][equation_tex_Q] 第 ![\[公式\]][equation_tex_j] 个点

那么此时， ![\[公式\]][equation_tex_WORK_28P_2CQ_2CF_29] 就表示将 ![\[公式\]][equation_tex_P] 中所有点移动到 ![\[公式\]][equation_tex_Q] 中所有点位置的总花费

![\[公式\]][equation_tex_F_5E_2A_3D_5Carg_5Cmax_F_WORK_28P_2CQ_2CF_29] 就表示**使得总移动花费最小的调度方式**

## 3 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.

## 4 其他度量方式 ##

## 4.1 CD(Chamfer Distance) ##

计算点云 ![\[公式\]][equation_tex_P_1] 和 ![\[公式\]][equation_tex_P_2] 的CD：

计算配对 ![\[公式\]][equation_tex_P_1] 中每个点与其距离最近的 ![\[公式\]][equation_tex_P_2] 中点的距离，并将它们相加：

![\[公式\]][equation_tex_Ch_28P_1_2C_P_2_29_3D_5Csum_7Bp_1_5Cin_P_1_7D_5Cmin_7Bp_2_5Cin_P_2_7D_7C_7C_p_1_-_p_2_7C_7C_5C_5C]

对称版本CD：

![\[公式\]][equation_tex_CH_28P_1_2C_P_2_29_3D_Ch_28P_1_2C_P_2_29_2B_Ch_28P_2_2C_P_1_29_5C_5C]

## 4.2 HD(**Hausdorff Disance**) ##

*  directed distance

![\[公式\]][equation_tex_h_28P_1_2C_P_2_29_3D_5Cmax_7Bp_1_5Cin_P_1_7D_5Cmin_7Bp_2_5Cin_P_2_7D_7C_7Cp_1_-_p_2_7C_7C_5C_5C]

*  distance(symmetry)

![\[公式\]][equation_tex_H_28P_1_2C_P_2_29_3D_5Cmax_5Cleft_28h_28P_1_2CP_2_29_2C_h_28P_2_2C_P_1_29_5Cright_29_5C_5C]

## 5 参考资料 ##

[运筹学运输问题- - 百度文库wenku.baidu.com][- - _wenku.baidu.com]

[EMDhomepages.inf.ed.ac.uk![图标][v2-b2ce787be96241beb4e8f202f4f58f9d_180x120.jpg]][homepage]

发布于 11-03

「真诚赞赏，手留余香」

赞赏

还没有人赞赏，快来当第一个赞赏的人吧！

深度学习（Deep Learning）

计算机视觉

三维视觉

赞同 83 条评论

喜欢 收藏 申请转载

赞同 8

### 文章被以下专栏收录 ###

*  ![小刘学计算机视觉][4b70deef7_xs.jpg_source_172ae18b]
    
    ## 小刘学计算机视觉 ##
    
    记录小刘的计算机视觉学习之路
    
    关注专栏
    
    ![算法集锦][4b70deef7_xs.jpg_source_172ae18b 1]
    
    ## 算法集锦 ##
    
    关于各种算法的集合
    
    关注专栏

### 推荐阅读 ###

*  # 点云配准论文 #
    
    点云配准，求解两个(具有overlap的)点云P, Q之间的变换(旋转矩阵和平移向量)，使得点云P, Q的坐标处于同一坐标系下。点云配准在无人驾驶、三维重建等领域具有广泛的应用。 本文整理了点云配…
    
    千百度 
    
    ![搞懂PointNet++，这篇文章就够了！][PointNet]
    
    # 搞懂PointNet++，这篇文章就够了！ #
    
    刘昕宸 发表于小刘学计算...
    
    # ECCV2020优秀paper汇总|涉及点云处理、三维重建、深度估计、姿态识别、3D识别与检测等 #
    
    整理：Tom Hardy 公众号：3D视觉工坊前言ECCV2020的oral和spotlight名单已经发布，与往年相比，accepted paper list中增加了很多3D方向相关的作品，实在值得鼓舞。 工坊对这些优秀作品进行…
    
    Tom H... 发表于计算机视觉...
    
    ![细嚼慢咽读论文：点云补全网络 GRNet][GRNet]
    
    # 细嚼慢咽读论文：点云补全网络 GRNet #
    
    刘昕宸 发表于小刘学计算...

## 3 条评论 ##

切换为时间排序

写下你的评论...

发布

*  ![陈超][v2-278d6cf2210d517fe662f2109630476f_s.jpg_source_06d4cd63]
    
    陈超 11-03
    
    膜大佬
    
    赞 回复 踩 举报
 *  ![刘昕宸][v2-921b3954c50cba02fb07d2604346823f_s.jpg_source_06d4cd63]
    
    刘昕宸  (作者)  回复 陈超 11-03
    
    \[爱\]\[爱\]
    
    赞 回复 踩 举报

*  ![HfutSora][]
    
    HfutSora 11-03
    
    ![v2-ba306425d0a7aee2c7260381f1bf7b97.gif][]
    
    赞 回复 踩 举报

[EMD_Earth Mover_s Distance]: /images/20221120/1777d7e9c7b04d77a6091ebe130abad3.png
[v2-921b3954c50cba02fb07d2604346823f_xs.jpg_source_172ae18b]: /images/20221120/6ea820dc79e3482c94cb4419e4fee0f8.png
[Link 1]: https://www.zhihu.com/question/48510028
[v2-f62c9f522c0f3f8e50828c0e4a35903a_b.jpg]: https://pic3.zhimg.com/v2-f62c9f522c0f3f8e50828c0e4a35903a_b.jpg
[v2-f62c9f522c0f3f8e50828c0e4a35903a_720w.jpg]: /images/20221120/a61b2760abc74984bbc1d4f1a61f01bd.png
[equation_tex_A_1_2C_A_2]: https://www.zhihu.com/equation?tex=A_1%2C+A_2
[equation_tex_B_1_2C_B_2_2C_B_3]: https://www.zhihu.com/equation?tex=B_1%2C+B_2%2C+B_3
[equation_tex_A_1_2C_A_2_3A_200_2B_300_3D_500]: https://www.zhihu.com/equation?tex=A_1%2C+A_2+%3A+200+%2B+300+%3D+500
[equation_tex_B_1_2C_B_2_2C_B_3_3A_150_2B_150_2B_200_3D_500]: https://www.zhihu.com/equation?tex=B_1%2C+B_2%2C+B_3+%3A+150+%2B+150+%2B+200+%3D+500
[equation_tex_x_7Bij_7D]: https://www.zhihu.com/equation?tex=x_%7Bij%7D
[equation_tex_A_i]: https://www.zhihu.com/equation?tex=A_i
[equation_tex_B_j]: https://www.zhihu.com/equation?tex=B_j
[equation_tex_i_3D1_2C2_3B_j_3D1_2C2_2C3]: https://www.zhihu.com/equation?tex=i%3D1%2C2%3B+j%3D1%2C2%2C3
[equation_tex_5Cmin_f_3D_6x_7B11_7D_2B4x_7B12_7D_2B6x_7B13_7D_2B6x_7B21_7D_2B5x_7B22_7D_2B5x_7B23_7D_5C_5C]: https://www.zhihu.com/equation?tex=%5Cmin+f+%3D+6x_%7B11%7D%2B4x_%7B12%7D%2B6x_%7B13%7D%2B6x_%7B21%7D%2B5x_%7B22%7D%2B5x_%7B23%7D%5C%5C
[equation_tex_x_7B11_7D_2Bx_7B12_7D_2Bx_7B13_7D_5Cleq200_5C_5C]: /images/20221120/1cc28cb4732e4652828621d2a8351dbd.png
[equation_tex_x_7B21_7D_2Bx_7B22_7D_2Bx_7B23_7D_5Cleq300_5C_5C]: /images/20221120/1244537abfc54361a1641b6b62a8c7b8.png
[equation_tex_x_7B11_7D_2B_x_7B21_7D_5Cleq_150_5C_5C]: https://www.zhihu.com/equation?tex=x_%7B11%7D+%2B+x_%7B21%7D+%5Cleq+150+%5C%5C
[equation_tex_x_7B12_7D_2Bx_7B22_7D_5Cleq_150_5C_5C]: https://www.zhihu.com/equation?tex=x_%7B12%7D%2Bx_%7B22%7D+%5Cleq+150+%5C%5C
[equation_tex_x_7B13_7D_2Bx_7B23_7D_5Cleq_200_5C_5C]: https://www.zhihu.com/equation?tex=x_%7B13%7D%2Bx_%7B23%7D+%5Cleq+200+%5C%5C
[equation_tex_x_7Bij_7D_5Cgeq_0_5Cquad_28i_3D1_2C2_3B_j_3D_1_2C2_2C3_29_5C_5C]: https://www.zhihu.com/equation?tex=x_%7Bij%7D+%5Cgeq+0+%5Cquad+%28i%3D1%2C2%3B+j+%3D+1%2C2%2C3%29+%5C%5C
[v2-e08bcdacd85c15a96ec60c1f1292c198_ipico.jpg]: https://pic1.zhimg.com/v2-e08bcdacd85c15a96ec60c1f1292c198_ipico.jpg
[www.zhihu.com_v2-e08bcdacd85c15a96ec60c1f1292c198_ipico.jpg]: /images/20221120/f5cb31ff89f84fefae028f9aeaed9de4.png
[equation_ipico.jpg]: https://pic2.zhimg.com/equation_ipico.jpg
[blue_zhuanlan.zhihu.com_equation_ipico.jpg]: /images/20221120/bb38b38c908a4a178d0c70f30cfac57d.png
[equation_tex_P_3D_5C_7B_28p_1_2C_5Comega_7Bp_1_7D_29_2C_..._2C_28p_m_2C_5Comega_7Bp_m_7D_29_5C_7D]: https://www.zhihu.com/equation?tex=P+%3D+%5C%7B+%28p_1%2C+%5Comega_%7Bp_1%7D%29%2C+...%2C+%28p_m%2C+%5Comega_%7Bp_m%7D%29+%5C%7D
[equation_tex_Q_3D_5C_7B_28q_1_2C_5Comega_7Bq_1_7D_29_2C_..._2C_28q_n_2C_5Comega_7Bq_n_7D_29_5C_7D]: /images/20221120/8bb6d8529d6b4013a2442ec809210c00.png+%3D+%5C%7B+%28q_1%2C+%5Comega_%7Bq_1%7D%29%2C+...%2C+%28q_n%2C+%5Comega_%7Bq_n%7D%29+%5C%7D
[equation_tex_D_3D_5Bd_7Bij_7D_5D]: https://www.zhihu.com/equation?tex=D+%3D+%5Bd_%7Bij%7D%5D
[equation_tex_d_7Bij_7D]: https://www.zhihu.com/equation?tex=d_%7Bij%7D
[equation_tex_p_i]: https://www.zhihu.com/equation?tex=p_i
[equation_tex_q_j]: /images/20221120/9888f5bb251b48f2be5d3261811f41e3.png
[equation_tex_F_3D_5Bf_7Bij_7D_5D]: /images/20221120/ca2dd1d3d26a47f195065c34b5e6c48d.png
[equation_tex_F_5E_2A_3D_5Carg_5Cmax_F_WORK_28P_2CQ_2CF_29_3D_5Carg_5Cmax_F_5Cleft_28_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_d_7Bij_7D_5Cright_29_5C_5C]: https://www.zhihu.com/equation?tex=F%5E%2A+%3D+%5Carg+%5Cmax_F+WORK%28P%2CQ%2CF%29+%3D+%5Carg+%5Cmax_F+%5Cleft+%28+%5Csum_%7Bi%3D1%7D%5Em+%5Csum_%7Bj%3D1%7D%5En+f_%7Bij%7D+d_%7Bij%7D+%5Cright%29%5C%5C
[equation_tex_f_7Bij_7D_5Cgeq_0_5Cquad_5Cquad_1_5Cleq_i_5Cleq_m_2C_1_5Cleq_j_5Cleq_n_5C_5C]: https://www.zhihu.com/equation?tex=f_%7Bij%7D+%5Cgeq+0+%5Cquad+%5Cquad+1+%5Cleq+i+%5Cleq+m%2C+1+%5Cleq+j+%5Cleq+n%5C%5C
[equation_tex_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_5Cleq_5Comega_7Bp_i_7D_2C_5Cquad_5Cquad_1_5Cleq_i_5Cleq_m_5C_5C]: https://www.zhihu.com/equation?tex=%5Csum_%7Bj%3D1%7D%5En+f_%7Bij%7D+%5Cleq+%5Comega_%7Bp_i%7D%2C+%5Cquad+%5Cquad+1+%5Cleq+i+%5Cleq+m%5C%5C
[equation_tex_5Csum_7Bi_3D1_7D_5Em_f_7Bij_7D_5Cleq_5Comega_7Bq_j_7D_2C_5Cquad_5Cquad_1_5Cleq_i_5Cleq_n_5C_5C]: https://www.zhihu.com/equation?tex=%5Csum_%7Bi%3D1%7D%5Em+f_%7Bij%7D+%5Cleq+%5Comega_%7Bq_j%7D%2C+%5Cquad+%5Cquad+1+%5Cleq+i+%5Cleq+n%5C%5C
[equation_tex_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_3D_5Cmin_28_5Csum_7Bi_3D1_7D_5Em_5Comega_7Bp_i_7D_2C_5Csum_7Bj_3D1_7D_5En_5Comega_7Bq_j_7D_29_5C_5C]: https://www.zhihu.com/equation?tex=%5Csum_%7Bi%3D1%7D%5Em+%5Csum_%7Bj%3D1%7D%5En+f_%7Bij%7D+%3D+%5Cmin%28%5Csum_%7Bi%3D1%7D%5Em+%5Comega_%7Bp_i%7D%2C+%5Csum_%7Bj%3D1%7D%5En+%5Comega_%7Bq_j%7D%29%5C%5C
[equation_tex_5Comega]: /images/20221120/e98b10d3cefc4e0e91f4e8eca4013f10.png
[equation_tex_F_5E_2A]: https://www.zhihu.com/equation?tex=F%5E%2A
[equation_tex_WORK_28P_2CQ_2CF_29]: /images/20221120/5ae238ab3edb4b99bed66ab6aa4b8598.png
[equation_tex_EMD_28P_2CQ_29_3D_5Cfrac_7B_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_d_7Bij_7D_7D_7B_5Csum_7Bi_3D1_7D_5Em_5Csum_7Bj_3D1_7D_5En_f_7Bij_7D_7D_5C_5C]: https://www.zhihu.com/equation?tex=EMD%28P%2CQ%29+%3D+%5Cfrac+%7B%5Csum_%7Bi%3D1%7D%5Em+%5Csum_%7Bj%3D1%7D%5En+f_%7Bij%7D+d_%7Bij%7D%7D+%7B%5Csum_%7Bi%3D1%7D%5Em+%5Csum_%7Bj%3D1%7D%5En+f_%7Bij%7D%7D+%5C%5C
[equation_tex_P]: https://www.zhihu.com/equation?tex=P
[equation_tex_5C_7B_p_1_2C_..._2C_p_m_5C_7D]: https://www.zhihu.com/equation?tex=%5C%7B+p_1%2C+...%2C+p_m+%5C%7D
[equation_tex_m]: https://www.zhihu.com/equation?tex=m
[equation_tex_5C_7B_5Comega_7Bp_1_7D_2C_..._2C_5Comega_7Bp_m_7D_5C_7D]: https://www.zhihu.com/equation?tex=%5C%7B+%5Comega_%7Bp_1%7D%2C+...%2C+%5Comega_%7Bp_m%7D+%5C%7D
[equation_tex_Q]: /images/20221120/8bb6d8529d6b4013a2442ec809210c00.png
[equation_tex_5C_7B_q_1_2C_..._2C_q_n_5C_7D]: https://www.zhihu.com/equation?tex=%5C%7B+q_1%2C+...%2C+q_n+%5C%7D
[equation_tex_n]: https://www.zhihu.com/equation?tex=n
[equation_tex_5C_7B_5Comega_7Bq_1_7D_2C_..._2C_5Comega_7Bq_n_7D_5C_7D]: https://www.zhihu.com/equation?tex=%5C%7B+%5Comega_%7Bq_1%7D%2C+...%2C+%5Comega_%7Bq_n%7D+%5C%7D
[equation_tex_i]: https://www.zhihu.com/equation?tex=i
[equation_tex_j]: /images/20221120/7291f631ad634eb792a126940c6d61a3.png
[equation_tex_F_5E_2A_3D_5Carg_5Cmax_F_WORK_28P_2CQ_2CF_29]: https://www.zhihu.com/equation?tex=F%5E%2A+%3D+%5Carg+%5Cmax_F+WORK%28P%2CQ%2CF%29
[homepage]: https://link.zhihu.com/?target=http%3A//homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RUBNER/emd.htm
[2]: https://link.zhihu.com/?target=http%3A//homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RUBNER/emd.htm%23RUBNER98A
[equation_tex_P_1]: https://www.zhihu.com/equation?tex=P_1
[equation_tex_P_2]: /images/20221120/fcf8fbab3e994b5098b14b62994aecff.png
[equation_tex_Ch_28P_1_2C_P_2_29_3D_5Csum_7Bp_1_5Cin_P_1_7D_5Cmin_7Bp_2_5Cin_P_2_7D_7C_7C_p_1_-_p_2_7C_7C_5C_5C]: https://www.zhihu.com/equation?tex=Ch%28P_1%2C+P_2%29+%3D+%5Csum_%7Bp_1+%5Cin+P_1%7D+%5Cmin_%7Bp_2+%5Cin+P_2%7D+%7C%7C+p_1+-+p_2+%7C%7C%5C%5C
[equation_tex_CH_28P_1_2C_P_2_29_3D_Ch_28P_1_2C_P_2_29_2B_Ch_28P_2_2C_P_1_29_5C_5C]: https://www.zhihu.com/equation?tex=CH%28P_1%2C+P_2%29+%3D+Ch%28P_1%2C+P_2%29+%2B+Ch%28P_2%2C+P_1%29%5C%5C
[equation_tex_h_28P_1_2C_P_2_29_3D_5Cmax_7Bp_1_5Cin_P_1_7D_5Cmin_7Bp_2_5Cin_P_2_7D_7C_7Cp_1_-_p_2_7C_7C_5C_5C]: https://www.zhihu.com/equation?tex=h%28P_1%2C+P_2%29+%3D+%5Cmax_%7Bp_1%5Cin+P_1%7D+%5Cmin_%7Bp_2+%5Cin+P_2%7D+%7C%7Cp_1+-+p_2%7C%7C%5C%5C
[equation_tex_H_28P_1_2C_P_2_29_3D_5Cmax_5Cleft_28h_28P_1_2CP_2_29_2C_h_28P_2_2C_P_1_29_5Cright_29_5C_5C]: https://www.zhihu.com/equation?tex=H%28P_1%2C+P_2%29+%3D+%5Cmax+%5Cleft+%28h%28P_1%2CP_2%29%2C+h%28P_2%2C+P_1%29+%5Cright+%29%5C%5C
[- - _wenku.baidu.com]: https://link.zhihu.com/?target=https%3A//wenku.baidu.com/view/4bcdc4273b68011ca300a6c30c2259010302f343.html
[v2-b2ce787be96241beb4e8f202f4f58f9d_180x120.jpg]: https://pic2.zhimg.com/v2-b2ce787be96241beb4e8f202f4f58f9d_180x120.jpg
[4b70deef7_xs.jpg_source_172ae18b]: https://pic2.zhimg.com/4b70deef7_xs.jpg?source=172ae18b
[4b70deef7_xs.jpg_source_172ae18b 1]: https://pic4.zhimg.com/4b70deef7_xs.jpg?source=172ae18b
[PointNet]: https://pic2.zhimg.com/v2-fe3c9853371c7c5237fa586420072ddc_250x0.jpg?source=172ae18b
[GRNet]: https://pic1.zhimg.com/v2-fe3c9853371c7c5237fa586420072ddc_250x0.jpg?source=172ae18b
[v2-278d6cf2210d517fe662f2109630476f_s.jpg_source_06d4cd63]: https://pic1.zhimg.com/v2-278d6cf2210d517fe662f2109630476f_s.jpg?source=06d4cd63
[v2-921b3954c50cba02fb07d2604346823f_s.jpg_source_06d4cd63]: https://pic1.zhimg.com/v2-921b3954c50cba02fb07d2604346823f_s.jpg?source=06d4cd63
[HfutSora]: https://pic4.zhimg.com/v2-d708e1abfa67cb3008c9952cb100ba77_s.jpg?source=06d4cd63
[v2-ba306425d0a7aee2c7260381f1bf7b97.gif]: https://pic4.zhimg.com/v2-ba306425d0a7aee2c7260381f1bf7b97.gif