Back to results
US 5,107,345 AGranted
Adaptive block size image compression method and system
AssigneeQUALCOMM Incorporated
InventorChong U. Lee
Life of this patent
Estimating the term…
Abstract
An image compression system and method for compressing image data for transmission. Each block and corresponding sub-blocks of pixel data is subjected to a discrete cosine transform (DCT) operation. Varying levels of sub-blocks of resulting corresponding transform coefficients are selected for construction into a composite transform coefficient block corresponding to each input block of pixel data. The selection of transform coefficient block size for the composite block is determined by a comparison process between transform block and sub-block coding efficiency. The composite block is variable length coded to further reduce bit count in the compressed data.
Claims47
An image compression system for compressing a 16.times.16 block of pixel data comprising:
- first transform means for receiving and performing 2.times.2 discrete cosine transform (DCT) operations on said block of pixel data, and providing a corresponding block of sixty-four 2.times.2 DCT coefficient value sub-blocks;
- second transform means for receiving and performing 4.times.4 DCT operations on said block of pixel data, and providing a corresponding block of sixteen 4.times.4 DCT coefficient value sub-blocks;
- third transform means for receiving and performing 8.times.8 DCT operations on said block of pixel data, and providing a corresponding block of four 8.times.8 DCT coefficient value sub-blocks;
- fourth transform means for receiving and performing a 16.times.16 DCT operation on said block of pixel data, and providing a corresponding 16.times.16 DCT coefficient value block;
- first memory means for storing bit values each corresponding to a number of bits required to encode according to a predetermined encoding format each different 2.times.2 DCT coefficient value, said first memory means for receiving each 2.times.2 DCT coefficient value sub-block and providing a corresponding first set of bit values;
- second memory means for storing bit values each corresponding to a number of bits required to encode according to a predetermined encoding format each different 4.times.4 DCT coefficient value, said second memory means for receiving each 4.times.4 DCT coefficient value sub-block and providing a corresponding second set of bit values;
- third memory means for storing bit values each corresponding to a number of bits required to encode according to a predetermined encoding format each different 8.times.8 DCT coefficient value, said third memory means for receiving each 8.times.8 DCT coefficient value sub-blocks and providing a corresponding third set of bit values;
- fourth memory means for storing bit values each corresponding to a number of bits required to encode according to a predetermined encoding format each different 16.times.16 DCT coefficient value, said fourth memory means for receiving said 16.times.16 DCT coefficient value block and providing a corresponding fourth set of bit values;
- first code length summer means for, receiving said first set of bit values, summing ones of said first set of bit values corresponding to each respective 2.times.2 DCT coefficient value sub-block and providing corresponding first code length sum values;
- second code length summer means for, receiving said second set of bit values, summing ones of said second set of bit values corresponding to each respective 4.times.4 DCT coefficient value sub-block and providing corresponding second code length sum values;
- third code length summer means for, receiving said third set of bit values, summing ones of said third set of bit values corresponding to each respective 8.times.8 DCT coefficient value sub-block and providing corresponding third code length sum values;
- fourth code length summer means for, receiving said fourth set of bit values, summing said fourth set of bit values and providing a corresponding fourth code length sum value;
- first adder means for receiving and adding predetermined groups of said first code length sum values, and providing corresponding first adder values;
- first comparator means for receiving and comparing each first adder value with a predetermined corresponding second code length sum value, and providing a corresponding first comparison value;
- first multiplexer means for receiving each first adder value, each corresponding second code length sum value, and each corresponding first comparison value and for providing a first multiplexer value selected from one of each first adder value and corresponding second code length sum value in accordance with said first comparison value;
- first register means for receiving and storing in a predetermined order each first comparison value;
- second adder means for receiving and adding predetermined groups of first multiplexer values, and providing corresponding second adder values;
- second comparator means for receiving and comparing each second adder value with a predetermined corresponding third code length sum value, and providing a corresponding second comparison value;
- second multiplexer means for receiving each second adder value, each corresponding third code length sum value, and each corresponding second comparison value and for providing a second multiplexer value selected from one of each second adder value and corresponding third code length sum value in accordance with said second comparison value;
- second register means for receiving and storing in a predetermined order each second comparison value;
- third adder means for receiving and adding said second multiplexer values, and providing a third adder value;
- third comparator means for receiving and comparing said third adder value with said fourth code length sum value, and providing a corresponding third comparison value;
- third register means for receiving and storing said third comparison value;
- third multiplexer means for receiving each of said 2.times.2 DCT coefficient value sub-blocks, said 4.times.4 DCT coefficient value sub-blocks and a corresponding predetermined one of said first register means stored first comparison values, and for providing a third multiplexer value selected from one of groups of said 2.times.2 DCT coefficient value sub-blocks and a corresponding one of said 4.times.4 DCT coefficient value sub-blocks in accordance with said stored corresponding first comparison value;
- fourth multiplexer means for receiving each third multiplexer value, said 8.times.8 DCT coefficient value sub-blocks and a corresponding predetermined one of said second register means stored second comparison values, and for providing a fourth multiplexer value selected from one each third multiplexer value and a corresponding one of said 8.times.8 DCT coefficient value sub-blocks in accordance with said stored corresponding second comparison value;
- fifth multiplexer means for receiving each fourth multiplexer value, said 16.times.16 DCT coefficient value block and a corresponding predetermined one of said third register means stored third comparison values, and for providing a fifth multiplexer value selected from one each fourth multiplexer value and said 16.times.16 DCT coefficient value block in accordance with said stored corresponding third comparison value;
- serializer means for receiving said fifth multiplexer value and each of said stored first, second and third comparison values, for ordering DCT coefficient values of said fifth multiplexer value in accordance with said stored first, second and third comparison values and for providing a corresponding output of serialized DCT coefficient values;
- encoder means for receiving and encoding said serialized DCT coefficients according to said predetermined encoding format and for providing corresponding encoder output values;
- and
- assembler means for receiving and ordering said encoder output values and said stored first, second and third comparison values according to a predetermined format, and for providing a corresponding assembler output values.
27 more elements
An image signal compression system comprising:
- transform means for, receiving a 16.times.16 block of pixel data, performing a 16.times.16 discrete cosine transform (DCT) operation on said block of pixel data and providing a corresponding 16.times.16 block of DCT coefficient values, performing four 8.times.8 DCT operations on said block of pixel data and providing a corresponding block of four 8.times.8 DCT coefficient value sub-blocks, performing sixteen 4.times.4 DCT operations on said block of pixel data and providing a corresponding block of sixteen 4.times.4 DCT coefficient value sub-blocks, performing sixty-four 2.times.2 DCT operations on said block of pixel data and providing a corresponding block of sixty-four 2.times.2 DCT coefficient value sub-blocks;
- quantization means for receiving and quantizing said 16.times.16 block of DCT coefficient values and each 8.times.8, 4.times.4 and 2.times.2 sub-block of DCT coefficient values, and for providing a corresponding 16.times.16 block of quantized DCT coefficients and corresponding 8.times.8, 4.times.4 and 2.times.2 sub-block of quantized DCT coefficient values;
- block size assignment means for, receiving said 16.times.16 block of quantized DCT coefficient values and each 8.times.8, 4.times.4 and 2.times.2 sub-block of quantized DCT coefficient values, determining for said 16.times.16 block of quantized DCT coefficient values and each of corresponding groups of 8.times.8, 4.times.4 and 2.times.2 sub-blocks of quantized DCT coefficient values a bit count value corresponding to a number of bits required to respectively encode said 16.times.16 block of quantized DCT coefficient values and said corresponding groups of 8.times.8, 4.times.4 and 2.times.2 sub-blocks of quantized DCT coefficient values according to a predetermined coding format, determining from said bit count values ones of said 16.times.16 block of DCT coefficient values and said corresponding groups of 8.times.8, 4.times.4 and 2.times.2 sub-blocks of quantized DCT coefficient values requiring a lesser number of bits to encode according to said coding format, and providing a corresponding selection value;
- selection means for, receiving said selection value and said 16.times.16 block of quantized DCT coefficient values and each 8.times.8, 4.times.4 and 2.times.2 sub-block of quantized DCT coefficient values, selecting ones of said 16.times.16 block of quantized DCT coefficient values and groups of 8.times.8, 4.times.4 and 2.times.2 sub-block of quantized DCT coefficient values in accordance with said selection value, and providing an output of a corresponding composite block of quantized DCT coefficient values formed from said selected ones of said 16.times.16 block of quantized DCT coefficient values and groups of 8.times.8, 4.times.4 and 2.times.2 sub-block of quantized DCT coefficient values;
- ordering means for, receiving said composite block of quantized DCT coefficient values, ordering said composite block of quantized DCT coefficient values according to a predetermined ordering format, and providing a corresponding output of ordered quantized DCT coefficient values;
- encoder means for, receiving said ordered quantized DCT coefficient values, coding said ordered quantized DCT coefficient values according to said predetermined coding format, and providing corresponding coded values;
- and
- assembler means for, receiving said selection value and said coded values, combining said selection value and said coded value as a coded image value representative of said block of pixel data with said coded image value of a reduced bit count with respect to a bit count of said block of pixel data, and providing an output of said coded image value.
5 more elements
A method for image signal compression of a block of pixel data comprising the steps of:
- performing a 16.times.16 discrete cosine transform (DCT) operation on an 16.times.16 block of pixel data so as to provide a corresponding 16.times.16 block of DCT coefficient values;
- performing four 8.times.8 DCT operations on said block of pixel data so as to provide a corresponding block of four 8.times.8 DCT coefficient value sub-blocks;
- performing sixteen 4.times.4 DCT operations on said block of pixel data so as to
- performing sixty-four 2.times.2 DCT operations on said block of pixel data so as to provide a corresponding block of sixty-four 2.times.2 DCT coefficient value sub-blocks;
- determining bit count values corresponding to a number of bits required to respectively encode said 16.times.16 block of DCT coefficient values and predetermined groups of 8.times.8, 4.times.4 and 2.times.2 sub-blocks of DCT coefficient values according to a predetermined coding format;
- determining, from said bit count values, ones of said 16.times.16 block of DCT coefficient values and said corresponding groups of 8.times.8, 4.times.4 and 2.times.2 sub-blocks of DCT coefficient values requiring a lesser number of bits to encode according to said predetermined coding format so as to provide a corresponding selection value;
- selecting ones of said 16.times.16 block of DCT coefficient values and groups of 8.times.8, 4.times.4 and 2.times.2 sub-block of DCT coefficient values in accordance with said selection value;
- generating a composite block of DCT coefficient values formed from said selected ones of said 16.times.16 block of DCT coefficient values and groups of 8.times.8, 4.times.4 and 2.times.2 sub-block of DCT coefficient values;
- ordering said composite block of DCT coefficient values according to a predetermined ordering format so as to provide a corresponding output of ordered DCT coefficient values;
- encoding said ordered DCT coefficient values according to said predetermined coding format so as to provide corresponding coded values;
- and
- assembling said selection value and said coded values in a predetermined order as a coded image value representative of said block of pixel data.
9 more elements
A system for decoding a compressed image signal comprising:
- separator means for, receiving a compressed image signal representative of a selection value and coded values, separating said selection value and said coded values from one another, and providing an output of said separated selection value and said coded values;
- decoder means for receiving and decoding according to a predetermined coding format said coded values, and for providing corresponding decoded values;
- ordering means for, receiving said decoded values and said selection value, ordering said decoded values according to a predetermined ordering format in response to said selection value, and providing an output forming a composite block of one of a block of transform coefficient values and various sub-blocks of transform coefficient values;
- inverse transform means for, receiving said composite block of transform coefficient values, performing an inverse transform operation on said one of said block and each sub-block of transform coefficient values of said composite block transform coefficient values, and providing an output of a corresponding one of a block of pixel data and sub-blocks of pixel data;
- and
- combiner means for, receiving said one of said block of pixel data and said sub-blocks of pixel data, receiving said selection value, and in accordance with said selection value combining when present said sub-blocks of pixel data into a combined block of pixel data and providing one of said block of pixel data and said combined block of pixel data as an output block of pixel data.
3 more elements
A system for reconstructing a 16.times.16 block of pixel image data from a compressed image data signal comprising:
- data separator means for, receiving a compressed image data signal containing in a predetermined order a selection value, coded run-length values, and coded non-zero discrete cosine transform (DCT) coefficient values indicative of a compressed 16.times.16 block of pixel data, separating said selection value, said coded run-length values, and said coded non-zero DCT coefficient values, and providing corresponding outputs of said selection value, said coded run-length values and said coded non-zero DCT coefficient values;
- encoder means for, receiving and decoding according to a predetermined coding format each of said coded run-length values and said coded non-zero DCT coefficient values so as to provide decoded run-length values and non-zero DCT coefficient values, run-length decoding said run-length values and non-zero DCT coefficient values, and for providing an output of DCT coefficient values;
- inverse serializer means for, receiving said DCT coefficient values and said selection value, ordering said DCT coefficient values according to a predetermined ordering format in response to said selection value so as to provide a composite block of ones of a 16.times.16 block of DCT coefficient values and 8.times.8, 4.times.4 and 2.times.2 sub-blocks of DCT coefficient values;
- inverse quantization means for receiving and inverse quantizing each DCT coefficient of said composite block of DCT coefficient values, and for providing a corresponding output of a composite block of inverse quantized DCT coefficient values;
- inverse transform means for, performing a 16.times.16 inverse discrete cosine transform (IDCT) operation on said composite block of inverse quantized DCT coefficient values when comprised of a 16.times.16 block of inverse quantized DCT coefficient values, performing an 8.times.8 IDCT operation on each 8.times.8 sub-block of inverse quantized DCT coefficient values when comprised of at least one 8.times.8 sub-block of inverse quantized DCT coefficient values, performing a 4.times.4 IDCT operation on each 4.times.4 sub-block of inverse quantized DCT coefficient values when comprised of at least one 4.times.4 block of inverse quantized DCT coefficient values, performing a 2.times.2 IDCT operation on each 2.times.2 sub-block of inverse quantized DCT coefficient values when comprised of at least one 2.times.2 block of inverse quantized DCT coefficient values, and for providing a corresponding ones of a 16.times.16 block and 8.times.8, 4.times.4 and 2.times.2 sub-blocks of pixel data;
- sub-block combiner means for receiving said selection value, receiving when output from said inverse transform means each of said 16.times.16 block and 8.times.8, 4.times.4 and 2.times.2 sub-blocks of pixel data, assembling said 16.times.16 block and said 8.times.8, 4.times.4 and 2.times.2 sub-blocks of pixel data into an output 16.times.16 block of pixel data.
3 more elements
The system of claim 33 wherein said inverse quantization means comprises:
- first inverse quantizer means for receiving and inverse quantizing each 2.times.2 sub-block of quantized DCT coefficient values according to a first predetermined inverse quantization scheme, and for providing a corresponding 2.times.2 sub-block of inverse quantized DCT coefficient values to said 2.times.2 IDCT element input;
- second inverse quantizer means for receiving and inverse quantizing each 4.times.4 sub-block of quantized DCT coefficient values according to a second predetermined inverse quantization scheme, and for providing a corresponding 4.times.4 sub-block of inverse quantized DCT coefficient values to said 4.times.4 IDCT element input;
- third inverse quantizer means for receiving and inverse quantizing each 8.times.8 sub-block of quantized DCT coefficient values according to a third predetermined inverse quantization scheme, and for providing a corresponding 8.times.8 sub-block of inverse quantized DCT coefficient values to said 8.times.8 IDCT element input;
- and
- fourth inverse quantizer means for receiving and inverse quantizing said 16.times.16 block of quantized DCT coefficient values according to a fourth predetermined inverse quantization scheme, and for providing a corresponding 16.times.16 block of inverse quantized DCT coefficient values to said 16.times.16 IDCT element input.
2 more elements
A method for reconstructing a block of pixel data from a compressed image data signal comprising the steps of:
- receiving a compressed image data signal representative of a selection value and coded values;
- separating said selection value and said coded values from one another so as to provide an output of said separated selection value and said coded values;
- decoding according to a predetermined coding format said coded values so as to provide corresponding decoded values;
- ordering said decoded values according to a predetermined ordering format in according to said selection value so as to provide an output forming a composite block of one of a block of transform coefficient values and various sub-blocks of transform coefficient values;
- performing an inverse transform operation on said one of said block and each sub-block of transform coefficient values of said composite block of transform coefficient values so as to provide an output of a corresponding one of a block of pixel data and sub-blocks of pixel data;
- and
- combining in accordance with said selection value said sub-blocks of pixel data, when present, into a combined block of pixel data so as to provide one of said block of pixel data and said combined block of pixel data as an output block of pixel data.
4 more elements
A method for reconstructing a 16.times.16 block of pixel image data from a compressed image data signal comprising:
- receiving a compressed image data signal containing in a predetermined order a selection value, coded run-length values, and coded non-zero discrete cosine transform (DCT) coefficient values indicative of a compressed 16.times.16 block of pixel data;
- separating said selection value, said coded run-length values, and said coded non-zero DCT coefficient values so as to provide corresponding outputs of said selection value, said coded run-length values and said coded non-zero DCT coefficient values;
- decoding according to a predetermined coding format each of said coded run-length values and said coded non-zero DCT coefficient values;
- run-length decoding said run-length values and non-zero DCT coefficient values so as to provide an output of DCT coefficient values;
- ordering said DCT coefficient values according to a predetermined ordering format in response to said selection value so as to provide a composite block of ones of a 16.times.16 block of DCT coefficient values and 8.times.8, 4.times.4 and 2.times.2 sub-blocks of DCT coefficient values;
- inverse quantizing each DCT coefficient of said composite block of DCT coefficient values so as to provide a corresponding output of a composite block of inverse quantized DCT coefficient values;
- performing a 16.times.16 inverse discrete cosine transform (IDCT) operation on said composite block of inverse quantized DCT coefficient values when comprised of a 16.times.16 block of inverse quantized DCT coefficient values so as to provide a corresponding 16.times.16 block of pixel data;
- performing an 8.times.8 IDCT operation on each 8.times.8 sub-block of inverse quantized DCT coefficient values when comprised of at least one 8.times.8 block of inverse quantized DCT coefficient values so as to provide corresponding 8.times.8 sub-blocks of pixel data;
- performing a 4.times.4 IDCT operation on each 4.times.4 sub-block of inverse quantized DCT coefficient values when comprised of at least one 4.times.4 block of inverse quantized DCT coefficient values so as to provide corresponding 4.times.4 sub-blocks of pixel data;
- performing a 2.times.2 IDCT operation on each 2.times.2 sub-block of inverse quantized DCT coefficient values when comprised of at least one 2.times.2 block of inverse quantized DCT coefficient values so as to provide corresponding 2.times.2 sub-blocks of pixel data;
- combining in response to selection value said 8.times.8, 4.times.4 and 2.times.2 sub-blocks of pixel data into a composite 16.times.16 block of pixel data so as to provide one of said 16.times.16 block of pixel data and said composite 16.times.16 block of pixel data as a reconstructed 16.times.16 block of pixel data.
8 more elements
Dependencies are inferred from the claim text.