Parallel entropy coding

1. A method for parallel encoding digital pictures, comprising:

a) partitioning a digital picture into two or more vertical sections;

b) performing a first stage of entropy coding on the two or more vertical sections with two or more corresponding Stage 1 encoder units on a row-by-row basis, wherein the entropy coding of the two or more vertical sections is performed in parallel such that each Stage 1 encoder unit performs entropy coding on its respective vertical section and returns a partially coded Stage 1 output to a Stage 2 encoder unit, wherein each partially coded Stage 1 output includes a representation of data for a corresponding vertical section that has been compressed by a compression factor greater than 1; and

c) generating a final coded bitstream with the Stage 2 encoder unit from the partially encoded bitstreams as a Stage 1 output.

2. The method of claim 1 wherein the compression factor is 50 or greater.

3. The method of claim 1 , further comprising, prior to b), performing a mode search on the two or more vertical sections on a row-by-row basis.

4. The method of claim 1 , wherein b) includes transferring boundary syntax data for a last sub-section of a row of one vertical section to an encoder that performs entropy coding for a vertical section that borders on the last sub-section.

5. The method of claim 4 , wherein b) includes entropy coding using context adaptive variable length coding and the boundary syntax data includes a number of non-zero coefficients for every block.

6. The method of claim 4 wherein b) includes entropy coding using context adaptive binary arithmetic coding and the boundary syntax data includes one or more syntax elements from which a context index increment can be derived.

7. The method of claim 1 , wherein b) and c) include entropy coding using context adaptive variable length coding and wherein b) and c) include avoiding data dependency between Stage 1 encoders in encoding a subsection skip run.

8. The method of claim 7 , wherein the partially coded Stage 1 output generated by each Stage 1 encoder unit includes a bitstream containing partially encoded bits representing each subsection in the vertical section encoded by the given encoder unit, and a corresponding size of the bitstream.

9. The method of claim 8 , wherein, during c), the Stage 2 encoder initializes a subsection skip run to 0 as indicated and, for each incoming MB bitstream, the Stage 2 encoder determines whether a given macroblock is skipped by checking the size of the bitstream.

10. The method of claim 9 , wherein, if the bitstream size is determined to be zero, the corresponding subsection is a skipped subsection and the Stage 2 encoder updates the value of the subsection skip run, and wherein, if, the size of the bitstream size is determined to be other than zero, the Stage 2 encoder encode the subsection skip run, concatenate the bitstream, and reset subsection skip run to zero.

11. The method of claim 1 wherein b) and c) include entropy coding using context adaptive binary arithmetic coding and the partially coded Stage 1 output generated by each Stage 1 encoder unit includes a binary string containing a plurality of bins representing each subsection in the vertical section encoded by the given encoder unit.

12. The method of claim 11 , wherein the Stage 1 encoders output the binary string only as the Stage 1 output, and wherein, during c), the Stage 2 encoder parses the binary string to retrieve all subsection syntax elements from the Stage 1 output and derives a context index for each bin in the bin string, and encode the bin string to the final coded bitstream.

13. The method of claim 11 wherein the partially coded Stage 1 output generated by each Stage 1 encoder unit further includes a context index array that stores a context index for each bin in the bin string.

14. The method of claim 13 , wherein the Stage 1 encoders output the binary string and the context index array as the Stage 1 output and, during c), the Stage 2 encoder unit directly encodes the final coded bitstream from the bin string and the context index array.

15. The method of claim 11 wherein the partially coded Stage 1 output generated by each Stage 1 encoder unit further includes a context index increment packet that includes a context index increment for one or more bins in the bin string that require a context index increment to derive their context index.

16. The method of claim 15 wherein, during c), the Stage 2 encoder unit parses each bin string, retrieves a corresponding context index increment from the context index increment packet and adds the context index increment to a context index Offset to determine the context index for a bin.

17. The method of claim 1 , wherein b) and c) include avoiding data dependency between Stage 1 encoders for first and last vertical sections in encoding a subsection quantization parameter (QP) difference.

18. The method of claim 17 , wherein b) and c) include entropy coding using context adaptive variable length coding and wherein the Stage 1 output for a given subsection includes an encoder-assigned QP value (QP E ) for the given subsection, a first part containing a bitstream before the subsection QP difference, and a second part containing a bitstream after the subsection QP difference and wherein the subsection QP difference is not encoded in either the first or second parts, and wherein the Stage 1 output includes a first size for the first part and a second size for the second part.

19. The method of claim 18 , wherein during c) the Stage 2 encoder unit compares the first and second sizes to zero, and wherein:

if the first size is zero, the Stage 2 encoder updates a subsection skip run for the given subsection,

