SYSTEM AND METHOD FOR DECODING USING PARALLEL PROCESSING

• US 20100061455A1
• Filed: 12/05/2008
• Published: 03/11/2010
• Est. Priority Date: 09/11/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: ON2 Technologies Incorporated (Alphabet Inc.)
• Inventors: Wilkins, Paul, Bankoski, James, Xu, Yaowu
• Granted Patent: US 8,311,111 B2
• Time in Patent Office: Days
• US Class Current: 375/240.130
• 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

A method for decoding a stream of encoded video data is disclosed. The video stream includes partitions that have been compressed using lossless encoding. Each partition includes rows that have also been encoded using intra-frame or inter-frame encoding, for example. 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 including a plurality of partitions that have been compressed using at least a first encoding scheme, comprising:

selecting at least a first one of the partitions that includes at least one row of blocks that has also been encoded using at least a second encoding scheme;

selecting at least a second one of the partitions that includes at least one row of blocks that has also been encoded using the second encoding scheme;

decoding the first partition using a first processor; and

decoding the second partition using a second processor, 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 an image frame represented by the video data.

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 a frame of the video information 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 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 size of the specified macroblock offset.

16. The method of claim 1, further comprising:

reading in the video data a record that indicates the location of the partitions within the encoded video data.

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

18. A method for encoding video data including at least one frame having a plurality of rows of blocks, comprising:

encoding the rows using a second encoding scheme, wherein the input to encoding each row includes information contained in an adjacent row;

dividing the plurality of rows into a plurality of partitions, wherein at least two adjacent rows are placed into separate partitions;

further encoding each of the plurality of the partitions using a first encoding scheme;

recording a value indicative of the number or partitions into which the plurality of rows have been divided; and

recording a value indicative of the location of the partitions within the encoded video data.

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

20. The method of claim 18, wherein the first encoding scheme is an entropy encoding scheme.

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

22. The method of claim 18, wherein the number of partitions N is a number greater than one.

23. The method of claim 18, wherein dividing the rows into a plurality of partitions further comprises:

grouping every Nth row of the frame into a different one of the plurality of partitions, so that each adjacent row in the frame is placed into a separate partition.

24. A method for decoding a stream of video data representing at least one frame image composed of a plurality of rows of blocks, wherein the data is encoded using a first encoding scheme and a second encoding scheme, comprising:

providing a plurality of processors having shared primary memory space;

reading a record in the video data that indicates a partition count and a partition location offset;

dividing the video data into a plurality of partitions based on the partition count and partition location offset;

identifying 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 in accordance with the first encoding scheme;

decoding the first one of the plurality of portions 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 portions in accordance with the first decoding method, 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 can be used as input in decoding the second partition.