Analyzing the similarities of actions based on video clustering
Vu Gia Truong

Do Hang Nga

Keiji Yanai

The University of Electro-Communications, Tokyo{vugia,dohang,yanai}@mm.inf.uec.ac.jp

Abstract

1.2. Research purpose
The main purpose of this research is to analyze visual
similarities between verbs. It is equal to ﬁnding several
pairs of verbs which are visually similar from a collectionof verbs. A verb represents an action which can be deﬁned
as a group of continuous smaller sub-actions. So similarity
between a pair of verbs can be evaluated as the ratio of subaction which both of them share to the sum of sub-actionsof verbs pairs.
For example, a pair of visually similar verbs are“type+keyboard” and “play+piano”. The main sub-actionof the verb “type+keyboard” is “hand move up anddown continuously”, and the main sub-action of the verb
“play+piano” is also “hand move up and down continuously”. The ratio of the same sub-action is high so they
can be considered as similar.
In contrary, a pair of visually dissimilar verbs is“push+up” and “play+daf”. The main sub-action of the verb
“push+up” is “body move up and down continuously”andthe main sub-action of the verb “play+daf” is “hand movearound continuously”. The ratio of the same sub-action is
low so they can be considered as dissimilar.
Because each verb is represented by a set of attribution
vectors, the ratio of overlapped sub-actions between a pairof verbs corresponds to simlarity between these representative sets.

In this paper, we propose a novel approach to represent
a verb as a set of attribution vectors. Similarities between
verbs are deﬁned as distances between their representative
attribution vectors sets. By ranking distances between these
sets, several pairs of verbs which are visually similar arefound from a collection of verbs.
We then use dendrogram to illustrate the similarities between verbs pairs. Each verb is drawn as a leaf node ina dendrogram. By counting number of nodes between leaf
nodes and height of connected branches, similarities can beeasily estimated.

1. Introduction
1.1. Background
Analyzing visual similarity between nouns and adjectives has been conducted by Kohara et al. [5]. But analyzing visual similarities between verbs has not been conducted so far. There are two difﬁculties that researchers
must face to conduct such analysis. The ﬁrst is “how torepresent verb” and the second is “how to collect enoughdata for several different verbs”.
To overcome the ﬁrst difﬁculty, we propose a novel approach to represent a verb as a set of attribution vectors.
These attribution vectors are obtained from clustered representative Bag-of-spatio-temporal feature vectors of verb.
We evaluate the effectiveness of our method by applying it
to UCF-101 data set [7]. This dataset contains 101 different
verbs and 13320 video shots which are mined from internet.

2. Related work
Video recognition is one of common tasks in computer
vision. The goal of this task is to automatically detecting
actions in a given video sequence. The main approach isrepresenting video as ﬁxed-size vectors and using classiﬁer
to decide which class this video belongs to. According to
the approach, at ﬁrst feature descriptors are extracted fromvideos. Several types of features have been proposed. According to Jiang et al. [3], they can be classiﬁed into three
categories as follows: 1) frame-based appearance features,2) spatio-temporal visual features, and 3) acoustic features.
Frame-based appearance features are extracted from frames

To overcome the second difﬁculty, we used UCF-101
data set [7] contains 101 different actions. As an alternative way, we can use an automatic dataset construct system
proposed by Nga et al. [1]. However, the results of thesystem still contains irrelevant video shots which should be
excluded in order to use them as video shots corresponding
to a speciﬁc “verb”, because they are not perfect.
13.2. Preparing datasetof videos separately. This approach ignores the changeof actions through time. In contrary to frame-based appearance features, spatio-temporal visual features consider
the change of actions through time. This capability makespatio-temporal visual features became most popular approach. Some example of spatio-temporal visual features
are: HOG-3D [4], SURF-based spatio-temporal feature [6].
The third is acoustic features which are extracted from audio of video shots.
The number of local feature descriptors extracted fromeach video is different. Feature descriptors of each video
need to be encoded into a ﬁxed-size vector for later classiﬁcation. The most popular encoding method is Bag-ofFeatures (BoF). BoF model learns a codebook ofﬂine byclustering a large set of descriptors with k-means and thenassigns each descriptor of the video the closest entry in thecodebook.
After representing video as a ﬁxed-size vector, a pretrained classiﬁer is used to decide which action a video belongs to. Because of simplicity and high accuracy SVM
has been used broadly. From these decisions, we are unable
to understand the relationships between actions themselves
which are critical in video retrieval techniques.
Instead of classifying actions, our approach focuses on
calculation of similarities between actions which allows us
to further study relationships between verbs in which actions are described. Because of the complexity of actions,each verb which describes action needs a lot of video shots
to be represented sufﬁciently. Also a large number of verbs
is required to make this study deeper.

