Probabilistic
Web Image Gathering
ACM SIGMM workshop MIR`05 Nov.11th, 2005

Keiji Yanai The University of Electro-Communications, Japan
Kobus Barnard University of Arizona, USA
1.
2.
3.
4.

Objective & background
Related work
MethodExperiments1

2(Long-term) Objective of
our Web Image Gathering

Gather several hundreds of images
associated with one concept fromthe Web without human intervention
 It’s not image search.
 Non-interactive.

No feedback. Fully-automatic.

• We can gather 10,000 kinds of images while sleeping !!
• We can use as much time as we need for processing.

 A large number of “X” images

visual knowledge of “X”
Acquisition of visual knowledge for realizing
generic object recognition for any
concepts
The Universityof Electro-Communications
Tokyo, JAPAN (UEC)3

There are great many kinds of images in the real world.
We canunderstandof Webtheseimages easily.
Extracting
visualknowledgeall
fromimages
is promising approach to solve it, I believe.
But, computer systems cannot, because they don’t have
Gathering Web images with high precision is the first step.
enough visual knowledge to understand these images.

The University of Electro-Communications
Tokyo, JAPAN (UEC)4

What is Web Image Gathering ?

Many “waterfall” images withhigh precision.
WebThis is beyond search results.

imagegathering
This is “visual knowledge”
on “waterfall”.
system“Waterfall”

The University of Electro-Communications
Tokyo, JAPAN (UEC)5

Objective of this paper Introduce a probabilistic method to

our Web image gathering system [MM03]
 Import a simplified translation model [ICCV01]
 Select relevant images using a probabilistic model No supervision, No feedback, No humanintervention, No prior knowledge
Just provide “keywords”

The University of Electro-Communications
Tokyo, JAPAN (UEC)2. Related work

7Web image search “Search” does not need a lot of images as output.
 High precision and quick response are the most important.
 Some systems assume interaction (RF).

different from “gathering”
 Commercial: apply text search methods to images
 Google Image Search, Picsearch, AltaVista Image Search, Lycos
 Only based on HTML analysis,• Image analysis for billions of images is too expensive
 Cannot expect good (high-precision) results

The University of Electro-Communications
Tokyo, JAPAN (UEC)8Web image search (-2002)
 Research: combine textual and image features [until 2002] HTML and image analysis

after Web-crawling by their original crawler[Scarloff 99]• WebSeer [Frankel 96], WebSEEk [Smith 97], Image Rover• Interactive 2-step search: [1st ]Text search -> [2nd]CBIR• Original Crawler: Small-scale experiments.
query
keywords

Searchingfor imagesby keyword

selectingimages

Text-based result

searching forsimilar images
by image features

Finalsearch
The University of Electro-Communications
result Tokyo, JAPAN (UEC)9Web image search (recent) [recently] Filtering the results ofGoogle Image Search• [Feng MM04] Co-learning of textual and image featureswith SVM : Need (a little) supervision interactive• [Fergus CVPR04, ICCV05] (the latest object recognition technique)
Unsupervised part-based probabilistic image classification
similar to ours

Part-based

We’re region-based !!

The University of Electro-Communications
Region-based
Tokyo, JAPAN (UEC)3. System overview&probabilistic method

11Overview of the method
Collection stage : same as our previous system [MM03]zObtain URL of HTML files related to the query
keywords by using text search engines
Gather images from WWW by using those URLs

Selection Stage :Replace CBIR-based by prob.-basedz

Select images based on their image features「sunset」「夕日」

Collection stage

Selection stage（search by keywords ）（analyzing images）
querykeywords
HTML files & images
URLs「sunset」「夕日」
Text search engines

WWWresults

The University of Electro-Communications
Tokyo, JAPAN (UEC)12Collection stage [MM03]
1. Send the query to text search engines, andobtain URLs of HTML files related to the keyword.
2. Gather HTML files from WWW.
3. Extract URLs of images from HTML files.
4. Evaluate relevancy between images and thekeywords, and classifying images into A, B Selectionand C.
stage
5. Gather only group A and B images from WWW.
querykeywords

Gathering
HTML files

Query keywords

URLs

Text search engines

Extracting andevaluating
URLs of images

AHTML files

CB

Gathering
image files
image files

WWW

The University of Electro-Communications
Tokyo, JAPAN (UEC)13

Sellection stage [new](A) Segment imgs. & extract region features(B) Learn P(X|r) with GMM and EM(C) Select high P(X|r) regions, repeat to (B)(D) Calculate P(X|I) and select high P(X|I) images
A: initial training set
B: unlabeled setA

Probabilistic
selection(1)B

Learn P(X|r)

(A)

(B)

Repeat several times
to refine “X” model

Probabilistic
selection(2)Calculate
P(X|I) andselectimages

Select highP(X|r) regions(C)
The University(D)of Electro-Communications
Tokyo, JAPAN (UEC)14
Evaluation of imagesby analyzing HTML files
Classifying URLs of image files

AWWW

Highly evaluatedBC file name, ALT tag, link words
 title tag, neighborhood of the image-tag
 OtherwiseABCExamples<IMG SRC=”lion.jpg” ALT=”lion in Ueno zoo”>
A<A HREF=”raion01.jpg”>a photo of aThelion</a>A
University of Electro-Communications
Tokyo, JAPAN (UEC)15Region features

Segmentation （JSEG）

riririririri

Extract region featuresfrom regions the size of
which are larger than a threshold.

color
textureshape

24 dim.
vector Need to prepare negative images (backgrounds)

Collect a lot of images from the Web
randomly.
The University of Electro-Communications
random Web images
Tokyo, JAPAN (UEC)16

Probabilistic region selection (1) Positive regions from rank-A images :ri Negative regions from background images : ri+

Probabilisticclusteringwith GMMriri +r +− i rri − ir+i ++ri ri ri−−EM alri−ri r
gorithm+i‘X’ & ‘non-X’ features+−Select ‘X’
p Xj = P(c j | X )and ‘non-X’ a<(1-t) j
p X = P(c j | nonX )components

a>t

aj =p Xj
p Xj + p Xja>t
We seta<(1-t) t=0.85
The University of Electro-Communications
Tokyo, JAPAN (UEC)

17

Probabilistic region selection (2)Learning an “X” region modela<(1-t)

r1 r8 r
r5 2
‘X’ model

P ( X | ri )selected ‘X` regions
P( X | ri ) > P (nonX | ri )a>t

