JP2012079186A - 画像検索装置、画像検索方法及びプログラム - Google Patents

Abstract

【課題】クエリ画像の有する特徴的な領域に注視した高精度の類似画像検索を実現すること。
【解決手段】クエリ画像内の部分画像と類似する検索対象画像内の部分画像を含む領域を切り出して、この領域とクエリ画像との間で類似度を算出する。また、この類似度には、領域内に含まれる部分画像の数と、該領域内の部分画像のうちのクエリ画像から抽出した部分画像と類似する部分画像の数との比が重み付けされるため、クエリ画像と類似する部分画像に注視した類似度が算出される。
【選択図】図１

Description

本発明は、検索キーとなる画像に類似する画像を検索する画像検索装置等に関する。

画像を検索キーとして入力し、画像の特徴量（配色、テクスチャ、形状等の画像の特徴を数値化して表現したもの）を比較することにより、検索キーである画像（以下「クエリ画像」という）に類似する画像を検索する技術が知られている。ユーザがクエリ画像を入力すると、クエリ画像から特徴量を抽出して、検索対象の画像の特徴量との類似度を算出することで、類似画像を検索する（例えば、特許文献１）。

１枚の画像から抽出される特徴量は、その画像全体の特徴を示すものであるため、全体的に類似している画像を検索する際に有効である。これに対し、画像を構成する部分的な領域による画像（以下「部分画像」という）が類似している画像を検索する場合には、一枚の画像が複数の領域により構成されていると捉えて、その部分画像毎の特徴量によって画像の特徴を表すことで、部分画像を重要視した類似画像検索が可能になる。

但し、画像を部分画像に分割して、その部分画像毎から算出した特徴量を単に比較するとなると、例えば、１００分割した２枚の画像であれば、１００×１００通りのパターンで特徴量を比較し類似度を算出ため、計算量が膨大となる。

そこで、部分画像を用いた計算量を抑えて類似度の算出が可能な部分画像ビジュアルキーワードという手法が考案された。ビジュアルキーワードでは、１枚の画像が複数の部分画像により構成されていると捉え、画像から部分画像を抽出して、予め画像がクラスタリングされて形成されたクラスタに対して、その部分画像を特徴量に基づいて分類し、各部分画像が属するクラスタの数に基づいて特徴ベクトルが生成される。

このように、ビジュアルキーワードを用いることで、画像全体から抽出される特徴量ではなく、画像を細かな領域として捉えた特徴量により、精度のよい画像検索が可能になる。

特開２００１−５２１７５号公報

ところで、ユーザがクエリとして入力する画像には、ユーザの検索意図を含む特徴的な領域が含まれており、類似度の判定は、この「特徴的な領域」に注視して行うことが望ましい。例えば、クエリ画像に人物が含まれている場合には、人物の特徴に注視して類似度の判定を行うことが望ましい。

しかし、従来のビジュアルキーワードや特許文献１の技術では、画像全体を満遍なく捉えて類似度を算出するため、画像の持つ特徴的な領域に特化した検索ができなかった。

本発明は、上述の課題に鑑みて為されたものであり、その目的とするところは、クエリ画像の有する特徴的な領域に注視した高精度の類似画像検索を実現することである。

上記目的を達成するため、第１の発明は、クエリ画像との類似度を算出して該類似度の高い画像を検索対象画像の中から検索する画像検索装置において、前記クエリ画像内から複数の部分画像を抽出する第１抽出手段と、前記検索対象画像内から複数の部分画像を抽出する第２抽出手段と、前記クエリ画像から抽出した部分画像と類似する前記検索対象画像内の部分画像を選択し、この選択した部分画像を含む領域を前記検索対象画像内から切り出す領域切出手段と、前記クエリ画像と、前記切り出された領域内の画像との間の類似度を算出する際に、前記切り出された領域内に含まれる前記部分画像の数と、該領域内の部分画像のうちの前記クエリ画像から抽出した部分画像と類似する部分画像の数との比を重みとして付与する類似度算出手段と、を備えることを特徴としている。

