Content Based Image

Retrieval
Natalia Vassilieva
nvassilieva@hp.com
HP Labs Russia

© 2008 Hewlett-Packard Company

Tutorial outline
• Lecture 1
− Introduction
− Applications
• Lecture 2
− Performance measurement
− Visual perception
− Color features
• Lecture 3
− Texture features
− Shape features
− Fusion methods
• Lecture 4
− Segmentation
− Key points detection
• Lecture 5
− Multidimensional indexing
− Survey of existing systems
Lecture 2
Performance measurement
Visual perception
Color features
Lecture 2: Outline
• Performance measurement
− Retrieval effectiveness

• Some facts about human visual perception

• Color features
− Color fundamentals
− Color spaces
− Color features: histograms and moments
− Comparison

4/55
Performance measurement
Performance concerns
• Efficiency
− Important due to the large data size
• Retrieval effectiveness
− No similarity metric which exactly conforms to human
perception

5/55
Problems in effectiveness evaluation
• Define a common image collection
− Corel Photo CDs
− Brodatz texture collection: http://www.ux.uis.no/~tranden/brodatz.html
− CoPhIR: http://cophir.isti.cnr.it/whatis.html
− Participate in ImageCLEF, TRECVID, imageEVAL, ROMIP
• Obtain relevance judgement
− Use of collections with predefined subsets (Corel collection)
− Image grouping (medical)
− Simulating users
− User judgements
• Pooling
• Different types of judgement data (relevant – not relevant, ranking, …)

6/55
Effectiveness measurement
• “You can see, that our results are better”

7/55
Effectiveness measurement
• “You can see, that our results are better”
• User comparison n

∑w i
• Numerical-valued measures P= i =1
N
− Rank of the best image ∑w
i =1
i

− Average rank of relevant images

− Percentage of weighted hits
− Percentage of similarity ranking

K2
S (i) = ∑ Q(i, k ),
k = K1
K1 = P(i) − σ (i), K 2 = P(i) + σ (i)

8/55
Effectiveness measurement (2)
• Numerical-valued measures
− Recall and precision

• Average recall/precision
• Recall at N, Precision at N
• F-measure

9/55
Effectiveness measurement (3)
• Numerical-valued measures
− Target testing
− Error rate

− Retrieval efficiency

10/55
Effectiveness measurement (3)
• Graphical representations
− Precision versus Recall graphs
− Precision at N versus N, Recall at N versus N
− Retrieval accuracy versus noise graph

11/55
Effectiveness measurement (4)
• Different measurement (QBIC versus MMT)

12/55
Lecture 2: Outline
• Performance measurement
− Retrieval effectiveness

• Some facts about human visual perception

• Color features
− Color fundamentals
− Color spaces
− Color features: histograms and moments
− Comparison

13/55
Some facts about our visual perception
• We are driven by a desire to make meanings
(We all seem to 'see things' in inkblots, flames, stains, clouds and so on.)

• Human visual perception is self-learning

− If you are an European, it is hard to recognize Japanese
and Chinese faces
− We are looking for the known objects in the picture

14/55
Some facts about our visual perception
− We are looking for the known objects in the picture

Some well known optical illusions

15/55
Some facts about our visual perception
• Cultural and environmental factors affects the
way we see things

Are these stairs goes up or down?

• Arabs would read this (right to left)
as a set of stairs going down

Is left line shorter than the right

• one?
Left: outside corner of a building
• Right: inside corner of a room

Inside corner may appear to be nearer

(and therefore larger)

16/55
Some facts about our visual perception
• Brightness adaptation and discrimination
− Range of light intensity
levels to which human
visual system can
adapt: order of 1010
− Subjective brightness
(perceived intensity) is
a logarithmic function of
the actual light intensity

