cs001005@cslab9a.cs.brown.edu (Thomas Colthurst) (04/04/90)
In the January 1988 issue of BYTE, Barnsley and Sloan ("A Better
Way to Compress Images", p. 215-223) claim 10,000 to 1 image compression
ratios. Specifically, they claim that high-detail gray-scale aerial
photographs taking 130 megabytes can be compressed downto 13,000 bytes.
They also show pictures of the Black Forest, a Bolivian girl, and the
Monterey coast that are encoded to 2000, 2000, and 100 bytes,
respectively, and were "based on photographs in recent issues of
National Geographic." At SIGGRAPH '87, they showed a full sequence
video animation, A Cloud Study, which was "encoded at a ratio exceeding
1,000,000 to 1." A Cloud Study actually wasn't a pure IFS; it used IFS's
with time-varying parameters as detailed in "Blowing in the Wind: The
Continuous Dependence of Fractals on Parameters" (Fractals Everywhere,
3.11, p. 111-117 ).
The times required for these compressions is estimated as 100 hours
for complex color images on a Masscomp 5600 workstation (dual
68020-based systems). Decoding takes 30 minutes. Barnsley describes in
BYTE a custom hardware device prototype, called IFSIS, but gives no
performance characteristics. The algorithm they use first breaks up the
image into segments using edge detection, spectrum analysis, color
separation, etc. They then try to match these segments with a library
of fractals. I have yet to find a detail description of how this is
done, but Discover March 1989 ("Fractals in Your Future", pg. 26-27)
shows computer screen photos of the process. A non-automatic (requires
user to do the collage) program called Collage is described in Fractals
Everywhere (9.8, pg. 377-380). If anyone can find a more exact
description of the automatic compression algorithm, I would love to hear
about it, as I am currently working on an evolutionary algorithm for IFS
image compression.
A few details on the properties of IFS and IFS compressed images:
The size of the IFS increases at most linearly with increasing detail.
This is on of the main results of the Collage Theorem (see "Solution of
an inverse problem for fractals and other sets" by Barnsley, et al., in
Proc. Natl. Acad. Sci. USA, Vol. 83, pp. 1975-77, Apr. 1986 ). One of
the nice things about IFSs is that they aren't just for fractals: IFS
codes for polygons, for instance, are also very easy to construct. As
for real world images, the examples above sound very impressive, but the
algorithm used for compression has a large influence on the ratio
acheived (i.e., I'm not completely sure that the above images weren't
hand compressed, which would give them an advantage over machine
compressed ratios). Again, if anyone has details about the performance
of an automatic IFS compression algorithm, I would appreciate hearing
about them.
-Thomas Cpatterso@deimos.ADS.COM (Tim J. Patterson) (04/07/90)
In article <1571@dftsrv.gsfc.nasa.gov> seiler@amarna.gsfc.nasa.gov writes: >In article <3166@usceast.UUCP>, park@usceast.cs.scarolina.edu (Kihong Park) writes... >>Has anybody seen published work by M. Barnsley(or a public demonstration) >>corresponding to the performance of his image compression system based on >>IFSs? Since natural images are in many instances non-fractal, I am particularly >>interested in how his system fares w.r.t. the degree of faithfulness of the >>reproduced image vs original image. That is, does his system of IFSs increase >>drastically in size as more faithfulness is enforced? If there are enough >>responses, I will post a summary. > >If Barnsley can in fact produce what he claims, he may indeed have something. >However, his methods seem to be cloaked in a veil of mystery, as he explains >that he believes the success of his company depends on getting a working system >on the market at least 6 months ahead of anyone else. When he was here at NASA >Goddard over a year ago, he invited us to send a "non-expert" to his place, >where he would demonstrate his system, allowing the visitor to twiddle knobs >and such. He claimed that he could compress any image and retain full quality, >__given enough processing time__. It appears that to him the quality is not an >issue, but the time is. I believe he still has an offer where you can send him >an image, and he will send back a compressed image and tell you how much it was I've seen one of the images which was compressed 10,000 to one. It took a huge amount of time ( I vaguely recall days) to do the compression. Overall quality was not very good but what do you expect at that compression rate?
cs001005@cslab9c.cs.brown.edu (Thomas Colthurst) (04/07/90)
The thing that disturbs me about Barnsley's claims is not that I don't believe that he has something, but that the 'veil of mystery' around his system prevents me not only from implementing a compression system, but also to doubt that any efficient means are possible. That is, all of the IFS compressed images that we have seen could have been hand-compressed. The long time periods are disturbing as well -- WE DON'T EVEN KNOW THE ORDER OF THE ALGORITHM THAT DOES THE COMPRESSION. IFS compression may be very nice, but if the compression algorithm is not of polynomial time ... Does anyone know whether the literature on geometric algorithms addresses the general problem behind IFS compression, that is, given an arbitrary shape, find some smaller copies of the shape that can be positioned to 'collage' it? (Smaller copies being defined as linear transformations of) I've seen specific cases of the problem in brain-teaser books (two smaller rectangles can make a rectange, four triangles can make up an equilateral triangle) I wonder whether anyone has attacked the problem in general. -Thomas C
seibel@cgl.ucsf.edu (George Seibel) (04/08/90)
In article <35410@brunix.UUCP> cs001005@cslab9c.cs.brown.edu (Thomas Colthurst) writes: >The thing that disturbs me about Barnsley's claims is not that I don't >believe that he has something, but that the 'veil of mystery' around his >system prevents >me not only from implementing a compression system, but also to doubt >that any efficient means are possible. That is, all of the IFS Now hold on there. The only thing that Barnsley's secrecy is preventing you from doing is using HIS ideas and technology without giving him whatever credit/money/power/prestige that he wants. There's nothing preventing you from sitting down for a few decades and figuring it out on your own. No one should find this surprising or disturbing; this isn't science, it's business. Try calling up Intel and asking them for the precise details of their latest process. Their secrecy is, after all, preventing you from fabbing a few chips :-) George Seibel, UCSF seibel@cgl.ucsf.edu
sjreeves@trace.gatech.edu (Stan Reeves) (04/09/90)
In article <11700@ttidca.TTI.COM> schear@ttidca.tti.com (Steve Schear) writes: >In article <3166@usceast.UUCP> park@usceast.cs.scarolina.edu (Kihong Park) writes: >>Has anybody seen published work by M. Barnsley(or a public demonstration)... >The most recent published example of Mr. Barnsley's work I have found is in the >March issue of Scientific American. Barnsley had a student here (Arnaud Jacquin) who just presented a paper at ICASSP 90 (International Conference on Acoustics, Speech, and Signal Processing). I'm not sure if his method is exactly the same as the one Barnsley is using, but apparently Barnsley has done what he could to discourage this student from publishing his results. That seems to indicate that Barnsley considers the publication of this student's work a threat to his business. The results Arnaud presented were quite interesting, although not miraculous. :-) Stan Reeves Georgia Tech, School of Electrical Engineering, Atlanta, GA 30332-0250 UUCP: ...!{allegra,hplabs,ulysses}!gatech!eedsp!sjreeves INTERNET: sjreeves@eedsp.gatech.edu
uselton@orville.nas.nasa.gov (Samuel P. Uselton) (04/09/90)
In article <13652@cgl.ucsf.EDU> seibel@cgl.ucsf.edu (George Seibel) writes: >In article <35410@brunix.UUCP> cs001005@cslab9c.cs.brown.edu (Thomas Colthurst) writes: >>The thing that disturbs me about Barnsley's claims is not that I don't >>believe that he has something, but that the 'veil of mystery' around his >>system prevents >>me not only from implementing a compression system, but also to doubt >>that any efficient means are possible. That is, all of the IFS > >Now hold on there. The only thing that Barnsley's secrecy is preventing >you from doing is using HIS ideas and technology without giving him >whatever credit/money/power/prestige that he wants. There's nothing >preventing you from sitting down for a few decades and figuring it out >on your own. No one should find this surprising or disturbing; this >isn't science, it's business. Try calling up Intel and asking them for ^^^^^^^^ >the precise details of their latest process. Their secrecy is, after all, >preventing you from fabbing a few chips :-) > >George Seibel, UCSF >seibel@cgl.ucsf.edu I have two problems with Barnsley and his IFS based image encoding. The first is that he seems to want to be a business when it serves his purposes (protecting trade secrets etc) and ALSO publish "technical" papers for "academic" credit. His 1988 presentation at SIGGRAPH in Atlanta was the most obnoxious piece of commercialism masquerading as a "technical" talk I have seen in 15 years of conferences. My second difficulty is that he seems to want to sell you a product based on his word that it does its job well, without letting anyone else with expertise test the system. This proves nothing, but it suggests several possibilities: (1) there are certain things the system does poorly, he is trying to hide; (2) manual intervention, and expert choices may be required to get good compression; (3) what he is doing is actually quite simple, and would be figured out by an expert using the system. (and other possibilties...) I don't know if any of these are true, but I'M certainly not BUYING anything from him until I FIND OUT. Sam Uselton Disclaimer: I work for CSC, but they don't hold these opinions; I do. I work on a contract for NASA, but they don't hold these opinions either (at least not as policy. There may be some individuals...)
kassover@jupiter.crd.ge.com (David Kassover) (04/10/90)
In article <5538@amelia.nas.nasa.gov> uselton@nas.nasa.gov (Samuel P. Uselton) writes: ... >My second difficulty is that he seems to want to sell you a product based on >his word that it does its job well, without letting anyone else with >expertise test the system. Have you (or he) considered performing a beta test, under a suitable non-disclosure agreement? It would be nice if each of you would consider the rights and responsibilities required of signatories to such a mundane, BUSINESS transaction, before casting aspersions on each other. (or on generalized classes of people you each accuse the other of belonging to)
spl@duck.ncsc.org (Steve Lamont) (04/10/90)
In article <5538@amelia.nas.nasa.gov> uselton@nas.nasa.gov (Samuel P. Uselton) writes: > ... His [Barnsley's] 1988 presentation at SIGGRAPH in Atlanta was the most >obnoxious piece of commercialism masquerading as a "technical" talk I have >seen in 15 years of conferences. Agreed! I also was embarrassed by his presentation, particularly since I had just been extolling the technical virtues of SIGGRAPH just before the beginning of Barnsley's talk. I chalked it up to his naivete or poor judgement but now I can't say as I'm so sure of that. Where the *hell* were the reviewers on that paper??? spl -- Steve Lamont, sciViGuy (919) 248-1120 EMail: spl@ncsc.org NCSC, Box 12732, Research Triangle Park, NC 27709 Don't send in no bums. I want deals. -John Steinbeck, _The Grapes of Wrath_
Garry_Newsam.macitd@itd.dsto.oz (Garry Newsam) (04/11/90)
A couple of weeks or so ago I posted a query on user's experience with Dr. Barnsley's Iterated Systems Inc. software; as I got no response then, I thought I'd try again by tagging onto the present discussion. We are interested in using the software for compression in an image database, but before we buy it we would like to know what it does, in particular whether it compresses automatically or whether it has to be manually guided. Now that the price of VRIFS II has come down to ~$1,000 it is definitely affordable, but nobody likes to buy a pig in a poke and I have had some difficulty in finding out just exactly what VRIFS II does. For these reasons I would be grateful to hear from anyone who has actually used VRIFS. I should stress that I am not trying to find out how the software works, rather just some details on what it does. I greatly enjoyed reading Fractals Everywhere and find the idea to be a beautiful and stimulating application of mathematics, but I also respect the authors' rights to realize any profits from their discoveries. Garry Newsam ANZUS: Last line of protection for penguins
robert@texas.sgi.com (Robert Skinner) (04/12/90)
In article <1935@speedy.mcnc.org>, spl@duck.ncsc.org (Steve Lamont) writes: > In article <5538@amelia.nas.nasa.gov> uselton@nas.nasa.gov (Samuel P. Uselton) writes: > > ... [Barnsley's] 1988 presentation at SIGGRAPH in Atlanta was the most > >obnoxious piece of commercialism masquerading as a "technical" talk I have > >seen in 15 years of conferences. > > Agreed! I also was embarrassed by his presentation... > > Where the *hell* were the reviewers on that paper??? > I agree totally with Sam and Steve. I was embarrassed by Barnsley's presentation and offended by his commercialism. I can put up with a lot of crap if a person has a demonstrable product, but his machine seems cloaked in mystery. I hope that he DOES get rewarded financially if he indeed has something there, I just wish he would turn down the hype until its ready. Most people that present a paper at Siggraph and have a product to sell, let the product speak for itself, with slides and videos. Most never ask attendees to see the product, and when asked directly they say that the product can be seen on the exhibition floor or in (an unspecified) suite. On the other hand, Barnsley interrupted his presentation for "the most important announcement of my life" to tell everyone that his system was on display in room XXX of hotel YYY. He even hawked his book, for crissake. I don't think the reviewers can predict from the paper whether a person's presentation will be offensive. They can only judge the contents of the paper itself. I'll let someone more qualified comment on the content of his paper. It looks pretty thin to me, but I admit I know very little about the area. What do others think? Is it possible to reproduce any of his results given what's in his paper? (I know there's code in his book, but that doesn't count.) Robert Skinner robert@sgi.com He who knows not and knows that he knows not is ignorant. Teach him. He who knows not and knows not that he knows not is a fool. Shun him. He who knows and knows not that he knows is asleep. Wake him. He who knows and knows that he knows is wise. Follow him.
sjs@roland.ctt.bellcore.com (Stan Switzer) (04/12/90)
Regarding Barnsley's method: > I've seen one of the images which was compressed 10,000 to one. It > took a huge amount of time ( I vaguely recall days) to do the > compression. Overall quality was not very good but what do you expect > at that compression rate? Unless the nature of the image degradation can be characterized in some formal way, the technique will only be useful for producing Gaughinesque renditions of scanned images. I can see some applications where all you need is gee-whiz graphics, but I can't see how how it could be useful beyond that. On the other hand, if the nature of the image quality degradation could be formally (and publicly) described, then the technique might be useful in a wide range of applications. As it stands, it is impossible to tell. Stan Switzer sjs@bellcore.com
cs001005@cslab9c.cs.brown.edu (Thomas Colthurst) (04/13/90)
In <22023@bellcore.bellcore.com>, sjs@roland.ctt.bellcore.com (Stan Switzer) writes: >Regarding Barnsley's method: > >> I've seen one of the images which was compressed 10,000 to one. It >> took a huge amount of time ( I vaguely recall days) to do the >> compression. Overall quality was not very good but what do you expect >> at that compression rate? > >Unless the nature of the image degradation can be characterized in >some formal way, the technique will only be useful for producing >Gaughinesque renditions of scanned images. I can see some >applications where all you need is gee-whiz graphics, but I can't see >how how it could be useful beyond that. > >On the other hand, if the nature of the image quality degradation >could be formally (and publicly) described, then the technique might >be useful in a wide range of applications. As it stands, it is >impossible to tell. It's hard to tell how well Barnsley's algorithm preserves quality because we don't have the original pictures, just the reconstructed images. From my inspection, though, these don't look too bad. The nature of the image quality degradation is formally described by the collage theorem, but this is only a theoretical result about the potential of an IFS compression system, specifically that increase in image detail can be obtained by only a linear increase in size of the compression. A specific algorithm that uses IFS compression may not achieve that potential, or may acheive that potential only in n^3 time or worse ... The evolutionary IFS compression algorithm that I am currently working on will be able to achieve an arbitrarily specified level of detail, but I haven't done a time analysis yet ... -Thomas C
patterso@deimos.ADS.COM (Tim J. Patterson) (04/13/90)
Organization: Advanced Decision Systems In article <22023@bellcore.bellcore.com> sjs@bellcore.com (Stan Switzer) writes: >Regarding Barnsley's method: > >> I've seen one of the images which was compressed 10,000 to one. It >> took a huge amount of time ( I vaguely recall days) to do the >> compression. Overall quality was not very good but what do you expect >> at that compression rate? > >Unless the nature of the image degradation can be characterized in >some formal way, the technique will only be useful for producing >Gaughinesque renditions of scanned images. I can see some >applications where all you need is gee-whiz graphics, but I can't see >how how it could be useful beyond that. > >On the other hand, if the nature of the image quality degradation >could be formally (and publicly) described, then the technique might >be useful in a wide range of applications. As it stands, it is >impossible to tell. > >Stan Switzer sjs@bellcore.com There have been a lot of different measures proposed for compression error analysis--rms error, edge loss, rms in the hvs space etc. and to my knowledge nobody has a definative image quality index. What are you really saying when requesting a formal public measure and saying this would make the technique useful? Tim
genetti@cs.tamu.edu (Jon Genetti) (04/13/90)
In article <6277@odin.corp.sgi.com> robert@sgi.com writes: >I don't think the reviewers can predict from the paper whether a >person's presentation will be offensive. They can only judge >the contents of the paper itself. > What content of the paper? Everything in the paper had already been published more than once in various journals. I guess SIGGRAPH wanted to "protect itself" in case this happens to be a revolutionary idea. jon genetti.
flitter@atisun.dt.navy.mil (Lance Flitter) (04/13/90)
I believe that one of the prime areas that Barnsley's technique is supposed to be used for is sattelite images. If a sattelite had and IFS generator it could compress weather pattern photos and save considerable time sending them to earth.