Data encoding using one or more adaptive decision trees

A method for compressing a stream of data at a predetermined compression ratio, said method comprising the steps of:

• providing a first class set having a first plurality of error value ranges, wherein each error value range covers a sequential set of error values arid is identified by a class code representing the sequential set of error values associated said each error value range and further wherein a class code encompassing error values having a greater frequency of occurrence employs a lesser number of bits than a class code for a class encompassing error values having a lesser frequency of occurrence;
• generating a predicted data value for the data value to be quantized;
• determining an error value as the difference between the predicted data value and the data value to be compressed;
• identifying a class code for the data value by determining an error value range in the plurality of error value ranges the error value is within;
• encoding the class code to a first code comprising at least one bit, such that the data value is quantized;
• outputting the first code as part of a compressed data stream;
• after outputting the first code for a predetermined number of data values,
• comparing a number of bits utilized to output the compressed data stream representing data values to the predetermined compression ratio;
• if the number of bits utilized is greater than the predetermined compression ratio, modifying the first plurality of error value ranges in size for the first class set to provide a second class set having a second plurality of error value ranges different in size from the first plurality of error value ranges, such that error value ranges encompassing error values having a greater frequency of occurrence are increased in size to encompass a wider range of error values, thereby decreasing the compression ratio;
• and
• if the number of bits utilized is less than the predetermined compression ratio, modifying the first plurality of error value ranges for the first class set to provide a second class set having a second plurality of error value ranges different in size from the first plurality of error value ranges, such that error value ranges encompassing error values having a greater frequency of occurrence are decreased in size to encompass a narrower range of error values, thereby increasing the compression ratio;
• such that error value ranges are adapted to maintain the compressed data stream in the proximity of the predetermined compression ratio.

A method for compressing a stream of data values at a predetermined compression ratio, said method comprising the steps of:

• establishing at least one binary decision tree for the data values, said binary decision tree having a plurality of leaf nodes and at least one non-leaf node arranged in a binary rooted tree, each leaf node represented by pairs of threshold error values, each member of each pair of threshold error values representing a leaf node in the binary decision tree and a threshold of a range of data values and each said at least one non-leaf node representing a binary decision required to arrive at the appropriate leaf node;
• identifying a range of error values that the data value is within;
• quantizing the data value, wherein the step of quantizing the data value includes the step of generating a binary code according to the range of error values the data value is within and a path address of the node corresponding to the range threshold;
• entropy coding said binary code, such that the stream of data values are output as a compressed bit stream after outputting a binary code for a predetermined number of data values,
• comparing a number of bits utilized to output the compressed bit stream representing data values to the predetermined compression ratio;
• if the number of bits utilized is greater than the number of bits dictated by the predetermined compression ratio, increasing the ranges of error values in size by increasing the values of the threshold values, such that ranges represented by nodes closer to a root node in the binary rooted tree, and therefore identified by a binary code having a lessor number of bits, are increased in size to encompass a wider range of data values, thereby decreasing the compression ratio;
• and
• if the number of bits utilized is less than the number of bits dictated by the predetermined compression ratio, decreasing the ranges of error values in size by decreasing the values of the threshold values, such that ranges represented by nodes closer to the root node are decreased in size to encompass a narrower range of data values, thereby increasing the compression ratio;
• such that ranges of error values are adapted to maintain the compressed data stream in the proximity of the predetermined compression ratio.

An apparatus for compressing a stream of data values at a predetermined compression ratio comprising:

• at least one binary decision tree for encoding the data error values, said binary decision tree comprising a root node and a plurality of binary nodes represented by pairs of threshold values, each member of each pair of threshold values representing a node in the binary decision tree and a threshold of a range of data error values;
• a first look-up table for storing threshold values for different quantization granularities, each of said threshold values representing a threshold of a range of values and organized in groups according to the quantization granularity, said range of values identified by a class code identifying a binary path from the root node to the node corresponding to the threshold value.
• selection means for selecting a first quantization granularity to index the first look-up table;
• comparison means for identifying a range of values in the selected quantization granularity within which the input data value lies, said comparison means comparing the data value to the threshold values of the group selected according to the first quantization granularity from the first lookup table;
• generation means for generating a binary code, said binary code comprising at least one bit and determined according to the range the data value is within and the path address of the node corresponding to the range;
• output means for outputting a compressed data stream wherein said compressed stream includes data representing the binary code subjected to entropy encoding;
• counting means for counting a number of bits output as part of the compressed data stream;
• comparison means for comparing the number of bits utilized to output the compressed data stream to the predetermined compression ratio;
• quantization granularity control means for updating the quantization granularity of the group of threshold values,
• if the number of bits utilized is greater than the predetermined compression ratio, said control means controls said selections means to select a second quantization granularity that is coarser than the first quantization granularity, such that groups encompassing error values having a greater frequency of occurrence having a class code employing a lessor number of bits are increased in size to encompass a wider range of error values thereby decreasing the compression ratio;
• and
• if the number of bits utilized is less than the predetermined compression ratio, said control means controls said selections means to select a second quantization granularity that is finer than the first quantization granularity such that groups encompassing error values having a greater frequency of occurrence having a class code employing a lessor number of bits are decreased in size to encompass a narrower range of error values thereby increasing the compression ratio, such that error ranges are adapted to maintain the compressed data stream in the proximity of the predetermined compression ratio.

