(57)【特許請求の範囲】
【請求項１】
リファレンス画像から抽出されたリファレンスベクトルの集合から、クエリ画像のクエリベクトルに類似したベクトルを検索する検索装置であって、
リファレンス画像について、リスト識別子LIDn毎に、リファレンス画像識別子と、粗量子化及び直積量子化を用いて符号化した画像特徴符号との複数の組を対応付けた転置インデックスを登録する転置インデックス登録手段と、
クエリ画像についてリスト識別子LIDnと画像特徴符号の複数の組を入力する検索手段と
を有し、
前記検索手段は、
前記クエリ画像の各リスト識別子と画像特徴符号の組について、当該リスト識別子に対応する転置インデックスのリストを取得し、
前記クエリ画像の画像特徴符号と、取得したリスト中のリファレンス画像の各画像特徴符号との間の距離を算出し、
前記距離が短いほど高くなるスコア値を算出し、
当該リファレンス画像毎に該スコア値を累積加算し、
前記スコア値が最も高くなるリファレンス画像を検索結果として出力する
ことを特徴とする検索装置。
【請求項２】
前記検索手段は、距離が短い上位所定件数(K)に相当するスコア値のみを当該リファレンス画像に累積加算することを特徴とする請求項１に記載の検索装置。
【請求項３】
前記検索手段について、前記上位所定件数(K)は、予め設定された固定数か、又は、予め設定された距離に関する閾値THに基づいて当該距離が閾値TH以下となる距離の数であることを特徴とする請求項２に記載の検索装置。
【請求項４】
前記検索手段について、前記上位所定件数(K)のうちi件目に対応する加算スコアは、
（１）K番目の距離の二乗からi番目の距離の二乗を引いたものとするか、
（２）k番目の距離の二乗とi番目の距離の二乗の比から1を引いたものとするか、
（３）k番目の距離とi番目の距離の比の二乗から1を引いたものとするか、又は、
（４）k番目の距離とi番目の距離の比から1を引いたものの二乗とする
ことを特徴とする請求項３に記載の検索装置。
【請求項５】
前記画像特徴符号は、前記直積量子化のための残差コードブックの代表ベクトルの識別子の列で表されており、
前記画像特徴符号間の距離は、第１の識別子列ｘ及び第２の識別子列ｙについて、第１の識別子列ｘのl番目の識別子に対応する代表ベクトルと第２の識別子列ｙのl番目の識別子に対応する代表ベクトルとの間の各距離を1≦l≦Lについて総和したものである
ことを特徴とする請求項１から４のいずれか１項に記載の検索装置。
【請求項６】
前記画像特徴符号間の距離は、前記残差コードブックにおける２つの第１の識別子列ｘ及び第２の識別子列ｙの総当りの組み合わせについて、第１の識別子列ｘの代表ベクトルと第２の識別子列ｙの代表ベクトルとの間の距離を登録したテーブルＴを用いて算出される
ことを特徴とする請求項５に記載の検索装置。
【請求項７】
クエリ画像及びリファレンス画像から局所特徴のクエリベクトル及びリファレンスベクトルを抽出する局所特徴抽出手段と、
前記局所特徴抽出手段から出力されたクエリベクトル及びリファレンスベクトルに対して、コードブックを用いて第１階層で粗量子化し、その量子化誤差を残差コードブックを用いて第２階層で直積量子化し、当該クエリ画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を前記検索手段へ出力し、当該リファレンス画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を前記転置インデックス登録手段へ出力する符号化手段と
を有することを特徴とする請求項１から６のいずれか１項に記載の検索装置。
【請求項８】
前記局所特徴抽出手段は、ＯＲＢ(Oriented FAST and Rotated BRIEF)又はＦＲＥＡＫ(Fast Retina Keypoint)に基づくバイナリ局所特徴ベクトルを抽出し、
前記コードブックは、前記バイナリ局所特徴ベクトルのリファレンスベクトルを、K-Medoids法を用いてクラスタリングしたものであり、
前記粗量子化は、前記バイナリ局所特徴ベクトルのクエリベクトルを、前記コードブック内の最も類似したバイナリ代表ベクトルに割り当て、
前記量子化誤差は、バイナリ特徴ベクトルと、そのバイナリ特徴ベクトルに最も類似したバイナリ代表ベクトルとの排他的論理和によって算出される
ことを特徴とする請求項７に記載の検索装置。
【請求項９】
請求項１から６のいずれか１項に記載の検索装置として機能するサーバと、クエリ画像を入力する端末とを有するシステムであって、
前記端末は、
クエリ画像から局所特徴のクエリベクトルを抽出する局所特徴抽出手段と、
前記局所特徴抽出手段から出力されたクエリベクトルに対して、コードブックを用いて第１階層で粗量子化し、その量子化誤差を残差コードブックを用いて第２階層で直積量子化し、当該クエリ画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を出力する符号化手段と、
前記クエリ画像におけるリスト識別子LIDn毎の画像特徴符号の複数の組を、前記サーバへ送信するクエリ符号送信手段と、
前記サーバから、検索された１つ以上のリファレンス画像を受信し且つ出力するリファレンス画像受信手段と
を有し、
前記サーバは、
リファレンス画像から局所特徴のリファレンスベクトルを抽出する局所特徴抽出手段と、
前記局所特徴抽出手段から出力されたリファレンスベクトルに対して、コードブックを用いて第１階層で粗量子化し、その量子化誤差を残差コードブックを用いて第２階層で直積量子化し、当該リファレンス画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を、前記転置インデックス登録手段へ出力する符号化手段と、
前記端末から、前記クエリ画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を受信するクエリ符号受信手段と、
前記スコア値が最も高くなるリファレンス画像を検索結果として送信するリファレンス画像送信手段と
を有することを特徴とするシステム。
【請求項１０】
前記局所特徴抽出手段は、ＯＲＢ又はＦＲＥＡＫに基づくバイナリ局所特徴ベクトルを抽出し、
前記コードブックは、前記バイナリ局所特徴ベクトルのリファレンスベクトルを、K-Medoids法を用いてクラスタリングしたものであり、
前記粗量子化は、前記バイナリ局所特徴ベクトルのクエリベクトルと、前記コードブック内のバイナリ代表ベクトルとを排他的論理和によって算出する
ことを特徴とする請求項９に記載のシステム。
【請求項１１】
装置に搭載されたコンピュータを、リファレンス画像から抽出されたリファレンスベクトルの集合から、クエリ画像のクエリベクトルに類似したベクトルを検索するように機能させるプログラムであって、
リファレンス画像について、リスト識別子LIDn毎に、リファレンス画像識別子と、粗量子化及び直積量子化を用いて符号化した画像特徴符号との複数の組を対応付けた転置インデックスを登録する転置インデックス登録手段と、
クエリ画像についてリスト識別子LIDnと画像特徴符号の複数の組を入力する検索手段と
を有し、
前記検索手段は、
前記クエリ画像の各リスト識別子と画像特徴符号の組について、当該リスト識別子に対応する転置インデックスのリストを取得し、
前記クエリ画像の画像特徴符号と、取得したリスト中のリファレンス画像の各画像特徴符号との間の距離を算出し、
前記距離が短いほど高くなるスコア値を算出し、
当該リファレンス画像毎に該スコア値を累積加算し、
前記スコア値が最も高くなるリファレンス画像を検索結果として出力する
ようにコンピュータを機能させることを特徴とするプログラム。
【請求項１２】
装置を用いて、リファレンス画像から抽出されたリファレンスベクトルの集合から、クエリ画像のクエリベクトルに類似したベクトルを検索する検索方法であって、
リファレンス画像について、リスト識別子LIDn毎に、リファレンス画像識別子と、粗量子化及び直積量子化を用いて符号化した画像特徴符号との複数の組を対応付けた転置インデックスを登録する転置インデックス登録部を有し、
クエリ画像についてリスト識別子LIDnと画像特徴符号の複数の組を入力する第１のステップと、
前記クエリ画像の各リスト識別子と画像特徴符号の組について、当該リスト識別子に対応する転置インデックスのリストを取得する第２のステップと、
前記クエリ画像の画像特徴符号と、取得したリスト中のリファレンス画像の各画像特徴符号との間の距離を算出する第３のステップと、
前記距離が短いほど高くなるスコア値を算出する第４のステップと、
当該リファレンス画像毎に該スコア値を累積加算する第５のステップと、
前記スコア値が最も高くなるリファレンス画像を検索結果として出力する第６のステップと
を有することを特徴とする検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バイナリ局所特徴ベクトルを用いて画像を検索する技術に関する。
【背景技術】
【０００２】
近年、局所特徴点に基づいた画像認識や検索技術が注目されている。物体認識に用いる特徴ベクトルの抽出アルゴリズムとしては、回転やスケールの変化にロバストな、例えばＳＩＦＴ(Scale-Invariant Feature Transform)（例えば非特許文献１参照）やＳＵＲＦ(Speeded Up Robust Features)が用いられる。例えばＳＩＦＴの場合、１枚の画像からは１２８次元の特徴ベクトルの集合が抽出される。ＳＩＦＴとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。一方で、ＳＵＲＦの場合、ＳＩＦＴよりも高速処理が可能であって、１枚の画像から６４次元の特徴ベクトルの集合が抽出される。ＳＩＦＴは、処理コストが高く且つリアルタイムマッチングが困難であるのに対し、ＳＵＲＦは、積分画像を利用することによって処理を高速化している。
【０００３】
従来、局所特徴量を用いた類似画像検索の枠組みは、「Bag-of-Visual Words」（又はBag-of-Features、Bag-of-Keypoints）と称される（例えば非特許文献１参照）。この技術によれば、Bag-of-Wordsモデル及び転置インデックスを用いた文章の検索方法を、類似画像の検索に適用したものである。Bag-of-Wordsは、文章を１つの単語の頻度により定義される特徴ベクトルで表現し、文章集合に基づいて予め導出されたＩＤＦ(Inverse Document Frequency)を単語の重みとして文章間の類似度を導出する枠組みである。これに対し、Bag-of-Visual Wordsは、画像の局所特徴量を量子化し、量子化後の局所特徴量を単語と見立て、同様に頻度により定義される１つの特徴ベクトルとして表現し、ＩＤＦを用いた重み付けを利用して同一の類推方法を適用することができる。
【０００４】
一方で、スマートフォンやタブレット端末のようなモバイル端末が普及する中で、コンテンツ検索処理に対して、更なる省メモリ化及び高速マッチング化が要求されてきている。特に、拡張現実感（Augmented Reality, AR）の用途における画像認識の技術分野によれば、リアルタイムに処理するべく、ＳＩＦＴやＳＵＲＦよりも更に高速にコンテンツを検索することが要求される。そこで、バイナリ局所特徴ベクトルを用いた抽出アルゴリズムであるＦＡＳＴ（例えば非特許文献２参照）やＦＲＥＡＫ（例えば非特許文献３参照）が注目されている。これら技術によれば、ＳＩＦＴやＳＵＲＦよりも高速に特徴ベクトルが抽出でき、更に抽出される特徴ベクトルもコンパクトとなる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−２８２５８１号公報
【非特許文献】
【０００６】
【非特許文献１】J. Sivic et al., "Video Google: A Text Retrieval Approach toObject Matching in Videos," in Proc. ICCV, 2003.
【非特許文献２】E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, "ORB: Anefficient alternative to SIFT or SURF," in Proc. ICCV, 2011.
【非特許文献３】A. Alahi, R. Ortiz, and P. Vandergheynst, "FREAK: Fast RetinaKeypoint," in Proc. CVPR, 2012.
【非特許文献４】O. Boiman, E. Shechtman, and M. Irani, "In defense ofnearest-neighbor based image classification," in Proc. of CVPR, 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に記載された従来の類似画像検索の枠組みでは、特徴ベクトルを量子化し、文書検索で用いられるＩＤＦ類似度の導出に利用していた。しかしながら、この量子化処理は、特徴ベクトル間の分別性を低下させ、検索精度を低下されることが指摘されている（例えば非特許文献４参照）。
【０００８】
また、既存の画像認識技術を大規模なシステムに適用した場合、一般的には、大量のリファレンス画像を蓄積したデータベースのサーバを、クラウドに設置することが想定される。この場合、例えばスマートフォンのようなクライアントは、自ら撮影されたクエリ画像をサーバへ送信し、そのサーバから最も類似するリファレンス画像（又はリファレンス情報）を受信することができる。
【０００９】
この場合、サーバにおける処理負荷軽減のために、クライアントが、画像から局所特徴ベクトルを抽出し、その局所特徴ベクトルをサーバへ送信することも想定できる。これによって、データベースサーバにおける局所特徴抽出処理の負荷が軽減されると共に、画像そのものをネットワークを介して送信するよりも、データ量が少ないという利点がある。
【００１０】
しかしながら、現実的には、ＦＡＳＴやＦＲＥＡＫのようなバイナリ局所特徴ベクトルを用いたとしても、サーバにおけるバイナリ局所特徴ベクトルの検索処理の負荷は依然として大きい。また、バイナリ局所特徴ベクトルは次元数が大きいために、送信データ量も依然として大きい。
【００１１】
そこで、本発明は、バイナリ局所特徴ベクトルを用いた画像の検索処理の負荷を軽減する検索装置、システム、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明によれば、リファレンス画像から抽出されたリファレンスベクトルの集合から、クエリ画像のクエリベクトルに類似したベクトルを検索する検索装置であって、
リファレンス画像について、リスト識別子LIDn毎に、リファレンス画像識別子と、粗量子化及び直積量子化を用いて符号化した画像特徴符号との複数の組を対応付けた転置インデックスを登録する転置インデックス登録手段と、
クエリ画像についてリスト識別子LIDnと画像特徴符号の複数の組を入力する検索手段とを有し、
検索手段は、
クエリ画像の各リスト識別子と画像特徴符号の組について、当該リスト識別子に対応する転置インデックスのリストを取得し、
クエリ画像の画像特徴符号と、取得したリスト中のリファレンス画像の各画像特徴符号との間の距離を算出し、
距離が短いほど高くなるスコア値を算出し、
当該リファレンス画像毎に該スコア値を累積加算し、
スコア値が最も高くなるリファレンス画像を検索結果として出力する
ことを特徴とする。
【００１３】
本発明の検索装置における他の実施形態によれば、検索手段は、距離が短い上位所定件数(K)に相当するスコア値のみを当該リファレンス画像に累積加算することも好ましい。
【００１４】
本発明の検索装置における他の実施形態によれば、検索手段について、上位所定件数(K)は、予め設定された固定数か、又は、予め設定された距離に関する閾値THに基づいて当該距離が閾値TH以下となる距離の数であることも好ましい。
【００１５】
本発明の検索装置における他の実施形態によれば、
検索手段について、上位所定件数(K)のうちi件目に対応する加算スコアは、
（１）k番目の距離の二乗からi番目の距離の二乗を引いたものとするか、
（２）k番目の距離の二乗とi番目の距離の二乗の比から1を引いたものとするか、
（３）k番目の距離とi番目の距離の比の二乗から1を引いたものとするか、又は、
（４）k番目の距離とi番目の距離の比から1を引いたものの二乗とする
ことも好ましい。
【００１６】
本発明の検索装置における他の実施形態によれば、
画像特徴符号は、直積量子化のための残差コードブックの代表ベクトルの識別子の列で表されており、
画像特徴符号間の距離は、第１の識別子列ｘ及び第２の識別子列ｙについて、第１の識別子列ｘのl番目の識別子に対応する代表ベクトルと第２の識別子列ｙのl番目の識別子に対応する代表ベクトルとの間の各距離を1≦l≦Lについて総和したものである
ことも好ましい。
【００１７】
本発明の検索装置における他の実施形態によれば、
画像特徴符号間の距離は、残差コードブックにおける２つの第１の識別子列ｘ及び第２の識別子列ｙの総当りの組み合わせについて、第１の識別子列ｘの代表ベクトルと第２の識別子列ｙの代表ベクトルとの間の距離を登録したテーブルＴを用いて算出されることも好ましい。
【００１８】
本発明の検索装置における他の実施形態によれば、
クエリ画像及びリファレンス画像から局所特徴のクエリベクトル及びリファレンスベクトルを抽出する局所特徴抽出手段と、
局所特徴抽出手段から出力されたクエリベクトル及びリファレンスベクトルに対して、コードブックを用いて第１階層で粗量子化し、その量子化誤差を残差コードブックを用いて第２階層で直積量子化し、当該クエリ画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を検索手段へ出力し、当該リファレンス画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を転置インデックス登録手段へ出力する符号化手段と
を有することも好ましい。
【００１９】
本発明の検索装置における他の実施形態によれば、
局所特徴抽出手段は、ＯＲＢ(Oriented FAST and Rotated BRIEF)又はＦＲＥＡＫ(Fast
Retina Keypoint)に基づくバイナリ局所特徴ベクトルを抽出し、
コードブックは、バイナリ局所特徴ベクトルのリファレンスベクトルを、K-Medoids法を用いてクラスタリングしたものであり、
粗量子化は、バイナリ局所特徴ベクトルのクエリベクトルを、コードブック内の最も類似したバイナリ代表ベクトルに割り当て、
量子化誤差は、バイナリ特徴ベクトルと、そのバイナリ特徴ベクトルに最も類似したバイナリ代表ベクトルとの排他的論理和によって算出されることも好ましい。
【００２０】
本発明によれば、前述した検索装置として機能するサーバと、クエリ画像を入力する端末とを有するシステムであって、
端末は、
クエリ画像から局所特徴のクエリベクトルを抽出する局所特徴抽出手段と、
局所特徴抽出手段から出力されたクエリベクトルに対して、コードブックを用いて第１階層で粗量子化し、その量子化誤差を残差コードブックを用いて第２階層で直積量子化し、当該クエリ画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を出力する符号化手段と、
クエリ画像におけるリスト識別子LIDn毎の画像特徴符号の複数の組を、サーバへ送信するクエリ符号送信手段と、
サーバから、検索された１つ以上のリファレンス画像を受信し且つ出力するリファレンス画像受信手段とを有し、
サーバは、
リファレンス画像から局所特徴のリファレンスベクトルを抽出する局所特徴抽出手段と、
局所特徴抽出手段から出力されたリファレンスベクトルに対して、コードブックを用いて第１階層で粗量子化し、その量子化誤差を残差コードブックを用いて第２階層で直積量子化し、当該リファレンス画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を、転置インデックス登録手段へ出力する符号化手段と、
端末から、クエリ画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を受信するクエリ符号受信手段と、
スコア値が最も高くなるリファレンス画像を検索結果として送信するリファレンス画像送信手段と
を有することを特徴とする。
【００２１】
本発明のシステムにおける他の実施形態によれば、
局所特徴抽出手段は、ＯＲＢ又はＦＲＥＡＫに基づくバイナリ局所特徴ベクトルを抽出し、
コードブックは、バイナリ局所特徴ベクトルのリファレンスベクトルを、K-Medoids法を用いてクラスタリングしたものであり、
粗量子化は、バイナリ局所特徴ベクトルのクエリベクトルと、コードブック内のバイナリ代表ベクトルとを排他的論理和によって算出する
ことも好ましい。
【００２２】
本発明によれば、装置に搭載されたコンピュータを、リファレンス画像から抽出されたリファレンスベクトルの集合から、クエリ画像のクエリベクトルに類似したベクトルを検索するように機能させるプログラムであって、
リファレンス画像について、リスト識別子LIDn毎に、リファレンス画像識別子と、粗量子化及び直積量子化を用いて符号化した画像特徴符号との複数の組を対応付けた転置インデックスを登録する転置インデックス登録手段と、
クエリ画像についてリスト識別子LIDnと画像特徴符号の複数の組を入力する検索手段とを有し、
検索手段は、
クエリ画像の各リスト識別子と画像特徴符号の組について、当該リスト識別子に対応する転置インデックスのリストを取得し、
クエリ画像の画像特徴符号と、取得したリスト中のリファレンス画像の各画像特徴符号との間の距離を算出し、
距離が短いほど高くなるスコア値を算出し、
当該リファレンス画像毎に該スコア値を累積加算し、
スコア値が最も高くなるリファレンス画像を検索結果として出力する
ようにコンピュータを機能させることを特徴とする。
【００２３】
本発明によれば、装置を用いて、リファレンス画像から抽出されたリファレンスベクトルの集合から、クエリ画像のクエリベクトルに類似したベクトルを検索する検索方法であって、
リファレンス画像について、リスト識別子LIDn毎に、リファレンス画像識別子と、粗量子化及び直積量子化を用いて符号化した画像特徴符号との複数の組を対応付けた転置インデックスを登録する転置インデックス登録部を有し、
クエリ画像についてリスト識別子LIDnと画像特徴符号の複数の組を入力する第１のステップと、
クエリ画像の各リスト識別子と画像特徴符号の組について、当該リスト識別子に対応する転置インデックスのリストを取得する第２のステップと、
クエリ画像の画像特徴符号と、取得したリスト中のリファレンス画像の各画像特徴符号との間の距離を算出する第３のステップと、
距離が短いほど高くなるスコア値を算出する第４のステップと、
当該リファレンス画像毎に該スコア値を累積加算する第５のステップと、
スコア値が最も高くなるリファレンス画像を検索結果として出力する第６のステップと
を有することを特徴とする。
【発明の効果】
【００２４】
本発明の検索装置、システム、プログラム及び方法によれば、バイナリ局所特徴ベクトルを用いた画像の検索処理の負荷を軽減することができる。
【図面の簡単な説明】
【００２５】
【図１】本発明におけるシステム構成図である。
【図２】本発明における符号化部の機能構成図である。
【図３】符号化部の処理を表す説明図である。
【図４】転置インデックス登録部のデータ構造を表す説明図である。
【図５】検索部における処理を表す説明図である。
【図６】本発明における検索部の処理を表すフローチャートである。
【発明を実施するための形態】
【００２６】
以下、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２７】
図１は、本発明におけるシステム構成図である。
【００２８】
本発明によれば、検索装置１は、大量のリファレンス画像を予め入力し且つ蓄積している。その上で、以下のように２つの実施の形態に区分できる。
（１）検索装置（単体）：ユーザからクエリ画像が入力され、そのクエリ画像に対するリファレンス画像を検索し、そのリファレンス画像をユーザに対して出力する。
（２）サーバ−クライアント・システム：サーバとしての検索装置１と、クライアントとしての端末２とが、ネットワークを介して接続されている。端末２は、ユーザからクエリ画像が入力され、そのクエリ画像を検索装置１へ送信する。これに対し、検索装置１は、受信したクエリ画像に対するリファレンス画像を検索し、そのリファレンス画像を端末２へ返信する。そして、端末２は、そのリファレンス画像をユーザに対して出力する。
【００２９】
＜検索装置１＞
検索装置１は、局所特徴ベクトルの集合で表されるリファレンス画像（検索対象の画像）の集合から、同じく局所特徴ベクトルの集合で表されるクエリ画像（検索キーとなる画像）に類似したリファレンスコンテンツを検索する。検索装置１は、少なくとも、局所特徴抽出部１１と、符号化部１２と、転置インデックス登録部１３と、検索部１４とを有する。これら機能構成部は、検索装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。また、これら機能構成部の処理の流れは、装置を用いた検索方法としても理解できる。
【００３０】
［局所特徴抽出部１１］
局所特徴抽出部１１は、クエリ画像及びリファレンス画像から局所特徴のクエリベクトル及びリファレンスベクトルを抽出する。本発明によれば、バイナリ局所特徴ベクトルの抽出アルゴリズムとして、ＯＲＢ(Oriented FAST and Rotated BRIEF)又はＦＲＥＡＫ(Fast Retina Keypoint)を用いる。ＯＲＢの場合、１つのコンテンツから２５６ビットのバイナリ局所特徴ベクトルの集合が抽出される。例えば、高速にマッチングを実行するべく、バイナリコードによる特徴記述としてＢＲＩＥＦ(Binary Robust Independent Elementary Features)がある。本発明によれば、ＢＲＩＥＦに回転不変性を導入した特徴記述をすることができる「ＯＲＢ」を用いる。特に、ＯＲＢによれば、ＳＩＦＴやＳＵＲＦと比較して、同等以上の精度を保持すると共に、数百倍の高速化を実現することができる。
【００３１】
ＯＲＢは、「特徴点検出処理」と「特徴ベクトル記述処理」との２つのステップから構成される。
（特徴点検出処理）
ＯＲＢの特徴点検出処理によれば、高速にキーポイントを検出するためにＦＡＳＴ(Features from Accelerated Segment Test)を用いる。また、ＦＡＳＴでは、スケール変化に対してロバストではないため、画像を複数のサイズに変換し、それぞれのサイズの画像から特徴点を抽出する。
【００３２】
また、既存のＦＡＳＴには、回転不変性を得るためのキーポイントのオリエンテーション算出のアルゴリズムがない。そのために、ＯＲＢでは、回転不変性を得るべくOriented FASTを採用している。オリエンテーションを基準として特徴記述をすることによって、入力画像が回転していても、同一なキーポイントは同一な特徴量となって検出することができる。そのために、キーポイントの中心とパッチの輝度の重心の方向ベクトルを用いる。
【００３３】
（特徴ベクトル記述処理）
次に、ＯＲＢの特徴ベクトル記述処理によれば、検出された特徴点毎に、ＢＲＩＥＦ特徴ベクトル記述子によってバイナリ局所特徴ベクトルが抽出される。これらは、特徴点周辺の２箇所のピクセルの輝度の大小関係から求められる。
【００３４】
ＢＲＩＥＦは、バイナリコードによってキーポイントの特徴量記述を実行することができる。ＳＩＦＴやＳＵＲＦによれば、特徴量記述に高次元の実数を用いていた。しかしながら、高次元の実数を用いた場合、メモリ容量の増加と類似度計算の増加と問題となる。そこで、ＯＲＢに基づくＢＲＩＥＦを用いてバイナリコードの特徴記述によって省メモリ化し、類似度計算にハミング距離を用いて処理コストを抑制する。
【００３５】
ＢＲＩＥＦによれば、パッチ内においてランダムに選択された２点の輝度差の符号からバイナリコードを生成する。選択するピクセルは、キーポイント位置を中心としたガウス分布に従ってランダムに選択する。ここで、ＯＲＢは、更に高精度にマッチングをさせるために、学習を用いてピクセルを選択している。選択するピクセル位置は、ペアのビット分散が大きく且つＮ組のペアの相関が低い場合に、特徴記述能力が高いバイナリコードとして、特徴記述に使用する。Ｎ組のペアは、Greedyアルゴリズムを用いて絞り込む。
【００３６】
［符号化部１２］
符号化部１２は、局所特徴抽出部１１から出力された、バイナリ局所特徴ベクトルのクエリベクトル及びリファレンスベクトルを画像特徴符号化して、その画像特徴符号を転置インデックス登録部１３へ出力する。
【００３７】
図２は、本発明における符号化部の機能構成図である。
図３は、符号化部の処理を表す説明図である。
【００３８】
図２によれば、符号化部１２は、コードブック記憶部１２０と、粗量子化部１２１と、残差ベクトル分割部１２２と、残差コードブック記憶部１２３と、直積量子化部１２４とを有する。
【００３９】
コードブック記憶部１２０は、バイナリ局所特徴ベクトルと同一ビット長の代表バイナリ局所特徴ベクトルＢ1〜Ｂsが記憶されている。ＯＲＢのバイナリ局所特徴ベクトルの場合、例えば２５６ビット長である。この代表バイナリ局所特徴ベクトルは、K-Medoids法を用いてクラスタリングして算出されたものであってもよい。
【００４０】
粗量子化部１２１は、局所特徴抽出部１１から出力されたバイナリ局所特徴ベクトルＢを、コードブック記憶部１２０のコードブックを用いて、第１階層として粗量子化する。ここでの量子化では、バイナリ局所特徴ベクトルＢと最も類似した代表バイナリ局所特徴ベクトルＢnのリスト識別子LIDを導出する。「最も類似した」とは、例えばハミング距離が最も近いものであってもよい。
LID＝argmins ham（Ｂ,Ｂs）
ham（ｘ,ｙ）：ｘとｙとのハミング距離
次に、入力されたバイナリ局所特徴ベクトルＢと、そのＢと最も類似した（例えばハミング距離が最も近くなる）バイナリ代表ベクトルＢsとの排他的論理和を算出し、それを残差バイナリベクトルＢRとする。
ＢR＝Ｂ XOR Ｂs    （XOR：排他的論理和）
算出された残差バイナリベクトルＢRは、残差ベクトル分割部１２２へ出力される。
【００４１】
残差ベクトル分割部１２２は、残差バイナリ局所特徴ベクトルＢRを、Ｌ個の部分残差ベクトルに分割する。例えばＬ＝８である場合、２５６ビット／８個＝３２ビットの部分残差ベクトルに区分される。各部分残差ベクトルは、直積量子化部１２４へ出力される。
【００４２】
残差コードブック記憶部１２３は、各部分残差ベクトルと同一ビット長の代表残差ベクトルＢ1〜Ｂsが記憶されている。例えば３２ビット長である。この代表残差ベクトルも、K-Medoids法を用いてクラスタリングして算出されたものであってもよい。
【００４３】
直積量子化部１２４は、残差コードブック記憶部１２３を用いて、第２階層として直積量子化する。l（1〜L）番目の部分残差ベクトルを量子化するために、l番目のコードブックlを利用する。これによって、以下のような画像特徴符号RCが得られる。即ち、画像特徴符号RCは、直積量子化のための残差コードブックの代表ベクトルの識別子列で表され、以下のようにｆlをＬ個連結したものである。
RC＝（ｆ1，・・・，ｆL）
【００４４】
バイナリ局所特徴ベクトルＢを符号化した結果として、リスト識別子LIDと画像特徴符号RCとの組が得られる。
（LID, RC）
LID：log2Ｓビット（Ｓは、コードブック記憶部のコードブック数）
RC：L・log2Ｆビット（Ｆは、残差コードブック記憶部のコードブック数）
【００４５】
そして、直積量子化部１２４は、以下の２つの方向で出力する。
（１）当該クエリ画像のバイナリ局所特徴ベクトルについては、リスト識別子LIDn毎に、画像特徴符号RCの複数の組を、検索部１４へ出力する。
（２）当該リファレンス画像のバイナリ局所特徴ベクトルについては、リスト識別子LIDn毎に、画像特徴符号RCの複数の組を、転置インデックス登録部１３へ出力する。
【００４６】
［転置インデックス登録部１３］
転置インデックス登録部１３は、リスト識別子LIDn毎に、画像識別子RIDと画像特徴符号RCとの組（RID,RCn）をリストとして登録したものである。
【００４７】
図４は、転置インデックス登録部のデータ構造を表す説明図である。
【００４８】
リファレンス画像RIDについて、リスト識別子LIDn毎に、リスト識別子LIDと、粗量子化及び直積量子化を用いて符号化した画像特徴符号RCとの複数の組が対応付けられている。
RID  ->  （LID1,RC1）（LID2,RC2）・・・（LIDn,RCn）・・・（LIDN,RCN）
組（LID,RC）毎に、その画像識別子RIDと画像特徴符号RCとの組（RID,RC）を、転置インデックスにおけるそのリスト識別子LIDに連結して登録する。
LID1  ->  （RID,RC）（RID,RC）（RID,RC）・・・
LID2  ->  （RID,RC）（RID,RC）（RID,RC）・・・
・・・
LIDn  ->  （RID,RC）（RID,RC）（RID,RC）・・・
・・・
【００４９】
［検索部１４］
検索部１４は、クエリ画像について、リスト識別子LIDnと画像特徴符号QCnの複数の組を入力する。
クエリ符号  ->（LID1,QC1）（LID2,QC2）・・・（LIDn,QCn）・・・（LIDN,QCN）
【００５０】
図５は、検索部における処理を表す説明図である。
図６は、本発明における検索部の処理を表すフローチャートである。
【００５１】
検索部１４は、以下の処理ステップを、リファレンス画像毎に実行し（Ｓ４）、最終的に、最も高いスコア値のリファレンス画像を検索結果として出力する（Ｓ５）。
score[]＝0                                                        （Ｓ０）
for each i＝１〜N
転置インデックスのLIDi番目のリストを取得                      （Ｓ１）
リスト中の組（RID1, RC1）〜（RIDM, RCM）について
クエリ画像に基づく組（QCi, RCj）の距離Ｄijを算出し、
距離と画像識別子の組（Ｄij, RIDj）を作成する            （Ｓ２）
Ｄijを昇順にソートする                                         （Ｓ３）
上位K番目までの組Ｄi'j'を選択する
for each k＝1〜K
k番目のＤi'j'について、score［RCj'］＋＝Ｓ（Ｄi'j',Ｄ）
end for
end for
【００５２】
（Ｓ０）最初に、初期設定として、変数score[]＝０とする。
【００５３】
検索部１４は、以下のＳ１〜Ｓ３の処理を、入力されたクエリ画像に基づくリスト識別子と画像特徴符号の組（LIDi, QCi）毎に、繰り返し実行する（i＝1〜N）。
【００５４】
（Ｓ１）クエリ画像の各リスト識別子と画像特徴符号の組（LIDi,QCi）について、当該リスト識別子LIDiに対応する転置インデックスのリスト（RIDj,RCj）・・・を取得する。
【００５５】
（Ｓ２）転置インデックスの当該リスト識別子LIDiに並ぶリストの分だけ、以下の処理を繰り返し実行する（j＝1〜M）。
クエリ画像の画像特徴符号QCiと、取得したリスト中のリファレンス画像の各画像特徴符号RCjとの間の距離Ｄijを算出する。そして、その距離Ｄijと画像識別子RIDjとの組（Ｄij, RIDj）を作成する。
【００５６】
画像特徴符号間の「距離」は、第１の識別子列ｘ及び第２の識別子列ｙについて、第１の識別子列ｘのl番目の識別子に対応する代表ベクトルと第２の識別子列ｙのl番目の識別子に対応する代表ベクトルとの間の各距離を1≦l≦Lについて総和したものである。例えば２つの画像特徴符号を以下のように表したとする。
第１の画像特徴符号QCi＝（ｘ1，ｘ2，・・・，ｘL）
第２の画像特徴符号RCj＝（ｙ1，ｙ2，・・・，ｙL）
第１の画像特徴符号QCiと第２の画像特徴符号RCjとの間の距離Ｄij
＝ｘ1の代表ベクトルとｙ1の代表ベクトルとの間の距離
＋ｘ2の代表ベクトルとｙ2の代表ベクトルとの間の距離
＋・・・・・
＋・・・・・
＋ｘLの代表ベクトルとｙLの代表ベクトルとの間の距離
【００５７】
尚、画像特徴符号間の距離は、残差コードブックにおける２つの第１の識別子列ｘ及び第２の識別子列ｙの総当りの組み合わせについて、第１の識別子列ｘの代表ベクトルと第２の識別子列ｙの代表ベクトルとの間の距離を登録したテーブルＴを用いて算出されるものであってもよい。
テーブル：Ｔl［QCil］［RCjl］
距離Ｄij＝Σ1LＴl［QCil］［RCjl］
即ち、l番目のコードを符号化する際に利用したl番目のコードブックＣl内の代表バイナリベクトルＣl1，Ｃl2，・・・，ＣlFについて、ＣlxとＣlyとの間の距離が予め計算されており、テーブルＴl［x］［y］に保持されていることとなる。
【００５８】
（Ｓ３）次に、距離Ｄijと画像識別子RIDjとの組（Ｄij, RIDj）を、距離が短い順（昇順）にソートする。
【００５９】
そして、距離が短い上位所定件数(K)のみを選択する。距離が短いとは、類似度が高いことを意味する。また、上位所定件数(K)は、予め設定された固定数であってもよい。又は、予め設定された距離に関する閾値THに基づいて当該距離が閾値TH以下となる距離の数であってもよい。
【００６０】
具体的には、上位K件の複数の組（Ｄij, RIDj）について、距離が短いほど高くなるスコア値を算出し、それらスコア値を累積加算する。具体的には、k番目の距離Ｄi'j'及びK番目の距離Ｄを用いて、以下のいずれかによって、スコア値を算出する。
Ｓ(Ｄi'j',Ｄ)：k番目の距離を持つ画像への投票スコア値
（１）k番目の距離の二乗から、i番目の距離の二乗を引いたものとする
Ｓ(Ｄi'j',Ｄ)＝Ｄ2−Ｄi'j'2
（２）k番目の距離の二乗とi番目の距離の二乗の比から、1を引いたものとする
Ｓ(Ｄi'j',Ｄ)＝Ｄ2／Ｄi'j'2−１
（３）k番目の距離とi番目の距離の比の二乗から、1を引いたものとする
Ｓ(Ｄi'j',Ｄ)＝(Ｄ／Ｄi'j')2−１
（４）k番目の距離とi番目の距離の比から1を引いたものの二乗とする
Ｓ(Ｄi'j',Ｄ)＝(Ｄ／Ｄi'j'−１)2
【００６１】
（Ｓ４）当該リファレンス画像毎に該スコア値を累積加算する。次のリファレンス画像について、Ｓ１〜Ｓ３を繰り返す。
【００６２】
（Ｓ５）最終的に、スコア値が最も高くなるリファレンス画像を、検索結果として出力する。
【００６３】
図１に戻って、本発明によれば、前述した検索装置として機能するサーバと、クエリ画像を入力する端末とを有するシステムとして構成することもできる。
【００６４】
＜サーバ（検索装置）１＞
サーバ１は、前述の検索装置に加えて、ネットワークに接続する通信インタフェース１０と、クエリ符号受信部１５と、リファレンス符号送信部１６とを更に有する。
【００６５】
クエリ符号受信部１５は、端末２から、クエリ画像についてリスト識別子LIDn毎に画像特徴符号の複数の組を受信する。受信したそれら画像特徴符号の組は、検索部１４へ出力される。
リファレンス画像送信部１６は、検索部１４から出力された、スコア値が最も高くなるリファレンス画像を検索結果として検索結果として、端末２へ送信する。
【００６６】
＜端末２＞
端末２は、前述した検索装置１と同一の局所特徴量抽出部２１及び符号化部２２を有する。その上で、端末２は、ネットワークに接続する通信インタフェース２０と、クエリ符号送信部２５と、リファレンス画像受信部２６とを更に有する。
【００６７】
クエリ符号送信部２５は、符号化部２２から出力された、クエリ画像におけるリスト識別子LIDn毎の画像特徴符号の複数の組を、サーバ１へ送信する。
リファレンス画像受信部２６は、サーバ１から、検索された１つ以上のリファレンス画像を受信し、そのリファレンス画像をユーザに対して出力する。
【００６８】
以上、詳細に説明したように、本発明の検索装置、システム、プログラム及び方法によれば、バイナリ局所特徴ベクトルを用いた画像の検索処理の負荷を軽減することができる。具体的には、バイナリ局所特徴ベクトルを用いた画像の検索処理について、検索範囲を制限することによって処理負荷を軽減し且つ高速な検索処理を実現することができる。また、量子化された残差ベクトルを更に符号化し、その符号に基づいて特徴ベクトル間の距離を推定し、その距離に基づいた類似度を算出するために、量子化に伴う精度低下を軽減することができる。更に、クライアントによって局所特徴抽出処理が実行されたとしても、サーバへ送信するデータ量を、できる限り少なくすることができる。
【００６９】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００７０】
１  検索装置
２  端末
１０、２０  通信インタフェース
１１、２１  局所特徴抽出部
１２、２２  符号化部
１２０  コードブック記憶部
１２１  粗量子化部
１２２  残差ベクトル分割部
１２３  残差コードブック記憶部
１２４  直積量子化部
１３  転置インデックス登録部
１４  検索部
１５  クエリ符号受信部
１６  リファレンス画像送信部
２５  クエリ符号送信部
２６  リファレンス画像受信部
【図１】
0006042778.tif 000002
【図２】
0006042778.tif 000003
【図３】
0006042778.tif 000004
【図４】
0006042778.tif 000005
【図５】
0006042778.tif 000006
【図６】
0006042778.tif 000007