論文 / 著書情報
Article / Book Information
題目(和文)

大規模映像資源のための高速・高性能なセマンティックインデクシン
グ

Title(English)

Efficient and Effective Semantic Indexing for Large-Scale Video
Resources

著者(和文)

井上中順

Author(English)

Nakamasa Inoue

出典(和文)

学位:博士(工学),学位授与機関:東京工業大学,
報告番号:甲第9552号,
授与年月日:2014年3月26日,
学位の種別:課程博士,
審査員:篠田 浩一,佐藤 泰介,徳永

健伸,村田

剛志,杉山

Citation(English)

Degree:Doctor (Engineering),
Conferring organization: Tokyo Institute of Technology,
Report number:甲第9552号,
Conferred date:2014/3/26,
Degree Type:Course doctor,
Examiner:,,,,

学位種別(和文)

博士論文

Type(English)

Doctoral Thesis

Powered by T2R2 (Tokyo Institute Research Repository)

将Efficient and Effective Semantic
Indexing for Large-Scale Video
Resources

Nakamasa Inoue
Supervised by Professor Koichi Shinoda

Department of Computer Science
Graduate School of Information Science and Engineering
Tokyo Institute of Technology
Dissertation submitted to the Tokyo Institute of Technology for the degreeof Doctor of Engineering

Feb. 2014

i

Abstract
Video semantic indexing aims to assign semantic concepts to a video segment and is one of the fundamental and important problems in computer
vision. In this study, we propose an efficient and effective semantic indexing system, which extends the bag-of-visual-words system to a probabilistic
framework using a Gaussian mixture model (GMM). To improve the modeling accuracy, we introduce a q-Gaussian mixture model, which controls
the tail-heaviness of the GMM. To improve the speed of the system, we
propose two complementary techniques: fast parameter estimation using atree-structured GMM and Neighbor-to-Neighbor (NTN) search.
We evaluated our system on the TRECVID video benchmark. We achieved
Mean Average Precision of 0.321, while the computational cost of parameter
estimation is reduced by 76.2%.

ii

Acknowledgments
I would like to express my sincerest thanks and gratitude to my advisor
Professor Koichi Shinoda for his support during my study at Tokyo Instituteof Technology.
I would like to express my gratitude to Professor Sadaoki Furui and Associate Professor Takahiro Shinozaki for their support and kind help in myresearch. I would also like to thank every member of the Shinoda Laboratory
for their help and discussion.
I would like to extend my appreciation to my thesis committee for theiradvices and comments: Professor Taisuke Sato, Professor Takenobu Tokunaga, Professor Tsuyoshi Murata, and Professor Masashi Sugiyama.
Last but not least, I would like to thank my family for all their support
through this study at Tokyo Institute of Technology.

Contents
1 Introduction

12 Semantic Indexing

4

2.1 Low-Level Feature Extraction . . . . . . . . . . . . . . . . . .

4

2.2 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.3 Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83 Multi-Modal Semantic Indexing
3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

3.2 Feature Extraction . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Visual Features . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2 Audio Features . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Detection Methods . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3.1 Log-Likelihood Ratio . . . . . . . . . . . . . . . . . . . 15
3.3.2 GMM Supervector SVM . . . . . . . . . . . . . . . . . 18
3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4.1 Experimental Conditions . . . . . . . . . . . . . . . . . 23
3.4.2 Detection Accuracy . . . . . . . . . . . . . . . . . . . . 23
3.4.3 Multi-frame Feature Extraction . . . . . . . . . . . . . 24
3.4.4 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . 24
3.4.5 Comparison with Other Methods . . . . . . . . . . . . 28
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Tree-structured Gaussian Mixture Models

36

4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Tree-structured GMMs . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Fast MAP Adaptation . . . . . . . . . . . . . . . . . . . . . . . 41

iii

CONTENTS

iv

4.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4.1 Database and Task . . . . . . . . . . . . . . . . . . . . 43
4.4.2 Experimental Conditions . . . . . . . . . . . . . . . . . 44
4.4.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5 q-Gaussian Mixture Models

54

5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2 q-Gaussian Mixture Models . . . . . . . . . . . . . . . . . . . 55
5.3 Training q-GMM for a Background Model. . . . . . . . . . . 57

5.4 q-GMM for histogram-based image representation . . . . . . . 59
5.5 q-GMM Kernel . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.6.1 Experimental Conditions . . . . . . . . . . . . . . . . . 62
5.6.2 Experimental Results . . . . . . . . . . . . . . . . . . . 64
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6 Neighbor-To-Neighbor Search72

6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.2 Neighbor-To-Neighbor (NTN) Search for Vector Quantization73

6.2.1 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.2.3 The parameter δ . . . . . . . . . . . . . . . . . . . . . 76
6.3 NTN Search for Gaussian Mixture Models . . . . . . . . . . . 77
6.4 Experimental evaluation . . . . . . . . . . . . . . . . . . . . . 80
6.4.1 Experimental setup . . . . . . . . . . . . . . . . . . . . 80
6.4.2 Experimental Results . . . . . . . . . . . . . . . . . . . 82
6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7 Conclusion and Future Work91

List of Figures
2.1 The most common framework for semantic indexing: 1) Lowlevel features are extracted from video, 2) A Video/Image
representation is extracted, 3) A detection score is calculated.

5

3.1 Overview of our semantic indexing system. Our system consists of three parts: 1) low-level feature extraction, 2) GMM
supervector extraction by using fast MAP adaptation, and 3)
SVM classification. First, visual and audio features are extracted. Second, GMM parameters are estimated by using
MAP adaptation. Tree-structured GMMs are used to improve
the speed of MAP adaptation. Third, the outputs of SVMs forthe four feature types are fused to compute a final score.

. . 103.2 Harris corner detector . . . . . . . . . . . . . . . . . . . . . . 11
3.3 SIFT descriptor . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4 A hyperplane that maximizes the margin. . . . . . . . . . . . 21
3.5 An example of a kernel trick. Data is not linearly separable in(a). The data becomes linearly separable in (b) after transforming the input data to a new feature space. . . . . . . . . . 22
3.6 Number of appearances of semantic concepts . . . . . . . . . 24
3.7 Comparison of Mean APs for different schemes. . . . . . . . . 25
3.8 Mean APs with different numbers of frames. The dotted line
indicates the average number of frames in a shot. . . . . . . . 25
3.9 InfAP by semantic concepts on the TRECVID 2011 Semantic
Indexing Dataset.

. . . . . . . . . . . . . . . . . . . . . . . . 28v

LIST OF FIGURES

vi

3.10 2D visualization of 4D Average Precisions (APs) for Har-SIFT,
Hes-SIFT, Dense-SIFTH and MFCC. To compare the effectiveness of each type of feature, the four AP values are normalized so that their sum is one. . . . . . . . . . . . . . . . . . . 29
3.11 Top 25 video shots for “Bus”. Correct shots are marked in red. 30
3.12 Top 25 video shots for “Female Human Face Closeup”. Correct shots are marked in red.

. . . . . . . . . . . . . . . . . . 30

3.13 Top 25 video shots for “Airplane Flying”. Correct shots aremarked in red. . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.14 Top 25 video shots for “Running”. Correct shots are marked
in red. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.15 Top 25 video shots for “Cityscape”. Correct shots are marked
in red. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.16 Top 25 video shots for “Mountain”. Correct shots are marked
in red. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.17 Top 25 video shots for “Dark-skinned People”. Correct shots
are marked in red. . . . . . . . . . . . . . . . . . . . . . . . . 33
3.18 Top 25 video shots for “Singing”. Correct shots are marked inred. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.19 Comparison with other methods on TRECVID 2011. . . . . . . 34
3.20 Comparison with other methods on TRECVID 2012. . . . . . . 34
4.1 An example of a tree-structured GMM T(2,3) . . . . . . . . . . . 39
4.2 Example video shots for training and testing sets. The top
5 results obtained by using our system (multi-modal fusion)
are shown in the right side of the figure. . . . . . . . . . . . . 46
4.3 Calculation time for each step (The lower bars for each feature show the time in the case that the optimized tree wasused). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.4 Mean absolute error (MAE) of cik obtained using different
tree structures (the SIFTH-Dense feature and cTH = 0.001
were used). 1,364 trees of depth at most 5 that have at most
5 children per node and the binary tree are tested. All MAE
were less than 0.05. . . . . . . . . . . . . . . . . . . . . . . . 50

LIST OF FIGURES

vii

4.5 Calculation time obtained using different tree structures (theSIFTH-Dense feature and cTH = 0.001 were used). 1,364 treesof depth at most 5 that have at most 5 children per node andthe binary tree are tested. T(3,4,4,5) was the best tree and wasselected as the optimized tree.

. . . . . . . . . . . . . . . . . 51

4.6 Comparison of Mean Inf AP with runs of the TRECVID 2010. . 51
4.7 Results of partial randomization test (p < 0.05). Significant
differences among top 10 runs in TRECVID 2010 and our fusion methods are shown. A black cell shows that there issignificant difference between two methods.

. . . . . . . . . 52

5.1 The framework of image and video semantic indexing using
q-Gaussian mixture models. . . . . . . . . . . . . . . . . . . . 55
5.2 The q-Gaussian distributions. The (normal) Gaussian distribution is obtained when q = 1. The tail of a q-Gaussian distribution is longer than that of a Gaussian distribution whenq > 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.3 (a): Standardized histogram of the first elements of standardized SIFT descriptors. 1 million low-level descriptors are
randomly sampled from training data of PASCAL VOC 2010
dataset. (b-1), (b-2): A fitting result by a Gaussian distribution and its residuals. (c-1), (c-2): A fitting result by aq-Gaussian distribution (q = 1.12) and its residuals.

. . . . . 56

5.4 Assignment hardness h with different q-values. . . . . . . . . 61
5.5 The performance comparison of q-GMM kernels with different q-values on the PASCAL VOC 2010 dataset. The q-GMM
kernel outperforms the GMM baseline (q = 1.00) and the improved Fisher kernel [37] of GMM means. . . . . . . . . . . . 64
5.6 Mean AP on PASCAL VOC 2010 for different numbers of mixture components for q-GMM kernel. . . . . . . . . . . . . . . . 65
5.7 Mean AP on PASCAL VOC 2010 for different hyper-parameterτ in maximum a posteriori adaptation for q-GMM kernel. . . . 66
5.8 The performance comparison of q-GMM kernels with different q-values on the TRECVID 2010 dataset. . . . . . . . . . . 66

LIST OF FIGURES

viii

5.9 The performance comparison with other methods in TRECVID
2010. We achieved 0.071 in Mean AP by using a q-GMM
kernel with SIFT-HueHistogram features and achieved 0.109
with additional 4 types of low-level features. . . . . . . . . . . 67
5.10 Examples of detected video shots in TRECVID 2010 dataset.
Top 5 video shots are shown for ten semantic concepts. . . . . 67
6.1 Neighbor-to-neighbor (NTN) search. NTN search assigns acode to an input vector from a neighbor vector to a neighbor
vector. A typical example of a neighbor vector is a descriptor
xj adjacent to a descriptor xj−1 where image descriptors aredensely sampled from an image. The red path on the image
shows the ordering of descriptors.

. . . . . . . . . . . . . . . 73

6.2 A histogram of descriptors. Red bars: descriptors that havethe same visual word as a neighbor descriptor. White bars:
all descriptors. SIFT descriptors are extracted from every 4
pixels at 5 scales on the PASCAL VOC 2007 training images.
The codebook size is 512. 61.3% of two adjacent descriptors
have the same visual word. . . . . . . . . . . . . . . . . . . . 74
6.3 Algorithm overview.

. . . . . . . . . . . . . . . . . . . . . . 74

6.4 Distribution of pik and pjk(i < j). Calculation of a Gaus6.5

sian probability pjk is skipped for k ∈ Uik . . . . . . . . . . . . 80
Relative computational cost. Computational cost for eachstep of super-vector (SV) coding and Fisher-vector (FV) coding is reported. The codebook size is 512. Feature extraction:
SIFT descriptors are extracted from every 4 pixels at 5 scales,
Coding: each descriptor is assigned to codeword(s), Pooling: an SV or FV image representation is generated. 85.3%,
56.6%, 88.4%, 65.4% and 64.2% of computational time is occupied from coding by VQ, NTN-VQ, GMM, NTN-GMM, and
NTN-LM-GMM, respectively. Total computational cost is reduced by 66.0%, 66.5% and 85.3% by NTN-VQ, NTN-GMM,
and NTN-LM-GMM, respectively. . . . . . . . . . . . . . . . . 82
6.6 Cumulative histogram of δ ∗. Statistics of the true δ ∗ in
Eq. (6.8) on PASCAL VOC 2007 training images is reported
for NTN-VQ.

. . . . . . . . . . . . . . . . . . . . . . . . . . . 84

LIST OF FIGURES

ix

6.7 Speed-accuracy trade-off for different values of δ. Tradeoff between assignment time and Mean AP is reported. Allplots are for δ = 1.0, 0.9, · · · 0.1, 0.09, · · · , 0.01. VQ: stan-

dard hard vector quantization (VQ), NTN-VQ: neighbor-toneighbor (NTN) search for VQ, GMM: standard Gaussian mixture model (GMM), NTN-GMM: NTN search for a GMM, NTNLM-GMM: NTN-GMM with the log-max approximation.

. . . 85

6.8 Comparison with RAND-VQ. Trade-off between assignment
time and Mean AP is reported. NTN-VQ: neighbor-to-neighbor(NTN) search for VQ, this is the same plot as Figure 6.7, ANNVQ: approximate nearest neighbor search [15], RAND-VQ:
NTN-VQ in which a neighbor vector is replaced by a randomly
sampled vector.

. . . . . . . . . . . . . . . . . . . . . . . . . 86

6.9 Comparison of the accumulated distance and the direct
distance. VQ error rate in NTN-VQ for different values of δis reported. All plots are for δ = 1.0, 0.9, · · · 0.1, 0.09, · · · 0.01.
Accumulated distance: ∆ij is defined by Eq. (6.6). Direct

distance: ∆ij is replaced by the direct distance "xi − xj ".

Pre-computed direct distance: the direct distance is used but
distance calculations for it are not counted. . . . . . . . . . . 87
6.10 The computational cost reduction by NTN-VQ for different
images. Four images (a), (b), (c), and (d) are from PASCAL
VOC 2007. The reduction rate of the assignment cost by NTNVQ and ANN-VQ for each image is reported. . . . . . . . . . . 88
6.11 Speed-accuracy trade-off for different codebook sizes. Tradeoff between assignment time and Mean AP for codebook sizesof K = 2048, 1024, 512, · · · , 16. is reported. VQ: standard

hard vector quantization (VQ), NTN-VQ: neighbor-to-neighbor(NTN) search for VQ δ = 0.20, GMM: standard Gaussian
mixture model (GMM), NTN-GMM: NTN search for a GMM
δ = 0.09, NTN-LM-GMM: NTN-GMM with the log-max approximation δ = 0.09. . . . . . . . . . . . . . . . . . . . . . . 89

List of Tables
3.1 Mean APs for different schemes (K = 512). R denotes a
result of Randomization test (p = 0.05). . . . . . . . . . . . . 26
4.1 The 30 target semantic concepts in the TRECVID 2010 dataset 44
4.2 The average numbers of extracted features. . . . . . . . . . . 44
4.3 Resulting inferred average precisions (Inf APs) for each semantic concept and for each method. Mean Inf APs on thetesting set and Mean APs on a two-fold cross-validation splitof the training data are also shown.

. . . . . . . . . . . . . . 47

4.4 Resulting inferred average precisions (Inf APs) for each semantic concept and for each method. Mean Inf APs on thetesting set and Mean APs on a two-fold cross-validation splitof the training data are also shown.

. . . . . . . . . . . . . . 48

4.5 Calculation time (sec) for MAP adaptation. Calculation time
was measured by using a single core of Intel Xeon 2.93 GHz
CPU. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6 Comparison of Mean Inf AP, calculation time (sec) for MAP
adaptation, number of leaf nodes |VA | and Mean absolute

error (MAE) of cik by using different thresholds cTH for the
SIFTH-Dense feature. . . . . . . . . . . . . . . . . . . . . . . . 52
5.1 The targeted semantic concepts for PASCAL VOC 2010 and
TRECVID 2010. . . . . . . . . . . . . . . . . . . . . . . . . . . 63x

LIST OF TABLES

xi

5.2 Performance comparison on PASCAL VOC 2010 dataset. BoW:
bag-of-visual-words histogram representation [3] obtained byusing vector quantization. Our histogram: q-GMM based histogram representation in Sec. 5.4 for q = 1.00 (GMM) and
q = 1.05. χ2 kernel: χ2 kernel on q-GMM histogram representation. FK: Fisher kernel [36] of a GMM. IFK: improved
Fisher kernel [37]. Our kernel: q-GMM kernel in Sec.5.5 for
q = 1.00 (GMM) and q = 1.05.

. . . . . . . . . . . . . . . . . 68

5.3 Testing cost and Mean AP for each method. K is the numberof mixture components, D is the dimension of low-level descriptor, and N is the averaged number of support vectors ofan SVM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.4 Average precision (AP) by semantic concepts on TRECVID
2010. Results for GMM, q-GMM (q = 1.05), score fusion of
GMM and q-GMM (q = 1.05), and feature fusion of 5 types ofvisual and audio features for q-GMM are reported. . . . . . . 70
6.1 Speed comparison at the fixed accuracy level. VQ: standard hard vector quantization (VQ), ANN-VQ: approximate
nearest neighbor search [15], NTN-VQ: our neighbor-to-neighbor(NTN) search for VQ (Alg. 1), GMM: standard Gaussian mixture model (GMM), Tree-GMM: an extension of the hierarchical k-means to a GMM framework, NTN-GMM: our NTN
search for a GMM (Alg. 2), NTN-LM-GMM: NTN-GMM withlog-max approximation. δ: a parameter of our NTN methods,
Mean AP: image classification accuracy on the testing set andthe validation set of the VOC 2007 classification challenge.
|E|: the number of distance or probability calculations per
input vector, Time: assignment time in sec, Reduction rate r:

reduction rate of the assignment cost. Note that there are no
statistically significant differences in Mean AP between themethod marked “*” and each other method in the same split
table on randomization test (p < 0.05).

. . . . . . . . . . . . 83

Chapter 1

Introduction
Recently, a large amount of video data has been made available throughonline archives. For example, over 6 billion hours of video are viewed eachmonth on YouTube. Since it is often difficult to find relevant video manuallyfrom such archives, an effective video-search system is in demand. Current
search engines require users to develop metadata such as key-words anda short summarization in text to efficiently locate video in their archives.
However, developing metadata is costly for users so attached metadata isoften too simple and not enough for video-search purposes. Furthermore,detailed metadata is required for video-segment retrieval aiming at finding
a specific scene or a specific object in video. Video-segment retrieval is still
known to be in a nascent stage [1] and thus is hardly served by present-day
search engines.
In this study, we focus on semantic indexing which is necessary as abasis for automatically generating metadata. Semantic indexing aims to assign semantic concepts, which include objects, actions, and scenes such as
airplane, bus, singing, dancing, cityscape, and nighttime, to video segments.
This has been a challenging task due to the semantic gap [2]: “the lack ofcorrespondence between the low-level features and the high-level semantic concepts”, where low-level features present color, texture, shape, andspatiotemporal features extracted from video.
Most previous studies used a statistical model to construct the relationship between low-level features and semantic concepts. In particular, thebag-of-visual-words (BoW) [3, 4], a statistical method for image recognition, has been proven to be effective for video semantic indexing. It repre1

Introduction

2