第１の発明によれば、クエリ画像内の部分画像と類似する検索対象画像内の部分画像を含む領域を切り出して、この領域とクエリ画像との間で類似度を算出する。また、この類似度には、領域内に含まれる部分画像の数と、該領域内の部分画像のうちのクエリ画像から抽出した部分画像と類似する部分画像の数との比が重み付けされるため、クエリ画像と類似する部分画像に注視した類似度が算出される。従って、クエリ画像の有する特徴的な領域に注視した高精度の類似画像検索を実現することができる。

また、第２の発明における前記類似度算出手段は、前記クエリ画像内に含まれる前記部分画像の数と、該クエリ画像内の部分画像のうちの前記検索対象画像内の部分画像と類似する部分画像の数との比を更に前記類似度の重みとして付与することを特徴としている。

第２の発明によれば、クエリ画像内に含まれる部分画像の数と、該クエリ画像内の部分画像のうちの検索対象画像内の部分画像と類似する部分画像の数との比が類似度に重み付けされるため、クエリ画像内での検索対象画像と類似する領域に注視した類似度を算出できる。従って、クエリ画像の有する特徴的な領域に注視した高精度の類似画像検索を実現することができる。

また、第３の発明における前記領域切出手段は、前記クエリ画像から抽出した部分画像と類似する前記検索対象画像内の部分画像を選択する際に、該部分画像の集合のうちの外側に位置する部分画像を選択から除外して、その除外後の部分画像を含む領域を切り出すことを特徴としている。

第３の発明によれば、クエリ画像から抽出した部分画像と類似する検索対象画像内の部分画像のうちの、外側から部分画像を除外して領域を切り出すため、類似度を算出する対象の領域を特徴的な領域に絞り込んでいくことができる。従って、クエリ画像の有する特徴的な領域に注視した高精度の類似画像検索を実現することができる。

本発明によれば、クエリ画像の有する特徴的な領域に注視した高精度の類似画像検索を実現することができる。

本発明に係る画像検索装置の機能構成を示すブロック図。 特徴ベクトル生成処理のフローチャート。 画像データからの領域画像の抽出とビジュアルキーワードへのマッピングの様子を示す図。 比較領域の切り出しと、類似度の算出の処理のフローチャート。 比較領域の切り出しと、類似度の算出を説明するための第１の概念図。 比較領域の切り出しと、類似度の算出を説明するための第２の概念図。 比較領域の切り出しと、類似度の算出を説明するための第３の概念図。 比較領域の切り出しの他の例を示す概念図。

［画像検索装置の構成］
以下、本発明の実施の形態を図面に基づいて説明する。
図１は、本発明を適用した画像検索装置１の機能ブロック図である。画像検索装置１は、通信ネットワークを介して接続されたインターネットに接続され、該インターネットを介してウェブ上から画像データを収集可能となっている。この収集したデータをデータベース（ＤＢ）に蓄積して、検索対象の画像を作成する。

画像検索装置１は、通信ネットワークを介して接続されたパーソナルコンピュータや携帯端末等のクライアント端末から送信されるクエリ画像を検索要求として受信する。そして、その検索要求に応じた類似画像検索を行って、類似度順にランキングした検索結果をクライアント端末に返送する。

本実施形態における画像検索装置１は、ビジュアルキーワードの手法を用いて画像をインデックス化する。ビジュアルキーワードによる画像検索とは、画像を複数の画像領域の集合として表現し、各画像を構成する画像領域（以下、適宜「部分画像」という）から得られる特徴量に基づいて画像のインデックス（特徴ベクトル）を生成する技術であり、テキスト中のキーワードから文章の特徴量を求めるテキスト検索技術の応用といえる。

このため、ビジュアルキーワードによる画像検索では、画像中の画像領域をキーワードとして扱うことでテキスト検索技術（転置インデックスやベクトル空間モデル、単語の出現頻度等）における技術を画像領域検索へ適用して、大規模且つ高速性を実現することができる。

ビジュアルキーワードによる画像検索についての参考技術文献としては、
・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.31^st 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.15^th 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.）等において公開されており、適宜公知技術を採用可能である。

この特徴領域から抽出した特徴量に基づいて生成した特徴ベクトルは、オブジェクト（物体）の存在する可能性の高い特徴領域から生成されるため、画像中のオブジェクトの特徴を示す指標として有効である。

