Methods and devices for data compression using context-based coding order

Abstract

A method is presented for entropy coding data using an entropy coder to encode an input sequence. A context model is used to determine the context of each symbol and a probability estimation is made for each symbol. A method is presented for revising the coding order to be context-based, grouping symbols consecutively on the basis that they have a common context. A method is presented for entropy decoding a bitstream of encoded data encoded using a context-based coding order.

What is claimed is: 
     
         1 . A non-transitory processor-readable medium storing processor-executable instructions which, when executed by one or more processors, cause the one or more processors to decode encoded data to reconstruct a sequence of symbols, wherein the encoded data has been encoded in accordance with a context model, wherein the context model specifies a context for each symbol, and wherein, when executed, the instructions cause the one or more processors to:
 for each of two or more of the contexts, decode a portion of the encoded data to obtain a group of consecutive symbols having that context, wherein decoding includes
 jointly determining in parallel, for the consecutive symbols in one of the groups, a probability associated with each symbol, and 
 decoding each of the consecutive symbols from the encoded data based on its determined probability; and 
   reconstruct the sequence of symbols by reordering the symbols of the groups of consecutive symbols, wherein reordering the symbols results in a series of sequences, and wherein the context for each symbol is associated, at least in part, with that symbol's position in its sequence.   
     
     
         2 . The non-transitory processor-readable medium claimed in  claim 1 , wherein the reordering is based upon a coding order specified by the context model. 
     
     
         3 . The non-transitory processor-readable medium claimed in  claim 2 , wherein each of the groups of consecutive symbols is associated with one of the contexts defined in the context model, and wherein the reordering includes interleaving the symbols of the groups to undo the context-based grouping. 
     
     
         4 . The non-transitory processor-readable medium claimed in  claim 1 , wherein the group of consecutive symbols contains symbols having the same symbol position in their respective sequences. 
     
     
         5 . The non-transitory processor-readable medium claimed in  claim 1 , wherein the encoded data comprises a plurality of significance maps, each map including a significant-coefficient sequence and a last-coefficient sequence, and wherein each group of consecutive symbols comprises bits having the same bit position in a series of the significant-coefficient sequences or the last-coefficient sequences. 
     
     
         6 . A decoder for decoding encoded data to reconstruct a sequence of symbols, wherein the encoded data has been encoded in accordance with a context model, wherein the context model specifies a context for each symbol, the decoder comprising:
 means for decoding that, for each of two or more of the contexts, decodes a portion of the encoded data to obtain a group of consecutive symbols having that context, wherein decoding includes
 jointly determining in parallel, for the consecutive symbols in one of the groups, a probability associated with each symbol, and 
 decoding each of the consecutive symbols from the encoded data based on its determined probability, and 
   means for reconstructing the sequence of symbols by reordering the symbols of the groups of consecutive symbols, wherein reordering the symbols results in a series of sequences, and wherein the context for each symbol is associated, at least in part, with that symbol's position in its sequence.   
     
     
         7 . The decoder claimed in  claim 6 , wherein the means for reconstructing reorders the symbols based upon a coding order specified by the context model. 
     
     
         8 . The decoder claimed in  claim 7 , wherein each of the groups of consecutive symbols is associated with one of the contexts defined in the context model, and wherein the means for reconstructing reorders by interleaving the symbols of the groups to undo the context-based grouping. 
     
     
         9 . The decoder claimed in  claim 6 , wherein the group of consecutive symbols contains symbols having the same symbol position in their respective sequences. 
     
     
         10 . The decoder claimed in  claim 6 , wherein the encoded data comprises a plurality of significance maps, each map including a significant-coefficient sequence and a last-coefficient sequence, and wherein each group of consecutive symbols comprises bits having the same bit position in a series of the significant-coefficient sequences or the last-coefficient sequences. 
     
     
         11 . A non-transitory processor-readable medium storing processor-executable instructions which, when executed by one or more processors, cause the one or more processors to entropy encode an input sequence of symbols using a context model, wherein the context model specifies a context for each symbol, wherein the instructions, when executed, cause the one or more processors to:
 reorder the input sequence to group the symbols on the basis of context to form groups of symbols, each group being associated with a respective one of the contexts;   for each of the groups of symbols, jointly determine in parallel, for the symbols in the group, a probability associated with each symbol; and   for each of the groups of symbols, encode consecutively the symbols in that group based upon their determined probabilities, to produce encoded data, wherein the input sequence includes a series of sequences and wherein the context for each symbol is based, at least in part, upon that symbol's position in its sequence.   
     
     
         12 . The non-transitory processor-readable medium claimed in  claim 11 , wherein the group of consecutive symbols contains symbols having the same symbol position in their respective sequences. 
     
     
         13 . The non-transitory processor-readable medium claimed in  claim 11 , wherein the input sequence comprises a plurality of significance maps, each map including a significant-coefficient sequence and a last-coefficient sequence, and wherein each group of symbols comprises bits having the same bit position in a series of the significant-coefficient sequences or the last-coefficient sequences. 
     
     
         14 . An encoder for entropy encoding an input sequence of symbols using a context model, wherein the context model specifies a context for each symbol, the encoder comprising:
 means for reordering the input sequence to group the symbols on the basis of context to form groups of symbols, each group being associated with a respective one of the contexts,   means for determining probability by, for each of the groups of symbols, jointly determining in parallel, for the symbols in the group, a probability associated with each symbol, and   means for encoding that, for each of the groups of symbols, encodes consecutively the symbols in that group based upon their determined probabilities, to produce encoded data, wherein the input sequence includes a series of sequences and wherein the context for each symbol is based, at least in part, upon that symbol's position in its sequence.   
     
     
         15 . The encoder claimed in  claim 14 , wherein the group of consecutive symbols contains symbols having the same symbol position in their respective sequences. 
     
     
         16 . The encoder claimed in  claim 14 , wherein the input sequence comprises a plurality of significance maps, each map including a significant-coefficient sequence and a last-coefficient sequence, and wherein each group of symbols comprises bits having the same bit position in a series of the significant-coefficient sequences or the last-coefficient sequences.