USRE49727E1 - System and method for decoding using parallel processing - Google Patents

Abstract

An apparatus for decoding frames of a compressed video data stream having at least one frame divided into partitions, includes a memory and a processor configured to execute instructions stored in the memory to read partition data information indicative of a partition location for at least one of the partitions, decode a first partition of the partitions that includes a first sequence of blocks, decode a second partition of the partitions that includes a second sequence of blocks identified from the partition data information using decoded information of the first partition.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a continuation of U.S. nonprovisional patent application Ser. No. 13/565,364, filed Aug. 2, 2012, now U.S. Pat. No. 9,357,223, which is a divisional of U.S. nonprovisional patent application Ser. No. 12/329,248, filed Dec. 5, 2008, which claims priority to U.S. provisional patent application No. 61/096,223, filed Sep. 11, 2008, which are incorporated herein in entirety by reference.

TECHNICAL FIELD

The present invention relates in general to video decoding using multiple processors.

BACKGROUND

An increasing number of applications today make use of digital video for various purposes including, for example, remote business meetings via video conferencing, high definition video entertainment, video advertisements, and sharing of user-generated videos. As technology is evolving, people have higher expectations for video quality and expect high resolution video with smooth playback at a high frame rate.

There can be many factors to consider when selecting a video coder for encoding, storing and transmitting digital video. Some applications may require excellent video quality where others may need to comply with various constraints including, for example, bandwidth or storage requirements. To permit higher quality transmission of video while limiting bandwidth consumption, a number of video compression schemes are noted including proprietary formats such as VPx (promulgated by On2 Technologies, Inc. of Clifton Park, N.Y., H.264 standard promulgated by ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG), including present and future versions thereof. H.264 is also known as MPEG-4Part 10 or MPEG-4 AVC (formally, ISO/IEC 14496-10).

There are many types of video encoding schemes that allow video data to be compressed and recovered. The H.264 standard, for example, offers more efficient methods of video coding by incorporating entropy coding methods such as Context-based Adaptive Variable Length Coding (CAVLC) and Context-based Adaptive Binary Arithmetic Coding (CABAC). For video data that is encoded using CAVLC, some modem decompression systems have adopted the use of a multi-core processor or multiprocessors to increase overall video decoding speed.

SUMMARY

An embodiment of the invention is disclosed as 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. The method includes selecting at least a first one of the partitions that includes at least one row of blocks that has been encoded using at least a second encoding scheme. A second partition is selected that includes at least one row of blocks encoded using the second encoding scheme. The first partition is decoded by a first processor, and the second partition is decoded by a second processor. 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. Further, the decoding of the first partition is offset by a specified number of blocks so that at least a portion of the output from the decoding of the second partition is used as input in decoding the first partition.

BRIEF DESCRIPTION OF THE DRAWINGS

The description herein makes reference to the accompanying drawings wherein like reference numerals refer to like parts throughout the several views, and wherein:

FIG.1 is a diagram of the hierarchy of layers in a compressed video bitstream in accordance with one embodiment of the present invention.

FIG.2 is a block diagram of a video compression system in accordance with one embodiment of the present invention.

FIG.3 is a block diagram of a video decompression system in accordance with one embodiment of the present invention.

FIG.4 is a schematic diagram of a frame and its corresponding partitions outputted from the video compression system ofFIG.2.

FIG.5 is a schematic diagram of an encoded video frame in a bitstream outputted from the video compression system ofFIG.2 and sent to the video decompression system ofFIG.3.

FIGS.6A-6B arc timing diagrams illustrating the staging and synchronization of cores on a multi-core processor used in the video decompression system ofFIG.3.

FIG.7A is a schematic diagram showing data-dependent macroblocks and an offset calculation based used in the video compression and decompression systems ofFIGS.2 and3.

FIG.7B is a schematic diagram showing data-dependent macroblocks and an alternative offset calculation used in the video compression and decompression systems ofFIGS.2 and3.

DETAILED DESCRIPTION

