Encoding method and apparatus

• US 6,978,048 B1
• Filed: 03/10/2000
• Issued: 12/20/2005
• Est. Priority Date: 03/12/1999
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Andrew, James Philip, Majani, Eric, Higginbottom, Paul Raymond
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Dang, Duy M.
• Application Number:
  US09/523,595
• Time in Patent Office: 2,111 Days
• Field of Search: 382232-251, 382/276, 375/240.03, 375/240.01, 375/240.11, 375/240.24, 375/240.19, 375/240.18
• US Class Current: 382/240
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform

Abstract

A method of encoding an digital image (502) by a discrete wavelet transform (DWT) to a predetermined level of decomposition on a block by block basis, each block (1501, 1504, 1506) having a specified size in number of coefficients, is disclosed. The image is divided into tiles, each having dimensions required to produce the number of coefficients in a first dimension of the transformed block at the predetermined level of decomposition, and less than the number of coefficients in a second dimension of the transformed block. At a particular DWT level, tiles are decomposed. HH, HL and LH subband coefficients are accumulated to form blocks of specified size, and these are encoded to a bit stream (402). A predetermined number of associated LL subband coefficients are similarly accumulated, the process performed recursively per DWT level until the predetermined decomposition level is attained, and the corresponding LL subband coefficients encoded to the bit stream (402).

Claims

1. A method of encoding a digital image comprising a plurality of pixels, the image being able to be transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition, and capable of being encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, the method comprising the steps of:

a) dividing the image into a plurality of tiles, each tile having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, wherein the predetermined level of DWT decomposition is greater than one, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition;

b) selecting a current tile;

c) decomposing the current tile, using the DWT, to one level of decomposition to form a plurality of subbands including a LL, LH, HL and HH subband;

d) accumulating coefficients in each subband of the LH, HL and HH subbands to form blocks of the specified block size, and encoding each block to a bit stream;

e) accumulating LL subband coefficients and repeating steps b) to e) until a predetermined number of coefficients, dependent on the specified block size, of the LL subband have been accumulated;

f) assigning as a current tile the predetermined number of accumulated LL sub-band coefficients;

g) repeating steps c) to f) until the predetermined level of DWT decomposition is reached; and

h) encoding the LL subband into the bit stream.

2. A method according to claim 1, wherein accumulating coefficients in each subband includes accumulating coefficients in corresponding subbands of different tiles.

3. A method according to claim 1, wherein encoding comprises encoding each block substantially as each block is accumulated.

4. A method according to claim 1, wherein the specified block size comprises H coefficients in the first dimension by W coefficients in the second dimension.

5. A method according to claim 4, wherein the number of coefficients in the first dimension is equal to the number of coefficients in the second dimension (W=H).

6. A method according to claim 4, wherein the predetermined level of DWT decomposition is J and the minimum number of pixels in a first dimension of each tile is defined by 2^JH+O(2^J−

1), where O is an overlap required by the DWT filter.

7. A method according to claim 6, wherein the number of pixels in a second dimension of each tile is less than that of the first dimension and is defined by 2W+O.

8. A method according to claim 6, wherein the DWT filter is a Daubechies 9/7 filter and the overlap required is 7 pixels or coefficients coefficient (O=7).

9. A method according to claim 6, wherein the DWT filter is a Haar filter and the overlap required is no pixels or coefficient (O=0).

10. A method of decoding a digital image comprising a plurality of pixels, the image having been transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition, and having been encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, the image having been divided into a plurality of tiles, each tile having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition, the decoding method comprising substantially the inverse steps to those recited in claim 1.

11. An apparatus adapted for decoding a digital image comprising a plurality of pixels, the image having been transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition, and having been encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, the image having been divided into a plurality of tiles, each tile having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition, said apparatus adapted to implement the method recited in claim 10.

12. A method of encoding a digital image comprising a plurality of pixels, the image being able to be transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition and capable of being encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, the method comprising the steps of:

a) dividing the image into a plurality of tiles, each tile having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, wherein the predetermined level of DWT decomposition is greater than one, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition;

b) selecting a tile of the image as a current tile;

c) decomposing the current tile, using the DWT, to provide a plurality of coefficients in LL, LH, HL and HH subbands;

