(57)【特許請求の範囲】
【請求項１】
映像を入力する入力部と、
前記入力部に入力された映像アーカイブの全映像から特徴量データベースを構築するデータベース構築部と、
前記入力部に入力されたクエリ映像に類似する前記映像アーカイブ中の映像を検索する類似映像検索部と、
前記類似映像検索部によって検索された類似映像の情報を出力する出力部とを備え、
前記データベース構築部は、前記映像アーカイブ中の各映像から第１のフレーム数ずつ間引くようにフレームを抽出し、抽出されたフレームから画像特徴量を抽出し、抽出された画像特徴量をクラスタリングして前記特徴量データベースを構築し、
前記類似映像検索部は、前記クエリ映像から第２のフレーム数ずつ間引くようにフレームを抽出し、抽出されたフレームから画像特徴量を抽出し、抽出されたクエリ映像から抽出された各々のフレームの画像特徴量と各クラスタの代表値との距離を計算し、距離の近いクラスタのＩＤを選択し、各クラスタに属する複数のフレームの画像特徴量が記憶装置の連続領域に格納された前記特徴量データベースの中から、前記選択により特定されたクラスタのＩＤに属する複数のフレームの画像特徴量を検索し、検索された画像特徴量を特徴量距離の近い順に並び替えることによりクラスタ単位で類似フレームを検索し、前記類似フレームの検索結果から連続系列を探索し一定以上の連続性が認められた区間を類似映像と判定する、
ことを特徴とする類似映像検索装置。
【請求項２】
請求項１記載の類似映像検索装置において、前記特徴量データベースは、各クラスタに属するフレームのＩＤとその画像特徴量を関連付けした第１のデータ及び前記クラスタのＩＤと当該クラスタに関連する前記第１のデータを構成する複数のフレームの画像特徴量から計算される代表値とを関連付けした第２のデータを含むことを特徴とする類似映像検索装置。
【請求項３】
請求項１又は２記載の類似映像検索装置において、一つの映像から前記第１及び第２のフレーム数ずつ間引くように抽出されたフレームに連続する整数値のＩＤが付されており、前記クエリ映像の先頭フレームの類似フレームとして検索されたフレームのＩＤを類似映像の候補として登録し、ｍ番目の後続フレームの類似フレームとして検索されたフレームのＩＤから（ｍ−１）を引いたＩＤを投票先として順次投票を行い、得票数が一定数以上となった候補を類似映像と判定することを特徴とする類似映像検索装置。
【請求項４】
請求項３記載の類似映像検索装置において、前記後続フレームに対して類似フレームとして検索されたフレームの投票先の候補が未登録の場合、当該フレームのＩＤを新たな候補として登録することを特徴とする類似映像検索装置。
【請求項５】
請求項３記載の類似映像検索装置において、前記投票先のＩＤに隣接する一定範囲内の整数値のＩＤに対して投票を行うことを特徴とする類似映像検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模な映像アーカイブから、入力映像に類似する映像の一覧を検出するための映像検索技術に関するものである。
【背景技術】
【０００２】
テレビ映像のデジタルアーカイブ化やインターネット上の動画配信サービスの普及により、大規模な映像データを高速に検索・分類する必要性が増加している。特に、膨大な映像コンテンツに対して人手でテキスト情報を付与することが困難なことから、画像特徴を用いた映像検索技術が求められている。大規模な映像アーカイブには、同一あるいは類似映像が多数含まれるため、それらを高速に、また、できる限りもれなく検出できることが望ましい。また、スローモーションや早送り映像など、再生速度の異なる映像が含まれる場合は、これらも類似映像として検出できることが望ましい。
【０００３】
画像特徴を用いた静止画像検索手法としては、画像自体の持つ色や形状などの情報を高次元ベクトル情報として抽出し、ベクトル間距離をもとに画像間の類似性を評価して検索する方法が提案されている。また、k-means法などによって特徴量データをクラスタリングして保存しておくことで、大規模画像データに対しても高速な類似検索を実現する方法が知られている。
【０００４】
一方で、画像特徴を用いた従来の類似映像検索手法としては、クエリ映像と類似映像候補のフレーム毎の特徴量比較による手法が知られている。従来法の一般的な処理手順は、（１）クエリ映像からフレームを切り出して画像特徴量を計算し、（２）クエリ映像の先頭フレーム特徴量と距離が近いフレームを特徴量データベースから探して候補とし、（３）クエリ映像の後続フレームの特徴量と候補の後続フレームの特徴量の距離を計算し、（４）一定フレーム数以上の特徴量距離の合計値が閾値以下の候補を類似映像として出力する、というものである。
【０００５】
例えば、特開２００９−２２０１８号公報では、入力映像をフレーム間の特徴量が互いに特定の範囲内の変動幅で収まる区間に分割し、区間の代表フレームから抽出した特徴量を特徴量テーブルに保存しておき、新しいフレームが入力されたとき、特徴量テーブルから類似するフレームを探し、条件を満たすものすべてを候補とする。後続フレームが入力されたとき、そのフレームの特徴量が、候補の後続フレームの特徴量と一致するかを逐次照合していき、閾値以上の長さの特徴量が一致した候補を、類似映像として出力する。
【０００６】
非特許文献１「Tiny LSH for Content-based Copied Video Detection」は、ハッシュテーブルを用いることで、特徴量テーブルからの候補選択を高速化する方法を開示している。本手法では、フレーム特徴量に対して、複数個のハッシュ関数を用いて複数のハッシュ値を計算する。ここでは、似た特徴量からは同じハッシュ値が生成されるハッシュ関数を使用する。このハッシュ値と特徴量テーブルへのポインタを組とするハッシュテーブルを作成する。新しいフレームが入力されたとき、同様にハッシュ値を計算しハッシュテーブルを探索することで、特徴量の似たフレームへのポインタを得ることができる。ハッシュ値の衝突が起きた場合はポインタが書き換えられるが、複数のハッシュ値のいずれかからのポインタが存在していれば、特徴量テーブルから類似フレームを見つけることができる。このような候補選択手法は、ハッシュテーブルを用いたアルゴリズムであるため、その計算量はデータ量に依存せず一定である。
【０００７】
また、特開２０００−３３９４７４号公報は、異なるフレームレートを持つ動画像の特徴量を比較する場合に正確な類似度を算出する方法を開示している。本手法は、クエリ映像の時間位置情報と、データベースに含まれる被検索映像区間の時間位置情報とを参照して、特徴量比較を行うフレーム位置を修正する手段を用いている。既知の動画像の再生位置情報を用いて特徴量の比較位置を決めているため、フレームレートの異なる類似映像も検知することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−２２０１８号公報
【特許文献２】特開２０００−３３９４７４号公報
【非特許文献】
【０００９】
【非特許文献１】K. Yoshida and N. Murabayashi, “Tiny LSH for Content-based Copied Video Detection,” Proc. of SAINT 2008, IEEE CS, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来手法では、先頭フレームの検索結果を候補として特徴量比較を行うため、そもそも先頭フレームの検索結果に現れない類似映像は検出することができない。先頭フレームをずらしながら、すべての候補を調べる方法が考えられるが、そのような処理には計算コストがかかる。特に、大規模な映像アーカイブの場合は、候補選択のための特徴量テーブルの探索に膨大な時間がかかる。また、類似映像が多数含まれる場合は、候補の後続フレーム特徴量の読み出しコスト、比較コストが増加する。
【００１１】
候補選択については、非特許文献１のように、ハッシュテーブルを用いることで高速化することができる。しかし、多数の類似映像が存在する場合、ハッシュ値の衝突が大量に発生し、特徴量テーブルにおいてハッシュテーブルからのポインタがないフレームが存在してしまう可能性が高い。
【００１２】
後続フレームの特徴量の比較のコストは、ハッシュテーブルを用いた場合でも同様である。特徴量テーブルの全エントリがメインメモリに保存できないほどの大規模映像アーカイブにおいては、特徴量データをハードディスクなどの補助記憶装置に格納する必要があり、特徴量の読み出しコストも無視することができない。
【００１３】
また、大規模アーカイブにおいては、再生速度の異なる映像が含まれる場合もあり、用途によってはそのような映像も検出できることが望ましい。特許文献２の手法では、既知の再生位置情報をもとに特徴量の比較位置を修正しているが、演出などによって再生速度が変えられたシーンを検出することはできない。時間情報を用いずに、複数のパターンで比較位置を修正する方法も考えられるが、すべての候補に対して複数回の特徴量比較処理を行うことは現実的ではない。
【００１４】
本発明は、数万時間規模の映像データに対して、高速かつ検出漏れの少ない類似映像検索を行う手法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明では、複数フレームの検索とその検索結果の統合による類似映像検索手法を用いる。本手法では、候補の後続フレームの特徴量比較を行わない。その代わり、クエリ映像の先頭フレームと同様に、クエリ映像の後続フレームについても類似フレーム検索を行い、複数の検索結果の中に連続系列が存在するかを調べる。通常の特徴量テーブルの探索では登録数に応じて検索時間が増加するため、本発明では、クラスタリング済みの特徴量データベースを構築しておくことで、複数回の類似フレーム検索を高速に行うことを可能としている。
【００１６】
以上の検索方法を実現する装置は、映像を入力する入力部と、入力部に入力された映像アーカイブの全映像から特徴量データベースを構築するデータベース構築部と、入力部に入力されたクエリ映像に類似する映像アーカイブ中の映像を検索する類似映像検索部と、類似映像検索部によって検索された類似映像の情報を出力する出力部とを備え、データベース構築部は、映像アーカイブ中の各映像から一定時間間隔でフレームを抽出し、抽出されたフレームから画像特徴量を抽出し、抽出された画像特徴量をクラスタリングして特徴量データベースを構築し、類似映像検索部は、クエリ映像から一定時間間隔でフレームを抽出し、抽出されたフレームから画像特徴量を抽出し、抽出されたクエリ映像の各々のフレームに対して画像特徴量を用いて特徴量データベースから類似フレームを検索し、クエリ映像の各々のフレームに対する類似フレームの検索結果から連続系列を探索し一定以上の連続性が認められた区間を類似映像と判定する。
【００１７】
特徴量データベースは、クラスタのＩＤとその代表値を関連付けした第１のデータ及び各クラスタに属するフレームのＩＤとその画像特徴量を関連付けした第２のデータを含み、第２のデータは同一クラスタに属するデータが記憶装置の連続領域に格納されている。第１のデータは主記憶装置に格納され、第２のデータは補助記憶装置に格納される。
【００１８】
一つの映像から一定時間間隔で抽出されたフレームに連続する整数値のＩＤが付されている場合、類似映像の判定に当たっては、一例として、クエリ映像の先頭フレームの類似フレームとして検索されたフレームのＩＤを類似映像の候補として登録し、ｍ番目の後続フレームの類似フレームとして検索されたフレームのＩＤから（ｍ−１）を引いたＩＤを投票先として順次投票を行い、得票数が一定数以上となった候補を類似映像と判定する。また、投票先のＩＤに隣接する一定範囲内の整数値のＩＤに対して投票を行うようにすると、再生速度の異なる類似映像を検出することができる。更に、後続フレームに対して類似フレームとして検索されたフレームの投票先の候補が未登録の場合、当該フレームのＩＤを新たな候補として登録するようにすれば、クエリ映像の先頭フレームを使った検索結果に現れない類似画像も検索することができる。
【発明の効果】
【００１９】
本発明では先頭フレームの検索結果のみを候補としないため、画質劣化やフレームサンプリングの位置ずれなどにより、先頭フレームでの候補選択に失敗する類似映像についても検出することができる。また、クエリ映像と候補映像の各フレームの特徴量を比較するのではなく、複数フレームの検索結果から連続性有するフレーム列を検出するだけでよいため、再生速度の異なる映像も検出することができる。さらに、類似映像が大量に含まれる大規模映像アーカイブにおいては、多数の候補の後続フレーム特徴量を特徴量データベースから読み出す必要がないため、高速に動作する。
【図面の簡単な説明】
【００２０】
【図１】本発明による類似映像検索装置のハードウェア構成例を示す図である。
【図２】本発明による類似映像検索装置の処理を説明する機能ブロック図である。
【図３】特徴量データベースの構造体を示す図である。
【図４】類似映像情報の構造体を示す図である。
【図５】類似映像検索部のデータフローを示す図である。
【図６】検索結果統合部の動作例を説明するための概略図である。
【図７】検索結果統合部の処理手順例を示すフローチャートである。
【図８】候補テーブルの構造体を示す図である。
【図９】検索結果統合部の投票処理の手順を示すフローチャートである。
【図１０】再生速度の異なる映像の検索を説明するための概略図である。
【図１１】従来法の類似映像検索部のデータフローを表す図である。
【図１２】本発明の補助記憶装置へのアクセス回数を説明するための概略図である。
【図１３】従来法の補助記憶装置へのアクセス回数を説明するための概略図である。
【図１４】本発明による類似映像情報の表示画面例を示す図である。
【図１５】本発明による類似映像情報の表示画面例を示す図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して、本発明の好適な実施形態について詳細に説明する。
図１は、本発明による類似映像検索装置のハードウェア構成の一例を示す図である。本実施例の類似映像検索装置は、一般的な計算機上に実装可能である。
【００２２】
本実施例の類似映像検索装置は、ＣＰＵ１０１、主記憶装置１０２、補助記憶装置１０３、映像入力部１０５、入力装置１０６、ディスプレイ１０７を備える。ＣＰＵ１０１、主記憶装置１０２、補助記憶装置１０３は、データバス１０４によって相互に接続され、インタフェース（Ｉ／Ｆ）を介して映像入力部１０５、入力装置１０６、ディスプレイ１０７に接続される。ＣＰＵ１０１は、主記憶装置１０２に記憶されたプログラムを実行することにより、各種処理を実行する。主記憶装置１０２は、ＣＰＵ１０１から直接アクセスすることのできる記憶装置であり、一般的な計算機におけるメインメモリである。主記憶装置１０２には、実行プログラムや処理途中のデータが格納される。補助記憶装置１０３は、ハードディスクなどの大容量記憶装置である。補助記憶装置１０３には、映像アーカイブから抽出した特徴量データが格納される。映像入力部１０５は、映像アーカイブ１０８やクエリ映像１０９を計算機に取り込むための入力インタフェースである。入力装置１０６は、マウスやキーボードなど、ユーザの操作を計算機に伝えるための入力インタフェースである。ディスプレイ１０７は、液晶ディスプレイやＣＲＴなどの表示装置であり、実行結果をユーザに伝える出力インタフェースである。
【００２３】
図２は、本発明による類似映像検索装置の処理を説明する機能ブロック図である。本発明の類似映像検索装置は、特徴量データベース構築部２２０と類似映像検索部２３０を備える。特徴量データベース構築部２２０及び類似映像検索部２３０は、主記憶装置１０２に記憶されたプログラムをＣＰＵ１０１で実行することによって実現される。
【００２４】
特徴量データベース構築部２２０では、検索対象の映像アーカイブ１０８中の全映像ファイルからクラスタリング済み特徴量データベース２０５を構築する。まず、フレーム抽出部２０２において、入力映像ファイルをデコードし、一定時間間隔でフレームを切り出す。特徴抽出部２０３では、フレームから既知の方法で画像特徴量を計算する。画像特徴量は、色特徴や形状特徴などを数値化したもので、固定長のベクトルデータで表される。設計仕様にもよるが、大規模な画像データベースに対して有意な画像検索結果を得るためには、通常、数十〜数百次元のベクトルデータが必要となる。データベース構築部２０４では、特徴量データのクラスタリングを行い、結果をクラスタリング済み特徴量データベース２０５として記憶装置に書き込む。
【００２５】
クラスタリング済み特徴量データベース２０５は、図３の構造体で表される。図３において、主記憶装置側には、クラスタ情報の構造体が格納される。クラスタ情報は、クラスタＩＤとその代表値から構成される。代表値は、例えばクラスタ要素の特徴量の平均値である。図３に示すように、補助記憶装置側には、フレームの特徴量情報が格納される。特徴量情報は、フレームＩＤと特徴量から構成される。フレームＩＤは、各フレームの固有番号を表す整数値である。時間的に連続するフレームには、連続したＩＤが付与される。特徴量は、固定長のベクトルデータである。特徴量情報は、クラスタ毎に、補助記憶装置の連続領域に格納される。クラスタリング済みの特徴量データベースに対する検索では、まず、クエリ画像の特徴量とクラスタの代表値との距離を計算し、距離の近いクラスタを選択する。次に、選択したクラスタに属する特徴量データを補助記憶装置から読み出し、特徴量距離の近い順に並び替えて出力する。このとき、データ読み出しの対象となる補助記憶装置の領域は、例えば、クラスタ要素数の最大値ｎとクラスタＩＤ：ｘから、ｘｎ〜（ｘ＋１）ｎ−１のように算出することができる。
【００２６】
図２の説明に戻り、類似映像検索部２３０では、映像アーカイブ１０８に含まれるクエリ映像１０９の類似映像を検索し、類似映像情報２１１として出力する。まず、フレーム抽出部２０７では、クエリ映像１０９から一定間隔でフレームを抽出する。抽出間隔は、フレーム抽出部２０２で用いた抽出間隔と必ずしも同一である必要はない。次に、特徴抽出部２０８では、フレームから画像特徴量を抽出する。この特徴量は、特徴抽出部２０３と同一のアルゴリズムで計算される。複数フレーム検索部２０９及び検索結果統合部２１０では、フレーム抽出部２０７で抽出された複数フレームに対して類似画像検索を行い、その検索結果から連続系列を探索することで類似映像の判定を行う。これらの処理は、本発明を特徴付ける処理であるため、以下で詳しく述べる。なお、特徴量データベース構築部２２０のフレーム抽出部２０２と類似映像検索部２３０のフレーム抽出部２０７は、いずれか一方が他方を兼用してもよい。同様に、特徴量データベース構築部２２０の特徴抽出部２０３と類似映像検索部２３０の特徴抽出部２０８は、いずれか一方が他方を兼用してもよい。
【００２７】
最終的に、類似映像検索部２３０は類似映像情報２１１を出力する。出力される類似映像情報２１１は、図４に示す構造体である。類似映像情報の構造体は、開始フレームＩＤ、終了フレームＩＤ、及び信頼度から構成される。開始フレームＩＤ、終了フレームＩＤは、クエリ映像と類似する映像区間を表す。信頼度は、クエリ映像と検出された映像との類似性を表す値である。
【００２８】
次に、類似映像検索部２３０の動作について詳しく説明する。図５は、類似映像検索部２３０のデータフローを示す図である。フレーム抽出部２０７は、クエリ映像１０９から先頭フレーム５０３を抽出し、一定間隔毎に後続フレーム５０４を抽出する。図には先頭フレームと後続フレームを区別して表示しているが、本手法では、各フレームに対する処理に違いはない。特徴量抽出部２０８では、各フレームから画像特徴量５０６，５０７を抽出する。複数フレーム検索部２０９では、各フレームの特徴量を用いて、クラスタリング済み特徴量データベース２０５から、類似フレームＩＤを検索する。検索結果は、フレームＩＤのリストであり、装置側で設定する検索結果上限値Ｎ以下の要素数を持つ。例えば、数万時間のテレビ映像アーカイブに対しては、Ｎ＝１０００程度を想定している。この結果、各フレームに対する検索結果ＩＤのリスト５１０〜５１３が得られる。検索結果統合部２１０では、複数の検索結果ＩＤのリストから、連続するＩＤ列を探索する。一定長以上の連続性が認められれば、類似映像情報２１１として出力する。
【００２９】
図６は、検索結果統合部２１０の動作を表す概略図である。検索結果統合部２１０では、検索結果から連続するＩＤ列を探すために、図のような候補に対する投票方式を用いる。この例では、ＩＤ：１０１を候補として、２、３、４、５番目のフレーム検索結果に含まれるＩＤ：１０２、ＩＤ：１０３、ＩＤ：１０４、ＩＤ：１０５の検索結果ＩＤから、それぞれ投票を行う。５フレームを処理した時点で、ＩＤ：１０１の得票数は５となるため、類似映像であると判定する。このとき、類似映像情報として、開始フレームＩＤ：１０１、終了フレームＩＤ：１０５、また得票数（ここでは５）を信頼度として出力する。
【００３０】
本手法を用いると、類似映像の判定基準の閾値を調整することで、特定フレームの検索に失敗する類似映像も検出することができる。例えば、ＩＤ：３０１を候補とした場合、３フレーム目の検索結果に近接フレームが含まれていない。しかし、最終的な得票数が閾値以上となれば、類似映像と判定される。また、本手法では、先頭フレームの検索結果に表れない候補も検出することができる。例えば、ＩＤ：７２２の近接フレームは、先頭フレーム目の検索結果には表れないが、後続フレームの検索結果に閾値以上の近接フレームが出現すれば、類似映像と判定される。
【００３１】
本発明の検索結果統合部２１０の動作について、図７のフローチャートを参照して説明する。まず、ステップ７０１で先頭フレームの検索結果５１０を読み込む。検索結果は、フレームＩＤのリストであり、検索結果の要素数は設計仕様にもよるが、１０００程度を想定している。次に、ステップ７０２で、候補テーブルを作成する。候補テーブルは、図８で表される構造体である。ここでは、ステップ７０１で読み込まれたすべてのフレームＩＤを候補の先頭フレームＩＤとして書き込む。また、各候補の得票数に１を書き込む。ステップ７０３では、後続フレームの検索結果を読み込む。検索結果は、フレームＩＤのリストである。ステップ７０４では、後続フレームの検索結果をもとに、候補に対して投票処理を行う。投票処理については、図９を用いて後ほど詳しく述べる。ステップ７０５では、投票処理の回数を調べ、回数が一定数に達していれば、ステップ７０６に進み、そうでなければ次フレームの検索結果を用いて投票を行うためにステップ７０３に戻る。ステップ７０６では、候補テーブルの各候補の投票数を調べ、閾値以上の投票数を持つ候補を類似映像として出力する。ここで用いる閾値は、処理フレーム数以下の整数値であり、設計仕様によって異なる。閾値を処理フレーム数より小さくすることで、画質劣化やフレームサンプリングの位置ずれによって、特定フレームの画像検索結果に近接フレームが現れない候補も、類似映像として検出することができる。
【００３２】
図７におけるステップ７０４の投票処理の動作を、図９のフローチャートを参照して説明する。まずステップ９０１では、検索結果リストから最初の要素（検索結果ＩＤ）を読み込む。ステップ９０２では、現在のクエリフレームのＩＤと先頭フレームのＩＤとの差から、投票先の候補ＩＤを算出する。例えば、５フレーム目の検索結果ＩＤがＩＤ：３０５であれば、ＩＤ：３０１が投票先の候補となる。ステップ９０３では、候補テーブルにステップ９０２で算出した候補ＩＤが存在するかを調べる。存在すれば、ステップ９０４で、その候補の投票数をインクリメントする。見つからなければ、ステップ９０５に進み、新規候補として候補テーブルに追加する。ステップ９０６では、検索結果リストのすべての要素を処理したかどうかを調べ、未処理の要素があればステップ９０１に戻り、なければ投票処理を終了させる。
【００３３】
以上の説明では、（検索結果ＩＤ）−｛（クエリフレームのＩＤ）−（先頭フレームのＩＤ）｝を、投票先の候補ＩＤとして用いていた。そのため、再生速度の異なる映像や、フレームサンプル間隔の異なる映像の場合は、適切な候補に投票されない可能性がある。本手法では、投票先の候補ＩＤに幅を持たせることで、この問題を解消することができる。図１０は、その動作の一例を示した概略図である。この例では、候補ＩＤ：２２１に対して、２フレーム目の検索結果ＩＤ：２２３から投票を行っている。図１０の下の表は、候補ＩＤ：２２１への投票を許可する結果フレームＩＤを、入力フレームＩＤ毎に示した対応表である。この例は、０．７倍速から１．５倍速までの類似映像を検出可能とした対応表である。候補ＩＤのチェックは単純な整数比較のみで実行できる。ただし、あるフレームの検索結果から同じ候補に複数回投票されないように制限する必要がある。本手法では、フレーム抽出や特徴量抽出などの前処理をやり直すことなく、また、特別な時間情報を用いることなく、再生速度の異なる映像の検出が可能となる。
【００３４】
次に、従来法の類似映像検索のデータフローを図１１に示す。本発明のデータフロー（図５）と比較すると、破線で囲まれた部分の処理が大きく異なる。従来法では、特徴抽出部２０８で計算された先頭フレーム特徴量５０６を用いて、特徴量テーブル１１０８から検索結果ＩＤ１１１０〜１１１２を取得し、これらを候補とする。特徴量比較部１１１３では、特徴量テーブル１１０８から、各候補の後続フレーム特徴量１１１４を読み出し、クエリ映像の後続フレーム特徴量５０７との距離を計算する。一定区間以上のフレーム特徴量の距離の合計が閾値以下の時、その候補を類似映像として出力する。
【００３５】
従来法では、フレーム検索部１１０９において、先頭フレームの検索結果から候補を選んでいるため、画質劣化やフレームサンプリングの位置ずれなどにより、先頭フレームの検索結果に類似映像の先頭フレームが含まれない場合、その類似映像を検出することができない。この問題を解決するために、後続フレームについても同様の処理を行い、候補を立てる方法が考えられる。しかし、多数の候補が存在する場合には、特徴量テーブルからの後続フレーム特徴量の読み込みやその比較などの処理コストが増大するため、大規模データの検索には適さない。
【００３６】
次に、本発明を用いた場合の、補助記憶装置へのアクセス回数を図１２の概略図を用いて説明する。クラスタリング済みのデータベースの画像検索では、クエリ画像の特徴量とクラスタ代表値との距離を計算し、距離の近いクラスタを数個選び、そのクラスタに該当するデータを補助記憶装置から読み出す。この際、クラスタのデータは補助記憶装置の連続領域に格納されているため、１回の読み出しでまとめてデータを取得できる。そのため、１回の検索に必要な読み出し回数は、検索結果数の上限値をＮ、クラスタの平均要素数をＭとすると、Ceil(Ｎ／Ｍ)となる。ここで、Ceil()は整数値への切り上げを行う演算子である。クエリ映像のフレーム数をＬとすると、類似映像検索処理に必要な補助記憶装置へのアクセス回数の合計は、Ｌ×Ceil(Ｎ／Ｍ)となる。例えば、図１２では、１フレーム目の検索結果を得るために、クラスタ１とクラスタ２が選ばれ、補助記憶装置の該当領域からデータを読み出している。後続フレームの検索についても同様である。
【００３７】
これに対して、従来法を用いた場合の補助記憶装置へのアクセス回数を、図１３の概略図を用いて説明する。ここでは説明の簡略化のために、先頭フレームの検索におけるアクセス回数は無視している。従来法では、先頭フレームの検索結果から候補が決まると、各候補に対してその後続フレームの特徴量を補助記憶装置から読み出す。補助記憶装置にはフレームＩＤの順にデータが格納されていると仮定すると、連続領域をまとめて読み込む場合のアクセス回数は、候補数Ｎだけ必要になる。
【００３８】
数万時間の映像アーカイブを想定した例として、検索結果数の上限値（＝候補数）Ｎ＝１０００、クラスタ平均要素数Ｍ＝５００、クエリ映像のフレーム数Ｌ＝１０の場合を考えると、本発明を用いた場合のアクセス数は１０×Ceil(１０００／５００)＝２０回であり、従来法のＮ＝１０００回に比べて、補助記憶装置へのアクセス回数を大幅に削減される。
【００３９】
図１４は、類似映像情報をユーザに伝えるためのディスプレイ表示画面例である。画面上部には、クエリ映像の各フレームのサムネイル画像とフレームＩＤを表示している。フレームＩＤの代わりに、フレームＩＤに対応する時間情報を表示させても良い。画面下には、検出された類似映像を同様に表示している。各検索結果に対して信頼度が表示されており、信頼度の高い順に表示の順番を並び替えている。また、投票処理において検索結果に現れなかったフレーム（この例ではＩＤ：３０３やＩＤ：７２１）については、例えば、サムネイル画像の輝度値を下げて表示している。これにより、ユーザは、検索結果として提示された映像の、どの部分が似ていないかを知ることができる。
【００４０】
図１５は、ユーザが検索結果を確認しながら、システムに対して類似映像の判定基準を指示するための表示画面の例である。画面上部には、クエリ映像の各フレームのサムネイル画像を表示している。画面下部には、各フレームの検索結果のサムネイル画像が表示されており、連続性の確認された検索結果は強調表示されている。また、クエリ映像の各フレームの下に、そのフレームの検索結果からの投票数を表示している。
【００４１】
例えば、動画中で暗転した場面などで、画像特徴に乏しいフレームが検索クエリとなると、検索結果に候補の近接ＩＤがほとんど含まれない場合がある。このとき、候補の得票率が全体的に下がり、類似映像の検出結果に悪影響を与えてしまう。そこで、ユーザは各フレームの検索結果のサムネイルや投票数を確認して、特徴の少ないフレームを使用しないようにシステムに対して伝える。例えば、図１５では、３フレーム目に特徴の少ないフレームが出現している。ユーザは、３フレーム目のサムネイルの下のチェックボックスを外すことで、システムにそのフレームの検索結果を用いないように指示する。システム側は、そのフレームの検索結果からの投票を取り消す処理を行い、閾値を下げて再度判定処理を行い、検索結果画面に反映させる。
【符号の説明】
【００４２】
１０１  ＣＰＵ
１０２  主記憶装置
１０３  補助記憶装置
１０４  データバス
１０５  映像入力部
１０６  入力装置
１０７  ディスプレイ
１０８  映像アーカイブ
１０９  クエリ映像
２０２  フレーム抽出部
２０３  特徴抽出部
２０４  データベース構築部
２０５  クラスタリング済み特徴量データベース
２０７  フレーム抽出部
２０８  特徴抽出部
２０９  複数フレーム検索部
２１０  検索結果統合部
２１１  類似映像情報
２２０  特徴量データベース構築部
２３０  類似映像検索部
１１０８  特徴量テーブル
１１０９  フレーム検索部
１１１３  特徴量比較部
１１１５  類似映像情報
【図１】
0005567384.tif 000002
【図２】
0005567384.tif 000003
【図３】
0005567384.tif 000004
【図４】
0005567384.tif 000005
【図５】
0005567384.tif 000006
【図６】
0005567384.tif 000007
【図７】
0005567384.tif 000008
【図８】
0005567384.tif 000009
【図９】
0005567384.tif 000010
【図１０】
0005567384.tif 000011
【図１１】
0005567384.tif 000012
【図１２】
0005567384.tif 000013
【図１３】
0005567384.tif 000014
【図１４】
0005567384.tif 000015
【図１５】
0005567384.tif 000016