Curved wavelet transform for image and video compression

• US 7,418,144 B2
• Filed: 03/01/2005
• Issued: 08/26/2008
• Est. Priority Date: 03/03/2004
• Status: Expired due to Fees

• Current Assignee: Her Majesty The Queen In Right of Canada As Represented By The Minister of National Defence
• Original Assignee: Her Majesty The Queen In Right Of Canada, As Represented By The Minister Of Industry, Through The Communications Research Centre Canada
• Inventors: Wang, Demin, Zhang, Liang, Vincent, Andre
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US11/068,160
• Publication Number:
  US 20050196060A1
• Time in Patent Office: 1,274 Days
• Field of Search: 382232-233, 382/236, 382/238, 382/239, 382242-251, 382/253, 375/240.19
• US Class Current: 382/240
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/619 the transform being operated outside the prediction loop
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

A curved wavelet transform and a related image/video compression system are disclosed. The curved wavelet transform (CWT) is carried out by applying one-dimensional (1-D) wavelet filters along curves, rather than along only horizontal and vertical directions. The image/video compression system includes a curve determination unit, a curved wavelet transform unit, a wavelet coefficient quantization unit, a wavelet coefficient coding unit, and a curve coding unit. The quantization and coding of the wavelet coefficients are related to the curves. In one embodiment, recursive wavelet filters are used for inverse wavelet decomposition. The system provides higher compression capability than conventional wavelet-based image compression systems.

Claims

1. A method of image transformation comprising:

transforming an n-dimensional image, wherein n≧

2, into a wavelet-transformed image comprised of wavelet coefficients by performing one-dimensional wavelet transformations on image values along a plurality of curved paths dependent upon content of the image, using the steps of;

a) determining the plurality of curved paths within the image;

b) determining image values along each of the curved paths;

d) performing the one-dimensional wavelet transformations on the image values along the curved paths using a low-pass 1-D wavelet filter and a high-pass 1-D wavelet filter along each of the curved paths to obtain a low-pass filtered image comprised of low-pass wavelet coefficients and a high-pass filtered image comprised of high-pass wavelet coefficients; and

,

e) down-sampling the low-pass and the high-pass filtered images along the first coordinate to obtain down-sampled low-pass and high-pass filtered images.

2. A method as defined in claim 1 wherein the content of the image includes at least one of:

contours within the image, edges within the image, luminance, texture, and color; and

wherein the wavelet transformations on image values are performed using wavelet filters having supports along the plurality of curved paths.

3. A method as defined in claim 2, wherein the n-dimensional image is representable as an n-dimensional pixel array;

and wherein substantially each pixel is associated with a curved path from the plurality of the curved paths.

4. A method as defined in claim 3, wherein

the plurality of curved paths within the image is representable by single-valued contiguous functions of a first coordinate associated with a dimension of the n-dimensional image, the plurality of curved paths being thereby associated with the first coordinate.

5. A method as defined in claim 4, wherein transforming an n-dimensional image further comprises the step of:

c) extending curved paths from the plurality of curved paths.

6. A method as defined in claim 5, further comprising:

f) transforming the down-sampled low-pass and high-pass filtered images along pluralities of curved paths in respective down-sampled images, said curved paths being dependent upon contents thereof and representable by single-valued contiguous functions of a second coordinate in the image associated with another dimension of the n-dimensional image.

7. A method as defined in claim 5, wherein step c) further comprises:

for each of the curved paths from the plurality of curved paths having an end in the interior of the image, extending the curved path at the end in the interior of the image by appending thereto image values from adjacent curved paths.

8. A method as defined in claim 6, further comprising:

g) decomposing the image into a hierarchical sequence of down-sampled low-pass and high-pass filtered images comprised of wavelet coefficients by recursively performing steps a)-f) for down-sampled low-pass filtered images at successively decreasing resolution levels.

9. A method as defined in claim 4, wherein the step of determining the plurality of curved paths comprises the steps of:

i) dividing the image into a plurality of portions;

ii) performing 1-D wavelet transformations of each portion along multiple pluralities of straight paths for obtaining multiple pluralities of wavelet coefficients, wherein each said plurality of straight paths is characterized by a different pre-defined orientation in the image portion;

iii) for each image portion, selecting one of the multiple pluralities of straight paths by comparing the multiple pluralities of wavelet coefficients according to a pre-determined criterion; and

iv) forming curved paths in the image from connecting straight paths from the selected pluralities of straight paths from different image portions.

