The 16th Meeting on Image Recognition and Understanding

VisualTextualRank: A Video Shot Ranking Method
Using Visual Similarity and Tag Co-occurrence
Do Hang Nga1,a)1.

Introduction and Objective

The explosive growth of video sharing websites makes it
easier for researchers of action recognition field to constructaction shot database. However, video shot retrieval for specific actions still encounters many difficulties including computation cost, noise, diversity of keywords as well as humanactions and so on. Here, a video shot is a part of a video
which refers to a set of consecutive frames representing aspecific scene.
In case of image retrieval, the popular Google Image
search engine adopts a ranking method called VisualRank [1]which exploits the visual link structure between images. According to VisualRank, images found to share the most visual characteristics with the group at large shall be determined as the most relevant ones and ranked to the top of
search results. VisualRank can also be applied to video shotranking as in [3], [4].
Howerver, in case of human actions, since they are too
diverse, their corresponding video shots are not always visually similar even they are semantically related. The change
in camera view or the way how people perform the action
may cause visual differences. Our intuition is that, two video
shots which belong to two videos tagged with related keywords may represent the same action even if they do nothold the same visual features (See Fig.1).

Keiji YANAI1,b)

method, VisualTextualRank, which extends VisualRank [1]. Our method is based on random walk over bipartite graph to integrate visual information of video shotsand tag information of Web videos effectively. Note thatinstead of treating the textual information as an additionalfeature for shot ranking, we explore the mutual reinforcement between shots and textual information of their corresponding videos to improve shot ranking.

2.

Proposed Method

The basic idea of VisualTextualRank (abbreviated asVTR) is that, the relevant tags are used to annotate relevant videos; the relevant video shots are from videos annotated with relevant tags and visually similar to each other.
Thus VTR co-ranks tags and video shots so that at eachiterative ranking step, ranks of shots are refined using theirvisual similarities as well as their relevance with corresponding tags, and then, ranks of tags are updated based on theirrelevance with video shots in conjunction with refined ranking positions of video shots.
VTR is an extension of VisualRank [1] with idea inspiredby [2]. In [2], tags and videos are also co-ranked using theircorrelation to refine their relevance with specific topic. However, unlike our work, in [2], relevance of the whole video, notevery scene in it, is evaluated and visual features of videos
are totally ignored. On the other hand, VisualRank exploits
only a visual linkage between images and does not take textual information into account. Our proposed VTR employs
both visual and textual features of Web videos to explore
the mutual reinforcement across video shots and tags.
The proposed co-ranking method can be represented byfollowing iterative processes:
RSk = α × SM ∗ × SC ∗ × RTk + (1 − α) pFig. 1An example of two video shots with tag lists of their videos
which are retrieved by YouTube with “blow candle” keyword. Since some relevant words such as “birthday” and“cake” are tagged to both videos, we can presume thatthese two video shots are semantically related to eachother and relevant to “blow candle” even though they are
not visually similar.

In this paper, we propose a novel ranking
1a)b)Faculty of Informatics,
The University ofCommunications, Chofugaoka 1–5–1, Chofu-shi,
182–8585 Japandohang@mm.cs.uec.ac.jp
yanai@cs.uec.co.jp

EletroTokyo,′ ∗RTk+1 = (SC ) × RSk

(1)
(2)

RS and RT are vectors which represent rank positions ofshots and tags, respectively. Let the number of shots be
ns and the number of tags be nt , the dimension of RS will
be ns × 1 and the dimension of RT will be nt × 1. SMrefers to shot-shot similarity matrix where SMi,j means visual similarity score between shot i and shot j; SM ∗ is its
column-normalized matrix with size as ns × ns . SC represents shot-tag similarity matrix where SCi, k measures
textual relevance score between the video of shot i and tag1The 16th Meeting on Image Recognition and Understanding

Table 1 Experimental results. VR and VTR refer to perfork; SC ∗ is its ns × nt column-normalized matrix. SC ′ refers
mance of video shot retrieval system adopting Visualto the transposed matrix of SC which represents tag-shot
Rank and proposed VisualTextualRank respectively.
similarity matrix and SC ′∗ is its column-normalized maAction
VR VTRAction
VR VTR
ActionVR VTR
climb+tree
24 24
100 100
play+drum
40 45
trix. RT is initially defined as a uniform vector. Following soccer+dribble
ride+horse24 15
fold+origami
96 99
skate
37 42
roll+makizushi
24 36
crochet+hat
95 97
swim+crawl
36 49
VisualRank, we also introduce damping factor α and damp- arrange+flower 94 96
sew+button
24 46
cut+hair
35 42
fry+tempura
23 12
paint+picture
88 87
run+marathon
35 43
ing vector p into shot ranking. Damping factor α has been
slap+face
20 45
boxing86 84
count+money
33 58
read+book
19 21
jump+parachute 82 63
paint+wall
33 32
found empirically as holding minor impact on global order- jump+trampoline
squat
19 34
82 92shoot+football
33 29
row+dumbell
16 30
do+exercise
79 61
ing in ranking results. Damping vector p can be a uniform do+aerobics 78 79 draw+eyebrows 32 32 wash+clothes 15 29
fieldhockey+dribble 32 68
wash+dishes
15 39
do+yoga
77 70
hit+golfball
32 70
vector or a nonuniform vector.
comb+hair
14 26
surf+wave
75 73

3.

Experiments

