まだプログラマーですが何か?

プログラマーネタとアスリートネタ中心。たまに作成したウェブサービス関連の話も http://twitter.com/dotnsf

タグ:similarity

IBM Watson から提供されている Visual Recognition(画像認識) API の1つで、ずっとベータ版として提供されていた Similarity Search (類似画像検索)API が正式公開となる前にサービス終了となりました:
Visual Recognition API – Similarity Search Update


非常に簡単に使うことができて、機能も便利で、ベータ版と知りつつ自分もいくつかのプロダクトの中で使ったり、そのサービスをブログやイベント等で紹介したりもしていました。詳しい経緯はわかりませんが、サービスが終了になったことは非常に残念でした。

実は以前にも同じようなことがありました。いわゆる「トレードオフ分析」を行う機能を API として提供していた Watson Tradeoff Analytics API は 2017/05/11 を以ってサービスの追加ができなくなりました(作成済みのサービスは 2018/04 まで使えます)。この API はちょうど自分がこの分析手法を勉強し始めた頃にサービス終了がアナウンスされ、とても残念でした。

この API に関してはちょうどトレードオフ分析を勉強しはじめた当初だったこともあり、自分でもトレードオフアルゴリズムを理解し始めた頃でもありました。で、こんな互換 API を作って公開したのでした:
Yet Another Watson Tradeoff Analytics API


さて話を元に戻して今回の Similarity Search API のサービス終了です。これも非常に残念なことでした。トレードオフ分析の時と異なるのは自分が画像検索アルゴリズムについて勉強していたわけではなく、互換 API を作るにはちとハードルが高かったということでした。

が、調べてみると画像検索にはいくつかの考え方やアルゴリズム、それらごとの向き/不向きがあって、比較的簡単に実現する方法もないわけではない、ということがわかりました。その1つがカラーヒストグラムを使った方法でした:
類似画像検索とカラーヒストグラム


オリジナルの Similarity Search API がこのアルゴリズムを使っていたかどうかは分からない(おそらく使っていない)のですが、とりあえずこのアルゴリズムによって「画像を学習する」&「学習した画像の中から類似した画像を見つける」という最低限必要な機能は実装できそうだ、と思えるようになりました。というわけで今回も互換 API の開発に挑戦してみたのでした。そしてとりあえず出来上がったものをオープンソース化したのがこちらです:
YASS(Yet Another Similarity Search)

2017092400



実装の対象としたのは Watson API Explorer の Visual Recognition API のページを参考に "Collections" カテゴリと "collection images" カテゴリにある全 12 API 、そしてオリジナルにはなかった「学習画像のバイナリを取得する API 」を合わせた 13 API です。オリジナル API のパラメータについては元のものとほぼ互換性を付けたつもりです。また新しい API のパラメータは URL 部分以外にないので特に説明は不要と思っています。なお「ほぼ互換性」という表現を使いましたが、互換性のない箇所は以下のとおりです:
  • オリジナル API の実行時に指定が必要だった API Key を廃止しました。実行時に API Key の指定は不要です。代わりに(必要であれば)Basic 認証をかけることができるようにしました。
  • オリジナル API の実行時に指定が必要だった version パラメータを廃止しました。実行時に version の指定は不要です。正確には version = '2016-05-20' の仕様に従ったものを実装しています。
  • オリジナル API の制限事項であった「1コレクションに対して 1,000,000 画像まで」という制約はありません。ただし画像バイナリごと Cloudant に格納されるため、Cloudant の容量にはお気をつけください。
  • 学習させた画像のバイナリ(画像そのもの)を取得するための API : GET /v3/collections/{collection_id}/images/{image_id}/binary を新たに追加しました。collection_id と image_id を指定して実行すると Content-Type と合わせて画像バイナリが API サーバーから返されます。
  • API 実行後の HTTP レスポンスには status という属性を含めるようにしました(このため、実行結果のフォーマットには互換性がありません)。status = true の場合は成功、false の場合はなんらかのエラーが発生したことを意味しています。

