18-08-2011, 02:09 PM
[attachment=15368]
Discrete Wavelet Transform (DWT)
Overview
Need for Compression
Transmission and storage of uncompressed video would be extremely costly and impractical.
Frame with 352x288 contains 202,752 bytes of information
Recoding of uncompressed version of this video at 15 frames per second would require 3 MB. One minute180 MB storage. One 24-hour day262 GB
Using compression, 15 frames/second for 24 hour1.4 GB, 187 days of video could be stored using the same disk space that uncompressed video would use in one day
Principles of Compression
Spatial Correlation
Redundancy among neighboring pixels
Spectral Correlation
Redundancy among different color planes
Temporal Correlation
Redundancy between adjacent frames in a sequence of image
Classification of Compression
Lossless vs. Lossy Compression
Lossless
Digitally identical to the original image
Only achieve a modest amount of compression
Lossy
Discards components of the signal that are known to be redundant
Signal is therefore changed from input
Achieving much higher compression under normal viewing conditions no visible loss is perceived (visually lossless)
Predictive vs. Transform coding
Classification of Compression
Predictive coding
Information already received (in transmission) is used to predict future values
Difference between predicted and actual is stored
Easily implemented in spatial (image) domain
Example: Differential Pulse Code Modulation(DPCM)
Classification of Compression
Transform Coding
Transform signal from spatial domain to other space using a well-known transform
Encode signal in new domain (by string coefficients)
Higher compression, in general than predictive, but requires more computation (apply quantization)
Subband Coding
Split the frequency band of a signal in various subbands
Classification of Compression
Subband Coding (cont.)
The filters used in subband coding are known as quadrature mirror filter(QMF)
Use octave tree decomposition of an image data into various frequency subbands.
The output of each decimated subbands quantized and encoded separately
Discrete Wavelet Transform
The wavelet transform (WT) has gained widespread acceptance in signal processing and image compression.
Because of their inherent multi-resolution nature, wavelet-coding schemes are especially suitable for applications where scalability and tolerable degradation are important
Recently the JPEG committee has released its new image coding standard, JPEG-2000, which has been based upon DWT.
Discrete Wavelet Transform
Wavelet transform decomposes a signal into a set of basis functions.
These basis functions are called wavelets
Wavelets are obtained from a single prototype wavelet y(t) called mother wavelet by dilations and shifting:
where a is the scaling parameter and b is the shifting parameter
Discrete Wavelet Transform
Theory of WT
The wavelet transform is computed separately for different segments of the time-domain signal at different frequencies.
Multi-resolution analysis: analyzes the signal at different frequencies giving different resolutions
MRA is designed to give good time resolution and poor frequency resolution at high frequencies and good frequency resolution and poor time resolution at low frequencies
Good for signal having high frequency components for short durations and low frequency components for long duration.e.g. images and video frames
Discrete Wavelet Transform
Theory of WT (cont.)
Wavelet transform decomposes a signal into a set of basis functions.
These basis functions are called wavelets
Wavelets are obtained from a single prototype wavelet y(t) called mother wavelet by dilations and shifting:
where a is the scaling parameter and b is the shifting parameter
Discrete Wavelet Transform
The 1-D wavelet transform is given by :
Discrete Wavelet Transform
The inverse 1-D wavelet transform is given by:
Discrete Wavelet Transform
Discrete wavelet transform (DWT), which transforms a discrete time signal to a discrete wavelet representation.
it converts an input series x0, x1, ..xm, into one high-pass wavelet coefficient series and one low-pass wavelet coefficient series (of length n/2 each) given by:
Discrete Wavelet Transform
where sm(Z) and tm(Z) are called wavelet filters, K is the length of the filter, and i=0, ..., [n/2]-1.
In practice, such transformation will be applied recursively on the low-pass series until the desired number of iterations is reached.
Discrete Wavelet Transform
Lifting schema of DWT has been recognized as a faster approach
The basic principle is to factorize the polyphase matrix of a wavelet filter into a sequence of alternating upper and lower triangular matrices and a diagonal matrix .
This leads to the wavelet implementation by means of banded-matrix multiplications
Discrete Wavelet Transform
Two Lifting schema:
Discrete Wavelet Transform
where si(z) (primary lifting steps) and ti(z) (dual lifting steps) are filters and K is a constant.
As this factorization is not unique, several {si(z)}, {ti(z)} and K are admissible.
