Relevance Feedback for Image Retrieval
Download
Report
Transcript Relevance Feedback for Image Retrieval
Relevance Feedback for Image Retrieval
Jianping Fan
Department of Computer Science
University of North Carolina at Charlotte
Charlotte, NC 28223
1. How to Build Image Database?
a. Taking whole frame as an object
b. Extracting objects or regions from images
1. How to Build Image Database?
c. Feature Extraction
Color
Texture
Shape
1. How to Build Image Database?
d. Image Clustering
1. How to Build Image Database?
e. Database Indexing
Images in Database
Cluster 1
Cluster i
Cluster n
Subcluster i1
Subcluster ij
Subcluster im
Subregion ij1
Subregion ijl
Subregion ijp
images
images
images
log Ni Di
Query By Examples
Query example
Ranked Results
Query-By-Example
Query Example
Feature
Extraction
Distance
Function
Top-K Results
Within-Node Nearest
Neighbor Search
2. What’s Relevance Feedback?
a. The client send his/her request to the database system;
b. The database system sends him/her some ranked answers;
c. The client can exchange his/her judgment with the system.
no
no
2. What’s Relevance Feedback?
2. What’s Relevance Feedback?
3. Relevance Feedback
Distance Weighting Approach:
Database Indexing
Query Example
Feature
Extraction
3. Relevance Feedback
Query Example
Feature
Extraction
Distance
Function
Within-Node Nearest
Neighbor Search
Top-K Results
3. Relevance Feedback
Effectiveness of Feature Weighting:
Original Feature Space
Weighted Feature Space
3. Relevance Feedback
Two More Issues for Feature Weighting
a. Informative Sample Generation: what we should return
to users, so that they can make good decision on
relevance vs. irrelevance?
b. Query Movement Control: Through weighting the features,
it is able for us to control the importance between the
features for image similarity characterization. However, for
image retrieval application, we also need to control the
query point to move to target in the best way!
3. Relevance Feedback
3. Relevance Feedback
Query Updating
New Query Vector
Vectors for Negatives
Previous Query Vector
Vectors for Positive Images
3. Relevance Feedback
Query Point Movement Control
Target Image
Where to go?
No Convergence
Best Search Road
Initial Query Point
Potential Convergence
Search Road
3. Relevance Feedback
Informative Image Sampling
?
4. MEGA System in UCSB
a. Initialize the query
4. MEGA System in UCSB
b. Send the query to system
4. MEGA System in UCSB
c. Client mark the relevant examples
4. MEGA System in UCSB
d. System Evaluation according to client feedback
4. MEGA System in UCSB
e. Second client feedback
4. MEGA System in UCSB
f. Second System Evaluation
3. Relevance Feedback
Problem for Feature Weighting Approach
a. Cost-Sensitive: It is very expensive to update the feature
weights on real time!
b. Semantic Gap: The distance functions may not be able to
characterize the underlying image similarity effectively!
c. Visualization: The underlying image display tools may separate
similar images in different places, it is hard for users to evaluate
the visual similarity (relevance) between the images!
3. Relevance Feedback
Challenging Issues
d. Convergence: It is very important to guarantee the algorithm
for kernel updating is converged!
e. Cost Reduction: It is very important to reduce the cost for
kernel updating!
4. Relevance Feedback for Query by Keywords
Query is initialized by keyword
Kernel-Based Clustering of Google Search Results
Similarity-Based Image Projection and Visualization
Intention capturing and Kernel Selection for Junk
Image Filtering
Relevance is user-dependent!
4. Relevance Feedback for Query by Keywords
Requirements for such new search engine:
Fast algorithm for feature extraction;
Multiple kernels for diverse image similarity
characterization;
Implicit query intention capturing and real-time kernel
updating
4. Relevance Feedback for Query by Keywords
Keyword-Based
Google Images
Search
Fast Feature
Extraction &
Basic Kernels
Mixture-of-Kernels
&
Image Clustering
Hyperbolic Image
Visualization
Accept?
No
Query Intention
Expression &
Hypothesis Making
Through incremental learning, we can consider
multiple competing hypotheses for the same task!
4. Relevance Feedback for Query by Keywords
Fast Feature Extraction
4. Relevance Feedback for Query by Keywords
Image Representation & Similarity
a. Color histogram for whole image
b. 10 color histograms for different patterns
c. Wavelet transformation
4. Relevance Feedback for Query by Keywords
images
points in HD Space
They are invisible for human eye!
4. Relevance Feedback for Query by Keywords
Basic kernels for image similarity characterization:
Color Histogram Kernel
( u v )
2 ( u ,v ) / c ( u , v ) 1
(u, v) e
2
u v
Wavelet Filter
Bank Kernel
m
2
i
i
w (u, v) e
i
2 ( ui ,vi ) / w
i 1
2
i
Sub-Image Color Histogram Kernel
I (u, v) e
D ( u .v ) / I
4. Relevance Feedback for Query by Keywords
Mixture-of-kernels for diverse similarity characterization:
K (u, v) i i (u, v)
i 1
i 1
i
1
(a) It could be expensive for learning a good
combination!
(b) The similarity between the images depends
on the given kernel function!
4. Relevance Feedback for Query by Keywords
Hypothesis Making & Initial Analysis
R
Majority
subject to:
Decision function:
Outliers
4. Relevance Feedback for Query by Keywords
Similarity-Preserving Image Projection
Transform large amount of images (represented by high-dimensional visual
features) into their similarity contexts for enabling better visualization!
4. Relevance Feedback for Query by Keywords
Hyperbolic Image Visualization & Hypothesis Assessment
projection
Invisible HD Space
Visible 2D Disk Unit
4. Relevance Feedback for Query by Keywords
Mountain
4. Relevance Feedback for Query by Keywords
Ocean
4. Relevance Feedback for Query by Keywords
Sunrise
4. Relevance Feedback for Query by Keywords
Grass
4. Relevance Feedback for Query by Keywords
User-System Interaction for Making New Hypothesis
Hypothesis-Driven Image Re-Clustering
4. Relevance Feedback for Query by Keywords
Hypothesis-Driven Data Analysis:
a. Updating decision function: margin between
relevant images and irrelevant images!
b. Updating the combination of feature subsets!
c. Updating image projection optimization
criteria to obtain more accurate projection!
d. Updating image representation!
4. Relevance Feedback for Query by Keywords
Incremental Learning: Update decision function
1
min W W0
2
2
[1 Yl (W X l b)]
l 1
m
T
Dual Problem
m m
m
1
T
T
min l hYlYh X l X h l (1 YlW0 X l )
l 1
2 l 1 h 1
Subject to:
m
lm1 : 0 l C , l Yl 0
l 1
4. Relevance Feedback for Query by Keywords
Incremental Learning: Update decision function
a. Old decision function
b. New decision function with user’s feedbacks
4. Relevance Feedback for Query by Keywords
Incremental Learning: Update Feature Weights
4. Relevance Feedback for Query by Keywords
Make the decision function to be visible!
4. Relevance Feedback for Query by Keywords
Enlarge the margin between two classes!
4. Relevance Feedback for Query by Keywords
Enlarge the margin between two classes!
4. Relevance Feedback for Query by Keywords
Larger margin has good generalization property!
4. Relevance Feedback for Query by Keywords
Red Rose
Forest
Red Rose
Forest
4. Relevance Feedback for Query by Keywords
Red Flower
Red Flower
Sailing
Sailing
4. Relevance Feedback for Query by Keywords
Convergence for Incremental Learning
2000 queries over Google Images
Control & reduce users’ efforts!
4. Relevance Feedback for Query by Keywords
Incremental Learning is critical for Visual Analytics
Future Work for Relevance Feedback