Design of Hybrid Compression Model using DWT-DCT-HUFFMAN Algorithms for Compression of Bit Stream

Design of Hybrid Compression Model using DWT-DCT-HUFFMAN Algorithms for Compression of Bit Stream

Dishant Khosla, Amandeep Kaur

Punjabi University, Patiala

Abstract

Digital image and video in their raw form require an enormous amount of storage capacity and the number of such applications is increasing day by day. Also the huge data systems also contain a lot of redundant information. As massive data transfer is taking place over communication links, compression of data to be stored or transmitted reduces storage space and transmission bandwidth as redundant information is removed. Compression also increases the capacity of the communication channel. Considering the important role played by digital imaging and video in todays world, it is necessary to develop a system that produces high degree of compression while preserving critical image or video information. In this paper, a video which is a combination of a number of still images or frames is divided into a number of frames to form a complete image. Here hybrid DWT-DCT- Huffman algorithm is used for compression and reconstruction of image generated by a combination of number of frames of the inputted video taking benefit from the advantages of all the three algorithms. The need of video divided into individual frame came from the fact that the video is a combination of number of frames displayed at a faster rate and we are not able to distinguish between individual frames. So video conversion process is used and also compression is performed on the generated image.

Keywords: Redundant, Discrete Wavelet Transform, Discrete Cosine Transform.

1. Introduction.

   With the growth of multimedia and Internet, compression techniques have become the thrust area in the fields of computers. Popularity of multimedia has led to integration of various types of computer data. Multimedia combines many data types like text, graphics, still images, animation, audio and video data. Many different data compression techniques currently exist for the compression of different types of data. Text compression requires regeneration for the original data from the compressed form in exactly the same form. Similarly, graphical data may also require the data to be same after decoding. Graphics, images, audio and video data require

   huge amount of storage [1]. This not only require large storage capacity, but, the uncompressed form of these data types require higher bandwidth for multimedia communication through computers or else the rate of data transfer is low making networks including Internet sluggish. Compression is one of the tools for better utilization of storage devices, resulting in saving of storage space. Compression techniques may also use more than one technique. For this, one method is applied first and encoded data so obtained undergoes another compression cycle using same or some other compression technique. With this higher compression rates can be achieved [5].

   In this paper, hybrid DWT-DCT-Huffman algorithm is used for compression and reconstruction taking benefit from the advantages of all the three algorithms. The algorithm performs the DCT on the DWT coefficients. DCT and DWT are the most commonly used transformation. DCT has high energy compaction property and requires less computational resources. On the other hand, DWT is mutli resolution transformation. Here Huffman algorithm is used as an entropy coding technique in which the source symbols which may be either the intensities of an image or the output of an intensity mapping operation are coded statically according to their occurrence. Short codes words are assigned to highly probable values and long code words to less probable values.The proposed scheme is intended to be used as the video compressor technique in imaging and video applications [4].

