
Wavelet Video Processing Technolog full report.doc (Size: 95.5 KB / Downloads: 377)
ABSTRACT
The biggest obstacle to the multimedia revolution is digital obesity. This is the blot that occurs when pictures, sound and video are converted from their natural analog form into computer language for manipulation or transmission. In the present explosion of high quality data, the need to compress it with less distortion of data is the need of the hour. Compression lowers the cost of storage and transmission by packing data into a smaller space.
One of the hottest areas of advanced form of compression is wavelet compression. Wavelet Video Processing Technology offers some alluring features, including high compression ratios and eye pleasing enlargements.
INTRODUCTION
Uncompressed multimedia data requires considerable storage capacity and transmission bandwidth. Despite rapid progress in mass storage density processor speeds and digital communication system performance, demand for data storage capacity and data transmission bandwidth continues to outstrip the capabilities of available technologies. The recent growth of data intensive multimediabased web applications have not only sustained the need for more efficient ways to encode signals and images but have made compression of such signals central to storage and communication technology. For still image compression, the joint photographic experts group (JPEG) standard has been established. The performance of these codes generally degrades at low bit rates mainly because of the underlying blockbased Discrete cosine Transform (DCT) scheme. More recently, the wavelet transform has emerged as a cutting edge technology, within the field of image compression. Wavelet based coding provides substantial improvements in picture quality at higher compression ratios. Over the past few years, a variety of powerful and sophisticated wavelet based schemes for image compression have been developed and implemented. Because of the many advantages, the top contenders in JPEG2000 standard are all wavelet based compression algorithms. IMAGE
COMPRESSION
Image compression is a technique for processing images. It is the compressor of graphics for storage or transmission. Compressing an image is significantly different than compressing saw binary data. Some general purpose compression programs can be used to compress images, but the result is less than optimal. This is because images have certain statistical properties which can be exploited by encoders specifically designed for them. Also some finer details in the image can be sacrificed for saving storage space.
Compression is basically of two types.
1. Lossy Compression
2. Lossless Compression.
Lossy compression of data concedes a certain loss of accuracy in exchange for greatly increased compression. An image reconstructed following lossy compression contains degradation relative to the original. Often this is because the compression scheme completely discards redundant information. Under normal viewing conditions no visible is loss is perceived. It proves effective when applied to graphics images and digitized voice.
Lossless compression consists of those techniques guaranteed to generate an exact duplicate of the input data stream after a compress or expand cycle. Here the reconstructed image after compression is numerically identical to the original image. Lossless compression can only achieve a modest amount of compression. This is the type of compression used when storing data base records, spread sheets or word processing files.
IMAGE COMPRESSION SYSTEM
A typical lossy image compression system consists of three
closely connected components namely.
(a) Source encoder
(b) Quantizer
© Entropy encoder
FIGURE 1 IMAGE COMPRESSION SYSTEM
Source encoder
This is a linear transformer in which the given signal or image is transformed to a different domain. Compression using wavelet transforms belongs to a class of technique called transform coding. The objectives of transform coding are
I) To create a representation for the data in which there is less correlation among the coefficient values. This called decorrelating the data.
II) To have a representation in which it is possible to quantize different coordinates with different precision.
The other two components are discussed later.
STEPS IN COMPRESSION
The usual steps involved in compressing an image are.
1. Specifying the rate (bits available) and distortion (tolerable
error) parameters for the target image.
2. Dividing the image data into various classes, based on their
importance.
3. Dividing the available bit budget among these classes such that
the distortion is a minimum.
4. Quantize each class separately using the bit allocation
information.
5. Encode each class separately using an entropy coder and write
to the file.
Bit allocation
The first step in compressing an image is to segregate the image data in to different classes. Depending on the importance of the data it contains, each class is allocated a portion of the total bit budget, such that the compressed image has the minimum possible distortion. Then procedure is called bit allocation. The Rate Distortion theory is often used for solving the problem of allocating bits to a set of classes, or for bit rate control in general. The theory aims at reducing the distortion for a given target bit rate, by optimally allocating bits to the various classes of data. One approach to solve the problem of optimal bit allocation using Rate Distortion theory is explained below.
1. Initially, all classes are allocated a predefined maximum numbers of bits.
2. For each class, one bit is reduced from its quota of allocated bits, and the distortion due to the reduction of that one bit is calculated.
3. Of all the classes, the class with minimum distortion for a reduction of 1 bit is noted, and 1 bit is reduced from its quota of bits.
4. The total distortion for all classes D is calculated.
5. The total rate for all the classes is calculated as R = p (i) *
B (i), where p is the probability and B is the bit allocation for each
class.
6. Compare the target rate and distortion specifications with the values obtained above. If not optimal, go to step 2.
Here we keep on reducing one bit at a time till we achieve optimality either or distortion or target rate, or both.Classifying image data.
An image is represented as a two dimensional array of coefficients, each coefficient representing the brightness level in that point. When looking from a higher perspective, the coefficients cannot be differentiated as more important one, and lesser important one. But most natural images have smooth colour variations, with the fine details being represented as sharp edges in between the smooth variations. Technically, the smooth variations in colour can be termed as low frequency variations and the sharp variations as high frequency variations.
The low frequency components constitute the base of an image and the high frequency components add upon them to refine the image thereby giving a detailed image. Hence the smooth variations are demanding more importance than the details. Separating the smooth variations and details of the image can be done in many ways. One such way is the decomposition of the image using Discrete Wavelet Transform (DWT).
DWT of an image
A low pass filter and a high pass filter are chosen, such that they exactly halve the frequency range between themselves. The filter pass is called the analysis filter pair. First the low pass filter is applied for each row of data, thereby getting the low frequency components of the row. But since the low pass filter is a half band filter, the output data contains frequencies only in the first half of the original frequency range. So they can be subsampled by two, so that the output data now contains only half the original number of samples. Now the high pass filter is applied for the same row of data, and similarly the high pass components are separated and placed by the side of the low pass components. This procedure is done for all rows.
Next, the filtering is done for each column of the intermediate data. The resulting two dimensional array of coefficients contains four bands of data, each labeled as LL(low Low), HL (highlow), LH (Low High) and HH (HighHigh). The LL band can be decomposed once again in the same manner, thereby producing even more subbands. This can be done up to any level, thereby resulting in a pyramidal decomposition as shown.
The LL band at the highest level can be classified as most important and the other detail bands can be classified as of lesser importance, with the degree of importance decreasing from the top of the pyramid to the bands at the bottom.
FIGURE 2
Inverse DWT of an image.
Just as a forward transform is used to separate the image data into various classes of importance a reverse transform is used to reassemble the various classes of data into a reconstructed image. A pair of high pass and low pass filters is used here also. Then filter pair is called the synthesis filter pair. The filtering procedure is just the opposite. We start from the topmost level, apply the filters coloumnwise first and then rowwise and proceed to the next level, till we reach the first level.
Quantization
Quantization refers to the process of approximating the continuous set of values in the image data with a finite set of values. The input to a quantizer is the original data, and the output is always one among a finite number of levels. The quantizer is a function whose set of output values are discrete, and usually finite. Obviously, this is a process of approximation, and as good quantizer is one which represents the original signal with minimum loss or distortion.
A quantizer can be specified by its input partitions and output levels. If the input range is divided into levels of equal spacing, then the quantizer is termed as a uniform quantizer, and if not, it is termed as a nonuniform quantizer. A uniform quantizer can be easily specified by its lower bound and step size. Also, implementing a uniform quantizer is easier than a nonuniform quantizer.
In a uniform quantizer, if the input falls between n*r and (n=1)*r, the quantizer out put the symbol n.
FIGURE 3 UNIFORM QUANTIZER
Just the same way a quantizer partitions its input and outputs discrete levels, a dequantizer is one which receives the output levels of a quantizer and converts them into normal data, by translating each level into a reproduction point in the actual range of data.
The optimum quantizer (encoder) and optimum dequantizer (decoder) must satisfy the following conditions.
Given the output levels or partitions of the encoder, the best decoder is one that puts the reproduction parts x1 on the centers of
mass of the partitions. This is known as centered condition.Given the reproduction points of the decoder, the best encoder is one that puts the partition boundaries exactly in the middle of the reproduction points i.e., each x is translated to its nearest reproduction point. This is known as nearest neighbor condition.
The quantization error (xx1) is used as a measure of the optimality of the quantizer and dequantizer.
Entropy coding
After the data has been quantized in to a finite set of values, it can be encoded using an entropy coder to give additional compression. Entropy means the amount of information present in the data, and an entropy coder encodes the given set of symbols with the minimum number of bits required to represent them.
Two of the most popular entropy coding schemes are Huffman coding and Arithmetic coding.
CHIP PROVIDES WAVELET TRANSFORMS
Analog Devices have developed a family of general purpose waveletcodec chips. The latest chip, ADV6OLIC, claims to accommodate compression ratios from visually lossless to as great as 350to1. Figure below shows the architecture of the chip.
FIGURE 4 ARCHITECTURE OF ADV601LC
In waveletbased compression processing, the silicon area needed for compression is the same as the area needed for decompression. In contrast, other compression techniques require more work and special circuitry to compress than to decompress a signal. The ADV60ILC accepts component digital video through its video interface and delivers a compressed video stream through its host interface in encode mode .In decode mode, the IC accepts a compressed bit stream through its host interface and delivers component digital video through its video interface.TheADV60ILC compresses images by filtering the video into 42 separate frequency bands. The chip then optimizes each band to include only frequencies the naked eyes can discern. Because the eye lacks sensitivity at high frequencies, this is no reason to compress and store this information.
ADVANTAGES
Wavelet video processing technology offers some enticing features
1. The high image compression ratios reduces the hard disk storage capacity for real time recording and for archival storage
2. it has higher resolution than DCT based JPEG and MPEG
3. it facilitates efficient post processing to even further compress the already â€œcompressed images for archival storage.
4. In magnification mode images can be enlarged almost to infinity without the pixelation effects that accompany linear zooms.
5. The compressed video file cannot be edited
6. Because wavelet transforms compress the entire frame, any change makes it impossible to decompress the image. This aspect is important for courtroom evidence.Wavelet processing captures every image and creates a mathematical map of the entire image from which it can be determined whether the image has undergone alternations
APPLICATIONS
1. JPEG2000 uses wavelet transforms to compress images
2. MPEG4 uses wavelet tiling to allow the division of images into several tiles, each with separate encoding
3. Kallix corp. uses wavelet technology in to video surveillance systems
CONCLUSION
Waveletbased coding provides substantial improvement in picture quality at low bit rates because of overlapping bases function and better energy compaction property of wavelet transforms. Because of the inherent multi resolution nature wavelet based codes facilitate progressive transmission of images thereby allowing variable bit rates. The JPEG2000 standard incorporates wavelet technology. Interesting issues like obtaining accurate models of images, optimal representations of such models and rapidly computing such optimal representation are the grand challenges facing the data compression community. Interaction of harmonic analysis with data compression, joint source channel coding, image coding based on models of human perception, scalability robustness, error resilience, and complexity are a few of the many outstanding challenges in image coding to be fully resolved and may affect image data compression performance in the years to come.
BIBLIOGRAPHY
1. Bill Travis, Wavelets both implode and explode images, EDN, December 2000
2. Raghuveer.M.Rao and Ajit.S.Bopardikar, Wavelet Transforms, Introduction to theory and applications, Pearson Education Asia.
3. Jaideva.C.Goswami and Andrew.K.Chan,Fundamentals of wavelets,theory,algorithms and application, Wiley Interscience Publication.
4. Chan.Y.T,Wavelet basics, Kluwer Academic Publishers.
5. http:/engineering.rowan.edu/~polikar/WAVELETS/WTtutorial.html
ABSTRACT
The biggest obstacle to the multimedia revolution is digital obesity. This is the blot that occurs when pictures, sound and video are converted from their natural analog form into computer language for manipulation or transmission. In the present explosion of high quality data, the need to compress it with less distortion of data is the need of the hour. Compression lowers the cost of storage and transmission by packing data into a smaller space.
One of the hottest areas of advanced form of compression is wavelet compression. Wavelet Video Processing Technology offers some alluring features, including high compression ratios and eye pleasing enlargements.
CONTENTS
1. INTRODUCTION
2. IMAGE COMPRESSION
3. IMAGE COMPRESSION SYSTEM
 Steps in compression
 Bit allocation
 Classifying image data
 DWT of an image
 Inverse DWT of an image
 Quantization
 Entropy coding