また、領域分割により部分画像を抽出している場合には、画像の配色やテクスチャ、形状等の各画像の特徴を数値化して表現した画像特徴量を用いる。この領域分割により検出した領域画像の特徴量から生成した特徴ベクトルは、画像を構成する各部分から生成されるため、画像の全体的な構成を示す指標として有効である。

そして、画像データから検出した複数の部分画像を、その部分画像が有する特徴量に基づいてビジュアルキーワードにマッピング（分類）する（ステップＳ１３）。ビジュアルキーワードへのマッピングは、各ビジュアルキーワード（クラスタ）の中心点と、領域画像の特徴量との特徴量空間における距離に基づいて、距離が最も近いビジュアルキーワードを選定することで行う。

図３の例では、画像ＩＤ‘０００１’の画像から検出した部分画像Ｔ１、Ｔ３〜Ｔ６がビジュアルキーワード＃１、部分画像Ｔ２がビジュアルキーワード＃２にマッピングされている。また、画像ＩＤ‘０００２’の画像から検出した部分画像Ｔ１２〜Ｔ１４がビジュアルキーワード＃３にマッピングされている。また、画像ＩＤ‘０００２’の画像の部分画像Ｔ１１と、画像ＩＤ‘０００３’の画像の部分画像Ｔ２１がビジュアルキーワード＃４にマッピングされている。

特徴ベクトル生成部２０は、各部分画像をビジュアルキーワード（クラスタ）にマッピングすると、各ビジュアルキーワードでの領域画像の出現頻度を計上し、このビジュアルキーワード毎での領域画像の出現頻度により多次元で表される特徴ベクトルを生成する（ステップＳ１４）。インデクシング部７０の特徴ベクトル生成処理においては、生成した特徴ベクトルと、画像ＩＤを対応付けてインデックスＤＢ７５に記憶する。

例えば、図３の‘０００１’の画像であれば、該画像から検出した領域画像の出現頻度は、ビジュアルキーワード＃１では‘５’、ビジュアルキーワード＃２では‘１’、ビジュアルキーワード＃３では‘０’となる。この複数のビジュアルキーワードに対する出現頻度をベクトル要素として生成した特徴ベクトルを画像のインデックスとしてインデックスＤＢ７５に記憶する。

また、インデクシング部７０の特徴ベクトル生成処理においては、検索対象画像から検出した領域画像に領域ＩＤを割り振り、その領域画像をマッピングしたビジュアルキーワードのＶＫＩＤを画像ＩＤと領域ＩＤとに対応付けて領域管理ＤＢ８０に記憶する。この領域管理ＤＢ８０により、各画像内の部分画像がどのビジュアルキーワードにマッピングされているかを確認することができる。

〔比較領域の切り出しと、類似度の算出〕
次に、図４のフローチャートと、図５〜図７の概念図とを用いて、比較領域の切り出しの処理と、類似度の算出処理とを説明する。これらの処理は、比較領域切出部３０が、インデックスＤＢ７５及び領域管理ＤＢ８０から、一つずつ画像ＩＤを選択して行われる。

先ず、比較領域切出部３０は、クエリ画像内から抽出した部分画像と、選択した検索対象画像内から抽出した部分画像とのマッチングを行い、マッチする部分画像、即ち類似度の高い部分画像を選択する（ステップＳ２１）。具体的には、クエリ画像の特徴ベクトルと、検索対象画像の特徴ベクトルとが有するビジュアルキーワード毎の部分画像の出現頻度に基づいてマッチングを行うことができる。

例えば、図５に示すように、クエリ画像Ｇ３の特徴ベクトルのうちビジュアルキーワード＃１に属する部分画像の数は‘４’となり、検索対象画像Ｇ５の特徴ベクトルのビジュアルキーワード＃１に属する部分画像の数は‘５’である。これは、同じビジュアルキーワード、即ち、クラスタにマッピングされている部分画像の数を示していることから、これらの部分画像は類似度が高いと判定することができる。