10. A method as defined in claim 9, wherein step iii) comprises computing a measure of rate distortion for the image portion for each of the multiple pluralities of wavelet coefficients, and wherein the pre-determined criterion is to optimize the measure of rate distortion.

11. A method as defined in claim 9, wherein step iii) comprises computing a measure of high-pass wavelet coefficients for the image portion for each of the pre-defined orientations, and wherein the pre-determined criterion is a minimization of the measure of the high-pass wavelet coefficients.

12. A method of encoding an n-dimensional image comprising the steps of:

A. transforming the n-dimensional image according to the method of image transformation as defined in claim 6 for obtaining a wavelet-transformed image comprised of wavelet coefficients obtained by wavelet filtering along curved paths;

B. quantizing the wavelet coefficients; and

C. coding the wavelet coefficients and their corresponding curved paths for obtaining a coded representation of the image.

13. A method of encoding an n-dimensional image as defined in claim 12, wherein step B includes adapting a quantization step size according to orientations of the curved path used to compute the wavelet coefficients.

14. A method of encoding an n-dimensional image as defined in claim 12, wherein step C is performed using zero-tree structures adaptive to the curved paths.

15. A method of decoding an n-dimensional image encoded by the method of claim 12, comprising the steps of:

D. receiving the encoded image;

E. decoding information defining the curved paths from the received coded image representation;

F. decoding the wavelet coefficients from the received coded image representation using the decoded information defining the curved paths;

G. de-quantizing the wavelet coefficients using the decoded information defining the curved path; and

,

H. performing multi-level inverse wavelet transform along the curved paths.

18. A method as defined in claim 5, wherein step c) is performed by repeating at least one of a first and a last image value in the sequence of image values along the curved path at the beginning and the end thereof, respectively.

19. A method of encoding an n-dimensional image comprising the steps of:

K. transforming the n-dimensional image according to the method of image transformation as defined in claim 18 for obtaining a wavelet-transformed image comprised of wavelet coefficients obtained by wavelet filtering along curved paths;

L. quantizing the wavelet coefficients; and

M. coding the wavelet coefficients and their corresponding curved paths for obtaining a coded representation of the image.

20. A method of decoding an n-dimensional image encoded by the method of claim 19, comprising the steps of:

N. receiving the encoded image representation;

O. decoding information defining the curved paths from the received coded image representation;

P. decoding the wavelet coefficients from the received coded image representation using the decoded information defining the curved paths;

Q. de-quantizing the wavelet coefficients using the decoded information defining the curved path; and

,

R. performing multi-level inverse wavelet transform along the curved paths using recursive wavelet filters.

21. A method of decoding according to claim 20, wherein step R comprises, for each curved path, the steps of:

computing a first image value f(0) along the curved path from a set of (L+1) first wavelet coefficients F(k), k=0, . . . L, along the curved path, wherein integer L is a half-length of the recursive filter; and

sequentially computing image values f(i), wherein integer i=1,2, . . . is an index of image values and respective wavelet coefficients along the curved path, in a direction of increasing i along the curved path from L preceding image values f(i−

1), . . . , f(i−

L) and (L+1) following wavelet coefficients, wherein f(i)=f(0) for i<

0.

16. An image encoding system for encoding and compressing images into encoded image data, the images represented using arrays of pixels, the image encoding system comprising:

a curve determination unit for determining a plurality of curved paths in an image wherein substantially each pixel is associated with a curved path from the plurality of curved paths;

a curved wavelet transform unit for performing wavelet transformations of image values along the plurality of curved paths and for outputting wavelet transformed images represented by wavelet coefficients;

a curve coding unit for coding the plurality of curved paths;

a wavelet coefficient quantization unit for performing curved path adaptive quantization of the wavelet coefficients; and

,

a wavelet coefficient coding unit for performing curved path adaptive coding of the wavelet coefficients.

17. An image decoding system for decoding and restoration of images encoded by an image encoding system according to claim 16, the image decoding system comprising:

a curve decoding unit for decoding information defining the curved paths;

a wavelet coefficient decoding unit responsive to the decoded information defining the curved paths for adaptively decoding wavelet coefficients for the image;

a wavelet coefficient de-quantization unit for de-quantization of the decoded wavelet coefficients of the image; and

,

an inverse curved wavelet transform unit for performing inverse wavelet transformations for restoring image values along the curved paths in the image.