US 6,477,280 B1 · Lossless adaptive encoding of finite alphabet data

Abstract

An encoder reorders quantized wavelet coefficients to cluster large and small wavelet coefficients into separate groups without requiring the use of data-dependent data structures. The coefficients are then adaptively encoded based on a run-length code which continuously modifies a parameter that controls the codewords uses to represent strings of quantized coefficients, seeking to minimize the number of bits spent in the codewords. A matrix of indices contains the coarsest coefficients in the upper left corner, and filling in low high and high low sub bands in larger and larger blocks in an alternating manner, such that low high sub bands comprise the top of the matrix and the high low sub bands comprise the left side of the matrix. The shortest codewords are assigned to represent a run of the most likely character having length of 2k, where k is a parameter. k is adjusted based on successive characters being encountered. k is increased when the character is the same, and decreased when the character is different. A decoder applies the above in reverse order. Decoding of the encoded coefficients is first performed, followed by an unshuffling of the coefficients. The unshuffled coefficients are then subjected to an inverse wavelet transform to recover the transformed and compressed data, such as image pixels.

Claims39

Dependent claims

A method of encoding finite alphabet data characters, the method comprising:

initializing a string length for an adaptive run-length encoder;
modifying the string length based on a modified encoding parameter produced by,
applying a scaling factor to a current encoding parameter,
adjusting the value of the scaled encoding parameter based on already encoded characters, and
applying an inverse scaling factor to the adjusted and scaled encoding parameter to produce the modified encoding parameter.

2 more elements

A process for encoding finite alphabet data characters, which are characterized by a sequence of binary values, comprising using a computing device to perform the following process actions:

for each binary value in sequence:
determining if the value is a first or second binary value;
whenever the value is the first binary value, taking no action unless the number of preceding pixels locations for which no action has been taken equals a current string length, and if it does, establishing a first type of codeword by representing the number of preceding values for which no action has been taken with a single first encoding value;
whenever the value is the second binary value, establishing a second type of codeword by representing the value under consideration and the number of preceding values for which no action has been taken with a second encoding value and a binary word indicating the number of preceding values for which no action has been taken;
and
whenever a codeword is established, modifying the current string length to establish a new current string length based on a modified encoding parameter, said modified encoding parameter being produced by,
applying a scaling factor to a current encoding parameter,
adjusting the value of the scaled encoding parameter based on already encoded values, and
applying an inverse scaling factor to the adjusted and scaled encoding parameter to produce the modified decoding parameter and.

6 more elements

A process for decoding finite alphabet data characters, which are characterized by a sequence of binary values, and which are encoded by a process that reduces the sequence of binary values to a series of codewords from which can be derived whether each value in the sequence exhibits the first binary value or the second binary value, said codewords coming in two types a first of which is a first codeword value representing a number of binary values in a string of values that have the first binary value and the second of which comprises a second codeword value followed by a binary word that indicates the number of binary values preceding a value having the second binary value that exhibit the first binary value, said process comprising using a computing device to perform the following process actions:

(a) receiving the series of codewords;
(b) establishing a current string length that is identical to the initial length used in encoding the sequence of binary values, wherein the string length represents a number of consecutive binary values having the first binary value;
(c) determining if the last-received codeword is of the first or second type;
(d) whenever the last-received codeword is of the second type, generating a number of values exhibiting the first binary value as indicated by the binary word component of the codeword and then generating an additional value exhibiting the second binary value;
and
(e) whenever the last-received codeword is of the first type, generating a number of values exhibiting the first binary value equal to the current string length;
(f) modifying the current string length to establish a new current string length based on a modified decoding parameter, said modified decoding parameter being produced by,
applying a scaling factor to a current decoding parameter, which is initially the same as that used as the initial encoding parameter during encoding,
adjusting the value of the scaled decoding parameter based on already decoded values, and
applying an inverse scaling factor to the adjusted and scaled decoding parameter to produce the modified decoding parameter;
and
(g) repeating actions (c) through (f) using the new current string length.

9 more elements

Dependencies are inferred from the claim text.

Lossless adaptive encoding of finite alphabet data

Life of this patent

Lossless adaptive encoding of finite alphabet data

Life of this patent

Abstract

Claims39