 Open Access
 Total Downloads : 298
 Authors : Sukhi S, Rafeekha M J
 Paper ID : IJERTV3IS030589
 Volume & Issue : Volume 03, Issue 03 (March 2014)
 Published (First Online): 18032014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
High Speed Arithmetic Coder Architecture used in SPIHT
Sukhi S1, Rafeekha M J2
1PG scholar, Dept of Electronics and Communication Engineering, TKM Institute Of Technology, Kollam, Kerala, India, 2Assistant Professor, Dept of Electronics and Communication Engineering, TKM Institute Of Technology, Kollam, Kerala, India
Abstract Arithmetic coding (AC) method can obtain optimal performance for its ability to generate codes with fractional bits. It is widely used in various image compression algorithms. The set partitioning in hierarchical trees (SPIHT) uses an AC method to improve its peak signaltonoise ratio (PSNR) about 0.5 db. SPIHT is a very powerful image compression technique, very fast among the best image compression algorithm. In this algorithm three ordered lists are used to store the significant information during set partitioning. As the algorithm proceeds, data are ma nipulated between three lists namely, the list of insignificant pix els (LIP), the list of insignificant sets (LIS) and the list of signifi cant pixels (LSP). The LIP contains the pixels which on compari son with the threshold fall below it and are considered insignifi cant during that pass. LIS contains sets of wavelet coefficients which are defined by tree structures, and which had been found to have magnitude smaller than a threshold. Set Partitioning in Hierarchical Trees (SPIHT) algorithm for image compression is proposed with an arithmetic coder thereby it compresses the Discrete Wavelet Transform decomposed images. SPIHT has straightforward coding procedure and requires no tables which make a SPIHT algorithm an appropriate one for low cost hard ware implementation. In order to avoid rescanning the wavelet transformed coefficients, a breadth first search SPIHT without lists is used instead of SPIHT with lists. With the help of Breadth First search high speed architecture is achieved. The coding is done in VHDL language, synthesized using Xilinx ISE 13.2 and simulated using ISim.
Keywords Arithmetic coding, Common bit detection (CBD) circuit, Discrete wavelet transform (DWT), Set Partitioning in Hierarchical Trees (SPIHT)

INTRODUCTION
Nowadays, the size of storage media increases day by day. Although the largest capacity of hard disk is about two Tera bytes, it is not enough large if we store a video file without compressing it[1]. For example, if we have a colour video file stream, that is, with three 720×480 sized layer, 30 frames per second and 8 bits for each pixel. Then the storage space can be obtained as 720* 480* 3* 8* 30= 249Mbit/s. This equals about 31.1MB per second. For a 650MB CDROM, we can only store a video of about 20 seconds long. That is why we want to do image and video compression though the capacity of storage media is quite large now. The motivation of data compression is using less quantity of data to represent the original data without distortion.
Consider the system in Fig. 1. when the encoder receives the target image, it converts the image into bit stream. On the other hand, the decoder receives the bit stream and then con
verts it back to the image. If the quantity of bit stream is less than that of the original image then we call this process as
Image Compression Coding.
Fig.1.Fundamental of image compression
Now, we want to know how and why we can make an image compressed. Generally speaking, the neighbouring pixels in an image have highly correlation to each other. That is why images can be compressed in a high compression ratio. Com pression ratio is the ratio of the orginal uncompressed image file to the compressed file[2].
Compression Ratio= Uncompressed file Size
Compressed File Size (1) Two fundamental components of compression are redun dancy and irrelevancy reduction. Redundancy reduction aims at removing duplication from the signal source (image/video). Irrelevance reduction omits only those parts of the signal that are not noticed by the signal receiver. In general, three types of redundancies that can be identified namely; Spatial Redun dancy or correlation between neighboring pixel values. Spec tral redundancy or correlation between different colorplanes or spectralbands. Temporal redundancy or correlation be tween adjacent frames in a sequence of images especially in video applications. Compression techniques are classified into two namely lossy compression and lossless compression. Lossless compression technique guarantees the exact duplica tion of input in compress/decompress cycle. This is mainly used in medical applications[3]. Methods for lossless image compression are: Runlength encoding, DPCM, Predictive Coding and Entropy encoding. With Lossy compression tech nique higher levels of data reduction is possible but it results in less perfect reproduction of the original image. This is use ful in applications such as broadcast television, videoconfer encing, and facsimile transmission, in which a certain amount of error is acceptable tradeoff for increased compression per
formance. Methods for lossy image compression are: Reduc ing the color space to the most common colours in the image, chroma subsampling, transform coding, and fractal compres sion. Block diagram of image compression technique is shown in figure.2.
Fig.2.Block diagram of image compression technique
Generally a compression system consists of encoder and decoder stages. Encoder consists of the mapper, quantizer and encoder. Mapper transforms the input image into a format by reducing the interpixel redundancies. Quantizing refers to a reduction of the precision of the floating point values of the wavelet transform. A symbol encoder further compresses the quantized values to give a better overall compression. It uses a model to accurately determine the probabilities for each quan tized value and produces an appropriate code based on these probabilities so that the resultant output code stream will be smaller than the input stream. An arithmetic coder or Huffman coder is used as symbol encoders. Decoder part of the com pression model consists of symbol decoder and inverse map per[4][5]. Among these FPGAs are best suited to implement image processing algorithms because they offers features like infinite reprogram ability, high parallelism, flexibility, compu tational power and short development time.

