Transcript ImageRover: A Content-Based Image Browser for the World

ImageRover: A Content-Based Image
Browser for the World Wide Web
•
•
•
•
•
•
Introduction
Approach
Image Collection Subsystem
Image Query Subsystem
Performance Experiment
Summary
Reference:
•Stan S., Leonid T., and Marco L. C., ImageRover: A Content-Based Image
Browser for the World Wide Web, Proc. IEEE Workshop on Content-based
Access of Image and Video Libraries, June 1997.
1998/5/21
by Chang I-Ning
1
Introduction
• Technical challenges:
– The great scale and unstructured nature of the
world wide web.
– The problem of developing fast and effective
image indexing methods for fast image
database queries.
• Searching images need not require solving
the image understanding problem, just as
useful text search tools.
1998/5/21
by Chang I-Ning
2
Approach
• The general approach
– Provide the decompositions that can be
precomputed for images:
• color histograms, edge orientation histograms,
texture measures, shape invariants,…etc.
– Resulting information is stored in vector form.
– At search time, select a weighted subset of
these decompositions to be used for computing
image similarity measurements.
1998/5/21
by Chang I-Ning
3
Approach
• ImageRover system consists of two main
components
– Image collection subsystem
• Image Digestion  icon and image index vector.
• Image Analysis Submodules: color and orientation.
– Image search subsystem
• Query Server: approximate k-d search algorithm.
• User Interface: Web browser as an HTML.
• Relevance Feedback: relevance feedback algorithm
1998/5/21
by Chang I-Ning
4
Image Collection Subsystem
• Utilizes a distributed fleet of WWW robots
that can contain
– collection modules.
– digestion modules.
– a local database.
• The robots are dispatched and coordinated
via a separate coordination layer.
– Manages updates of the image index database.
1998/5/21
by Chang I-Ning
5
Image Collection Subsystem
1998/5/21
by Chang I-Ning
6
Image Query Subsystem
• Query Server
– The image query subsystem is based on a
client-server architecture.
• Performs a dimensionality reduction (PCA)
 builds an optimized k-d tree.
• Improve performance
– Search accuracy= level of approximation factor
– An approximate k-d search algorithm can allow
the user to specify an “approximation” level for
the nearest neighbors and to control the tradeoff
between speed and accuracy.
1998/5/21
by Chang I-Ning
7
Image Query Subsystem
1998/5/21
by Chang I-Ning
8
• User Interface
– ImageRover querys by example paradigm.
1998/5/21
by Chang I-Ning
9
1998/5/21
by Chang I-Ning
10
1998/5/21
by Chang I-Ning
11
Image Query Subsystem
• Relevance Feedback
– The ImageRover system employs a novel
relevance feedback algorithm that selects the
Minkowski Lm distance metrics appropriate for
a particular query.
– This mechanism allows the user to perform
queries by example based on more than one
sample image and to collect the images he or
she finds during the search, refining the result
at each iteration.
1998/5/21
by Chang I-Ning
12
Performance Experiment
• Tested the performance of the approximate knearest neighbors search on an SGI Indigo2 R10K
with 128MB of main memory, for a data set of
size N =500,000 and dimension k =78. In searches
for 20 nearest neighbors in 1000 random trials :
–  = 5.0, search averaged 1.02 CPU seconds per query.
–  = 10.0, search averaged 0.11 CPU seconds per query.
– Brute-force search averaged 1.82 CPU seconds per
query.
• The approximation yield a significant speed-up :
– up to 16 times faster, depending on the specified .
1998/5/21
by Chang I-Ning
13
Summary
• ImageRover’s distributed robot framework
can enable a modest fleet of 32 singlethreaded robots to collect and index over
one million images monthly.
• ImageRover is a search by image content
navigation tool that provides a powerful
method for data exploration or browsing of
WWW images.
1998/5/21
by Chang I-Ning
14