Referring toFIG.1, video coding standards, such as H.264, provide a defined hierarchy oflayers10 for avideo stream11. The highest level in the layer can be avideo sequence13. At the next level,video sequence13 consists of a number ofadjacent frames15. Number ofadjacent frames15 can be further subdivided into asingle frame17. At the next level,frame17 can be composed of a series of fix-sizedmacroblocks20, which contain compressed data corresponding to, for example, a 16×16 block of displayed pixels inframe17. Each macroblock contains luminance and chrominance data for the corresponding pixels. Macroblocks20 can also be of any other suitable size such as 16×8 pixel groups or 8×16 pixel groups. Macroblocks20 are further subdivided into blocks. A block, for example, can be a 4×4 pixel group that can further describe the luminance and chrominance data for the corresponding pixels. Blocks can also be of any other suitable size such as 16×16, 16×8, 8×16, 8×8, 8×4, 4×8 and 4×4 pixels groups.

Although the description of embodiments are described in the context of the VP8 video coding format, alternative embodiments of the present invention can be implemented in the context of other video coding formats. Further, the embodiments are not limited to any specific video coding standard or format.

Referring toFIG.2, in accordance with one embodiment, to encode aninput video stream16, anencoder14 performs the following functions in a forward path (shown by the solid connection lines) to produce an encoded bitstream26: intra/inter prediction18, transform19,quantization22 andentropy encoding24.Encoder14 also includes a reconstruction path (shown by the dotted connection lines) to reconstruct a frame for encoding of further macroblocks.Encoder14 performs the following functions in the reconstruction path:dequantization28,inverse transformation30,reconstruction32 andloop filtering34. Other structural variations ofencoder14 can be used to encodebitstream26.

Wheninput video stream16 is presented for encoding, eachframe17 withininput video stream16 can be processed in units of macroblocks. At intra/inter prediction stage18, each macroblock can be encoded using either intra prediction or inter prediction mode. In the case of intra-prediction, a prediction macroblock can be formed from samples in the current frame that have been previously encoded and reconstructed. In the case of inter-prediction, a prediction macroblock can be formed from one or more reference frames that have already been encoded and reconstructed.

Next, still referring toFIG.2, the prediction macroblock can be subtracted from the current macroblock to produce a residual macroblock (residual).Transform stage19 transform codes the residual signal to coefficients andquantization stage22 quantizes the coefficients to provide a set of quantized transformed coefficients. The quantized transformed coefficients are then entropy coded byentropy encoding stage24. The entropy-coded coefficients, together with the information required to decode the macroblock, such as the type of prediction mode used, motion vectors and quantizer value, are output to compressedbitstream26.

The reconstruction path inFIG.2, can be present to permit that both the encoder and the decoder use the same reference frames required to decode the macroblocks. The reconstruction path, similar to functions that take place during the decoding process, which arc discussed in more detail below, includes dequantizing the transformed coefficients bydequantization stage28 and inverse transforming the coefficients byinverse transform stage30 to produce a derivative residual macroblock (derivative residual). At thereconstruction stage32, the prediction macroblock can be added to the derivative residual to create a reconstructed macroblock. Aloop filter34 can he applied to the reconstructed macroblock to reduce distortion.

Referring toFIG.3, in accordance with one embodiment, to decodecompressed bitstream26, adecoder21, similar to the reconstruction path ofencoder14 discussed previously, performs the following functions to produce an output video stream35: entropy decoding25,dequantization27,inverse transformation29, intra/inter prediction23,reconstruction31,loop filter34 anddeblocking filtering33. Other structural variations ofdecoder21 can be used to decodecompressed bitstream26.

When compressedbitstream26 is presented for decoding, the data elements can be decoded byentropy decoding stage25 to produce a set of quantized coefficients.Dequantization stage27 dequantizes andinverse transform stage29 inverse transforms the coefficients to produce a derivative residual that is identical to that created by the reconstruction stage inencoder14. Using the type of prediction mode and/or motion vector information decoded from the compressedbitstream26, at intra/inter prediction stage23,decoder21 creates the same prediction macroblock as was created inencoder14. At thereconstruction stage33, the prediction macroblock can be added to the derivative residual to create a reconstructed macroblock. Theloop filter34 can be applied to the reconstructed macroblock to reduce blocking artifacts. Adeblocking filter33 can be applied to video image frames to further reduce blocking distortion and the result can he outputted to output video stream35.

