Adaptive entropy encoding/decoding for screen capture content

• US 7,016,547 B1
• Filed: 06/28/2002
• Issued: 03/21/2006
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Smirnov, Sergey
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US10/186,639
• Time in Patent Office: 1,362 Days
• Field of Search: 382/162, 382/166, 382/209, 382/218, 382/219, 382/173, 382/244, 382/232, 382/233, 382/234, 382/245, 341/87, 341/106, 341/55, 341/67, 345/545, 345/538, 375/240.1, 375/241, 375/253, 719/328, 358/426.13
• 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 screen capture encoder comprising:

a run length encoder for encoding plural runs of symbols for pixels of screen capture content, each of the plural runs encoded as a run value and a run length, wherein the run value for at least one of the plural runs is a color value symbol, and wherein the run value for at least one of the plural rums is an above color value symbol; and

a module for adaptively assigning plural Huffman codes to results of the encoding, wherein the module parameterizes the plural Huffman codes as a Huffman code threshold and lengths for less than all of the plural Huffman codes, thereby reducing associated bitrate for the plural Huffman codes.

2. The screen capture encoder of claim 1 wherein the run value for at least one of the plural runs is a previous frame color value symbol.

3. The screen capture encoder of claim 1 further comprising:

means for selectively using a second encoder instead of the run length encoder.

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

decoding plural run length encoded pixel series for a frame of screen capture content, each of the plural series encoded as a run length and a run value, wherein a first run value for a first series of the plural series is a color value for each pixel in the first series, wherein a second run value for a second series of the plural series is an adjacent pixel marker for each pixel in the second series, and wherein the decoding includes using one or more color values of an adjacent pixel series for the second series.

5. The computer-readable medium of claim 4 wherein the adjacent pixel marker is an adjacent row marker, and wherein the adjacent pixel series is spatially adjacent the second series within the frame of screen capture content.

6. The computer-readable medium of claim 4 wherein the adjacent pixel marker is an adjacent frame marker, and wherein the adjacent pixel series is temporally adjacent the second series.

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

creating a variable length code table for a set of plural unique symbol values, the table including a set of plural variable length codes, wherein a threshold separates the set of plural variable length codes into a first group of one or more of the plural variable length codes and a second group of one or more of the plural variable length codes, the one or more variable length codes in the first group having lengths based at least in part upon probability of occurrence of corresponding unique symbol values;

parameterizing the table as the threshold and the lengths for the one or more variable length codes in the first group, thereby reducing bitrate associated with the table.

8. The computer-readable medium of claim 7 wherein the threshold is a count of the one or more variable length codes in the first group, and wherein the one or more variable length codes of the second group have substantially equal lengths.

9. The computer-readable medium of claim 7 further comprising, during an encoding session, repeating the creating and the parameterizing for adaptive encoding.

10. A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method of creating a Huffman code table for a set of n unique symbol values, the method comprising:

setting a Huffman code count m, where m is less than n;

for each of m unique symbol values in the set, generating a different Huffman code with a length substantially in proportion to probability of occurrence for the unique symbol value;

for each of n minus m remaining unique symbol values in the set, generating a different Huffman code of substantially equal length; and

parameterizing the table as the Huffman code count and the m lengths, thereby reducing bitrate associated with the table.

11. The computer-readable medium of claim 10 wherein the probability of occurrence is probability of occurrence in content to be encoded with the table, whereby the table adapts to the content to be encoded.

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

receiving a code count and one or more code lengths, wherein the code count separates a set of plural variable length codes into a first group of one or more of the plural variable length codes and a second group of one or more of the plural variable length codes, wherein the one or more code lengths are for the one or more variable length codes in the first group; and

reconstructing a variable length code table for all of the set of plural variable length codes from the code count and the one or more code lengths.

13. The computer-readable medium of claim 12 further comprising, during a decoding session, repeating the receiving and the reconstructing for adaptive decoding.

14. A computer-readable medium storing computer-executable instructions for causing a computer system programmed thereby to perform a method of reconstructing a Huffman code table for a set of n unique symbol values, the method comprising:

receiving a Huffman code count m, where m is less than n;

receiving m Huffman code lengths for m different Huffman codes;

for each of m unique symbol values in the set, generating a different Huffman code having the received Huffman code length for the different Huffman code;

for each of n minus m remaining unique symbol values in the set, generating a different Huffman code of substantially equal length.

15. The computer-readable medium of claim 14, wherein the method further comprises, during a decoding session, repeating the reconstructing for each of one or more additional Huffman code tables for adaptive decoding.