DEIM Forum 2013 A10-3

Comparison of Different Semantic Negative Concepts Selection Methods
in SVM Classifier Training for Image Annotation
Shan-Bin Chan† Shin’ichi Satoh‡

andHayato Yamana†‡†School of Fundamental Science and Engineering, Waseda University 3–4–1 Okubo, Shinjuku-ku, Tokyo, 169–8555, Japan‡National Institute of Informatics 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan
E-mail:†{chrisjan, yamana}@yama.info.waseda.ac.jp,‡satoh@nii.ac.jp

Abstract When SVM is adopted for image annotation, most researchers randomly choose negative sample images forclassifier training. Adopting different negative sample image datasets will vary annotation accuracy. This research discusses
the accuracy and mean reciprocal rank (MRR) between different negative sample images selection methods. This research
adopted ImageNet dataset for positive and negative sample images, and implement SVM for classifiers training. Then we
adopted WordNet for building semantic hierarchical tree, and then propose six different negative sample images selection
methods. The results show that the accuracy of baseline method (random sampling) is 0.48 and the best proposed method is
0.51.
Keyword Negative Sample Selection, ImageNet, WordNet, SVM, Image Annotation, Machine Learning
selection methods. The chapter 4 will show the experiment

1. Introduction
SVM prediction is a very popular technique for image

results. And the final chapter will discuss the conclusions.

annotation. One-class SVM method is always adopted toannotate

images.

Researchers

preparepositive

and

2. Related Works

negative sample images for one-class SVM classifier

In order to efficient access to large image database,training. There are several methods for positive sample

content-based image annotation becomes popular research

image

topic

collection.

Researchers

can

use

pre-collected

recently.

The

feasibility

andeffectivenessofdatasets or gather positive sample images form image

automatic image annotation is also hot topic in computersearch engines. Some researchers also use the famous

vision research. Li et al. proposed a two-level hierarchicalonline album service such as Flickr or Picasa for positiveensemblesampleclassifiers and co-occurrence language model to annotate

imagescollection.

And

the

same

collection

methods are adopted for the negative sample images
collection.
The qualities of the positive sample images are

model

composedofprobabilistic

SVM

images automatically.[13]In the automatic image annotation process, Le et al. also
proposed approaches to incorporate lexical semantics into

important in SVM classifier training. That’s a given thatimage

better qualities of positive sample images will produce

semantics-constrained K-means clustering in combination

better SVM prediction accuracy. So that specialists selectwith hierarchical ensembles that can enhance the quality

the positive sample images for SVM classifier training.

of clustering to some degree and the hierarchical ensemble

But there are few studies discuss about the negative

annotation architecture, and also provide more accurate

sample images collection.

and consistent annotations.[13]In this study, we will discuss the accuracy and meanInannotation.

order

to

achieve

They

high

proposedannotationusing

accuracy,

reciprocal rank between different negative sample images

researchers adopted active learning for effective image

selection methods. A semantic hierarchical tree structure

annotation. They selected semantically ambiguous images

is built by using WordNet[5] for negative sample images

for users to label, and then used the user feedbacks to

selection. We adopted ImageNet[7] for the positive andretrain the image classifiers to improve the annotation

negative sample image collection. And One-class SVM isaccuracy.[6][10][11]employed for classifier training and prediction.
The chapter 2 will discuss the precious studies andrelated works. The chapter 3 will introduce our propose
methods for comparing different negative sample image

To label a image manually is laborious. WordNet isadopted by researchers to automatically enhance object
labels.[1]Image annotation by SVMs that simply employs one

low-level image feature is insufficient. Le et al. proposedin detail.

fusion of multi low-level image features for one-class
SVM classifier training and prediction.[3][4]3.1 Collect Concepts

There are very few studies discuss about the negative

We collect concepts from the photos on Flickr by using

sample images selection methods in one-class SVMs when

Flickr API. We employ the “flickr.photos.getRecent” API

implementing

researchers

to retrieve the recently uploaded photos randomly. We

randomly collected negative sample images for one-classonly retrieve the tags of recently uploaded photos and we

SVM

Although

