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 an implicitly defined set of vectors, hereafter called code points, which are symmetrically placed with respect to the origin;
said code points implicitly represented by a hypercube radius vector α
=<
α
1,α
2, . . . ,α
D>
, wherein said code points are used for representing information elements;
said information elements constituting data to be compressed, and said information elements also being vectors; and
computing a compression function for said information elements by;
inspecting the signs of said information elements to determine in which orthant said information element lies, thereby determining the implicit code point of the implicit codebook to represent said information element; and
determining an index of the associated implicit code point so selected for said information element; and
compressing said information elements by application of said compression function.
2 Assignments
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
37 Claims
-
1. A computer-implemented method for data compression comprising the steps of:
-
establishing an implicit codebook comprising an implicitly defined set of vectors, hereafter called code points, which are symmetrically placed with respect to the origin;
said code points implicitly represented by a hypercube radius vectorα =<
α
1,α
2, . . . ,α
D>
, wherein said code points are used for representing information elements;
said information elements constituting data to be compressed, and said information elements also being vectors; andcomputing a compression function for said information elements by; inspecting the signs of said information elements to determine in which orthant said information element lies, thereby determining the implicit code point of the implicit codebook to represent said information element; and determining an index of the associated implicit code point so selected for said information element; and compressing said information elements by application of said compression function. - 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, 34)
-
-
25. A computer-implemented method to find a collection A of perfect hypercube codebooks, comprising the steps of:
-
applying an orthant K-means algorithm to find a collection of K perfect hypercube codebooks that yield low average coding distortion for transformed example data; increasing a number of implicit code points by increasing the number of hypercubes; and compressing source data with minimal coding distortion by coding transformed source data using at least one code point selected from said increased number of implicit code points.
-
-
26. A computer-implemented compression method, comprising the steps of:
-
obtaining a vector v for compression, said vector v comprising at least one information element to be compressed; computing u=Tv, where u is denoted by <
u1, u2, . . . , uD>
;forming ζ (u)=<
ζ
(u1), . . . , ζ
(uD)>
;finding k=k=argminj∥
u−
α j⊙
ζ (u)∥
, whereα j is drawn from a set of hypercube radius vectors A={α 1,α 2, . . . ,α K};
whereinα j⊙
ζ (u) is the element of K(α j) that lies in the same orthant as u, and wherein k is the index of a hypercube codebook that has a vertex closest to u;forming the D-bit binary number i as the bitwise concatenation i=m(uD)m(uD−
1) . . . m(u2)m(u1), where the j th bit of i is 0 if uj is zero or positive, and is 1 if it is negative; andtransmitting the pair <
k−
1,i>
, said pair comprising a code representing said at least one information element to be compressed.
-
-
27. A computer-implemented decompression method, comprising the steps of:
-
obtaining the pair <
k−
1,i>
for decompression, said pair comprising a code representing at least one compressed information element;selecting α k=<
α
1k, α
2k, . . . , α
Dk>
from the set of hypercube radius vectors A={α 1,α 2, . . . ,α K};setting where ũ
j is either +α
jk or −
α
jk, depending as whether the jth bit of i is 0 or 1;computing {tilde over (v)}=T−
1ũ
; andreturning {tilde over (v)}., wherein {tilde over (v)}. comprises said at least one compressed information element decompressed.
-
-
28. 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 not satisfied, computing a new radius vector collection A(i+1) as follows; partitioning U+ into K sets S0 . . . SK−
1, wherewhere Sj comprises all the vectors v in U+ that are closer to α j(i) than any other element of A(i);setting α j(i+1), the j th entry of the new radius vector collection A(i+1), to the mean of the vectors in Sj, which is in symbolsincrementing the iteration count i; and returning to said testing step; else, if the termination condition is satisfied, stopping and returning A(i) as the desired family A of K hypercube codebooks that yield low average coding distortion for transformed example data.
-
-
29. A computer-implemented method for data compression, comprising the steps of:
computing a compression function for information elements by; inspecting the signs of said 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 said information element; and compressing at least one information element by applying said compression function to said at least one information element. - View Dependent Claims (30, 31, 32, 33, 35, 36, 37)
Specification