Digital video compression

• US 20050100229A1
• Filed: 10/06/2004
• Published: 05/12/2005
• Est. Priority Date: 10/31/2003
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Poulouin, David Dominique M., Chan, Woei, Becker, Axel, Andrew, James Philip
• Granted Patent: US 7,822,281 B2
• Time in Patent Office: Days
• US Class Current: 382/232
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/117 Filters, e.g. for pre-processing or post-processing sub-band filter banks H04N19/635
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• 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/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

Abstract

A method of compressing a current image of a sequence of images is disclosed. The current image is transformed (502) with a predetermined transform to provide a set of transform coefficients, which are divided into blocks. An encoding termination condition is determined (714) for at least one block, and the block is encoded (605) in a series of coding passes. In a current coding pass, a performance measure is predicted, and encoding is terminated if the performance measure satisfies the encoding termination condition. Different color components may be given different weightings (713).

Claims

1. A method of compressing a current image of a sequence of images, said method comprising the steps of:

(a) transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) dividing the set of transform coefficients into blocks;

(c) determining an encoding termination condition for at least one block;

(d) encoding the at least one block in a series of coding passes;

(e) predicting, in a current coding pass, a performance measure; and

(f) terminating encoding of the at least one block if the predicted performance measure satisfies the encoding termination condition.

2. A method as claimed in claim 1 wherein said predicting step predicts a performance measure for a subsequent coding pass in the series and said terminating step terminates encoding of the at least one block before the subsequent coding pass.

3. A method as claimed in claim 2 wherein said predicting step comprises the steps of:

(e)(i) fitting a model to a set of performance measures of coding passes already coded in the series; and

(e)(ii) estimating the performance measure of the subsequent coding pass from the model.

4. A method as claimed in claim 3 wherein the set of performance measures comprises a convex hull of the coding passes already coded in the series.

5. A method as claimed in claim 1 wherein the performance measure is a rate-distortion slope and the encoding termination criterion is satisfied if the predicted rate-distortion slope is less than a rate-distortion cutoff threshold.

6. A method as claimed in claim 1, further comprising the steps of:

comparing one or more blocks with corresponding blocks of a previous image in the sequence; and

classifying one or more blocks as static if said comparing step shows that a difference between the one or more blocks and the corresponding previous blocks is small according to a predetermined criterion.

7. A method as claimed in claim 6 wherein, if the block being encoded is a static block, said predicting step is only performed if said encoding step has reached a bit-plane that is within a predetermined number of bit-planes of the truncation point of a corresponding block in the previous image of the sequence.

8. A method as claimed in claim 7 wherein the predetermined number of bit-planes is one.

9. A method as claimed in claim 6 wherein, for a static block, encoding is terminated if the encoding has reached the same bit-plane as a truncation bit-plane of a corresponding block of a previously encoded image of the sequence.

10. A method as claimed in claim 1 wherein encoding of the at least one block is not terminated by said terminating step if a predetermined number of bit-planes were encoded in a corresponding block of a previous image and said encoding step has not yet encoded the predetermined number of bit-planes.

11. A method as claimed in claim 10 wherein the predetermined number of bit-planes is two.

12. A method as claimed in claim 1 wherein encoding of the at least one block is not terminated by said terminating step if a codeword generated by said encoding step is less than a predetermined size.

13. A method as claimed in claim 12 wherein the predetermined size is three bytes.

14. A method as claimed in claim 1 wherein encoding of the at least one block is not terminated by said terminating step if there are no non-zero clean-up passes in the series of coding passes.

15. A method as claimed in claim 1 wherein the predetermined transform is a discrete wavelet transform.

16. A method as claimed in claim 3 wherein the set of performance measures comprises the performance measures of clean-up passes of the series of coding passes.

17. A method as claimed in claim 1 wherein said predicting step predicts a performance measure for the current coding pass.

18. A method as claimed in claim 17 wherein the encoding termination condition depends on a truncation point of a corresponding block of a previously encoded image of the sequence.

19. A method as claimed in claim 17 wherein the encoding termination condition is a rate-distortion cutoff threshold for the current image.

20. A method as claimed in claim 19 wherein the rate-distortion cutoff threshold is determined using an achieved rate and a rate-distortion cutoff threshold of a corresponding block of a previously encoded image of the sequence.