sents an image by a histogram of low-level image descriptors such as scaleinvariant feature transform (SIFT) [5]. In BoW, vector quantization (VQ) is
needed to extract a histogram. However, quantization errors often degrade
the indexing performance. To solve this problem, several soft clustering
methods [6, 7, 8] are introduced. In particular, Gaussian mixture models(GMMs) [8] are often preferred since they are a straightforward extensionof VQ to a probabilistic framework.
In video search, we should consider not only image information but also
audio information to find video that the user wishes to view [9, 10, 11]. For
example, a combination of a music and an action sometimes has a specificmeaning in a dance scene. Some previous studies have analyzed speech innews video [12, 13] by using speech recognition methods. However, they
are not very effective for video other than news such as consumer generated video in which speech is often spontaneous with noise or a backgroundmusic. Furthermore, acoustic information other than speech, for example
sounds from a musical instrument, can not be captured by the speech recognition methods. To capture visual and audio information effectively, a multimodal method is necessary for semantic indexing.
On the other hand, since video has more information than an image,computational cost becomes a problem in real applications. Since vector
quantization is the most computationally expensive part in the BoW algorithm [3], many studies have been done to develop fast VQ algorithms. For
example, approximate nearest neighbor (ANN) algorithms such as randomized kd-trees [14] and hierarchical k-means tree [15] are known to provide
speed-ups VQ with only minor loss in accuracy. To improve both speed andaccuracy, we need to extend them to a probabilistic framework, for example
to GMMs.
In this study, we propose a fast and accurate semantic indexing system.
We have four main contributions as follows. 1) A multi-modal semantic
indexing system which uses GMMs : we extend the BoW to a probabilistic
framework where a video shot is represented by a GMM. Audio and visualfeatures are extracted from video. 2) A fast parameter estimation techniqueusing a tree-structured GMM : we propose fast maximum a posteriori (MAP)
adaptation for estimating GMM parameters. 3) An improved modeling by aq-GMM : we improve the accuracy of modeling by introducing a parameterq to control the tail-heaviness of a GMM. 4) A fast search technique namely

Introduction

3

Neighbor-to-Neighbor (NTN) search : we further improve the speed of thesystem especially when densely-sampled image descriptors are used.
The remainder of the dissertation is organized as follows. Chapter 2
gives an over view of semantic indexing. Chapter 3 describes the multimodal semantic indexing system. Chapter 4 describes the fast MAP estimation technique using a tree-structured GMM . Chapter 5 describes theextension of the system to q-Gaussian mixture models. Chapter 6 describes
the NTN search. Finally, conclusions and future work are described in Chapter 7.

Chapter 2

Semantic Indexing
In this chapter, the fundamental approaches to semantic indexing will be discussed. The most common framework for semantic indexing consists of thethree steps in Figure 2.1. In the first step, low-level features are extracted.
Here, video is represented by a set of low-level features X = {xi }N
i=1 wherexi ∈ Rd is a vector describing local information such as RGB-color and texture, and N is the number of low-level features. In the second step, video isrepresented by a vector φ(X). This vector is so-called a video representation,for example a histogram representation in the bag-of-visual-word approach[3, 4]. In the third step, a detection score f (φ(X)) is calculated where f is adiscriminative function often trained based on supervised learning methods.
Relation between semantic concepts sometimes considered in this step. The
following sections discuss previous approaches for each step.

2.1 Low-Level Feature Extraction
Low-level feature extraction typically consists of two phases: key-point detection and feature description.
Key-Point Detection
In the first phase, key-point detectors are applied to find interest regions
in video or in an image. Many detectors are proposed not for semantic indexing but for other computer-vision applications such as image matching[16, 17, 18], texture recognition [19], and robot servoing [20, 21]. However, they are also often effective for semantic indexing.
4

Semantic Indexing

5

Figure 2.1: The most common framework for semantic indexing: 1) Low-levelfeatures are extracted from video, 2) A Video/Image representation is
extracted, 3) A detection score is calculated.

For image matching, Lowe [5] proposed Scale Invariant Feature Transform (SIFT), which is the most widely used algorithm in many applications.
In SIFT, key-points are detected based on the Difference-of-Gaussian (DoG)
detector which is a simplification of the Laplacian-of-Gaussian (LoG) detector [5] to detect edges in a scale invariant way. Mikolajczyk et al. [22]proposed the Harris-affine detector which is robust against affine transforms. They also proposed the Hessian-affine detector to detect blob structure, which is complementary to the Harris-affine detector. Maximally stable external region (MSER) [17] focused on segmentation in an image andis a precise blob detector while its computational cost is higher than the
Hessian-affine detector. For image classification, dense sampling which uses
grid points have shown to be effective [23, 37]. The combination of dense
sampling with above key-point detectors often improve the performance ofimage classification. For action recognition in video, some works focus on
temporal information. Space-Time Interest Points (STIP) [24] extends theHarris-corner detector to video. Dense Trajectories [25] tracks objects invideo at grid points.
Feature Description
In the second phase, a feature vector is extracted from each local region
around a key-point. SIFT [5] extracts local gradient vectors which are robust against changes in scale, rotation, and illumination. A SIFT vector is
128 dimensional which consists of 8-dimensional histograms for 4x4 blocks.
Histogram of oriented gradients (HOG) [26] proposed for human detection
also extracts local gradient vectors as SIFT, but its dimension is often larger
than SIFT. A typical HOG vector concatenates 9-dimensional histograms for
7x15 blocks. Local binary pattern (LBP) is another feature robust against

Semantic Indexing

6

changes in illumination. The combination of HOG and LBP is proposedin [27] for human detection. Note that these features are extracted froma gray-scale image. To capture color information, J. Weijer proposed hue
histogram [28] and its combination with SIFT. Extensions of SIFT to color
spaces such as HSV space and Opponent SIFT are proposed in [29].
Some works focused on fast algorithms and implementations of SIFT.
Speeded-Up Robust Features (SURF) improved the speed of Hessian detector and used it instead of the DoG detector in SIFT. BRIEF [30] and ORB[31], which are specialized for image matching, further improved the speed
by introducing binary descriptors. GPU implementations [32, 67, 68] are
known to be effective for large-scale image processing.

2.2 ModelingIn the bag-of-visual-words (BoW) approach [3], an image is represented
as a histogram of visual words obtained by applying VQ to each low-leveldescriptors. k-means clustering is often used for training a visual codebook
that consists of several thousands of visual words.
Soft-assignment approaches are effective for reducing quantization errors in VQ and thus they outperform BoW. Gemert et al. [6] proposed akernel codebook in which each low-level descriptor is assigned to all visual
words in a soft manner with weighting. Hang et al. [33, 7] used sparse coding which assigns a low-level descriptor to several tens of visual words bysolving a constrained least square fitting problem. Perronnin et al. [8] useda Gaussian mixture model (GMM) for a codebook which holds mean andvariance information for each visual word. The GMM is a straight-forward
extension of BoW to a probabilistic framework.
Recently, high-dimensional image representations have been proven tobe effective in image classification. Vector of locally aggregated descriptor(VLAD) [34] and super-vector coding [23] use the first order differences
between low-level descriptors and visual words in addition to the BoW histogram. Fisher vector [35] represents an image as a concatenation of parameters of a parametric probability model. Perronnin et al. [36, 37] achieved
the best performance in the PASCAL VOC image classification challenge byusing a GMM as the parametric probability model for the Fisher vector. They
reported that an normalization technique [37] is needed since the Fisher

Semantic Indexing

7

vectors become sparser as the number of Gaussians increases. They proposed the L2+power normalization to make the Fisher vectors dense. The
normalized fisher vector is called “improved Fisher kernel (IFK)”. Chatfield
et al. [38] reported that IFK is the best of these recent image representations.
On the other hand, several previous works focused on applying Tsallis
statistics [39, 40, 41] to image processing. Tsallis q-entropy, which is a generalization of the Boltzmann-Gibbs (BG) entropy, is used for image thresholding for foreground extraction in [42, 43, 44, 45]. These works show that
long-range correlation between foreground pixels can be modeled by using
the Tsallis q-entropy. Fabbrib et al. [46] applied Tsallis q-entropy to image texture classification. They reported that texture classification accuracy
is improved by using Tsallis q-entropies for multiple q-values as a feature
vector. A q-Gaussian distribution, which is a generalization of Gaussian distribution and Student’s t-distribution, is expected to effectively represent
a distribution of low-level features in the bag-of-visual-words framework.
Since a mixture of long-tailed distirbutions such as a t-mixture model [49]improves the performance of image registration [47] and image segmentation [48], we expect it will improve the performance of semantic indexing.
To the best of our knowledge, we are the first to apply Tsallis statistics to thebag-of-visual-words framework.
To reduce the cost of this step, many previous studies have shown thata tree-sturucture is effective. Nistér et al. [50] propose a “vocabulary tree”
which uses a hierarchical k-means tree. Lowe [5] uses a kd-tree for nearest
neighbor search of SIFT descriptors. Muja and Lowe [15] have proposed an
automatic selection method from the recent two approximate nearest neighbor (ANN) algorithms: randomized kd-trees [14], and hierarchical k-means
tree [15]. They have provided it as a fast software library for approximate
nearest neighbors (FLANN). Sparse coding [33] assigns several tens of codewords to an input vector by solving a constrained least square fitting problem. J. Wang el al. [7] introduced k-nearest neighbor (k-NN) search as the
preprocessing to the sparse coding. The tree-structured GMM in this study
extends the hierarchical k-means to a GMM framework.

Semantic Indexing8

2.3 Detection
In the detection step, a discriminative function to compute confidense scores
is trained on labeled data. Here, we focus on supervised learning methods.
In semantic indexing, a learning method must handle imbalance in thenumber of positives and negatives since the number of positive samples areoften limited. Moreover, it also must handle the problem of the curse ofdimensionality since the dimension of a video/image representation is oftenvery high. In this demands, the most well-known and effective method is
the support vector machine (SVM), which separates a feature space into two
different classes, positive and negative. To estimate a posterior probability,
a probability for a particular semantic concept which is not given by an
SVM, Platt [51] and Lin et al. [52] suggest a sigmoid fitting of SVM scores
where parameters in the sigmoid function are estimated based on maximum
likelihood criteria. The logistic regression (LR) is also known to estimates
the posterior probability. While the LR sometimes performs better than the
SVM, its computational cost is also larger than the SVM. Hence, the SVM
has become the default choice in most semantic indexing schemes.
In many supervised learning methods including the SVM and the LR,a kernel trick which enables non-linear classification often improves theclassification performance significantly. In general, the (Gaussian) radialbasis function (RBF) kernel is almost the best choice. However, Zhang [53]showed that earth-movers-distance kernel [54] and χ2 kernel are more optimal than it in the bag-of-visual-words framework. Since the BoW represents
an image by a histogram of visual words, which sometimes have frequent
but meaningless words, these kernels consider a normalization of the histogram to obtain better performance than the RBF. Some recent works arefocusing on kernel learning. For example, multiple kernel learning (MKL)[55] enables to learn a linear combination of pre-dfined kernels, e.g. kernels
for different types of features. Multiple kernel Fisher discriminant analysis(MK-FDA) [56] is an extension of the FDA to multiple kernels. However,these methods are computationally more expensive than the SVM. The linear combination of SVM scores is known to be a reasonable alternative forthem.

Chapter 3

Multi-Modal Semantic
Indexing
3.1 Overview
In this chapter, we describe our multi-modal semantic indexing system,
which uses Gaussian-mixture-model (GMM) supervectors. The overview
of our semantic indexing system is shown in Fig. 3.1. We assume videos
are automatically segmented into shots in preprocessing. A shot consists ofcontinuous frames without switching between cameras.
Our system consists of three parts. First, visual and audio low-level features are extracted from a video shot. The SIFT features are extracted byusing three different interest point detectors: Harris-Affine [22], HessianAffine [22], and Dense [57]. The MFCCs, which describe the short-time
spectral shape of audio frames, are extracted to capture audio information.
The details of low-level feature extraction are described in Sec 3.2. Second,a GMM supervector is created for each type of low-level features. A GMM
models the distribution of low-level features extracted from a video shot.
Its parameter is estimated by using MAP adaptation. Third, SVM scores foreach type of low-level features are fused to compute a final score.

9

Multi-Modal Semantic Indexing

10

Figure 3.1: Overview of our semantic indexing system. Our system consists ofthree parts: 1) low-level feature extraction, 2) GMM supervector extraction by using fast MAP adaptation, and 3) SVM classification. First,
visual and audio features are extracted. Second, GMM parameters are
estimated by using MAP adaptation. Tree-structured GMMs are used
to improve the speed of MAP adaptation. Third, the outputs of SVMs
for the four feature types are fused to compute a final score.

3.2 Feature Extraction
3.2.1 Visual Features
SIFT features with Harris-Affine detector (Har-SIFT)
Scale-invariant feature transform (SIFT) [5] is a low-level feature extraction
method that is widely used for object categorization. The extracted features
are invariant to image scaling and changing illumination. The Harris-Affine
local region detector [22], which is an extension of the Harris corner detector, provides affine-invariant local regions.
Let I(x, y) be the luminosity value at a point (x, y). A point (x, y) is a
Harris corner if the following value R is larger than a predetermined threshold (Figure 3.2),
R = det M − k (traceM )2 = λ1 λ2 − k (λ1 + λ2 )2(3.1)

where k is a parameter, λ1 and λ2 are eigenvalues of the following matrixM:
2
M = σDg(σI ) ∗!

Ix2 (x, y, σD )Ix Iy (x, y, σD )Ix Iy (x, y, σD )Iy2 (x, y, σD )

"

.

(3.2)

Multi-Modal Semantic Indexing

Figure 3.2: Harris corner detector

11

Multi-Modal Semantic Indexing

12Here, g(σI ) is a Gaussian fuction with a window size of σI and Ix , Iy are thepartial derivative of I(x, y) given byIx (x, y, σD ) = I(x + 1, y, σD ) − I(x − 1, y, σD )Iy (x, y, σD ) = I(x, y + 1, σD ) − I(x, y − 1, σD ).

(3.3)
(3.4)

For each corner point, a SIFT descriptor is extracted as follows (Figure 3.3).
1. Compute a gradient m(x, y) and an orientation θ(x, y) bym(x, y) =#(Ix (x, y, σD ))2 + (Iy (x, y, σD ))2 ,θ(x, y) = tan−1

Iy (x, y, σD ).
Ix (x, y, σD )

(3.5)
(3.6)

2. Split a local region into 4x4 blocks to compute a histogram of oriented
gradients of 8 directions {θi = π4 i}7i=0 for each block.
hi =$

w(x, y)δ(θi , θ(x, y)),

(3.7)

x,y

w(x, y) = G(x, y, σ)m(x, y).

(3.8)

3. Concatenate 16 histograms to obtain 128-dimensional vector.
The proposed method uses 32-dimension SIFT features, whose dimensions are reduced from 128 to 32 by applying principal component analysis(PCA). The SIFT features are extracted from every other frame in a video
shot.
SIFT features with Hessian-Affine detector (Hes-SIFT)
A Hessian-Affine detector [22] is complementary to the Harris-Affine detector. A point (x, y) is a Hessian key-point if the following detH and traceH
take an extreme value at (x, y),2
detH = Ixx Iyy (x, y, σD ) − Ixy(x, y, σD ),traceH = Ixx (x, y, σD ) + Iyy (x, y, σD ),(3.9)(3.10)

Multi-Modal Semantic Indexing

Figure 3.3: SIFT descriptor

13

Multi-Modal Semantic Indexing

14

where H is an Hessian matrix given byH=!

Ixx (x, y, σD ) Ixy (x, y, σD )Ixy (x, y, σD ) Iyy (x, y, σD )"(3.11)

The combination of several different detectors can improve the robustness against noise. SIFT descriptors are extracted in the same way as SIFT
with a Harris-Affine detector. PCA is applied to reduce their dimensions
from 128 to 32.
SIFT and hue histogram with dense sampling (Dense-SIFTH)
To capture color information, SIFT features and hue histograms [28] arecombined. As a result, 164 dimensional low-level features (which consistof 128-dimension SIFT features and 36-dimension hue histograms) are obtained. PCA is also used to reduce the dimensions to 32. This feature is
extracted only from key frames by using dense sampling, which provides amuch larger number of low-level features than sparse sampling such as theHarris-Affine and Hessian-Affine detectors.
HOG with dense sampling (Dense-HOG)
32-dimensional histogram of oriented gradients (HOG) are extracted fromup to 100 frames per shot by using dense sampling with 2x2 blocks. PCA isapplied but dimensions of the HOG features are kept to 32.
LBP with dense sampling (Dense-LBP)
Local Binary Patterns (LBPs) [27] are extracted from up to 100 frames per
shot by using dense sampling with 2x2 blocks to capture texture information. We follow the procedure in [27] to extract LBP features. PCA is applied
to reduce dimensions from 228 to 32.

3.2.2 Audio Features
MFCC audio features (MFCC)
Mel-frequency cepstral coefficients (MFCCs), which describe the short-time
spectral shape of audio frames, are extracted to capture audio informa-

Multi-Modal Semantic Indexing

15

tion. Semantic concepts related to people speaking, talking, and singing
can be detected by using MFCCs since MFCCs are effective for speech recognition and audio classification. The 38-dimension audio features consist of
12-dimension MFCCs, 12-dimension ∆ MFCCs, 12-dimension ∆∆ MFCCs,
1-dimension ∆ log-power and 1-dimension ∆∆ log-power are extracted.
Here, “∆” means the derivative of the feature.

3.3 Detection Methods
3.3.1 Log-Likelihood Ratio
A detection score of a log-likelihood ratio detector is given by
L=p(X|H = +1),
p(X|H = −1)(3.12)

where X is a set of low-level features extracted from a video shot and H isa random variable that takes +1 if a targeted semantic concept appears inthe shot and otherwise −1.

A probability p(·|H) is estimated by using a Gaussian mixture model(GMM). The probability density function (pdf) of a GMM is given byp(x|θ) =K$
k=1

wk N (x|µk , Σk ),(3.13)

where x ∈ X is a low-level feature, θ = {wk , µk , Σk }K
k=1 is a set of GMM
parameters, K is the number of Gaussian components (vocabulary size),

wk is a mixture coefficient, and N (x|µk , Σk ) is a Gaussian pdf with a mean
vector µk and a covariance matrix Σk . Here, we assume X = {xi }Ni=1 is i.i.d.
to obtainp(X|θ) =N%
i=1

p(xi |θ).

(3.14)EM Algorithm
The expectation-maximization (EM) algorithm [58] is a standard way tofind the maximum likelihood (ML) solution for models with latent variables.
For each model parameter in θ, we set the derivatives of log p(X|θ) to zero.

Multi-Modal Semantic Indexing

16

Note that this is the condition that a ML solution must satisfy. With respect
to the mean vector µk of a GMM, by setting the derivative of log p(X|θ) tozero, we obtain
0=−

N
$
i=1

&

wk N (xi |µk , Σk )
Σk (xi − µk ),k! wk! N (xi |µk! , Σk! )(3.15)

where cik is a responsibility (posterior probabilities) given by
cik = &

wk N (xi |µk , Σk ).
k! wk! N (xi |µk! , Σk! )(3.16)

By assuming that Σ−1
k is a nonsingular matrix, we obtain
N

µ̂k =

1 $
cik xi ,Ck(3.17)

i=1

by multiplying Σ−1
k to Eq (3.15), where Ck is the sum of responsibilities
given by
Ck =

N
$

cik .

(3.18)

i=1

This shows that the ML solution of the mean vector µ̂k is the weighted sumof all vectors in X with weighting factor cik .
With respect to the covariance matrix Σk of a GMM, by setting thederivative of log p(X|θ) to zero, we obtain
N

Σ̂k =

1 $
cik (xi − µ̂k )(xi − µ̂k )T .
Ck

(3.19)

i=1

