TRECVID Semantic Indexing Task とMultimedia Event Detection Task への取り組み○樋爪和也†，柳井啓司‡
Kazuya HIZUME† and Keiji YANAI‡†: 電気通信大学 大学院情報理工学研究科 総合情報学専攻，hizume-k@mm.cs.uec.ac.jp‡: 電気通信大学 大学院情報理工学研究科 総合情報学専攻，yanai@cs.uec.ac.jp
概要： 本稿では米国国立標準技術局(NIST)主催の動画像における競争型ワークショップである TRECVID および Semantic indexing task、Mutimeda event detection task の概要について述
べ、それらに対し我々が行った手法について解説する。200 コア以上の並列計算を用いて動画から抽出した特徴量を BoF 表現に変換し、Multiple Kernel Learning-SVM で学習・分類を行った。
大規模動画像認識、Bag-of-Features、Multiple Kernel Learning

1． はじめに
近年、動画像が持つ情報にパターン認識の技術を適用したコンテンツベースの映像検索手法が盛んに研究されている。そうした研究を促進するために TRECVID と呼ばれる国際的な評価ワークショップが存在し、世界中の多くの映像検索技術に関する研究チームが参加している。本稿では、このTRECVID で行われているタスクの中から我々がこ

図 1 SIN タスクのカテゴリ例

こ数年参加している 2 つのタスクに注目し、その概要と我々の手法について述べる。与えられた学習およびテストデータは膨大であり、それらを処理するために 200 コア以上の並列計算で延べ 6000 時間以上の大規模な動画像処理を行う必要があった。
本稿ではこうした大規模映像データ処理についても述べる。

2． TRECVID

像検索技術に関連する研究を促進する競争型ワークショップである。毎年、各国の研究グループが参加し、TRECVID が設定した共通のタスクおよび評価基準に対して各々の手法で研究に取り組む。
共通のタスクに対して結果の優劣を競争させ、結果の比較検討および成果の共有を行うことで、映像検索技術の研究を促進させることが目的である。

TRECVID（TREC Video Retrieval Evaluation）[1] と は 、 米 国 国 立 標 準 技 術 研 究 所 （ NIST ） とDisruptive Technology Office（DTO）が主催する映2012 年度は 6 つのタスクが設定されており、その 中 か ら 我 々 が 例 年 参 加 し て い る Semanticindexing （ SIN ） と Multimedia event detection

（MED）の 2 つのタスクについて説明する。

るものや、Winning a race without a vehicle のような状態を指す。また SIN タスクとは異なり、動画はショ

2.1. Semantic indexing タスク

ット分割されていない。TRECVID2012 でのイベンシーンごとに分割されたショットデータの中から特定の概念を含んだショットを検出するタスクである。対象となる概念は大まかに以下の 3 種類である。

ト数は 20、締め切り直前に検出イベントが与えられ

物体、人（例 Airplane、Bus、Male_Person）

動き（例 Dancing、Ski、Walking）

風景（例 Beach、Indoor、Mountain）

図 1 に示す通り、短く分割されたショット中では対象となる概念がはっきりと写っている。ただしデータに対するラベル付けは参加者が共同で行っているため、対象となる概念がショット中にどの程度出現するかは不定である。認識対象となるカテゴリ数とデータは年々増加しており、TRECVID2012 でのカテゴリ数は 346、学習データは計 600 時間、テスト
デ ー タ は 計 200 時 間 で あ る 。 デ ー タ は 全 てる追加のアドホックイベント数が 5 である。学習デー
タは Linguistic Data Consortium が収集したユーザが 撮影 した 映像 であ り、MPEG-4/H.264 形式 で1350 時間以上、テストデータは 4000 時間以上である。
評価形式には Normalized Detection Cost（NDC）が用いられている。まず各チームがイベントの有無を判定するための Threshold を独自に設定し、各テストデータのスコアを決定する。この結果から PMD、PFA が計算され、NDC は以下の式によって求められる。NDC は値が小さいほど良い結果であると言える。また Cost と PTarget の値は主催側で決定される。

MPEG-4/H.264 形式のインターネットアーカイブ映像であり、1 ショットあたり 10 秒から 3.5 分に制限されている。また、各々が用意した外部データを学習データとして扱うことも可能である。
評価形式はテストデータをランキング付けし、カテ

