System and method for compressing and decompressing images and video

• US 8,805,106 B2
• Filed: 09/24/2009
• Issued: 08/12/2014
• Est. Priority Date: 09/26/2008
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Han, Bing, Wu, Dapeng Oliver, Tian, Jun, Yu, Hong Heather
• Primary Examiner(s): Bhatnagar, Anand
• Assistant Examiner(s): PARK, SOO JIN
• Application Number:
  US12/566,473
• Publication Number:
  US 20100080473A1
• Time in Patent Office: 1,783 Days
• Field of Search: 382/232, 382/233, 382/238, 382/239, 382244-253
• US Class Current: 382/239
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/62 by frequency transforming in three dimensions H04N19/63 takes precedence
• CPC Class Codes: H04N 19/625 using discrete cosine transform [DCT]
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform

Abstract

A system and method for image and video compression and decompression using compressive sensing is provided. A method for decompressing a compressed image, where the compressed image having a plurality of compressed image blocks, and the method is performed on a processor, includes selecting a compressed image block, entropy decoding the selected compressed image block, and recovering an image block corresponding to the decoded selected compressed image block using compressive sensing recovery.

Claims

1. A method for decompressing a two-dimensional discrete cosine transform (DCT) compressed image, the method being performed on a processor, the method comprising:

selecting one of a plurality of compressed image blocks in the two-dimensional DCT compressed image;

entropy decoding the selected compressed image block; and

recovering an image block corresponding to the decoded selected compressed image block using compressive sensing recovery, wherein recovering the image block comprises applying a total variance minimization optimization to the decoded selected compressed image block, and wherein the total variance minimization optimization is expressed as

min∥

x∥

_TV subject to −

q/2≦

Ax−

y≦

q/2,

where x is the image block to be decoded, TV is total variance, A is a measurement matrix, s is measurements of the image block x, and q is a quantization step size.

2. The method of claim 1, wherein recovering the image block comprises solving a second order cone programming problem expressible as:

ŝ

=arg min TV(s), s.t.Θ

ŝ

=y,

where ŝ

is a recovered signal, s is an original signal, and y is measurements of the signal s.

3. The method of claim 1, further comprising:

repeating the selecting, the entropy decoding, and the recovering for each compressed image block in the plurality of compressed image blocks to recover image blocks corresponding to each of the compressed image blocks; and

recovering an original image by combining each of the image blocks.

4. A method for decompressing a two-dimensional discrete cosine transform (DCT) compressed image, the method being performed on a processor, the method comprising:

a) selecting one of a plurality of compressed image blocks in the two-dimensional DCT compressed image;

b) entropy decoding the selected compressed image block;

c) determining whether the decoded selected compressed image block was compressed without compressive sensing;

d) when the decoded selected compressed image block was compressed without compressive sensing, transforming the decoded selected compressed image block into a pixel domain image block; and

e) when the decoded selected compressed image block was compressed with compressive sensing, recovering an image block corresponding to the decoded selected compressed image block using compressive sensing recovery, wherein recovering the image block comprises applying a total variance minimization optimization to the decoded selected compressed image block, and wherein the total variance minimization optimization is expressed as

min∥

x∥

_TV subject to −

q/2≦

Ax−

y≦

q/2,

where x is the image block to be decoded, TV is total variance, A is a measurement matrix, y is measurements of the image block x, and q is a quantization step size.

5. The method of claim 4, further comprising, unquantizing the selected compressed image block.

6. The method of claim 4, further comprising:

repeating a), b), c), d), and e) for each compressed image block in the plurality of image blocks to recover image blocks corresponding to each of the compressed image blocks; and

recovering an original image by combining each of the image blocks.

7. The method of claim 4, wherein the selected compressed image block comprises a flag indicating whether the selected compressed image block was compressed with or without compressive sensing.

8. The method of claim 4, wherein transforming the decoded selected compressed image block comprises applying an inverse discrete cosine transform to the decoded selected compressed image block.

9. An apparatus for decompressing a two-dimensional discrete cosine transform (DCT) compressed image, the apparatus comprising:

a processor; and

a computer readable storage medium storing programming for execution by the processor, the programming including instructions to;

select one of a plurality of compressed image blocks in the two-dimensional DCT compressed image;

entropy decode the selected compressed image block; and

recover an image block corresponding to the decoded selected compressed image block using compressive sensing recovery, wherein the instructions to recover the image block comprise instructions to apply a total variance minimization optimization to the decoded selected compressed image block, and wherein the total variance minimization optimization is expressed as

min∥

x∥

_TV subject to −

q/2≦

Ax−

y≦

q/2,

where x is the image block to be decoded, TV is total variance, A is a measurement matrix, s is measurements of the image block x, and q is a quantization step size.

10. The apparatus of claim 9, wherein the instructions to recover the image block comprise instructions to solve a second order cone programming problem expressible as:

ŝ

=arg min TV(s), s.t.Θ

ŝ

=y,

where ŝ

is a recovered signal, s is an original signal, and y is measurements of the signal s.

11. The apparatus of claim 9, wherein the programming further comprises instructions to:

repeat the instructions to select, entropy decode, and recover for each compressed image block in the plurality of image blocks to recover image blocks corresponding to each of the compressed image blocks; and

recover an original image by combining each of the image blocks.

12. An apparatus for decompressing a two-dimensional discrete cosine transform (DCT) compressed image, the apparatus comprising:

a processor; and

a computer readable storage medium storing programming for execution by the processor, the programming including instructions to;

a) select one of a plurality of compressed image blocks in the two-dimensional DCT compressed image;

b) entropy decode the selected compressed image block;

c) determine whether the decoded selected compressed image block was compressed without compressive sensing;

d) when the decoded selected compressed image block was compressed without compressive sensing, transform the decoded selected compressed image block into a pixel domain image block; and

e) when the decoded selected compressed image block was compressed with compressive sensing, recover an image block corresponding to the decoded selected compressed image block using compressive sensing recovery, wherein the instructions to recover the image block comprise instructions to apply a total variance minimization optimization to the decoded selected compressed image block, and wherein the total variance minimization optimization is expressed as

min∥

x∥

_TV subject to −

q/2≦

Ax−

y≦

q/2,

where x is the image block to be decoded, TV is total variance, A is a measurement matrix, y is measurements of the image block x, and q is a quantization step size.

13. The apparatus of claim 12, wherein the programming further comprises instructions to unquantize the selected compressed image block.

14. The apparatus of claim 12, wherein the programming further comprises instructions to:

repeat a), b), c), d), and e) for each compressed image block in the plurality of image blocks to recover image blocks corresponding to each of the compressed image blocks; and

recover an original image by combining each of the image blocks.

15. The apparatus of claim 12, wherein the selected compressed image block comprises a flag indicating whether the selected compressed image block was compressed with or without compressive sensing.

16. The apparatus of claim 12, wherein the instructions to transform the decoded selected compressed image block comprise instructions to apply an inverse discrete cosine transform to the decoded selected compressed image block.