(57)【要約】【課題】高精度かつ効率的に広告映像を検出する。【解決手段】映像検出装置１は、入力映像の区間構造を解析して部分区間に分割する構造解析部１０１と、部分区間の特徴に基づいて、広告映像が含まれる候補区間を１つ以上検出し、その開始時刻および終了時刻を求める候補区間検出部１０２と、候補区間の開始時刻および終了時刻の内部に存在する部分区間の画像および音のうちの少なくとも１つを解析し、特徴量を抽出するショット特徴抽出部１０３と、特徴量に基づいて、部分区間を符号によって表現する符号化部１０４と、符号によって表現された１つ以上の部分区間によって構成される符号系列から、再起的に出現する符号系列となる部分区間群を検出する再起符号系列検出部１０５と、検出された部分区間群のうち、所定の条件を満たすもののみを広告映像区間として出力するフィルタ部１０６とを備える。【選択図】図１
2013009248.tif 000002
【特許請求の範囲】
【請求項１】
処理対象となる入力映像から広告映像を検出する映像検出方法であって、
前記入力映像の区間構造を解析して部分区間に分割する構造解析処理と、
前記部分区間の特徴に基づいて、前記広告映像が含まれる候補区間を１つ以上検出し、その開始時刻および終了時刻を求める候補区間検出処理と、
前記候補区間の開始時刻および終了時刻の内部に存在する前記部分区間の画像および音のうちの少なくとも１つを解析し、特徴量を抽出する特徴抽出処理と、
前記特徴量に基づいて、前記部分区間を符号によって表現する符号化処理と、
前記符号によって表現された１つ以上の部分区間によって構成される符号系列から、再起的に出現する符号系列となる部分区間群を検出する再起符号系列検出処理と、
前記検出された部分区間群のうち、所定の条件を満たすもののみを広告映像区間として出力するフィルタ処理と、
を備えることを特徴とする映像検出方法。
【請求項２】
請求項１記載の映像検出方法であって、前記構造解析処理では、前記入力映像の切れ目であるカット点を解析し、これらカット点のうち、少なくとも発話区間でも音楽区間でもない点の時刻、および同条件を満たす次の点までの時間長を求めることを特徴とする映像検出方法。
【請求項３】
請求項１記載の映像検出方法であって、前記特徴抽出処理では、部分領域ごとの輝度平均値、分散、部分領域ごとの色平均値、分散、輝度ヒストグラム、色ヒストグラム、ＭＦＣＣのうちの少なくとも１つを特徴量として抽出することを特徴とする映像検出方法。
【請求項４】
請求項１記載の映像検出方法であって、前記再起符号系列検出処理では、一定以上の生起回数となる部分符号系列を繰り返し検出することによって再起符号系列を検出し、前記フィルタ処理では、所定の時間長となる再起符号系列のみを出力することを特徴とする映像検出方法。
【請求項５】
処理対象となる入力映像から広告映像を検出する映像検出装置であって、
前記入力映像の区間構造を解析して部分区間に分割する構造解析部と、
前記部分区間の特徴に基づいて、前記広告映像が含まれる候補区間を１つ以上検出し、その開始時刻および終了時刻を求める候補区間検出部と、
前記候補区間の開始時刻および終了時刻の内部に存在する前記部分区間の画像および音のうちの少なくとも１つを解析し、特徴量を抽出する特徴抽出部と、
前記特徴量に基づいて、前記部分区間を符号によって表現する符号化部と、
前記符号によって表現された１つ以上の部分区間によって構成される符号系列から、再起的に出現する符号系列となる部分区間群を検出する再起符号系列検出部と、
前記検出された部分区間群のうち、所定の条件を満たすもののみを広告映像区間として出力するフィルタ部と、
を備えることを特徴とする映像検出装置。
【請求項６】
請求項５記載の映像検出装置であって、前記構造解析部は、前記入力映像の切れ目であるカット点を解析し、これらカット点のうち、少なくとも発話区間でも音楽区間でもない点の時刻、および同条件を満たす次の点までの時間長を求めることを特徴とする映像検出装置。
【請求項７】
請求項５記載の映像検出装置であって、前記特徴抽出部は、部分領域ごとの輝度平均値、分散、部分領域ごとの色平均値、分散、輝度ヒストグラム、色ヒストグラム、ＭＦＣＣのうちの少なくとも１つを特徴量として抽出することを特徴とする映像検出装置。
【請求項８】
請求項５記載の映像検出装置であって、前記再起符号系列検出部は、一定以上の生起回数となる部分符号系列を繰り返し検出することによって再起符号系列を検出し、前記フィルタ部は、所定の時間長となる再起符号系列のみを出力することを特徴とする映像検出装置。
【請求項９】
請求項１乃至４のいずれか１項に記載した各処理をコンピュータに実行させることを特徴とする映像検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理対象となる入力映像を解析し、広告映像を検出する映像検出方法、映像検出装置、および映像検出プログラムに関する。
【背景技術】
【０００２】
ＶＯＤ（Video On Demand ）やＩＰＴＶ（Internet Protocol Television）、地上デジタル放送再送信などに代表されるように、通信を利用した映像配信サービスの利用が活発化し、多チャンネルで膨大な量の映像コンテンツが配信されるようになった。
【０００３】
製作者側にとっては、これまでの放送や映画館でのスクリーン上映に加えて、前記の映像配信サービスによるマルチチャネルでの販売を展開できるようになった。さらにこのことは、単純な販売チャネルの増加だけでなく、新しいビジネスチャンスももたらしている。その代表が映像広告である。映像広告は、宣伝対象に対する興味を惹き、消費者を購買へと動機づけるための重要な宣伝材料である。したがって、映像広告は、市場動向やユーザのニーズに合ったタイムリーなものであることが要請される。
【０００４】
しかしながら、前記のような新しい映像配信サービスでは必ずしもうまくいかない。すなわち、これまで主流であった放送や映画館では、同時（あるいは同時期）に全ユーザが同じコンテンツを視聴することが普通であった。このため、いつどこで、場合によってはどのようなユーザ層がそのコンテンツを視聴するかが把握できたため、適切な広告映像を打つことができた。一方、新しい映像配信サービスでは、各々のユーザが好きな時間に自由な場所で視聴を楽しむことが普通である。このため、ユーザが視聴する時期・時刻によっては、挿入されている広告映像が全く興味を惹かないものになったり、全く無意味なものとなったりする問題が起こる。このような問題に対処するため、例えばユーザが視聴する時期に応じて適切な広告映像に差し替えるなど、適応的な広告映像配信システムが望まれている。
【０００５】
このようなシステムを実現するために必要な技術は多岐に渡るが、広告映像を古いものから新しいものに差し替えるためには、少なくともまず始めに、元の映像のどこに広告映像が挿入されているかを知っておく必要がある。予めこの情報が得られている場合には何の苦労もないが、大量の映像データが流通している昨今、全ての映像データについてその広告映像の位置を知り、管理することは容易ではない。そこで、大量の映像データから広告映像のみを自動的に検出する技術が求められている。
【０００６】
広告映像の検出技術に関しては、これまでにも数多くの発明がなされてきている。古くデジタルビデオレコーダーなどでは、広告映像区間とその他の映像区間とで音声チャネル数が異なることを利用していたが、最近では音声チャネル数に違いがなくなったために、このような方法では検出することが難しくなった。このため、映像を直接解析し、広告映像を検出する技術に関する発明がなされてきている。既存の先行技術は、大別して下記の２つに分類される。
【０００７】
（１）リファレンスデータがある場合
（２）リファレンスデータがない場合
前者は、検出すべき広告映像が定まっており、かつこれが得られている場合（このデータをリファレンスデータと呼ぶ）を想定したものであり、映像データの中からリファレンスデータと合致する映像区間を探しだす技術である。一方、後者は、このようなリファレンスデータが一切得られていないことを想定した技術である。
【０００８】
前者に属する技術として、特許文献１には、リファレンスデータとして静止画像を保持しておき、当該静止画像に類似する映像フレームを検出する技術が開示されている。
【０００９】
後者に属する技術として、非特許文献１には、Support Vector Machine（ＳＶＭ）や隠れマルコフモデル（Hidden Markov Model:ＨＭＭ）などに代表される統計モデルを用いて広告映像に現れる独特な特徴をモデル化しておき、この“広告映像モデル”に基づいて検出を行う技術が開示されている。映像特徴としては、映像の中に含まれる隣り合うショット（カット点とカット点に挟まれた一続きの映像区間）間の画像フレームの類似度と、エッジの変化率に関する平均と分散、音のタイプ（発話、音楽、無音など）、それらの時間差分量を用いている。これらの映像特徴をＳＶＭを用いてモデル化し、広告映像区間らしい区間を検出する。
【００１０】
同じく後者に属する技術として、非特許文献２には、モデルを用いずショットの類似度のみに基づいて検出を行う技術が開示されている。この技術では、まず、全ての映像をショットに分割する。続いて、各ショットに含まれる画像フレームの色の平均と分散、方向輝度の平均と分散、エッジ、および画像中に含まれる顔の位置と大きさをショットの特徴量として抽出し、全ショット間の類似度を特徴量に基づいて計算する。最後に、他のショットとの類似度の分布が特別な傾向をもつショットのみを広告映像区間として検出する。
【００１１】
またさらに後者に属する技術として、特許文献２には、１つ以上のショットを検出し、その開始時刻と終了時刻が無音であるもののうち、その間隔が１５秒、３０秒のいずれかである区間を広告映像区間として検出する技術が開示されている。
【００１２】
特許文献２と同様、特許文献３には、広告映像の時間長を利用した技術が開示されている。この技術では、１００ミリ秒間以上連続して平均音量値が８０より低下した時刻をブランクとして検出し、このブランクの間隔が広告映像の時間長（例えば１５秒、３０秒）と一致した際に当該区間を広告映像として検出する。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特許第４４２１５２７号公報
【特許文献２】特許第３４０７８４０号公報
【特許文献３】特許第３５１３４２４号公報
【非特許文献】
【００１４】
【非特許文献１】X.-S. Hua, L. Lu, and H.-J. Zhang. “Robust Learning-based TV Commercial Detection,” in Proceedings of IEEE International Conference on Multimedia & Expo., 2005.
【非特許文献２】P. Duygulu, M.-Y. Chen, and A. Hauptmann. “Comparison and Combination of Two Novel Commercial Detection Methods,” in Proceedings of IEEE International Conference on Multimedia & Expo., pp. 1267-1270, 2004.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
特許文献１に記載されているようなリファレンスデータを前提とした技術では、必ず検出対象となる広告映像が既知である必要がある。しかしながら、新規に公開される広告映像も含め、過去全ての広告映像を予め入手・記憶しておき、これと照らし合わせることは事実上不可能であるという問題がある。
【００１６】
一方、リファレンスデータを前提としない技術では、必ずしも検出対象となる広告映像が既知でなくともよい。そのため、前記のような問題は回避できるが、以下の問題がある。
【００１７】
非特許文献１に記載の技術では、広告映像のモデルを利用する。汎用かつ精度の高いモデルを得るためには、全ての広告映像を包含するようなデータを事前に得ておく必要がある。しかしながら、このようなモデルを得るには、大量の広告映像データが必要となるため、実用上の精度が得にくいという問題があった。
【００１８】
非特許文献２の技術では、モデルを用いないため、事前に大量のデータを要求するようなことはない。しかしながら、計算量が問題となる。通常、1時間の映像データには、1,000程度のショットが含まれている。これらの全てのショットの類似度を計算するには、499,500回の類似度計算が必要となる。現在、多チャンネル配信などにより、1時間あたりに配信される映像の時間長はこれよりも遥かに大きく、今後もますます増えていくことが予想される。したがって、このように計算量の多い技術は実用的でない。
【００１９】
特許文献２や特許文献３の技術では、単純に境界の時間間隔が広告映像の長さにあっているかのみによって検出を行う至極単純なものである。そのため、過剰検出（誤検出）が多く、精度が低いという問題点があった。
【００２０】
以上示したように、従来は、大量の映像から効率的かつ高精度に広告映像を検出する映像検出技術は実現されていなかった。
【００２１】
本発明は、前記課題を解決するためになされたものであり、高精度かつ効率的に広告映像を検出することができる映像検出方法、映像検出装置、および映像検出プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
前記目的を達成するため、第１の態様に係る発明は、処理対象となる入力映像から広告映像を検出する映像検出方法であって、前記入力映像の区間構造を解析して部分区間に分割する構造解析処理と、前記部分区間の特徴に基づいて、前記広告映像が含まれる候補区間を１つ以上検出し、その開始時刻および終了時刻を求める候補区間検出処理と、前記候補区間の開始時刻および終了時刻の内部に存在する前記部分区間の画像および音のうちの少なくとも１つを解析し、特徴量を抽出する特徴抽出処理と、前記特徴量に基づいて、前記部分区間を符号によって表現する符号化処理と、前記符号によって表現された１つ以上の部分区間によって構成される符号系列から、再起的に出現する符号系列となる部分区間群を検出する再起符号系列検出処理と、前記検出された部分区間群のうち、所定の条件を満たすもののみを広告映像区間として出力するフィルタ処理とを備えることを特徴とする。
【００２３】
第２の態様に係る発明は、第１の態様に係る発明において、前記構造解析処理で、前記入力映像の切れ目であるカット点を解析し、これらカット点のうち、少なくとも発話区間でも音楽区間でもない点の時刻、および同条件を満たす次の点までの時間長を求めることを特徴とする。
【００２４】
第３の態様に係る発明は、第１の態様に係る発明において、前記特徴抽出処理で、部分領域ごとの輝度平均値、分散、部分領域ごとの色平均値、分散、輝度ヒストグラム、色ヒストグラム、ＭＦＣＣのうちの少なくとも１つを特徴量として抽出することを特徴とする。
【００２５】
第４の態様に係る発明は、第１の態様に係る発明において、前記再起符号系列検出処理で、一定以上の生起回数となる部分符号系列を繰り返し検出することによって再起符号系列を検出し、前記フィルタ処理では、所定の時間長となる再起符号系列のみを出力することを特徴とする。
【００２６】
また、前記目的を達成するため、第５の態様に係る発明は、処理対象となる入力映像から広告映像を検出する映像検出装置であって、前記入力映像の区間構造を解析して部分区間に分割する構造解析部と、前記部分区間の特徴に基づいて、前記広告映像が含まれる候補区間を１つ以上検出し、その開始時刻および終了時刻を求める候補区間検出部と、前記候補区間の開始時刻および終了時刻の内部に存在する前記部分区間の画像および音のうちの少なくとも１つを解析し、特徴量を抽出する特徴抽出部と、前記特徴量に基づいて、前記部分区間を符号によって表現する符号化部と、前記符号によって表現された１つ以上の部分区間によって構成される符号系列から、再起的に出現する符号系列となる部分区間群を検出する再起符号系列検出部と、前記検出された部分区間群のうち、所定の条件を満たすもののみを広告映像区間として出力するフィルタ部とを備えることを特徴とする。
【００２７】
第６の態様に係る発明は、第５の態様に係る発明において、前記構造解析部が、前記入力映像の切れ目であるカット点を解析し、これらカット点のうち、少なくとも発話区間でも音楽区間でもない点の時刻、および同条件を満たす次の点までの時間長を求めることを特徴とする。
【００２８】
第７の態様に係る発明は、第５の態様に係る発明において、前記特徴抽出部が、部分領域ごとの輝度平均値、分散、部分領域ごとの色平均値、分散、輝度ヒストグラム、色ヒストグラム、ＭＦＣＣのうちの少なくとも１つを特徴量として抽出することを特徴とする。
【００２９】
第８の態様に係る発明は、第５の態様に係る発明において、前記再起符号系列検出部が、一定以上の生起回数となる部分符号系列を繰り返し検出することによって再起符号系列を検出し、前記フィルタ部が、所定の時間長となる再起符号系列のみを出力することを特徴とする。
【００３０】
また、前記目的を達成するため、第９の態様に係る発明は、第１乃至４のいずれかの態様における各処理をコンピュータに実行させることを特徴とする映像検出プログラムである。
【発明の効果】
【００３１】
本発明によれば、高精度かつ効率的に広告映像を検出することができる映像検出方法、映像検出装置、および映像検出プログラムを提供することが可能である。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施形態における映像検出装置の構成例を示す図である。
【図２】本発明の実施形態における映像検出装置の動作を示すフローチャートである。
【図３】本発明の実施形態における構造解析処理の一例を示す図である。
【図４】本発明の実施形態における候補区間検出処理の一例を示す図である。
【図５】本発明の実施形態における特徴量抽出位置の一例を示す図である。
【図６】本発明の実施形態における記憶装置に記憶される情報の一例を示す図である。
【図７】本発明の実施形態における再起符号系列検出処理の一例を示す図である。
【図８】本発明の実施形態における記憶装置に記憶される情報の一例を示す図である。
【発明を実施するための形態】
【００３３】
以下、図面を用いて、本発明の実施の形態を詳細に説明する。
【００３４】
図１は、本発明の実施形態における映像検出装置１の構成例を示す図である。この映像検出装置１は、映像データベース１０８に記憶されている映像を入力とし、その入力映像から広告映像を検出して記憶装置１０７に記憶する装置であって、構造解析部１０１、候補区間検出部１０２、ショット特徴抽出部１０３、符号化部１０４、再起符号系列検出部１０５、フィルタ部１０６、および記憶装置１０７を備える。これら処理部は、ＣＰＵ、メモリ、外部記憶装置などからなるコンピュータのハードウェアとソフトウェアプログラムとによって実現される。本実施形態においては、映像データベース１０８は映像検出装置１の外部にあり、相互に通信可能な通信網によって接続されている。また、記憶装置１０７は映像検出装置１の内部にある場合を例示している。もちろん、映像データベース１０８は映像検出装置１の内部にあってもよいし、記憶装置１０７は映像検出装置１の外部にあってもよい。
【００３５】
図２は、映像検出装置１の動作を示すフローチャートである。
【００３６】
まず、構造解析部１０１が、映像データベース１０８に登録された映像に対して少なくともショット解析を含む映像構造解析処理を実行し、映像を意味のある部分区間（以下、単に「区間」という。）に分割する（ステップＳ２０１）。続いて、候補区間検出部１０２が、構造解析部１０１の処理結果を受けて、検出対象となる広告映像が含まれると想定される区間のみを候補区間として検出し、構造解析部１０１の処理結果と共に記憶部１０７に記憶する（ステップＳ２０２）。続いて、ショット特徴抽出部１０３が、映像データベース１０８に登録された映像の候補区間に対して、構造解析部１０１の処理結果として得られるショット毎に特徴量を抽出する（ステップＳ２０３）。続いて、符号化部１０４が、ショット特徴抽出部１０３が抽出したショット特徴量に基づいて、ショットを符号として表現する符号化処理を実行し、記憶部１０７に記憶する（ステップＳ２０４）。続いて、再起符号系列検出部１０５が、記憶部１０７に記憶されたショットの符号系列を読み込み、そのショットの符号系列から再起（２度以上生起）している符号系列を列挙する（ステップＳ２０５）。最後に、フィルタ部１０６が、列挙された再起符号系列から広告映像の条件を満たす系列を抽出し、記憶部１０７に記憶する（ステップＳ２０６）。このようにして、映像検出装置１は、リファレンスデータ、広告映像モデル、ショット間の類似度を用いることなく、大量の映像から高精度かつ効率的に広告映像を検出することができる。
【００３７】
以降、映像検出装置１が実行する各処理の一例について詳述する。以降の各処理は、映像データベース１０８に登録された全ての映像に対して実行してもよいし、特定の一部の映像に対して実行してもよい。映像データベース１０８には、各映像がどのような映像であるのかを示すメタデータが付いているものとしてもよいが、本実施形態では、いかなるメタデータも仮定せずに広告映像を検出するものとする。また、処理対象となる映像は、一般性を失うことなく、一続きのデータであるとする。
【００３８】
〔ステップＳ２０１：構造解析処理〕
構造解析部１０１は、映像データベース１０８に登録された映像に対して構造解析処理を実行する。ここでいう構造解析とは、映像を意味のある区間単位に区切ることであり、本実施形態では、カット点とカット点の間に挟まれるショット、および広告映像区間とその他（映像本編など）の映像区間との境界候補を発見することを目的としている。したがって、少なくともショット、すなわち、画像フレームの切れ目（カット点）を解析する必要がある。また、後者の境界候補を得るために、以下に述べるように、音の切れ目も解析することが好ましい。
【００３９】
まず、ショットの解析には、様々な公知の方法を用いることができる。例えば、参考文献１に記載のショット検出法を用いればよい。
【００４０】
［参考文献１］：Y. Tonomura, A. Akutsu, Y. Taniguchi, and G. Suzuki,“Structured Video Computing”，IEEE Multimedia, vol.1, no.3, pp.34-43, 1994．
このショットの情報のみを用い、カット点を直ちに境界候補としてもよい。しかしながら、これだけでは、必ずしも広告映像区間とその他の映像区間との境界になるとは限らない。通常、映像全体に対して広告映像の区間は疎に分布しているから、むしろ相当数の過剰検出を見込むことになる。そこで、好ましくは音の切れ目も用いて境界候補を絞り込んでいく。この様子を、図３を用いて説明する。
【００４１】
この図に示すように、元の映像３０１に対して得られたショット３０２に基づいて、映像の切れ目を発見することができる。一方で、広告映像区間とその他の映像区間とは映像として連続しておらず、無関係であるから、その境界では必ず音声も不連続になる（途切れる）。そこで、音の切れ目の情報を複合して用いることで、境界候補を絞り込むことができる。
【００４２】
音の切れ目を解析する方法としては、映像中の音声を解析し、例えば、発話区間でも音楽区間でもない音声フレームを切れ目とすることができる。参考文献２などに記載の、公知の音楽・発話区間検出技術を利用して、発話区間および音楽区間を検出することができるので、これらのいずれにも当てはまらない区間を境界とすればよい。
【００４３】
［参考文献２］：K. Minami, A. Akutsu, H. Hamada, and Y. Tonomura，“Video Handling with Music and Speech Detection”，IEEE Multimedia, vol.5, no.3, pp.17-25, 1998．
このようにして得られたショット３０２と発話または音楽区間３０３から境界候補を発見する。すなわち、ショットの境界（カット点）であり、かつ発話区間でも音楽区間でもない区間が候補境界であるから、この結果、３０４の境界候補が得られることとなる。この図に示されるように、音の切れ目の情報を活用することによって、ショット３０２のみによって得られる境界よりも効率的に境界候補３０４を絞り込むことができる。このように解析した境界候補の時刻、および各ショットの開始または終了時刻を候補区間検出部１０２に出力する。
【００４４】
ここで、特許文献２あるいは特許文献３のように、検出された境界候補の間隔が１５秒あるいは３０秒であるような区間を見出し、これを広告映像として出力することもできる。しかしながら、この条件だけでは、広告映像でない区間も過剰検出されてしまい、著しく精度が低いという問題点があった。以降述べるように、本実施形態では、効果的なショット特徴量の抽出と符号化、および効率的な再起符号系列の検出を導入することによって、高精度な検出を実現する。
【００４５】
以上が構造解析処理の処理詳細の一例である。
【００４６】
〔ステップＳ２０２：候補区間検出処理〕
続いて、候補区間検出部１０２は、検出対象となる広告映像が含まれると想定される区間のみを候補区間として検出し、ステップＳ２０１の構造解析処理の処理結果と共に記憶部１０７に記憶する。この候補区間検出処理では、映像全体の中で、広告映像である可能性のある区間を残し、それ以外の区間を間引く。
【００４７】
一般に、広告映像は視聴者の注意を惹きつけるための工夫がなされている。例えば、ショット分割を細かくして画面変化を多くしたり、音に特徴的な効果音や音楽を挿入したりすることが多い。したがって、このような特徴をもたない映像区間は、広告映像である可能性が低い。以下では、この観察に基づく候補区間検出処理の一例を、図４を用いて説明する。この例では、ショット（カット）の頻度に基づいて候補区間を検出する場合について説明している。
【００４８】
図４に示すように、映像と、それに対応してステップＳ２０１の構造解析処理を経て得られたショットが得られている。まず、映像に対して、窓長さＷ、シフトＷＳの窓を設ける。窓長さＷは、窓の大きさ（単位時間範囲）を表す。シフトＷＳは、窓を移動させる時間長を表す。Ｗ、ＷＳは任意の値で指定すればよい。例えば、図４では、Ｗを３０秒、ＷＳを３０秒とした場合を例示している。この窓の単位でショットの数＃Ｓをカウントし、これが一定以上の値をもつ窓に含まれるショットを候補区間として検出する。図４の例では、＃Ｓが４以上の窓に（部分的にでも）含まれるショットを候補区間として検出している。
【００４９】
図４の例では、ＷとＷＳを同じ長さとしているため、窓は互いに重なりがなく、＃Ｓは重複なく計算されている。しかしながら、必ずしもＷとＷＳは同じ時間である必要はない。仮にＷを３０秒、ＷＳを１５秒とした場合には、窓は互いに１５秒ずつ重なりあうことになる。いずれの場合にも、窓長さＷの範囲でこれに含まれるショット数をカウントし、＃Ｓを求めることには変わりはない。ただし、最も近い二つの窓は連続し、間に空白の区間がないことが好ましく、Ｗ≧ＷＳとするのがよい。
【００５０】
窓単位での＃Ｓのみを用いて候補区間を得ると、ノイズの影響によって正確な候補区間検出ができない場合がある。このような場合には平滑化処理、例えばk-近傍法やmajority voting法などのノイズ抑制処理を導入してもよい。
【００５１】
ステップＳ２０１で得られた境界候補の時刻、候補区間となったショットの開始（または終了）時刻と時間長、および各ショットの開始（または終了）時刻が境界候補であるか否かを表す情報を記憶部１０７に記憶する。
【００５２】
以上がステップＳ２０２の処理詳細の一例である。
【００５３】
〔ステップＳ２０３：ショット特徴抽出処理〕
続いて、ショット特徴抽出部１０３は、映像データベース１０８に登録された映像の候補区間に対してショット毎に特徴量を抽出する。 ステップＳ２０２で検出された各候補区間には、それぞれ１つ以上のショットが含まれている。本処理では、その各ショットから、ショットの特徴を表す特徴量を抽出する。抽出する特徴量としては、画像情報として輝度値の統計量、色の統計量などを利用することができる。あるいは、参考文献３に記載のBag-of-Visual-Wordsヒストグラムや、参考文献４に記載のGISTなどを利用してもよい。
【００５４】
［参考文献３］：J. Sivic and A. Zisserman. “Video Google: A Text Retrieval Approach to Object Matching in Videos”, In Proc. International Conference on Computer Vision (ICCV), pp. 1470-1477, 2003.
［参考文献４］：A. Oliva and A. Torralba. “Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope”. International Journal of Computer Vision (IJCV), vol. 42, no. 3, pp. 145-175, 2001.
音情報としては基本周波数や音量、あるいはMel Frequency Cepstrul Coefficients（ＭＦＣＣ）などを利用してもよい。また、前記画像、音に関する特徴量を一つ以上組み合わせて利用しても構わない。
【００５５】
一方で、多くの特徴量を利用する場合、それだけ計算時間を必要とする。特に、大量の映像を処理する場合には、計算時間はできる限り少ない方が好ましい。この場合、例えば、（１）部分領域ごとの輝度平均値、分散、（２）部分領域ごとの色平均値、分散、（３）輝度ヒストグラム、（３）色ヒストグラム、（４）ＭＦＣＣのうち、いずれか一つを特徴量として採用することが好ましい。ここで、部分領域とは、１枚の画像を例えば３×３などに分割した際の各領域のことを指す。これらの特徴量は高速に抽出可能な上、後の検出においても高い精度を発揮する効果的な特徴量である。
【００５６】
また、ショットはそれ自体複数の画像フレームと一定の長さの音信号を含んでいるため、どの画像フレーム、あるいは音信号から特徴量を抽出するかについては任意性をもつ。本実施形態では、ショットを時間軸方向にｎ等分割したとき、それぞれの中間にある画像フレームあるいは音信号から特徴量を抽出する。図５は、２等分割した場合に画像特徴を抽出する位置を示す図である。この例では、１４枚の画像フレームＦ１〜Ｆ１４を含んでいる。２等分割すると、前段の区間には７枚の画像フレームＦ１〜Ｆ７が含まれ、後段の区間には７枚の画像フレームＦ８〜Ｆ１４が含まれる。その中間位置にあるフレームＦ４、Ｆ１１から特徴量を抽出する。ｎの選び方は任意であるが、例えば、計算時間の短縮を図るべく、ｎ＝１としてもよい。この場合には、ショットのちょうど中間１フレームから特徴量を抽出することになる。抽出した特徴量は、ショット特徴量として符号化部１０４に出力する。
【００５７】
以上がステップＳ２０３の処理詳細の一例である。
【００５８】
〔ステップＳ２０４：符号化処理〕
続いて、符号化部１０４は、ステップＳ２０３で抽出されたショット特徴量に基づいて、ショットを符号として表現する符号化処理を実行し、記憶部１０７に記憶する。符号化にはいくつかの方法があるが、ここでは２つの方法を説明する。１つはベクトル量子化に基づく方法であり、もう１つはハッシュを利用する方法である。
【００５９】
ベクトル量子化に基づく方法では、ショット特徴量を符号化するための符号帳を予め用意しておき、これに基づいてショット特徴量を符号化する。符号帳を作成する方法は、さまざまな公知の方法を用いることができるが、例えば、k-means法などのクラスタリング法を適用し、作成する。符号化する際には、各クラスタの中心ベクトルとショット特徴量との距離を計算し、これが最も近い距離にあるクラスタのｉｄを符号として割り当てる。
【００６０】
ハッシュを利用する方法では、例えば以下のような手続きを用いる。まず、ショット特徴量（あるいはその部分）のベクトルをf=(f1, f2, …, fd)と表す。このとき、複数の閾値をf’i (i = 1, 2, …, M)として与え、ベクトルの各次元の値がこの閾値以上であるか否かに基づいて、別の値bに変換する。
【００６１】
例えば、fが３次元で、f=(0.8, 0.1, 0.5)だったとしよう。このとき、閾値を３つ用意し、これをそれぞれf’1 = 0.2, f’2 = 0.5, f’3 = 0.7としたとする。このとき、仮に、f’1未満の値に0001、f’1以上f’2未満の値に0010、f’2以上f’3未満の値に0100、f’3以上の値に1000をアサインするものとする。f1は0.8なのでf’3以上であるから1000、f2は0.1なのでf’1未満であるから0001、f3は0.5なのでf’2以上であるから0100となる。すると、このときのbはb = 100000010100というハッシュ値に変換できる。この値によって符号を得ることができる。この閾値は任意の値を用いてよいが、例えば、各ベクトルの要素の統計量、およびそれを座標変換して得られる値を用いることができる。
【００６２】
以上、ステップＳ２０１〜ステップＳ２０４の処理を終えた時点で、各候補区間に含まれるショットの系列を符号の系列に変換することができるので、これらを記憶部１０７に記憶する。図６に、ステップＳ２０４の終了時点で記憶部１０７に記憶された情報の一例を示す。図６（ａ）に示すように、テーブル６１には、候補区間の情報（候補区間id、 区間開始時刻、区間終了時刻）が記憶されている。また、図６（ｂ）に示すように、テーブル６２には、ショットの情報（ショットid、所属する候補区間のid、ショットの開始時刻、ショットの時間長、ショットが境界候補であるか否かを表す情報、ショットを表す符号）が記憶されている。このように数値ベクトルではなく符号Ａ，Ｄ，Ｅ，・・・などでショットを表せば、従来のようにショットの類似度を計算する場合に比べて大幅に計算量を削減することが可能となる。
【００６３】
以上がステップＳ２０４の処理詳細の一例である。
【００６４】
〔ステップＳ２０５：再起符号系列検出処理〕
続いて、再起符号系列検出部１０５は、記憶部１０７に記憶されたショットの符号系列を読み込み、当該ショットの符号系列から再起符号系列を列挙する。
【００６５】
広告映像は、同じ広告映像が複数のチャンネル、時刻に渡って繰り返し利用される。そこで、全ての候補区間内に再起して出現する符号系列を抽出することによって、広告映像らしい区間を得ることができる。
【００６６】
しかしながら一方で、このような再起符号系列を求める処理は多くの計算時間を要することが知られている。これまでにも、同様の問題を解くいくつかの公知の技術があり、例えば、参考文献５、参考文献６、参考文献７に記載の技術などを用いることができる。
【００６７】
［参考文献５］：特許第３７５９４３８号公報
［参考文献６］：R. Agrawal and R. Srikant. “Mining sequential patterns”, In Proc. International Conference on Data Engineering (ICDE), pp. 3-14, 1995.
［参考文献７］：J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu. “Prefixspan: Mining sequential patterns by prefix-projected growth”, In Proc. International Conference of Data Engineering (ICDE), pp. 215-224, 2001.
前記の技術はいずれも効果的であるが、広告映像の検出に最適化されていない。そこで、本実施形態では、下記の観点を考慮することにより、より効率的な処理を実現する。
【００６８】
（１）連続する符号系列のみを列挙する
（２）広告映像は基準となる長さをもつ（１５秒、３０秒、６０秒など）
深さ優先探索型の参考文献７に記載のPrefixSpanを基本とし、後述のステップＳ２０６のフィルタ処理を合わせ、これを修正した効率的な処理を用いることが好ましい。幅優先探索よりも深さ優先探索の方が、必要となるメモリ量が少なくて済む。以降、この再起符号系列を求める処理の一例について、図７を用いて述べる。
【００６９】
まず、候補区間とそれに含まれるショットの符号を時刻順に並べた符号系列を記憶部１０７から得る。図７では、候補区間１〜４の４つの候補区間が得られており、それぞれ以下の符号系列をもっている。
【００７０】
候補区間１：{A, C, D, E, F, G, A, C, F}
候補区間２：{A, B, C, E, F, G, F, D}
候補区間３：{C, E, F, B, Y, E, B, C}
候補区間４：{A, D, E, H, G, E} 
まず始めに、これらの候補区間に現れる符号数（生起回数）をカウントする。この例の場合、A: 4, B: 3, C: 5, D: 3, E: 6, F: 5, G: 3, H: 1, Y: 1 となる。この中で、一定以上の生起回数をもつ符号を処理対象として記憶しておく。以降、これらの符号に対して順に処理を進めていくことになるが、ここでは、深さ優先探索をベースに処理を実行するものとし、まずは最大の生起回数をもつEに着目する。各候補区間のうち、Eを境にこれよりも後に出現する符号系列により、（部分）候補区間を新たに生成する。図７の例では、候補区間１は、{A, C, D, E, F, G, A, C, F}なので、Eよりも後に出現する区間{F, G, A, C, F}を候補区間１aとする。以降同様に、下記のような新たな（部分）候補区間を生成する。
【００７１】
候補区間１a：{F, G, A, C, F}
候補区間２a：{F, G, F, D}
候補区間３a：{F, B, Y, E, B, C}
候補区間３b：{B, C}
候補区間４a：{H, G, E}
次に、候補区間１a〜4aにおいて、最初に現れる符号の生起回数をカウントすると、F: 3, B: 1, H: 1となる。この中で最大の生起回数となったFに着目し、部分候補区間を生成する。これと同時にFを記憶し、前回記憶したEと合わせて{E, F}という再起符号系列が発見される。
【００７２】
以上の処理を繰り返すことにより、再起符号系列を列挙することができる。この例では、深さ優先探索を前提としているので、まず最大の生起回数となるEやFに着目して処理を実行したが、例えばCなどの他の符号についても同様に処理を進める。各候補区間、あるいは部分候補区間内で、一定以上の生起回数となった符号全てに着目して、同様の処理を繰り返すことが好ましい。
【００７３】
また、ノイズの影響により、同じ広告映像であっても符号系列に揺らぎが出る場合がある。このような場合への対処として、一定数以下の符号が置き換わってもよいことを許容したり、編集距離が一定以下の場合には同じ符号系列であるとみなすように閾値を導入することによって、頑健性を高めることができる。また、同時に、次のような効果を得ることもできる。
【００７４】
すなわち、広告映像は、通常、１５秒版、３０秒版、６０秒版など複数の版が存在し、これらの版を同じものを広告するための広告映像として管理したい場合もある。このような版の違う広告映像は、全く別の映像ではなく、互いに一部が共通しており、いくつかのショットが挿入・削除されたり、置換されたりして制作されている場合が多いため、符号の置換や編集距離によって差異を定量化・吸収することができる。 
以上の処理を経て、発見された全ての再起符号系列区間をフィルタ部１０６に出力する。
【００７５】
以上がステップＳ２０５の処理詳細の一例である。
【００７６】
〔ステップＳ２０６：フィルタ処理〕
最後に、フィルタ部１０６は、列挙された再起符号系列から、広告映像の条件を満たす系列を抽出し、記憶部１０７に記憶する。
【００７７】
日本の場合、広告映像は、１５秒、３０秒、６０秒など、所定の時間長をもっていることが普通である。したがって、抽出された再起符号系列のうち、所定の時間長をもつもののみをろ過（採択）し、最終的に広告映像であるとして検出を行う。検出された再起符号系列の長さは、記憶部１０７に記憶されたショットの時間長を参照することによって求めることができる。再起符号系列の長さを求めると、広告映像の時間長が所定の時間長に当てはまるか否かを判定し、当てはまるもののみを採択する。ただし、この際、ステップＳ２０１で境界候補でないと判定されたショット（カット）で開始、または終端する再起符号系列は採択しない。また、元々の広告映像の時間のずれ、構造解析処理の誤差、丸め誤差などの影響により、必ずしも正確に１５秒などの時間長にならない場合もある。そこで、一定の許容範囲（例えば±0.5秒等）を設けておき、その範囲に収まる時間長の再起符号系列を許容することが好ましい。
【００７８】
図２に示すフローチャートでは、一度全ての再起符号系列を列挙し終えたのち（ステップＳ２０５）、列挙された全ての再起符号系列についてフィルタ処理（ステップＳ２０６）を実行することとしている。しかしながら、実際には、一つ再起符号系列を発見したタイミングでフィルタ処理を適用し、その再起符号系列を採択するか否かを逐次的に判定してもよい。こうすることにより、逐次不要な再起符号系列を忘却することができるため、メモリ使用量の観点で効率化できる。
【００７９】
ろ過された再起符号系列の情報を広告映像区間として記憶部１０７に記憶し、処理を終了する。例えば、テーブル６３には、図８に示すように、開始時刻あるいは終了時刻、時間長、および再起符号系列が記憶される。このような広告映像区間の情報は、そのまま利用者が参照できるように出力しても構わない。
【００８０】
以上がステップＳ２０６の処理詳細の一例である。
【００８１】
以上のように、本発明の実施形態における映像検出装置１では、映像の画像・音情報を解析することにより符号系列を得、再起的に出現する符号系列となる部分区間群を検出するようにしている。そのため、リファレンスデータ、広告映像モデル、ショット間の類似度を用いることなく、大量の映像から高精度かつ効率的に広告映像を検出することができる。
【００８２】
また、構造解析処理Ｓ２０１では、入力映像の切れ目であるカット点を解析し、これらカット点のうち、少なくとも発話区間でも音楽区間でもない点の時刻、および同条件を満たす次の点までの時間長を求めるようにしている。そのため、広告映像とその他の映像を分離する境界を効率的に絞り込むことができる。
【００８３】
また、特徴抽出処理Ｓ２０３では、部分領域ごとの輝度平均値、分散、部分領域ごとの色平均値、分散、輝度ヒストグラム、色ヒストグラム、ＭＦＣＣのうちの少なくとも１つを特徴量として抽出するようにしている。そのため、従来の特徴抽出処理に比べて高速に特徴量を抽出可能な上、高い精度で広告映像を検出することができる。
【００８４】
また、再起符号系列検出処理Ｓ２０５では、一定以上の生起回数となる部分符号系列を繰り返し検出することによって再起符号系列を検出し、フィルタ処理Ｓ２０６では、所定の時間長となる再起符号系列のみを出力するようにしている。そのため、従来の再起符号系列検出処理に比べて極めて効率的に再起符号系列を検出することができる。
【００８５】
なお、再起符号系列検出処理Ｓ２０５では、再起的に出現する符号系列となる部分区間群を検出することとしているが、予め符号系列（リファレンスデータ）が記憶されている場合は、その符号系列と同一の符号系列となる部分区間群を検出するようにしてもよい。すなわち、一度得られた広告映像を別の新たな映像から検出する場合には、既にその広告映像の時間長と符号系列が得られているため、これをリファレンスデータとして記憶装置１０７に記憶しておく。この場合、前記のステップＳ２０１〜Ｓ２０６を全て実行する必要はない。すなわち、少なくともステップＳ２０１、ステップＳ２０３、ステップＳ２０４を実行して映像を符号系列に変換したのち、予め記憶されているリファレンスデータに基づいて、各広告映像の時間長、符号系列と合致する映像区間をスキャンすればよい。このように、一度得られた広告映像をリファレンスデータとして記憶しておけば、より効率的に処理を実行することが可能となる。
【００８６】
以上、本発明の実施形態における映像検出装置１について詳細に説明した。このような映像検出方法は、ソフトウェアプログラムを用いてコンピュータ上で実行できることはいうまでもなく、また、本発明は、説明した実施形態の一例に限定されず、特許請求の範囲に記載した技術的範囲において各種の変形を行うことが可能である。例えば、本発明は、ＩＰＴＶやデジタルサイネージ、ＶＯＤ(Video on Demand) 、地上デジタル放送再送信などといった様々な映像配信・通信サービスに用いることができる。
【符号の説明】
【００８７】
１…映像検出装置
１０１…構造解析部
１０２…候補区間検出部
１０３…ショット特徴抽出部
１０４…符号化部
１０５…再起符号系列検出部
１０６…フィルタ部
１０７…記憶装置
１０８…映像データベース
【図１】
2013009248.tif 000003
【図２】
2013009248.tif 000004
【図３】
2013009248.tif 000005
【図４】
2013009248.tif 000006
【図５】
2013009248.tif 000007
【図６】
2013009248.tif 000008
【図７】
2013009248.tif 000009
【図８】
2013009248.tif 000010