はじめに

こんにちは。Yahoo! JAPAN研究所の日暮です。

今回のAdvent Calendar 2017では、私がYahoo! JAPAN研究所の研究開発において携わる特定物体認識の技術の応用事例として、Yahoo!ラボのアプリ「サイヤスカメラ」を紹介していきたいと思います。

よろしくお願いします。

サイヤスカメラとは

サイヤスカメラとは、Yahoo! JAPAN研究所が開発したラボアプリです。手元にある商品を撮影するだけで、Yahoo!ショッピングから最安値の商品を検索できるiOSアプリです。

商品カテゴリーは、「ドリンク・水・酒」「食料品」「キッチン・日用品」「本・雑誌・コミック」「音楽・映像ソフト」です。商品数は合計で約100万品です。商品を撮影すると、約1.5秒ほどで撮影した商品の結果が表示されます。

App Store （外部サイト）からダウンロードできますのでぜひ試してみてください。

特定物体認識技術について

特定物体認識とは

近年のインターネットショッピングの商品数・店舗数の増大に伴い、スマホなどで撮影した画像から商品を検索することの需要が増加していますが、このようなシステムを実現するためには、画像から類似度が高い物体を検索できる手法が必要です。その一つとして特定物体認識技術が注目されています［1］。

特定物体認識では、データベースから物体そのものを「検索し」物体を特定します。近年盛り上がりを見せているディープラーニングなどによる認識は一般物体認識と呼ばれており、こちらは物体そのものを当てる問題ではなく、カテゴリーや類似商品を当てる問題である点が異なっています。例えば、図1に示すように、一般物体認識ではペットボトルのお茶であるという分類をするというような問題を対象としているのに対し、特定物体認識では商品名を特定するような問題を対象としています。

特定物体認識の仕組みですが、特定物体認識は認識対象とするすべての物体の画像から特徴点座標および局所特徴量を抽出し、データベース（特徴量データベース）化する作業を事前に行います（図2）。データベース構築の手順は次の通りです。

1. 認識対象とする商品画像を用意する
2. 1の全てについて、特徴点座標・局所特徴量を抽出する
3. 2で抽出したデータをデータベース化する

認識時には撮影された画像の局所特徴量を基にデータベースを検索し物体を特定します（図3）。手順は次の通りです。

1. 撮影画像から特徴点座標および局所特徴量を抽出
2. 1の局所特徴量を用いて局所特徴量データベースを検索
3. 検索された商品画像ごとに投票
4. 投票数上位の商品画像について、撮影画像との特徴点座標の照合

大規模特定物体認識の課題とサイヤスカメラのアプローチ

単一の画像から数百の特徴量が抽出されるため、上記の検索の流れで最も時間を要する処理が局所特徴量の検索です。数十万の物体画像を対象とした場合でも、億単位の局所特徴量が抽出されるため、商品数が多い場合には現実的な時間では処理できなくなる課題があります。そこで、われわれは以下4点の施策を行い、大規模特定物体認識においても利用する上で現実的な時間で処理が行えるシステムを考案しました。

1. 局所特徴量データベースの分割
2. 各特徴量データベースにおける特徴量検索の並列化
3. グラフとツリーを組み合わせたインデックス導入
4. 直積量子化手法をインデックスに適用

次の章でそれぞれについて紹介します。

サイヤスカメラのアプローチ紹介

サイヤスカメラの高速検索を実現した技術について紹介します。

1. 局所特徴量データベースの分割

1つ目の工夫点として、商品カテゴリーごとに局所特徴量データベースを分割し1サーバーあたり1データベースとしてシステムを構築しました。これにより、2点の効果を得ることができています。

まず、カテゴリーごとにデータベースのパラメータを最適化することが可能になリました。カテゴリーにより、商品数は少ないが精度を重視するカテゴリー、商品数が多いため検索速度を重視するカテゴリーなどがあります。それぞれについてパラメータを最適化することで、データベースごとに最適な高速化を実現しました。

次に、局所特徴量データベースごとにサーバーが分かれているため、並列でサーバーにリクエストすることで、検索処理の並列化が行えるようになりました。

2. 各特徴量データベースにおける特徴量検索の並列化

図4のように単一の画像ごとに数百の局所特徴量が抽出されます。局所特徴量を抽出し、局所特徴量データベースで検索を行う際に、検索を局所特徴量ごとに並列化して高速化を図りました。

3. グラフとツリーを組み合わせたインデックス導入

局所特徴量は100次元以上の高次元のベクトルデータで表現されるため、局所特徴量データベースは高次元ベクトルデータの検索が行えるものである必要があります。一般的に、ベクトルデータの検索には、k最近傍検索（k-nearest neighbor algorithm, k-NN）などの近傍検索の手法が用いられます。k最近傍検索とは、クエリとしてベクトルデータが与えられた時に、クエリと空間内に点在するベクトルデータとの距離に基づき近い順にk個のデータを検索する手法です。空間内のすべてのデータとの距離を計算すると時間がかかるので、この検索を高速化するためには事前にインデックスを作成することになりますが、1つの特徴量が100次元を超えるような高次元ベクトルデータの検索においては、高速に検索することが大変困難です。サイヤスカメラでは、この高次元ベクトルデータの検索に、Yahoo! JAPAN研究所が所有する高次元ベクトルデータの近傍検索技術を実装した”NGT”というソフトウエアを利用しています。