2. Overview of used Compression Algorithms.

   1. Discrete Wavelet Transform.

      Mathematically a wave is expressed as a sinusoidal (or oscillating) function of time or space. Fourier analysis expands an arbitrary signal in terms of infinite number of sinusoidal functions of its harmonics. Fourier representation of signals is known to be very effective in analysis of time- invariant (stationary) periodic signals. In contrast to a sinusoidal function, a wavelet is a small wave whose energy is concentrated in time. Properties of wavelets allow both time and frequency analysis of signals simultaneously because of the fact that the

      energy of wavelets is concentrated in time and still possesses the wave-like (periodic) characteristics. Wavelet representation thus provides a versatile mathematical tool to analyse transient, time-variant (non stationary) signals that may not be statistically predictable especially at the region of discontinuities a special feature that is typical of images having discontinuities at the edges [4].

      Wavelets are functions generated from one single function (basis function) called the prototype or mother wavelet by dilations (scalings) and translations (shifts) in time (frequency) domain. If the mother wavelet is denoted by t, the other wavelets a,b(t) can be represented as

      a,b(t) = (4.1)

      where a and b are two arbitrary real numbers. The variables a and b represent the parameters for dilations and translations respectively in the time axis. From Eq. 4.1, it is obvious that the mother wavelet can be essentially represented as

      (t) = 1,0(t) (4.2)

      For any arbitrary a 1 and b = 0, it is possible to derive that

      a,0(t) = (4.3)

      As shown in Eq. 4.3, a,0(t) is nothing but a time- scaled (by a) and amplitude-scaled (by ) version of the mother wavelet function (t) in Eq. 4.2. The parameter a causes contraction of (t) in the time axis when a < 1 and expansion or stretching when a

      > 1. Thats why the parameter a is called the dilation (scaling) parameter. For a < 0, the function a,b(t) results in time reversal with dilation. Mathematically, substituting t in Eq. 4.3 by t-b to cause a translation or shift in the time axis resulting in the wavelet function a,b(t)as shown in Eq. 4.1. The function a,b(t) is a shift of a,0(t) in right along the time axis by an amount b when b > 0 whereas it is a shift in left along the time axis by an amount b when b < 0. Thats why the variable b represents the translation in time (shift in frequency) domain.

      Fig.1shows an illustration of a mother wavelet and its dilations in the time domain with the dilation parameter a=. For the mother wavelet (t) shown in Fig.4(a), a contraction of the signal in the time axis when < 1 is shown in Figure 4(b) and expansion of the signal in the time axis when > 1 is shown in Figure 4(c). Based on this definition of wavelets, the wavelet transform of a function (signal) f(t) is mathematically represented by

      W(a,b) = a,b(t) dt (4.4) The inverse transform to reconstruct f(t) from W(a,b) is mathematically represented by

      f(t) = a,b(t) da db (4.5)

      where C = d and () is the Fourier transform of the mother wavelet (t) .

      Fig.1: (a) A mother wavelet, (b) (t/):0< < 1 , c)(t/) : >1

      If a and b are two continuous (non discrete) variables and f (t) is also a continuous function, W ( , ) is called the continuous wavelet transform (CWT). Hence the CWT maps a one-dimensional function f(t) to a function W(a,b) of two continuous real variables a (dilation) and b (translation) [11].

   2. Discrete Cosine Transform.

      Discrete Cosine Transform is the basis for many image and video compression algorithms, especially the still image compression standard JPE in lossy mode and the video compression standards MPEG-1, MPEG-2, and MPEG-4. Since an image is a two-dimensional signal, the two- dimensional DCT is relevant in terms of still image and video compression. The two dimensional DCT can be computed using the one-dimensional DCT horizontally and then vertically across the signal because DCT is a separable function [8].

      The DCT is a widely used transformation in transformation for data compression. It is an orthogonal transform, which has a fixed set of (image independent) basis functions, an efficient algorithm for computation, and good energy compaction and correlation reduction properties. Like other transforms, the Discrete Cosine Transform attempts to decorrelate the image data. After decorrelation each transform coefficient can be encoded independently without losing compression efficiency [11].

      • The One-Dimensional DCT.

        The most common DCT definition of a 1-D sequence of length N is

        C(u) = (u) (4.6)

        for u = 0,1,2,,N 1. Similarly, the inverse transformation is defined as

        f(x) = C(u) (4.7)

        for x = 0,1,2,,N 1. In both, Eq. 4.6 and 4.7 (u) is defined as

        (u) = (4.8)

        It is clear from Eq. 4.6 that for u = 0, C (u=0) = .

        Thus, the first transform coefficient is the average value of the sample sequence. In literature, this value is referred to as the DC Coefficient. All other transform coefficients are called the AC Coefficients. To fix ideas, ignore the f(x) and (u) component in Eq. 4.6. The plot of

        for N = 8 and varying values of u is shown in Fig. 2. In accordance with our previous observation, the first the top-left waveform (u = 0) renders a constant (DC) value, whereas, all other waveforms (u = 1,2,,7 ) give waveforms at progressively increasing frequencies. These waveforms are called the cosine basis function. Note that these basis functions are orthogonal. Hence, multiplication of any waveform in Fig. 2 with another waveform followed by a summation over all sample points yields a zero (scalar) value, whereas multiplication of any waveform in Fig. 2 with itself followed by a summation yields a constant (scalar) value. Orthogonal waveforms are independent, that is, none of the basis functions can be represented as a combination of other basis functions.

        If the input sequence has more than N sample points then it can be divided into sub-sequences of length N and DCT can be applied to these chunks independently. Here, a very important point to note is that in each such computation the values of the basis function points will not change.

        Fig. 2: One dimensional cosine basis function (N=8).

        Only the values of f(x) will change in each sub- sequence. This is a very important property, since it shows that the basis functions can be pre-computed offline and then multiplied with the sub-sequences. This reduces the number of mathematical operations (i.e. Multiplications and additions) thereby rendering computation efficiency [7].

      • The Two-Dimensional DCT.

      The 2-D DCT is a direct extension of the 1-D case and is given by

      C(u,v) = (u) (v)

      (4.9)

      for u,v = 0,1,2,,N 1 and (u) and (v) are defined in Eq. 4.8. The inverse transform is defined as

      f(x,y) =

      (4.10)

      for x,y = 0,1,2,,N 1.

      The 2-D basis functions can be generated by multiplying the horizontally oriented 1-D basis functions (shown in Fig. 2) with vertically oriented set of the same functions .The basis functions for N

      = 8 are shown in. Again, it can be noted that the basis functions exhibit a progressive increase in frequency both in the vertical and horizontal direction. The top left basis function of results from multiplication of the DC component in Fig. 2 with its transpose. Hence, this function assumes a constant value and is referred to as the DC coefficient [10].

      Fig. 3: Two dimensional DCT basis functions (N = 8). Neutral gray represents zero, white represents positive amplitudes, and black represents negative amplitude.

   3. Huffman Coding.

      The third compression algorithm we used is an important class of prefix codes known as Huffman codes. The basic idea behind Huffman coding is to assign to each symbol of an alphabet a sequence of bits roughly equal in length to the amount of information conveyed by the symbol in question. The end result is a source code whose average code-word length approaches the fundamental limit

      set by the entropy of a discrete memory less source, namely, H. The essence of the algorithm used to synthesize the Huffman code is to replace the prescribed set of source statistics of a discrete memory less source with a simpler one. This reduction process is continued in a step-by-step manner until we are left with a final set of only two source statistics (symbols), for which (0,1) is an optimal code. Starting from this trivial code, we then work backward and thereby construct the Huffman code for the given source [6].

      Specifically, the Huffman encoding algorithm proceeds as follows:

      1. The source symbols are listed in order of decreasing probability. The two source symbols of lowest probability are assigned a 0 and a 1. This part of the step is referred to as a splitting stage.

      2. These two source symbols are regarded as being combined into a new source symbol with probability equal to the sum of the two original probabilities. (The list of source symbols, and therefore source statistics, is thereby reduced in size by one). The probability of the new symbol is placed in the list in accordance with its value.

      3. The procedure is repeated until we are left with a final list of source statistics (symbols) of only two for which a 0 and a 1 are assigned [2].

      The code for each (original) source symbol is found by working backward and tracing the sequence of 0s and 1s assigned to that symbol as well as its successors. Huffman coding creates the optimal code for a set of symbols and probabilities subject to the constraint that symbols be coded one at a time. After code has been created decoding is accomplished in a simple lookup table manner. The code itself is an instantaneous uniquely decodable block code. Any string of Huffman encoded symbol can be decoded by examining the individual symbols of the string in a left to right manner. For a binary code a left to right scan of the encoded string 0100011011 reveals that the first valid code word is 010 which is code for symbol s3.

      Fig. 3: (a) Example of the Huffman encoding algorithm.

      (b) Source code

      The next valid code word is 00 which corresponds to symbol s0. Continuing in this manner reveals the completely decoded message s3 s0 s2 s4 [3].

      Average length of code word (Lavg) = 0.4(2) + 0.2(2) + 0.2(2) + 0.1(3) + 0.1(3) = 2.2

      Entropy (H) = 0.4 ) + 0.2 ) + 0.2 log2( ) + 0.1 ) + 0.1 ) = 2.12193

      bits.

