sidney@borland.com (Sidney Markowitz) (03/25/91)
I'm interested on information on compression techniques that are suitable for images, where exact reproduction of the data is not necessary after decompression, as long as the result looks ok as an image. I've heard that there are, for example, fractal techniques that achieve much better compression on images than standard data compression techniques, like LZW, with which I'm familiar. Can anyone point me to some references to look up and/or some example code that can be ftp'd? How good compression can you get for different resolutions in typical images? Thanks. -- sidney markowitz <sidney@borland.com>
spot@CS.CMU.EDU (Scott Draves) (03/25/91)
In article <1991Mar25.051453.23477@borland.com> sidney@borland.com (Sidney Markowitz) writes:
I'm interested on information on compression techniques that are
suitable for images, where exact reproduction of the data is not
necessary after decompression, as long as the result looks ok as an
image.
this is usu called "lossey" compression. There are two of current
interest, JPEG and HDTV Digicipher. Here are some references
(provided to me by hewlett@media-lab, thank you!)
G.K Wallace, "Overview of the JPEG (ISO/CCITT) Still Image
Compression System, "Visual Communications and Image Processing '89,
SPIE, Philadelphia, November 1989
A. Fernandez, R. Ansari, D.J. Gall and C.T. Chen, "HDTV Subband/DCT
Coding: Analysis of System Complexity," IEEE Globecom Proceedings,
343.1.1 - 343.1.4, 1990
I've heard that there are, for example, fractal techniques that
achieve much better compression on images than
The fractal compression is done by Barnesly (sp?) from Georgia Tech, I
think. As far as I can tell, it is a money-making hoax. He won't
disclose his algorithms unless you pay him lots of money, and I have
yet to see an example of an actual compressed image (He has a few
images he likes to show, and they *are* generated by ridiculously
small quantities of data. But he doesn't show the original.... i
wonder why...)
--
christianity is stupid
Scott Draves communism is good
spot@cs.cmu.edu give updrenze@umaxc.weeg.uiowa.edu (Douglas Renze) (03/26/91)
Hmm. Well, in the info-mac archives in the directory info-mac/source/c there's a set of algorithms for GIF image compression. I haven't looked at them, but I would assume that they're fairly complete & that they could (maybe) be adapted to other image types (I'm not very familiar with the GIF image format). FYI, the info-mac archives are at 36.44.0.6 and you can do an anonymous login.
jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) (03/26/91)
From article <5040@ns-mx.uiowa.edu>, by drenze@umaxc.weeg.uiowa.edu (Douglas Renze): > ... a set of algorithms for GIF image compression. I haven't looked at > them, but I would assume that they're fairly complete & that they could > (maybe) be adapted to other image types ... > GIF images use Ziv-Lempel compression, which is not a particularly good way to compress images. The problem is, it operates on strings of successive letters, and it works best if short strings of letters have some significance and are likely to be repeated. In images, repetitions of any string, when they occur, are usually accidental, and strings of pixels, reading left to right, are lousy predictors of the next pixel compared to 2-dimensional neighborhoods. I did an experiment using my splay-tree based compression algorithm with just one state in its source model, and it equalled the performance of Ziv-Lempel compression on digitized portraits. Multi-state compression models for images can do much better (and my splay-tree based algorithm is not intended to be a space-optimal compression algorithm). These results were published in my CACM paper of Aug, 1988. Further results of mine concerning use of splay-tree based compression on images will appear in the 1991 Data Compression Conference two weeks from now. (PS: Does the use of Ziv-Lempel compression for GIF images mean that the question of patent rights for the Ziv-Lempel algorithm applies to GIF images? My source code for one GIF viewer had a note saying that the uncompression code was borrowed from the UNIX compress command, and I understand that there are patent infringement questions currently being asked about UNIX compress.) (PPS: I give away copies of my splay-tree compression code to anyone who asks for it.) Doug Jones jones@cs.uiowa.edu
toddpw@nntp-server.caltech.edu (Todd P. Whitesel) (03/26/91)
jones@pyrite.cs.uiowa.edu writes: >(PS: Does the use of Ziv-Lempel compression for GIF images mean that >the question of patent rights for the Ziv-Lempel algorithm applies to >GIF images? It might. I know a few GIF program authors are worried about it, one to the point of leaving it out of a commercial program. I'm almost about to release a shareware GIF viewer myself and I was beginning to wonder. What bugs me is that if somebody really does own all the rights to LZW and/or GIF, they've done a piss-poor job protecting those rights and I hope they don't get to screw everybody who went out and used the technology. >(PPS: I give away copies of my splay-tree compression code to anyone >who asks for it.) Sounds interesting -- could you give a copy in my direction? Todd Whitesel toddpw @ tybalt.caltech.edu
GNewsam@itd.dsto.oz (G.N. Newsam) (03/26/91)
In article <1991Mar25.051453.23477@borland.com> sidney@borland.com (Sidney Markowitz) writes: > I'm interested on information on compression techniques that are > suitable for images, where exact reproduction of the data is not > necessary after decompression, as long as the result looks ok as an > image. This would seem a great starter for a FAQ posting in the group by some expert out there. Thanking you in advance. G.N. Newsam Anzus: The last line of defence for penguins. (Opinions expressed above are those of the penguins only and do not necessarily coincide with those of DSTO as a whale.)
cokasaki@PROOF.ERGO.CS.CMU.EDU (Chris Okasaki) (03/26/91)
In article <5043@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes: >...and strings of >pixels, reading left to right, are lousy predictors of the next pixel >compared to 2-dimensional neighborhoods. Given a 2-dimensional image and a locally adaptive compression algorithm which works on 1-dimensional streams, one can do much better than simply processing the pixels from left to right, row by row. As the previous poster suggested, a 2-dimensional neighborhood provides a much better predictor. This is especially important for compression algorithms such as the poster's splay-tree algorithm which adapt very quickly. What one wishes to do is increase the 2-dimensional "locality" of any particular contiguous subsequence of the 1-dimensional stream of data seen by the compressor. One very simple, and very fast, approach is to "snake" through the image, compressing the first row from left to right, the second row from right to left, the third row from left to right, etc. This prevents the annoying "jumps" from the end of one row to the beginning of the next. An even better method is to process the image in strips of N rows, "snaking" vertically across the first strip, then back across the second strip, etc. For instance, a 5x4 image might be processed in the following order (with N=2): 1 4 5 8 9 2 3 6 7 10 19 18 15 14 11 20 17 16 13 12 The value of N depends on size of the compression algorithm's "window", that is, how many previous pixels are significant in determining the current state. For instance, if an algorithm uses the last M pixels to predict the value of the current pixel, then N=sqrt(M) would be a good choice. Unfortunately, M is not always easy to calculate, and even if M is known, the M pixels may not be weighted the same, further complicating the choice of N. An even better, if significantly more complex, path through the image can best be described recursively. The basic pattern is ->1 4-> | ^ v | 2->3 where you enter from the top left and exit from the top right (this orientation will be rotated as the algorithm progresses). Now, divide the image into quadrants, and process each quadrant recursively in the following manner: Quadrant 1 (top left) : enter from the top left, exit from the bottom left Quadrant 2 (bot. left) : enter from the top left, exit from the top right Quadrant 3 (bot. right): enter from the top left, exit from the top right Quadrant 4 (top right) : enter from the bottom right, exit from the top right (Note that the orientation's of the recursive subcalls for Quadrants 1 and 4 are flipped.) For example, an 8x8 image would be processed in the following order: 1 4 5 6 | 59 60 61 64 2 3 8 7 | 58 57 62 63 15 14 9 10 | 55 56 51 50 16 13 12 11 | 54 53 52 49 ------------+------------ 17 18 31 32 | 33 34 47 48 20 19 30 29 | 36 35 46 45 21 24 25 28 | 37 40 41 44 22 23 26 27 | 38 39 42 43 Of course, compressing a 2-dimensional image with an algorithm DESIGNED for that job will almost certainly yield better results than a 1-dimensional stream compressor applied to the same image, but by being careful in our choice of the ORDER in which pixels are processed we may be able come close to the performance of a true 2-d compressor, while still employing our trusty, well-understood, 1-d compression utilities. Comments? Chris cokasaki@cs.cmu.edu BTW, these paths that I've been desribing might be best thought of as space-filling curves. Does anyone know of any better curves in terms of the "locality" of contiguous subsequences? -- ------------------------------------------------------------------------------- | Chris Okasaki | Life is NOT a zero-sum game! | | cokasaki@cs.cmu.edu | | -------------------------------------------------------------------------------
wcs) (03/26/91)
]In article <5043@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes: ]>...and strings of ]>pixels, reading left to right, are lousy predictors of the next pixel ]>compared to 2-dimensional neighborhoods. In article <12481@pt.cs.cmu.edu> cokasaki@PROOF.ERGO.CS.CMU.EDU (Chris Okasaki) suggests using space-filling curves, and then 1-d-compressing along them. Another cheap method, which can often provide good results (at least for black&white), is to first take the difference between each row and the previous one, and then use the 1-d-left-to-right Lempel-Ziv or Huffman or whatever. It's been a while since I did any benchmarks, but I got decent results for gray-scale weather images; we didn't bother using 2-D methods in our production code, since even straight compress shrunk most of my data to 35% of original, and color radar data compressed down to 2-3% (it was usually mostly black.) This let us ship data at 9600 baud faster than it was arriving from the satellite, and the application was short-term; your mileage may vary, and better techniques could have improved the economics if we need. -- # Bill Stewart 908-949-0705 erebus.att.com!wcs AT&T Bell Labs 4M-312 Holmdel NJ (Little Girl:) When I grow up, I want to be a nurse } From this week's UFT (Little Boy:) When I grow up, I want to be an engineer } radio commercial .... guess the Political Correctness Police don't run NYC's teachers' union yet
cme@ellisun.sw.stratus.com (Carl Ellison) (03/27/91)
In article <1991Mar25.051453.23477@borland.com> sidney@borland.com (Sidney Markowitz) writes: >I'm interested on information on compression techniques that are >suitable for images, where exact reproduction of the data is not >necessary after decompression, as long as the result looks ok as an >image. I saw some very good images which had been compressed to 1 bit per pixel (B&W). This was many years ago -- at the Univ. of Utah -- by students working under Professor Thomas G. Stockham.
jaffer@zurich.ai.mit.edu (Aubrey Jaffer) (03/27/91)
>jones@pyrite.cs.uiowa.edu writes: > >>(PS: Does the use of Ziv-Lempel compression for GIF images mean that >>the question of patent rights for the Ziv-Lempel algorithm applies to >>GIF images? It definitely does, assuming GIF format uses LZ compression and the patent is considered valid. Only a lawsuit will determine actual coverage. If the algorithm differs somewhat from LZ you may be safe (but consult a lawyer). Much better would be to distribute replacements for GIF and LZ that are not covered by patents. Software patents pose a severe threat to programming as a profession. If the current trends in software patents continue only lawyers will be qualified to program. If you are concerned about these issues I invite you join the League for Programming Freedom, a group dedicated to bringing back the freedom to write programs. For more information send Internet mail to league@prep.ai.mit.edu.
toddpw@nntp-server.caltech.edu (Todd P. Whitesel) (03/27/91)
jaffer@zurich.ai.mit.edu (Aubrey Jaffer) writes: > Much better would be to distribute >replacements for GIF and LZ that are not covered by patents. This is an excellent idea, especially given the direction CI$ seems to be going with GIF. Is anybody working on such a thing? Todd Whitesel toddpw @ tybalt.caltech.edu
ge@dbf.kun.nl (Ge' Weijers) (03/27/91)
cokasaki@PROOF.ERGO.CS.CMU.EDU (Chris Okasaki) writes: [description of algorithm deleted] >Of course, compressing a 2-dimensional image with an algorithm DESIGNED >for that job will almost certainly yield better results than a 1-dimensional >stream compressor applied to the same image, but by being careful in our >choice of the ORDER in which pixels are processed we may be able come close >to the performance of a true 2-d compressor, while still employing our >trusty, well-understood, 1-d compression utilities. >Comments? Yep. An article in the Computer Journal suggested using space-filling curves to compress images. I'll look up the reference if you want. The article mentions Peano- and Hilbert-curves. I never know which is which, but you're using one of the two. Ge' -- Ge' Weijers Internet/UUCP: ge@cs.kun.nl Faculty of Mathematics and Computer Science, (uunet.uu.net!cs.kun.nl!ge) University of Nijmegen, Toernooiveld 1 6525 ED Nijmegen, the Netherlands tel. +3180652483 (UTC-2)
ge@dbf.kun.nl (Ge' Weijers) (03/27/91)
wcs@cbnewsh.att.com (Bill Stewart 908-949-0705 erebus.att.com!wcs) writes: >Another cheap method, which can often provide good results >(at least for black&white), is to first take the difference >between each row and the previous one, and then use the 1-d-left-to-right >Lempel-Ziv or Huffman or whatever. That's probably why group 3 fax machines use it, with a fixed Huffman table. Ge' -- Ge' Weijers Internet/UUCP: ge@cs.kun.nl Faculty of Mathematics and Computer Science, (uunet.uu.net!cs.kun.nl!ge) University of Nijmegen, Toernooiveld 1 6525 ED Nijmegen, the Netherlands tel. +3180652483 (UTC-2)
robertsw@gtephx.UUCP (Wallace) (03/28/91)
In article <5043@ns-mx.uiowa.edu> jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) writes: [ ... mucho text deleted ... ] > >(PPS: I give away copies of my splay-tree compression code to anyone >who asks for it.) > > Doug Jones > jones@cs.uiowa.edu doug, please submit your code to comp.sources; i'm quite certain there exists a _great_ interest on the net. besides, what better way to become a net.legend. :-) cheers && happy hacking, wild rider
jj@alice.att.com (jj, like it or not) (03/28/91)
Well, you could look into JPEG, which is a (soon to be) standard
image compression format.
You could check out Safranek and Johnston, ICASSP 89, for a B&W
method.
You could check out Stockham's paper in the same ICASSP,
as well.
--
-------->From the pyrolagnic keyboard of jj@alice.att.com<--------
Copyright alice!jj 1991, all rights reserved, except transmission by USENET and
like free facilities granted. Said permission is granted only for complete copies
that include this notice. Use on pay-for-read services specifically disallowed.csu@alembic.acs.com (Dave Mack) (04/02/91)
In article <JAFFER.91Mar27002238@michael.ai.mit.edu> jaffer@zurich.ai.mit.edu (Aubrey Jaffer) writes: >>jones@pyrite.cs.uiowa.edu writes: >> >>>(PS: Does the use of Ziv-Lempel compression for GIF images mean that >>>the question of patent rights for the Ziv-Lempel algorithm applies to >>>GIF images? > >It definitely does, assuming GIF format uses LZ compression and the >patent is considered valid. Only a lawsuit will determine actual >coverage. If the algorithm differs somewhat from LZ you may be safe >(but consult a lawyer). Much better would be to distribute >replacements for GIF and LZ that are not covered by patents. Except that the patent-holder (Unisys, I believe) has publicly stated that it does not intend to enforce the patent on software implementations, only on hardware implementations of the algorithm. This issue was hacked to death in news.admin a couple of months ago, since LZW compression is also used by the "compress" program which most versions of news use to compress news batches. There is *no* problem with using software implementations of LZW compression for anything, be it GIF encoding or news transport. And your favorite modem manufacturer is already paying royalties to Unisys. Don't sweat it. -- Dave Mack