LITERATURE REVIEW.

Set Partitioning In Hierarchical Trees Algorithm
SPIHT is an image compression algorithm with lists to store the significant information of wavelet coefficients for image coding purpose[6]. It mainly uses three different lists, namely List of Significant Pixels(LSP),List of Insignificant sets(LIS) and list of Insignificant pixels(LIP). In SPIHT algo rithm initially all wavelet coefficients are considered as insig nificant sets and these sets are placed in the list called LIS. Wavelet coefficients in LIS are compared with a predefined threshold if the wavelet coefficient value is greater than the predefined threshold then they are placed in the list called LSP and if the value is lesser than the predefined threshold then the wavelet coefficients are placed in the list called LIP. All the pixel values in the list LIS are tested for there significant state. Significant state of the wavelet coefficients are tested using the equation (2) which is as given below. So, this the reason why SPIHT algorithm less bits to code after the discrete wave let transform [7].
(2)
Where Ci,j represents the coefficient value for the position i,j in the wavelet subband. represents set of coefficients and Sn() represents the significan state of the set. Flow diagram of SPIHT is shown in figure.3.
Fig.3.Flow diagram of SPIHT

Discrete Wavelet Transform
A Discrete Wavelet Transform is a wavelet transform in which wavelets are discretely sampled. If Discrete Wavelet Transform is compared with the Fourier Transform it has an advantage of temporal resolution which captures both fre quency and location information. A wave is an oscillating function of time or space and is periodic. In contrast, wave lets are localized waves. Wavelets have their energy concen trated in time and they are used for analysis of transient sig nals. Wavelet transform uses wavelets of finite energy whereas the Fourier Transform and short Time Fourier Transform uses wavelets of finite energy.
Fig.4.Block diagram of DWT
III .PROPOSED METHOD
The main objective of this method is to designed and implemented a SPIHT Encoding Coder for Lossy virtual Images. Embedded Zero Tree Wave let algorithm (EZW) used here is simple, specially designed for wavelet transform and effective image compression algorithm. This algorithm is devised by Shapiro and it has property that the bits in the bit stream are generated inorder of importance, yield ing a fully embedded code. SPIHT stands for Set Partitioning in Hierarchical Trees. The SPIHT coder is a highly refined version of the EZW algo rithm and is a powerful image compression algo rithm that produces an embedded bit stream from which the best reconstructed images. The SPIHT algorithm was powerful, efficient and simple image compression algorithm. By using these algorithms, the highest PSNR values for given compression ra tios for a variety of images can be obtained.

System architecture
The block diagram of the SPIHT encoding is as shown in the Fig.5. The input image is gray scale image of size 512×512 each pixel of 8 bits. The transformed wavelet coefficients are placed in a buffer and they are accessed in a SPIHTBreadth First Search way. Processor dispatcher dispatches the transformed wavelet coefficients to the arithme tic coder through internal bus.
Fig.5. Block diagram of SPIHT encoding
Output of arithmetic coder is provided to the internal bus and sent to the code FIFO. The Read FIFO and Truncate module are responsible for the final code stream formation, which reads each code FIFO from top to bottom and truncates the code stream according to the bit rate requirement.

