Method for visual optimisation of embedded block codes to exploit visual masking phenomena

• US 6,760,482 B1
• Filed: 03/01/2002
• Issued: 07/06/2004
• Est. Priority Date: 02/19/1999
• Status: Expired due to Term

• Current Assignee: Unisearch Limited (University Of New South Wales)
• Original Assignee: Unisearch Limited (University Of New South Wales)
• Inventors: Taubman, David Scott
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US09/913,908
• Time in Patent Office: 858 Days
• Field of Search: 382/232, 382/239, 382/240, 382/248, 382/250, 382/251, 382/253, 358/426.02, 358/426.04, 358/426.11, 348/404.1, 348/408.1, 348/420.1, 375/240.02, 375/240.03, 375/240.18, 375/240.19, 375/240.2, 375/240.24
• US Class Current: 382/240
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform

Abstract

A method for lossy compression of images reduces visual distortion for a given compressed bit-rate or, equivalently, requires a lower bit-rate for a given level of visual distortion. An image is decomposed using a space-frequency transform and frequency bands are then partitioned into small blocks. The blocks are independently quantized and coded using an embedded block coder, so that each block bit-stream contains a large number of finely spaced truncation points. A visual distortion measure is computed for each block at each truncation point, where the metric is sensitive to masking properties of the Human Visual System. The distortion values and bit-stream lengths corresponding to each block'"'"'s truncation point are used to optimise overall visual distortion at one or more target bit-rates or to minimise the bit-rate corresponding to one or more target visual distortion levels. A computationally and memory efficient procedure is described for computing the visual distortion measure for each block'"'"'s truncation point, within each frequency band, as required by the subject compression system.

Claims

1. A method of compressing a digital image to produce a scalable bit stream having a plurality of quality layers, the method including the steps of:

a) decomposing the image into a set of distinct frequency bands using a space frequency transform;

b) partitioning the samples in each frequency band into code blocks;

c) for each code-block, generating an embedded bit-stream to represent the contents of the respective code block;

d) determining a rate-distortion optimal set of truncation points, n_i^l for each code-block, B_i, and each quality layer, l, subject to a constraint on the overall bit-rate or distortion for the layer in a manner which is sensitive to the masking property of the Human Visual System (HVS); and

e) storing the embedded bit-streams for each code-block.

2. The method as claimed in claim 1, wherein the code block truncation points are selected according to a rate-distortion optimisation criterion, using a distortion measure which is sensitive to masking in the HVS.

3. The method as claimed in claim 2, wherein contributions to the distortion measure from each sample in a code block are weighted as a function of a neighbourhood of samples surrounding the respective sample.

4. The method as claimed in claim 3, wherein the weighting function is a function of the magnitudes of the samples in the respective neighbourhood of samples.

5. The method as claimed in claim 3, wherein the weighting function is held constant over a sub-block of samples.

6. The method as claimed in claim 5, wherein the sub-block of samples has dimensions no larger than the full size of the respective code block.

7. The method as claimed in claim 5, wherein the weighting function is a function of the magnitude of samples taken only from within the sub-block of samples.

8. The method as claimed in claim 2, wherein the distortion measure is a weighted sum of the squared errors taken at each sample.

9. The method as claimed in claim 2, wherein the method is applied to colour image compression in an opponent colour representation, and wherein distortion from the chrominance channels is scaled differently to the distortion from the luminance channels prior to the application of the rate-distortion optimisation procedure.

10. The method as claimed in claim 9, wherein the distortion measure is modified to account for masking of chrominance artefacts by activity in the luminance channel.

11. The method as claimed in claim 10, wherein the distortion measure is modified to account for cross-channel masking.

12. The method as claimed in claim 1, wherein the method is performed by a coding engine using an algorithm which passes through the block multiple times for every bit-plane in the magnitude of the samples, starting with the most significant bit and working down to the least significant bit, the truncation points being identified with the completion of each coding pass.

