Subject: Re: Rice Algorithm

From: [email-masked] (Tony Robinson)
Date: 08 Aug 1994 07:22:29 GMT

In article <[email-masked]> [email-masked] (Brendt Wohlberg) writes:
> 
> Does anyone have any information/references relating to the Rice
> Algorithm for lossless image compression? 

Yes - it is the simplest Huffmann coding that you can imagine.

The nth code is n bits long, hence has a probabilty of 2^{-n}.  For
simplicity, start with a run of zeros and add a 1 terminator:

code	value
1	0
01	1
001	2
0001	3
00001	4
000001	5

It can easily be extended to cope with any signal variance.   For
example, add another two bits at the bottom end:

code	value
100	0
101	1
110	2
111	3
0100	4
0111	7
00100	8

The optimal number of final bits to be added is:

n = \log_2 \left( \log(2) {\sigma \over \sqrt 2 } \right)
  = \log_2 \left(\log(2) E(|x|)  \right)

I think the proper reference to this work is:

@techreport{Rice91,
	author=		"Robert F. Rice",
	title=		"Some Practical Noiseless Coding Techniques, 
			{Part II, Module PSI14,K+}",
	type=		"JPL Publication",
	number=		"91-3",
	institution=	"Jet Propulsion Laboratories",
	month=		nov,
	year=		1991}

It works suprisingly well.  If you want to test your code out I can
provide a working implementation in:

	svr-ftp.eng.cam.ac.uk:/comp.speech/sources/shorten-1.14.tar.Z

But this is designed to work on N independent data streams (i.e. stereo
audio), not images.

Tony Robinson