use the POS (part-of-speech) application[14] to tag thetwo-class SVMs is also adopted for multiclass image

retrieved tags. And we store the image tags, counts, andannotation by some researchers. In this study, we will only

POS tags to MySQL database. We have already collecteddiscuss the one-class SVMs for image annotation.

176,303 concepts from July 2009 to July 2010. We will

image

classifier

annotation.

training

and

Most

prediction.

In this research, we adopted ImageNet as the image

only use the noun as the concepts for sample images

dataset, and adopted WordNet to automatically label

retrieval. Finally, the amounts of noun concepts are 6,838.

sampleimagesinto“positive”

and“negative”

forclassifier training. Finally, we propose six negative
sampleaccuracy

imagesselection

betweenmethods

different

andnegativecomparesample3.2 Build Semantic Hierarchical TreetheAfter the collection of concepts, we employ WordNet to

image

build a semantic hierarchical tree. Apart of semantic

datasets.

hierarchical tree is shown as Fig 2. In this semantichierarchical tree, we can understand the relationship anddistance between each concept.

3. Methods
Our approach is shown as Fig 1. And our research flow
is as the following steps:

Artifac t
Struc tu reCollect Concepts for Experiment

Building

Build Semantic Hierarchical Tree
Propose Six Negative Sample Images Selection
Methods

Hous

Theater

Car

Collect popular concepts from recently uploaded

3.3 Gather Sample Images
We use these noun concepts collected from Flickr as thephotos on Flickr.
semantic

Bik e

Fig 2. Apart of semantic hierarchical tree

Fig 1. Research Procedure

Build

VehicleWhee le d vehicle

Compare the Results•

Convey anceePrepare Positive and Negative Sample Images
for SVM Classifier Training and Prediction•

Instru mentality

hierarchical

tree

by

employingqueries and search the WordNet ID by using WordNet API.

WordNet.

And then we use the WordNet ID to gather the sample•

Select 100 concepts for experiment.

image URL list from ImageNet. Then we retrieve the•Retrieve sample images by employing ImageNet.

sample images from the sample image URL list. For each•

Propose six negative sample images selection methods

concept, we retrieve 2,000 images for maximum as sample

for the precision and accuracy comparison.

images. And we delete the sample image whose image size

For each pre-selected concept, prepare positive andis under 10Kbytes. We also skip the noun concepts if thenegative sample images for SVM classifier training.

number of their sample images is less than 50. Finally, theCompare the SVM predict results.

total number of collected noun concepts with sample

The following subsections will introduce our approach

images is 4,751. In this research we will only pick 100••

concepts from 4,751 noun concepts for experiment. The

adopting random sampling method. They randomly gather

pre-selected concepts are shown in Table 1.

the negative sample images from internet or datasets, andthen employ the SVM classifiers training. In this research,

Table 1. 100 pre-selected concepts
airplanebutterfly

Ant
Car

ape
cat

ducks

Eagle

elephant

fruit

gardenglowwormhorsejellyfish
lobby
newspaper

apple
cow
envelopes

ball
crane
equestrian

golf

ice
ice tea iceberg
cream
Key keyboard kitchen
motormango
maple
cycle
onion

orchidbikedolphinfabricfish

gorillahall

insectknife
mushroom
owls

bird
door
footballfor experiment. We totally collect 3,511,137 sample

heron

hook

SVM classifiers training.

jacketjasmine

jeans

lamps

leopardlion
narnarthex
cissusnails
palacepencil penguin

quesaresrabbit
rackdillastaurant
rocketshark
sheep
sky swallow temple
tiger
videotree
turtle umbrella unicycle utensil vessel
violintapes
yellow
volleyball whale window
wolf
worms
yam
yard
jacketzebra
ziggurat zinnia
zitherpeoplepineappleseaorangewe adopt random sampling method as the baseline method

beach
dog

quads

quahogimages from ImageNet, and randomly choose negative
sample images from these 3,511,137 sample images for3.4.2 Proposed Method 1
We choose fewer negative sample images for theconcepts, which are near to the positive concept. And wechoose more negative sample images for the concepts,
which are far from the positive concept. The relationshipbetween numbers of negative sample images and distanceis shown in Fig 4.
Numbers of negative sample images

