System for compression and decompression of video data using discrete cosine transform and coding techniques

• US 5,253,078 A
• Filed: 08/23/1990
• Issued: 10/12/1993
• Est. Priority Date: 03/14/1990
• Status: Expired due to Term

• Current Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Original Assignee: C Cube Microsystems Inc (Broadcom, Inc.)
• Inventors: Hsu, Wen-Chang, Kirkpatrick, James W. Jr., Purcell, Stephen C., Bonomi, Mauro, Balkanski, Alexandre
• Primary Examiner(s): Razavi, Michael
• Application Number:
  US07/572,198
• Time in Patent Office: 1,146 Days
• Field of Search: 358/133, 358/135, 358/426, 358/427, 358/432, 358/433, 358/443, 358/310, 382/56, 364/725, 364/726, 364/727, 364/728.01, 364/826
• US Class Current: 382/250
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A digital video compression system and an apparatus implementing this system are disclosed. Specifically, matrices of pixels in RGB, YUV or CMYK formats are accepted for data compression. The data are rearranged in 8x8 pixel blocks, each block being of one pixel component type. The pixel data are then subjected to a discrete cosine transform (DCT). A quantization step eliminates DCT coefficients having amplitude below a set of preset thresholds. The video signal is further compressed by coding the elements of the quantized matrices in a zig-zag manner. This representation is further compressed by Huffman codes. Decompression of the signal is substantially the reverse of compression steps. The inverse discrete cosine transform (IDCT) may be implemented by the DCT circuit. The circuits may be implemented in a single integrated circuit chip. Three levels of compression rate control are provided during processing of video data.

Claims

1. A system for data compression and decompression, comprising:

video interface means for receiving and transmitting digitized images as a stream of composite pixels, each composite pixel being represented by data of a plurality of chrominance and luminance component types;

block memory means for receiving and sorting, during data compression, said stream of composite pixels from said video interface means into single-component type data blocks, and for receiving and reconstituting, during data decompression, single-component type data blocks into said stream of composite pixels;

discrete cosine transform means for performing, during data compression, a 2-dimensional discrete cosine transform on single-component type data blocks received from said block memory, and providing coefficients of said 2-dimensional discrete cosine transform, and for performing, during data decompression, a 2-dimensional inverse discrete cosine transform, and providing as output data said coefficients of said 2-dimensional inverse discrete cosine transform to said block memory means as single-component type data blocks;

quantization means for attenuating, during data compression, higher frequency coefficients of said 2-dimensional discrete cosine transform, and for partially restoring, during data decompression, said higher frequency coefficients of said 2-dimensional discrete cosine transform, in preparation for said 2-dimensional inverse discrete cosine transform;

zig-zag means for rearranging, during data compression, said coefficients of said 2-dimensional discrete cosine transform from "sequential" order into "zig-zag" order, and for rearranging, during data decompression, said zig-zag ordered coefficients of said 2-dimensional discrete cosine transform from a "zig-zag" order to a "sequential" order;

data packing and unpacking means for packing, during data compression, said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform as run length-represented coefficients of said 2-dimensional discrete cosine transform, and for unpacking, during data compression, said run length-represented coefficients of said 2-dimensional discrete cosine transform to said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform;

Huffman coding/decoding means for coding, during data compression, said run length-represented coefficients of said 2-dimensional discrete cosine transform into Huffman Codes, and for decoding, during data compression, said Huffman codes into said run length-represented coefficients of said 2-dimensional discrete cosine transform;

first-in first-out memory means for temporary storage of said run length represented coefficients of said 2-dimensional discrete cosine transform such that said Huffman coding/decoding means operates asynchronously and independent of said data packing and unpacking means; and

host interface means for transmitting, during data compression, said Huffman codes to a host computer, and for retrieving, during data decompression, said Huffman codes from a host computer.

2. A system as in claim 1, for data compression and decompression, wherein said video interfacing means performing alternatively "master mode" and "slave mode" operations, said video interface means comprises:

