Zero-search, zero-memory vector quantization
First Claim
1. A computer-implemented method for data compression comprising the steps of:
- via a computational device, receiving at least one signal in any of digitized and non-digitized form, said received at least one signal representing at least one data object to be compressed;
responsive to receiving said signal in non-digitized form, via a computational device, digitizing said at least one received signal;
via a computational device, extracting at least one information element from said at least one digitized signal;
via a computational device, establishing an implicit codebook comprising a set of code points for representing said at least one information element extracted from said at least one digitized signal, each of said at least one information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector;
via a computational device, inspecting the signs of each information element to determine in which orthant said each information element lies to determine the implicit code point to represent said each information element;
via a computational device, determining an index of the implicit code point associated with said each information element; and
via a computational device, transmitting or storing said each resulting index as the compressed representation of said each information element.
1 Assignment
0 Petitions
Accused Products
Abstract
The invention comprises a method for lossy data compression, akin to vector quantization, in which there is no explicit codebook and no search, i.e. the codebook memory and associated search computation are eliminated. Some memory and computation are still required, but these are dramatically reduced, compared to systems that do not exploit this method. For this reason, both the memory and computation requirements of the method are exponentially smaller than comparable methods that do not exploit the invention. Because there is no explicit codebook to be stored or searched, no such codebook need be generated either. This makes the method well suited to adaptive coding schemes, where the compression system adapts to the statistics of the data presented for processing: both the complexity of the algorithm executed for adaptation, and the amount of data transmitted to synchronize the sender and receiver, are exponentially smaller than comparable existing methods.
-
Citations
36 Claims
-
1. A computer-implemented method for data compression comprising the steps of:
-
via a computational device, receiving at least one signal in any of digitized and non-digitized form, said received at least one signal representing at least one data object to be compressed; responsive to receiving said signal in non-digitized form, via a computational device, digitizing said at least one received signal; via a computational device, extracting at least one information element from said at least one digitized signal; via a computational device, establishing an implicit codebook comprising a set of code points for representing said at least one information element extracted from said at least one digitized signal, each of said at least one information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector; via a computational device, inspecting the signs of each information element to determine in which orthant said each information element lies to determine the implicit code point to represent said each information element; via a computational device, determining an index of the implicit code point associated with said each information element; and via a computational device, transmitting or storing said each resulting index as the compressed representation of said each information element. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. A computer-implemented method for data compression and subsequent decompression comprising the steps of:
-
via a computational device, receiving at least one signal representing at least one data object in any of digitized and non-digitized form; responsive to receiving said at least one signal in non-digitized form, via a computational device, digitizing said at least one received signal; via a computational device, extracting at least one information element from said digitized signal; via a computational device, establishing an implicit codebook comprising a set of code points for representing at least one information element extracted from said digitized signal, each of said at least one information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector; via a computational device, inspecting the signs of each information element to determine in which orthant said each information element lies to determine the implicit code point to represent said each information element; via a computational device, determining an index of the implicit code point associated with said each information element; via a computational device, transmitting or storing each resulting index as the compressed representation of each said information element; and via a computational device, applying a decompression function to said compressed information elements to produce at least a partial facsimile of said at least one information element.
-
-
28. A computer-implemented method for finding a family A of K hypercube codebooks, comprising the steps of:
-
via a computational device, receiving at least one signal representing at least one data object in any of digitized and non-digitized form; responsive to said at least one signal being received in non-digitized form, via a computational device, digitizing said at least one received signal; via a computational device, extracting an example dataset U from said digitized signal; beginning with a fixed number K of desired hypercubes, and said example dataset U; via a computational device, mapping each element uε
U, where u=u1, . . . , uD, to the positiveorthant PD, via the map p;
u1, . . . , uD→
|u1|, |u2|, . . . , |uD|, yielding the set
U+={p(u)|uε
U};
via a computational device, selecting an initial set of K radius vectors A(0)={ α 0(0), . . . ,α K-1(0)};via a computational device, setting an iteration count i to 0; via a computational device, establishing a termination condition τ
, which depends upon one or more of;the number of iterations executed; the closeness of match between a current radius vector collection A(i) and U+; and the improvement of a statistic over a previous iteration, wherein said dependence is expressed as τ
(i, A(i),U+);via a computational device, testing τ
(i,A(i),U+); andif the termination condition is satisfied, via a computational device, outputting A(i) as the desired radius vector collection; and via a computational device, stopping; else, if the termination condition is not satisfied, via a computational device, computing a new radius vector collection A(i+1) as follows; via a computational device, partitioning U+ into K sets S0 . . . SK-1, where
-
-
29. A computer-implemented method for data compression, comprising the steps of:
-
via a computational device, receiving at least one signal representing at least one data object in any of digitized and non-digitized form; responsive to said at least one signal being received in non-digitized form, via a computational device, digitizing said at least one received signal; via a computational device, extracting at least one information element from said digitized signal; via a computational device, computing a compression function for said at least one information element extracted from said digitized signal by; via a computational device, first applying a symmetrizing transform; via a computational device, inspecting the signs of said transformed information elements to determine in which quadrant of an implicit codebook a corresponding implicit code point lies; via a computational device, determining an index of an associated implicit code point for each said information element; and via a computational device, transmitting or storing each said resulting index as the compressed representation of each said information element. - View Dependent Claims (30, 31, 32, 33, 34)
-
-
35. A computer-implemented method for data compression comprising the steps of:
-
via a computational device, receiving at least one signal representing at least one spoken utterance in any of non-digitized and digitized form; responsive to receiving said at least one signal in non-digitized form, via a computational device, digitizing said at least one received signal; via a computational device, extracting at least one information element from said digitized signal; via a computational device, establishing an implicit codebook comprising a set of code points for representing said at least one information element extracted from said digitized signal, each of said at least one information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector; via a computational device, inspecting the signs of each information element to determine in which orthant said each information element lies to determine the implicit code point to represent said each information element; via a computational device, determining an index of the implicit code point associated with said each information element; and via a computational device transmitting or storing said each resulting index as the compressed representation of said each information element.
-
-
36. A computer-implemented method for data compression comprising the steps of:
-
via a computational device, receiving at least one signal representing at least one image in any of digitized and non-digitized form; responsive to receiving said signal in non-digitized form, via a computational device, digitizing said at least one received signal; via a computational device, extracting at least one information element from said digitized signal; via a computational device, establishing an implicit codebook comprising a set of code points for representing said at least one information element extracted from said digitized signal, each of said at least one information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector; via a computational device, inspecting the signs of each information element to determine in which orthant said each information element lies to determine the implicit code point to represent said each information element; via a computational device, determining an index of the implicit code point associated with said each information element; and via a computational device, transmitting or storing said each resulting index as the compressed representation of said each information element.
-
Specification