3.4 Propose Negative Sample Images Selection Methods
In this research, we propose six negative sample image
selection methods and one baseline method for experiment.
We calculate the distance between each concept by
employing the semantic hierarchical tree. The distance
relationship is shown as Fig 3. For example, the distance
between concept “car” and concept “bike” is 2, and the
distance between concept “car” and concept “conveyance”

Distancis 3.

Fig 4. Graph of relationship between distance and numbers

Artifac t
Struc tu re

Building
Hous

Theaterof negative sample images for proposed method 1

Instru mentality

In this method, the total numbers of negative sample
images will be almost equal to the numbers of positive

Convey ance

sample images.

VehicleD=3

3.4.3 Proposed Method 2eWhee le d vehicle

Numbers of negative sample images

D=1
Car

D=2

Bik e

Fig 3. Distance relationship between each concept
According to the distance relationship between concepts,
we propose six negative sample image selection methods.
3.4.1 Random Sampling (Baseline)
Most researchers collect the negative sample images byDistance
Fig 5. Graph of relationship between distance and numbers

of negative sample images for proposed method 2

sample images.

We choose more negative sample images for the

Numbers of negative sample images

concepts, which are near to the positive concept. And wechoose fewer negative sample images for the concepts,
which are far from the positive concept. The relationshipbetween numbers of negative sample images and distanceis shown in Fig 5.
In this method, the total numbers of negative sample
images will be almost equal to the numbers of positive
sample images.

Distance

3.4.4 Proposed Method 3

Fig 7. Graph of relationship between distance and numbers

We choose about 10 negative concepts, which are nearof negative sample images for proposed method 4

to the positive concept. And we also choose about 10
negative concepts, which are far from the positive concept.
The relationship between numbers of negative sample
images and distance is shown in Fig 6.

3.4.6 Proposed Method 5
We choose much more negative sample images for theconcepts, which are near to the positive concept. And wechoose very fewer negative sample images for theconcepts, which are far from the positive concept. The

Numbers of negative sample images

relationship between numbers of negative sample images
and distance is shown in Fig 8.
Numbers of negative sample images

Distance
Fig 6. Graph of relationship between distance and numbersof negative sample images for proposed method 3
Distance

In this method, the total numbers of negative sample
images will be almost equal to the numbers of positive
sample images.

Fig 8. Graph of relationship between distance and numbersof negative sample images for proposed method 5

3.4.5 Proposed Method 4

In this method, the total numbers of negative sample

We choose negative sample images which like normal
distribution. We choose fewer negative sample images forimages will be almost equal to the numbers of positive
sample images.

the concepts both on near and far distance to the positive
concept. And we choose more negative sample images forthemiddledistancetothepositive

concept.

3.4.7 Proposed Method 6

The

For each distance, we choose uniform negative concepts,

relationship between numbers of negative sample images

and then prepare the negative sample images. In theand distance is shown in Fig 7.

experiment

In this method, the total numbers of negative sample
images will be almost equal to the numbers of positive

wechoose2

negative

concepts.

The

relationship between numbers of negative sample images
and distance is shown in Fig 9.

In this method, the total numbers of negative sample

belongs to one pre-selected concept. Then, there are 100

images will be almost equal to the numbers of positive

fusion scores for the test image airplane.jpg. Finally, we

sample images.

rank the 100 fusion scores (100 pre-selected concepts) andchoose top-3 suggested concepts of test image airplane.jpg

Numbers of negative sample images

for accuracy comparison.
We consider three conditions “Top1”, “Top2”, and“Top3” for each proposed method. “Top1” means thesuggested top-1 concept {airplane} matched with test
image airplane.jpg. “Top2” means the suggested top-2
concepts {airplane, sky} content the main concept of test
image airplane.jpg. “Top3” means the suggested top-3
concepts {eagle, airplane, sky} content the main concept
Distanceof test image airplane.jpg.
Finally, we calculate the accuracy for each condition in

Fig 9. Graph of relationship between distance and numbers

each method. For example, in the “Top1” condition inof negative sample images for proposed method 6

