類似画像検索

類似画像検索とは、沢山ある画像の中から、任意の画像と見た目が似ているものを自動的に選択するアルゴリズムです。 Google画像検索などに応用されています。
今回は簡単な類似画像検索をpythonとopencvを使って実装していきます。

アルゴリズム

類似画像検索は以下のアルゴリズムで実行できます。

データベースの作成

検索対象の画像集合を準備する
各画像に対し画像ハッシュを求める
画像パスと画像ハッシュをデータベースに登録する

検索処理

検索対象のクエリ画像を選択する
クエリ画像の画像ハッシュ値を求める
データベースの要素を順番に参照する
クエリと要素のハッシュ値を比較し、最も距離が近いものを記録する
すべての要素に対し3,4を繰り返す
最も距離の近い要素を類似画像として出力する

ここで、距離は一般的にハミング距離を使います。
これは画像ハッシュがビット列で扱われる為だと思うので、ビット列ではない異なる画像特徴量を用いる場合は、
COS類似度やマハラノビス距離など異なる距離尺度を用いて良いと思います。

実装

上記のアルゴリズムをpythonで実装していきます。

データベースの作成部分

検索対象の画像パスの一覧を作成します。ルートディレクトリからだーっと全部検索していってもいいのですが、
今回はちょっと楽をする為に、カレントディレクトリにimages/を作成し、そこに画像をコピーしてきました。 images/に保存された各画像のdHashのテーブルを作成するコードは以下になります。

import cv2
import numpy as np
import os


def dHash(img, N):
    img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    img = cv2.resize(img, (N+1, N))

    out = img[:, 1:] > img[:, :-1]
    return out.astype(np.int64)


def make_database(dir_path):
    txt = open("database.txt", "w")
    for f in os.listdir(dir_path):
        img = cv2.imread(dir_path + "/" + f)
        dh = dHash(img, 8)
        dh = dh.flatten()
        dh = int("".join(map(str, dh)), base=2)
        txt.write(dir_path+"/"+f +","+str(dh)+"\n")
    txt.close()


if __name__ == "__main__":
    make_database("images/")

dHashは画像ハッシュ関数です。詳細は前の記事を参照してください。
これを実行すると直下にdabase.txtが作成されます。
中身はカンマ区切りで画像パスとハッシュ値(int64)が行ごとに書かれています。

検索処理

選択されたクエリ画像のハッシュ値を求め、データベースを参照します。
まず、データベースの値を読み取ります。

def load_database():
    txt = open("./database.txt", "r").read().split("\n")[:-1]
    paths = [t.split(",")[0] for t in txt]
    hashes = [format(int(t.split(",")[1]), "064b") for t in txt]
    return paths, hashes

読み取り処理は普通のファイル処理です。
読み取りついでにint64で保存されたハッシュ値からバイナリ列に変換しています。

次に検索処理を実装します。検索処理は与えられたクエリ画像のハッシュ値を求め、データベースと比較します。
実装自体は簡単で、先程求めたデータベースのハッシュリストと、クエリ画像のハッシュ値を比較するだけです。

import cv2
import numpy as np
import os
import sys
from scipy.spatial.distance import hamming


def dHash(img, N):
    img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    img = cv2.resize(img, (N+1, N))

    out = img[:, 1:] > img[:, :-1]
    return out.astype(np.int64)


def load_database():
    txt = open("./database.txt", "r").read().split("\n")[:-1]
    paths = [t.split(",")[0] for t in txt]
    hashes = [format(int(t.split(",")[1]), "064b") for t in txt]
    return paths, hashes


def search(hashes, dhash):
    str2list = lambda x: list(map(int, x))  # バイナリ文字列からint listへの変換
    f = lambda v: hamming(dhash, str2list(v)) # ハミング距離を求める関数

    distances = list(map(f, hashes))
    min_index = np.argsort(distances) #ハミング距離の小さい順にソート

    return min_index, distances


if __name__ == "__main__":
    img_path = "./image.jpg"

    pathes, hashes = load_database()
    q = cv2.imread(img_path)
    dh = dHash(q, 8).flatten()
    min_index, distances = search(hashes, dh)

    print("１番目に類似した画像", pathes[min_index[0]])
    print("２番目に類似した画像", pathes[min_index[1]])

動作例

PC内の画像をかき集めて実験してみました。そのまま実験結果を載せようとすると色々な意味で問題が起きそうだったので、
処理後の結果だけ載せます。

入力画像	類似画像	dHashのハミング距離
		0.0
		0.28125

すごくTinyに実装した割には概ね似ている画像が出てきているように思います。
しかしながら、dHashは色情報をうまく扱えないので、「えーこれが似てない扱いなの？」って結果も散見されました。
この辺は、色情報を含めたハッシュ化（特徴量抽出）が必要かもしれませんね。
また、処理時間は画像300枚に対して6msくらいでした。
今回は愚直に線形探索を行いましたが、世の中にはハッシュ探索の賢い実装もあるので、それも試してみたいですね。