17/55
Some facts about our visual perception
• Brightness adaptation and discrimination
− The human visual
system cannot operate
over such a range
(1010) simultaneously
− It accomplishes this
variation by changing
its overall sensitivity –
brightness adaptation
phenomena
The range of subjective brightness that the
eye can perceive when adapted to the level
Ba
Ba – brightness adaptation level
Bb – below it all stimuli are perceived as black
18/55
Some facts about our visual perception
• Brightness adaptation and discrimination
− The eye discriminates between
changes in brightness at any specific
adaptation level.
Basic experimental setup ∆Ic
used to characterize – Weber ratio,
brightness discrimination. I
∆Ic – the increment of illumination discriminable 50% of the time;
I – background illumination.

• Small values of Weber ratio mean good brightness

discrimination (and vice versa).
• At low levels of illumination brightness
discrimination is poor (rods) and it improves
significantly as background illumination increases
(cones).

19/55
Some facts about our visual perception
• Perceived brightness is not a simple function of intensity

− Mach band effect

(Scalloped effect)

20/55
Some facts about our visual perception
• Perceived brightness is not a simple function of intensity

− Simultaneous contrast

21/55
Lecture 2: Outline
• Performance measurement
− Retrieval effectiveness

• Some facts about human visual perception

• Color features
− Color fundamentals
− Color spaces
− Color features: histograms and moments
− Comparison

22/55
Color fundamentals
• Color in the eye
− Varying sensitivity of different
cells in the retina (cones) to light
of different wavelengths:
• S-cones: short-wavelength (blue);
• M-cones: middle-wavelength
(green);
• L-cones: long-wavelength (red).

Normalized typical human cone cell

responses (S, M, and L types) to
monochromatic spectral stimuli
Color fundamentals
• Primary and secondary colors
− Due to different absorption curves of
the cones, colors are seen as variable
combinations of the so-called primary
colors: red, green and blue.
Mixture of lights − The primary colors can be added to
(Additive primaries) produce the secondary colors of light:
magenta (R+B), cyan (G + B), and
yellow (R + G).
− For pigments and colorants, a primary
color is the one that subtracts
(absorbs) a primary color of light and
Mixture of pigments
(Subtractive primaries) reflects the other two.
Color fundamentals
• Brightness, hue, and saturation

− Brightness is a synonym of intensity

− Hue represents the impression related to the dominant
wavelength of the color stimulus
− Saturation expresses the relative color purity
(amount of white light in the color)
− Hue and Saturation taken together are called the
chromaticity coordinates (polar system)
Color fundamentals
• From tristimulus values to chromaticity
coordinates
− The amounts of red, green, and blue needed to form
any particular color are called the tristimulus values
and denoted by X, Y, and Z
− The chromaticity coordinates x and y (Cartesian
system) are obtained as:
X Y Z
x= , y= , z=
X +Y + Z X +Y + Z X +Y + Z

x+ y+ z =1
Color fundamentals
• CIE xy Chromaticity Diagram
− Created by the International Commission
on Illumination (CIE) in 1931.
− Function of x (red) and y (green) :
z = 1 – (x + y).
− The outer boundary is the spectral
(monochromatic) locus, wavelengths
shown in nm.
− (x,y) = (1/3,1/3) is a flat energy spectrum
point (point of equal energy).
− Any point on the boundary is completely
saturated.
The CIE 1931 chromaticity
diagram. − Boundary → point of equal energy :
saturation → 0
Color fundamentals
• Color Gamut

RGB monitor
color gamut

printing device
color gamut

Gamut of the CIE RGB primaries Typical gamuts of a monitor and

and location of primaries on the of a printing device.
CIE 1931 xy chromaticity diagram.
Lecture 2: Outline
• Performance measurement
− Retrieval effectiveness

• Some facts about human visual perception

• Color features
− Color fundamentals
− Color spaces
− Color features: histograms and moments
− Comparison
Color spaces
• The purpose of a color space (or color model
or color system) is to facilitate the specification
of colors in some standard way.
• A color model provides a coordinate system
and a subspace in it where each color is
represented by a single point.
• Common color spaces:
− RGB (monitors, video cameras),
− CMY/CMYK (printers),
− HSI/HSV/HSL/HSB (image processing),
− CIE Lab (image processing).
Color spaces
• RGB color space