r3a<(1-t)‘nonX’ model

P (nonX | ri )

r4
r6 r7

Selected ‘nonX` regions
P ( X | ri ) < P (nonX | ri )The University of Electro-Communications
Tokyo, JAPAN (UEC)

Repeat learning & selecting

a>tSelect “X” regions

18Final Image Selection
 Select top T regions regarding

P ( X | ri ) (r ∈ I )for each image I j and average themP ( X | rtop1 j )P( X | I j ) =ij

P ( X | rtop1 j ) + P ( X | rtop 2 j )
2P ( X | rtop 2 j )Finally, images ofP ( X | rtop 2 j ' )P ( X | I j ) ≥ th are selected

P ( X | rtop 2 j ' )as final results.
The University of Electro-Communications
Tokyo, JAPAN (UEC)4. Experimental
results

20Experiments for 10 words
 sunset, mountain, waterfall, beach,ramen (Chinese noodle), flower, lion, apple,

baby, laptop-PC Method:raw (only HTML analysis) 29,944 images for 10 words
old[MM03] (color-histogram) 16,687
new (propoosed method) 14,825
 Evaluation:

precision, # of output images
The University of Electro-Communications
 Time: about 6 hours/concepts with 10PCsTokyo, JAPAN (UEC)21

Results： # images and precision#clusters：150，repeat: 2times
precision
90(%)
Avg. prec. 66.0% -> 73.5%

#7000
imgs.
6000

80

5000

70

4000

60

3000

50
40

2000

raw
oldnewraw
oldnew

30

Cn ote -Pyb able
ap pl io ner
fl o wchb eaa llterfwadl emosu nn oo

10a in0u nt20s et

10001482 imgs/words

The University of Electro-Communications
Tokyo, JAPAN (UEC)22

Many result images
 Sunset(positive and negative) Mountain (positive and negative) waterfall laptop-PC

http://img.cs.uec.ac.jp/mm05/
The University of Electro-Communications
Tokyo, JAPAN (UEC)Results: using word vectors 23
as well as image features

The University of Electro-Communications
Tokyo, JAPAN (UEC)24

Precision of A-imagesrawoldnewprecision(%)
100
90
80

Avg.
raw
72％
old
73％

70
60
50
40
30

new
80％
C(617.1img)

e-Pn otyb ableap plio nerf l owchb ea

fal l
ter
wadl en oonaio
un tmosu ns et

20

The University of Electro-Communications
Tokyo, JAPAN (UEC)

25

Precision of B-images(equivalent to the recognition results by the models)
raw
old
new

precision(%)
100
90
80

Avg.
raw
56％
old
58％

70
60
50
40
30

new
67％
PC(865.4img)

te nobyba

pl e
apnl ior
we
fl oh
ac
bel
fa l
te r
wa

leod
non
ta i
un

mosunset

20

The University of Electro-Communications
Tokyo, JAPAN (UEC)Results in case of varying times 26of repeat and # GMM components.
# imgs.

75 (%)
prec.

1600
70

1500

65

1400

1300

m=50m=100m=150m=200
m=300
m=50m=100m=150m=200m=300

6012345 The University
6 timesof repeatof Electro-Communications
Tokyo, JAPAN (UEC)Comparison with
Google Image Searchprec.(%)
100

27Google
ours

9080

Avg.
prec.
GIS
top500
58.6％

70
60
50
40
30
20

ours
73.5％

100su
nsme
ou tnt
ai
n
no
odlew
ater
fa
ll
beachf low
erlionap
plebabno yte-PC(1483)
The University of Electro-Communications
Tokyo, JAPAN (UEC)28

Comparison with related work
 [Feng MM04] Co-learning of textual and image

features with a little supervision

 54.0 F-measure for 15 concepts

 [Fergus CVPR04] Unsupervised
 65.9% precision at 15% recall for 11 concepts

 [Fergus ICCV05] Unsupervised + improved model 69.9% precision at 15% recall for 7 concepts
 Good at “objects” such as airplane, car, and bike

 Our results: good at “scene” such as sunset and mountain 63.0 F-mesures (pre.73,5% , rec.55.1%)

for 10The University of Electro-Communications
Tokyo, JAPAN (UEC)29

Conclusion
 We Introduced region-based

probabilistic image selection method
into Web image gathering.
 Iterative algorithm with GMM and EM

enabled training from imperfect data.
 We used images evaluated highly inHTML analysis as initial training set.
 Precision 73.5% , Recall 55.1% for 10 concepts
The University of Electro-Communications
Tokyo, JAPAN (UEC)30

Future work
 Improve by combining part-based andregion-based approach Part-based seems to be better for “object”

 Build real world image corpus

for generic object recognition
 1000 images/concept for 1000 concepts

We can build it while sleeping The! University of Electro-Communications
Tokyo, JAPAN (UEC)Thank you!
You can eat all the results at
http://img.cs.uec.ac.jp/mm05/

32

The University of Electro-Communications
Tokyo, JAPAN (UEC)