Image compression by optimal reconstruction

• US 5,534,925 A
• Filed: 05/02/1994
• Issued: 07/09/1996
• Est. Priority Date: 05/02/1994
• Status: Expired due to Term

• Current Assignee: Cognitech, Inc.
• Original Assignee: Cognitech, Inc.
• Inventors: Zhong, Sifen
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): Le, Vu
• Application Number:
  US08/237,594
• Time in Patent Office: 799 Days
• Field of Search: 348/384, 348/390, 348/400, 348/403, 348/404, 348/405, 348/407, 348/699, 345/136, 345/137, 345/138, 382/22, 382/42, 382/54
• US Class Current: 348/384.1
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/85 using pre-processing or post-processing specially adapted for video compression
• CPC Class Codes: H04N 19/86 involving reduction of coding artifacts, e.g. of blockiness

Abstract

A method of producing a video image from a compressed version of a source video image which has been compressed by transforming to a transform domain and quantizing the source video image in accordance with quantization constraints, including back-transforming from the transform domain and dequantizing the compressed version to produce a decompressed video image, reducing total variation in the first decompressed video image to produce a reduced variation image, transforming the reduced variation image to produce a revised transform and conforming the revised transform with the quantization constraints of the compressed version so as to produce a constrained transform, and back-transforming the constrained transform so as to produce a replica of the source video image.

Claims

1. A method of producing a video image from a compressed version of a source video image which has been compressed by transforming to a transform domain and quantizing said source video image in accordance with quantization constraints, comprising:

inverse transforming from said transform domain and dequantizing said compressed version to produce a first decompressed video image;

reducing total variation in said first decompressed video image by reducing lengths of level pixel sets in the image as a function of spatial oscillation of each level set to produce a reduced variation image;

transforming said reduced variation image to produce a revised transform and conforming said revised transform with said quantization constraints of said compressed version so as to produce a constrained transform; and

inverse transforming said constrained transform so as to produce a replica of said source video image.

2. The method of claim 1 wherein said quantization constraints correspond to upper and lower bounds of respective quantization bins into which respective components of said compressed version fit.

3. The method of claim 2 wherein the step of conforming said revised transform comprises changing values of respective components of said revised transform toward upper or lower bounds of corresponding quantization bins depending upon whether said components of said revised transform are above or below said upper or lower bounds, respectively, of the corresponding quantization bins.

4. The method of claim 1 wherein the step of reducing total variation comprises spatially shifting level pixel sets in the image as a function of spatial oscillations of each level set.

5. The method of claim 1 wherein the step of reducing lengths is performed tangentially with respect to edges in said image associated with each level set.

6. A method of compressing a source video image, comprising:

defining plural sub-transform operators corresponding to respective portions of a transform domain;

initializing an initial prediction image;

performing plural iterations corresponding to said plural sub-transform operators, each iteration comprising the following steps;

(a) subtracting the prediction image of the previous iteration from said source video image to produce a residual image;

(b) transforming said residual image with the sub-transform operator corresponding to the current iteration;

(c) quantizing the result of step (b) by associating it with quantization constraints to produce a quantized transform residual and outputting said quantized transform residual;

(d) dequantizing and inverse transforming said quantized transform residual;

(e) adding the result of step (d) to the prediction image of the previous iteration to produce a current prediction image;

(f) reducing total variation in said current prediction image by reducing lengths of level pixel sets in the image as a function of spatial oscillation of each level set to produce a reduced variation current prediction image;

(g) subtracting the prediction image of the previous iteration from said reduced variation current prediction image to produce a revised current residual image;

(h) transforming said revised current residual image to produce a current residual transform and conforming said current residual transform with said quantization constraints of said transform residual of step (c) to produce a modified transform residual;

(i) inverse transforming said modified transform residual to produce a modified residual image and adding said modified residual image to the prediction image of the previous iteration to produce the prediction image of the current iteration.

7. The method of claim 6 wherein said quantization constraints correspond to upper and lower bounds of respective quantization bins into which respective components of said compressed version fit.

8. The method of claim 7 wherein the step of conforming said residual transform comprises changing values of respective components of said revised transform toward upper or lower bounds of corresponding quantization bins depending upon whether said components of said revised transform are above or below said upper or lower bounds, respectively, of the corresponding quantization bins.

9. The method of claim 6 wherein the step of initializing an initial prediction image comprising setting it to zero.

10. The method of claim 6 wherein the initial one of said sub-transform operators corresponds to a zero-frequency component.