21. A method as claimed in claim 17 wherein encoding of the at least one block is not terminated by said terminating step if there are no non-zero clean-up passes in the series of coding passes.

22. A method as claimed in claim 6 wherein said comparing step comprises calculating a motion detection parameter for one or more of the blocks.

23. A method as claimed in claim 22 wherein the motion detection parameter comprises an inner product of a block and a corresponding previous block divided by the square root of the product of sums of squares of the block and the corresponding previous block.

24. A method as claimed in claim 22 wherein the predetermined criterion is met for a block if the motion detection parameter of the block is less than a threshold value.

25. A method as claimed in claim 24 wherein the image comprises a plurality of components and the threshold value is different for different components.

26. A method as claimed in claim 24 wherein the predetermined transform is a multi-level transform and the threshold value is different for different levels of the transformed image.

27. A method as claimed in claim 22, wherein the motion detection parameter is calculated using two bits per coefficient.

28. A method as claimed in claim 1 wherein the current image is defined with respect to a plurality of color-space components and said transforming, dividing, determining, encoding, predicting and terminating steps are performed to encode a first set of components, the method comprising the further steps of:

estimating a compressibility of the current image relative to a previous image in the sequence based on the encoded first set of components and corresponding encoded components of the previous image;

weighting the encoding termination condition based on the estimated compressibility; and

encoding a second set of components of the current image until the weighted encoding termination condition is reached.

29. A method of compressing a current image of a sequence of images, the method comprising the steps of:

(a) transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) dividing the set of transform coefficients into blocks;

(c) determining an encoding termination condition for at least one block;

(d) encoding the at least one block in a series of coding passes;

(e) predicting, in a current coding pass, a performance measure for a subsequent coding pass in the series; and

(f) terminating encoding of the at least one block before the subsequent coding pass if the predicted performance measure satisfies the encoding termination condition.

30. A method of compressing a current image of a sequence of images, the method comprising the steps of:

(a) transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) dividing the set of transform coefficients into blocks;

(c) comparing the blocks with corresponding blocks of a previous image in the sequence;

(d) designating at least one block as a static block if the comparing step shows that a difference between the at least one block and the corresponding previous block is small according to a predetermined criterion;

(e) encoding the transform coefficients to provide a compressed bit-stream wherein, if a current coefficient falls in a static block, the current coefficient is encoded to a truncation bit-plane that is the same as a truncation bit-plane of the corresponding previous block.

31. A method of compressing a current image of a sequence of images, the current image being defined with respect to a plurality of color-space components, said method comprising the steps of:

determining an encoding termination condition for the current image;

encoding a first set of components of the current image until the encoding termination condition is reached;

estimating a compressibility of the current image relative to a previous image in the sequence based on the encoded first set of components and corresponding encoded components of the previous image;

weighting the encoding termination condition based on the estimated compressibility; and

encoding a second set of components of the current image until the weighted encoding termination condition is reached.

32. A method as claimed in claim 31 wherein said estimating step comprises:

measuring achieved bit rates of the encoded first set of components;

retrieving achieved bit rates of corresponding components of the previous image;

comparing the achieved bit rates and the retrieved achieved bit rates, and calculating a compressibility based on said comparison.

33. A method as claimed in claim 31 wherein the weighting of the encoding termination condition provides later termination of the encoding of the second set if the current image is determined to be more compressible than the previous image.

34. A method as claimed in claim 31 wherein the weighting of the encoding termination condition provides earlier termination of the encoding of the second set if the current image is determined to be less compressible than the previous image.

35. A method as claimed in claim 31 wherein the first set of components comprises chrominance components and the second set of components comprises a luminance component.

36. A method as claimed in claim 35 wherein the weighting of the encoding termination condition of the luminance component provides later termination of the encoding of the luminance component if the current image is determined to be more compressible than the previous image.

37. A method as claimed in claim 35 wherein the luminance component weighting is unity if the current image is determined to be less compressible than the previous image.

38. A method as claimed in claim 35 wherein the encoding termination condition is a rate-distortion cutoff threshold and the weighted threshold is given by:

39. A method as claimed in claim 31 wherein the first set of components comprises a luminance component and the second set of components comprises at least one chrominance component.

40. A method as claimed in claim 39 wherein the weighting of the encoding termination condition of the at least one chrominance component provides later termination of the encoding of the at least one chrominance component if the current image is determined to be more compressible than the previous image.

