8/10/2022
Module 2
• Review of matrix theory: row and column ordering- Toeplitz, Circulant and block
matrix
• 2D Image transforms: DFT, its properties, Walsh transform, Hadamard transform,
Haar transform, DCT, KL transform and Singular Value Decomposition.
• Image Compression: Need for compression, Basics of lossless compression – bit
plane coding, run length encoding and predictive coding, Basics of lossy
compression – uniform and non-uniform quantization techniques used in image
compression, Concept of transform coding, JPEG Image compression standard.
1
8/10/2022
Toeplitz matrix
2
8/10/2022
Circulant Matrix
3
8/10/2022
• Linear convolution - Toeplitz matrix
• Circular convolution - circulant matrix
• A circulant matrix is Toeplitz but the converse is not true
• The product of 2 circulant matrices is a circulant matrix
• The product of 2 Toeplitz matrices need not be Toeplitz.
4
8/10/2022
Orthogonal and unitary matrix
• An orthogonal matrix is such that its inverse is equal to its transpose
• A is orthogonal if A-1 =A T OR ATA = AAT=I
• A matrix is called unitary matrix if ts inverse is equal to itsconjugate
transpose
• A-1= A*T OR AA*T = A*TA =I
• A real orthogonal matrix is also unitary but a unitary matrix need not
be orthogonal
Block Matrix
• A matrix whose elements are matrices themselves are called block
matrix
5
8/10/2022
6
8/10/2022
Image Transforms
What does image transform do
• It represents a given image as a series summation of a set of unitary
matrices
• For an N X N image u(m,n) the forward and inverse transforms are
given below
V AUA T
U A*T VA *
7
8/10/2022
8
1. Check whether the DFT matrix is unitary or not.
1
2. 2D DISCRETE FOURIER TRANSFORM
3. PROPERTIES OF 2D DISCRETE FOURIER TRANSFORM
3.1 Separable Property
The separable property allows a 2D transform to be computed in two steps by successive 1D
operations of rows and columns of an image.
2
3
3.2 Spatial Shift Property
3.3 Periodicity Property
4
3.4 Convolution Property
5
3.5 Scaling Property
6
3.6 Conjugate Symmetry Property
3.7 Multiplication by exponential Property
7
3.8 Rotation Property
4. Compute the 2D DFT of the 4 × 4 grayscale image given below.
8
5. Compute the inverse 2D DFT of the transform coefficients given by
9
6. Walsh Transform
Fourier analysis is basically the representation of a signal by a set of orthogonal sinusoidal
waveforms. The coefficients of this representation are called frequency components and
the waveforms are ordered by frequency.
Walsh introduced a complete set of orthonormal square-wave functions to represent these
functions.
The computational simplicity of the Walsh function is due to the fact that Walsh functions
are real and they take only two values which are either +1 or –1.
The one-dimensional Walsh transform basis can be given by the following equation
7. Find the 1D Walsh basis for the fourth-order system (N = 4).
Also, n and k vary from 0 to N–1. In our example, N = 4. So n and k have the values of 0, 1, 2
and 3.
So the shortcut method for finding Walsh Transform
10
11
8. Hadamard Transform
9. Harr Transform (Calculation)
12
10. Properties of Discrete Cosine Transform (DCT)
1. The discrete cosine transform has excellent energy compaction for highly correlated data.
2. Separable property A 2D DCT can be computed as two separate one-dimensional transforms.
Because of this separable property, the 2D DCT of an image can be computed in two steps by
successive 1D operations on rows and columns of an image.
11. Mathematical Expression of 2D DCT
12. Compute the discrete cosine transform (DCT) matrix for N = 4.
13
Similarly find X[k] for k=1,2 and 3
13. KL Transform
This transform also called as Hotelling [Link] transform is a reversible linear
transform that exploits statistical properties of a vector representation.
The basic functions of KL transforms are orthogonal eigen vectors of the covariance
matrix of a data set.
After a KL transform, most of the energy of the transform coefficients are concentrated
within the first few components.
Drawbacks of KL transform: It is input dependent and the basic function has to be
calculated for each signal model in which it is operated. KL transform require O(m2)
multiply / add operations. The DFT and DCT require O(log2m) multiplications.
Applications of KL transform:
Clustering Analysis: to determine the new coordinates for the sample data where
largest covariance lies on the first axis and next largest on the next axis and so on, and
therefore used for dimensionality reduction.
Image compression
14
14. Singular Value Decomposition (SVD) Transform
The singular value decomposition of a rectangular matrix A is a decomposition of the form
Where A is an m × n matrix
U, V are orthonormal matrices.
D is a diagonal matrix comprised of singular values of A
The singular values 1 2 ........ n 0 appear in descending order along the main
diagonal of D.
The singular values are obtained by taking the square root of the eigen values of AA T and
ATA.
15
16
17