Current context-based entropy coding methods, such as Context-based Adaptive Arithmetic Coding (CABAC), are limited by dependencies that exploit spatial locality by requiring macroblocks to reference neighboring macroblocks and that exploit temporal localities by requiring macroblocks to reference macroblocks from another frame. Because of these dependencies and the adaptivity,encoder14 codes the bitstream in a sequential order using context data from neighboring macroblocks. Such sequential dependency created byencoder14 causes thecompressed bitstream26 to be decoded in a sequential fashion bydecoder21. Such sequential decoding can be adequate when decoding using a single-core processor. On the other hand, if a multi-core processor or a multi-processor system is used during decoding, the computing power of the multi-core processor or the multi-processor system would not be effectively utilized.

Although the disclosure has and will continue to describe embodiments of the present invention with reference to a multi-core processor and the creation of threads on the multi-core processor, embodiments of the present invention can also be implemented with other suitable computer systems, such as a device containing multiple processors.

According to one embodiment,encoder14 divides the compressed bitstream into partitions36 rather than a single stream of serialized data. With reference toFIG.4 and by way of example only, the compressed bitstream can be divided into four partitions, which are designated as Data Partitions1-4. Other numbers of partitions are also suitable. Since each partition can be the subject of a separate decoding process when they are decoded bydecoder21, the serialized dependency can be broken up in the compressed data without losing coding efficiency.

Referring toFIG.4,frame17 is shown with dividedmacroblock rows38.Macroblock rows38 consist ofindividual macroblocks20. Continuing with the example, everyNth macroblock row38 can be grouped into one of partitions36 (where N is the total number of partitions). In this example, there are four partitions andmacroblock rows0,4,8,12, etc. are grouped intopartition1.Macroblock rows1,5,9 and13, etc. are grouped intopartition2.Macroblock rows2,6,10,14, etc. are grouped intopartition3.Macroblock rows3,7,11,15, etc. are grouped intopartition4. As a result, each partition36 includes contiguous macroblocks, but in this instance, each partition36 does not containcontiguous macroblock rows38. In other words, macroblock rows of blocks in the first partition and macroblock rows in the second partition can be derived from two adjacent macroblock rows in a frame. Other grouping mechanisms arc also available and arc not limited to separating regions by macroblock row or grouping every Nth macroblock row into a partition. Depending on the grouping mechanism, in another example, macroblock rows that are contiguous may also be grouped into the same partition36.

An alternative grouping mechanism may include, for example, grouping a row of blocks from a first frame and a corresponding row of blocks in a second frame. The row of blocks from the first frame can be packed in the first partition and the corresponding row of blocks in the second frame can be packed in the second partition. A first processor can decode the row of blocks from the first frame and a second processor can decode the row of blocks from the second frame. In this manner, the decoder can decode at least one block in the second partition using information from a block that is already decoded by the first processor.

Each of the partitions36 can be compressed using two separate encoding schemes. The first encoding scheme can be lossless encoding using, for example, context-based arithmetic coding like CABAC. Other lossless encoding techniques may also be used. Referring back toFIG.1, the first encoding scheme may be realized by, for example,entropy encoding stage24.

Still referring toFIG.1, the second encoding scheme, which can take place before the first encoding scheme, may be realized by at least one of intra/inter prediction stage18, transformstage19, andquantization22. The second encoding scheme can encode blocks in each of the partitions36 by using information contained in other partitions. For example, if a frame is divided into two partitions, the second encoding scheme can encode the second partition using information contained in the macroblock rows of the first partition.

Referring toFIG.5, an encodedvideo frame39 from compressedbitstream26 is shown. For simplicity, only parts of the bitstream that are pertinent to embodiments of the invention are shown. Encodedvideo frame39 contains avideo frame header44 which contains bits for a number ofpartitions40 and bits for offsets of eachpartition42. Encodedvideo frame39 also includes the encoded data from data partitions36 illustrated as P₁-P_Nwhere, as discussed previously, N is the total number of partitions invideo frame17.

