DEIM Forum 2013 D1-5

ビデオストリームからの対象ビデオの短時間検出
千田 佑真†

古賀 久志†

渡辺 俊典†† 電気通信大学大学院 情報システム学研究科 情報システム基盤学専攻〒 182-8585 東京都調布市調布ヶ丘 1-5-1
E-mail: †{chida,koga,watanabe}@sd.is.uec.ac.jp
あらまし

近年，ストリーミングビデオからのオンラインビデオ検索に関する研究が盛んに行われている．これらの研究では，著作権違反の発見などを目的として，編集されたビデオを原ビデオの類似物として検出すること，特にどのフレームからどのフレームまでが類似動画であるかの特定精度に力点を置いたものが多い．これに対して本研究では，ストリーミングビデオにおいて，検索対象のビデオ (クエリビデオ) が流れ始めてから検出されるまでの時間の短縮を目標とする．この技術は，ビデオ検出をきっかけとして次のサービスを呼び出すような状況で有用になる．提案
手法では，ショットごとにハッシュ値を計算し，連続してハッシュ値が複数回一致することを条件としてクエリビデ
オを検出する．この時，ハッシュ値が一致するショット数のしきい値はクエリビデオの長さに依存させず，ストリーミ
ングビデオの特性を学習して適応的に変化させる．しきい値をクエリビデオの長さに依存させない理由は，人間が少数のショットから瞬時に認識対象のビデオを認識する能力を模擬することを意図している．
キーワード

ビデオ検出，オンライン処理，ハッシュ，ビデオストリーミング

Fast Detection of Query Videos from Video Streams
Yuma CHIDA† , Hisashi KOGA† , and Toshinori WATANABE†† Department of Information System Fundamentals, Graduate School of Information Systems,
The University of Electro-Communications
1-5-1 Chofugaoka, Chofu, Tokyo, 182-8585 Japan
E-mail: †{chida,koga,watanabe}@sd.is.uec.ac.jp

1. は じ め に
デジタル放送や youtube に代表されるビデオストリーミング
サービスの普及により，様々な場面でビデオコンテンツを利用点が異なる．

•

ストリーミングビデオからの特徴をリアルタイムで抽出必要がある．

•

検索をリアルタイムで行う必要がある．その際，ストする機会が増えている．そしてビデオコンテンツの量が膨大に

リーミングビデオに含まれる動画の切れ目も検出しなければな

なるにつれ，動画検索技術が重要になっている．一般に動画検らない．

索は人間が付与したタグを用いるタグベースの手法とコンテン

ストリーミングビデオに対するオンライン検索に関する従来研

ツベースの手法に大別されるが，本研究ではコンテンツベース

究では，の動画検索を取り扱う．

（ 1 ） 編集されたビデオを原ビデオの類似物として検出する

コンテンツベースの動画検索に関しては，ビデオアーカイブ能力

内でのオフライン検索についてこれまで盛んに研究されてきた．

（ 2 ） どのフレームからどのフレームまでが類似動画である

例としては，ユーザーが提示した動画ファイルに対するビデオ

かの特定精度．

データベースからの類似動画検索が挙げられる．一方で，近年に力点を置いた研究が多い．これは著作権違反検出への応用とストリーミング中のビデオに対して著作権違反検出やコンテンいう観点では自然である．

ツ管理を行いたいという要求から，ストリーミングビデオに対

これに対して，本研究ではオンライン検索において，検索対するオンライン検索が注目されている．ストリーミングビデオ

象のビデオ (以下クエリビデオと呼ぶ) が流れ始めてから検出に対するオンライン検索ではオフライン検索と比較して以下のされるまでの認識時間の短縮を研究目標とする．この技術は，

ビデオ検出をきっかけとして次のサービスを呼び出すような状ので，注目部分以外が変わった場合でも特徴量が変わらないと況で有用になる．例えば，監視カメラで不審人物を発見したらいう利点がある．しかし，1 枚のフレームから抽出される特徴

警備会社に通報するシステムや，テレビ映像からテレビ CM を量の数が膨大であることと，その分計算時間がかかるという問検出して，それに関する情報をユーザにその場で提示するよう題があることから，リアルタイム性を重視している本研究にはなシステムなどが考えられる．

向いていない．また，類似ではなく同一の動画を検索対象とし

2. 関 連 研 究
2. 1 類似ビデオの検索
Huang[1] らの研究では，オンライン環境においてビデオていることからも，本研究では大域特徴量を用いた．

3. 提 案 手 法
本研究では，複数個の検索対象のビデオ（クエリビデオ）

ストリームから，クエリビデオと類似するビデオの検索を

V1 , V2 , · · · , Vk を用意し, それらを 1 つのストリーミングビデオ行った．クエリとビデオストリームとの重みつき編集類似度