Line Based Lifting Wavelet Engine
Lifting step scheme consists of three simple phases: the first step, or Lazy wavelet, splits the data into two subsets: even and odd; the second step calculates the wavelet coeffi cients (highpass) as the failure to predict the odd set based on
the even set; finally the third step updates the even set using the wavelet coefficients to compute the scaling function coef ficients (lowpass). The predict phase ensures polynomial cancellation in the highpass, and the update phase ensures preservation of moments in the lowpass. In folded architec ture the output of processing element is fed back through the delay registers. By adding different number of delay registers and coefficients of processing elements folded architecture based lifting scheme can be used to design different wavelets. Folded architecture for (9, 7) wavelet with line based lifting wavelet engine is as shown in Fig.3. Coefficients for (9, 7) are
0.5 and 0.25which are represented by a, b, c, d. Two delay registers (D) are used in order to schedule the data in each phase. Based on the phase of interleaved computation, the coefficient for multiplier M1is either a or c or similarly the coefficient for multiplier M2 is b or d. Critical path in this folded architecture is reduced[8].
Fig.6. Architecture of Lifting based Wavelet Engine
Fig.7. illustrates the steps for performing a twolevel DWT on an image. The 1D DWT is first performed on the rows of the image producing lowfrequency L1 and highfrequency com ponents H1. After performing a 1D DWT again on the col umns of and the first level of decomposition is completed LL1, LH1, HL1 and HH1 are obtained.
Fig.7. Applying DWT on an image

2D DWT Architecture
The computation style of the entropy coder after DWT will affect thc optimal scheduling of the 2D DWT computation. Fig.8. shows the simplified JPEG2000 functional block dia gram. Embedded Block Coding with Optimized Truncation (EBCOT) is a blockcoding engine. Images after DWT are decomposed into many subbands. Every subband is then partitioned into codeblocks. EBCOT processes these quan tized wavele coefficients codeblock by code block. After
Tier 1 compression of EBCOT every codeblock will gener ate a subbitstream.
Fig.8. functional block diagram of Simplified JPEG2000
To extend the ID DWT core to compute 2D DWT in JPEG2000 two cases are considered. First.if' a frame memory is necessary and has already existed before DWT operation. The data of the whole image are assumed to be stored in the memory. Although 2D DWT can be scheduled to calculate all rows first (horizontal ID DWT) and then all columns (vertical ID DWT). it is possible to start the EBCOT computation once there is a complete codeblock data available. Due to the in place computing capability of lifting scheme the original samples can be replaced directly by the calculated coeffi cients. Hence, the original framesize memory is enough. The advantage of this implementation is the ease of data flow con trol. Due to the interleaving characteristics of the output. i.e one low pass sample followed by, one high pass sample.The interleaving storage arrangement is illustrated by an example of a 4 X 4 image show in Fig. 8. An address generator (AG) is needed to provide the proper access addresses to read sam ples for nest level wavelet decomposition and then write back. The block diagram of the JPEG 2000 system is shown in Fig.
10. T h e frame memory is used for the storage of the data for DWT, and also for the entropy coded subbitstreams of each codeblock after EBCOT.
Fig.9. Examplc of 2level wavelet transform shows the inplace interleaving organization of wavelet coefficients. where a circle represents a pixel.
Second, if a f'rame memory is not available or not allowed due to the constraint on the cost memory size. Then the con cept of linebased DWT can be adopted. Since EBCOT is not linebased, the height of the line buffer will depend on the height of the codeblock. The required buffer size for DWT will be smaller than the frame memory.
Fig.10. JPEG 2000 system Block diagram

Principle of arithmetic coding
Arithmetic coding is a variablelength source encoding technique [7]. In traditional entropy encoding techniques such as Huffman coding, each input symbol in a message is substi tuted by a specific code specified by an integer number of bits. In arithmetic coding a sequence of input symbols is repre sented by an interval of real numbers between 0.0 and 1.0. More probable symbols reduce the interval less than the less probable symbols and hence add fewer bits in the encoded message. As a result, the coding result can reach to Shannons entropy limit for a sufficiently large sequence of input sym bols as long as the statistics are accurate. In arithmetic coding uses three registers namely low, high and range. Cumulative frequency is defined as the cumulative counts of the symbol
i. If current interval is given by (low, high) then the values of range, low and high are calculated using the formula as given in equation.
Range =HighLow+1
High =Low+Range*[cum_freq[i1]/cum_freq[0]] Low =Low+Range*[cum_freq[i]/cum_freq[0]] (3)
Where cum_freq[i] represents the cumulative frequency of the symbol.Arithmetic coding is a wellknown method for lossless data compression. Arithmetic coding is a compression tech nique that can give compression levels at very near entropy .