Onceencoder14 has dividedframe17 into partitions36,encoder14 writes data intovideo frame header44 to indicate number ofpartitions40 and offsets of eachpartition42. Number ofpartitions40 and offsets of eachpartition42 can be represented inframe17 by a bit, a byte or any other record that can relay the specific information todecoder21.Decoder21 reads the number ofdata partitions40 fromvideo frame header44 in order to decode the compressed data. In one example, two bits may be used to represent the number of partitions. One or more bits can be used to indicate the number of data partitions (or partition count). Other coding schemes can also be used to code the number of partitions into the bitstream. The following list indicates how two bits can represent the number of partitions:

		BIT 1	BIT 2	NUMBER OFPARTITIONS
		0	0	Onepartition
		0	1	Twopartitions
		1	0	Fourpartitions
		1	1	Eight partitions

If the number of data partitions is greater than one,decoder21 also needs information about the positions of the data partitions36 within the compressedbitstream26. The offsets of each partition42 (also referred to as partition location offsets) enable direct access to each partition during decoding.

In one example, offset of eachpartition42 can be relative to the beginning of the bitstream and can be encoded and written into thebitstream26. In another example, the offset for each data partition can be encoded and written into the bitstream except for the first partition since the first partition implicitly begins in thebitstream26 after the offsets of eachpartition42. The foregoing is merely exemplary. Other suitable data structures, flags or records such words and bytes, can be used to transmit partition count and partition location offset information.

Although the number of data partitions can be the same for eachframe17 throughout theinput video sequence16, the number of data partitions may also differ from frame to frame. Accordingly, eachframe17 would have a different number ofpartitions40. The number of bits that are used to represent the number of partitions may also differ from frame to frame. Accordingly, eachframe17 could be divided into varying numbers of partitions.

Once the data has been compressed intobit stream26 with the proper partition data information (i.e. number ofpartitions40 and offsets of partitions42),decoder21 can decode the data partitions36 on a multi-core processor in parallel. In this manner, each processor core may be responsible for decoding one of the data partitions36. Since multi-core processors typically have more than one processing core and shared memory space, the workload can be allocated between each core as evenly as possible. Each core can use the shared memory space as an efficient way of sharing data between each core decoding each data partition36.

For example, if there are two processors decoding two partitions, respectively, the first processor will begin decoding the first partition. The second processor can then decode macroblocks of the second partition and can use information received from the first processor, which has begun decoding macroblocks of the first partition. Concurrently with the second processor, the first processor can continue decoding macroblocks of the first partition and can use information received from the second processor. Accordingly, both the first and second processors can have the information necessary to properly decode macroblocks in their respective partitions.

Furthermore, as discussed in more detail below, when decoding a macroblock row of the second partition that is dependent on the first partition, a macroblock that is currently being processed in the second partition is offset by a specified number of macroblocks. In this manner, at least a portion of the output of the decoding of the first partition can be used as input in the decoding of the macroblock that is currently being processed in the second partition. Likewise, when decoding a macroblock row of the first partition that is dependent on the second partition, a macroblock that is currently being processed in the first partition is offset by a specified number of macroblocks so that at least a portion of the output of the decoding of the second partition can be used as input in the decoding of the macroblock that is currently being processed in the first partition.

When decoding the compressed bitstream,decoder21 determines the number of threads needed to decode the data, which can be based on the number ofpartitions40 in each encodedframe39. For example, if number ofpartitions40 indicates that there are four partitions in encodedframe39,decoder21 creates four threads with each thread decoding one of the data partitions. Referring toFIG.4, as an example,decoder21 can determine that four data partitions have been created. Hence, ifdecoder21 is using a multi-core processor, it can create four separate threads to decode the data from that specific frame.

As discussed previously,macroblocks20 within each frame use context data from neighboring macroblocks when being encoded. When decodingmacroblocks20, the decoder will need the same context data in order to decode the macroblocks properly. On the decoder side, the context data can be available only after the neighboring macroblocks have already been decoded by the current thread or other threads. In order to decode properly, the decoder includes a staging and synchronization mechanism for managing the decoding of the multiple threads.

With reference toFIGS.6A and6B, a time diagram shows the staging and synchronization mechanism to decode partitions36 on threads of a multi-core processor in accordance with an embodiment of the present invention.FIGS.6A and6B illustrate an exemplarypartial image frame45 at various stages of the decoding process. The example is simplified for purposes of this disclosure and the number of partitions36 is limited to three. Each partition36 can be assigned to one of the threethreads46,48 and50. As discussed previously, each partition36 includes contiguous macroblocks.

