Method and apparatus for efficiently encoding and decoding image sequences

• US 4,816,914 A
• Filed: 01/07/1987
• Issued: 03/28/1989
• Est. Priority Date: 01/07/1987
• Status: Expired due to Term

• Current Assignee: Polycom Incorporated (HP Inc.)
• Original Assignee: Pictel Corporation
• Inventors: Ericsson, S. Staffan
• Primary Examiner(s): Groody, James J.
• Assistant Examiner(s): Kostak, Victor R.
• Application Number:
  US07/001,326
• Time in Patent Office: 811 Days
• Field of Search: 358/136, 358/135, 358/105, 358/133, 358/280, 358/141, 382/50
• US Class Current: 375/240.03
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• 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/50 using predictive coding H04N19/61 takes precedence
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding

Abstract

A method and apparatus, for encoding transform coefficient data representing an error or a motion description of each of a plurality of blocks in one image frame of a timed sequence of image frames, identify those blocks for which data will be transmitted, quad-tree encode, and then variable length encode the locations of the blocks. The bit rate can be controlled by varying the quantization of the encoded data and preferably quantization step size is predicted prior to encoding the data. Further, the quad-tree encoding process can be terminated after the coding process generates a selected number of bits. At the receiver, the method and apparatus provide a multiple lookup table method for decoding the variable length coded data.

Claims

1. A method for encoding transform coefficient data associated with the transform of an image frame, the coefficient data being represented in a two-dimensional array, the method comprising the steps of

identifying those coefficients of the coefficient data associated with the transform which will be transmitted to a receiver,

quad-tree encoding the array locations of those coefficients which will be transmitted, and

encoding, using a variable length coding procedure, the quad-tree data code words.

2. The method of claim 1 further wherein said identifying step comprises the step of

subjecting said coefficients to a thresholding and quantizing process for reducing the number of coefficient data bits to be transmitted, and

whereby the coefficient data of said image is represented by fewer data bits as quantizer step size increases.

3. The method of claim 2 further comprising the steps of

subjecting said coefficients to a thresholding process for reducing the coefficient data transmitted,

whereby the coefficient data of said image is represented by fewer data bits as the threshold level increases.

4. The method of claim 1 further comprising the step of

encoding, using a variable length coding procedure, the value of the transform coefficient data for each quad-tree data code word identified array location.

5. The method of claim 1 wherein said quad tree encoding step comprises the steps of

assigning a selected number of bits to said quad tree encoding step,

performing said quad tree encoding of the transform coefficients from low to high frequency representing components, and

terminating said quad-tree encoding when said selected number of code bits has been exhausted.

6. The method of claim 1 further comprising the step of

decoding, at a receiving station, the variable length coded data, said decoding step comprising the steps of

applying a received data stream to a first and a second lookup table, said first lookup table being responsive to a first number of sequentially received bits of each variable length code word beginning at the first bit of each word, said number of bits being less than the length of the longest variable length code word, and said second lookup table being responsive to a second number of sequentially received bits of each variable length code word beginning after the first bit of each word, said second number of bits being less than the length of the longest variable length code word, and the sum of said first number and said second number being at least equal to the length of the longest variable length code word,

setting a flag whenever said variable length code word cannot be decoded using only the first lookup table, and

decoding said variable length code word using said second lookup table whenever said flag is set and using said first table only when there is no flag.

7. The method of claim 6 wherein said setting step comprises the step of

responding to a unique code word output of said first lookup table for setting said flag.

8. The method of claim 6 wherein said setting step comprises the step of

responding to a flag enable output of said first lookup table for setting said flag.

9. The method of claim 1 further comprising the step of

predicting a quantization step size for an image from available image statistics, and prior to encoding said image.

10. The method of claim 9 wherein said predicting step comprises the step of

selecting said quantization step size based upon the quantization step size for the previous image, the number of blocks completely coded in the previous image, a minimum number of blocks to be coded for this image, a total prediction error energy for this image and a total prediction error energy for the previous image.

11. An apparatus for encoding transform coefficient data associated with the transform of an image frame, the coefficient data being represented in a two-dimensional array, said apparatus comprising

means for identifying those coefficients of the coefficient data associated with the transform which will be transmitted to a receiver,

encoding means for quad-tree coding the array locations of those coefficients which will be transmitted, and

means for variable length coding the quad-tree data code words.

12. The apparatus of claim 11 further wherein said identifying means comprises

means for subjecting said coefficients to a quantizing process for reducing the number of coefficient data bits to be transmitted,

whereby the coefficient data of said image is represented by fewer data bits as quantizer step size increases.

13. The apparatus of claim 12 further comprising

means for subjecting said coefficients to a thresholding process for reducing the coefficient data transmitted,

whereby the coefficient data of said image is represented by fewer data bits as the threshold level increases.

14. The apparatus of claim 11 further comprising

means for variable length coding the value of the transform coefficient data for each quad-tree data identified array location.

15. The apparatus of claim 11 wherein said quad tree encoding means comprises

means for assigning a selected number of bits to said quad tree encoding step,

means for performing said quad tree encoding of transform coefficients from low to high frequency representing components, and