d) encoding coefficients of the LH, HL, HH subbands of a current level of DWT decomposition into a bit-stream;

e) determining if the current level of DWT decomposition is the predetermined level of DWT decomposition, including

ea) encoding the coefficients of the LL subband into the bitstream, if the current level of DWT decomposition is the predetermined level of DWT decomposition, and repeating steps b) to e), and

eb) storing coefficients not previously encoded of the LL subband if the current level of DWT decomposition is not the predetermined level of DWT decomposition; and

f) determining if the number of stored coefficients of the LL subband at the current level of DWT decomposition is at least a predetermined number dependent on the specified block size, including

fa) assigning the predetermined number of LL coefficients as a current tile, if the number of stored LL coefficients is at least the predetermined number, and repeating steps c) to f), and

fb) repeating steps b) to f) if the number of stored LL coefficients is less than the predetermined number.

13. A method according to claim 12, wherein the specified block size comprises H coefficients in the first dimension by W coefficients in the second dimension.

14. A method according to claim 13, wherein the number of coefficients in the first dimension is equal to the number of coefficients in the second dimension of the specified block (W=H).

15. A method according to claim 13, wherein the predetermined level of DWT decomposition is J and the minimum number of pixels in a first dimension of each tile is defined by 2^JH+O(2^J−

1), where O is an overlap required by the DWT filter.

16. A method according to claim 15, wherein the number of pixels in a second dimension of each tile is less than that of the first dimension and is defined by 2W+O.

17. A method according to claim 15, wherein the DWT filter is a Daubechies 9/7 filter and the overlap required is 7 pixels or coefficient (O=7).

18. A method according to claim 15, wherein the DWT filter is a Haar filter and the overlap required is no pixels or coefficient (O=0).

19. A method according to claim 12, wherein the encoding is preformed by a Bit-plane entropy Encoder.

20. A method according to claim 12, wherein the encoding is preformed by an Arithmetic Encoder.

21. A method according to claim 12, wherein the encoding is preformed by a hybrid encoder comprising an Arithmetic and Bit-plane entropy Encoder.

22. An apparatus for encoding an image, the image being capable of being transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition and capable of being encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, the apparatus comprising:

a) means for dividing the image into a plurality of tiles, each tile having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, wherein the predetermined level of DWT decomposition is greater than one, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition;

b) selecting means for selecting a current tile;

c) decomposing means for decomposing the current tile using the DWT to one level of decomposition to form a plurality of subbands including a LL, LH, HL and HHH subband;

d) means for accumulating a predetermined number of coefficients, dependent on the specified block size, of the LL sub-band coefficients;

e) means for assigning, as a current tile, the predetermined number of accumulated LL subband coefficients;

f) means for feeding back the current tile to the decomposing means for decomposing the current tile to a further level of decomposition;

g) means for accumulating coefficients in each subband of the LH, HL and HH subbands to form blocks of the specified size, and accumulating at least one block of the specified block size in the LL subband at the predetermined level; and

h) encoding means for encoding each block to a bit stream as each block is formed, wherein said encoding means (h) encodes LH, HL and HH subbands to the bit stream when said accumulating means (g) forms corresponding blocks of the specified block size.

23. An apparatus according to claim 22, wherein said encoder means is a bit-plane entropy encoder.

24. An apparatus according to claim 22, wherein said encoder means is an Arithmetic Encoder.

25. An apparatus according to claim 22, wherein said encoder means is a hybrid encoder comprising an Arithmetic Encoder and Bit-plane entropy Encoder.

26. An apparatus for encoding an image, the image being capable of being transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition, and capable of being encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, the apparatus comprising:

storage means for storing at least a portion of the image, the portion of the image having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, wherein the predetermined level of DWT decomposition is greater than one, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition;

first and second filtering means for successively applying a linear transform to a first dimension and a second dimension of corresponding image portions respectively to provide LL, LH, HL and HH subbands, each subband comprising at least one coefficient;

partial band storage means for accumulating a predetermined number of coefficients, dependent on the specified block size, of the LL subband, and using the accumulated LL coefficient as an image portion for refiltering by said first and second filtering means to achieve a next level decomposition;

