高田 佳佑
2008年 2月 7日
近年,Web上ではかつてないほど膨大な量の動画を閲覧できる状況になっている. しかしながら,それらの検索システムについてはテキストベーストなものが利用されているのが現状である. この場合,ユーザによって付加されたタグと呼ばれるキーワードを基に検索を行なうのが一般的であるが, 付加するタグの選択はユーザの主観に依存するところが多く, 検索結果には様々な動画が存在してしまっている.
これらタグだけでは判別できない内容の差異を認識するためには, 動画自身の特徴量を考慮することが重要であり, これらの研究は TRECVID [1]を中心に盛んに進められている. 本研究では,これらの特徴量の比較基準に Earth Mover's Distance を利用し, キーフレーム数の異なる動画間での類似度算出を可能とすることで, キーフレームごとの特徴量を基にした類似動画検索を試みる. また,YouTube [2]から動画を収集し,評価実験を行なうことで,その有効性を示す.
画像間の類似度を算出するための基準として, Rubner らによって提案された Earth Mover's Distance (EMD) [3]があるが, Peng らは,これを動画のクリップ間の類似度を算出するための基準として利用することで, ショット数が異なるクリップ間の類似度算出を可能とした[4]. 本研究では,Peng らの手法を参考に,クリップ分割やキーフレーム抽出を簡略化する一方で, 特徴量を追加するなどして改良を加えた手法を利用する.
本研究の検索手法の概要は,次のようになっている.
以下,要点の詳細を説明する.
本研究では,以下に示す4つの特徴量を利用する. なお,それぞれの値はになるように正規化を行なう.
抽出した特徴量を基に,全動画間の EMD に基づく類似度の算出を行なう. 本研究では,キーフレームの特徴量でシグネチャを作成し, そのキーフレームが含まれるシーンの長さを各シグネチャの重みとすることで,EMD に基づいた類似度を算出する. 類似度の値はで算出され,2つの動画が類似しているほど1に近い値をとる.
算出した類似度を基に類似動画の検索を行なう. 本研究では,2種類の検索方法を利用する.
ランキング検索とクラスタリング検索それぞれの方法について,評価実験を行なった.
実験には,YouTubeから 「baseball」「basketball」「soccer」「tennis」「volleyball」の5つのタグで収集した 合計500個(総再生時間約38時間)の動画データベースを利用した. 動画は各タグについて100個ずつ用意されており,それぞれ20個の正解動画と,残り80個の不正解動画から構成されている. なお,本研究では試合動画を正解動画,それ以外を不正解動画として,それぞれの動画を収集した.
各正解動画について,同一タグの残り全99個の動画に対してのランキング検索を行ない,
それぞれのタグの全正解動画に対する平均適合率(AP: average precision)と,
その平均値(MAP: mean average precision)を求める.
平均適合率とは,検索結果における各再現率(recall)レベルでの適合率(precision)の平均値であり,
(1) | |||
実験結果を図3に示す. 最も結果が良かったのは「volleyball」で全特徴量を利用したときで,平均適合率はとなった. また,MAPでもという数値を残せており, 本手法の有効性を示すことが出来たものと考えられる.
同一タグの動画をクラスタリングし,各グループのF値(F-measure)を求める.
F値とは,適合率と再現率の調和平均であり,
(2) | |||
最も結果の良かった,グループ間の類似度算出に群平均法を用いた場合の結果と, 対象の全動画を一度に表示した場合(全表示)のF値を図4に示す. 結果が最大となったのは「volleyball」において閾値がのときで, F値はとなった. 全表示の場合のF値はであり,クラスタリング検索を行なうことにより, 類似動画を有効的に表示できたことが見てとれる.
「soccer」と「volleyball」の結果が良かったのは, どの正解動画もコートの色が似通っていたためと考えられる. 一方で,「tennis」では試合によってコートの色が全く異なり, 色特徴よりもオプティカルフローの方が良い精度を残した. このように,「sports」という同一カテゴリ内においても重要な特徴量は一意に決定できず, どのような特徴量をどのように利用するかは難しい問題である.
本研究では,EMD を用いた類似Web動画の検索手法について説明し, 2種類の検索方法を用いて実装を行なった. YouTube から収集した実験データに対する評価実験の結果, 条件によっては,どちらの方法も非常に有効であることが示された. 今後は,新たな特徴量を追加していくと共に, キーフレームの抽出方法やクラスタリング手法を改善することについても検討していきたい. 加えて,もっと様々なタグに対しても評価実験を行ない,それらの結果を他手法と比較することで,客観的な評価も行なっていきたい考えである.