(57)【要約】【課題】ビジュアルキーワードにより画像から生成する特徴ベクトルの精度を高めることである。【解決手段】クエリ画像Ｇ１の部分画像Ｇ１０が属するクラスタ＃２に、検索対象画像Ｇ３及びＧ５から抽出した部分画像Ｇ３０及びＧ５０も属する場合、クエリ画像Ｇ１、検索対象画像Ｇ３、Ｇ５の特徴ベクトルのクラスタ＃２に対応したスカラ値は、中心点Ｃからの距離に応じてそれぞれ加算される。各画像の特徴ベクトルのクラスタ＃２に対応したスカラ値には、クエリ画像Ｇ１では距離ｄ１、検索対象画像Ｇ３では距離ｄ３、検索対象画像Ｇ５では距離ｄ５にそれぞれ基づいた重み値が加算される。【選択図】図４
2011128773.tif 000002
【特許請求の範囲】
【請求項１】
画像データから特徴ベクトルを生成し、その特徴ベクトル間の類似度に基づいて類似画像を検索する画像検索装置において、
前記画像データから複数の部分画像を抽出する部分画像抽出手段と、
前記抽出された部分画像が有する特徴量に基づいて前記複数の部分画像を予め形成されたクラスタに分類する分類手段と、
前記部分画像が有する特徴量と、該部分画像が分類されたクラスタが有する特徴量との特徴量空間における距離を算出する距離算出手段と、
前記算出された距離に基づいた重み値を前記部分画像が属するクラスタ毎に加算し、該クラスタ毎に加算した値をスカラ値とした特徴ベクトルを生成する特徴ベクトル生成手段と、
を備えることを特徴とする画像検索装置。
【請求項２】
画像データの有する特徴量に基づいて複数の画像データを予めクラスタリングすることで形成したクラスタが有する特徴量を該クラスタ毎に対応付けて記憶するクラスタ記憶手段を更に備え、
前記分類手段は、
前記部分画像が有する特徴量と、前記クラスタ記憶手段に記憶されたクラスタの特徴量との距離を算出し、その距離に基づいて該部分画像の分類を行い、
前記特徴ベクトル生成手段は、
前記算出された距離と、前記形成されたクラスタの特徴量から該クラスタに属する画像データの特徴量までの距離とに基づいて前記重み値を求めることを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記特徴ベクトル生成手段は、
前記距離算出手段により算出された前記クラスタの特徴量の距離が、前記クラスタリングされた該クラスタの特徴量から最遠の画像データの特徴量までの距離以上である場合には、前記重み値を０とすることを特徴とする請求項２に記載の画像検索装置。
【請求項４】
前記特徴ベクトル生成手段は、
前記距離算出手段により算出された前記クラスタの特徴量の距離が、前記クラスタリングされた該クラスタの特徴量から直近の画像データまでの距離以下である場合には、前記重み値を１とすることを特徴とする請求項２又は３に記載の画像検索装置。
【請求項５】
前記特徴ベクトル生成手段は、
前記クラスタリングにより形成されたクラスタのうち、その前記特徴量空間におけるクラスタの大きさが最小であるクラスタの大きさに基づいて、前記重み値を正規化することを特徴とする請求項２〜４の何れか一項に記載の画像検索装置。
【請求項６】
コンピュータが、画像データから特徴ベクトルを生成し、その特徴ベクトル間の類似度に基づいて類似画像を検索する画像検索方法において、
前記画像データから複数の部分画像を抽出する部分画像抽出ステップと、
前記抽出された部分画像が有する特徴量に基づいて前記複数の部分画像を予め形成されたクラスタに分類する分類ステップと、
前記部分画像が有する特徴量と、該部分画像が分類されたクラスタが有する特徴量との特徴量空間における距離を算出する距離算出ステップと、
前記算出された距離に基づいた重み値を前記部分画像が属するクラスタ毎に加算し、該クラスタ毎に加算した値をスカラ値とした特徴ベクトルを生成する特徴ベクトル生成ステップと、
を行うことを特徴とする画像検索方法。
【請求項７】
請求項６に記載の画像検索方法を前記コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像データの有する特徴量に基づいて類似画像を検索する画像検索装置、画像検索方法及びプログラムに関する。
【背景技術】
【０００２】
画像を検索キーとして入力し、画像の特徴量（配色、テクスチャ、形状等の画像の特徴を数値化して表現したもの）を比較することにより、検索キーである画像（以下「クエリ画像」という）に類似する画像を検索する技術が知られている。ユーザがクエリ画像を入力すると、クエリ画像から特徴量を抽出して、検索対象の画像の特徴量との類似度を算出することで、類似画像を検索する（例えば、特許文献１）。
【０００３】
１枚の画像から抽出される特徴量は、その画像全体の特徴を示すものであるため、全体的に類似している画像を検索する際に有効である。これに対し、画像を構成する部分的な領域による画像（以下「部分画像」という）が類似している画像を検索する場合には、一枚の画像が複数の領域により構成されていると捉えて、その部分画像毎の特徴量によって画像の特徴を表すことで、部分画像を重要視した類似画像検索が可能になる。
【０００４】
但し、画像を部分画像に分割して、その部分画像毎から算出した特徴量を単に比較するとなると、例えば、１００分割した画像であれば、１００×１００通りのパターンで特徴量を比較し類似度を算出するため、計算量が膨大となる。
【０００５】
そこで、部分画像を用いた計算量を抑えて類似度の算出が可能な部分画像ビジュアルキーワードという手法が考案された。ビジュアルキーワードでは、１枚の画像が複数の部分画像により構成されていると捉え、画像から部分画像を抽出して、予め画像がクラスタリングされて形成されたクラスタに対して、その部分画像を特徴量に基づいて分類し、各部分画像が属するクラスタの数に基づいて特徴ベクトルが生成される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００１−５２１７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
このように、ビジュアルキーワードでは、クラスタに基づいて画像が特徴付けされ、各クラスタの特徴量に基づいて類似度を算出するため、クラスタ数分の計算処理で類似度が求められる。
【０００８】
しかし、特徴ベクトルの生成は、クラスタリングやクラスタに対する分類の性能に影響を受ける。即ち、部分画像は何れかのクラスタに必ず分類されるため、そのクラスタと部分画像との類似性が低かったとしても、その類似性の低いクラスタに部分画像が属するとして計上されて特徴ベクトルが生成されることとなる。
【０００９】
このため、クラスタとの類似性の低い部分画像によって特徴ベクトルが生成されると、特許文献１のように特徴ベクトルの類似度を算出する際に、類似しない部分画像を有する画像同士の類似度が高く算出されてしまう可能性があった。従って、ビジュアルキーワードを用いた画像検索の精度が悪くなってしまった。
【００１０】
本発明は、上述の課題に鑑みて為されたものであり、その目的とするところは、ビジュアルキーワードにより画像から生成する特徴ベクトルの精度を高めることである。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、第１の発明は、画像データから特徴ベクトルを生成し、その特徴ベクトル間の類似度に基づいて類似画像を検索する画像検索装置において、
前記画像データから複数の部分画像を抽出する部分画像抽出手段と、
前記抽出された部分画像が有する特徴量に基づいて前記複数の部分画像を予め形成されたクラスタに分類する分類手段と、
前記部分画像が有する特徴量と、該部分画像が分類されたクラスタが有する特徴量との特徴量空間における距離を算出する距離算出手段と、
前記算出された距離に基づいた重み値を前記部分画像が属するクラスタ毎に加算し、該クラスタ毎に加算した値をスカラ値とした特徴ベクトルを生成する特徴ベクトル生成手段と、を備えることを特徴としている。
【００１２】
第１の発明によれば、画像データから抽出した部分画像の特徴量と、その部分画像が属するクラスタの特徴量との距離に基づいた重み値で特徴ベクトルの各クラスタのスカラ値を加算するため、部分画像が属するクラスタに対応するスカラ値を、そのクラスタとの類似性に応じて重み付けすることができる。これにより、画像データ間の類似度の算出において、各画像データの部分画像が属するクラスタとの類似性を加味した類似度が算出されるようになる。従って、ビジュアルキーワードにより生成される特徴ベクトルの精度を高めることができる。
【００１３】
また、第２の発明は、画像データの有する特徴量に基づいて複数の画像データを予めクラスタリングすることで形成したクラスタが有する特徴量を該クラスタ毎に対応付けて記憶するクラスタ記憶手段を更に備え、
前記分類手段は、
前記部分画像が有する特徴量と、前記クラスタ記憶手段に記憶されたクラスタの特徴量との距離を算出し、その距離に基づいて該部分画像の分類を行い、
前記特徴ベクトル生成手段は、
前記算出された距離と、前記形成されたクラスタの特徴量から該クラスタに属する画像データの特徴量までの距離とに基づいて前記重み値を求めることを特徴としている。
【００１４】
第２の発明によれば、画像データが予めクラスタリングされて形成されたクラスタの特徴量から、該クラスタに属する画像データまでの距離を重み値の算出の指標に加えることにより、分類の基準となったクラスタの特性を加味した特徴ベクトルを生成できる。
【００１５】
また、第３の発明における前記特徴ベクトル生成手段は、前記距離算出手段により算出された前記クラスタの特徴量の距離が、前記クラスタリングされた該クラスタの特徴量から最遠の画像データの特徴量までの距離以上である場合には、前記重み値を０とすることを特徴としている。
【００１６】
第３の発明によれば、クラスタの特徴量から部分画像の特徴量までの距離が離れている場合に、該部分画像がクラスタに属さないと見なしたことに相当する０に重み値を設定することで、クラスタとの類似性を有さない部分画像についてのスカラ値への加算を行わず、クラスタ毎のスカラ値を有する特徴ベクトルの特徴づけを際立たせることができる。
【００１７】
また、第４の発明における前記特徴ベクトル生成手段は、
前記距離算出手段により算出された前記クラスタの特徴量の距離が、前記クラスタリングされた該クラスタの特徴量から直近の画像データまでの距離以下である場合には、前記重み値を１とすることを特徴としている。
【００１８】
第４の発明によれば、クラスタの特徴量から部分画像の特徴量までの距離が近い場合に、該部分画像がクラスタに属していると見なしたことに相当する１に重み値を設定することで、クラスタと類似性の高い部分画像についてのスカラ値を確実に高めて、クラスタ毎のスカラ値を有する特徴ベクトルの特徴づけを際立たせることができる。
【００１９】
また、第５の発明における前記特徴ベクトル生成手段は、前記クラスタリングにより形成されたクラスタのうち、その前記特徴量空間におけるクラスタの大きさが最小であるクラスタの大きさに基づいて、前記重み値を正規化することを特徴としている。
【００２０】
第５の発明によれば、形成されたクラスタのうち、クラスタの大きさが最小であるクラスタの大きさに基づいて重み値を正規化するため、クラスタ間の大きさの違いによる重み値のブレを低めることができる。
【００２１】
また、第６の発明は、コンピュータが、画像データから特徴ベクトルを生成し、その特徴ベクトル間の類似度に基づいて類似画像を検索する画像検索方法において、
前記画像データから複数の部分画像を抽出する部分画像抽出ステップと、
前記抽出された部分画像が有する特徴量に基づいて前記複数の部分画像を予め形成されたクラスタに分類する分類ステップと、
前記部分画像が有する特徴量と、該部分画像が分類されたクラスタが有する特徴量との特徴量空間における距離を算出する距離算出ステップと、
前記算出された距離に基づいた重み値を前記部分画像が属するクラスタ毎に加算し、該クラスタ毎に加算した値をスカラ値とした特徴ベクトルを生成する特徴ベクトル生成ステップと、
を行うことを特徴としている。
【００２２】
また、第７の発明は、第６の発明の画像検索方法を前記コンピュータに実行させるためのプログラムである。
【００２３】
第６及び７の発明によれば、第１の発明と同様の効果が得られる。
【発明の効果】
【００２４】
本発明によれば、ビジュアルキーワードにより画像から生成する特徴ベクトルの精度を高めることができる。
【図面の簡単な説明】
【００２５】
【図１】本発明に係る画像検索装置の機能構成を示すブロック図。
【図２】特徴ベクトル生成処理の処理フローを示すフローチャート。
【図３】画像データからの部分画像の抽出とクラスタリングの様子を示す図。
【図４】クラスタの特徴量と、部分画像の特徴量とに基づく特徴ベクトル生成を説明するための概念図。
【図５】距離に基づいた重み値を求めるための式を示す第１のグラフ。
【図６】距離に基づいた重み値を求めるための式を示す第２のグラフ。
【図７】距離に基づいた重み値を求めるための式を示す第３のグラフ。
【発明を実施するための最良の形態】
【００２６】
［画像検索装置の構成］
以下、本発明の実施の形態を図面に基づいて説明する。
図１は、本発明を適用した画像検索装置１の機能ブロック図である。画像検索装置１には、図示しないクライアント端末が通信ネットワーク（インターネットや電話回線網等）を介して接続され、互いにデータ通信可能となっている。
【００２７】
画像検索装置１は、通信ネットワークを介して接続されたパーソナルコンピュータや携帯端末等のクライアント端末から送信されるクエリ画像を検索要求として受信する。そして、その検索要求に応じた類似画像検索を行って、類似度順にランキングした検索結果をクライアント端末に返送する。
【００２８】
本実施形態における画像検索装置１は、ビジュアルキーワードの手法を用いて画像をインデックス化する。ビジュアルキーワードによる画像検索とは、画像を複数の画像領域の集合として表現し、各画像を構成する画像領域（以下、適宜「部分画像」という）から得られる特徴量に基づいて画像のインデックス（特徴ベクトル）を生成する技術であり、テキスト中のキーワードから文章の特徴量を求めるテキスト検索技術の応用といえる。
【００２９】
このため、ビジュアルキーワードによる画像検索では、画像中の画像領域をキーワードとして扱うことでテキスト検索技術（転置インデックスやベクトル空間モデル、単語の出現頻度等）における技術を画像領域検索へ適用して、大規模且つ高速性を実現することができる。ビジュアルキーワードによる画像検索についての参考技術文献としては、
・Sivic  and  Zisserman:“Efficient  visual  search  for  objects  in  videos”,  Proceedings  of  the  IEEE,  Vol.96,No.4.,pp.548-566,Apr  2008.
・Yang  and  Hauptmann:“A  text  categorization  approach  to  video  scene  classification  using  keypoint  features”,Carnegie  Mellon  University  Technical  Report,pp.25,Oct  2006.
・Jiang  and  Ngo:“Bag-of-visual-words  expansion  using  visual  relatedness  for  video  indexing”,Proc.31st  ACM  SIGIR  Conf.,pp.769-770,Jul  2008.
・Jiang,  Ngo,  andYang:“Towards  optimal  bag-of-features  for  object  categorization  and  semantic  video  retrieval”,Proc.6th  ACM  CIVR  Conf.,pp.494-501,Jul.2007.
・Yang,  Jiang,  Hauptmann,  and  Ngo:“Evaluating  bag-of-visual-words  representations  in  scene  classification”,Proc.15th  ACM  MM  Conf.,  Workshop  onMMIR,pp.197-206,Sep.  2007.
等が挙げられる。
【００３０】
また、ある一つの画像を複数の部分画像の集合として表現することによって、一般的な類似画像検索とは異なり、画像中の一部分を任意大きさや位置で切り出した部分画像をクエリ画像とした検索が可能となる。このため、ユーザは、所望の検索結果を得るために、画像の一部分を指定するといった操作により、より直接・正確にクエリを表現することができる。
【００３１】
図１に示すように、画像検索装置１は、クエリ画像受付部１０、特徴ベクトル生成部２０、類似度算出部３０、検索結果出力部４０、クラスタリング部５０、クラスタＤＢ５５、インデクシング部６０、インデックスＤＢ６５及び検索対象画像ＤＢ７０を備えて構成される。これらの機能部は、所謂コンピュータにより構成され、演算／制御装置としてのＣＰＵ（Central  Processing  Unit）、記憶媒体としてのＲＡＭ（Random  Access  Memory）及びＲＯＭ（Read  Only  Memory）、通信インターフェイス等が連関することで実現される。
【００３２】
クエリ画像受付部１０は、クライアント端末から送信される類似画像検索の検索キーとなるクエリ画像を受信して受け付ける。このクエリ画像は、検索対象画像ＤＢ７０に格納されている画像や、その画像データの一部分の領域を指定する操作により切り出された画像、新たに受信した画像がある。また、クエリ画像としては、１つの画像であってもよいし、複数の画像の組み合わせでもよい。
【００３３】
特徴ベクトル生成部２０は、クエリ画像から部分画像を抽出し、その部分画像の特徴量に基づいて特徴ベクトルを生成する特徴ベクトル生成処理（図２参照）を行って、クエリ画像から特徴ベクトルを生成する。特徴ベクトル生成処理については後述する。
【００３４】
類似度算出部３０は、インデックスＤＢ６５に記憶された検索対象の画像毎の特徴ベクトルと、クエリ画像の特徴ベクトルとの類似度を算出する。この類似度の算出には、コサイン距離やBhattacharyya距離等の公知技術が用いられる。
【００３５】
検索結果出力部４０は、類似度算出部３０により算出された類似度に基づいて、検索対象の画像をランク付けしたデータを生成する。この検索結果出力部４０が出力するデータは、例えば、検索対象画像の画像ＩＤを類似度に基づいてソートしたデータである。画像ＩＤには、検索対象画像ＤＢ７０にアクセスするためのアドレス（ＵＲＬ）を付加してもよい。
【００３６】
検索対象画像ＤＢ７０は、クエリ画像に対して類似する画像を検索する対象となる画像データ（以下適宜「検索対象画像」という）を記憶するデータベースである。例えば、画像を識別するための識別情報である画像ＩＤと、画像データとを対応付けて記憶する。
【００３７】
クラスタリング部５０は、検索対象画像ＤＢ７０に記憶された画像データから複数の部分画像を抽出し、その部分画像の有する特徴量に基づいて複数の部分画像をクラスタリングする。尚、クラスタリングの標準的な手法としては、k-means,  Hierarchical  Agglomerative  Clustering(HAC)などが用いられる。尚、クラスタリング部５０がクラスタリングの対象とする画像は、検索対象画像ＤＢ７０に記憶された画像から抽出した部分画像であってもよいし、学習用に予め用意した画像から抽出した部分画像であってもよい。
【００３８】
クラスタＤＢ５５は、クラスタリング部５０によるクラスタリングにより形成されたクラスタを識別するクラスタＩＤと、そのクラスタの特徴量空間での中心点の座標である中心座標とを対応付けて記憶するデータベースである。この中心座標は、各クラスタに属する画像の特徴量の平均値を示す値であり、特徴量空間上での多次元の座標により示される。
【００３９】
インデクシング部６０は、検索対象画像ＤＢ７０に記憶された画像データについての特徴ベクトルを生成して、この生成した特徴ベクトルを画像データのインデックスとしてインデックスＤＢ６５に対応付けて記憶する。尚、このインデクシング部６０による特徴ベクトルの生成も図２に示す特徴ベクトル生成処理に基づいて行われる。
【００４０】
インデックスＤＢ６５は、検索対象画像ＤＢ７０に記憶された画像データの画像ＩＤと、この画像データから生成した特徴ベクトルとを対応付けて記憶するデータベースである。
【００４１】
［特徴ベクトル生成処理］
次に、特徴ベクトル生成部２０及びインデクシング部６０が行う特徴ベクトル生成処理について、図２の特徴ベクトル生成処理の処理フローを示すフローチャートと、図３〜図５の概要図とを参照しながら説明する。尚、特徴ベクトル生成部２０はクエリ画像に対して、インデクシング部６０は検索対象画像ＤＢ７０に記憶された画像データに対してそれぞれ特徴ベクトル生成処理を行う。
【００４２】
先ず、特徴ベクトル生成部２０及びインデクシング部６０は、クエリ画像又は検索対象画像ＤＢ７０の画像データから、部分画像を抽出する。（ステップＳ１１）。この部分画像の抽出方法としては、画像中の特徴的な領域（特徴領域）を抽出する手法と、画像を所定領域で分割することで抽出する手法とがある。
【００４３】
画像中の特徴的な領域を抽出する手法としては、
・Ｈａｒｒｉｓ−ａｆｆｉｎｅ
・Ｈｅｓｓｉａｎ−ａｆｆｉｎｅ
・Ｍａｘｉｍａｌｌｙ  ｓｔａｂｌｅ  ｅｘｔｒｅｍａｌ  ｒｅｇｉｏｎｓ（ＭＳＥＲ）
・Ｄｉｆｆｅｒｅｎｃｅ  ｏｆ  Ｇａｕｓｓｉａｎｓ（ＤｏＧ）
・Ｌａｐｌａｃｉａｎ  ｏｆ  Ｇａｕｓｓｉａｎ（ＬｏＧ）
・Ｄｅｔｅｒｍｉｎａｎｔ  ｏｆ  Ｈｅｓｓｉａｎ（ＤｏＨ）
等がある。
また、特徴領域を抽出する手法としては、画像中のランダムな大きさ・位置の画像領域を選択する手法も知られている。
【００４４】
また、特徴領域の検出技術については、“Local  Invariant  Feature  Detectors:  A  Survey”（Foundations  and  Trends  in  Computer  Graphics  and  Vision,Vol.3,No.3,pp.177-280,2007.）等において公開されており、適宜公知技術を採用可能である。
【００４５】
また、画像を所定領域で分割して抽出する手法としては、例えば、予め定めたＭ×Ｎブロックに分割したり、分割後のブロックの大きさが予め定めたｍ×ｎ画素となるように分割したりする手法がある。例えば、画像を１０×１０のブロックに分割する場合、画像の大きさが６４０×４８０画素であれば、１ブロックの大きさは６４×４８画素となる。
【００４６】
図３では、画像を所定領域に分割した例を示しており、Ｎｏ．０００１の画像については７×６ブロックに分割されている。また、Ｎｏ．０００２の画像については５×７ブロック、Ｎｏ．０００３の画像については６×６ブロックに分割されている。尚、図示の例では、説明の簡略化のために数ブロックに分割しているが、数万のブロックに分割される。
【００４７】
次に、特徴ベクトル生成部２０及びインデクシング部６０は、抽出した部分画像が有する特徴量を算出する（ステップＳ１２）。尚、特徴領域を抽出している場合には、スケール変化や回転、角度変化等のアフィン変換に耐性を持つ局所特徴量を抽出する。局所特徴量の一例としては、例えば次のものが挙げられる。
【００４８】
・ＳＩＦＴ
・ｇｒａｄｉｅｎｔ  ｌｏｃａｔｉｏｎ  ａｎｄ  ｏｒｉｅｎｔａｔｉｏｎ  ｈｉｓｔｏｇｒａｍ
・ｓｈａｐｅ  ｃｏｎｔｅｘｔ
・ＰＣＡ−ＳＩＦＴ
・ｓｐｉｎ  ｉｍａｇｅｓ
・ｓｔｅｅｒａｂｌｅ  ｆｉｌｔｅｒｓ
・ｄｉｆｆｅｒｅｎｔｉａｌ  ｉｎｖａｒｉａｎｔｓ
・ｃｏｍｐｌｅｘ  ｆｉｌｔｅｒｓ
・ｍｏｍｅｎｔ  ｉｎｖａｒｉａｎｔｓ
【００４９】
局所特徴量の抽出については、“A  performance  evaluation  of  local  descriptors”（IEEE  Trans.  Pattern  Analysis  and  Machine  Intelligence,  Vol.27,  No.10,pp.1615-1630,2005.）等において公開されており、適宜公知技術を採用可能である。
【００５０】
この特徴領域から抽出した部分画像の特徴量に基づいて生成した特徴ベクトルは、オブジェクト（物体）の存在する可能性の高い特徴領域から生成されるため、画像中のオブジェクトの特徴を示す指標として有効である。
【００５１】
また、領域分割により部分画像を抽出している場合には、画像の配色やテクスチャ、形状等の各画像の特徴を数値化して表現した画像特徴量を用いる。
【００５２】
画像特徴量についての参考文献は、
“Content-based  image  retrieval  at  the  end  of  the  early  years”,IEEE  Transactions  on  Pattern  Analysis  and  Machine  Intelligence,  Vol.22,No.12,pp.1349-1380.Dec  2000.
が知られている。
【００５３】
この領域分割により抽出した部分画像の特徴量から生成した特徴ベクトルは、画像を構成する各部分から生成されるため、画像の全体的な構成を示す指標として有効である。
【００５４】
そして、特徴ベクトル生成部２０及びインデクシング部６０は、画像データから抽出した複数の部分画像の集合を、その部分画像が有する特徴量に基づいてクラスタＤＢ５５のクラスタに分類する（ステップＳ１３）。クラスタへの分類は、クラスタリング部５０により画像データが予めクラスタリングされることで形成されたクラスタの中心点と、部分画像の特徴量との特徴量空間における距離に基づいて、該部分画像が属するクラスタを決定する。
【００５５】
以下、各クラスタを識別するＩＤを‘＃’を付して説明する。図３では、抽出した部分画像Ｔ１、Ｔ３〜Ｔ６がクラスタ＃１、部分画像Ｔ２がクラスタ＃２、部分画像Ｔ１２〜Ｔ１４がクラスタ＃３、部分画像Ｔ１１及びＴ２１がクラスタ＃４、部分画像Ｔ２４〜Ｔ２６がクラスタ＃５、部分画像Ｔ２２及びＴ２３がクラスタ＃６に分類されている。
【００５６】
特徴ベクトル生成部２０及びインデクシング部６０は、各部分画像をクラスタに分類すると、そのクラスタリングした部分画像の中から１つの部分画像を選択する（ステップＳ１４）。そして、その選択した部分画像が属するクラスタ（所属クラスタ）のクラスタＤＢ５５における中心点と、部分画像の特徴量との特徴量空間上での距離を算出する（ステップＳ１５）。
【００５７】
図４においては、クエリ画像Ｇ１から抽出された部分画像Ｇ１０がクラスタ＃２に分類され、その部分画像Ｇ１０の特徴量と、クラスタ＃２の中心点Ｃとの距離ｄ１が算出される例が図示されている。
【００５８】
そして、部分画像毎の距離に基づいて重み値を求め、その重み値を該部分画像が属するクラスタ毎に加算する（ステップＳ１６）。
【００５９】
この重み値の設定は、例えば、図５に示すグラフに基づいて行われる。同図の重み値は、次の式により求められる。
重み値＝１−（１／Ｄ）×ｄ
尚、Ｄは、クラスタの半径であり、例えば、クラスタに属する部分画像のうちの中心点Ｃからの距離が最遠の部分画像と中心点Ｃとの距離である。
【００６０】
特徴ベクトルは、図４に示すように、クラスタ毎にスカラ値を有し、図示しないメモリに一時的に格納される。上述のように選択した部分画像について重み値を求めると、その重み値を、該部分画像が属するクラスタのスカラ値に加算する。
【００６１】
このように、部分画像が属するクラスタのスカラ値に、距離に基づく重み値が加算されるため、部分画像が出現するクラスタに０〜１の範囲の値が加算される。従って、特徴ベクトルのクラスタ毎のスカラ値は、部分画像の各クラスタに属する（出現する）数そのものではなく、部分画像がクラスタに出現する数と、そのクラスタの中心点からの距離との両方に基づいて算出されることとなる。
【００６２】
特徴ベクトル生成部２０及びインデクシング部６０は、画像データから抽出した部分画像を全て選択されている場合には（ステップＳ１７；Ｎｏ）、所属クラスタ毎の重み値をスカラ値とした特徴ベクトルを生成する（ステップＳ１８）。
【００６３】
また、ステップＳ１７において、画像データから抽出した部分画像のうち、選択していない残りの部分画像がある場合には（ステップＳ１７；Ｙｅｓ）、ステップＳ１４に処理を移行して、ステップＳ１４〜Ｓ１６の処理を繰り返す。
【００６４】
特徴ベクトル生成部２０は、特徴ベクトル生成処理により生成したクエリ画像の特徴ベクトルを類似度算出部３０に出力する。また、インデクシング部６０は、生成した特徴ベクトルをインデックスとして、検索対象画像の画像ＩＤに対応付けてインデックスＤＢ６５に記憶する。
【００６５】
以上のように、本実施形態によれば、クエリ画像や検索対象画像から抽出した複数の部分画像を各クラスタに分類し、その部分画像が属するクラスタの中心点と、部分画像の特徴量との距離に基づいた重み値によって、特徴ベクトルのクラスタ毎のスカラ値を加算して、特徴ベクトルを生成する。
【００６６】
図４に示すような大きく分けて空、山、海という構成の画像（クエリ画像Ｇ１、検索対象画像Ｇ３、Ｇ５）離間の類似度を算出するとする。視覚的に、空と海の部分については、検索対象画像Ｇ５よりも検索対象画像Ｇ３のほうがクエリ画像Ｇ１に類似しているとする。また、山の部分は、検索対象画像Ｇ３と検索対象画像Ｇ５とで同等であるとする。
【００６７】
図４に示すようにクエリ画像Ｇ１と、検索対象画像Ｇ３、Ｇ５との間の類似度を算出する際、同一のクラスタに属する部分画像が画像間にあるとしても、クラスタとの中心点との距離、即ちクラスタとの類似性を加味した特徴ベクトルが生成される。
【００６８】
例えば、クエリ画像Ｇ１の部分画像Ｇ１０が属するクラスタ＃２に、検索対象画像Ｇ３及びＧ５から抽出した部分画像Ｇ３０及びＧ５０も属する場合、クエリ画像Ｇ１、検索対象画像Ｇ３、Ｇ５の特徴ベクトルのクラスタ＃２に対応したスカラ値は、中心点Ｃからの距離に応じてそれぞれ加算される。
【００６９】
各画像の特徴ベクトルのクラスタ＃２に対応したスカラ値には、クエリ画像Ｇ１では距離ｄ１、検索対象画像Ｇ３では距離ｄ３、検索対象画像Ｇ５では距離ｄ５にそれぞれ基づいた重み値が加算される。
【００７０】
この加算する重み値は、部分画像がクラスタに属する際に０〜１の範囲で設定されるため、出現頻度に対して重み付けした値といえ、部分画像が属するクラスタに対する類似性に相当する。例えば、「空」の画像がクラスタリングされているクラスタに属すると判断された部分画像ついて、重み値は、部分画像が「空」にどれだけ類似しているかを示す指標となる。
【００７１】
このように、重み値の加算により生成される特徴ベクトルは、部分画像がどの程度、各クラスタに類似しているかを示すこととなる。これに対して逆の観点からは、クラスタに属しながらも、該クラスタに類似していないものについては重み値が低められるので、この重み値は、どの程度、各クラスタに類似していないかを示す指標であるともいえる。
【００７２】
このような重み値を用いることで、あるクラスタに類似する（距離の近い）部分画像を有する画像同士の類似度を高め、類似しない部分画像を有する画像同士の類似度を低めることができる。したがって、その分類先のクラスタと類似性が低い場合には、重み値を低めることで、クラスタに対する分類の精度を吸収し、特徴ベクトルへの影響を抑えることができる。
【００７３】
従って、部分画像とクラスタとの距離（類似性）が加味した精度の高い特徴ベクトルを生成することができ、ビジュアルキーワードの手法による類似画像検索における類似度の精度を高めることができる。
【００７４】
尚、上述した実施形態により本発明が限定されるものではなく、その要旨を逸脱しない範囲で変更可能である。
【００７５】
［変形例１］
例えば、部分画像と中心点との距離に基づいて図５に示すグラフの式に基づいた重み値を設定することとしたが、この式は適宜変更可能である。即ち、クラスタリング部５０で形成されたクラスタの平均特徴量から該クラスタに属する検索対象画像ＤＢ７０の画像データから抽出した部分画像の特徴量までの距離に基づいて重み値を求めることとしてもよい。
【００７６】
例えば、図６に示すグラフに基づいた式で重み値を設定することとしてもよい。この場合、クラスタリング部５０がクラスタリングを行う際に、各クラスタに分類された部分画像の中で、該クラスタの中心点からの距離が最も遠い部分画像との該距離をＭａｘ、距離が最も近い部分画像との該距離をＭｉｎとして設定して、クラスタ毎にクラスタＤＢ５５に記憶しておく。
【００７７】
そして、特徴ベクトルを生成する対象となるクエリ画像又は検索対象画像について、各画像から抽出した部分画像と、クラスタの中心点との距離がＭａｘ以上である場合には、重み値を０、Ｍｉｎ以下である場合には重み値を１として設定する。
【００７８】
また、部分画像とクラスタの中心点との距離がＭｉｎ以上、Ｍａｘ以上でる場合には、次式に基づいて重み値が設定される。
重み値＝１−（ｄ−Ｍｉｎ）／（Ｍａｘ−Ｍｉｎ）
【００７９】
このように、クラスタリングにより予め分類された各クラスタの中心点からの距離が最も遠い部分画像に基づいて重み値を設定することで、クラスタに属しながらも類似性を有しない部分画像については特徴ベクトルのスカラ値を加算しないため、類似性を有さない部分画像による特徴ベクトルへの影響を抑えることができる。
【００８０】
また、最も近い部分画像との距離に応じて重み値を設定することで、クラスタの中心点、即ち、そのクラスタの平均的な特徴量に近い部分画像については重み値を１として高めることができるので、類似性を有する部分画像によって特徴ベクトルを際立たせることができる。
【００８１】
尚、部分画像とクラスタの中心点との距離がＭｉｎ以上、Ｍａｘ以上である場合の重み値を求める式は、図７のグラフに基づいた次式にしてもよい。
重み値＝１−（ｄ２−Ｍｉｎ）／（Ｍａｘ−Ｍｉｎ）
【００８２】
この式により求めた重み値によれば、クラスタの中心点と、部分画像との距離が近いほど、重み値が高まるため、類似性を有する部分画像によって特徴ベクトルを更に際立たせることができる。
【００８３】
［変形例２］
また、クラスタリング部５０が形成したクラスタのうち、該クラスタの大きさ（例えば、直径）が最小のものを選択して、そのクラスタの大きさによって重み値の値を正規化することとしてもよい。
【００８４】
具体的には、クラスタリング部５０のクラスタリングによりクラスタを形成した際に、そのクラスタの平均特徴量と、該クラスタ内に属する部分画像のうちの該平均特徴量から最遠の部分画像の特徴量との距離を取得する。そして、クラスタリング部５０が形成したクラスタの中でその距離が最小となるもの（ＳｍａｌｌｅｓｔＭａｘＤｉｓｔａｎｃｅ）、即ち、クラスタの大きさが最小となったクラスタの半径によって、重み値を正規化する。
【００８５】
上述した実施形態における重み値の算出式は、
重み値＝１−（１／（ＳｍａｌｌｅｓｔＭａｘＤｉｓｔａｎｃｅ／Ｄ））×ｄ
となる。
【００８６】
また、変形例１における算出式それぞれは、
重み値＝１−（ｄ−Ｍｉｎ）／（（ＳｍａｌｌｅｓｔＭａｘＤｉｓｔａｎｃｅ／Ｍａｘ）−Ｍｉｎ）
重み値＝１−（ｄ２−Ｍｉｎ）／（（ＳｍａｌｌｅｓｔＭａｘＤｉｓｔａｎｃｅ／Ｍａｘ）−Ｍｉｎ）
となる。
【００８７】
これにより、クラスタリング部５０によって形成されたクラスタの間に大きさのばらつきが生じた場合にも、最小のクラスタの大きさに基づいて、そのばらつきを抑えることができる。
【００８８】
［変形例３］
また、テキスト検索における単語の重み付け手法であるＴＦ／ＩＤＦ（term  frequency-inverse  document  frequency）により更に重み付けを行って特徴ベクトルを生成することとしてもよい。
【００８９】
ＴＦ／ＩＤＦに関する参考資料としては、
C.D.Manning,  P.Raghavan  and  H.Schutze:"  Introduction  to  Information  Retrieval",Cambridge  University  Press.2008.
が知られている。
【００９０】
ＴＦ／ＩＤＦは、文章中の特徴的な単語を抽出するためのアルゴリズムであり、単語の出現頻度であるＴＦと、逆出現頻度であるＩＤＦとの二つの指標により算出される。具体的には、次式により求められる。
ＴＦ／ＩＤＦ＝ＴＦ（ｉ,ｊ）／Ｔ（ｉ）＊ＩＤＦ（ｊ）
ＩＤＦ（ｉ）＝ｌｏｇ（Ｎ／ＤＦ（ｉ））
【００９１】
ここで、
ＴＦ（ｉ，ｊ）は、キーワード抽出対象のドキュメントｉ中でのキーワードｊの出現数
Ｔ（ｉ）は、ドキュメントｉ中の全ての単語の数
Ｎは、全てのドキュメント数
ＤＦ（ｊ）は、キーワードｊが含まれるドキュメントの数
である。
【００９２】
これを、ドキュメントを画像、単語を同一のクラスタに属する部分画像（ビジュアルキーワード）として捉え、各画像のクラスタ毎のＴＦ／ＩＤＦ値を求めて、このＴＦ／ＩＤＦ値をクラスタ毎に加算することで、特徴ベクトルを生成する。
【００９３】
このとき、画像ＩＤをｉ、各クラスタｋとしてビジュアルキーワードに適用した重み値のＴＦ／ＩＤＦ（ｉ,ｋ）は以下の式により算出する。
【００９４】
ＴＦ／ＩＤＦ（ｉ,ｋ）＝ＴＦ（ｉ,ｋ）／Ｔ（ｉ）＊ＩＤＦ（ｋ）
ＩＤＦ（ｋ）      ＝ｌｏｇ（Ｎ／ＤＦ（ｋ））
【００９５】
尚、ＴＦ（ｉ,ｋ）は、画像ｉから抽出した部分画像がクラスタｋで出現する数に重み付けを行ったものであり、各クラスタｋ内に属する（出現する）部分画像と、クラスタｋの中心点との距離に基づく上述した重み値（０〜１）となる。
【００９６】
また、Ｔ（ｉ）は、画像ｉから抽出した部分画像の総数に、クラスタとの距離に基づく重み付けをした値であり、画像ｉから抽出した各部分画像が属するクラスタとの距離に基づいた重み値を合計したものである。
【００９７】
また、ＤＦ（ｋ）は、クラスタリングにより各クラスタｋに分類した部分画像が、各クラスタｋに出現する数に、クラスタとの距離に基づく重み付けを行った値である。また、Ｎは、検索対象画像ＤＢ７０の画像総数である。
【００９８】
このように、ＴＦ／ＩＤＦにおけるドキュメントを画像とみなし、ドキュメント内の単語を同一のクラスタに属する部分画像（ビジュアルキーワード）とみなして重み付けを行うことで、各画像に出現する部分画像の重要度を下げ、特定の画像に際立って出現する特徴的な部分画像についての重要度を上げるように特徴ベクトルのスカラ値に重み付けを行うことができる。
【００９９】
［変形例４］
また、上述では、一つのクエリ画像が受け付けられた場合を例示して説明したが、クエリ画像が複数受け付けることとしてもよい。この場合は、特徴ベクトルの生成を各クエリ画像に対して行う。そして、特徴ベクトル生成部が各クエリ画像から生成した複数の特徴ベクトルを加算することで一つの特徴ベクトルに合成して、インデックスＤＢ６５の特徴ベクトルと比較し類似度を算出する。
【０１００】
このように、複数の特徴ベクトルを加算することで一つの特徴ベクトルに合成できるのは、画像を複数の部分画像の集合として表現するというビジュアルキーワード固有の技術による。即ち、クエリ画像が複数である場合には、その複数のクエリ画像から検出される部分画像の集合を、１つのクエリ（検索要求）に対する部分画像の集合と見なすことができるため、特徴ベクトルの合成が可能となる。
【０１０１】
これにより、ユーザが検索時に入力するクエリ画像が複数であった場合にも、複数のクエリ画像から統合した各クエリ画像の特徴を重要視した特徴ベクトルを生成することができ、ユーザの検索意図を考慮した類似画像検索のランキングを生成することができる。
【０１０２】
［変形例５］
また、上述では、重み値を求める際の「クラスタの有する特徴量」として「クラスタに属する画像の特徴量の平均値」を用いることとして説明したが、これに限られない。
【０１０３】
例えば、各クラスタにクラスタリングされた部分画像それぞれの特徴量を用いることとしてもよい。この場合、クラスタに属する部分画像の特徴量それぞれと、特徴ベクトル生成対象の画像から抽出した部分画像の特徴量との距離を算出して、その距離の平均値に基づいて重み値を設定する。クラスタに属する画像の特徴量の平均値を用いた場合、クラスタ内での特徴量のばらつきが直接その平均値の値を左右するが、クラスタリングされた部分画像それぞれの特徴量との距離の平均値を用いることで、特徴ベクトル生成におけるクラスタ内での画像のばらつきの影響を抑制できる。
【０１０４】
また、各クラスタにクラスタリングされた部分画像それぞれの特徴量を用いる場合に、各クラスタに属する部分画像の特徴量それぞれと、特徴ベクトル生成対象の画像から抽出した部分画像の特徴量との距離が最も短い部分画像をクラスタ内から選択し、その部分画像との距離に基づいて重み値を設定する。この場合、クラスタ内で最も類似する部分画像との距離を用いて、どの程度クラスタに類似しているかという指標を特徴ベクトルに加えることができる。
【０１０５】
尚、同様に、各クラスタに属する部分画像の特徴量それぞれと、特徴ベクトル生成対象の画像から抽出した部分画像の特徴量との距離が最も遠い部分画像をクラスタ内から選択し、その部分画像との距離に基づいて重み値を設定することとしてもよい。
【０１０６】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０１０７】
１  画像検索装置
１０  クエリ画像受付部
２０  特徴ベクトル生成部
３０  類似度算出部
４０  検索結果出力部
５０  クラスタリング部
６０  インデクシング部
Ｃ  中心点
ｄ１  距離
ｄ３  距離
ｄ５  距離
５５  クラスタＤＢ
６５  インデックスＤＢ
ＤＢ７０  検索対象画像
Ｇ１  クエリ画像
Ｇ１０  部分画像
Ｇ３  検索対象画像
Ｇ３０  部分画像
Ｇ５  検索対象画像
Ｇ５０  部分画像
【図１】
2011128773.tif 000003
【図２】
2011128773.tif 000004
【図３】
2011128773.tif 000005
【図４】
2011128773.tif 000006
【図５】
2011128773.tif 000007
【図６】
2011128773.tif 000008
【図７】
2011128773.tif 000009