This also shows that the ML solution is the weighted sum of the ML solution of a single Gaussian. which has the same form as the corresponding
result for a single Gaussian fitted to the data set, but again with each data
point weighted by the corresponding posterior probability and with the denominator given by the effective number of points associated with the corresponding component.
For the mixture coefficient wk , we use a Lagrange multiplier since thesum of the coefficients has to be one. By introducing a Lagrange multiplierMulti-Modal Semantic Indexing

17

λ, instead of log p(X|θ), we maximize
log p(X|θ) + λ

' K
$

k! =1

(

wk! − 1 ,(3.20)

which gives
0=

N
$
i=1

N (xi |µk , Σk )+ λ.
k! wk! N (xi |µk! , Σk! )&(3.21)

By taking sum over k, we obtain λ = −N . The ML solution for wk is givenbyCk.
k! Ck!

wk = &(3.22)The EM algorithm has two steps: E step and M step. In the E step,
responsibilities are evaluated with the current parameters. In the M step,
parameters are updated by using responsibilities obtained at E step. The
following summarizes the EM algorithm for a GMM.
1. Initialize mean vectors µ̂k , covariance matrixes Σ̂k and mixture coefficients ŵk . Compute the initial value for the likelihood function.
2. E step. Compute the responsibilities as
cik = &Kŵk N (xi |µ̂k , Σ̂k )k! =1 ŵk! N (xi |µ̂k! , Σ̂k! ),(3.23)

by using the current parameters.
3. M step. Update the parameters asN

1 $cik xi ,Ck(3.24)cik (xi − µ̂k )(xi − µ̂k )T ,(3.25)Ck,
k ! Ck !

(3.26)

µ̂k ←
Σ̂k ←

N
1 $

Ck

i=1

i=1

ŵk ← &

Multi-Modal Semantic Indexing

18

where
Ck =

N
$

(3.27)

cik ,i=1

by using the current responsibilities.
4. Compute the log likelihood function bylog p(X|θ̂) =

N
$

log

i=1

)K
$
k=1

*

ŵk N (xi |µ̂k , Σ̂k ) ,(3.28)

to check for convergence. Return to the step 2 until convergence.

3.3.2 GMM Supervector SVM
The GMM supervector SVM is another powerful model for detecting semantic concepts. A GMM supervector, which is used as an input of a support
vector machine, is the concatenation of GMM parameters estimated for each
video shot.
MAP Adaptation for GMM
As described above, the GMM parameters are often estimated by using the
EM algorithm with the maximum likelihood criterion. However, a set of
extracted low-level feature vectors may not be enough to estimate the parameters precisely. In such cases, the alternative way is to use maximum aposteriori (MAP) adaptation. MAP adaptation, a parameter estimation using the MAP criterion, is robust against over-fitting caused by limited data
since it uses a prior distribution. A GMM for prior distribution, namely auniversal background model (UBM), is first estimated by applying the EM
algorithm to all the training data. The UBM presents the feature distribution
for the whole database.

Multi-Modal Semantic Indexing

19

The MAP solution for GMM means, namely MAP adaptation, is given by&(U)τ µ̂k + ni=1 cik xiµ̂k =,τ + Ckwk gk (xi )cik = &K,
k=1 wk gk (xi )
n
$
Ck =
cik ,

(3.29)(3.30)(3.31)

i=1(U)(U)
gk (x) = N (x|µ̂k , Σ̂k ),(3.32)

where X = {xi }ni=1 is a set of feature vectors extracted from a shot, τ is apredefined hyper-parameter, and θ̂(U) is the parameter for a universal back-ground model (UBM). The UBM presents how the features are distributedin the general case: therefore, the parameter θ̂(U) is estimated by using all
features in the training set.
GMM Supervector
Finally, GMM supervectors are created for each shot and are given by


µ̃k =

µ̃1



(3.33)µ̂k ,(3.34) µ̃2 
φ(X) =  . , .. 

#

(U)

wk

1

( U)

Σk

µ̃K
2− 1
2

where µ̂k is an adapted mean vector, and θ(U) is the GMM parameter for the
UBM. The dimension of GMM supervectors is Kd, where K is the number ofGaussian components and d is the dimension of the low-level feature vector.
The weighted sum of Mahalanobis distances between corresponding Gaussian pairs is obtained by calculating the squared Euclidean distance between
two GMM supervectors. RBF kernels are used for SVM classification:!

2k(X, X # ) = e−γ$φ(X)−φ(X )$ ,where γ is a kernel parameter.

(3.35)

Multi-Modal Semantic Indexing

20

Support Vector Machine
A support vector machine (SVM) is trained for each semantic concept andfor each type of features. An SVM is a binary classifier which focuses onmodeling the boundary between two classes [59, 60]. A hyperplane which
separates d-dimensional data into two classes is trained by an SVM. To improve the classification accuracy, SVMs introduce a kernel feature space
which maps a sample into a higher dimensional space where the data becomes linearly separable.
dGiven a N number of training samples {xi , yi }N
i=1 , each sample xi ∈ R ,and a class label yi ∈ {−1, 1}, all the hyperplanes in Rd are parametrized bya vector w and a constant b ,wT x + b = 0(3.36)

where w is a vector orthogonal to the hyperplane. For a given (w, b), a
decision (score) function of an SVM is given by
f (x) = sign(wT x + b)

(3.37)

which classifies the training samples. A canonical hyperplane is defined toseparate training samples from the hyperplane by a distance of 1, whilesatisfying the following two conditions:wT xi + b ≥ +1

when yi = +1,

wT xi + b ≤ −1 whenyi = −1.

(3.38)(3.39)

This is simplified as,yi (wT xi + b) ≥ 1(3.40)

Then, the magnitude of w is normalized to obtain geometric distancefrom the hyperplane to a sample. The distance is obtained asd((w, b), xi ) =yi (wT xi + b)
1
≥
"w"
"w"

(3.41)

By minimizing "w" a hyperplane that maximizes the geometric distanceMulti-Modal Semantic Indexing

21

Figure 3.4: A hyperplane that maximizes the margin.

is obtained to the closets samples as shown in Figure 3.4.
Lagrange multipliers [59, 61] are introduced to solve the problem as:
minimize:

W (α) = −subject to:

$

i

$

αi +

i

yi αi = 00 ≤ αi ≤ C

1$
yi yj αi αj xTi xj
2
i,j

(∀i)

where αi is a parameter of an SVM, and C is a regulalization parameter totune the margins for the hyperplane. Above problem is reduced as follows
by introducing a matrix Hij = yi yj xTi xj ,minimize:subject to:1
W (α) = −αT 1 + αT Hα
2
T
α y=0
0 ≤ α ≤ C1 (∀i)

This is solved by using quadratic programming techniques. Finally, theMulti-Modal Semantic Indexing

22

Figure 3.5: An example of a kernel trick. Data is not linearly separable in (a). The
data becomes linearly separable in (b) after transforming the input
data to a new feature space.

optimal hyperplane is given byw=$

αi yi xi

(3.42)iwhich shows that w is a linear combination of the training samples of αi )= 0.
Training samples which have αi > 0 are called support vectors and are used
to calculate the decision function.
If the data is not linearly separable, a kernel trick is used to transforma d-dimensional input vector into a higher d# -dimensional vector φ(x) as
shown in Figure 3.5.
By using the kernel trick, Eq.(3.42) is replaced as follows,w=$

αi yi φ(xi )iwhere φ(xi ) is a mapping functionby. The decision function is obtained by
f (x) =$

αi yi k(xi , x) + b(3.43)iwhere k is a kernel function given as a inner product of the mapped samples. The same process to find the optimal hyperplane is applied in a highMulti-Modal Semantic Indexing

23

dimensional feature space after transforming the problem in this way. Sincea kernel function is often non-linear, classification accuracy is expected to
be improved by using it.

3.4 Experiments
3.4.1 Experimental Conditions
In our experiments, the TRECVID 2009 High-Level Feature Extraction Dataset
and TRECVID 2011 Semantic Indexing Dataset are used to evaluate our semantic indexing system. Each dataset is divided into a training set and a test
set. The evaluation measure is Mean Average Precision (Mean AP) among
20 semantic concepts (Figure 3.6). Mean AP is the mean of AP for eachsemantic concept given by
N

AP =

1 $
Pr(r)Rel(r),R(3.44)

r=1

where R is the number of positive samples (appearances), N is the numberof testing samples, Pr(r) is the precision at the rank of r and Rel(r) takes avalue of one if the r-th shot is positive; otherwise, it takes zero. The number
of appearances is shown in Figure 3.6.

3.4.2 Detection Accuracy
Figure 3.7 shows Mean APs for different numbers of Gaussian components
for SIFT features (Harris-affine detector) with a log-likelihood ratio detector (SIFT-LR) or a GMM-supervector SVM (SIFT-SVM), and MFCC featureswith a LR detector (MFCC-LR) or a GMM-supervector SVM (MFCC-SVM).
Detailed AP for each semantic concept is shown in Figure 3.8. As can beseen, SIFT-SVM outperforms the others for 19 of 20 semantic concepts, and
MFCC-SVM outperforms the others for “Singing”. This shows that visual
information is often more important than audio information for detecting
semantic concepts.
When both of SIFT and MFCC are used, Mean AP is improved from 0.141(for SIFT-SVM) to 0.173. This shows that MFCC captures complementary information to SIFT. Table 3.1 compares the following seven fusion methods:

Multi-Modal Semantic Indexing

24

Figure 3.6: Number of appearances of semantic concepts

Fusion 1: SIFT-LR + SIFT-SVM
Fusion 2: MFCC-LR + MFCC-SVM
Fusion 3: SIFT-LR + MFCC-LR
Fusion 4: SIFT-SVM + MFCC-SVM
Fusion 5: SIFT-LR + SIFT-LR + MFCC-LR + MFCC-SVM
Fusion 6: SIFT-SVM + Hes-SIFT-SVM
Fusion 7: SIFT-LR + SIFT-LR + MFCC-LR + MFCC-SVM + Hes-SIFT-SVM
The best performance is obtained by Fusion 7.

3.4.3 Multi-frame Feature Extraction
Figure 3.8 shows Mean AP for different number of image frames, from which
SIFT features are extracted. SIFT-SVM shows better performance than BoW
especially when the number of image frames is larger than 15 since GMMs
used in SIFT-SVM can estimate the distribution of SIFT features more precisely than than histogram used in BoW.

3.4.4 Error Analysis
Figure 3.9 shows resulting APs for Har-SIFT, Hes-SIFT, Dense-SIFTH and
MFCC. We conclude that the four types of features are complementary toMulti-Modal Semantic Indexing

25

Figure 3.7: Comparison of Mean APs for different schemes.

Figure 3.8: Mean APs with different numbers of frames. The dotted line indicatesthe average number of frames in a shot.

Multi-Modal Semantic Indexing

26

Table 3.1: Mean APs for different schemes (K = 512). R denotes a result of Randomization test (p = 0.05).

MethodFusion 8
Fusion 7
Fusion 6
Fusion 5
Fusion 4
SIFT-SVM
Fusion 1
SIFThes -SVM
BoW(Multiframe)
Fusion 3
BoW
Fusion 2
SIFT-LR
MFCC-SVM
MFCC-LR

R
14
13
10
9
8
8
7
7
6
3
2
2
0
0
0

Mean AP
0.186
0.173
0.155
0.154
0.145
0.141
0.138
0.129
0.097
0.064
0.060
0.050
0.051
0.043
0.042

Singing
0.233
0.213
0.038
0.216
0.151
0.032
0.037
0.025
0.015
0.113
0.004
0.163
0.015
0.126
0.095

Female.
0.271
0.266
0.206
0.261
0.205
0.192
0.193
0.163
0.115
0.100
0.049
0.066
0.045
0.020
0.067

M.I.
0.149
0.132
0.048
0.102
0.022
0.038
0.063
0.044
0.041
0.096
0.020
0.016
0.053
0.010
0.028

each other: Har-SIFT is effective for detecting rigid objects and close-up objects, Hes-SIFT is effective for detecting objects with a background, DenseSIFTH is effective for detecting scenes, and MFCC is effective for detecting
human events and actions (Figure3.10). The followings are our detailed
observations and error analysis regarding each type of feature:
Har-SIFT
Har-SIFT achieved the highest InfAP (with the exception of the fusion methods) for 12 concepts: “Bus” (Figure 3.11), “Female Human Face Closeup”(Figure 3.12), “Ground Vehicles”, “Singing”, “Doorway”, “Hand”, “Animal”,“Old People”, “Cheering”, “Flowers”, “Telephones”, and “Sitting Down”. Since
Har-SIFT features are extracted from corner points, rigid objects such as cars
and buses were successfully detected. For detecting people and animals,
corner points for their eyes helped improving performance. However, we
still have some errors in classifying fine-grained categories, e.g. “Truck” and“Bus”, “Female” and “Male”.

Multi-Modal Semantic Indexing

27

Hes-SIFTHes-SIFT achieved the highest InfAP for 7 concepts: “Airplane Flying” (Figure 3.13), “Running” (Figure 3.14), “Vehicle”, “Walking”, “Throwing”, “Bicycling”, and “Classroom”. By introducing the Hessian-Affine detector, objects
on a flat background, for example, an airplane in the sky and a car on ahighway, were successfully detected. However, it is still difficult to detectan object from a complex background since our modeling can not separate
foreground and background.
Dense-SIFTH
Dense-SIFTH achieved the highest InfAP for 9 concepts: “Cityscape” (Figure 3.15), “Mountain” (Figure 3.16), “Demonstration Or Protest”, “Nighttime”, “Boat Ship”, “Dancing”, “Car Racing”, “Swimming”, and “Explosion
Fire”. The hue histogram of Dense-SIFTH detected scenes with few colors,e.g. explosion fire with red and yellow, nighttime with black, and a mountain with green.
MFCC
MFCC achieved the highest InfAP for two concepts: “Dark-skinned People”(Figure 3.17), and “Asian People”. For “Singing” (Figure 3.18), AP was improved by 5.2% by combining MFCC with the three visual features. Since
MFCC captured speech and music in video, people speaking or singing weredetected even if they are partially occluded by some objects. This showsthat MFCC captured complementary information with the visual features.
However, false detections occur when video has a background music that is
not related to the video contents.

Multi-Modal Semantic Indexing

28

Figure 3.9: InfAP by semantic concepts on the TRECVID 2011 Semantic Indexing
Dataset.

3.4.5 Comparison with Other Methods
Our results in the semantic indexing task on TRECVID 2011 and 2012 areshown in Figure 3.19 and 3.20. The best result was 0.173 and 0.321 ofMean InfAP, respectively, which is ranked first in the TRECVID 2011 and2012 official runs. This shows that our multi-modal system based on the
GMMs is powerful and accurate compared with the others.

Multi-Modal Semantic Indexing

29

Hes-SIFT 0.6

Classroom

AirplaneFlying
Walking
Running
GroundVehicles
BicycleBus
Vehicle Doorway
BoatShip
Hand
AnimalCityscapeThrowing
Flowers Demonstra!onSi"ngDown
Nigh"me
OldPeople
Cheering
Telephones Dancing
ExplosionFire
FemaleFace
Har-SIFT
0.6

0.4

0.2
Singing00.2
Swimming

Mountain
CarRace

Dense-SIFTH
0.4
0.6

DarkSkinnedPeople
0.2

AsianPeople
0.4

Objects
Human ac!ons/events/races
Scenes

0.6 MFCC
Figure 3.10: 2D visualization of 4D Average Precisions (APs) for Har-SIFT, HesSIFT, Dense-SIFTH and MFCC. To compare the effectiveness of eachtype of feature, the four AP values are normalized so that their sum
is one.

Multi-Modal Semantic Indexing

30

Figure 3.11: Top 25 video shots for “Bus”. Correct shots are marked in red.

● ● ● ● ●● ● ● ● ●●●● ● ● ●
● ● ● ● ●● ● ● ● ●Figure 3.12: Top 25 video shots for “Female Human Face Closeup”. Correct shots
are marked in red.

Multi-Modal Semantic Indexing

31

Figure 3.13: Top 25 video shots for “Airplane Flying”. Correct shots are marked inred.

Figure 3.14: Top 25 video shots for “Running”. Correct shots are marked in red.

Multi-Modal Semantic Indexing

32

Figure 3.15: Top 25 video shots for “Cityscape”. Correct shots are marked in red.

Figure 3.16: Top 25 video shots for “Mountain”. Correct shots are marked in red.

Multi-Modal Semantic Indexing

33

●

●

●

●
●

●
●

●

●

●

●

●
●

●

●

●

●

Figure 3.17: Top 25 video shots for “Dark-skinned People”. Correct shots aremarked in red.

Figure 3.18: Top 25 video shots for “Singing”. Correct shots are marked in red.

Multi-Modal Semantic Indexing

20.0

F̲A̲TokyoTech̲Canon̲1
F̲A̲TokyoTech̲Canon̲2
F̲D̲TokyoTech̲Canon̲4
F̲A̲TokyoTech̲Canon̲3

Mean InfAP (%)

15.0

10.0

5.0

0.0
TRECVID 2011 Semantic Indexing Runs

Figure 3.19: Comparison with other methods on TRECVID 2011.

Figure 3.20: Comparison with other methods on TRECVID 2012.

34

Multi-Modal Semantic Indexing35

3.5 Conclusion
In this chapter, we proposed a high-performance semantic indexing systemusing Gaussian mixture model (GMM) supervectors with the six audio andvisual features. Our best result on the TRECVID 2011 and 2012 was Mean
AP of 0.173 and 0.312, respectively. However, since our system, especially
the GMM-parameter-estimation step, is computationally expensive, we needto improve the speed of the system.

Chapter 4

Tree-structured Gaussian
Mixture Models
4.1 Overview
In this chapter, we describe a fast maximum a posteriori (MAP) adaptation
technique for a GMM-supervectors-based video semantic indexing system.
As shown in Chapter 3, the use of GMM supervectors is one of the state-ofthe-art methods in which MAP adaptation is needed for estimating the distribution of local features extracted from video data. The proposed method
cuts the calculation time of the MAP adaptation step. With the proposed
method, a tree-structured GMM is constructed to quickly calculate posterior probabilities for each mixture component of a GMM. The basic idea ofthe tree-structured GMM is to cluster Gaussian components and approximate them with a single Gaussian. Leaf nodes of the tree correspond tothe mixture components, and each non-leaf node has a single Gaussian thatapproximates its descendant Gaussian distributions.

4.2 Tree-structured GMMs
Let X = {xi }ni=1 be a set of (one type of) low-level features extracted froma video shot. A probability distribution function (pdf) of a Gaussian mixture

36Tree-structured Gaussian Mixture Models

37model (GMM) is given byp(x|θ) =K$
k=1

wk N (x|µk , Σk ),(4.1)

where x is a low-level feature vector, θ = {wk , µk , Σk }K
k=1 is a set of parameters, K is the number of mixture components, wk is a mixture coefficient.
N (·|µk , Σk ) is a Gaussian pdf with a mean vector µk and a covariance matrix
Σk .

As described in Chapter 3, MAP adaptation, a parameter estimation using the MAP criterion, is robust against over-fitting caused by limited data
since it uses a prior distribution. The MAP solution gives the following equations:&( U)τ µ̂k + ni=1 cik xi
&
µ̂k =
,
τ + ni=1 cik(4.2)(U) (U)

cik = &

wk gk (xi )(U) (U)K
k=1 wk gk (xi )
( U)
(U)
(U)
gk (x) = N (x|µk , Σk ),

,

(4.3)
(4.4)

(U)

where n is the number of feature vectors, and µ̂k is a mean vector of UBM,
(U)

