Adaptive entropy encoding/decoding for screen capture content

• US 7,340,103 B2
• Filed: 01/10/2007
• Issued: 03/04/2008
• Est. Priority Date: 06/28/2002
• Status: Expired due to Term

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Smirnov, Sergey
• Primary Examiner(s): Do; Anh Hong
• Application Number:
  US11/652,172
• Publication Number:
  US 20070116370A1
• Time in Patent Office: 419 Days
• Field of Search: 382/245, 382/166, 382/232, 382/233, 382/162, 348/589, 348/563, 348/595, 348/600, 348/E9.039, 348/E9.057, 348/409.1, 348/415.1, 348/417.1, 348/418.1, 348/420.1, 348/422.1, 715/781, 345/555, 345/611
• US Class Current: 382/245
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• 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/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/156 Availability of hardware or computational resources, e.g. encoding based on power-saving criteria
• CPC Class Codes: H04N 19/625 using discrete cosine transform [DCT]
• CPC Class Codes: H04N 19/93 Run-length coding

Abstract

Adaptive entropy encoding and decoding techniques are described. For example, a screen capture encoder and decoder perform adaptive entropy encoding and decoding of palettized screen capture content in screen capture video. The encoder selects between different entropy encoding modes (such as an arithmetic coding mode and a combined run length/Huffman encoding mode, which allow the encoder to emphasize bitrate reduction at some times and encoding speed at other times). The run length encoding can use run value symbols adapted to common patterns of redundancy in the content. When the encoder detects series of pixels that could be encoded with different, alternative runs, the encoder selects between the alternative runs based upon efficiency criteria. The encoder also performs adaptive Huffman encoding, efficiently parameterizing Huffman code tables to reduce overall bitrate while largely preserving the compression gains of the adaptive Huffman encoding. A decoder performs converse operations.

Claims

1. A computer-readable storage medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method comprising:

receiving run length encoded data for a current frame in a series; and

run length decoding plural pixel series in the current frame from the run length encoded data for the current frame, each of the plural pixel series being encoded as a run length and a run value, wherein the run value for at least one of the plural pixel series is a color value symbol, wherein the run value for at least one of the plural pixel series is an above color value symbol, wherein the run value for at least one of the plural pixel series is a previous frame color value symbol that references color values of pixels in a previous frame before the current frame in the series, and wherein the previous frame color value symbol indicates the color values of pixels in the previous frame are identical to color values of pixels at the same locations in the current frame.

2. The computer-readable storage medium of claim 1 wherein the method further comprises adaptive Huffman decoding the run values and the run lengths before the run length decoding.

3. The computer-readable storage medium of claim 2 wherein the method further comprises:

receiving a code count and lengths for less than all of plural Huffman codes; and

reconstructing the plural Huffman codes from the code count and the lengths.

4. The computer-readable storage medium of claim 1 wherein the pixels are for screen capture content.

5. The computer-readable storage medium of claim 1 wherein the previous frame is decoded before the current frame during decoding.

6. A method comprising:

run length encoding plural pixel series in a current frame in a series, each of the plural pixel series being encoded as a run length and a run value, wherein the run value for at least one of the plural pixel series is a color value symbol, wherein the run value for at least one of the plural pixel series is an above color value symbol, wherein the run value for at least one of the plural pixel series is a previous frame color value symbol that references color values of pixels in a previous frame before the current frame in the series, and wherein the previous frame color value symbol indicates the color values of pixels in the previous frame are identical to color values of pixels at the same locations in the current frame; and

outputting encoded data for the plural pixel series.

7. The method of claim 6 wherein the method further comprises adaptive Huffman encoding the run values and the run lengths after the run length encoding.

8. The method of claim 7 wherein the method further comprises, as part of the outputting, signaling a code count and lengths for less than all of plural Huffman codes.

9. The method of claim 6 wherein the pixels are for screen capture content.

10. A computer-readable storage medium storing computer-executable instructions for causing a computer system programmed thereby to perform the method of claim 6.

11. The method of claim 6 wherein the pixels are for palletized content.

12. The method of claim 6 wherein the method further comprises, for at least one of the plural pixel series, selecting between using the color value symbol, above color value symbol and previous frame color value symbol for the pixel series.

13. A method comprising:

receiving run length encoded data for a current frame in a series; and

run length decoding plural pixel series in the current frame from the run length encoded data for the current frame, each of the plural pixel series being encoded as a run length and a run value, wherein the run value for at least one of the plural pixel series is a color value symbol, wherein the run value for at least one of the plural pixel series is an above color value symbol, wherein the run value for at least one of the plural pixel series is a previous frame color value symbol that references color values of pixels in a previous frame before the current frame in the series, and wherein the previous frame color value symbol indicates the color values of pixels in the previous frame are identical to color values of pixels at the same locations in the current frame.

14. The method of claim 13 wherein the method further comprises adaptive Huffman decoding the run values and the run lengths before the run length decoding.

15. The method of claim 14 wherein the method further comprises:

receiving a code count and lengths for less than all of plural Huffman codes; and

reconstructing the plural Huffman codes from the code count and the lengths.

16. The method of claim 13 wherein the pixels are for screen capture content.

17. The method of claim 13 wherein the previous frame is decoded before the current frame during decoding.