As a dataset containing various kinds of actions, we use
the UCF-101 dataset which were created by hand. The actions included in this dataset can be divided into the following ﬁve categories: 1) Human-Object Interaction, 2) BodyMotion, 3) Human-Human Interaction, 4) Playing MusicalInstrument, 5) Sports. Figure 1 shows the thumbnails of allaction categories in the dataset.
By using the automatic Web video shot collecting system proposed by Nga et al.[1], we can obtain a large-scaleaction shots dataset automatically. However, the dataset automatically constructed may contain irrelevant video shots
which must be removed manually. The noise removal process is extremely time-consuming since the scale of the datais too large.

3. Method
Figure 1. Thumbnails of all action categories in the dataset.

3.1. Overview
Our method can be summarized as three steps as follows:

3.3. Extracting Bag-of-spatio-temporal vectors

1. Preparing dataset Each verb in the dataset is represented by hundreds of video shots which correspondto the action.

A video shot can be seen as a set of frames which arecontinuously connected along the time axis. The changeof feature point position through time contains rich information related to actions the video shot represents. Thesechanges can be converted into spatio-temporal features. We
use Noguchi et al.’s approach [6] to extract spatio-temporalfeatures from video shot.
Figure 2 illustrate the detailed ﬂow of their method. Thisapproach can be summarized as 4 steps below.

2. Extracting bag-of-spatio-temporal vectors
Each video shot is represented by extracted Bag-ofSpatio-Temporal Feature (BOSTF) vector.
3. Extracting attribution vectors
By clustering all of bag-of-spatio-temporal vectors, attribution vectors are obtained. Each verb is now considered as a set of attribution vectors.

(a) Extract visual feature(b) Decide spatio-temporal feature points

4. Similarities evaluation(c) Extract motion features

Similarities between verbs are obtained by ranking distances for each pair of attribution vectors set.

(d) Convert into vector descriptors
2

Table 1. An example of clustering result

verb
video shot A
video shot B
video shot C

1
40%
30%
10%

2
30%
20%
40%

3
20%
10%
30%

4
10%
40%
20%

Table 2. An example of attribution vectors

video shot A= (0.4, 0.3, 0.2, 0.1)
video shot B= (0.3, 0.2, 0.1, 0.4)
video shot C= (0.1, 0.4, 0.3, 0.2)

Figure 2. The processing ﬂow of extracting spatio-temporal features

3.5. Similarity evaluation

For each video shot, hundreds of spatio-temporal featuredescriptors are obtained. Then using Bag-of-Features approach where the dictionary size is 5000, one video shotis converted into a 5000 length size bag-of-spatio-temporalfeature (BOSTF) vector. Even though dictionary size isquite large, Bag-of-Features approach is incapable of fully
describing complexity of action. Because of this reason,
purely increasing size of dictionary does not come up witha better similarity evaluation result.
Actions themselves contain a lot of sub-actions. To
archive better similarity evaluation result, each video shot
should be split into smaller sub-actions which are simpler.
We validate effectiveness of this approach by simply slitting each video shot into 2 equal parts. Then we compare
the performance between using split video shots and entire
video shots.

After extracting attribution vectors, each verb is now represented as a set which contains hundreds of attribution vectors. To calculate distance between 2 sets, instead of Euclid
distance, Jensen-Shannon divergence is used.
Jensen-Shannon divergence formula for calculating distance between 2 distributions p and q is shown in Equation
1.
D JS (q||p) = DKL (q||(q + p)/2) + DKL (p||(q + p)/2)(1)

DKL is Kullback-Leibler divergence which describes thescale of difference between distribution f (x) and g(x).
Kullback-Leibler divergence’s formula is shown in Equation 2.
∫f (x)DKL ( f (x)||g(x)) =f (x) log
dx
(2)
g(x)

3.4. Extracting attribution vectors

The smaller distance between a pair of sets, the moresimilar their representative verbs are. We ﬁrst rank calculated distances to get top 20 most similar pairs of verbs.
Then we use dendrogram to illustrate similarities clearly.
Dendrogram is one type of tree diagrams often used toillustrate the arrangement of the clusters. Each cluster isdrawn as leaf node of dendrogram. Leaf nodes are connected to the others by several branches which are separated
by many nodes. Similarity between 2 clusters is deﬁned as“how low is the number of nodes between them” and “howlow is distance between 2 representative vectors sets whichis equal to height of connected branches”.
By considering each verb as a cluster, similarities between verbs can be illustrated vividly. A verb and its mostsimilar one are drawn as a pair of leaf nodes and they havethese following features: 1) There is only 1 node between
them, 2) Height of connected branches is low.