If R,G, and B are represented with 8 bits (24-

bit RGB image), the total number of colors is
(28)3=16,777,216
Color spaces
• Munsell color system
− By Professor Albert H. Munsell in
the beginning of the 20th century.
− Specifies colors based on 3 color
dimensions, hue, value
(lightness), and chroma (color
purity or colorfulness).

Munsell hues; value 6 / chroma 6

Color spaces
• HSI/HSL/HSV/HSB color spaces

− RGB, CMY/CMYK are hardware oriented color

spaces (suited for image acquisition and display).
− The HSI/… (Hue, Saturation, Intensity/Lightness/
Value/Brightness) are perceptive color spaces
(suited for image description and interpretation).
− Allow the decoupling of chromatic signals (H+S)
from the intensity signal (I).
Color spaces
• HSI/HSL/HSV/HSB color spaces

R+G+B
I =
3
max(R, G , B) + min(R, G , B)
L=
2

V = max(R, G , B)
Graphical depiction of HSV (cylinder and cone)

http://www.easyrgb.com/index.php?X=MATH

Graphical depiction of HSL

Color spaces
• CIE L*a*b color space
− It’s a device independent and perceptually uniform
color model.
− It allows the color gamuts of monitors and output
devices to be related to one another.
− The L*a*b* components are given by

Lightness 75%

Lightness 25%
Color spaces
• HCL color space

CIE Lab color space HCL color space

Color spaces
• HCL color space

, where , ,

And finally to allow hue to vary in an interval from -180° to +180°:

Lecture 2: Outline
• Performance measurement
− Retrieval effectiveness

• Some facts about human visual perception

• Color features
− Color fundamentals
− Color spaces
− Color features: histograms and moments
− Comparison
Color features

Statistical moments for every

color channel

F(I) = (E1I,E2I,E3I,
σ1I,σ2I,σ3I,
F(I) = (h1I, h2I, …, hNI) s1I,s2I,s3I)

Metrics: L1, L2, L∞ Metrics: ~L1

Stricker M., Orengo M. Similarity of Color Images. Proceedings of the SPIE Conference,
vol. 2420, p. 381-392, 1995
Color histograms
• Quantization of color space

− Quantization is important: size of the feature vector.

− When no color similarity function used:
• Too many bins – similar colors are treated as dissimilar.
• Too little bins – dissimilar colors are treated as similar.
 Color histograms
• Quantization of color space: recall
Recall at 10

Recall at 10

Quantization Quantization

ImageDB-100 ImageDB-1000
 Color histograms
• Quantization of color space: precision

Precision at N
Precision at N

Top N Top N

ImageDB-100 ImageDB-1000
Color histograms: main disadvantages
1. Colors similarity across histo bins is not considered:

Cumulative histograms

d(H1, H2) > d(H1, H3)

Color histograms: main disadvantages
1. Colors similarity across histo bins is not considered:

Cumulative histograms

d ( H 1 , H 2 ) = ( H 1 − H 2 ) ⋅ A ⋅ ( H 1 − H 2 )T
А – matrix with color similarity coefficients
Niblack W., Barber R., et al. The QBIC project:
Querying images by content using color, texture and
shape. In IS&T/SPIE International Symposium on
Electronic Imaging: Science & Technology,
d(H1, H2) > d(H1, H3) Conference 1908, Storage and Retrieval for Image
and Video Databases, Feb. 1993
Color histograms: main disadvantages
1. Colors similarity across histo bins is not considered:

Cumulative histograms

d ( H 1 , H 2 ) = ( H 1 − H 2 ) ⋅ A ⋅ ( H 1 − H 2 )T

Fuzzy histo

Coefficient
d(H1, H2) > d(H1, H3)

Hue
Color histograms: main disadvantages
1. Colors similarity across histo bins is not considered:

Cumulative histograms

