BREAKPOINT DETERMINING FOR HYBRID VARIABLE LENGTH CODING AND ENCODING THE DETERMINED BREAKPOINT

• US 20080170613A1
• Filed: 12/20/2007
• Published: 07/17/2008
• Est. Priority Date: 01/16/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chen, Wen-hsiung, Chang, Pi Sheng, Tian, Dihong
• Granted Patent: US 8,121,427 B2
• Time in Patent Office: Days
• US Class Current: 375/240.03
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/157 Assigned coding mode, i.e. the coding mode being predefined or preselected to be further used for selection of another element or parameter
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients

Abstract

A method, and apparatus, and logic encoded in one or more computer-readable tangible medium to carry out a method of determining a breakpoint position in an ordered sequence of quantized transform coefficients of a block of image data for a hybrid variable length coding the ordered sequence. The breakpoint location in the sequence is between a low-frequency region and a high-frequency region. The hybrid variable length coding method includes coding the low-frequency region using a selected low-frequency variable length coding method; coding the high-frequency region using a selected high-frequency variable length coding method; and coding the position in the sequence of the breakpoint. The breakpoint location is determining uses a relatively simple and fast method based on pre-defined cost criteria. A method is included that instead of coding the breakpoint separately, codes the breakpoint jointly with coefficient events.

Claims

1. A method comprising:

for an ordered sequence of quantized transform coefficients of a block of image data, the quantized transform coefficients having respective amplitudes including a most likely-to-occur amplitude and at least one other amplitude, and for a selected low-frequency variable length coding method that includes recognizing events that each includes a cluster of coefficients having respective amplitudes other than the most likely-to-occur amplitude, determining a set of candidate breakpoints, each candidate breakpoint being defined by an ending event location for position events recognized in using the selected low-frequency variable length coding method, any candidate breakpoints that defines a position after the start of the sequence being for a hybrid coding method that includes using the selected low-frequency coding method until the ending event, and using a selected high-frequency method to encode a part of the sequence starting from immediately after the ending event;

for each candidate breakpoint, determining the weighted sum of the number of clusters of coefficients with other than the most likely-to-occur amplitude having each cluster length possible for the candidate breakpoint, the weighting for the number of clusters having a particular cluster length being an amount proportional the particular cluster length;

selecting as the breakpoint to use a candidate breakpoint that maximizes the weighted sum of numbers of clusters of each cluster length;

encoding the sequence including encoding a first portion of the sequence up to and including the final ending event defined by the selected breakpoint using the selected low-frequency variable length coding method and encoding a second portion of the sequence from the first coefficient after the final ending event to the end of the sequence using the selected high-frequency variable length coding method.

2. A method as recited in claim 1, further comprising encoding the position in the ordered sequence of the breakpoint selected breakpoint such that a decoder can know how to decode a coded bitstream.

3. A method as recited in claim 2, wherein the selected low-frequency coding method includes one-dimensional position and one-dimensional amplitude coding.

4. A method as recited in claim 2, wherein the selected low-frequency coding method includes two-dimensional position and one-dimensional amplitude coding.

5. A method as recited in claim 2, wherein the selected low-frequency coding method includes integrated position and amplitude coding.

6. A method as recited in claim 2, wherein the selected low-frequency coding method includes two-dimensional position and multi-dimensional amplitude coding.

7. A method as recited in claim 2, wherein the selected low-frequency coding method includes integrated position and amplitude coding with low valued amplitude and low number of clusters coding.

8. A method as recited in claim 2, wherein the selected breakpoint is encoded jointly with position events as an indication in the encoding of the position events in the selected low-frequency variable length coding method of whether or not to switch from the selected low-frequency coding method to the selected high-frequency variable length coding method.

9. A method as recited in claim 1, wherein 0 is the most likely-to-occur amplitude such that position events for the selected low-frequency variable length coding method include a cluster of one or more non-zero-valued quantized coefficients.

10. A method as recited in claim 1, wherein the weighting for the number of clusters having a particular cluster length is proportional to the amount by which the particular cluster length exceeds a pre-defined value.

11. A method as recited in claim 1, wherein determining the weighted sums for all candidate breakpoints is carried out by scanning the ordered sequence, adding when reaching a current candidate breakpoint an increment to the sum determined for the previous candidate breakpoint proportional to the run-length of consecutive coefficients having other than the most-likely-to-occur amplitude between the present candidate breakpoint and the previous candidate breakpoint.

