Method of compressing images of arbitrarily shaped objects

• US 6,862,371 B2
• Filed: 12/31/2001
• Issued: 03/01/2005
• Est. Priority Date: 12/31/2001
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Mukherjee, Debargha
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US10/036,985
• Publication Number:
  US 20030123740A1
• Time in Patent Office: 1,156 Days
• Field of Search: 382/252, 382/248, 382/249, 382/245, 382/250, 375/240.14, 375/240.11, 345/474, 345/536
• US Class Current: 382/248
• CPC Class Codes: H04N 19/649 the transform being applied to non rectangular image segments

Abstract

A method of manipulating spectral content of a block of pixels for compression includes the step of classifying each pixel within a selected block of pixels as relevant or irrelevant. A forward transform is applied to the selected block to generate a coefficient block. The coefficient values are modified to generate a modified coefficient block subject to a set of pre-determined constraints including a constraint that the relevant pixels have a same value in an inverse transformation of the modified coefficient block as in the selected block. Proceeding in a reverse zig zag coefficient order the method is repeated for other coefficients having non-zero quantized values.

Claims

1. A method of manipulating spectral content of a block of pixels for compression comprising the steps of:

a) classifying each pixel within a selected block of pixels as relevant or irrelevant;

b) generating a coefficient block representing a forward transform of the selected block; and

c) modifying coefficient values to generate a modified coefficient block subject to a set of pre-determined constraints including a constraint that the relevant pixels have a same value in an inverse transformation of the modified coefficient block as in the selected block.

2. The method of claim 1 further comprising the steps of:

d) repeating steps a)-c) for every block of pixels of the source image.

3. The method of claim 1 wherein step c) includes the steps of:

i) selecting a coefficient from the coefficient block in a reverse zig-zag order wherein the selected coefficient has a non-zero value; and

ii) finding a feasible solution resulting in a zero quantizable selected coefficient subject to the pre-determined constraints.

4. The method of claim 3 wherein the coefficient value is modified subject to a constraint that no zero quantizable coefficient preceding the selected coefficient in the reverse zig-zag order is permitted to become non-zero quantizable.

5. The method of claim 1 further comprising the step of:

d) entropy encoding the coefficient block to generate compressed data corresponding to the selected block.

6. The method of claim 1 wherein values of individual elements of a mask classify pixels in corresponding positions within the selected block as relevant or irrelevant.

7. The method of claim 1 wherein the selected block includes relevant pixels associated with an object and irrelevant pixels not associated with the object.

8. The method of claim 1 further comprising the step of:

d) providing the modified coefficient block to a block compression process.

9. The method of claim 1 wherein step d) further comprises the step of applying a linear program to identify a feasible solution resulting in a zero-quantizable coefficient subject to the constraints.

10. The method of claim 9 further comprising the step of applying a quadratic program to generate a modified selected block having minimal energy.

11. The method of claim 10 further comprising the step of terminating further modifications to the coefficient block if a ratio of the energy of the modified block to the energy of the initial selected block exceeds a pre-determined threshold.

12. The method of claim 1 wherein step b) further comprises the step of assigning an average relevant pixel value to every irrelevant pixel before performing a forward transform.

13. The method of claim 1 wherein the forward transform is one of a discrete cosine, a discrete sine, and a discrete Fourier transform.

14. A method of manipulating spectral content of a block of pixels for compression comprising the steps of:

a) providing a source block of pixels from a source image;

b) classifying the pixels as modifiable or nonmodifiable;

c) performing a forward transform on the selected block;

d) quantizing the transformed block to generate a quantized coefficient block; and

e) modifying at least one coefficient to produce a corresponding zero quantized coefficient subject to a plurality of constraints including the constraint that the coefficient is modified without altering pixel values of an inverse transform that correspond to nonmodifiable pixels in the selected block.

15. The method of claim 14 wherein the non-zero quantized coefficients are selected for modification from the quantized coefficient block proceeding in reverse zig-zag order.

16. The method of claim 14 wherein values of individual elements of a mask classify pixels in corresponding positions within the selected block as relevant or irrelevant.

17. The method of claim 14 wherein the modifiable pixels are modified subject to the constraint that no zero quantized coefficient preceding the selected non-zero quantized coefficient may become non-zero.

18. The method of claim 14 wherein the forward transform is a selected one of a discrete cosine, a discrete sine, and a discrete Fourier transform.

19. The method of claim 14 further comprising the step of:

f) applying entropy encoding to the modified coefficient block to generate compressed image data.

20. The method of claim 16 further comprising the step of:

f) repeating step e) to increase a number of zero quantized coefficients proceeding in a reverse zig-zag order subject to a constraint that no preceding zero quantized coefficient may become non-zero quantized.