【前提環境】
この互換 API は Node.js で記述されています。従って API サーバーには Node.js のランタイム(と npm)がインストールされている必要があります。また画像や検索に必要な情報は Cloudant データベースに格納されます。2017/Sep/24 現在の仕様では IBM Bluemix 上の Cloudant を使う前提で記述されているため、IBM Bluemix のアカウントを取得して、Cloudant サービスを1つインスタンス化し、その username と password を用意してください。


【インストール方法】
(1) 上記サイトから git clone するか、zip download &展開して、ソースコードを取得します。
(2) ソースコードの settings.js を編集します(青字はコメント。最低限編集が必要になるのは上2つ):
exports.cloudant_username = '(Cloudant Username)';  // Cloudant の username(必須)
exports.cloudant_password = '(Cloudant Password)';  // Cloudant の password(必須)
exports.cloudant_db_prefix = 'yass_';               // Cloudant に作成するデータベース名の prefix(必須だが変更しなくてもよい)
exports.basic_username = 'username';                // Basic 認証をかける場合の username(''にした場合は Basic 認証なし)
exports.basic_password = 'password';                // Basic 認証をかける場合の password(''にした場合は Basic 認証なし)
exports.api_base_path = '/v3';                      // API の基本パス(''でもよいし、変更してもしなくても良い)
(3) npm install を実行
例) $ npm install

(4) Node.js で app.js を実行
例) $ node app.js

(5) curl やアプリケーションから API を利用
例) $ curl -XGET 'http://localhost:6001/v3/collections'


【システム構成】
Similarity Search API の "Collection" に相当する部分を「Cloudant のデータベース」に、画像データに相当する部分を「Cloudant のドキュメント」にみなして格納するようにしました。ドキュメントには attachment として画像ファイルそのものを格納すると同時に、類似検索ができるよう正規化されたカラーヒストグラム情報や、画像データの metadata を合わせて格納するようにしています:
2017092401


類似検索 API(POST /v3/collections/{collection_id}/find_similar)を実行した時の挙動はまず Collection から全画像を取り出し(つまり Collection に該当する Cloudant データベースから全ドキュメントを取り出し)、カラーヒストグラム情報を1つずつ取り出しては色の類似性を調べて、その上位何件かを返すというアルゴリズムにしています。必ずしも効率のよい検索方法ではないと理解していますが、カラーヒストグラムの比較を効率よく行う方法が思いついていないので、現状はこの方法にしています:
2017092402



【所感】
カラーヒストグラムアルゴリズムを採用したこの互換 API の検索精度はオリジナルのものとは同じではない可能性が高いと思っています(色が重要、どちらかというとイラストよりも写真の類似性に向いている、など)。あまり期待通りでなかったとしてもオープンソース化されているので該当部分のアルゴリズムを変更する、という方法もあると思っています(ちなみに MIT ライセンスで公開してます)。

あと、IBM Watson の互換 API を作ったのは今回が2回目ですが、このように「はじめから仕様が決まっている(仕様が変わらないことも決まっている) API を作る」のは楽です。ある程度、仕様として完成されているが故の安心感もありますし、何度も使っていた API なので動作確認も楽でした。実際、今回の互換 API は休暇を利用して(学習部分も含めて)ほぼ3日で作り上げました(「3日で作れる程度のアルゴリズム実装」と言えなくもないと思います)。


 

類似画像検索の API というか機能というか、、を作っています。いずれはオープンソース化を念頭に入れているので、その成果もいずれ公開するつもりですが、今自分が作ろうとしている仕組みについて調べたことをまとめる目的で公開します。


類似画像検索では「ある2つの画像が似ているかどうか?」を数値で判断し、「こっちの画像よりもあっちの画像の方がより似ている」、「この画像に似ているのはこれとこれとこれと・・」みたいな識別ができるようにする必要があります。

