(57)【特許請求の範囲】
【請求項１】
複数の検索対象画像の中からクエリ画像に類似する画像を検索して出力する画像検索装置において、
クエリ画像及び検索対象画像内から抽出した複数の部分画像の各々を複数のクラスタの何れかに分類することで、各画像から抽出した部分画像の各クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成手段と、
前記クエリ画像の特徴ベクトルと、前記複数の検索対象画像の特徴ベクトルとの類似度を算出し、該類似度に基づいて該検索対象画像をランキングするランキング手段と、
前記クエリ画像の部分画像を分類したクラスタを基準クラスタとして、該基準クラスタ全ての数に対して前記検索対象画像の部分画像を共通に分類した前記基準クラスタの数の割合を算出する共通分類度算出手段と、
前記ランキングされた検索対象画像の上位から、前記割合が所定値以上の検索対象画像を出力対象として選出する選出手段と、
を備えることを特徴とする画像検索装置。
【請求項２】
請求項１に記載の画像検索装置と、
前記検索対象画像の中から一ずつ前記クエリ画像を選択して前記特徴ベクトル生成手段に入力することで、前記選出手段により選出された検索対象画像を得て、該検索対象画像と該クエリ画像とを纏めた一集合を作成するクラスタリング部と、
を備える、クラスタリング装置。
【請求項３】
コンピュータが、複数の検索対象画像の中からクエリ画像に類似する画像を検索して出力する画像検索方法において、
クエリ画像及び検索対象画像内から抽出した複数の部分画像の各々を複数のクラスタの何れかに分類することで、各画像から抽出した部分画像の各クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成工程と、
前記クエリ画像の特徴ベクトルと、前記複数の検索対象画像の特徴ベクトルとの類似度を算出し、該類似度に基づいて該検索対象画像をランキングするランキング工程と、
前記クエリ画像の部分画像を分類したクラスタを基準クラスタとして、該基準クラスタ全ての数に対して前記検索対象画像の部分画像を共通に分類した前記基準クラスタの数の割合を算出する共通分類度算出工程と、
前記ランキングされた検索対象画像の上位から、前記割合が所定値以上の検索対象画像を出力対象として選出する選出工程と、
を前記コンピュータが行うことを特徴とする画像検索方法。
【請求項４】
請求項３に記載の画像検索方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像検索装置、画像検索方法及びプログラムに関する。
【背景技術】
【０００２】
画像を検索キーとして入力し、画像の特徴量（配色、テクスチャ、形状等の画像の特徴を数値化して表現したもの）を比較することにより、検索キーである画像（以下「クエリ画像」という）に類似する画像を検索する技術が知られている。ユーザがクエリ画像を入力すると、クエリ画像から特徴量を抽出して、検索対象の画像の特徴量との類似度を算出することで、類似画像を検索する（例えば、特許文献１）。
【０００３】
また、画像内の部分的な領域に注目した類似画像の検索技術として、ビジュアルキーワードという手法が知られている。これは、１枚の画像が複数の部分画像により構成されていると捉えることにより考案された手法であり、次のような処理により特徴ベクトルが生成される。
【０００４】
即ち、画像から複数の部分画像を抽出して、予め画像がクラスタリングされて形成された基準となるクラスタ（以下適宜「基準クラスタ」という）に対して、その部分画像を特徴量に基づいてマッピング（分類）し、各部分画像が属する基準クラスタの数に基づいて特徴ベクトルが生成される。このように、ビジュアルキーワードを用いることで、画像全体から抽出される特徴量ではなく、画像を細かな領域として捉えた特徴量により、精度のよい画像検索が可能になる。
【０００５】
上記のように算出した類似度に基づいてクエリ画像に類似する画像を検索結果として出力する。類似度に基づいてランキング（順位付け）して表示する際には、該類似度が所定の閾値以上となる画像を選出して検索結果として出力するのが一般的である（例えば、特許文献２）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００１−５２１７５号公報
【特許文献２】特開２００５−１４８８０１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、画像検索を行う場合に、ユーザが入力するクエリ画像には、ユーザの探索したいオブジェクト（対象物）が含まれており、そのオブジェクトと類似する画像が検索結果として出力されるのが望ましい。
【０００８】
しかし、画像から抽出される特徴量や特徴ベクトルは、画像の配色やテクスチャ、形状等を機械的に数値化したものであるため、クエリ画像に含まれるオブジェクトを考慮したものではない。このため、類似度が予め設定した閾値以上であっても、クエリ画像と類似するオブジェクトを含まない画像を選出してしまうことがあった。また、閾値の値を高めて設定すると、クエリ画像と類似するオブジェクトを含む画像を検索結果として選出できなくなった。このように、閾値を予め定めると、選出される検索結果の精度が落ちてしまう。
【０００９】
本発明は、上述の課題に鑑みてなされたものであって、その目的とするところは、類似画像検索の結果として出力する画像の選出精度を向上させることである。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、第１の発明は、複数の検索対象画像の中からクエリ画像に類似する画像を検索して出力する画像検索装置において、クエリ画像及び検索対象画像内から抽出した複数の部分画像の各々を複数のクラスタの何れかに分類することで、各画像から抽出した部分画像の各クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成手段と、前記クエリ画像の特徴ベクトルと、前記複数の検索対象画像の特徴ベクトルとの類似度を算出し、該類似度に基づいて該検索対象画像をランキングするランキング手段と、前記クエリ画像の部分画像を分類したクラスタを基準クラスタとして、該基準クラスタ全ての数に対して前記検索対象画像の部分画像を共通に分類した前記基準クラスタの数の割合を算出する共通分類度算出手段と、前記ランキングされた検索対象画像の上位から、前記割合が所定値以上の検索対象画像を出力対象として選出する選出手段と、を備えることを特徴としている。
【００１１】
第１の発明によれば、クエリ画像の部分画像を分類した基準クラスタに対して、検索対象画像の部分画像を共通に分類した基準クラスタの数の割合を算出し、ランキングされた検索対象画像の上位から、割合が所定値以上の検索対象画像を出力対象として選出する。即ち、出力対象の選定条件は、クエリ画像を基準として算出される共通の基準クラスタの数の割合となり、クエリ画像に基づいてその選定条件は動的に変化する。このため、クエリ画像に基づいて、類似度が高く、更にクエリ画像と共通の基準クラスタを有する検索対象画像が選出されることとなる。従って、類似画像検索の結果として出力する画像の選出精度を向上させることができる。
【００１２】
また、第２の発明のクラスタリング装置は、請求項１に記載の画像検索装置と、前記検索対象画像の中から一ずつ前記クエリ画像を選択して前記特徴ベクトル生成手段に入力することで、前記選出手段により選出された検索対象画像を得て、該検索対象画像と該クエリ画像とを纏めた一集合を作成するクラスタリング部と、を備えることを特徴としている。
【００１３】
第２の発明によれば、検索対象画像から選択したクエリ画像に対して選出された検索結果を纏めることにより一集合を作成する。このため、クエリ画像と類似するオブジェクトを含む画像によって画像群が作成されることとなり、精度の高い画像のクラスタリングを実現することができる。
【発明の効果】
【００１４】
本発明によれば、類似画像検索の結果として出力する画像の選出精度を向上させることである。
【図面の簡単な説明】
【００１５】
【図１】画像検索装置の機能構成を示すブロック図。
【図２】特徴ベクトル生成処理のフローチャート。
【図３】検索処理のフローチャート。
【図４】共通分類度の算出の一例を説明するための図。
【図５】出力対象の画像の選出の一例を説明するための図。
【図６】実験結果を示す図。
【図７】クラスタリング処理のフローチャート。
【発明を実施するための最良の形態】
【００１６】
［画像検索装置の構成］
以下、本発明の画像検索装置を、図１に示す画像検索装置１に適用した場合の実施の形態を図面に基づいて説明する。
【００１７】
図１は、画像検索装置１の機能ブロック図である。画像検索装置１は、通信ネットワークを介して接続されたインターネットに接続され、該インターネットを介してウェブ上から画像データを収集可能となっている。この収集したデータをデータベース（ＤＢ）に蓄積して、検索対象の画像を作成する。
【００１８】
画像検索装置１は、通信ネットワークを介して接続されたパーソナルコンピュータや携帯端末等のクライアント端末から送信されるクエリ画像を検索要求として受信する。そして、その検索要求に応じた類似画像検索を行って、類似度順にランキングした検索結果をクライアント端末に出力する。
【００１９】
また、画像検索装置１の機能をモジュールとして用いてもよく、例えば、他のモジュールからクエリ画像の入力を受け付け、検索結果の画像を該モジュールに返すこととしてもよい。
【００２０】
本実施形態における画像検索装置１は、ビジュアルキーワードの手法を用いて画像の特徴ベクトルを生成してインデックス化する。ビジュアルキーワードによる画像検索とは、１枚の画像を複数の画像領域の集合として表現し、各画像を構成する画像領域（以下、適宜「部分画像」という）から得られる特徴量に基づいて画像のインデックス（特徴ベクトル）を生成する技術であり、テキスト中のキーワードから文章の特徴量を求めるテキスト検索技術の応用といえる。
【００２１】
このため、ビジュアルキーワードによる画像検索では、画像中の画像領域をキーワードとして扱うことでテキスト検索技術（転置インデックスやベクトル空間モデル、単語の出現頻度等）における技術を画像領域検索へ適用して、大規模且つ高速性を実現することができる。
【００２２】
ビジュアルキーワードによる画像検索についての参考技術文献としては、
・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.）等において公開されており、適宜公知技術を採用可能である。
【００４８】
この特徴領域から抽出した特徴量に基づいて生成した特徴ベクトルは、オブジェクト（物体）の存在する可能性の高い特徴領域から生成されるため、画像中のオブジェクトの特徴を示す指標として有効である。
【００４９】
また、領域分割により部分画像を抽出している場合には、画像の配色やテクスチャ、形状等の各画像の特徴を数値化して表現した画像特徴量を用いる。この領域分割により検出した領域画像の特徴量から生成した特徴ベクトルは、画像を構成する各部分から生成されるため、画像の全体的な構成を示す指標として有効である。
【００５０】
次に、マッピング部２４は、画像から抽出した複数の部分画像の中から１つを選択し（ステップＳ１３）、その部分画像と、各ビジュアルキーワード（ビジュアルキーワード生成部６０により予め形成されたクラスタ）との間の距離を算出する（ステップＳ１４）。この距離は、特徴量空間上における部分画像の中心座標と、ビジュアルキーワードの中心座標との間の距離によって求められる。クラスタの中心座標に用いる値としては、クラスタに属するデータ（特徴量）の平均値としてのcentroidの他に、中心に最も近いデータを採用するmedoidや、データを昇順に並べたときに中央に位置するデータを採用するmedian等を適用することができる。
【００５１】
そして、算出した距離が最も近いビジュアルキーワードに、選択した部分画像をマッピング（分類）する（ステップＳ１５）。この際、マッピング部２４は、インデックスＤＢ７５の特徴ベクトルの各ビジュアルキーワードのスカラ値をその部分画像の数を加算する。また、領域管理ＤＢ８０の部分画像の領域ＩＤに、該部分画像をマッピングしたビジュアルキーワードのＶＫＩＤの割り当てを行い、各々を対応付けて記憶する。
【００５２】
例えば、図４において、部分画像Ｇ１１と、ビジュアルキーワードＶＫ１〜ＶＫＮとの間の距離を算出した結果、ビジュアルキーワードＶＫ１が最も近いと判定されたとする。この場合は、部分画像Ｇ１１がビジュアルキーワードＶＫ１にマッピングされ、特徴ベクトルＶのＶＫ１のスカラ値に１加算されることとなる。
【００５３】
次に、マッピング部２４は、ステップＳ１３において全ての部分画像を選択したか否かを判定し（ステップＳ１６）、未選択の部分画像がある場合には（ステップＳ１６；Ｎｏ）、ステップＳ１３に処理を移行して、ステップＳ１５までの処理を繰り返す。
【００５４】
また、全ての部分画像を選択したと判定した場合には（ステップＳ１６；Ｙｅｓ）、マッピングしたビジュアルキーワードに基づいて特徴ベクトルを生成する（ステップＳ１７）。即ち、マッピングした結果のビジュアルキーワード毎での部分画像の出現頻度により多次元で表される特徴ベクトルを生成する。これにより、図４のようにクエリ画像Ｇ１についての特徴ベクトルＶが生成される。
【００５５】
特徴ベクトル生成部２０は、上記の処理により生成したクエリ画像の特徴ベクトルをランキング部３０及び共通分類度算出部４０に出力する。また、インデクシング部７０が特徴ベクトル生成処理により、検索対象画像の各々の特徴ベクトルを生成すると、検索対象画像の画像ＩＤに対応付けてインデックスＤＢ７５に対応付けて記憶する。
【００５６】
以上のように、特徴ベクトル生成処理により、画像内の局所的な特徴量のビジュアルキーワードへの分布によって表わされる特徴ベクトルを生成できる。
【００５７】
〔検索処理〕
次ぎに、ランキング部３０、共通分類度算出部４０及び検索結果選出部５０より行う検索処理について、図３のフローチャートと、図４及び５の概念図とを参照しながら説明する。
【００５８】
先ず、ランキング部３０は、特徴ベクトル生成部２０から出力されるクエリ画像の特徴ベクトルを得ると、この特徴ベクトルと、インデックスＤＢ７５に格納された複数の検索対象画像の特徴ベクトルとの間の類似度を算出する（ステップＳ３１）。
【００５９】
そして、その算出した類似度に基づいて検索対象画像をランキング（順位付け）して、類似度の降順に並び替える（ステップＳ３２）。これにより、図５に示すように、クエリ画像Ｇ１に対して類似する検索対象画像が類似度順に得られる。
【００６０】
また、共通分類度算出部４０は、クエリ画像が属するビジュアルキーワード（ＶＫ）を基準クラスタとし、該基準クラスタに対して検索対象画像の部分画像が共通して分類された前記基準クラスタの数の割合を共通分類度として算出する（ステップＳ３３）。
【００６１】
この共通分類度は、クエリ画像の部分画像をマッピングしたビジュアルキーワードのうち、検索対象画像の部分画像をマッピングした共通のビジュアルキーワードの数を、クエリ画像の部分画像をマッピングしたビジュアルキーワードの数で除した値である。
【００６２】
例えば、図４においては、クエリ画像Ｇ１の部分画像がマッピングされたビジュアルキーワードがＶＫ１、ＶＫ２、ＶＫ３の３つであり、このビジュアルキーワードの中で検索対象画像の部分画像がマッピングされたビジュアルキーワードがＶＫ１とＶＫ３の２つであるので、共通分類度は２／３として算出される。
【００６３】
検索結果選出部５０は、ランキング部３０がランキングした検索対象画像の上位から、共通分類度が所定の閾値以上のものを選出する（ステップＳ３４）。例えば、閾値を１０％と設定したとすると、検索対象画像Ｇ５１〜Ｇ５６が選出されることとなる。これらの検索対象画像は、クエリ画像を基準として共通のビジュアルキーワードに属する部分画像を含む度合いの高いものである。
【００６４】
検索結果選出部５０は、共通分類度に基づいて選出した類似度の高い順の検索対象画像を検索結果とし、クエリ画像を受け付けたクライアント端末やモジュールに対して出力する（ステップＳ３５）。
【００６５】
以上のように、クエリ画像に対する検索結果を出力する際に、クエリ画像と検索対象画像の特徴ベクトル間の類似度により、局所的な特徴量に基づいた類似画像を検索し、更に、クエリ画像を基準とした相対的な値である共通分類度に基づいて共通領域を有する検索対象画像を選出する。
【００６６】
共通分類度に基づく検索対象画像の選出を所定の閾値に基づいて行うこととなるが、この閾値は、クエリ画像を基準とした相対的な比率である。図６は、共通分類度の閾値を１０％と設定して、１０，２００枚の検索対象画像に対してクエリ画像を変えて実験を行った結果の例である。図６に示すように、共通分類度の閾値を１０％と設定しても、実験の結果選出される検索対象画像の類似度の最低値は、基準となるクエリ画像によって変動することとなる。
【００６７】
このため、従来の類似度に対して固定的（絶対的）な閾値を設定するのとは異なり、実際に選出される検索対象画像の類似度はクエリ画像に応じて動的に変化させると共に、クエリ画像と共通なビジュアルキーワードを有する検索対象画像を選出する。従って、クエリ画像のマッピングされたビジュアルキーワードに基づくことで、類似画像検索の結果として出力する画像の選出精度を向上させることができる。
【００６８】
［変形例］
尚、上述した実施形態は本発明を適用した一例であり、その適用可能な範囲は適宜変更可能である。
【００６９】
例えば、共通分類度に対して重み付けを行ってもよい。具体的に、上述の実施形態では、クエリ画像をマッピングしたビジュアルキーワードの数と、検索対象画像を共通にマッピングしたビジュアルキーワードの数とにより共通分類度（例えば、２／３＝（１＋１）／（１＋１＋１））を算出しているが、これらのビジュアルキーワードの数に対して、部分画像とビジュアルキーワードとの間の距離を用いて重み付けを行う。
【００７０】
図４において、クエリ画像の部分画像Ｇ１１〜Ｇ１５をビジュアルキーワードＶＫ１にマッピングしており、そのマッピングした部分画像それぞれとビジュアルキーワードＶＫ１との間の距離の平均値Ｄ１を求める。また、ビジュアルキーワードＶＫ２についても、マッピングした部分画像と、ビジュアルキーワードＶＫ２との間の距離の平均値Ｄ２を求める。
【００７１】
この距離に基づいて、クエリ画像をマッピングしたビジュアルキーワードの数に重み付けを行うことで、この数は、１×Ｄ１＋１×Ｄ２＋１×Ｄ３となる。
【００７２】
また、同様に検索対象画像についても、各ビジュアルキーワードにマッピングした部分画像との距離の平均値を、ビジュアルキーワード毎に算出し、この距離に基づいてクエリ画像と共通してマッピングしたビジュアルキーワードの数に重み付けを行う。
【００７３】
例えば、図４においては、検索対象画像をマッピングしたビジュアルキーワードＶＫ１についての部分画像との間の距離の平均値をＤＡ、ビジュアルキーワードＶＫ３についての部分画像との間の距離の平均値をＤＣと求めたとすると、クエリ画像と共通してマッピングしたビジュアルキーワードの数に重み付けを行うと、１×ＤＡ＋１×ＤＣとなる。
【００７４】
このように重み付けしたビジュアルキーワードの数により共通分類度を求めると、（ＤＡ＋ＤＣ）／（Ｄ１＋Ｄ２＋Ｄ３）となる。このように部分画像とビジュアルキーワードとの間の距離に基づいて重み付けを行うことで、ビジュアルキーワードと部分画像との間の距離のばらつきを考慮できるため、共通分類度の精度を向上させることができる。
【００７５】
また、例えば、上述した実施形態はクエリ画像に対して検索結果を出力する構成のみに特化して説明したが、これを利用して検索対象画像のクラスタリングを行うこととしてもよい。図７は、そのクラスリングの処理を説明するためのフローチャートである。
【００７６】
図示は省略するが、図１の画像検索装置１に対してクラスタリング部を備え、このクラスタリング部が検索対象画像ＤＢ９０の中から一つの検索対象画像を選択する（ステップＳ５１）。そして、その選択した検索対象画像をクエリ画像としてクエリ画像受付部１０に入力することで、上述した検索処理を実行させる（ステップＳ５２）。
【００７７】
クラスタリング部は、検索結果選出部５０から出力される検索結果を受け取り、その検索対象画像と、クエリ画像とにより一集合（クラスタ）を形成してクラスタＤＢ（図示略）に集合毎に記憶する（ステップＳ５３）。
【００７８】
そして、その登録したクエリ画像及び検索対象画像を検索対象画像ＤＢ９０から削除する（ステップＳ５４）。この削除は、例えば、各画像に対して削除フラグを設定する等として、実際にデータを削除しなくてもよい。
【００７９】
クラスタリング部は、検索対象画像ＤＢ９０に未処理の画像があるか否かを判定し（ステップＳ５５）、未処理の画像があると判定した場合には（ステップＳ５５；Ｙｅｓ）、ステップＳ５１に処理を移行して、検索処理を行わせていく。
【００８０】
このように、検索対象画像ＤＢ９０に格納された画像に対して、上述の検索処理を行って一集合となる画像群を逐次作成していくことで、クエリ画像と類似性の高いオブジェクトを含む画像で纏め上げて（クラスタリング）いくことができるようになる。
【００８１】
クラスタリング処理により作成した複数の集合は、その集合同士の距離（例えば、集合内の画像群の特徴ベクトルの平均間の距離）に基づいて更に纏め上げていくこととしてもよい。このクラスタリングの標準的な手法としては、k-means,  Hierarchical  Agglomerative  Clustering(HAC)などが用いられる。即ち、複数のクラスタを纏め上げていくボトムアップによる階層的クラスタリングを行うことにより、類似するオブジェクトを含むクラスタを作成してくことができる。
【００８２】
また、テキスト検索における単語の重み付け手法であるＴＦ／ＩＤＦ（term  frequency-inverse  document  frequency）により、特徴ベクトルに重み付けを行うこととしてもよい。
【００８３】
ＴＦ／ＩＤＦに関する参考資料としては、
C.D.Manning,  P.Raghavan  and  H.Schutze:"  Introduction  to  Information  Retrieval",Cambridge  University  Press.2008.
が知られている。
【００８４】
ＴＦ／ＩＤＦは、文章中の特徴的な単語を抽出するためのアルゴリズムであり、単語の出現頻度であるＴＦと、逆出現頻度であるＩＤＦとの二つの指標により算出される。具体的には、次式により求められる。
ＴＦ／ＩＤＦ＝ＴＦ（ｉ,ｊ）／Ｔ（ｉ）＊ＩＤＦ（ｊ）
ＩＤＦ（ｉ）＝ｌｏｇ（Ｎ／ＤＦ（ｉ））
【００８５】
ここで、
ＴＦ（ｉ，ｊ）は、キーワード抽出対象のドキュメントｉ中でのキーワードｊの出現数
Ｔ（ｉ）は、ドキュメントｉ中の全ての単語の数
Ｎは、全てのドキュメント数
ＤＦ（ｊ）は、キーワードｊが含まれるドキュメントの数
である。
【００８６】
これを、ドキュメントを画像、単語を同一のビジュアルキーワードに属する部分画像として捉え、各画像のビジュアルキーワード毎にＴＦ／ＩＤＦ値を求めて、このＴＦ／ＩＤＦ値を、部分画像をマッピングしたビジュアルキーワードに加算することで、特徴ベクトルを生成する。
【００８７】
このとき、画像ＩＤをｉ、各ビジュアルキーワードｋとして、各ビジュアルキーワードの重み値であるＴＦ／ＩＤＦ（ｉ,ｋ）は以下の式により算出する。
【００８８】
ＴＦ／ＩＤＦ（ｉ,ｋ）＝ＴＦ（ｉ,ｋ）／Ｔ（ｉ）＊ＩＤＦ（ｋ）
ＩＤＦ（ｋ）      ＝ｌｏｇ（Ｎ／ＤＦ（ｋ））
【００８９】
尚、ＴＦ（ｉ,ｋ）は、画像ｉから抽出した部分画像がビジュアルキーワードｋで出現する数に重み付けを行ったものであり、各ビジュアルキーワードｋ内に属する（出現する）部分画像と、ビジュアルキーワードｋの中心点との距離に基づく上述した重み値（０〜１）となる。
【００９０】
また、Ｔ（ｉ）は、画像ｉから抽出した部分画像の総数に、ビジュアルキーワードとの距離に基づく重み付けをした値であり、画像ｉから抽出した各部分画像が属するクラスタとの距離に基づいた重み値を合計したものである。
【００９１】
また、ＤＦ（ｋ）は、各ビジュアルキーワードｋに分類した部分画像が、各ビジュアルキーワードｋに出現する数に、ビジュアルキーワードとの距離に基づく重み付けを行った値である。また、Ｎは、検索対象画像ＤＢ９０の画像総数である。
【００９２】
このように、ＴＦ／ＩＤＦにおけるドキュメントを画像とみなし、ドキュメント内の単語を同一のビジュアルキーワードに属する部分画像とみなして重み付けを行うことで、各画像に出現する部分画像の重要度を下げ、特定の画像に際立って出現する特徴的な部分画像についての重要度を上げるように特徴ベクトルのスカラ値に重み付けを行うことができる。
【００９３】
このＴＦ／ＩＤＦによる重み付けを用いて、クエリ画像内の部分画像が属するビジュアルキーワードと、検索対象画像内の部分画像が属するビジュアルキーワードとの類似スコアを求めてもよい。
【００９４】
また、共通分類度算出部４０は、全ての検索対象画像に対して求めることとして説明したが、例えば、類似度でランキングした検索対象画像のうちの、上位から所定数（例えば、１〜２０位までの２０個）の検索対象画像についてのみ算出することとしてよい。また、所定数の検索対象画像の共通分類度が全て閾値以上である場合には、更に下位の検索対象画像について算出の対象を順に広げて（例えば、２１〜４０位までの２０個）もよい。これにより、算出した共通分類度が閾値以上であるか否かの判定は、その所定数について行えばよいため、処理の高速化を図れる。
【００９５】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００９６】
１  画像検索装置
１０  クエリ画像受付部
２０  特徴ベクトル生成部
２２  部分画像抽出部
２４  マッピング部
３０  ランキング部
４０  共通分類度算出部
５０  検索結果選出部
６０  ビジュアルキーワード生成部
７０  インデクシング部
７２  部分画像抽出部
７４  マッピング部
６５  ビジュアルキーワードＤＢ
７５  インデックスＤＢ
８０  領域管理ＤＢ
９０  検索対象画像ＤＢ
ＶＫ１-ＶＫＮ  ビジュアルキーワード
【図１】
0005121917.tif 000002
【図２】
0005121917.tif 000003
【図３】
0005121917.tif 000004
【図４】
0005121917.tif 000005
【図５】
0005121917.tif 000006
【図６】
0005121917.tif 000007
【図７】
0005121917.tif 000008