OpenCVで画像ヒストグラムの類似度をEarth Mover’s Distance (EMD)で求めてみる

しばらく遊び惚けてて、このブログ放置しておりましたが（笑）

先日、librosaで楽曲に含まれる12半音（クロマグラム）を表示してみましたが

memomemokun.hateblo.jp

librosaにはクロマグラムをはじめ、音楽楽曲に含まれるビートやテンポ、メルスペクトル、MFCC（メル周波数ケプストラム係数）やそのΔ特徴量、tonnetz(三和音のトーラス構造)など、様々な情報を解析することが可能なようなので、それらを使い、

クロマグラム類似度別とか、MFCC（メル周波数ケプストラム係数）類似度別とかに様々な楽曲を自動で分類できないかと思い、librosaをちょっと調べていたのですが、クロマグラムやMFCCのような何らかの確率分布同士の近さ加減を計る手段にワッサースタイン計量と言うものがあるそうで

ワッサースタイン計量 - Wikipedia

ワッサースタイン計量（ワッサースタインけいりょう、英: Wasserstein metric）とは、与えられた距離空間 M上の確率分布の間に定義される距離函数である。

直感的な説明としては、各分布をM上に堆積した土の単位量と見なすとき、ワッサースタイン計量とは一つの堆積を別の物へと移すときにかかる最小のコストである。そのようなコストは、移されるべき土の量に移す距離を掛けた値であるとされる。このアナロジーに従い、この計量は計算機科学の分野においてEMD（英語版）（earth mover's distance）として知られている。

「ワッサースタイン計量」という名前は、この概念を1969年に導入したロシアの数学者レオニード・ワッサースタイン（英語版）の名にちなみ、1970年にローランド・ドブルシン（英語版）によって付けられた。多くの英語の出版物においてはドイツ語のスペル "Wasserstein" が用いられている（これは、"Vasershtein" という名がドイツに起源を持つことに起因している）。

それを求めるためのEarth Mover’s Distance (EMD)というロジックがあるそうで（Earth mover's distance - Wikipedia）、幸い、Pythonの画像処理ライブラリーOpenCVのOpenCV v4 implementationにはEarth Mover’s Distanceを計算するためのその名もズバリEMDという関数があるので、使い方を調べてみることに。

OpenCVは当初Intelによって開発され、その後Willow Garageによってサポート（その後Willow GarageはIntelによって買収）された画像処理・画像解析および機械学習等の機能を持つC/C++、Java、Python、MATLAB用のBSDライセンスのオープンソース・ライブラリとのことなので、

まずは、画像のヒストグラムから、ヒストグラム同士の近さ（類似度）をOpenCVのEMD関数を使って、どんな感じで求められるのか試してみることに。

で、

まず、テスト結果を示すと、

使用する画像は以下の８つの画像で

	0.jpg
	1.jpg
	2.jpg
	3.jpg
	4.jpg
	5.jpg
	6.jpg
	7.jpg

上の画像のそれぞれのヒストグラムを求め、最初の画像「0.jpg」からのヒストグラム同士の近さ順を計算し並べてみると以下で、全体的に緑が多そうな0.jpgと2.jpgが一番近く、なんとなく使用されている色合いの近さ順に並んでる感じですね〜〜。

なを、今回のテストに使ったソースは以下で、下のテスト結果の、それぞれの画像と一緒に右側に添付している画像は元の画像のそれぞれのヒストグラム（BGR色分布）のグラフになります。

	0.jpg
	2.jpg
	5.jpeg
	3.jpg
	1.jpg
	4.jpg
	7.jpg
	6.jpg

上の結果を求めた時のソースは以下で

import cv2
import numpy as np
import matplotlib.pyplot as plt
import glob

# 読み込み画像のリサイズサイズ
IMG_SIZE = (400, 400)

# cv2.EMD用に２次元配列をシグネチャに変換する
def img_to_sig(arr):

    # cv2.EMDに渡す値は単精度浮動小数点数
    sig = np.empty((arr.size, 3), dtype=np.float32)
    count = 0
    for i in range(arr.shape[0]):
        for j in range(arr.shape[1]):
            sig[count] = np.array([arr[i,j], i, j])
            count += 1
    return sig
    
    
    
# BGR形式に格納されているcv2の画像情報のヒストグラムを求める
def img_hist(img):
    hist1 = cv2.calcHist([img], [0], None, [256], [0, 256])
    hist2 = cv2.calcHist([img], [1], None, [256], [0, 256])
    hist3 = cv2.calcHist([img], [2], None, [256], [0, 256])
    
    return np.hstack((hist1, hist2, hist3))
    


# ヒストグラムのグラフを出力する
def drawHist(img, hist):
    plt.cla()
    color = ('b','g','r')
    for i,col in enumerate(color):
        plt.plot(hist[:, i], color = col)
        plt.xlim([0,256])
    #ヒストグラムファイル名はやっつけで無理やり吐き出してます
    plt.savefig(img.replace('jpg', 'png') )
    
    

# 画像のヒストグラムの類似度を求める
def calcEMD():
    org_img = cv2.imread('0/0.jpg')
    org_img = cv2.resize(org_img, IMG_SIZE)
    org_hist = img_hist(org_img)
    sig1 = img_to_sig(org_hist)


    EMD = {}
    imgs = glob.glob('0/*.jpg')
    for img in imgs:
        target_img = cv2.imread(img)
        target_img = cv2.resize(target_img, IMG_SIZE)
        target_hist = img_hist(target_img)
        drawHist(img, target_hist)
        sig2 = img_to_sig(target_hist)
        dist, _, flow = cv2.EMD(sig1, sig2, cv2.DIST_L2)
        EMD[img] = dist

    return EMD


if __name__ == "__main__":

    EMD = calcEMD()
    for k, v in sorted(EMD.items(), key=lambda x: x[1]):
        print(str(k) + ": " + str(v))

計算結果が以下

ヒストグラムが近い画像ほどEMDの値は０に近くなっています。0.jpgは同じ画像同士なので本来EMDの値は０なのでしょうが、計算誤差ですがね、めちゃ小さい値で０にはなってませんがご愛嬌ということで（笑）

0/0.jpg: 6.45833351882e-05
0/2.jpg: 28.4774799347
0/5.jpg: 38.5849494934
0/3.jpg: 39.4100914001
0/1.jpg: 42.3670158386
0/4.jpg: 51.9549560547
0/7.jpg: 59.3758888245
0/6.jpg: 75.4120178223

プログラム日記φ(．．)

おもにPython関係のプログラムメモ

OpenCVで画像ヒストグラムの類似度をEarth Mover’s Distance (EMD)で求めてみる