第15回情報理論的学習理論ワークショップ(IBIS2012)

コミュニケーションとしての映像とその検索
篠⽥浩⼀(東京⼯業⼤学)

講演の内容1. ⾳声と映像
2. TRECVID Semantic Indexing (SIN)
3. SIN のための⾳声技術
4. TRECVID Multimedia Event Detection (MED)
5. まとめ2

インターネット映像の急増
EB/Month
600
500

Youtube (2011):
Increase 48 hours / min
3,000,000,000 views / day

400

VIDEO

300
200

OTHER

10002010

2011

2012

2013

2014

2015

IP Traffic (Cisco Visual Networking Index 2010-2015)

3

No Meta data
Large Variety
Low quality
Mostly Useless課題

インターネット映像からのContent-Based Video Retrieval (CBVR)
これまでの研究対象
TV ドラマ, 映画, ニュース, スポーツなど••••ジャンルが特定⾼品質
プロによる編集
メタデータが豊富

インターネット映像とは明らかに異なるどのような⽅法論をとるべきか？
5

Gartner Hype Cycle for 2011
BabbleImage
Recognition

Video Analysis for
Consumer Service

GestureRecognition

SpeechRecognition
Biometric
Authentication
MethodCrash!

6

⾳声研究から学べないか？
映像研究はこれから “Babble”
⾳声研究は “Babble Crash”から⽣き延びた
BabbleSpeechRecognition
Video Analysis for
Consumer Service

Crash!
7

⾳声開発

萌芽画像

萌芽映像

‘80

‘90

実⽤
開発

実⽤

萌芽開発

‘00

‘10

実⽤

year
8

⽶国国防省(DARPA)⾳声認識ベンチマーク
100%

Switchboard
Conversational
SpeechReadSpeech

WORD ERROR RATEWSJSpontaneousSpeech

ATIS

10%

1k 
Resource
Management

1%

VariedMicrophone

20k

foreign

Broadcast
Speechforeign
NAB

5k



Noisy



• 段階的にタスクを設定• 着実に技術を蓄積
Courtesy NIST 1999 DARPA
HUB-4 Report, Pallett et al.

1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003

⾳声と映像は違う?
• ⾳声は１次元、映像は３次元• ⾳声には “Semantic Gap” がない( ? )• ⾳声はコミュニケーションの道具であるが映像は違う ( ? )• 映像は、⾳声のような明確な構造がない( ?)(⾳素→形態素→単語→⽂、⽂法)

10

送り⼿

⾳声と映像は同じ

受け⼿

Audio Channel
メッセージ

メッセージ

Video Channel
映像はコミュニケーションの⼿段(⾮明⽰的な)語彙や⽂法をもつ※⾳声にもSemantic Gapは存在する

11

映像検索のための⾳声技術
1. 「送り⼿」をモデル化するための⽣成モデル
2. 低品質・多様性・データ不⾜に頑健な確率的フレームワーク
3. ⾼速計算⼿法

12機械学習によるアプローチ（共通）
⾳声

画像+
データ量
計算量
Semantic gap

⼩• 特定の応⽤に集中• 他機関との協働

映像=⼤13

TRECVID
Semantic Indexing

14

TRECVID(TREC Video Retrieval Evaluation)
2001年に Text REtrieval Conference (TREC) から独⽴NIST(National Institute of Standard and Technology) が主催

⽬的 : 映像コンテンツ分析・検索研究の促進
クローズドな国際競争型ワークショップ
ホームページ: http://trecvid.nist.gov••••

⼤規模データが使える (著作権等の問題をクリア)
⼿法の⽐較が容易、そのため進歩が速い
ラベル付け作業を分担
勝ち負けがはっきりする
15

TRECVID タスクの歴史
Known item search
Semantic indexing
Shot boundary detection
Storysegmentation

Content-based copy detection
Low-levelfeatureextraction

Surveillance event detection
Rushessummarization

Instance searchMultimedia
event detection

2001

2006

2012
16

TRECVID データセット
TV shows

Internet video

Data (hours)

TV news

http://www-nlpir.nist.gov/projects/tvpubs/tv11.slides/tv11.intro.slides.pdf
17

2011年 TRECVID
66 チームが参加（⽇本からは12チーム)
5 tasks:
Semantic indexing (SIN)
Multimedia event detection (MED)
Known item search (KIS)
Instance search (INS)Surveillance event detection (SED)18

Semantic Indexing (SIN)

⽬的

ビデオショットからの Concept を検出
Concepts: objects, scenes, ...

TRECVIDの中核的タスク
静⽌画の⼀般物体認識に対応

19

Multimedia Event Detection (MED)
⽬的

ビデオクリップからのイベント検出
e.g. Batting a run inMaking a cake

SINより⾼次の対象
スポーツ番組からのハイライト検出
をインターネット映像まで延⻑

20

Instance Search (INS)⽬的

特定の⼈物、場所、ロゴを検出

対象は明確、学習データは少ない
データベース：BBC rushes

21Known Item Search (KIS)
⽬的

詳細なテキスト記述に合致する映像シーンを検出
例：⾚いシャツの男が⽝にりんごをあげている