その判断アルゴリズムにはいくつかの方法(基準)があります。おおまかに言うと「色合いが似てる」とか「輪郭が似てる」とかです。以下で紹介するカラーヒストグラムはそのひとつで、「同じような色合いの画像を似ていると判断する」方法です:
Color Histogram - Wikipedia


※この方法は「同じような色」の画像を「類似している」と判断します。輪郭や形を意識しているわけではありません。したがってあるカラー画像のモノクロ画像はあまり似ていない、という判断になると思います。また元の画像を中心から180度回転させたもの(上下逆さまにしたもの)は使っている色の構成自体は同じものなので「似ている」と判断することになります。


例えば横幅 W ピクセル、縦幅 H ピクセルの画像があったとします。ピクセル総数は W * H です。この ( W * H ) 個のピクセル毎に RGB 値を取得して、RGB の出現頻度のヒストグラム(階級度数分布)を作ります。ただし通常の RGB 値は #RRGGBB (RR, GG, BB は全て16進2桁の数)と表されるように R, G, B 各色毎に 256 種類の値を持ちますので、そのまま出現頻度を求めようとすると 256 * 256 * 256 = 16777216 種類もの出現パターンがあります。これだとカラーヒストグラムを作りにくい(傾向が出にくい)し、16777216 次元のベクトル演算が必要になるためちと面倒です。そこで各色毎の値を 4 種類として(つまり RR, GG, BB の各上位 2 ビットの値のみ使うように減色して)、4 * 4 * 4 = 64 次元のカラーヒストグラムを作ることにします。

あるピクセル ( x, y ) の RGB 値が #RRGGB という値であったとして、RR, GG, BB それぞれの上位2ビットを取得した結果が rr, gg, bb であったとします。このピクセルのカラー値 c(x,y) は 16 * rr + 4 * gg + bb で表すことができ、この値は 0 から 63 までの 64 種類の値を取り得ます。

この c(x,y) を全ての x と y(0 <= x < W, 0 <= y < H) について計算し、求めた c(x,y) の分布結果でカラーヒストグラムを作成します。例えばこの画像(314 * 340):
baseball


のカラーヒストグラム(分布表)を計算すると、以下のようになりました:
2017092001


カラーヒストグラムの見方は横軸が上記方法で計算したカラー値、縦軸がその出現個数です。一番左の数はカラー値が0、つまり「黒」の数で、一番右は「白」の数です。どうしてもこの2つの値は多くなりがちであると思いますが、それ以外にも点々とした箇所があり、これが画像の(色合いの)特徴を表しているわけです。

もう1つ、こちらの画像(340 * 340):
basketball



で同じカラーヒストグラムを作ると、以下のようになります:
2017092001


このようにしてあらかじめ画像を登録する際にカラーヒストグラムの計算結果を合わせて記憶するようにします。そして類似画像検索時にはカラーヒストグラムの近いものを探す、というアルゴリズムで実装できます。例えばこちらの画像(340 * 340)が上記2つの画像のどちらに似ているか、という識別をしてみます:
snooker


この画像のカラーヒストグラムはこのようになりました:
2017092002


簡単にいうと、このヒストグラムだけを比較して、「ヒストグラムはどの画像に近いか?」を判断することになります。もちろん画像のサイズは全て同じではないのでそこは正規化する必要もありますが、ロジックそのものはこれで実現できそうです。


もちろん「このロジックで精度の高い類似画像検索が実現できるか?」は別に考慮する必要があります。たとえば先程の上限逆さまにしたこの画像:
snooker


これを「元の画像と似ている」と判断すべきか、「似ていない」と判断すべきかはケース・バイ・ケースだと思っています(似ていると判断したいケースもあれば、似ていないと判断したいケースもある)。このカラーヒストグラムを使ったアルゴリズムの場合は回転結果は全く同じカラーヒストグラムを生成することになるので「似ている」と判断したい時に有効なアルゴリズムの1つと言えますが、「似ていない」と判断させたいのであれば輪郭などを元に判断するアルゴリズムを採用する必要がある、という意味です。

自前で類似画像検索を作成しようとしている人の参考になれば。


