画像検索に適した特徴ベクトルを抽出するプログラム、方法及び画像検索装置
【課題】画像検索の際に、比較すべき画像に回転及びスケールの違いがあっても高い検索精度で、少ない計算資源で実行することができる特徴点の特徴ベクトルを抽出する。
【解決手段】ｍ個の特徴点集合について、特徴ベクトルの抽出対象となる注目特徴点ｐ０からｋ１番目に近傍の特徴点ｑを選択し（Ｓ１）、直線ｐ０−ｑの距離ｒを導出し（Ｓ２）、ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出し（Ｓ３）、ｐ０とＢの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、ｐ０の特徴ベクトルｆを算出する（Ｓ４）。
【解決手段】ｍ個の特徴点集合について、特徴ベクトルの抽出対象となる注目特徴点ｐ０からｋ１番目に近傍の特徴点ｑを選択し（Ｓ１）、直線ｐ０−ｑの距離ｒを導出し（Ｓ２）、ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出し（Ｓ３）、ｐ０とＢの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、ｐ０の特徴ベクトルｆを算出する（Ｓ４）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像検索に適した特徴ベクトルを抽出する技術に関する。
【背景技術】
【０００２】
近年、オンライン／オフラインに限られず、ストレージの大容量化に伴って、大量のコンテンツを蓄積することが可能となっている。また、携帯電話機やスマートフォンに代表される情報端末機器の普及によって、ユーザ自ら取得した写真データのようなデジタルコンテンツも、データベースに大量かつ容易に蓄積することができる。オフラインデータベースとして、ＨＤＤ(Hard Disk Drive)、ＤＶＤ(Digital Versatile Disk)、Blu-ray disc等の記憶装置がある。また、オンラインデータベースとしては、Flickr（登録商標）やMySpace（登録商標）のようなソーシャルネットワークサービスがある。これら記憶装置及びサービスによれば、データベースに蓄積された個人の大量且つ多様なマルチメディアコンテンツを検索するする技術が重要となる。
【０００３】
例えば、大量の参照画像（静止画像及び動画像）の中から、クエリ画像に類似する参照画像を高い精度で検索する技術がある（例えば非特許文献１参照）。この技術によれば、画像から大量の局所特徴ベクトルを抽出し、それらをベクトル量子化し、同一の代表ベクトルにベクトル量子化された局所特徴ベクトルの数によって類似度を算出する。しかしながら、この技術は、多くの計算資源（リソース）を必要とするという問題があった。
【０００４】
この問題に対して、できる限り少ない計算資源によって、画像を高速に検索することができる技術がある（例えば特許文献１参照）。この技術によれば、２値化された画像から特徴点を抽出し、特徴点の配置からアフィン不変な特徴ベクトルを抽出し、特徴ベクトルのマッチングに基づく投票処理によって検索する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】ＷＯ２００６／０９２９５７
【非特許文献】
【０００６】
【非特許文献１】J. Sivic et al., "Video Google: A Text Retrieval Approach toObject Matching in Videos," in Proc. ICCV, 2003.
【非特許文献２】H. Uchiyama and H. Saito, "Random dot markers," in IEEEVirtual Reality, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、前述した従来技術によれば、以下のような問題がある。
（１）特徴点に対して、高次元の特徴ベクトルを抽出しているために、多くの計算資源を必要とすると共に、近傍探索における検索精度が低下する。これは、特徴ベクトルを抽出する点集合の自由度よりも大きい次元の冗長な特徴ベクトルを抽出していることに基づく。
（２）アフィン不変な特徴ベクトルを抽出しているため、アフィン不変性が求められないような環境では、逆に検索精度が低下する。
【０００８】
そこで、本発明は、画像検索の際に、比較すべき画像に回転及びスケールの違いがあっても高い検索精度で、且つ、少ない計算資源で実行することができるような特徴点の特徴ベクトルを抽出するプログラム、方法及び画像検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明によれば、画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有するようにコンピュータを実行させることを特徴とする。
【００１０】
本発明のプログラムにおける他の実施形態によれば、
第４のステップにおける特徴ベクトルの算出について、注目特徴点ｐ０を中心として、特徴点ｂから一方の回転方向へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍを順に算出し、
特徴ベクトルｆ１〜ｆｍは、注目特徴点ｐ０から当該特徴点ｐ１〜ｐｍへのｘｙ座標ベクトルｆ(ｘi,ｙi)である
ようにコンピュータを実行させることも好ましい。
【００１１】
本発明のプログラムにおける他の実施形態によれば、
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
ｘ軸と、注目特徴点ｐ０及び特徴点ｂを結ぶ直線ｐ０−ｂとの間の角度θを導出し、
注目特徴点ｐ０を中心として、直線ｐ０−ｂがｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる
ようにコンピュータを実行させることも好ましい。
【００１２】
本発明のプログラムにおける他の実施形態によれば、
第４のステップは、更に、注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、スケールが一定となるようにスケールを伸縮させるべくコンピュータを実行させることも好ましい。
【００１３】
本発明のプログラムにおける他の実施形態によれば、
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
注目特徴点ｐ０からｋ２番目に近傍の特徴点ｃを導出し、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる
ようにコンピュータを実行させることも好ましい。
【００１４】
本発明のプログラムにおける他の実施形態によれば、
第１のステップの前段について、
特徴ベクトルの抽出対象となる注目特徴点ｐ０について、ｐ０の最も近傍に位置するｎ個の特徴点集合Ｘ（ｐ０を含まない）を抽出するステップと、
ｎ個の特徴点集合Ｘから、ｍ（ｍ≦ｎ）個の特徴点集合Ｙ（ｐ０を含まない）を選択するステップと
を有し、
ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて、第１〜第４のステップを繰り返す
ようにコンピュータを実行させることも好ましい。
【００１５】
本発明のプログラムにおける他の実施形態によれば、
第３のステップについて、注目特徴点ｐ０を中心として、距離ｒ／ρ以上（ρ≧１）から距離ｒ・ρ以下の範囲に含まれる１つ以上の特徴点Ｂを導出するようにコンピュータを実行させることも好ましい。
【００１６】
本発明のプログラムにおける他の実施形態によれば、
第４のステップについて、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、ｘ軸と直線ｐ０−ｂとの間の角度θを付加するようにコンピュータを実行させることも好ましい。
【００１７】
本発明のプログラムにおける他の実施形態によれば、
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像の特徴ベクトル毎に、クエリ画像の特徴ベクトルと共に付加された角度θと、当該参照画像の特徴ベクトルと共に付加された角度θとの角度差Δθを算出する第６ステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
クエリ画像の特徴ベクトルそれぞれに対して算出された参照画像の画像識別子及び角度差Δθに基づく区分角度差に応じて投票処理を行うことによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることを特徴とする。
【００１８】
本発明のプログラムにおける他の実施形態によれば、
第４のステップについて、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、スケールの伸縮前の直線ｐ０−ｃの距離δを付加するようにコンピュータを実行させることも好ましい。
【００１９】
本発明のプログラムにおける他の実施形態によれば、
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像毎に、クエリ画像の特徴ベクトルと共に付加された距離δと、当該参照画像の特徴ベクトルと共に付加された距離δとの距離比Δδを算出する第６のステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
クエリ画像の画像識別子に基づいて、複数の参照画像の画像識別子を、距離比δに基づく区分距離比に応じて投票することによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることも好ましい。
【００２０】
本発明によれば、装置を用いて、画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出する方法において、
画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有することを特徴とする。
【００２１】
本発明によれば、大量の参照画像を蓄積した参照画像蓄積手段を有し、クエリ画像に類似する参照画像を検索する画像検索装置において、
参照画像蓄積手段の参照画像から、ｘｙ座標の複数の特徴点を抽出する参照用特徴点抽出手段と、
参照画像の各特徴点における特徴ベクトルを抽出する参照用特徴量抽出手段と、
参照画像の各特徴点における特徴ベクトルを、画像データベースに登録する参照用特徴量登録手段と、
クエリ画像から、ｘｙ座標の複数の特徴点を抽出するクエリ用特徴点抽出手段と、
クエリ画像の各特徴点における特徴ベクトルを抽出するクエリ用特徴量抽出手段と、
クエリ画像の特徴ベクトルに類似する、参照画像の特徴ベクトルを検索する画像検索手段と
を有し、
参照用特徴量抽出手段及びクエリ用特徴量抽出手段は、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択し、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出し、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出し、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する
ことを特徴とする。
【発明の効果】
【００２２】
本発明のプログラム、方法及び画像検索装置によれば、画像検索の際に、比較すべき画像に回転及びスケールの違いがあっても高い検索精度で、且つ、少ない計算資源で実行することができるような特徴点の特徴ベクトルを抽出する。
【図面の簡単な説明】
【００２３】
【図１】画像検索装置の機能構成図である。
【図２】本発明における特徴量抽出部の処理を表すフローチャートである。
【図３】図２のＳ１における特徴点配置を表す説明図である。
【図４】図２のＳ２における特徴点配置を表す説明図である。
【図５】図２のＳ３〜Ｓ５における特徴点配置を表す説明図である。
【図６】図２のＳ６１（ｂ１）における特徴点配置を表す第１の説明図である。
【図７】図２のＳ６２及びＳ６３（ｂ１）における特徴点配置を表す第１の説明図である。
【図８】図２のＳ６１（ｂ２）における特徴点配置を表す第２の説明図である。
【図９】図２のＳ６２及びＳ６３（ｂ２）における特徴点配置を表す第２の説明図である。
【図１０】本発明における投票部の処理を表すフローチャートである。
【図１１】本発明における投票部の概念を表す説明図である。
【発明を実施するための形態】
【００２４】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２５】
図１は、画像検索装置の機能構成図である。
【００２６】
画像検索装置１は、大量の参照画像に中から、クエリ画像に類似する参照画像を検索する。図１によれば、画像検索装置１は、参照画像蓄積部１０と、登録部１１と、検索部１２とを有する。参照画像蓄積部１０は、検索対象となる大量の参照画像を蓄積しており、参照画像毎に画像識別子（ＩＤ）が付与されている。
【００２７】
登録部１１は、参照用特徴点抽出部１１１と、参照用特徴量抽出部１１２と、参照用特徴点登録部１１３と、画像データベース１１４とを有する。また、クエリ用特徴点抽出部１２１と、クエリ用特徴量抽出部１２２と、特徴点検索部１２３及び投票部１２４からなる画像検索部とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、本発明は、参照用特徴量抽出部１１２及びクエリ用特徴量抽出部１２２における特徴ベクトルの抽出に特徴がある。
【００２８】
参照用特徴点抽出部１１１は、参照画像蓄積部１０から入力された参照画像から、ｘｙ座標の多数の特徴点を抽出する。また、クエリ用特徴点抽出部１２１は、入力されたクエリ画像から、ｘｙ座標の多数の特徴点を抽出する。
【００２９】
「特徴点」とは、視覚的に際立つ特徴を有する画像上のｘｙ座標点をいう。特徴点は、例えばHarris、FAST、SUSAN等のコーナー(corner：角)検出器によって抽出されるものであってもよい。コーナー検出器は、画像に写る対象物の矩形の頂点、即ち２つのエッジの交点を、特徴点として検出する。また、特許文献１に記載された技術のように、適応二値化を行い、その重心から特徴点座標を導出するものであってもよい。
【００３０】
参照用特徴点抽出部１１１によって抽出された多数の特徴点は、参照画像の画像識別子と共に、参照用特徴量抽出部１１２へ出力される。また、クエリ用特徴点抽出部１１２によって抽出された多数の特徴点は、クエリ用特徴量抽出部１２２へ出力される。
【００３１】
参照用特徴量抽出部１１２は、参照画像（画像識別子）毎に、各特徴点における特徴ベクトルを抽出する。また、クエリ用特徴量抽出部１２２は、クエリ画像について、各特徴点における特徴ベクトルを抽出する。本発明によれば、各特徴点について、注目特徴点の近傍に位置する他の特徴点の配置に基づいて、回転及びスケールに不変で且つ低次元な特徴ベクトルを抽出する。画像検索の際に、回転及びスケールに不変な特徴ベクトルを用いることによって、回転及びスケールの違い対する画像に対しても精度高く検索することができる。また、低次元な特徴ベクトルを用いることによって、少ない計算資源で画像検索を実行することができる。
【００３２】
図２は、本発明の特徴量抽出部における特徴ベクトルの抽出処理を表すフローチャートである。
【００３３】
（Ｓ１）特徴ベクトルの抽出対象となる注目特徴点ｐ０について、注目特徴点ｐ０の最も近傍に位置するｎ個の特徴点集合Ｘ（注目特徴点ｐ０を含まない）を抽出する（図３参照）。図３によれば、ｎ＝５の例であって、注目特徴点ｐ０の最も近傍に位置する５個の特徴点集合Ｘが抽出されている。
【００３４】
（Ｓ２）ｎ個の特徴点集合Ｘから、注目特徴点ｐ０を含まないｍ（ｍ≦ｎ）個の特徴点集合Ｙを選択する（図４参照）。図４によれば、ｍ＝４の例であって、注目特徴点ｐ０を含まない４個の特徴点集合Ｙが選択されている。Ｓ２〜Ｓ６のステップを、ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて繰り返す。
【００３５】
（Ｓ３）特徴点集合Ｙについて、注目特徴点ｐ０からｋ１番目に近傍の特徴点ｑを選択する（図５参照）。図５によれば、ｋ１＝１の例であって、注目特徴点ｐ０から１番目に近傍の特徴点ｑを選択する。ｋ１の値は、ｍ個以下の任意の数値に固定される。
【００３６】
（Ｓ４）注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する（図５参照）。
【００３７】
（Ｓ５）注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する（図５参照）。ここで、所定長の近傍について、注目特徴点ｐ０を中心として、距離ｒ／ρ以上（ρ≧１）から距離ｒ・ρ以下の範囲に含まれる１つ以上の特徴点Ｂを導出する。図５によれば、２個の特徴点ｂが導出されている。
【００３８】
（Ｓ６）注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度及びスケールが一定となるように回転させ且つスケールを伸縮させる。そして、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する。図５によれば、特徴点集合Ｂの各特徴点ｂ１，ｂ２について、以下の処理を実行する。
【００３９】
（Ｓ６１）ｘ軸と、注目特徴点ｐ０及び特徴点ｂ１を結ぶ直線ｐ０−ｂ１との間の角度θ（０≦θ＜２π）を導出する（図６参照）。また、注目特徴点ｐ０を中心として、特徴点ｂ１から一方の回転方向（図６によれば反時計回り）へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍを割り振る。
【００４０】
特徴ベクトルｆ１〜ｆｍは、注目特徴点ｐ０から当該特徴点ｐ１〜ｐｍへのｘｙ座標ベクトルｆ(ｘi,ｙi)である。
ｐ０->ｐ１へのベクトル：ｆ１＝（ｘ１,ｙ１）
ｐ０->ｐ２へのベクトル：ｆ２＝（ｘ２,ｙ２）
ｐ０->ｐ３へのベクトル：ｆ３＝（ｘ３,ｙ３）
ｐ０->ｐ４へのベクトル：ｆ４＝（ｘ４,ｙ４）
【００４１】
（Ｓ６２）注目特徴点ｐ０を中心として、直線ｐ０−ｂ１がｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる（図７参照）。図７によれば、特徴点ｐ１〜ｐ４全てを、注目特徴点ｐ０を中心に、時計回りに回転させる。回転は、以下の行列を、各特徴ベクトルｆiに乗算することによって表される。
【数１】
【００４２】
（Ｓ６３）注目特徴点ｐ０からｋ２番目に近傍の特徴点ｃを導出する（図７参照）。図７によれば、ｋ２＝４の例であって、注目特徴点ｐ０から４番目に近傍の特徴点ｃ（ｘｃ,ｙｃ）を選択する。ｋ２の値は、ｍ個以下の任意の数値に固定される。そして、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる（スケーリング）。子ケールの伸縮は、以下の行列を、各特徴ベクトルｆiに乗算することによって表される。
【数２】
【００４３】
（Ｓ６４）注目特徴点ｐ０について、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍが順に算出される。注目特徴点ｐ０の特徴ベクトルｆは、回転及びスケーリングを合わせて、以下の行列を、各特徴ベクトルｆiに乗算されたものとなる。
【数３】
これによって、回転及びスケーリング後の各点の座標Ｒf1，Ｒf2，・・・，Ｒfmを連結し、２×ｍ次元の特徴ベクトルを得る。
【００４４】
（Ｓ６１）次に、ｘ軸と、注目特徴点ｐ０及び特徴点ｂ２を結ぶ直線ｐ０−ｂ２との間の角度θを導出する（図８参照）。また、注目特徴点ｐ０を中心として、特徴点ｂ２から一方の回転方向（図８によれば時計回り）へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍを割り振る。
【００４５】
（Ｓ６２）注目特徴点ｐ０を中心として、直線ｐ０−ｂ２がｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる（図９参照）。図９によれば、特徴点ｐ１〜ｐ４全てを、注目特徴点ｐ０を中心に、時計回りに回転させる。
【００４６】
（Ｓ６３）注目特徴点ｐ０からｋ２（ｋ２＝４）番目に近傍の特徴点ｃ（ｘｃ,ｙｃ）を導出する（図９参照）。そして、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる。
【００４７】
（Ｓ６４）注目特徴点ｐ０について、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍが順に算出される。
【００４８】
そして、Ｓ２〜Ｓ６のステップを、ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて繰り返す。
【００４９】
尚、前述した特徴量抽出部のアルゴリズムは、以下のように表される。
for each p0∈{特徴点} do
X←p0の近傍n点の集合
for each Y∈{X内の点からm点を選ぶ全ての組み合わせ} do
q←Y内の点の中でのp0のk1近傍
r←p0とqの距離
for each B∈{Y内の点の中でPとの距離がr/ρ以上rρ以下の点(ρ≧1)}
Y及びb=(xB,yB)から特徴ベクトルを算出
end for
end for
end for
【００５０】
参照用特徴量登録部１１３は、参照用特徴量抽出部１１２から出力された特徴ベクトルを、画像識別子と共に、画像データベース１１４へ登録する。ここで、参照用特徴量登録部１１３は、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、メタデータとして、ｘ軸と直線ｐ０−ｂとの間の角度θを付加することも好ましい。また、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、メタデータとして、スケールの伸縮前の直線ｐ０−ｃの距離δを付加することも好ましい。その他、ｐ０の座標(x, y)を付加することも好ましい。尚、効率的な検索を実現するために、kd-treeやSR-tree、Locality Sensitive Hashing等の索引構造を利用することも好ましい。
【００５１】
参照画像から導出された特徴ベクトルは、画像データベースに登録される。また、クエリ画像から導出された特徴ベクトルは、特徴点検索部１２３へ入力される。
【００５２】
特徴点検索部１２３は、クエリ用特徴点抽出部１２２から入力したクエリ画像の特徴点をキーとして、画像データベース１１４に蓄積された参照画像の特徴点を検索する。特徴点検索部１２３は、クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出する。そして、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とが検索される。これによって、クエリ画像の特徴ベクトルに類似する、参照画像の特徴ベクトルを検索することができる。また、特徴点検索部１２３は、所定回数以上検索された参照画像の特徴点のみを抽出する。各特徴点からは、１つ以上の特徴ベクトルが抽出されるために、特徴ベクトルについて検索した場合、同じ特徴点が複数回検索されることとなる。ここで、所定回数以上の複数回検索された特徴点は、クエリ画像の特徴ベクトルに更に類似する、参照画像の特徴ベクトルに基づくものであると認められる。
【００５３】
投票部１２４は、投票処理によって、クエリ画像に最も類似する参照画像を検出する。
【００５４】
図１０は、本発明における投票部の処理を表すフローチャートである。
【００５５】
図１０（ａ）によれば、角度差θを用いて投票処理を実行する。
（Ｓ８）投票部１２４は、抽出された参照画像の特徴ベクトル毎に、クエリ画像の特徴ベクトルと共に付加された角度θと、当該参照画像の特徴ベクトルと共に付加された角度θとの角度差Δθを算出する。
（Ｓ９）次に、投票処理部１２４は、抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する。
（Ｓ１０）そして、投票処理部１２４は、クエリ画像の特徴ベクトルそれぞれに対して算出された参照画像の画像識別子及び角度差Δθに基づく区分角度差に応じて投票処理を行うことによって、最も類似する参照画像を検出する。
【００５６】
図１０（ｂ）によれば、距離比δを用いて投票処理を実行する。
（Ｓ８）投票部１２４は、抽出された参照画像毎に、クエリ画像の特徴ベクトルと共に付加された距離δと、当該参照画像の特徴ベクトルと共に付加された距離δとの距離比Δδを算出する。
（Ｓ９）次に、投票部１２４は、抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する。
（Ｓ１０）そして、投票部１２４は、クエリ画像の画像識別子に基づいて、複数の参照画像の画像識別子を、距離比δに基づく区分距離比に応じて投票することによって、最も類似する参照画像を検出する。
【００５７】
図１１は、本発明における投票部の概念を表す説明図である。
【００５８】
図１１によれば、画像識別子と角度差Δθとの２次元の投票テーブル上に投票される。投票テーブルは、Ｖ［ｉ］［ａ］によって表される。初期時には、投票テーブルの全ての要素は０に設定される。
ｉ：特徴点の画像識別子
ａ：角度差Δθ
ａ←floor((θ−θ’)×M/2π＋0.5) mod M
【００５９】
投票時に加えるスコアは１としてもよいが、特徴ベクトル間の距離に基づいて、特徴ベクトルの距離が近い特徴点に対するスコアを増加させることも好ましい。例えば距離がｄだけ離れている特徴ベクトルに、exp(-d2/s)（sはパラメータ）スコアを加えることも好ましい。投票後、画像IDがiの画像のスコアをmax(v[i][0], v[i][1],…, v[i][Ｍ])により算出し、画像をスコアでソートした際の、上位画像の結果を出力する。
【００６０】
以上、詳細に説明したように、本発明のプログラム、方法及び画像検索装置によれば、画像検索の際に、比較すべき画像に回転及びスケールの違いがあっても、幾何的な拘束条件を適用することよって、高い検索精度で且つ少ない計算資源で実行することができるような特徴点の特徴ベクトルを抽出する。
【００６１】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６２】
１ 画像検索装置
１０ 参照画像蓄積部
１１ 登録部
１１１ 参照用特徴点抽出部
１１２ 参照用特徴量抽出部
１１３ 参照用特徴点登録部
１１４ 画像データベース
１２ 検索部
１２１ クエリ用特徴点抽出部
１２２ クエリ用特徴量抽出部
１２３ 特徴点検索部
１２４ 投票部
【技術分野】
【０００１】
本発明は、画像検索に適した特徴ベクトルを抽出する技術に関する。
【背景技術】
【０００２】
近年、オンライン／オフラインに限られず、ストレージの大容量化に伴って、大量のコンテンツを蓄積することが可能となっている。また、携帯電話機やスマートフォンに代表される情報端末機器の普及によって、ユーザ自ら取得した写真データのようなデジタルコンテンツも、データベースに大量かつ容易に蓄積することができる。オフラインデータベースとして、ＨＤＤ(Hard Disk Drive)、ＤＶＤ(Digital Versatile Disk)、Blu-ray disc等の記憶装置がある。また、オンラインデータベースとしては、Flickr（登録商標）やMySpace（登録商標）のようなソーシャルネットワークサービスがある。これら記憶装置及びサービスによれば、データベースに蓄積された個人の大量且つ多様なマルチメディアコンテンツを検索するする技術が重要となる。
【０００３】
例えば、大量の参照画像（静止画像及び動画像）の中から、クエリ画像に類似する参照画像を高い精度で検索する技術がある（例えば非特許文献１参照）。この技術によれば、画像から大量の局所特徴ベクトルを抽出し、それらをベクトル量子化し、同一の代表ベクトルにベクトル量子化された局所特徴ベクトルの数によって類似度を算出する。しかしながら、この技術は、多くの計算資源（リソース）を必要とするという問題があった。
【０００４】
この問題に対して、できる限り少ない計算資源によって、画像を高速に検索することができる技術がある（例えば特許文献１参照）。この技術によれば、２値化された画像から特徴点を抽出し、特徴点の配置からアフィン不変な特徴ベクトルを抽出し、特徴ベクトルのマッチングに基づく投票処理によって検索する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】ＷＯ２００６／０９２９５７
【非特許文献】
【０００６】
【非特許文献１】J. Sivic et al., "Video Google: A Text Retrieval Approach toObject Matching in Videos," in Proc. ICCV, 2003.
【非特許文献２】H. Uchiyama and H. Saito, "Random dot markers," in IEEEVirtual Reality, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、前述した従来技術によれば、以下のような問題がある。
（１）特徴点に対して、高次元の特徴ベクトルを抽出しているために、多くの計算資源を必要とすると共に、近傍探索における検索精度が低下する。これは、特徴ベクトルを抽出する点集合の自由度よりも大きい次元の冗長な特徴ベクトルを抽出していることに基づく。
（２）アフィン不変な特徴ベクトルを抽出しているため、アフィン不変性が求められないような環境では、逆に検索精度が低下する。
【０００８】
そこで、本発明は、画像検索の際に、比較すべき画像に回転及びスケールの違いがあっても高い検索精度で、且つ、少ない計算資源で実行することができるような特徴点の特徴ベクトルを抽出するプログラム、方法及び画像検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明によれば、画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有するようにコンピュータを実行させることを特徴とする。
【００１０】
本発明のプログラムにおける他の実施形態によれば、
第４のステップにおける特徴ベクトルの算出について、注目特徴点ｐ０を中心として、特徴点ｂから一方の回転方向へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍを順に算出し、
特徴ベクトルｆ１〜ｆｍは、注目特徴点ｐ０から当該特徴点ｐ１〜ｐｍへのｘｙ座標ベクトルｆ(ｘi,ｙi)である
ようにコンピュータを実行させることも好ましい。
【００１１】
本発明のプログラムにおける他の実施形態によれば、
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
ｘ軸と、注目特徴点ｐ０及び特徴点ｂを結ぶ直線ｐ０−ｂとの間の角度θを導出し、
注目特徴点ｐ０を中心として、直線ｐ０−ｂがｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる
ようにコンピュータを実行させることも好ましい。
【００１２】
本発明のプログラムにおける他の実施形態によれば、
第４のステップは、更に、注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、スケールが一定となるようにスケールを伸縮させるべくコンピュータを実行させることも好ましい。
【００１３】
本発明のプログラムにおける他の実施形態によれば、
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
注目特徴点ｐ０からｋ２番目に近傍の特徴点ｃを導出し、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる
ようにコンピュータを実行させることも好ましい。
【００１４】
本発明のプログラムにおける他の実施形態によれば、
第１のステップの前段について、
特徴ベクトルの抽出対象となる注目特徴点ｐ０について、ｐ０の最も近傍に位置するｎ個の特徴点集合Ｘ（ｐ０を含まない）を抽出するステップと、
ｎ個の特徴点集合Ｘから、ｍ（ｍ≦ｎ）個の特徴点集合Ｙ（ｐ０を含まない）を選択するステップと
を有し、
ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて、第１〜第４のステップを繰り返す
ようにコンピュータを実行させることも好ましい。
【００１５】
本発明のプログラムにおける他の実施形態によれば、
第３のステップについて、注目特徴点ｐ０を中心として、距離ｒ／ρ以上（ρ≧１）から距離ｒ・ρ以下の範囲に含まれる１つ以上の特徴点Ｂを導出するようにコンピュータを実行させることも好ましい。
【００１６】
本発明のプログラムにおける他の実施形態によれば、
第４のステップについて、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、ｘ軸と直線ｐ０−ｂとの間の角度θを付加するようにコンピュータを実行させることも好ましい。
【００１７】
本発明のプログラムにおける他の実施形態によれば、
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像の特徴ベクトル毎に、クエリ画像の特徴ベクトルと共に付加された角度θと、当該参照画像の特徴ベクトルと共に付加された角度θとの角度差Δθを算出する第６ステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
クエリ画像の特徴ベクトルそれぞれに対して算出された参照画像の画像識別子及び角度差Δθに基づく区分角度差に応じて投票処理を行うことによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることを特徴とする。
【００１８】
本発明のプログラムにおける他の実施形態によれば、
第４のステップについて、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、スケールの伸縮前の直線ｐ０−ｃの距離δを付加するようにコンピュータを実行させることも好ましい。
【００１９】
本発明のプログラムにおける他の実施形態によれば、
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像毎に、クエリ画像の特徴ベクトルと共に付加された距離δと、当該参照画像の特徴ベクトルと共に付加された距離δとの距離比Δδを算出する第６のステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
クエリ画像の画像識別子に基づいて、複数の参照画像の画像識別子を、距離比δに基づく区分距離比に応じて投票することによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることも好ましい。
【００２０】
本発明によれば、装置を用いて、画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出する方法において、
画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有することを特徴とする。
【００２１】
本発明によれば、大量の参照画像を蓄積した参照画像蓄積手段を有し、クエリ画像に類似する参照画像を検索する画像検索装置において、
参照画像蓄積手段の参照画像から、ｘｙ座標の複数の特徴点を抽出する参照用特徴点抽出手段と、
参照画像の各特徴点における特徴ベクトルを抽出する参照用特徴量抽出手段と、
参照画像の各特徴点における特徴ベクトルを、画像データベースに登録する参照用特徴量登録手段と、
クエリ画像から、ｘｙ座標の複数の特徴点を抽出するクエリ用特徴点抽出手段と、
クエリ画像の各特徴点における特徴ベクトルを抽出するクエリ用特徴量抽出手段と、
クエリ画像の特徴ベクトルに類似する、参照画像の特徴ベクトルを検索する画像検索手段と
を有し、
参照用特徴量抽出手段及びクエリ用特徴量抽出手段は、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択し、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出し、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出し、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する
ことを特徴とする。
【発明の効果】
【００２２】
本発明のプログラム、方法及び画像検索装置によれば、画像検索の際に、比較すべき画像に回転及びスケールの違いがあっても高い検索精度で、且つ、少ない計算資源で実行することができるような特徴点の特徴ベクトルを抽出する。
【図面の簡単な説明】
【００２３】
【図１】画像検索装置の機能構成図である。
【図２】本発明における特徴量抽出部の処理を表すフローチャートである。
【図３】図２のＳ１における特徴点配置を表す説明図である。
【図４】図２のＳ２における特徴点配置を表す説明図である。
【図５】図２のＳ３〜Ｓ５における特徴点配置を表す説明図である。
【図６】図２のＳ６１（ｂ１）における特徴点配置を表す第１の説明図である。
【図７】図２のＳ６２及びＳ６３（ｂ１）における特徴点配置を表す第１の説明図である。
【図８】図２のＳ６１（ｂ２）における特徴点配置を表す第２の説明図である。
【図９】図２のＳ６２及びＳ６３（ｂ２）における特徴点配置を表す第２の説明図である。
【図１０】本発明における投票部の処理を表すフローチャートである。
【図１１】本発明における投票部の概念を表す説明図である。
【発明を実施するための形態】
【００２４】
以下では、本発明の実施の形態について、図面を用いて詳細に説明する。
【００２５】
図１は、画像検索装置の機能構成図である。
【００２６】
画像検索装置１は、大量の参照画像に中から、クエリ画像に類似する参照画像を検索する。図１によれば、画像検索装置１は、参照画像蓄積部１０と、登録部１１と、検索部１２とを有する。参照画像蓄積部１０は、検索対象となる大量の参照画像を蓄積しており、参照画像毎に画像識別子（ＩＤ）が付与されている。
【００２７】
登録部１１は、参照用特徴点抽出部１１１と、参照用特徴量抽出部１１２と、参照用特徴点登録部１１３と、画像データベース１１４とを有する。また、クエリ用特徴点抽出部１２１と、クエリ用特徴量抽出部１２２と、特徴点検索部１２３及び投票部１２４からなる画像検索部とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。尚、本発明は、参照用特徴量抽出部１１２及びクエリ用特徴量抽出部１２２における特徴ベクトルの抽出に特徴がある。
【００２８】
参照用特徴点抽出部１１１は、参照画像蓄積部１０から入力された参照画像から、ｘｙ座標の多数の特徴点を抽出する。また、クエリ用特徴点抽出部１２１は、入力されたクエリ画像から、ｘｙ座標の多数の特徴点を抽出する。
【００２９】
「特徴点」とは、視覚的に際立つ特徴を有する画像上のｘｙ座標点をいう。特徴点は、例えばHarris、FAST、SUSAN等のコーナー(corner：角)検出器によって抽出されるものであってもよい。コーナー検出器は、画像に写る対象物の矩形の頂点、即ち２つのエッジの交点を、特徴点として検出する。また、特許文献１に記載された技術のように、適応二値化を行い、その重心から特徴点座標を導出するものであってもよい。
【００３０】
参照用特徴点抽出部１１１によって抽出された多数の特徴点は、参照画像の画像識別子と共に、参照用特徴量抽出部１１２へ出力される。また、クエリ用特徴点抽出部１１２によって抽出された多数の特徴点は、クエリ用特徴量抽出部１２２へ出力される。
【００３１】
参照用特徴量抽出部１１２は、参照画像（画像識別子）毎に、各特徴点における特徴ベクトルを抽出する。また、クエリ用特徴量抽出部１２２は、クエリ画像について、各特徴点における特徴ベクトルを抽出する。本発明によれば、各特徴点について、注目特徴点の近傍に位置する他の特徴点の配置に基づいて、回転及びスケールに不変で且つ低次元な特徴ベクトルを抽出する。画像検索の際に、回転及びスケールに不変な特徴ベクトルを用いることによって、回転及びスケールの違い対する画像に対しても精度高く検索することができる。また、低次元な特徴ベクトルを用いることによって、少ない計算資源で画像検索を実行することができる。
【００３２】
図２は、本発明の特徴量抽出部における特徴ベクトルの抽出処理を表すフローチャートである。
【００３３】
（Ｓ１）特徴ベクトルの抽出対象となる注目特徴点ｐ０について、注目特徴点ｐ０の最も近傍に位置するｎ個の特徴点集合Ｘ（注目特徴点ｐ０を含まない）を抽出する（図３参照）。図３によれば、ｎ＝５の例であって、注目特徴点ｐ０の最も近傍に位置する５個の特徴点集合Ｘが抽出されている。
【００３４】
（Ｓ２）ｎ個の特徴点集合Ｘから、注目特徴点ｐ０を含まないｍ（ｍ≦ｎ）個の特徴点集合Ｙを選択する（図４参照）。図４によれば、ｍ＝４の例であって、注目特徴点ｐ０を含まない４個の特徴点集合Ｙが選択されている。Ｓ２〜Ｓ６のステップを、ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて繰り返す。
【００３５】
（Ｓ３）特徴点集合Ｙについて、注目特徴点ｐ０からｋ１番目に近傍の特徴点ｑを選択する（図５参照）。図５によれば、ｋ１＝１の例であって、注目特徴点ｐ０から１番目に近傍の特徴点ｑを選択する。ｋ１の値は、ｍ個以下の任意の数値に固定される。
【００３６】
（Ｓ４）注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する（図５参照）。
【００３７】
（Ｓ５）注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する（図５参照）。ここで、所定長の近傍について、注目特徴点ｐ０を中心として、距離ｒ／ρ以上（ρ≧１）から距離ｒ・ρ以下の範囲に含まれる１つ以上の特徴点Ｂを導出する。図５によれば、２個の特徴点ｂが導出されている。
【００３８】
（Ｓ６）注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度及びスケールが一定となるように回転させ且つスケールを伸縮させる。そして、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する。図５によれば、特徴点集合Ｂの各特徴点ｂ１，ｂ２について、以下の処理を実行する。
【００３９】
（Ｓ６１）ｘ軸と、注目特徴点ｐ０及び特徴点ｂ１を結ぶ直線ｐ０−ｂ１との間の角度θ（０≦θ＜２π）を導出する（図６参照）。また、注目特徴点ｐ０を中心として、特徴点ｂ１から一方の回転方向（図６によれば反時計回り）へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍを割り振る。
【００４０】
特徴ベクトルｆ１〜ｆｍは、注目特徴点ｐ０から当該特徴点ｐ１〜ｐｍへのｘｙ座標ベクトルｆ(ｘi,ｙi)である。
ｐ０->ｐ１へのベクトル：ｆ１＝（ｘ１,ｙ１）
ｐ０->ｐ２へのベクトル：ｆ２＝（ｘ２,ｙ２）
ｐ０->ｐ３へのベクトル：ｆ３＝（ｘ３,ｙ３）
ｐ０->ｐ４へのベクトル：ｆ４＝（ｘ４,ｙ４）
【００４１】
（Ｓ６２）注目特徴点ｐ０を中心として、直線ｐ０−ｂ１がｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる（図７参照）。図７によれば、特徴点ｐ１〜ｐ４全てを、注目特徴点ｐ０を中心に、時計回りに回転させる。回転は、以下の行列を、各特徴ベクトルｆiに乗算することによって表される。
【数１】
【００４２】
（Ｓ６３）注目特徴点ｐ０からｋ２番目に近傍の特徴点ｃを導出する（図７参照）。図７によれば、ｋ２＝４の例であって、注目特徴点ｐ０から４番目に近傍の特徴点ｃ（ｘｃ,ｙｃ）を選択する。ｋ２の値は、ｍ個以下の任意の数値に固定される。そして、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる（スケーリング）。子ケールの伸縮は、以下の行列を、各特徴ベクトルｆiに乗算することによって表される。
【数２】
【００４３】
（Ｓ６４）注目特徴点ｐ０について、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍが順に算出される。注目特徴点ｐ０の特徴ベクトルｆは、回転及びスケーリングを合わせて、以下の行列を、各特徴ベクトルｆiに乗算されたものとなる。
【数３】
これによって、回転及びスケーリング後の各点の座標Ｒf1，Ｒf2，・・・，Ｒfmを連結し、２×ｍ次元の特徴ベクトルを得る。
【００４４】
（Ｓ６１）次に、ｘ軸と、注目特徴点ｐ０及び特徴点ｂ２を結ぶ直線ｐ０−ｂ２との間の角度θを導出する（図８参照）。また、注目特徴点ｐ０を中心として、特徴点ｂ２から一方の回転方向（図８によれば時計回り）へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍを割り振る。
【００４５】
（Ｓ６２）注目特徴点ｐ０を中心として、直線ｐ０−ｂ２がｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる（図９参照）。図９によれば、特徴点ｐ１〜ｐ４全てを、注目特徴点ｐ０を中心に、時計回りに回転させる。
【００４６】
（Ｓ６３）注目特徴点ｐ０からｋ２（ｋ２＝４）番目に近傍の特徴点ｃ（ｘｃ,ｙｃ）を導出する（図９参照）。そして、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる。
【００４７】
（Ｓ６４）注目特徴点ｐ０について、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍが順に算出される。
【００４８】
そして、Ｓ２〜Ｓ６のステップを、ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて繰り返す。
【００４９】
尚、前述した特徴量抽出部のアルゴリズムは、以下のように表される。
for each p0∈{特徴点} do
X←p0の近傍n点の集合
for each Y∈{X内の点からm点を選ぶ全ての組み合わせ} do
q←Y内の点の中でのp0のk1近傍
r←p0とqの距離
for each B∈{Y内の点の中でPとの距離がr/ρ以上rρ以下の点(ρ≧1)}
Y及びb=(xB,yB)から特徴ベクトルを算出
end for
end for
end for
【００５０】
参照用特徴量登録部１１３は、参照用特徴量抽出部１１２から出力された特徴ベクトルを、画像識別子と共に、画像データベース１１４へ登録する。ここで、参照用特徴量登録部１１３は、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、メタデータとして、ｘ軸と直線ｐ０−ｂとの間の角度θを付加することも好ましい。また、注目特徴点ｐ０に対して、特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、メタデータとして、スケールの伸縮前の直線ｐ０−ｃの距離δを付加することも好ましい。その他、ｐ０の座標(x, y)を付加することも好ましい。尚、効率的な検索を実現するために、kd-treeやSR-tree、Locality Sensitive Hashing等の索引構造を利用することも好ましい。
【００５１】
参照画像から導出された特徴ベクトルは、画像データベースに登録される。また、クエリ画像から導出された特徴ベクトルは、特徴点検索部１２３へ入力される。
【００５２】
特徴点検索部１２３は、クエリ用特徴点抽出部１２２から入力したクエリ画像の特徴点をキーとして、画像データベース１１４に蓄積された参照画像の特徴点を検索する。特徴点検索部１２３は、クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出する。そして、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とが検索される。これによって、クエリ画像の特徴ベクトルに類似する、参照画像の特徴ベクトルを検索することができる。また、特徴点検索部１２３は、所定回数以上検索された参照画像の特徴点のみを抽出する。各特徴点からは、１つ以上の特徴ベクトルが抽出されるために、特徴ベクトルについて検索した場合、同じ特徴点が複数回検索されることとなる。ここで、所定回数以上の複数回検索された特徴点は、クエリ画像の特徴ベクトルに更に類似する、参照画像の特徴ベクトルに基づくものであると認められる。
【００５３】
投票部１２４は、投票処理によって、クエリ画像に最も類似する参照画像を検出する。
【００５４】
図１０は、本発明における投票部の処理を表すフローチャートである。
【００５５】
図１０（ａ）によれば、角度差θを用いて投票処理を実行する。
（Ｓ８）投票部１２４は、抽出された参照画像の特徴ベクトル毎に、クエリ画像の特徴ベクトルと共に付加された角度θと、当該参照画像の特徴ベクトルと共に付加された角度θとの角度差Δθを算出する。
（Ｓ９）次に、投票処理部１２４は、抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する。
（Ｓ１０）そして、投票処理部１２４は、クエリ画像の特徴ベクトルそれぞれに対して算出された参照画像の画像識別子及び角度差Δθに基づく区分角度差に応じて投票処理を行うことによって、最も類似する参照画像を検出する。
【００５６】
図１０（ｂ）によれば、距離比δを用いて投票処理を実行する。
（Ｓ８）投票部１２４は、抽出された参照画像毎に、クエリ画像の特徴ベクトルと共に付加された距離δと、当該参照画像の特徴ベクトルと共に付加された距離δとの距離比Δδを算出する。
（Ｓ９）次に、投票部１２４は、抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する。
（Ｓ１０）そして、投票部１２４は、クエリ画像の画像識別子に基づいて、複数の参照画像の画像識別子を、距離比δに基づく区分距離比に応じて投票することによって、最も類似する参照画像を検出する。
【００５７】
図１１は、本発明における投票部の概念を表す説明図である。
【００５８】
図１１によれば、画像識別子と角度差Δθとの２次元の投票テーブル上に投票される。投票テーブルは、Ｖ［ｉ］［ａ］によって表される。初期時には、投票テーブルの全ての要素は０に設定される。
ｉ：特徴点の画像識別子
ａ：角度差Δθ
ａ←floor((θ−θ’)×M/2π＋0.5) mod M
【００５９】
投票時に加えるスコアは１としてもよいが、特徴ベクトル間の距離に基づいて、特徴ベクトルの距離が近い特徴点に対するスコアを増加させることも好ましい。例えば距離がｄだけ離れている特徴ベクトルに、exp(-d2/s)（sはパラメータ）スコアを加えることも好ましい。投票後、画像IDがiの画像のスコアをmax(v[i][0], v[i][1],…, v[i][Ｍ])により算出し、画像をスコアでソートした際の、上位画像の結果を出力する。
【００６０】
以上、詳細に説明したように、本発明のプログラム、方法及び画像検索装置によれば、画像検索の際に、比較すべき画像に回転及びスケールの違いがあっても、幾何的な拘束条件を適用することよって、高い検索精度で且つ少ない計算資源で実行することができるような特徴点の特徴ベクトルを抽出する。
【００６１】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【符号の説明】
【００６２】
１ 画像検索装置
１０ 参照画像蓄積部
１１ 登録部
１１１ 参照用特徴点抽出部
１１２ 参照用特徴量抽出部
１１３ 参照用特徴点登録部
１１４ 画像データベース
１２ 検索部
１２１ クエリ用特徴点抽出部
１２２ クエリ用特徴量抽出部
１２３ 特徴点検索部
１２４ 投票部
【特許請求の範囲】
【請求項１】
画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有するようにコンピュータを実行させることを特徴とするプログラム。
【請求項２】
第４のステップにおける特徴ベクトルの算出について、注目特徴点ｐ０を中心として、特徴点ｂから一方の回転方向へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍを順に算出し、
前記特徴ベクトルｆ１〜ｆｍは、注目特徴点ｐ０から当該特徴点ｐ１〜ｐｍへのｘｙ座標ベクトルｆ(ｘi,ｙi)である
ようにコンピュータを実行させることを特徴とする請求項１に記載のプログラム。
【請求項３】
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
ｘ軸と、注目特徴点ｐ０及び特徴点ｂを結ぶ直線ｐ０−ｂとの間の角度θを導出し、
注目特徴点ｐ０を中心として、直線ｐ０−ｂがｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる
ようにコンピュータを実行させることを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
第４のステップは、更に、注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、スケールが一定となるようにスケールを伸縮させるべくコンピュータを実行させることを特徴とする請求項１から３のいずれか１項に記載のプログラム。
【請求項５】
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
注目特徴点ｐ０からｋ２番目に近傍の特徴点ｃを導出し、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる
ようにコンピュータを実行させることを特徴とする請求項４に記載のプログラム。
【請求項６】
第１のステップの前段について、
特徴ベクトルの抽出対象となる注目特徴点ｐ０について、ｐ０の最も近傍に位置するｎ個の特徴点集合Ｘ（ｐ０を含まない）を抽出するステップと、
ｎ個の特徴点集合Ｘから、ｍ（ｍ≦ｎ）個の特徴点集合Ｙ（ｐ０を含まない）を選択するステップと
を有し、
ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて、第１〜第４のステップを繰り返す
ようにコンピュータを実行させることを特徴とする請求項１から５のいずれか１項に記載のプログラム。
【請求項７】
第３のステップについて、注目特徴点ｐ０を中心として、距離ｒ／ρ以上（ρ≧１）から距離ｒ・ρ以下の範囲に含まれる１つ以上の特徴点Ｂを導出するようにコンピュータを実行させることを特徴とする請求項１から６のいずれか１項に記載のプログラム。
【請求項８】
第４のステップについて、注目特徴点ｐ０に対して、前記特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、ｘ軸と直線ｐ０−ｂとの間の角度θを付加するようにコンピュータを実行させることを特徴とする請求項１から７のいずれか１項に記載のプログラム。
【請求項９】
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像の特徴ベクトル毎に、クエリ画像の特徴ベクトルと共に付加された角度θと、当該参照画像の特徴ベクトルと共に付加された角度θとの角度差Δθを算出する第６ステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
前記クエリ画像の特徴ベクトルそれぞれに対して算出された参照画像の画像識別子及び前記角度差Δθに基づく区分角度差に応じて投票処理を行うことによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることを特徴とする請求項８に記載のプログラム。
【請求項１０】
第４のステップについて、注目特徴点ｐ０に対して、前記特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、スケールの伸縮前の直線ｐ０−ｃの距離δを付加するようにコンピュータを実行させることを特徴とする請求項１から７のいずれか１項に記載のプログラム。
【請求項１１】
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像毎に、クエリ画像の特徴ベクトルと共に付加された距離δと、当該参照画像の特徴ベクトルと共に付加された距離δとの距離比Δδを算出する第６のステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
前記クエリ画像の画像識別子に基づいて、複数の参照画像の画像識別子を、前記距離比δに基づく区分距離比に応じて投票することによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることを特徴とする請求項１０に記載のプログラム。
【請求項１２】
装置を用いて、画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出する方法において、
画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有することを特徴とする方法。
【請求項１３】
大量の参照画像を蓄積した参照画像蓄積手段を有し、クエリ画像に類似する参照画像を検索する画像検索装置において、
前記参照画像蓄積手段の参照画像から、ｘｙ座標の複数の特徴点を抽出する参照用特徴点抽出手段と、
前記参照画像の各特徴点における特徴ベクトルを抽出する参照用特徴量抽出手段と、
前記参照画像の各特徴点における特徴ベクトルを、画像データベースに登録する参照用特徴量登録手段と、
前記クエリ画像から、ｘｙ座標の複数の特徴点を抽出するクエリ用特徴点抽出手段と、
前記クエリ画像の各特徴点における特徴ベクトルを抽出するクエリ用特徴量抽出手段と、
クエリ画像の特徴ベクトルに類似する、参照画像の特徴ベクトルを検索する画像検索手段と
を有し、
前記参照用特徴量抽出手段及び前記クエリ用特徴量抽出手段は、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択し、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出し、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出し、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する
ことを特徴とする画像検索装置。
【請求項１】
画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有するようにコンピュータを実行させることを特徴とするプログラム。
【請求項２】
第４のステップにおける特徴ベクトルの算出について、注目特徴点ｐ０を中心として、特徴点ｂから一方の回転方向へ、特徴点集合Ｙの各特徴点ｐ１〜ｐｍの特徴ベクトルｆ１〜ｆｍを順に算出し、
前記特徴ベクトルｆ１〜ｆｍは、注目特徴点ｐ０から当該特徴点ｐ１〜ｐｍへのｘｙ座標ベクトルｆ(ｘi,ｙi)である
ようにコンピュータを実行させることを特徴とする請求項１に記載のプログラム。
【請求項３】
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
ｘ軸と、注目特徴点ｐ０及び特徴点ｂを結ぶ直線ｐ０−ｂとの間の角度θを導出し、
注目特徴点ｐ０を中心として、直線ｐ０−ｂがｘ軸に重なるように、ｍ個全ての特徴点集合Ｙを回転させる
ようにコンピュータを実行させることを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
第４のステップは、更に、注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、スケールが一定となるようにスケールを伸縮させるべくコンピュータを実行させることを特徴とする請求項１から３のいずれか１項に記載のプログラム。
【請求項５】
第４のステップは、特徴点集合Ｂの各特徴点ｂについて、
注目特徴点ｐ０からｋ２番目に近傍の特徴点ｃを導出し、注目特徴点ｐ０及び特徴点ｃを結ぶ直線ｐ０−ｃのスケールが単位長（１）となるように、注目特徴点ｐ０から見たｍ個全ての特徴点集合Ｙのスケールを伸縮させる
ようにコンピュータを実行させることを特徴とする請求項４に記載のプログラム。
【請求項６】
第１のステップの前段について、
特徴ベクトルの抽出対象となる注目特徴点ｐ０について、ｐ０の最も近傍に位置するｎ個の特徴点集合Ｘ（ｐ０を含まない）を抽出するステップと、
ｎ個の特徴点集合Ｘから、ｍ（ｍ≦ｎ）個の特徴点集合Ｙ（ｐ０を含まない）を選択するステップと
を有し、
ｎ個の特徴点集合Ｘからｍ個の特徴点集合Ｙの全ての組み合わせについて、第１〜第４のステップを繰り返す
ようにコンピュータを実行させることを特徴とする請求項１から５のいずれか１項に記載のプログラム。
【請求項７】
第３のステップについて、注目特徴点ｐ０を中心として、距離ｒ／ρ以上（ρ≧１）から距離ｒ・ρ以下の範囲に含まれる１つ以上の特徴点Ｂを導出するようにコンピュータを実行させることを特徴とする請求項１から６のいずれか１項に記載のプログラム。
【請求項８】
第４のステップについて、注目特徴点ｐ０に対して、前記特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、ｘ軸と直線ｐ０−ｂとの間の角度θを付加するようにコンピュータを実行させることを特徴とする請求項１から７のいずれか１項に記載のプログラム。
【請求項９】
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴点に対応する特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像の特徴ベクトル毎に、クエリ画像の特徴ベクトルと共に付加された角度θと、当該参照画像の特徴ベクトルと共に付加された角度θとの角度差Δθを算出する第６ステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
前記クエリ画像の特徴ベクトルそれぞれに対して算出された参照画像の画像識別子及び前記角度差Δθに基づく区分角度差に応じて投票処理を行うことによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることを特徴とする請求項８に記載のプログラム。
【請求項１０】
第４のステップについて、注目特徴点ｐ０に対して、前記特徴ベクトルｆ１〜ｆｍ及び画像識別子に加えて、スケールの伸縮前の直線ｐ０−ｃの距離δを付加するようにコンピュータを実行させることを特徴とする請求項１から７のいずれか１項に記載のプログラム。
【請求項１１】
多数の参照画像に中から、クエリ画像を用いて、参照画像を検索するために、
参照画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像に対して、第１〜第４のステップによって特徴ベクトルを導出し、
クエリ画像の特徴点の特徴ベクトルと、各参照画像の特徴点の特徴ベクトルとの間の距離を算出し、所定距離以下又は所定個数以内の参照画像の特徴ベクトルとその特徴ベクトルに対応する特徴点とを検索し、所定回数以上検索された参照画像の特徴点を抽出する第５のステップと、
抽出された参照画像毎に、クエリ画像の特徴ベクトルと共に付加された距離δと、当該参照画像の特徴ベクトルと共に付加された距離δとの距離比Δδを算出する第６のステップと、
抽出された参照画像の特徴ベクトル毎に参照画像の画像識別子を抽出する第７のステップと、
前記クエリ画像の画像識別子に基づいて、複数の参照画像の画像識別子を、前記距離比δに基づく区分距離比に応じて投票することによって、最も類似する参照画像を検出する第８のステップと
してコンピュータを実行させることを特徴とする請求項１０に記載のプログラム。
【請求項１２】
装置を用いて、画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出する方法において、
画像から抽出されたｘｙ座標の各特徴点の特徴ベクトルを抽出するようにコンピュータを実行させるプログラムにおいて、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択する第１のステップと、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出する第２のステップと、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出する第３のステップと、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する第４のステップと
を有することを特徴とする方法。
【請求項１３】
大量の参照画像を蓄積した参照画像蓄積手段を有し、クエリ画像に類似する参照画像を検索する画像検索装置において、
前記参照画像蓄積手段の参照画像から、ｘｙ座標の複数の特徴点を抽出する参照用特徴点抽出手段と、
前記参照画像の各特徴点における特徴ベクトルを抽出する参照用特徴量抽出手段と、
前記参照画像の各特徴点における特徴ベクトルを、画像データベースに登録する参照用特徴量登録手段と、
前記クエリ画像から、ｘｙ座標の複数の特徴点を抽出するクエリ用特徴点抽出手段と、
前記クエリ画像の各特徴点における特徴ベクトルを抽出するクエリ用特徴量抽出手段と、
クエリ画像の特徴ベクトルに類似する、参照画像の特徴ベクトルを検索する画像検索手段と
を有し、
前記参照用特徴量抽出手段及び前記クエリ用特徴量抽出手段は、
注目特徴点ｐ０及びｍ個の特徴点集合について、ｐ０からｋ１番目に近傍の特徴点ｑを選択し、
注目特徴点ｐ０及び特徴点ｑを結ぶ直線ｐ０−ｑの距離ｒを導出し、
注目特徴点ｐ０を中心とし且つ距離ｒを半径とした円周から、所定長の近傍に含まれる１つ以上の特徴点集合Ｂを導出し、
注目特徴点ｐ０と特徴点集合Ｂの各特徴点ｂとについて、角度が一定となるように回転させて、ｍ個全ての特徴点を用いて、注目特徴点ｐ０の特徴ベクトルｆを算出する
ことを特徴とする画像検索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１３−８９０７９（Ｐ２０１３−８９０７９Ａ）
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願番号】特願２０１１−２２９８８１（Ｐ２０１１−２２９８８１）
【出願日】平成２３年１０月１９日（２０１１．１０．１９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２５年５月１３日（２０１３．５．１３）
【国際特許分類】
【出願日】平成２３年１０月１９日（２０１１．１０．１９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]