PowerPoint Presentation
Image Compression Using
Fourier Transform & Wavelet Transform
OBJECTIVES
1.
Fourier Transform
2.
Wavelet Transform
4.
Image Compression by Fourier Transform
5.
Image Compression by Wavelet Transform
3.
Image Compression
6.
Comparison
7.
References
1. Fourier Transform
In the year 1807, Joseph Fourier presented Fourier series, which could express any function as linear combination of harmonically related sinusoids or periodic exponentials.
Later, Fourier gave representation of non-periodic signals as weighted integral of sinusoids. This representation is known as Fourier transform.
Fourier transform (FT) is an integral transform that represents a signal or a function in terms of sinusoids. It is a mathematical tool used for frequency analysis of signals.
Commonly used to transform a function in the time domain to the frequency domain.
Mathematical representation
The Fourier transform of a function is given by
and its inversion is given by
Fourier transform decomposes the signal in infinite number of sine or cosine waves
(1.1)
(1.2)
Discrete Fourier Transform (DFT)
DFT calculates Fourier transform on a discrete set of frequencies from a discrete set of time samples.
Discrete Fourier transform of a signal is given by
and its inversion is given by
x.
Where k is index of discrete frequencies and n is the index of the time samples.
(1.3)
(1.4)
There is no essential difference between FFT and DFT in the fact that they both ca
y out Fourier transform on discrete signals. FFT was introduced to reduce the computational complexity involved in DFT.
The complexity of the DFT algorithm is O(n 2 ) while FFT has a complexity of O(n · log n).
For a 1024 point transform (N=1024), this will give approximately a 100 fold speed improvement.
Fast Fourier Transform (FFT)
where is a periodic function with only distinct values and its inversion is given by
(1.5)
(1.6)
FFT is given by
Block Diagram of FFT
Different FFT Algorithms
Fast Fourier Transform
Cooley Tukey Algorithm
Radix-2 Decimation Algorithm
Radix-4 Algorithm
Split Radix Algorithm
Fast Hartley Transform
Quick Fourier Transform
Data compression of digitized signals.
Audio waves sampled digitally.
Eliminate frequencies with values under a certain threshold by truncating small FFT.
Used for digital frequency filtering.
Magnetic Resonance Imaging
Few applications of FFT
How wavelets came into existence?
FT expresses the data or signals as a sum of sine waves which are not localized in time or space. Hence, these sine waves oscillate endlessly.
Fourier Transform oscillating endlessly
Wavelet
Therefore, new sets of functions were needed that can precisely analyse the signals or data in time and frequency. This accompany or gave a path to the exploration of wavelets.
Wavelet is a wave-like oscillation with amplitude that begins at zero, rises and then falls back to zero. They are characterized by having compact support and area underneath the curve is zero.
An alternative approach for FT is the Wavelet Transform, which decomposes a function into a set of wavelets.
2. WAVELET
WAVELET TRANSFORM
DISCRETE WAVELET TRANSFORM
CONTINUOUS WAVELET TRANSFORM
L then the wavelet is defined by
(1.7)
Mathematically
The translation or position parameter determines the location of the wavelet in the time domain by shifting the wavelet.
The dilation or scale parameter determines its scale and location in the frequency domain.
normalization
wavelet with
scale a and position
Mother wavelet
Dilation of Wavelet
Translation of wavelet
The continuous wavelet transform of a square integrable function with respect to the basic wavelet is given by
and the co
esponding wavelet inversion formula is given by
(1.8)
(1.9)
Mathematically
Function representing time-series
Wavelet Coefficients which are function of position ‘b’ and scale ‘a’.
Complex conjugate of wavelet with translation and dilation
When a signal say ‘ x(t)’ is discreetly sampled then we can say that the WT is discrete.
The signal x(t) here is calculated by first passing it over inferior pass filter which results in the outcome of convolution of two.
Discrete Wavelet Transform
(1.10)
CWT uses every possible wavelet over a range of scales and locations i.e. an infinite number of scales and locations. While the DWT uses a finite set of wavelets i.e. defined at a particular set of scales and locations.
If dilation and translation parameter a and b are chosen to be discrete then the DWT wont generate huge amount of data.
When a and b are based on power 2 (i.e. dyadic), then analysis becomes much more efficient and accurate.
3. What is Image Compression?
It is a technique to minimize the size of a graphics file without degrading the quality of the image.
The reduction in file size allows more storage space and reduces the time required for images to be sent.
The compression of images is ca
ied out by an encoder and outputs a compressed form of an image.
In the processes of compression, the mathematical transforms play a vital role.
Image
Mathematical Transform
Compressed Image
4. How FFT works in image compression?
FFT on Rows
FFT on Columns
Applying FFT on rows of the picture that is to be compressed.
Then applying FFT on the columns of the new picture obtained.
Next, we get a 2-dimensional FFT of the original picture which is represented as a sum of sines and cosines in the X and Y-axis.
Truncating all the small Fourier coefficients we get a massive compression.
Finally, after applying inverse FFT we obtain a compressed version of the original picture.
Inverse FFT
PIC-1
NEW PIC
2-D FFT OF PIC-1
COMPRESSED PIC-1
import numpy as np
import matplotlib.pyplot as plt
import os
plt.rcParams['figure.figsize'] = [5, 5]
plt.rcParams.update({'font.size': 18})
#reading an image by using imread funtion
A=imread(os.path.join('/content/drive/MyDrive/dog.jpg'))
B = np.mean(A, -1)
#crearting a figure
plt.figure()#The figure() function in pyplot module of matplotlib li
ary is used to create a new figure.
#showing the image
plt.imshow(256-A)#The imshow() function in pyplot module of matplotlib li
ary is used to display data as an image
plt.axis('off')#The plt. axis() method allows you to set the x and y limits with a single call,
Bt=np.fft.fft2(B)
Code
#sorting a
ay
Btsort = np.sort(np.abs(Bt.reshape(-1)))
for keep in(0.1,0.05,0.01,0.002):
thresh =Btsort[int(np.floor((1-keep)*len(Btsort)))]
ind = np.abs(Bt)>thresh
Btlow=Bt*ind
Alow = np.fft.ifft2(Btlow).real
plt.figure()
plt.imshow(256-Alow,cmap='gray')
plt.axis('off')
plt.title('Compressed image: keep = ' + str(keep*100) + '%')
5. How wavelet transform works in image compression?
DWT
Inverse DWT
Wavelet compression offers an approach that allows one to reduce the size of the data while at the same time improving its quality through the removal of high-frequency noise components.
DWT of the original picture is obtained by truncating all the smaller wavelet coefficients. Finally, after applying inverse FFT we obtain a compressed version of the original picture.
PIC-1
2-D DWT OF
PIC-1
COMPRESSED PIC-1
import numpy as np
import matplotlib.pyplot as plt
import os
import pywt
#changing the size of an image
plt.rcParams['figure.figsize'] = [16, 16]
#changing the font size
plt.rcParams.update({'font.size': 18})
#reading the image using imread image
A=imread(os.path.join('/content/drive/MyDrive/dog.jpg’))
#taking average
B = np.mean(A, -1)
n=2
w='db1'
Code
#using pywt.wavedec2 for multilevel decomposition
coeffs = pywt.wavedec2(B, wavelet=w, level=n)
coeffs[0] /= np.abs(coeffs[0]).max()
for detail_level in range(n):
coeffs[detail_level + 1] = [d/np.abs(d).max() for d in coeffs[detail_level + 1]]
a
, coeff_slices= pywt.coeffs_to_a
ay(coeffs)
plt.imshow(a
, cmap='gray_r',vmin=-0.25,vmax=0.75)
#again changing the figure size
plt.rcParams['figure.figsize'] = [16, 16]
fig=plt.figure(figsize=(18, 16))
plt.show()
The major advantage of using wavelets is that they can be used for analyzing functions at various scales.
We could listen to an entire symphony or just the violin.
Ideas such as multi-resolution, versions of an image at various resolutions, is very similar to how the human eye works. As you zoom in at smaller and smaller scales, you can find details that you did not see before.
In practice, the wavelet transforms have great advantages over the traditional Fourier methods in analyzing signals which contain discontinuities and sharp spikes like most natural images.
6. COMPARISON
References
[1] Pathak, R. S. (2009). The wavelet transform (Vol. 4). Springer Science & Business Media.
[2] Chui, C. K. (2016). An introduction to wavelets. Elsevier.
[3] Debnath, L., & Bhatta, D. (2016). Integral transforms and their applications. Chapman and Hall/CRC.
[4] Soni, M., & Kunthe, P XXXXXXXXXXA General comparison of FFT algorithms. Pioneer Journal Of IT & Management.
THANK YOU
FOR YOUR ATTENTION
1
scale
frequency
µ