As depicted inFIGS.6A and6B, as an example, threethreads46,48 and50 arc shown, and each ofthreads46,48 and50 are capable of performing decoding in parallel with each other. Each of the threethreads46,48 and50 processes one partition in a serial manner while all threepartitions40 are processed in parallel with each other.

Each ofFIGS.6A and6B contain an arrow that illustrates which macroblock is currently being decoded in each macroblock row, which macroblocks have been decoded in each macroblock row, and which macroblocks have yet to be decoded in each macroblock row. If the arrow is pointing to a specific macroblock, that macroblock is currently being decoded. Any macroblock to the left of the arrow (if any) has already been decoded in that row. Any macroblock to the right of the arrow has yet to be decoded. Although the macroblocks illustrated inFIGS.6A and6B all have similar sizes, the techniques of this disclosure are not limited in this respect. Other block sizes, as discussed previously, can also be used with embodiments of the present invention.

Referring toFIG.6A, at time t1,thread46 has initiated decoding of afirst macroblock row52.Thread46 is currently processing macroblock j infirst macroblock row52 as shown byarrow58.Macroblocks0 to j−1 have already been decoded infirst macroblock row52. Macroblocks j+1 to the end offirst macroblock row52 have yet to be decoded infirst macroblock row52.Thread48 has also initiated decoding of asecond macroblock row54.Thread48 is currently processingmacroblock0 insecond macroblock row54 as shown by arrow60.Macroblocks1 to the end ofsecond macroblock row54 have been decoded insecond macroblock row54.Thread50 has not begun decoding of athird macroblock row56. No macroblocks have been decoded or are currently being decoded inthird macroblock row56.

Referring toFIG.6B, at time t2,thread46 has continued decoding offirst macroblock row52.Thread46 is currently processing macroblock j*2 infirst macroblock row52 as shown byarrow62.Macroblocks0 to j*2-1 have already been decoded infirst macroblock row52. Macroblocks j*2+1 to the end offirst macroblock row52 have yet to be decoded infirst macroblock row52.Thread48 has also continued decoding ofsecond macroblock row54.Thread48 is currently processing macroblock j insecond macroblock row54 as shown byarrow64.Macroblocks0 to j−1 have already been decoded insecond macroblock row54. Macroblocks j+1 to the end ofsecond macroblock row54 have yet to be decoded insecond macroblock row54.Thread50 has also initiated decoding of athird macroblock row56.Thread50 is currently processingmacroblock0 inthird macroblock row56 as shown byarrow66.Macroblocks1 to the end of thirdmacroblock row56 have yet to be decoded inthird macroblock row56.

Previous decoding mechanisms were unable to efficiently use a multi-core processor to decode a compressed bitstream because processing of a macroblock row could not be initiated until the upper adjacent macroblock row had been completely decoded. The difficulty of previous decoding mechanisms stems from the encoding phase. When data is encoded using traditional encoding techniques, spatial dependencies within macroblocks imply a specific order of processing of the macroblocks. Furthermore, once the frame has been encoded, a specific macroblock row cannot be discerned until the row has been completely decoded. Accordingly, video coding methods incorporating entropy coding methods such as CABAC created serialized dependencies which were passed to the decoder. As a result of these serialized dependencies, decoding schemes had limited efficiency because information for each computer processing system (e.g. threads46,48 and50) was not available until the decoding process has been completed on that macroblock row.

Utilizing the parallel processing staging and synchronization mechanism illustrated inFIGS.6A and6B allowsdecoder21 to efficiently accelerate the decoding process of image frames. Because each partition36 can be subject to a separate decoding process, interdependencies between partitions can be managed by embodiments of the staging and synchronization scheme discussed previously in connection withFIGS.6A and6B. Using this staging and synchronization decoding scheme, eachthread46,48 and50 that decodes an assigned partition can exploit context data from neighboring macroblocks. Thus,decoder21 can decode macroblocks that contain context data necessary to decode a current macroblock before the preceding macroblock row has been completely decoded.