subband storage means for accumulating the blocks of specified block size for each level in the LH, HL and HH subbands, and accumulating the blocks of specified block size in the LL subband at the predetermined level of decomposition; and

encoder means for encoding each accumulated block into a bit stream as each block is formed, wherein said encoder means encodes the LH, HL and HH subbands to the bit stream when said subband storage means accumulates corresponding blocks of the specified block size.

27. An apparatus according to claim 26, wherein said encoder means is a bit-plane entropy encoder.

28. An apparatus according to claim 26, wherein said encoder means is an Arithmetic Encoder.

29. An apparatus according to claim 26, wherein said encoder means is a hybrid encoder comprising an Arithmetic Encoder and Bit-plane entropy Encoder.

30. A computer readable memory medium for storing a program for an apparatus which encodes a digital image comprising a plurality of pixels, the image being able to be transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition and capable of being encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, said program comprising:

a) code for a dividing step, of dividing the image into a plurality of tiles, each tile having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, wherein the predetermined level of DWT decomposition is greater than one, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition;

b) code for a selecting step, of selecting a current tile;

c) code for a decomposing step, of decomposing the current tile, using the DWT, to one level of decomposition to form a plurality of subbands including an LL, LH, HL and HH subband;

d) code for an accumulating step, of accumulating coefficients in each subband of the LH, HL and HH subbands to form blocks of the specified block size and for encoding each block to a bit stream;

e) code for an accumulating step, of accumulating LL subband coefficients, and for repeating steps b) to e) until a predetermined number of coefficients, dependent on the specified block size, of the LL subband have been accumulated;

f) code for an assigning step, of assigning as a current tile the predetermined number of accumulated LL subband coefficients;

g) code for repeating steps c) to g) until the predetermined level of DWT decomposition is reached; and

h) code for an encoding step, of encoding the LL subband into the bit stream.

31. A computer readable memory medium according to claim 30, wherein said code for accumulating coefficients in each subband is adapted to include steps for accumulating coefficients in corresponding subbands of different tiles.

32. A computer readable memory medium according to claim 30, wherein said code for encoding is adapted to include steps for encoding each block substantially as each block is accumulated.

33. A computer readable memory medium according to claim 30, said code being adapted so that the specified block size comprises H coefficients in the first dimension by W coefficients in the second dimension.

34. A computer readable memory medium according to claim 33, said code being adapted so that the number of coefficients in the first dimension is equal to the number of coefficients on the second dimension (W=H).

35. A computer readable memory medium according to claim 33, said code being adapted so that the predetermined level of DWT decomposition is J and the minimum number of pixels in a first dimension of each tile is defined by 2^JH+O(2^J−

1), where O is an overlap required by the DWT filter.

36. A computer readable memory medium according to claim 35, said code being adapted so that the number of pixels in a second dimension of each tile is less than that of the first dimension and is defined by 2W+O.

37. A computer readable memory medium according to claim 35, said code being adapted so that the DWT filter is a Daubecbies 9/7 filter and the overlap required is 7 pixels or coefficients (O=7).

38. A computer readable memory medium according to claim 35, said code being adapted so that the DWT filter is a Haar filter and the overlap required is no pixels or coefficients (O=0).

39. A computer readable memory medium for storing a program for an apparatus which encodes a digital image comprising a plurality of pixels, the image being able to be transformed by a discrete wavelet transform (DWT) to a predetermined level of decomposition and capable of being encoded on a block by block basis, each block having a specified block size in number of coefficients, in a first dimension and a second dimension, said program comprising:

a) code for a dividing step, of dividing the image into a plurality of tiles, each tile having firstly, substantially a minimum number of pixels required to produce the number of coefficients in the first dimension of the block at the predetermined level of DWT decomposition, wherein the predetermined level of DWT decomposition is greater than one, and secondly, less than a minimum number of pixels required to produce the number of coefficients in the second dimension of the block at the predetermined level of DWT decomposition;

b) code for a selecting step, of selecting a tile of the image as a current tile;

c) code for a decomposing step, of decomposing the current tile, using the DWT filter, to provide a plurality of coefficients in LL, LH, HL and HH subbands;

d) code for an encoding step, of encoding coefficients of the LH, HL, and HH subbands of a current level of DWT decomposition into a bitstream;

