park@usceast.cs.scarolina.edu (Kihong Park) (04/14/90)
The following is a summary of the responses conveyed by various people publicly on the net and privately to me regarding my intitial posting on comp.graph and alt.fractals. I am sure I haven't adequately reflected the opinions of all parties engaged in the discussion, and for that I apologize. The postings and replies basically constituted two categories, one referring to technicalities and experiences with Barnsley's Iterated Function Systems approach to compressing and synthesizing images, and the other discussing the issues surrounding academic vs commercial aspects of his approach. 1. How "good" is IFS? 1.1. It seems to be very good. A lot of the responses attesting to this effect were made in reference to popular articles(eg. Sci Am, Byte), demonstrations, books, etc. The main point forwarded was the impressive compression ratios achieved(eg. 10000:1). Since "conventional" methods do not even come close to some of the more humble ratios reported using IFS, this certainly is a "eye-catcher". IFSs certainly do work well if the image is self-similar, but as pointed out, that's not a prerequisite. Even though the performance may vary between different types of images, IFS based compressions methods are nevertheless general purpose methods. 1.2. It seems promising but it has its problems. The good points are the same as above. High compression ratios, general purpose, works on images other than "fractal" ones, IFSs are relatively easy to understand and implement. And, you can draw nice synthesized pictures which would be otherwise difficult to do. The negative points are as follows: 1) The speed is slow However one does the actual compression, it seems that compressing an image can take time in the order of hours. There are varying reports on examples ranging from 6 hours to well above. Whatever the practical case, it is the fact that there do not seem to be reports on the formal time-complexities of the algorithms which makes their evaluation that more difficult. As expected, the decoding, i.e., rendering process, takes much less time. 2) User Friendliness & Automation of IFS inference As the March 1990 Sci Am article suggests, the present VRIFS system is manually driven, and the automatic version is expected to hit the scene this coming summer. How good a system Barnsley's company will come up with will have to be seen, but as to his present marketed product, the general response was that it was not too pleasant to use. If one has to manually fit the transformations to appease the Collage theorem, it may take a substantial amount of human effort to do so. Automation seems to be a nontrivial problem, and it would suggest that anyone can design their own system. That is, it is a somewhat independent problem. 3) General Performance Commercially as well as academically, there does not seem to be a lot of comparative work done to forward any meaningful conclusion. As many people have pointed out, because of its commercial interest, a somewhat secretive veil surrounds Barnsley's inference method. This is understandable, and it would seem that it is now the task of the general interested public to do independent work, and hence render judgement on IFS's practical as well as potential applicability. My original posting asked how well Barnsley's IFS method scaled w.r.t. imposing more faithfulness of reproduction. One person made the statement that "the size of the IFS grows at most linearly with increasing detail". Barnsley's Collage theorem roughly states that the Hausdorff distance between the actual image and the image defined as the attractor of a given IFS is bounded above by the distance of the actual image with the first-step fitted image divided by 1 - the scale factor. Hence, as one adds more transformations to the IFS s.t. their scale factors are less that the scale factor of the IFS, the upper bound representing the picture differences becomes reduced. I hope this is what was pointed to by the above statement. But, this is a too general notion to say much about actual scaling. As some other person has pointed out, comparative analysis with more concrete criteria is necessary. The most important factor is how faithfulness scales w.r.t. time. And here, it would seem, experimental analysis is a must. 4) Dependence on Image type Trivially, the best forum for IFS based compression methods are regular, self-similar images. Many natural images have a degree of self-similarity, and at that they have "random" variations. We can easily synthesize images which look like "standard" bushes, trees, ferns etc., but this doesn't mean that in certain applications of image compression, one will be satisfied with this. And for many other images, the synthesizing process is not as simple, and hence the inference process is also not. How much more effort in terms of time and size is needed to enforce more faithfulness seems to be very much dependent on the image one is compressing. 2. Academic vs Commercial aspects of IFS A lot of postings and responses have indicated a very irritated, and not too receptive audience who object to Barnsley pushing his commercial interest as well as academic credit taking at the same time. It seems that because of his business interest, claims are made but not fully explained in fear of exposing too much information. Understandably, there is a conflicting factor waiting to surface if both aspects are not juggled with tact and academic courtesy. To summarize the majority response, at least from the comp.graphics and alt.fractals population sample, a lot of people seem to be annoyed by Barnsley's actions. To be fair to Barnsley, the following factors should nevertheless be noted. He has written a rather nice textbook-like book on fractal geometry which to my knowledge is used in a quite a few schools offering courses on this subject(Fractals Everywhere, M. Barnsley, Academic Press, 1988). Well, then again, nobody was actually contesting his academic contribution. As to his commercial product, from his company point-of-view, all the hype surrounding IFS is good marketing strategy. Of course, unless too many people get annoyed. The fact that he doesn't want to disclose too many details about his software is also understandable from a business point-of-view. The fact of the matter is, as far as I know, all his major results, including the Collage theorem date a few years back. Thus, the concept of IFS and attractors as images is so-to-say public knowledge. He seems to want to capitalize on his work by building a good image compression system, and selling it. Hence, whatever product he comes out with is "beyond" the standards of academia. He is presently taking on the role of a business man, and thus should be considered as such. Academic forums where research is announced naturally presumes that a proof validating the claims would be provided. If a product pitch is made, or has been made at academic gatherings without further validating the claims as was suggested by some people, then it seems to me at least, to be a fault of the organizers and not so much the person himself. Concluding the summary, I would like to remark that building an automatic image compression system based on IFS is an engineering effort more than anything else. Of course, this doesn't imply that some sophisticated approximation methods from mathematics won't be applied to yield an interesting technique which stands by itself. But as to compressing images using IFS, if interesting algorithms are devised which deserve the attention of the academic community and the creator is willing to disclose the necessary imformation to validate its results, then this is a matter of academia. If on the other hand, algorithms are devised with commercial interest in mind, then nondisclosure of information will be from a business viewpoint necessary, and thus this would fall outside of the realm of academia. I hope I haven't conveyed a too biased summary of the discussion which is actually still going on at this time. I think that many people are interested in image compression techniques based on IFS, and for those of us who are presently not interested in setting up a company should try to devise our own methods and experiments to evaluate the approach. I have a concatenated file of all the postings corresponding to this subject matter, so if there is a late comer and he/she wishes to look at the original discussion, you can write to me at the follwing address and I will mail it to you. Of course, I can't mail you the ones that were sent to me privately. Kihong Park. (park@cs.scarolina.edu)