3. Video Compression Process

   In this research work, compression is performed on an image generated from the video which is a sequence of still images and each still image representing one frame. This video is converted into an image which contains a number of frames in the sequence in which they appear in the video. The desired number of frames which make this image are being inputted by the user and then compression is performed on this generated image. Firstly DWT algorithm which is a multi resolution technique is applied on the generated image and the image obtained after applying DWT contains different resolutions by discarding the detail coefficients and taking only the approximate coefficients. Here the filter used is symlet with level 3 and its different parameters are also set accordingly. The image obtained after apply DWT is being further compressed by using DCT technique which shows high energy compaction characteristics. The image obtained after applying DCT is further compressed by using Huffman technique which provides compression while preserving image quality [11]. Here Huffman algorithm genrates codewords for each intensity value of pixel based on their probability and assigns shorter codewords to more frequently occurring symbols an longer codewords to less frequently occurring symbols and in turn provides compression. Here the simulation results show the image generated from the video with its histogram, the compressed image obtained by applying DWT with its histogram and the compressed image obtained by applying DCT with its histogram. The results also show the Mean Square Error and Peak Signal to Noise Ratio after applying DWT and DCT technique. The Huffman coding results show the gray level with its probability and Huffman code. In the end, the compression ratio is computed taking into account the actual size of the image and size of the Huffman image [9].

