Compression - Choose the best Rice index

Author

Choose the best Rice index

danilobrambilla@tiscali.it

2008-02-06, 6:57 pm

Hi all,

I am coding on Rice compression algorithm to compress data chunks
whose length is between 8 to 32 bytes (8 - 16 - 24 or 32). For each
chunk I want to choose the best index n to achive the best
compression, and I think i'll try all of them from 0 to 7. Data
distribution is geometric, so Rice will be fine, but I'd like to avoid
Rice calculation for each of the 0 to 7 indexes, so I am assuming
that:

.. if I start coding a chunk with Rice index 0 to 7, I'll be able to
find that coded chunk will perhaps decrease in length and then grow
up, so reached the index where the lenght starts growing, will be
unuserful to go on till Index 7.

For example, I'll start to code a chunk using index 0. Then I try on
the same chunk the index 1 and got a better compression. Then using
index 2, suppose the compression is worst. So, it is correct if I
suppose then going on with indexes 3, 4 ecc. I'll got always worst
results, so my best index will be 1?

Thank you and best regards,

LiloLilo

Thomas Richter

2008-02-09, 6:56 pm

danilobrambilla@tiscali.it wrote:

> I am coding on Rice compression algorithm to compress data chunks
> whose length is between 8 to 32 bytes (8 - 16 - 24 or 32). For each
> chunk I want to choose the best index n to achive the best
> compression, and I think i'll try all of them from 0 to 7. Data
> distribution is geometric, so Rice will be fine, but I'd like to avoid
> Rice calculation for each of the 0 to 7 indexes, so I am assuming
> that:
>
> . if I start coding a chunk with Rice index 0 to 7, I'll be able to
> find that coded chunk will perhaps decrease in length and then grow
> up, so reached the index where the lenght starts growing, will be
> unuserful to go on till Index 7.
>
> For example, I'll start to code a chunk using index 0. Then I try on
> the same chunk the index 1 and got a better compression. Then using
> index 2, suppose the compression is worst. So, it is correct if I
> suppose then going on with indexes 3, 4 ecc. I'll got always worst
> results, so my best index will be 1?

If my memory suits me well, this is indeed the case. But there was an
even easier algorithm to compute the rice index "adaptively" from the
statistics of the data; I don't remember it off-hands, but IIRC, you
can find it in Weinberger's paper on JPEG-LS, and in Marcellin and
Taubman's book.

So long,
Thomas

LiloLilo

2008-02-09, 6:56 pm

But there was an
> even easier algorithm to compute the rice index "adaptively" from the
> statistics of the data; I don't remember it off-hands, but IIRC, you
> can find it in Weinberger's paper on JPEG-LS, and in Marcellin and
> Taubman's book.

Yes I know, as I read about JPEG-LS. But as already asked in this newsgroup
some time ago, it may be possible it is copiright protected.

Thank you for help

Thomas Richter

2008-02-09, 6:56 pm

LiloLilo wrote:
> But there was an
>
> Yes I know, as I read about JPEG-LS. But as already asked in this newsgroup
> some time ago, it may be possible it is copiright protected.

Algorithms cannot be copyright protected. Specific implementations can.
Why do you want to copy the JPEG-LS source code?

Greetings,
Thomas

LiloLilo

2008-02-10, 6:56 pm

> Algorithms cannot be copyright protected. Specific implementations can.
> Why do you want to copy the JPEG-LS source code?

I don't want to copy JPEG-LS. Just studied the algorithm to find out how it
works.
I need to apply Rice encoding, so I need a way to choose the best index. I
was supposed to try all of the possible ones for choose the best.
In JPEG-LS the index is chosen by this well known way:

for ( k = 0; (N << k) < A; k ++);

where k in the index, N is the number of items, and A is they're sum. Just
suppose this way may be copirigth protected, so looking for another way like
exaustive search.

Thank you for help.

Thomas Richter

2008-02-10, 6:56 pm

LiloLilo wrote:
>
> I don't want to copy JPEG-LS. Just studied the algorithm to find out how it
> works.

Then, where is the problem?

> I need to apply Rice encoding, so I need a way to choose the best index. I
> was supposed to try all of the possible ones for choose the best.
> In JPEG-LS the index is chosen by this well known way:
>
> for ( k = 0; (N << k) < A; k ++);
>
> where k in the index, N is the number of items, and A is they're sum. Just
> suppose this way may be copirigth protected, so looking for another way like
> exaustive search.

Again, you don't understand the law. You *cannot* copyright-protect an
algorithm. You can protect an implementation. Copyright is not for
ideas. Patents are. Even if the above "for loop" is patented, the
mathematics behind cannot be patented. Go into the Weinberger paper,
you'll find that the above loop is a simplification of a more precise
formula. Go implement this formula then. Check the JPEG-LS standard. Any
patents that apply to it must be declared there.

Again: Copyright != Patent.

So long,
Thomas

danilobrambilla@tiscali.it

2008-02-11, 3:56 am

> Again, you don't understand the law. You *cannot* copyright-protect an
> algorithm. You can protect an implementation. Copyright is not for
> ideas. Patents are. Even if the above "for loop" is patented, the
> mathematics behind cannot be patented. Go into the Weinberger paper,
> you'll find that the above loop is a simplification of a more precise
> formula. Go implement this formula then. Check the JPEG-LS standard. Any
> patents that apply to it must be declared there.
>
> Again: Copyright !=3D Patent.
>
> So long,
> =A0 =A0 =A0 =A0 Thomas

Thank you I got the difference now. This is just first time I have to
code for commercial, so beeing aware of patent and so on...

Have a nice day

Sponsored Links