Transcript Compression

Digital Image Processing
Final Project
Compression Using DFT, DCT,
Hadamard and SVD
Transforms
and
Zvi Devir
Assaf Eden
The project’s criterions
A. The Applied transform.
B. The size of the blocks the image is
divided to.
C. The quality of the compression.
D. Adaptive compression (later)
The DFT Transform

The 2D Discrete Fourier Transform (DFT) is defined
by:
 2i

ux  vy
F (u, v )   f ( x, y )  exp  
 M

x, y



The transform is linear and separable.
It maps a real function (matrix) f(x,y) into a complex
phase plane u,v - denoted F(u,v).
The inverse
 2i
ux  vy
f ( x, y )   F (u, v )  exp  
transform is:
 M

u ,v
Can be calculated with O (n² log n).
The DCT Transform

The Discrete Cosine Transform (DCT) is defined as:
 1
 N
c(k , n)  
 2
 N




N is the vector size
  (2n 1)k 
cos

2
N


Unlike the DFT matrix, thec DCT
matrix
c* 
c 1 isc Treal and
orthogonal. That is
The DCT transform can be calculated in O (n² log n).
The property of the DCT matrix together with the fact
that it is a fast transform has made it useful substitute
for the KL transform of highly correlated first order
Markov sequences.
The Hadamard Transform



The Hadamard transform is defined by the sorted
Hadamard matrix.
The Hadamard matrix has only binary values of ±1.
The Hadamard matrices are defined recursively:
1   1  1
H2 


2   1  1



H n 1
1  Hn

 Hn  H2 
2  Hn
H n 

 H n 
The sorted Hadamard matrix can be calculated
recursively too.
The Hadamard transform is real symmetric and
orthogonal. That is H  H *  H T  H 1
The transform can be calculated in O (n² log n).
Compression Using DCT, DFT
and Hadamard
After transforming the image to the
Phase plane, the significant data is
given in a bounded area.
 Our compression methods takes only
the part that is significant and ignore
the insignificant pixels (of the phase
plane).

The SVD Transform
(For Comparison)

The Single Value Decomposition (SVD) of a matrix is
the factorization of
T
  U   V
Where U and V are orthogonal matrices and 
is a diagonal sorted real matrix.

No fast algorithm...
Compression using SVD
When we use SVD for compression we
take the singular values and work with
them in our matrix.
 The importance of the SVD is that the
solution it provides for an image
approximation by separable basis
images.

Implementation of
DFT, DCT and Hadamard
Transforming the given image to the
phase plane.
 Sample a part of the transformed
image:

– DFT - Taking rectangles near the four
corners.
– DCT and Hadamard - Taking triangle from
the top left corner.

Transforming the image back.
Discrete Fourier Transform
Discrete Cosine Transform
Hadamard Transform
Our Implementation for the
Transformations





First we wrote a 1D version for each of the three
transformation.
Then we implemented a 2D versions of the
transforms using the 1D versions.
We also used a matrix multiplication for the
transforms, since the original versions were too
slow...
In the actual implementation we used Matlab’s fft2()
and ifft2() functions for DFT, and pre-calculated
matrices for DCT and Hadamard.
Using the pre-calcualated matrices is much faster
since a 2D tranform is only a multiplication of three
matrices.
Using Adaptive Compression
In this algorithm we will find out how
much we should cut from each block so
most of the image is maintained.
 From Parseval theorem,

~
~
~
~
F  F    T ( )  T ( F  F )  T ( F )  T ( F )  U  U
We can measure the error in the phase
plane.
Using Adaptive Compression
Using the MSE of each block for each
ratio, we can decide how much to
compress the block.
 We increment the MSE wage for the
first steps.

Conclusions




After making some tests we found out that
the DCT transform work better, on equal
ratio, then the other transforms.
Works best for correlated data.
Hadamard is useful for small block sizes.
When using DFT, the blocks are noticeable.
Therefore we might consider using larger
blocks the overlaps.
DCT, Hadamard and SVD handle sharp
borders better than DFT.
Conclusions
(continued)
Adaptive compression with DFT or DCT
does not handle well sharp edges.
 The smaller the block size, the adaptive
compression gives better results.

Additional Directions

Other methods for reducing image size
– Quantization
– Other masks
Testing results on blocks with adaptive
size (Like quadtree subdivision).
 Checking different methods that were
not discussed here.

– Haar, Slant, KL ...
– Actually any orthonormal base