xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (08/29/90)
winans@sirius.mcs.anl.gov (John Winans) writes in news.admin: >Lets not start an a.s.p argument here again/too. We should think of a.s.p >as a challenge. I get it from one hop away over a T1 so it doesn't bother >me all that much. And I know it is read here because I occasionally look >at my nntp report(s) like a good news.admin. So I will keep it. > >HOWEVER: >What a.s.p might be good for is a place to test image compression programs >and stuff like that. The acive users of the group would probably not want >to see it go away and might be willing to work with others to try to reduce >it's load on the net. Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on the net, a month or two back, there was a suggestion that a good way to compress realistic images was to XOR scan lines after the first with their predecessor line, then LZW compress the output. The first idea is good, since scan coherence will give a big information reduction; but the result of the XOR is not the kind of data (strings of repeating bytes) that LZW does well on; it is more "speckley" or "noisy". However, since for coherent scan lines, the XOR result will have few one bits, providing a very skewed distribution of byte bit pattern frequencies, this is exactly the kind of data that arithmetic compression shines at crunching. Anyone who has access to a wrapper for doing archives and a good arithmetic compression algorithm might like to see what could be done with this approach. I'd give it a try, but I rarely remain coherent (I'm severely depressed) long enough to do serious code development, and my own improvements on arithmetic compression have sat working, but ugly and still needing speedups, untouched for months now. Anyway, a thought for the ambitious interested in making himself/herself a name on the net. Note the Followup-to: line if interested in participating in a discussion of this idea. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
dmm0t@hudson.acc.Virginia.EDU (David M. Meyer) (08/29/90)
Compressing a.s.p would be a wonderful idea, except that almost all of the traffic is in .GIF pictures, which are already compressed pretty thoroughly. I'm not sure exactly what the methods used are, but neither PKZIP nor compress actually shrinks .GIF files. -- David M. Meyer | dmm0t@virginia.edu Department of Mechanical & Aerospace Engineering | (804) 924-7926 University of Virginia |
del@thrush.mlb.semi.harris.com (Don Lewis) (08/29/90)
In article <1990Aug28.192024.22435@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >winans@sirius.mcs.anl.gov (John Winans) writes in news.admin: >>HOWEVER: >>What a.s.p might be good for is a place to test image compression programs >>and stuff like that. The acive users of the group would probably not want >>to see it go away and might be willing to work with others to try to reduce >>it's load on the net. > >Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on >the net, a month or two back, there was a suggestion that a good way to >compress realistic images was to XOR scan lines after the first with their >predecessor line, then LZW compress the output. Taking differences between the scan lines instead of doing XOR's might also be interesting. -- Don "Truck" Lewis Harris Semiconductor Internet: del@mlb.semi.harris.com PO Box 883 MS 62A-028 Phone: (407) 729-5205 Melbourne, FL 32901
barry@network.ucsd.edu (Barry Brown) (08/29/90)
In article <1990Aug28.192024.22435@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >winans@sirius.mcs.anl.gov (John Winans) writes in news.admin: >>What a.s.p might be good for is a place to test image compression programs >>and stuff like that. The acive users of the group would probably not want >>to see it go away and might be willing to work with others to try to reduce >>it's load on the net. > >Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on >the net, a month or two back, there was a suggestion that a good way to >compress realistic images was to XOR scan lines after the first with their >predecessor line, then LZW compress the output. Problem: GIF files are already compressed. If you're talking about compressing GIF files, you'll need to figure out a way to compress LZW-compressed files. If, on the other hand, you're talking about compressing the actual image, then you're headed for trouble because that means defining a whole new format. With GIFs already well supported, you (or whoever decides to pursue this) will be in for a lot of opposition. -- Barry E. Brown -- \ Cal-Animage Beta publicity officer bebrown@ucsd.{edu,uucp,bitnet} \ Anime Stuff FTP Server administrator Somewhere in University City.... \ (ftp network.ucsd.edu [128.54.16.3]) "Kaeshite! Kaeshite! Kaeshitekaeshitekaeshite! -- Azusa (Ranma 1/2)
peter@sugar.hackercorp.com (Peter da Silva) (08/29/90)
In article <1990Aug28.192024.22435@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: > Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on > the net, a month or two back, there was a suggestion that a good way to > compress realistic images was to XOR scan lines after the first with their > predecessor line, then LZW compress the output. I believe that XORing alternate scan-lines and run-length-encoding the result would do a better job. I've heard of this algorithm being pretty effective in past discussions. Should one do this with the image bitplane-mapped or pixel-mapped? -- Peter da Silva. `-_-' <peter@sugar.hackercorp.com>.
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (08/29/90)
In article <1990Aug29.000054.28444@murdoch.acc.Virginia.EDU> dmm0t@hudson.acc.Virginia.EDU (David M. Meyer) writes: >Compressing a.s.p would be a wonderful idea, except that almost all >of the traffic is in .GIF pictures, which are already compressed >pretty thoroughly. I'm not sure exactly what the methods used >are, but neither PKZIP nor compress actually shrinks .GIF files. Right. The idea is to come up with a much better way of compressing the raw pixel data, and then incorporate that new compression scheme in "all" the picture handling software. This means the compression scheme must be 1) public domain, 2) reasonably, but not necessarily blindingly fast (it is worth spending _hours_ to compress a file if you can make it 20% the size any other compression scheme can make it, and then save that space on every USENet site and every home computer's storage!), 3) able to decompress very fast (paying a high decompression cost at every site doesn't have the same economic balance that a high compression cost at the site of origin has), 4) available in source code; and 5) widely ported. This is not a short term "fix" that we can band-aid into a.s.p next week; but if a highly effective scheme is found, it will spread itself fast enough; the economic motivation to save disk space is everywhere. Note that it is sufficient that the scheme found compress _realistic_image_ data well; it doesn't have to compress random input at all well, nor does it need to do well on text; image data is a worthwhile target for compression in its own right, and at its present rate of dissemination, will probably rapidly overwhelm in size the sum of all other stored machine readable data. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (08/29/90)
barry@network.ucsd.edu (Barry Brown) writes: > xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >>winans@sirius.mcs.anl.gov (John Winans) writes in news.admin: >>>What a.s.p might be good for is a place to test image compression programs >>>and stuff like that. The acive users of the group would probably not want >>>to see it go away and might be willing to work with others to try to reduce >>>it's load on the net. >> >>Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on >>the net, a month or two back, there was a suggestion that a good way to >>compress realistic images was to XOR scan lines after the first with their >>predecessor line, then LZW compress the output. > >Problem: > >GIF files are already compressed. If you're talking about compressing GIF >files, you'll need to figure out a way to compress LZW-compressed files. Nope, only considering finding a _much_ better way to compress the original format than GIF provides. Test results conveyed to me in private email already have suggested my idea has merit. Wish I could be the one to do it and acquire the fame and glory and a compression scheme with my name on it, but at least I put up the initial suggestion. >If, on the other hand, you're talking about compressing the actual image, >then you're headed for trouble because that means defining a whole new >format. With GIFs already well supported, you (or whoever decides to pursue >this) will be in for a lot of opposition. Find a way to store the same image in 1/5th the space GIF requires, and the opposition will last about as long as a mid-summer snowfall. A little disk space is cheap, but the amount required by picture data squeezes lots of corporate and individual pocketbooks, and will motivate a lot of software retrofits of a new compression scheme. GIF -> MagicFormat and MagicFormat -> GIF converters will cover the rest of the problems, just like the overwhelming number of converters now in use. Defining a "whole new format" for image data seems to happen once a month, and defining a new compression scheme about every three months; I doubt One More Format will slow people down much. [Can you say n(n-1) converters? I knew you could! Where oh where is the one standard image storage format we so desperately need?] Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
eillihca@fizzle.stanford.edu (Achille Hui) (08/29/90)
peter@sugar.hackercorp.com (Peter da Silva) writes: >In article <1990Aug28.192024.22435@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >> Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on >> the net, a month or two back, there was a suggestion that a good way to >> compress realistic images was to XOR scan lines after the first with their >> predecessor line, then LZW compress the output. >I believe that XORing alternate scan-lines and run-length-encoding the result >would do a better job. I've heard of this algorithm being pretty effective >in past discussions. Should one do this with the image bitplane-mapped or >pixel-mapped? >-- >Peter da Silva. `-_-' ><peter@sugar.hackercorp.com>. I have tried several things on several images: lighthouse, oldmill, lush (1024x768x ~ 256 ) each ~ 600k babe24 ( ~ 512 x ~ 800 x ~ 256 ) ~ 400k avaliable from ticsys.tamu.edu 1) just compress the raw image extracted from the gif files 2) XOR neighbouring scan lines in raw image and then compress it. 3) subtract neighbouring ...... 4) build a color index table for each scan line and it turns out the size of the resulting files .. 1) ~ 90% of original gif 2,3) ~ 110% 4) ~ 100% if we exclude the color index table for the lines! -eillihca@fizzle.stanford.edu
gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) (08/30/90)
In article <1990Aug29.154719.17301@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >Note that it is sufficient that the scheme found compress _realistic_image_ >data well; it doesn't have to compress random input at all well, *Realistic* astronomical images contain a lot of gaussian noise. How general do you want your algorithm to be? As for other comments: I found in the "good old days" that ARC tended to huffman-encode images instead of LZW, because it was smaller. The "best" picture format on the ST is/was one called Tiny, which you can ftp a description of from atari.archive.umich.edu in ~/atari/graphics/picfmts.doc. However, that format would suck shit on an astronomical image. Adaptive huffman encoding might be your best bet. -- "Fuck you, Wumpus." -- Joe Stong
dik@cwi.nl (Dik T. Winter) (08/30/90)
In article <eillihca.651947189@fizzle.stanford.edu> eillihca@fizzle.stanford.edu (Achille Hui) writes: > 1) just compress the raw image extracted from the gif files > 2) XOR neighbouring scan lines in raw image and then compress it. > 3) subtract neighbouring ...... > 4) build a color index table for each scan line > > and it turns out the size of the resulting files .. > 1) ~ 90% of original gif > 2,3) ~ 110% > 4) ~ 100% if we exclude the color index table for the lines! > It depends on the kind of compressor you use. If you used standard compress, I am not much surprised; compress works very well if there are multi-byte patterns to be found that will get shorter encodings. But picture data (and also audio files) in general do not reveal such patterns. For audio files a much better compression is obtained when successive samples are subtracted (or XOR'ed) and the result Huffmann encoded. The reason this works good on audio files is that the differences (or XOR's, but for audio differences is better I think) are in general small numbers, so the largest part of the results will be in a (very) small range of possible values and that is where Huffmann is good at. (Note that the lower the dynamics of the audio the better Huffmann will work. I have seen Huffmann compression used this way reduce files to 30-50% where LZW might even go above 100%.) Translating this to pictures we find that XOR'ing successive scanlines will result in only a low number of possible results (again depending on the colour dynamics of the picture), and so Huffman might be superior. A disadvantage is that Huffmann is considerably slower than LZW. Huffmann has to scan the input twice, once to build the code table and once to do the coding. But decompressing is only marginally slower (the reason that it is slower is that LZW works at the byte level while Huffmann is at the bit level). Now if someone is willing to give it a try, somewhere in my sources I have routines that do Huffmann code table building, compression and decompression. I know nothing about the GIF format. (And I sure hope I spelled Huffmann right :-)) -- dik t. winter, cwi, amsterdam, nederland dik@cwi.nl
peter@sugar.hackercorp.com (Peter da Silva) (08/30/90)
In article <eillihca.651947189@fizzle.stanford.edu> eillihca@fizzle.stanford.edu (Achille Hui) writes: > peter@sugar.hackercorp.com (Peter da Silva) writes: > >I believe that XORing alternate scan-lines and run-length-encoding the result > >would do a better job. > 2) XOR neighbouring scan lines in raw image and then compress it. > 3) subtract neighbouring ...... > 2,3) ~ 110% [of original] Yes, but as Kent pointed out later on, LZW is poorly adapted to dealing with that sort of data set. Have you tried run-length encoding? -- Peter da Silva. `-_-' <peter@sugar.hackercorp.com>.
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (08/30/90)
peter@sugar.hackercorp.com (Peter da Silva) writes: > xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >> Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on >> the net, a month or two back, there was a suggestion that a good way to >> compress realistic images was to XOR scan lines after the first with their >> predecessor line, then LZW compress the output. > >I believe that XORing alternate scan-lines and run-length-encoding the result >would do a better job. I've heard of this algorithm being pretty effective >in past discussions. Should one do this with the image bitplane-mapped or >pixel-mapped? Not to suggest not running the experiment, but run length encoding (RLE) suffers from the same problem as LZ compression: the output data of the XOR is "speckley", with (sparse, one hopes) one bits scattered essentially at random in a long string of zero bits. This is not the kind of data on which RLE does well: long strings of one pattern followed by long strings of another. Comparitively, (taking 8 bit pixels as an easy example), the number of byte bit patterns with zero or one one-bit set is 9/256ths of the total patterns. If a large part of the output bytes of the XOR fall in this set, then this will strongly bias the "histogram" of byte frequencies, the right kind of data to make arithmetic encoding highly effective. To address your other issue, in realistic picture image data, I would expect pixel level RLE to be the better choice for the original image [I have _no_ concept of what would work better on the XOR output, and that might be worth trying in and of itself], since the count overhead is about the same but is paid to encode less data at the bitplane level. Runs at the bitplane level _probably_ correspond to runs at the pixel level, except occasionally by accident, so you encode about the same length run at either level, you just pay more overhead at the bitplane level. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (08/30/90)
eillihca@fizzle.stanford.edu (Achille Hui) writes: > peter@sugar.hackercorp.com (Peter da Silva) writes: >> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >>> Hmmm. Good idea. Here's one suggestion for an experiment. Somewhere on >>> the net, a month or two back, there was a suggestion that a good way to >>> compress realistic images was to XOR scan lines after the first with their >>> predecessor line, then LZW compress the output. >>I believe that XORing alternate scan-lines and run-length-encoding the result >>would do a better job. I've heard of this algorithm being pretty effective >>in past discussions. Should one do this with the image bitplane-mapped or >>pixel-mapped? >I have tried several things on several images: > lighthouse, oldmill, lush (1024x768x ~ 256 ) each ~ 600k > babe24 ( ~ 512 x ~ 800 x ~ 256 ) ~ 400k >avaliable from ticsys.tamu.edu >1) just compress the raw image extracted from the gif files >2) XOR neighbouring scan lines in raw image and then compress it. >3) subtract neighbouring ...... >4) build a color index table for each scan line >and it turns out the size of the resulting files .. >1) ~ 90% of original gif >2,3) ~ 110% >4) ~ 100% if we exclude the color index table for the lines! Well, this is not what either Peter or I suggested, but it is a data point. I'd be interested in at least some pseudocode of what you did for 2), to be sure you are doing what others have done. Reports about two months back in comp.graphics found a ~30% better compression of the XORed data with LZ than of the raw data with LZ, certainly not what you show from your tests. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) (08/30/90)
gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) writes: > xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: >>Note that it is sufficient that the scheme found compress _realistic_image_ >>data well; it doesn't have to compress random input at all well, >*Realistic* astronomical images contain a lot of gaussian noise. How >general do you want your algorithm to be? Well, as long as the "noise" is bit-sparse per pixel, the compression algorithms, such as Huffman encoding and arithmetic compression, that specialize in coding frequent pixels in short bit strings will probably still beat the compression algorithms, such as LZ, that look for repeated strings of pixels, or run length encoding, that looks for long strings of identical pixels, both of which are massively sabotaged by noise. >As for other comments: I found in the "good old days" that ARC tended >to huffman-encode images instead of LZW, because it was smaller. That, from my remarks above, is the expected result. Byte compression oriented compressors _should_ do even better with the XOR step between, but testing is needed. >The "best" picture format on the ST is/was one called Tiny, which you >can ftp a description of from atari.archive.umich.edu in >~/atari/graphics/picfmts.doc. Not an ftp site here; can you give a five line desription of Tiny's algorithm? >However, that format would suck shit on an astronomical image. Adaptive >huffman encoding might be your best bet. In a comparision between arithmetic compression and Huffman compression, each has different inefficiencies that prevent "perfect" information theoretic minimal encodings: Huffman pays: 1) a one bit per encoded unit penalty to act as a "stop bit", to divide the encoding of one unit from the encoding of the next; 2) (for the adaptive method) a penalty in that the start-up unit frequency estimate is incorrect and all units are initially considered equally likely; 3) some penalty from never being able to allow the expected frequency of a unit to go to zero, so that an encoding for it must exist and thus expand the encoding space at the expense of the encodings of existant units which must avoid aliasing to that encoding; 4) a fractional bit penalty per encoded unit (byte or pixel) from encoding an experienced frequency in an integer number of bits, when a fractional number would more closely approximate the true, observed frequency. Arithmetic compression pays no "bit per unit" penalty, and encodes the observed frequency in fractions of a bit, 1) and 4) above, but it pays other penalties: 2) and 3) for about the same reasons as Huffman, plus: 5) table compression penalty: to stay in 32 bit arithmetic (I'm talking here about the arithmetic compression algorithm with which I'm intimately familiar, others may differ), the total observed frequency must fit in 14 bits, so the frequencies must be divided by two and floored at one every 2**13 bytes; 6) an explicit EOF unit 257th encoding (in the case of encoding 8 bit bytes) must be carried along and never used for the whole input data compression, causing a minimal 1/(2**13) loss in encoding efficiency, just so that it can be used at the end to close off the file; and perhaps others I don't recognize. The result of these various penalties is that over a large input file with a reasonably skewed unit distribution histogram, the arithmetic compression method is a winner over Huffman encoding by saving the stop bit and by encoding units in fractions of a bit, and about breaks even otherwise, since penalties 5) and 6) are quite small. Of course, given a file consisting of monotonous repetitions of strings of all the possible units in order, both of these methods, as well as run length encoding, will suck rocks, and LZ will be a run-away winner. For realistic image data, however, byte encodings should beat string encodings, and arithmetic encodings beat adaptive Huffman encodings. The proof is in the testing, of course. Kent, the man from xanth. <xanthian@Zorch.SF-Bay.ORG> <xanthian@well.sf.ca.us>
cosell@bbn.com (Bernie Cosell) (08/30/90)
dik@cwi.nl (Dik T. Winter) writes: }Huffmann }has to scan the input twice, once to build the code table and once to }do the coding. ... You could just use an adaptive Huffman code and eliminate the second pass. /Bernie\
pim@cti-software.nl (Pim Zandbergen) (08/30/90)
>>GIF files are already compressed. If you're talking about compressing GIF >>files, you'll need to figure out a way to compress LZW-compressed files. >GIF -> MagicFormat and MagicFormat -> GIF converters will cover the rest of >the problems, just like the overwhelming number of converters now in use. >Defining a "whole new format" for image data seems to happen once a month, >and defining a new compression scheme about every three months; I doubt >One More Format will slow people down much. What about ppm as a Magic Format ? ppm files are not compressed. The pbmplus package is widely used and contains all sorts of tools for converting to mac, gif, tiff and other formats. ppmcompress would be a valuable addition to the pbmplus package. -- Pim Zandbergen domain : pim@cti-software.nl CTI Software BV uucp : uunet!mcsun!hp4nl!ctisbv!pim Laan Copes van Cattenburch 70 phone : +31 70 3542302 2585 GD The Hague, The Netherlands fax : +31 70 3512837
wiml@milton.u.washington.edu (William Lewis) (08/31/90)
In article <1990Aug30.100256.14356@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: > 2) (for the adaptive method) a penalty in that the start-up unit > frequency estimate is incorrect and all units are initially > considered equally likely; Well, since with a differenced image we already know it's going to have lots of small values and fewer large values, this could be coded into the algorithm as a default startup table ... > 6) an explicit EOF unit 257th encoding (in the case of encoding If the image size is stored in the header, this is not necessary as the decoder can simply stop reading when it's filled its buffer. -- wiml@blake.acs.washington.edu Seattle, Washington | No sig under (William Lewis) | 47 41' 15" N 122 42' 58" W |||||||| construction