Compressing pictures (LONG)

[Don Lewis]

In article <6873 at milton.u.washington.edu> wiml at milton.u.washington.edu (William Lewis) writes:
>   * Taking differences is probably much, much better than XORing, 
>since the point is to take advantage of the vertical continuity of
>the image. The problem is that it doubles the number of values the
>compressor will have to deal with -- from max->min to min->max, which
>is 2*(max-min) values. The obvious solution is to wrap around, ie, 
>use modulo(max-min) arithmetic, except that this overlays some of the
>least frequently used values (the extremes) on the most frequently used
>ones (small values), making the huffman/arithmatic coder less
>efficient.

I don't think this is a problem.  Think of the differences as signed
twos-complement values.  There should be a nice symmetric peak in
the histogram around zero.  The relatively few difference values
that get aliased in with the common difference values will just
get just as efficiently encoded as the common values.  On the other
hand, since we are encoding the data anyway, we might look at encoding
n+1 bit differences anyway if that happens to be more efficient (due
to the greater skew in distribution).

Another idea that may be help a bit is to take differences across
the rows after taking differences between the scan lines.  This will
better encode the top row as well as horizontal features.

There is one thing that bothers me, though.  The pixel data that
we are trying to compress consists of indices into a color map, correct?
It would seem to me then that the quality of the results would depend
on the arrangement of the entries in the color map.  If adjacent color
map entries map into widely separated colors and colors that are
closely related map into widely separated color map entries, we will
get poor results.  We might need to look at optimally arranging
the color map or taking the differences and compressing in RGB
(or HLS, etc.) space.
--
Don "Truck" Lewis                      Harris Semiconductor
Internet:  del at mlb.semi.harris.com     PO Box 883   MS 62A-028
Phone:     (407) 729-5205              Melbourne, FL  32901