特徴ベクトル生成装置、特徴ベクトル生成方法及びプログラム
【課題】ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減すること。
【解決手段】特徴ベクトル生成部２０は、部分画像抽出部２２により、クエリ画像から複数の部分画像を抽出する。クラスタリング部２４は、抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングする。マッピング部２６は、クラスタリングによって形成されたクラスタ（基準クラスタ）と、ビジュアルキーワード（基準クラスタ）との間の距離を算出し、クラスタにクラスタリングされた部分画像を、該クラスタとの距離が最も近いビジュアルキーワードに分類する。
【解決手段】特徴ベクトル生成部２０は、部分画像抽出部２２により、クエリ画像から複数の部分画像を抽出する。クラスタリング部２４は、抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングする。マッピング部２６は、クラスタリングによって形成されたクラスタ（基準クラスタ）と、ビジュアルキーワード（基準クラスタ）との間の距離を算出し、クラスタにクラスタリングされた部分画像を、該クラスタとの距離が最も近いビジュアルキーワードに分類する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴ベクトル生成装置、特徴ベクトル生成方法及びプログラムに関する。
【背景技術】
【０００２】
画像を検索キーとして入力し、画像の特徴量（配色、テクスチャ、形状等の画像の特徴を数値化して表現したもの）を比較することにより、検索キーである画像（以下「クエリ画像」という）に類似する画像を検索する技術が知られている。ユーザがクエリ画像を入力すると、クエリ画像から特徴量を抽出して、検索対象の画像の特徴量との類似度を算出することで、類似画像を検索する（例えば、特許文献１）。
【０００３】
また、画像内の部分的な領域に注目した類似画像の検索技術として、ビジュアルキーワードという手法が知られている。これは、１枚の画像が複数の部分画像により構成されていると捉えることにより考案された手法であり、次のような処理により特徴ベクトルが生成される。
【０００４】
即ち、画像から複数の部分画像を抽出して、予め画像がクラスタリングされて形成された基準となるクラスタ（以下適宜「基準クラスタ」という）に対して、その部分画像を特徴量に基づいて分類し、各部分画像が属する基準クラスタの数に基づいて特徴ベクトルが生成される。このように、ビジュアルキーワードを用いることで、画像全体から抽出される特徴量ではなく、画像を細かな領域として捉えた特徴量により、精度のよい画像検索が可能になる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−５２１７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上述の従来技術には、次ぎのような課題があった。
先ず、特許文献１の技術により１枚の画像から抽出される特徴量は、その画像全体の特徴を示すものであるため、全体的な構成が類似している画像を検索する際に有効である。しかし、一般に１枚の画像の中に含まれるオブジェクトは多種多様であり、それらを特許文献１の特徴量で表現するのは困難である。
【０００７】
一枚の画像が複数の領域に分割し、その分割した部分画像毎の特徴量によって画像の特徴を表すこともできるが、比較対象の画像間で部分画像毎の特徴量を比較するには、例えば、１００分割した２枚の画像の比較であれば、１００×１００通りのパターンで特徴量を比較し類似度を算出するように、計算量が膨大となる。
【０００８】
これに対し、ビジュアルキーワードあれば、各基準クラスタに分類された部分画像の数によって表現された特徴ベクトルにより類似度の算出が可能になる。しかし、各部分画像と、各基準クラスタとの間の距離を全て算出する必要があり、１枚の画像から抽出される部分画像は数百〜数千、分類対象であるクラスタの数は数万〜数十万となると、これらの全ての組み合わせでの距離算出の計算コストは膨大となってしまった。
【０００９】
本発明は、上述の課題に鑑みて為されたものであり、その目的とするところは、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することである。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、第１の発明は、画像内から抽出した複数の部分画像を複数の基準クラスタの何れかに分類して、各基準クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成装置において、前記抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングするクラスタリング手段と、前記クラスタリングによって形成されたクラスタを対象クラスタとして、該対象クラスタと前記各基準クラスタとの間の距離を算出する距離算出手段と、前記対象クラスタに属する部分画像を、該対象クラスタとの前記距離が最も近い基準クラスタに分類する分類手段と、を備えることを特徴としている。
【００１１】
第１の発明によれば、画像から抽出した部分画像を一旦クラスタリングして纏め上げ、このクラスタリングに形成される対象クラスタと、基準クラスタとの間の距離に基づいて、対象クラスタに属する部分画像をまとめて基準クラスタに分類する。このため、部分画像と、基準クラスタとの間の距離を全て算出する計算コストが削減される。従って、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することができる。
【００１２】
また、第２の発明における前記分類手段は、前記個々の部分画像と、前記画像内から抽出した部分画像の分類が行われた基準クラスタとの間の距離を算出し、この距離が最も近い基準クラスタに分類先を変更することを特徴としている。
【００１３】
第２の発明によれば、個々の部分画像と、分類が行われた基準クラスタとの間の距離が最も近い基準クラスタに分類先を変更するため、クラスタ単位でまとめて分類された部分画像の中でも、基準クラスタとの距離が遠い部分画像については適切な基準クラスタに分類先を変更することができる。従って、上記の効果に加えて、特徴ベクトルの精度を向上させることができる。
【００１４】
また、第３の発明において、前記分類が行われた基準クラスタと、該基準クラスタに分類された前記部分画像との間の距離を算出するクラスタ距離算出手段を更に備え、前記分類手段は、前記クラスタ距離算出手段により算出された距離が所定値以上の部分画像を選定し、その選定した部分画像と該部分画像の分類が行われた基準クラスタとの間の距離を算出して、分類先の変更を行うことを特徴としている。
【００１５】
第３の発明によれば、分類された部分画像と、分類先の基準クラスタとの間の距離が一定値以上となる部分画像について、該部分画像と基準クラスタとの間の距離に基づいて分類先を変更する。このため、対象クラスタとの距離が遠い部分画像について、分類先の変更を行える。従って、分類先の見直しを行う部分画像を絞り込むことができ、特徴ベクトルの精度向上のための計算コストを抑えることができる。
【発明の効果】
【００１６】
本発明によれば、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することができる。
【図面の簡単な説明】
【００１７】
【図１】画像検索装置の機能構成を示すブロック図。
【図２】特徴ベクトル生成処理のフローチャート。
【図３】特徴ベクトルを生成するまでの処理を説明するための概念図。
【図４】マッピング先のビジュアルキーワードを変更する処理を説明するための概念図。
【発明を実施するための最良の形態】
【００１８】
［画像検索装置の構成］
以下、本発明の特徴ベクトル生成装置を、図１に示す画像検索装置１内の特徴ベクトル生成部２０及びインデクシング部７０に適用した場合の実施の形態を図面に基づいて説明する。
【００１９】
図１は、画像検索装置１の機能ブロック図である。画像検索装置１は、通信ネットワークを介して接続されたインターネットに接続され、該インターネットを介してウェブ上から画像データを収集可能となっている。この収集したデータをデータベース（ＤＢ）に蓄積して、検索対象の画像を作成する。
【００２０】
画像検索装置１は、通信ネットワークを介して接続されたパーソナルコンピュータや携帯端末等のクライアント端末から送信されるクエリ画像を検索要求として受信する。そして、その検索要求に応じた類似画像検索を行って、類似度順にランキングした検索結果をクライアント端末に返送する。
【００２１】
本実施形態における画像検索装置１は、ビジュアルキーワードの手法を用いて画像の特徴ベクトルを生成してインデックス化する。ビジュアルキーワードによる画像検索とは、１枚の画像を複数の画像領域の集合として表現し、各画像を構成する画像領域（以下、適宜「部分画像」という）から得られる特徴量に基づいて画像のインデックス（特徴ベクトル）を生成する技術であり、テキスト中のキーワードから文章の特徴量を求めるテキスト検索技術の応用といえる。
【００２２】
このため、ビジュアルキーワードによる画像検索では、画像中の画像領域をキーワードとして扱うことでテキスト検索技術（転置インデックスやベクトル空間モデル、単語の出現頻度等）における技術を画像領域検索へ適用して、大規模且つ高速性を実現することができる。
【００２３】
ビジュアルキーワードによる画像検索についての参考技術文献としては、
・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.）等において公開されており、適宜公知技術を採用可能である。
【００４８】
この特徴領域から抽出した特徴量に基づいて生成した特徴ベクトルは、オブジェクト（物体）の存在する可能性の高い特徴領域から生成されるため、画像中のオブジェクトの特徴を示す指標として有効である。
【００４９】
また、領域分割により部分画像を抽出している場合には、画像の配色やテクスチャ、形状等の各画像の特徴を数値化して表現した画像特徴量を用いる。この領域分割により検出した領域画像の特徴量から生成した特徴ベクトルは、画像を構成する各部分から生成されるため、画像の全体的な構成を示す指標として有効である。
【００５０】
そして、クラスタリング部２４が、画像データから抽出した複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングする（ステップＳ１３）。このクラスタリングにより形成されるクラスタを適宜「対象クラスタ」という。クラスタリングの標準的な手法としては、k-means, Hierarchical Agglomerative Clustering(HAC)などが用いられる。また、クラスタ数Ｍは、部分画像の数の１／５（Ｌ＝５）〜１／１０（Ｌ＝１０）程度に設定する。
【００５１】
例えば、部分画像抽出部２２は、図３に示すように画像Ｇ１からＫ個の部分画像を抽出したとする。この部分画像をクラスタリング部２４は、部分画像の特徴量に基づいてクラスタリングすることにより、図３のようにＭ個の対象クラスタを形成する。各対象クラスタには、類似する特徴量を有する部分画像が纏め上げられることになる。
【００５２】
次に、マッピング部２６は、ステップＳ１３のクラスタリングにより形成された対象クラスタの中から１つを選択し（ステップＳ１４）、その対象クラスタと、各ビジュアルキーワード（ビジュアルキーワード生成部６０により予め形成された基準クラスタ）との間の距離を算出する（ステップＳ１５）。この距離は、特徴量空間上におけるクラスタの中心座標と、ビジュアルキーワードの中心座標との間の距離によって求められる。クラスタの中心座標に用いる値としては、クラスタに属するデータ（特徴量）の平均値としてのcentroidの他に、中心に最も近いデータを採用するmedoidや、データを昇順に並べたときに中央に位置するデータを採用するmedian等を適用することができる。
【００５３】
そして、算出した距離が最も近いビジュアルキーワードに、選択した対象クラスタ内の部分画像をマッピング（分類）する（ステップＳ１６）。この際、マッピング部２６は、インデックスＤＢ７５の特徴ベクトルの各ビジュアルキーワードのスカラ値にその部分画像の数を加算する。また、領域管理ＤＢ８０の部分画像の領域ＩＤに、該部分画像をマッピングしたビジュアルキーワードのＶＫＩＤの割り当てを行い、各々を対応付けて記憶する。
【００５４】
例えば、図３において、クラスタ＃１と、ビジュアルキーワードＶＫ１〜ＶＫＮとの間の距離を算出した結果、ビジュアルキーワードＶＫ３が最も近いと判定されたとする。この場合は、クラスタ＃１に属する部分画像Ｇ１１〜Ｇ１５がビジュアルキーワードＶＫ３にマッピングされることとなる。
【００５５】
次に、マッピング部２６は、ステップＳ１４において全ての対象クラスタを選択したか否かを判定し（ステップＳ１７）、未選択の対象クラスタがある場合には（ステップＳ１７；Ｎｏ）、ステップＳ１４に処理を移行して、ステップＳ１６までの処理を繰り返す。
【００５６】
また、全ての対象クラスタを選択したと判定した場合には（ステップＳ１７；Ｙｅｓ）、各部分画像と、ステップＳ１６でマッピングが行われたビジュアルキーワードとの間の距離を算出して、その距離に基づいて部分画像の再マッピングを行う。
【００５７】
即ち、部分画像を１つ選択して（ステップＳ１８）、その部分画像と、部分画像をマッピングしているビジュアルキーワードとの間の距離を算出する（ステップＳ１９）。この距離算出は、選択した部分画像をマッピングしたビジュアルキーワードだけでなく、ステップＳ１６においてマッピングが行われた全てのビジュアルキーワードに対して行う。また、ビジュアルキーワードとの間の距離は、部分画像の有する特徴量の特徴量空間上での座標と、ビジュアルキーワードの中心座標との間の距離により求められる。
【００５８】
そして、選択した部分画像との間の距離が最も近いビジュアルキーワードを選定して、部分画像にそのビジュアルキーワードのＶＫＩＤを割り当てることで、該ビジュアルキーワードに再マッピングする（ステップＳ２０）。
【００５９】
例えば、ステップＳ１６において、図４に示すように、クラスタ＃１に属する部分画像Ｇ１１〜Ｇ１５をビジュアルキーワードＶＫ３にマッピングしたとする。この際、部分画像Ｇ１５と、各ビジュアルキーワードとの間の距離を算出した結果、ビジュアルキーワードＶＫ５との距離が最も近いと判定され、部分画像Ｇ１５は、ビジュアルキーワードＶＫ３からビジュアルキーワードＶＫ５に再マッピングされることとなる。従って、クラスタとして一纏まりで部分画像がマッピングされたとして、適切なビジュアルキーワードに再マッピングすることができる。
【００６０】
マッピング部２６は、ステップＳ１８において全ての部分画像を選択したか否かを判定して（ステップＳ２１）、未選択のものがあると判定した場合には（ステップＳ２１；Ｎｏ）、ステップＳ１８に処理を移行する。
【００６１】
また、全ての部分画像を選択したと判定した場合には（ステップＳ２１；Ｙｅｓ）、マッピングしたビジュアルキーワードに基づいて特徴ベクトルを生成する（ステップＳ２２）。即ち、マッピングした結果のビジュアルキーワード毎での部分画像の出現頻度により多次元で表される特徴ベクトルを生成する。これにより、図３のように画像Ｇ１についての特徴ベクトルＶが生成される。
【００６２】
特徴ベクトル生成部２０は、上記の処理により生成した特徴ベクトルを類似度算出部３０に出力すると、類似度算出部３０が、検索対象画像の特徴ベクトルとの間の類似度を算出する。また、インデクシング部７０は、上記の処理により生成した特徴ベクトルを、検索対象画像の画像ＩＤに対応付けてインデックスＤＢ７５に対応付けて記憶する。
【００６３】
以上のように、本実施形態によれば、画像から抽出した部分画像をクラスタリングすることにより、類似する部分画像を纏め上げて、クラスタ単位でビジュアルキーワードにマッピングするため、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することができる。
【００６４】
より具体的には、抽出した部分画像の数がＫ個、ビジュアルキーワードの数がＮ個とすると、従来の各部分画像とビジュアルキーワードとの間の距離に基づいてマッピング手法であれば、Ｋ×Ｎの計算コストがかかる。これに対し、本実施形態の手法であれば、Ｋ個の部分画像をＭ個のクラスタにクラスタリングする計算コストＫ×Ｍと、Ｍ個のクラスタとＮ個のビジュアルキーワードとの距離算出によりマッピングする計算コストＭ×Ｎとの合計となる。
【００６５】
例えば、一枚の画像から抽出される部分画像が1,000個であり、クラスタ数が200個（部分画像の数の１／５）であり、ビジュアルキーワードが450,000個であるとする。この場合、従来のマッピング手法であれば、計算コストは、450,000,000（＝1,000×450,000）となり、本実施形態の手法であれば、計算コストは、90,200,000（＝1,000×200＋200×450,000）となる。このように、本実施形態の手法であれば、従来の手法に対して、計算コストを約80％削減することができる。
【００６６】
また、ステップＳ１８〜Ｓ２１の処理により一旦マッピングした部分画像を再マッピングするために距離算出を行っているが、この距離の算出は、全てのビジュアルキーワードではなく、ステップＳ１６でマッピングされたビジュアルキーワードとしている。即ち、予め生成しておいたＮ個のビジュアルキーワードのうち、部分画像がマッピングされたビジュアルキーワードはＱ個（≦Ｎ）となるから、このＱ個のビジュアルキーワードとの間の距離算出を行えばよく、この計算コストはＫ×Ｑとなる。従って、特徴ベクトルの精度向上のための計算コストも抑えることができる。
【００６７】
尚、上述の実施形態は本発明を適用した一例であって、その適用可能な範囲は上述に限られない。例えば、本実施形態において、ステップＳ１６のマッピングの後に、部分画像とビジュアルキーワードとの距離に基づいて再マッピングを行うこととして説明したが、この処理を行わずにマッピングを完了させることとしてもよい。但し、上述したように、再マッピングすることで、生成される特徴ベクトルの精度が向上するのは無論である。
【００６８】
また、上述の実施形態では、クラスタ内の部分画像を、該クラスタと最も距離の近いビジュアルキーワードにマッピングすることとして説明したが、例えば、クラスタ内でも該クラスタの中心座標と距離が一定値以上離れている部分画像については、個別にビジュアルキーワードとの距離を測ってマッピングすることとしてもよい。
【００６９】
即ち、クラスタ距離算出手段としてのクラスタリング部２４（７４）は、クラスタリングの際に、クラスタの中心座標と、部分画像との距離を保持しておき、その距離が一定値以上離れている場合には、クラスタ内の部分画像をビジュアルキーワードにマッピングするステップＳ１６の処理の対象から外す。そして、マッピング部２６（７６）は、そのマッピング対象から外した部分画像については、個々にビジュアルキーワードとの間の距離を算出して、最も近いビジュアルキーワードに対してマッピングを行う。
【００７０】
これにより、クラスタリングされた部分画像の大部分を、クラスタとビジュアルキーワードとの距離に基づいてマッピングすることができるので、マッピングの計算コストを低減させつつ、特徴ベクトルの精度も向上させることができる。
【００７１】
また、ステップＳ１８〜Ｓ２１において、画像から抽出した全ての部分画像についてビジュアルキーワードとの距離を算出することしたが、例えば、ステップＳ１６においてマッピングした部分画像のうち、そのマッピング先のビジュアルキーワードの中心との距離が所定値以上の部分画像を選択して距離算出及び再マッピングすることとしてもよい。
【００７２】
具体的には、図４において、部分画像Ｇ１１〜Ｇ１５と、ビジュアルキーワードＶＫ３の中心Ｃ３との距離を算出して、その距離が所定値以上となった部分画像Ｇ１５について他のビジュアルキーワードとの距離を算出して、再マッピングする。従って、再マッピングする対象の部分画像を絞り込むことができる。
【００７３】
また、テキスト検索における単語の重み付け手法であるＴＦ／ＩＤＦ（term frequency-inverse document frequency）により、特徴ベクトルに重み付けを行うこととしてもよい。
【００７４】
ＴＦ／ＩＤＦに関する参考資料としては、
C.D.Manning, P.Raghavan and H.Schutze:" Introduction to Information Retrieval",Cambridge University Press.2008.
が知られている。
【００７５】
ＴＦ／ＩＤＦは、文章中の特徴的な単語を抽出するためのアルゴリズムであり、単語の出現頻度であるＴＦと、逆出現頻度であるＩＤＦとの二つの指標により算出される。具体的には、次式により求められる。
ＴＦ／ＩＤＦ＝ＴＦ（ｉ,ｊ）／Ｔ（ｉ）＊ＩＤＦ（ｊ）
ＩＤＦ（ｉ）＝ｌｏｇ（Ｎ／ＤＦ（ｉ））
【００７６】
ここで、
ＴＦ（ｉ，ｊ）は、キーワード抽出対象のドキュメントｉ中でのキーワードｊの出現数
Ｔ（ｉ）は、ドキュメントｉ中の全ての単語の数
Ｎは、全てのドキュメント数
ＤＦ（ｊ）は、キーワードｊが含まれるドキュメントの数
である。
【００７７】
これを、ドキュメントを画像、単語を同一のビジュアルキーワードに属する部分画像として捉え、各画像のビジュアルキーワード毎にＴＦ／ＩＤＦ値を求めて、このＴＦ／ＩＤＦ値を、部分画像をマッピングしたビジュアルキーワードに加算することで、特徴ベクトルを生成する。
【００７８】
このとき、画像ＩＤをｉ、各ビジュアルキーワードｋとして、各ビジュアルキーワードの重み値であるＴＦ／ＩＤＦ（ｉ,ｋ）は以下の式により算出する。
【００７９】
ＴＦ／ＩＤＦ（ｉ,ｋ）＝ＴＦ（ｉ,ｋ）／Ｔ（ｉ）＊ＩＤＦ（ｋ）
ＩＤＦ（ｋ） ＝ｌｏｇ（Ｎ／ＤＦ（ｋ））
【００８０】
尚、ＴＦ（ｉ,ｋ）は、画像ｉから抽出した部分画像がビジュアルキーワードｋで出現する数に重み付けを行ったものであり、各ビジュアルキーワードｋ内に属する（出現する）部分画像と、ビジュアルキーワードｋの中心点との距離に基づく上述した重み値（０〜１）となる。
【００８１】
また、Ｔ（ｉ）は、画像ｉから抽出した部分画像の総数に、ビジュアルキーワードとの距離に基づく重み付けをした値であり、画像ｉから抽出した各部分画像が属するクラスタとの距離に基づいた重み値を合計したものである。
【００８２】
また、ＤＦ（ｋ）は、各ビジュアルキーワードｋに分類した部分画像が、各ビジュアルキーワードｋに出現する数に、ビジュアルキーワードとの距離に基づく重み付けを行った値である。また、Ｎは、検索対象画像ＤＢ９０の画像総数である。
【００８３】
このように、ＴＦ／ＩＤＦにおけるドキュメントを画像とみなし、ドキュメント内の単語を同一のビジュアルキーワードに属する部分画像とみなして重み付けを行うことで、各画像に出現する部分画像の重要度を下げ、特定の画像に際立って出現する特徴的な部分画像についての重要度を上げるように特徴ベクトルのスカラ値に重み付けを行うことができる。
【００８４】
このＴＦ／ＩＤＦによる重み付けを用いて、クエリ画像内の部分画像が属するビジュアルキーワードと、検索対象画像内の部分画像が属するビジュアルキーワードとの類似スコアを求めてもよい。
【００８５】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００８６】
１ 画像検索装置
１０ クエリ画像受付部
２０ 特徴ベクトル生成部
２２ 部分画像抽出部
２４ クラスタリング部
２６ マッピング部
３０ 類似度算出部
５０ 検索結果出力部
６０ ビジュアルキーワード生成部
７０ インデクシング部
７２ 部分画像抽出部
７４ クラスタリング部
７６ マッピング部
６５ ビジュアルキーワードＤＢ
７０ 検索対象画像ＤＢ
７５ インデックスＤＢ
８０ 領域管理ＤＢ
９０ 検索対象画像ＤＢ
【技術分野】
【０００１】
本発明は、特徴ベクトル生成装置、特徴ベクトル生成方法及びプログラムに関する。
【背景技術】
【０００２】
画像を検索キーとして入力し、画像の特徴量（配色、テクスチャ、形状等の画像の特徴を数値化して表現したもの）を比較することにより、検索キーである画像（以下「クエリ画像」という）に類似する画像を検索する技術が知られている。ユーザがクエリ画像を入力すると、クエリ画像から特徴量を抽出して、検索対象の画像の特徴量との類似度を算出することで、類似画像を検索する（例えば、特許文献１）。
【０００３】
また、画像内の部分的な領域に注目した類似画像の検索技術として、ビジュアルキーワードという手法が知られている。これは、１枚の画像が複数の部分画像により構成されていると捉えることにより考案された手法であり、次のような処理により特徴ベクトルが生成される。
【０００４】
即ち、画像から複数の部分画像を抽出して、予め画像がクラスタリングされて形成された基準となるクラスタ（以下適宜「基準クラスタ」という）に対して、その部分画像を特徴量に基づいて分類し、各部分画像が属する基準クラスタの数に基づいて特徴ベクトルが生成される。このように、ビジュアルキーワードを用いることで、画像全体から抽出される特徴量ではなく、画像を細かな領域として捉えた特徴量により、精度のよい画像検索が可能になる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−５２１７５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上述の従来技術には、次ぎのような課題があった。
先ず、特許文献１の技術により１枚の画像から抽出される特徴量は、その画像全体の特徴を示すものであるため、全体的な構成が類似している画像を検索する際に有効である。しかし、一般に１枚の画像の中に含まれるオブジェクトは多種多様であり、それらを特許文献１の特徴量で表現するのは困難である。
【０００７】
一枚の画像が複数の領域に分割し、その分割した部分画像毎の特徴量によって画像の特徴を表すこともできるが、比較対象の画像間で部分画像毎の特徴量を比較するには、例えば、１００分割した２枚の画像の比較であれば、１００×１００通りのパターンで特徴量を比較し類似度を算出するように、計算量が膨大となる。
【０００８】
これに対し、ビジュアルキーワードあれば、各基準クラスタに分類された部分画像の数によって表現された特徴ベクトルにより類似度の算出が可能になる。しかし、各部分画像と、各基準クラスタとの間の距離を全て算出する必要があり、１枚の画像から抽出される部分画像は数百〜数千、分類対象であるクラスタの数は数万〜数十万となると、これらの全ての組み合わせでの距離算出の計算コストは膨大となってしまった。
【０００９】
本発明は、上述の課題に鑑みて為されたものであり、その目的とするところは、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することである。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、第１の発明は、画像内から抽出した複数の部分画像を複数の基準クラスタの何れかに分類して、各基準クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成装置において、前記抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングするクラスタリング手段と、前記クラスタリングによって形成されたクラスタを対象クラスタとして、該対象クラスタと前記各基準クラスタとの間の距離を算出する距離算出手段と、前記対象クラスタに属する部分画像を、該対象クラスタとの前記距離が最も近い基準クラスタに分類する分類手段と、を備えることを特徴としている。
【００１１】
第１の発明によれば、画像から抽出した部分画像を一旦クラスタリングして纏め上げ、このクラスタリングに形成される対象クラスタと、基準クラスタとの間の距離に基づいて、対象クラスタに属する部分画像をまとめて基準クラスタに分類する。このため、部分画像と、基準クラスタとの間の距離を全て算出する計算コストが削減される。従って、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することができる。
【００１２】
また、第２の発明における前記分類手段は、前記個々の部分画像と、前記画像内から抽出した部分画像の分類が行われた基準クラスタとの間の距離を算出し、この距離が最も近い基準クラスタに分類先を変更することを特徴としている。
【００１３】
第２の発明によれば、個々の部分画像と、分類が行われた基準クラスタとの間の距離が最も近い基準クラスタに分類先を変更するため、クラスタ単位でまとめて分類された部分画像の中でも、基準クラスタとの距離が遠い部分画像については適切な基準クラスタに分類先を変更することができる。従って、上記の効果に加えて、特徴ベクトルの精度を向上させることができる。
【００１４】
また、第３の発明において、前記分類が行われた基準クラスタと、該基準クラスタに分類された前記部分画像との間の距離を算出するクラスタ距離算出手段を更に備え、前記分類手段は、前記クラスタ距離算出手段により算出された距離が所定値以上の部分画像を選定し、その選定した部分画像と該部分画像の分類が行われた基準クラスタとの間の距離を算出して、分類先の変更を行うことを特徴としている。
【００１５】
第３の発明によれば、分類された部分画像と、分類先の基準クラスタとの間の距離が一定値以上となる部分画像について、該部分画像と基準クラスタとの間の距離に基づいて分類先を変更する。このため、対象クラスタとの距離が遠い部分画像について、分類先の変更を行える。従って、分類先の見直しを行う部分画像を絞り込むことができ、特徴ベクトルの精度向上のための計算コストを抑えることができる。
【発明の効果】
【００１６】
本発明によれば、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することができる。
【図面の簡単な説明】
【００１７】
【図１】画像検索装置の機能構成を示すブロック図。
【図２】特徴ベクトル生成処理のフローチャート。
【図３】特徴ベクトルを生成するまでの処理を説明するための概念図。
【図４】マッピング先のビジュアルキーワードを変更する処理を説明するための概念図。
【発明を実施するための最良の形態】
【００１８】
［画像検索装置の構成］
以下、本発明の特徴ベクトル生成装置を、図１に示す画像検索装置１内の特徴ベクトル生成部２０及びインデクシング部７０に適用した場合の実施の形態を図面に基づいて説明する。
【００１９】
図１は、画像検索装置１の機能ブロック図である。画像検索装置１は、通信ネットワークを介して接続されたインターネットに接続され、該インターネットを介してウェブ上から画像データを収集可能となっている。この収集したデータをデータベース（ＤＢ）に蓄積して、検索対象の画像を作成する。
【００２０】
画像検索装置１は、通信ネットワークを介して接続されたパーソナルコンピュータや携帯端末等のクライアント端末から送信されるクエリ画像を検索要求として受信する。そして、その検索要求に応じた類似画像検索を行って、類似度順にランキングした検索結果をクライアント端末に返送する。
【００２１】
本実施形態における画像検索装置１は、ビジュアルキーワードの手法を用いて画像の特徴ベクトルを生成してインデックス化する。ビジュアルキーワードによる画像検索とは、１枚の画像を複数の画像領域の集合として表現し、各画像を構成する画像領域（以下、適宜「部分画像」という）から得られる特徴量に基づいて画像のインデックス（特徴ベクトル）を生成する技術であり、テキスト中のキーワードから文章の特徴量を求めるテキスト検索技術の応用といえる。
【００２２】
このため、ビジュアルキーワードによる画像検索では、画像中の画像領域をキーワードとして扱うことでテキスト検索技術（転置インデックスやベクトル空間モデル、単語の出現頻度等）における技術を画像領域検索へ適用して、大規模且つ高速性を実現することができる。
【００２３】
ビジュアルキーワードによる画像検索についての参考技術文献としては、
・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.）等において公開されており、適宜公知技術を採用可能である。
【００４８】
この特徴領域から抽出した特徴量に基づいて生成した特徴ベクトルは、オブジェクト（物体）の存在する可能性の高い特徴領域から生成されるため、画像中のオブジェクトの特徴を示す指標として有効である。
【００４９】
また、領域分割により部分画像を抽出している場合には、画像の配色やテクスチャ、形状等の各画像の特徴を数値化して表現した画像特徴量を用いる。この領域分割により検出した領域画像の特徴量から生成した特徴ベクトルは、画像を構成する各部分から生成されるため、画像の全体的な構成を示す指標として有効である。
【００５０】
そして、クラスタリング部２４が、画像データから抽出した複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングする（ステップＳ１３）。このクラスタリングにより形成されるクラスタを適宜「対象クラスタ」という。クラスタリングの標準的な手法としては、k-means, Hierarchical Agglomerative Clustering(HAC)などが用いられる。また、クラスタ数Ｍは、部分画像の数の１／５（Ｌ＝５）〜１／１０（Ｌ＝１０）程度に設定する。
【００５１】
例えば、部分画像抽出部２２は、図３に示すように画像Ｇ１からＫ個の部分画像を抽出したとする。この部分画像をクラスタリング部２４は、部分画像の特徴量に基づいてクラスタリングすることにより、図３のようにＭ個の対象クラスタを形成する。各対象クラスタには、類似する特徴量を有する部分画像が纏め上げられることになる。
【００５２】
次に、マッピング部２６は、ステップＳ１３のクラスタリングにより形成された対象クラスタの中から１つを選択し（ステップＳ１４）、その対象クラスタと、各ビジュアルキーワード（ビジュアルキーワード生成部６０により予め形成された基準クラスタ）との間の距離を算出する（ステップＳ１５）。この距離は、特徴量空間上におけるクラスタの中心座標と、ビジュアルキーワードの中心座標との間の距離によって求められる。クラスタの中心座標に用いる値としては、クラスタに属するデータ（特徴量）の平均値としてのcentroidの他に、中心に最も近いデータを採用するmedoidや、データを昇順に並べたときに中央に位置するデータを採用するmedian等を適用することができる。
【００５３】
そして、算出した距離が最も近いビジュアルキーワードに、選択した対象クラスタ内の部分画像をマッピング（分類）する（ステップＳ１６）。この際、マッピング部２６は、インデックスＤＢ７５の特徴ベクトルの各ビジュアルキーワードのスカラ値にその部分画像の数を加算する。また、領域管理ＤＢ８０の部分画像の領域ＩＤに、該部分画像をマッピングしたビジュアルキーワードのＶＫＩＤの割り当てを行い、各々を対応付けて記憶する。
【００５４】
例えば、図３において、クラスタ＃１と、ビジュアルキーワードＶＫ１〜ＶＫＮとの間の距離を算出した結果、ビジュアルキーワードＶＫ３が最も近いと判定されたとする。この場合は、クラスタ＃１に属する部分画像Ｇ１１〜Ｇ１５がビジュアルキーワードＶＫ３にマッピングされることとなる。
【００５５】
次に、マッピング部２６は、ステップＳ１４において全ての対象クラスタを選択したか否かを判定し（ステップＳ１７）、未選択の対象クラスタがある場合には（ステップＳ１７；Ｎｏ）、ステップＳ１４に処理を移行して、ステップＳ１６までの処理を繰り返す。
【００５６】
また、全ての対象クラスタを選択したと判定した場合には（ステップＳ１７；Ｙｅｓ）、各部分画像と、ステップＳ１６でマッピングが行われたビジュアルキーワードとの間の距離を算出して、その距離に基づいて部分画像の再マッピングを行う。
【００５７】
即ち、部分画像を１つ選択して（ステップＳ１８）、その部分画像と、部分画像をマッピングしているビジュアルキーワードとの間の距離を算出する（ステップＳ１９）。この距離算出は、選択した部分画像をマッピングしたビジュアルキーワードだけでなく、ステップＳ１６においてマッピングが行われた全てのビジュアルキーワードに対して行う。また、ビジュアルキーワードとの間の距離は、部分画像の有する特徴量の特徴量空間上での座標と、ビジュアルキーワードの中心座標との間の距離により求められる。
【００５８】
そして、選択した部分画像との間の距離が最も近いビジュアルキーワードを選定して、部分画像にそのビジュアルキーワードのＶＫＩＤを割り当てることで、該ビジュアルキーワードに再マッピングする（ステップＳ２０）。
【００５９】
例えば、ステップＳ１６において、図４に示すように、クラスタ＃１に属する部分画像Ｇ１１〜Ｇ１５をビジュアルキーワードＶＫ３にマッピングしたとする。この際、部分画像Ｇ１５と、各ビジュアルキーワードとの間の距離を算出した結果、ビジュアルキーワードＶＫ５との距離が最も近いと判定され、部分画像Ｇ１５は、ビジュアルキーワードＶＫ３からビジュアルキーワードＶＫ５に再マッピングされることとなる。従って、クラスタとして一纏まりで部分画像がマッピングされたとして、適切なビジュアルキーワードに再マッピングすることができる。
【００６０】
マッピング部２６は、ステップＳ１８において全ての部分画像を選択したか否かを判定して（ステップＳ２１）、未選択のものがあると判定した場合には（ステップＳ２１；Ｎｏ）、ステップＳ１８に処理を移行する。
【００６１】
また、全ての部分画像を選択したと判定した場合には（ステップＳ２１；Ｙｅｓ）、マッピングしたビジュアルキーワードに基づいて特徴ベクトルを生成する（ステップＳ２２）。即ち、マッピングした結果のビジュアルキーワード毎での部分画像の出現頻度により多次元で表される特徴ベクトルを生成する。これにより、図３のように画像Ｇ１についての特徴ベクトルＶが生成される。
【００６２】
特徴ベクトル生成部２０は、上記の処理により生成した特徴ベクトルを類似度算出部３０に出力すると、類似度算出部３０が、検索対象画像の特徴ベクトルとの間の類似度を算出する。また、インデクシング部７０は、上記の処理により生成した特徴ベクトルを、検索対象画像の画像ＩＤに対応付けてインデックスＤＢ７５に対応付けて記憶する。
【００６３】
以上のように、本実施形態によれば、画像から抽出した部分画像をクラスタリングすることにより、類似する部分画像を纏め上げて、クラスタ単位でビジュアルキーワードにマッピングするため、ビジュアルキーワードを用いた特徴ベクトル生成のための計算コストを低減することができる。
【００６４】
より具体的には、抽出した部分画像の数がＫ個、ビジュアルキーワードの数がＮ個とすると、従来の各部分画像とビジュアルキーワードとの間の距離に基づいてマッピング手法であれば、Ｋ×Ｎの計算コストがかかる。これに対し、本実施形態の手法であれば、Ｋ個の部分画像をＭ個のクラスタにクラスタリングする計算コストＫ×Ｍと、Ｍ個のクラスタとＮ個のビジュアルキーワードとの距離算出によりマッピングする計算コストＭ×Ｎとの合計となる。
【００６５】
例えば、一枚の画像から抽出される部分画像が1,000個であり、クラスタ数が200個（部分画像の数の１／５）であり、ビジュアルキーワードが450,000個であるとする。この場合、従来のマッピング手法であれば、計算コストは、450,000,000（＝1,000×450,000）となり、本実施形態の手法であれば、計算コストは、90,200,000（＝1,000×200＋200×450,000）となる。このように、本実施形態の手法であれば、従来の手法に対して、計算コストを約80％削減することができる。
【００６６】
また、ステップＳ１８〜Ｓ２１の処理により一旦マッピングした部分画像を再マッピングするために距離算出を行っているが、この距離の算出は、全てのビジュアルキーワードではなく、ステップＳ１６でマッピングされたビジュアルキーワードとしている。即ち、予め生成しておいたＮ個のビジュアルキーワードのうち、部分画像がマッピングされたビジュアルキーワードはＱ個（≦Ｎ）となるから、このＱ個のビジュアルキーワードとの間の距離算出を行えばよく、この計算コストはＫ×Ｑとなる。従って、特徴ベクトルの精度向上のための計算コストも抑えることができる。
【００６７】
尚、上述の実施形態は本発明を適用した一例であって、その適用可能な範囲は上述に限られない。例えば、本実施形態において、ステップＳ１６のマッピングの後に、部分画像とビジュアルキーワードとの距離に基づいて再マッピングを行うこととして説明したが、この処理を行わずにマッピングを完了させることとしてもよい。但し、上述したように、再マッピングすることで、生成される特徴ベクトルの精度が向上するのは無論である。
【００６８】
また、上述の実施形態では、クラスタ内の部分画像を、該クラスタと最も距離の近いビジュアルキーワードにマッピングすることとして説明したが、例えば、クラスタ内でも該クラスタの中心座標と距離が一定値以上離れている部分画像については、個別にビジュアルキーワードとの距離を測ってマッピングすることとしてもよい。
【００６９】
即ち、クラスタ距離算出手段としてのクラスタリング部２４（７４）は、クラスタリングの際に、クラスタの中心座標と、部分画像との距離を保持しておき、その距離が一定値以上離れている場合には、クラスタ内の部分画像をビジュアルキーワードにマッピングするステップＳ１６の処理の対象から外す。そして、マッピング部２６（７６）は、そのマッピング対象から外した部分画像については、個々にビジュアルキーワードとの間の距離を算出して、最も近いビジュアルキーワードに対してマッピングを行う。
【００７０】
これにより、クラスタリングされた部分画像の大部分を、クラスタとビジュアルキーワードとの距離に基づいてマッピングすることができるので、マッピングの計算コストを低減させつつ、特徴ベクトルの精度も向上させることができる。
【００７１】
また、ステップＳ１８〜Ｓ２１において、画像から抽出した全ての部分画像についてビジュアルキーワードとの距離を算出することしたが、例えば、ステップＳ１６においてマッピングした部分画像のうち、そのマッピング先のビジュアルキーワードの中心との距離が所定値以上の部分画像を選択して距離算出及び再マッピングすることとしてもよい。
【００７２】
具体的には、図４において、部分画像Ｇ１１〜Ｇ１５と、ビジュアルキーワードＶＫ３の中心Ｃ３との距離を算出して、その距離が所定値以上となった部分画像Ｇ１５について他のビジュアルキーワードとの距離を算出して、再マッピングする。従って、再マッピングする対象の部分画像を絞り込むことができる。
【００７３】
また、テキスト検索における単語の重み付け手法であるＴＦ／ＩＤＦ（term frequency-inverse document frequency）により、特徴ベクトルに重み付けを行うこととしてもよい。
【００７４】
ＴＦ／ＩＤＦに関する参考資料としては、
C.D.Manning, P.Raghavan and H.Schutze:" Introduction to Information Retrieval",Cambridge University Press.2008.
が知られている。
【００７５】
ＴＦ／ＩＤＦは、文章中の特徴的な単語を抽出するためのアルゴリズムであり、単語の出現頻度であるＴＦと、逆出現頻度であるＩＤＦとの二つの指標により算出される。具体的には、次式により求められる。
ＴＦ／ＩＤＦ＝ＴＦ（ｉ,ｊ）／Ｔ（ｉ）＊ＩＤＦ（ｊ）
ＩＤＦ（ｉ）＝ｌｏｇ（Ｎ／ＤＦ（ｉ））
【００７６】
ここで、
ＴＦ（ｉ，ｊ）は、キーワード抽出対象のドキュメントｉ中でのキーワードｊの出現数
Ｔ（ｉ）は、ドキュメントｉ中の全ての単語の数
Ｎは、全てのドキュメント数
ＤＦ（ｊ）は、キーワードｊが含まれるドキュメントの数
である。
【００７７】
これを、ドキュメントを画像、単語を同一のビジュアルキーワードに属する部分画像として捉え、各画像のビジュアルキーワード毎にＴＦ／ＩＤＦ値を求めて、このＴＦ／ＩＤＦ値を、部分画像をマッピングしたビジュアルキーワードに加算することで、特徴ベクトルを生成する。
【００７８】
このとき、画像ＩＤをｉ、各ビジュアルキーワードｋとして、各ビジュアルキーワードの重み値であるＴＦ／ＩＤＦ（ｉ,ｋ）は以下の式により算出する。
【００７９】
ＴＦ／ＩＤＦ（ｉ,ｋ）＝ＴＦ（ｉ,ｋ）／Ｔ（ｉ）＊ＩＤＦ（ｋ）
ＩＤＦ（ｋ） ＝ｌｏｇ（Ｎ／ＤＦ（ｋ））
【００８０】
尚、ＴＦ（ｉ,ｋ）は、画像ｉから抽出した部分画像がビジュアルキーワードｋで出現する数に重み付けを行ったものであり、各ビジュアルキーワードｋ内に属する（出現する）部分画像と、ビジュアルキーワードｋの中心点との距離に基づく上述した重み値（０〜１）となる。
【００８１】
また、Ｔ（ｉ）は、画像ｉから抽出した部分画像の総数に、ビジュアルキーワードとの距離に基づく重み付けをした値であり、画像ｉから抽出した各部分画像が属するクラスタとの距離に基づいた重み値を合計したものである。
【００８２】
また、ＤＦ（ｋ）は、各ビジュアルキーワードｋに分類した部分画像が、各ビジュアルキーワードｋに出現する数に、ビジュアルキーワードとの距離に基づく重み付けを行った値である。また、Ｎは、検索対象画像ＤＢ９０の画像総数である。
【００８３】
このように、ＴＦ／ＩＤＦにおけるドキュメントを画像とみなし、ドキュメント内の単語を同一のビジュアルキーワードに属する部分画像とみなして重み付けを行うことで、各画像に出現する部分画像の重要度を下げ、特定の画像に際立って出現する特徴的な部分画像についての重要度を上げるように特徴ベクトルのスカラ値に重み付けを行うことができる。
【００８４】
このＴＦ／ＩＤＦによる重み付けを用いて、クエリ画像内の部分画像が属するビジュアルキーワードと、検索対象画像内の部分画像が属するビジュアルキーワードとの類似スコアを求めてもよい。
【００８５】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００８６】
１ 画像検索装置
１０ クエリ画像受付部
２０ 特徴ベクトル生成部
２２ 部分画像抽出部
２４ クラスタリング部
２６ マッピング部
３０ 類似度算出部
５０ 検索結果出力部
６０ ビジュアルキーワード生成部
７０ インデクシング部
７２ 部分画像抽出部
７４ クラスタリング部
７６ マッピング部
６５ ビジュアルキーワードＤＢ
７０ 検索対象画像ＤＢ
７５ インデックスＤＢ
８０ 領域管理ＤＢ
９０ 検索対象画像ＤＢ
【特許請求の範囲】
【請求項１】
画像内から抽出した複数の部分画像を複数の基準クラスタの何れかに分類して、各基準クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成装置において、
前記抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングするクラスタリング手段と、
前記クラスタリングによって形成されたクラスタを対象クラスタとして、該対象クラスタと前記各基準クラスタとの間の距離を算出する距離算出手段と、
前記対象クラスタに属する部分画像を、該対象クラスタとの前記距離が最も近い基準クラスタに分類する分類手段と、
を備えることを特徴とする特徴ベクトル生成装置。
【請求項２】
前記分類手段は、
前記個々の部分画像と、前記画像内から抽出した部分画像の分類が行われた基準クラスタとの間の距離を算出し、この距離が最も近い基準クラスタに分類先を変更する
ことを特徴とする請求項１に記載の特徴ベクトル生成装置。
【請求項３】
前記分類が行われた基準クラスタと、該基準クラスタに分類された前記部分画像との間の距離を算出するクラスタ距離算出手段を更に備え、
前記分類手段は、
前記クラスタ距離算出手段により算出された距離が所定値以上の部分画像を選定し、その選定した部分画像と該部分画像の分類が行われた基準クラスタとの間の距離を算出して、分類先の変更を行う
ことを特徴とする請求項２に記載の特徴ベクトル生成装置。
【請求項４】
コンピュータが、画像内から抽出した複数の部分画像を複数の基準クラスタの何れかに分類して、各基準クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成方法において、
前記抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングするクラスタリング工程と、
前記クラスタリングによって形成されたクラスタを対象クラスタとして、該対象クラスタと前記各基準クラスタとの間の距離を算出する距離算出工程と、
前記対象クラスタに属する部分画像を、該対象クラスタとの前記距離が最も近い基準クラスタに分類する分類工程と、
を前記コンピュータが実行することを特徴とする特徴ベクトル生成方法。
【請求項５】
請求項４に記載の特徴ベクトル生成方法をコンピュータに実行させるためのプログラム。
【請求項１】
画像内から抽出した複数の部分画像を複数の基準クラスタの何れかに分類して、各基準クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成装置において、
前記抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングするクラスタリング手段と、
前記クラスタリングによって形成されたクラスタを対象クラスタとして、該対象クラスタと前記各基準クラスタとの間の距離を算出する距離算出手段と、
前記対象クラスタに属する部分画像を、該対象クラスタとの前記距離が最も近い基準クラスタに分類する分類手段と、
を備えることを特徴とする特徴ベクトル生成装置。
【請求項２】
前記分類手段は、
前記個々の部分画像と、前記画像内から抽出した部分画像の分類が行われた基準クラスタとの間の距離を算出し、この距離が最も近い基準クラスタに分類先を変更する
ことを特徴とする請求項１に記載の特徴ベクトル生成装置。
【請求項３】
前記分類が行われた基準クラスタと、該基準クラスタに分類された前記部分画像との間の距離を算出するクラスタ距離算出手段を更に備え、
前記分類手段は、
前記クラスタ距離算出手段により算出された距離が所定値以上の部分画像を選定し、その選定した部分画像と該部分画像の分類が行われた基準クラスタとの間の距離を算出して、分類先の変更を行う
ことを特徴とする請求項２に記載の特徴ベクトル生成装置。
【請求項４】
コンピュータが、画像内から抽出した複数の部分画像を複数の基準クラスタの何れかに分類して、各基準クラスタへの分類数に基づく特徴ベクトルを生成する特徴ベクトル生成方法において、
前記抽出された複数の部分画像を、該部分画像の特徴量に基づいてクラスタリングするクラスタリング工程と、
前記クラスタリングによって形成されたクラスタを対象クラスタとして、該対象クラスタと前記各基準クラスタとの間の距離を算出する距離算出工程と、
前記対象クラスタに属する部分画像を、該対象クラスタとの前記距離が最も近い基準クラスタに分類する分類工程と、
を前記コンピュータが実行することを特徴とする特徴ベクトル生成方法。
【請求項５】
請求項４に記載の特徴ベクトル生成方法をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−７９１８７（Ｐ２０１２−７９１８７Ａ）
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願番号】特願２０１０−２２５３０４（Ｐ２０１０−２２５３０４）
【出願日】平成２２年１０月５日（２０１０．１０．５）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願日】平成２２年１０月５日（２０１０．１０．５）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
[ Back to top ]