data synchronization means for providing during "master mode" operation and receiving, during "slave mode" operations, synchronization signals, said synchronization signals provide synchronization between said system and external video equipment providing said digitized images.

3. A system as in claim 2, for data compression and decompression, wherein said video interface means further comprises external buffer memory address generation means for generating external buffer memory address for storing video data in an external video memory buffer.

4. A system as in claim 3, wherein said video interface means further comprising video frame means for, during compression, receiving from said external video equipment and storing into said external video buffer memory horizontal line-by-line "video sequence" signals of said digitized images, and retrieving from said video buffer memory buffer into said video interface means "block video pixel" data corresponding to pixels in an area within said digitized images, and for, during decompression, receiving from said video interface means and storing into said external video buffer memory said "buffer video pixel" data of said digitized images, and providing said external video equipment said "video sequence" signals of said digitized images.

5. A system as in claim 1 for data compression and decompression, wherein said Huffman coding/decoding means comprises:

Huffman table means for storing and providing Huffman code encoding tables during compression and Huffman code decoding tables during decompression;

coding means for translating said run length-represented coefficients of said 2-dimensional discrete cosine transform into Huffman codes using said Huffman code encoding tables; and

decoding means for translation of said Huffman codes to said run length-represented coefficients of said 2-dimensional discrete cosine transform using said Huffman code decoding tables.

6. A system as in claim 5 for data compression and decompression, wherein said coding means comprises:

read control means for requesting from said first-in first-out memory means a run length represented coefficient of said 2-dimensional discrete cosine transform;

coding address means for providing an address constructed from said run length-represented coefficient of said 2-dimensional discrete cosine transform to said Huffman table means for requesting an entry in said Huffman code encoding tables; and

Huffman code output means for providing said entry in said Huffman code encoding tables as output Huffman code.

7. A system as in claim 5 for data compression and decompression, wherein said decoding means comprises:

Huffman code receiving means for receiving a Huffman code;

decoding address means for providing an address, constructed from either said Huffman code or a next address, to said Huffman table means for requesting an entry in said Huffman code decoding tables;

decoding control means for examining said entry of said Huffman code decoding tables to determine if said entry of said Huffman code decoding tables is a run-length represented coefficient of said 2-dimensional discrete cosine transform or comprises a next address, and for providing said next address to said decoding address means when said entry of said Huffman code decoding table comprises a next address; and

Huffman decode output means for providing said run-length represented coefficient of said 2-dimensional discrete cosine transform as an output Huffman decoded datum.

8. A system for data compression and decompression, comprising:

video interface means for receiving and transmitting digitized images;

discrete cosine transform means for performing, during data compression, a 2-dimensional discrete cosine transform on data received by said video interface means, and providing coefficients of said 2-dimensional discrete cosine transform, and for performing, during data decompression, a 2-dimensional inverse discrete cosine transform, and providing as output data said coefficients of said 2-dimensional inverse discrete cosine transform to said video interface for transmission as digitized images;

quantization means for attenuating, during data compression, higher frequency coefficients of said 2-dimensional discrete cosine transform, and for partially restoring, during data decompression, said higher frequency coefficients of said 2-dimensional discrete cosine transform, in preparation for said 2-dimensional inverse discrete cosine transform;

zig-zag means for rearranging, during data compression, said coefficients of said 2-dimensional discrete cosine transform from "sequential" order into "zig-zag" order, and for rearranging, during data decompression, said zig-zag ordered coefficients of said 2-dimensional discrete cosine transform from a "zig-zag" order to a "sequential" order;

data packing and unpacking means for packing, during data compression, said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform as run length-represented coefficients of said 2-dimensional discrete cosine transform, and for unpacking, during data decompression, said run length-represented coefficients of said 2-dimensional discrete cosine transform to said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform;

Huffman coding/decoding means for coding, during data compression, said run length-represented coefficients of said 2-dimensional discrete cosine transform into Huffman codes, and for decoding, during data decompression, said Huffman codes into said run length-represented coefficients of said 2-dimensional discrete cosine transform;