IBM Bluemix を通じて提供されている Watson API の1つ Visual Recognition(画像認識) API に「類似イメージ検索」というベータ版の新機能が追加されました:
https://new-console.ng.bluemix.net/catalog/services/visual-recognition/


2016101101


この API はその名の通り、「ある画像に似た画像を(あらかじめ登録しておいた画像群の中から)探す」というものです。個々の REST API としては画像の登録や削除、そして類似検索といった機能が用意されており、それらを組み合わせて実装することになります。また他の Watson API 同様、検索した結果に対してはスコアという検索結果に対する自信の数値根拠が合わせて返される、という特徴があります。


またこの類似画像検索 API のデモサイトも公開されています。選択した画像に似た画像が表示される、というものです。一度使ってみると、どういったことが可能になるのか、というイメージが付きやすくなると思います:
https://similarity-search-demo.mybluemix.net/

2016101201


このブログは公私混同を売りにしている(笑)こともあるので、実際に自分のサービスを使って試してみた様子を以下に紹介します。自分の場合は(お約束ですが)マンホールマップの画像を使わせていただきました。複数の種類のマンホール画像をあらかじめ登録しておいて、後から登録していないマンホール画像を指定して類似検索した時に同じ絵柄のマンホールを見つけることができるかどうか!? という挑戦です。

実はこの挑戦はかなりハードルの高い挑戦でもあります。なぜなら「単にマンホールとして認識」されてしまうと、登録画像は全てマンホールなので「似た絵柄のマンホール」を探すことができないと思われるからです。またマンホールの外側にある部分の類似性は無視してほしいわけですが、その辺りの所、ワトソンはどうなのよ!? ということを確認するための実験的要素の強い作業です。

なおこちらのページのマンホール画像はあらかじめ登録しておく画像の1つとしています:
2016101202


詳しくは API Reference を参照いただきたいのですが、あらかじめ画像を登録する際には画像データに加えて、JSON 形式のメタデータファイルを用意する必要があります。このメタデータに登録された内容は検索結果に含まれて返されることになるものです。そのため ID や作成日時、作成ユーザーといった情報をこのメタデータに加えておくと、画像検索した結果から作成ユーザー情報まで取り出す、ということも可能になります。

今回は登録するデータとしてこの画像と、



画像に加えて、こんな内容のメタデータを用意しておきました:
{
  "id":120002,
  "username":"morimo_t",
  "created":"2010-08-17 22:03:26",
  "text":"川崎市の色蓋。よく通る道路だったのにはじめて気がつきました。",
  "address":"神奈川県川崎市幸区堀川町",
  "lat":35.53229904174805,
  "lng":139.697998046875,
  "nice":5
}

↑細かい説明は省きますが、画像検索した結果にこの画像が含まれていた場合に、これらのメタデータと合わせて結果が取得できる、というためのものです(なのでメタデータが不要であれば空オブジェクトでも構いません)。このように画像とメタデータの組み合わせを登録する画像全てに対して用意しておきます。

実際に画像を登録する前にいくつか準備が必要です。まず当たりまえですが、IBM Bluemix にログインし、Visual Recognition サービスを追加しておきます:
2016101203


サービス追加後、「サービス資格情報」の「資格情報の表示」を選択して、認証情報の "api_key" の値を確認しておいてください(この後で使います):
2016101204


ここからは curl を使って REST API を実行するので、Linux か Mac のユーザーはターミナルを開いてください。Windows ユーザーの場合、curl は別途インストールする必要があります。以下のサイトから環境にあった Windows 用 curl をダウンロードし、インストールしてください:
https://curl.haxx.se/download.html

2016101205


curl コマンドを使う準備ができたら実際に REST API を実行してみましょう。画像を登録するにはまず入れ物(「コレクション」といいます)を用意します。ちなみに類似画像検索はこのコレクション単位で実行して、回答を取得することになります。上記デモサイトのようにショッピング用の商品画像から類似画像を探す、という使い方であれば商品の画像を登録するコレクションを作って、そこに商品画像をまとめて登録して検索する、という使い方をすることになります。