gk is a Gaussian component, cik is a responsibility of a Gaussian component
gk for a feature vector xi , which is the posterior probability of xi being at
k-th Gaussian component, and τ is a predefined hyper-parameter.
A tree structure of Gaussian components that makes calculation of Eq. (4.3)
efficient is constructed from the UBM. Fig. 4.1 shows an example of a treestructured GMM. Each leaf node corresponds to a Gaussian component of
the UBM, and each other node has a single Gaussian obtained by combining corresponding Gaussian pdfs of descendant nodes. This tree structure isconstructed by top-down clustering of Gaussian components. For a given set
of Gaussian components G = {g1 , g2 , · · · , gK }, we define a combined single

Tree-structured Gaussian Mixture Models

38

Gaussian G(G) by
def

G(G) = N (·|µ̄, Σ̄),

(4.5)

K

µ̄ =

1 $
µk ,
K

(4.6)

k=1

Σ̄ =

K
1 $

K

k=1

T
(Σk + µk µTk ) − µ̄µ̄ .

(4.7)

To find a pair of Gaussian components which are close to each other,a distance measure between them is needed. The sum of Kullback-Leibler
divergence from gk to gk! and that of from gk! to gk is used for this measurement as follows:d(gk , gk! ) ==3

gk (x)
gk (x) log
dx +gk! (x)3

gk! (x) log

gk! (x)dx
gk (x)

11−1(µk − µk! )T (Σ−1k + Σk! )(µk − µk! )2
2−1!
+ tr(Σ−1k! Σk ) + tr(Σk Σk ) − 2d .

(4.8)

(4.9)

As for the following tree-construction algorithm, it is assumed that the
maximum number of child nodes for each layer (with the exception of theleaf layer) is given. For example, if the maximum number of child nodes forthe first layer (which only has a root node) is two and that for the second
layer is three, the resulting tree will be designed as shown in Fig. 4.1. In
this case, a tree with a depth of three (including the leaf layer) is obtained.
This tree-structured GMM is denoted asT(2,3) = (V, E, GTREE ),(4.10)

where V is a set of nodes, E is a set of edges, and GTREE = {g (v) |v ∈ V }is a set of Gaussian pdfs. In general, a node at the t-th layer of a tree
T(P1 ,P2 ,··· ,PT ) has, at most, Pt child nodes.

The node pdfs g (v) of a tree T(P1 ,P2 ,··· ,PT ) are created by the following

algorithm. The basic idea is to apply hierarchical k-means clustering for
(U)

(U)

( U)

Gaussian components. Note that GUBM = {g1 , g2 , · · · , gK } is a set of

mixture components of the UBM, G(v) is a subset of GUBM corresponding tonode v, and g (v) is a Gaussian pdf for node v.

Tree-structured Gaussian Mixture Models

39

Figure 4.1: An example of a tree-structured GMM T(2,3) .

1. Prepare a queue and enqueue (r, G(r) ), where r is the root node,G(r) = GUBM , and g (r) ← G(G(r) ).
2. (Initialization for k-means) Dequeue (v, G(v) ). Let {cp }Pp=1 be thechild nodes of node v. Select the initial cluster centers g (cp ) from thegiven set of Gaussian components G(v) , where the min-max selection
method is used instead of random selection. The min-max selection
method is explained in Appendix.

3. (Clustering by k-means) Assign each Gaussian component in G(v) to
the nearest child node, i.e.
G(cp ) ← {g ∈ G(v) | p = argmin d(g, g (cp! ) )}.

(4.11)

p!

Update g (cp ) by using Eq. (4.5) as follows:g (cp ) ← G(G(cp ) ),(4.12)

Tree-structured Gaussian Mixture Models

40

Repeat this step until the following sum of distance converges:
D=

P
$
$

d(g, g (cp ) ).

(4.13)

p=1 g∈G(cp )4. For p = 1, 2, · · · , P , enqueue (cp , G(cp ) ) if cp is not in the (T + 1)-thlayer and |G(cp ) | > 1. Go to step 5 if the queue is empty; otherwise,
return to step 2.

5. For each node v in the (T + 1)-th layer, create leaf nodes * for each(U)

gk ∈ G(v) ⊂ GUBM and set(U)g ($) = gk .

(4.14)For the initialization for k-means clustering (Step 2 in the tree-construction
algorithm,we use the min-max selection method. This method is known toprovides better initial values than random selection. This method first selects from G(v) a node set whose nodes are distant from each other, and thensets a cluster center at an internal dividing point between node v and eachof the selected nodes.
2-1) Choose the mixture component g̃ (c1 ) that has the largest distance tog (v) , i.e.,g̃ (c1 ) = argmax d(g, g (v) ).

(4.15)g∈G(v)

2-2) For p = 2, · · · , P , choose g̃ (cp ) from the rest of mixture components

which belong to the node v and not yet assigned to any child node,i.e.,g̃ (cp ) = argmax mind(g, g̃ (cp! ) ),!
(v)

g∈Gp−1

1≤p <p(v)(4.16)(v)

where Gp−1 = G(v) \ {g̃ (c1 ) , · · · , g̃ (cp−1 ) }. If Gp−1 is an empty set, thechild node is deleted from the tree.

2-3) For p = 1, 2, · · · , P , set the parameters of child Gaussian pdfs g (cp ) as

Tree-structured Gaussian Mixture Models

41

follows:
g (cp ) ←N (·|µ̄, Σ̄),

(4.17)µ̄ =αµ̃(cp ) + (1 − α)µ(v) ,(4.18)

Σ̄ =α(Σ̃(cp ) + µ̃(cp ) (µ̃(cp ) )T )+ (1 − α)(Σ(v) + µ(v) (µ(v) )T )− µ̄µ̄T ,(4.19)

where 0 ≤ α ≤ 1 is a weight parameter to mix the selected pdf g̃ (cp ) =N (·|µ̃(cp ) , Σ̃(cp ) ) and their parent pdf g (v) = N (·|µ(v) , Σ(v) ).

4.3 Fast MAP Adaptation
A fast MAP adaptation technique which estimates cik in Eq. (4.3) efficiently
by using a tree-structured GMM is explained in the following. For a constructed tree-structured GMM T(P1 ,P2 ,··· ,PT ) , node weights are first defined
as follows:a) For each leaf node *, set(U)w($) = wk ,(4.20)(U)

if g ($) = gk ∈ GUBM .
b) Calculate weights for t = T + 1, T, · · · , 1 as follows. For each node v
in the t-th layer,

w(v) =$

w(c) ,(4.21)c∈C(v)

where C(v) is a set of child nodes of the node v.
The algorithm for estimating cik for feature vector xi is described asfollows. The key idea is to construct a GMM of active nodes VA , whichmeans vector xi will be assigned to descendants of nodes in VA . |VA | is kept
small by obtaining active nodes from the root node.
1. Set VA ← {r}, where r is the root node.

Tree-structured Gaussian Mixture Models

42

2. Expand active nodes by making child nodes of the active nodes active:
VA ←4(4.22)

C(v),

v∈VA

where C(v) is a set of child nodes of the node v. Here, C(*) = {*} isused for leaf nodes * to keep the leaf nodes active.
3. Consider a GMM for active node VA given byp(x|VA ) =$w̃(v) g (v) (x),(4.23)

v∈VA

where
w(v)
.
(v)
v∈VA ww̃(v) = &Calculate(v)

ci(4.24)w̃(v) g (v) (xi )w(v) g (v) (xi )&=.
(v) (v)(v) (v)v∈VA w̃ g (xi )v∈VA w g (xi )

=&

(v)

4. Keep a node v active if ci(4.25)is larger than the predetermined thresholdcTH , i.e.
(v)

VA ← {v ∈ VA | ci

(4.26)> cTH }.

5. If all nodes in VA are leaf nodes, outputĉik =


c($)
i

0

(U)

(* ∈ VA , g ($) = gk )(otherwise).

(4.27)

Otherwise, return to Step 2.
Since the observed ĉik for non-active nodes is 0, the sum in Eq. (4.2)
can be calculated for non-zero ĉik only. Our fast MAP adaptation requiresO(n log K) time which improves O(nK) time for the basic MAP adaptation.
Moreover, calculation speed and levels of approximation can be controlled
by selecting the threshold cTH in 0 < cTH ≤ 1. Note that the same cik as given

Tree-structured Gaussian Mixture Models

43by Eq. (4.3) is obtained when cTH is set to 0 (because all leaf nodes will be
active at the final step).
Finally, GMM supervectors are created for each shot in the same way
as Chapter 3. Note that the proposed method can be used for creating the
Fisher vectors [35, 36].
SVMs for the four types of features described in Section 3.2 are combinedby calculating the weighted sum of detection scores asf (X) =$

βF fF (X),

(4.28)F∈{SIFT-Har, SIFT-Hes,
SIFTH-D, MFCC}

where βF is a combination weight and fF (X) is a detection score for thefeature F. The combination weights are optimized for each semantic concept
by cross validation.

4.4 Experiments
4.4.1 Database and Task
Our experiments were conducted on the TRECVID 2010 dataset [64, 13].
The dataset consists of 400 hours of Internet archive videos with creative
commons licenses. The shot boundaries and key-frame images are automatically detected and provided with the video data. Half of the videos wereused for training, and the others were used for testing. The number of shots
was 119,685 for training and 146,788 for testing.
We evaluated our system on the TRECVID 2010 Semantic Indexing benchmark. The task is to detect the 30 semantic concepts (including objects,
events and scenes) listed in Table 4.1. They are considered useful for video
searching.
The annotated labels for the 30 concepts are also provided with the video
data (including testing videos for evaluation). The labels for training data
are created using a collaborative annotation system [65]; however, some of
the training shots are still unlabeled. It was assumed that the unlabeled samples are negative since the annotation system is based on an active learning
method that requires shots appearing to be positive samples to be annotatedpreferentially. On the other hand, labels for testing videos are attached onTree-structured Gaussian Mixture Models

44

Table 4.1: The 30 target semantic concepts in the TRECVID 2010 dataset

Airplane Flying
AnimalAsian People
Bicycling
Boat shipBus
Car Racing
Cheering
CityscapeClassroom
Dancing
Dark-skinned People
Demonstration Or Protest
Doorway
Explosion Fire

Female Human Face Closeup
Flowers
Ground Vehicles
Hand
MountainNighttime
Old People
Running
Singing
Sitting down
Swimming
Telephones
Throwing
VehicleWalking

Table 4.2: The average numbers of extracted features.

FeatureSIFT-Har
SIFT-Hes
SIFTH-Dense
MFCC# of features per shot
19,53618,98630,0005,160

the basis of the submission pool of TRECVID 2010, which allows precise
estimation of average precision.
The evaluation measures are Mean average precision (Mean AP) and thecalculation time of the testing phase. The AP is estimated by using a method
called inferred average precision (Inf AP), proposed in [66].

4.4.2 Experimental Conditions
SiftGPU [67] and Mikolajczyk’s implementation [22] were used for SIFT feature extraction. MFCC features were extracted by using a speech recognition
toolkit HTK [69]. The average numbers of features per shot are summarizedin Table 4.2.
The number of mixtures (vocabulary size) K for GMMs was 512 forvisual features and 256 for audio features. For computational efficiency,
it was assumed that covariance matrices are diagonal. Hyper parameter

Tree-structured Gaussian Mixture Models

45τ in the MAP adaptation was set to 20.0, which is the standard value ofthe toolkit HTK. Parameter γ in the RBF kernel was γ = d¯−1 , where d¯ ispre-calculated average distance between two GMM supervectors in training
data. SVMs were trained for each semantic concept by using the libSVM
implementation [70]. Combination weights for the fusion in Eq. (4.28) were
optimized by using two-fold cross validation on training data.
For tree-structured GMMs, the optimal tree structure Topt was selected asTopt = argmin CT(T ),(4.29)T ∈S

where CT(T ) is calculation time when the tree T is used and
S = {T(P1 ,P2 ,··· ,PT ) | 1 ≤ T ≤ 5, 1 ≤ Pt ≤ 5}.

(4.30)The trees T(4,4,5) , T(4,5,5) , T(3,4,4,5) and T(3,3) were selected for SIFT-Har, SIFTHes, SIFTH-Dense and MFCC, respectively. Parameter α in Eq. (4.17) was
fixed to 0.1.
Threshold cTH for the fast MAP adaptation was set to 0.001. Here, a low
threshold was set so as to keep detection performance high. Experiments
using different thresholds were also conducted (see Subsection 4.4.3).
In the experiments, calculation time was measured by using a single coreof Intel Xeon 2.93 GHz CPU. Calculation time without feature extraction
time is reported since some features were pre-extracted by using GPUs. The
average feature extraction time per shot was 0.38 sec by using a GPU NVIDIA
Tesla M2050.

4.4.3 Results
Mean Inf APs
Table 4.3 and Table 4.4 summarizes obtained Inf APs and Mean Inf AP foreach types of low-level features and two fusion methods: visual fusion andmulti-modal fusion. The visual fusion is a combination of three types ofvisual features (SIFT-Har, SIFT-Hes, and SIFTH-Dense). The multi-modal
fusion combines the MFCC in addition to the visual features. As a result, we
can see that the Mean Inf APs using tree-structured GMMs are comparable
to those using no trees. Some example video shots for training and testingTree-structured Gaussian Mixture Models

●

■●

● ●

●

46

●

●

● ●

Figure 4.2: Example video shots for training and testing sets. The top 5 results
obtained by using our system (multi-modal fusion) are shown in theright side of the figure.

sets are shown in Fig. 4.2.
Calculation time
Table 4.5 lists calculation times for MAP adaptation using different featuresand different trees. The results for binary trees (Tbinary ) are also listed in thetable. The calculation speed when the optimal tree is used on average 4.2
times faster than when trees were not used; that is, calculation time was
reduced by 76.2%.
Fig. 4.3 shows calculation time for each step in the testing phase of the
proposed semantic indexing system. The testing cost was reduced, on average, by 56.6% by using tree-structured GMMs. The second and third highest
costs were for the PCA projection and the SVM prediction (including calculation of kernels). The SVM prediction can be speed up by using linear
kernels instead of RBF kernels. To avoid decrease in detection accuracy, apossible compromise is to use linear kernels for roughly ranking shots andre-evaluate high-ranked shots by using RBF kernels.
Analysis of estimation error
Estimation errors of cik were evaluated from the mean absolute error (MAE),
given as follows:
n

K

1 $$
MAE =
|ĉik − cik |,n(4.31)

i=1 k=1

where ĉik and cik are given by Eq. (4.27) and Eq. (4.3), respectively. The
MAE for SIFTH-Dense was 0.32 on average (note that 0 ≤ MAE ≤ 2). Al-Tree-structured Gaussian Mixture Models

47

Table 4.3: Resulting inferred average precisions (Inf APs) for each semantic concept and for each method. Mean Inf APs on the testing set and Mean APs
on a two-fold cross-validation split of the training data are also shown.
Semantic concept
Airplane_Flying
AnimalAsian_People
Bicycling
Boat_ShipBus
Car_Racing
Cheering
CityscapeClassroom
Dancing
Dark-skinned_People
Demonstration_Or_Protest
Doorway
Explosion_Fire
Female-Human-Face-Closeup
Flowers
Ground_Vehicles
Hand
MountainNighttime
Old_People
Running
Singing
Sitting_Down
Swimming
Telephones
Throwing
VehicleWalking
Mean InfAP

SIFT-HarNo tree
Topt
0.064
0.064
0.039
0.041
0.024
0.029
0.039
0.041
0.046
0.044
0.012
0.012
0.021
0.019
0.053
0.051
0.090
0.098
0.004
0.005
0.034
0.036
0.089
0.088
0.095
0.095
0.084
0.082
0.025
0.025
0.139
0.124
0.030
0.028
0.159
0.165
0.078
0.073
0.059
0.055
0.072
0.073
0.043
0.045
0.039
0.041
0.112
0.105
0.002
0.001
0.121
0.131
0.008
0.010
0.059
0.059
0.158
0.150
0.093
0.103
0.063
0.063

SIFT-Hes
No tree
Topt
0.080
0.078
0.034
0.035
0.014
0.015
0.040
0.033
0.040
0.041
0.011
0.013
0.014
0.013
0.044
0.045
0.109
0.110
0.020
0.022
0.030
0.028
0.073
0.071
0.065
0.069
0.068
0.067
0.026
0.025
0.096
0.105
0.019
0.017
0.148
0.150
0.062
0.073
0.053
0.054
0.055
0.054
0.040
0.041
0.047
0.045
0.069
0.074
0.001
0.001
0.162
0.164
0.006
0.006
0.063
0.063
0.163
0.172
0.135
0.138
0.060
0.061

SIFTH-Dense
No tree
Topt
0.032
0.030
0.026
0.020
0.001
0.002
0.029
0.026
0.050
0.049
0.007
0.009
0.060
0.054
0.033
0.037
0.125
0.108
0.010
0.010
0.034
0.033
0.118
0.133
0.130
0.121
0.073
0.068
0.045
0.043
0.125
0.121
0.029
0.028
0.153
0.151
0.047
0.055
0.192
0.194
0.120
0.113
0.022
0.023
0.020
0.018
0.069
0.068
0.001
0.001
0.343
0.339
0.008
0.009
0.019
0.016
0.150
0.146
0.061
0.060
0.071
0.070

MFCC
No tree
Topt
0.001
0.001
0.002
0.002
0.041
0.041
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.008
0.008
0.009
0.009
0.000
0.000
0.001
0.001
0.138
0.139
0.001
0.001
0.000
0.001
0.011
0.011
0.021
0.021
0.001
0.001
0.021
0.020
0.000
0.000
0.003
0.003
0.002
0.002
0.013
0.011
0.000
0.000
0.086
0.090
0.000
0.000
0.199
0.199
0.001
0.000
0.019
0.020
0.015
0.014
0.002
0.002
0.020
0.020

Mean AP on validation set 1

0.078

0.078

0.081

0.082

0.105

0.107

0.028

0.028

Mean AP on validation set 2

0.084

0.085

0.092

0.091

0.111

0.111

0.028

0.027

though we have estimation errors of cik in the fast MAP adaptation algorithm, they can be cancelled when the distance in Eq. (3.35) is calculated
since the same errors occur in training and testing phases.
Effect of using different thresholds
Table 4.6 lists the results obtained using different thresholds cTH for the fast
MAP adaptation. The number of leaf nodes that are active (at least once in
Eq. (4.22) ) and MAE are also listed in the table.
As cTH gets higher, the calculation time shortens, but Mean Inf AP was decreased when cTH = 0.1 and 0.5. Moreover, the number of active leaf nodes
decreases, and MAE increases. It can thus be concluded that calculation
time should be reduced not by setting a high threshold cTH but by selecting
a better-structured tree to keep detection performance high. In particular,cTH should be equal to or smaller than 0.01.

Tree-structured Gaussian Mixture Models

48

Table 4.4: Resulting inferred average precisions (Inf APs) for each semantic concept and for each method. Mean Inf APs on the testing set and Mean APs
on a two-fold cross-validation split of the training data are also shown.
Semantic concept
Airplane_Flying
AnimalAsian_People
Bicycling
Boat_ShipBus
Car_Racing
Cheering
CityscapeClassroom
Dancing
Dark-skinned_People
Demonstration_Or_Protest
Doorway
Explosion_Fire
Female-Human-Face-Closeup
Flowers
Ground_Vehicles
Hand
MountainNighttime
Old_People
Running
Singing
Sitting_Down
Swimming
Telephones
Throwing
VehicleWalking
Mean InfAP

Visual fusion
No tree
Topt
0.105
0.105
0.068
0.073
0.012
0.009
0.045
0.056
0.085
0.084
0.018
0.016
0.040
0.040
0.052
0.051
0.180
0.177
0.015
0.011
0.068
0.067
0.151
0.159
0.137
0.132
0.098
0.097
0.050
0.047
0.169
0.175
0.043
0.044
0.211
0.210
0.092
0.089
0.180
0.169
0.127
0.133
0.059
0.058
0.073
0.077
0.154
0.158
0.002
0.003
0.173
0.186
0.010
0.012
0.062
0.065
0.205
0.200
0.134
0.142
0.094
0.095