d ( H 1 , H 2 ) = ( H 1 − H 2 ) ⋅ A ⋅ ( H 1 − H 2 )T

Fuzzy histo

Color similarity measure

d(H1, H2) > d(H1, H3)

Color histograms: main disadvantages
2. Spatial color layout is not considered:
( 3, 0.242552, 77, 99)
( 1, 0.218489, 60, 65)
(21, HA= HB
0.208021, =81,
HC13)
(19, 0.108854, 88, 41)
(13, 0.079948, 78, 30)
A B C (27, 0.070677, 120, 78)
(31, 0.030260, 64, 87)
(19, 0.013958, 126, 83)

bin number amount of position of color

(color num) color

α | h Q − h I | ( x Q − x I ) 2 + ( y Q − y I ) 2 , hiQ ≠ 0, hiI ≠ 0;
N  Qi i i i i i

dist (Q, I ) = ∑  βhi , hiQ ≠ 0, hiI = 0;

i =1 
 β h i
I
, hiI ≠ 0, hiQ = 0.
Color moments

Average, standard deviation, skewness

Average, covariance matrix of the color channels

Consider spatial layout: fuzzy regions

Stricker M., Dimai A. Spectral Covariance

and Fuzzy Regions for Image Indexing.
Machine Vision and Applications, vol. 10.,
p. 66-73, 1997
Lecture 2: Outline
• Performance measurement
− Retrieval effectiveness

• Some facts about human visual perception

• Color features
− Color fundamentals
− Color spaces
− Color features: histograms and moments
− Comparison
Histograms or color moments? (1)
Stricker M., Orengo M. Similarity of Color Images. ... (3000 images)
Histograms or color moments? (2)
ImageDB-1000

Precision at N
Recall at 10

Quantization Top N
Histograms or color moments? (3)
1,2

0,8
Precision

0,6

0,4

0,2

0
0 1 2 3 4 5 6 7 8 9 10
Top N

Moments, Clouds Moments, Fields

HSL, 6*2*2, Clouds HSL, 6*2*2, Fields
Histograms or color moments? (4)
1,2

0,8
Precision

0,6

0,4

0,2

0
0 1 2 3 4 5 6 7 8 9 10
Top N

Moments, People Moments, Bears

HSL, 6*2*2, People HSL, 6*2*2, Bears
Lecture 2: Resume
• Performance: efficiency and effectiveness
− Lack of the common benchmark collections and retrieval
effectiveness measurement

• Human visual perception is very complex

− Have to take into account known facts about our perception to
reduce the semantic gap

• Color features: histograms and moments

− On heterogeneous collections moments are slightly better
− Fusion of histograms and moments can give better results
Lecture 2: Bibliography
• Muller H., Muller W., McG. Squire D., Marchand-Maillet S., Pun T. Performance
evaluation in content-based image retrieval: overview and proposals. In Pattern
Recognition Letters, vol. 22, pp. 593-601, 2001.
• Lu G. , Sajjanhar A. On performance measurement of multimedia information
retrieval systems. In Proc of the International Conference on Computational
Intelligence and Multimedia Applications, pp.781-787, 1998.
• Swain M. J., Ballard D. H. Color indexing. In International Journal of Computer
Vision, vol. 7, no. 1, pp. 1132, 1991.
• Stricker M., Orengo M. Similarity of Color Images. In Proc. of the SPIE Conference,
vol. 2420, pp. 381 – 392, 1995.
• Stricker M., Dimai A. Spectral Covariance and Fuzzy Regions for Image Indexing.
In Machine Vision and Applications, vol. 10, pp. 66 – 73, 1997.
• Sarifuddin M., Missaoui R. A new perceptually uniform color space with associated
color similarity measure for content based image and video retrieval. In Proc. of the
ACM SIGIR Workshop on Multimedia Information Retrieval, 2005.
• Sural S., Qian G., Pramanik S. A histogram with perceptually smooth color
transition for image retrieval. In Proc. of the Fourth International Conference on
Computer Vision, Pattern Recognition and Image Processing, 2002.