method1, if only 30 suggested concepts are correct in the
100 test images (one test image with one suggested

3.5 SVM Classifier Training and Predict
We extract low-level features from the entire sample
images, and perform the SVM classifier training for eachconcept), the accuracy of method1 at “Top1” will be 0.30.
And in this research, we also discuss the mean
reciprocal rank (MRR).

pre-selected concept. Our approach preform three feature
extraction methods, Color Moments (CM), Local Binary

4. Results

Pattern (LBP), and Edge Orientation Histogram (EOH) on

We take positive concept “airplane” for example, theeach positive and negative sample images. On CM feature

total positive sample images are 826. Table 2,3,4 shows

extraction method, we use 6x6 grids and YCbCr as thethe negative concepts and numbers of negative sample

parameters and the total extracted dimensions are 324. On

images that we have chosen in each distance for SVM

LBP feature extraction method, we use 4x4 grids and 59

classifier training for the proposed six negative sample

quantization as the parameters and the total extracted

images selection methods.

dimensions are 944. On EOH feature extraction method,
we use 6x6 grids and 72 quantization as the parameters

Table 2. Chosen negative concepts and numbers ofand the total extracted dimensions are 1,168.[3][4] After

negative sample images in method 1 and method 2

finishing the feature extraction of sample images, we
implement SVM classifier training for each pre-selectedconcept. We use C-SVC as the SVM type and use

Method1
D1

jet,3seaplane,23
bomber,23
propeller_plane,23

floatplane,6glider,22
wide_body,22
airbus,22

craft,9

craft,32
lighter,32

hovercraft,12

vehicle,21
vessel,21
hovercraft,21

sailing,15

conveyance,29
space_shuttle,29

merchant_marine,18

bike,28
windjammer,28

container,21

car_carrier,26
car_ferry,26

empty,23

shoe_tree,25
telephone,25

Chi-Square as the kernel type for SVM classifier training.
D2

3.5 Compare Experiment Results
We prepare 100 test images and predict with 100

D3

pre-selected SVM classifiers. The main concept of 100
test images is the same as 100 pre-selected concepts. For

D4

each test image we also extract three features CM, LBP,
and EOH. After predicting with SVM classifiers, we havethree SVM predict results. Then we calculate the averageof these three SVM predict results for ranking. For

D5

D6

example, a test image airplane.jpg will match with 100
pre-selected classifiers. For each classifier will returnD7

three predict results: CM, LBP, and EOH. We averagethese three results as fusion score. Each fusion score

D8

Medhod2

D9

D10

caddy,26

cue,23holder,23

D8 m a g n e t s , 1 9hydroplane,19

lock,29

chimes,22
batting_cages,22D9

D11 s u s p e n d e r , 1 6
red_carpets,16D12 c o c k p i t , 1 8nightclub,18
D13 h a t c h l i n g s , 1 9
coif,19

airframe,21
handsaw,21
winery,19
scimitar,19
ravine,18
washer,18
girl,16rose_hips,16D14 w i n g e r , 2 1
sedum,21
D15 s c a l l o p s , 2 2
bus_boys,22

leek,26

D17 p o p c o r n , 2 5
rana_temporaria,25

mimosa,23

D18 r y e , 2 6
hippos,26

candy_corn,21D19 p a n t h e r s , 2 8eel,28american_copper,18

D20 h a d d o c k , 2 9
sunfish,29

foie_gras,15

scad,12

D22 w h i p p e t , 2 2merino,22
bushbuck,22

cimarron,9D23 r u g b y , 2 2angus,22
cavalla,22

soccer,6

mound,24
hangar,24
launcher,24

loggia,17

flange,23
cap,23loadstone,23
filament,23

D11 g a l l e r y , 2

sports_arena,29
stoppers,29
apron,29

D12 a n o m a l y , 1 7

fancy_dress,22
jodhpur,22
light,22

D13arthropod,23
beanie,23
coral_reefs,18
ref,18D15 f r u i t , 2 1
octopod,21

fizz,20
principal,20D16 m a l t , 2 2tarantula,22

apple,23
litchi,23
crab,23