4. Simulation Results

   In the compression process firstly a video sample is read. The specifications of sample video used are:

   No of Frames = 121

   Size of video = 144 × 176 Video type = Coloured Video

   This video is converted into an image which contains a number of frames in the sequence in which they appear in the video. The desired number of frames which make this image are nFrames being inputted by the user.

   Now we select nFrames Case 1: nFrames = 25

   Actual size of Image = 5068800 bytes

   Fig. 4 shows the complete image generated from the video which consists of number of frames in the sequence in which they appear in the video being inputted by the user for a particular video input.

   .

   Fig. 4: Complete Image on which compression is to be performed

   After applying DWT on Video Image: Mean Square Error = 146.4944 db Peak Signal to Noise Ratio = 26.5066db

   Fig. 5: Complete Image and the compressed image after applying DWT and their Histograms

   Fig. 5 shows the complete image generated from the video with its Histogram and the image compressed after applying DWT with its Histogram.

   After applying DCT on Video Image: Mean Square Error = 1.1194e+003 db Peak Signal to Noise Ratio = 17.6749 db

   Fig. 6: Compressed Image after applying DWT together with the Image compression done on DWT Image by applying DCT and their Histograms

   Fig. 6 shows the image compressed after applying DWT with its Histogram and the image generated after applying DCT on the DWT compressed image with its Histogram.

   After applying Huffman algorithm on DCT compressed Image:

   The coding results of Huffman algorithm (gray level, probability, huffman code) are:

   Table 1: Huffman Coding results.

   Gray Code	Probability	Huffman Code
   [0]	[0.0259]	'00100'
   [1]	[0.0033]	'00110110'
   [2]	[0.0023]	'110100110'
   [3]	[0.0018]	'011100110'

   . . .

   . . .

   . . .

   [252]	[2.6989e-004]	'110001001011'
   [253]	[3.7405e-004]	'00010111010'
   [254]	[0.0023]	'110001111'

   Size of completely compressed image = 767259 bytes

   Compression Ratio = = 1.055110

   Case 2: nFrames = 49

   Actual size of Image = 9934848 bytes

   Fig. 7 shows the complete image generated from the video which consists of number of frames in the sequence in which they appear in the video being inputted by the user for a particular video input.

   Fig. 7: Complete Image on which compression is to be performed

   After applying DWT on Video Image: Mean Square Error = 150.1662 db

   Peak Signal to Noise Ratio = 26.3991 db

   Fig. 8 shows the complete image generated from the video with its Histogram and the image compressed after applying DWT with its Histogram.

   Fig. 8: Complete Image and the compressed image after applying DWT and their Histograms

   After applying DCT on Video Image: Mean Square Error = 1.4335e+003 db Peak Signal to Noise Ratio = 16.6010 db

   Fig. 9 shows the image compressed after applying DWT with its Histogram and the image generated after applying DCT on the DWT compressed image with its Histogram.

   After applying Huffman algorithm on DCT compressed Image:

   Fig. 9: Compressed Image after applying DWT together with the Image compression done on DWT Image by applying DCT and their Histograms

   The coding results of Huffman algorithm (gray level, probability, huffman code) are:

   Table 1: Huffman Coding results.

   Gray Level	Probability	Huffman codes
   [0]	[0.0161]	'100010'
   [1]	[0.0028]	'00000110'
   [2]	[0.0019]	'011111110'
   [3]	[0.0016]	'001110010'

   . . .

   . . .

   . . .

   [251]	[1.5944e-004]	'1111111111011'
   [252]	[1.5702e-004]	'1101011111111'
   [253]	[1.6508e-004]	'1111111111111'
   [254]	[6.5628e-004]	'11111001111'

   Size of completely compressed image = 9433641 bytes

   Compression Ratio = = 1.0531