As deﬁned before, verb which describes action is composed from several continuous connected sub-actions. Similarity between a pair of verbs can be evaluated as the ratioof sub-actions which both of them share. For each pair ofverbs, their similarity can be simply calculated by calculating ratio between number of BOSTF vectors which bothof them share and sum of BOSTF vectors in this pair. But
this approach needs a dataset which has bigger video shots
count to archive acceptable similarity evaluation result.
To get a better similarity evaluation result, relationships
between each video shot and verbs need to be obtained.
These relationships are represented by attribution vectors
which are obtained by clustering all of BOSTF vectors. In
this paper, three clustering methods, K-means, pLSA, andAfﬁnity Propagation, are used. Experiment results showthat between these three clustering methods, pLSA is themost effective method.
An example of the calucation of attribution vector is asfollows: video shot of verb 1 are A, B, and C, the assignment rates for verb 1, 2, 3, and 4 are shown in Table 1, thenattribution vectors for video shot A, B, and C are obtained
as shown in Table 2

4. Experiments and Results
Effectiveness of our method is evaluated through two
experiments. Note that we show only results obtained by
pLSA, because the results by pLSA was the best among3

three clustering methods, K-means, pLSA, and Afﬁnity
Propagation.
In the ﬁrst experiment, BOSTF vectors are extracted
from entire video shots. In the second experiment, we split
each video shot into half along the time sequence and extract BOSTF vectors from split video shots. A pair of verbs
is considered as similar if their distance is smaller than 0.04
and there is only 1 node between their leaf nodes on thedendrogram.

Figure 4. Part of Dendrogram

Table 4 shows top 20 most similar verb pair. Comparing to the ﬁrst experiment’s results, distances between
verbs become smaller. Pairs of verbs which both do notchange direction through time get higher rank scores. For
example “ThrowDiscs” and “HammerThrow” is a pair ofverbs which do not change direction frequently throughtime. They go from 6th rank to second rank . In contrary,“HorseRiding” and “Rafting” is a pair of verbs which dochange direction frequently, They go from second rank to
14th rank.
Similar pair of verbs: “ThrowDiscs” and “HammerThrow” ’s creenshot is shown as Figure 5.
Low rank score pair of verbs: “HorseRiding” and “Rafting” ’s creenshot is shown as Figure 6.

4.1. Entire video shots
In this experiment, the top 3 most similar verb pairs
are: “Mixing” and “CuttingInKitchen”,“ShavingBeard”
and “Haircut”, “HorseRiding” and “Rafting’.
“ShavingBeard” and “Haircut” ’s screen shots are shownin Figure 3. Smallest distance between verb pairs is 0.0200.

Figure 3. “ShavingBeard”and“Haircut”’s screen shot

Table 3. Top 20 most similar verb pairs
Verb A
MixingRaftingShavingBeard
PizzaTossing
FrontCrawl
SoccerJuggling
ThrowDiscs
HeadMassage
PlayingDaf
HorseRiding
PlayingTabla
Haircut
ShavingBeard
FloorGymnastics
PlayingTabla
RopeClimbing
Kayaking
MixingHaircut
PommelHorse

Verb B
Verb’s distance Relative distanceCuttingInKitchen
0.0200
1.00
HorseRiding
0.0244
1.22
Haircut
0.0248
1.24
HeadMassage
0.0271
1.36
BreastStroke
0.02791.40
Nunchucks
0.0285
1.42
HammerThrow
0.0305
1.52
BlowingCandles
0.0306
1.53
Haircut
0.0308
1.54
Biking0.0319
1.59
PlayingGuitar
0.03191.60
BlowDryHair
0.0321
1.61
ApplyLipstick
0.0326
1.63
BalanceBeam
0.0326
1.63
PlayingCello0.0332
1.66
BabyCrawling
0.0333
1.66
HorseRiding
0.0333
1.67
BoxingSpeedBag
0.0335
1.67
BrushingTeeth
0.0336
1.68
HammerThrow
0.03391.69

Figure 5. “ThrowDiscs” and “HammerThrow”’s creenshot

Figure 6. “HorseRiding” and “Rafting”’s creenshot

