Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method for DCT-based compression and decompression

IP.com Disclosure Number: IPCOM000021516D
Publication Date: 2004-Jan-21
Document File: 5 page(s) / 81K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for DCT-based compression and decompression. Benefits include improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 45% of the total text.

Method for DCT-based compression and decompression

Disclosed is a method for DCT-based compression and decompression. Benefits include improved performance.

Background

         The Joint Photographic Experts Group (JPEG) published ISO/IEC JTC1 10918-1 in 1994 as a standard for still-image compression and decompression. This standard defines the encoding and decoding procedures for discrete cosine transform (DCT) based JPEG encoding and decoding.

         The compression/decompression procedures include the following (see Figure 1):

•         Forward discrete cosine transformation (FDCT)

•         Quantization (Q)

•         Entropy encoding (ENC)

•         Entropy decoding (DEC)

•         Inverse quantization (IQ)

•         Inverse discrete cosine transformation (IDCT)

         The input of the ENC and the output of DEC are in zigzag scan order. A zigzag scan process (ZZ) occurs before ENC processing and a inverse zigzag scan process (IZZ) after DEC processing (see Figure2).

         The input of JPEG compression and the output of JPEG decompression are in row raster order, which starts from left to right and from top to bottom as shown as below:

0, 1, 2, 3, 4, 5, 6, 7, … 56, 57, 58, 59, 60, 61, 62, 63

         The arrows in Figure 2 show how the zigzag scan moves. It is totally different from the row raster scan although it still starts from the top-left corner and stops at the bottom right corner:

0, 1, 8, 16, 9, 2, 3, … 53, 60, 61, 54, 47, 55, 62, 63

         In a real application, the discrete cosine transformation is too complicated for hardware implementation. Many fast DCTs have been developed. Most of the fast DCT schemes use a row-column 1-dimensional (1-D) DCT algorithm, which first performs 1-D DCTs of the rows of input followed by 1-D DCTs of the columns of the results of the first 1D-DCT. Data is input in row scan order but outputs the results in column scan order from top to bottom and from left to right:

0, 8, 16, 24, 32, 40, 48, 56, … 7, 15, 23, 31, 39, 47, 55, 63

Conventional JPEG compression implementation

         DCT-based compression and decompression is inefficient because data is buffered when the order changes occur between the output of one procedure and the input of the subsequent procedure.

         Conventionally, the processing flow for DCT-based JPEG compression with FDCT is:

1.         Preload the quantization table in row-scan order in memory during initialization.

2.         FDCT inputs data in row-scan order, outputs the results in column scan order, and buffers it to the memory until all 64 data are complete.

3.         Q reads the output of FDCT and the quantization table in row-scan order, divides the values one by one, and buffers the result in row-scan order to memory until all 64 data are complete.

4.         ENC reads the Q output in zigzag order and processes it.

5.         Repeat steps 2 – 4 until all blocks are finished.

         In steps 2 and 3, the intermediate data and the outputs of FDCT and Q are buffered to memory because of the order changes. For example, the Q output data is in row-scan order while the ENC inputs data in zigzag order. Th...