A method for decompressing a stream of bits representative of data values at a predetermined decompression ratio, wherein the data values include encoded class codes used to quantize the original data values, said method comprising the steps of:

• establishing a first binary decision tree for decoding the data error values, said binary decision tree comprising a root node and a plurality of binary nodes represented by pairs of symmetric threshold values, symmetric around the root node, each member of each pair of symmetric threshold values representing a node in the binary decision tree and a threshold of a range of data values, each node identified by a class code comprising bits representing a path address from the root node to the node;
• decoding a stream of bits to determine the node corresponding to the error value range the data value is within;
• reconstructing the data value from the error value range corresponding to the decoded node;
• after decompressing a predetermined number of data values,
• comparing a number of input bits in the stream of bits utilized to represent the compressed data to the predetermined compression ratio;
• if the number of bits utilized is greater than the number of bits dictated by the predetermined compression ratio, increasing the error value ranges in size by increasing the value of the symmetric threshold values to produce a second binary decision tree for decoding data error values such that error value ranges represented by nodes closer to the root node and identified by a binary code having a lessor number of bits, are increased in size to encompass a wider range of data error values thereby decreasing the compression ratio;
• and
• if the number of bits utilized is less than the number of bits dictated by the predetermined compression ratio, decreasing the error value ranges in size by decreasing the value of the symmetric threshold values to produce a second binary decision tree for decoding data error values such that error value ranges represented by nodes closer to the root node and identified by a binary code having a lessor number of bits, are decreased in size to encompass a narrower range of data error values thereby increasing the compression ratio;
• such that the error ranges change to maintain the compressed data stream in the proximity of the predetermined compression ratio and accurately reconstruct the data values.

An apparatus for decompressing a stream of bits representative of data values, wherein said data values include encoded class codes used in quantizing original data values said data values compressed at a predetermined compression ratio, said apparatus comprising:

• a first look-up table for storing error values for different quantization granularities, each of said error values representing a threshold of a range of data error values and organized in groups according to the quantization granularity, each said range of error values identified by a class code;
• selection means for selecting a first quantization granularity to index the first look-up table and retrieve a group of error values;
• means for generating a predicted data value for the data value to be quantized;
• a decoder for decoding a portion of the stream of bits to produce a class code corresponding to the data value to be reconstructed;
• means for determining a representative error value for the class code decoded at the selected quantization granularity from group of values retrieved from the look up table;
• reconstruction means for reconstructing the data value from the predicted data value and representative error value;
• counting means for counting the number of bits of the input bit stream utilized to encode class codes;
• comparison means for comparing the number of bits utilized to the predetermined compression ratio;
• quantization granularity control means for updating the quantization granularity of the group of threshold values,
• if the number of bits utilized is greater than the predetermined compression ratio, said control means controls said selections means to select a second quantization granularity that is coarser than the first quantization granularity such that the classes encompassing error values having a greater frequency of occurrence having a class code employing a lessor number of bits are increased in size to encompass a wider range of error values thereby decreasing the compression ratio;
• and
• if the number of bits utilized is less than the predetermined compression ratio, said control means controls said selections means to select a second quantization granularity that is finer than the first quantization granularity such that the classes encompassing error values having a greater frequency of occurrence having a class code employing a lessor number of bits are decreased in size to encompass a narrower range of error values thereby increasing the compression ratio;
• such that error value ranges are adapted by selecting another quantization granularity to maintain the compressed data stream in the proximity of the predetermined compression ratio and accurately reconstruct the data values.