Encoding method and apparatus
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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).
-
Citations
50 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
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. - View Dependent Claims (23, 24, 25)
-
-
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. - View Dependent Claims (27, 28, 29)
-
-
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. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38)
-
-
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. - View Dependent Claims (40, 41, 42, 43, 44, 45, 46, 47, 48)
-
-
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.
-
Specification