NGTは、グラフとツリーを組み合わせたインデックスを用いる近傍検索手法を採用しています。図5にインデックスの構造を示します。図のようにツリーの上から下へたどる（青の矢印）ことでクエリの近傍候補となるデータを取得した後に、そこからグラフをたどる（緑の矢印）ことで網羅的にデータを探索します。詳細は過去のtechblogの記事、または、参考文献［2］をご覧下さい。

また、NGTのダウンロードは以下のURLから行えます。OSSとして公開されていますので、ぜひこちらもご利用下さい。

• NGT紹介ページ
• GitHub（外部サイト）

4. 直積量子化手法をインデックスに適用

前述の通り、1枚の画像データあたり数百の局所特徴量が抽出されるため、数十万画像から億単位の特徴量が抽出されます。局所特徴量データベースはこれらの大量の高次元ベクトルデータをデータベース化する必要があります。NGTを利用することで、高次元のベクトルデータを高速検索できるようになりましたが、サイヤスカメラのように億単位の高次元ベクトルデータをインデックスに登録する場合には、さらなる高速化の工夫が必要となりました。今回、それを解決するために高次元空間を複数の低次元空間に分割する量子化を行いました（図6）。量子化の手法には直積量子化を採用しています。直積量子化の詳細な手法については、参考文献［3］をご覧下さい。

サイヤスカメラのシステム構成

サイヤスカメラのシステム構成を図7に示します。

図7中の商品認識サーバーは大規模特定物体認識機能を提供するサーバーです。商品データベースサーバーは商品名などの商品情報を特徴量データベースと共通の商品ID体系で関連付けたデータベースです。フロントエンドサーバーは商品認識サーバーと商品データベースサーバーへのリクエストをまとめる機能を有したウェブAPIです。iOSアプリは、画像の撮影や認識の実行などを行います。

なお、前述のとおり認識処理時間および精度向上のために特徴量データベースを分割しているため、それに対応して商品認識サーバーは複数用意します。

商品認識時の流れは次のとおりです。

1. iOSアプリで商品を撮影する
2. iOSアプリがフロントエンドサーバーに商品画像をリクエスト
3. フロントエンドサーバーは、全ての商品認識サーバーにリクエスト
4. 商品認識サーバーは特定物体認識を実施し、認識された商品の商品IDをフロントエンドサーバーに返却
5. フロントエンドサーバーは4.で得られた全ての商品IDを商品データベースへリクエスト
6. 商品データベースは商品情報をフロントエンドサーバーに返却
7. フロントエンドサーバーは得られた認識結果をまとめてiOSアプリに返却
8. iOSアプリは認識結果をユーザーに表示する

サイヤスカメラのデータ紹介

サイヤスカメラに登録されているデータは、ヤフーショッピングに出品されている商品内で、今回、特定物体認識の特性から形状が変化せず、平面（立体物でも正面がほぼ一意に決まる）物を対象として、ドリンク・水・お酒、食料品の一部、キッチン・日用品の一部、本・雑誌・コミック、そして音楽ソフト・映像ソフトの5カテゴリーを選定し利用しています。それぞれの件数と得られた局所特徴量数は表1の通りです。対象の商品について、画像（画像サイズ＝250または400ピクセル）と商品情報を取得し、特徴量データベースおよび商品データベースを作成したものが現在公開されているサイヤスカメラで利用されています。

商品認識のデモ

では、サイヤスカメラで実際に商品を撮影して認識させてみましょう。

以下がアプリの認識を実際に行う画面です。アプリの下部の赤いボタンを押すと、認識を開始します。アプリに商品をかざして、商品を認識するとカメラ部分に商品が自動的表示されます。

認識した商品をクリックすると、商品の最安値を検索して結果を表示します。

また、図10は一例として、日本酒「獺祭」を認識させてみた例です。獺祭のラベルを認識して商品が検索されていることがわかると思います。ただし、こちらの結果には日本酒だけでなく書籍も表示されています。このようなカテゴリー違いは現状のアプローチでは起きてしまうことが分かっており、今後の課題となっています。ディープラーニングなどを利用したカテゴリー分類の仕組みと特定物体認識を組み合わせることで解決できるのではないかと考えています。

おわりに

本投稿では、ヤフーショッピングの商品検索アプリ “サイヤスカメラ” を事例として、（1）特徴量データベースの分割、（2）検索の並列化、（3）グラフインデックスの導入、および （4）直積量子化の導入により億単位の局所特徴量を用いた商品認識システム構築について紹介しました。本システムにより、スマートフォンで撮影された商品画像から実用的な時間内での商品認識が可能になりました。このような新しい技術を利用して、お客様のショッピング体験を向上できるようにこれからも工夫していきたいと考えています。

最後に、ラボアプリ、サイヤスカメラもぜひご利用下さい！

参考文献

• ［1］ Sivic, J. and Zisserman, A., “Video Google: A text retrieval approach to object matching in videos” , Proc. of IEEE Inter. Conf. on Computer Vision, pp.1470-1477, 2008
• ［2］ Iwasaki, M., “Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search”, Proc. of Inter. Conf. on Similarity Search and Applications, pp. 20-33, 2016.
• ［3］ Jegou, H., Douze, M. and Schmid, C., “Product quantization for nearest neighbor search”, IEEE trans. on pattern analysis and machine intelligence, 33（1）, pp.117-128, 2011.