e) code for a determining step, of determining if the current level of DWT decomposition is the predetermined level of DWT decomposition, including

ea) code for an encoding step, of encoding the coefficients of the LL subband into the bitstream, if the current level of DWT decomposition is the predetermined level of DWT decomposition, and repeating steps b) to e), and

eb) code for a storing step, of storing coefficients not previously encoded of the LL subband if the current level of DWT decomposition is not the predetermined level of DWT decomposition; and

f) code for a determining step, of determining if the number of the stored coefficients of the LL subband at the current level of DWT decomposition is at least a predetermined number dependent on the specified block size, including

fa) code for an assigning step, of assigning the predetermined number of LL coefficients as a current tile, if the number of stored LL coefficients is at least the predetermined number, and repeating steps c) to f), and

fb) code for a repeating step, of repeating steps b) to f) if the number of stored LL coefficients is less than the predetermined number.

40. A computer readable memory medium according to claim 39, said code being adapted so that specified block size comprises H coefficients in the first dimension by W coefficients in the second dimension.

41. A computer readable memory medium according to claim 40, said code being adapted so that the number of coefficients in the first dimension is equal to the number of coefficients in the second dimension of the specified block (W=H).

42. A computer readable memory medium according to claim 40, said code being adapted so that the predetermined level of DWT decomposition is J and the minimum number of pixels in a first dimension of each tile is defined by 2^JH+O(2^J−

1), where O is an overlap required by the DWT filter.

43. A computer readable memory medium according to claim 42, said code being adapted so that the number of pixels in a second dimension of each tile is less than that of the first dimension and is defined by 2W+O.

44. A computer readable memory medium according to claim 42, said code being adapted so that the DWT filter is a Daubechies 9/7 filter and the overlap required is 7 pixels or coefficients (O=7).

45. A computer readable memory medium according to claim 42, said code being adapted so that the DWT filter is a Haar filter and the overlap required is no pixels or coefficients (O=0).

46. A computer readable memory medium according to claim 39, wherein said steps for encoding are adapted to perform encoding in accordance with a bit-plane entropy encoding process.

47. A computer readable memory medium according to claim 39, wherein said steps for encoding are adapted to perform encoding in accordance with an Arithmetic Encoding process.

48. A computer readable memory medium according to claim 39, wherein said steps for encoding are adapted to performed encoding in accordance with a hybrid encoding process comprising Arithmetic and Bit-plane entropy encoding sub-processes.

49. A method of encoding a digital image on a block by block basis, block having a specified block size in number of coefficients, the method comprising the steps of:

a) dividing the image into a plurality of tiles, each tile having a number of pixels less than required to produce the number of coefficients in the block, to decompose each tile to form a plurality of subbands including a LL, LH, HL and HH subband by using a discrete wavelet transform (DWT) to a predetermined level of decomposition greater than one;

b) selecting a current tile;

c) decomposing the current tile to form a plurality of subbands including a LL, LH, HL and HH subband by using the DWT;

d) encoding LH, HL and HH subbands to a bit stream;

e) accumulating LL subband coefficients and repeating steps b) to e) until a predetermined number of coefficients, dependent on the specified block size, of the LL subband have been accumulated;

f) assigning, as a current tile, the predetermined number of accumulated LL subband coefficients;

g) repeating steps c) to g) until the predetermined level of decomposition is reached; and

h) encoding the LL subband to the bit stream.

50. An apparatus for encoding a digital image on a block by block basis, each block having a specified block size in number of coefficients, said apparatus comprising:

a) means for dividing the image into a plurality of tiles, each tile having a number of pixels less than required to produce the number of coefficients in the block, to decompose each tile to form a plurality of subbands including a LL, LH, HL and HH subband by using a discrete wavelet transform (DWT) to a predetermined level of decomposition greater than one;

b) selecting means for selecting a current tile;

c) decomposing means for decomposing the current tile to form a plurality of subbands including a LL, LH, HL and HH subband by using the DWT;

d) encoding means for encoding LH, HL and HH subbands to a bit stream;

e) means for accumulating LL subbands until a predetermined number of coefficients, dependent on the specified block size, of the LL subband have been accumulated;

f) means for assigning, as a current tile, the predetermined number of accumulated LL subband coefficients; and

g) encoding means for encoding the LL subband to the bit stream.