17. A method as recited in claim 1, wherein 0 is the most likely-to-occur amplitude such that position events for the selected low-frequency variable length coding method include a cluster of one or more non-zero-valued quantized coefficients.

12. A method comprising:

determining a breakpoint for hybrid variable length coding an ordered sequence of quantized transform coefficients of a block, or for hybrid variable length coding ordered sequences of a multi-block partition, the breakpoint determining using a relationship to properties of blocks that neighbor the block or multi-block partition, wherein the breakpoint is defined by an ending event location for position events recognized in using a selected low-frequency variable length coding method, wherein hybrid variable length coding a sequence includes encoding a first portion of the sequence up to and including the final ending event defined by the breakpoint using the selected low-frequency variable length coding method and encoding a second portion of the sequence from the first coefficient after the final ending event to the end of the sequence using a selected high-frequency variable length coding method;

encoding the ordered sequence of quantized transform coefficients of the block, or the ordered sequences of the ordered sequences of the multi-block partition, the encoding using hybrid variable length coding using the determined breakpoint,

wherein the determined breakpoint is encoded jointly with position events as an indication in the encoding of the position events in the selected low-frequency variable length coding method of whether or not to switch from the selected low-frequency coding method to the selected high-frequency variable length coding method.

13. A method comprising:

for each ordered sequence of quantized transform coefficients of a block of image data in a multi-block partition, the quantized transform coefficients having respective amplitudes including a most likely-to-occur amplitude and at least one other amplitude, and for a selected low-frequency variable length coding method that includes recognizing events that each includes a cluster of coefficients having respective amplitudes other than the most likely-to-occur amplitude, determining a respective set of candidate breakpoints, each candidate breakpoint being defined by an ending event location for position events recognized in using the selected low-frequency variable length coding method, any candidate breakpoints that defines a position after the start of the respective sequence being for a hybrid coding method that includes using the selected low-frequency coding method until the ending event, and using a selected high-frequency method to encode a part of the sequence starting from immediately after the ending event;

for each candidate breakpoint, determining the weighted sum of the number of clusters of coefficients with other than the most likely-to-occur amplitude having each cluster length possible for the candidate breakpoint for the respective sequence in the multi-block partition, the weighting for the number of clusters having a particular cluster length being an amount proportional the particular cluster length;

for the plurality of the blocks in the multi-block partition, determining a set of candidate breakpoints to use for all blocks of the multi-block partition, and for each such candidate breakpoint, the determining the sum of respective weighted sums for the respective blocks, each weighted sum being for a respective one of the blocks of the multi-block partition, and being for a candidate breakpoint equal to the weighted sum of the number of events in the low frequency region of the particular block, the weighting for the number of clusters having a particular cluster length being by an amount proportional the particular cluster length, wherein each candidate breakpoint is one of the candidate breakpoints of the sets of breakpoints determined in for the respective sequences of the blocks of the plurality, and applied as a soft breakpoint when determining the weighted sums for the blocks in the multi-block partition;

comparing the sum of the weighted sums using the candidate breakpoints, and selecting as the single breakpoint the one candidate breakpoint of the set determined in that gives the maximum sum of weighted sums.

14. A method as recited in claim 13, further comprising:

encoding all the sequences of the multi-block partition, including, for each sequence, encoding a first portion of the sequence up to the selected single breakpoint using the selected low-frequency variable length coding method and encoding a second portion of the sequence from the first coefficient after the selected single breakpoint to the end of the sequence using the selected high-frequency variable length coding method, the one single breakpoint being used as a soft breakpoint for any sequence of a block of the multi-block partition.

15. A method as recited in claim 14, further comprising encoding the position of the selected single breakpoint.

16. A method as recited in claim 13, wherein the weighting for the number of clusters having a particular cluster length is by how much the cluster length exceeds a predefined value.

18. A computer-readable medium having instructions encoded thereon that when executed by one or more processors of a processors system cause a method to be carried out, the method comprising:

for an ordered sequence of quantized transform coefficients of a block of image data, the quantized transform coefficients having respective amplitudes including a most likely-to-occur amplitude and at least one other amplitude, and for a selected low-frequency variable length coding method that includes recognizing events that each includes a cluster of coefficients having respective amplitudes other than the most likely-to-occur amplitude, determining a set of candidate breakpoints, each candidate breakpoint being defined by an ending event location for position events recognized in using the selected low-frequency variable length coding method, any candidate breakpoints that defines a position after the start of the sequence being for a hybrid coding method that includes using the selected low-frequency coding method until the ending event, and using a selected high-frequency method to encode a part of the sequence starting from immediately after the ending event;

