Transcript Embedded colour image coding for content-based retrieval

Embedded colour image coding
for content-based retrieval
Source: Journal of Visual Communication and
Image Representation, Vol. 15, Issue 4,
December 2004, pp. 507-521
Author: Guoping Qiu
Speaker: Chia-Yi Chuang
Date: 2005/03/22
1
Outline


Introduction
Integrating SBIC, CPAM and VQ





Segmentation-based image coding
Colored pattern appearance model and
vector quantization
Statistics
Experimental results
Conclusions
2
Introduction
Image
feature
extraction
Image
Database
Image
feature
extraction
Similarity
matching
Image
Similar Images
Query Image
3
Flow chart
2. CPAM and VQ
1. SBIC
Original image
CPAM
SS,ASP,CSP
Image segmented blocks
VQ
Image
Database
Store
Pasp,Pcsp
3. Statistics
Iasp,Icsp
4
1. SBIC (1/4)



Segmentation-Based Image Coding
 It is often classified as 2nd generation image coding.
Idea：
 classify image regions into different classes.
 allocate different number of bits to different regions
according to the properties of the region.
Restrictions
 Shapes of the regions must be square
 Maximum size is N×N
 Pixels have similar colors in each region
5
1. SBIC (2/4)

A constrained adaptive segmentation algorithm (CASA)
6
1. SBIC (3/4)
7
Calculate：
1. SBIC (4/4)
53
51
...
80
44
44
…
28
0
99
…
…
…
…
101
Bmin=1 , Bmax=16 ,
Bstep=1
Original Image
EL = 10
EL = 20
8
2. CPAM and VQ
 Coloured pattern appearance model and vector
quantization
9
2.1 CPAM(1/2)

Coloured Pattern Appearance Model



It is defined as the spatial and spectral characteristics
of a (small) block of pixels.
A colored image pattern is modeled by three
components:
 the stimulus strength (SS).
 the achromatic spatial pattern (ASP).
 the chromatic spatial pattern (CSP).
By separating achromatic and chromatic signals, it is
possible to work on two low-dimensional vectors
rather than one very high-dimensional vector.
10
Y = 0.299R + 0.587G + 0.114B
Cb = -0.168R – 0.331G + 0.499B
2.1 CPAM(2/2)
Cr = 0.500R – 0.419G – 0.081B
Mean = 115
(121,235,99)
(250,94,1)
(82,41,29)
(154,198,166) (221,148,69)
(20,247,92)
(198,23,6)
(1,146,195)
(164,3,51)
(59,61,137)
(184,264,21)
(257,27,35)
(84,62,129)
(204,39,47)
(91,183,172)
Cb
Cr
(88,1,53)
Y
-49
11
-73
-13
-9
-52
-39
-38
-29
-21
-66
-26
49
-3
38
-108
7
14
7
-49
-35
30
-24
10
185
33
130
52
181
161
161
73
108
57
69
212
97
76
89
154
1.61
0.29
1.13
0.45
1.58
1.4
1.4
0.64
0.94
0.49
0.6
1.85
0.84
0.66
0.78
1.34
Asp
-0.25
-0.18
-0.57
-0.23
0.06
0.12
0.06
-0.43
-46
39
86
21
-19
43
-101
89
-33
41
-8
55
-0.29
0.36
-0.07
0.48
-76
77
-7
-20
19
42
38
-33
0.17
0.37
0.33
-0.29
114
6
82
-45
Csp
11
2.2 Vector Quantization

Encoder


Map k-dimensional vector x to index i
Decoder

Map index i to the reproduction vector
0
100
225
20
200
1
100
50
80
45
…
95
30
0
10
255
…
124
250
45
…
255
50
Codebook
240
101
53
51
252
100
50
50
250
80
44
44
243
80
45
45
240
28
0
99
230
1
124
30
0
100
225
11
255
22
200
95
0
10
255
20
200
Original image
Coded image
Reconstructed image
12
3. Integrating SBIC, CPAM, and VQ for
colour image coding and indexing

Since the segmentation is based on the
homogeneity of the region, a segmented larger
block and a segmented smaller block will roughly
have the same level of homogeneity.


VQ coding of variable size patterns
Construction of image descriptors from
SBIC/CPAM/VQ stream
13
3.1 VQ coding of variable size patterns


To design one set of codebook at an intermediate block
size and which will be used by all the block sizes.
Bc - the size of the CPAM pattern (the block size of the
codebook)；Bs - the block size of a segmented block.


If Bs < Bc then up-sample Bs, to Bc using bilinear
interpolation.
If Bs > Bc then subsample Bs to Bc using bilinear
interpolation.
14
3.2 Construction of image descriptors
from SBIC/CPAM/VQ stream


Let Pasp(i,j) be the probability of a block of
size i and whose ASP vector is encoded by
the vector quantizer to the jth codeword of
VQasp.
Let Pcsp(k,l) be the probability of a block of
size k and whose CSP vector is encoded into
the lth codeword of VQcsp.
15
4. Statistics
Image (2000 blocks)
Iasp(1,0)=15 , Pasp(1,0)=0.0075
Icsp(1,0)=20 , Pcsp(1,0)=0.001
Iasp(1,1)=30 , Pasp(1,1)=0.015
Icsp(1,1)=25 , Pcsp(1,1)=0.0125
…
…
4096
Iasp(1,255)=200 , Pasp(1,255)=0.1
Icsp(1,255)=60 , Pcsp(1,255)=0.03
Iasp(2,0)=150 , Pasp(2,0)=0.075
Icsp(2,0)=80 , Pcsp(2,0)=320=0.04
…
…
Iasp(16,254)=40 , Pasp(16,254)=0.02
Icsp(16,254)=75 , Pcsp(16,254)=0.0375
Iasp(16,255)=100 , Pasp(16,255)=0.05
Icsp(16,255)=50 , Pcsp(16,255)=0.025
16
Similarity measurement
Image A : PAasp(i,j)、PAcsp(k,l)
Image B : PBasp(i,j)、PBcsp(k,l)
The similarity between A and B can be measured by
the following distance:
where
and
are relative weights given to
the chromatic and achromatic pattern features.
17
Experimental results (1/5)
Set A
Set B
Examples of query image pairs. For each image in
set A, there is a corresponding (similar but different)
target image in set B, or vice versa.
18
Experimental results (2/5)
Therefore, EL=7 tends to give very satisfactory
image quality and reasonable retrieval performance.


The trend seemed to be that the higher the error
limit, the lower the average ranks of the returned
target images.
But, if the error limit is too high, the opposite is true.
19
colour correlogram (cc)； MPEG7 colour structure (MPEG7 cs)
Experimental results (3/5)
 CC and MPEG7 CS had more
queries found the target image
EL=7, Bmin=4, Bmax=10, and Bstep=2
at lower ranks (better
performance).
 Both methods had queries
which returned the targets at
a much higher ranks (worse
performance).
20
Experimental results (4/5)
EL=7, Bmin=4, Bmax=10, and Bstep=2
the average ranking of the
new method is much lower
(better performance).
21
Experimental results (5/5)
The image on the upper left corner is the query, the rest are
the returned images arranged in terms of similarity in a
canonical order.
22
Conclusions



This is a color image coding and indexing
method which integrates SBIC, CPAM and VQ.
Our objectives are twofolds,
i.e., compression and easy content access.
The proposed method has at least comparable
performances to state of the art methods,such
as colour correlogram(cc) and the latest MPEG7
colour structure(MPEG7 cs) descriptor in
content-based image retrieval.
23