学習データなし
SINタスクで得られたコンセプトを利⽤

22

Surveillance Event Detection (SED)
⽬的
監視カメラからのイベント検出
イベント: PeopleRuns, Pointing, PeopleMeet, など
混雑状況、固定カメラ
データベース
イギリス・ガトウィック空港における５台の監視カメラ映像(145時間)

23Semantic Indexing(SIN)24

タスク設定データベース：IACC(Internet Archive videos with Creative Commons licenses) :コンセプト数:
Run:

346

600 h

各々のコンセプトについて上位2000個のショットのリストを提出※各々のチームは最⼤４つのRunを提出できる評価基準: Average Precision (AP)
1: Rank: Number of true shots from 1st to k-th

25

コンセプトの出現頻度
Number of positive samples in 264,673 training video shots
Outdoor (29,997 shots)# positive shots

more than 10,000

5%Singing (3875 shots)
1% of development data

Airplane (371 shots)
346 semantic concepts

26

Bag of Words (BoW)
静⽌画における⼀般物体認識で主流
ショット

局所特徴⇨ヒストグラム⇨⇨SVM

キーフレームを利⽤• 計算量が⽐較的少ない• 量⼦化誤差が⼤きい27

新たな動き (1) : 頑健性
低品質、多様性、データ不⾜に対応• More features

SIFT, Color SIFT, SURF, HOG, GIST, Dense features• Multi-modal
⾳声の利⽤ :• Multi-frameSinging, Dance, Car, etc.

キーフレーム以外を利⽤• Soft clustering

量⼦化誤差の低減

28新たな動き (2) : ⾼速化
参加58チーム中28チーム(半分)しか結果を提出できなかった• 近似アルゴリズム• 分散処理• Graphical Processing Unit (GPU)の利⽤

29

期待したが効果のなかったもの• ⼤局特徴(⾊ヒストグラムなど)

局所特徴だけで⼗分(相補的な関係にない)• ⾳声認識, OCR

それら⾃体の性能が低い• 物体の位置検出

位置検出性能が低い、位置のないConceptも• Concept間のコンテキスト
データ量が少なすぎる

30

Semantic Indexingのための⾳声技術

31

３つの⾳声技術
1. 多様性、低品質

Gaussian Mixture Models (GMM)

2. データ不⾜
3. ⾼速化

MAP 適応⽊構造サーチ32

フレームワーク
Tree-structured
GMMGMMs
1) SIFT-Har
supervectors

video (shot)2) SIFT-Hes
3) SIFTH-Dense
4) HOG-Dense
5) HOG-Sub
6) MFCC

SVM
score

…

Score
fusion

…
…
…
SVM
score

33

特徴抽出
Tree-structured
GMMs
GMM1) SIFT-Har
supervectors

video (shot)2) SIFT-Hes
3) SIFTH-Dense
4) HOG-Dense
5) HOG-Sub
6) MFCC

SVM
score

…

Score
fusion

…
…
…
SVM
score

34

低次特徴• 6つの画像特徴
SIFT-Har, SIFT-Hes, SIFTH-Dense, HOG-Dense, HOG-Sub• Multi-modal
⾳響特徴: Mel-Frequency Cepstral Coefficient (MFCC)• Multi-frame
毎フレーム、１フレームおき、２秒に１フレームなど35画像特徴
1) SIFT-Har- Harris-affine detector- Multi-frame (every two frame)

2) SIFT-Hes- Hessian-affine detector- Multi-frame (every two frame)

3) SIFTH-Dense- SIFT + Hue histogram- 30,000 samples in a key frame4) HOG-Dense- 32 dim HOG feature- 10,000 samples in a key frame5) HOG-Sub- Temporal differential of HOG- Detect movement※ Reduce dim to 32 by PCA
36

⾳響特徴: MFCC
Mel-frequency cepstral coefficients
⾳声認識、⾳響イベント認識でよく⽤いられる
MFCC(12)MFCC(12)MFCC(12)
Log-power(1)Log-power(1)37コンセプトのモデル
Tree-structured
GMMs
GMM1) SIFT-Har
supervectors

video (shot)2) SIFT-Hes
3) SIFTH-Dense
4) HOG-Dense
5) HOG-Sub
6) MFCC

SVM
score

…

Score
fusion

…
…
…
SVM
score

38

⾳声技術その１

Gaussian Mixture Model (GMM)

ガウス分布の重み付け和
:

⼊⼒特徴

:
混合成分 k の重み ∑1), Σ : 混合成分 k の平均と分散各々のショットをGMMでモデル化
39

GMM は BoW の拡張
BoW

Code vector
Histogram

GMMGaussian mean
Weight distribution
Red Color: ショットごとに推定40

⾳声技術その2Maximum A Posteriori (MAP) 適応• 転移学習の⼀⼿法• GMMの平均ベクトルに対し、その事前分布を仮定
1. すべての学習データを⽤いて Universal background model (UBM)を推定
2. UBMを初期モデルとして、MAP適応により、GMMの平均ベクトルを推定する。
事前分布：UBMにおける、対応する分布
UBM
MAP
adaptation

より少ないデータ量で⾼精度な推定

