Zero-search, zero-memory vector quantization
First Claim
1. A 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 {overscore (α
)}=<
α
1,α
2,K,α
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.
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 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 {overscore (α
)}=<
α
1,α
2,K,α
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. - 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, 31)
-
-
25. A 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.
-
26. A compression method, comprising the steps of:
-
obtaining a vector v for compression;
computing u=Tv, where u is denoted by <
u1,K,uD);
forming {overscore (ζ
)}(u)=<
ζ
(u1), . . . , ζ
(uD)>
;
finding k=argminj∥
u−
{overscore (α
)}j⊙
{overscore (ζ
)}(u)∥
, where {overscore (α
)}jis drawn from a set of hypercube radius vectors A={{overscore (α
)}1, {overscore (α
)}2, . . . , {overscore (α
)}K;
wherein {overscore (α
)}j⊙
{overscore (ζ
)}(u) is the element of k({overscore (α
)}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 ujis zero or positive, and is 1 if it is negative; and
transmitting the pair <
k−
1,i>
.
-
-
27. A decompression method, comprising the steps of:
-
obtaining the pair <
k−
1,i>
for decompression;
selecting {overscore (α
)}k=<
{overscore (α
)}1k, . . . , {overscore (α
)}Dk>
from the set of hypercube radius vectors A={{overscore (α
)}1, {overscore (α
)}2, . . . , {overscore (α
)}K};
setting where is ũ
jeither +α
jkor −
α
jk, depending as whether the j th bit of i is 0 or 1;
computing {tilde over (υ
)}j=T−
1{overscore (u)}; and
returning {tilde over (υ
)}.
-
-
28. A 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=<
1,K,uD>
, to the positive orthant D, via the map p;
<
u1,K,uD>
→
<
u1∥
,∥
u2∥
,K,∥
uD∥
>
, yielding the set u+={p(u)|u∈
u};
selecting an initial set of K radius vectors A(0)={{overscore (α
)}0(0) . . . {overscore (α
)}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+); and
if 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, wherewhere Sj comprises all the vectors v in u+ that are closer to {overscore (α
)}j(i) than any other element of A(i);
setting {overscore (α
)}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.
-
-
29. A 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; and
determining an index of an associated implicit code point for said information element. - View Dependent Claims (30, 32, 33, 34, 35, 36, 37)
Specification