System and method for decoding using parallel processing

• US 8,311,111 B2
• Filed: 12/05/2008
• Issued: 11/13/2012
• Est. Priority Date: 09/11/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Xu, Yaowu, Wilkins, Paul, Bankoski, James
• Primary Examiner(s): Perungavoor, Sath V
• Assistant Examiner(s): Pe, Geepy
• Application Number:
  US12/329,248
• Publication Number:
  US 20100061455A1
• Time in Patent Office: 1,439 Days
• Field of Search: 375/240.08, 37524024-24026
• US Class Current: 375/240.13
• CPC Class Codes: H04N 19/174 the region being a slice, e.g. a line of blocks or a group of blocks
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/82 involving filtering within a prediction loop
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

Decoding a stream of encoded video data involves partitions that have been compressed using lossless encoding. Each partition includes rows that have also been encoded using intra-frame or inter-frame encoding. During the decoding process, two or more of the partitions are entropy decoded on two or more processors in parallel, except that partitions containing adjacent rows in the frame are decoded with an offset so that at least a portion of the output of the entropy decoding of one partition can be used as input in the entropy and intra/inter-frame decoding of the other.

Claims

1. A method for decoding a stream of encoded video data, the stream of encoded video data including at least one frame divided into a plurality of partitions, comprising:

identifying partition data information indicative of a partition location for each of at least some of the plurality of partitions;

identifying, based on the partition data information, at least a first one of the plurality of partitions that includes at least one row of blocks;

identifying, based on the partition data information, at least a second one of the plurality of partitions that includes at least one row of blocks, wherein the first partition and the second partition have each been individually compressed using at least a first encoding scheme and a second encoding scheme;

decoding, using a first processor, the first partition; and

decoding, using a second processor, the second partition, wherein the decoding of the second partition is offset by a specified number of blocks so that at least a portion of the output from the decoding of the first partition is used as input in decoding the second partition in accordance with the first encoding scheme.

2. The method of claim 1, wherein the first encoding scheme includes lossless encoding and the second encoding scheme includes at least one of intra-frame prediction and inter-frame prediction.

3. The method of claim 2, wherein the at least one row of blocks in the first partition and the at least one row of blocks in the second partition are derived from two adjacent rows in the at least one frame.

4. The method of claim 2, wherein the lossless encoding is an entropy encoding scheme.

5. The method of claim 1, wherein at least a portion of a row of blocks of the output from the decoding of the second partition is used as input in decoding at least a portion of another row of blocks in the first partition in accordance with at least one of the first encoding scheme and the second encoding scheme.

6. The method of claim 5, wherein the row in the second partition is adjacent in the at least one frame to the row in the first partition.

7. The method of claim 1, wherein the second encoding scheme is configured to encode the at least one row of blocks in the first partition using context information contained in the at least one row of blocks in the second partition.

8. The method of claim 1, wherein the second encoding scheme is configured to encode the at least one row of blocks in the second partition using context information contained in the at least one row of blocks in the first partition.

9. The method of claim 8, wherein the second encoding scheme includes at least one of intra-frame prediction and inter-frame prediction.

10. The method of claim 8, wherein the at least one row of blocks in the first partition and the at least one row of blocks in the second partition are derived from two adjacent rows in an image frame represented by the video data, and wherein decoding the second partition further comprises:

decoding at least one block in the second partition using information from a block that is already decoded by the first processor, wherein the at least one block in the second partition and the already decoded block in first partition are adjacent to each other the image frame.

11. The method of claim 8, wherein decoding the second portion further comprises:

using at least a portion of the context information of the blocks most recently decoded by the first processor as context data for decoding at least one block in the second partition.

12. The method of claim 8, wherein the specified offset is determined based upon the size of the context used by the second encoding scheme.

13. The method of claim 8, wherein the at least one row of blocks in the first partition and the at least one row of blocks in the second partition are derived from corresponding rows in two successive frames of the video data, and wherein decoding the second partition further comprises:

decoding at least one block in the second partition using information from a block that is already decoded by the first processor.

14. The method of claim 1, further comprising:

reading in the video data a record that indicates the number of partitions.

15. The method of claim 1, further comprising:

reading in the video data a record that indicates the specified number of blocks.

16. The method of claim 1, wherein identifying partition data information indicative of a partition location for each of at least some of the plurality of partitions comprises:

reading, from the stream of encoded video data, a record that indicates the partition location for each of the at least some of the plurality of partitions within the encoded video data.

17. The method of claim 1, wherein the first encoding scheme is context-based arithmetic coding.

19. The method of claim 1, wherein the first partition and the second partition each include non-adjacent rows of blocks in the at least one frame.

18. A method for decoding a stream of encoded video data including at least one frame having a plurality of rows of blocks divided into a plurality of partitions:

providing a plurality of processors having shared primary memory space;

reading partition data information in the encoded video data that indicates a partition count and a partition location for each of at least some of the plurality of partitions;

identifying, based on the partition data information, a first one and a second one of the plurality of partitions, wherein the first one of the plurality of partitions includes encoded context information that can be used to decode the second one of the plurality of partitions and wherein the first one and the second one of the plurality of partitions have each been individually compressed using at least a first encoding scheme and a second encoding scheme;

decoding the first one of the plurality of partitions in accordance with the second encoding scheme, using a first one of the plurality of processors; and

decoding the second one of the plurality of partitions in accordance with the first decoding scheme, using a second one of the plurality of processors, wherein the decoding of the second partition is offset by a specified number of blocks, the specified number at least as large as the number of blocks in the encoded context information;

wherein at least a portion of the output from the decoding of the first partition is used as input in decoding the second partition.