今回は「類似マンホール検索」が目的なので、マンホール画像だけを登録するコレクションをあらかじめ作っておくことにします(そしてそこにはマンホール画像以外は登録しないようにします)。新たにコレクションを作成するにはこの REST API を実行します:
# curl -X POST -F "name=XXXXXXXX" "https://gateway-a.watsonplatform.net/visual-recgnition/api/v3/collections?api_key=(apy_key)&version=2016-05-20"

メソッドは POST で、マルチパートフォームデータとして name パラメータでコレクションの名前(上の例では "XXXXXXXX")を指定します。また URL パラメータで Visual Recognition サービスを参照して確認した api_key と、version("2016-05-20")を指定して実行します。

この実行が成功すると、指定した名前のコレクションが作成され、以下のような実行結果 JSON が返ってきます:
{
  "collection_id": "XXXXXXXX_xxxxxx",
  "name": "XXXXXXXX",
  "status": "available",
  "created": "2016-10-11T05:58:47.129Z",
  "images": 0,
  "capacity": 1000000
}

"name" に指定したコレクション名が入っていて、その名称に "_xxxxxx" という形式が付いた "collection_id" が得られているはずです。この後からはこの collection_id を使って API を実行するので、この値をメモしておきましょう。またこのコレクションには現在 0 枚の画像が登録されており("images" の値)、最大で 1000000 枚の画像が登録できる、という状態になっているようです。

では入れ物ができたので、この入れ物に画像を登録します。画像ファイル名が image.png、対応するメタファイル名が image.json である場合、以下の API を実行します:
# curl -X POST -F "image_file=@image.png" -F "metadata=@image.json" "https://gateway-a.watsonplatform.net/visual-recgnition/api/v3/collections/XXXXXXXX_xxxxxx/images?api_key=(apy_key)&version=2016-05-20"

マルチパートフォームデータで画像ファイルとメタデータファイルを POST メソッドで送り、URL パラメータの中で collection_id を指定しています。この API の実行が成功すると、このような JSON が返ってきます:
{
  "images": [
    {
      "image_id": "mmmmmm",
      "image_file": "image.png",
      "created": "2016-10-11T16:12:16.435Z",
      "metadata": {
        "id":120002,
        "username":"morimo_t",
        "created":"2010-08-17 22:03:26",
        "text":"川崎市の色蓋。よく通る道路だったのにはじめて気がつきました。",
        "address":"神奈川県川崎市幸区堀川町",
        "lat":35.53229904174805,
        "lng":139.697998046875,
        "nice":5
      }
    }
  ],
  "images_processed": 1
}

実行結果として image_id などが生成されています。また metadata の中身は指定してメタデータファイルの中身になっているはずです。

この時点でコレクションの状態を確認してみることにします。コレクションの状態を確認するにはこの APIを実行します:
# curl "https://gateway-a.watsonplatform.net/visual-recgnition/api/v3/collections/XXXXXXXX_xxxxxx?api_key=(apy_key)&version=2016-05-20"

実行が成功すると、以下のような JSON が返ってきます。画像が1つ登録されたので "images" の値が 0 から 1 に変化しています:
{
  "collection_id": "XXXXXXXX_xxxxxx",
  "name": "XXXXXXXX",
  "status": "available",
  "created": "2016-10-11T05:58:47.129Z",
  "images": 1,
  "capacity": 1000000
}

こんな調子であらかじめ登録しておく画像(=検索対象となる画像)をすべて登録しておきます。なお、コレクションに追加できる画像は(API Reference によると) 2MB 以内にするべきとのこと。また1つのコレクションに 1000000 (100万)画像まで登録できることになっていますが、1つのファイルを登録するのに仮に1秒かかるとすると、100 万画像で 100 万秒、つまりノンストップで行っても約 11.5 日かかる計算になります。派手に使う場合は準備に2週間~程度かかる、という心づもりが必要になりますね。