if the first size is not zero and the second size is zero, the Stage 2 encoder encodes the subsection skip run, concatenates the first part and resets the subsection skip run to zero,

if both the first and second sizes are not zero, the Stage 2 encoder derives a value of the subsection QP difference as a difference between the encoder assigned QP value QP E and a reconstructed QP value for a previous subsection, updates the reconstructed QP value for the previous subsection with the encoder assigned QP value QP E , encodes the subsection skip run and then sets the subsection skip run to zero, concatenates the first part into the Stage 2 Output, encodes the value of the subsection QP difference, and concatenates the second part into the Stage 2 Output.

20. The method of claim 17 ) wherein b) and c) include entropy coding using context adaptive binary arithmetic coding and wherein the Stage 1 output for a given subsection includes an encoder-assigned QP value (QP E ) for the given subsection, a binary string for the given subsection that does not include a value of a subsection QP difference, and a context index increment packet that does not include a context index increment corresponding to the subsection QP difference.

21. The method of claim 20 wherein during c), the stage 2 encoder parses the binary string and determines whether a subsection QP difference exists for the given subsection, wherein,

if the subsection QP difference does not exist, the Stage 2 encoder encodes the binary string to the Stage 2 Output,

if the subsection QP difference does exist, the Stage 2 encoder encodes the binary string and, during encoding of the binary string, the Stage 2 encoder derives the context index increment for the subsection QP difference based on a previous subsection's syntax information and encodes the subsection QP difference using the derived context index increment.

22. The method of claim 17 wherein b) and c) include cutting off a data dependency encoding of a first vertical section and encoding of a last vertical section.

23. The method of claim 22 wherein, for each subsection in a last column of subsections, the Stage 1 encoder assigns a fixed value to an encoder-assigned QP value (QP E ) and forces each subsection in the last column to always have a subsection QP difference value syntax element.

24. The method of claim 23 wherein the Stage 1 encoder assigns the fixed value and determines a subsection QP difference value for each subsection in the last column from the fixed value and a reconstructed QP value for a next-to-last column.

25. The method of claim 24 , wherein b) and c) include entropy coding using context adaptive variable length coding, and wherein the Stage 1 encoder encodes the subsection QP difference value and wherein the Stage 2 encoder encodes a value of a subsection skip run from the Stage 1 output.

26. The method of claim 24 , wherein b) and c) include entropy coding using context adaptive binary arithmetic coding, wherein the partially coded Stage 1 output generated by each Stage 1 encoder unit includes a binary string containing a plurality of bins representing each subsection in the vertical section encoded by the given encoder unit, and wherein the Stage 1 encoder includes determined subsection QP difference value into the binary string.

27. The method of claim 26 wherein the Stage 2 encoder derives a context index increment for the subsection QP difference from the Stage 1 output and encodes the subsection QP difference value and the binary string to the Stage 2 output.

28. A non-transitory computer-readable storage medium having computer executable program instructions embodied therein, wherein the computer executable program instructions are configured, when executed to:

a) partition a digital picture into two or more vertical sections;

b) perform a first stage of entropy coding on the two or more vertical sections with two or more corresponding Stage 1 encoder units on a row-by-row basis, wherein the entropy coding of the two or more vertical sections is performed in parallel such that each Stage 1 encoder unit performs entropy coding on its respective vertical section and returns a partially coded Stage 1 output to a Stage 2 encoder unit, wherein each partially coded Stage 1 output includes a representation of data for a corresponding vertical section that has been compressed by a compression factor greater than 1; and

c) generate a final coded bitstream with the Stage 2 encoder unit from the partially encoded bitstreams as a Stage 2 output.

29. A system for parallel digital picture encoding, comprising:

two or more Stage 1 encoder units;

a Stage 2 encoder unit;

a memory coupled to the Stage 1 and Stage 2 encoder units;

instructions embodied in the memory and executable by the processor, wherein the instructions are configured to implement a method for the parallel encoding of the one or more digital pictures, wherein the computer executable program instructions are configured, when executed to:

a) partition a digital picture into two or more vertical sections;

b) perform a first stage of entropy coding on the two or more vertical sections with two or more corresponding Stage 1 encoder units on a row-by-row basis, wherein the entropy coding of the two or more vertical sections is performed in parallel such that each Stage 1 encoder unit performs entropy coding on its respective vertical section and returns a partially coded Stage 1 output to the Stage 2 encoder unit, wherein each partially coded Stage 1 output includes a representation of data for a corresponding vertical section that has been compressed by a compression factor greater than 1; and

c) generate a final coded bitstream with the Stage 2 encoder unit from the partially encoded bitstreams as a Stage 2 output.