(57)【要約】【課題】リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりした映像を含むクエリ映像であっても、そのクエリ映像の検索を可能とし、その処理を高速に行なう。【解決手段】データベース１５に格納されているリファレンス映像から、クエリ映像を検索する映像検索装置であって、前記クエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する映像分割部１１と、前記選択されたフレームから映像の特徴を示す特徴量を抽出する特徴量抽出部１２と、前記抽出した特徴量を１つ以上の量子化識別子に変換する特徴量量子化部１３と、前記量子化識別子に対応する転置インデックスを構成するリストに前記選択されたフレームの映像識別子と時刻情報を格納する特徴量蓄積部１４と、を備える。【選択図】図１
2013070158.tif 000002
【特許請求の範囲】
【請求項１】
データベースに格納されているリファレンス映像から、クエリ映像を検索する映像検索装置であって、
前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する映像分割部と、
前記選択されたフレームから映像の特徴を示す特徴量を抽出する特徴量抽出部と、
前記抽出した特徴量を１つ以上の量子化識別子に変換する特徴量量子化部と、
前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する特徴量蓄積部と、
前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する転置インデックス検索部と、を備えることを特徴とする映像検索装置。
【請求項２】
前記特徴量抽出部は、前記選択された各フレームについて、予め定義された１つ以上の領域毎に特徴量を抽出し、
前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、
前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納することを特徴とする請求項１記載の映像検索装置。
【請求項３】
前記特徴量量子化部は、ベクトル量子化を行なうためのコードブックを有し、特徴量に対して最近傍となる代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする請求項１または請求項２記載の映像検索装置。
【請求項４】
前記特徴量量子化部は、前記最近傍から近い順にｋ（ｋは自然数）個の代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする請求項３記載の映像検索装置。
【請求項５】
前記特徴量量子化部は、特徴量と予め定義された基底との内積の値を規定の閾値で離散化することによって、特徴量を量子化識別子に変換することを特徴とする請求項１または請求項２記載の映像検索装置。
【請求項６】
前記特徴量量子化部は、前記内積を離散化する際に、１つ以上の値に離散化することによって、特徴量を量子化識別子に変換することを特徴とする請求項５記載の映像検索装置。
【請求項７】
前記転置インデックス検索部は、前記クエリ映像の各セグメントの量子化識別子に対応する転置インデックスを参照し、前記転置インデックスに登録されているリファレンス映像の映像識別子、およびリファレンス映像のセグメントの時刻情報と前記クエリ映像のセグメントの時刻情報とのオフセット値に投票を行ない、得票数が一定値以上かつ一定の範囲内で極大となるリファレンス映像の映像識別子およびオフセット値を検出候補とすることを特徴とする請求項１記載の映像検索装置。
【請求項８】
前記クエリ映像の各セグメントに割り当てられている量子化識別子ｉｄそれぞれについて、
前記転置インデックスに登録されているリファレンス映像の映像識別子をｖとし、
リファレンス映像のセグメントの時刻情報をｔ’とし、
クエリ映像のセグメントの時刻情報をｔとしたときに、
前記転置インデックス検索部は、投票時に前記（ｔ，ｉｄ）の情報を、前記ｖおよびオフセット値（ｔ’−ｔ）毎に記録し、前記検出候補それぞれについて、（ｔ，ｉｄ）のリストを参照し、隣り合うリストの要素のｔが一定以上離れている箇所でリストを分割し、前記分割したリストそれぞれに対応するスコアを算出し、前記算出したスコアを前記リスト内の最大のｔから最小のｔを減算した値を用いて正規化し、前記正規化した値を検出結果とすることを特徴とする請求項７記載の映像検索装置。
【請求項９】
前記転置インデックス検索部は、前記（ｔ，ｉｄ）のリストのスコアを、リスト内の要素の個数とすることを特徴とする請求項８記載の映像検索装置。
【請求項１０】
前記転置インデックス検索部は、前記（ｔ，ｉｄ）のリストのスコアを、リスト内の要素のうち、前記ｉｄに関連付けられた重要度の和とし、前記重要度は、転置インデックスに蓄積されているセグメント数を、転置インデックスのｉｄ番目のリストのサイズで除算したものの対数とすることを特徴とする請求項８記載の映像検索装置。
【請求項１１】
前記転置インデックス検索部は、隣接するｔについて同じｉｄが出現した際には、スコアを一度しか加算しないことを特徴とする請求項１０記載の映像検索装置。
【請求項１２】
データベースに格納されているリファレンス映像から、クエリ映像を検索するプログラムであって、
前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する処理と、
前記選択されたフレームから映像の特徴を示す特徴量を抽出する処理と、
前記抽出した特徴量を１つ以上の量子化識別子に変換する処理と、
前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する処理と、
前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する処理と、の一連の処理を、コンピュータに実行させることを特徴とするプログラム。
【請求項１３】
前記選択された各フレームについて、予め定義された１つ以上の領域毎に特徴量を抽出する処理と、
前記領域毎に抽出された特徴量を量子化識別子に変換する処理と、
前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納する処理と、をさらに含むことを特徴とする請求項１２記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリ映像を入力して、ハードディスクドライブやその他のメディア、ネットワークストレージ等に保存されているリファレンス映像から、前記クエリ映像を検索する映像検索装置およびプログラムに関する。
【背景技術】
【０００２】
近年のブロードバンドの普及、およびＨＤＤ（Hard Disk Drive）、ＤＶＤ（Digital Versatile Disk）、Ｂｌｕ−ｒａｙ  ｄｉｓｃ等のストレージの大容量化に伴って、デジタルコンテンツを著作権者やコンテンツプロバイダの許諾を得ずに、ネットワークを介して共有・公開することが容易になってきており、このような不正な共有・公開が問題となっている。このような問題に対して、デジタルコンテンツの指紋（特徴量）を利用して、複数のデジタルコンテンツの中から、著作権者が自由配布を許諾していない特定のコンテンツを自動的に検出する技術が提案されている。
【０００３】
特許文献１では、三次元周波数解析と主成分分析を用いて、コンテンツの特徴量を記述している。この手法では、空間周波数解析（DCT）で得られた係数に時間軸方向への周波数解析（FFT）を加えた三次元周波数解析を行ない、さらに主成分分析により三次元周波数解析で得られた係数から特徴量を抽出している。特許文献２では、特許文献１で利用されている特徴量を用いて、流通コンテンツと類似している特定コンテンツを絞り込み、絞り込めない場合には、位相限定相関法を用いて流通コンテンツと最も類似している特定コンテンツを決定し、閾値によって同一コンテンツであるか否かを判定している。
【０００４】
非特許文献１では、映像の各フレーム全体からカラーレイアウトと呼ばれる特徴量を抽出し、複数のフレームをシーケンシャルにマッチングさせることで、映像の一部分が切り取られる等の時間的編集が行なわれた場合でも検出を可能にしている。
【０００５】
また、非特許文献２では、映像の各フレームからコーナーと呼ばれる特徴点を検出し、その周辺から特徴量を抽出し、各特徴点をマッチングさせることによって、切り取り等の編集が行なわれた場合であっても、不正流通コンテンツを検出できるようにしている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−１８６７５号公報
【特許文献２】特開２００６−２８５９０７号公報
【非特許文献】
【０００７】
【非特許文献１】E. Kasutani and A. Yamada, “The MPEG-7 color layout descriptor: a compact image feature description for high-speed image/video segment retrieval,” in Proc. of ICIP, 2001, pp. 674-677.
【非特許文献２】J. Law-To et al., “Video Copy Detection: A Comparative Study,”in Proc. ACM CIVR’07, pp. 371-378, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１および２で開示されている手法では、動画コンテンツ１つから１つの特徴量を抽出するため、例えば、動画コンテンツを２つに分割する等の時間軸方向の編集が行なわれると検出ができなくなるという問題がある。非特許文献１で開示されている手法では、画面全体から１つの特徴量のみを抽出しているため、テロップやロゴを挿入するような空間的編集が行なわれると検出ができなくなる問題がある。また、非特許文献２で開示されている手法では、１画面から数十個の特徴点を抽出し、それら全てをマッチングさせているため、特徴点の抽出およびマッチングに時間がかかりすぎるという問題がある。
【０００９】
本発明は、このような事情に鑑みてなされたものであり、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりした映像を含むクエリ映像であっても、そのクエリ映像の検索を可能とし、その処理を高速に行なうことができる映像検索装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
（１）上記の目的を達成するために、本発明は、以下のような手段を講じた。すなわち、本発明の映像検索装置は、データベースに格納されているリファレンス映像から、クエリ映像を検索する映像検索装置であって、前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する映像分割部と、前記選択されたフレームから映像の特徴を示す特徴量を抽出する特徴量抽出部と、前記抽出した特徴量を１つ以上の量子化識別子に変換する特徴量量子化部と、前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する特徴量蓄積部と、前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する転置インデックス検索部と、を備えることを特徴とする。
【００１１】
このように、リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、各セグメントから予め定められた数のフレームを選択し、選択されたフレームから映像の特徴を示す特徴量を抽出し、抽出した特徴量を１つ以上の量子化識別子に変換し、リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストにセグメントの映像識別子と時刻情報を格納し、クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを参照し、投票により、クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。
【００１２】
（２）また、本発明の映像検索装置において、前記特徴量抽出部は、前記選択された各フレームについて、予め定義された１つ以上の領域毎に特徴量を抽出し、前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納することを特徴とする。
【００１３】
このように、前記選択された各フレームについて、予め定義された１つ以上の領域毎に特徴量を抽出し、前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納するので、一つのフレームから複数の特徴量を抽出することが可能となり、検索精度を向上させることが可能となる。
【００１４】
（３）また、本発明の映像検索装置において、前記特徴量量子化部は、ベクトル量子化を行なうためのコードブックを有し、特徴量に対して最近傍となる代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする。
【００１５】
このように、ベクトル量子化を行なうためのコードブックを有し、特徴量に対して最近傍となる代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換し、量子化識別子に基づいてマッチングを行なうので、検索時間を短縮することが可能となる。
【００１６】
（４）また、本発明の映像検索装置において、前記特徴量量子化部は、前記最近傍から近い順にｋ（ｋは自然数）個の代表ベクトルにベクトル量子化をすることによって、特徴量を量子化識別子に変換することを特徴とする。
【００１７】
このように、前記最近傍から近い順にｋ（ｋは自然数）個の代表ベクトルにベクトル量子化をすることによって、類似した特徴量同士が同一の量子化識別子を共有する確率を向上させ、検索の精度を高めることが可能となる。
【００１８】
（５）また、本発明の映像検索装置において、前記特徴量量子化部は、特徴量と予め定義された基底との内積の値を規定の閾値で離散化することによって、特徴量を量子化識別子に変換することを特徴とする。
【００１９】
このように、特徴量と予め定義された基底との内積の値を規定の閾値で離散化することによって、特徴量を量子化識別子に変換し、量子化識別子に基づいてマッチングを行なうので、検索時間を短縮することが可能となる。
【００２０】
（６）また、本発明の映像検索装置において、前記特徴量量子化部は、前記内積を離散化する際に、１つ以上の値に離散化することによって、特徴量を量子化識別子に変換することを特徴とする。
【００２１】
このように、前記内積を離散化する際に、１つ以上の値に離散化することによって、類似した特徴量同士が同一の量子化識別子を共有する確率を向上させ、検索時間を短縮し、検索の精度を高めることが可能となる。
【００２２】
（７）また、本発明の映像検索装置において、前記転置インデックス検索部は、前記クエリ映像の各セグメントの量子化識別子に対応する転置インデックスを参照し、前記転置インデックスに登録されているリファレンス映像の映像識別子、およびリファレンス映像のセグメントの時刻情報と前記クエリ映像のセグメントの時刻情報とのオフセット値に投票を行ない、得票数が一定値以上かつ一定の範囲内で極大となるリファレンス映像の映像識別子およびオフセット値を検出候補とすることを特徴とする。
【００２３】
このように、前記クエリ映像の各セグメントの量子化識別子に対応する転置インデックスを参照し、前記転置インデックスに登録されているリファレンス映像の映像識別子、およびリファレンス映像のセグメントの時刻情報と前記クエリ映像のセグメントの時刻情報とのオフセット値に投票を行ない、得票数が一定値以上かつ一定の範囲内で極大となるリファレンス映像の映像識別子およびオフセット値を検出候補とするので、検索時間を短縮することが可能となる。
【００２４】
（８）また、本発明の映像検索装置において、前記クエリ映像の各セグメントに割り当てられている量子化識別子ｉｄそれぞれについて、前記転置インデックスに登録されているリファレンス映像の映像識別子をｖとし、リファレンス映像のセグメントの時刻情報をｔ’とし、クエリ映像のセグメントの時刻情報をｔとしたときに、前記転置インデックス検索部は、投票時に前記（ｔ，ｉｄ）の情報を、前記ｖおよびオフセット値（ｔ’−ｔ）毎に記録し、前記検出候補それぞれについて、（ｔ，ｉｄ）のリストを参照し、隣り合うリストの要素のｔが一定以上離れている箇所でリストを分割し、前記分割したリストそれぞれに対応するスコアを算出し、前記算出したスコアを前記リスト内の最大のｔから最小のｔを減算した値を用いて正規化し、前記正規化した値を検出結果とすることを特徴とする。
【００２５】
このように、投票時に（ｔ，ｉｄ）の情報を、ｖおよびオフセット値（ｔ’−ｔ）毎に記録し、検出候補それぞれについて、（ｔ，ｉｄ）のリストを参照し、隣り合うリストの要素のｔが一定以上離れている箇所でリストを分割し、分割したリストそれぞれに対応するスコアを算出し、算出したスコアをリスト内の最大のｔから最小のｔを減算した値を用いて正規化し、正規化した値を検出結果とするので、検索の精度を高めることが可能となる。
【００２６】
（９）また、本発明の映像検索装置において、前記転置インデックス検索部は、前記（ｔ，ｉｄ）のリストのスコアを、リスト内の要素の個数とすることを特徴とする。
【００２７】
（１０）また、本発明の映像検索装置において、前記転置インデックス検索部は、前記（ｔ，ｉｄ）のリストのスコアを、リスト内の要素のうち、前記ｉｄに関連付けられた重要度の和とし、前記重要度は、転置インデックスに蓄積されているセグメント数を、転置インデックスのｉｄ番目のリストのサイズで除算したものの対数とすることを特徴とする。
【００２８】
このように、（ｔ，ｉｄ）のリストのスコアを、リスト内の要素のうち、ｉｄに関連付けられた重要度の和とし、重要度は、転置インデックスに蓄積されているセグメント数を、転置インデックスのｉｄ番目のリストのサイズで除算したものの対数とするので、多くのセグメントに出現する量子化識別子の重要度が小さくなり、特定のセグメントに固有の量子化識別子の重要度が大きくなり、検索の精度を高めることが可能となる。
【００２９】
（１１）また、本発明の映像検索装置において、前記転置インデックス検索部は、隣接するｔについて同じｉｄが出現した際には、スコアを一度しか加算しないことを特徴とする。
【００３０】
このように、部分リストのスコアを計算する際に、隣接するｔについて同じ（ｒ，ｉｄ）が出現した際には、スコアを一度しか加算しないようにすることで、特に動きの少ない領域において、偶然無関係な特徴の量子化識別子が連続して一致してしまうことによる誤検出を削減し、検索の精度を高めることが可能となる。
【００３１】
（１２）また、本発明のプログラムは、データベースに格納されているリファレンス映像から、クエリ映像を検索するプログラムであって、前記リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択する処理と、前記選択されたフレームから映像の特徴を示す特徴量を抽出する処理と、前記抽出した特徴量を１つ以上の量子化識別子に変換する処理と、前記リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストに前記セグメントの映像識別子と時刻情報を格納する処理と、前記クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、前記転置インデックスを参照し、投票により、前記クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定する処理と、の一連の処理を、コンピュータに実行させることを特徴とする。
【００３２】
このように、リファレンス映像およびクエリ映像を一定時間長のセグメントに分割し、各セグメントから予め定められた数のフレームを選択し、選択されたフレームから映像の特徴を示す特徴量を抽出し、抽出した特徴量を１つ以上の量子化識別子に変換し、リファレンス映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを構成するリストにセグメントの映像識別子と時刻情報を格納し、クエリ映像のセグメント情報と対応する量子化識別子の集合に基づいて、転置インデックスを参照し、投票により、クエリ映像の全部または一部を含むリファレンス映像の映像識別子および時刻情報を特定するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。
【００３３】
（１３）また、本発明のプログラムは、前記選択された各フレームについて、予め定義された１つ以上の領域毎に特徴量を抽出する処理と、前記領域毎に抽出された特徴量を量子化識別子に変換する処理と、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納する処理と、をさらに含むことを特徴とする。
【００３４】
このように、前記選択された各フレームについて、予め定義された１つ以上の領域毎に特徴量を抽出し、前記特徴量量子化部は、前記領域毎に抽出された特徴量を量子化識別子に変換し、前記特徴量蓄積部は、前記領域毎の量子化識別子に基づいて、前記各領域に対応する転置インデックスを構成するリストに前記領域の映像識別子と時刻情報を格納するので、１つのフレームから複数の特徴量を抽出することが可能となり、検索精度を向上させることが可能となる。
【発明の効果】
【００３５】
本発明によれば、クエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択し、前記選択されたフレームから映像の特徴を示す特徴量を抽出し、前記抽出した特徴量を１つ以上の量子化識別子に変換し、前記量子化識別子に対応する転置インデックスを構成するリストに前記選択されたフレームの映像識別子と時刻情報を格納するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。
【図面の簡単な説明】
【００３６】
【図１】本発明の実施形態に係る映像検索装置のブロック図である。
【図２】映像を分割する様子を示す図である。
【図３Ａ】矩形領域Ｒｉの設定の例を示す図である。
【図３Ｂ】矩形領域Ｒｉの設定の例を示す図である。
【図３Ｃ】矩形領域Ｒｉの設定の例を示す図である。
【図４】特徴量の抽出の方法を示す図である。
【図５】ソフト割り当ての一例を示す図である。
【図６】転置インデックスの一例を示す図である。
【図７】投票の様子を示す図である。
【発明を実施するための形態】
【００３７】
以下、本発明の実施形態について図面を参照して説明する。本実施形態では、予め検出を行なおうとする著作権コンテンツをリファレンス映像として入力し、特徴量を抽出し、さらに特徴量を量子化し、データベースを構築しておく。その後、入力されたクエリ映像を用いて、リファレンス映像を検索する。
【００３８】
図１は、本発明の実施形態に係る映像検索装置のブロック図である。図１に示すように、映像検索装置１０は、映像分割部１１、特徴量抽出部１２、特徴量量子化部１３、特徴量蓄積部１４、データベース１５、およびデータベース検索部１６から構成されている。また、これらの構成要素は、制御バス１７に接続され、相互に信号の送受信を行なうことができる。
【００３９】
映像分割部１１は、リファレンス映像をブロックに分割する。図２は、分割の様子を示す図である。この分割は、空間の分割と時間方向の分割を含む。空間方向の分割は、図３に示すように、任意の形状の矩形によって定義される。図２に示した例は、図３Ｂに示す分割を採用し、Ｒ４の矩形に対応するブロックを示している。なお、図３Ａは、画面全体を１つの矩形領域とした場合である。キャプションやロゴなどが挿入されることを想定しないのであれば、この矩形領域を利用する。図３Ｂは、編集が行なわれる場所を予め決めない場合の矩形領域の設定である。図３Ｃは、画面下や画面右に字幕などの編集が想定される場合の矩形領域の設定である。どちらか片方に編集が行なわれても、他方の矩形領域に影響がない。
【００４０】
時間方向の分割は、連続するフレームを一定の時間（例えば０．５秒毎）で区切ることによって行なわれる。矩形のＩＤがｒの矩形かつ、時間方向にｔ番目のブロックをＢｒ，ｔと表記する。仮に３０ｆｐｓの映像を０．５秒毎に区切ると、各ブロック中には１５枚のフレームが存在することになる。
【００４１】
特徴量抽出部１２は、映像分割部１１で得られた各ブロックＢｒ，ｔから特徴量を抽出する。これは単純に、Ｂｒ，ｔに含まれる全てのフレームから特徴ベクトルを抽出しても良いが、抽出される特徴量の数を制限したい場合にはフレームを一定間隔でサンプリングしてから特徴量を抽出しても良い。例えば、ＤＣＴ係数を利用する手法や局所特徴領域を記述するために広く用いられているScale-invariant feature transform（SIFT）を用いることができる。
【００４２】
ここで、Ｂｒ，ｔから抽出された特徴量の集合をＦｒ，ｔとする。下記にＤＣＴ係数のＡＣ（Alternating Current）成分を特徴量とする際の抽出法を説明する。まず、部分フレームを８ｘ８画素に縮小し、離散コサイン変換（ＤＣＴ）を行なう。得られたＤＣＴ係数のうち、ＡＣ成分をジグザグスキャン順にＭ個取得することでＭ次元の特徴量を得る。
【００４３】
特徴量量子化部１３は、特徴量抽出部１２で抽出された各特徴量集合Ｆｒ，ｔ内の特徴量を、それぞれ０〜Ｎ−１までの値に量子化し、量子化ＩＤの集合Ｗｒ，ｔ（整数値）を作成する。Ｗｒ，ｔ内のＩＤの数は、予め最大数が決められているか、量子化時のソフト割り当ての個数によって決定される。
【００４４】
以下、ＤＣＴ係数のＡＣ成分を特徴量とした際のＷｒ，ｔの作成法を説明する。Ｍ次元の特徴量の各次元をそれぞれ、正の値であれば１、負の値であれば０にバイナリ化する。これによりＭ次元の特徴量はＮビットのビット列に変換される。このビット列は２＾Ｍ通り存在し、このビット列を１０進数表記した０〜２＾Ｍ−１が量子化後の値となる（Ｎ＝２＾Ｍ）。この手順により、Ｗｒ，ｔが得られる。但し、特徴量の微小な変化によって量子化ＩＤが変化してしまうことに対応するため、ソフト割り当てを行なう。ソフト割り当ては、例えば、下記の文献に記載されている技術を用いて行なうことが可能である。
J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, "Lost in quantization: Improving particular object retrieval in large scale image databases," in Proc. of CVPR, 2008.
【００４５】
図５は、ソフト割り当ての一例を示す図である。このソフト割り当てとは、量子化時に特徴量を１つのＩＤだけに割り当てるのではなく、複数の量子化ＩＤに割り当てることである。本発明では、Ｆｒ，ｔの各特徴量ｆの各次元について、絶対値が小さいものからＫ次元のビットを自由に反転させたＩＤにも割り当てることで、合計２＾Ｋ個のＩＤに割り当てが行なわれる。ＩＤの最大数が定められている場合には、ＩＤの最大数を超えるまで、絶対値の小さいものから順番にビット反転を行なったＩＤを割り当てることを繰り返す。
【００４６】
なお、一般的な特徴ベクトルについて、ベクトル量子化を用いて量子化を行なっても良い。予め特徴量の集合からｋ−ｍｅａｎｓクラスタリングを行ない、Ｎ個の代表ベクトルを求めておく。Ｆｒ，ｔ内の特徴量をそれぞれ最も近い代表ベクトルに割り当て、その代表ベクトルのＩＤを量子化ＩＤとする。また、最も近い代表ベクトルではなく、最も近いＫ個の代表ベクトルに割り当てることでソフト割り当てを実現することができる。
【００４７】
以上のようにして、Ｗｒ，ｔの作成を行なう。なお、量子化ＩＤの重複は許さないものとする。
【００４８】
特徴量蓄積部１４は、量子化ＩＤの集合Ｗｒ，ｔを、図６に示す転置インデックスに保存する。転置インデックスは矩形毎に個別に用意する。図６に示すように、Ｗｒ，ｔ内の全てのＩＤについて、対応するリストにブロックＢｒ，ｔの情報を登録する。登録する情報は、リファレンス映像のビデオＩＤ、ブロックの時刻情報（ｔ）とする。この登録を全てのｒ，ｔに対して行なう。特徴量蓄積部１４は、これらの登録情報をデータベース１５に格納する。
【００４９】
一方、データベース検索部１６は、リファレンス映像からクエリ映像の検索を行なう。検索を行なう際には、クエリ映像は、リファレンス映像を蓄積した場合と同様に、ブロックに分割し、特徴量を抽出し、量子化を行なう。ブロックの分割法はリファレンス映像を蓄積した際と同じにしなければならないが、特徴量を抽出する際に抽出される特徴量の数を削減したり、量子化を行なう際にソフト割り当てを行なうＩＤの数を削減することで、探索速度を向上させることができる。
【００５０】
データベース検索部１６は、クエリ映像から抽出されたＷｒ，ｔそれぞれについて、Ｗｒ，ｔ内のすべての量子化ＩＤについて、転置インデックスの該当するリストを参照し、対応するブロックＩＤのリストを取得する。リスト中のブロックＩＤをｔ’とすると、対応するオフセットｔ’−ｔに投票を行なう。同時に、投票時の情報（ｒ，ｔ，ｉｄ）をオフセット値ｔ’−ｔ毎に保存する。ここでｉｄは量子化識別子である。また、その際、ｔについて昇順にソートされるように保存する。
【００５１】
図７は、投票の様子を示す図である。全てのＷｒ，ｔについて投票が終了すると、各オフセット値のスコアについて、閾値以上かつ極大の値を持つオフセット値のリストを取得する。その後、それぞれのオフセット値について、下記の処理を行なう。
【００５２】
オフセット値ｔ’−ｔについて、対応する（ｒ，ｔ，ｉｄ）のリストを取得する。このリストは、前述のとおりｔについて昇順にソートされている。このリストを、隣り合うｔが一定以上の間隔が開いている箇所で分割することによって、部分リストに分割する。その後、それぞれの部分リストについて、スコアを計算する。最も単純には、リスト内の要素の数をスコアとする。要素の数ではなく、それぞれの要素に、ｉｄに基づく重みを利用しても良い。この重みには、文書検索で用いられるInverse Document Frequency（IDF）を用いることができる。
【００５３】
本発明の場合、ＩＤＦは、蓄積している映像のセグメント数をＤ、ｉｄ番目の転置インデックスのリストのサイズをＤ’とすると、ＩＤＦ＝ｌｏｇ（Ｄ’／Ｄ）と求めることができる。更に、スコアを部分リスト内の最大のｔと最小のｔの差（＝検出したコピー領域の長さ）に応じて、この差が大きくなるほどスコアを小さくするように正規化しても良い。最も簡単にはスコアを最大のｔから最小のｔを引いた値で除算する。
【００５４】
また、部分リストのスコアを計算する際に、隣接するｔについて同じ（ｒ，ｉｄ）が出現した際には、スコアを一度しか加算しないようにしても良い。
【００５５】
この処理を全てのオフセットについて行なった後、部分リストのスコアでソートし、上位の結果を検索結果とする。
【００５６】
以上説明したように、本実施形態によれば、クエリ映像を一定時間長のセグメントに分割し、前記各セグメントから予め定められた数のフレームを選択し、前記選択されたフレームから映像の特徴を示す特徴量を抽出し、前記抽出した特徴量を１つ以上の量子化識別子に変換し、前記量子化識別子に対応する転置インデックスを構成するリストに前記選択されたフレームの映像識別子と時刻情報を格納するので、クエリ映像の全部または一部が、リファレンス映像の時間軸上の一部分を切り出したり、リファレンス映像にテロップやロゴが挿入されたりしたものであっても、クエリ映像の検索が可能となり、検索時間を短縮し、検索の精度を高めることが可能となる。
【符号の説明】
【００５７】
１０  映像検索装置
１１  映像分割部
１２  特徴量抽出部
１３  特徴量量子化部
１４  特徴量蓄積部
１５  データベース
１６  データベース検索部
１７  制御バス
【図１】
2013070158.tif 000003
【図２】
2013070158.tif 000004
【図３Ａ】
2013070158.tif 000005
【図３Ｂ】
2013070158.tif 000006
【図３Ｃ】
2013070158.tif 000007
【図４】
2013070158.tif 000008
【図５】
2013070158.tif 000009
【図６】
2013070158.tif 000010
【図７】
2013070158.tif 000011