Earth Mover's Distance 簡介推土機距離

Earth Mover's Distance (EMD) 是 Rubner 於 2000 年在 IJCV 發表的文章 The Earth Mover's Distance as a Metric for Image Retrieval [1] 中提出來的衡量圖片相似度的方法。這個方法也可以用在衡量兩組集合，或是兩個機率分布的距離，因此 Earth Mover's Distance 不只被用來用於圖片檢索，也用在其他的地方。

Earth Mover's Distance 的定義

假設輸入為兩個向量 P 跟 Q，P 的維度是 M 而 Q 的維度是 N： \[ P = [p_1, p_2, \cdots , p_M] \\ Q = [q_1, q_2, \cdots , q_N] \] Earth Mover's Distance 的概念是想像 P 有 M 堆土，而我們想把 P 的土搬移到 Q 之中 N 堆土的樣子需要花的最少力氣。

舉個簡單的例子

假設 P = [1, 5, 1]，Q = [0, 4, 3] ，意思是有三個相鄰的土推，一開始三堆中分別有 [1, 5, 1] 單位的土，而相鄰的兩個土堆距離為 1，如果想要把這些土推變成 [0, 4, 3] ，最少需要花多少力氣才能完成？

在這個簡單的例子中，我們很容易可以看出只要分別從第一與第二堆中移動一個單位到第三堆就是我們要的答案，也就是說總共所花的力氣為 1 * 2 + 1 * 1 = 3。而在 paper 中有提到在計算 Earth Mover's Distance 時還會 normalize，也就是除以兩個土堆總重量比較輕的那一個，因此在這個例子中 EMD 便為 3 / 7 = 0.4286。

如何解出 Earth Mover's Distance？

這個問題可以用線性規劃來解（註：想複習線性規劃的讀者可以先看以前的文章）。上面一段已經寫出了 P 跟 Q 的定義了，而在用線性規劃解問題時我們要把距離跟移動的土堆都寫成數學式子的形式。在這裡假設 D = [d_{ij}] 為 P 的第 i 堆至 Q 的第 j 堆的距離，而我們想要找的是 F = [f_{ij}]，代表從 P 的第 i 堆移動了多少土去 Q 的第 j 堆。把土從 P 移到 Q 所花的最佳方法為： \[ arg\ \underset{F}{min}\sum_{i=1}^{M} \sum_{j=1}^{N}d_{ij} f_{ij} \] 並且還得加上一些約束條件： \[ f_{ij} \geq 0 \\ \sum_{j=1}^N f_{ij} \leq p_i \\ \sum_{i=1}^M f_{ij} \leq q_j \\ \sum_{i=1}^{M} \sum_{j=1}^{N}d_{ij} f_{ij} = min(\sum_{i=1}^{M}p_i, \sum_{j=1}^{N}q_j) \] 第一式的意思為只能從 P 移到 Q，不能反過來；第二跟第三個條件是指 P 之中每堆土的存量與 Q 之中最多能放多少土；而第四個式子是指最多就只有那麼多土可以搬運。而找出最佳的 \(F^*\) 以後我們想要求的 Earth Mover's Distance 即為以下式子： \[ EMD(P, Q) = \frac{\sum_{i=1}^{M} \sum_{j=1}^{N}d_{ij} f_{ij}^*}{\sum_{i=1}^{M} \sum_{j=1}^{N}f_{ij}^*} \] 因此實務上想要算出 EMD 時可以寫出上面的約束式子，並且用線性規劃的演算法來求解。在這篇文章發表以後也有不少文章介紹如何用其他更有效率的演算法或近似演算法來更快地找出 EMD，有興趣的讀者可以自行去搜尋。

參考資料

[1] The Earth Mover's Distance as a Metric for Image Retrieval, Yossi Rubner, Carlo Tomasi and Leonidas J. Guibas, 2000