Compression - Golomb parameter k

Author

Golomb parameter k

George Wilson

2005-05-16, 3:55 pm

Question:
1. "Is there any other way of computing the best value of Golomb
parameter other than computing Golomb parameter using mean value of
samples or as in JPEG LS"

Considering the data which follows a Geometric Distribution, with the
interest in coding the data using Golomb code,"How may be the Golomb
parameter k computed ?", other than the method using JPEG LS (
for(k=0;(N[Q]<<k)<A[Q];k++); )or mean values of previous samples.

n - is generated by mapping the negative values to positive
q(quotient) = floor(n/m), m = 2^k.
r (remainder)
n = m * q + r;
+------------------+-------------------------+
Golomb Code = |(q)unary quotient | (r) Remainder in k bits |
+------------------+-------------------------+

Literature on the web say
K = log(max(0,1+floor(log2(log(PI - 1) / log(Mu/Mu+1))));
K - Optimized Golomb parameter
Mu - Mean of few previous samples
PI - (sqrt(5) + 1)/2; PI is called Golden constant.

Excluding the method of computation of Golomb parameter in JPEG LS and
the above method which uses mean and more floating point operation "Is
there any other way of computing the best value of Golomb parameter"

Question:
1. "Is there any other way of computing the best value of Golomb
parameter other than computing Golomb parameter using mean value of
samples or as in JPEG LS"

Comments and discussions are appreciated.

George Wilson.

Thomas Richter

2005-05-17, 8:55 am

Hi,

> 1. "Is there any other way of computing the best value of Golomb
> parameter other than computing Golomb parameter using mean value of
> samples or as in JPEG LS"

Yes, definitely. The algorithm used in JPEG-LS is constructed upon
an estimation, and on the requirement of a low-complexity codec.
The optimal Golomb parameter should be the result of an optimization,
i.e. given a probability distribution $p$, find a parameter $k$ such
that the resulting code length is minimal. Unfortunately, this
problem will most likely not allow an exact analytic solution. Thus,
several approximations are performed by Weinberger et al. to keep
the code simple. Luckely, purely Laplacian distributions are
characterized by a single parameter, so several ways of measuring
this parameter are possible.

A second problem of the approach is of course that modeling the output
data of the LOCO predictor by i.i.d. data of Laplacian distribution is
not very accurate. The next more realistic model would be that of
i.i.d. data with generalized Gaussian distribution, but this again
makes the analysis of the problem even harder (forcing you to handle
incomplete gamma functions).

> Considering the data which follows a Geometric Distribution, with the
> interest in coding the data using Golomb code,"How may be the Golomb
> parameter k computed ?", other than the method using JPEG LS (
> for(k=0;(N[Q]<<k)<A[Q];k++); )or mean values of previous samples.

Questions from my side: Do you want to stay within the limits set
by JPEG-LS? Thus, are only Golomb codes allowed with a Golomb
parameter which is a power of two? If not, then the Weinberger
choice is of course not optimal.

> Literature on the web say
> K = log(max(0,1+floor(log2(log(PI - 1) / log(Mu/Mu+1))));
> K - Optimized Golomb parameter
> Mu - Mean of few previous samples
> PI - (sqrt(5) + 1)/2; PI is called Golden constant.

Ehem, *cough*. The mean should be zero, unless you're only encoding
absolute values of the data. You're most likely meaning the parameters
S_t and N_t as in the Weinberger paper[1] you've surely read
already. Here N_t is the sum of negative samples, S_t + N_t the
sum of absolute values.

> Excluding the method of computation of Golomb parameter in JPEG LS and
> the above method which uses mean and more floating point operation "Is
> there any other way of computing the best value of Golomb parameter"

Note that the above formula (unlike what's done in JPEG-LS) allows
arbitrary Golomb parameters, not just powers of two. So yes, the formula
is different, though the codec is different (it is a larger
family).

> Question:
> 1. "Is there any other way of computing the best value of Golomb
> parameter other than computing Golomb parameter using mean value of
> samples or as in JPEG LS"

As said, Laplacian distributions are rather simple; one parameter is
enough to describe them. The sum of absolute values of encoded samples
is *one* way to characterize them, I could think of many others, e.g.
the median value (= find a value M such that the number of encoded
samples above M is equal to the number of encoded samples below M).
A simple calculation will give a formula that relates M to the parameter
of the geometric distribution, and again to the sum of absolute values.
However, from a mathematical point this will not give a new result,
just an equivalent formulation by means of other variables.

Thus, my question would rather be: Are you interested in a mathematical
analysis of the problem, or in engineering a strategy for JPEG-LS
encoding that is presumably better/faster than that described in the
standard. In the former case, you will surely find answers, though
complicated ones. In the latter case, I've the feeling that the
JPEG-LS algorithm is already pretty optimal; you might improve codecs
by means of lookup-tables or other software-engineering approaches,
but that's all I would expect.

So long,
Thomas

[1]: M.J. Weinberger, G.Seroussi, G. Sapiro: The LOCO-I
Lossless Image Compression Algorithm: Principles and
Standardization into JPEG-LS, IEEE Transactions on Image Processing,
Vol.0, No.8, August 2000.

You most likely know this paper already. What might be interesting
would be to follow the cited papers used to establish the result
of Thm.1 in this paper,[33],[38] and [39]. Sorry, I haven't.

George Wilson

2005-05-24, 8:55 am

Hi, I was interested in an engineering strategy for coding the data in
Golomb code faster and better than JPEG LS

Thanks Thomas

George Wilson

Thomas Richter

2005-05-24, 8:55 am

Hi,

> Hi, I was interested in an engineering strategy for coding the data in
> Golomb code faster and better than JPEG LS

Within the limits of JPEG-LS or outside? In the latter case, it seems
unlikely you'd be able to find a method that works much faster except
by preparing a lookup table. A better performing version might be
possible, though (i.e. higher compression ratio) by using the sharper
limits provided by "Theorem I". I haven't tried this, but I would
believe that the performance impact is not very remarkable.

In the long run, however, I'd suggest to look into binary arithmetic
coders like the MQ or QM code, or the ELS coder. All compress better
than the simple Golomb codes, and are not much slower if implemented
cleverly.

So long,
Thomas

jdallen2000@yahoo.com

2005-05-31, 3:56 am

George Wilson wrote:
> Question:
> 1. "Is there any other way of computing the best value of Golomb
> parameter ...
> +------------------+-------------------------+
> Golomb Code = |(q)unary quotient | (r) Remainder in k bits |
> +------------------+-------------------------+
>

Good compression implies uniform random distribution in the
compressor's output. Adjust the Golomb parameter dynamically
to achieve. Thus if 1's outnumber 0's in the unary quotients,
the parameter is set too low and should be adjusted up
(or down if 0's outnumber 1's.

You will need a "velocity" parameter to control how often you
update the Golomb parameter. How to optimize that velocity
parameter? Again, the "good compression implies uniformity"
maxim comes to the rescue! If {11,00} outnumber {01,10} in
the unary codes, velocity may be too high or vice versa.

With these approaches, dynamic Golomb codes achieve almost exactly
the same net compression ratio as IBM's QM coder!

(Disclaimer: You may need a License from the Patent-Holder for
commercial use of a dynamic Golomb Coder in Noreth America.)

James D. Allen
(e-mail jamesdowallen at gmail)

Sponsored Links