Error-Resilient Entropy Coding For Partial Embedding And Fine Grain Scalability

• US 20090232408A1
• Filed: 03/12/2008
• Published: 09/17/2009
• Est. Priority Date: 03/12/2008
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Meany, James J.
• Granted Patent: US 8,509,555 B2
• Time in Patent Office: Days
• US Class Current: 382/246
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/34 Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/64 characterised by ordering of coefficients or of bits for transmission
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

Methods, apparatus and computer program products are provided that generate a plurality of code words representative of data to be encoded. The code words may be generated to have first and second portions with each first portion including information that is representative of a predetermined characteristic of an associated second portion and each second portion including information that is representative of a respective portion of the data. A plurality of blocks may also be defined with each block including one or more bitplanes of the second portions of the code words. The plurality of blocks may be sequenced to achieve progressive representations of the encoded content in accordance with schemes to order the data according to priority of content. Content may be provided a level of error protection commiserate with its priority.

Claims

1. (canceled)

2. An error-resilient method of encoding or decoding data into a compressed bitstream comprising:

representing data values to be encoded or decoded with a plurality of code words, wherein the plurality of code words include code words having first and second portions with each first portion including information that is representative of a predetermined characteristic of an associated second portion and with each second portion including information that is representative of a respective portion of the data, and wherein the second portions of the code words are arranged into a plurality of bitblocks with each bitblock including one or more bitplanes of the second portions of the code words.

3. A method according to claim 2 further comprising the step of associating relative progression priorities to the individual bitblocks in accordance with a significance of the bitplanes within the bitblocks, with bitblocks having higher significance bitplanes being associated to higher progression priorities.

4. A method according to claim 3, further comprising the step of providing bitblocks with protection from errors by means of placement within the bitstream, with bitblocks placed sequentially within the bitstream in accordance with relative progression priorities, such that bitblocks having higher progression priorities are placed earlier within the bitstream, wherein bitblocks placed earlier in the bitstream are provided greater protection from errors whose incidence increases for later positions within the bitstream.

5. A method according to claim 3, further comprising the step of providing bitblocks with protection from errors by means of error correction coding applied to at least one bitblock, such that the level of error correction coding provided to at least one bitblock is greater than any error correction coding provided to bitblocks having lower relative progression priorities.

6. A method according to claim 3, further comprising the step of providing bitblocks with differing levels of protection from errors by means of transmission over channels subject to differing expected levels of signal to noise ratio, such that at least one bitblock is transmitted over a channel having a higher expected signal to noise ratio than the channel(s) used for transmission of bitblocks having lower relative progression priorities.

7. A method according to claim 3, further comprising the step of providing bitblocks with differing levels of protection from errors by means of differing strategies for block retransmission in an Automatic Repeat-reQuest (ARQ) error control protocol, with at least one block containing bitblocks having higher relative progression priorities retransmitted upon errors, but with blocks containing bitblocks having lower relative progression priorities not retransmitted upon errors.

8. A method according to claim 2 further comprising defining each bitblock to include a different bitplane that is not included in any other bitblock.

9. A method according to claim 2 wherein representing data values with a plurality of code words comprises employing code words having first and second portions with each first portion including information that is representative of the set of data values representable by an associated second portion, and with each second portion uniquely including information that is representative of the encoded data value within the set of data values designated by the associated first portion.

10. A method according to claim 9 wherein the number of data values in the set designated by the first portion of each code word is equal to 2^K, where K is an integer greater than or equal to zero, with each associated second portion comprised of code symbols, with the number of code symbols forming the associated second portion equal to K, and with the code symbols of the associated second portion collectively defining a code value which uniquely includes information that is representative of the encoded data value from among the set of 2^K data values designated by the first portion of the code word.

11. A method according to claim 9 wherein the first portion of each code word contains information representative of a consecutive range of data values representable by an associated second portion, and wherein each associated second portion is comprised of code symbols which collectively define a code value from among a range of possible code values, for which the range of possible code values defines an ordinal one-to-one mapping to the consecutive range of data values designated by the first portion of the code word.

12. A method according to claim 9, further comprising sorting a distribution of estimated probabilities or frequencies of occurrence for the data values to be encoded to produce a monotonically non-ascending distribution of probabilities or frequencies of occurrence, with the data values to be encoded associated to the placement of the corresponding probability or frequency value within the sorted distribution,

wherein the sorting of the probability or frequency distribution is performed in a forward adaptive or backward adaptive fashion,

wherein the compressed bitstream includes information representative of any forward adaptive sorting of the probability or frequency distribution, and

wherein representing data values with a plurality of code words comprises associating the plurality of code words to the data values as ordered within the sorted probability or frequency distribution.

13. A method according to claim 2, further comprising employing transformation and quantization of the data prior to encoding or after decoding the data, wherein transformation of the data comprises representing the data as a weighted sum of predetermined basis functions and wherein quantization of the transformed data comprises representing the transformed data such that the quantized data has an equal or smaller number of unique coefficient values than the transformed data, and wherein representing data values with a plurality of code words comprises associating the plurality of code words to the transformed and quantized data.

