Earth Mover's Distance を用いた類似 Web 動画検索

高田佳佑

2008年 2月 7日

1 はじめに

近年，Web上ではかつてないほど膨大な量の動画を閲覧できる状況になっている．しかしながら，それらの検索システムについてはテキストベーストなものが利用されているのが現状である．この場合，ユーザによって付加されたタグと呼ばれるキーワードを基に検索を行なうのが一般的であるが，付加するタグの選択はユーザの主観に依存するところが多く，検索結果には様々な動画が存在してしまっている．

これらタグだけでは判別できない内容の差異を認識するためには，動画自身の特徴量を考慮することが重要であり，これらの研究は TRECVID [1]を中心に盛んに進められている．本研究では，これらの特徴量の比較基準に Earth Mover's Distance を利用し，キーフレーム数の異なる動画間での類似度算出を可能とすることで，キーフレームごとの特徴量を基にした類似動画検索を試みる．また，YouTube [2]から動画を収集し，評価実験を行なうことで，その有効性を示す．

2 方針

画像間の類似度を算出するための基準として， Rubner らによって提案された Earth Mover's Distance (EMD) [3]があるが， Peng らは，これを動画のクリップ間の類似度を算出するための基準として利用することで，ショット数が異なるクリップ間の類似度算出を可能とした[4]．本研究では，Peng らの手法を参考に，クリップ分割やキーフレーム抽出を簡略化する一方で，特徴量を追加するなどして改良を加えた手法を利用する．

3 提案手法

本研究の検索手法の概要は，次のようになっている．

$\begin{table}\begin{center} \begin{tabular*}{79mm}{cp{60mm}} \hline\hline \multi... ...を基に類似動画を検索する． \\ \hline\hline \end{tabular*}\end{center}\end{table}$

以下，要点の詳細を説明する．

3.1 特徴量抽出

本研究では，以下に示す4つの特徴量を利用する．なお，それぞれの値はになるように正規化を行なう．

3.1.0.1 0. 色特徴

キーフレームを4分割し，それぞれについてカラーヒストグラムを作成する．色空間は L*a*b* 表色系を利用し，次元数は $5\times3\times3=45$ 次元とする．

3.1.0.2 i. 音特徴

キーフレームの前後合計1秒間の音声の大きさを解析し，それらの平均値を抽出する．

3.1.0.3 ii. オプティカルフロー

キーフレームの前後合計1秒間について，全隣接フレーム間のオプティカルフローを算出し，それらの平均値を抽出する．オプティカルフローの算出にはLucas-Kanade法[5]を利用する．

3.1.0.4 iii. キーフレームポジション

動画の中でのキーフレームの再生位置を，始めを0，終りを1として，

の特徴量として抽出する．

3.2 類似度計算

抽出した特徴量を基に，全動画間の EMD に基づく類似度の算出を行なう．本研究では，キーフレームの特徴量でシグネチャを作成し，そのキーフレームが含まれるシーンの長さを各シグネチャの重みとすることで，EMD に基づいた類似度を算出する．類似度の値はで算出され，2つの動画が類似しているほど1に近い値をとる．

3.3 類似動画検索

算出した類似度を基に類似動画の検索を行なう．本研究では，2種類の検索方法を利用する．

3.3.0.1 0. ランキング検索

クエリ動画に対しての類似度を基に，結果をランキング形式で表示する(図1)．特徴量の重み付けは，ユーザが行なえるものとする．

**図 1:** =75mm ランキング検索の例(一番上がクエリ動画であり，以下類似度の降順に検索結果が並ぶ)
$\includegraphics[clip,width=1.00\hsize]{eps/similarity_ranking.eps}$

3.3.0.2 i. クラスタリング検索

検索対象の動画を，階層的クラスタリングを行なうことで複数のグループに分割し，動画を分類した状態で表示する(図2)．本研究では，類似度の大きいものから順にグループ化していき，その類似度が閾値より小さくなるまで続けることでクラスタリングを行なう．グループ間の類似度の算出には群平均法(group average method)，最短距離法(nearest neighbor method)，最長距離法(furthest neighbor method) [6]の3つを利用し，ユーザが選択できるものとする．

**図 2:** =75mm クラスタリング検索の例(各画像が各動画のサムネイルであり，動画数の降順に分類結果が並ぶ)
$\includegraphics[clip,width=1.00\hsize]{eps/hierarchical_clustering.eps}$

4 評価実験

ランキング検索とクラスタリング検索それぞれの方法について，評価実験を行なった．

4.1 実験データ

実験には，YouTubeから「baseball」「basketball」「soccer」「tennis」「volleyball」の5つのタグで収集した合計500個(総再生時間約38時間)の動画データベースを利用した．動画は各タグについて100個ずつ用意されており，それぞれ20個の正解動画と，残り80個の不正解動画から構成されている．なお，本研究では試合動画を正解動画，それ以外を不正解動画として，それぞれの動画を収集した．