全ての画像が登録されたら、最後に類似画像認識を実行してみます。今回はこの画像を検索してみました(この画像はコレクションには登録していません):



↑上記で紹介した登録画像と同じ絵柄のマンホール画像です。この画像を search.png として保存し、以下の REST API を実行します:
# curl -X POST -F "image_file=@search.png" "https://gateway-a.watsonplatform.net/visual-recgnition/api/v3/collections/XXXXXXXX_xxxxxx/find_similar?api_key=(apy_key)&version=2016-05-20&limit=5"

collection_id を指定して、マルチパートフォームデータが画像ファイルを POST 送信しています。またこの例では URL パラメータに limit=5 を指定して、類似度の上位5つまでを取得するように指示しています。

この API が正しく実行されると、以下のような結果が取得できます:
{
  "image_file": "5137462154683827112.png",
  "similar_images": [
    {
      "image_id": "2f98c6",
      "image_file": "120002.png",
      "score": 0.7548828,
      "created": "2016-10-11T15:22:25.824Z",
      "metadata": {
        "address": "神奈川県川崎市幸区堀川町",
        "created": "2010-08-17 22:03:26",
        "id": 120002,
        "lat": 35.53229904174805,
        "lng": 139.697998046875,
        "nice": 5,
        "text": "川崎市の色蓋。よく通る道路だったのにはじめて気がつきました。€‚",
        "username": "morimo_t"
      }
    },
    {
      "image_id": "d20e86",
      "image_file": "804002.png",
      "score": 0.7416992,
      "created": "2016-10-11T15:59:02.442Z",
      "metadata": {
        "id": 804002,
           :
           :
      }
    },
    {
      "image_id": "b6f1e7",
      "image_file": "1594034.png",
      "score": 0.74121094,
      "created": "2016-10-11T15:17:22.733Z",
      "metadata": {
        "id": 1.594034e+06,
           :
           :
      }
    },
    {
      "image_id": "f0bb1f",
      "image_file": "1888484723171738767.png",
      "score": 0.73828125,
      "created": "2016-10-11T15:31:14.768Z",
      "metadata": {
        "id": 1.888484723171739e+18,
           :
           :
      }
    },
    {
      "image_id": "9f72ed",
      "image_file": "90003.png",
      "score": 0.72998047,
      "created": "2016-10-11T15:31:21.935Z",
      "metadata": {
        "id": 90003,
           :
           :
      }
    }
  ],
  "images_processed": 1
}

この形式だとわかりにくいので、実行結果を表&画像にしてみました:
#画像スコア
10.7548828
20.7416992
30.74121094
40.73828125
50.72998047


なんとも評価の難しい結果になりました。まず1位は期待通りに、事前に登録しておいた同じ絵柄のマンホールを取得することができました!これは素晴らしい!! そして問題は2位以下です。これらはマンホールの絵柄としては明らかに異なり、「類似画像」としてはふさわしくないのですが、そのスコアが1位の画像と大差ない、という結果になりました。

まず今回登録した画像には正解(というか、同じ絵柄のマンホール)が1つしかないので、それが1位になってることは評価に値すると思っています。ただ間違いである2位との差がほとんどないというのも実は厄介で、「似た画像はこの1つだけです」という判断をさせたり、正解が1個もないような検索時に「似た画像はありません」という判断をするのが難しくなってしまうのでした。うーむ・・・

一方で、今回は 500 枚のマンホール画像を事前に登録したのですが、この枚数が少なすぎた可能性はありますね。

とはいえ、最初に触れているように、今回の検証は「マンホールの絵柄の類似性を確認できるか?」というかなりハードルの高い検証をしたつもりでしたが、ある程度は判断できているようにも見えます。今後は登録画像枚数も増やした上で再度色んなパターンで検証することになると思ってます。



なお、この類似画像検索 API の詳細については API Reference を参照ください:
http://www.ibm.com/watson/developercloud/visual-recognition/api/v3/#collections


このページのトップヘ