32

MAP 適応
⼊⼒:,Σ
̂

,…,
: UBMにおける混合成分 の平均と分散: 混合成分 の平均のMAP推定量: 制御パラメータ
where

⼊⼒

に対する混合成分の負担率

漸近的な性質をもつ
データが少なくなると、 ̂ →データが多くなると、 ̂ は最尤推定量に近づく
42

識別器
Tree-sturuc
1) SIFT-Hartured GMMs

GMMsupervectors

video (shot)2) SIFT-Hes3) SIFTH-Dense
4) HOG-Dense
5) HOG-Sub
6) MFCC

SVM
score

…

Score
fusion

…
…
…
SVM
score

43

GMM Supervector + SVM
1. GMMの平均ベクトルを連結 → GMM supervector
wherenormalizedmean

2. Support Vector Machine (SVM) with RBF kernel

GMMに対するFisher Kernelの近似

Score fusion
SVM スコアの重み付け和

where

重みは Concept ごとに cross validation で決定
45

計算量
HOG-Dense 特徴を⽤いたときの計算時間 (sec)■ Feature■ PCA ■ GMM Estimation ■ SVM

GMMの推定が⼤部分

46

負担率の計算の高速化
High cost!
where

⼊⼒に対する混合成分の負担率47⾳声技術その3⽊構造GMMを⽤いた⾼速計算
⼊⼒がどの混合成分に属するか?
(BoW: ⼊⼒をどのコードに割り当てるか?)

Gaussian components

48

負担率
: 局所特徴に対する混合成分の負担率

Gaussian components49特徴量空間の⼀部でのみ計算

Gaussian components

50

⽊構造GMM (1)Leaf layer

混合成分間の距離：
Symmetric KL divergence

Gaussian components

51

⽊構造GMM (2)Non-leaf layers

ノードのガウス分布は、リーフのガウス分布集合を近似

Gaussian components

52

⽊構造GMM (3)Non-leaf layers

ノードのガウス分布は、リーフのガウス分布集合を近似

Gaussian components

53

⽊構造GMM (4)Non-leaf layers

ノードのガウス分布は、リーフのガウス分布集合を近似

Gaussian components

54⾼速サーチ (1): Active nodes

55

⾼速サーチ (2): Active nodes

56

⾼速サーチ (3): Active nodes

57

TRECVID2011 SIN の結果※ Mean InfAP: Inferred AP averaged over all concepts
58コンセプト毎のAverage Precision59効果的な低次特徴は？

60

GMM推定の計算時間
検出性能の劣化なしに、4.2 倍の⾼速化

61

Multimedia Event Detection(MED)62

Multimedia Event Detection (MED)
⽬的

ビデオクリップからのイベント検出
e.g. Batting a run inMaking a cake

SINより⾼次の対象
スポーツ番組からのハイライト検出
をインターネット映像まで延⻑
データベースHAVIC : 2000時間のホームビデオ
Linguistic data consortium (LDC)が提供
63

MED (2)• 2010に開始された新しいタスク• 2011年は18チーム(⽇本からは5チーム)• ⽶国情報省(IARPA)のAutomated Low-Level Analysisand Description of Diverse Intelligence Video(ALADDIN) プロジェクトが援助

64

HAVIC データベース• ビデオクリップ(２分程度): 3488個• サンプル：各々のイベントに付き100個(半分が開発⽤、半分がテスト⽤)
2010 (3 events)

2011 (10 events)

Assembling a shelter

Birthday party

Making a sandwich

Batting a run inChanging a vehicle tire

ParadeMaking a cakeFlash mob gathering

Parkour

Getting a vehicle unstuck

Repairing an appliance

Grooming an animal

Working on a sewing project65

評価基準：•••

Missed Detection Probability Pmiss
1 – Recall
False Alarm Probability PFA
False Alarm / Clips with no events
Normalized Detection Cost (NDC)
上記２つを適当な重みで混合したもの

11

CostMiss = 80
CostFA = 1
Ptarget = 0.001
66

トレンド
• SINの⼿法を応⽤

多くの特徴＋BoW+SVM• 時空間特徴

STIP (Space-time interest point), etc.

• コンテキストのモデル化 (Semantic model)
効果があまりない ← データが少ない？

• ⾳声認識、OCR

効果なし、SINと同じ理由
67

TRECVID2011
Mean Minimum NDC

1.5
1.3
1.1
0.9
0.7
0.5
0.3
0.1
‐0.1

TRECVID 2011 MED runs

Mean MNDC

Mean ANDC

1st Team

0.448

0.465

2nd Team

0.499

0.522

3rd Our team

0.525

0.556

68

69

70

おわりに• 頑健かつ⾼速な映像検索– ⾳声分野で開発された技術が性能向上に寄与– GMM, MAP適応, ⽊構造サーチ• 単語レベル (SIN) から⽂レベル (MED) へ– 映像のコミュニケーションモデル
– コンテキストの活⽤• No data like more data

– データ量にスケールする技術が重要– 計算の⾼速化がますます重要に• 他に使える⾳声技術は?

⾔語モデル、識別学習、Deep Learning, etc.

71