UNIVERSITY OF CALIFORNIA Santa Barbara JPEG Image Compression Using an FPGA A Thesis submitted in partial satisfaction of the requirements for the degree Master of Science in Electrical and Computer Engineering by James Rosenthal Committee in charge: Professor Steven Butner, Chair Professor Michael Melliar-Smith Professor Tim Cheng December 2006 The thesis of James Rosenthal is approved. Tim Cheng Michael Melliar-Smith Steven Butner, Committee Chair December 2006 JPEG Image Compression Using an FPGA Copyright (cid:176)c 2006 by James Rosenthal iii ABSTRACT JPEG Image Compression Using an FPGA by James Rosenthal Image compression is an important topic in commercial, industrial, and academic applications. Whether it be in commercial photography, industrial imaging, or video, digital pixel information can comprise considerably large amounts of data. Management of such data can involve significant overhead in computational com- plexity, storage, and data processing. Typical access speeds for storage mediums are inversely proportional to capacity. Through data compression, such tasks can be optimized. Image and video compressors and decompressors (codecs) are implemented mainly in software as digital signal processors have optimized instruction sets to manage the required operations. Hardware-specific codecs can be integrated into digital systems fairly easily, requiring work only in the areas of interface and overall integration. Improvements in speed occur primarily because the hardware can be tailored to the compression algorithm as well as the application. Using an FPGA to implement a codec combines the best of two worlds: significantly increased processing speed due to the use of customized hardware, and flexibility to make changes and tunings of the algorithm since FPGA-based designs are iv easily modified. The JPEG algorithm was chosen for this project as it is well defined and highly recognizable. JPEG provides a baseline compression algorithm that can be modified in numerous ways to fit any desired application. The JPEG specifi- cation, released initially in 1991, does not specify a particular implementation. A programmable hardware platform, developed in the computer architecture laboratory at UCSB, was chosen as a substrate for this project. The baseline JPEG compression algorithm was tailored to fit this board, using custom hard- ware pipelining, as well as parallel data paths. The core compression design was created using the Verilog hardware description language. THe supporting software was written in C, developed for a DSP and the PC. The implementation of this project was successful on achieving significant compression ratios. The sample images chosen showed different degrees of con- trast and fine detail to show how the compression affected high frequency com- ponents within the images. The throughput of the design excelled in the FPGA core. However, inherent limitations in the interface to the FPGA limited the overall performance of the design. v Contents 1 Introduction 1 1.1 Image Compression . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Redundancy Coding . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 The Human Visual System . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Transform Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Lossless Compression . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 Lossy Compression . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.7 Color Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.8 JPEG Compression . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.8.1 Sequential DCT Based . . . . . . . . . . . . . . . . . . . . 9 1.8.2 Progressive DCT Based . . . . . . . . . . . . . . . . . . . 10 1.8.3 Lossless Mode . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.8.4 Hierarchical Mode . . . . . . . . . . . . . . . . . . . . . . 11 2 Baseline JPEG Compression 12 2.1 Level Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Discrete Cosine Transform . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Zigzag Scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5 DC Differential Coding . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6 Entropy Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.6.1 Run Length Coding . . . . . . . . . . . . . . . . . . . . . . 20 2.6.2 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . 21 2.7 Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 vi 2.8 JPEG File Construction . . . . . . . . . . . . . . . . . . . . . . . 22 2.8.1 Application Specific Data Header . . . . . . . . . . . . . . 24 2.8.2 Define Quantization Table Header . . . . . . . . . . . . . . 26 2.8.3 Frame Header Segment . . . . . . . . . . . . . . . . . . . . 29 2.8.4 Huffman Table Definition Segment . . . . . . . . . . . . . 31 2.8.5 Start of Scan . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.8.6 Entropy Coded Scan . . . . . . . . . . . . . . . . . . . . . 51 2.8.7 End Of Image . . . . . . . . . . . . . . . . . . . . . . . . . 52 3 System Overview 53 3.1 FPGA Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.1.1 Module Design . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1.2 JPEG Encoder Core . . . . . . . . . . . . . . . . . . . . . 58 3.1.3 Modular Addressing . . . . . . . . . . . . . . . . . . . . . 69 3.1.4 Status and Control Registers . . . . . . . . . . . . . . . . . 69 3.1.5 FIFO Interface . . . . . . . . . . . . . . . . . . . . . . . . 74 3.1.6 Interrupt Driven Interface . . . . . . . . . . . . . . . . . . 78 3.2 DSP Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.2.1 DSP FIFO Server . . . . . . . . . . . . . . . . . . . . . . . 80 3.2.2 Action Codes . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.2.3 Response Codes . . . . . . . . . . . . . . . . . . . . . . . . 83 3.2.4 Control Structures . . . . . . . . . . . . . . . . . . . . . . 84 3.2.5 Status Structures . . . . . . . . . . . . . . . . . . . . . . . 85 3.2.6 External Memory Interface . . . . . . . . . . . . . . . . . . 85 3.2.7 Programmed I/O Interface . . . . . . . . . . . . . . . . . . 87 3.2.8 DMA Interface . . . . . . . . . . . . . . . . . . . . . . . . 93 3.3 PC Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 vii 3.3.1 PLogic Interface . . . . . . . . . . . . . . . . . . . . . . . . 96 3.3.2 Imaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.3.3 TCL Interface . . . . . . . . . . . . . . . . . . . . . . . . . 99 4 Discussion 101 4.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 viii List of Figures 2.1 DCT Basis Functions . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 High Level File Structure . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Application Specific Header . . . . . . . . . . . . . . . . . . . . . 24 2.4 Define Quantization Table Segment . . . . . . . . . . . . . . . . . 26 2.5 Start of Frame Header Segment . . . . . . . . . . . . . . . . . . . 29 2.6 Define Huffman Table Segment . . . . . . . . . . . . . . . . . . . 31 2.7 Start of Scan Segment . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1 High Level System Overview . . . . . . . . . . . . . . . . . . . . . 53 3.2 FPGA Core Overview . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3 Module Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 Module Input Timing . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.5 Module Output Timing . . . . . . . . . . . . . . . . . . . . . . . . 57 3.6 DCT High Level . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.7 DCT Multiply Accumulate Module . . . . . . . . . . . . . . . . . 60 3.8 Zigzag Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.9 Quantization and Rounding . . . . . . . . . . . . . . . . . . . . . 63 3.10 Entropy Encoder . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.11 Output Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.12 Modular Addressing . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.13 Encoder Control Register . . . . . . . . . . . . . . . . . . . . . . . 70 3.14 Interrupt Control Register . . . . . . . . . . . . . . . . . . . . . . 71 3.15 Encoder Status Register . . . . . . . . . . . . . . . . . . . . . . . 71 3.16 Encoder Count Status Register . . . . . . . . . . . . . . . . . . . 72 3.17 FIFO Status Register . . . . . . . . . . . . . . . . . . . . . . . . . 72 ix 3.18 FIFO Address Register . . . . . . . . . . . . . . . . . . . . . . . . 73 3.19 Interrupt Status Register . . . . . . . . . . . . . . . . . . . . . . . 73 3.20 FIFO Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.21 Asynchronous Write State Machine . . . . . . . . . . . . . . . . . 77 3.22 Asynchronous Read State Machine . . . . . . . . . . . . . . . . . 78 3.23 PC Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 3.24 TCL Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.1 Image: Baboon Source . . . . . . . . . . . . . . . . . . . . . . . . 105 4.2 Image: Baboon Result . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3 Image: Lena Source . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.4 Image: Lena Result . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.5 Image: Peppers Source . . . . . . . . . . . . . . . . . . . . . . . . 107 4.6 Image: Peppers Result . . . . . . . . . . . . . . . . . . . . . . . . 107 x