Top Document: comp.compression Frequently Asked Questions (part 1/3) Previous Document: [16] What is the state of the art in lossless image compression? Next Document: [18] I need specs and source for TIFF and CCITT group 4 Fax See reader questions & answers on this topic!  Help others by sharing your knowledge You may want to read first item 77 in part 2 of this FAQ: "Introduction to Fractal compression". from Tal Kubo <kubo@zariski.harvard.edu>: According to Barnsley's book 'Fractals Everywhere', this method is based on a measure of deviation between a given image and its approximation by an IFS code. The Collage Theorem states that there is a convergent process to minimize this deviation. Unfortunately, according to an article Barnsley wrote for BYTE a few years ago, this convergence was rather slow, about 100 hours on a Cray, unless assisted by a person. Barnsley et al are not divulging any technical information beyond the meager bit in 'Fractals Everywhere'. The book explains the idea of IFS codes at length, but is vague about the application of the Collage theorem to specific compression problems. There is reason to believe that Barnsley's company has *no algorithm* which takes a given reasonable image and achieves the compression ratios initially claimed for their fractal methods. The 1000to1 compression advertised was achieved only for a 'rigged' class of images, with human assistance. The best unaided performance I've heard of is good lossy compression of about 801. Steve Tate <srt@duke.cs.duke.edu> confirms: Compression ratios (unzoomed) seem to range from 20:1 to 60:1... The quality is considerably worse than wavelets or JPEG on most of the noncontrived images I have seen. But Yuval Fisher <fisher@inls1.ucsd.edu> disagrees: Their performance has improved dramatically beyond what they were talking about in BYTE a few years ago. Human assistance to the compression is no longer needed and the compression time is reasonable, although the more time and compute power you throw at the compression, the smaller the resulting file for the same level of quality. Geoffrey A Stephenson <ketlux@ketlux.demon.co.uk> adds: Iterated systems are shipping a general purpose compressor at about 300 Pounds in the UK that claims "640x480 24 bit colour compression of about 1 min at 922k > 10k on a 486/50 software only, decomp. to 8 bits in 3 secs, etc." At a recent multimedia conference in London they handed out free demo disks that show the decomp. in action. The package runs under both DOS anf WIN (DLLs provided for use in applications). They also sell a board to speed up compression and offer versions supporting full motion video (but not apparently at all SVGA sizes like the static picture version). I have not yet got my hands on a full version to test different types of pictures, but friends have a and claim it looks good. Thomas W. Colthurst <thomasc@athena.mit.edu> clarifies the distinction between IFS and the Fractal Transform: It is time, once and for all, to put to death the Barnsley myth that IFSs are good for image compression. They are not. Various algorithms have been proposed for this "inverse problem" ranging from the trendy (genetic algorithms) to the deep (moment methods) to the ad hoc (the hungry algorithm) to the absurd (the socalled "graduate student algorithm", consisting of locking up a grad student in a tiny office with a SGI workstation and not letting them out until they come up with a good IFS for your image). They are all useless for practical image compression. In fact, there are even good theoretical reasons for believing that IFSs will never be useful for image compression. For example, even if you have an IFS for object A and an IFS for object B, there is no way to combine these IFSs to get an IFS for object A union B or object A intersect B. Even Barnsley himself admits, in his latest book, that he doesn't use IFS image compression. Instead, he uses the socalled "fractal transform," which is really just a variant of vector quantization where you use the image itself, sampled at a higher scale, as the VQ codebook. To be fair, the fractal transform can be analyzed using local IFSs, but local IFSs are immensely more complicated and general than normal IFSs, to the point where one feels suspect even using the word "IFS" to describe them. It should be emphasized that the fractal transform is a real, working method that performs about as well as other existing methods like VQ or the discrete cosine transform. The fractal transform will probably never beat vector quantization (VQ) as for size of the compressed image, but does have the advantage that you don't need to carry your codebook around. The latest results have it slightly winning over the discrete cosine transform; only time and more research will tell if this advantage persists. Just like VQ, the fractal transform takes a while to compress, but is quick at decompression (Barnsley's company has hardware to do this in realtime). In short, IFSs are good for just about everything fractals are (and more!), but are absolutely horrid for image compression. Programs: Check http://links.uwaterloo.ca/ for pointers to some fractal compression programs and lots of papers on fractal compression. The Waterloo BragZone (http://links.uwaterloo.ca/bragzone.base.html or ftp://links.uwaterloo.ca/pub/BragZone/ ) compares the results of various image compression schemes against a 32 element test suite. Numerous ratedistortion graphs, data tables, and sample images are available. A fractal image compression program is available by ftp in ftp://inls.ucsd.edu/pub/youngfractal/ ; it contains source for compression and decompression, source for Xwindows decompression, MSDOS executables and images. [Note from FAQ maintainer: Fisher's program (see below) implements the same algorithm but is more general; see http://inls.ucsd.edu/y/Fractals/ for the source code.] A fractal image decompression program (note: decompression only) is available in ftp://inls.ucsd.edu/pub/inlsucsd/ In the same directory, fractal_paper.ps.Z is the paper "Fractal image compression" by Yuval Fisher, Siggraph 92. Reading this paper is required to understand how the Young compression programs (see above) works. A note from Yuval Fisher <yfisher@ucsd.edu>: Connect to http://inls.ucsd.edu/y/Fractals/ . There is information there on my new book of contributed articles on fractal image compression, as well as the book's table of contents, some C code to encode and decode raw byte files of any size using a quadtree method, a manual explaining the use of the code, a fractal image compression bibliography (not guaranteed to be complete or close to it), some better executable code with sample encodings, and the SIGGRAPH '92 course notes on fractal image compression (these are based on appendix A of Chaos and Fractals by Peitgen et al., Springer Verlag). [The C code is also available in ftp://inls.ucsd.edu/pub/inlsucsd/ ] Another fractal compression program is available by ftp in ftp://vision.auc.dk/pub/Limbo/. It is also based on quadtrees, as yuvpak20 and frac_comp. The source code for the program published in the Oct 93 issue of Byte is in ftp://ftp.uu.net/published/byte/93oct/fractal.exe. This is a selfextractible arc file (must be run on MSDOS for extraction). The source code is for a TARGA video board. [Note from FAQ maintainer: this code is taken from Barnsley's book "Fractal Image Compression"; it implements the brute force method and is thus very slow.] Iterated Systems have released a beta version of their fractal imager. It will let you view a number of formats including JPG and do conversions to their fractal format. The program can be downloaded from http://www.iterated.com "The Data Compression Book" (see [NEL 1996] in item 7 above) contains a chapter on fractal compression; it includes source code for a simple fractal compression program. The source is also available at http://www.teaser.fr/~jlgailly/frac1.0.tar.gz Several fractal compression programs, including a volume coder, are available at http://www.eecs.wsu.edu/~wcochran/ Several papers on fractal image compression are available on ftp.informatik.unifreiburg.de in directory /documents/papers/fractal . A biliography is in ftp://schmance.uwaterloo.ca/pub/Fractal/ References: A. Jacquin, 'Fractal image coding based on a theory of iterated contractive image transformations', Proc. SPIE Visual Communications and Image Processing, 1990, pages 227239. (The best paper that explains the concept in a simple way.) A. Jacquin, "A Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding", PhD Thesis, Georgia Tech, 1989. It can be obtained from university microfilms for $35, phone 18005210600. M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld, October 1991, pp. 4252. M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan, 'Harnessing chaos for image synthesis', Computer Graphics, vol 22 no 4 pp 131140, 1988. M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated function systems to images', Visual Comm. and Image Processing, vol SPIE1001, 1988. A. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations" p.18, January 1992 (Vol 1 Issue 1) of IEEE Trans on Image Processing. A.E. Jacquin, 'A novel fractal blockcoding technique for digital images', Proc. ICASSP 1990. G.E. Oien, S. Lepsoy & T.A. Ramstad, 'An inner product space approach to image coding by contractive transformations', Proc. ICASSP 1991, pp 27732776. D.S. Mazel, Fractal Modeling of TimeSeries Data, PhD Thesis, Georgia Tech, 1991. (One dimensional, not pictures) S. A. Hollatz, "Digital image compression with twodimensional affine fractal interpolation functions", Department of Mathematics and Statistics, University of MinnesotaDuluth, Technical Report 912. (a nutsandbolts howtodoit paper on the technique) Stark, J., "Iterated function systems as neural networks", Neural Networks, Vol 4, pp 679690, Pergamon Press, 1991. Monro D M and Dudbridge F, "Fractal block coding of images", Electronics Letters 28(11):10531054 (1992) Beaumont J M, "Image data compression using fractal techniques", British Telecom Technological Journal 9(4):93108 (1991) Fisher Y, "Fractal image compression", Siggraph 92 Graf S, "Barnsley's Scheme for the Fractal Encoding of Images", Journal Of Complexity, V8, 7278 (1992). Monro D.M. 'A hybrid fractal transform', Proc ICASSP 93, pp. V: 16972 Monro D.M. & Dudbridge F. 'Fractal approximation of image blocks', Proc ICASSP 92, pp. III: 485488 Monro D.M., Wilson D., Nicholls J.A. 'High speed image coding with the Bath Fractal Transform', IEEE International Symposium on Multimedia Technologies Southampton, April 1993 Jacobs, E.W., Y. Fisher and R.D. Boss. "Image Compression: A study of the Iterated Transform Method." _Signal Processing 29_ (1992) 25263 Vrscay, Edward R. "Iterated Function Systems: Theory, Applications, and the Inverse Problem." _Fractal Geometry and Analysis_, J. Belair and S. Dubuc (eds.) Kluwer Academic, 1991. 405468. Books: Fractal Image Compression: Theory and Application, Yuval Fisher (ed.), Springer Verlag, New York, 1995. To order the book, call 1800SPRINGER and ask for the book with ISBN number 0387942114 or check http://www.springerny.com/ Fractal Image Compression Michael F. Barnsley and Lyman P. Hurd ISBN 0867204575, ca. 250 pp., $49.95 Copies can be ordered directly from the publisher by sending a message to kpeters@math.harvard.edu with name, address and a Mastercard or Visa card number with expiration date. Barnsley's company is: Iterated Systems, Inc. 5550A Peachtree Parkway, Suite 650 Norcross, GA 30092 tel: 4048400310 or 18004FRACTL fax: 4048400806 In UK: Phone (0734) 880261, Fax (0734) 880360 User Contributions:Comment about this article, ask questions, or add new information about this topic:Top Document: comp.compression Frequently Asked Questions (part 1/3) Previous Document: [16] What is the state of the art in lossless image compression? Next Document: [18] I need specs and source for TIFF and CCITT group 4 Fax Part1  Part2  Part3  Single Page [ Usenet FAQs  Web FAQs  Documents  RFC Index ] Send corrections/additions to the FAQ Maintainer: jloup@gzip.OmitThis.org
Last Update March 27 2014 @ 02:11 PM

News Headers
[70] Introduction to data compression (long)
[71] Introduction to MPEG (long)
[72] What is wavelet theory?
[73] What is the theoretical compression limit?
[74] Introduction to JBIG
[75] Introduction to JPEG
[76] What is Vector Quantization?
[77] Introduction to Fractal compression (long)
[78] The BurrowsWheeler block sorting algorithm (long)