11. The method of claim 6 wherein the step of reducing total variation comprises spatially shifting level pixel sets in the image as a function of spatial oscillations of each level set.

12. The method of claim 6 wherein the step of reducing lengths is performed tangentially with respect to edges in said image associated with each level set.

13. A method of decompressing an image which has been compressed into successive quantized transform residuals satisfying respective quantization constraints, comprising:

initializing an initial prediction image;

performing an iteration of the following steps for each of said successive quantized transform residuals;

(a) dequantizing and inverse transforming the quantized transform residual corresponding to the current iteration;

(b) adding the result of step (a) to the prediction image of the previous iteration to produce a current prediction image;

(c) reducing total variation in said current prediction image by reducing lengths of level pixel sets in the image as a function of spatial oscillation of each level set to produce a reduced variation current prediction image;

(d) subtracting the prediction image of the previous iteration from said reduced variation current prediction image to produce a revised current residual image;

(e) transforming said revised current residual image to produce a current residual transform and conforming said current residual transform with said quantization constraints to produce a modified transform residual;

(f) inverse transforming said modified transform residual to produce a modified residual image;

combining the modified residual images of all iterations to produce a decompressed image.

14. The method of claim 13 wherein said quantization constraints correspond to upper and lower bounds of respective quantization bins into which respective components of said quantized transform residuals fit.

15. The method of claim 14 wherein the step of conforming said current residual transform comprises changing values of respective components of said current transform toward upper or lower bounds of corresponding quantization bins depending upon whether said components of said current residual transform are above or below said upper or lower bounds, respectively, of the corresponding quantization bins.

16. The method of claim 13 wherein the step of reducing total variation comprises spatially shifting level pixel sets in the image as a function of spatial oscillations of each level set.

17. The method of claim 13 wherein the step of reducing lengths is performed tangentially with respect to edges in said image associated with each level set.

22. The method of claim 17 wherein the step of reducing total variation comprises spatially shifting level pixel sets in the image as a function of spatial oscillations of each level set.

18. A method of recovering a video image from a compressed version of a source video image which has been compressed by quantizing said source video image so as to impose quantization constraints thereon, comprising:

dequantizing said compressed version to produce a first decompressed video image;

reducing total variation in said first decompressed video image by reducing lengths of level pixel sets in the image as a function of spatial oscillation of each level set to produce a reduced variation image;

conforming said reduced variation image with said quantization constraints of said compressed version so as to produce a replica of said source video image.

19. The method of claim 18 wherein the step of reducing total variation comprises spatially shifting level pixel sets in the image as a function of spatial oscillations of each level set.

20. The method of claim 18 wherein the step of reducing lengths is performed tangentially with respect to edges in said image associated with each level set.

21. A method of compressing a source video image, comprising:

defining plural sub-transform operators corresponding to respective portions of a transform domain;

initializing a prediction image;

performing plural iterations corresponding to said plural sub-transform operators, each iteration comprising the following steps;

(a) generating and outputting a quantized transform corresponding to the sub-transform operator of the current iteration of a residue of the source image and previous iteration'"'"'s prediction image falling within certain quantization constraints;

(b) generating an inverse transformed de-quantized residue from the result of step (a), adding it to the prediction image of the previous iteration and producing from the sum thereof a reduced-variation image, wherein lengths of level pixel sets in the image are reduced as a function of spatial oscillation of each level set;

(c) subtracting the previous iteration'"'"'s prediction image from said reduced-variation image to generate a revised residue;

(d) conforming the transform of the revised residue with said quantization constraints and adding the inverse transform of the result thereof to the prediction image of the previous iteration to produce the prediction image of the current iteration.

23. A method of expanding an image of n pixels to an image of m*n pixels from a compressed version of the image which has been compressed by transforming to a transform domain and quantizing said image in accordance with quantization constraints, comprising:

defining n blocks of m spatial frequency transform coefficients;

defining each zero frequency coefficient in each of said blocks as being the value of the corresponding pixel in said n pixel image;

dequantizing the coefficients in each block and inverse transforming each block to produce a trial image;

reducing total variation in said trial image by reducing lengths of level pixel sets in the image as a function of spatial oscillation of each level set to produce a reduced variation image;

transforming said reduced variation image to produce a revised transform and conforming said revised transform with quantization constraints of the dequantizing step so as to produce a constrained transform; and

inverse transforming said constrained transform so as to produce said expanded image.

24. The method of claim 23 wherein the step of reducing total variation comprises spatially shifting level pixel sets in the image as a function of spatial oscillations of each level set.