3.1 Implementation Details and Dataset
We chose the system of automatically extracting fromtagged Web videos video shots corresponding to specific actions proposed in [3] to validate our ranking method since
it provides a large-scale shot database which is suitable forour purpose and it is easy to implement. The system in [3]consists of two main steps: video ranking and shot ranking. At the shot ranking step, they apply VisualRank torank shots from top ranked videos. We adopt our method
to this step and compare the performance of their systemwith VisualRank and with our ranking method.
To calculate ranking positions of shots in VisualTextualRank, we must construct shot-shot similarity matrix SMand shot-tag similarity matrix SC as shown in Eq.1. As
for the calculation of SM , we use the same method as described in [3]. Relevance of a video to a tag is measured in
the similar way as represented in [3] using the tag database
constructed in advance. Note that here shots are obtainedby segmenting selected videos but filtered by their lengthand tags are tags of selected videos but filtered based on
their occurrence frequencies. Following [3], we select only
shots which last longer than one second and shorter than
one minute. To avoid using personal and subjective tags,we choose tags which appear at least five times over selectedvideos.
Damping factor α is chosen as 0.8 for practice. Damping
vector is defined following the best results obtained in [3].
That means damping vector is defined by giving uniform
bias values to the elements corresponding to the top k shots
regarding tag relevance of their videos to the keyword. kequals 1000 in practice.
We conduct experiments with the human action databaseof [3]. This database consists of 100 action categories. Eachcategory has 2000 video shots on average. Precision is defined as the percentage of relevant video shots in the top
ranked 100 shots (Prec@100).
3.2 Experimental Results
Experimental results are shown in Table 1. We consider
action with precision higher than 40% as “succeeded action”,action with precision lower than or equal to 40% but higher
than 25% as “acceptable action” and the remain as “failedaction”. The results reported in [3] are: 34 succeeded, 33
acceptable, 34 failed.
Experimental results demonstrate that by adopt-shoot+arrow
73 81
massage+leg
72 78
fix+tire
67 77
batting
66 61basketball+dribble 64 87
blow-dry+hair
64 59
knit+sweater
64 68
ride+bicycle
62 70
curl+bicep
58 59
shoot+ball
58 58
tie+shoelace
57 73
laugh50 54
dive+sea
49 41
harvest+rice
49 46
ski
49 60
iron+clothes
47 48
twist+crunch
47 32
dance+flamenco
45 53
dance+hiphop
43 68
eat+ramen
42 47
dance+tango
41 41
play+trumpet
41 59
AVG. (1-34)
65.9 68.3

lunge
play+pianorow+boatsing
chat+friend
clean+floor
cut+onion
shave+mustache
pick+lockplaster+wall
blow+candle
wash+facewalking+street
brush+teeth
catch+fishdrive+car
plant+flower
play+guitar
lift+weightraise+leg
hang+wallpaper
jump+rope
AVG. (35-67)

32 27
drink+coffee
14 16
32 34
swim+breaststroke 13 18
32 23
cry
12 12
32 65
eat+sushi
12 23
31 52
serve+teniss
11 27
31 38
tie+necktie
11 28
31 24
boil+egg911
31 30
head+ball916
30 28
swim+backstroke
9930 55
take+medicine
8
7
29 44
serve+volleyball
740
29 24
swim+butterfly
7
9
29 46
bake+bread
6
8
28 27
cook+rice
61128 59
grill+fish
51328 40
jog
56
28 24
slice+apple
51628 41peel+apple
51427 51
bowl+ball4427 40smile4626 46kiss
2326 49
AVG. (68-100) 12.2 19.8
31.0 41.7
AVG. (ALL)
36.6 43.5

ing our proposed ranking method, more relevant shots
are brought to the top.
In terms of overall performance, VTR improves the average precision by approximately 7%. Especially, precision is boosted greatly incases such as “hit+golfball”, “dance+hiphop”, “plaster+wall”, “blow+candle”, “jump+rope”, “catch+fish”,“play+guitar”, “wash+dishes”, “slap+face”. The acceptable group is the most significantly improved. By applying
proposed VTR, the number of succeeded actions increases
from 34 to 51 and the number of failed ones decrease from34 to 23.

4.

Conclusion

In this paper, we propose a novel graph based ranking
method, VisualTextualRank, which performs co-ranking ofvideo shots and tags employing both visual links between
video shots along with textual links between videos and theirtags. We apply VTR to the system of extracting automatically relevant video shots for specific human actions. The
effectiveness of proposed VTR was validated by experimental results.
References
[1]

[2]

[3]
[4]

Jing, Y. and Baluja, S.: VisualRank: Applying PageRankto Large-Scale Image Search, IEEE Transactions on PatternAnalysis and Machine Intelligence, Vol. 30, No. 11, pp. 1870–
1890 (2008).
Liu, L., Sun, L., Rui, Y., Shi, Y. and Yang, S.: Web video
topic discovery and tracking via bipartite graph reinforcement model, Proc. of the ACM International World Wide
Web Conference, pp. 1009–1018 (2008).
Nga, D. H. and Yanai, K.: Automatic Construction of an Action Video Shot Database using Web Videos, Proc. of IEEE
International Conference on Computer Vision (2011).
Nga, D. H. and Yanai, K.: Automatic Collection of Web Video
Shots Corresponding to Specific Actions using Web Images,
Proc. of CVPR Workshop on Large-Scale Video Search andMining (LSVSM) (2012).

2