The University of Texas at El Paso
Senior Project II
Zero Loss: GIF Image Compression
Ivan E. Marquez
Noesis' goal is to implement the Lempel-Ziv-Welch (LZW) algorithm on a Field Programmable Gate Array (FPGA) chip in order to convert a raw image into the Graphic Interchange Format (GIF).
Many types of image compression are done solely through software applications. Zero Loss: GIF Image Compression consists of implementing the LZW algorithm on hardware, specifically on a FLEX 10k Field Programmable Gate Array (FPGA) chip from Altera. Software applications usually take up a great amount of space in the hard disks computers. Having the compression technique on hardware, enables the availability of more space in hard disk.
Method of Completion
Testing the LZW algorithm using the C programming language was critical in the implementation on hardware. First, the LZW algorithm was done on software so as to better understand the encoding and decoding processes. Using C, Noesis created a program in which a raw image was compressed into the GIF format. In addition, the decompression stage was included in order to compare the viewable image with the raw image. Diagram 1 below represents the general block diagram of the LZW algorithm.
Diagram 1. LZW General Block Diagram
Within the compression stage, a dictionary is created to assign single codes to repetitive patterns found in the raw image. In the decompression stage, the decoding process takes place by comparing the coded output to the created dictionary. The C program was completed during the first semester of senior project.
The C (software) design was then converted into a digital logic (hardware) design using the Signal Processing Worksystem (SPW). SPW is computer aided design software package which assisted in simulating and testing the hardware design. After the SPW design simulated succesfully, Verilog Hardware Description Language (Verilog HDL) and Synplicity were used to translate SPW blocks into Altera's Max Plus II. The following figure (Diagram 2) depicts Noesis' project overview:
Diagram 2. Project Overview
In the process of implementing the lzw algorithm, certain qualifications should have been attained. These included simulation of the algorithm using C, simulation of digital logic design using SPW, hardware implementation of entire design using Verilog/Max+Plus II and the FLEX 10K FPGA chip, and the comparison between the raw and viewable images. As far as completing all these requirements, the hardware implementation using the FPGA chip was not realized due to some problems encountered at the end of Senior Project II. Diagram 3 corresponds to the actual progress of our project.
Diagram 3. Project Progress
The green block refers to the completed SPW hardware design which was successfully simulated and tested. The yellow blocks symbolize the stages were problems were encountered when synthesizing SPW blocks and using them in Max Plus II. The process to resolve some of these issues was extremely tedious and time consuming. Therefore, because of lack of time, it was opted to improve the SPW design by enhancing some of its blocks in order to obtain better results when compressing and decompressing sample images. And obviously, the hardware implementation into the FPGA, shown in the red block, was not achieved.
Diagrams 4 and 5 represent the compression and decompression designs, respectively, for the SPW design of the LZW algorithm in block form.
As mentioned before, the LZW replaces patterns of pixels with single codes. It uses an adaptive dictionary or table which is a list of frequently occurring patterns. This adaptive dictionary is itself divided into an initial and an extended dictionary. These two are created independently in the compression (encoding) and the decompression (decoding) stages of the entire process.
Diagram 4. SPW Compression Design
For the encoding part, the initial dictionary contains a predetermined number of single coded entries assigned to it. In our particular case, since we're dealing with eight-bit pixels as individual inputs, the initial table requires 256 possible color-pixels where each single color-pixel is given a unique code. This means that codes from 0 to 255 refer to individual pixels. In other words, the whole process deals with images in which there are 256 different possible colors for each pixel.
For compression to take place, the code that the LZW algorithm outputs can be of any arbitrary length, but it must have more bits in it than a single character. Thus, we opted for 12-bit codes, which indicates that the extended table will be represented by the addition of new patterns (or series) of pixels. Therefore, codes 256 to 4095 (or 0 to FFF in hexadecimal) refer to patterns of pixels. Hence, encoding occurs when a single code is output instead of a series of pixels.
Diagram 5. SPW Decompression Design
The decompression process works in a similar fashion as the compression part. It also starts with an initialized dictionary, which comes from the knowledge we have about the stream of pixels that we eventually get. In other words, the possible colors that pixels can take should be known.
In short, the encoding part takes a raw image as input and compresses it into GIF format file. The decoding part acquires the compressed file as input and decompresses it, achieving a viewable image at the output (see Diagram 1).
The following diagram denotes the Altera board that was intended to be used in our project. It includes the FLEX 10K FPGA chip.
Diagram 6. UP1 Prototype Board
The team met the requirement of successfully designing the LZW algorithm in SPW and being able to show images compressing and decompressing. The results from this project were good as far as compression was involved. Moreover, the algorithm showed no signs of error, proving that this algorithm is lossless. To conclude, this group worked very well together and had no major problems. Most importantly, everyone remained being friends with each other.