pythonでBag-of-Visual Wordsとやらを実装してみた。

2016-03-05(初版) → 2016-03-04(改訂)

OpenCVとscikit-learnを組み合せて何か面白いことが出来ないか、なんて試行錯誤をしています。画像の類似度を調べて何か出来そうな気がしたので、ひとまず類似度を調べてみることにしました。

画像が似ているかどうかを調べる方法として、Bag-of-Visual Wordsというのがあるそうです。Bag-of-Wordsっていう文書をベクトルとして表現する手法の応用だとか。一枚一枚にベクトルを対応付けて、そのベクトルの距離で画像が似ているかどうかを判別するもののようです。ま、難しいことは良いでしょう、とりあえず。

ここで掲載したプログラムを実行するにはpython3とscikit-learn、OpenCV、numpyが必要になります。適当にインストールしておいてください。

手順

大雑把に言うと、以下のような手順でVisual Wordというものを作ります。

全ての画像の特徴点(局所特徴量)を抽出する。
抽出した特徴量を全部まとめてクラスタリングする。
クラスタリングで出来た代表点をVisual Wordとする。

で、その後以下のようにして個々の画像の特徴ベクトルを計算します。

特徴ベクトルが欲しい画像の特徴点を抽出する。
各特徴点と最も近いVisual Wordを探す。
見つけたVisual Wordに投票する。

投票ってのが謎ですが、要は特徴点をクラスタリングして、各クラスタに帰属した点の数を数えるイメージになります。

Visual Wordを作ってみる

で、ここからは実際に書いたものを見ていくことにします。全部実装したソースコードは末尾にありますが、最適化が入っているので見た目が違ったりします。ご了承ください。

特徴点を抽出する

特徴点の抽出にはAKAZEってやつを使いました。何か性能がとても良いらしい。この特徴点の抽出アルゴリズムが非常に重要らしいので、色々試してみると良いかと思います。ちなみに私は試していません。

akaze = cv2.AKAZE_create()

features = []
for img in images:
    features.extend(akaze.detectAndCompute(img, None)[1])

だいたいこんな感じです。imagesはOpenCV形式の画像データが入った配列と思ってください。 detectAndComputeを使うと二次元の配列として特徴点の情報を返してくれるのでとても便利。

2016-03-04 追記

コードの誤りを修正しました。

クラスタリングする

visual_words = MiniBatchKMeans(n_clusters=128).fit(features).cluster_centers_

どかーんとsklearnがやってくれます。素敵。 n_clustersというパラメータがクラスタの数になります。前述の通りクラスタの数はそのまま特徴ベクトルの次元数になりますので、この例だと128次元ということになります。画像枚数にもよりますが、もっと次元を増やした方が良いような気がします。

特徴ベクトルを計算してみる

なんとこれだけでVisual Wordが出来てしまいました。もう全て終わったも同然です。仕上げに特徴ベクトルを計算してみます。

features = akaze.detectAndCompute(img, None)[1]

vector = numpy.zeros(len(visual_words))
for f in features:
    vector[((visual_words - f)**2).sum(axis=1).argmin()] += 1

出来ました。心無しかややこしい処理が入っている気がしますが、気のせいです。個々の特徴点について、全てのVisual Wordとの距離を計算して、一番近いものに投票する、というような手順になっています。

ここまでで必要なソースはほぼ出揃ったことになります。理論を調べていると頭がごちゃごちゃしてくるのですが、手順は結構簡単で素敵ですね。

計算した特徴ベクトル同士の距離が近い画像は似ている画像、離れている画像は似ていない画像、ということになります。なので、似ている画像が欲しいときはベクトルが近い画像を探せば良いことになります。

実行してみた

Caltech 101という画像データセットを使わせて頂いて実験をしてみました。入っていた9,145枚の画像を全て学習させてもそこそこの時間で終わりました。結構速い。なお、学習用のデータとテスト入力のデータには同一のものを仕様しました。適当です。

以下の画像を同じものを探してみます。

入力に使ったドットの目立つ太極図

類似度で上位20件の画像が以下の通り。

薄い灰色で縁取られた太極図小さな文字が入った太極図灰色っぽい太極図普通の太極図勾玉2つの写真線が滲んだ太極図歪んだ太極図横に文字が書かれた太極図赤い太極図少しノイズの乗った太極図背景が黄色い太極図点線で書かれた太極図背景が青くて尻尾が長い太極図パンダのぬいぐるみ点が小さめの太極図少し小さい太極図黒い傘のイラスト太極拳のキーホルダー勾玉の詩集のようなもの青と黒、木目柄で縁取られた太極拳

適当に書いたプログラムですが、そこそこの精度が出ているようです。良い感じ。パンダが出ているあたり色で見ているように思えますが、特徴点を使う方法では色は関係無い、はず。多分。

おまけ。ソースコード

以下は軽く高速化を行なったプログラムになります。無尽蔵にキャッシュするようになっているので、そこそこのメモリが必要になるかもしれません。

import functools
import pathlib
import shutil

from sklearn.cluster import MiniBatchKMeans
import cv2
import numpy


input_dir = '/path/to/images/'
output_dir = '/path/to/save/'

akaze = cv2.AKAZE_create()
images = tuple(pathlib.Path(input_dir).glob('*.jpg'))


@functools.lru_cache(maxsize=1024)
def read_image(path, size=(320, 240)):
    img = cv2.imread(str(path))
    if img.shape[0] > img.shape[1]:
        return cv2.resize(img, (size[1], size[1]*img.shape[0]//img.shape[1]))
    else:
        return cv2.resize(img, (size[0]*img.shape[1]//img.shape[0], size[0]))


@functools.lru_cache(maxsize=None)
def load_kps(path):
    return akaze.detectAndCompute(read_image(path), None)[1]


def detect_all(verbose=False):
    for i, path in enumerate(images):
        if verbose:
            print('read {0}/{1}({2:.2%}) {3}'.format(i+1, len(images), (i+1)/len(images), path))

        try:
            yield from load_kps(path)
        except TypeError as e:
            print(e)


def make_visual_words(verbose=False):
    features = numpy.array(tuple(detect_all(verbose=verbose)))
    return MiniBatchKMeans(n_clusters=128, verbose=verbose).fit(features).cluster_centers_


def make_hist(vws, path):
    hist = numpy.zeros(vws.shape[0])
    for kp in load_kps(path):
        hist[((vws - kp)**2).sum(axis=1).argmin()] += 1
    return hist


def find_nears(vws, hist, n=5, verbose=False):
    nears = []
    for i, path in enumerate(images):
        if verbose:
            print('read {0}/{1}({2:.2%}) {3}'.format(i+1, len(images), (i+1)/len(images), path))

        try:
            h = make_hist(vws, path)
        except TypeError:
            continue

        nears.append((((h - hist)**2).sum(), h, path))
        nears.sort(key=lambda x:x[0])
        nears = nears[:n]
    return nears


if __name__ == '__main__':
    vws = make_visual_words(True)

    path = images[0]
    img = read_image(path)
    hist = make_hist(vws, path)

    nears = find_nears(vws, hist, n=20, verbose=True)
    for x in nears:
        print('{0:.2f} - {2}'.format(*x))
        shutil.copy(str(x[2]), '{0}{1:.2f}.jpg'.format(output_dir, x[0]))

参考：