図５の例では、部分画像Ｇ３０、Ｇ３１と、部分画像Ｇ５１がビジュアルキーワード＃１にマッピングされているから、領域管理ＤＢ８０を参照することで、同一のビジュアルキーワードにマッピングされている部分画像を検索して、マッチしている部分画像が選択される。このように、ビジュアルキーワードから生成した特徴ベクトルを用いることで、部分画像のマッチングが容易にできる。

次に、比較領域切出部３０は、クエリ画像の部分画像とマッチした検索対象画像内の部分画像に基づいて、比較領域の切り出しを行う（ステップＳ２２）。具体的には、マッチした部分画像を含むような領域の切り出しを行う。図５においては、クエリ画像内の部分画像Ｇ３０〜Ｇ３３が検索対象画像内の部分画像Ｇ５１〜Ｇ５３とマッチしたと判定され、これらを含むような矩形が形成されて、これが比較領域Ｒとして切り出される。

次に、類似度算出部４０は、クエリ画像と、比較領域内の画像との類似スコアを算出する（ステップＳ２３）。具体的には、比較領域内の画像についての特徴ベクトルを生成して、この特徴ベクトルと、クエリ画像の特徴ベクトルとの距離を類似スコアとして算出する。

比較領域内の画像の特徴ベクトルについては、ステップＳ２２において切り出した比較領域、即ち、比較対象として位置を考慮して切り出した領域内の部分画像を、領域管理ＤＢ８０の領域ＩＤに基づいて検索して、その領域ＩＤに対応付けられたＶＫＩＤから該部分画像が属するビジュアルキーワードを判定できることから、このビジュアルキーワード毎の部分画像の出現頻度を新たに算出することで特徴ベクトルが生成される。

この処理は、既にビジュアルキーワードにマッピングした部分画像の領域ＩＤ及びＶＫＩＤを集計すればよく、図６のように比較領域Ｒに対する特徴ベクトルＶ７を生成することができる。また、類似スコアの算出については、クエリ画像内の部分画像と、比較領域内の部分画像との間の類似度を各々に算出して、その総計を類似スコアとしてもよい。

次に、類似度算出部４０は、クエリ画像内から抽出した部分画像に対する、比較領域内の部分画像とマッチした部分画像の割合を算出する（ステップＳ２４）。例えば、図６に示すクエリ画像Ｇ３において抽出された部分画像の数は‘８’であり、比較領域内の部分画像とマッチした部分画像の数は‘４’であるから、クエリ画像Ｇ３内における全部分画像数に対するマッチした部分画像の割合は１／２となる。

次に、類似度算出部４０は、比較領域内から抽出した部分画像に対する、クエリ画像内の部分画像とマッチした部分画像の割合を算出する（ステップＳ２５）。例えば、図６に示す比較領域Ｒにおいて抽出された部分画像の数は‘９’であり、クエリ画像Ｇ３内の部分画像とマッチした部分画像の数は‘３’であるから、比較領域Ｒ内における全部分画像数に対するマッチした部分画像の割合は１／３となる。

類似度算出部４０は、ステップＳ２３において算出した類似スコアに、クエリ画像内及び比較領域内でのマッチした部分画像の割合を重み付けとして乗算することで、類似度を算出する（ステップＳ２６）。

上記の類似度の算出を式で表すと次のようになる。
類似度＝クエリ画像内のマッチした部分画像の割合Ａ×比較領域内のマッチした部分画像の割合Ｂ×類似スコアＣ
クエリ画像内のマッチした部分画像の割合Ａ＝クエリ画像内のマッチした部分画像の個数／クエリ画像内の部分画像の個数
比較領域内のマッチした部分画像の割合Ｂ＝比較領域内のマッチした部分画像の個数／比較領域内の部分画像の個数

例えば、図７のクエリ画像Ｇ３と、比較領域Ｒとの間の類似度を算出した場合、比較領域Ｒ内において画像の上部と、下部にマッチする部分画像Ｇ７１〜Ｇ７３がある。従来の類似度の算出では、クエリ画像内の部分画像との類似の度合いによって類似度が算出されるため、図７のような場合には高い類似度が得られる。

