Subject: Re: K-ary arithmetic coding

From: [email-masked] (Scott Firestone)
Date: 22 Feb 91 16:14:55 GMT

In article <[email-masked]> [email-masked] (Viet Anh) writes:
>
>IBM's "Q-coder" --- an arithmetic code for a binary source --- has
>received a lot of attention lately.  I'd like to point out that there
>exist arithmetic codes for K-ary sources, and that these may be more
>efficient and/or more convenient in a given application.

There is as much confusion about the Q-coder as there is interest.  The
Q-coder can be used to compress any type of image, whether it is binary or
not.  The only stipulation is that the image must have a highly skewed
histogram, so that each symbol can be efficiently encoded through a series
of binary decisions.  The lossless JPEG algorithm calls for DPCM followed
by a Q-coder.  The output of a DPCM filter is an "image" that is highly
skewed - the histogram is concentrated around 0 and falls off rapidly for
higher difference values.  Also, the JPEG lossy algorithm calls for a DCT
followed by DPCM/Q-coder on the DC coefficient, and a Q-coder on each of
the AC coefficients, which have a histogram already skewed around zero.
(Actually, the binary arithmetic coder in the JPEG specs is strictly not a
Q-coder, but it's close enough to be called one.)

In fact, for image data with skewed histogram, the Q-coder will in general
outperform any other type of lossless entropy coding, even an optimal K-ary
arithmetic coder.  This is because a typical K-ary arithmetic coder can
only get down to theoretical entropy.  However a Q-coder can get below
theoretical entropy by predicting the interval widths before coding the
next symbol.  In the lossless JPEG specs, the Q-coder uses the surrounding
DPCM pixel values and the previous history of the image to predict the next
pixel value.  I have seen a DPCM/Q-coder get down to 95% of entropy for a
really noisy image (the flower garden) and 30% of entropy for a smoothly
varying image (computer graphics stuff).

There is a paper in one of the IEEE proceedings written by Rabani.  I
believe it is called "survey of lossless conpression schemes."  In the
paper Rabani concludes that in general the Q-coder outperforms any other
type of lossless compression.

After the MPEG specs were finallized, someone discovered that replacing the
MPEG huffman coder with a Q-coder improved performance of the MPEG
algorithm.  I do not know if anyone has proposed the Q-coder modification
of the MPEG specs.

Oh, and yes - the Q-coder is still the best thing around for fax and binary
image compression.

Sco[ttt ... ttt)      [email-masked]