PMD = (Threshold を上回らなかった正解データ数)/（正解データ数）
PFA = （Threshold を上回った非正解データ数）/（非正解データ数）

ゴリごとに上位 2000 ショットを対象としてランキングを考慮した平均適合率である infAP[2]が計算される。提出方法として、すべてのカテゴリを認識する
full、指定された 50 カテゴリのみの light がある。ただし評価結果が返却されるのは一部のカテゴリのみである。2012 年からは新たに Beach + Mountainのような 2 種類の認識対象を組み合わせる pair が追加された。Pair では 10 種類の組み合わせが課題として与えられる．

図 2 MED タスクのカテゴリ例

2.2. Multimedia event detection タスク
Birthday party、Parade、Rock climbing のような複雑なイベント（図２）を対象に、テストデータが各イベントを含むかどうかを判定する。ここでのイベン
トとは SIN タスクのように特定の動作ではなく、Repairing an appliance のような複数の動作から成3． 関連研究
TRECVID2011 では SIN タスクにおいて東京工業大学と Canon [3]の合同チームが日本から参加チームとしては初の 1 位となった。彼らはショット中の全フレームから SIFT、HoG を、ショット全体からMFCC 音響特徴といった特徴量を抽出し、これら

色 特 徴 は画 像 の RGB 画 素 値 を使 用 す る 。に混合ガウス分布（GMMs）を適用している。このとSURF、および RGB 色特徴は全フレームより抽出

き、木構造 GMMs を構築することでシステムの高する。

速化を図っており、さらに正規化した平均ベクトルを連結した GMM Supervector を作成する。分類には SVM を使用し、Mean infAP=0.173 を記録した。
MED タスクではアメリカの BBN VISER[4]チームが 1 位となった。彼らは四つの局所特徴、三つの色特徴、二つの動き特徴、三つの音響特徴を抽出し、Audio-Visual Bi-Modal Words として視覚特徴と音響特徴の相関モデルを作成した。さらに物体検出や音声認識、テキスト OCR なども採用しており、最終的に 18 種類のシステムを Weighted Average
Fusion により連結することで最高位を記録している。

4． SIN タスク認識手法
SIN タスクで扱う動画は既にショット分割が行われており、各概念はショット中において多くの時間で出現している。そのため、ショット全体から特徴量図 3 処理の流れ、点線枠は MED のシステムのを抽出し、ショット単位で認識を行うことが可能であみる。本研究では画像単位で得られる局所特徴と動画全体から得られる動き特徴を使用し、パターン認

4.1.2 時空間特徴

識における基本的なアルゴリズムを用いて動画像動画像全体から抽出する時空間特徴として、野認識を行う。

口が提案した時空間特徴抽出手法[6]を用いる。

TRECVID2012 の両タスクで使用したシステム全

まず、動画に含まれるズームやパンなどのカメラ体の流れは同じであるため、まず SIN タスクで使用モーションの検出を行う。Web 動画には手振れのした手法について述べる。図 3 に処理の流れを示ような意図しないカメラモーションが多く含まれておす。図 3 の点線枠で囲まれた部分は MED タスクでり、さらに解像度が低い。これを解決するために、行う追加処理であり、SIN タスクでは行わない。

カメラモーションを検出した場合、その特徴を破棄する。検出手法には Lucas-Kanade アルゴリズムを4.1 特徴抽出用いる。まず、動画に含まれるズームやパンなどの4.1.1 画像特徴カメラモーションの検出を行う。Web 動画には手振フレーム画像から抽出する特徴量として、れのような意図しないカメラモーションが多く含まれSURF[5]と色特徴を使用する。ており、さらに解像度が低い。これを解決するため

SURF(Speeded-Up Robust Feature)は、特徴点とに、カメラモーションを検出した場合、その特徴をその周辺の局所特徴を記述した特徴量である。画破棄する。検出手法には Lucas-Kanade アルゴリ

像の照明変化、スケール変化、回転に対して頑健ズム 9) を用いる。

であり、128 次元の特徴ベクトルで表現される。

次にフレーム画像から SURF を抽出する。このSURF の点の内、時空間特徴として適しているのる。フレーム画像から抽出した SURF および色特徴はフレーム間で動きのある点のみであるため、動きにはマルチフレーム処理を適用し、全フレームからのなかった点は削除する。そして残った点につい抽出した特徴量を一つの BoF ベクトルに変換する。て Delaunay 三角分割を行う。Delaunay 三角分割