SPIHT Algorithm
SPIHT i a waveletbased image compression coder. It first converts the image into its wavelet transform and then transmits information about the wavelet coefficients. The decoder uses the received signal to reconstruct the wavelet and performs an inverse transform to recover the image. We selected SPIHT because SPIHT and its predecessor, the em bedded zerotree wavelet coder, were significant break throughs in still image compression in that they offered sig
nificantly improved quality over vector quantization, JPEG, and wavelets combined with quantization, while not requiring training and producing an embedded bit stream. SPIHT dis plays exceptional characteristics over several properties all at once [8] including:

Good image quality with a high PSNR

Fast coding and decoding

A fully progressive bitstream

Can be used for lossless compression

May be combined with error protection

Ability to code for exact bit rate or PSNR
Fig.11. Flow Chart of SPIHT algorithm
SPIHT codes a wavelet by transmitting information about the significance of a pixel. By stating whether or not a pixel is above some threshold, information about that pixels value is implied. Furthermore, SPIHT transmits information stating whether a pixel or any of its descendants are above a threshold. If the statement proves false, then all of its descendants are known to be below that threshold level and they do not need for computation. In addition to transmitting wavelet coeffi cients in a implementation, for both the encoder and decoder since the order must be calculated for each image. Bit plane ordering, the SPIHT algorithm develops an individual order to transmit information within each bit plane. The ordering is implicitly created from the threshold information discussed above and by a set of rules which both the encoder and de coder agree upon. Thus each image will transmit wavelet co efficients in an entirely different order. Slightly better peak signal to noise ratio (PSNR) are achieved by using this dy namic ordering of the wavelet coefficients[9]. The tradeoff for the improvement is increased runtimes, in a hardware considered during the rest of the current pass. At the end of each pass the threshold is divided by two and the algorithm continues. By proceeding in this manner, information about the most significant bits of the wavelet coefficients will al ways precede information on lower order significant bits, which is referred to as bit plane ordering. Within each bit plane data is transmitted in three lists: the list of insignificant pixels (LIP), the list of insignificant sets (LIS) and the list of significant pixels (LSP).


Architecture of arithmetic coder
The architecture of arithmetic coder is as shown in Fig.5. Arithmetic coder consists of three main parts, upper and lower bound update, and common bit detector. The tree construction part visits the wavelet coefficients by the breadth first search order. For speedup, all valid bitplanes are scanned in parallel. Significant wavelet coefficients are provided as input to the arithmetic coder.
Fig.12. Architecture of arithmetic coder
Upper bound and lower bound update units in arithmetic coder are used for updating the initial intervals to 0 and 1. High and low values are multiplied with cumulative probabili ties and updated high and low values are given as input to common bit detector unit. Output is then passed to the code stream output unit in arithmetic coder. Cumulative probability part will hold the frequency of occurrence of wavelet coeffi cient. Upper bound and lower bound update units in arithmetic coder are implemented with carry look ahead adder and float ing point multiplier.

Upper Bound and Lower Bound Update
Upper bound and lower bound update registers consists of Look ahead adder and Fast array multiplier. The calculation units for upper and lower bound update units are as shown in the Fig.13. Output of upper and lower update units are new_low and new_ high. For speed up purpose, a Carry Look Ahead adder and a floating point multiplier are employed to reduce the delay of critical path. The cumulative probabilities cum_ freq [i] and cum_ freq [i1] are provided by the cumula tive probability module and this is accompanied by high and new values to compute new bounds for the probability interval these are calculated using the formula (3).
Fig.13. Calculation units for upper and lower update unit

Common bit detector
The internal structure of common bit detector is as shown in the Fig.7. The new bound values are then registered and connected to the common bit detector (CBD) part which un rolls the internal loop and records the same bits from the MSB to the LSB between two registers.
Fig.14. Internal Structure of common Bit Detector

