Outline of Vector Quantization of Images: S.R.Subramanya 1

Outline of Vector Quantization of
Images
S.R.Subramanya 1
VQ Coding Outline
• Divide data (signal) into non-overlapping vectors

• (Each vector contains ‘n’ elements (pixels/samples))
• For each image vector :
• Find closest vector in codebook
• Get its index in codebook
• Encode indices
S.R.Subramanya 2
VQ Decoding Outline
• Entropy decode the indices

• Lookup codebook for each index and retrieve vector
• Combine vectors to reconstruct image (data)
S.R.Subramanya 3
VQ Terminology
• Vector : Group of ‘n’ elements (pixels/samples)

• Codebook : (Final) set of codevectors
• Training set : (Initial) set of codevectors
• Codevector : Vector derived from image/group of images
S.R.Subramanya 4
Why VQ is better than scalar
Quantization
• Scalar Quantizer :
Treats each pixel independently
 Does not use correlation between neighboring pixels
• Vector Quantizer:
• Image (data) divided into vectors (blocks)
• Correlation among pixels in vectors is exploited
• Block size should be appropriate:
• Too large block : correlation is lost
• Too small block : More code vectors
• If no interpixel correlation, then no gain
S.R.Subramanya 5
VQ Bitrate
• Vector size : n (say, n = p x p) pixels

• Codebook size : L vectors
• Codebook index size :  log 2 L  bits
• Bit Rate of VQ :  log 2 L  n bits/pixel
S.R.Subramanya 6
Distortion Measures
Image Codebook
V1 codevectors : V ,
i 1 i  L
xk
V2
closest matching
code vector
Vk
Image vectors : Xj
VL
Mean Square Error (MSE) 1 n