Multi-modal fusion
No tree
Topt
0.105
0.117
0.076
0.076
0.012
0.009
0.045
0.056
0.085
0.084
0.021
0.016
0.056
0.043
0.052
0.051
0.185
0.179
0.017
0.021
0.068
0.067
0.208
0.203
0.137
0.132
0.104
0.098
0.050
0.047
0.173
0.178
0.043
0.044
0.208
0.206
0.090
0.090
0.182
0.164
0.120
0.132
0.061
0.063
0.073
0.077
0.182
0.188
0.003
0.004
0.278
0.276
0.010
0.018
0.062
0.066
0.205
0.200
0.135
0.143
0.102
0.102

Mean AP on validation set 1

0.147

0.148

0.153

0.154

Mean AP on validation set 2

0.158

0.158

0.162

0.161

Effect of using different tree structures
Fig. 4.4 shows calculation time obtained using different tree structures. The
tree of T(3,4,4,5) was the best in terms of calculation time. We can see thatthe tree should not be too deep to improve the speed of MAP adaptation.
Fig. 4.5 shows MAE obtained using different tree structures. MAE can be
reduced by changing the tree structure. However, we conclude that any tree
structures will not be the cause for decreasing final performance since there
was no decrease in Mean Inf AP even in the case of MAE = 0.53 in Table 4.6.
Comparison With Other Methods
Fig. 4.6 compares Mean Inf APs obtained in the above-described experiment with those values obtained by the other methods used at TRECVID
2010. Our fusion methods got better results than the best result reported at
TRECVID 2010 (0.900).
Fig. 4.7 shows the results of significance test obtained by applying par-

Tree-structured Gaussian Mixture Models

49

Figure 4.3: Calculation time for each step (The lower bars for each feature show
the time in the case that the optimized tree was used)
Table 4.5: Calculation time (sec) for MAP adaptation. Calculation time was measured by using a single core of Intel Xeon 2.93 GHz CPU.

FeatureSIFT-Har
SIFT-Hes
SIFTH-Dense
MFCC

No tree
1.62
1.67
2.89
0.22

Topt
0.49
0.48
0.81
0.03

Tbinary
0.98
1.00
1.89
0.08

tial randomization test (p < 0.05). The muti-modal fusion was significantly
better than the visual fusion. Our method performed better than the othermethods in TRECVID 2010 for semantic concepts related to human and human actions such as “Singing” and “Dancing” since we used audio features.
However, there was no significant difference between the muti-modal fusion
and the top result in TRECVID 2010. This result shows that the performancecan be improved by combining a larger number of visual features since the
top ranked methods in TRECVID 2010 used more than 10 types of visualfeatures.
Although our final goal is to develop a generic methods for automaticallyassigning semantic concepts to videos, overall performances are still low
compared with that of human annotation. One future challenge is detectionTree-structured Gaussian Mixture Models

50

Figure 4.4: Mean absolute error (MAE) of cik obtained using different tree structures (the SIFTH-Dense feature and cTH = 0.001 were used). 1,364
trees of depth at most 5 that have at most 5 children per node and thebinary tree are tested. All MAE were less than 0.05.

Tree-structured Gaussian Mixture Models

51

Figure 4.5: Calculation time obtained using different tree structures (the SIFTHDense feature and cTH = 0.001 were used). 1,364 trees of depth at most
5 that have at most 5 children per node and the binary tree are tested.
T(3,4,4,5) was the best tree and was selected as the optimized tree.

Figure 4.6: Comparison of Mean Inf AP with runs of the TRECVID 2010.

Tree-structured Gaussian Mixture Models

52

Table 4.6: Comparison of Mean Inf AP, calculation time (sec) for MAP adaptation,
number of leaf nodes |VA | and Mean absolute error (MAE) of cik byusing different thresholds cTH for the SIFTH-Dense feature.

cTH
0.001
0.01
0.1
0.5

Mean Inf AP
0.695
0.699
0.660
0.641

Calc. time
0.81
0.68
0.59
0.53

|VA |
17.0
11.2
7.3
5.4

MAE
0.32
0.53
0.80
0.98

Figure 4.7: Results of partial randomization test (p < 0.05). Significant differences among top 10 runs in TRECVID 2010 and our fusion methods
are shown. A black cell shows that there is significant difference between two methods.

of many kinds of semantic concepts; however, we have to consider which
concepts are really useful for applications of video search.

4.5 Conclusion
A fast and accurate semantic indexing system using fast MAP adaptation and
GMM supervectors was proposed. A tree-structured GMM was constructed
to quickly calculate posterior probabilities for each mixture component ofa GMM. The calculation time for MAP adaptation was reduced by 76.2%
from the conventional method, while high detection performance was main-Tree-structured Gaussian Mixture Models

53

tained. Our future work will focus on a GPU implementation of the fast MAP
adaptation and feature extraction.

Chapter 5

q-Gaussian Mixture Models
5.1 Overview
As described in the previous chapters, Gaussian mixture models (GMMs)
which extend the bag-of-visual-words (BoW) to a probabilistic framework
are effective for image and video semantic indexing. Recently, the q-Gaussian
distribution, which is derived in the non-extensive statistics, has been shown
to be useful for representing patterns in many complex systems in physics
such as fractals and cosmology. In this chapter, we extend our GMM-based
system to q-Gaussian mixture models (q-GMMs), which are mixture modelsof q-Gaussian distributions, for image and video semantic indexing.
The procedure of the proposed image and video semantic indexing basedon q-Gaussian mixture models (q-GMMs) is shown in Fig. 5.1. First, lowlevel features (e.g. SIFT features) are extracted from image/video data.
Second, a q-GMM for a background model is estimated from low-level features in training data. Finally, each image is represented by a histogram of
low-level features in which the background model is used as a visual codebook.

54

q-Gaussian Mixture Models

55

Figure 5.1: The framework of image and video semantic indexing using q-Gaussian
mixture models.

Figure 5.2: The q-Gaussian distributions. The (normal) Gaussian distribution is
obtained when q = 1. The tail of a q-Gaussian distribution is longer
than that of a Gaussian distribution when q > 1.

5.2 q-Gaussian Mixture Models
The q-Gaussian distribution, which has a parameter q to control its tailheaviness, is derived by maximizing Tsallis q-entropy Sq given by1
Sq = −
1−q

8

1−

3

9
p(x) dx .
q(5.1)

The Boltzmann-Gibbs (BG) entropy is obtained from Tsallis q-entropy Sq for
q → 1. The probability density function of the q-Gaussian distribution Nq is

q-Gaussian Mixture Models

56

Figure 5.3: (a): Standardized histogram of the first elements of standardized SIFT
descriptors. 1 million low-level descriptors are randomly sampled fromtraining data of PASCAL VOC 2010 dataset. (b-1), (b-2): A fitting result
by a Gaussian distribution and its residuals. (c-1), (c-2): A fitting result
by a q-Gaussian distribution (q = 1.12) and its residuals.

given by


8
9 1



1
1
−
q


1−
(x − µ)T Σ−1 (x − µ) 1 − q ,


3−q
 Zq
3−q
Nq (x | µ, Σ) =if (x − µ)T Σ−1 (x − µ) <
,


1−q





0,
otherwise,(5.2)

where µ is a mean vector, Σ is a covariance matrix, and Zq is a normalizing
constant to make the integral over Eq. (5.2) to 1. Note that the q-Gaussian
distribution asymptotically approaches to the Gaussian distribution whenq → 1.

Fig. 5.2 shows the shape of q-Gaussian distributions for some q-values.

The q-Gaussian distribution has a longer tail than the Gaussian distribution
when q > 1. The long-tailed distribution obtained for q > 1 is expected
to be effective for representing complexly correlated data. Fig. 5.3 showsa histogram of the first values of 1 million low-level descriptors with fitting results. The q-Gaussian distribution is more suitable than the Gaussian
distribution to represent distribution of the low-level descriptors.
To further improve the expressiveness of the q-Gaussian distribution, we
introduce a mixture model of q-Gaussian distributions, namely a q-Gaussianq-Gaussian Mixture Models

57

mixture model (q-GMM), bypq (x | θ) =

K
$
k=1

wk Nq (x | µk , Σk ),(5.3)

where K is the number of mixtures, wk is a mixture coefficient, and θ ={wk , µk , Σk }K
k=1 is a set of q-GMM parameters.

5.3 Training q-GMM for a Background Model
From a set of low-level features X = {xi }Ni=1 in training data, we estimate
q-GMM parameters for a background model which is used instead of a codebook for BoW. We propose the expectation maximization (EM) algorithm
for q-GMMs as follows.
E-stepEvaluate posterior probabilities cik as follows:ŵk Nq (xi | µ̂k , Σ̂k )cik = &K.
k=1 ŵk Nq (xi | µ̂k , Σ̂k )M-step(5.4)

To derive the parameter-update rules for the M-step, we introduce a Qfunction given byQ(θ) = log%i'pq (xi | θ) + λ 1 −

$
k!

wk!