4.2 ランキング検索

4.2.1 実験方法

各正解動画について，同一タグの残り全99個の動画に対してのランキング検索を行ない，それぞれのタグの全正解動画に対する平均適合率(AP: average precision)と，その平均値(MAP: mean average precision)を求める．平均適合率とは，検索結果における各再現率(recall)レベルでの適合率(precision)の平均値であり，

	$\textstyle AP = \frac{1}{n} \sum^{}_{n} P_i$		(1)
	$\textstyle \hspace{0mm} {\scriptstyle n:\ } \mbox{\scriptsize 正解動画の数}$
	$\textstyle \hspace{0mm} {\scriptstyle P_i:\ } \mbox{\scriptsize$i$番目の正解動画が検索された時点での適合率}$

の式で表される．実験では，特徴量をそれぞれ単体で利用した場合と，タグごとに最適な重み付けで全特徴量を利用した場合の合計5つについての値を求める．

4.2.2 実験結果

実験結果を図3に示す．最も結果が良かったのは「volleyball」で全特徴量を利用したときで，平均適合率はとなった．また，MAPでもという数値を残せており，本手法の有効性を示すことが出来たものと考えられる．

**図 3:** =75mm ランキング検索の平均適合率(AP)とその平均値(MAP)
$\includegraphics[clip,width=1.00\hsize]{eps/similarity_ranking_result.eps}$

4.3 クラスタリング検索

4.3.1 実験方法

同一タグの動画をクラスタリングし，各グループのF値(F-measure)を求める． F値とは，適合率と再現率の調和平均であり，

	$\textstyle F = \frac{2 \cdot P \cdot R}{P \raisebox{0zw}{+} R}$		(2)
	$\textstyle \hspace{0mm} {\scriptstyle P:\ } \mbox{\scriptsize 適合率\ \ \ } {\scriptstyle R:\ } \mbox{\scriptsize 再現率}$

の式で表される．本研究では，F値の最も大きいグループを正解動画グループとし，そのF値を比較することによって，結果の評価を行なう．実験は，タグごとに最適な重み付けで全特徴量を利用した場合の類似度を基に，閾値を

から

まで

刻みで変化させて行なった．

4.3.2 実験結果

最も結果の良かった，グループ間の類似度算出に群平均法を用いた場合の結果と，対象の全動画を一度に表示した場合(全表示)のF値を図4に示す．結果が最大となったのは「volleyball」において閾値がのときで， F値はとなった．全表示の場合のF値はであり，クラスタリング検索を行なうことにより，類似動画を有効的に表示できたことが見てとれる．

**図 4:** =75mm クラスタリング検索の各閾値での正解動画グループのF値と全表示した場合のF値
$\includegraphics[clip,width=1.00\hsize]{eps/hierarchical_clustering_result.eps}$

5 考察

「soccer」と「volleyball」の結果が良かったのは，どの正解動画もコートの色が似通っていたためと考えられる．一方で，「tennis」では試合によってコートの色が全く異なり，色特徴よりもオプティカルフローの方が良い精度を残した．このように，「sports」という同一カテゴリ内においても重要な特徴量は一意に決定できず，どのような特徴量をどのように利用するかは難しい問題である．

6 まとめ

本研究では，EMD を用いた類似Web動画の検索手法について説明し， 2種類の検索方法を用いて実装を行なった． YouTube から収集した実験データに対する評価実験の結果，条件によっては，どちらの方法も非常に有効であることが示された．今後は，新たな特徴量を追加していくと共に，キーフレームの抽出方法やクラスタリング手法を改善することについても検討していきたい．加えて，もっと様々なタグに対しても評価実験を行ない，それらの結果を他手法と比較することで，客観的な評価も行なっていきたい考えである．

文献目録

1: TRECVID, http://www-nlpir.nist.gov/projects/trecvid/
2: YouTube, http://www.youtube.com/
3: Rubner, Y., Tomasi, C. and Guibas, L.: The Earth Mover's Distance as a Metric for Image Retrieval, IJCV, Vol. 40, No. 2, pp. 99-121 (2000).
4: Peng, Y. and Ngo, C.: EMD-Based Video Clip Retrieval by Many-to-Many Matching, in Proc. of CIVR, LNCS 3568, pp. 71-81 (2005).
5: Lucas, B. and Kanade, T.: An Iterative Image Registration Technique with an Application to Stereo Vision, in Proc. of IJCAI, pp. 674-679 (1981).
6: Jain, A., Murty, M. and Flynn, P.: Data Clustering: A Review, ACM Computing Surveys, Vol. 31, No. 3, pp. 264-323 (1999).

YANAI Lab.