Referring again toFIGS.6A and6B, offset j can be determined by examining the size of the context data used in the preceding macroblock row (e.g. measured in a number of macroblocks) during the encoding process. Offset j can be represented inframe17 by a bit, a byte or any other record that can relay the size of the context data todecoder21.FIGS.7A and7B illustrate two alternatives for the size of offset j.

Referring toFIG.7A, in one embodiment,current macroblock68 is currently being processed.Current macroblock68 uses context data from the left, top-left, top and top-right macroblocks during encoding. In other words,current macroblock68 uses information from macroblocks: (r+1, c−1), (r, c−1), (r, c) and (r, c+1). In order to properly decodecurrent macroblock68, macroblocks (r+1, c−1), (r, c−1), (r, c) and (r, c+1) should be decoded beforecurrent macroblock68. Since, as discussed previously, decoding of macroblocks can be performed in a serial fashion, macroblock (r+1, c−1) can be decoded beforecurrent macroblock68. Further, in the preceding macroblock row (i.e. macroblock row r), since the encoding process uses (r, c+1) as the rightmost macroblock, the decoder can use (r, c+1) as the rightmost macroblock during decoding as well. Thus, offset j can be determined by subtracting the column row position of rightmost macroblock of the preceding row used during encoding of the current macroblock from the column row position of the current macroblock being processed. InFIG.7A, offset j would be determined by subtracting the column row position of macroblock (r, c+1) from the column position of current macroblock68 (i.e. (r+1, c)), or c+1−c, giving rise to an offset of 1.

Referring toFIG.7B, in one embodiment,current macroblock68′ is currently being processed.Current macroblock68′ uses information from macroblocks: (r+1, c−1), (r, c−1), (r, c), (r, c+1), (r, c+2), and (r, c+3). In order to properly decodecurrent macroblock68′, macroblocks (r+1, c−1), (r, c−1), (r, c) (r, c+1), (r, c+2) and (r, c+3) should be decoded beforecurrent macroblock68′. Since, as discussed previously, decoding of macroblocks can be performed in a serial fashion, macroblock (r+1, c−1) can be decoded beforecurrent macroblock68′. Further, in the preceding macroblock row (i.e. macroblock row r), since the encoding process uses (r, c+3) as the rightmost macroblock, the decoder can use (r, c+3) as the rightmost macroblock during decoding as well. As discussed previously, offset j can be determined by subtracting the column row position of rightmost macroblock of the preceding row used during encoding of the current macroblock from the column row position of the current macroblock being processed. InFIG.7A, offset j would be calculated by subtracting the column row position of macroblock (r, c+3) from the column position ofcurrent macroblock68′ (i.e. (r+1, c)), or c+3−c, giving rise to an offset of 3.

In the preferred embodiment, the offset can be determined by the specific requirements of the codec. In alternative embodiments, the offset can be specified in the bitstream.

While the invention has been described in connection with certain embodiments, it is to be understood that the invention is not to he limited to the disclosed embodiments but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims, which scope is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures as is permitted under the law.

Claims (25)

What is claimed is:

1. An apparatus for decoding frames of a compressed video data stream, including at least one frame divided into partitions, the apparatus comprising:

a memory; and

a processor configured to execute instructions stored in the memory to:

read, from the compressed video data stream, partition data information indicative of a partition location with respect to the compressed video data stream for at least one of the partitions;

decode, from the compressed video data stream, a first partition of the partitions that includes a first sequence of blocks; and

decode, from the compressed video data stream, a second partition of the partitions that includes a second sequence of blocks identified based on the partition location indicated by the partition data information, using decoded information of the first partition;

wherein the first partition and the second partition have each been individually compressed; and

output or store a decoded frame including the first sequence of blocks and the second sequence of blocks.

2. The apparatus ofclaim 1, wherein the decoding includes decoding lossless coded information.

3. The apparatus ofclaim 1, wherein the processor is further configured to identify one row of blocks in the frame having a boundary between the first partition and the second partition.

4. The apparatus ofclaim 1, wherein the first partition includes contiguous blocks in at least a portion of a first row and at least a portion of a first subsequent row.

5. The apparatus ofclaim 4, wherein the second partition includes contiguous blocks in at least a portion of a second row and at least a portion of a second subsequent row.