しかし、比較領域Ｒ内の中央部にマッチする部分画像がない場合には、類似度が低くなることが望ましい。上述の式に基づいて、比較領域内の部分画像の個数に対するマッチした部分画像の個数の割合を用いることで、マッチしていない領域がある画像については類似度を低めることができる。

このように、クエリ画像内の部分画像とマッチした検索対象画像内の領域内で、更に内領域内でマッチした部分画像に注視した類似度を算出することができる。従って、クエリ画像の有する特徴的な領域に注視した高精度の類似画像検索を実現することができる。

尚、上述した実施形態では、類似スコアに対する重み付けに、クエリ画像内におけるマッチした部分画像の割合と、比較領域内におけるマッチした部分画像の割合との両方を用いることとして説明したが、何れか一方によって重み付けすることとしてもよい。

また、比較領域の切り出しを、マッチした部分画像全てを含む領域として行うこととして説明したが、例えば、マッチした部分画像の集合に対して、上下左右の各方向で最も外側に位置する部分画像を除去して、その除去後の部分画像の集合を含む領域を比較領域として切り出すこととしてもよい。

例えば、図８においては、比較領域Ｒ内の部分画像の集合に対して、この比較領域Ｒの中央から最も遠方にある部分画像はＧ５２となる。従って、この部分画像Ｇ５２を除去した部分画像のうちの、クエリ画像Ｇ３の部分画像とマッチする部分画像であるＧ５１、Ｇ５３を含む比較領域Ｒ１０を切り出す。この除去する部分画像の個数は、定数（例えば、２個）で定めてもよいし、抽出された部分画像の全体数に対する割合（例えば、５％）で定めてもよい。

このように、マッチした部分画像の中で外側の部分画像を除去して比較領域を切り出すことで、類似度を算出する検索画像の領域を更に絞り込むことができるため、高精度な類似画像検索を実現できる。

また、テキスト検索における単語の重み付け手法であるＴＦ／ＩＤＦ（term frequency-inverse document frequency）により、特徴ベクトルに重み付けを行うこととしてもよい。

ＴＦ／ＩＤＦに関する参考資料としては、
C.D.Manning, P.Raghavan and H.Schutze:" Introduction to Information Retrieval",Cambridge University Press.2008.
が知られている。

ＴＦ／ＩＤＦは、文章中の特徴的な単語を抽出するためのアルゴリズムであり、単語の出現頻度であるＴＦと、逆出現頻度であるＩＤＦとの二つの指標により算出される。具体的には、次式により求められる。
ＴＦ／ＩＤＦ＝ＴＦ（ｉ,ｊ）／Ｔ（ｉ）＊ＩＤＦ（ｊ）
ＩＤＦ（ｉ）＝ｌｏｇ（Ｎ／ＤＦ（ｉ））

ここで、
ＴＦ（ｉ，ｊ）は、キーワード抽出対象のドキュメントｉ中でのキーワードｊの出現数
Ｔ（ｉ）は、ドキュメントｉ中の全ての単語の数
Ｎは、全てのドキュメント数
ＤＦ（ｊ）は、キーワードｊが含まれるドキュメントの数
である。

これを、ドキュメントを画像、単語を同一のビジュアルキーワードに属する部分画像として捉え、各画像のビジュアルキーワード毎にＴＦ／ＩＤＦ値を求めて、このＴＦ／ＩＤＦ値をビジュアルキーワード毎に加算することで、特徴ベクトルを生成する。

このとき、画像ＩＤをｉ、各ビジュアルキーワードｋとして、各ビジュアルキーワードの重み値であるＴＦ／ＩＤＦ（ｉ,ｋ）は以下の式により算出する。

ＴＦ／ＩＤＦ（ｉ,ｋ）＝ＴＦ（ｉ,ｋ）／Ｔ（ｉ）＊ＩＤＦ（ｋ）
ＩＤＦ（ｋ） ＝ｌｏｇ（Ｎ／ＤＦ（ｋ））

尚、ＴＦ（ｉ,ｋ）は、画像ｉから抽出した部分画像がビジュアルキーワードｋで出現する数に重み付けを行ったものであり、各ビジュアルキーワードｋ内に属する（出現する）部分画像と、ビジュアルキーワードｋの中心点との距離に基づく上述した重み値（０〜１）となる。