means for terminating operation of said encoding means when said selected number of bits has been exhausted.

16. The apparatus of claim 11 further comprising

means for decoding, at a receiving station, the variable length coded data, said decoding means comprising

means for applying a received data stream to a first and a second lookup table, said first lookup table being responsive to a first number of sequentially received bits of each variable length code word beginning at the first bit of each word, said number of bits being less than the length of the longest variable length code word, and said second lookup table being responsive to a second number of sequentially received bits of each variable length code word beginning after the first bit of each word, said second number of bits being less than the length of the longest variable length code word, and the sum of said first number and said second number being at least equal to the length of the longest variable length code word,

means for setting a flag whenever said variable length code word cannot be decoded using only the first lookup table, and

means for decoding said variable length code word using said second lookup table whenever said flag is set and using said first table only when there is no flag.

17. The apparatus of claim 16 wherein said setting means comprises

means for responding to a unique code word output of said first lookup table for setting said flag.

18. The apparatus of claim 16 wherein said setting means comprises

means for responding to a flag enable output of said first lookup table for setting said flag.

19. The apparatus of claim 11 further comprising the step of

means for predicting a quantization step size for an image from available image statistics, and prior to encoding said image.

20. The apparatus of claim 19 wherein said predicting means comprises

means for selecting said quantization step size based upon the quantization step size for the previous image, the number of blocks completely coded in the previous image, a minimum number of blocks to be coded for this image, a total prediction error energy for this image and a total prediction error energy for the previous image.

21. A method for decoding a variable length coded data stream comprising the steps of

applying a received data stream to a plurality of lookup tables, a first lookup table being responsive to a first number of sequentially received bits of each variable length code word beginning at the first bit of each word, said number of bits being less than the length of the longest variable length code word, and each other lookup table being responsive to at least part of a second number of sequentially received bits of each variable length code word beginning after the first bit of each word, said second umber of bits being less than the length of the longest variable length code word, and the sum of said first number and said second number being at least equal to the length of the longest variable length code word,

setting a flag whenever said variable length code word cannot be decoded using only the first lookup table, and

decoding said variable length code word using said other lookup tables whenever said flag is set and using said first table only when there is no flag.

22. The method of claim 21 wherein there are two lookup tables.

23. A method for encoding motion estimation transform data representing the motion of each of a plurality of blocks representing an image frame in a time sequence of image frames, said transform data for each block being arranged in a two dimensional array, each block having associated therewith motion transform data representing the motion estimate for that block, said method comprising the steps of

identifying those blocks for which motion estimation transform data will be transmitted,

quad-tree encoding the locations of those blocks for which motion estimation data will be transmitted, and

encoding, using a variable length coding procedure, the quad-tree data code words.

24. Apparatus for encoding motion estimation transform data representing the motion of each of a plurality of blocks representing an image frame in a time sequence of image frames, said transform data for each block being arranged in a two dimensional array, each block having associated therewith motion data representing the motion estimate for that block, said apparatus comprising

means for identifying those blocks for which motion estimation transform data will be transmitted,

quad-tree encoding means for coding the locations of those blocks for which motion estimation transform data will be transmitted, and

means for variable length coding the quad-tree data code words.

25. Apparatus for decoding a variable length coded data stream comprising

means for applying a received data stream to a plurality of lookup tables, a first lookup table being responsive to a first number of sequentially received bits of each variable length code word beginning at the first bit of each word, said number of bits being less than the length of the longest variable length code word, and each other lookup table being responsive to at least part of a second number of sequentially received bits of each variable length code word beginning after the first bit of each word, said second number of bits being less than the length of the longest variable length code word, and the sum of said first number and said second number being at least equal to the length of the longest variable length code word,

means for setting a flag whenever said variable length code word cannot be coded using only the first lookup table, and

means for decoding said variable length code word using said other lookup tables whenever said flag is set and using said first table only when there is no flag.

26. The apparatus of claim 25 wherein there are two lookup tables.

27. A method for encoding transform data for a plurality of blocks associated with an image frame in a time sequence of image frames, said method comprising the steps of

transform coding data associated with said image frame for generating a plurality of transform coefficients;

and

predicting a quantization step size for said transform coefficients from image statistics, and prior to encoding said image.

28. The method of claim 27 wherein said predicting step comprises the step of

selecting said quantization step size based upon the quantization step size for the previous image, the number of blocks completely coded in the previous image, a minimum number of blocks to be coded for this image, a total prediction error energy for this image and a total prediction error energy for the previous image.

29. Apparatus for encoding transform data for a plurality of blocks associated with an image frame in a time sequence of image frames, said apparatus comprising

means for transform coding data associated with said image frame for generating a plurality of transform coefficients;

and

means for predicting a quantization step size for said transform coefficients from image statistics, and prior to encoding said image.

30. The apparatus of claim 29 wherein said predicting means comprises

means for selecting said quantization step size based upon the quantization step size for the previous image, the number of blocks completely coded in the previous image, a minimum number of blocks to be coded for this image, a total prediction error energy for this image and a total prediction error energy for the previous image.