6. The apparatus ofclaim 1, wherein the first partition comprises blocks of two or more contiguous rows of blocks.

7. The apparatus ofclaim 1, wherein the processor is further configured to decode the second sequence of blocks using context information contained in the first sequence of blocks.

8. The apparatus ofclaim 7, wherein the processor is further configured to perform at least one of intra-frame prediction or inter-frame prediction on the second partition.

9. The apparatus ofclaim 7, wherein the processor decodes the second partition with an offset of a specified number of blocks such that at least a portion of decoded context information of the first sequence of blocks is available as context data for decoding at least one block in the second partition.

10. The apparatus ofclaim 9, wherein the offset is determined based upon size of the context.

11. The apparatus ofclaim 7, wherein the first sequence of blocks in the first partition and the second sequence of blocks in the second partition are derived from corresponding rows of blocks in two successive frames of the video data, and wherein the processor is further configured to:

decode at least one block in the second partition using information from a block previously decoded.

12. The apparatus ofclaim 1, wherein the decoding includes context-based arithmetic coding.

13. A non-transitory computer-readable storage medium having stored thereon an encoded bitstream, including at least one frame divided into individually compressed partitions, wherein the encoded bitstream is configured for decoding by operations comprising:

reading, from the encoded bitstream, partition data information indicative of a partition location with respect to the encoded bitstream for at least one of the partitions;

decoding, from the encoded bitstream, a first partition of the partitions that includes a first sequence of blocks;

decoding, from the encoded bitstream, a second partition of the partitions that includes a second sequence of blocks identified based on the partition location indicated by the partition data information, using decoded information of the first partition; and

outputting or storing a decoded frame including the first sequence of blocks and the second sequence of blocks.

14. The non-transitory computer-readable storage medium of claim 13, wherein the decoding includes decoding losslessly coded information.

15. The non-transitory computer-readable storage medium of claim 13, wherein the decoding includes decoding the second sequence of blocks using context information contained in the first sequence of blocks.

16. The non-transitory computer-readable storage medium of claim 15, wherein the decoding includes decoding the second partition with an offset of a specified number of blocks such that at least a portion of decoded context information of the first sequence of blocks is available as context data for decoding at least one block in the second partition.

17. The non-transitory computer-readable storage medium of claim 16, wherein the offset is determined based upon size of the context.

18. The non-transitory computer-readable storage medium of claim 15, wherein the first sequence of blocks in the first partition and the second sequence of blocks in the second partition are derived from corresponding rows of blocks in two successive frames of the video data, and wherein the decoding includes:

decoding at least one block in the second partition using information from a block previously decoded.

19. The non-transitory computer-readable storage medium of claim 13, wherein the decoding includes context-based arithmetic coding.

20. An apparatus for encoding frames of a video, including at least one frame divided into partitions, the apparatus comprising:

a memory; and

a processor configured to execute instructions stored in the memory to:

encode, into a compressed video data stream, a first partition of the partitions that includes a first sequence of blocks;

encode, into the compressed video data stream, at a partition location with respect to the compressed video data stream, a second partition of the partitions that includes a second sequence of blocks encoded using information of the first partition;

include, in the compressed video data stream, partition data information indicative of the partition location with respect to the compressed video data stream for at least one of the partitions; and

output or store the compressed video data stream.

21. The apparatus of claim 20, wherein the processor is configured to execute the instructions to use context information from the first sequence of blocks to encode the second sequence of blocks.

22. The apparatus of claim 21, wherein the processor is configured to execute the instructions to encode the second partition with an offset of a specified number of blocks such that at least a portion of context information from the first sequence of blocks is available as context data for encoding at least one block in the second partition.

23. The apparatus of claim 22, wherein the offset is determined based upon size of the context.

24. The apparatus of claim 22, wherein the first sequence of blocks in the first partition and the second sequence of blocks in the second partition are derived from corresponding rows of blocks in two successive frames of the video data, and the processor is configured to execute the instructions to:

use information from a block previously decoded to encode at least one block in the second partition.

25. The apparatus of claim 24, wherein to encode the processor is configured to execute the instructions to use context-based arithmetic coding.

Images