41. A method as claimed in claim 39 wherein the weighting of the encoding termination condition of the at least one chrominance component provides earlier termination of the encoding if the current image is determined to be less compressible than the previous image.

42. A method as claimed in claim 39 wherein the encoding termination condition is a rate-distortion cutoff threshold and the weighted threshold is given by:

43. A method as claimed in claim 31 wherein said determining step comprises determining a rate-distortion cutoff threshold for the current image.

44. A method as claimed in claim 43 wherein the rate-distortion cutoff threshold of the current image is a function of an achieved rate in a previous image in the sequence and the rate-distortion cutoff threshold for the previous image.

45. A method as claimed in claim 31, wherein said encoding step comprises:

transforming a current component of the current image with a predetermined transform to provide a set of transform coefficients;

dividing the set of transform coefficients into blocks;

encoding each block until the encoding termination condition is met.

46. A method as claimed in claim 45 wherein the encoding termination condition is met if a rate-distortion slope of a current coding pass is less than a rate-distortion cutoff threshold of the current component.

47. A method as claimed in claim 35 comprising the further step of:

trimming the encoded coefficients of the second set of components.

48. A method as claimed in claim 47 wherein the trimming comprises discarding encoded data associated with coding passes having a rate-distortion slope that is less than the weighted rate-distortion cutoff threshold of the current component.

49. An apparatus for compressing a current image of a sequence of images, said apparatus comprising:

(a) means for transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) means for dividing the set of transform coefficients into blocks;

(c) means for determining an encoding termination condition for at least one block;

(d) means for encoding the at least one block in a series of coding passes;

(e) means for predicting, in a current coding pass, a performance measure; and

(f) means for terminating encoding of the at least one block if the predicted performance measure satisfies the encoding termination condition.

50. An apparatus for compressing a current image of a sequence of images, the apparatus comprising:

(a) means for transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) means for dividing the set of transform coefficients into blocks;

(c) means for determining an encoding termination condition for at least one block;

(d) means for encoding the at least one block in a series of coding passes;

(e) means for predicting, in a current coding pass, a performance measure for a subsequent coding pass in the series; and

(f) means for terminating encoding of the at least one block before the subsequent coding pass if the predicted performance measure satisfies the encoding termination condition.

51. An apparatus for compressing a current image of a sequence of images, the apparatus comprising:

(a) means for transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) means for dividing the set of transform coefficients into blocks;

(c) means for comparing the blocks with corresponding blocks of a previous image in the sequence;

(d) means for designating at least one block as a static block if the means for comparing shows that a difference between the at least one block and the corresponding previous block is small according to a predetermined criterion;

(e) means for encoding the transform coefficients to provide a compressed bit-stream wherein, if a current coefficient falls in a static block, the current coefficient is encoded to a truncation bit-plane that is the same as a truncation bit-plane of the corresponding previous block.

52. An apparatus for compressing a current image of a sequence of images, the current image being defined with respect to a plurality of color-space components, the apparatus comprising:

means for determining an encoding termination condition for the current image;

means for encoding a first set of components of the current image until the encoding termination condition is reached;

means for estimating a compressibility of the current image relative to a previous image in the sequence based on the encoded first set of components and corresponding encoded components of the previous image;

means for weighting the encoding termination condition based on the estimated compressibility; and

means for encoding a second set of components of the current image until the weighted encoding termination condition is reached.

53. A system for compressing a current image in a sequence of images, the system comprising:

a storage unit that stores information descriptive of the compression of previous images in the sequence; and

a processor connected to said storage unit and adapted to;

transform the current image with a predetermined transform to provide a set of transform coefficients;

divide the set of transform coefficients into blocks;

determine an encoding termination condition for at least one block,

wherein the termination condition depends on the stored information for one or more previous images in the sequence;

encode the at least one block in a series of coding passes;

predict, in a current coding pass, a performance measure;

terminate encoding of the at least one block if the predicted performance measure satisfies the encoding termination condition; and

store information descriptive of the compression of the current image in said storage unit.

54. A system for compressing a current image in a sequence of images, the system comprising:

a storage unit that stores information descriptive of the compression of previous images in the sequence; and

a processor connected to said storage unit and adapted to;

