(57)【特許請求の範囲】
【請求項１】
複数のリファレンス画像から、クエリ画像と類似するリファレンス画像を検索する画像検索装置であって、
前記複数のリファレンス画像の各々について、前記リファレンス画像に対して回転又は拡大率の変化を含む複数の変換を行って生成された複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行って前記局所特徴量の各々が分類された複数のクラスタの各々に対して求められたセントロイドの特徴量を格納したセントロイド格納部と、
前記複数のリファレンス画像の各々に対し、前記複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量の各々について、前記局所特徴量が属するクラスタのセントロイド、及び前記変換を表す幾何特徴を格納したインデクス格納部と、
入力された前記クエリ画像に基づいて、前記クエリ画像に対して前記複数の変換を行って複数の変換画像を生成し、前記クエリ画像及び前記複数の変換画像の各々から、前記局所特徴量及び前記幾何特徴を抽出する局所特徴量抽出部と、
前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド格納部に格納された前記複数のクラスタの各々に対するセントロイドの各々の特徴量と、前記クエリ画像の局所特徴量との類似度を算出し、前記クエリ画像の局所特徴量に対応する前記セントロイドを取得するセントロイド取得部と、
前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド取得部によって取得された前記セントロイドに対応して前記インデクス格納部に格納された前記リファレンス画像に対する前記幾何特徴との比率又は差分を算出し、前記複数のリファレンス画像の各々について前記幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、前記算出された前記リファレンス画像に対する前記幾何特徴との比率又は差分に対して設けられた前記リファレンス画像についての投票箱に投票する投票部と、
前記複数のリファレンス画像の各々に対し、前記リファレンス画像についての前記投票箱の投票結果に基づいて、前記クエリ画像と前記リファレンス画像との類似度を示すスコアを算出するスコア部と、
前記スコア部によって算出された前記スコアに基づいて、前記クエリ画像と類似する前記リファレンス画像を出力する類似画像出力部と、
を含む画像検索装置。
【請求項２】
前記局所特徴量抽出部は、画像の拡大率及び画像の三軸の各々の回転角を、前記幾何特徴として抽出する
請求項１記載の画像検索装置。
【請求項３】
前記スコア部は、前記複数のリファレンス画像の各々に対し、前記リファレンス画像についての前記投票箱の各々の投票数のうち、最大の投票数を、前記リファレンス画像との類似度を示す前記スコアとして算出する
請求項１又は２記載の画像検索装置。
【請求項４】
前記投票部は、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド取得部によって取得された前記セントロイドに対応して前記インデクス格納部に格納された前記リファレンス画像に対する前記幾何特徴との比率又は差分を算出し、前記複数のリファレンス画像の各々について前記幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、前記算出された前記リファレンス画像に対する前記幾何特徴との比率又は差分に対して設けられた前記リファレンス画像についての投票箱に、前記セントロイド取得部によって取得された前記セントロイドに対応する、前記クエリ画像または前記リファレンス画像の局所特徴量の数に応じた票数、前記セントロイド取得部によって取得された前記セントロイドに対応する局所特徴量を有する前記リファレンス画像の数に応じた票数、又は前記リファレンス画像から抽出された局所特徴量の数に応じた票数を投票する
請求項１〜請求項３の何れか１項記載の画像検索装置。
【請求項５】
局所特徴量抽出部、セントロイド取得部、投票部、スコア部、及び類似画像出力部を含み、
複数のリファレンス画像の各々について、前記リファレンス画像に対して回転又は拡大率の変化を含む複数の変換を行って生成された複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行って前記局所特徴量の各々が分類された複数のクラスタの各々に対して求められたセントロイドの特徴量を格納したセントロイド格納部、及び前記複数のリファレンス画像の各々に対し、前記複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量の各々について、前記局所特徴量が属するクラスタのセントロイド、及び前記変換を表す幾何特徴を格納したインデクス格納部を用いて、複数のリファレンス画像から、クエリ画像と類似するリファレンス画像を検索する画像検索装置における画像検索方法であって、
前記局所特徴量抽出部が、入力された前記クエリ画像に基づいて、前記クエリ画像に対して前記複数の変換を行って複数の変換画像を生成し、前記クエリ画像及び前記複数の変換画像の各々から、前記局所特徴量及び前記幾何特徴を抽出するステップと、
前記セントロイド取得部が、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド格納部に格納された前記複数のクラスタの各々に対するセントロイドの各々の特徴量と、前記クエリ画像の局所特徴量との類似度を算出し、前記クエリ画像の局所特徴量に対応する前記セントロイドを取得するステップと、
前記投票部が、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド取得部によって取得された前記セントロイドに対応して前記インデクス格納部に格納された前記リファレンス画像に対する前記幾何特徴との比率又は差分を算出し、前記複数のリファレンス画像の各々について前記幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、前記算出された前記リファレンス画像に対する前記幾何特徴との比率又は差分に対して設けられた前記リファレンス画像についての投票箱に投票するステップと、
前記スコア部が、前記複数のリファレンス画像の各々に対し、前記リファレンス画像についての前記投票箱の投票結果に基づいて、前記クエリ画像と前記リファレンス画像との類似度を示すスコアを算出するステップと、
前記類似画像出力部が、前記スコア部によって算出された前記スコアに基づいて、前記クエリ画像と類似する前記リファレンス画像を出力するステップと、
を含む画像検索方法。
【請求項６】
前記局所特徴量抽出部が前記幾何特徴を抽出するステップは、画像の拡大率及び画像の三軸の各々の回転角を、前記幾何特徴として抽出する
請求項５記載の画像検索方法。
【請求項７】
前記スコア部が前記スコアを算出するステップは、前記複数のリファレンス画像の各々に対し、前記リファレンス画像についての前記投票箱の各々の投票数のうち、最大の投票数を、前記リファレンス画像との類似度を示す前記スコアとして算出する
請求項６記載の画像検索方法。
【請求項８】
前記投票部が投票するステップは、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド取得部によって取得された前記セントロイドに対応して前記インデクス格納部に格納された前記リファレンス画像に対する前記幾何特徴との比率又は差分を算出し、前記複数のリファレンス画像の各々について前記幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、前記算出された前記リファレンス画像に対する前記幾何特徴との比率又は差分に対して設けられた前記リファレンス画像についての投票箱に、前記セントロイド取得部によって取得された前記セントロイドに対応する、前記クエリ画像または前記リファレンス画像の局所特徴量の数に応じた票数、前記セントロイド取得部によって取得された前記セントロイドに対応する局所特徴量を有する前記リファレンス画像の数に応じた票数、又は前記リファレンス画像から抽出された局所特徴量の数に応じた票数を投票する
請求項５〜請求項７の何れか１項記載の画像検索方法。
【請求項９】
コンピュータを、請求項１〜請求項４の何れか１項記載の画像検索装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像検索装置、方法、及びプログラムに係り、特に、クエリ画像と類似するリファレンス画像を検索する画像検索装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来より、画像中に同一の被写体が写っているかを高速に分析するための技術として、画像から抽出した局所特徴量をあらかじめ作成しておいたクラスタに分類し、同一クラスタの局所特徴量をより多く含む画像ほど、同一の被写体が写っている可能性が高いと判定するbag of visual wordsなどと呼ばれる手法がある（例えば、非特許文献１）。この手法では、局所特徴量１つ１つを比較するのではなく、同じクラスタに分類された局所特徴量のみを処理し、カウントすることにより画像の類似度を算出することができるため、高速に類似する画像を発見することができる。
【０００３】
また、局所特徴量の回転角度および拡大・縮小の比率の一貫性を検証する手法がある。例えば、非特許文献２に記載の技術では、図１４に示すクエリ画像１とリファレンス画像とは、３点ともが回転角度１３５度、拡大率が０．５であるのに対し、クエリ画像２とリファレンス画像とは２点が回転角度９０度、拡大率２であるが、もう一点は回転角度、拡大率ともに異なる。従って、回転角度および拡大率が一貫している点の多いクエリ画像１の方が、クエリ画像２よりも類似度が高いとして判定することができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Sivic，Josef,and Andrew Zisserman，“Video Google: A text retrieval approach to object matching in videos.”，Computer Vision，2003，Proceedings，Ninth IEEE International Conference on，IEEE，2003.
【非特許文献２】Jegou，Herve，Matthijs Douze，and Cordelia Schmid，“Improving bag-of-features for large scale image search.”，International Journal of Computer Vision 87.3，2010，p.316-336.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１の手法では、各局所特徴量の幾何的な情報が失われているため対応しない部分から抽出された局所特徴量を対応していると判定してしまい、類似画像抽出の精度が低下してしまう。例えば、上記図１４に示したリファレンス画像の三角形から抽出された３つの局所特徴量は、クエリ画像１だけでなく、異なる図形であるクエリ画像２とも３点がマッチすると判定され、類似度が高いと判断されてしまう。
【０００６】
また、非特許文献２の手法では、回転方向を１軸しか考慮していないため、３次元方向の回転に対応することができない。例えば、図１５に示すようにリファレンス画像を二次元平面内で回転したクエリ画像１は、リファレンス画像とマッチすると判定することができるが、三次元空間において上下方向や左右方向から見た画像であるクエリ画像２については、それらの軸に対する回転を局所特徴量に付随する情報として取得していないため、幾何的な一貫性を検証することができず、同一物体であっても類似度が高いと判定することができないという問題があった。そのため、三次元空間における幾何的な一貫性を検証可能にすることが課題となる。
【０００７】
本発明は、上記事情に鑑みて成されたものであり、クエリ画像と類似するリファレンス画像を精度よく取得することができる画像検索装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、本発明に係る画像検索装置は、複数のリファレンス画像から、クエリ画像と類似するリファレンス画像を検索する画像検索装置であって、前記複数のリファレンス画像の各々について、前記リファレンス画像に対して回転又は拡大率の変化を含む複数の変換を行って生成された複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行って前記局所特徴量の各々が分類された複数のクラスタの各々に対して求められたセントロイドの特徴量を格納したセントロイド格納部と、前記複数のリファレンス画像の各々に対し、前記複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量の各々について、前記局所特徴量が属するクラスタのセントロイド、及び前記変換を表す幾何特徴を格納したインデクス格納部と、入力された前記クエリ画像に基づいて、前記クエリ画像に対して前記複数の変換を行って複数の変換画像を生成し、前記クエリ画像及び前記複数の変換画像の各々から、前記局所特徴量及び前記幾何特徴を抽出する局所特徴量抽出部と、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド格納部に格納された前記複数のクラスタの各々に対するセントロイドの各々の特徴量と、前記クエリ画像の局所特徴量との類似度を算出し、前記クエリ画像の局所特徴量に対応する前記セントロイドを取得するセントロイド取得部と、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド取得部によって取得された前記セントロイドに対応して前記インデクス格納部に格納された前記リファレンス画像に対する前記幾何特徴との比率又は差分を算出し、前記複数のリファレンス画像の各々について前記幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、前記算出された前記リファレンス画像に対する前記幾何特徴との比率又は差分に対して設けられた前記リファレンス画像についての投票箱に投票する投票部と、前記複数のリファレンス画像の各々に対し、前記リファレンス画像についての前記投票箱の投票結果に基づいて、前記クエリ画像と前記リファレンス画像との類似度を示すスコアを算出するスコア部と、前記スコア部によって算出された前記スコアに基づいて、前記クエリ画像と類似する前記リファレンス画像を出力する類似画像出力部と、を含んで構成されている。
【０００９】
本発明に係る画像検索方法は、局所特徴量抽出部、セントロイド取得部、投票部、スコア部、及び類似画像出力部を含み、複数のリファレンス画像の各々について、前記リファレンス画像に対して回転又は拡大率の変化を含む複数の変換を行って生成された複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行って前記局所特徴量の各々が分類された複数のクラスタの各々に対して求められたセントロイドの特徴量を格納したセントロイド格納部、及び前記複数のリファレンス画像の各々に対し、前記複数の変換画像、及び前記リファレンス画像の各々から抽出された局所特徴量の各々について、前記局所特徴量が属するクラスタのセントロイド、及び前記変換を表す幾何特徴を格納したインデクス格納部を用いて、複数のリファレンス画像から、クエリ画像と類似するリファレンス画像を検索する画像検索装置における画像検索方法であって、前記局所特徴量抽出部が、入力された前記クエリ画像に基づいて、前記クエリ画像に対して前記複数の変換を行って複数の変換画像を生成し、前記クエリ画像及び前記複数の変換画像の各々から、前記局所特徴量及び前記幾何特徴を抽出するステップと、前記セントロイド取得部が、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド格納部に格納された前記複数のクラスタの各々に対するセントロイドの各々の特徴量と、前記クエリ画像の局所特徴量との類似度を算出し、前記クエリ画像の局所特徴量に対応する前記セントロイドを取得するステップと、前記投票部が、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド取得部によって取得された前記セントロイドに対応して前記インデクス格納部に格納された前記リファレンス画像に対する前記幾何特徴との比率又は差分を算出し、前記複数のリファレンス画像の各々について前記幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、前記算出された前記リファレンス画像に対する前記幾何特徴との比率又は差分に対して設けられた前記リファレンス画像についての投票箱に投票するステップと、前記スコア部が、前記複数のリファレンス画像の各々に対し、前記リファレンス画像についての前記投票箱の投票結果に基づいて、前記クエリ画像と前記リファレンス画像との類似度を示すスコアを算出するステップと、前記類似画像出力部が、前記スコア部によって算出された前記スコアに基づいて、前記クエリ画像と類似する前記リファレンス画像を出力するステップと、を含んで構成されている。
【００１０】
本発明の前記局所特徴量抽出部は、画像の拡大率及び画像の三軸の各々の回転角を、前記幾何特徴として抽出するようにすることができる。
【００１１】
本発明の前記スコア部は、前記複数のリファレンス画像の各々に対し、前記リファレンス画像についての前記投票箱の各々の投票数のうち、最大の投票数を、前記リファレンス画像との類似度を示す前記スコアとして算出するようにすることができる。
【００１２】
本発明の前記投票部は、前記局所特徴量抽出部によって抽出された前記クエリ画像の局所特徴量の各々について、前記セントロイド取得部によって取得された前記セントロイドに対応して前記インデクス格納部に格納された前記リファレンス画像に対する前記幾何特徴との比率又は差分を算出し、前記複数のリファレンス画像の各々について前記幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、前記算出された前記リファレンス画像に対する前記幾何特徴との比率又は差分に対して設けられた前記リファレンス画像についての投票箱に、前記セントロイド取得部によって取得された前記セントロイドに対応する、前記クエリ画像または前記リファレンス画像の局所特徴量の数に応じた票数、前記セントロイド取得部によって取得された前記セントロイドに対応する局所特徴量を有する前記リファレンス画像の数に応じた票数、又は前記リファレンス画像から抽出された局所特徴量の数に応じた票数を投票するようにすることができる。
【００１３】
本発明のプログラムは、コンピュータを、本発明の画像検索装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１４】
本発明の画像検索装置、方法、及びプログラムによれば、複数のリファレンス画像の各々について、当該リファレンス画像に対して回転及び拡大率の変化を含む複数の変換を行って生成された複数の変換画像、及びリファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行って局所特徴量の各々が分類された複数のクラスタの各々に対して求められたセントロイドの特徴量を格納し、抽出された局所特徴量の各々について、局所特徴量が属するクラスタのセントロイド、及び幾何特徴を格納し、クエリ画像に対して複数の変換を行って複数の変換画像を生成し、クエリ画像及び複数の変換画像の各々から、局所特徴量及び幾何特徴を抽出し、抽出されたクエリ画像の局所特徴量の各々について、複数のクラスタの各々に対するセントロイドの各々の特徴量と、クエリ画像の局所特徴量との類似度を算出し、クエリ画像の局所特徴量に対応するセントロイドを取得し、抽出されたクエリ画像の局所特徴量の各々について、取得されたセントロイドに対応して格納されたリファレンス画像に対する幾何特徴との比率又は差分を算出し、複数のリファレンス画像の各々について幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、算出されたリファレンス画像に対する幾何特徴との比率又は差分に対して設けられたリファレンス画像についての投票箱に投票し、リファレンス画像についての投票箱の投票結果に基づいて、クエリ画像とリファレンス画像との類似度を示すスコアを算出し、算出されたスコアに基づいて、クエリ画像と類似するリファレンス画像を出力することで、クエリ画像と類似するリファレンス画像を精度よく取得することができる、という効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】リファレンス画像を回転又は拡大率の変化をさせる処理を示す概念図である。
【図２】本発明の第１の実施の形態に係る画像検索装置の一構成例を示すブロック図である。
【図３】リファレンス画像のアフィン変換の処理を示す概念図である。
【図４】セントロイド管理テーブルの一例を示す概念図である。
【図５】セントロイド−リファレンス特徴ベクトル関係管理テーブルを示す概念図である。
【図６】幾何特徴に関する類似度の投票の処理を示す概念図である。
【図７】リファレンス画像及びクエリ画像の幾何特徴の一例を示す図である。
【図８】リファレンス画像とクエリ画像との幾何特徴の比率又は差分、及び投票の処理の一例を示す図である。
【図９】本発明の第１及び第２の実施の形態に係る画像検索装置の学習処理ルーチンの内容を示すフローチャートである。
【図１０】本発明の第１及び第２の実施の形態に係る画像検索装置の画像検索処理ルーチンの内容を示すフローチャートである。
【図１１】本発明の第１及び第２の実施の形態に係る画像検索装置の画像検索処理ルーチンの内容を示すフローチャートである。
【図１２】本発明の第２の実施の形態に係るクラスタリング装置の一構成例を示すブロック図である。
【図１３】本発明の第２の実施の形態に係る画像検索装置の一構成例を示すブロック図である。
【図１４】従来技術を説明するための説明図である。
【図１５】従来技術を説明するための説明図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を詳細に説明する。以下では、まず本発明の実施の形態の概要について説明する。
【００１７】
＜本発明の実施の形態の概要＞
本発明の実施の形態では、まず画像から局所特徴量を抽出する。次に、図１に示すように、画像を上下方向、左右方向、及び二次元平面内で回転させると共に、拡大率を変化させた複数の変換画像を作成し、変換画像からも局所特徴量を抽出しておく。これにより、例えば、上記図１５におけるクエリ画像２から抽出した局所特徴量は、上記図１におけるリファレンス画像５から抽出した局所特徴量と多くマッチし、クエリ画像２とリファレンス画像との類似度が高いと判定することができる。
【００１８】
具体的には、本発明の実施の形態では、まず、事前処理として、予め登録する各リファレンス画像について、局所特徴量及び当該局所特徴量の幾何特徴を抽出しておく。また、抽出した局所特徴量をクラスタリングしておく。そして、クエリ画像が入力されたとき、クエリ画像からも局所特徴量及び当該局所特徴量の幾何特徴を抽出し、各局所特徴量に対応するクラスタに属するリファレンス画像の局所特徴量について、幾何特徴の比率又は差分の一貫性を検証する。クエリ画像の局所特徴量に対して、幾何特徴の比率又は差分の一貫性の高い局所特徴量を持つリファレンス画像を、クエリ画像との類似度が高いとして出力する。
【００１９】
［第１の実施の形態］
＜画像検索装置１００の構成＞
第１の実施の形態に係る画像検索装置１００の構成について説明する。第１の実施の形態では、複数のリファレンス画像から、クエリ画像と類似するリファレンス画像を検索する画像検索装置に本発明を適用させた場合について説明する。図２に示すように、本発明に係る画像検索装置１００は、ＣＰＵと、ＲＡＭと、後述する学習処理ルーチン及び画像検索処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この画像検索装置１００は、機能的には図２に示すように、入力部１と、演算部２と、出力部３とを備えている。
【００２０】
入力部１は、複数のリファレンス画像を含むリファレンス画像集合と、クエリ画像との入力を受け付ける。
【００２１】
演算部２は、局所特徴量抽出部２０と、クラスタリング部２２と、セントロイド格納部２４と、インデクス格納部２６と、セントロイド取得部２８と、投票部３０と、スコア部３２と、類似画像出力部３４とを備えている。
【００２２】
局所特徴量抽出部２０は、入力部１により入力された複数のリファレンス画像の各々について、当該リファレンス画像に対して回転又は拡大率の変化を含む複数の変換を行って、複数の変換画像を生成する。そして、局所特徴量抽出部２０は、生成された複数の変換画像、及びリファレンス画像の各々から、局所特徴量及び幾何特徴を抽出する。
【００２３】
また、局所特徴量抽出部２０は、入力部１により入力されたクエリ画像に基づいて、リファレンス画像と同様に、クエリ画像に対して回転又は拡大率の変化を含む複数の変換を行って、複数の変換画像を生成する。そして、局所特徴量抽出部２０は、クエリ画像及び複数の変換画像の各々から、局所特徴量及び幾何特徴を抽出する。本発明の実施の形態では、画像の拡大率及び三軸の画像の回転角を、幾何特徴として抽出する。
【００２４】
具体的には、局所特徴量抽出部２０は、リファレンス画像集合が入力された際、まず複数のリファレンス画像の各々から局所特徴量を抽出する。局所特徴量としては、例えば、回転パラメータ及びスケールパラメータを用いない場合のＳＩＦＴ（Scale Invariant Feature Transform）を用いることができる。局所特徴量は、リファレンス画像だけでなく、リファレンス画像を上下方向、左右方向および二次元平面内で回転させ、拡大率を変化させた変換画像からも抽出する。なお、局所特徴量は、ベクトル形式で表現される。リファレンス画像を回転させた変換画像は、例えば、リファレンス画像のアフィン変換により生成することができる。
【００２５】
アフィン変換によって、変換前の画像における点（ｘ，ｙ）は、変換後の画像において以下の式（１）に示す点（ｘ’，ｙ’）に対応する。図３に、リファレンス画像をアフィン変換によって回転させる処理の一例を示す概念図を示す。
【００２６】
【数１】
0005995916.tif 000002
【００２７】
ただし、ｓはクエリ画像及びリファレンス画像の拡大率、θ、φ、ψは上記図３に示した３軸の回転角度である。拡大率ｓ、及び回転角度θ、φ、ψは幾何特徴の一例である。
【００２８】
また、局所特徴量抽出部２０は、クエリ画像が入力された際、リファレンス画像集合が入力された際と同様に、クエリ画像から局所特徴量及び対応する幾何特徴を抽出する。
【００２９】
なお、利用する局所特徴量が回転角を表すパラメータが算出される局所特徴量であった場合、ψを変化させたリファレンス画像を作成せず、ψの値として局所特徴量の回転角を表すパラメータを使用してもよい。また、利用する局所特徴量が拡大率（スケール）を表すパラメータが算出される局所特徴量であった場合、ｓを変化させたリファレンス画像を作成せず、ｓの値として局所特徴量の拡大率を表すパラメータを使用してもよい。
【００３０】
クラスタリング部２２は、入力部１により入力された複数のリファレンス画像の各々について生成された複数の変換画像、及びリファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行い、局所特徴量の各々を複数のクラスタに分類する。クラスタリングの際のクラスタ数は、任意の値に予め設定してよい。また、クラスタリング部２２は、複数のクラスタの各々について、当該クラスタのセントロイドを求める。セントロイドとは、例えば、クラスタに属する局所特徴量の重心を求めた特徴量である。そして、クラスタリング部２２は、複数のクラスタの各々について求めたセントロイドの特徴量を、クラスタリング結果として、後述するセントロイド格納部２４に格納する。
【００３１】
また、クラスタリング部２２は、入力部１により入力された複数のリファレンス画像の各々に対し、複数の変換画像、及び当該リファレンス画像の各々から抽出された局所特徴量の各々について、当該局所特徴量が属するクラスタのセントロイド、及び当該局所特徴量に対応する幾何特徴を、後述するインデクス格納部２６に格納する。
【００３２】
セントロイド格納部２４には、クラスタリング部２２によって求められた複数のクラスタの各々についてのセントロイドの特徴量が格納される。セントロイド格納部２４に格納されるクラスタリング結果の一例を図４に示す。図４に示すクラスタリング結果は、セントロイドＩＤと特徴量との組み合わせを示すデータである。
【００３３】
なお、セントロイドＩＤはクラスタのセントロイドを識別するＩＤである。上記図４に示したセントロイド格納部２４に格納されるクラスタリング結果は一例であり、格納される属性や名称が異なっていてもよい。また、テキストファイル形式など、テーブル以外の形式で保存されていてもよい。
【００３４】
インデクス格納部２６には、複数のリファレンス画像の各々に対し、当該リファレンス画像から抽出された局所特徴量が属するクラスタのセントロイド、及び当該局所特徴量に対応する幾何特徴が格納される。インデクス格納部２６に格納されるデータの一例を図５に示す。上記図５に示すデータは、リファレンス画像の画像ＩＤと局所特徴量ＩＤとセントロイドＩＤと幾何特徴の各々との組み合わせを示すデータである。画像ＩＤ及び局所特徴量ＩＤは、リファレンス画像及び局所特徴量を識別するＩＤである。また、上記図５に示したインデクス格納部２６に格納されるデータは一例であり、格納される属性や名称が異なっていてもよい。また、テキストファイル形式など、テーブル以外の形式で保存されていてもよい。
【００３５】
セントロイド取得部２８は、局所特徴量抽出部２０によって抽出されたクエリ画像の局所特徴量の各々について、セントロイド格納部２４に格納された複数のクラスタの各々に対するセントロイドの各々の特徴量と、当該クエリ画像の局所特徴量との類似度を算出し、当該クエリ画像の局所特徴量に対応するセントロイドを取得する。
【００３６】
具体的には、セントロイド取得部２８は、局所特徴量抽出部２０によって抽出されたクエリ画像の局所特徴量の各々を、セントロイド格納部２４に格納された各セントロイドの特徴量と比較し、当該局所特徴量と最も類似度の高いセントロイドを選択し、当該局所特徴量を当該セントロイドに対応するセントロイドＩＤに割り当てる。局所特徴量をセントロイドに割り当てるための類似度としては、例えば、局所特徴量とセントロイドの特徴量との距離を用いればよい。
【００３７】
投票部３０は、局所特徴量抽出部２０によって抽出されたクエリ画像の局所特徴量の各々について、セントロイド取得部２８によって取得されたセントロイドに対応してインデクス格納部２６に格納されたリファレンス画像に対する幾何特徴との比率又は差分を算出する。なお、本発明の実施の形態では、幾何特徴のうち拡大率については比率を算出し、回転角度については差分を算出する。
【００３８】
そして、投票部３０は、複数のリファレンス画像の各々について幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、算出されたリファレンス画像に対する幾何特徴との比率又は差分に対して設けられたリファレンス画像についての投票箱に投票する。
【００３９】
具体的には、投票部３０は、投票に際し、まずは投票対象となる投票箱を予め準備する。投票箱は、各リファレンス画像の画像ＩＤに対し、拡大率の比率、θの差分、φの差分、ψの差分の４次元空間を格子状に区切ることによって作成する。例えば、図６に示すように拡大率を８段階、θを６段階、φを６段階、ψを６段階に分けると、８×６×６×６=１７２８個の投票箱を、各リファレンス画像に対して作成する。
【００４０】
投票は、同一のセントロイドＩＤに対応する、リファレンス画像とクエリ画像との局所特徴量の各組み合わせについて行う。例えば、図７に示すようにＩＤ１及びＩＤ２のリファレンス画像からＲ１，Ｒ２，Ｒ３，Ｒ４、クエリ画像からＱ１とＱ２との局所特徴量が抽出されたとすると、投票の対象はＲ１とＱ１、Ｒ３とＱ１、Ｒ２とＱ２、Ｒ４とＱ２の組み合わせとなる。投票の結果の一例を図８に示す。
【００４１】
図８に示すように、画像ＩＤ１についての投票箱Ａには、Ｒ１とＱ１及びＲ２とＱ２の組み合わせより２票が投票される。また、画像ＩＤ２についての投票箱ＢにはＲ３とＱ１との組み合わせより１票、投票箱ＣにはＲ４とＱ２との組み合わせより１票が投票され、その他の投票箱に投票された票数は０である。画像ＩＤ１についての投票箱の中で最も多く投票された投票箱の票数は２、画像ＩＤ２についての投票箱の中で最も多く投票された投票箱の票数は１であり、これが各画像ＩＤのスコアとなる。クエリ画像はリファレンス画像ＩＤ１ともＩＤ２とも、セントロイドＩＤが共通する局所特徴量を２つ有しているが、以上のようにして、リファレンス画像ＩＤ１の方がＩＤ２に比べてクエリ画像との類似度が高いと判定することができる。
【００４２】
また、１回あたりの投票の投票数を、クエリ画像又はリファレンス画像における、同一セントロイドに対応する局所特徴量の数によって重みづけしてもよい。例えば、クエリ画像の局所特徴量に対応するセントロイドについて、当該セントロイドに対応する局所特徴量が、クエリ画像にｎｑ個、リファレンス画像にｎｒ個あった場合、当該セントロイドについての投票における投票数ｗｖを以下の式（２）の値とすることができる。
【００４３】
【数２】
0005995916.tif 000003
【００４４】
上記式（２）に示した投票数を用いることにより、例えば、ビルの画像における窓のように同じセントロイドに対応する局所特徴量が大量に含まれる場合に、画像の類似度が窓の個数だけで決定されてしまうのを避け、窓以外の局所特徴量も考慮して類似する画像を取得することが可能になる。
【００４５】
また、クエリ画像の局所特徴量に対応するセントロイドについて、当該セントロイドに対応する局所特徴量が、クエリ画像にｎｑ個あった場合、当該セントロイドについての投票における投票数ｗｖを以下の式（３）の値とすることができる。
【００４６】
【数３】
0005995916.tif 000004
【００４７】
また、クエリ画像の局所特徴量に対応するセントロイドについて、当該セントロイドに対応する局所特徴量が、リファレンス画像にｎｒ個あった場合、当該セントロイドについての投票における投票数ｗｖを以下の式（４）の値とすることができる。
【００４８】
【数４】
0005995916.tif 000005
【００４９】
また、１回あたりの投票の投票数を、リファレンス画像集合において各セントロイドに対応する局所特徴量が何枚のリファレンス画像に含まれていたかによって重みづけしてもよい。例えば、全画像数がＮであり、クエリ画像の局所特徴量に対応するセントロイドについて、当該セントロイドに対応する局所特徴量がｎｆ枚のリファレンス画像から抽出されていた場合、当該セントロイドについての投票における投票数ｗｖを以下の式（５）の値とすることができる。
【００５０】
【数５】
0005995916.tif 000006
【００５１】
上記式（５）に示した投票数を用いることにより、多くの画像に含まれるセントロイドに関する投票で類似度が決まってしまうのを避け、珍しいセントロイドが対応したときにはより類似していると判定されやすくすることが可能になる。
【００５２】
また、１回あたりの投票の投票数を、リファレンス画像における局所特徴量の数によって重みづけしてもよい。例えば、あるリファレンス画像から抽出された局所特徴量の数がＮｒ個であった場合、当該リファレンス画像についての投票箱に対する投票における投票数ｗｖを以下の式の値とすることができる。
【００５３】
【数６】
0005995916.tif 000007
【００５４】
上記式（６）に示した票数を用いることにより、リファレンス画像から大量の局所特徴量が抽出された場合に類似度が高くなりやすく、一方で少量の局所特徴量が抽出された場合には類似度が低くなりやすくなるのを避け、クエリ画像とリファレンス画像とにおいて局所特徴量のセントロイドＩＤが共通する割合を考慮して類似度を算出することが可能になる。
【００５５】
上記式（２）、式（５）及び式（６）の重みづけはそれぞれ同時に用いることができ、３つの重みづけを同時に用いた場合、投票における投票数ｗｖは以下の式（７）の値となる。
【００５６】
【数７】
0005995916.tif 000008
【００５７】
スコア部３２は、複数のリファレンス画像の各々に対し、当該リファレンス画像についての投票箱の投票結果に基づいて、クエリ画像とリファレンス画像との類似度を示すスコアを算出する。具体的には、スコア部３２は、リファレンス画像の画像ＩＤに対応する複数の投票箱の投票結果を集約することにより、リファレンス画像のスコアを算出する。
【００５８】
例えば、スコア部３２は、複数のリファレンス画像の各々に対し、当該リファレンス画像についての投票箱の各々の投票数のうち、最大の投票数を当該リファレンス画像のスコアとして算出する。
【００５９】
類似画像出力部３４は、スコア部３２によって算出されたスコアに基づいて、クエリ画像と類似するリファレンス画像を出力する。具体的には、類似画像出力部３４は、算出したリファレンス画像のスコアを高い順にソートし、スコアの高いリファレンス画像の画像ＩＤを出力する。
【００６０】
出力部３は、類似画像出力部３４によって出力されたリファレンス画像の画像ＩＤをリストとして出力する。
【００６１】
＜画像検索装置１００の作用＞
次に、第１の実施の形態に係る画像検索装置１００の作用について、まず、リファレンス画像を登録する学習処理ルーチンについて説明する。入力部１において複数のリファレンス画像を含むリファレンス画像集合の入力を受け付けると、画像検索装置１００は、図９に示す学習処理ルーチンを実行する。
【００６２】
まず、ステップＳ１００では、入力部１において受け付けたリファレンス画像集合を取得する。
【００６３】
次に、ステップＳ１０２では、上記ステップＳ１００で取得したリファレンス画像集合から、１つのリファレンス画像を設定する。
【００６４】
次に、ステップＳ１０４において、局所特徴量抽出部２０によって、上記ステップＳ１０２で設定したリファレンス画像に対して、回転又は拡大率の変化を含む複数の変換を行って、複数の変換画像を生成する。
【００６５】
ステップＳ１０６において、局所特徴量抽出部２０によって、上記ステップＳ１０４で生成された複数の変換画像、及び上記ステップＳ１０２で設定されたリファレンス画像の各々から局所特徴量及び幾何特徴を抽出する。
【００６６】
ステップＳ１０８において、上記ステップＳ１００で取得したリファレンス画像集合に含まれる全てのリファレンス画像について上記ステップＳ１０２〜上記ステップＳ１０６の処理が終了したかを判定し、終了していなければステップＳ１０２へ戻って処理を繰り返し、終了していればステップＳ１１０へ移行する。
【００６７】
ステップＳ１１０において、クラスタリング部２２によって、上記ステップＳ１０６で抽出された局所特徴量に対してクラスタリングを行い、局所特徴量の各々を複数のクラスタに分類する。
【００６８】
ステップＳ１１２において、クラスタリング部２２によって、上記ステップＳ１１０で求められた複数のクラスタの各々について、当該クラスタのセントロイドを求める。そして、クラスタリング部２２によって、複数のクラスタの各々について求めたセントロイドの特徴量を、セントロイド格納部２４に格納する。
【００６９】
ステップＳ１１４において、クラスタリング部２２によって、上記ステップＳ１０６で抽出された複数の局所特徴量のうち、１つの局所特徴量を設定する。
【００７０】
ステップＳ１１６において、クラスタリング部２２によって、上記ステップＳ１１４で設定された局所特徴量について、当該局所特徴量に対応するリファレンス画像の画像ＩＤ、当該局所特徴量が属するクラスタのセントロイドＩＤ、及び当該局所特徴量に対応する幾何特徴（拡大率ｓ、及び回転角度θ、φ、ψ）を、インデクス格納部２６に格納する。
【００７１】
ステップＳ１１８において、上記ステップＳ１０６で抽出された全ての局所特徴量について上記ステップＳ１１４〜上記ステップＳ１１６の処理が終了したかを判定し、終了していなければステップＳ１１４へ戻って処理を繰り返し、終了していれば、処理を終了する。学習処理ルーチンの終了により、リファレンス画像の登録は完了となる。
【００７２】
次に、クエリ画像を入力し、クエリ画像と類似するリファレンス画像を取得する画像検索処理ルーチンについて説明する。入力部１においてクエリ画像の入力を受け付けると、画像検索装置１００は、図１０及び図１１に示す画像検索処理ルーチンを実行する。
【００７３】
まず、ステップＳ２００では、入力部１において入力を受け付けたクエリ画像を取得する。
【００７４】
次に、ステップＳ２０２では、局所特徴量抽出部２０によって、上記ステップＳ２００で取得したクエリ画像に対し、回転又は拡大率の変化を含む複数の変換を行って、複数の変換画像を生成する。
【００７５】
ステップＳ２０４では、局所特徴量抽出部２０によって、上記ステップＳ２００で取得したクエリ画像及び上記ステップＳ２０２で生成された複数の変換画像の各々から、局所特徴量及び幾何特徴を抽出する。
【００７６】
ステップＳ２０６では、上記ステップＳ２０４で抽出された局所特徴量の各々のうち、１つの局所特徴量を設定する。
【００７７】
ステップＳ２０８では、セントロイド取得部２８によって、上記ステップＳ２０６で設定されたクエリ画像の局所特徴量について、セントロイド格納部２４に格納された複数のクラスタの各々に対するセントロイドの各々と、上記ステップＳ２０６で設定されたクエリ画像の局所特徴量との類似度を算出し、上記ステップＳ２０６で設定されたクエリ画像の局所特徴量に対応するセントロイドを取得する。そして、セントロイド取得部２８は、上記ステップＳ２０６で設定されたクエリ画像の局所特徴量に対して、取得されたセントロイドに対応するセントロイドＩＤを割り当てる。
【００７８】
ステップＳ２１０では、投票部３０によって、上記ステップＳ２０８で割り当てられたセントロイドＩＤに対応してインデクス格納部２６に格納されたリファレンス画像の１つの局所特徴量を設定する。
【００７９】
そして、ステップＳ２１２では、投票部３０によって、上記ステップＳ２１０で設定された局所特徴量の局所特徴量ＩＤに対応する、インデクス格納部２６に格納された画像ＩＤと幾何特徴とを取得する。
【００８０】
ステップＳ２１４では、投票部３０によって、上記ステップＳ２１０で設定された局所特徴量に対応する幾何特徴と、上記ステップＳ２１２で取得された画像ＩＤに対応するリファレンス画像の幾何特徴との比率又は差分を算出する。そして、投票部３０によって、上記ステップＳ２１２で取得された画像ＩＤに対応するリファレンス画像について幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、算出された比率又は差分に対して設けられたリファレンス画像についての投票箱に投票する。
【００８１】
ステップＳ２１６では、上記ステップＳ２０８で割り当てられたセントロイドＩＤに対応する全ての局所特徴量について上記ステップＳ２１２〜上記ステップＳ２１４の処理が終了したか否かを判定し、終了していなければステップＳ２１０へ戻って処理を繰り返し、終了していれば、ステップＳ２１８へ移行する。
【００８２】
ステップＳ２１８では、上記ステップＳ２０４で抽出されたクエリ画像の全ての局所特徴量について上記ステップＳ２０６〜上記ステップＳ２１６の処理が終了したか否かを判定し、終了していなければステップＳ２０６へ戻って処理を繰り返し、終了していれば、ステップＳ２２０へ移行する。
【００８３】
ステップＳ２２０では、リファレンス画像集合から、１つのリファレンス画像を設定する。
【００８４】
ステップＳ２２２では、スコア部３２によって、上記ステップＳ２２０で設定されたリファレンス画像についての投票箱の各々の投票数のうち、最大の投票数を当該リファレンス画像のスコアとして算出する。
【００８５】
ステップＳ２２４では、リファレンス画像集合に含まれる全てのリファレンス画像について、上記ステップＳ２２０〜ステップＳ２２２の処理が終了したか否かを判定し、終了していなければステップＳ２２０へ戻って処理を繰り返し、終了していれば、ステップＳ２２６へ移行する。
【００８６】
ステップＳ２２６では、類似画像出力部３４によって、上記ステップＳ２２２で算出したリファレンス画像のスコアを高い順にソートし、スコアの高いリファレンス画像の画像ＩＤを出力する。
【００８７】
ステップＳ２２８では、類似画像出力部３４によって出力されたリファレンス画像ＩＤをリストとして出力部３により出力し、処理を終了する。
【００８８】
以上説明したように、第１の実施の形態に係る画像検索装置１００によれば、複数のリファレンス画像の各々について、当該リファレンス画像に対して回転又は拡大率の変化を含む複数の変換を行って生成された複数の変換画像、及びリファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行って局所特徴量の各々が分類された複数のクラスタの各々に対して求められたセントロイドの特徴量を格納し、抽出された局所特徴量の各々について、局所特徴量が属するクラスタのセントロイド、及び幾何特徴を格納し、クエリ画像に対して複数の変換を行って複数の変換画像を生成し、クエリ画像及び複数の変換画像の各々から、局所特徴量及び幾何特徴を抽出し、抽出されたクエリ画像の局所特徴量の各々について、複数のクラスタの各々に対するセントロイドの各々の特徴量と、クエリ画像の局所特徴量との類似度を算出し、クエリ画像の局所特徴量に対応するセントロイドを取得し、抽出されたクエリ画像の局所特徴量の各々について、取得されたセントロイドに対応して格納されたリファレンス画像に対する幾何特徴との比率又は差分を算出し、複数のリファレンス画像の各々について幾何特徴の比率又は差分の各々に対して設けられた投票箱のうち、算出されたリファレンス画像に対する幾何特徴との比率又は差分に対して設けられたリファレンス画像についての投票箱に投票し、リファレンス画像についての投票箱の投票結果に基づいて、クエリ画像とリファレンス画像との類似度を示すスコアを算出し、算出されたスコアに基づいて、クエリ画像と類似するリファレンス画像を出力することで、クエリ画像と類似するリファレンス画像を精度よく取得することができる。
【００８９】
また、クエリ画像について、同一の被写体が写っている画像をあらかじめ登録しておいたリファレンス画像中から高速かつ高精度に取得することができる。
【００９０】
また、画像の各局所特徴量について、局所特徴量の類似度及び幾何特徴の比率又は差分に基づいて、対応する投票箱に投票し、リファレンス画像の画像ＩＤに対応する複数の投票箱に投票された結果を集約し、より多くの投票がなされたリファレンス画像を類似度が高いと判定することにより、同一物体で視点方向や拡大率の異なる画像を類似度が高いと判定することが可能になる。
【００９１】
また、幾何特徴として局所特徴量の拡大率及び三次元空間での各回転角を抽出することにより、二次元平面内だけでなく、上下方向や左右方向に視点が変化した場合にも、画像間の類似度が高いと判定することが可能になる。
【００９２】
また、リファレンス画像１枚につき、拡大率の比率および３軸の各回転角の差分の４次元空間を格子状に区切った各領域の投票箱を作成し、各リファレンス画像に対応する投票箱の投票結果で最大の値をリファレンス画像のスコアとすることにより、三次元空間において、どの視点から見ている可能性が最も高いかを判別し、その方向から見た場合の局所特徴量との幾何的な一貫性を検証することが可能になる。
【００９３】
また、クエリ画像又はリファレンス画像において同一セントロイドに対応する局所特徴量数、リファレンス画像集合において各セントロイドが何枚の画像に含まれていたか、及びリファレンス画像における局所特徴量の総数の少なくとも１つ以上を用いて投票の投票数を重みづけすることにより、ある画像に同じセントロイドに対応する局所特徴量が大量に含まれる場合に類似度が当該セントロイドに対応する局所特徴量だけで決定されてしまうのを避ける、または、多くの画像に含まれるセントロイドに関する投票で類似度が決まってしまうのを避ける、または、リファレンス画像から大量の局所特徴量が抽出された場合に類似度が高く、少量の局所特徴量が抽出された場合には類似度が低くなりやすくなるのを避けることが可能になる。
【００９４】
［第２の実施の形態］
次に、第２の実施の形態について説明する。第２の実施の形態では、リファレンス画像の各々から抽出された局所特徴量に対してクラスタリングを行う処理と、クエリ画像とリファレンス画像との類似度を示すスコアを算出し、算出されたスコアに基づいて、クエリ画像と類似するリファレンス画像を出力する処理とを別々の装置で行う点が、第１の実施の形態と異なっている。
【００９５】
第２の実施の形態では、クラスタリング装置２００が学習処理ルーチンを実行し、画像検索装置２１０が画像検索処理ルーチンを実行する。なお、第１の実施の形態に係る画像検索装置１００と同一の構成となる部分については、同一符号を付して、詳細な説明を省略する。
【００９６】
＜クラスタリング装置２００の構成＞
図１２に示すように、第２の実施の形態に係るクラスタリング装置２００は、入力部４と、演算部５とを備えている。
【００９７】
入力部４は、複数のリファレンス画像を含むリファレンス画像集合を受け付ける。
【００９８】
演算部５は、局所特徴量抽出部５０と、クラスタリング部２２と、セントロイド格納部２４と、インデクス格納部２６とを備えている。
【００９９】
局所特徴量抽出部５０は、局所特徴量抽出部２０と同様に、入力部１により入力された複数のリファレンス画像の各々について、当該リファレンス画像に対して回転又は拡大率の変化を含む複数の変換を行って、複数の変換画像を生成する。そして、局所特徴量抽出部２０は、生成された複数の変換画像、及びリファレンス画像の各々から、局所特徴量及び幾何特徴を抽出する。
【０１００】
＜画像検索装置２１０の構成＞
図１３に示すように、第２の実施の形態に係る画像検索装置２１０は、入力部６と、演算部７と、出力部３とを備えている。
【０１０１】
入力部６は、クエリ画像の入力を受け付ける。
【０１０２】
演算部７は、局所特徴量抽出部７０と、セントロイド格納部７４と、インデクス格納部７６と、セントロイド取得部２８と、投票部３０と、スコア部３２と、類似画像出力部３４とを備えている。
【０１０３】
局所特徴量抽出部７０は、局所特徴量抽出部２０と同様に、入力部１により入力されたクエリ画像に基づいて、クエリ画像に対して回転又は拡大率の変化を含む複数の変換を行って、複数の変換画像を生成する。そして、局所特徴量抽出部７０は、クエリ画像及び複数の変換画像の各々から、局所特徴量及び幾何特徴を抽出する。
【０１０４】
セントロイド格納部７４には、クラスタリング装置２００のクラスタリング部２２によって求められた複数のクラスタの各々についてのセントロイドの特徴量が格納される。
【０１０５】
インデクス格納部７６には、複数のリファレンス画像の各々に対し、クラスタリング装置２００のクラスタリング部２２によって求められた局所特徴量が属するクラスタのセントロイド、及び当該局所特徴量に対応する幾何特徴が格納される。
【０１０６】
次に、第２の実施の形態に係るクラスタリング装置２００及び画像検索装置２１０の作用について説明する。
【０１０７】
＜クラスタリング装置２００の作用＞
まず、クラスタリング装置２００の作用について説明する。入力部１において複数のリファレンス画像を含むリファレンス画像集合の入力を受け付けると、クラスタリング装置２００は、上記図９に示す学習処理ルーチンを実行し、セントロイド格納部２４には、複数のクラスタの各々についてのセントロイドの特徴量が格納され、インデクス格納部２６には、複数のリファレンス画像の各々に対しての局所特徴量が属するクラスタのセントロイド、及び当該局所特徴量に対応する幾何特徴が格納される。
【０１０８】
＜画像検索装置２１０の作用＞
次に、画像検索装置２１０の作用について説明する。まず、クラスタリング装置２００のセントロイド格納部２４に格納されている複数のクラスタの各々についてのセントロイドの特徴量が、画像検索装置２１０に入力されると、セントロイド格納部７４に格納される。また、クラスタリング装置２００のインデクス格納部２６に格納されている複数のリファレンス画像の各々に対しての局所特徴量が属するクラスタのセントロイド、及び当該局所特徴量に対応する幾何特徴が入力されると、インデクス格納部７６に格納される。そして、入力部６においてクエリ画像の入力を受け付けると、画像検索装置２１０によって、図１０及び図１１に示す画像検索処理ルーチンが実行され、クエリ画像と類似するリファレンス画像の画像ＩＤが出力される。
【０１０９】
なお、第２の実施の形態に係るクラスタリング装置２００及び画像検索装置２１０の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１１０】
以上説明したように、第２の実施の形態に係るクラスタリング装置２００及び画像検索装置２１０によれば、クエリ画像と類似するリファレンス画像を精度よく取得することができる。
【０１１１】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１１２】
例えば、上記第１の実施の形態に係る画像検索装置１００及び第２の実施の形態に係るクラスタリング装置２００は、セントロイド格納部２４、及びインデクス格納部２６を備えている場合について説明したが、例えばセントロイド格納部２４、及びインデクス格納部２６の少なくとも１つが画像検索装置１００の外部装置に設けられ、画像検索装置１００は、外部装置と通信手段を用いて通信することにより、セントロイド格納部２４、及びインデクス格納部２６の少なくとも１つを参照するようにしてもよい。
【０１１３】
また、上記第２の実施の形態に係る画像検索装置２１０は、セントロイド格納部７４、及びインデクス格納部７６を備えている場合について説明したが、例えばセントロイド格納部７４、及びインデクス格納部７６の少なくとも１つが画像検索装置２１０の外部装置に設けられ、画像検索装置２１０は、外部装置と通信手段を用いて通信することにより、セントロイド格納部７４、及びインデクス格納部７６の少なくとも１つを参照するようにしてもよい。
【０１１４】
また、上述の画像検索装置１００、クラスタリング装置２００、及び画像検索装置２１０は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０１１５】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１１６】
１，４，６  入力部
２，５，７  演算部
３     出力部
２０，５０，７０  局所特徴量抽出部
２２   クラスタリング部
２４，７４    セントロイド格納部
２６，７６    インデクス格納部
２８   セントロイド取得部
３２   スコア部
３０   投票部
３４   類似画像出力部
１００ 画像検索装置
２００ クラスタリング装置
２１０ 画像検索装置
【図２】
0005995916.tif 000009
【図４】
0005995916.tif 000010
【図５】
0005995916.tif 000011
【図７】
0005995916.tif 000012
【図９】
0005995916.tif 000013
【図１０】
0005995916.tif 000014
【図１１】
0005995916.tif 000015
【図１２】
0005995916.tif 000016
【図１３】
0005995916.tif 000017
【図１４】
0005995916.tif 000018
【図１】
0005995916.tif 000019
【図３】
0005995916.tif 000020
【図６】
0005995916.tif 000021
【図８】
0005995916.tif 000022
【図１５】
0005995916.tif 000023