d ( X j , VK )   ( X j (i )  Vk (i )) 2
(Euclidean Distance) n i 1
1 n
Weighted MSE d ( X j ,VK )   (Wi ( X j (i )  Vk (i )) 2
n i 1
S.R.Subramanya 7
Two Basic Kinds of Codebook
• Local Codebook
 One codebook for each image
 Codebook derived from vectors of one image
 Good performance (Quality of reconstruction)
 More overhead :
(1) computation
(2) Transmission of CB to decoder
S.R.Subramanya 8
Two Basic Kinds of Codebook
• Global Codebook
 One codebook for a class of images
 Codebook derived from vectors of all images in the class
 Less overhead (compared to local codebook)
 Lower performance
S.R.Subramanya 9
Major Issues in VQ
• Generation (construction) of codebook

 concerns what needs to be included in the codebook
• Design of codebook
 concerns structuring codebook entries to minimize
search time
S.R.Subramanya 10
Codebook Generation
• Generate codebook from a Training set

• Training Set: Set of vectors derived from image vectors
• Codevectors should minimize distortion
• Most commonly used algorithm : LBG algorithm
• LBG : Linde–Buzo–Gray algorithm
S.R.Subramanya 11
LBG Algorithm Outline
S.R.Subramanya 12
Codebook Initialization
Three basic schemes:

• Random
• Perturb and Split (Bottoming)
• Pairwise Nearest Neighbor (PNN) clustering (PNN)
S.R.Subramanya 13
Codebook Design
• Basic objective : Minimize search time for codevector

• Full (Exhaustive) Search : very expensive
• Design emphasis : Organization of codebook
S.R.Subramanya 14
Codebook Organizations
•Tree-structured codebook
• Product codebook
• Mean/Residual VQ
• Interpolative/Residual VQ
• Gain/Shape VQ
• Classified VQ
• Finite State VQ
S.R.Subramanya 15
Tree – Structured Codebook
• Codebook organized as M–ary tree

• Number of Levels :  log m L 
• Code vectors stored at the leaves
• Intermediate node : ‘average’ of ‘codevectors’ of children
• Improved search time
• Increased Storage cost
• Performance inferior to full search
S.R.Subramanya 16
Variations of Tree – Structured VQ
• Tapered trees:
 Non – Uniform number of branches at nodes
 Branches per node increases going down the tree
( Ex: 2 branches at level 1, 3 at level 2 etc.)
• Pruned Trees
 Start with (full) large initial tree
 Remove code vectors that do not reduce distortion
S.R.Subramanya 17
Product Codebook
• Codebook : Cartesian product of many smaller codebooks

• Vector characterized by many independent features:f1,f2...,fN
• Separate codebook for each feature
• Smaller codebook sizes : L1,L2...,LN
• Effective codebook size : L1,L2...,LN
• Actual storage + search complexity O(L1+L2+...+LN)
S.R.Subramanya 18
Prediction/Residual Class VQ
• Predict Original Image

• Derive Residual Image
• Data used in prediction: Scalar Quantization + Encoding
• Residual Image : Vector Quantization
• Major Types:
 Mean/Residual VQ
 Interpolative/Residual VQ
S.R.Subramanya 19
Mean/Residual VQ
• Image Vectors have similar variations about different

mean/ends
• Remove mean from vectors  fewer code vectors
S.R.Subramanya 20
Mean/Residual VQ
• Scheme :
• Compute ‘mean’ of image vectors : M={m1,m2...,mN}
~
• Quantize M using scalar quantization : M
• (Apply DPCM before Quantization  further bitrate
reduction)
• Subtract Quantized means from vector elements
 Residual vectors
• Quantize Residual vectors using VQ

S.R.Subramanya 21
Interpolative/Residual VQ
• Subsample original image by l in each dimension (typically,

l=8)
• Quantize subsampled value
• Upsample using Quantized subsampled values (typically,
bilinear interpolation is used)
• Form Residual : (Original – Upsampled)
• Segment Residual to form 4 x 4 vectors
• Quantize Residual vectors using VQ
S.R.Subramanya 22
Classified VQ
• Several codebooks
• Each codebook for a specific feature
 ex. edges, smooth areas, etc.
• Codebooks could be of different sizes
S.R.Subramanya 23
What is the measure of performance
VQ?
 How does one rate the performance of a

compressed image or sound using VQ?
 There is no good way to measure the
performance of VQ.
 This is because the distortion that VQ
incurs will be evaluated by us humans
and that is a subjective measure.
VQ?
 We can always resort to good old Mean
Squared Error (MSE) and Peak Signal to
Noise Ratio (PSNR).
 MSE is defined as follows:
where M is the number of elements in the signal, or image.

VQ?
 For example, if we wanted to find
the MSE between the
reconstructed and the original
image, then we would take the
difference between the two images
pixel by pixel, square the results,
and average the results.
VQ?
 The PSNR is defined as follows:
where n is the number of bits per symbol.

 As an example, if we want to find the
PSNR between two 256 gray level images,
then we set n to 8 bits.

Outline of Vector Quantization of Images: S.R.Subramanya 1

Uploaded by

Copyright:

Available Formats

Outline of Vector Quantization of Images: S.R.Subramanya 1

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Outline of Vector Quantization of Images: S.R.Subramanya 1

Uploaded by

Copyright:

Available Formats

Outline of Vector Quantization of

• Divide data (signal) into non-overlapping vectors

• Entropy decode the indices

• Vector : Group of ‘n’ elements (pixels/samples)

• Vector size : n (say, n = p x p) pixels

Mean Square Error (MSE) 1 n

• Generation (construction) of codebook

• Generate codebook from a Training set

Three basic schemes:

• Basic objective : Minimize search time for codevector

• Codebook organized as M–ary tree

• Codebook : Cartesian product of many smaller codebooks

• Predict Original Image

• Image Vectors have similar variations about different

• Quantize Residual vectors using VQ

• Subsample original image by l in each dimension (typically,

 How does one rate the performance of a

where M is the number of elements in the signal, or image.

where n is the number of bits per symbol.

You might also like