transform the current image with a predetermined transform to provide a set of transform coefficients;

divide the set of transform coefficients into blocks;

determine an encoding termination condition for at least one block,

wherein the termination condition depends on the stored information for one or more previous images in the sequence;

encode the at least one block in a series of coding passes;

predict, in a current coding pass, a performance measure for a subsequent coding pass in the series;

terminate encoding of the at least one block before the subsequent coding pass if the predicted performance measure satisfies the encoding termination condition; and

store information descriptive of the compression of the current image in said storage unit.

55. A system for compressing a current image of a sequence of images, the system comprising:

a storage unit that stores transform coefficients of the current image and transform coefficients of a previous image in the sequence wherein the transform coefficients are obtained by applying a predetermined transform to the image and the previous image and wherein the stored transform coefficients are divided into blocks; and

a processing unit that;

(a) compares each block of the current image with the corresponding block of the previous image and designates as static those blocks of the current image that are substantially the same as the corresponding previous block; and

(b) encodes the transform coefficients of the current image to provide a compressed bit-stream wherein, if a current one of the coefficients falls in a static block, the processing unit encodes the coefficient to a truncation bit-plane that is the same as the truncation bit-plane of the corresponding previous block.

56. A system for compressing a current image of a sequence of images, the system comprising:

a storage unit that stores a compressed version of a previous image in the sequence; and

a processing unit that;

(a) determines an encoding termination condition for the current image;

(b) encodes a first set of components of the current image until the encoding termination condition is reached;

(c) estimates a compressibility of the current image relative to the previous image based on the encoded set of components and corresponding encoded components retrieved from the storage unit;

(d) weights the encoding termination condition based on the estimated compressibility, and

(e) encodes a second set of components of the current image until the weighted encoding termination condition is reached.

57. A computer program product comprising machine-readable program code recorded on a machine-readable recording medium, for controlling the operation of a data processing apparatus on which the program code executes to perform a method of compressing a current image of a sequence of images, the method comprising the steps of:

(a) transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) dividing the set of transform coefficients into blocks;

(c) determining an encoding termination condition for at least one block;

(d) encoding the at least one block in a series of coding passes;

(e) predicting, in a current coding pass, a performance measure; and

(f) terminating encoding of the at least one block if the predicted performance measure satisfies the encoding termination condition.

58. A computer program product comprising machine-readable program code recorded on a machine-readable recording medium, for controlling the operation of a data processing apparatus on which the program code executes to perform a method of compressing a current image of a sequence of images, the method comprising the steps of:

(a) transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) dividing the set of transform coefficients into blocks;

(c) determining an encoding termination condition for at least one block;

(d) encoding the at least one block in a series of coding passes;

(e) predicting, in a current coding pass, a performance measure for a subsequent coding pass in the series; and

(f) terminating encoding of the at least one block before the subsequent coding pass if the predicted performance measure satisfies the encoding termination condition.

59. A computer program product comprising machine-readable program code recorded on a machine-readable recording medium, for controlling the operation of a data processing apparatus on which the program code executes to perform a method of compressing a current image of a sequence of images, the method comprising the steps of:

(a) transforming the current image with a predetermined transform to provide a set of transform coefficients;

(b) dividing the set of transform coefficients into blocks;

(c) comparing the blocks with corresponding blocks of a previous image in the sequence;

(d) designating at least one block as a static block if the comparing step shows that a difference between the at least one block and the corresponding previous block is small according to a predetermined criterion;

(e) encoding the transform coefficients to provide a compressed bit-stream wherein, if a current coefficient falls in a static block, the current coefficient is encoded to a truncation bit-plane that is the same as a truncation bit-plane of the corresponding previous block.

60. A computer program product comprising machine-readable program code recorded on a machine-readable recording medium, for controlling the operation of a data processing apparatus on which the program code executes to perform a method of compressing a current image of a sequence of images, the current image being defined with respect to a plurality of color-space components, the method comprising the steps of:

determining an encoding termination condition for the current image;

encoding a first set of components of the current image until the encoding termination condition is reached;

estimating a compressibility of the current image relative to a previous image in the sequence based on the encoded first set of components and corresponding encoded components of the previous image;

weighting the encoding termination condition based on the estimated compressibility; and

encoding a second set of components of the current image until the weighted encoding termination condition is reached.