[CELT-dev] Octagon Coding

[Benjamin M. Schwartz]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dear Celts,

I've become intrigued by the problem of spherical quantizers, so I decided
to see if I could come up with something better than PVQ.  What I wound up
writing is something I call an "octagon quantizer.  In two dimensions, PVQ
uses a "diamond" (square) shape.  An octagon code (OVQ) uses an octagon,
which is a much better approximation to the circle.  In two dimensions,
PVQ uses an octahedron, and OVQ uses a rhombicuboctahedron, which is
(again) a much better approximation to the sphere.

In OVQ, the resolution parameter K is replaced by two (int) parameters A
and B.  Quantization then proceeds very simply: all components greater
than B are subjected to PVQ (after subtracting B) with resolution A, and
all components less than B are scalar-quantized.  Thus, setting B=0 gives
PVQ, and setting A=0 gives scalar quantization.  In L dimensions, for
large L, the best approximation to a sphere should happen at a ratio of
A/B = sqrt(L).  I believe that OVQ is asymptotically better than PVQ, but
a fair comparison is tricky because for B>0, they require different
numbers of bits to encode.

If you have seen this quantizer before, let me know.  I don't imagine that
it's a new idea.

In an attempt to make a fair comparison, I wrote a few test functions to
determine the optimal A and B for a given number of dimensions and a given
number of bits, minimizing the maximum possible error, for which I have a
good analytic approximation.  For example, with L=100, and 326 bits
maximum, the largest possible PVQ (and therefore the best) is K=178.  The
best possible OVQ has A=50, B=2.  (B=5 would be the optimal ratio, but is
impossible without more bits.  Scalar quantization isn't cheap.)  I then
ran Monte Carlo tests (50000 samples) to observe the difference in RMS
quantization error.  For PVQ, the RMS error was 0.12858.  For Octagon, it
was 0.12377, better by about 3.8%.

This result is good, but also a bit disappointing to me.  OVQ does much
better in terms of the observed maximum error (8%) or the theoretical
maximum error (11%), but these are probably not such valuable measures.
Also, this case (L=100, N<=2^326) is particularly favorable for OVQ, which
is most advantageous in many dimensions with near-continuum sampling.  I
was particularly disappointed to see no measurable benefit in terms of RMS
error for N=3, though the maximum error is improved significantly.

Anyway, I welcome any feedback or advice on the matter.  I have written up
a complete implementation of quantization, encode, and decode for both PVQ
and OVQ in Python.  Algorithmically, OVQ comes with very little overhead
above PVQ; in fact, because A and B tend to be much less than K (e.g. 50
vs. 178), OVQ might actually be faster.

- --Ben
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.9 (GNU/Linux)

iEYEARECAAYFAknBZ9kACgkQUJT6e6HFtqRMXACgl+yGOyx3ppP4uDBoYoTHthmf
jxAAoIOeipXgwqdnocafcjUVCNBBu0pn
=s7wc
-----END PGP SIGNATURE-----