for each candidate breakpoint, determining the weighted sum of the number of clusters of coefficients with other than the most likely-to-occur amplitude having each cluster length possible for the candidate breakpoint, the weighting for the number of clusters having a particular cluster length being an amount proportional the particular cluster length;

select as the breakpoint to use a candidate breakpoint that maximizes the weighted sum of numbers of clusters of each cluster length;

encoding the sequence including encoding a first portion of the sequence up to and including the final ending event defined by the selected breakpoint using the selected low-frequency variable length coding method and encoding a second portion of the sequence from the first coefficient after the final ending event to the end of the sequence using the selected high-frequency variable length coding method.

19. A computer-readable medium having instructions encoded thereon that when executed by one or more processors of a processors system cause a method to be carried out, the method comprising:

determining a breakpoint for hybrid variable length coding an ordered sequence of quantized transform coefficients of a block, or for hybrid variable length coding ordered sequences of a multi-block partition, the breakpoint determining using a relationship to properties of blocks that neighbor the block or multi-block partition, wherein the breakpoint is defined by an ending event location for position events recognized in using a selected low-frequency variable length coding method, wherein hybrid variable length coding a sequence includes encoding a first portion of the sequence up to and including the final ending event defined by the breakpoint using the selected low-frequency variable length coding method and encoding a second portion of the sequence from the first coefficient after the final ending event to the end of the sequence using a selected high-frequency variable length coding method;

encoding the ordered sequence of quantized transform coefficients of the block, or the ordered sequences of the ordered sequences of the multi-block partition, the encoding using hybrid variable length coding using the determined breakpoint,

wherein the determined breakpoint is encoded jointly with position events as an indication in the encoding of the position events in the selected low-frequency variable length coding method of whether or not to switch from the selected low-frequency coding method to the selected high-frequency variable length coding method.

20. A computer-readable medium having instructions encoded thereon that when executed by one or more processors of a processors system cause a method to be carried out, the method comprising:

for each ordered sequence of quantized transform coefficients of a block of image data in a multi-block partition, the quantized transform coefficients having respective amplitudes including a most likely-to-occur amplitude and at least one other amplitude, and for a selected low-frequency variable length coding method that includes recognizing events that each includes a cluster of coefficients having respective amplitudes other than the most likely-to-occur amplitude, determining a respective set of candidate breakpoints, each candidate breakpoint being defined by an ending event location for position events recognized in using the selected low-frequency variable length coding method, any candidate breakpoints that defines a position after the start of the respective sequence being for a hybrid coding method that includes using the selected low-frequency coding method until the ending event, and using a selected high-frequency method to encode a part of the sequence starting from immediately after the ending event;

for each candidate breakpoint, determining the weighted sum of the number of clusters of coefficients with other than the most likely-to-occur amplitude having each cluster length possible for the candidate breakpoint for the respective sequence in the multi-block partition, the weighting for the number of clusters having a particular cluster length being an amount proportional the particular cluster length;

for the plurality of the blocks in the multi-block partition, determining a set of candidate breakpoints to use for all blocks of the multi-block partition, and for each such candidate breakpoint, the determining the sum of respective weighted sums for the respective blocks, each weighted sum being for a respective one of the blocks of the multi-block partition, and being for a candidate breakpoint equal to the weighted sum of the number of events in the low frequency region of the particular block, the weighting for the number of clusters having a particular cluster length being by an amount proportional the particular cluster length, wherein each candidate breakpoint is one of the candidate breakpoints of the sets of breakpoints determined in for the respective sequences of the blocks of the plurality, and applied as a soft breakpoint when determining the weighted sums for the blocks in the multi-block partition;

comparing the sum of the weighted sums using the candidate breakpoints, and selecting as the single breakpoint the one candidate breakpoint of the set determined in that gives the maximum sum of weighted sums;

encoding all the sequences of the multi-block partition, including, for each sequence, encoding a first portion of the sequence up to the selected single breakpoint using the selected low-frequency variable length coding method and encoding a second portion of the sequence from the first coefficient after the selected single breakpoint to the end of the sequence using the selected high-frequency variable length coding method, the one single breakpoint being used as a soft breakpoint for any sequence of a block of the multi-block partition; and

encoding the position of the selected single breakpoint.