Distance between pair of the verbs, “ShavingBeard” and“Haircut”, is 0.00197, which is smaller than the minimum
distance obtained in the ﬁrst experiment. As shown in Figure 7, they are connected by only one node.

Distance between the most similar pair of verbs: “Mixing” and “CuttingInKitchen” is 0.02. As shown in Figure 4
they are connected by only one node.

4.2. Split video shots
In this experiment, the top 3 most similar verb pairs
are: “Mixing” and “CuttingInKitchen”,“ShavingBeard”
and “Haircut”, “ThrowDiscs” and “HammerThrow”.

Figure 7. Part of Dendrogram4

Table 4. Top 20 most similar verb pairs
Verb A
MixingThrowDiscs
ShavingBeard
SoccerJuggling
ShavingBeard
Haircut
FrontCrawl
PlayingTabla
PlayingTabla
MilitaryParade
MoppingFloor
PizzaTossing
HorseRiding
Rafting
PlayingGuitar
Haircut
RopeClimbing
HeadMassage
ShavingBeard
PlayingDaf

Representing videos using mid-level discriminative
patches. In Proc. of IEEE Computer Vision and Pattern Recognition, pages 2571–2578, 2013.

Verb B
Verb pair’s distance Relative distanceCuttingInKitchen
0.01571.00
HammerThrow
0.0181
1.16
Haircut
0.0197
1.26
Nunchucks
0.0205
1.31
ApplyLipstick
0.0222
1.42
BrushingTeeth
0.0224
1.43
BreastStroke
0.0233
1.49
PlayingGuitar
0.0234
1.50
PlayingCello0.0238
1.53
BandMarching
0.0241
1.54
BabyCrawling
0.0245
1.56
HeadMassage
0.0245
1.56
Biking0.0246
1.57
HorseRiding
0.02501.60
ApplyLipstick
0.0253
1.61
BlowDryHair
0.02591.65
BabyCrawling
0.0262
1.67
BlowingCandles
0.0267
1.70
PlayingGuitar
0.02701.72
BlowDryHair
0.0271
1.73[3] Y. G. Jiang, S. Bhattacharya, S. F. Chang, and M. Shah.
High-level event recognition in unconstrained videos.
International Journal of Multimedia Information Retrieval, 2(2):73–101, 2013.
[4] A. Kläser, A. Marszałek, and C. Schmid. A spatiotemporal descriptor based on 3d-gradients. In Proc. of
British Machine Vision Conference, pages 995–1004,
2008.
[5] Y. Kohara and K. Yanai. Visual analysis on relations between nouns and adjectives using a large number of web
images. In Proc. of International Workshop on Modern
Science and Technology (IWMST), 2012.
[6] A. Noguchi and K. Yanai. A surf-based spatio-temporalfeature for feature-fusion-based action recognition. In
Proc. of ECCV WS on Human Motion: Understanding,Modeling, Capture and Animation, 2010.

5. Conclusions
In this paper, we propose a novel approach to represent
verbs as sets of attribution vectors. Calculating distances
between these sets allow us to evaluate similarities between
verbs. Even though this approach is simple, when it is applied to 101 different verbs dataset, we obtained an acceptable similarity evaluation result. Moreover, we discovered
dozens of visually similar verbs pairs.
To improve similarity evaluation result, keeping complexities of verbs is an important task. As deﬁned before,
action which is described by verb is structured from several
smaller sub-actions. Representative method should separate sub-actions and use them for representing. Sub-actionsof actions which do not change direction through time canbe ontained by simply split video shots into half. This led
to a small improvement in similarity evaluation result. But
because different sub-actions have different life span, thisapproach is unable to extract sub-actions for all of verbs.
A promising approach for separating actions into subactions is the method proposed by Jain et al. [2]. Theirmethod extracts representative parts from video shot of actions and uses these parts to construct BoF dictionary. By
using constructed BoF dictionary, each video shot is represented by a collections of representative sub-actions. We
plan to implement this method in our next work. We alsoplan to expand the dataset to 200 types of different verbs.

[7] K. Soomro, A. R. Zamir, and M. Shah. UCF101: A
dataset of 101 human actions classes from videos in thewild. arXiv preprint arXiv:1212.0402, 2012.

References[1] N. H. Do and K. Yanai. Automatic construction of anaction video shot database using web videos. In Proc. ofInternational Conference on Computer Vision (ICCV),
2011.
[2] A. Jain, A. Gupta, M. Rodriguez, and L. S. Davis.
5