Hybrid variable length coding method for low bit rate video coding

A method of image compression comprising:

• dividing an image into blocks;
• and
• for each block:
• transforming the block to form transform coefficients for the block;
• quantizing the transform coefficients of the block;
• ordering the quantized coefficients of the block along a two-dimensional path to form an ordered series of quantized transform coefficients;
• forming events from the series of quantized transform coefficients, each event being a run of non-zero-valued coefficients in a first contiguous region defined by a breakpoint, a run of zero-valued coefficients in the first region, or a run of zero-valued coefficients in a second region defined by the breakpoint, the breakpoint defining the first region and a second continuous region in the series following the first region;
• forming a codeword for each runlength of non-zero-valued coefficients in the first region, the forming a codeword according to a first coding method;
• forming a codeword for each runlength of zero-valued coefficients in the first region, the forming a codeword according to a second coding method;
• and
• encoding the coefficient values in the second region according to a third coding method, the third coding method including identifying runs of zero-valued coefficients in the second region,
• such that relatively short codewords are formed to represent runlengths that are relatively more likely to occur, and relatively long codewords are formed to represent runlengths that are relatively less likely to occur, and
• wherein the breakpoint value is selected from a finite set of pre-defined breakpoint values according to which of the breakpoints of the set produces the shortest number of bits, or the breakpoint defines a soft boundary between the first and second regions, such that for a block having a sequence of consecutive values all being zero or all being non-zero crosses the breakpoint, the boundary between the first and second region is at or after the end of the sequence such that the whole sequence or any event that starts in the first region is in the first region.

An apparatus to encode an ordered series of quantized coefficients of a transform of a block of image data, the transform such that 0 is the most likely coefficient amplitude and 1 is the next most likely coefficient amplitude, the apparatus comprising:

• means for forming non-zero-amplitude events in a first contiguous region of the series of quantized transform coefficients, the first region defined by a breakpoint defining a first and a second contiguous regions region following the first region, each non-zero-amplitude event defined by the runlength of a run of non-zero-valued coefficients and by the values of the non-zero coefficients;
• means for forming zero-amplitude events in the first region of the series of quantized transform coefficients, each zero-amplitude event defined by the runlength of zero-valued coefficients;
• means for forming a codeword for each formed non-zero-amplitude event according to a first runlength coding method and codewords for the non-zero amplitudes in the event according to a first amplitude coding method;
• means for forming a codeword for each formed zero-amplitude event in the first region according to a second runlength coding method and a first amplitude coding method;
• means for forming zero-amplitude events from the second region of the series of quantized transform coefficients;
• means for forming a codeword for each formed zero-amplitude event in the second region according to a third runlength coding method;
• and
• means for forming a codeword for each non-zero amplitudes in the second region according to a second amplitude coding method,
• such that relatively short codewords are formed to represent events that are relatively more likely to occur, and relatively long codewords are formed to represent events that are relatively less likely to occur,
• wherein the breakpoint value is selected from a finite set of pre-defined breakpoint values according to which of the breakpoints of the set produces the shortest number of bits, or the breakpoint defines a soft boundary between the first and second regions, such that for a block having a sequence of consecutive values all being zero or all being non-zero crosses the breakpoint, the boundary between the first and second region is at or after the end of the sequence such that the whole sequence or any event that starts in the first region is in the first region.

An apparatus to encode an ordered series of quantized coefficients comprising:

• an event recognizer to recognize runs of consecutive zero-amplitude coefficients and runs of consecutive non-zero-amplitude coefficients in a first contiguous region of the series defined by a breakpoint in the ordering, the breakpoint defining the first contiguous and a second contiguous region following the first region in the series, the event recognizer further to recognize runs of consecutive zero-amplitude coefficients in the second region, the recognizer forming the runlengths of the zero and non-zero amplitudes in the first region, the non-zero amplitudes in the non-zero runs in the first region, the runlengths of zero-amplitudes in the second region, and the non-zero amplitudes in the second region;
• and
• an encoder coupled to the event recognizer, the encoder accepting and forming a codeword for each of the runlengths of non-zero-amplitudes in the first region, for each of the runlengths of zero-amplitudes in the first region, for each of the non-zero amplitudes in the first region, and further encoding the runlengths of zero-amplitudes in the second region, and the non-zero amplitudes in the second region,
• such that the apparatus forms relatively short codewords to represent combinations that are relatively more likely to occur, and relatively long codewords to represent combinations that are relatively less likely to occur,
• wherein the breakpoint value is selected from a finite set of pre-defined breakpoint values according to which of the breakpoints of the set produces the shortest number of bits, or the breakpoint defines a soft boundary between the first and second regions, such that for a block having a sequence of consecutive values all being zero or all being non-zero crosses the breakpoint, the boundary between the first and second region is at or after the end of the sequence such that the whole sequence or any event that starts in the first region is in the first region.