BoF ベクトルの生成には soft assignment[7]を利用とは空間内の点を連結して三角形のグループを作した。これは BoF におけるコードワードへの割り当成することで、点の特徴だけでなくそのての際、複数のコードワードに割り当てを行う。割り周辺の特徴も考慮する手法である。この 3 点のSURF 記述子を視覚特徴とするため、64×3 = 192

当てる値はコードワードとの距離の逆数を L1 正規化して使用した。

次元で表現される。
動き特徴は、まず SURF を抽出したフレームか4.2.1 空間ピラミッド表現

ら N フレーム先までのフレームを取得する。上記抽出された画像特徴は空間ピラミッド表現[8]をの SURF 点の動き情報はこの内の N=2 フレームか用いて、領域毎の特徴ベクトルを作成した。空間ピら計算される。取得した N フレームを M 分割し、そラミッド表現では領域を階層的にグリッドで分割し、の区間内で Lucas-Kanade アルゴリズムによって特それぞれのグリッドに対して BoF ベクトルを作成す徴点のオプティカルフローを計算する。各区間のる事で、局所特徴の空間情報も考慮した特徴ベク

動き特徴はオプティカルフローの x,y 成分の正方トルを得ることができる（図５）。時空間特徴は元々向および負方向に動きなしを加えた 5 次元で表現マルチフレームから抽出する特徴なので、ショットされる。設定は区間 N = 5、分割数 M = 5 としてお単位での BoF ベクトルを生成する。

り、三角形の面積変化は 5 次元で表現されるため、本研究ではピラミッドレベルを 1 および 2 として、動き特徴は 20×3 + 5 = 65 次元となる。また、動き画像全体および 2×2 の領域分割を行ったヒストグ

特徴を回転に対して有効にするため、SURF 記述ラムを作成、連結した。これに伴い、コードワード数子で得た回転角を利用してオプティカルフローのは画像特徴では 1000、時空間特徴では 5000 とし回転も行う。

た。よって最終的な BoF ベクトルの次元数はすべ最後に視覚特徴、動き特徴を単純に結合するこての特徴量において 5000 次元である。とによって 192 + 65 = 257 次元の一つの時空間特徴とする。図 4 は処理の一連の流れを図式化したものである。

図 5 空間ピラミッドマッチング例
4.3 分類器
図 4 動き特徴における視覚特徴抽出の様子

本 研 究 で は 、 分 類 器 と し て Support Vector
Machine （SVM）を使用する。SVM は 2 値分類問

4.2 Bag-of-Features

題を解くために考えられた学習アルゴリズムであり、抽出した特徴量から Bag-of-Features 表現を用認識性能の優れた学習モデルのひとつである。

いて局所特徴の出現頻度の特徴ベクトルを作成す

SVM は線形識別器であるが、カーネル関数を用いることで非線形への拡張が可能である。本研究定を行う。選定には VisualRank 手法を使用し、教では RBF-χ2 カーネルを用いる。

師なしショットランキングを行う。VisualRank については 5.1 で詳細を述べる。
MKL-SVM の学習、分類も SIN タスクと同様である。スコアはショット分割前の元の動画単位で決定されるため、元の動画に含まれるショットのうち、上

4.3.1 MKL-SVM
Multiple Kernel Learning（MKL）は複数の SVMカーネル（サブカーネル）を式 1 のように統合することにより、新しい最適なカーネルを求める手法である。各サブカーネルをそれぞれの特徴と対応させ

位 3 つの出力値の平均をその動画のスコアとした。
また、Threshold はポジティブ学習データの 2-foldcross validation で得たスコアの平均と設定した。
5.1 VisualRank
対象となるイベントを含んだショットを探すため、ることによって、MKL は特徴選択や特徴統合に用Web ページランキング手法の PageRank を画像にいることができる。

応用した VisualRank 手法[9]を適用する教師なしショットランキングを行う。VisualRank 手法では画像の類似度行列を用いて反復計算によって各画像のランク値が求められる。本研究ではショットの類似度

SIN タスクでは、MKL-SVM の出力値をソートす計算にヒストグラムインタセクションを用いる。X はることで上位 2000 のテストショットを決定する。

BoF ベクトルであり、本研究では時空間特徴の BoF

5． MED タスク認識手法

ベクトルを使用する。

