(57)【要約】【課題】より高精度にインスタンスを示す画像を検索する。【解決手段】特徴集約集計部１２が、インスタンス画像から抽出された局所特徴を集約した集約特徴ＤＢ２１、及び各インスタンス画像群における各集約特徴の出現回数を示すインスタンス特徴ＤＢ２２を作成し、各フレーム画像から局所特徴を抽出し、特徴照合集計部１５が、フレーム画像から抽出された各局所特徴と集約特徴ＤＢ２１内の各集約特徴との照合結果に基づいて、映像毎のフレーム画像特徴ＤＢ２３、映像特徴ＤＢ２４を作成し、逆フレーム画像頻度計算部１６が、各集約特徴のＩＦＦを示す逆フレーム画像頻度ＤＢ２５を作成し、検索ランキング部１７が、インスタンス特徴ＤＢ２２、逆フレーム画像頻度ＤＢ２５、映像特徴ＤＢ２４を参照し、ＢＭ２５にインスタンス特徴ＤＢ２２とＩＦＦとをさらに考慮したＥＢＭ２５を求め、ＥＢＭ２５に基づく検索結果を作成する。【選択図】図１
2014099110.tif 000002
【特許請求の範囲】
【請求項１】
クエリとなるインスタンスを示すインスタンス画像、及び検索対象となる複数のフレーム画像からなる画像群の各フレーム画像から複数の特徴を抽出する特徴抽出手段と、
前記特徴抽出手段により複数のインスタンスの各々を示す複数のインスタンス画像の各々から抽出された複数の特徴から、重複する特徴を集約した集約特徴の各々の前記複数のインスタンス画像における前記インスタンス毎の第１出現頻度を集計する特徴集約集計手段と、
前記集約特徴の各々と前記フレーム画像から抽出された複数の特徴とを照合し、前記集約特徴の各々について、前記各フレーム画像における第２出現頻度、及び前記画像群における第３出現頻度を集計する特徴照合集計手段と、
前記集約特徴の各々について、前記第２出現頻度に基づいて、前記画像群における該集約特徴の出現頻度が低いほど高くなる逆フレーム画像頻度を計算する逆フレーム画像頻度計算手段と、
前記集約特徴の各々の前記逆フレーム画像頻度、前記第１出現頻度、及び第３出現頻度、並びに前記画像群に含まれる集約特徴の数に関する画像群長に基づいて定まる各集約特徴の重要度の和で表される検索対象のインスタンスに対する各画像群の評価値を求め、前記評価値に基づく検索結果を作成する検索結果作成手段と、
を含む画像検索装置。
【請求項２】
前記特徴集約集計手段は、検索対象として新たに追加されたインスタンスを示すインスタンス画像から抽出された特徴のうち、前記集約特徴に含まれない追加特徴に基づいて、前記第１出現頻度の集計結果を更新し、
前記特徴照合集計手段は、前記追加特徴と前記フレーム画像から抽出された複数の特徴とを照合し、前記第２出現頻度及び前記第３出現頻度を更新し、
前記逆フレーム画像頻度計算手段は、更新された前記第２出現頻度に基づいて、前記逆フレーム画像頻度を再計算し、
前記検索結果作成手段は、再計算された逆フレーム画像頻度、更新された前記第１出現頻度、及び更新された前記第３出現頻度に基づいて、前記新たに追加されたインスタンスに対する検索結果を作成する
請求項１記載の画像検索装置。
【請求項３】
前記検索結果作成手段は、前記検索結果に前記画像群のファイル名、または前記画像群のファイル名と該画像群の評価値とを含める請求項１または請求項２記載の画像検索装置。
【請求項４】
特徴抽出手段と、特徴集約集計手段と、特徴照合集計手段と、逆フレーム画像頻度計算手段と、検索結果作成手段とを含む画像検索装置における画像検索方法であって、
前記特徴抽出手段が、クエリとなるインスタンスを示すインスタンス画像、及び検索対象となる複数のフレーム画像からなる画像群の各フレーム画像から複数の特徴を抽出し、
前記特徴抽出手段により複数のインスタンスの各々を示す複数のインスタンス画像の各々から抽出された複数の特徴から、重複する特徴を集約した集約特徴の各々の前記複数のインスタンス画像における前記インスタンス毎の第１出現頻度を集計し、
前記特徴照合集計手段が、前記集約特徴の各々と前記フレーム画像から抽出された複数の特徴とを照合し、前記集約特徴の各々について、前記各フレーム画像における第２出現頻度、及び前記画像群における第３出現頻度を集計し、
前記逆フレーム画像頻度計算手段が、前記集約特徴の各々について、前記第２出現頻度に基づいて、前記画像群における該集約特徴の出現頻度が低いほど高くなる逆フレーム画像頻度を計算し、
前記検索結果作成手段が、前記集約特徴の各々の前記逆フレーム画像頻度、前記第１出現頻度、及び第３出現頻度、並びに前記画像群に含まれる集約特徴の数に関する画像群長に基づいて定まる各集約特徴の重要度の和で表される検索対象のインスタンスに対する各画像群の評価値を求め、前記評価値に基づく検索結果を作成する
画像検索方法。
【請求項５】
コンピュータを、請求項１〜請求項３のいずれか１項記載の画像検索装置を構成する各手段として機能させるための画像検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像検索装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来、特定の人、物、場所等であるイスタンスを示す画像をクエリとして、大規模画像データベースからインスタンスを含む画像を検索することが行われている。例えば、インスタンスを示す画像群と映像フレーム画像群との間の局所特徴量の出現パターンの類似性に基づいて、インスタンスを含む映像を検索する技術、つまりクエリ画像群と映像との類似尺度を使用した映像検索技術が提案されている（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Cai-Zhi Zhu et al., "Large Vocabulary Quantization for Searching Instances from Videos.", In Proc. of ICMR'12, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、従来技術とは異なるアプローチにより、より高精度にインスタンスを示す画像を検索することができる画像検索装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
上記目的を達成するために、本発明の画像検索装置は、クエリとなるインスタンスを示すインスタンス画像、及び検索対象となる複数のフレーム画像からなる画像群の各フレーム画像から複数の特徴を抽出する特徴抽出手段と、前記特徴抽出手段により複数のインスタンスの各々を示す複数のインスタンス画像の各々から抽出された複数の特徴から、重複する特徴を集約した集約特徴の各々の前記複数のインスタンス画像における前記インスタンス毎の第１出現頻度を集計する特徴集約集計手段と、前記集約特徴の各々と前記フレーム画像から抽出された複数の特徴とを照合し、前記集約特徴の各々について、前記各フレーム画像における第２出現頻度、及び前記画像群における第３出現頻度を集計する特徴照合集計手段と、前記集約特徴の各々について、前記第２出現頻度に基づいて、前記画像群における該集約特徴の出現頻度が低いほど高くなる逆フレーム画像頻度を計算する逆フレーム画像頻度計算手段と、前記集約特徴の各々の前記逆フレーム画像頻度、前記第１出現頻度、及び第３出現頻度、並びに前記画像群に含まれる集約特徴の数に関する画像群長に基づいて定まる各集約特徴の重要度の和で表される検索対象のインスタンスに対する各画像群の評価値を求め、前記評価値に基づく検索結果を作成する検索結果作成手段と、を含んで構成されている。
【０００６】
本発明の画像検索装置によれば、特徴抽出手段が、クエリとなるインスタンスを示すインスタンス画像から複数の特徴を抽出する。ここでは、複数のインスタンスの各々を示す複数のインスタンス画像の各々から複数の特徴を抽出する。そして、特徴集約集計手段が、特徴抽出手段により複数のインスタンス画像から抽出された複数の特徴のうち、重複する特徴を集約した集約特徴の各々の前記複数のインスタンス画像における前記インスタンス毎の第１出現頻度を集計する。
【０００７】
また、特徴抽出手段が、検索対象となる複数のフレーム画像からなる画像群の各フレーム画像から複数の特徴を抽出する。そして、特徴照合集計手段が、集約特徴の各々とフレーム画像から抽出された複数の特徴とを照合し、集約特徴の各々について、各フレーム画像における第２出現頻度、及び画像群における第３出現頻度を集計する。さらに、逆フレーム画像頻度計算手段が、集約特徴の各々について、第２出現頻度に基づいて、画像群における集約特徴の出現頻度が低いほど高くなる逆フレーム画像頻度を計算する。
【０００８】
そして、検索結果作成手段が、集約特徴の各々の逆フレーム画像頻度、第１出現頻度、及び第３出現頻度、並びに画像群に含まれる集約特徴の数に関する画像群長に基づいて定まる各集約特徴の重要度の和で表される検索対象のインスタンスに対する各画像群の評価値を求め、評価値に基づく検索結果を作成する。
【０００９】
このように、インスタンス画像から抽出され集約された集約特徴のインスタンス画像における出現頻度を、各集約特徴の重要度として考慮した評価値に基づいて検索結果を作成するため、より高精度にインスタンスを示す画像を検索することができる。
【００１０】
また、前記特徴集約集計手段は、検索対象として新たに追加されたインスタンスを示すインスタンス画像から抽出された特徴のうち、前記集約特徴に含まれない追加特徴に基づいて、前記第１出現頻度の集計結果を更新し、前記特徴照合集計手段は、前記追加特徴と前記フレーム画像から抽出された複数の特徴とを照合し、前記第２出現頻度及び前記第３出現頻度を更新し、前記逆フレーム画像頻度計算手段は、更新された前記第２出現頻度に基づいて、前記逆フレーム画像頻度を再計算し、前記検索結果作成手段は、再計算された逆フレーム画像頻度、更新された前記第１出現頻度、及び更新された前記第３出現頻度に基づいて、前記新たに追加されたインスタンスに対する検索結果を作成することができる。これにより、追加分の処理を行うだけで、追加されたインスタンスについても高精度にインスタンスを示す画像を検索することができる。
【００１１】
また、前記検索結果作成手段は、前記検索結果に前記画像群のファイル名、または前記画像群のファイル名と該画像群の評価値とを含めることができる。検索結果は評価値に基づいて作成されればよく、様々な形態の検索結果を作成可能である。
【００１２】
また、本発明の画像検索方法は、特徴抽出手段と、特徴集約集計手段と、特徴照合集計手段と、逆フレーム画像頻度計算手段と、検索結果作成手段とを含む画像検索装置における画像検索方法であって、前記特徴抽出手段が、クエリとなるインスタンスを示すインスタンス画像、及び検索対象となる複数のフレーム画像からなる画像群の各フレーム画像から複数の特徴を抽出し、前記特徴抽出手段により複数のインスタンスの各々を示す複数のインスタンス画像の各々から抽出された複数の特徴から、重複する特徴を集約した集約特徴の各々の前記複数のインスタンス画像における前記インスタンス毎の第１出現頻度を集計し、前記特徴照合集計手段が、前記集約特徴の各々と前記フレーム画像から抽出された複数の特徴とを照合し、前記集約特徴の各々について、前記各フレーム画像における第２出現頻度、及び前記画像群における第３出現頻度を集計し、前記逆フレーム画像頻度計算手段が、前記集約特徴の各々について、前記第２出現頻度に基づいて、前記画像群における該集約特徴の出現頻度が低いほど高くなる逆フレーム画像頻度を計算し、前記検索結果作成手段が、前記集約特徴の各々の前記逆フレーム画像頻度、前記第１出現頻度、及び第３出現頻度、並びに前記画像群に含まれる集約特徴の数に関する画像群長に基づいて定まる各集約特徴の重要度の和で表される検索対象のインスタンスに対する各画像群の評価値を求め、前記評価値に基づく検索結果を作成する方法である。
【００１３】
また、本発明の画像検索プログラムは、コンピュータを、上記の画像検索装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００１４】
以上説明したように、本発明の画像検索装置、方法、及びプログラムによれば、インスタンス画像から抽出され集約された集約特徴のインスタンス画像における出現頻度を、各集約特徴の重要度として考慮した評価値に基づいて検索結果を作成するため、より高精度にインスタンスを示す画像を検索することができる、という効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】第１の実施の形態に係る映像検索装置の構成を示す概略図である。
【図２】インスタンス画像のデータ構造の一例を示す図である。
【図３】局所特徴のデータ構造の一例を示す図である。
【図４】集約特徴ＤＢのデータ構造の一例を示す図である。
【図５】インスタンス特徴ＤＢのデータ構造の一例を示す図である。
【図６】フレーム画像特徴ＤＢのデータ構造の一例を示す図である。
【図７】映像特徴ＤＢのデータ構造の一例を示す図である。
【図８】逆フレーム画像頻度ＤＢのデータ構造の一例を示す図である。
【図９】検索結果のデータ構造の一例を示す図である。
【図１０】第１の実施の形態における映像検索処理ルーチンの内容を示すフローチャートである。
【図１１】第２の実施の形態に係る映像検索装置の構成を示す概略図である。
【図１２】追加特徴ＤＢのデータ構造の一例を示す図である。
【図１３】更新された集約特徴ＤＢのデータ構造の一例を示す図である。
【図１４】更新されたインスタンス特徴ＤＢのデータ構造の一例を示す図である。
【図１５】評価結果を示す図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１７】
＜各実施の形態の概要＞
各実施の形態では、インスタンス（実例）を示す画像（以下、「インスタンス画像」という）を入力とし、大規模映像データベースからインスタンスを含む映像を検索し、検索結果を出力する映像検索装置に本発明の画像検索装置を適用した場合について説明する。各実施の形態に係る映像検索装置は、インスタンス画像群の局所特徴の重要度の指標である逆フレーム画像頻度、インスタンス画像群及び映像群における局所特徴の出現頻度、並びに各映像に含まれる局所特徴の総数である映像長に注目することで、インスタンスを含む映像の検索（以下、「インスタンス検索」ともいう）を高精度に行うインスタンス検索システムを実現するものである。
【００１８】
各実施の形態では、Ｗｅｂページのキーワード検索でよく用いられるＢＭ２５（Best Match 25）と呼ばれるランキング手法を、インスタンス検索に応用する。ＢＭ２５を応用する際、ＢＭ２５におけるキーワードの重要度を示す指標であるＩＤＦ（Inverse Document Frequency）をインスタンスに関する局所特徴の重要度とみなし、重要度が高い局所特徴を多く含む映像を検索するための指標とする。また、インスタンス検索におけるクエリは、１つ以上のインスタンス画像から得られた局所特徴量分の大きなベクトルとして表現されるため、クエリとして小さいベクトルを想定したＢＭ２５を、キーワードに基づく文書検索から映像検索に適合した形に拡張し、拡張したＢＭ２５（各実施の形態では「ＥＢＭ２５」と呼ぶ）をインスタンス検索に適用する。
【００１９】
＜第１の実施の形態＞
第１の実施の形態に係る映像検索装置１０は、ＣＰＵと、ＲＡＭと、後述する映像検索処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成されている。このコンピュータは、機能的には、図１に示すように、インスタンス画像特徴抽出部１１と、特徴集約集計部１２と、フレーム画像抽出部１３と、フレーム画像特徴抽出部１４と、特徴照合集計部１５と、逆フレーム画像頻度計算部１６と、検索ランキング部１７と、検索結果出力部１８とを含んだ構成で表すことができる。また、映像検索装置１０には、追加特徴データベース（ＤＢ）２１、インスタンス特徴ＤＢ２２、フレーム画像特徴ＤＢ２３、映像特徴ＤＢ２４、及び逆フレーム画像頻度ＤＢ２５を記憶する所定の記憶領域が設けられている。
【００２０】
映像検索装置１０には、インスタンス検索のクエリとして、インスタンス画像が入力される。第１の実施の形態では、インスタンス特徴ＤＢ２２を作成するため、複数のインスタンスを対象とし、インスタンスのそれぞれについて、複数のインスタンス画像からなるインスタンス画像群が入力される。例えば、インスタンスの数がｑ個で、各インスタンスについてｈ枚のインスタンス画像が用意されている場合には、ｑ個のインスタンス画像群、総数ｑ×ｈ枚のインスタンス画像が入力されることとなる。ただし、入力されるインスタンス画像は、１つのインスタンスについて１枚以上であればよい。また、インスタンスを示す映像を入力とし、その映像の各フレームをインスタンス画像群として入力してもよい。なお、１つのインスタンスに対するインスタンス画像群に含まれるインスタンス画像の数が多いほど、インスタンス検索の検索精度が向上する。
【００２１】
図２に、インスタンス画像のデータ構造の一例を示す。図２は、インスタンス画像がｎ×ｍ画素で構成され、各画素の画素値としてＲＧＢ値を有する場合の例であり、画素毎の位置（ｘｎ，ｙｍ）とＲＧＢ値（ｒｎｍ，ｇｎｍ，ｂｎｍ）とが対応付けられたデータ構造となっている。
【００２２】
インスタンス画像特徴抽出部１１は、映像検索装置１０に入力されたインスタンス画像群を受け付け、各インスタンス画像から特徴点を検出し、検出した特徴点の特徴量を記述した特徴ベクトルを局所特徴として抽出する。インスタンス画像特徴抽出部１１は、例えば、インスタンス画像において輝度値の変化が激しい箇所をHarris-Laplace法（「C. Harris et al., “A combined corner and edge detector.”, 4th Alvey Vision Conf., 1988.」参照）により特徴点として検出する。そして、検出した各特徴点の特徴量をCompact Color SIFT（「K. Mikolajczyk et al., “Scale and affine invariant interest point detectors.”, IJCV, 2004.」参照）により記述する。Compact Color SIFTは輝度に関する１２８次元のＳＩＦＴ特徴量に色度を表す６４次元のベクトルを追加した局所特徴量である。
【００２３】
図３に局所特徴のデータ構造の一例を示す。図３は、上記のCompact Color SIFTを用いた例であり、抽出された各局所特徴の識別番号（特徴１，特徴２，・・・，特徴ｉ）と１９２次元のCompact Color SIFT特徴量（特徴ベクトル）とが対応付けられたデータ構造となっている。
【００２４】
特徴集約集計部１２は、インスタンス画像特徴抽出部１１で抽出された局所特徴のうち、重複している局所特徴を一つに集約する。「重複している局所特徴」とは、インスタンス画像群として映像の各フレームを用いた場合などのように、ほぼ同一のインスタンス画像から同一の局所特徴が抽出された場合に、その同一の局所特徴を「重複」とみなすものである。特徴集約集計部１２は、集約した局所特徴を集約特徴とした集約特徴ＤＢ２１を作成し、所定の記憶領域に記憶する。図４に、集約特徴ＤＢ２１のデータ構造の一例を示す。図４の例では、各集約特徴の識別番号（特徴１，特徴２，・・・，特徴ｊ）と１９２次元のCompact Color SIFT特徴量（特徴ベクトル）とが対応付けられたデータ構造となっている。このデータ構造は、インスタンス画像特徴抽出部１１により抽出された局所特徴（例えば、図３）のデータ構造と同様であるが、特徴集約集計部１２により局所特徴の数がｉからｊに集約されたことを示している。
【００２５】
また、特徴集約集計部１２は、集約特徴に基づいて、各インスタンスを示すインスタンス画像群における各集約特徴の出現回数を、インスタンスの特徴としてインスタンス毎に抽出し、インスタンス特徴ＤＢ２２として作成し、所定の記憶領域に記憶する。図５に、インスタンス特徴ＤＢ２２のデータ構造の一例を示す。図５は、インスタンスの数がｑ個、集約特徴の総数がｊ個の例であり、各インスタンスの識別番号（インスタンス１，・・・，イスタンスｑ）と、各集約特徴の出現回数ｋｆ（keypoint frequency）とが対応付けられたデータ構造となっている。
【００２６】
なお、特徴集約集計部１２は、集約された局所特徴をクラスタリングして次元数を下げることにより、さらに集約してもよい。
【００２７】
フレーム画像抽出部１３は、映像検索装置１０に入力された映像群を受け付け、例えば１ｆｐｓ（１秒間に１フレーム）のレートで各映像からフレーム画像を抽出する。フレーム画像のデータ構造は、インスタンス画像のデータ構造（例えば、図２）と同様であるため、詳細な説明は省略する。
【００２８】
フレーム画像特徴抽出部１４は、局所特徴を抽出する対象がインスタンス画像ではなくフレーム画像抽出部１３で抽出されたフレーム画像であるという点が、インスタンス画像特徴抽出部１１と異なるだけであり、また、抽出される局所特徴のデータ構造も、インスタンス画像特徴抽出部１１で抽出される局所特徴のデータ構造（例えば、図３）と同様であるため、詳細な説明は省略する。
【００２９】
特徴照合集計部１５は、フレーム画像特徴抽出部１４で抽出された各局所特徴と、集約特徴ＤＢ２１に記憶されている各集約特徴との照合を行う。上記のCompact Color SIFTの場合、例えば、１９２次元の特徴ベクトル間のコサイン類似度（０〜１の範囲の値を取り、同一の特徴ベクトルの場合は１）を用いて、コサイン類似度が所定値以上（例えば、０．９５）の局所特徴と集約特徴とを一致する特徴と判定する。フレーム画像から抽出された局所特徴に対して、コサイン類似度が所定値以上となる集約特徴が集約特徴ＤＢ２１に複数存在する場合には、コサイン類似度が最も大きい集約特徴同士を疎の局所特徴に一致する集約特徴と判定する。
【００３０】
なお、局所特徴間の照合は、コサイン類似度を用いる場合に限定されず、各特徴ベクトル間の距離や類似度を測る尺度であれば、どのようなものを用いてもよい。
【００３１】
また、特徴集約集計部１２によりクラスタリングにより局所特徴が集約されている場合には、特徴照合集計部１５は、集約特徴ＤＢ２１における各クラスタの重心を用いて、フレーム画像から抽出された局所特徴との照合を行うことができる。
【００３２】
特徴照合集計部１５は、フレーム画像から抽出された局所特徴と集約特徴ＤＢ２１に記憶されている集約特徴との照合結果に基づいて、フレーム画像特徴ＤＢ２３を映像毎に作成し、所定の記憶領域に記憶する。図６に、フレーム画像特徴ＤＢ２３のデータ構造の一例を示す。図６の例では、１つの映像から抽出された各フレーム画像の識別番号（フレーム画像１，・・・，フレーム画像Ｎ）と、各フレーム画像における各集約特徴の出現回数Ｋｆが対応付けられている。
【００３３】
また、特徴照合集計部１５は、フレーム画像から抽出された局所特徴と集約特徴ＤＢ２１に記憶されている局所特徴との照合結果に基づいて、映像特徴ＤＢ２４を作成し、所定の記憶領域に記憶する。図７に、映像特徴ＤＢ２４のデータ構造の一例を示す。図７の例では、映像の識別番号（映像１，・・・，映像ｖ）と、各映像における各集約特徴の出現回数ＫＦが対応付けられている。出現回数ＫＦは、映像毎に作成されたフレーム画像特徴ＤＢ２３の集約特徴毎の出現回数をフレーム画像１からフレーム画像Ｎまで合計して求めることができる。
【００３４】
逆フレーム画像頻度計算部１６は、映像毎のフレーム画像特徴ＤＢ２３を参照し、集約特徴ｊの逆フレーム画像頻度ＩＦＦｊ（Inverse Frame Frequency）を、下記（１）式に基づいて計算する。
【００３５】
【数１】
2014099110.tif 000003
【００３６】
ここで、Ｎは１つの映像内の全フレーム画像数、ｎｊは１つの映像内における集約特徴ｊを含むフレーム画像数であり、フレーム画像特徴ＤＢ２３において、集約特徴ｊの出現回数Ｋｆｊが１以上となっているフレーム画像をカウントすることにより求めることができる。集約特徴ｊがフレーム画像特徴ＤＢ２３において高い頻度で出現している場合には、集約特徴ｊはインスタンスに対する識別能力が低い局所特徴であるとみなせるため、ＩＦＦｊは小さくなる。逆に、集約特徴ｊのフレーム画像特徴ＤＢ２３における出現頻度が低い場合には、集約特徴ｊはインスタンスに対する識別能力が高い集約特徴であるとみなせるため、ＩＦＦｊは大きくなる。
【００３７】
逆フレーム画像頻度計算部１６は、集約特徴ＤＢ２１に記憶されている集約特徴（特徴１，・・・，特徴ｊ）の全てについてＩＦＦｊを計算し、計算結果を逆フレーム画像頻度ＤＢ２５として作成し、所定の記憶領域に記憶する。図８に、逆フレーム画像頻度ＤＢ２５のデータ構造の一例を示す。図８の例では、集約特徴の識別番号（特徴１，・・・，特徴ｊ）と、計算されたとＩＦＦｊとが対応付けられている。逆フレーム画像頻度ＤＢ２５は映像毎に作成される。
【００３８】
検索ランキング部１７は、各インスタンスに対してそのインスタンスが含まれている可能性のある映像候補を、入力された映像群の中から検索し、映像候補をランキングする。具体的には、まず、検索ランキング部１７は、インスタンス特徴ＤＢ２２からインスタンスｑのインスタンス特徴である各集約特徴の出現回数ｋｆ１，・・・，ｋｆｊを取得する。また、検索ランキング部１７は、映像ｖの逆フレーム画像頻度ＤＢ２５から各集約特徴の逆フレーム画像頻度ＩＦＦ１，・・・，ＩＦＦｊを取得する。さらに、検索ランキング部１７は、映像特徴ＤＢ２４から映像ｖに対応付けられた各集約特徴の出現回数ＫＦ１，・・・，ＫＦｊを取得する。そして、検索ランキング部１７は、下記（２）式に示すインスタンスｑに対する映像ｖの評価値ＥＢＭ２５（ｑ，ｖ）を計算する。
【００３９】
【数２】
2014099110.tif 000004
【００４０】
ここで、ｋ１、ｋ２、及びｂ１は設定パラメータで、例えば、ｋ１＝ｋ２＝１．２、ｂ１＝０．７５とすることができる。またｖｌは映像長（video length）、ａｖｖｌは平均映像長（average video length）を意味し、ｖｌは映像ｖに対応付けられた各集約特徴の出現回数ＫＦの和、ａｖｖｌは映像特徴ＤＢ２４内における各映像のｖｌの平均である。また、Σｑｊはインスタンスｑの集約特徴１，・・・，ｊに関する和を意味する。（２）式に示した評価値ＥＢＭ２５は、下記（３）式に示すＢＭ２５（「S. E. Robertson et al., “Some Simple Effective Approximations to the 2-Poisson Model for Probabilistic Weighted Retrieval.”, In Proc. of SIGIR'04, 1994.」参照）に、各集約特徴の重要度として、インスタンス特徴ＤＢ２２における集約特徴の出現頻度の項（（ｋ２＋１）ｋｆｊ）／（ｋ２＋ｋｆｊ）と、逆フレーム画像頻度ＩＦＦｊとをさらに考慮したものである。
【００４１】
【数３】
2014099110.tif 000005
【００４２】
ＢＭ２５及びＥＢＭ２５は共に、インスタンスに対して重要度が高い集約特徴を多く含み、かつ映像長が大き過ぎない映像に対してハイスコアを与える。しかし、ＢＭ２５では、フレーム画像特徴ＤＢ２３内での集約特徴の出現頻度のみで、各集約特徴の重要度が定義されたが、ＥＢＭ２５では、インスタンス特徴ＤＢ２２における集約特徴の出現頻度もさらに考慮されている。ＥＢＭ２５は、テキスト検索分野でキーワードによる検索ではなくドキュメントをクエリとした検索を行う際のＢＭ２５の拡張に相当する。
【００４３】
検索ランキング部１７は、インスタンスｑに対する各映像（映像１，・・・，映像ｖ）の評価値ＥＢＭ２５をそれぞれ計算し、評価値ＥＢＭ２５の降順で映像をランキングした検索結果を作成する。検索結果は、インスタンスの各々（インスタンス１，・・・，インスタンスｑ）について作成する。図９に、検索結果のデータ構造の一例を示す。図９では、各インスタンスの識別番号（インスタンス１，・・・，インスタンスｑ）と、評価値ＥＢＭ２５の降順で並べられた映像とが対応付けられている。
【００４４】
なお、検索結果は、上記のようにランキング形式にする場合に限定されず、評価値が最大となる映像のみを検索結果としてもよいし、評価値が所定値以上となる映像をランダムに並べた検索結果としてもよい。また、検索結果を、映像のファイル名としてもよいし、映像のファイル名とＥＢＭ２５の値としてもよい。検索結果は、ＥＢＭ２５の値に基づくものであれば、様々な形態をとることが可能である。
【００４５】
検索結果出力部１８は、検索ランキング部１７で作成された検索結果を出力する。
【００４６】
次に、第１の実施の形態に係る映像検索装置１０の作用について説明する。映像検索装置１０に、複数のインスタンスを示す複数のインスタンス画像群が入力されると、映像検索装置１０において、図１０に示す映像検索処理ルーチンが実行される。
【００４７】
ステップ１００で、インスタンス画像特徴抽出部１１が、映像検索装置１０に入力されたインスタンス画像群を受け付け、各インスタンス画像から特徴点を検出し、検出した特徴点の特徴量を記述した特徴ベクトルを局所特徴として抽出する。
【００４８】
次に、ステップ１０２で、特徴集約集計部１２が、上記ステップ１００で抽出された局所特徴から、重複している局所特徴を一つに集約し、集約した局所特徴を集約特徴とした集約特徴ＤＢ２１を作成し、所定の記憶領域に記憶する。また、特徴集約集計部１２が、集約特徴に基づいて、各インスタンスの特徴として、各インスタンス画像群における各集約特徴の出現回数を示すインスタンス特徴ＤＢ２２を作成し、所定の記憶領域に記憶する。
【００４９】
次に、ステップ１０４で、フレーム画像抽出部１３が、映像検索装置１０に入力された映像群を受け付け、各映像からフレーム画像を抽出する。次に、ステップ１０６で、フレーム画像特徴抽出部１４が、上記ステップ１０４で抽出された各フレーム画像から局所特徴を抽出する。
【００５０】
次に、ステップ１０８で、特徴照合集計部１５が、上記ステップ１０６でフレーム画像から抽出された各局所特徴と、上記ステップ１０２で記憶された集約特徴ＤＢ２１内の各集約特徴とを、特徴ベクトル間の類似度に基づいて照合する。そして、特徴照合集計部１５が、照合結果に基づいて、各フレーム画像における各集約特徴の出現頻度Ｋｆを示すフレーム画像特徴ＤＢ２３を映像毎に作成し、所定の記憶領域に記憶する。また、特徴照合集計部１５が、照合結果に基づいて、各映像における各集約特徴の出現回数ＫＦを示す映像特徴ＤＢ２４を作成し、所定の記憶領域に記憶する。
【００５１】
次に、ステップ１１０で、逆フレーム画像頻度計算部１６が、フレーム画像特徴ＤＢ２３を参照し、集約特徴ｊの逆フレーム画像頻度ＩＦＦｊを、集約特徴ＤＢ２１に記憶されている集約特徴（特徴１，・・・，特徴ｊ）の全てについて計算し、各集約特徴のＩＦＦを示す逆フレーム画像頻度ＤＢ２５を作成し、所定の記憶領域に記憶する。逆フレーム画像頻度ＤＢ２５は映像毎に作成する。
【００５２】
次に、ステップ１１２で、検索ランキング部１７が、インスタンス特徴ＤＢ２２からインスタンスｑのインスタンス特徴である各集約特徴の出現回数ｋｆ１，・・・，ｋｆｊを取得し、各映像の逆フレーム画像頻度ＤＢ２５から各集約特徴の逆フレーム画像頻度ＩＦＦ１，・・・，ＩＦＦｊを取得し、映像特徴ＤＢ２４から各映像に対応付けられた各集約特徴の出現回数ＫＦ１，・・・，ＫＦｊを取得する。そして、検索ランキング部１７が、インスタンスｑに対する各映像の評価値ＥＢＭ２５を計算し、評価値ＥＢＭ２５の降順で映像をランキングした検索結果を作成する。検索結果は、各インスタンスについて作成する。
【００５３】
次に、ステップ１１４で、検索結果出力部１８が、上記ステップ１１２で作成された検索結果を出力して、映像検索処理ルーチンを終了する。
【００５４】
以上説明したように、第１の実施の形態に係る映像検索装置によれば、インスタンス画像群における出現頻度と、逆フレーム画像頻度とを集約特徴の重要度としてさらに考慮したＥＢＭ２５を評価値として用いることにより、より高精度にインスタンスを示す画像を検索することができる。
【００５５】
＜第２の実施の形態＞
第２の実施の形態では、既にインスタンス特徴ＤＢ２２に所定数のデータが蓄積されている状態で、新しく追加されたインスタンス画像をクエリとして映像を検索する場合について説明する。なお、第２の実施の形態に係る映像検索装置について、第１の実施の形態に係る映像検索装置１０と同一の構成については、同一符号を付して詳細な説明を省略する。
【００５６】
第２の実施の形態に係る映像検索装置２１０は、ＣＰＵと、ＲＡＭと、後述する映像検索処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成されている。このコンピュータは、機能的には、図１１に示すように、インスタンス画像特徴抽出部１１と、特徴集約集計部２１２と、フレーム画像抽出部１３と、フレーム画像特徴抽出部１４と、特徴照合集計部２１５と、逆フレーム画像頻度計算部１６と、検索ランキング部１７と、検索結果出力部１８とを含んだ構成で表すことができる。また、映像検索装置１０には、集約特徴ＤＢ２１、インスタンス特徴ＤＢ２２、フレーム画像特徴ＤＢ２３、映像特徴ＤＢ２４、逆フレーム画像頻度ＤＢ２５、及び追加特徴ＤＢ２６を記憶する所定の記憶領域が設けられている。
【００５７】
特徴集約集計部２１２は、インスタンス画像特徴抽出部１１で抽出された新しいインスタンス画像の局所特徴を受け取り、集約特徴ＤＢ２１を参照して、重複している局所特徴を排除し、新たに追加された追加特徴を抽出する。ここでは、インスタンスｑ＋１を示すインスタンス画像群が新たに入力され、追加特徴ｊ＋１が追加された場合について説明する。特徴集約集計部２１２は、追加特徴ｊ＋１を、集約特徴ＤＢ２１と同じデータ構造の追加特徴ＤＢ２６に記憶すると共に、集約特徴ＤＢ２１を追加特徴ｊ＋１の追加分だけ更新する。図１２に、追加特徴ＤＢ２６の一例を、図１３に、更新された集約特徴ＤＢ２１の一例を示す。
【００５８】
また、特徴集約集計部２１２は、追加されたインスタンスｑ＋１及び追加特徴ｊ＋１により、インスタンス特徴ＤＢ２２を更新する。図１４に、更新されたインスタンス特徴ＤＢ２２の一例を示す。図１４の例では、更新前のインスタンス特徴ＤＢ２２（図５）に、追加特徴ｊ＋１の列及びインスタンスｑ＋１の行が追加されている。なお、追加特徴ｊ＋１は新たに追加された集約特徴であるため、インスタンス１，・・・，インスタンスｑについての出現回数ｋｆｊ＋１は０である。
【００５９】
特徴照合集計部２１５は、フレーム画像から抽出された局所特徴と追加特徴ＤＢ２６に記憶されている追加特徴との照合結果に基づいて、フレーム画像特徴ＤＢ２３及び映像特徴ＤＢ２４を更新する。局所特徴と追加特徴との照合方法は、第１の実施の形態の特徴照合集計部１５における局所特徴と集約特徴との照合方法と同様である。フレーム画像特徴ＤＢ２３の更新では、各フレーム画像における追加特徴ｊ＋１の出現回数Ｋｆｊ＋１をカウントし、追加特徴ｊ＋１の列をフレーム画像特徴ＤＢ２３に追加する。また、映像特徴ＤＢ２４の更新では、更新された映像毎のフレーム画像特徴ＤＢ２３の追加特徴ｊ＋１の出現回数Ｋｆｊ＋１をフレーム画像１からフレーム画像Ｎまで合計して、映像毎の追加特徴ｊ＋１の出現回数ＫＦｊ＋１を求めて、追加特徴ｊ＋１の列を映像特徴ＤＢ２４に追加する。
【００６０】
次に、第２の実施の形態に係る映像検索装置２１０の作用について、第１の実施の形態と異なる点について説明する。
【００６１】
図１０の映像検索処理ルーチンのステップ１０２では、特徴集約集計部２１２が、ステップ１００で抽出された新しいインスタンス画像の局所特徴から、集約特徴ＤＢ２１を参照して追加特徴を抽出し、追加特徴ＤＢ２６に記憶すると共に、集約特徴ＤＢ２１を新たな追加特徴の追加分だけ更新する。また、特徴集約集計部２１２が、新たなインスタンス及び追加特徴の追加分だけ、インスタンス特徴ＤＢ２２を更新する。
【００６２】
ステップ１０８では、特徴照合集計部２１５が、ステップ１０６で抽出された局所特徴と、上記ステップ１０２で追加特徴ＤＢ２６に記憶された追加特徴との照合結果に基づいて、追加特徴の追加分だけ、フレーム画像特徴ＤＢ２３及び映像特徴ＤＢ２４を更新する。
【００６３】
後段の処理では、上記のように更新された各データベースを参照して、第１の実施の形態と同様に評価値ＥＢＭ２５を計算して、検索結果を作成すればよい。
【００６４】
以上説明したように、第２次の実施の形態に係る映像検索装置によれば、インスタンス特徴ＤＢに所定数以上のデータが蓄積されている場合には、新たに追加されたインスタンス画像について処理するだけで、第１の実施の形態と同様に、より高精度にインスタンスを示す画像を検索することができる。
【００６５】
＜評価結果＞
ここで、ＴＲＥＣＶＩＤ２０１１，２０１２のインスタンス検索タスクのデータセットを使用した検索精度の評価結果について説明する。ＴＲＥＣＶＩＤは毎年行われている映像検索分野のコンペティションで、アメリカのＮＩＳＴ（National Institute of Standards and Technology）が主催している。ＴＲＥＣＶＩＤ２０１１のインスタンス検索タスクでは２５個のインスタンスが用意され、それぞれに平均約４枚の画像が付与されている。そして約２万本の映像データベース（海外の番組映像）が検索対象になる。ＴＲＥＣＶＩＤ２０１２のインスタンス検索タスクでは２１個のインスタンスが用意され、それぞれに平均約５枚の画像が付与されている。そして約８万本の映像データベース（Ｗｅｂ上のConsumer Generated Media（ＣＧＭ））が検索対象になる。ＴＲＥＣＶＩＤ２０１１のインスタンス毎の平均正解映像数は約７３で、ＴＲＥＣＶＩＤ２０１２では約５９である。検索結果ランキングの精度はMean Average Precision（ＭＡＰ）という指標で評価した。ＭＡＰは下記（４）式で定義される。
【００６６】
【数４】
2014099110.tif 000006
【００６７】
ここで｜Ｑ｜は全インスタンス数、｜Ｒｑ｜はインスタンスｑの正解映像数、ｊは映像の検索結果ランク、ｒｅｌ（ｑ，ｊ）はランクｊの映像がｑに対して正解であれば１を、不正解であれば０を返す関数である。ｃ（ｑ，ｊ）はランク１からランクｊまでに存在した正解映像の数である。ランク１から順に正解映像が並んでいる場合、つまり最高の検索精度はＭＡＰ＝１００（％）である。
【００６８】
図１５に検索精度の評価結果を示す。ＫＦは映像中における局所特徴の出現頻度の総和のみで検索ランキングした手法、ＩＦＦは映像中における局所特徴の逆フレーム画像頻度の総和のみで検索ランキングした手法である。図１５の結果から、ＩＦＦを使用することで検索精度が大幅に改善することが分かる。そして、映像中における局所特徴の出現頻度及び映像長による正規化を考慮するＢＭ２５を使用することでランキングが改善され、さらにクエリとなるインスタンス画像における局所特徴の出現頻度及びＩＦＦをさらに考慮するＥＢＭ２５（本実施の形態の手法）の検索精度は、ＢＭ２５を上回る結果を出すことが分かる。ＭＡＰの差は危険度１％水準での検定で有意であることを確認している。
【００６９】
今後、映像メディアは録画や記録デバイス、ソーシャルネットワーキングサービス等の発達により爆発的に増加することが予想され、その様な状況に対処しうるロバストな映像検索技術が求められているが、本実施の形態の手法を使用することで、大規模映像データベースからの高精度なインスタンス検索を実現することが可能になる。
【００７０】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７１】
例えば、上記各実施の形態では、インスタンスの検索対象の画像を映像とする場合について説明したが、検索対象の画像を静止画像とした場合にも、本発明を適用可能である。この場合、例えば１００００枚の静止画像を検索対象として入力した場合、映像中の特徴点の出現回数ＫＦを静止画像中の特徴点の出現回数ＫＦ’に、映像中のＫＦの総和であるｖｌを静止画像中の特徴点の出現回数の総和であるｖｌ’に、ｖｌの平均値であるａｖｄｌをｖｌ’の平均値であるａｖｄｌ’に置き換え、上記のＥＢＭ２５を適用すればよい。ＩＦＦは１００００枚の静止画像集合の中で（１）式により計算される。
【００７２】
また、検索対象を静止画像とした場合には、検索結果として、静止画像のファイル名や、静止画像のファイル名とＥＢＭ２５の値など、ＥＢＭ２５の値に基づく様々な形態の検索結果を出力することができる。さらに、検索対象を映像及び静止画像の両方とした場合、検索結果として、映像と静止画像とが混在したものを出力してもよい。
【００７３】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００７４】
１０、２１０  映像検索装置
１１   インスタンス画像特徴抽出部
１２、２１２  特徴集約集計部
１３   フレーム画像抽出部
１４   フレーム画像特徴抽出部
１５、２１５  特徴照合集計部
１６   逆フレーム画像頻度計算部
１７   検索ランキング部
１８   検索結果出力部
２１   集約特徴ＤＢ
２２   インスタンス特徴ＤＢ
２３   フレーム画像特徴ＤＢ
２４   映像特徴ＤＢ
２５   逆フレーム画像頻度ＤＢ
２６   追加特徴ＤＢ
【図１】
2014099110.tif 000007
【図２】
2014099110.tif 000008
【図３】
2014099110.tif 000009
【図４】
2014099110.tif 000010
【図５】
2014099110.tif 000011
【図６】
2014099110.tif 000012
【図７】
2014099110.tif 000013
【図８】
2014099110.tif 000014
【図９】
2014099110.tif 000015
【図１０】
2014099110.tif 000016
【図１１】
2014099110.tif 000017
【図１２】
2014099110.tif 000018
【図１３】
2014099110.tif 000019
【図１４】
2014099110.tif 000020
【図１５】
2014099110.tif 000021