(57)【特許請求の範囲】
【請求項１】
画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力する特徴点検出部と、
前記特徴点情報に基づいて、検出された前記複数の特徴点の中から、重要度順に所定数の特徴点を選定する特徴点選定部と、
選定された各特徴点に対する局所領域を取得する局所領域取得部と、
各局所領域を複数のサブ領域に分割するサブ領域分割部と、
各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成するサブ領域特徴ベクトル生成部と、
各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに前記特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する次元選定部と、
を備える局所特徴量抽出装置。
【請求項２】
請求項１に記載の局所特徴量抽出装置であって、
前記特徴点選定部において選定される特徴点数、および、前記次元選定部において選定される次元数を決定する選定数決定部をさらに備える、
局所特徴量抽出装置。
【請求項３】
請求項２に記載の局所特徴量抽出装置であって、
前記選定数決定部は、前記選定された特徴点の特徴量の合計サイズを指定するための情報である指定特徴量サイズ情報を受け付け、該指定特徴量サイズ情報に基づいて前記特徴点数及び前記次元数を決定する、
局所特徴量抽出装置。
【請求項４】
請求項３に記載の局所特徴量抽出装置であって、
前記選定数決定部は、前記合計サイズ及び前記次元数の対応関係を示す情報と、前記指定特徴量サイズ情報とに基づいて、前記特徴点数及び前記次元数を決定する、
局所特徴量抽出装置。
【請求項５】
請求項３に記載の局所特徴量抽出装置であって、
前記選定数決定部は、前記合計サイズ及び前記特徴点数の対応関係を示す情報と、前記指定特徴量サイズ情報とに基づいて、前記特徴点数及び前記次元数を決定する、
局所特徴量抽出装置。
【請求項６】
請求項３に記載の局所特徴量抽出装置であって、
前記選定数決定部は、前記合計サイズ、前記特徴点数、及び前記次元数の対応関係を示す情報と、前記指定特徴量サイズ情報とに基づいて、前記特徴点数及び前記次元数を決定する、
局所特徴量抽出装置。
【請求項７】
請求項１に記載の局所特徴量抽出装置であって、
前記特徴点選定部における特徴点の選定結果を示す選定結果情報該を受け付け、該選定結果情報に基づいて前記次元数を決定する選定数決定部をさらに備える、
局所特徴量抽出装置。
【請求項８】
請求項７に記載の局所特徴量抽出装置であって、
前記選定結果情報には、選定された特徴点ごとの重要度を示す重要度情報が含まれ、
前記選定数決定部は、前記重要度情報に基づいて、選定された特徴点ごとに前記次元数を決定する、
局所特徴量抽出装置。
【請求項９】
コンピュータが、
画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力し、
前記特徴点情報に基づいて、検出された前記複数の特徴点の中から、重要度順に所定数の特徴点を選定し、
選定された各特徴点に対する局所領域を取得し、
各局所領域を複数のサブ領域に分割し、
各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成し、
各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに前記特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する、
局所特徴量抽出方法。
【請求項１０】
コンピュータに、
画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力する機能と、
前記特徴点情報に基づいて、検出された前記複数の特徴点の中から、重要度順に所定数の特徴点を選定する機能と、
選定された各特徴点に対する局所領域を取得する機能と、
各局所領域を複数のサブ領域に分割する機能と、
各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成する機能と、
各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに前記特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する機能と、
を実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、局所特徴量抽出装置、局所特徴量抽出方法、及びプログラムに関する。
【背景技術】
【０００２】
画像内の被写体を、撮影サイズや角度の変化、オクルージョンに対して頑健に識別可能とするために、画像内の特徴的な点（特徴点）を多数検出し、各特徴点周辺の局所領域の特徴量（局所特徴量）を抽出する方式が提案されている。その代表的な方式として、特許文献１や非特許文献１には、ＳＩＦＴ（Ｓｃａｌｅ  Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍ）特徴量を用いる局所特徴量抽出装置が開示されている。【０００３】
図２３は、ＳＩＦＴ特徴量を用いる局所特徴量抽出装置の一般的な構成の一例を示す図である。また、図２４は、図２３に示した局所特徴量抽出装置におけるＳＩＦＴ特徴量の抽出のイメージを示す図である。【０００４】
図２３に示すように、局所特徴量抽出装置は、特徴点検出部２００、局所領域取得部２１０、サブ領域分割部２２０、及びサブ領域特徴ベクトル生成部２３０を備えている。特徴点検出部２００は、画像から特徴的な点（特徴点）を多数検出し、各特徴点の座標位置、スケール（大きさ）、及び角度を出力する。局所領域取得部２１０は、検出された各特徴点の座標値、スケール、及び角度から、特徴量抽出を行う局所領域を取得する。サブ領域分割部２２０は、局所領域をサブ領域に分割する。図２４に示す例では、サブ領域分割部２２０は、局所領域を１６ブロック（４×４ブロック）に分割している。サブ領域特徴ベクトル生成部２３０は、局所領域のサブ領域ごとに勾配方向ヒストグラムを生成する。具体的には、サブ領域特徴ベクトル生成部２３０は、各サブ領域の画素ごとに勾配方向を算出し、それを８方向に量子化する。なお、ここで求める勾配方向は、特徴点検出部２００が出力する各特徴点の角度に対する相対的な方向である。すなわち、特徴点検出部２００が出力する角度に対して正規化された方向である。そして、サブ領域特徴ベクトル生成部２３０は、サブ領域ごとに量子化された８方向の頻度を集計し、勾配方向ヒストグラムを生成する。こうして、各特徴点に対して生成される１６ブロック×８方向の勾配方向ヒストグラムが、１２８次元の局所特徴量として出力される。【０００５】
また、特許文献２には、局所特徴量を用いた検索精度や認識精度を向上させるために、画像の回転や拡大、縮小等が行われても抽出される再現性が高い特徴点に、局所特徴量の算出対象を絞る手法が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許第６７１１２９３号明細書
【特許文献２】特開２０１０−７９５４５号公報
【非特許文献】
【０００７】
【非特許文献１】David G. Lowe著、「Distinctive image features from scale-invariant keypoints」、（米国）、International Journal of Computer Vision、60(2)、2004年、p. 91-110
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述した局所特徴量は、そのサイズが大きくなってしまうという問題点がある。例えば、ＳＩＦＴ特徴量の場合、各次元のヒストグラム値を１バイトであらわすこととすると、１２８次元×１バイトのサイズが必要となる。また、特許文献１や非特許文献１に開示されている手法では、入力画像から抽出される全ての特徴点に対し局所特徴量の生成が行われている。そのため、検出された特徴点の数が増加するにつれて、生成される局所特徴量のサイズが大きくなってしまうこととなる。【０００９】
このように局所特徴量のサイズが大きくなってしまうと、画像の照合（マッチング）のために局所特徴量を用いる場合に問題が生じることがある。例えば、ユーザ端末（例えばカメラ付きの携帯端末など）が、画像から局所特徴量を抽出し、当該画像に類似する画像を検索するために局所特徴量をサーバに送信する場合、局所特徴量のサイズが大きいと通信時間が長くなってしまう。そのため、画像の検索結果が得られるまでの時間が長くなってしまう。また、局所特徴量のサイズが大きいと、画像の局所特徴量を照合する際の処理時間が長くなってしまう。また、局所特徴量を用いた画像検索の場合、画像の局所特徴量をメモリ上に格納することとなるが、局所特徴量のサイズが大きいとメモリ上に局所特徴量を格納可能な画像数が少なくなってしまう。そのため、大量の画像を対象とする大規模検索には適さないこととなる。【００１０】
また、特許文献２に開示されている手法では、局所特徴量の算出対象を、再現性の高い特徴点に絞ることはできるものの、再現性の高い特徴点の数が多い場合には、特許文献１や非特許文献１に開示されている手法と同様の問題が生じることとなる。【００１１】
そこで、本発明は、被写体識別の精度を維持しつつ、特徴量のサイズを小さくすることを目的とする。
【課題を解決するための手段】
【００１２】
本発明の一側面に係る局所特徴量抽出装置は、画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力する特徴点検出部と、特徴点情報に基づいて、検出された複数の特徴点の中から、重要度順に所定数の特徴点を選定する特徴点選定部と、選定された各特徴点に対する局所領域を取得する局所領域取得部と、各局所領域を複数のサブ領域に分割するサブ領域分割部と、各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成するサブ領域特徴ベクトル生成部と、各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する次元選定部と、を備える。【００１３】
また、本発明の一側面に係る局所特徴量抽出方法では、コンピュータが、画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力し、特徴点情報に基づいて、検出された複数の特徴点の中から、重要度順に所定数の特徴点を選定し、選定された各特徴点に対する局所領域を取得し、各局所領域を複数のサブ領域に分割し、各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成し、各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する。【００１４】
また、本発明の一側面に係るプログラムは、コンピュータに、画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力する機能と、特徴点情報に基づいて、検出された複数の特徴点の中から、重要度順に所定数の特徴点を選定する機能と、選定された各特徴点に対する局所領域を取得する機能と、各局所領域を複数のサブ領域に分割する機能と、各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成する機能と、各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する機能と、を実現させるためのものである。【００１５】
なお、本発明において、「部」とは、単に物理的手段を意味するものではなく、その「部」が有する機能をソフトウェアによって実現する場合も含む。また、１つの「部」や装置が有する機能が２つ以上の物理的手段や装置により実現されても、２つ以上の「部」や装置の機能が１つの物理的手段や装置により実現されてもよい。
【発明の効果】
【００１６】
本発明によれば、被写体識別の精度を維持しつつ、特徴量のサイズを小さくすることが可能となる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施形態である局所特徴量抽出装置の構成を示す図である。
【図２】特徴点選定部の構成例を示す図である。
【図３】特徴点選定部の構成例を示す図である。
【図４】特徴点選定部の構成例を示す図である。
【図５】特徴点選定部の構成例を示す図である。
【図６】１２８次元の特徴ベクトルから次元を選定する場合の一例を示す図である。
【図７】次元選定の別の一例を示す図である。
【図８】次元を選定する際の優先順位の一例を示す図である。
【図９】勾配方向ヒストグラムの次元の優先順位の一例を示す図である。
【図１０】優先順位に従って出力される局所特徴量の構成例を示す図である。
【図１１】次元を選定する際の優先順位の一例を示す図である。
【図１２】次元選定の別の一例を示す図である。
【図１３】円状の局所領域の一例を示す図である。
【図１４】円状の局所領域における次元選定の一例を示す図である。
【図１５】局所特徴量抽出装置における処理の一例を示すフローチャートである。
【図１６】本発明の第２の実施形態における局所特徴量抽出装置の構成を示す図である。
【図１７】本発明の第３の実施形態における局所特徴量抽出装置の構成を示す図である。
【図１８】指定特徴量サイズと次元数との対応関係の一例を示す図である。
【図１９】本発明の第４の実施形態における局所特徴量抽出装置の構成を示す図である。
【図２０】本発明の第５の実施形態における局所特徴量抽出装置の構成を示す図である。
【図２１】局所特徴量抽出装置を適用可能な照合システムの一例を示す図である。
【図２２】照合装置における、局所特徴量を用いた照合の一例を示す図である。
【図２３】ＳＩＦＴ特徴量を用いる局所特徴量抽出装置の一般的な構成の一例を示す図である。
【図２４】局所特徴量抽出装置におけるＳＩＦＴ特徴量の抽出のイメージを示す図である。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施形態について説明する。
【００１９】
＝＝第１の実施形態＝＝
図１は、本発明の第１の実施形態である局所特徴量抽出装置の構成を示す図である。局所特徴量抽出装置１Ａは、特徴点検出部１０、特徴点選定部１２、及び局所特徴量生成部１４を含んで構成される。局所特徴量抽出装置１Ａは、例えば、パーソナルコンピュータや携帯情報端末等の情報処理装置を用いて構成することができる。そして、局所特徴量抽出装置１Ａを構成する各部は、例えば、メモリ等の記憶領域を用いたり、記憶領域に格納されているプログラムをプロセッサが実行したりすることにより実現することができる。なお、後述する他の実施形態における構成要素についても同様に実現することができる。
【００２０】
特徴点検出部１０は、画像から特徴的な点（特徴点）を多数検出し、各特徴点に関する情報である特徴点情報を出力する。ここで、特徴点情報とは、例えば、検出された特徴点の座標位置やスケール、特徴点のオリエンテーション、特徴点に対して割り当てられた固有のＩＤ（Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）である「特徴点番号」等を示すものである。
【００２１】
なお、特徴点検出部１０は、特徴点情報を、各特徴点のオリエンテーションの方向毎に別々の特徴点情報として出力しても良い。例えば、特徴点検出部１０は、各特徴点における最も主たるオリエンテーションの方向についてのみ特徴点情報を出力することとしてもよいし、２番目以降の主たるオリエンテーションの方向についての特徴点情報も出力することとしてもよい。また、特徴点検出部１０は、２番目以降の主たるオリエンテーションの方向についての特徴点情報も出力する場合、各特徴点におけるオリエンテーションの方向ごとに異なる特徴点番号を付与することができる。
【００２２】
特徴点の検出対象となる画像は、静止画または動画（ショートクリップを含む。）の何れであってもよく、例えば、デジタルカメラやデジタルビデオカメラ、携帯電話等の撮像機器で撮影された画像や、スキャナー等を通して取り込まれた画像などである。
【００２３】
また、画像は、ＪＰＥＧ（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）のように圧縮された画像であってもよいし、ＴＩＦＦ（Ｔａｇｇｅｄ  Ｉｍａｇｅ  Ｆｉｌｅ  Ｆｏｒｍａｔ）のように圧縮されていない画像であってもよい。
【００２４】
また、画像は、圧縮された動画あるいはそれを復号した動画でも良い。なお、画像が動画である場合、特徴点検出部１０は、動画を構成するフレーム画像毎に特徴点の検出を行うことができる。また、画像が、圧縮された動画である場合、その圧縮形式は、ＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）、ＭＯＴＩＯＮ  ＪＰＥＧ、ＷＩＮＤＯＷＳ Ｍｅｄｉａ Ｖｉｄｅｏ（ＷＩＮＤＯＷＳ、ＷＩＮＤＯＷＳ Ｍｅｄｉａは登録商標）等、復号可能な形式であれば何でもよい。
【００２５】
特徴点検出部１０は、画像から特徴点を検出して特徴点情報を抽出する際に、例えば、ＤｏＧ（Ｄｉｆｆｅｒｅｎｃｅ−ｏｆ−Ｇａｕｓｓｉａｎ）処理を用いることができる。具体的には、特徴点検出部１０は、ＤｏＧ処理を用いてスケールスペースにおける極値探索をすることで特徴点の位置とスケールを決定することができる。さらに特徴点検出部１０は、決定した特徴点の位置およびスケールと周辺領域の勾配情報とを用いて各特徴点のオリエンテーションを算出することができる。なお、特徴点検出部１０は、画像から特徴点を検出して特徴点情報を抽出する際に、ＤｏＧではなく、Ｆａｓｔ−Ｈｅｓｓｉａｎ  Ｄｅｔｅｃｔｏｒ等の他の手法を用いてもよい。
【００２６】
特徴点選定部１２は、特徴点検出部１０から出力される特徴点情報に基づいて、検出された特徴点の中から重要度順に指定数（所定数）の特徴点を選定する。そして、特徴点選定部１２は、選定した特徴点の特徴点番号や重要度の順序を示す情報などを、特徴点の選定結果として出力する。
【００２７】
特徴点選定部１２は、例えば、選定される特徴点の「指定数」を示す指定数情報をあらかじめ保持しておくことができる。指定数情報は、例えば、プログラムにおいて規定されていてもよいし、プログラムが参照するテーブル等に記憶されていることとしてもよい。また、指定数情報は、指定数そのものを示す情報であってもよいし、画像における局所特徴量の合計サイズ（例えばバイト数）を示す情報であってもよい。指定数情報が、画像における、局所特徴量の合計サイズを示す情報である場合、特徴点選定部１２は、例えば、合計サイズを、１つの特徴点における局所特徴量のサイズで割ることにより、指定数を算出することができる。
【００２８】
図２〜図５を参照して、特徴点選定部１２の構成例について説明する。図２に示すように、特徴点選定部１２は、高スケール順特徴点選定部２０を含む構成とすることができる。高スケール順特徴点選定部２０は、特徴点検出部１０から出力される特徴点情報に基づいて、スケールの高い順に指定数の特徴点を選定することができる。
【００２９】
具体的には、高スケール順特徴点選定部２０は、特徴点情報に基づいて、全特徴点のスケール順に特徴点を並び替え、スケールの大きな特徴点から順に重要度を付与する。そして、高スケール順特徴点選定部２０は、重要度が高い順に特徴点を選定していき、指定数分だけ特徴点を選定した時点で、選定した特徴点に関する情報を選定結果として出力する。高スケール順特徴点選定部２０は、例えば、各特徴点に固有で割り当てられている特徴点番号を選定結果として出力することができる。
【００３０】
一般的に、画像から検出される特徴点は、小さなスケールに多数分布し、スケールが大きくなるほどその数は少なくなる。そのため、高スケール順特徴点選定部２０が、スケールの大きな順に特徴点を選定することにより、結果的に、幅広いスケールの特徴点を選定することが可能となる。このように幅広いスケールの特徴点が選定されることにより、画像中に写る物体の大きさの変動に幅広く対応することが可能となる。その結果、画像検索や物体検出等のアプリケーションにおける精度をほとんど劣化させる事なく、特徴量記述の対象となる特徴点数を少なくすることが可能となる。
【００３１】
図３に示すように、特徴点選定部１２は、特徴点分類部２２及び代表特徴点選定部２４を含む構成とすることができる。特徴点分類部２２は、特徴点情報に基づいて、検出された複数の特徴点を複数のグループに分類することができる。そして、代表特徴点選定部２４は、各グループから少なくとも１つの特徴点を選定することにより、指定数の特徴点を選定することができる。
【００３２】
具体的には、特徴点分類部２２は、例えば、特徴点情報に含まれる特徴点の座標位置に関する情報を用いて、空間方向の特徴点の密集度を算出する。そして、特徴点分類部２２は、座標位置が近い特徴点をグルーピングし、グループ毎に固有の識別子を割当てることで、各特徴点がどの識別子を持つグループに属しているかを表す情報を空間方向特徴点密集度情報として出力することができる。
【００３３】
代表特徴点選定部２４は、空間方向特徴点密集度情報に基づいて、指定数の特徴点を選定することで、選定した特徴点に関する情報を選定結果として出力することができる。例えば、代表特徴点選定部２４は、各特徴点がどのグループに属しているかを示す情報を空間方向特徴点密集度情報として受け取った場合、各グループの中で最もスケールが大きい特徴点を選定してもよいし、各グループ内で最も孤立している特徴点（例えば、グループ内に存在する全特徴点との距離の和が最大となる特徴点）を選定してもよい。
【００３４】
また、代表特徴点選定部２４は、特徴点数の少ないグループから選定された特徴点は重要度が高く、特徴点数の多いグループから選定された特徴点は重要度が低いと判断してもよい。
【００３５】
そして、各グループから選定された特徴点の数が指定数よりも多い場合、代表特徴点選定部２４は、例えば、重要度に基づいて特徴点を指定数まで削減し、選定した特徴点に関する情報を選定結果として出力することができる。このとき、代表特徴点選定部２４は、重要度が高い順に特徴点を選定すればよい。
【００３６】
一方、各グループから選定された特徴点の数が指定数よりも少ない場合、代表特徴点選定部２４は、例えば、特徴点数が少ないグループから順に、さらに１点ずつ特徴点を選定していってもよい。
【００３７】
一般的に、画像から検出される特徴点は、画像中の特定の領域に集中することがあり、それらの特徴点の持つ情報には冗長性が含まれている可能性がある。図３に示す構成では、代表特徴点選定部２４が、空間方向の特徴点の密集度を考慮することにより、画像中から満遍なく特徴点を選定することができる。したがって、画像検索や物体検出等のアプリケーションにおける精度をほとんど劣化させることなく、特徴量記述の対象となる特徴点数を少なくすることが可能となる。
【００３８】
なお、特徴点の分類手法は空間方向の特徴点の密集度によるものに限られない。例えば、特徴点分類部２２は、空間方向の特徴点の密集度に加えて、グループ内の特徴点の持つオリエンテーションの類似度に基づいて特徴点をさらに分類することとしてもよい。例えば、特徴点分類部２２は、空間方向の特徴点の密集度により分類したグループ内の特徴点の中で最も隣接する（距離が最も近い）特徴点同士のオリエンテーションを見て、それが非常に類似している場合は同一のグループにし、類似していない場合は別々のグループにすることとしてもよい。
【００３９】
なお、特徴点分類部２２は、空間方向の特徴点の密集度に基づいて特徴点を分類した後に、特徴点のオリエンテーションに基づいて分類を行うという二段階の処理ではなく、空間方向の特徴点の密集度及びオリエンテーションの類似度を同時に考慮して特徴点の分類を行ってもよい。
【００４０】
図４に示すように、特徴点選定部１２は、特徴点無作為選定部２６を含む構成とすることができる。特徴点無作為選定部２６は、全特徴点に対してランダムに重要度を付与し、重要度が高い順に特徴点を選定することができる。そして、特徴点無作為選定部２６は、指定数の特徴点を選定した時点で、選定した特徴点に関する情報を選定結果として出力することができる。
【００４１】
一般的に、画像から検出される特徴点は、小さなスケールに多数分布し、スケールが大きくなるほどその数は少なくなる。そのため、特徴点無作為選定部２６が、特徴点に対して重要度をランダムに付与し、重要度順に特徴点を選定していくことにより、理想的には前述の分布の形状を保持して特徴点を選定することができる。結果的に、幅広いスケールの特徴点が選定され、画像中に写る物体の大きさの変動に幅広く対応することが可能となる。その結果、画像検索や物体検出等のアプリケーションにおける精度をほとんど劣化させることなく、特徴量記述の対象となる特徴点数を少なくすることが可能となる。
【００４２】
図５に示すように、特徴点選定部１２は、特定スケール領域特徴点選定部２８を含む構成とすることができる。特定スケール領域特徴点選定部２８は、特徴点情報に基づいて、全特徴点のスケールの中で、特定のスケール領域に含まれる特徴点のみを選定することができる。
【００４３】
そして、選定された特徴点が指定数よりも多い場合、特定スケール領域特徴点選定部２８は、例えば、重要度に基づいて特徴点を指定数まで削減し、選定した特徴点に関する情報を選定結果として出力することができる。このとき、特定スケール領域特徴点選定部２８は、重要度が高い順に特徴点を選定すればよい。
【００４４】
例えば、特定スケール領域特徴点選定部２８は、選定対象とするスケール領域の中心に近いスケールを持つ特徴点ほどその重要度が高いと判断し、重要度順に特徴点の選定を行うこととしてもよい。また、特定スケール領域特徴点選定部２８は、選定対象とするスケール領域の中で、スケールの大きい特徴点ほど重要度が高いと判断し、その重要度順に特徴点の選定を行ってもよい。
【００４５】
一方、特定のスケール領域に含まれる特徴点が指定数よりも少ない場合、特定スケール領域特徴点選定部２８は、例えば、このスケール領域に近い特徴点ほど重要度が高いと判断し、このスケール領域の前後のスケール領域から順番に特徴点を新たに選定していってもよい。
【００４６】
画像検索や物体検出等のアプリケーションにおいて、データベース側に登録されている画像上の物体のサイズが既知であり、かつクエリ側の画像とデータベース側の画像との間で、写っている物体のサイズ比が想定可能な場合がある。この場合、データベース側の特徴点の中で重要度が高い特徴点を知ることができれば、それらの特徴点の持つスケールに対し、クエリ側の画像とデータベース側の画像の物体サイズ比に相当する補正をかけたスケール領域から集中的に特徴点を選定することが効果的である。なお、データベース側の特徴点の中で重要度が高い特徴点を知るための手法は任意である。例えば、顕著性マップ（Ｓａｌｉｅｎｃｙ  Ｍａｐ）等を用いて事前にデータベース側の画像中の注視領域を特定し、その領域から検出されている特徴点を重要度が高いと定義してもよい。また例えば、スケールの大きい特徴点を重要であると定義しても良い。
【００４７】
図１に戻り、局所特徴量生成部１４は、特徴点検出部１０から出力される特徴点情報と、特徴点選定部１２から出力される選定結果とを受け取る。そして、局所特徴量生成部１４は、選定された各特徴点に対する局所領域の特徴量である局所特徴量を生成（記述）する。なお、局所特徴量生成部１４は、ＺＩＰやＬＺＨ等の可逆圧縮で圧縮された形式で局所特徴量を出力してもよい。
【００４８】
局所特徴量生成部１４は、特徴点の重要度順に局所特徴量を生成して出力することができる。また、局所特徴量生成部１４は、特徴点の座標位置順に局所特徴量を生成して出力してもよい。なお、特徴点の重要度順に局所特徴量が生成されることにより、選定された全ての特徴点の局所特徴量を利用せずに、一部の特徴点の局所特徴量だけを用いて照合処理を行うことが可能となる。
【００４９】
局所特徴量生成部１４は、例えば、選定された特徴点の重要度順を示す情報及びその特徴点番号情報を選定結果として受け取る場合、その特徴点番号に相当する特徴点を特徴量生成の対象とすることができる。
【００５０】
図１に示すように、局所特徴量生成部１４は、局所領域取得部４０、サブ領域分割部４２、サブ領域特徴ベクトル生成部４４、及び次元選定部４６を含んで構成することができる。
【００５１】
局所領域取得部４０は、特徴量情報に基づいて、検出された各特徴点の座標値、スケール、及びオリエンテーションから、特徴量抽出を行う局所領域を取得する。なお、局所領域取得部４０は、１つの特徴点に対してオリエンテーションの異なる複数の特徴点情報が存在する場合、各特徴点情報に対して局所領域を取得することができる。
【００５２】
サブ領域分割部４２は、局所領域を特徴点のオリエンテーション方向に応じて回転させて正規化した後、サブ領域に分割する。例えば、サブ領域分割部４２は、図２４に示したように、局所領域を１６ブロック（４×４ブロック）に分割することができる。また例えば、サブ領域分割部４２は、局所領域を２５ブロック（５×５ブロック）に分割することもできる。
【００５３】
サブ領域特徴ベクトル生成部４４は、局所領域のサブ領域ごとに特徴ベクトルを生成する。サブ領域の特徴ベクトルとしては、例えば、勾配方向ヒストグラムを用いることができる。具体的には、サブ領域特徴ベクトル生成部４４は、各サブ領域の画素ごとに勾配方向を算出し、それを８方向に量子化する。ここで求める勾配方向は、特徴点検出部１０が出力する各特徴点の角度に対する相対的な方向である。すなわち、特徴点検出部１０が出力する角度に対して正規化された方向である。そして、サブ領域特徴ベクトル生成部４４は、サブ領域ごとに量子化された８方向の頻度を集計し、勾配方向ヒストグラムを生成する。この場合、サブ領域特徴ベクトル生成部４４は、各特徴点に対して生成される１６ブロック×８方向＝１２８次元の勾配方向ヒストグラムにより構成される特徴ベクトルを出力する。また、勾配方向を８方向に量子化するだけに限らず、４方向、６方向、１０方向など任意の量子化数に量子化してよい。勾配方向をＤ方向に量子化する場合、量子化前の勾配方向をＧ（０〜２πラジアン）とすると、勾配方向の量子化値ｉ（ｉ＝０，・・・，Ｄ−１）は、例えば式（１）や式（２）などで求めることができるが、これに限られない。
【００５４】
【数１】
0006044548.tif 000002
【００５５】
【数２】
0006044548.tif 000003
ここでfloor()は小数点以下を切り捨てる関数、round()は四捨五入を行う関数、modは剰余を求める演算である。また、勾配方向ヒストグラムを生成するときに、単純な頻度を集計するのではなく、勾配の大きさを加算して集計してもよい。また、勾配方向ヒストグラムを集計するときに、画素が属するサブ領域だけではなく、サブ領域間の距離に応じて近接するサブ領域（隣接するブロックなど）にも重み値を加算するようにしてもよい。また、量子化された勾配方向の前後の勾配方向にも重み値を加算するようにしてもよい。なお、サブ領域の特徴ベクトルは勾配方向ヒストグラムに限られず、色情報など、複数の次元（要素）を有するものであればよい。本実施形態においては、サブ領域の特徴ベクトルとして、勾配方向ヒストグラムを用いることとして説明する。
【００５６】
また、サブ領域特徴ベクトル生成部４４は、特徴点の座標位置情報を局所特徴量に含めて出力することができる。さらに、サブ領域特徴ベクトル生成部４４は、選定された特徴点のスケール情報を局所特徴量に含めて出力してもよい。
【００５７】
画像検索や物体検出等のアプリケーションにおいて、クエリ（検索要求）側の画像とデータベース側の画像に同一物体が写っている場合、画像間で対応する特徴点のスケール比率がほぼ一定になる。そのため、局所特徴量にスケール情報を含ませることにより、特徴量の照合精度を向上させることが可能になる。
【００５８】
次元選定部４６は、サブ領域の位置関係に基づいて、近接するサブ領域の特徴ベクトル間の相関が低くなるように、局所特徴量として出力する次元（要素）を選定する（間引きする）。より具体的には、次元選定部４６は、例えば、隣接するサブ領域間では少なくとも１つの勾配方向が異なるように次元を選定する。なお、本実施形態では、近接するサブ領域として主に隣接するサブ領域を用いることとするが、近接するサブ領域は隣接するサブ領域に限られず、例えば、対象のサブ領域から所定距離内にあるサブ領域を近接するサブ領域とすることもできる。
【００５９】
また、次元選定部４６は、単に次元を選定するだけではなく、選定の優先順位を決定することができる。すなわち、次元選定部４６は、例えば、隣接するサブ領域間では同一の勾配方向の次元が選定されないように、優先順位をつけて次元を選定することができる。そして、次元選定部４６は、選定した次元から構成される特徴ベクトルを、局所特徴量として出力する。なお、次元選定部４６は、優先順位に基づいて次元を並び替えた状態で、局所特徴量を出力することができる。
【００６０】
図６〜図１０を参照して、次元選定部４６における次元選定の具体例を説明する。図６は、局所領域を４×４ブロックのサブ領域に分割し、勾配方向を８方向に量子化して生成された１２８次元の勾配方向ヒストグラムの特徴ベクトルから次元を選定する場合の一例を示す図である。図６の例では、ＳＩＦＴ特徴量と同様の１２８次元（４×４＝１６ブロック×８方向）の特徴ベクトルから次元の選定が行われている。
【００６１】
図６に示すように、次元選定部４６は、１２８次元から半分の次元数である６４次元を選定する場合、隣接する左右、上下のブロック（サブ領域）では、同一の勾配方向の次元が選定されないように、次元を選定することができる。図６の例では、勾配方向ヒストグラムにおける量子化された勾配方向をｉ（ｉ＝０，１，２，３，４，５，６，７）とした場合に、ｉ＝０，２，４，６の要素を選定するブロックと、ｉ＝１，３，５，７の要素を選定するブロックとが交互に並んでいる例が示されている。また、図６では、別の例として、ｉ＝０，３，４，７の要素を選定するブロックと、ｉ＝１，２，５，６の要素を選定するブロックとが交互に並んでいる例が示されている。そして、図６の例では、隣接するブロックで選定された勾配方向（次元）を合わせると、全８方向となっている。すなわち、隣接するブロック間で特徴量を補完し合う関係となっている。
【００６２】
また、図６に示すように、次元選定部４６は、３２次元を選定する場合、斜め４５°に位置するブロック間でも、同一の勾配方向の次元が選定されないように、次元を選定することができる。そして、図６の例では、隣接する２×２ブロックで選定された勾配方向（次元）を合わせると、全８方向となっている。すなわち、この場合においても、隣接するブロック間で特徴量を補完し合う関係となっている。
【００６３】
このように、隣接するブロック間で勾配方向が重ならないように、また全勾配方向が均等に選定されることが望ましい。また同時に、図６に示す例のように、局所領域の全体から均等に次元が選定されることが望ましい。なお、図６に示した次元選定方法は一例であり、この選定方法に限らない。
【００６４】
図７は、次元選定の別の一例を示す図である。図７の例では、サブ領域分割部４２が、局所領域を５×５＝２５ブロックのサブ領域に分割し、サブ領域特徴ベクトル生成部４４が、各サブ領域から６方向の勾配方向ヒストグラムを生成している。すなわち、図７に示すように、サブ領域特徴ベクトル生成部４４が生成する特徴ベクトルは１５０次元である。
【００６５】
図７に示すように、次元選定部４６は、１５０次元から半分の７５次元を選定する場合に、隣接する左右、上下のブロックでは、同一の勾配方向の次元が選定されないように、次元を選定することができる。この例では、勾配方向ヒストグラムにおける量子化された勾配方向をｉ（ｉ＝０，１，２，３，４，５）とした場合に、ｉ＝０，２，４の要素を選定するブロックと、ｉ＝１，３，５の要素を選定するブロックとが交互に並んでいる。そして、図７の例では、隣接するブロックで選定された勾配方向を合わせると、全６方向となっている。
【００６６】
また、次元選定部４６は、７５次元から５０次元を選定する場合は、斜め４５°に位置するブロック間で、１つの方向のみが同一になる（残り１つの方向は異なる）ように次元を選定することができる。また、次元選定部４６は、５０次元から２５次元を選定する場合は、斜め４５°に位置するブロック間で、選定される勾配方向が一致しないように次元を選定することができる  図７に示す例では、次元選定部４６は、１次元から２５次元までは各サブ領域から１つの勾配方向を選定し、２６次元から５０次元までは２つの勾配方向を選定し、５１次元から７５次元までは３つの勾配方向を選定している。
【００６７】
また、次元選定部４６は、１〜２５次元、２６次元〜５０次元、５１次元〜７５次元の間は、例えば図８に示すようなブロックの順番で次元を追加するように選定していってもよい。図８に示す優先順位を用いる場合、次元選定部４６は、中心に近いブロックの優先順位を高くして、勾配方向を選定していくことができる。図９は、１５０次元の特徴ベクトルの要素の番号の一例を示す図である。この例では、５×５＝２５ブロックをラスタスキャン順に番号ｂ（ｂ＝０，１，・・・，２５）で表し、量子化された勾配方向をｉ（ｉ＝０，１，２，３，４，５）とした場合に、特徴ベクトルの要素の番号を６×ｂ＋ｉとしている。
【００６８】
また、図１０は、図８に示した優先順位に従って図９に示した要素を選定していくことにより得られる局所特徴量の構成例を示す図である。次元選定部４６は、例えば、図１０に示す順序で次元（要素）を出力することができる。具体的には、次元選定部４６は、例えば１５０次元の局所特徴量を出力する場合、図１０に示す順序で全１５０次元の要素を出力することができる。また、次元選定部４６は、例えば２５次元の局所特徴量を出力する場合、図１０に示す１行目（７６番目、４５番目、８３番目、・・・、１２０番目）の要素を図１０に示す順（左から右）に出力することができる。また、次元選定部４６は、例えば５０次元の局所特徴量を出力する場合、図１０に示す１行目に加えて、図１０に示す２行目の要素を図１０に示す順（左から右）に出力することができる。
【００６９】
ところで、図１０に示す例では、局所特徴量は階層的な構造となっている。すなわち、例えば、２５次元の局所特徴量と１５０次元の局所特徴量とにおいて、先頭の２５次元分の局所特徴量における要素の並びは同一となっている。このように、次元選定部４６は、階層的（プログレッシブ）に次元を選定することにより、アプリケーションや通信容量、端末スペックなどに応じて、任意の次元数の局所特徴量、すなわち任意のサイズの局所特徴量を抽出して出力することができる。また、次元選定部４６が、階層的に次元を選定し、優先順位に基づいて次元を並び替えて出力することにより、異なる次元数の局所特徴量を用いて、画像の照合を行うことができる。例えば、７５次元の局所特徴量と５０次元の局所特徴量を用いて画像の照合が行われる場合、先頭の５０次元だけを用いることにより、局所特徴量間の距離計算を行うことができる。
【００７０】
なお、図８〜図１０に示す優先順位は一例であり、次元を選定する際の順序はこれに限られない。例えば、ブロックの順番に関しては、図８の例の他に、図１１（ａ）や図１１（ｂ）に示すような順番でもよい。また例えば、全てのサブ領域からまんべんなく次元が選定されるように優先順位が定められることとしてもよい。また、局所領域の中央付近が重要として、中央付近のサブ領域の選定頻度が高くなるように優先順位が定められることとしてもよい。また、次元の選定順序を示す情報は、例えば、プログラムにおいて規定されていてもよいし、プログラムの実行時に参照されるテーブル等（選定順序記憶部）に記憶されていてもよい。
【００７１】
また、次元選定部４６は、図１２（ａ）や図１２（ｂ）に示すような選定を行ってもよい。この場合、あるサブ領域では６次元が選定され、当該サブ領域に近接する他のサブ領域では０次元が選定されている。このような場合においても、近接するサブ領域間の相関が低くなるようにサブ領域ごとに次元が選定されていると言うことができる。
【００７２】
また、局所領域やサブ領域の形状は、図６や図７に示したような正方形に限られず、任意の形状とすることができる。例えば、図１３に示すように、局所領域取得部４０は、円状の局所領域を取得することとしてもよい。この場合、サブ領域分割部４２は、図１３に示すように、円状の局所領域を例えば９分割や１７分割のサブ領域に分割することができる。この場合においても、次元選定部４６は、各サブ領域において、例えば図１４に示すように、次元を選定することができる。なお、図１４に示す例では、７２次元から４０次元を選定する際に、中央のサブ領域では次元の間引きが行われていない。
【００７３】
図１５は、局所特徴量抽出装置１Ａにおける処理の一例を示すフローチャートである。まず、特徴点検出部１０は、局所特徴量の生成対象となる画像を受け付ける（Ｓ１５０１）。特徴点検出部１０は、受け付けた画像から特徴点を検出し、特徴点の座標位置、スケール、特徴点のオリエンテーション、特徴点番号等を含む特徴点情報を出力する（Ｓ１５０２）。そして、特徴点選定部１２は、特徴点情報に基づいて、検出された特徴点の中から重要度順に特徴点を指定数だけ選定し、その選定結果を出力する（Ｓ１５０３）。
【００７４】
続いて、局所領域取得部４０は、選定された各特徴点の座標値、スケール、及び角度に基づいて、特徴量抽出を行う局所領域を取得する（Ｓ１５０４）。そして、サブ領域分割部４２は、局所領域をサブ領域に分割する（Ｓ１５０５）。サブ領域特徴ベクトル生成部４４は、局所領域のサブ領域ごとに、勾配方向ヒストグラムを生成する（Ｓ１５０６）。最後に、次元選定部４６は、定められた選定順序に従って、局所特徴量として出力する次元（要素）を選定する（Ｓ１５０７）。
【００７５】
このように、第１の実施形態の局所特徴量抽出装置１Ａでは、次元選定部４６が、サブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるように、局所特徴量として出力する次元（要素）を選定する。つまり、近接するサブ領域は相関が高いことが多いため、次元選定部４６は、近接するサブ領域からは同じ特徴ベクトルの次元（要素）が選定されないように、次元の選定を行うことができる。これにより、被写体識別の精度を維持しつつ、特徴量のサイズを小さくすることが可能となる。
【００７６】
また、次元選定部４６は、図１０に例示したように、局所特徴量を階層的（プログレッシブ）に出力することができる。これにより、選定された次元数（特徴量のサイズ）が異なる局所特徴量の間であっても、相互に照合（距離計算）を行うことができる。
【００７７】
また、次元選定部４６は、サブ領域の位置関係に基づいて次元の選定を行うため、次元の選定の際に学習を行う必要がない。つまり、データ（画像）に依存せずに汎用的な局所特徴量の抽出を行うことができる。
【００７８】
また、局所特徴量抽出装置１Ａでは、特徴点選定部１２が、特徴点情報に基づいて、検出された複数の特徴点の中から重要度順に所定数の特徴点を選定する。そして、局所特徴量生成部１４が、選定された各特徴点に対する局所特徴量を生成する。これにより、検出された全ての特徴点に対する局所特徴量を生成する場合と比較して局所特徴量のサイズを小さくすることができる。換言すると、局所特徴量のサイズを、指定数に応じたサイズに制御することができる。さらに、局所特徴量の生成対象となる特徴点が、重要度順に選定されているため、被写体識別の精度を維持することが可能である。また、局所特徴量のサイズが小さくなることにより、局所特徴量を用いて画像検索を行う場合において、通信時間や処理時間を低減させることが可能となる。
【００７９】
なお、局所特徴量抽出装置１Ａでは、サブ領域特徴ベクトル生成部４４と次元選定部４６の処理の順序を入れ替えてもよい。すなわち、局所特徴量抽出装置１Ａでは、次元選定部４６において次元を選定した後に、サブ領域特徴ベクトル生成部４４において、選定された次元に対する特徴ベクトルが生成されることとしてもよい。
【００８０】
＝＝第２の実施形態＝＝
次に第２の実施形態について説明する。図１６は、本発明の第２の実施形態における局所特徴量抽出装置の構成を示す図である。図１６に示すように、局所特徴量抽出装置１Ｂは、特徴点検出部１０、選定数決定部５０、特徴点選定部５２、及び局所特徴量生成部５４を含んで構成される。また、局所特徴量生成部５４は、所領域取得部４０、サブ領域分割部４２、サブ領域特徴ベクトル生成部４４、及び次元選定部５６を含んで構成される。このように、局所特徴量抽出装置１Ｂでは、第１の実施形態の局所特徴量抽出装置１Ａに選定数決定部５０が追加されている。また、局所特徴量抽出装置１Ｂでは、第１の実施形態の局所特徴量抽出装置１Ａの特徴点選定部１２及び次元選定部４６が、特徴点選定部５２及び次元選定部５６に変更されている。なお、第１の実施形態と同一の構成要素については同一の符号を付して説明を省略する。
【００８１】
選定数決定部５０は、特徴点選定部５２において選定される特徴点数（選定特徴点数）と、次元選定部５６において選定される次元数（選定次元数）とを決定することができる。例えば、選定数決定部５０は、特徴点数や次元数を示す情報をユーザから受け付けることにより、特徴点数や次元数を決定することができる。なお、特徴点数や次元数を示す情報は、特徴点数や次元数そのものを示すものである必要はなく、例えば、検索精度や検索速度などを示す情報であってもよい。具体的には、選定数決定部５０は、例えば、検索精度を高くすることを要求する入力を受け付けた場合には、特徴点数及び次元数の少なくとも一方が多くなるように特徴点数及び次元数を決定することとしてもよい。また、選定数決定部５０は、例えば、検索速度を速くすることを要求する入力を受け付けた場合には、特徴点数及び次元数の少なくとも一方が少なくなるように特徴点数及び次元数を決定することとしてもよい。
【００８２】
また、例えば、選定数決定部５０は、局所特徴量抽出装置１Ｂが用いられるアプリケーションや通信容量、端末の処理スペックなどに基づいて特徴点数及び次元数を決定することとしてもよい。具体的には、選定数決定部５０は、例えば、通信容量が小さい（通信速度が遅い）場合には、通信容量が大きい（通信速度が速い）場合と比較して特徴点数及び次元数の少なくとも一方が少なくなるように特徴点数及び次元数を決定することとしてもよい。また、選定数決定部５０は、例えば、端末の処理スペックが低い場合には、処理スペックが高い場合と比較して特徴点数及び次元数の少なくとも一方が少なくなるように特徴点数及び次元数を決定することとしてもよい。また、選定数決定部５０は、例えば、端末の処理負荷に応じて動的に特徴点数及び次元数を決定することとしてもよい。
【００８３】
特徴点選定部５２は、選定数決定部５０により決定された特徴点数に基づいて、第１の実施形態の特徴点選定部１２と同様に特徴点を選定することができる。
【００８４】
次元選定部５６は、選定数決定部５０により決定された次元数に基づいて、第１の実施形態の次元選定部４６と同様に特徴ベクトルの次元を選定し、局所特徴量として出力することができる。
【００８５】
このように、第２の実施形態の局所特徴量抽出装置１Ｂでは、選定数決定部５０が、特徴点選定部５２において選定される特徴点数と、次元選定部５６において選定される次元数とを決定することができる。これにより、ユーザ入力や通信容量、端末の処理スペックなどに基づいて、適切な特徴点数及び次元数を決定することが可能となる。これにより、被写体識別の精度を維持しつつ、特徴量のサイズを所望のサイズに制御することが可能となる。
【００８６】
＝＝第３の実施形態＝＝
次に第３の実施形態について説明する。図１７は、本発明の第３の実施形態における局所特徴量抽出装置の構成を示す図である。図１７に示すように、局所特徴量抽出装置１Ｃは、特徴点検出部１０、選定数決定部６０、特徴点選定部５２、及び局所特徴量生成部５４を含んで構成される。また、局所特徴量生成部５４は、所領域取得部４０、サブ領域分割部４２、サブ領域特徴ベクトル生成部４４、及び次元選定部５６を含んで構成される。このように、局所特徴量抽出装置１Ｃでは、第２の実施形態の局所特徴量抽出装置１Ｂの選定数決定部５０が、選定数決定部６０に変更されている。なお、第２の実施形態と同一の構成要素については同一の符号を付して説明を省略する。
【００８７】
選定数決定部６０は、画像全体の特徴量のサイズ（合計サイズ）を指定するための情報である指定特徴量サイズ情報に基づいて、画像全体の特徴量のサイズが指定特徴量サイズとなるように、特徴点数及び次元数を決定することができる。
【００８８】
まず、次元数を先に決定するパターンについて説明する。例えば、選定数決定部６０は、指定特徴量サイズと次元数との対応関係を規定した情報に基づいて、次元数を決定することができる。図１８には、指定特徴量サイズと次元数との対応関係を規定した情報の一例が示されている。選定数決定部６０は、図１８に示すような情報を参照することにより、指定特徴量サイズに対応する次元数を決定することができる。なお、図１８に示す対応関係では、指定特徴量サイズが大きいほど、選定される次元数が多くなっているが、対応関係はこれに限られない。例えば、指定特徴量サイズにかかわらず固定の次元数が対応づけられた対応関係であってもよい。なお、対応関係を規定した情報は、例えば、プログラムにおいて規定されていてもよいし、プログラムが参照するテーブル等に記憶されていることとしてもよい。
【００８９】
そして、選定数決定部６０は、指定特徴量サイズ及び決定した次元数に基づいて、特徴量サイズが指定特徴量サイズになるように、選定特徴点数を決定することができる。なお、局所特徴量生成部５４が、特徴点の座標位置等の付加情報を特徴量に含めて出力する場合、選定数決定部６０は、この付加情報の記述サイズを含んだ特徴量サイズが指定特徴量サイズになるように特徴点数を決定することができる。
【００９０】
また、選定数決定部６０は、特徴点選定部５２での選定結果に基づいて、次元数を再度決定することも可能である。例えば、入力画像が特徴の少ない画像である場合、そもそも検出可能な特徴点が少ないことがある。そのため、特徴点選定部５２で選定された特徴点数が、選定数決定部６０により決定された特徴点数に達しない場合がある。このような場合、選定数決定部６０は、特徴点選定部５２で選定された特徴点数の情報を特徴点選定部５２から受け付けて、選定された特徴点数で指定特徴量サイズになるように、次元数を決定しなおすことができる。これは、第３の実施形態における後述する別のパターンにおいても同様である。
【００９１】
次に、特徴点数を先に決定するパターンについて説明する。例えば、選定数決定部６０は、指定特徴量サイズと特徴点数との対応関係を規定した情報に基づいて、特徴点数を決定することができる。この対応関係を規定した情報は、図１８に示した、指定特徴量サイズと次元数との対応関係を規定した情報と同様に規定することができる。例えば、指定特徴量サイズが大きいほど、選定される特徴点数が多くなるように対応関係を規定することができる。なお、対応関係はこれに限られず、例えば、指定特徴量サイズにかかわらず固定の特徴点数が対応づけられた対応関係であってもよい。
【００９２】
そして、選定数決定部６０は、指定特徴量サイズ及び決定した特徴点数に基づいて、特徴量サイズが指定特徴量サイズになるように、選定次元数を決定することができる。なお、局所特徴量生成部５４が、特徴点の座標位置等の付加情報を特徴量に含めて出力する場合、選定数決定部６０は、この付加情報の記述サイズを含んだ特徴量サイズが指定特徴量サイズになるように次元数を決定することができる。
【００９３】
次に、特徴点数及び次元数を同時に決定するパターンについて説明する。例えば、選定数決定部６０は、指定特徴量サイズと、特徴点数及び次元数との対応関係を規定した情報に基づいて、特徴点数及び次元数を決定することができる。この対応関係を規定した情報は、図１８に示した、指定特徴量サイズと次元数との対応関係を規定した情報と同様に規定することができる。例えば、指定特徴量サイズが大きいほど、選定される特徴点数や次元数が多くなるように対応関係を規定することができる。なお、対応関係はこれに限られず、例えば、指定特徴量サイズにかかわらず固定の特徴点数や次元数が対応づけられた対応関係であってもよい。
【００９４】
なお、局所特徴量生成部５４が、特徴点の座標位置等の付加情報を特徴量に含めて出力する場合、選定数決定部６０は、この付加情報の記述サイズを含んだ特徴量サイズが指定特徴量サイズになるように特徴点数及び次元数を決定することができる。
【００９５】
このように、第３の実施形態の局所特徴量抽出装置１Ｃでは、選定数決定部６０が、特徴点選定部５２において選定される特徴点数と、次元選定部５６において選定される次元数とを、指定特徴量サイズ情報に基づいて決定することができる。これにより、被写体識別の精度を維持しつつ、特徴量のサイズを所望のサイズに制御することが可能となる。
【００９６】
＝＝第４の実施形態＝＝
次に第４の実施形態について説明する。図１９は、本発明の第４の実施形態における局所特徴量抽出装置の構成を示す図である。図１９に示すように、局所特徴量抽出装置１Ｄは、特徴点検出部１０、選定数決定部７０、特徴点選定部７２、及び局所特徴量生成部５４を含んで構成される。また、局所特徴量生成部５４は、所領域取得部４０、サブ領域分割部４２、サブ領域特徴ベクトル生成部４４、及び次元選定部５６を含んで構成される。このように、局所特徴量抽出装置１Ｄでは、第３の実施形態の局所特徴量抽出装置１Ｃの選定数決定部６０及び特徴点選定部５２が、選定数決定部７０及び特徴点選定部７２に変更されている。なお、第３の実施形態と同一の構成要素については同一の符号を付して説明を省略する。
【００９７】
特徴点選定部７２は、第１の実施形態の特徴点選定部１２と同様に、特徴点検出部１０から出力される特徴点情報に基づいて特徴点の選定を行う。そして、特徴点選定部７２は、選定した特徴点数を示す情報を選定数決定部７０に出力する。
【００９８】
選定数決定部７０は、第３の実施形態の選定数決定部６０と同様に、指定特徴量サイズ情報を受け付けることができる。そして、選定数決定部７０は、指定特徴量サイズ情報と、特徴点選定部７２で選定された特徴点数とに基づいて、画像全体の特徴量のサイズが指定特徴量サイズとなるように、次元数を決定することができる。
【００９９】
なお、局所特徴量生成部５４が、特徴点の座標位置等の付加情報を特徴量に含めて出力する場合、選定数決定部７０は、この付加情報の記述サイズを含んだ特徴量サイズが指定特徴量サイズになるように次元数を決定することができる。
【０１００】
このように、第４の実施形態の局所特徴量抽出装置１Ｄでは、選定数決定部７０が、指定特徴量サイズ情報と、特徴点選定部７２において選定される特徴点数とに基づいて、次元選定部５６において選定される次元数を決定することができる。これにより、被写体識別の精度を維持しつつ、特徴量のサイズを所望のサイズに制御することが可能となる。
【０１０１】
＝＝第５の実施形態＝＝
次に第５の実施形態について説明する。図２０は、本発明の第５の実施形態における局所特徴量抽出装置の構成を示す図である。図２０に示すように、局所特徴量抽出装置１Ｅは、特徴点検出部１０、選定数決定部８０、特徴点選定部８２、及び局所特徴量生成部５４を含んで構成される。また、局所特徴量生成部５４は、所領域取得部４０、サブ領域分割部４２、サブ領域特徴ベクトル生成部４４、及び次元選定部５６を含んで構成される。このように、局所特徴量抽出装置１Ｅでは、第２の実施形態の局所特徴量抽出装置１Ｂの選定数決定部５０及び特徴点選定部５２が、選定数決定部８０及び特徴点選定部８２に変更されている。なお、第２の実施形態と同一の構成要素については同一の符号を付して説明を省略する。
【０１０２】
特徴点選定部８２は、第１の実施形態の特徴点選定部１２と同様に、特徴点検出部１０から出力される特徴点情報に基づいて特徴点の選定を行う。そして、特徴点選定部８２は、選定した各特徴点の重要度を示す重要度情報を選定数決定部８０に出力する。
【０１０３】
選定数決定部８０は、特徴点選定部８２から出力される重要度情報に基づいて、次元選定部５６で選定される次元数を特徴点ごとに決定することができる。例えば、選定数決定部８０は、重要度が高い特徴点ほど選定される次元数が大きくなるように次元数を決定することができる。
【０１０４】
さらに、選定数決定部８０は、第４の実施形態の選定数決定部７０と同様に、指定特徴量サイズ情報を受け付け、画像全体の特徴量のサイズが指定特徴量サイズとなるように、次元数を決定することとしてもよい。具体的には、例えば、選定数決定部８０は、重要度が高い特徴点ほど選定される次元数が大きくなるとともに、画像全体の特徴量のサイズが指定特徴量サイズとなるように、次元数を決定することとしてもよい。
【０１０５】
なお、局所特徴量生成部５４が、特徴点の座標位置等の付加情報を特徴量に含めて出力する場合、選定数決定部８０は、この付加情報の記述サイズを含んだ特徴量サイズが指定特徴量サイズになるように次元数を決定することができる。
【０１０６】
このように、第５の実施形態の局所特徴量抽出装置１Ｅでは、選定数決定部８０が、特徴点選定部８２により選定された特徴点ごとの重要度に基づいて、次元選定部５６において選定される次元数を特徴点ごとに決定することができる。これにより、被写体識別の精度を維持しつつ、特徴量のサイズを所望のサイズに制御することが可能となる。
【０１０７】
＝＝適用例＝＝
図２１は、第１〜第５の実施形態に示した局所特徴量抽出装置を適用可能な照合システムの一例を示す図である。図２１に示すように、照合システムは、照合装置１００、特徴量データベース（ＤＢ：Ｄａｔａｂａｓｅ）１１０、及び局所特徴量抽出装置１２０を含んで構成されている。
【０１０８】
照合装置１００は、局所特徴量抽出装置１２０から送信される検索要求に含まれる局所特徴量を特徴量ＤＢ１１０に記憶されている局所特徴量と照合することにより、局所特徴量抽出装置１２０に入力された画像内の被写体と類似する被写体を含む画像を検索することができる。
【０１０９】
特徴量ＤＢ１１０は、複数の画像から抽出された局所特徴量を抽出元の画像と対応づけて記憶している。特徴量ＤＢ１１０に記憶されている局所特徴量は、例えば図１０に示した順序で出力された１５０次元の特徴ベクトルとすることができる。
【０１１０】
局所特徴量抽出装置１２０は、第１〜第５のいずれかの実施形態において示された局所特徴量抽出装置を用いることができる。
【０１１１】
局所特徴量抽出装置１２０は、入力画像において検出される特徴点の局所特徴量を含む検索要求を生成して照合装置１００に送信する。照合装置１００では、受信した局所特徴量を特徴量ＤＢ１１０に記憶されている局所特徴量と照合することにより、入力画像に類似する画像を判定する。そして、照合装置１００は、入力画像に類似していると判定した画像を示す情報を検索結果として局所特徴量抽出装置１２０に出力する。
【０１１２】
このような照合システムにおいて、局所特徴量抽出装置１２０では、第１〜第５の実施形態で説明したように、サブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるように、局所特徴量として出力する次元（要素）が選定されている。したがって、照合装置１００での照合精度を維持しつつ、局所特徴量のサイズを小さくすることができる。
【０１１３】
したがって、局所特徴量抽出装置１２０から照合装置１００に局所特徴量を送信する際の通信時間を短くすることができる。また、局所特徴量のサイズが小さいため、照合装置１００での照合の処理負荷を低くすることができる。さらに、図１０に示したように、局所特徴量が階層的（プログレッシブ）な構造となっているため、局所特徴量抽出装置１２０で抽出された局所特徴量の次元数と、特徴量ＤＢ１１０に記憶１１０に格納されている局所特徴量の次元数とが異なる場合であっても、照合装置１００は、互いに共通する次元数までの局所特徴量を用いることにより照合処理を実行することができる。
【０１１４】
例えば、図２２に示すように、特徴量ＤＢ１１０に記憶されている局所特徴量が１５０次元であり、局所特徴量抽出装置１２０で抽出される局所特徴量が５０次元である場合を考える。この場合、照合装置１００は、双方の５０次元までの局所特徴量を用いることにより照合を行うことができる。つまり、例えば局所特徴量抽出装置１２０の処理能力に応じて局所特徴量の次元数を変更しても、変更された次元数の局所特徴量を用いて、照合装置１００において照合処理を実行することが可能である。
【０１１５】
なお、本実施形態は、本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明は、その趣旨を逸脱することなく、変更／改良され得るととともに、本発明にはその等価物も含まれる。
【０１１６】
この出願は、２０１１年１１月１８日に出願された日本出願特願２０１１−２５３２２３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【０１１７】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１１８】
本実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力する特徴点検出部と、前記特徴点情報に基づいて、検出された前記複数の特徴点の中から、重要度順に所定数の特徴点を選定する特徴点選定部と、選定された各特徴点に対する局所領域を取得する局所領域取得部と、各局所領域を複数のサブ領域に分割するサブ領域分割部と、各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成するサブ領域特徴ベクトル生成部と、各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに前記特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する次元選定部と、を備える局所特徴量抽出装置。
（付記２）付記１に記載の局所特徴量抽出装置であって、前記特徴点選定部において選定される特徴点数、および、前記次元選定部において選定される次元数を決定する選定数決定部をさらに備える、局所特徴量抽出装置。
（付記３）付記２に記載の局所特徴量抽出装置であって、前記選定数決定部は、前記選定された特徴点の特徴量の合計サイズを指定するための情報である指定特徴量サイズ情報を受け付け、該指定特徴量サイズ情報に基づいて前記特徴点数及び前記次元数を決定する、局所特徴量抽出装置。
（付記４）付記３に記載の局所特徴量抽出装置であって、前記選定数決定部は、前記合計サイズ及び前記次元数の対応関係を示す情報と、前記指定特徴量サイズ情報とに基づいて、前記特徴点数及び前記次元数を決定する、局所特徴量抽出装置。
（付記５）付記３に記載の局所特徴量抽出装置であって、前記選定数決定部は、前記合計サイズ及び前記特徴点数の対応関係を示す情報と、前記指定特徴量サイズ情報とに基づいて、前記特徴点数及び前記次元数を決定する、局所特徴量抽出装置。
（付記６）付記３に記載の局所特徴量抽出装置であって、前記選定数決定部は、前記合計サイズ、前記特徴点数、及び前記次元数の対応関係を示す情報と、前記指定特徴量サイズ情報とに基づいて、前記特徴点数及び前記次元数を決定する、局所特徴量抽出装置。
（付記７）付記１に記載の局所特徴量抽出装置であって、前記特徴点選定部における特徴点の選定結果を示す選定結果情報該を受け付け、該選定結果情報に基づいて前記次元数を決定する選定数決定部をさらに備える、局所特徴量抽出装置。
（付記８）付記７に記載の局所特徴量抽出装置であって、前記選定結果情報には、選定された特徴点ごとの重要度を示す重要度情報が含まれ、前記選定数決定部は、前記重要度情報に基づいて、選定された特徴点ごとに前記次元数を決定する、局所特徴量抽出装置。
（付記９）付記７または８に記載の局所特徴量抽出装置であって、前記選定数決定部は、前記選定された特徴点の特徴量の合計サイズを指定するための情報である指定特徴量サイズ情報をさらに受け付け、前記選定結果情報及び前記指定特徴量サイズ情報に基づいて前記次元数を決定する、局所特徴量抽出装置。
（付記１０）付記１〜９の何れか一項に記載の局所特徴量抽出装置であって、前記次元選定部は、隣接するサブ領域間において、選定される次元が少なくとも１つは異なるように前記特徴ベクトルから次元を選定する、局所特徴量抽出装置。
（付記１１）付記１〜１０の何れか一項に記載の局所特徴量抽出装置であって、前記次元選定部は、局所領域内の複数のサブ領域の特徴ベクトルにおいて次元を選定するための選定順位に従って、前記特徴ベクトルから次元を選定する、局所特徴量抽出装置。
（付記１２）付記１１に記載の局所特徴量抽出装置であって、前記次元選定部は、前記選定順位に従って選定された次元の順に、選定された次元の要素を局所領域の特徴量として出力する、局所特徴量抽出装置。
（付記１３）付記１〜１２の何れか一項に記載の局所特徴量抽出装置であって、前記特徴点情報は、各特徴点のスケールを示すスケール情報を含み、前記特徴点選定部は、前記スケール情報に基づいて、検出された前記複数の特徴点の中から、スケールに応じた重要度順に前記所定数の特徴点を選定する、局所特徴量抽出装置。
（付記１４）付記１〜１２の何れか一項に記載の局所特徴量抽出装置であって、前記特徴点選定部は、前記特徴点情報に基づいて、検出された前記複数の特徴点を複数のグループに分類する特徴点分類部と、各グループから少なくとも１つの特徴点を選定することにより、前記所定数の特徴点を選定する代表特徴点選定部と、を備える局所特徴量抽出装置。
（付記１５）コンピュータが、画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力し、前記特徴点情報に基づいて、検出された前記複数の特徴点の中から、重要度順に所定数の特徴点を選定し、選定された各特徴点に対する局所領域を取得し、各局所領域を複数のサブ領域に分割し、各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成し、各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに前記特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する、局所特徴量抽出方法。
（付記１６）コンピュータに、画像内の複数の特徴点を検出し、各特徴点に関する情報である特徴点情報を出力する機能と、前記特徴点情報に基づいて、検出された前記複数の特徴点の中から、重要度順に所定数の特徴点を選定する機能と、選定された各特徴点に対する局所領域を取得する機能と、各局所領域を複数のサブ領域に分割する機能と、各局所領域内のサブ領域ごとに複数次元の特徴ベクトルを生成する機能と、各局所領域内のサブ領域の位置関係に基づいて、近接するサブ領域間の相関が低くなるようにサブ領域ごとに前記特徴ベクトルから次元を選定し、選定された次元の要素を局所領域の特徴量として出力する機能と、を実現させるためのプログラム。
【符号の説明】
【０１１９】
１Ａ〜１Ｅ  局所特徴量抽出装置
１０  特徴点検出部
１２  特徴点選定部
１４  局所特徴量生成部
４０  局所領域取得部
４２  サブ領域分割部
４４  サブ領域特徴ベクトル生成部
４６  次元選定部
【図１】
0006044548.tif 000004
【図２】
0006044548.tif 000005
【図３】
0006044548.tif 000006
【図４】
0006044548.tif 000007
【図５】
0006044548.tif 000008
【図６】
0006044548.tif 000009
【図７】
0006044548.tif 000010
【図８】
0006044548.tif 000011
【図９】
0006044548.tif 000012
【図１０】
0006044548.tif 000013
【図１１】
0006044548.tif 000014
【図１２】
0006044548.tif 000015
【図１３】
0006044548.tif 000016
【図１４】
0006044548.tif 000017
【図１５】
0006044548.tif 000018
【図１６】
0006044548.tif 000019
【図１７】
0006044548.tif 000020
【図１８】
0006044548.tif 000021
【図１９】
0006044548.tif 000022
【図２０】
0006044548.tif 000023
【図２１】
0006044548.tif 000024
【図２２】
0006044548.tif 000025
【図２３】
0006044548.tif 000026
【図２４】
0006044548.tif 000027