14. A method according to claim 13, further comprising the step of subdividing each bitblock and the first portions of associated code words into a plurality of bitblocks with one or more subdivisions applied over the range of each of one or more aspects of the associated transformed data, with said aspects selected from the group consisting of spatial, temporal, or other independent coordinates of the data as defined by spatial, temporal, or other subdivision of the data;

resolution or frequency coordinates of the transformed data as defined by the predetermined transformation basis functions;

orientation of transform subbands as defined by the predetermined transformation basis functions;

image plane among one or more image planes separated along color, spectral, temporal, or other independent coordinate(s), and significance of the bitplanes for the second portions of code words.

15. A method according to claim 14, wherein the individual bitblocks resulting from said subdividing step are each associated to an index comprised of one or more elements, with each element of the index associated with a corresponding bitblock aspect according to which the bitblocks have been subdivided,

wherein each element of the bitblock index is associated to a range of numeric values which vary in accordance with a relative priority of progression defined over a domain of the corresponding bitblock aspect, with higher values signifying higher progression priority, and

wherein each bitblock which contains the first portions of code words is associated to a significance index element having a higher relative priority value than the significance index elements associated to the corresponding bitblocks which contain bitplanes from the second portions of the same code words and which otherwise share the same coordinates within the domains of the bitblock aspects.

16. A method according to claim 15, wherein relative priority values for the significance index elements are associatable to a quality weighting factor which is defined in accordance with a predetermined distortion measure used to measure distortion between original and reconstructed data sets, with said quality weighting factor being monotonically related to an estimate of a change in a value for the predetermined distortion measure due to an error on a single bit of a bitplane represented within the bitblock, and

wherein the predetermined distortion measure is additionally weighted along one or more of the bitblock aspects, to support selective variation of the relative priority for subsets of the data in a prescribed fashion in accordance with factors selected from the group consisting of human perceptual considerations, quantitative distortion considerations, spatial, spectral or temporal filtering considerations, selective emphasis or region of interest considerations, considerations of the utility of the reconstructed data for specific applications, and an intended reversal of the relative progression priority along one or more of the bitblock aspects.

17. A method according to claim 16, wherein relative progression priorities for the individual bitblocks, prioritized with respect to bitblock aspects, are defined by an assignment of relative priorities to the individual aspects, ranging from the highest priority bitblock aspect to the lowest priority bitblock aspect,

wherein the relative progression priorities for the bitblocks are specified in accordance with a sort order which would be obtained by iteration of a series of nested loops which iterate over relative priority values of the index elements for the respective bitblock aspects, with the outermost loop iterating over the relative priority values of the index elements for the highest priority bitblock aspect, with successively internal loops iterating over the relative priority values of the index elements for successively lower priority bitblock aspects, and with the innermost loop iterating over the relative priority values of the index elements for the lowest priority bitblock aspect,

wherein a looped iteration over the relative priority values of the index elements for a bitblock aspect comprises iterating from the highest relative priority value to the lowest relative priority value of the index elements for the bitblock aspect associated with the current loop, while the relative priority values of the index elements for the higher priority bitblock aspects associated with the loops which are relatively external to the current loop remain fixed in accordance with the current iteration state of those relatively external loops, with the said relative priority values including any applicable weighting, and

wherein the relative progression priorities for individual bitblocks are specified in accordance with the iteration of the innermost loop, with successive iterations of the innermost loop specifying bitblocks with successively lower progression priorities, with each iteration of the innermost loop specifying the bitblock associated to the index for which the relative priority values of the index elements correspond to the current iteration state of the series of nested loops.

18. A method according to claim 16, wherein relative progression priorities for the individual bitblocks, prioritized with respect to bitblock aspects, are defined by an assignment of numeric weighting factors to each of the individual aspects, with the lowest priority progression aspect being assigned the smallest aspect weighting factor, with higher priority progression aspects being assigned correspondingly larger aspect weighting factors, and with the highest priority progression aspect being assigned the largest aspect weighting factor,

wherein a relative progression priority for each bitblock is computed as a weighted sum of the relative priority values of the index elements for the applicable bitblock aspects, each relative priority value multiplied by the aspect weighting factor for the respective bitblock aspect.

19. An apparatus for encoding or decoding data into a compressed bitstream comprising:

a processor configured to represent data values to be encoded or decoded with a plurality of code words, wherein the plurality of code words include code words having first and second portions with each first portion including information that is representative of a predetermined characteristic of an associated second portion and with each second portion including information that is representative of a respective portion of the data, and wherein the second portions of the code words are arranged into a plurality of bitblocks with each bitblock including one or more bitplanes of the second portions of the code words.

20. An apparatus according to claim 19 wherein the processor is further configured to associate relative progression priorities to the individual bitblocks in accordance with a significance of the bitplanes within the bitblocks, with bitblocks having higher significance bitplanes being associated to higher progression priorities.

21. A computer program product comprising at least one computer-readable storage medium having computer-readable program instructions stored therein, the computer-readable program instructions comprising:

program instructions configured to represent data values to be encoded or decoded with a plurality of code words,

wherein the plurality of code words include code words having first and second portions with each first portion including information that is representative of a predetermined characteristic of an associated second portion and with each second portion including information that is representative of a respective portion of the data, and

wherein the second portions of the code words are arranged into a plurality of bitblocks with each bitblock including one or more bitplanes of the second portions of the code words.