(

(5.5)

where pq is a pdf of a q-GMM defined by Eq. (5.3). A lagrangian multiplier
λ is introduced to obtain wk such that$k!

wk! = 1.

(5.6)

q-Gaussian Mixture Models

58

The derivations of the Q-function for each parameter are given by$
Nq (xi | µk , Σk )∂&Q(θ) =−λ∂wk
k! wk! Nq (xi | µk! , Σk! )i
1 $=cik − λ,wki
$ aik wk Nq (xi | µk , Σk )∂&Q(θ) =
Σ−1k (xi − µk )
!
!
!
∂µk
w
N
(x
|
µ
,
Σ
)
!
q
i
k
k
k
k
i
$
= Σ−1
aik cik (xi − µk ),
k

(5.7)
(5.8)
(5.9)
(5.10)i;<w N (x | µ , Σ )∂1$& k q i k k
Q(θ) =
Σ−2aik (xi − µk )(xi − µk )T − Σkk∂Σk2
k! wk! Nq (xi | µk! , Σk! )i(5.11)

1
= Σ−2
2 k

$
i

;
<
cik aik (xi − µk )(xi − µk )T − Σk ,(5.12)

where
aik =

2
.
3 − q − (1 − q)(xi − µk )T Σ−1
k (xi − µk )(5.13)The parameter-update rules for the M-step are obtained by setting thederivatives of Q to zero. For mixture coefficients wk , we obtainCkŵk = &K

k=1 Ckfrom Eq. (5.8) where Ck =&,(5.14)

i cik .

However, µ̂k and Σ̂k can not be obtained from Eqs. (5.10) and (5.12)
analytically since µk and Σk appear in aik . Our preliminary experiments
show that numerically solving those equations by the steepest descent (SD)method is time-consuming and it’s difficult to optimize step size in SD in ahigh-dimensional space. Hence we assume aik is a constant A for all i andq-Gaussian Mixture Models

59k, and analytically solve the equations as
N

1 $
µ̂k =
cik xi ,
Ck
Σ̂k =

i=1
N
$

A
Ck

(5.15)cik (xi − µ̂k )(xi − µ̂k )T .

i=1

(5.16)We determine the value of A so that the expectation of Σ̂k , E[Σ̂k ], isequal to Σk , a covariance matrix of a q-Gaussian distribution Nq (· | µk , Σk ).
The expectation of Σ̂k is calculated as
=

E Σ̂k

>

!

N

A $
=E
cik (xi − µ̂k )(xi − µ̂k )T
Ck
i=1

"

(5.17)N=A $cik V[xi ]Ck(5.18)

i=1

3−q
=A
Σk .
5 − 3q(5.19)

where we use the fact
V[xi ] =3−qΣk .
5 − 3q(5.20)

89−1(5.21)

Therefore, A is set toA=3−q
5 − 3q.

Here, we assume q < 53 since a q-Gaussian distribution has an infinite variance if q ≥ 53 .

5.4 q-GMM for histogram-based image representation
To represent an image by a feature vector, we create a histogram of low-level!

features H(X # ) from a set of low-level features X # = {xi }N
i=1 extracted fromq-Gaussian Mixture Models

60

an image as follows:


C1





$
 C2 

H(X ) = cik , ..  , Ck =
 . 
i
#

(5.22)

CK

where cik is the posterior probability of xi being at the k-th q-Gaussian component. It is given byŵk Nq (xi | µ̂k , Σ̂k )cik = &K.
k=1 ŵk Nq (xi | µ̂k , Σ̂k )(5.23)

where ŵk , µ̂k , and Σ̂k are q-GMM parameters for the background model.
The posterior probabilities cik can be viewed as weights in soft-assignmentof visual words since they satisfyK$
k=1

cik = 1, 0 ≤ cik ≤ 1.

(5.24)

Thus, the q-GMM can be regarded as an extension of BoW to a probabilistic
framework.
We found that the assignment using the q-GMM comes close to the hardassignment (i.e., only one of cik is equal to 1.0 and others are 0.0) as q
decreases, and comes close to the uniform-assignment (i.e., all cik haveequivalent values) as q increases. To measure how much the assignmentis close to the hard-assignment, we introduce the assignment hardness hdefined byN!

1 $ maxk cik − K −1
h= #.
N
1 − K −1

(5.25)

i=1

The assignment hardness h is designed to reach 1.0 for the hard-assignmentand 0.0 for the uniform-assignment.
Fig. 5.4 shows the assignment hardness with different q-values. To improve the final performance of image and video indexing, the assignment
should not be too hard nor too uniform. Here, we employ a q-value of 1.05
that has the middle value (0.5) of assignment hardness.

q-Gaussian Mixture Models

61

Figure 5.4: Assignment hardness h with different q-values.

5.5 q-GMM Kernel
Here, we introduce q-GMMs instead of the BoW histograms to represent images and videos. Generally, the number of low-level features extracted froman image is limited and may not be enough to estimate q-GMM parameters
robustly. Thus, we use the maximum a posteriori criteria which provides
robust parameter estimation. For each image that has low-level features!

X # = {xi }N
i=1 , we only update q-GMM mean vectors from the backgroundmodel as follows:& !
τ µ̂k + N#
i=1 cik xi
µ̃k =
,
&N !
τ + i=1 cik(5.26)

where N # is the number of the low-level features, µ̂k is a q-GMM parameterfor the background model, τ is a prefixed hyper-parameter, and cik is theposterior probability given by Eq. (6.10).
For a kernel to train support vector machines (SVMs), we introduce theq-Gaussian Mixture Models

62

following RBF-based kernel, namely q-GMM kernel,'k(X # , X ## ) = exp −γ

K
$
k=1

(

#
##
ŵk (µ̃#k − µ̃##k )T Σ̂−1k (µ̃k − µ̃k ) ,(5.27)

where X # is a set of low-level features extracted from an image, µ̃#k is an
updated q-GMM mean vector, Σ̂k , wk are q-GMM parameters for the background model, and γ is a scaling parameter. The weighted sum of Mahalanobis distance between the k-th q-Gaussian components is utilized in the
q-GMM kernel.
To efficiently compute the q-GMM kernel, we define the following supervector φ(X # ) and store it in storage.
√−1ŵ1 Σ̂1 2 µ̃#1√
−1ŵ2 Σ̂2 2 µ̃#2
#φ(X ) = 


 √

..
.

−1

ŵK Σ̂K 2 µ̃#K






,




(5.28)The dimension of the super-vector is Kd where K is the number of mixture
components and d is the dimension of low-level descriptors. The supervector immediately implies the following simplification of the q-GMM kernel.
;<k(X # , X ## ) = exp −γ"φ(X # ) − φ(X ## )"22 .

(5.29)

5.6 Experiments
5.6.1 Experimental Conditions
In this section, the proposed method is evaluated on two data sets: PASCAL
VOC 2010 and TRECVID 2010. The PASCAL Visual Object Classes Challenge(VOC) [71] provides a benchmark for comparison of object classification
methods. The PASCAL VOC 2010 classification (validation) challenge data
set consists of 4,998 training images and 5,105 testing images of 20 object
classes in Table 5.1. The evaluation measure is Mean average precision(Mean AP), which is the arithmetic mean of APs over all targeted object
classes. The TREC Video Retrieval Evaluation (TRECVID) [64] provides aq-Gaussian Mixture Models

63

Table 5.1: The targeted semantic concepts for PASCAL VOC 2010 and TRECVID
2010.

PASCAL VOC 2010
Aeroplane
Boat
Car
Cow
Horse
Pottedplant
Train
TRECVID 2010
Airplane Flying
Bicycling
Car Racing
Classroom
Demonstration Or Protest
Female Human Face Closeup
Hand
Old People
Sitting downThrowing

BicycleBottleCat
Diningtable
Motorbike
Sheep
Tvmonitor

Bird
Bus
Chair
Dog
Person
Sofa

AnimalBoat Ship
Cheering
Dancing
Doorway
Flowers
Mountain
Running
Swimming
VehicleAsian People
Bus
CityscapeDark-skinned People
Explosion Fire
Ground Vehicles
NighttimeSinging
Telephones
Walkingbenchmark for comparison of video indexing methods. The TRECVID 2010
Semantic Indexing data set consists of 119,685 training video shots and146,788 testing video shots. 30 semantic concepts of objects, actions, andscenes in Table 5.1 and their ground truth labels are provided. Officiallyprovided key-frame images for each video shot is used in our experiments.
The evaluation measure is Mean AP among the 30 semantic concepts.
To test our q-GMM on these benchmarks, the low-level image descriptors are densely sampled from 100x100 grid with 3 different scales on animage. The descriptor is a concatenation of 128-dimension SIFT descriptor [5] and 36-dimension hue-histogram descriptor [28]. The dimension ofeach descriptor is reduced to 32 by applying Principal Component Analysis(PCA) after the concatenation.
The q-GMM for a background model is constructed by applying the proposed EM algorithm to one million randomly sampled descriptors. The number of mixture components K and the hyper-parameter τ in Eq. (5.26) are
set to 512 and 20.0, respectively, in all experiments except the experimentevaluating their influence. Note that the dimension of the q-GMM histogramq-Gaussian Mixture Models

64

Figure 5.5: The performance comparison of q-GMM kernels with different q-values
on the PASCAL VOC 2010 dataset. The q-GMM kernel outperforms the
GMM baseline (q = 1.00) and the improved Fisher kernel [37] of GMM
means.

representation and q-GMM super-vector is 512 and 16,384 (=512×32), respectively.

5.6.2 Experimental Results
PASCAL VOC 2010
We first compared our q-GMM histogram representation in Sec.5.4 with the
hard-assignment BoW [3]. Mean AP of the BoW was 30.93% and the qGMM histogram improved it to 32.03%. The q value is set to 1.05 which has
the hardness of 0.5 as presented in Sec. 5.4. This shows that the q-GMM ismore suitable than the hard-assignment BoW for representing an image bya histogram of low-level descriptors.
Next, we compared our q-GMM kernel in Sec.5.5 with three kernel methods: χ2 -kernel, Fisher kernel (FK) [36], and Improved Fisher kernel (IFK)[37]. For the χ2 -kernel, we computed χ2 -distance between the q-GMM histogram representations. For FK and IFK, we extracted Fisher vectors for
GMM means, whose dimension is the same as our super-vector. We ap-

q-Gaussian Mixture Models

65

Figure 5.6: Mean AP on PASCAL VOC 2010 for different numbers of mixture components for q-GMM kernel.

plied L2 and power normalization as in [37] for IFK. The parameter of thepower normalization was set to 0.4 which performed the best in our experiments. As shown in Table 5.2, the q-GMM kernel performed the best
among these methods and achieved 49.42% in Mean AP. Figure 5.5 shows
the performance of the q-GMM kernel for different q values. As can be seen,
the q-GMM outperformed the normal GMM baseline (q = 1.00). The best q
value and its Mean AP were 1.06 and 49.47%, respectively. This shows theeffectiveness of the q-GMM kernel in image classification.
As described in [8], another idea to obtain a discriminative image representation is to train a class-specific model instead of the background model
for a visual codebook. However, APs for aeroplane and bicycle were decreased by 1.30% and 2.09%, respectively, when a q-GMM is trained on one
million descriptors sampled only from images of the targeted object. There
was no significant performance improvement by concatenating both representations: AP for aeroplane was improved by 0.46% but that for bicycle
was decreased by 0.31%. In conclusion, it is better to train a visual codebook on images of various object categories. A class-specific model could
be useful for other problems such as dog breed classification that focus on a
specific category.

q-Gaussian Mixture Models

66

Figure 5.7: Mean AP on PASCAL VOC 2010 for different hyper-parameter τ in maximum a posteriori adaptation for q-GMM kernel.

Figure 5.8: The performance comparison of q-GMM kernels with different q-values
on the TRECVID 2010 dataset.

q-Gaussian Mixture Models

67

Figure 5.9: The performance comparison with other methods in TRECVID 2010.
We achieved 0.071 in Mean AP by using a q-GMM kernel with SIFTHueHistogram features and achieved 0.109 with additional 4 types of
low-level features.

● ● ● ● ● ●● ●●
●
●

●
●

●

●

●

Figure 5.10: Examples of detected video shots in TRECVID 2010 dataset. Top 5
video shots are shown for ten semantic concepts.

q-Gaussian Mixture Models

68

Table 5.2: Performance comparison on PASCAL VOC 2010 dataset. BoW: bagof-visual-words histogram representation [3] obtained by using vector
quantization. Our histogram: q-GMM based histogram representationin Sec. 5.4 for q = 1.00 (GMM) and q = 1.05. χ2 kernel: χ2 kernel
on q-GMM histogram representation. FK: Fisher kernel [36] of a GMM.
IFK: improved Fisher kernel [37]. Our kernel: q-GMM kernel in Sec.5.5
for q = 1.00 (GMM) and q = 1.05.
Concept
aeroplane
bicyclebird
boat
bottle
bus
car
cat
chair
cow
diningtable
dog
horse
motorbikepersonpottedplant
sheep
sofa
train
tvmonitor
Mean AP

BoW[3]
54.38
36.53
24.76
37.41
9.71
56.62
35.63
41.75
33.96
7.12
14.89
24.36
21.53
27.30
68.63
8.54
19.68
16.17
44.59
35.04
30.93

Our histogram
GMM q-GMM
55.21
55.99
37.88
38.20
25.79
25.77
38.29
39.65
10.03
10.28
58.56
59.99
36.51
36.34
42.33
42.05
34.79
35.04
7.69
7.66
15.36
15.22
24.84
24.63
22.98
24.06
28.55
28.19
69.23
69.29
8.38
8.04
20.42
19.37
16.66
17.10
45.71
46.17
36.20
37.48
31.77
32.03

χ2

FK [36]

IFK[37]

75.10
42.52
36.57
50.51
16.36
66.90
45.76
49.62
41.99
12.24
24.11
35.30
31.77
43.41
73.42
10.85
30.07
24.09
51.33
45.88
40.39

68.41
46.79
34.26
50.37
18.06
71.80
51.08
52.09
43.39
13.48
30.76
39.41
35.90
49.64
73.16
14.31
32.64
26.97
57.97
41.96
42.62

81.21
52.07
43.82
58.36
20.51
77.17
55.82
56.96
47.10
20.35
34.11
44.30
43.71
56.27
76.69
15.78
42.17
33.38
62.93
48.79
48.58

Our kernel
GMM q-GMM
81.72
82.34
52.62
53.50
44.39
45.07
56.51
57.32
21.91
22.62
76.29
77.50
56.87
57.24
57.18
57.16
46.70
47.76
21.77
22.76
34.30
34.65
44.61
44.67
43.45
43.81
57.17
58.83
76.84
77.50
16.82
16.91
41.63
42.09
33.47
33.83
63.17
64.27
47.69
48.51
48.76
49.42

Analysis
Here, we analyze the influence of the number of mixture components andthe hyper-parameter τ in Eq.(5.26) on the performance. Figure 5.6 compares the q-GMM kernel with the GMM baseline for different numbers of
mixture components. It is shown that the q-GMM constantly performed better than the GMM baseline. We observed that the difference between the
GMM and the q-GMM is large when the number of mixture components islarge. This observation can be explained as follows. For a GMM, as thenumber of mixture components increases, fewer low-level descriptors are
assigned with a significant posterior probability cik to each Gaussian, i.e.,a matrix of cik becomes sparser and it decreases the performance. On theother hand, for a q-GMM, long-tailed q-Gaussian distributions prevent itfrom becoming sparse. This is the reason why we observed the large differ-

q-Gaussian Mixture Models

69

Table 5.3: Testing cost and Mean AP for each method. K is the number of mixture
components, D is the dimension of low-level descriptor, and N is theaveraged number of support vectors of an SVM.
Representation
Dimension Kernel type
N Testing cost Mean AP
q-GMM histogram
512
linear 1540
O(K)
32.03
χ2 1700
O(N K)
40.39
q-GMM supervector
16384
linear 1251
O(DK)
47.09
RBF 2261
O(N DK)
49.42
Fisher vector (mean)
16384
linear 1494
O(DK)
46.21
RBF 2556
O(N DK)
48.58

ence for a large number of mixture components.
Figure 5.7 illustrates the influence of the hyper-parameter τ in Eq.(5.26)
on the performance. We observed no significant change in performance
when τ was between 10.0 to 25.0. Thus, we conclude that values between
10.0 to 25.0 are reasonable. We also confirmed that the improvement by
the q-GMM is robust against the hyper-parameter τ .
TRECVID 2010
Table 5.4 shows the performance comparison of the q-GMM kernel and the
GMM baseline on TRECVID 2010. The q-GMM kernel of q = 1.05 outperformed the GMM and achieved 7.11% in Mean AP. As shown in Figure 5.8,
the q-value of 1.02 performed the best with 7.12% Mean AP on this dataset.
On the other hand, we observed that the performance is improved to
7.49% if we choose the best q-value for each of targeted semantic concept.
This shows that supervised q-value optimization has potential for improving
the overall performance in future work while our q-value optimization in
Sec 5.4, which is based on the assignment hardness, was in an unsupervisedway.
Another idea to improve the overall performance is to use the both of the
GMM and the q-GMM. The simplest implementation of this idea is averaging
two detection scores obtained from the GMM and the q-GMM. We additionally evaluated it and observed 7.30% Mean AP as shown in Table 5.4. On theother hand, a disadvantage of averaging scores is that it’s time-consuming
to compute independent scores for the GMM and the q-GMM. To reduce thecomputational costs, an efficient method for calculating q-Gaussian probabilities for multiple q-values is needed in future work.

q-Gaussian Mixture Models

70

Table 5.4: Average precision (AP) by semantic concepts on TRECVID 2010. Results
for GMM, q-GMM (q = 1.05), score fusion of GMM and q-GMM (q =1.05), and feature fusion of 5 types of visual and audio features for qGMM are reported.

Concept
Airplane Flying
AnimalAsian People
Bicycling
Boat ShipBus
Car Racing
Cheering
CityscapeClassroom
Dancing
Dark-skinned People
Demonstration Or Protest
Doorway
Explosion Fire
Female-Human-Face-Closeup
Flowers
Ground Vehicles
Hand
MountainNighttime
Old People
Running
Singing
Sitting Down
Swimming
Telephones
Throwing
VehicleWalking
Mean

Single feature
GMM q-GMM Fusion
2.75
2.67
3.01
2.18
2.53
2.39
0.45
0.18
0.40
3.10
2.90
3.31
5.28
5.51
5.24
0.80
0.43
0.57
4.30
3.92
4.03
3.22
3.56
3.38
9.91
10.75 10.85
1.24
1.27
1.21
3.12
5.10
4.53
12.85
13.21 13.77
13.63
13.54 14.14
7.84
7.14
7.95
4.61
4.03
4.28
10.94
10.55 11.09
3.57
3.95
3.59
14.59
14.15 15.46
4.06
4.05
3.92
20.14
20.83
20.15
12.89
9.99
12.24
2.58
1.98
2.37
1.42
1.87
1.90
6.80
8.11
8.40
0.12
0.08
0.09
32.98
33.07 33.35
1.03
1.39
1.39
3.49
5.61
5.45
14.61
14.04
14.28
5.66
6.98
6.41
7.01
7.11
7.30

Feature fusion
q-GMM
15.64
6.44
3.08
5.90
11.01
1.42
4.37
3.81
17.43
0.81
8.89
20.40
17.86
12.44
3.93
17.79
3.86
20.20
9.30
20.87
15.88
8.20
6.88
17.47
0.56
30.82
1.88
7.02
18.91
13.03
10.87

Comparison with other methods
Fig. 5.9 shows the performance comparison with the other methods in the
TRECVID 2010 Semantic Indexing Task [64]. Mean AP of 7.11%, whichq-Gaussian Mixture Models

71

was obtained by using our q-GMM kernel (q = 1.05), ranked 10-th among
87 official runs. Fig. 5.10 shows some examples of detected video shots.
We conclude the q-GMM kernel performed well since the other methods
typically used more than 5 types of low-level features while we used only
one type of low-level features (SIFT with hue histogram).
Furthermore, we achieved Mean AP of 10.90%, which is better than thebest performance on the TRECVID 2010, by combining q-GMM kernels for 4
additional types of low-level features: SIFT with Harris-affine detector, SIFT
with Hessian-affine detector, dense HOG, and MFCC audio features.

5.7 Conclusion
We proposed q-Gaussian mixture models (q-GMMs) and their application toimage and video semantic indexing systems. It has been shown in our experiments that the q-GMM kernels outperform both of the BoW method andthe normal GMM. The q-GMM kernel achieved 0.494 and 0.109 in Mean
Average Precision on the PASCAL VOC 2010 dataset and the TRECVID 2010
Semantic Indexing dataset, respectively. The linear kernel on q-GMM supervectors was shown to be effective in terms of the scalability. Our future
work will focus on optimization of q-values for each semantic concepts. An
extension of the Fisher information analysis to Tsallis statistics would beinteresting as a promising next step.

Chapter 6

Neighbor-To-Neighbor Search
6.1 Overview
Assigning a visual code to a low-level image descriptor, which we call code
assignment, is the most computationally expensive part of image classification algorithms based on the bag of visual word (BoW) framework. As described in Chapter 3, a tree-structured GMM reduces computational cost by
searching visual words for each input feature vectors independently. However, input vectors are often strongly depend on each other when they are
extracted from the same region in an image. Their typical examples aredensely-sampled image descriptors such as dense SIFT, which have been
proven to be effective in image classification [23, 37].
In this chapter, we proposes a fast computation method, Neighbor-toNeighbor (NTN) search, for this code assignment. Based on the fact thatimage features from an adjacent region are usually similar to each other, thisalgorithm effectively reduces the cost of calculating the distance between acodeword and a feature vector. This method can be applied not only to a
hard codebook constructed by vector quantization (NTN-VQ), but also to asoft codebook, a Gaussian mixture model (NTN-GMM).

72

Neighbor-To-Neighbor Search

73

Figure 6.1: Neighbor-to-neighbor (NTN) search. NTN search assigns a code to
an input vector from a neighbor vector to a neighbor vector. A typicalexample of a neighbor vector is a descriptor xj adjacent to a descriptor
xj−1 where image descriptors are densely sampled from an image. The
red path on the image shows the ordering of descriptors.

6.2 Neighbor-To-Neighbor (NTN) Search for Vector
Quantization
6.2.1 Outline
This section presents our neighbor-to-neighbor (NTN) search in a simple
framework, hard VQ. Let X be a set of input vectors and B(x) be a set ofneighbor vectors for an input vector x ∈ X. The NTN search assumes thata neighbor vector in B(x) is similar to x, and that the number of neighbor
vectors is smaller than the codebook size. A typical example that satisfies
this assumption is densely-sampled SIFT descriptors for image classification. Here, B(x) is a set of the four descriptors adjacent to a descriptor x (Figure 6.1 and Figure 6.2) or a set of descriptors in the same pre-segmented
region.
In NTN search, input vectors are ordered from a neighbor vector to aneighbor vector to skip distance calculations for some input vectors basedon a triangle inequality. We first explain the structure of our algorithm andthen explain our speeding-up idea.

Neighbor-To-Neighbor Search

74

Figure 6.2: A histogram of descriptors. Red bars: descriptors that have the samevisual word as a neighbor descriptor. White bars: all descriptors. SIFT
descriptors are extracted from every 4 pixels at 5 scales on the PASCAL
VOC 2007 training images. The codebook size is 512. 61.3% of two
adjacent descriptors have the same visual word.

(a) INIT, j=1(b) STEP1, j=2(c) STEP2-1, j=2(d) STEP2-2, j=2(e) STEP1(f) STEP2-1(g) STEP2-2: input vector: codeword: calculated distance

Figure 6.3: Algorithm overview.

Neighbor-To-Neighbor Search

75

6.2.2 Algorithm
Let {µk }K
k=1 be a codebook. In the initialization step for j = 1, xj is randomly selected from X. Its code vj is determined as
vj = argmin djk ,(6.1)

djk = "xj − µk ",

(6.2)

k

where distanceis calculated for each k = 1, 2, · · · , K. This process is the same as thestraightforward hard VQ.

For j = 2, 3, · · · , N , the following three steps are iterated (Figure 6.3).

(STEP 1: Select the next input vector)

For each x ∈ B(xj−1 ), calculate ∆(x) = "x − xj−1 ", and set
xj =argmin

∆(x),

(6.3)

x∈B(xj−1 )∩X̄

where X̄ = X \ {x1 , · · · , xj−1 } is a set of remaining input vectors. If
B(xj−1 ) ∩ X̄ = ∅ then xj is randomly picked from X̄.
(STEP 2: Calculate distance)
Set k ∗ = vj−1 .
2-1) Calculate distance djk∗ .
2-2) For k = 1, 2, · · · , k ∗ − 1, k ∗ + 1, · · · , K, calculate a lower bound djk for
djk as follows.

djk = dik − δ∆ij ,(6.4)

where i is the index of the input vector whose distance dik has been calculated, δ is a parameter, and ∆ij is an accumulated distance from xi to xj .
This process will be explained in detail in the next paragraph. If djk ≥ djk∗
then skip calculation of djk , otherwise calculate djk .
(STEP 3: Output a code)
Calculate
vj = argmin djk ,
k∈E

(6.5)

Neighbor-To-Neighbor Search

76

where E is a set of indices of codewords whose distance to xj is calculated
in STEP 2.
Here we explain Eq. (6.4) in STEP 2. For a given xj , let’s go back to theprevious input vector xi (i < j) whose distance dik has been calculated (Figure 6.3 (g)). Take the maximum such index i and let ∆ij be an accumulated
distance between xi and xj given by
∆ij =

j
$

p=i+1

"xp − xp−1 ".

(6.6)

The triangle inequality gives
dik − ∆ij ≤ djk ≤ dik + ∆ij .

(6.7)∃δ ∗ ∈ [−1, 1] s.t. djk = dik − δ ∗ ∆ij .

(6.8)

It implies

Thus, for δ ≥ δ ∗ , djk in Eq. (6.4) is a lower bound of distance djk . Notethat the result of coding by this algorithm is exactly the same as that by theoriginal hard VQ in this case.

6.2.3 The parameter δ
Our idea to improve the speed of the algorithm is to regard δ as a constantand use it as a parameter. Then, the lower bound is efficiently updated fromthe previous lower bound by
djk = dj−1,k − δ"xj − xj−1 ".

(6.9)

The lower bound is obtained by only one distance calculation from xj−1 toxj , which is already calculated in STEP 1. By relaxing the restriction δ ≥ δ ∗ ,we can further reduce the computational cost though the exact solution may
not be obtained in such cases.
Alg. 1 summarizes the neighbor-to-neighbor (NTN) search for hard VQ
which outputs assigned codes for each input vector quickly.

Neighbor-To-Neighbor Search

77

Algorithm 1 NTN-VQ
Input: input vectors X (N = |X|),
codebook {µk }Kk=1 , parameter δ.
Output: codes {vi }N
i=1x1 ← Rand(X)dk ← "x1 − µk " for all kv1 ← argmin dk ; k ∗ ← v1
kfor i = 2, · · · , N do
xi ← argmin "x − xi−1 "x∈B(xi−1 )∩X̄dk∗ ← "xi − µk∗ "for all k )= k ∗ dodk ← dk − δ"xi − xi−1 "if dk∗ > dk thendk ← "xi − µk "if dk∗ > dk then k ∗ ← k end if
end ifend forvi ← k ∗end for

6.3 NTN Search for Gaussian Mixture Models
A Gaussian mixture model (GMM) is an extension of hard VQ to a probabilistic framework since it provides a soft assignment of codewords to an input
vector. Here we extend the NTN search to a GMM framework (NTN-GMM).
The algorithm structure of NTN-GMM is the same as NTN-VQ, but insteadof a lower bound of distance for NTN-VQ, an upper bound of a Gaussian
probability is calculated for NTN-GMM.
Let µk , Σk and wk (k = 1, 2, · · · K) be the mean vector, the covariancematrix, and the mixture weight of the k-th mixture component (codeword)of a GMM, respectively. A code cjk for an input vector xj (j = 1, 2, · · · , N )to the k-th codeword is given by

pjk
cjk = &K

k! =1 pjk!

.

(6.10)

Neighbor-To-Neighbor Search

78

Here pjk is a Gaussian probability given by
9
1
2
pjk =
− "xj − µk "Σ−1 ,
2
1 exp
2
k
(2π) d |Σk | 2
wk

where "x"A =√8(6.11)xT Ax. Note that N K probability calculations are requiredin the standard GMM.
Our empirical observation shows that the distribution of pjk over all thecodewords is peaky, i.e., for each input vector xj , a few pjk ’s have a large
value and the others do not. If xj is similar to xj−1 , the “peak” is shifting
gradually as j increments. Conversely, the changes in the “bottom (nopeak)” of the distribution are generally small. This observation brings us
to an idea that we may ignore the change of Gaussian probabilities in the“bottom” of the distribution.
For a given xj , let xi (i < j) be the previous input vector whose Gaussian probability pik has been calculated. The idea is to ignore the difference
(b)

(b)

between pjk and pik and assume pjk = pik for k ∈ Gi ∩ Gj to skip calcu(b)lation of pjk . Here, Gj is a set of mixture components in the “bottom” ofthe distribution, which we call a bottom set, given by(b)

Gj = {k : pjk < pth }.

(6.12)

where pth is a threshold to categorize the mixture components into “peak”
and “bottom”.
(b)

A bottom set Gj

cannot be directly observed without computing pjk .

Thus, we introduce an upper bound pjk of a probability pjk given by
pjk = pik exp (δik ∆ij ) .

(6.13)

Here, ∆ij is the accumulated distance given by Eq. (6.6) and δik is given by
δik = Sk δ"xi − µk "Σ−1 ,k(6.14)

where δ ∈ [0, 1] is a parameter to control the speed of our algorithm (asSubsec. 6.2.3) and Sk is the square root of the spectral radius of Σ−1
k .

The upper bound pjk of the probability (Eq. (6.13)) is delivered as fol-

Neighbor-To-Neighbor Search79

lows. The law of cosines gives∃δ ∗ ∈ [−1, 1] s.t. "xj − µk "2Σ−1(6.15)

k= "xi − µk "2Σ−1 + "xi − xj "2Σ−1 − 2δ ∗ "xi − xj "Σ−1 "xi − µk "Σ−1 .
k

k

k

k

For δ ≥ max(δ ∗ , 0), it implies"xj − µk "2Σ−1 ≥ "xi − µk "2Σ−1 − 2Sk δ"xi − xj ""xi − µk "Σ−1kkk

≥ "xi − µk "2Σ−1 − 2Sk δ∆ij "xi − µk "Σ−1 ,kk(6.16)

where Sk is the square root of the spectral radius of Σ−1
k and ∆ij is theaccumulated distance given by Eq. (6.6). Thus, we have
8
9
wk
1
2
pjk =
exp − "xj − µk "Σ−1
Zk
2
k
8
9
wk
1
2
≤
exp − "xi − µk "Σ−1 + Sk δ∆ij "xi − µk "Σ−1
k
Zk
2
k
1
2
= pik exp Sk δ∆ij "xi − µk "Σ−1k= pik exp (δik ∆ij ) = pjk ,d(6.17)(6.18)(6.19)(6.20)

1

where Zk = (2π) 2 |Σk | 2 and δik is given in Eq.(6.14).

Note that this upper bound is obtained efficiently from a previous upperbound bypjk = pj−1,k exp (δik "xj − xj−1 ") .
(b)

(6.21)(b)

Finally, instead of the intersection of bottom sets Gi ∩ Gj , its subset Uijgiven by

Uij = {k : pjk < pth },(6.22)

is used for determining mixture components to skip calculation of pjk (Figure 6.4).
The threshold pth should depend on the maximum value of Gaussian
probabilities at j, i.e., maxk pjk . However, this value also cannot be observed
without computing all Gaussian probabilities at j. Since two adjacent descriptors are expected to be similar to each other, the value at the previous

Neighbor-To-Neighbor Search

80

Figure 6.4: Distribution of pik and pjk (i < j). Calculation of a Gaussian probability pjk is skipped for k ∈ Uik .

maximum point is used to determine the threshold as
pth = pjk∗ , k ∗ = argmax pj−1,k .

(6.23)k

Note that, by this thresholding, Gaussian probabilities at the previous maximum point and the current maximum point (at least) will be calculated foreach input vector.
Alg. 2 summarizes the NTN search for a GMM which outputs soft codes
for each input vector quickly.
To further improve the speed of NTN-GMM, avoiding the exp computation is effective since our observation shows that 63.0% of the computational cost in coding using a GMM is spent for it. An exp operator is deleted
by taking a log of Gaussian probabilities and introducing log-max (LM) approximation to approximate Eq. (6.10) by

cjk 1



1, if k = argmax log pjk ,k
0, otherwise.

(6.24)

6.4 Experimental evaluation
6.4.1 Experimental setup
We perform image classification experiments on the PASCAL VOC 2007 classification challenge [72]. The dataset consists of 9,963 images, which are
divided into a training set (5011 images) and a testing set (4952 images).
We use Mean Average Precision (Mean AP) over the 20 object categories forevaluating classification accuracies. A single core of a 2.93 GHz Intel XeonNeighbor-To-Neighbor Search

81

Algorithm 2 NTN-GMM
Input: input vectors X (N = |X|),
GMM {wk , µk , Σk }K
k=1 , parameter δ.
KOutput: soft codes {cik }N
i=1 k=1x1 ← Rand(X)pk , pk ← wk N (x1 |µk , Σk ) for all kδk ← Sk δ"x1 − µk "Σ−1 for all kkc1k ← PKpk
for all k; k ∗ ← argmax pk
k! =1 pk!

for i = 2, · · · , N do
xi ← argmin "x − xi−1 "kx∈B(xi−1 )∩X̄pk∗ , pk∗ ← wk∗ N (xi |µk∗ , Σk∗ )for all k )= k ∗ dopk ← pk exp(δk "xi − xi−1 ")if pk∗ < pk thenpk , pk ← wk N (xi |µk , Σk )
δk ← Sk δ"xi − µk "Σ−1k
end ifend forcik ← PKpk
for all k; k ∗ ← argmax pk

end fork! =1 pk!

k

CPU with an 8 GB memory is used for measuring computational costs.
We implement NTN-VQ (Alg. 1) on super-vector (SV) coding [23] andNTN-GMM (Alg. 2) on Fisher-vector (FV) coding [37]. We compare themwith two standard methods, VQ, GMM, and two tree-based methods, ANNVQ, Tree-GMM. The ANN-VQ uses a fast library for approximate nearest
neighbor (ANN) search in [15, 38] for SV coding. The Tree-GMM is anextension of the hierarchical k-means to a GMM framework for FV coding.
In addition, NTN-LM-GMM applies the LM approximation to NTN-GMM.
In all experiments, 2 × 2 SIFT descriptors are extracted from every 4

pixels 1 at 5 scales. We set a set of neighbor vectors B(x) to a set of the four
SIFT descriptors adjacent to a descriptor x. We omit Gaussian weighting for
SIFT descriptors. The averaged number of descriptors per image is 49580.
A codebook is trained on randomly sampled 1 million descriptors by using
k-means algorithm for VQ or EM algorithm for a GMM. Covariance matrices
for a GMM are assumed to be diagonal. The codebook size is set to 512. A
1

Mean APs were 0.582, 0.582 and 0.574 for density of 3, 4, and 5, respectively.

Neighbor-To-Neighbor Search

Figure 6.5:

82

Relative computational cost. Computational cost for each step ofsuper-vector (SV) coding and Fisher-vector (FV) coding is reported.
The codebook size is 512. Feature extraction: SIFT descriptors are
extracted from every 4 pixels at 5 scales, Coding: each descriptor is
assigned to codeword(s), Pooling: an SV or FV image representation is
generated. 85.3%, 56.6%, 88.4%, 65.4% and 64.2% of computationaltime is occupied from coding by VQ, NTN-VQ, GMM, NTN-GMM, and
NTN-LM-GMM, respectively. Total computational cost is reduced by
66.0%, 66.5% and 85.3% by NTN-VQ, NTN-GMM, and NTN-LM-GMM,
respectively.

one-vs-rest linear SVM is used for a classifier for each of 20 object categories,
where the regularization parameter is fixed to 1.0.

6.4.2 Experimental Results
Speed of coding
In Table 6.1, we compare speed of coding at the fixed accuracy level. Overall, our NTN methods are faster than the others while keeping the classification accuracy. We observe that NTN-VQ and NTN-LM-GMM reduce theassignment cost by 77.4% and by 89.3%, respectively. Note that there areno significant differences in Mean AP on randomization test (p < 0.05) between methods in the same split table in Table 6.1. Here, a parameter δ is
optimized on the validation set, where half of training images are used fortraining models and others are used for validating the models. As describedin Subsec. 6.2.3, the restriction of δ ≥ δ ∗ is relaxed in our methods. How-ever, more than 90% of djk gives a correct lower bound when δ = 0.20 for
NTN-VQ as shown in Figure 6.6.
Figure 6.7 shows the speed-accuracy trade-off for NTN methods for different values of δ. We observe that NTN-LM-GMM outperforms NTN-GMM

Neighbor-To-Neighbor Search
MethodVQ
ANN-VQ [15]NTN-VQ
GMM
Tree-GMM
NTN-GMM
NTN-LM-GMM

δ
0.20
0.09
0.09

Mean AP [test/val]*0.568 / 0.519
0.563 / 0.518
0.563 / 0.519*0.582 / 0.532
0.582 / 0.532
0.580 / 0.531
0.579 / 0.531

83
|E|
512.0
57.8
512.0
295.2
88.0
88.0

Time (sec)
856.2
475.7
193.2
2595.71496.8
642.0
276.8

r (%)
0.0
44.4
77.4
0.0
42.3
75.3
89.3

Table 6.1: Speed comparison at the fixed accuracy level. VQ: standard hard vector quantization (VQ), ANN-VQ: approximate nearest neighbor search[15], NTN-VQ: our neighbor-to-neighbor (NTN) search for VQ (Alg. 1),
GMM: standard Gaussian mixture model (GMM), Tree-GMM: an extension of the hierarchical k-means to a GMM framework, NTN-GMM: ourNTN search for a GMM (Alg. 2), NTN-LM-GMM: NTN-GMM with logmax approximation. δ: a parameter of our NTN methods, Mean AP:
image classification accuracy on the testing set and the validation setof the VOC 2007 classification challenge. |E|: the number of distanceor probability calculations per input vector, Time: assignment time insec, Reduction rate r: reduction rate of the assignment cost. Note that
there are no statistically significant differences in Mean AP between themethod marked “*” and each other method in the same split table on
randomization test (p < 0.05).

and NTN-VQ in terms of both speed and accuracy. This is because NTN-LMGMM has the advantages of both of NTN-VQ and NTN-GMM: it only requires
distance calculations without using an exp operator as NTN-VQ, but it has aweight coefficient and a covariance matrix for each codeword as NTN-GMM.
Compared with tree-based methods, a disadvantage of NTN methods isthat they are not very effective if neighbor vectors are not similar to eachother. We confirm this in Figure 6.8: a tree-based ANN-VQ performs better
than RAND-VQ which replaces a neighbor vector by a randomly sampled
vector in each iteration of NTN-VQ. Notably, the average distance between
two neighbor descriptors (xj−1 and xj ) is 132.8 and 507.7 for NTN-VQ and
RAND-VQ, respectively. This confirms that the assumption that neighbor
vectors are similar to each other, is necessary for NTN methods.
In addition, we confirm the necessity of the accumulated distance in
Eq. (6.6) by replacing it with direct distance, i.e., ∆ij = "xi − xj " in Fig-ure 6.9. If we ignore computation time for ∆ij , for example in the casewhere a distance matrix on input vectors is pre-computed in some way, thedirect distance is better than the accumulated distance. In general, the ac-

Neighbor-To-Neighbor Search

84

Figure 6.6: Cumulative histogram of δ ∗ . Statistics of the true δ ∗ in Eq. (6.8) on
PASCAL VOC 2007 training images is reported for NTN-VQ.

cumulated distance is computationally effective since it derives efficient update rules of a lower/upper bound in Eq. (6.9) and (6.21).
Result examples
We examine the effectiveness of NTN-VQ for several different images in Figure 6.10. The reduction rate of the assignment cost by NTN-VQ is 84.9% for
the image (a) and 66.8% for the image (d). Here, (a) and (d) are the best
and the worst cases on PASCAL VOC 2007, respectively. This shows that
NTN methods are more effective for images which can be segmented into
several uniform regions. Notably, NTN-VQ is still better than ANN-VQ evenin the worst case.
Codebook size
The simplest idea to reduce the assignment cost is to reduce the codebook
size. In Figure 6.11, which shows the speed-accuracy trade-off for different
codebook sizes, we confirm that using NTN methods is better than reducing
the codebook size. This also confirms that NTN-LM-GMM is the best in bothspeed and accuracy. Note that there is no significant difference in Mean
AP between a standard method and a NTN methods for each codebook size
K = 2048, 1024, · · · , 16.
Relative computational time in a pipeline
Figure 6.5 shows the relative cost of coding with respect to the cost of theother steps of processing pipeline for extracting SV and FV representations.
As can be seen, the coding step is the majority of the whole processing

Neighbor-To-Neighbor Search

85

Figure 6.7: Speed-accuracy trade-off for different values of δ. Trade-off between assignment time and Mean AP is reported. All plots are forδ = 1.0, 0.9, · · · 0.1, 0.09, · · · , 0.01. VQ: standard hard vector quantization (VQ), NTN-VQ: neighbor-to-neighbor (NTN) search for VQ, GMM:
standard Gaussian mixture model (GMM), NTN-GMM: NTN search fora GMM, NTN-LM-GMM: NTN-GMM with the log-max approximation.

Neighbor-To-Neighbor Search

86

Figure 6.8: Comparison with RAND-VQ. Trade-off between assignment time andMean AP is reported. NTN-VQ: neighbor-to-neighbor (NTN) search for
VQ, this is the same plot as Figure 6.7, ANN-VQ: approximate nearest
neighbor search [15], RAND-VQ: NTN-VQ in which a neighbor vector
is replaced by a randomly sampled vector.

pipeline: 85.3% and 88.4% of computational time are occupied from it in
FV coding and SV coding, respectively.
NTN-VQ, NTN-GMM and NTN-LM-GMM reduces the total computational
cost by 66.0%, 66.5%, and 85.3%, respectively. Note that the cost of poolingin FV coding, which generate a final FV representation, is also reduced by
the LM approximation since we can skip some summations in pooling if cik
is equal to zero.
For large-scale image classification, for example on the ImageNET withmore than 20,000 object categories, we should consider the SVM-classification
cost, which is neg- ligible in our experiments on PASCAL VOC with 20 categories. To reduce the SVM-classification cost, applying dimension reduction techniques such as product quantiza- Speed-accuracy trade-off for different codebooktion to the final image representation can be effectively utilized.

Neighbor-To-Neighbor Search

87

Figure 6.9: Comparison of the accumulated distance and the direct distance.
VQ error rate in NTN-VQ for different values of δ is reported. All plots
are for δ = 1.0, 0.9, · · · 0.1, 0.09, · · · 0.01. Accumulated distance: ∆ij
is defined by Eq. (6.6). Direct distance: ∆ij is replaced by the direct
distance "xi − xj ". Pre-computed direct distance: the direct distanceis used but distance calculations for it are not counted.

Neighbor-To-Neighbor Search

88

Figure 6.10: The computational cost reduction by NTN-VQ for different images. Four images (a), (b), (c), and (d) are from PASCAL VOC 2007.
The reduction rate of the assignment cost by NTN-VQ and ANN-VQ
for each image is reported.

Neighbor-To-Neighbor Search

89

Figure 6.11: Speed-accuracy trade-off for different codebook sizes. Tradeoff between assignment time and Mean AP for codebook sizes of
K = 2048, 1024, 512, · · · , 16. is reported. VQ: standard hard vector
quantization (VQ), NTN-VQ: neighbor-to-neighbor (NTN) search for
VQ δ = 0.20, GMM: standard Gaussian mixture model (GMM), NTNGMM: NTN search for a GMM δ = 0.09, NTN-LM-GMM: NTN-GMM
with the log-max approximation δ = 0.09.

Neighbor-To-Neighbor Search90

6.5 Conclusion
We have proposed a fast computation method for searching for the matches,neighbor-to-neighbor (NTN) search, and its applications to vector quantization (VQ) and a Gaussian mixture model (GMM). We tested NTN-VQ and
NTN-GMM on super-vector coding and Fisher-vector coding, respectively.
Our experiments on the PASCAL VOC 2007 classification challenge showedthat NTN-VQ, NTN-GMM, and NTN-LM-GMM reduced the assignment costby 77.4%, 75.3%, and 89.3%, respectively, without any significant degradation in the image classification performance. This result confirms theeffectiveness of our proposed algorithms.
In future work, we will focus on the speeding up of the feature extraction
step that we didn’t discuss in this chapter. Approximation of dense sampling
and SIFT descriptors would be interesting as promising next steps.

Chapter 7

Conclusion and Future Work
We have proposed an efficient and effective semantic indexing system. Our
system extended the bag-of-visual-words system to a probabilistic framework in which a video segment is modeled by a GMM. By extracting audio and visual low-level features, we effectively detected semantic concepts
from video data. A q-GMM, which is generalization of a GMM with a parameter q to control its tail-heaviness, further improved the modeling accuracy. In experiments on the TRECVID benchmark, we achieved Mean
Average Precision (AP) of 0.178, and 0.321 on TRECVID 2011, and 2012
datasets, respectively, which is the best performance among official runs in
the TRECVID workshop.
To improve the speed of the system, we have proposed fast MAP adaptation and Neighbor-to-Neighbor (NTN) search, which are complementary
techniques to each other. For fast MAP adaptation, a tree-structured GMM
was utilized to decrease the computational cost, where only the output probabilities of mixture components close to a feature vector are precisely calculated. The calculation time for MAP adaptation was reduced by 76.2% fromthe conventional method, while high detection performance was maintainedon the TRECVID benchmark. The NTN search further improved the speed
when densely sampled image descriptors are used in the low-level feature
extraction step. Based on the fact that image features extracted from anadjacent region are usually similar to each other, the NTN algorithm effectively reduced the cost of calculating the distance between a codeword anda feature vector. In experiments, we applied the NTN search to vector quantization (NTN-VQ) and a GMM (NTN-GMM). Results on the PASCAL VOC
91

Conclusion and Future Work92

2007 classification challenge showed that NTN-VQ reduced the assignment
cost by 77.4% in super-vector coding, and NTN-GMM reduced it by 89.3%
in Fisher-vector coding, without any significant degradation in classification
performance.
Our future work will focus on the relation between semantic concepts
to extend our system to generate detailed meta data such as a text summarization of video. In this study, we focused on detecting word-level semantic
concepts which is the most important part of meta-data in key-word searchengines. However, what users require will probably become sentence-level
semantic concepts such as complex events and human actions in near future.
To detect the sentence-level semantic concepts, temporal and spatial localization of objects and motions is needed which is not discussed in this study.
For example, temporal modeling using hidden Markov models (HMMs) orbayesian networks is expected to effectively capture the causality relation
between semantic concepts. To improve the speed of detection, the next
step would be the GPU implementation of our methods. We also would liketo apply our techniques to other applications than semantic indexing suchas robot serving, object tracking and video editing.

Bibliography[1] M. Kankanhalli and Y. Rui, Application potential of multimedia information retrieval, In Proc. IEEE MIR, vol. 96, pp. 712-720, 2008.
[2] A.W.M. Smeulders, M. Worring, S. Santini, A. Gupta, R. Jain Contentbased image retrieval at the end of the early years, In IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.22, no.12,
pp.1349–1380, 2000.
[3] G. Csurka, C. Dance, L. Fan, J. Willamowski, and C. Bray. Visual
categorization with bags of keypoints. Proc. ECCV SLCV workshop,
pages 59–74, 2004.
[4] J. Yang and A. G. Hauptmann. Evaluating bag-of-visual-words representations in scene classification. In Proc. of ACM Multimedia MIR
workshop, Augsburg, Germany, 2007.
[5] D. G. Lowe. Distinctive image features from scale-invariant keypoints. IJCV, 60(2):91–110, 2004.
[6] J. C. V. Gemert, J.-m. Geusebroek, C. J. Veenman, and A. W. M.
Smeulders. Kernel codebooks for scene categorization. In Proc. of
ECCV, pages 696–709, 2008.
[7] J. Wang, J. Yang, K. Yu, F. Lv, T. Huang, and Y. Gong. Localityconstrained linear coding for image classification. Proc. CVPR, pages
3360–3367, 2010.
[8] F. Perronnin, C. Dance, G. Csurka, and M. Bressan. Adapted vocabularies for generic visual categorization. Proc. ECCV, pages 464–475,
2006.
[9] C.G.M. Snoek, K.E.A. van de Sande, O. de Rooij, B. Huurnink,
E. Gavves, D. Odijk, M. de Rijke, Th. Gevers, M. Worring,
D.C. Koelma, and A.W.M. Smeulders The MediaMill TRECVID 201093

BIBLIOGRAPHY
Semantic Video Search Engine.

94
In Proc. of TRECVID workshop,

Gaithersburg, MD, USA, 2010.
[10] S.-F. Chang, D. Ellis, W. Jiang, K. Lee, A. Yanagawa, A.C. Loui, and
J. Luo, Large-scale Multimodal Semantic Concept Detection for Consumer Video. In Proc. of ACM Multimedia MIR workshop, Augsburg,
Germany, 2007.
[11] W. Jiang, C. Cotton, S.-F. Chang, and D. Ellis, Short-Term AudioVisual Atoms for Generic Video Concept Classification. In Proc. of
ACM Multimedia, Beijing, China, 2009.
[12] M. Huijbregts, R. Ordelman, F. De Jong, Annotation of Heterogeneous Multimedia Content Using Automatic Speech Recognition, In
Proc. SAMT, vol.4816, pp.78–90, 2007.
[13] A. F. Smeaton, P. Over, and W. Kraaij. High-Level Feature Detection
from Video in TRECVid: a 5-Year Retrospective of Achievements. In
A. Divakaran, editor, Multimedia Content Analysis, Theory and Applications, pages 151–174, Springer Verlag, Berlin, 2009.
[14] C. Silpa-anan and R. Hartley. Optimised kd-trees for fast image descriptor matching. Proc. CVPR, pages 1–8, 2008.
[15] M. Muja and D. G. Lowe. Fast approximate nearest neighbors with
automatic algorithm configuration. Proc. VISAPP, pages 331–340,
2009.
[16] M. Brown, and D.Lowe, Recognizing panoramas. In Proc. ICCV,
pp.1218–1225, 2003.
[17] J. Matas, O. Chum, M. Urban, and T. Pajdla, Robust wide-baseline
stereo from maximally stable extremal regions,

In Proc. BMVC,

pp.384–393, 2002.
[18] P. Pritchett, and A. Zisserman, Wide baseline stereo matching, In
Proc. ICCV, pp.754–760, 1998.
[19] T. Tuytelaars, L. V. Gool, L. Dhaene, and R. Koch, Matching ofaffinely invariant regions for visual servoing, In Proc. ICRA, 1999
[20] S. Lazebnik, C. Schmid, and J. Ponce, A sparse texture representation
using affine-invariant regions, In Proc. CVPR, 2003.

BIBLIOGRAPHY

95[21] S. Lazebnik, C. Schmid, and J. Ponce, Affine-invariant local descriptors and neighborhood statistics for texture recognition, In Proc.
ICCV, pp.649–655, 2003.
[22] K. Mikolajczyk and C. Schmid. Scale and affine invariant interest
point detectors. In IJCV, vol. 60(1), pages 63–86, 2004.
[23] X. Zhou, K. Yu, T. Zhang, and T. S. Huang. Image classification using
super-vector coding of local image descriptors. Proc. ECCV, pages
141–154, 2010.
[24] I. Laptev and T. Lindeberg, Space-time interest points In Proc. ICCV,
pp.432–439, 2003.
[25] H. Wang, A. Kl, C. Schmid, C.-lin Liu, Action Recognition by Dense
Trajectories In Proc. CVPR, pp.3169–3176, 2011.
[26] N. Dalal, W. Triggs, C. Schmid, S. Soatto, and C. Tomasi, Histogramsof Oriented Gradients for Human Detection, In Proc. CVPR, pp.886–
893, 2005[27] X. Wang, T. X. Han, S. Yan, An HOG-LBP human detector with partial
occlusion handling, In Proc. ICCV, pp.32–39, 2009.
[28] J. van de Weijer and C. Schmid. Coloring local feature extraction. In
Proc. of ECCV, pp. 334–348, 2006.
[29] K. E. A. van de Sande, T. Gevers, and C. G. M. Snoek. Evaluatingcolor descriptors for object and scene recognition. In IEEE Trans. on
Pattern Analysis and Machine Intelligence, vol. 32(9), pp. 1582–1596,
2010.
[30] M. Calonder, V. Lepetit and C. Strecha and P. Fua, BRIEF : Binary
Robust Independent Elementary Features, In Proc. ECCV, 2010.
[31] E. Rublee, V .Rabaud, K. Konolige and G. Bradski, ORB: an efficient
alternative to SIFT or SURF, In Proc. ICCV, 2011.
[32] S. N. Sinha, J. michael Frahm, M. Pollefeys, and Y. Genc. Gpu-based
video feature tracking and matching. In Proc. of EDGE workshop,
Chapel Hill, NC, USA, 2006.
[33] T. Huang. Linear spatial pyramid matching using sparse coding forimage classification. Proc. CVPR, pages 1794–1801, 2009.

BIBLIOGRAPHY

96[34] H. Jegou, M. Douze, C. Schmid, and P. Perez. Aggregating local descriptors into a compact image representation. In Proc. of CVPR, pages
3304–3311, 2010.
[35] T. Jaakkola, and D. Haussler, Exploiting Generative Models in Discriminative Classifiers In Proc. of NIPS, pp. 487–493, 1998.
[36] F. Perronnin, and C. Dance, Fisher kernels on visual vocabularies forimage categorization. In Proc. of CVPR, pp. 1–8, 2007.
[37] F. Perronnin, S. Jorge, and T. Mensink. Improving the fisher kernel for large-scale image classification. Proc. ECCV, pages 143–156,
2010.
[38] K. Chatfield, V. Lempitsky, A. Vedaldi, and A. Zisserman. The devil
is in the details: an evaluation of recent feature encoding methods.
Proc. BMVC, pages 1–12, 2011.
[39] M. Havrda and F. Charvat. Quantification method of classification
processes: concept of structural α-entropy, In Kybernetika, vol. 3, pp.
30–35, 1967.
[40] C. Tsallis, Possible generalization of boltzmann-gibbs statistics, In
Journal of Statistical Physics, vol. 52, pp. 479–487, 1988.
[41] C. Tsallis, R. S. Mendes, A. R. Plastino, The role of constraints within
generalized nonextensive statistics, In Physica A, vol. 261, no. 3, pp.
534-554, 1988.
[42] M. P. de Albuquerque, I. A. Esquef, and A. R. G. Mello, Image thresholding using Tsallis entropy. In Elsevier Pattern Recognition Letters,
vol. 25, pp. 1059–1065, 2004.
[43] P. K. Sahoo, and G. Arora, Image thresholding using two-dimensional
Tsallis-Havrda-Charvat entropy, In Elsevier Pattern Recognition Letters, vol. 27, issue. 6, pp. 520–528, 2006.
[44] Q. Lin, and C. Ou, Tsallis entropy and the long-range correlation inimage thresholding, In Elsevier Signal Processing, vol. 92, pp. 2931–
2939, 2012.
[45] Y. Li, X. Fan, and G. Li. Image segmentation based on Tsallis-entropy
and Renyi-entropy and their comparison. In Proc. of ICII, pp. 943–
948, 2006.

BIBLIOGRAPHY

97[46] R. Fabbrib, W. N. Goncalvesa, F. J. P. Lopesc, and O. M. Brunoa,
Multi-q pattern analysis: A case study in image classification, In
Elsevier Physica A: Statistical Mechanics and its Applications, vol.
391, issue. 19, pp. 4487–4496, 2012.
[47] D. Gerogiannis, C. Nikou, and A. Likas Robust Image Registration
using Mixtures of t-distributions, In Proc. of ICCV, 2007.
[48] T. M. Nguyen and Q. M. J. Wu, Robust Student’s-t Mixture Model
With Spatial Constraints and Its Application in Medical Image Segmentation, In IEEE Trans. on Medical Imaging, vol.31, no.1, 2012.
[49] N. Johnson, S. Kotz, and N. Balakrishnan, Discrete Multivariate Distributions, New York: Wiley Interscience, 1997.
[50] D. Nister and H. Stewenius. Scalable recognition with a vocabularytree. Proc. CVPR, pages 2161–2168, 2006.
[51] J. C. Platt, Probabilities for SV machines, In Advances in Large Margin Classifiers, pp.61–74, The MIT Press, 2000.
[52] H.-T. Lin, C.-J. Lin, and R. C. Weng, A note on Platt’s probabilistic
outputs for support vector machines, In Machine Learning, vol. 68,
pp. 267276, 2007.
[53] J. Zhang, M. Marszalek, S. Lazebnik, and C. Schmid, Local featuresand kernels for classification of texture and object categories: A comprehensive study, In International Journal of Computer Vision, vol.
73, pp. 213-238, 2007.
[54] Y. Rubner, C. Tomasi, and L. J. Guibas, The earth mover’s distanceas a metric for image retrieval, International Journal of Computer
Vision, vol. 40, pp. 99121, 2000.
[55] F. R. Back and G. R. G. Lanckriet. Multiple Kernel Learning, Conic
Duality, and the SMO Algorithm In Proc. of ICML, Banff, Alberta,
Canada, 2004.
[56] F. Yan, J. Kittler, K. Mikolajczyk, and A. Tahir. Non-sparse multiple
kernel learning for fisher discriminant analysis. In Proc. of ICDM,
Miami, Florida, USA, 2009.
[57] A. Bosch, A. Zisserman, and X. Munoz. Image classification using
random forests and ferns. In Proc. of ICCV, Rio de Janeiro, Brazil,
2007.

BIBLIOGRAPHY

98[58] A. P. Dempster, N. M. Laird, and D. B. Rubin, Maximum Likelihoodfrom Incomplete Data via the EM Algorithm, Journal of the Royal
Statistical Society, vol.Series B, 39, no.1, pp.1–38, 1977.
[59] V. N. Vapnik, Statistical learning theory, Wiley, New York, 1 ed., Sept.
1998.
[60] N. Cristianini and J. Shawe-Taylor, Support Vector Machines, Cambridge University Press, Cambridge, 2000.
[61] C. J. C. Burges, A tutorial on support vector machines for patternrecognition, Data Min. Knowl. Discov., vol.2, pp.121–167, 1998.
[62] W. M. Campbell, D. E. Sturim, and D. A. Reynolds. Support vector
machines using GMM supervectors for speaker verification. In IEEE
Signal Processing Letters, vol. 13, pp. 308–311, 2006.
[63] X. Zhou, X. Zhuang, S. Yan, S.-F. Chang, M. H.-Johnson, and T. S.
Huang. Sift-bag kernel for video event analysis. In Proc. of ACM
Multimedia, Vancouver, British Columbia, Canada, 2008.
[64] A. F. Smeaton, et al. Evaluation campaigns and trecvid. In Proc. of
ACM Multimedia MIR workshop, pp. 321–330, 2006.
[65] S. Ayache and G. Quénot. Video Corpus Annotation Using Active
Learning. In Proc. of ECIR, 2008.
[66] E. Yilmaz, E. Kanoulas, and J. A. Aslam. A simple and efficient sampling method for estimating ap and ndcg. In Proc. of ACM SIGIR,
Singapore, 2008.
[67] C. Wu. SiftGPU: A GPU implementation of sift. http://cs.unc.edu/˜
ccwu/siftgpu, 2007.
[68] Koen E. A. van de Sande, Theo Gevers, Cees G. M. Snoek. Empowering Visual Categorization With the GPU. In IEEE Transactions on
Multimedia, vol. 13 (1), pages 60–70, 2011.
[69] S. J. Young, G. Evermann, M. J. F. Gales, D. Kershaw, G. Moore, J. J.
Odell, D. G. Ollason, D. Povey, V. Valtchev, and P. C. Woodland. The
htk book, version 3.4, 2006.
[70] C.-C. Chang and C.-J. Lin. Libsvm: a library for support vector machines. Software available at http://www.csie.ntu.edu.tw/cjlin/libsvm, 2001.

BIBLIOGRAPHY

99[71] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman. The PASCAL Visual Object Classes Challenge 2010 (VOC2010)
Results. http://www.pascal-network.org/challenges/VOC/[72] M. Everingham, A. Zisserman, C. Williams, and L. V. Gool. The pascal visual obiect classes challenge 2007 (voc2007) results. http://
www.pascal-network.org/challenges/VOC/voc2007/, 2007.
[73] H. Jégou, M. Douze, and C. Schmid. Product quantization for nearest
neighbor search. IEEE Trans. on Pattern Analysis and Machine Intelligence, 33(1):117–128, 2011.

List of Publications
Journal Paper
1. Nakamasa Inoue and Koichi Shinoda, q-Gaussian Mixture Models for
Image And Video Semantic Indexing, In Elsevier Journal of Visual Communication and Image Representation, vol.24, no.8 pp.1450-1457, 2013.
2. Yusuke Kamishima, Nakamasa Inoue and Koichi Shinoda, Event Detection in Consumer Videos Using GMM Supervectors and SVMs, In
EURASIP Journal on Image and Video Processing, vol.2013:51, pp.1–13,
2013.
3. Nakamasa Inoue and Koichi Shinoda,

A Fast and Accurate Video

Semantic-Indexing System Using Fast MAP Adaptation and GMM Supervectors, In IEEE Transactions on Multimedia, vol.14, no.4–2, pp.1196–
1205, 2012.
4. Nakamasa Inoue, Tatsuhiko Saito, Koichi Shinoda, and Sadaoki Furui,
Multimodal High-Level Feature Extraction for Large-Scale Video Resources In IEICE Transactions on Information and Systems, vol.J93–D,
no.12, pp.2633–2644, 2010, in Japanese.

International Conference Paper (Reviewed)
1. Liang Zhuolin, Nakamasa Inoue, and Koichi Shinoda, Velocity Pyramid
for Multimedia Event Detection, In Proc. of MMM, Jan., 2014.
2. Nakamasa Inoue, and Koichi Shinoda, Neighbor-To-Neighbor Search
for Fast Coding of Feature Vectors In Proc. of ICCV, pp.1233-1240, Dec.,
2013.
3. Nakamasa Inoue and Koichi Shinoda, q-Gaussian Mixture Models Basedon Non-Extensive Statistics for Image And Video Semantic Indexing, In
Proc. of Asian Conference on Computer Vision (ACCV), pp.1–12 (PT1–20), Korea, Nov., 2012.

100

LIST OF PUBLICATIONS

101

4. Yusuke Kamishima, Nakamasa Inoue, Koichi Shinoda, and Shunsuke
Sato, Multimedia Event Detection Using GMM Supervectors and SVMs,
In Proc. of ICIP, USA, pp.3089–3092, Oct., 2012.
5. Nakamasa Inoue and Koichi Shinoda, A Fast MAP Adaptation Techniquefor GMM-supervector-based Video Semantic Indexing, In Proc. of ACM
Multimedia, USA, pp.1357–1360, Nov., 2011.
6. Nakamasa Inoue, Tatsuhiko Saito, Koichi Shinoda, and Sadaoki Furui,High-Level Feature Extraction using SIFT GMMs and Audio Models, In
Proc. of ICPR, Turkey, pp.3220–3223, Aug., 2010.

International Workshop Paper
1. Nakamasa Inoue, Kotaro Mori, Liang Zhuolin, and Koichi Shinoda, Semantic Indexing Using GMM Supervectors and Video-Clip Scores (TokyoTechCanon at TRECVID 2013), In Proc. of TREC Video Retrieval Evaluation (TRECVID) workshop, USA, Nov., 2013.
2. Nakamasa Inoue, Yusuke Kamishima, Kotaro Mori, and Koichi Shinoda,
Multimedia Event Detection Using GMM Supervectors and Camera Motion Cancelled Features (TokyoTechCanon at TRECVID 2012), In Proc.
of TREC Video Retrieval Evaluation (TRECVID) workshop, USA, Nov.,
2012.
3. Nakamasa Inoue and Koichi Shinoda, Video Semantic Indexing Using
GMM-Supervectors, Greater Tokyo Area Multimedia/Vision Workshop,
Japan, Aug, 2012.
4. Nakamasa Inoue, Toshiya Wada, Yusuke Kamishima, Koichi Shinoda,
and Shunsuke Sato, Semantic Indexing Using GMM Supervectors andTree-structured GMMs (TokyoTech+Canon at TRECVID 2011), In Proc.
of TREC Video Retrieval Evaluation (TRECVID) workshop, USA, Dec.,
2011.
5. Nakamasa Inoue, Toshiya Wada, Yusuke Kamishima, Koichi Shinoda,
Ilseo Kim, Byungki Byun, and Chin-Hui Lee, Semantic Indexing Using
GMM Supervectors with MFCCs and SIFT features (TT+GT at TRECVID
2010 Workshop), In Proc. of TREC Video Retrieval Evaluation (TRECVID)
workshop, USA, Nov., 2010.
6. Nakamasa Inoue, Shanshan Hao, Tatsuhiko Saito, Koichi Shinoda, Ilseo
Kim and Chin-Hui Lee,

High-Level Feature Extraction Using SIFT

LIST OF PUBLICATIONS

102

GMMs, Audio Models, and MFoM (TITGT at TRECVID 2009 Workshop),
In Proc. of TREC Video Retrieval Evaluation (TRECVID) workshop, USA,pp.373–380, Nov., 2009.

Domestic Conference Paper
1. 井上 中順, 篠田 浩一, GMM Supervector とビデオクリップスコアを用いた映像のセマンティックインデクシング, 電子情報通信学会 パターン
認識・メディア理解研究会 (PRMU), vol.112, no.441, pp.173–178, Feb.,2013.
2. 上嶋 勇祐, 井上 中順, 篠田 浩一, カメラの動き補正に基づく時空間特徴
量と GMM supervector を用いた映像からのイベント検出, 電子情報通信学会 パターン認識・メディア理解研究会 (PRMU), vol.112, no.441,

pp.185–190, Feb., 2013.
3. 井上 中順, 篠田 浩一, 映像のセマンティックインデクシングのための q混合ガウス分布, 電子情報通信学会 パターン認識・メディア理解研究会(PRMU), vol.112, no.197, pp.31–36, Sep., 2012.
4. 井上 中順, 篠田 浩一, GMM-Supervector を用いた高速な映像のセマン
ティック検索システム, 画像の認識・理解シンポジウム (MIRU), pp.DS–

09, Aug., 2012.
5. 井上 中順, 篠田 浩一, GMM-supervector を用いた映像の高速セマンティッ
ク検索システム〜映像の意味に基づいた検索を実現〜, 画像センシングシ
ンポジウム (SSII), pp.DS2–08, Jul., 2012.

6. 上嶋 勇祐, 井上 中順, 篠田 浩一, GMM-Supervector と SVM を用いた映像からのイベント検出, 電子情報通信学会 パターン認識・メディア理解研究会 (PRMU), vol.111, no.430, pp.195–200, Feb., 2012.

7. 井上 中順, 篠田 浩一, 木構造 GMM を用いたセマンティックインデクシ
ングの高速化, 電子情報通信学会 パターン認識・メディア理解研究会(PRMU), vol.111, no.77, pp.105–110, Jun., 2011.
8. 井上 中順, 上嶋 勇祐, 篠田 浩一, マルチモーダル・マルチフレームな手法を用いた TRECVID セマンティックインデクシング, 電子情報通信学会 パ
ターン認識・メディア理解研究会 (PRMU), vol.110, no.414, pp.25–30,

Feb., 2011.
9. 井上 中順, 上嶋 勇祐, 篠田 浩一, SIFT 混合ガウス分布を用いた一般物体認識のためのマルチカーネル学習, 電子情報通信学会 パターン認識・メ
ディア理解研究会 (PRMU), vol.110, no.187, pp.7–12, Sep., 2010.

LIST OF PUBLICATIONS

103

10. 斉藤 辰彦, 井上 中順, 篠田 浩一, 古井 貞煕, 音響特徴を用いた映像からのイベント検出の研究, 日本音響学会 2010 年 春季研究発表会, 日本音響学会講演論文集, pp.201-202, Mar, 2010.

11. 井上 中順, 斉藤 辰彦, 篠田 浩一, 古井 貞煕, SIFT 混合ガウス分布と音響特徴を用いた映像からの高次特徴検出, 電子情報通信学会 パターン認識・
メディア理解研究会 (PRMU), vol.109, no.306, pp.97–102, Nov., 2009.

Invited Talk
1. 井上 中順, 篠田浩一, ［特別講演］映像の高性能なセマンティックインデ
クシングを目指して, 電子情報通信学会 パターン認識・メディア理解研
究会 (PRMU), vol.111, no.353, pp.89–94, Dec., 2011.

Article1. Koichi Shinoda and Nakamasa Inoue, Reusing Speech Techniques forVideo Semantic Indexing, In IEEE Signal Processing Magazine, vol.30,
no.2, pp.118–122, 2013.

Award
2011 年 パターン認識・メディア理解研究会 研究奨励賞