SIMULATION RESULTS
The design of SPIHT algorithm with arithmetic coder is described in VHDL. Design and testing of individual module has been carried out. Fig.15.depicts the simulation results of lifting based DWT. The input to this module is the pixel val ues stored in 1D array. Output of this module is a trans formed coefficient.
Fig.17. Simulation result of lifting based DWT in MATLAB
Output of DWT is provided as input to SPIHT algorithm so the transformed wavelet coefficients are initially stored in the List of Insignificant Sets (LIS) now the wavelet coefficients in the LIS are compared with the threshold value if the wavelet coefficients are greater than the threshold then they are placed in List of significant pixels otherwise they are placed in List of Insignificant Pixels.
Output of SPIHTBreadth First Search algorithm is as shown in the Fig.18.
Fig.15. Simulation result of lifting based DWT
Fig.16. Simulation result of DWT in MATLAB
Fig.16. shows the simulation output of DWT in MATLAB software. Gray scale image of 512X512 is given as input.1D DWT is first applied on columns and then on the rows.
.
Fig.18. Simulation result of SPIHT algorithm
RTL Schematic view of SPIHTBreadth First Search algo rithm is as shown in the Fig.19. and Fig.20.
Fig.19. RTL Schematic view of SPIHT
Fig.20. RTL Schematic view of SPIHT
Fig.21. Simulation result of common bit detector
Fig.21. shows the simulation result of common bit detector module which unrolls the renormalization stage of arithmetic coder.
The Simulation result for SPIHT algorithm with arithme tic coder after integrating all the modules is as shown in Fig.22. The final output consists of code word generated which is of 8bits.
Fig.22. Simulation result of SPIHT algorithm with arithmetic coder after integration.

CONCLUSIONS


SPIHT is a very powerful image compression algorithm, widely used in real time applications. In the first phase Gray scale image of 512X512 is given as input. Convert this image into corresponding pixel values by using MATLAB and given to the arithmetic coder architecture. Arithmetic coder mainly consists of three modules .Upper bound modules, Lower bound module and a Common bit detector. Upper bound and lower bound update registers consists of Lookahead adder and Fast array multiplier. Output of this module updated low and high values which are provided as input to common bit detec tor. Common bit detector module which unrolls the renormali zation stage of arithmetic coder. Combine this coder with SPIHT algorithm .Compression of 4:1 is achieved in this ar chitecture so the memory occupied by Code word is reduced by four times when compared to the input with a bitrate of 8bpp. As a result smaller storage space is needed to store the encoded bitstream and it is easy to transmit encoded bit stream in lesser transmission bandwidth.
REFERENCES

H. Pan, W.C. Siu, and N.F. Law, A fast and low memory image coding algorithm based on lifting wavelet transfrm and modified SPIHT, Signal Process.: Image Commun., vol. 23, no. 3, pp. 146 161, Mar. 2008.

M. Akter, M. B. I. Reaz, F. MohdYasin, and F. Choong, A mod ifiedset partitioning in hierarchical trees algorithm for realtime image compression, J. Commun. Technol. Electron., vol. 53, no. 6, pp. 642650, Jun. 2008

A. A. Kassim, N. Yan, and D. Zonoobi, Wavelet packet transform basis selection method for set partitioning in hierarchical trees, J. Electron. Imag., vol. 17, no. 3, p. 033007, Jul. 2008.

M. Dyer, D. Taubman, and S. Nooshabadi, Concurrency tech nique for arithmetic coding in JPEG2000, IEEE Trans. Circuits Systems I, Reg. Papers, vol. 53, no. 6, pp. 12031213, Jun. 2006.

H. J. Ritter, Wavelet based image compression using FPGAs, Ph.D. dissertation, Martin Luther Univ., HalleWittenberg, Ger many, 2002.

R. Stefo, J. L. NÃºÃ±ez, C. Feregrino, S. Mahapatra, and S. Jones,
FPGABased modelling unit for high speed lossless arithmetic coding, FieldProgram. Logic Appl. Lecture Notes Comput. Sci., vol. 2147/2001, pp. 643647, 2001

JPEG2000 Part I Final Draft International Standard, ISO/IEC JTC1/ SC29/WG1 N1890, Sep. 2000..

F. W. Wheeler and W. A. Pearlman, SPIHT image compression without lists, in Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., Istanbul, Turkey, Jun. 2000, pp. 20472050.

A. Said and W. A. Pearlman, A new ,fast and efficient image co dec based on set partitioning in hierarchical trees, IEEE Trans. Circuits Syst. for Video Technol., vol. 6, no. 3, pp. 243249, Mar. 1996.