Earth Mover’s Distance

はじめに

　今回は、最近の業務で使用したEarth Mover’s Distance（EMD）と呼ばれる量について解説する。これは2つの分布の間の距離尺度を与える量である。

問題設定

　いま、運ぶ荷物Pと、それを収める倉庫Qがあるとする。Pに対しては、荷物の場所（位置座標p_i）と荷物量（w_{pi}）が定義される。一方で、Qに対しては、倉庫の場所（位置座標q_j）と倉庫の容量（w_{qj}）が定義される（下図参照）。

(1)   \begin{eqnarray*} P&=&\{(p_1,w_{p1}),(p_2,w_{p2}),\cdots,(p_m,w_{pm})\}\\ Q&=&\{(q_1,w_{q1}),(q_2,w_{q2}),\cdots,(q_n,w_{qn})\} \end{eqnarray*}


荷物Pにはm個のサイトが、倉庫Qにはn個のサイトが存在する。いま、p_iとq_jの間の距離d_{ij}=d(p_i,q_j)を考える。この距離d_{ij}を用いて次の量を定義する。

(2)   \begin{equation*} D(P,Q)=\min_F{\sum_{i=1}^{m}\sum_{j=1}^{n}f_{ij}d_{ij} \end{equation*}

あらゆるf_{ij}の組み合わせの中から2重和が最小となるものを見つけ、その最小値でD(P,Q)を定義するという意味である。ここで、f_{ij}は、PのiサイトからQのjサイトへ移動する荷物の量を表し、これには複数の束縛条件が付く。まず最初に次を満たさなければならない。

(3)   \begin{equation*} f_{ij}\geq0 \end{equation*}

これは、荷物の移動は常にPからQの向きであり逆行することはないことを表す。さらに、次の束縛条件が付く。

(4)   \begin{equation*} \sum_{j=1}^{n}f_{ij}\leq w_{pi} \end{equation*}

上式は、PのiサイトからQのすべての倉庫へ移動する荷物量は、Pのiサイトが持つ荷物量w_{pi}を超えることはないことを表している（下図参照）。

同様に、Qのjサイトの倉庫が受け入れられる荷物量はw_{qj}を超えることはない（下図参照）。

(5)   \begin{equation*} \sum_{i=1}^{m}f_{ij}\leq w_{qj} \end{equation*}


最後に次の条件を課す。

(6)   \begin{equation*} \sum_{i=1}^{m}\sum_{j=1}^{n}f_{ij}=\min{\left(\sum_{i=1}^{m}w_{pi},\sum_{j=1}^{n}w_{qj}\right)} \end{equation*}

つまり、PとQの間で移動する荷物の総量は、Pの荷物の総量とQの倉庫の総容量の小さいほうに等しい。これら4つの束縛条件の下で次式が最適化される（再掲）。

(7)   \begin{equation*} D(P,Q)=\min_F{\sum_{i=1}^{m}\sum_{j=1}^{n}f_{ij}d_{ij} \end{equation*}

最適化されたf_{ij}^{*}を用いて次式を定義する。

(8)   \begin{equation*} D_{emd}(P,Q)=\dfrac{\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n}f_{ij}^{*}d_{ij}}{\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n}f_{ij}^{*}} \end{equation*}

D_{emd}(P,Q)がEarth Mover’s Distance（EMD）である。

適用例

　画像処理では、2つの画像の類似度を見る際にEMDが用いられることがある。今回はこの適用例を紹介する。下の4つの画像を考える。

カッコ内には画像の幅・高さと色の数が記載してある。これらの画像は通常のRGB画像とは異なり、色数が制限されている。例えば、sea_1という画像の（R,G,B）の組の数は78個である。つまり、78個の色で表現された画像ということになる。画像sea_1の場合、画素数は256\times174=44544である。そして、各画素には78個の色のうちどれかひとつだけが割り振られている。各色がいくつの画素に割り振られているかを勘定するとヒストグラムを得ることができる（下図参照）。

横軸は各色に適当に番号を付けたもの、縦軸は各色に属する画素数である。このヒストグラムは画像sea_1の特徴を表現する分布とみなすことができる。そして、色の値(R,G,B)を座標値、その色に属する画素数を荷物量/倉庫の容量とみなせばEMDを用いて2つの画像間の距離を計算することができることに気付くだろう。計算コードはここにある（C++言語で実装した）。残念ならがPythonで利用できるEMDを計算するライブラリは見当たらなかったので、こちらのC言語で実装されたコードを利用した。各ペア間のEMDの値を以下に示す。

海同士の画像や山同士の画像の間の距離の方が、海と山の画像間の距離よりも小さいことが分かる。

まとめ

　今回は、2つの分布間の距離を表すEarth Mover’s Distance（EMD）を紹介した。これは、複数の束縛条件の下で最適化される距離である。束縛条件を少し変えれば、あるPythonライブラリを使うことができるが、一般的なEMDとは異なってしまうのでC言語のコードを利用した。
　ところで、なぜEarth Move’s Distanceと呼ぶのだろうか？私の推測だが、ここで使われるEarthは「地球」ではなく「土」や「土量」を意味すると思われる。ある場所の土を別の場所に移す際の労力を測る尺度という意味でEarth Mover’s Distanceという名前が付いたのではなかろうか。

Kumada Seiya

Kumada Seiya

仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP