AUTOMATIC VIDEO ANNOTATION VIA HIERARCHICAL TOPIC TRAJECTORY MODELCONSIDERING CROSS-MODAL CORRELATIONS
Takuho Nakano , Akisato Kimura† , Hirokazu Kameoka† , Shigeki Miyabe , Shigeki Sagayama ,Nobutaka Ono , Kunio Kashino† , Takuya NishimotoGraduate School of Information Science and Technology, The University of Tokyo†NTT Communication Science Laboratories, NTT Corporation/ŵĂŐĞĨĞĂƚƵƌĞƐ

ABSTRACT
We propose a new statistical model, named Hierarchical Topic Trajectory Model (HTTM), for acquiring a dynamically changing topic
model that represents the relationship between video frames and associated text labels. Model parameter estimation, annotation and retrieval can be executed within a uniﬁed framework with a few computation. It is also easy to add new modals such as audio signal
and geotags. Preliminary experiments on video annotation task withmanually annotated video dataset indicate that our proposed method
can improve the annotation accuracy.
Index Terms— Video annotation, generative approach, topic
model, canonical correlation analysis, hidden Markov model
1. INTRODUCTION
Content-based retrieval has been the subject of a signiﬁcant amountof research in this decade [1, 2, 3]. Especially, we are focusing onvideo signals as the subject of research, since video signals often
include various types of information such as text, audio and visual
information.
The realization of general-purposed image/video annotation retrieval has still been a challenging problem. Previous efforts havebeen mainly directed to how to construct and combine binary classiﬁers such as support vector machine (SVM) [4, 5] and supervised
multi-class learning (SML) [6] to annotate with respect to the presence or absence of each text label. However, this approach has thefollowing crucial drawbacks. 1) Generally speaking, incorporatingco-occurrences among text labels into this approach is quite difﬁcult. For example, if a image contains buses, cars and an unknown
object, that is hard to recognise, and we have to decide the object isa cow or a bike. If we use binary classiﬁers for cows and bikes, that
may give us no information. But we know that bikes co-occurs withbuses and cars more frequently than cows. Although some previous work [7] tried to integrate collocations between text labels withtwo different attributes, it is impossible to extend it to general typesof co-occurrences. 2) In many methods, “one vs the rest” classiﬁers
have been utilized mainly due to computational efﬁciency. However,this strategy often encounters the so-called masking problem[8] because of the disparity in samples, which means that discriminationfor each class often fails.
Recently, inference techniques based on topic models (see Fig.
1) have been proposed for acquiring topic models. Probabilistic
latent semantic analysis (pLSA) [9] and latent Dirichlet allocation
 {t-nakano, miyabe, sagayama, onono, nishi}@hil.t.u-tokyo.ac.jp† akisato@ieee.org, {kameoka, kunio}@eye.brl.ntt.co.jp

978-1-4577-0539-7/11/$26.00 ©2011 IEEE

2380

dŽƉŝĐƐ

dĞǆƚĨĞĂƚƵƌĞƐ

Fig. 1. Topic model representing topics of both image features andtext features in symmetric translation model.
(LDA) [10] are widely known and have been exploited for image
annotation retrieval [6, 11, 12, 13, 14]. Canonical correlation analysis (CCA) [15, 16, 17], which is a generalized variant of Fisher
linear discriminant analysis (FDA) for multi-category classiﬁcation,is also known as one of them. CCA is easy-to-use and feasible for
efﬁciently acquiring topic models. Its effectiveness on image annotation and retrieval has been presented in some previous researches[18, 19].
Another signiﬁcant issue for video annotation retrieval is a wayof representing temporal dynamics of videos. Two typical approaches exist: 1) representing a video as a set of keyframes andreplacing the problem into image annotation retrieval, and 2) representing a video as a statistical model that assumes some Markov
properties, such as a state space model and a hidden Markov model(HMM). Although the former approach makes the problem simple, any types of temporal information have been removed, which
would be quite signiﬁcant to capture a video concept composed ofa sequence of visual scenes. Meanwhile, the latter approach might
be redundant since a shot includes so many video frames similar toeach other. Keyframe extraction would be important to obtain a concise representation of shots. Previously, layered dynamic mixture
model [20] using hierarchical hidden Markov model (HHMM) arepresented. However, they needs considerable computational cost formodel parameter estimation and inference.
To this end, we propose a new statistical model which incorporates 1) co-occurrences among visual information and text information and 2) temporal dynamics of videos simultaneously. The
proposed model shown in Figure 2 is composed of keyframe-wise
topic models and a hidden Markov model connecting topic models
smoothly. From this viewpoint, we call the proposed model as ahierarchical topic trajectory model (HTTM).
2. HIERARCHICAL TOPIC TRAJECTORY MODEL2.1. Framework
Our proposed model consists of four layers: (a) time-series data,such as video frames, text labels and audio signals, (b) features extracted from data, (c) latent variables and (d) state variables .
Figure 2 overviews our proposed model, HTTM. The bottom

ICASSP 2011

&RQFHSWRQV;ĂͿ

6FHQHIHDWXUHV
6FHQH IHDWXUHV



;ďͿ


,QVWDQFHIHDWXUHV



;ĐͿ





;;ĚͿͿ

9LGHRIUDPHV

7H[W
ODEHOV

2WKHUPRGDOVFDQEHDGGLWLRQDOO\LQFOXGHG 

Fig. 2. Overview of proposed model (HTTM). Direct dependencies
of values are showed with arrow lines.
layer corresponds to observations namely video frames vx and text
labels wt . The second layer from the bottom corresponds to features
xt , y t extracted from the observations. The third layer from the bottom corresponds to latent variables z t representing the relationshipbetween video and audio features. The top layer consists of hidden
state series st , which outputs the latent variables.
HTTM can be formulated by the following joint probability density function (PDF):
T
Y
p(st |st−1 )p(zt |st )p(xt |zt )p(yt |zt )p(X, Y, Z, S) =t=1

, where X = {x1 , x2 , ..., xT } (Y, Z, S are all deﬁned similarly), T
is the number of keyframes in a given shot, and p(s1 |s0 ) = p(s1 ).
We will describe every component PDF in the following.
The feature vectors x and y are assumed to be independently
generated given the latent variable z from a normal distribution witha mean vector given by an afﬁne transformation of z: p(x|z) =N (x; Wx z + x̄, Ψx ) and p(y|z) = N (y; Wy z + ȳ, Ψy ), whereN (z; μ, Σ) denotes the multivariate normal distribution with mean
μ and covariance matrix Σ. A latent space provides a compact representation (topic model) reﬂecting cross-modal correlations. Thismodel can be easily extended to more than two types of feature vectors, which implies that our proposed model can deal with multiple
modals such as audios and geotags.
The latent variables z t (more precisely their conditional expectation) are modeled as the observations of an HMM with hidden
states st in layer (d). At each time t, a state variable st takes values from a ﬁnite set {1, . . . , K}. We deﬁne a transition probabilityp(st = j|st−1 = i) from a state st−1 = i at time t to a state st = j
at time t as pij . The output probability distributions of the states
are modeled using a Gaussian mixture model (GMM) as describedby the equation below:
PLk(1)p(z t |st = k) =j=1 πk,j p(z t |j, st = k),p(z t |j, st = k) = N (z t ; z̄ k,j , Σk,j ),where Lk is the number of Gaussians and z̄ k,j , Σk,j , πk,j are themean vector, the covariance matrix and the mixture weight of thej-th component of state k. For simplicity, we assume the number ofGaussians to be common between states (Lk = L). This HMM enables us to control temporal dependency of topic models and varietyof feature vectors simultaneously.
2.2. Model training
In this framework, the parameter estimation method can be achievedby a combination of those of topic models and HMM. It consists

2381

Fig. 3. Procedure of parameter estimation for HTTM. θ z and θ s area set of parameters of topic models and HMM, respectively.
of ﬁve steps, shown in Fig. 3, i.e.: (1) extracting features from data,(2) estimation parameters for model parameters of topic models, (3)extracting latent variables, (4) temporal clustering of scene features
via Viterbi search or forward-backward algorithm and (5) estimation
parameters for HMM.
Maximum-likelihood estimates for the parameters θ z ={Λ, A, B, x̄, ȳ, Cyy } of topic models can be obtained with the helpof probabilistic canonical correlation analysis (PCCA)[16]. The
mean values x̄, ȳ are simply calculated as the average of the training
data xt , y t . The estimation of the other parameters reduces to solving a generalized eigenvalue problem. Let dx and dy be the numberof dimensions of x and y respectively and let d (d ≤ min(dx , dy )) be the number of dimensions of the latent variable. By solving thefollowing generalized eigenvalue problems, we can obtain the top deigenvalues λi , (i = 1, 2, . . . d) in descending order and the d associated eigenvectors (ai , bi ) ∈ Rdx +dy :
«„
«
„
«„
«
„
a
Cxx
a
0
0
Cxy
=λ
,
Cyx
0
b
b
0
Cyy
where 0 denotes zero matrix and Cxx , Cyy , Cxy , Cyx denotes covariance matrices calculated from training data. We can deﬁne adiagonal matrix Λ = diag(λ1 , λ2 , . . . , λd ), and matrices A =(a1 , . . . , ad ) and B = (b1 , . . . , bd ). The conditional expectationof the latent variables z t are then obtained, respectively for the casewhere only the image feature x is given and that where both theimage feature x and the label feature y are given, as:1z(x) = Λ 2 A (x − x̄),“”
1z(x, y) = Λ 2 (I + Λ) A (x − x̄) + B  (y − ȳ) .

(2)
(3)

Parameters θ s = {{pij }, {z̄ k,j , Σk,j , πk,j }} for HMM can be
estimated from the latent variables z t . That is achieved by using
Baum-Welch algorithm [21], which is an iterative method for estimating parameters in two steps. At ﬁrst, model parameters are set
randomly.
• In the expectation step, the hidden state series st is estimatedstochastically, with Viterbi search or forward-backward algorithm.
• In the maximization step, model parameters θ s are estimatedconsidering state series estimated in the expectation step.
These two steps are repeated until the estimated parameters converge
or the iteration count reaches the predeﬁned maximum.
2.3. Recognition (Estimation of lacking features)
Recognition can be considered as estimation of label features fromvideo features only. It consists of six steps, shown in Fig. 4, i.e.: (1)extract features from data, (2) estimate latent variables, (3) estimate



Ϭ͘Ϭϳϴ
Ϭ͘Ϭϳϲ
Ϭ͘Ϭϳϰ
Ϭ Ϭϳϰ
Ϭ͘ϬϳϮ
Ϭ͘Ϭϳ
Ϭ͘Ϭϲϴ
Ϭ͘Ϭϲϲ
Ϭ Ϭϲϲ
Ϭ͘Ϭϲϰ
Ϭ ϬϲϮ
Ϭ͘ϬϲϮ


Ϭ͘Ϭϵ
Ϭ Ϭϴ
Ϭ͘Ϭϴ
Ϭ͘Ϭϳ
ŵĞĂŶW
ŶW

Ϭ͘Ϭϲ



Ϭ͘Ϭϱ



Ϭ͘Ϭϰ
Ϭ Ϭϯ
Ϭ͘Ϭϯ
Ϭ͘ϬϮ
Ϭ
Ϭϭ
Ϭ͘Ϭϭ
Ϭ





(a)

ŝŵĂŐĞ
ĨĞĂƚƵƌĞŽŶůǇƐϱͺŵϱϬ

(b)

Fig. 5. Recognition results. (a) Proposed model outperforms themodel without state estimation. (b) Label feature {0, idf(l)} performs best. (“sns mnm ” means K = nx , L = nm )Fig. 4. Procedure of recognition using HTTM.

state variables, (4) re-estimate latent variables considering instancefeatures and state variables, (5) estimate label features, (6) output
recognition result considering estimated label features. Our main
contribution in this stage is the fourth step, considering not only observations but also temporal dependencies to estimate latent variables. Re-estimation considering state variables, which represents
temporal dependencies, would improve estimation accuracy.
Image features xt are extracted from the images of the given
video. Latent variables z̃ t are estimated with the extracted image features xt by Eq. (2), considering the model parameter set θ zlearned in Sec. 2.2. Hidden state series Ŝ = {ŝ1 , ŝ2 , . . . , ŝt , . . .}are estimated from the estimated latent variable series Z̃ ={z̃ 1 , z̃ 2 , . . . , z̃ t , . . .}, considering the model parameter set θ s by
Viterbi decoding:QŜ ≈ argmax p(z̃ 1 |s1 )p(s1 ) Tt=2 p(z̃ t |st )p(st |st−1 ),S

where T is the size of series (the number of images used) andp(st |st−1 ) is transition probability1 .
Latent variables ẑ t are re-estimated by considering estimatedhidden states Ŝ and instance features xt . At each time t, the hidden
state st gives a distribution dependent of latent variable z t as described above. Using this information, estimation accuracy for latentvariable z t can be improved. Given a state variable st = k, the distribution of latent variable z t can be described by GMM with parameters z̄ k,j , Σk,j , πk,j (j = 1, 2, . . . , L) for mean vectors, covariancematrices, mixture weights. ẑ t are calculated by below equation:
Pẑ t = L
j=1 π̃j z̄ k,j ,where π̃i are given by:
πk,j N (z̃ t ; z̄ k,j , Σk,j )π̃j = PL.
l=1 πk,l N (z̃ t ; z̄ k,l , Σk,l )A label feature ŷ t can be estimated with re-estimated latent variables ẑ t . That is archived in the framework of PCCA:(4)ŷ t = y(ẑ t ) = Wy ẑ t + ȳ
1where Wy is given by Wy = Cyy BΛ 2 .
Labels are estimated or annotated from estimated label featuresŷ t . We use ranked output of image for each label i.e. ﬁx a label andrank images in a high likelihood order.
3. EXPERIMENTS
3.1. Experimental Conditions
1 Hidden state series Ŝ can be also estimated stochastically using forwardbackward algorithm for Viterbi decoding.

2382

We conducted experiments with TRECVID [3] 2005 data including
127 videos and 56191 shots. We divide them into two data, one isfor training, containing 102 videos, 45689 shots, the other is for testing, containing 25 videos, 10502 shots. Bag of Features (BoF) with
SIFT local descriptors provided by vireo374 [22] were used as image features. We chose 47 labels2 from LSCOM-Lite and LSCOM
annotation [23, 24] and remove shots without any of 47 labels. We
adopted the following 3 alternatives and test 8 = 23 methods toextract label feature:• Label features with zero and positive values such as {0, 1},or negative and positive values{−1, 1}.
• Weighting label features with tf-idf or not.
• Use latent semantic analysis (LSA) to extract correlations
among labels, or not.
The number of dimensions d of latent variables was set to 47. In
GMM we used diagonal covariance matrices.
We used mean average precision (meanAP), namely the meanvalue of average precision values over all the labels. Average precision is deﬁned by follow equation:
1 PN
rk pk ,
AP =R k=1
where rk takes the value rk = 1 if the k-th output is true, otherwise
0, N is the number of annotated samples, R takes the value
rk =P
R= N
k=1 rk , and pk denotes the precision value when considering
the 1-st through k-th outputs as all the results. If a system outputs
randomly, the precision takes values equal to chance level at eachrank and average precision also takes chance level. For the l-th label,values of the l-th dimension of ŷ t s are compared and the output are
the indexes in descending order.
3.2. Results
We conducted two experiments to verify the effectiveness of the proposed method for automatic video annotation and to analyze relationships between model parameters and annotation accuracy. In
the experiment (a), 8 types of methods for label feature extraction
were compared on the basis of meanAP. In the experiment (b), we
chose the best label features and evaluated the relationship between
the annotation accuracy and the number of states K and mixtures L(KL = 240, described below).
2 Used labels are:Airplane, Airplane Flying, Animal, Boat Ship,
Building, Bus, Car, Charts, Cityscape, Classroom, Computer TV-screen,
Corporate-Leader, Court, Crowd, Demonstration Or Protest, Desert, Entertainment, Explosion Fire, Face, Flag-US, Government-Leader, Hand, Maps,
Meeting, Military, Mountain, Natural-Disaster, Nighttime, Ofﬁce, Outdoor, People-Marching, Person, Police Security, Prisoner, Road, Singing,
Sky, Snow, Sports, Studio, Telephones, Truck, Urban, Vegetation, Walking Running, Waterscape Waterfront, Weather.

Ϭ͘ϬϭϮ
Ϭ͘ϬϰϱĐŚĂŶĐĞ

Ϭ͘ϬϭŝŵĂŐĞ
ĨĞĂƚƵƌĞ ŽŶůǇĨĞĂƚƵƌĞŽŶůǇƐϭͺŵϮϰϬϬ͘ϬϬϴƐϮ ŵϭϮϬƐϮͺŵϭϮϬ

Ϭ͘ϬϬϲĂǀĞƌĂŐĞƉƌĞĐŝƐŝŽŶ
ƌĂŐĞƉƌĞĐŝƐŝŽŶ
ƌĞĐŝƐŝŽŶ
Ŷ

Ϭ͘Ϭϰ
Ϭ͘Ϭϯϱ
Ϭ͘Ϭϯ

Ϭ͘ϬϮϱ
Ϭ͘ϬϮ

ƐϯͺŵϴϬ

Ϭ͘ϬϬϰ

Ϭ͘Ϭϭϱ

ƐϰͺŵϲϬ

Ϭ͘Ϭϭ

Ϭ͘ϬϬϮ

ƐϱͺŵϰϴϬ͘ϬϬϱϬϬŝƌƉůĂŶĞ

(a)ŝƌƉůĂŶĞͺ&ůǇŝŶŐ

(b)

ƵƐ

DŝůŝƚĂƌǇ

Fig. 6. Results of labels: Airplane, Airplane Flying, Bus and Military.
Figure 5 (a) shows the meanAP obtained from the framewise
topic model (left) and the proposed method, HTTM, with the ﬁxed
number of states K = 5 and mixtures L = 50 (right). This ﬁgure
indicates that our proposed model considering temporal dependency
outperformed a set of topic models without considering temporaldependency.
Figure 5 (b) shows the meanAP of 8 different methods for label
feature extraction. This ﬁgure indicates that the label feature expressed with zero or positive value and tf-idf weighting, performedbest.
In the experiment (b), we ﬁxed the number of states K and mixures L satisfying KL = 240 because K = 5 and L = 50 performed
best in experiment (a) and 240 has many divisors around 250. Theremight be some trade-offs between the number of hidden states andmixtures. Many hidden states and a few mixtures would emphasize
temporal structures of videos, while the opposite case would pay attention to the current frame features more.
Figure 6 shows the results of two labels each. Figure 6 (a) showsthat both Airplane and Airplane Flying performed best with K =4, L = 60. This suggests that correlation information was accurately
used in model learning with that condition. Figure 6 (b) indicatesthe results of Bus and Military. This shows that sometimes HMMs
performed worse than considering only image features. One possible
reason is that GMMs does not match to very small chance levels
those may considered as outliers.
4. CONCLUDING REMARKS
We proposed a new statistical model, Hierarchical Topic Trajectory
Model (HTTM), for acquiring a dynamically changing topic modelthat represents the relationship between video frames and associatedtext labels. Label features with zero or tf-idf values performs best.
The recognition results revealed some relationships among the number of states, the number of GMM mixtures and annotation accuracy.
Our future work includes some comparison with other video
recognition methods and automatic determination extension to estimate the number of states or mixtures.
5. ACKNOWLEDGMENTS
The authors thank Dr. Naonori Ueda, Dr. Eisaku Maeda, Dr. Futoshi
Naya and Dr. Junji Yamato of NTT Communication Science Laboratories for their help.
6. REFERENCES[1] J. S. Downie, “The music information retrieval evaluation exchange(2005–2007): A window into music information retrieval research,”
Acoustical Science and Technology, vol. 29, no. 4, pp. 247–255, 2008.

2383[2] K. Kashino, T. Kurozumi, and H. Murase, “A quick search method
for audio and video signals based on histogram pruning,” IEEE Trans.
MM, vol. 5, no. 3, pp. 348–357, 2003.
[3] A. F. Smeaton, P. Over, and W. Kraaij, “Evaluation campaigns and
TRECVid,” in Proc. MIR, pp. 321–330, 2006.
[4] S. Lazebnik, C. Schmid, and J. Ponce, “Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories,” inProc. CVPR, pp. 2169–2178, October 2006.
[5] K. Grauman and T. Darrell, “The pyramid match kernel: Efﬁcientlearning with sets of features,” Journal of Machine Learning Research,
vol. 8, pp. 725–760, April 2007.
[6] G. Carneiro, A. Chan, P. Moreno, and N. Vasconcelos, “Supervised
learning of semantic classes for image annotation and retrieval,” IEEE
Trans. PAMI, vol. 29, pp. 394–410, March 2007.
[7] G. Wang and D. Forsyth, “Joint learning of visual attributes, object
classes and visual saliency,” in Proc. ICCV, pp. 537 –544, sep 2009.
[8] T. Hastie, R. Tibshirani, and J. Friedman, The elements of statisticallearning: Data mining, inference, and prediction. Springer, February
2009.
[9] T. Hofmann, “Unsupervised learning by probabilistic latent semantic
analysis,” Mach. Learn., vol. 42, no. 1-2, pp. 177–196, 2001.
[10] D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent dirichlet allocation,” J.
Mach. Learn. Res., vol. 3, pp. 993–1022, January 2003.
[11] K. Barnard, P. Duygulu, D. Forsyth, N. de Freitas, D. M. Blei, and M. I.
Jordan, “Matching words and pictures,” J. Mach. Learn. Res., vol. 3,
pp. 1107–1135, 2003.
[12] J. Sivic, B. C. Russell, A. A. Efros, A. Zisserman, and W. T. Freeman,“Discovering objects and their location in images,” in Proc. ICCV,
vol. 1, pp. 370–377, 2005.
[13] L. Fei-Fei and P. Perona, “A Bayesian hierarchical model for learning
natural scene categories,” in Proc. CVPR, vol. 2, pp. 524 – 531 vol. 2,
jun 2005.
[14] F. Monay and D. Gatica-Perez, “Modeling semantic aspects for crossmedia image indexing,” IEEE Trans. PAMI, vol. 29, pp. 1802–1817,
August 2007.
[15] H. Hotelling, “Analysis of a complex of statistical variables into principal components,” Journal of Educational Psychology, vol. 24, 1933.
[16] F. R. Bach and M. I. Jordan, “A probabilistic interpretation of canonicalcorrelation analysis,” Technical Report 688, Department of Statistics,
University of California, Berkeley, 2005.
[17] C. Wang, “Variational bayesian approach to canonical correlation analysis,” IEEE Trans. NN, vol. 18, no. 3, pp. 905 –910, 2007.
[18] T. Bailloeul, C. Zhu, and Y. Xu, “Automatic image tagging as a random
walk with priors on the canonical correlation subspace,” in Proc. MIR,
pp. 75–82, 2008.
[19] T. Harada, H. Nakayama, and Y. Kuniyoshi, “Image annotation andretrieval based on efﬁcient learning of contextual latent space,” in Proc.
ICME, pp. 858–861, August 2009.
[20] L. Xie, L. Kennedy, S.-F. Chang, A. Divakaran, H. Sun, and C.-Y.
Lin, “Layered dynamic mixture model for pattern discovery in asynchronous multi-modal streams,” in Proc. ICASSP, vol. 2, pp. 1053–
1056, mar. 2005.
[21] L. E. Baum and T. Petrie, “Statistical inference for probabilistic functions of ﬁnite state Markov chains,” The Annals of Mathematical Statistics, vol. 37, no. 6, pp. 1554–1563, 1966.
[22] Y.-G. Jiang, C.-W. Ngo, and J. Yang, “Towards optimal bag-of-features
for object categorization and semantic video retrieval,” Proc. CIVR,
2007.
[23] M. R. Naphade, L. Kennedy, J. R. Kender, S.-F. Chang, J. R. Smith,
P. Over, and A. Hauptmann, “A light scale concept ontology for multimedia understanding for trecvid 2005,” IBM Research Technical Report, 2005.
[24] M. Naphade, J. R. Smith, J. Tesic, S. F. Chang, W. Hsu, L. Kennedy,
A. Hauptmann, and J. Curtis, “Large-scale concept ontology for multimedia,” in IEEE Trans. MM, vol. 13, pp. 86–91, 2006.