D17 m u s t a r d , 2 1
flamingo,21

pudding,26
edam,26
weaver,26

D18 w i l d , 1 9snapping,19champagne,24
star_anise,24
bluebirds,24

D19

martes_martes,29

marine_iguana,24
pieris_rapae,24

flathead,17

saddle,17
siamang,17

dive,2pointer,30

gordon_setter,2

clumber,12

D21

professional_baseball,3

therapists,29

D14 m a m m a l , 1 9
aquatic,19

D20

D24 s o f t b a l l , 2 3
professional_baseball,23
perfect_game,23

canvas,29

patriarch,29

D16 g u a n , 2 3
freezer,23D21 p a l l o n e , 2 1
bedlington_terriers,21
oryx,21D10

rod,30D22
D23

angus,2
D24 t o u c h _ f o o t b a l l , 2

rugby,3professional_baseball,1

Table 3. Chosen negative concepts and numbers ofnegative sample images in method 3 and method 4
Method3
D1
D2
D3

bomber,2biplane,2glider,17

jetliner,2

craft,29

D4 b a l l o o n , 1 9
airship,19
D5 b a r e b o a t , 2 1
space_shuttle,21

Table 4. Chosen negative concepts and numbers of

Medhod4

negative sample images in method 5 and method 6
Method5
D1

craft,1
D2

bomber,9
glider,17
floatplane,17Medhod6
bomber,18
monoplane,18
floatplane,18
airbus,18

airship,2lem,4

D6 s k i , 2 2
shipwreck,22

ski,10

D7 w e a p o n r y , 2 1
rowboats,21

canoe,11

D3 c r a f t , 4 2
lighter,42

craft,18
lighter,18

vessel,30
D4 s p a c e c r a f t , 3 0
hovercraft,30
airship,30

balloon,18
airship,18

D5 r o c k e t , 2 6
ship,26
yacht,26

boat,18
spaceship,18

shrimpers,26
space_shuttle,26

distance and the accuracy in “Top1” reaches 0.53, “Top2”
reaches 0.65, and “Top3” reaches 0.71.

trailer,30
D6 f i r e _ b o a t , 3 0
trawler,30
windjammer,30

public,18
hospital_ship,18

D7 m o u n t a i n _ b i k e , 2 7barrow,27
car_ferry,27

tracked,18
dredger,18

D8 b i r d _ f e e d e r , 2 5
flowerpot,25

cosmetic,18
cars,18

D9 b o m b , 1 9
drawstring,19

fuse,18
ligament,18

D10 m a s k , 1 6
elastic_band,16

digital,18
machine,18

0.4

D11

minivan,28

storeroom,18
military_uniform,18

0.3

golf_tee,24

pocket_watch,18
touchscreen,18

0.2

American,19grub,18argyle,18

cannas,15

trilobites,18
swamis,18

tiger_cub,13

dainty,18
road_runner,18

curd,9cuttlefish,18
gentian,18

D13

D14

D15

D16

D18

unai,18
long_legs,18
boar,18
sanderling,18

D21

D22

Top3

0.64

0.72
0.64

0.6

0.64

0.63

0.51

0.48
0.44

0.42

0.63

0.61

0.55

0.54

0.5

0.71

0.69

0.41

0.38

0.65

0.53

0.4

0.1

0

midges,18
new_england_aster,18

D20

0.73
0.7

D17 c r a b _ a p p l e s , 6

D19

Top2

0.8

cranberry_sauce,5chelonia_mydas,5fishing,4bovine,18
ruddy_turnstone,18

brahma,4

mountain,18
burro,18

shire_horse,3miniature_schnauzer,18
steer,18

D23 a m e r i c a n _ f o o t b a l l , 3

english_springer_spaniel,18
angus,18

D24

touch_football,18
perfect_game,18

touch_football,2RandomMethod1 Method2 Method3 Method4 Method5 Method6

Fig 10. Accuracy results for six proposed methods
0.66

0.64610.64
0.62210.62
0.6019Mean Reciprocal Rank

D12

Top1

0.6
0.58
0.56

0.55050.55210.55590.5408