また、Ｔ（ｉ）は、画像ｉから抽出した部分画像の総数に、ビジュアルキーワードとの距離に基づく重み付けをした値であり、画像ｉから抽出した各部分画像が属するクラスタとの距離に基づいた重み値を合計したものである。

また、ＤＦ（ｋ）は、各ビジュアルキーワードｋに分類した部分画像が、各ビジュアルキーワードｋに出現する数に、ビジュアルキーワードとの距離に基づく重み付けを行った値である。また、Ｎは、検索対象画像ＤＢ９０の画像総数である。

このように、ＴＦ／ＩＤＦにおけるドキュメントを画像とみなし、ドキュメント内の単語を同一のビジュアルキーワードに属する部分画像とみなして重み付けを行うことで、各画像に出現する部分画像の重要度を下げ、特定の画像に際立って出現する特徴的な部分画像についての重要度を上げるように特徴ベクトルのスカラ値に重み付けを行うことができる。

このＴＦ／ＩＤＦによる重み付けを用いて、クエリ画像内の部分画像が属するビジュアルキーワードと、検索対象画像内の部分画像が属するビジュアルキーワードとの類似スコアを求めてもよい。

今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。

１ 画像検索装置
３ 比較領域切出部
１０ クエリ画像受付部
２０ 特徴ベクトル生成部
３０ 比較領域切出部
４０ 類似度算出部
５０ 検索結果出力部
６０ ビジュアルキーワード生成部
７０ インデクシング部
７５ インデクシング部
６５ ビジュアルキーワードＤＢ
７５ インデックスＤＢ
８０ 領域管理ＤＢ
９０ 検索対象画像ＤＢ
Ｒ 比較領域

Claims (5)

1. クエリ画像との類似度を算出して該類似度の高い画像を検索対象画像の中から検索する画像検索装置において、
   前記クエリ画像内から複数の部分画像を抽出する第１抽出手段と、
   前記検索対象画像内から複数の部分画像を抽出する第２抽出手段と、
   前記クエリ画像から抽出した部分画像と類似する前記検索対象画像内の部分画像を選択し、この選択した部分画像を含む領域を前記検索対象画像内から切り出す領域切出手段と、
   前記クエリ画像と、前記切り出された領域内の画像との間の類似度を算出する際に、前記切り出された領域内に含まれる前記部分画像の数と、該領域内の部分画像のうちの前記クエリ画像から抽出した部分画像と類似する部分画像の数との比を重みとして付与する類似度算出手段と、
   を備えることを特徴とする画像検索装置。
2. 前記類似度算出手段は、
   前記クエリ画像内に含まれる前記部分画像の数と、該クエリ画像内の部分画像のうちの前記検索対象画像内の部分画像と類似する部分画像の数との比を更に前記類似度の重みとして付与することを特徴とする請求項１に記載の画像検索装置。
3. 前記領域切出手段は、
   前記クエリ画像から抽出した部分画像と類似する前記検索対象画像内の部分画像を選択する際に、該部分画像の集合のうちの外側に位置する部分画像を選択から除外して、その除外後の部分画像を含む領域を切り出すことを特徴とする請求項１または２に記載の画像検索装置。
4. コンピュータが、クエリ画像との類似度を算出して該類似度の高い画像を検索対象画像の中から検索する画像検索方法において、
   前記クエリ画像内から複数の部分画像を抽出する第１抽出工程と、
   前記検索対象画像内から複数の部分画像を抽出する第２抽出工程と、
   前記クエリ画像から抽出した部分画像と類似する前記検索対象画像内の部分画像を選択し、この選択した部分画像を含む領域を前記検索対象画像内から切り出す領域切出工程と、
   前記クエリ画像と、前記切り出された領域内の画像との間の類似度を算出する際に、前記切り出された領域内に含まれる前記部分画像の数と、該領域内の部分画像のうちの前記クエリ画像から抽出した部分画像と類似する部分画像の数との比を重みとして付与する類似度算出工程と、
   を前記コンピュータが実行することを特徴とする画像検索方法。
5. 請求項４に記載の画像検索方法をコンピュータに実行させるためのプログラム。

Images