Path: utzoo!utgpu!cs.utexas.edu!mailrus!uflorida!mlb.semi.harris.com!thrush.mlb.semi.harris.com!del From: del@thrush.mlb.semi.harris.com (Don Lewis) Newsgroups: alt.sources.d Subject: Re: Compressing pictures (LONG) Message-ID: <1990Aug31.034936.18954@mlb.semi.harris.com> Date: 31 Aug 90 03:49:36 GMT References: <1990Aug29.155925.17597@zorch.SF-Bay.ORG> <6873@milton.u.washington.edu> Sender: news@mlb.semi.harris.com Organization: Harris Semiconductor, Melbourne FL Lines: 37 In article <6873@milton.u.washington.edu> wiml@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@mlb.semi.harris.com PO Box 883 MS 62A-028 Phone: (407) 729-5205 Melbourne, FL 32901