作者：劉昕宸
位址：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
本文目的在于學術交流，并不代表本公衆号贊同其觀點或對其内容真實性負責，版權歸原作者所有，如有侵權請告知删除。