Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.


Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

On Stability of Adaptive Similarity Measures for Content-Based Image Retrieval

presentation at MMM 2012

Christian Beecks

on 24 January 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of On Stability of Adaptive Similarity Measures for Content-Based Image Retrieval

define a stability value based on the variance of an evaluation measure (for instance Mean Average Precision)

How does it work?
consider a distribution of MAP values
expected value
standard deviation

The Average Precision Stability (APS) is then defined as:
Properties of APS =

bounded between 0 and 1

high value indicates high stability

the APS decreases with increasing

can be used with any evaluation measure
On Stability of Adaptive Similarity Measures for Content-Based Image Retrieval
Christian Beecks
Thomas Seidl
Data Management and Data Exploration Group
RWTH Aachen University, Germany

18th International Conference on MultiMedia Modeling

generate a large visual vocabulary comprising visual words
represent each image by a high-dimensional vector of visual word frequencies
compare these vectors by cosine similarity

Many extensions have been proposed:
Hamming Embedding
Asymmetric Hamming Embedding
Compressed Fisher vectors
Vector of locally aggregated descriptors
Bag-of-visual-words Model
Search for similar images based on their contents

Generation of image models:
detection of interesting points/regions
extraction of local feature descriptors
compact representation of the descriptors

Prominent classes of image models:
vector-based (bag-of-visual-words model)
set-based (feature signature model)
Content-based Image Retrieval
do use object-specific visual vocabularies
representation of each image by an individual bag of clustered feature descriptors
compare these bags (feature signatures) by adaptive distances
Feature Signature Model
Goal: assessment of the retrieval performance by using a benchmark image database with ground truth

Frequently based two fundamental values:
precision (How many retrieved images are relevant?)
recall (How many relevant images are retrieved?)

Approaches to performance evaluation:
Precision-and-recall curve
Mean Average Precison
Normalized Discounted Cumulative Gain
Evaluation Measures
Average Precision Stability
dense sampling:
SIFT descriptors:
feature histogram:
interesting point detection (here: dense sampling)
representation of each image by using the visual vocabulary
feature descriptor extraction
generation of a large visual vocabulary by k-means clustering
Many adaptive distances have been proposed:
Earth Mover's Distance
Perceptually Modified Hausdorff Distance
Signature Quadratic Form Distance
interesting point detection (here: dense sampling)
Stability reflects how good a particular approach behaves when changing the image model quality
What is stability in CBIR?
Evaluation of the feature signature model on five databases:

Feature signatures were generated by
random sampling of image pixels
extracting local color + position + texture information
using an adaptive k-means clustering algorithm
Experimental Setup
Each query is transformed multiple times and Mean Average Precision is measured

Distribution of MAP-values varies with changing sampling size

Higher sampling size results in higher performance

WCD, EMD, and SQFD show a high performance with a small sampling size

PMHD requires a larger sampling size to be competitive
Experimental Evaluation
Average Precision Stability (APS) is computed by using expected values and standard deviations

On average, the SQFD shows the highest stability followed by the EMD and WCD

Reason for that: SQFD, EMD, and WCD consider the complete structure of the feature signatures
Experimental Evaluation
Thank you for your attention!
H. Jegou, M. Douze, C. Schmid, P. Pérez: Aggregating local descriptors into a compact image representation. CVPR 2010: 3304-3311
F. Perronnin, Y. Liu, J. Sánchez, H. Poirier: Large-scale image retrieval with compressed Fisher vectors. CVPR 2010: 3384-3391
H. Jegou, M. Douze, C. Schmid: Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search. ECCV (1) 2008: 304-317
M. Jain, H. Jegou, P. Gros: Asymmetric hamming embedding: taking the best of our bits for large scale image search. ACM Multimedia 2011: 1441-1444
all images are taken from the MIR Flickr database:
M. J. Huiskes, M. S. Lew: The MIR flickr retrieval evaluation. Multimedia Information Retrieval 2008: 39-43
J. Sivic, A. Zisserman: Video Google: A Text Retrieval Approach to Object Matching in Videos. ICCV 2003: 1470-1477
C. D. Manning, P. Raghavan, H. Schütze: Introduction to information retrieval. Cambridge University Press 2008: I-XXI, 1-482
C. Beecks, M. S. Uysal, T. Seidl: Signature Quadratic Form Distance. CIVR 2010: 438-445
Y. Rubner, C. Tomasi, L. J. Guibas: The Earth Mover's Distance as a Metric for Image Retrieval. International Journal of Computer Vision 40(2): 99-121 (2000)
B. G. Park, K. M. Lee, S. U. Lee: Color-Based Image Retrieval Using Perceptually Modified Hausdorff Distance. EURASIP J. Image and Video Processing (2008)
C. Beecks, M. S. Uysal, T. Seidl: A comparative study of similarity measures for content-based multimedia retrieval. ICME 2010: 1552-1557
feature descriptor extraction
C. J. van Rijsbergen: Information Retrieval. Butterworth 1979
K. Järvelin, J. Kekäläinen: Cumulated gain-based evaluation of IR techniques. ACM Trans. Inf. Syst. 20(4): 422-446 (2002)
A. Kent, M. M. Berry, F. U. Luehrs, J. W. Perry: Machine literature searching VIII. Operational criteria for designing information retrieval systems. American Documentation, 6: 93–101. (2005)
J. Z. Wang, J. Li, G. Wiederhold: SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries. IEEE Trans. Pattern Anal. Mach. Intell. 23(9): 947-963 (2001)
M. J. Huiskes, M. S. Lew: The MIR flickr retrieval evaluation. Multimedia Information Retrieval 2008: 39-43
J.-M. Geusebroek, G. J. Burghouts, A. W. M. Smeulders: The Amsterdam Library of Object Images. International Journal of Computer Vision 61(1): 103-112 (2005)
L. Fei-Fei, R. Fergus, P. Perona: Learning Generative Visual Models from Few Training Examples: An Incremental Bayesian Approach Tested on 101 Object Categories. CVPR Workshop on Generative Model Based Vision, 2004
S. A. Nene, S. K. Nayar and H. Murase: Columbia Object Image Library (COIL-100). Technical Report Columbia University, 2006
Why considering stability?
Varying image quality:
different image processing/enhancing features
photometric or geometric changes
Varying image model quality:
different parameters in the feature extraction phase (e.g. sampling strategies, cluster algorithms, normalizations)
Quality of the query image model and the database image model differs
They miss the ability to express the variance of the observed values
Average Precision Stability
Prominent approaches to content-based image retrieval: bag-of-visual-words model and feature signature model

We introduced Average Precision Stability as a simple and efficient measure

We have evaluated the stability of adaptive distance-based similarity measures

Signature Quadratic Form Distance shows the highest stability
How stable is the model with respect to changing sampling size?
all images are taken from the Corel Wang database:
J. Z. Wang, J. Li, G. Wiederhold: SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries. IEEE Trans. Pattern Anal. Mach. Intell. 23(9): 947-963 (2001)
Full transcript