MED タスクのデータは対象となるイベントが動画中の全体または一部に含まれており、さらに複数の動作から成るイベントはいくつかの構成要素が含まれる。そのため、SIN タスクと同様に動画全体を使って認識しようとするとノイズとなる部分が多く類似度行列が得られたら、VisualRank 計算式を使ってショットのランキング付けを行う。

含まれたり、複数の動作を一度に表現したりしてしまう。そこで、まずフレーム画像間のカラーヒストグラム差分を使って各動画をショット分割する（図 3 点

ここではS が正規化された類似度行列、p は補正線枠）。このとき各ショットの長さは最大 3000 フレーベクトル、r はランキングベクトルを指すものでムとした。元の動画は 30fps であるため、これは 100ある。αはpの影響を補正するパラメータである。

秒分に相当する。そして SIN タスクと同様に各ショ一般的にαは0.8以上の値が設定され、本研究でットから特徴を抽出し、BoF ベクトルを生成する。たは0.85と設定した。また、補正ベクトルは均一にだし、MED タスクで使用する特徴量は SURF、時与える。

空間特徴のみである。これは認識する対象がほぼMEDタスクのシステムでは得られたランキングベク動きを中心としたものであるため、SIN タスクで使用トルの上位500のショットをポジティブショットとして扱した色特徴は除外した。

い、学習データに使用する。

ここで、イベントを含まないショットが多く存在している。学習の際にこれらのデータをポジティブショットとして与えてしまうとノイズとなるため、ショットの選

6． 実験環境
表 1 に両タスクで使用したラベル付きデータ数と、テストデータ数を示す。なお、SIN タスクはカテゴリ度の有効性は伺える。しかし Airplane や Baby、によってラベル付き学習データが非常に多いため、Kitchen や Glasses など、動きよりも画像特徴が重視

学習の都合上、クラスごとに最大で 10000 ショットにされるようなカテゴリで大きく下回っている。そのた制限した。そのため、配布されたラベル付きデータめ、有効な画像特徴の追加が精度向上につなが数は記載した数字よりも多い。

ると考えられる。

特徴抽出や学習、分類などの計算には 80 台の次に MED タスクの結果を図 7 に示す。20 クラス

計算用マシンを使用した。各マシンは種類が様々の Pre イベントと 5 クラスのアドホックイベントはそれではあるが 4 コアの CPU、8GB のメモリを搭載してぞれ個別に評価されているため、グラフを別にしている。1 台あたり 3 コアを使用し、240 コアを使用しいる。我々のチームの結果は黒枠で囲んだ部分でた並列分散処理によって全体的な処理の高速化ある。NDC は小さいほど良い結果であるため、を図った。これにより、全行程の計算に SIN タスク

我々のチームは残念ながら下位の方の結果に終では約 4 日、MED タスクでは約 6 日かかった。

わった。これは他チームの PMD の値に比べ、PFA の値が非常に大きいことが原因である。NDC の計算

表 1 データ数式において正解データを検出できなかったエラー
率 PFA に対するコスト CostFA は非正解データを認識

SIN タスク
ショット数
MED タスク
動画数
MED タスク
分割後ショット数

学習データ

テストデータ344960145634

4225

98118

48792

733764

できなかったエラー率のコスト CostMD に対して、非常に大きく設定されている。これにより、PMD は他チームと大きく差があるようには見られないが、PFA の差によって NDC の差が広がってしまった。これには SIN タスクでも使用した認識システムの精度も影響しているが、ショットのスコアから元の動画のスコアを決定する方法も再検討する必要がある。 イベ
ントショットの検出のための threshold の値につい7． 実験結果ては、PFA を下げようと値を高くしすぎれば PMD が上昇してしまうトレードオフの関係のため、threshold

本研究では実験として、TRECVID2012でのSINタは cross validation で設定するしかない。本研究でスク、MEDタスクで得られた実験結果を記載する。

は元の動画のスコア決定に上位 3 ショットの値を使

図 6 は SIN タスクの我々と他チームの最高値、用しているが、元の動画のショット分割数や各ショッ中央値との比較である。今年は 346 カテゴリ中、図トの時間など、より元の動画を意識したスコアの決中の 50 のカテゴリが対象となった。右端は全カテゴ定方法が求められる。