first-in first-out memory means for temporary storage of said run length represented coefficients of said 2-dimensional discrete cosine transform such that said Huffman coding/decoding means operates asynchronously and independent of said data packing and unpacking means; and

host interface means for transmitting, during data compression, said Huffman codes to a host computer, and for retrieving, during data decompression, said Huffman codes from a host computer;

wherein said first-in first-out memory means provides a plurality of status signals indicating the usage of said first-in first-out memory means, and wherein said system further comprises adaptive control means for varying compression ratios achieved on said digitized images during compression according to said status signals.

9. A system as in claim 8, wherein said quantization means achieved attenuation of said higher frequencies coefficients of said 2-dimensional discrete cosine transform by combining each of said coefficients of said discrete cosine transform with a corresponding quantization constant, and wherein said adaptive control means varies compression ratios achieved on said digitized images by varying said quantization constant.

10. A system as in claim 8, wherein said adaptive control means varies compression ratios achieved on said digitized image by zeroing said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform after a predetermined number of said "zig-zag" ordered coefficients are received.

11. A system as in claim 10, wherein said predetermined number is selected from a plurality of predetermined values according to said status signals.

12. A system as in claim 8 further comprising overall adaptive control means for enabling and disabling said adaptive control means, wherein said overall adaptive control means monitors and examines, at predetermined points in the course of receiving said digitized images, the compression ratio achieved on said digitized image against a set predetermined compression targets, and when any of said predetermined targets is exceeded, said overall adaptive control means enables said adaptive control means, otherwise said overall adaptive control means disables said adaptive control means.

13. A method for data compression and decompression, comprising:

providing a video interface means for receiving and transmitting digitized images as a stream of composite pixels, each composite pixel being data of a plurality of chrominance and luminance component types;

providing block memory means for receiving and sorting, during data compression, said stream of composite pixels from said video interface means into single-component type data blocks, and for receiving and reconstituting, during data decompression, single-component type data blocks into said stream of composite pixels;

providing a discrete cosine transform means for performing, during data compression, a 2-dimensional discrete cosine transform on single-component type data blocks received from said block memory means, and providing coefficients of said 2-dimensional discrete cosine transform, and for performing, during data decompression, a 2-dimensional inverse discrete cosine transform, and providing as output data said coefficients of said 2-dimensional inverse discrete cosine transform to said block memory means as single-component type data blocks;

providing a quantization means for attenuating, during data compression, higher frequency coefficients of said 2-dimensional discrete cosine transform, and for partially restoring, during data decompression, said higher frequency coefficients of said 2-dimensional discrete cosine transform, in preparation for said 2-dimensional inverse discrete cosine transform;

providing a zig-zag means for rearranging, during data compression, said coefficients of said 2-dimensional discrete cosine transform from "sequential" order into "zig-zag" order, and for rearranging, during data decompression, said zig-zag ordered coefficients of said 2-dimensional discrete cosine transform from a "zig-zag" order to a "sequential" order;

providing a data packing and unpacking means for packing, during data compression, said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform as run length-represented coefficients of said 2-dimensional discrete cosine transform, said run length-represented coefficients of said 2-dimensional discrete cosine transform represent runs of zero coefficients as run lengths of zero coefficients, and for unpacking, during data decompression, said run length-represented coefficients of said 2-dimensional discrete cosine transform to said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform;

providing a Huffman coding/decoding means for coding, during data compression, said run length-represented coefficients of said 2-dimensional discrete cosine transform into Huffman codes, and for decoding, during data decompression, said Huffman codes into said run length-represented coefficients of said 2-dimensional discrete cosine transform;

providing a first-in first-out means for temporary storage of said run-length represented coefficients of said 2-dimensional discrete cosine transform such that said Huffman coding/decoding means operates asynchronously and independent of said data packing and unpacking means; and

providing a host interface means for transmitting, during data compression, said Huffman codes to a host computer, and for retrieving, during data decompression, said Huffman codes from a host computer.