5. Conclusion

   In this research work, a video which is a combination of a number of still images or frames is divided into a number of frames in the sequence in which they appear in the video to form a complete image. The number of frames being used to represent the image depends on the user. Then compression is performed on this image. Firstly DWT algorithm which is a multi resolution technique is applied on the generated image and the image obtained after applying DWT contains different resolutions by discarding the detail coefficients and taking only the approximate coefficients. Here the filter used is symlet with level 3 and its different parameters are also set accordingly. The image obtained after apply DWT

   Table 3: Compression ratio, PSNR, MSE results on different number of frames inputted for the Video Image.

   No of Frames in Video Image	MSE after DWT compression of Video Image	PSNR after DWT compression of Video Image (db)	MSE after DCT compression of DWT compressed Video Image	PSNR after DCT compression of DWT compressed Video Image (db)	Actual size of Video Image (bytes)	Compressed Video Image size (bytes)	Output of Huffman compressed Image /Compression Ratio
   4	124.0247	27.2297	446.7855	21.6638	811008	767259	1.0570
   9	135.8912	26.8329	560.7024	20.6775	1824768	1732214	1.0534
   16	142.0885	26.6392	598.8158	20.3919	3244032	3086297	1.0511
   25	146.4944	26.5066	1.1194e+003	17.6749	5068800	4804045	1.0551
   36	148.7417	26.4405	1.5162e+003	16.3572	7299072	6897192	1.0583
   49	150.1662	26.3991	1.4335e+003	16.6010	9934848	9433641	1.0531

   is being further compressed by using DCT technique which shows high energy compaction characteristics. The image obtained after applying DCT is further compressed by using Huffman technique which provides compression while preserving image quality. Here Huffman algorithm generates codewords for each intensity value of pixel based on their probability and in turn provides compression. Here the simulation results show the image generated from the video with its histogram, the compressed image obtained by applying DWT with its histogram and the compressed image obtained by applying DCT with its histogram. The results also show the Mean Square Error and Peak Signal to Noise Ratio after applying DWT and DCT technique. The Huffman coding results show the gray level with its probability and Huffman code. In the end, the compression ratio computed taking into account the actual size of the image and size of the Huffman image.

6. References

1. R. C. Gonzalez and R. E. Woods , Digital Image Processing Third Edition.

2. B. P. Lathi , Modern Digital and Analog Communication System Third Edition.

3. Simon Haykin , Communication Systems Fourth Edition.

4. A.K.Jain, Fundamentals of Digital Image Processing, Prentice-Hall Inc,Englewood Cliffs,1989.

5. W. B. Pennebaker and J. L. Mitchell, JPEG Still

   Image Data Compression Standard, 3rd ed. New York: Springer , 1993.

6. David A Huffman A Method for the Construction of Minimum Redundancy Codes, Proceedings of IRE, Vol. 40, no. 9, pp. 1098-1101, Sep. 1952.

7. N. Ahmed, T. Natarajan, K. R. Rao Discrete Cosine Transform, IEEE Transactions on Computers, Vol. C- 23, no. 1, pp. 9093, Jan. 1974.

8. S. M. Lei, M. T. Sun, K. Ramachandran and S. Palaniraj VLSI Implementation of an Entropy Coder and Decoder for Advanced TV Applications, IEEE International Symposium on Circuits and Systems, Vol. 4, pp. 3030-3033, May 1990.

9. S. M. Lei and M. T. Sun An Entropy Coding System for Digital HDTV Applications, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 1, no. 1, pp. 147-155, March 1991.

10. Andrew B. Watson Image Compression using Discrete Cosine Transform, Mathematical Journal, Vol. 4, no. 1, pp. 81-88, 1994.

11. Suchitra Shrestha and Khan Wahid Hybrid DWT- DCT Algorithm for Bio-Medical Image and Video Compression Applications, International Sciences Signal Processing and their Applications, pp. 280-283, 2010.