ZERO-SEARCH, ZERO-MEMORY VECTOR QUANTIZATION
First Claim
1. A computer-implemented method for data compression comprising the steps of:
- establishing an implicit codebook comprising a set of code points for representing information elements, each information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector;
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;
determining an index of the implicit code point associated with said each information element; and
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.
41 Citations
33 Claims
-
1. A computer-implemented method for data compression comprising the steps of:
-
establishing an implicit codebook comprising a set of code points for representing information elements, each information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector; 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; determining an index of the implicit code point associated with said each information element; and 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. A computer-implemented method for data compression and subsequent decompression comprising the steps of:
-
establishing an implicit codebook comprising a set of code points for representing information elements, each information element constituting a vector, said set of code points implicitly represented by a hypercube radius vector; 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; determining an index of the implicit code point associated with said each information element; transmitting or storing each resulting index as the compressed representation of each said information element; and applying a decompression function to said compressed information elements to produce at least a partial facsimile of said information elements.
-
-
27. A computer-implemented method for finding a family A of K hypercube codebooks, comprising the steps of:
-
beginning with a fixed number K of desired hypercubes, and an example dataset U; mapping each element u ∈
U, where u=u1, . . . , uD, to the positive orthant D, via the map p;
u1, . . . , uD→
u1 |, |u2 |, . . . , uD|, yielding the set U+={p(u)|u ∈
U};selecting an initial set of K radius vectors A(0)={ α 0(0), . . . ,α K-1(0)};setting an iteration count i to 0; 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+);testing τ
(i,A(i), U+); andif the termination condition is satisfied, returning A(i) as the desired radius vector collection; and stopping; else, if the termination condition is not satisfied, computing a new radius vector collection A(i+1) as follows; partitioning U+ into K sets S0 . . . SK-1, where
-
-
28. A computer-implemented method for data compression, comprising the steps of:
computing a compression function for information elements by; first applying a symmetrizing transform; inspecting the signs of said transformed information elements to determine in which quadrant of an implicit codebook a corresponding implicit code point lies; determining an index of an associated implicit code point for each said information element; and transmitting or storing each said resulting index as the compressed representation of each said information element. - View Dependent Claims (29, 30, 31, 32, 33)
Specification