Newsgroups: comp.compression Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu! wuarchive!csus.edu!borland.com!sidney From: sid...@borland.com (Sidney Markowitz) Subject: looking for info on image compression Message-ID: <1991Mar25.051453.23477@borland.com> Organization: Borland International Date: Mon, 25 Mar 1991 05:14:53 GMT 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 <sid...@borland.com>
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet! ns-mx!umaxc.weeg.uiowa.edu!drenze From: dre...@umaxc.weeg.uiowa.edu (Douglas Renze) Newsgroups: comp.compression Subject: Re: looking for info on image compression Message-ID: <5040@ns-mx.uiowa.edu> Date: 25 Mar 91 17:58:15 GMT References: <1991Mar25.051453.23477@borland.com> <SPOT.91Mar25095940@WOOZLE.GRAPHICS.CS.CMU.EDU> Sender: n...@ns-mx.uiowa.edu Reply-To: dre...@umaxc.weeg.uiowa.edu (Douglas Renze) Organization: U of Iowa, Iowa City, IA Lines: 6 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.
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet! ns-mx!pyrite.cs.uiowa.edu From: jo...@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) Newsgroups: comp.compression Subject: Re: looking for info on image compression Message-ID: <5043@ns-mx.uiowa.edu> Date: 25 Mar 91 19:48:07 GMT References: <5040@ns-mx.uiowa.edu> Sender: n...@ns-mx.uiowa.edu Lines: 38 From article <5...@ns-mx.uiowa.edu>, by dre...@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 jo...@cs.uiowa.edu
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu! ai-lab!zurich.ai.mit.edu!jaffer From: jaf...@zurich.ai.mit.edu (Aubrey Jaffer) Newsgroups: comp.compression Subject: Re: looking for info on image compression Message-ID: <JAFFER.91Mar27002238@michael.ai.mit.edu> Date: 27 Mar 91 05:22:38 GMT References: <5040@ns-mx.uiowa.edu> <5043@ns-mx.uiowa.edu> <1991Mar25.215830.5200@nntp-server.caltech.edu> Sender: n...@ai.mit.edu Organization: M.I.T. Artificial Intelligence Lab. Lines: 20 In-reply-to: toddpw@nntp-server.caltech.edu's message of 25 Mar 91 21:58:30 GMT >jo...@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 lea...@prep.ai.mit.edu.
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde! elroy.jpl.nasa.gov!sdd.hp.com!spool.mu.edu!uunet!viusys!alembic!csu From: c...@alembic.acs.com (Dave Mack) Newsgroups: comp.compression Subject: Re: looking for info on image compression Message-ID: <1991Apr2.003452.27382@alembic.acs.com> Date: 2 Apr 91 00:34:52 GMT References: <5043@ns-mx.uiowa.edu> <1991Mar25.215830.5200@nntp-server.caltech.edu> <JAFFER.91Mar27002238@michael.ai.mit.edu> Organization: Alembic Computer Services, McLean VA Lines: 29 In article <JAFFER.91Mar27002...@michael.ai.mit.edu> jaf...@zurich.ai.mit.edu (Aubrey Jaffer) writes: >>jo...@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
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!rutgers! cmcl2!kramden.acf.nyu.edu!brnstnd From: brns...@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.compression Subject: LZW is *not* safe to use Summary: IBM holds an earlier patent on LZW Message-ID: <29014:Apr215:25:5191@kramden.acf.nyu.edu> Date: 2 Apr 91 15:25:51 GMT References: <1991Mar25.215830.5200@nntp-server.caltech.edu> <JAFFER.91Mar27002238@michael.ai.mit.edu> <1991Apr2.003452.27382@alembic.acs.com> Organization: IR Lines: 20 In article <1991Apr2.003452.27...@alembic.acs.com> c...@alembic.acs.com (Dave Mack) writes: > Except that the patent-holder (Unisys, I believe) There are *two* patent holders on LZW: Unisys, through Welch's patent, and IBM, through the Miller-Wegman patent. The IBM patent covers LZW, among other things, and was filed earlier than the Sperry patent. (Yes, this does mean the Sperry patent should not have been approved.) It is *not* safe to use LZW. Unisys has been throwing disclaimers left and right for money it won't get. Despite the current market situation and various unfounded rumors, IBM has rights to LZW, and it hasn't disclaimed anything. > There is *no* problem with using software implementations of > LZW compression for anything, be it GIF encoding or news transport. No. There is a huge problem with all implementations of LZW, and the problem won't go away until 2006. ---Dan
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!evax!cs4304ak From: cs430...@evax.arl.utexas.edu (David Richardson) Newsgroups: comp.compression Subject: Re: LZW is *not* safe to use Message-ID: <1991Apr3.041358.6194@evax.arl.utexas.edu> Date: 3 Apr 91 04:13:58 GMT References: <JAFFER.91Mar27002238@michael.ai.mit.edu> <1991Apr2.003452.27382@alembic.acs.com> <29014:Apr215:25:5191@kramden.acf.nyu.edu> Organization: Computer Science Engineering Univ. of Texas at Arlington Lines: 18 In article <29014:Apr215:25:5...@kramden.acf.nyu.edu> brns...@kramden.acf.nyu.edu (Dan Bernstein) writes: >No. There is a huge problem with all implementations of LZW, and the >problem won't go away until 2006. Well, if IBM (or anyone else) who claims rights to LZW doesn't take positive action to enforce thier rights, the defendants in any future suit will have a good chance at proving that IBM (or whomever) abandoned thier patent. If anyone claims rights to software implimentations of LZW, I suggest they go to court real soon now, or at least give the world explicit permission to use the patent (a la Unisys). Disclaimer: I'm not a lawyer, but I play one on the net. -- David Richardson U. Texas at Arlington +1 817 856 6637 PO Box 192053 Usually hailing from: b645...@utarlg.uta.edu Arlington, TX 76019 b645...@utarlg.bitnet, SPAN: UTSPAN::UTADNX::UTARLG::B645ZAX -2053 USA The Lord is my shepherd, I shall not want.
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!snorkelwacker.mit.edu! hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd From: brns...@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.compression Subject: Re: LZW is *not* safe to use Message-ID: <10134:Apr318:51:3091@kramden.acf.nyu.edu> Date: 3 Apr 91 18:51:30 GMT References: <1991Apr2.003452.27382@alembic.acs.com> <29014:Apr215:25:5191@kramden.acf.nyu.edu> <1991Apr3.041358.6194@evax.arl.utexas.edu> Organization: IR Lines: 15 In article <1991Apr3.041358.6...@evax.arl.utexas.edu> cs430...@evax.arl.utexas.edu (David Richardson) writes: > Well, if IBM (or anyone else) who claims rights to LZW doesn't take > positive action to enforce thier rights, the defendants in any future > suit will have a good chance at proving that IBM (or whomever) abandoned > thier patent. No. Copyrighted documents and trademarks may fall into the public domain, but a patent is about as strong after 16 years of neglect as when it was new. (It is *stronger* after it has been applied commercially.) If you want citations for this, send me e-mail. Furthermore, the IBM Miller-Wegman patent was only issued two years ago. Two years is a short time in the patent business. ---Dan