A method to decode a bitstream in order to form a series of quantized coefficients of a transform of a block of image data, the transform such that 0 is the most likely coefficient amplitude and 1 is the next most likely coefficient amplitude, the bitstream encoded by a method that includes:

• recognizing events in a first contiguous region of the series defined by a breakpoint in the ordering, the breakpoint defining the first contiguous and a second contiguous region following the first region in the series, the events including runs of consecutive zero-amplitude coefficients and runs of consecutive non-zero-amplitude coefficients in the first region, the recognizing including forming runlengths of recognized runs;
• recognizing events that are runs of consecutive zero-amplitude coefficients in the second region;
• the recognizing including forming runlengths of recognized runs;
• and
• forming a codeword for each of the runlengths of non-zero-amplitudes in the first region using a first runlength coding method, for each of the runlengths of zero-amplitudes in the first region using a second runlength coding method, for each of the non-zero amplitudes in the first region using a first amplitude coding method, and further forming codewords for the runlengths of zero-amplitudes in the second region, and the non-zero amplitudes in the second region,
• such that the encoding method forms relatively short codewords to represent combinations that are relatively more likely to occur, and relatively long codewords to represent combinations that are relatively less likely to occur,
• the decoding method comprising:
• recognizing a codeword;
• determining the event represented by the recognized codeword;
• and
• determining the sub-series of coefficients of each determined event, until all coefficients in the series are determined,
• wherein the breakpoint value is selected from a finite set of pre-defined breakpoint values according to which of the breakpoints of the set produces the shortest number of bits, or the breakpoint defines a soft boundary between the first and second regions, such that for a block having a sequence of consecutive values all being zero or all being non-zero crosses the breakpoint, the boundary between the first and second region is at or after the end of the sequence such that the whole sequence or any event that starts in the first region is in the first region.

An apparatus to decode a bitstream encoded by a coding method, the apparatus comprising:

• a codeword recognizer to accept the bits of the bitstream and recognize a codeword of a set of possible codewords that each represent an event, and
• a decoder coupled to the codeword recognizer to determine the event for the codeword recognized by the codeword recognizer,
• wherein each event that is coded by a set of codewords in the bitstream in a first region defined by a breakpoint is a run of non-zero-valued coefficients coded by a first runlength coding method and a first amplitude coding method, or a run of non-zero-valued coefficients coded by a second runlength coding method, and wherein each event coded in a second region defined by the breakpoint is a run of none or more zero-valued coefficients coded by a third runlength method, or a non-zero amplitude coded by a second amplitude coding method, the breakpoint defining the first region of contiguous coefficients and the second region following the first region, the first, second, and third coding methods being such that relatively short codewords in the bitstream represent events that are relatively more likely to occur, and relatively long codewords represent events that are relatively less likely to occur,
• wherein the breakpoint value is selected from a finite set of pre-defined breakpoint values according to which of the breakpoints of the set produces the shortest number of bits, or the breakpoint defines a soft boundary between the first and second regions, such that for a block having a sequence of consecutive values all being zero or all being non-zero crosses the breakpoint, the boundary between the first and second region is at or after the end of the sequence such that the whole sequence or any event that starts in the first region is in the first region.

A computer readable hardware storage medium having instructions coded thereon that when executed by one or more processors cause execution of a method to encode an ordered series of quantized coefficients, the processing system including a memory configured to store a data structure, the method comprising:

• forming codewords for a set of event formed from the ordered series of quantized transform coefficients of a block of image data, wherein the data structure provides the codewords for the set of events formed from the ordered series of quantized transform coefficients, such that the forming of the codewords includes looking up the data structure,
• wherein an event of the first kind in a first region defined by a breakpoint is a run of non-zero-valued coefficients, an event of the second kind in the first region defined by the breakpoint is a run of zero-valued coefficients, and an event of the third kind in a second region defined by the breakpoint is a run of zero-valued coefficients in the second region, and
• wherein the breakpoint defines a first region of contiguous coefficients of the series, and an immediately following second region of contiguous coefficients,
• wherein the breakpoint has a value selected from a finite set of pre-defined breakpoint values according to which of the breakpoints of the set produces the shortest number of bits, or the breakpoint defines a soft boundary between the first and second regions, such that for a block having a sequence of consecutive values all being zero or all being non-zero crosses the breakpoint, the boundary between the first and second region is at or after the end of the sequence such that the whole sequence is or any event that staffs in the first region in the first region,
• such that relatively short codewords in the data structure stored in the memory represent events that are relatively more likely to occur, and relatively long codewords represent events that are relatively less likely to occur.