4. CHIP PROVIDES WAVELET TRANSFORMS
5. ADVANTAGES
6. APPLICATIONS
7. CONCLUSION
8. BIBLIOGRAPHY
ACKNOWLEDGEMENT
I extend my sincere gratitude towards Prof. P.Sukumaran Head of Department for giving us his invaluable knowledge and wonderful technical guidance. I express my thanks to Mr. Muhammed Kutty our group tutor and
also to our staff advisor Ms. Biji Paul for their kind cooperation and guidance for preparing and presenting this seminar.
I also thank all the other faculty members of AEI department and my friends for their help and support.
INTRODUCTION
Uncompressed multimedia data requires considerable storage capacity and transmission bandwidth. Despite rapid progress in mass storage density processor speeds and digital communication system performance, demand for data storage capacity and data transmission bandwidth continues to outstrip the capabilities of available technologies. The recent growth of data intensive multimediabased web applications have not only sustained the need for more efficient ways to encode signals and images but have made compression of such signals central to storage and communication technology.
For still image compression, the joint photographic experts group (JPEG) standard has been established. The performance of these codes generally degrades at low bit rates mainly because of the underlying blockbased Discrete cosine Transform (DCT) scheme. More recently, the wavelet transform has emerged as a cutting edge technology, within the field of image compression. Wavelet based coding provides substantial improvements in picture quality at higher compression ratios. Over the past few years, a variety of powerful and sophisticated wavelet based schemes for image compression have been developed and implemented. Because of the many advantages, the top contenders in JPEG2000 standard are all wavelet based compression algorithms.
IMAGE COMPRESSION
Image compression is a technique for processing images. It is the compressor of graphics for storage or transmission. Compressing an image is significantly different than compressing saw binary data. Some general purpose compression programs can be used to compress images, but the result is less than optimal. This is because images have certain statistical properties which can be exploited by encoders specifically designed for them. Also some finer details in the image can be sacrificed for saving storage space.
Compression is basically of two types.
1. Lossy Compression
2. Lossless Compression.
Lossy compression of data concedes a certain loss of accuracy in exchange for greatly increased compression. An image reconstructed following lossy compression contains degradation relative to the original. Often this is because the compression scheme completely discards redundant information. Under normal viewing conditions no visible is loss is perceived. It proves effective when applied to graphics images and digitized voice.
Lossless compression consists of those techniques guaranteed to generate an exact duplicate of the input data stream after a compress or expand cycle. Here the reconstructed image after compression is numerically identical to the original image. Lossless compression can only achieve a modest amount of compression. This is the type of compression used when storing data base records, spread sheets or word processing files.
IMAGE COMPRESSION SYSTEM
A typical lossy image compression system consists of three closely connected components namely.
(a) Source encoder
(b) Quantizer
© Entropy encoder
FIGURE 1 IMAGE COMPRESSION SYSTEM
Source encoder
This is a linear transformer in which the given signal or image is transformed to a different domain. Compression using wavelet transforms belongs to a class of technique called transform coding. The objectives of transform coding are
I) To create a representation for the data in which there is less correlation among the coefficient values. This called decorrelating the data.
II) To have a representation in which it is possible to quantize different coordinates with different precision.
The other two components are discussed later.
STEPS IN COMPRESSION
The usual steps involved in compressing an image are.
1. Specifying the rate (bits available) and distortion (tolerable error) parameters for the target image.
2. Dividing the image data into various classes, based on their importance.
3. Dividing the available bit budget among these classes such that the distortion is a minimum.
4. Quantize each class separately using the bit allocation information.
5. Encode each class separately using an entropy coder and write to the file.
Bit allocation
The first step in compressing an image is to segregate the image data in to different classes. Depending on the importance of the data it contains, each class is allocated a portion of the total bit budget, such that the compressed image has the minimum possible distortion. Then procedure is called bit allocation.
The Rate Distortion theory is often used for solving the problem of allocating bits to a set of classes, or for bit rate control in general. The theory aims at reducing the distortion for a given target bit rate, by optimally allocating bits to the various classes of data. One approach to solve the problem of optimal bit allocation using Rate Distortion theory is explained below.
1. Initially, all classes are allocated a predefined maximum numbers of bits.
2. For each class, one bit is reduced from its quota of allocated bits, and the distortion due to the reduction of that one bit is calculated.
3. Of all the classes, the class with minimum distortion for a reduction of 1 bit is noted, and 1 bit is reduced from its quota of bits.
4. The total distortion for all classes D is calculated.
5. The total rate for all the classes is calculated as R = p (i) * B (i), where p is the probability and B is the bit allocation for each class.
6. Compare the target rate and distortion specifications with the values obtained above. If not optimal, go to step 2.
Here we keep on reducing one bit at a time till we achieve optimality either or distortion or target rate, or both.
Classifying image data
An image is represented as a two dimensional array of coefficients, each coefficient representing the brightness level in that point. When looking from a higher perspective, the coefficients cannot be differentiated as more important one, and lesser important one. But most natural images have smooth colour variations, with the fine details being represented as sharp edges in between the smooth variations. Technically, the smooth variations in colour can be termed as low frequency variations and the sharp variations as high frequency variations.
The low frequency components constitute the base of an image and the high frequency components add upon them to refine the image thereby giving a detailed image. Hence the smooth variations are demanding more importance than the details.
Separating the smooth variations and details of the image can be done in many ways. One such way is the decomposition of the image using Discrete Wavelet Transform (DWT).
DWT of an image
A low pass filter and a high pass filter are chosen, such that they exactly halve the frequency range between themselves. The filter pass is called the analysis filter pair. First the low pass filter is applied for each row of data, thereby getting the low frequency components of the row. But since the low pass filter is a half band filter, the output data contains frequencies only in the first half of the original frequency range. So they can be subsampled by two, so that the output data now contains only half the original number of samples. Now the high pass filter is applied for the same row of data, and similarly the high pass components are separated and placed by the side of the low pass components. This procedure is done for all rows.
Next, the filtering is done for each column of the intermediate data. The resulting two dimensional array of coefficients contains four bands of data, each labeled as LL(low Low), HL (highlow), LH (LowHigh) and HH (HighHigh). The LL band can be decomposed once again in the same manner, thereby producing even more subbands. This can be done up to any level, thereby resulting in a pyramidal decomposition as shown.
The LL band at the highest level can be classified as most important and the other detail bands can be classified as of lesser importance, with the degree of importance decreasing from the top of the pyramid to the bands at the bottom.
FIGURE 2
Inverse DWT of an image.
Just as a forward transform is used to separate the image data into various classes of importance a reverse transform is used to reassemble the various classes of data into a reconstructed image. A pair of high pass and low pass filters is used here also. Then filter pair is called the synthesis filter pair. The filtering procedure is just the opposite. We start from the topmost level, apply the filters coloumnwise first and then rowwise and proceed to the next level, till we reach the first level.
Quantization
Quantization refers to the process of approximating the continuous set of values in the image data with a finite set of values. The input to a quantizer is the original data, and the output is always one among a finite number of levels. The quantizer is a function whose set of output values are discrete, and usually finite. Obviously, this is a process of approximation, and as good quantizer is one which represents the original signal with minimum loss or distortion.
A quantizer can be specified by its input partitions and output levels. If the input range is divided into levels of equal spacing, then the quantizer is termed as a uniform quantizer, and if not, it is termed as a nonuniform quantizer. A uniform quantizer can be easily specified by its lower bound and step size. Also, implementing a uniform quantizer is easier than a nonuniform quantizer.
In a uniform quantizer, if the input falls between n*r and (n=1)*r, the quantizer out put the symbol n.
FIGURE 3 UNIFORM QUANTIZER
Just the same way a quantizer partitions its input and outputs discrete levels, a dequantizer is one which receives the output levels of a quantizer and converts them into normal data, by translating each level into a reproduction point in the actual range of data.
The optimum quantizer (encoder) and optimum dequantizer (decoder) must satisfy the following conditions.
Â¢ Given the output levels or partitions of the encoder, the best decoder is one that puts the reproduction parts x1 on the centers of mass of the partitions. This is known as centered condition.
Â¢ Given the reproduction points of the decoder, the best encoder is one that puts the partition boundaries exactly in the middle of the reproduction points i.e., each x is translated to its nearest reproduction point. This is known as nearest neighbor condition.
The quantization error (xx1) is used as a measure of the optimality of the quantizer and dequantizer.
Entropy coding
After the data has been quantized in to a finite set of values, it can be encoded using an entropy coder to give additional compression. Entropy means the amount of information present in the data, and an entropy coder encodes the given set of symbols with the minimum number of bits required to represent them.
Two of the most popular entropy coding schemes are Huffman coding and Arithmetic coding.
CHIP PROVIDES WAVELET TRANSFORMS
Analog Devices have developed a family of general purpose waveletcodec chips. The latest chip, ADV6OLIC, claims to accommodate compression ratios from visually lossless to as great as 350to1. Figure below shows the architecture of the chip.
FIGURE 4 ARCHITECTURE OF ADV601LC
In waveletbased compression processing, the silicon area needed for compression is the same as the area needed for decompression. In contrast, other compression techniques require more work and special circuitry to compress than to decompress a signal.
The ADV60ILC accepts component digital video through its video interface and delivers a compressed video stream through its host interface in encode mode .In decode mode, the IC accepts a compressed bit stream through its host interface and delivers component digital video through its video interface.TheADV60ILC compresses images by filtering the video into 42 separate frequency bands. The chip then optimizes each band to include only frequencies the naked eyes can discern. Because the eye lacks sensitivity at high frequencies, this is no reason to compress and store this information.
ADVANTAGES
Wavelet video processing technology offers some enticing features
1. The high image compression ratios reduces the hard disk storage capacity for real time recording and for archival storage
2. it has higher resolution than DCT based JPEG and MPEG
3. it facilitates efficient post processing to even further compress the already â€œcompressed images for archival storage.
4. In magnification mode images can be enlarged almost to infinity without the pixelation effects that accompany linear zooms.
5. The compressed video file cannot be edited
6. Because wavelet transforms compress the entire frame, any change makes it impossible to decompress the image. This aspect is important for courtroom evidence.Wavelet processing captures every image and creates a mathematical map of the entire image from which it can be determined whether the image has undergone alternations
APPLICATIONS
1. JPEG2000 uses wavelet transforms to compress images
2. MPEG4 uses wavelet tiling to allow the division of images into several tiles, each with separate encoding
3. Kallix corp. uses wavelet technology in to video surveillance systems
CONCLUSION
Waveletbased coding provides substantial improvement in picture quality at low bit rates because of overlapping bases function and better energy compaction property of wavelet transforms. Because of the inherent multi resolution nature wavelet based codes facilitate progressive transmission of images thereby allowing variable bit rates. The JPEG2000 standard incorporates wavelet technology. Interesting issues like obtaining accurate models of images, optimal representations of such models and rapidly computing such optimal representation are the grand challenges facing the data compression community. Interaction of harmonic analysis with data compression, joint source channel coding, image coding based on models of human perception, scalability robustness, error resilience, and complexity are a few of the many outstanding challenges in image coding to be fully resolved and may affect image data compression performance in the years to come.
BIBLIOGRAPHY
1. Bill Travis, Wavelets both implode and explode images, EDN, December 2000
2. Raghuveer.M.Rao and Ajit.S.Bopardikar, Wavelet Transforms, Introduction to theory and applications, Pearson Education Asia.
3. Jaideva.C.Goswami and Andrew.K.Chan,Fundamentals of wavelets,theory,algorithms and application, Wiley Interscience Publication.
4. Chan.Y.T,Wavelet basics, Kluwer Academic Publishers.
5. http:/engineering.rowan.edu/~polikar/WAVELETS/WTtutorial.html
CONTENTS
1. INTRODUCTION
2. IMAGE COMPRESSION
3. IMAGE COMPRESSION SYSTEM
Â¢ Steps in compression
Â¢ Bit allocation
Â¢ Classifying image data
Â¢ DWT of an image
Â¢ Inverse DWT of an image
Â¢ Quantization
Â¢ Entropy coding
4. CHIP PROVIDES WAVELET TRANSFORMS
5. ADVANTAGES
6. APPLICATIONS
7. CONCLUSION
8. BIBLIOGRAPHY
ACKNOWLEDGEMENT
I extend my sincere gratitude towards Prof. P.Sukumaran Head of Department for giving us his invaluable knowledge and wonderful technical guidance.
I express my thanks to Mr. Muhammed Kutty our group tutor and also to our staff advisor Ms. Biji Paul for their kind cooperation and guidance for preparing and presenting this seminar.
I also thank all the other faculty members of AEI department and my friends for their help and support. 