13. The method as claimed in claim 12, wherein, for each code-block, B_i, the size of the bit-stream, R_iⁿ, at each truncation point, n, and the change in visual distortion, Δ

D_iⁿ, between truncation points n−

1 and n are determined and this information is supplied to a convex hull analysis system, which determines the set of truncation points, N_i={n₁,n₂, . . . }, which are candidates for the rate-distortion optimisation algorithm, as well as respective monotonically decreasing rate-distortion slopes S_i^n_j.

14. The method as claimed in claim 13, wherein summary information, N_i, R_iⁿ and S_iⁿ, is stored along with the embedded bit streams for each code block, the storing process taking place until sufficient information has been stored to enable truncation points to be determined for each code-block.

15. The method as claimed in claim 14, wherein the summary information is saved until all code-blocks in the image have been compressed.

16. The method as claimed in claim 15, wherein a truncation decision is made before all code-blocks in the image have been compressed, and the summary information is saved only for those code blocks for which truncation have not yet been made.

17. The method as claimed in claim 14, wherein the rate-distortion optimal set of truncation points n_i^l are determined for each code block with a plurality of layers, each layer targeted to a distinct bit-rate or distortion level, with each layer targeting successively higher image quality such that for each layer l there are n_i^l≧

n_i<sup>l−

1</sup> truncation points, and the final scalable image bit-stream is formed by including R_i^n_il−

R_i<sup>n_il−

1</sup>, samples from code-block B_i into layer l, along with respective auxiliary information to identify the number of samples which have been included for each block and the relevant truncation points.

18. The method as claimed in claim 13, wherein the coding engine uses an algorithm which passes through the code block multiple times for every bit-plane in the magnitude of the samples, starting with the most significant bit and working down to the least significant bit;

the truncation points being identified with the completion of each coding pass.

19. The method as claimed in claim 18, wherein, for each code-block, B_i, the size of the bit-stream, R_iⁿ, at each truncation point, n, and the change in visual distortion, Δ

D_iⁿ, between truncation points n−

1 and n are determined and this information is supplied to the convex hull analysis system to determine the set of truncation points, N_i={n₁,n₂, . . . }, which are candidates for the rate-distortion optimisation algorithm, as well as the monotonically decreasing rate-distortion slopes, S_i^n_j.

20. The method as claimed in claim 18, wherein the coding engine uses the EBCOT algorithm as herein before defined .

21. The method as claimed in claim 1, wherein all of the code blocks have substantially the same size, independently of the frequency band to which they belong.

22. The method as claimed in claim 21, wherein the size of the code blocks is substantially in the range 32×

32 to 64×

64.

23. The method as claimed in claim 1, wherein the block partitioning operation is implemented incrementally, generating new code blocks and sending them to the block coding system as the relevant frequency band samples become available.

24. The method as claimed in claim 1, wherein the space frequency domain transform is one selected from a Wavelet transform, a Wavelet packet transform, a Discrete Cosine transform, or a Fourier transform.

25. The method as claimed in claim 1, wherein a Wavelet transform is used, having a Mallat decomposition structure.

26. The method as claimed in claim 1, wherein the transform is implemented incrementally, producing new frequency band samples whenever new image samples become available to minimise the quantity of image or frequency band samples which must be buffered in working memory.

27. A method of decompressing a digital image from a compressed bit stream created by the method as claimed in claim 1, the decompression method including the steps of:

unpacking the layered compressed bit-stream to recover the truncated embedded bit-streams corresponding to each code-block;

decoding and assembling the code-blocks into a set of frequency bands; and

synthesising a reconstructed image from the frequency bands through the inverse transform.

28. The method as claimed in claim 27, wherein the blocks are decoded on demand, as the relevant frequency band samples are requested by the inverse transform.

29. The method as claimed in claim 27, wherein the synthesis operation proceeds incrementally, requesting frequency samples and using them to synthesise new image samples, as those image samples are requested by the application.