からオンラインで高速検出することを目的とする．ここで高速

WES(Weighted Edit Similarity) を計算することにより，クエとはクエリビデオが流れ始めてから，検出されるまでの時間をリを多少編集した動画も，検出できるようになっている．この短くするという意味である．

研究では類似動画の検出精度を重視しており，例えば，クエリ

基本的に，提案手法ではビデオのショットごとにハッシュ値

ビデオと ξ%(ξ はしきい値) 以上のショットが類似したビデオセを計算し，クエリビデオ Vi とストリーミングビデオ間で連続グメントを類似とみなすようにしている．このやり方では，ク

して複数回 (θi とする）ハッシュ値が一致したことを以って Vi

エリビデオに対する類似ビデオを検索する際には，クエリビデを検出する．多くの従来研究では，この θi は Vi の長さの何割

オの ξ%以上が流れ終わらないと類似ビデオが発見されず，検のように定め，θi を Vi の長さに比例させる．この方法では，出されるまでの時間がクエリビデオの長さに比例する．本研究検出されるまでの時間が Vi の長さに依存し，Vi が長いほど検ではクエリビデオの長さに無関係に，ビデオが流れ始めてから出される速度が遅くなる．しかし，人間がビデオを認識する様

すぐに同一かどうかを判断し，応答時間の短縮を目標として態を鑑みると，人間が認識対象のビデオの長さに関係なく，少いる。

数のショットから瞬時に対象ビデオを認識できている．例えば，

Dohring[3] らの研究では，オフライン環境において，長時間一度見たことのある CM や映画を再び見た時，長さの長い映画録画したテレビ映像に対して，類似シークエンスの検索を行っの方が思い出すのに時間がかかることはない．そこで本研究でた．この研究では，フレームからハッシュ値を計算し，ハッシュは，この人間の能力を模擬して θi は Vi の長さには依存させな値が一致したそれぞれのフレームから前後のフレームを順次見い．高速にクエリビデオを検出するにはハッシュ値が一致するていき，ショットの出現パターンが類似していた場合に，類似

ショットのしきい値 θi を小さく設定する必要がある．一方で，シークエンスとして検出する．特徴として，長い類似シークエ

θi が小さすぎると実際には Vi が流れていないにもかかわらず，ンスでも検出することができるが，シークエンスが長いと F 値

Vi を誤検出 (つまり，false positive) が発生する可能性がある．

が低くなってしまう．

そこで θi をストリーミングビデオの特性を学習して適応的に変2. 2 CM 検出アルゴリズム化させる．具体的には，ストリーミングビデオにおいて Vi が

武 [2] らの研究では，オフライン環境において，長時間録画

流れていないにも関わらず，偶然ハッシュ値が連続して一致す

したテレビ映像に対して，CM を自動発見する技術を提案した．
この研究では，CM の繰り返し流れる性質を利用し，出現のパターンが似た映像断片の集合を取り出せば，それが CM となっていることを示した．特徴として，CM の長さが 15 秒またはる回数を学習する．
提案手法が前提とするストリーミングビデオの条件を以下に
まとめる．

•

Vi が流れていないにも関わらずストリーミングビデオの30 秒であることを用いており，発見対象を CM に絞っている

ショットのハッシュ値が，Vi のショットのハッシュ値とたまたため，一般の動画に応用することは難しい．我々の研究では，

ま連続一致する回数は Vi のショット数より小さい．つまり，Vi

クエリビデオに対して長さの仮定を置かないことや，オンライが流れ終わった後には，Vi が流れたことを正確に判定できる．

ン環境のストリーミングビデオからクエリビデオの検出を試み

提案手法は Vi が流れ終わるのを待たないで，短時間で Vi を検ている点が異なっている．

出することを目的とする．

2. 3 フレームからの特徴量の計算•

ストリーミングビデオに Vi が出現する場合，全く同一

類似動画を検索対象とした研究 [1]，[3]，[5]，[6] やその他多のものが流れるがキャプチャ時エラー等により一部にノイズがくの研究では，フレームからの特徴量の計算に大域特徴量を用のることがある (図 1)．この場合ノイズによりハッシュ値が途いている．大域特徴量とは，フレーム全体から抽出される特徴

中で途切れ，ノイズの前後で Vi が 2 度検出されてしまう可能量であり，フレーム全体の画素値の情報をもとに計算される．

性がある．そこで提案手法では，これが起こらないように対策

また，特徴量がフレーム 1 枚につき 1 つであるため，計算量もをする必要がある．

データ量も少ないという利点がある．これに対して，SIFT[4]提案手法の流れは，最初にクエリビデオをハッシュテーブル

に代表される局所特徴量というフレームの一部から抽出されるに登録するオフライン処理と，実際にビデオストリームからク

特徴量がある．特定の一部分にだけ注目して特徴量を計算する

エリビデオを検索するオンライン処理の 2 つに大きく分けられ3. 1. 2 ショットのハッシュ値の計算
提案手法では，処理の高速化のためにビデオをショット分割
し，ショット単位で比較を行う．ショットというのはビデオの 1
シーンのことで，例えばカメラが切り替わったときや，動きの大きい場面でショットが切り替わる．実際にショット分割する
図 1 クエリビデオ Vi の途中にノイズが乗った場合

際は，連続した 2 枚のフレーム間でハッシュ値を比較し，値が一定値以上変化した場合にショットを分割する．ハッシュ値はる (図 2)．

16 ビットの 2 進数なので変化量の値域は 0〜16 までの範囲であるが，様々な動画に対する予備実験の結果により，ショット
分割を定めるハッシュ値の変化量の閾値は 3 とした．ショットを決定後，ショットのハッシュ値は，そのショットの中で一番出
現回数の多いハッシュ値とした．

3. 1. 3 ハッシュテーブルへ登録
ショットのハッシュ値をインデックスとしてクエリをショッ
ト単位でハッシュテーブルに登録する．つまり，(クエリビデオ

ID，ショット番号) のペアをハッシュテーブルへ登録する．
3. 2 ストリーミングビデオからのクエリビデオの検出
ここでは，ストリーミングビデオからのクエリビデオの検出方法について説明する．大きな流れは以下のようになる．
（ 1 ） ストリーミングビデオからオンラインで最新ショット

S を抽出し，そのハッシュ値を計算する．
（ 2 ） ハッシュテーブルを検索し，S とハッシュ値が一致する (クエリビデオ ID，ショット番号) のペアを見つける．
図2

提案手法の流れ（ 3 ） ステップ (2) で見つかったクエリビデオに対して，マッチング処理を行い当該クエリビデオが検出されたかどうかを判

3. 1 クエリビデオのハッシュテーブルへの登録

定する．

3. 1. 1 フレームのハッシュ値の計算
最初にクエリビデオ Vi (1 <=i<= k) の各フレーム f からハッになっているクエリビデオに対する処理を行う．

シュ値を計算する．また、このハッシュ値の計算方法では，武らのアルゴリズム [2] を利用した．f におけるピクセル (x, y)の輝度値を Ix,y とし，f のフレーム数を n とする．ハッシュ値の計算手順は以下のようになる．まず，以下の式により，輝度∗値 Ix,y を正規化して，正規化された輝度値 Ix,yに変換する．

∑
輝度値の相加平均：µ =

Ix,y
n

√∑
輝度値の標準偏差：σ =
∗
Ix,y
=

Ix,y − µσ(Ix,y − µ)2n(1)（ 4 ） S とハッシュ値が異なるが，現在マッチング処理対象
ステップ (1) ではオンラインでショット分割して，抽出された最新のショットに対するハッシュ値を計算する．これは 3.1
節で述べたクエリビデオのショットに対するハッシュ値の計算と同一手順を行えばよい．
ステップ (2) は単純なハッシュテーブルの検索である．S と同じハッシュ値となる (クエリビデオ ID，ショット番号) のペ
アが複数存在する場合は，ステップ (3) の処理対象となるクエ
リビデオは複数個になる点に注意されたい．

(2)

ステップ (3) では，処理対象のクエリビデオに対して，過去にハッシュ値が一致した回数を 1 増やす．ただし，誤検出を防(3)

次にフレームを縦方向に 4 分割，横方向に 4 分割して 16 分割

ぐため，ハッシュ値が一致したショットは時系列順になっていなければならない．そして，過去に θi 回ハッシュ値が一致した
クエリビデオ Vi が発生すれば，Vi を検出する．

し，各ブロックから正規化した輝度の相加平均を計算する．こステップ (4) では，ストリーミングビデオ中で Vi が流れていの結果，f に対して，16 次元特徴ベクトルが生成される．輝度るときに，Vi が流れ終わるか，またはノイズが発生するとハッ値を正規化することにより，画面全体の明るさの変化にロバス

シュ値が一致しなくなる．このときハッシュ値が連続して一致トな特徴となっている．そして，特徴ベクトルの各要素と，全しない回数を 1 増やし，その回数がしきい値 λi を超えたこと

ブロックの相加平均を比較することにより二値化し，f を 16を以って，現在マッチング途中のクエリビデオに対する処理をビットの二進値特徴として表現する．これが f のハッシュ値と行う．また，Vi が流れていないのに過去にたまたまハッシュ値

なる．

が一致してマッチング処理対象になった Vi に対して、その後
ハッシュ値が一致しなかった場合もこの (4) で処理される．
上記の処理を実現するために，各クエリビデオ毎に 3 状態からなるステートマシンを設ける．そして，以下の 3 つの状態をれは典型的にはストリーミングビデオ内で，Vi が流れていない

設定する．

にも関わらずたまたまハッシュ値が一致した場合に相当する．

•

マッチング中ではない

偶然，ハッシュ値が一致することで「マッチングでない」から•

マッチング中「マッチング中」に状態遷移することはありえるが，偶然ハッ•マッチング確定

シュ値が一致する事象が θi 回以上起きる確率は低いので，「マッ

例えば，Vi が「マッチング中ではない」という状態は，過去にハッシュ値が一致していないので，マッチング中でない状態

チング確定」状態に遷移せず誤検出とならない．

3. 2. 1 しきい値 θi の決定アルゴリズムである．
「マッチング中」という状態は，過去にハッシュ値が一ストリーミングビデオ内でクエリビデオ内に流れていないの致したが，まだ θi 回ハッシュ値が一致していない状態である．

にもかかわらず．たまたまハッシュ値が連続一致する回数は，「マッチング確定」という状態は，過去にハッシュ値が θi 回以

クエリビデオのハッシュ値とストリーミングビデオのハッシュ上一致し，ストリーミングビデオから Vi が検出された状態で値によって決定される．したがって，θi はクエリビデオ Vi 毎ある．図 3 にクエリの 3 状態の遷移の様子を示す．状態間の遷に設定し，ストリーミングビデオの特性を学習して適応的に変移は，図 3 に示すように以下の 4 種類がある．

化させる．

θi はストリーミング動画中で Vi が流れていないのにショッ
トのハッシュ値が連続して一致する個数（以下，ハッシュ値一
致偶然個数と呼ぶ）を学習することで決定され，そのような事象が発生した時に更新される．3 章冒頭で述べた前提条件より，ハッシュ値一致偶然個数は Vi のショット数より小さいので，最長でも Vi の長さだけ時間経過後に，このような事象が発生したことを検知できる．具体的な θi の決定アルゴリズムは次のようになる．
ストリーミングビデオの特性が時間の経過に応じて変化することに迅速に対応するため，過去のハッシュ値偶然一致個数の最近の値を重視した加重移動平均 µw を求める．ここでは，例
図3

クエリの状態遷移図

えば，TV 映像において，スポーツ番組が流れている時間帯とCM が流れている時間帯でストリーミングビデオの特性が変化
1⃝
ハッシュ値が始めて一致する．

するような状況を想定する．そして，ハッシュ値偶然一致個数2⃝
過去に時系列順にハッシュ値が θi 回以上一致する．

のばらつきに対応できるよう，標準偏差を µw に加算した (式3⃝Vi のショットが最後に検出されてから，λi 回ハッシュ(4))．

値が一致しない．
4⃝
Vi 以外のクエリビデオがマッチング確定する．あるいは Vi のショットが最後に検出されてから，λi 回ハッシュ値が一致しない．
1
2
3 が，通常の Vi が検出される流れである．初めて⃝→⃝→⃝Vi のショットが検出されると，Vi の状態が「マッチング中では•µw : 過去に偶然ハッシュ値が連続して一致した個数の加

重移動平均

•

σw : 過去に偶然ハッシュ値が連続して一致した個数の標

準偏差

θi = µw + σw

(4)ない」から「マッチング中」に変化する．その後，Vi のショッ

4 章の実験では，加重移動平均，標準偏差とも過去 3 回のハットがストリーミングビデオから検出される度に，ハッシュ値がシュ値偶然一致個数 (x1 , x2 , x3 とする) を用いて実装した．特一致した回数が増加し，θi を越えると状態が「マッチング中」に µw = x1 +2x62 +3x3 とした．

から「マッチング確定」に変化し，Vi が検出される．

しきい値 θi の計算タイミング「マッチング確定」状態では，時系列順にその Vi のショット

θi はクエリビデオ Vi が流れていないのに，たまたまハッシュが検出される限りその状態が継続される．一方で，ショットが値が一致したときに学習して更新される．具体的には以下の 2検出されない回数が λi を超えると，状態を「マッチング中でつの事象のいずれかが発生したときに更新する．

はない」に戻してマッチング終了となる．Vi がストリーミング（ 1 ） Vi が「マッチング中」から「マッチング中ではない」

ビデオにおいて流れ終わった時にこの状態遷移が起きる．

に戻ったときVi が「マッチング中」状態において，Vi 以外のクエリビデオ（ 2 ） Vi が「マッチング確定」から「マッチング中ではない」

がマッチング確定状態に遷移した時，「マッチング中ではない」に戻り，かつマッチしたショット数の合計が Vi の総ショット数

4 これは 1 個のストリーミングビデオにおいに戻る．(遷移 ⃝)の 50%未満の場合て 2 つのクエリビデオが全く同時に流れるのは不可能であるか(1) はまさにストリーミングビデオと Vi がたまたまハッシュ値

らである．さらに，ショットが検出されない回数が λi を越えたが一致した場合に，「マッチング確定」にならなかったときに相4 こ場合も同様に「マッチング中ではない」に戻る．(遷移 ⃝)当する．(2) は θi が小さいために，クエリビデオが流れていないのに誤検出が起きた場合である．マッチしたショット数が少り，性能評価を行った。次に、複数のテレビ CM をクエリビデ

なかったことから，誤検出したことを認識して θi を更新してオ，テレビ番組を長時間録画したものをストリーミングビデオ

いる．

として，現実の環境で実験を行った．

4. 1 人工動画での実験

3. 2. 2 しきい値 λi の決定アルゴリズム
ストリーミングビデオ中でクエリビデオ Vi が流れているとこの実験では，ストリーミングビデオ中でクエリビデオ Vi

きに，ハッシュ値が連続で一致しなくなるケースは以下の 2 通が流れていないにも関わらず，たまたま Vi とハッシュ値が一りである．

致することがあった場合を想定した人工動画を作成し，しきい（ 1 ） クエリビデオ Vi が流れ終わった場合

値 θi の性能評価を行った．評価項目は以下の 2 つである．

（ 2 ） クエリビデオ Vi の途中にノイズが乗った場合(1) は通常のクエリビデオ Vi の検出であり，λi 回 Vi のショッ•

誤検出の発生回数•

Vi の認識速度

トが検出されないとマッチング終了となる．(2) はビデオのキャ

両者はトレードオフの関係にある．前者を減らすには θi を大プチャ時のエラーにより，クエリビデオ Vi の途中にノイズがきく設定すれば良い．しかし，θi が大きいと Vi が実際に流れ乗った場合に発生する．このときのノイズの長さを L とするた時に検出するまでの時間が長くなる．したがって，θi は誤検と，λi < L の場合，1 つの Vi を 2 回検出してしまう．よって，出を抑えられる最小の値になっていることが望ましい．

λi > L となっている必要がある．しかし λi が L に対して必要

実際のストリーミングビデオでは，たまたまハッシュ値が一以上に大きいと，異なる 2 つのクエリビデオ Vi がストリーミ

致する動画の出現パターンには，規則性があると考えられる．

ングビデオ中で並んだときに，後の Vi の検出が遅くなること

例えば，スポーツ番組やニュース番組など，テレビ番組の種類

や，「マッチング中」状態にあるクエリビデオ Vi の数が増える

によってハッシュ値の一致しやすさが異なると考えられる．そことから，処理が重くなるというデメリットがある．よって λi

こで人工動画では，周期的にハッシュ値の一致が起きやすい期

は L に対して適応的に決定する必要がある．

間と起きにくい期間を作った．

λi は，ストリーミングビデオ中で Vi が流れている時に、ノ人工動画は，ベースとなるストリーミングビデオを用意し，イズにより Vi のショットが検出されなくなり，その後再び Vi

これにクエリビデオ Vi とダミービデオを複数を挿入する．ダのショットの続きが検出され始めたときの，ノイズによりハッミービデオは，Vi とハッシュ値が一致するが，Vi とは異なる

シュ値が変化したショットの長さを学習することで決定され，ものである．したがって，ストリーミングビデオが流れたとき，そのような事象が発生した時に更新される．

Vi だけが検出され，ダミービデオが検出されなければ最良の結ノイズの長さはキャプチャ時のエラーに依存し，時刻には依果となる．ダミービデオは，Vi とハッシュ値が一致するショッ

存せずハードウェアの特性によって決定される．したがって，

ト数を指定した上で作成する．ハッシュ値が一致するショット

ノイズの分布は正規分布に従うと仮定し，正規分布の平均と分数の上限は Vi のショット数の 50%とした．したがって，Vi がダミービデオであるかは，(Vi が流れ終わった後には) 一致する

散を学習することにした．

•µv : 過去に Vi を検出中にノイズによりハッシュ値が変ダミービデオは Vi をもとにして，ハッシュ値だけが同じに化したショットの長さの平均•

ショット数から判定できる (3 章の前提条件参照)．

σv : 過去に Vi を検出中にノイズによりハッシュ値が変なるように白黒のタイル状の模様の動画を作る．図 4 にクエリ化したショットの長さの標準偏差ビデオのフレームに対応するダミービデオのフレームの例を示とすると，λi は式 (5) により計算される．

す．提案手法では，フレームのハッシュ値は 16 個の部分ブロッλi = µv + 2σv(5)クの相対的な輝度値を 0(暗い) または 1(明るい) で表したもの
なので，元のフレームの暗い部分が黒になっている．

4 章の実験では，移動平均，標準偏差とも過去 9 回のハッシュ値が変化したショットの長さ (x1 , · · · , x9 とする) 用いて実装し9た．特に µv = x1 +···+xとした．
9λi の計算タイミング
λi は以下の場合に計算される，このときにハッシュ値が変化
したショットの長さが学習される．

•

Vi が「マッチング中」または「マッチング確定」状態に(a) クエリビデオ

あるとき，ハッシュ値が一致しなくなり，一定時間が経過しな
いうちに再びその続きのショットが検出された場合(b) ダミービデオ

図 4 ハッシュ値が同じフレーム

この一定時間は，ハッシュ値が一致しなくなった時点から Vi の
長さ分の時間とする．

4. 実

験

最初に，現実で起こりうるパターンを想定した人工動画を作

このようにして作成した長さの異なるダミー動画をベースとなるストリーミングビデオに挿入していく．
以下に作成した人工ストリーミングビデオの構成を示す．

•

ベースビデオ：1 時間の動画 ×1 個

図5

ダミーの長さに揺らぎのある場合•

クエリビデオ Vi：テレビ CM(12 秒，37 ショット)×6 個の項を加えたためである．分散の項によりハッシュ値の一致し•ダ ミ ー ビ デ オ：Vi か ら 作 成 し た ショ ット 数

やすさが増大すると θi が速く上昇する．しかし，逆に，分散の(1,2,3,4,5,14,15,16,17,18) が異なるビデオ ×54 個

項の影響で，ハッシュ値が一致しにくくなる場合は θi の下がり

1 時間のベースビデオに対して 1 分周期でダミービデオを方が遅く，Vi が検出されるまでの時刻が，実際のダミー動画の挿入した．ダミービデオにおいて Vi とハッシュ値が一致する

長さと較べて相対的に遅くなってしまっている．ハッシュが一

ショット数は，10 分周期に大きくなったり，小さくなったりす

致しにくく変化する場合の検出時間の短縮が今後の課題である．

る．これが上述したハッシュ値の一致が起きやすい期間と起き

4. 2 現実動画での実験にくい期間に対応する．ただし，それぞれの期間内でもダミー提案手法のアルゴリズムが現実動画でも正しく動くかどうかのハッシュ値が一致する長さは一定ではなく多少の揺らぎがあを検証するために，テレビ放送を録画したものをストリーミン

る．また，10 分おきに Vi を挿入した．

グビデオとして実験を行った．以下に使用したビデオの構成と実験結果

ファイル情報 (表 1，表 2) を示す．

この動画に提案手法を適用した結果を図 5 に示す．このグ
ラフでは横軸が時刻，縦軸がショット数である．ダミー動画でハッシュが一致するショット数，θi をそれぞれ赤，青の棒で表す．また，クエリは緑色の棒で示されている．

•

ストリーミングビデオ：テレビ放送 (アナログ) を 24 時

間録画した動画 ×1 個•

クエリビデオ Vi (1 <=i<= 5)：ストリーミングビデオから抽出したテレビ CM×5 個

赤，青の棒の長さを比較すると，まず全体的には，ダミー動

表1画の長さに応じて θi が適応的に変化しており，ストリーミング
ビデオの性質に応じて誤検出が起きない範囲で短い時間で Vi使用したビデオのファイル情報
長さ

サイズ

(sec)

(pixel)

フレームレート ショット数(fps)

24hour 720*480

29.97

43758

を検出することができていることがわかる．赤の棒の長さが青ストリーミングビデオの棒の長さ (θi ) より長い時，ダミー動画で θi 個以上のショッ

クエリビデオ V1

12

720*480

29.97

37

クエリビデオ V2

14

720*48029.97

30

クエリビデオ V3

15

720*480

29.97

23

り，赤の棒の長さが青の棒の長さより長い誤検出は，3 回起き

クエリビデオ V4

30

720*480

29.97

33ている．ダミー動画は 54 個含まれているので，誤検出の割合

クエリビデオ V5

15

720*480

29.97

25

トのハッシュ値が一致したことになり，誤検出となる．図 5 よ3は 54× 100 =5.6%であった．誤検出はダミー動画のハッシュ値が一致しにくい区間から一致しやすい区間に切り替わった時に 1 回のみ発生している．ハッシュ値が一致しにくい区間では適応的に学習した結果，θi が小さくなっているので，ハッシュ表2

ストリーミングビデオ中に含まれるクエリビデオ Vi の数

V1

V2

V3

V4

V5

10

20

2

2

6

値が一致しやすくなった直後に誤検出が起きるのは仕方がない．
しかし，1 度誤検出と判定すると，次からは θi が急激に大きくなった結果，誤検出は発生していない．
しきい値 θi は過去 3 回分の加重移動平均をとっているのにも関わらず，誤検出が 1 回しか発生しない理由は，式 (4) で分散

ただし，アナログ放送の動画ではフレームの上下に黒帯が入っているので，これを除外するため上下高さ 60 ピクセルず
つカットして使用した．ファイルとして録画したビデオを再生しながら処理して，オンライン環境を検証した．提案手法の可表 4 Vi の検出結果 (可変しきい値)

変しきい値 θi と λi の効果を検証するため，θi と λi を固定値にした場合と，可変にした場合とでそれぞれ Vi の検出精度と

V1

V2

V3

V4

V5

Vi 全体

検出数

11

23

3

4

8

49

検出速度の比較を行った．

正解

10

20

2

2

6

40

誤検出

1

3

1

2

2

9

適合率 P

0.90

0.87

0.67

0.50

0.75

0.82

検出精度の評価は再現率と適合率，および F 値によって行った．適合率 P，再現率 R，F 値はそれぞれ以下の式で表わさ
れる．

P =

検索結果のうち正しく検出された Vi の数検出された Vi の数

1

1

1

1

1

1

F値

0.95

0.93

0.80

0.67

0.86

0.90

(6)
れている Vi はすべて検出することができ，適合率は 0.82 と固検索結果のうち正しく検出された Vi の数
R=
ストリーミングビデオ中に含まれる Vi の数

F =

再現率 R

(7)

2P R
P +R

(8)

Vi の検出速度の評価は，ストリーミングビデオ中で Vi が流定しきい値を利用した場合よりも改善された．特に V2 に関しては，可変しきい値 λi を適用したことにより，F 値が 0.56 から 0.93 へ大きく改善された．V4 以外は多少精度が改善されたがほとんど変わらない結果となった．誤検出の原因は大きく分けて以下の 3 つに分類された．

れ始めてから Vi が検出されるまでにかかったショット数で評価（ 1 ） クエリビデオ Vi の途中にノイズが乗って，1 つの Viする．ただし，誤検出だったときはカウントせず，正しく検出に対して 2 回 Vi が検出された場合

された場合のみで評価する．

（ 2 ） クエリビデオ Vi のバージョン違いが流れた場合

4. 2. 1 固定しきい値での実験（ 3 ） しきい値 λi が大きい時に，断続的にハッシュ値が偶最初に，Vi 状態に影響するしきい値 θi と λi をそれぞれ固定然一致することが繰り返され，Vi が流れていないのに Vi を検値 3 として実験を行った．検出速度に関しては，θi が固定値と出した場合なっているため評価は行っていない．Vi の検出結果は以下の表(1) はストリーミングビデオの初期の学習段階の誤検出であり，のようになった．

ストリーミングビデオの始めの方で発生していた．(2) は CMのバージョン違いによるもので，Vi の最後に流れる企業のロ

表 3 Vi の検出結果 (固定しきい値)

ゴなどでショットが一致してしまいそれが誤検出につながった．

(3) は Vi とまったく無関係のショットがたまたま複数一致した

V1

V2

V3

V4

V5

Vi 全体

検出数

12

51

4

3

9

79

場合に発生していた．この対策として，λi を学習する条件とし

正解

10

20

2

2

6

40

て，Vi の長さより短い範囲ではなく，現在のマッチング中の Vi

誤検出

2

31

2

1

3

39

適合率 P

0.83

0.39

0.50

0.67

0.67

0.51

のショット番号から最終ショットまでより短い範囲にすること

再現率 R

1

1

1

1

1

1

F値

0.90

0.56

0.67

0.80

0.80

0.68

などが考えられる．
全体的には固定しきい値の場合と比べて，F 値が 0.68 から0.90 に増加したので，可変しきい値を導入したことによる効果
結果から，再現率は 1 となり，ストリーミングビデオに含まれている Vi はすべて正しく検出することができたが，誤検が確認できた．
検出速度

出が多く，適合率は 0.51 となった．特に V2 については適合率

正解の Vi が検出されたとき，Vi が流れ始めてから何ショッ

0.39 とが低くなっていた．この原因は，クエリ検出後にノイズトで検出したかで，検出速度を評価した．図 6 に Vi ごとに検が乗ってマッチングが終了し，ノイズ後のクエリビデオの続き出されるまでにかかったショット数を比較した．この結果ほとに対してもクエリを検出してしまったためであった．

んどの Vi は θi の最小値 3 で高速に検出されているが，Vi ごと

その他の誤検出の例として，Vi とまったく無関係のショットにみるとそれぞれで検出されるまでのショット数に偏りがあるがたまたま連続で一致して Vi が検出されてしまうことがあっことがわかった．特に V1 がマッチ確定までの時間が遅く，逆にた．例えば，白い背景に企業のロゴが入った物や，全体が黒でV2 はマッチ確定までの時間が速い傾向が見られた．したがって塗りつぶされたフレームにおいてハッシュ値が一致することがVi によってたまたまハッシュ値が一致する確率や，ノイズの大多かった．

きさが異なるということなので，このことから，提案手法で Vi

4. 2. 2 可変しきい値での実験ごとにしきい値を設定したことは，ストリーミングビデオ中で次に，提案手法をそのまま用いて，ストリーミングビデオのの Vi の特性に合わせて効率よく Vi を検索できていると考えら特性を学習して適応的に変化するしきい値 θi と λi が，クエリ
ビデオ Vi の検出に実際どれほど効果があるのかを検証した．Viの検出結果は以下の表のようになった．
結果から，再現率は 1 となり，ストリーミングビデオに含まれる．

5. まとめと今後の課題
本研究ではオンラインのビデオストリームに対して，クエリとして用意した複数のビデオをリアルタイムで高速に検索する

図 6 Vi ごとの検出速度の比較手法を提案した．人間が過去に一度見たことのあるビデオをビ

クエリビデオ内にノイズが乗っているケースを除いて，大部分

デオの長さに依存せず瞬時に認識検出できる能力があることかのケースでは 3〜数ショットで高速に検出することができた．

ら，しきい値 θi を Vi の長さに比例させないことで、より人間が実際目で見たときの判断に近い検索が可能となった．また、ストリーミングビデオの特性を学習することで、その場面に合わせてしきい値を変化させ，誤検出の割合を小さくすることができた．特にストリーミングビデオ中でたまたまクエリビデオが流れていないにもかかわらずハッシュ値が一致した場合や，逆にクエリビデオの中でノイズが入って部分的にハッシュ値が変化した場合でも検出できるように 2 種類の可変しきい値を設定した．
人工動画の実験では，可変しきい値の変化の様子を人工のス
トリーミングビデオを作成して評価した．この実験から，検出速度に関しては，ストリーミングビデオの特性に応じて誤検出が起きない範囲で短い時間で Vi を検出できることが確認できた．また，検出精度に関しては，最初の学習期間では誤検出が発生してしまうものの，それ以降は誤検出が起きずしきい値が適応的に変化することが確認できた．また，しきい値に分散の項を足しているので，しきい値の上がるスピードは速いが下がるのが遅くなっていた．そこでストリーミングビデオの長期的な特性を学習したり，しきい値の上げる方と下げる方で計算方法を変えるなどの対策が考えられる．
現実動画での実験では再現率は 1 となり，ストリーミングビ
デオ中に含まれる Vi はすべて検出することができた．適合率も可変しきい値を適用することで，0.51 から 0.82 に改善され，F値は 0.9 となった．適合率が 1 にならない理由は，初期の学習期間や CM のバージョン違いによるものと，クエリの長さよりも短い範囲でハッシュ値がたまたま一致することが原因であった．よって，後者の場合は λi を学習する条件として，Vi の長さより短い範囲ではなく，現在のマッチング中の Vi のショット
番号から最終ショットまでより短い範囲にするなどによって対策をしていきたい．検出速度は Vi によって異なるが，一部の謝辞 本研究は科学研究費基盤研究（C）課題番号 24500111の支援を受けて行った．
文

献[1] Zi Huang, Heng Tao Shen, Jie Shaoy, Bin Cuiz, XiaofangZhou, Practical Online Near-Duplicate Subsequence Detection , IEEE Transactions on Multimedia, Vol.12, No.5,
pp.386-398, 2010[2] 武小萌, 佐藤真一, 時間的共起ハッシュアルゴリズムに基づいた
CM 検出・同定 , 画像の認識・理解シンポジウム (MIRU2010)[3] Ina Dohring, Rainer Lienhart, Mining TV Broadcasts for
Recurring Video Sequences , Conference on Image andVideo Retrieval, pp.327-356, 2009[4] D. G. Lowe, Distinctive Image Features from ScaleInvariant Keypoints , Journal of Computer Vision, pp91110, 2004.
[5] Klaus Schoeﬀmann, Laszlo Boeszoermenyi, Video Sequence Identiﬁcation in TV Broadcasts , International Conference on Multimedia Modeling, pp129-139, 2011
[6] Xiangmin Zhou, Lei Chen, Monitoring Near Duplicates
Over Video Streams , ACM Multimedia, pp521-530, 2010