0.54
0.52
0.5
0.48
Random Method1 Method2 Method3 Method4 Method5 Method6

Fig 11. Mean reciprocal rank for six proposed methods
Fig 11 shows the mean reciprocal rank between baseline

Fig 10 shows the accuracy results for “Top1”, “Top2”,

method (random sampling) and proposed six negativeand “Top3” between baseline method (random sampling)sample images selection methods. The proposed method 6

and proposed six negative sample images selection

outperforms other proposed methods and also outperforms

methods. The experiment results show that the accuracy ofbaseline method.

baseline method in “Top1” reaches 0.48, “Top2” reaches
0.64, and “Top3” reaches 0.73. And the experiment results
also show that the proposed method 6 outperforms othermethods. Method 6 is the method we choose uniform
negative concepts (two negative concepts) from each

5. Conclusions
In this research, we discuss the accuracy of different
negative sample images selection methods in one-class
SVM classifier training and prediction. We adopted

WordNet for building semantic hierarchical tree andemploy this semantic hierarchical tree to calculate thedistance between each concept. We adopted the distanceinformation for proposing six negative sample image
selection methods for experiment. The experiment results
show that different methods indeed generate different
accuracy results. The method we proposed choose uniform
negative concepts from each distance outperformed thebaseline method and the other methods we have proposed.

Acknowledgements
This research was supported by grant from JST“Multimedia

Web

AnalysisFramework

towards

Development of Social Analysis Software,” Grant-in-Aid
for Scientific Research (No. 18049068), and Ambient SoC
Global COE Program of Waseda University” of the
Ministry of Education, Culture, Sports, Science andTechnology, Japan.

Reference[1] Bryan C. Russell, Antonio Torralba, Kevin P.
Murphy, and William T. Freeman, “LabelMe: A
Database
and
Web-Based
Tool
for
Image
Annotation”, International Journal of Computer
Vision 2008, pp. 157-173[2] Claudio Cusano, Gianluigi Ciocca, Raimondo
Schettini, “Image annotation using SVM”, SPIE 2003,
pp. 330-338[3] Duy-Dinh Le, Shin’ichi Satoh, and Tomoko Matsui,“High Level Feature Extraction”, TRECVID 2007
[4] Duy-Dinh Le and Shin’ichi Satoh, “A Comprehensive
Study of Feature Representations for Semantic
Concept Detection”, TRECVID 2011
[5] Fellbaum, C, “WordNet: An Electronic Lexical
Databas,” Bradford Books.
[6] Gerard Sychay, Edward Chang, and Kingshy Goh,
“Effective Image Annotation via Active Learning”,
ICME 2002[7] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai
Li, and Li Fei-Fei, “ImageNet: A Large-Scale
Hierarchical Image Database,” CVPR 2009, pp.
248-255[8] Marcus Rohrbach, Michael Stark, Gyorgy Szarvas,
Iryna Gurevych, and Bernt Schiele, “What Helps
Where-And
Why?
Semantic
Relatedness
forKnowledge Transfer”, CVPR 2010, pp. 910-917[9] Meng Wang and Xian-Sheng Hua, “Active Learningin Multimedia Annotation and Retrieval: A Survey”,
ACM TIST 2011[10] Simon Tong, and Edward Chang, “Support Vector
Machine Active Learning for Image Retrieval”, ACM
MM 2001[11] Simon Tong and Daphne Koller, “Support Vector
Machine Active Learning with Applications to Text
Classification”, Journal of Machine Learning
Research 2001, pp. 45-66[12] Vincent. S. Tseng, Ja-Hwung Su, Bo-Wen Wang, and

Yu-Ming Lin, “Web Image Annotation by Fusing
Visual Features and Textual Information”, SAC 2007[13] Wei Li, and Maosong Sun, “Automatic Image
Annotation Based on WordNet and HierarchicalEnsembles”, CICLing 2006, pp. 417-428[14] Yoshimasa
TsuruokaandJun'ichiTsujii,“Bidirectional Inference with the Easiest-First
Strategy for Tagging Sequence Data”, Proceedings of
HLT/EMNLP 2005, pp. 467-474