Transcript Document

Smooth Side-Match Classified Vector
Quantizer with Variable Block Size
IEEE Transaction on image processing, VOL.
10, NO. 5, MAY 2001
Department of Applied Mathematics
National Chung Hsing University
Shiueng Bien Yang and Lin Yu Tseng
Outline






Introduction
Basic Algorithm
Smooth Side-Match Method with
Variable Block Size
Genetic Clustering algorithm
Experimental Results
Conclusion
Introduction

The evolution of SMVQ




SMVQ
SMVQ with CVQ
SSM-CVQ
Feature of SSM-CVQ



Variable block size
Smooth side-match method
Genetic clustering algorithm is applied
on codebooks generation
Basic algorithm
SMVQ
m
vd ( w)   ( wi1  lin ) 2
i 1
n
hd ( w)   ( w1 j  umj ) 2
j 1
smd ( w)  hd ( w)  vd ( w)
Basic algorithm
SMVQ with CVQ (encoder)
Basic algorithm
SMVQ with CVQ (decoder)
Smooth Side-Match Method with
Variable Block Size

Variable Block Size



Image Compression with Variable Block
Size Segmentation
Quadtree is used to address blocks of
different sizes
Smooth side-match method


Diagonal basic blocks
Smooth side-match distortion
Image Compression with Variable
Block Size Segmentation
Quadtree is used to address blocks of
different sizes
Block size and codebooks

Blocks of sizes of 16x16 and 8x8 and 4x4
with low variance are low-detail blocks


Blocks of size of 4x4 with high variance
are high-detail blocks


Use three master codebooks
 4x4
 8x8
 16x16
Use CLUSTERING algorithm, we have q classes
and q master codebooks for each class
Total : 3 + q master codebooks
Diagonal basic blocks


Diagonal blocks are encoded first.
In the experiments, the number of the basic
blocks required is approximately 25% to 28% of
that of the conventional SMVQ.
Smooth side-match distortion (1)

The encoded is divided into two parts


Upper triangular region
Lower triangular region

Problem of SMVQ

Different, dif(e, f) is defined as

dif(e, f) = (gray level of e) – (gray level of f)
Smooth side-match distortion (2)

Upper triangular region
n
Upper _ vd ( y )   |
i 1
n
Upper _ hd ( y)   |
i 1
(dif (d 2,i , d1,i )  dif ( ym,i , ym 1,i ))
2
(dif (l j ,n1 , l j ,n )  dif ( y j ,1 , y j , 2 ))
2
D( y )  Upper _ vd ( y )  Upper _ hd ( y )
 dif (d1,i , ym ,i ) |
 dif (l j ,n , y j ,1 ) |
Smooth side-match distortion (3)

Lower triangular region
n
Lower _ vd ( y )   |
i 1
n
Lower _ hd ( y)   |
i 1
(dif (um 1,i ,um,i )  dif ( y1,i , y2,i ))
2
(dif (rj , 2 , rj ,1 )  dif ( y j ,n , y j ,n1 ))
2
D( y )  Lower _ vd ( y )  Lower _ hd ( y )
 dif (um ,i , y1,i ) |
 dif (rj ,1 , y j ,n ) |
Genetic Clustering Algorithm (1)

First Stage
Use nearest neighbor (NN) algorithm to reduce the
computation time and space in the second stage.
(1) d NN (Oi )  min O j  Oi
j i
(2) d
av
1 n
  d NN (Oi )
n i 1
1, if Oi  O j  d
A(i, j )  
0, otherwise
d  d av * u u is empirical chosen to be 1.5
(4) Let the connected components be denoted by
(3)
B1 , B2 ,..., Bm
Genetic Clustering Algorithm (2)

Second Stage
Use genetic algorithm to find an appropriate number of
clusters.
Initialization Step
chromosome (string): numbers of 1’s in the strings
almost uniformly distributes within [1,m]
B1, B2 ,...Bm  T ,
Bj  C j
S 
'
j
T  T1, T2 ,..., Ts 
if Vi  S j  Vi  Sk
S j * C j  Vi * Bi
C j  Bi
Genetic Clustering Algorithm
Data Representation
Gene
Individual
Chromosome
N strings is randomly generated.
a1, b1, c1......
a2 , b2 , c2 ......


an , bn , cn ......

N individuals
Population Size=N
Genetic Clustering Algorithm
Evolution Processes
1.
2.
3.
Self Reproduction
Crossover
Mutation
Genetic Clustering Algorithm
Fitness Function
fitness( R)   Dinter (Ci ) * w  Dintra(Ci )
Dintra(Ci ) 
Dinter (Ci ) 
V
Bk Ci
k
 Si * Bk
 min V  S  * B
k
i
k
i j


Bk Ci

evaluation(1)  f a1 , b1 , c1......
evaluation( 2)  f a2 , b2 , c2 ......


evaluation( n )  f an , bn , cn ......
Genetic Clustering Algorithm
Self Reproduction
P1
f ( xi )
Pi 
 f ( xi )
i 1
i
qi   Pk
k 1
if qi 1  rk  qi
k= ai , bi , ci ......
P2
P3
Genetic Clustering Algorithm
Crossover
Set Probability of crossover Pc
Position q
Randomly generate Pc1  Pcn
If Pck  Pc Pcl  Pc
......ak , bk , cl , d l ......
......al , bl , ck , d k ......
Position=q
Genetic Clustering Algorithm
Mutation
Set Probability of mutation Pm
Randomly generate Pm  Pm
If Pmq  Pm 1
a , b , c
q
q
new
......
n
Experimental results




High-detailed Blocks：
why 28 edge-classifiers
Outside image: Lena & F-16
The PSNRs of the coding for Lena
SSM-CVQ outperforms the others in both
the PSNR & the bit rate
High-detailed Blocks：
why 28 edge-classifiers
Fitness( R)   Dinter (Ci ) * w  Dint ra (Ci )
Outside image: Lena & F-16
JPEG Lena
32.01
0.2681
SMVQ
with CVQ
30.44
0.2704
The PSNRs of the coding for Lena
CLUSTERING is best !
SSM-CVQ outperforms the others in both
the PSNR & the bit rate
Conclusion



The CLUSTERING clusters the
appropriate number of clusters.
Low-detail blocks could reduce bit
rates
High-detail blocks and smooth sidematch distortion could increase
quality