リの平均値である。一部のカテゴリで中央値に追いまた図 8 は 20 カテゴリに対して VisualRank 手法ついているものの、全体としては下回る結果となっを適用した際の、選定画像の適合率を比較したグた。理由の一つとして、使用した特徴量の少なさがラフである。ベースラインとしてランダムに選んだあげられる。過去に我々は顔検出や音響特徴を使100 ショット、実験で使用した VisualRank を適用し用したが思うような結果を得られず、今年度は時間上位 500 ショットからランダムに選んだ 100 ショット、的な制約もあり比較的基本的な特徴量しか使用しさらに VisualRank を適用した上位 100 ショットの適なかった。他チームと比較すると、全体的に認識率合率を求めた。ほぼすべてのカテゴリでの高いカテゴリについては我々の結果もある程度VisualRank 適用前以上の適合率を得られた。しか上昇しているため、現在の特徴量だけでもある程しトップ 100 の場合は適用前よりも値が下がる結果

図 6 SIN タスク 他チームの最高値、中央値との比較

図 7 MED タスク 他チームとの比較
左：Pre イベント 20 クラス平均 右：アドホックイベント 5 クラス平均となった。これは複雑で大きな動作の中間にあるシのショットを極力排除する方法を適用する必要があョットが上位に入ってしまったためである。このようる。

なショットはショットの中で動きが少なかったり、ショ8． まとめットの時間が非常に短かったりすることで十分な特徴量が得られず、さらに中間のショットなので比較

本稿は動画像認識のワークショップである的数が多く存在するため、上位にランクインしてしTRECVIDについて、およびSemantic Indexingタスク、まったと考えられる。図 8、9、10 に VisualRank によMultimedia event detectionタスクへの取り組みについって上位にソートされたショットのフレーム画像を示て述べた。SINタスクでは動画像に関連した特徴量す。Birthday party や Parade はカテゴリに即した動やパターン認識における基本的なアルゴルズムを用画が上位に現れていると言える。しかし Making a

いて、全体の中で中位程度の結果を得ることができsandwich のように人物が瞬間的に映り込んだようなた。MEDタスクは独自にショット分割したデータにショットが上位に含まれる場合もあり、認識に大きなVisualRank法を用い、SINタスクのシステムをMEDタ影響が出ていると考えられる。よってこのような中間スクに適用できるように改良した。

図 8 VisualRank 適用の比較

図 9 VisualRank 上位ショット
Birthday party

図 10 VisualRank 上位ショット

図 11 VisualRank 上位ショット

Working on a sewing project

Making a sandwich

今後はシステム全体として追加すべき有効な画像特徴の再検討が必要である。Flisher ベクトルなど物体認識の分野で成功を収めている特徴量の導入を検討している．また、MED タスクにおいては追加の処理としてショット分割を行っているため、各ショットの元の動画に占める割合などを考慮し、最終的な動画のスコアの決定方法を探って行きたい。またポジティブショットを選定する際のアルゴリズムもさらに検証したい。
参考文献[1] TRECVID Home Page.
http://www-nlpir.nist.gov/projects/trecvid/.
[2] Yilmaz, E. and Kanoulas, E. and Aslam, J.A. A simple
and efficient sampling method for estimating AP andNDCG. In Proc. SIGIR, pp.603-610, 2008.

[3]

http://www-nlpir.nist.gov/projects/tvpubs/tv11.slides/tv11.tokyotechcanon.sin.slides.pdf[4] http://www-nlpir.nist.gov/projects/tvpubs/tv11.papers/bbnviser.pdf[5] H. Bay, T.Tuytelaars, and L.VanGool. SURF: Speeded
up robust features. In Proc. ECCV, pp. 404-415, 2006.
[6] A. Noguchi and K. Yanai. A surf-based spatio-temporalfeature for feature-fusion-based action recognition..
ECCV WS on Human Motion, 2010.
[7] . C. V. Gemert, J. mark Geusebroek, C. J. Veenman, andA. W. M. Smeulders. Kernel codebooks for scene
categorization. In Proc. ECCV, pp. 696–709, 2008.
[8] S. Lazebnik, C. Schmid, and J. Ponce, Beyond bags offeatures: Spatial pyramid matching for recognizing
natural scene categories. In Proc. CVPR, pp.2169-2178,
2006.
[9] Y. Jing and S. Baluja. Visualrank: Applying pagerank tolarge-scale image search. IEEE PAMI, Vol.30, No.11,
pp.1870-1890, 2008.