## Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z

# comp.compression Frequently Asked Questions (part 1/3)Section - [17] What is the state of fractal compression?

( Part1 - Part2 - Part3 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Counties ]

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
```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 1000-to-1 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 80-1.

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
non-contrived 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.

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 so-called "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 so-called "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.

or ftp://links.uwaterloo.ca/pub/BragZone/ ) compares the results of
various image compression schemes against a 32 element test suite.
Numerous rate-distortion graphs, data tables, and sample images are available.

A fractal image compression program is available by ftp in
ftp://inls.ucsd.edu/pub/young-fractal/ ; it contains source for
compression and decompression, source for X-windows 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/inls-ucsd/
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/inls-ucsd/ ]

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 self-extractible 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
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/frac-1.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.uni-freiburg.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 227-239.  (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 1-800-521-0600.

M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld,
October 1991, pp. 42-52.
M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan,
'Harnessing chaos for image synthesis', Computer Graphics,
vol 22 no 4 pp 131-140, 1988.
M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated
function systems to images', Visual Comm. and Image Processing,
vol SPIE-1001, 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 block-coding 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 2773-2776.
D.S. Mazel, Fractal Modeling of Time-Series Data, PhD Thesis,
Georgia Tech, 1991.    (One dimensional, not pictures)
S. A. Hollatz, "Digital image compression with two-dimensional affine
fractal interpolation functions", Department of Mathematics and
Statistics, University of Minnesota-Duluth, Technical Report 91-2.
(a nuts-and-bolts how-to-do-it paper on the technique)
Stark, J., "Iterated function systems as neural networks",
Neural Networks, Vol 4, pp 679-690, Pergamon Press, 1991.
Monro D M and Dudbridge F, "Fractal block coding of images",
Electronics Letters 28(11):1053-1054 (1992)
Beaumont J M, "Image data compression using fractal techniques",
British Telecom Technological Journal 9(4):93-108 (1991)
Fisher Y, "Fractal image compression", Siggraph 92
Graf S, "Barnsley's Scheme for the Fractal Encoding of Images",
Journal Of Complexity, V8, 72-78 (1992).
Monro D.M. 'A hybrid fractal transform', Proc ICASSP 93, pp. V: 169-72
Monro D.M. & Dudbridge F. 'Fractal approximation of image blocks',
Proc ICASSP 92, pp. III: 485-488
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) 25-263
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.  405-468.

Books:
Fractal Image Compression: Theory and Application, Yuval Fisher (ed.),
Springer Verlag, New York, 1995.
To order the book, call 1-800-SPRINGER and ask for the book with
ISBN number 0-387-94211-4 or check http://www.springer-ny.com/

Fractal Image Compression
Michael F. Barnsley and Lyman P. Hurd
ISBN 0-86720-457-5, 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: 404-840-0310 or 1-800-4FRACTL
fax: 404-840-0806
In UK: Phone (0734) 880261, Fax (0734) 880360

```

## User Contributions:

The Major Advantages of uniform dating

online dating services is not a newest platform but it has taken a sudden rise after the advancement in the technologies. This has revolutionised the way singles meet. With many struggles of dating in today sphere, More people these days are turning their heads towards the internet.

Even for arranged your marriage, Older dating and stuff like that, People are changing themselves and adopting the platform with all open heart and mind. Beside several advantages these platforms possess, Location and religion are the factors that set it apart. You can find your life partner from everywhere and out of any religion. These religions and castes barely matters when it comes to online dating sites.

really fast, Easy and convenient: At the first, Dating platforms might seem to be a daunting process, [url=https://charmdatescamreviews.wordpress.com/2018/03/19/charmdate-review-why-should-i-date-ukrainian-girls-how-charmdate-protects-me/]online dating ukraine[/url] But in real it is a simple and efficient process to register and connect with people all around the globe. The only thing you need to do is creating an eye catchy and appealing profile mentioning all needed details about you, Your hobbies and your fascinates. Its speedy and convenient access makes it a must have platform for those busy corporate out there.

Less pressing: This is one of the best platforms especially for the people who are shy or nervous as they can connect with people they find interesting via chats unless they get familiar enough with them to either have a verbal talk or start with dating in person. It gives you relaxed atmosphere, Where you can take out efficient time to think to understand and what you want to say to proceed ahead with the conversation.

Meet lots more people: This platform gives user a numerous choices to select from and also it is possible that you can connect with many people altogether and you can find sometimes a person who can be a great friend and a person who can be eligible to be your partner in the future time. This platform will allow you to pick the best one out of many with whom you think you can share your interests with.

add on a Deeper Level: This online site help you know a person back to front. The only appearance you have of your mate is his profile picture, Else you have to know it with the help of the chat you have with him. this can help you evaluate a person behind his face, numerous experts judge who these persons are truly are. Such dating platforms leave you unbiased to be love someone you share similar interests with.

Full Disclosure: The online dating sites allow you to specify whatever is your expectation and intention, Right right from the start so that you can find people looking for the same things and interests as of yours. The major benefit of all such platform is that it helps preventing misunderstandings and disappointments.

fee: Last but not the cheapest, Cost saving is the most appealing benefit of online dating because real life dates are expensive. You need to hangout with your partner every weekend and you further have to spend money either on food or night-life or both.

These platforms therefore gives you enable you to get to know the person well in advance through these online portals and thereafter you should spend money on real dates. different, On the very first meet even you must spend money with no surety that you will like the person as a partner or not.
Sep 19, 2021 @ 12:12 pm
Hey ... Im looking a man..
I love sex. Here are my erotic photos - is.gd/bPOmnQ
Sep 27, 2021 @ 2:14 pm
Hello !! Im looking a lover...
I dream of hard sex! Write me - tinyurl.com/yjefe8mm
Sep 30, 2021 @ 5:17 pm
Hey baby.. my name is Kelly...
I love oral sex! Write me - is.gd/sTu2T8
Oct 3, 2021 @ 5:05 am
Fill out the form and win a FREE \$500 or \$1000 voucher! - tinyurl.com/ygvk79dz
Oct 4, 2021 @ 6:18 pm
Hello dear!!! Im looking a man!
I dream of hard sex! Write me - is.gd/gPWpcf
Oct 7, 2021 @ 6:18 pm
Hi baby... my name Diane!!!
I love sex. Here are my erotic photos - tinyurl.com/yghegmr2
Oct 10, 2021 @ 7:07 am
Hey dear.. Im looking a man...
I want sex! Write me - is.gd/MvyEhY
Oct 19, 2021 @ 7:07 am
hallo baby!! Im looking a lover!!
I dream of hard sex! Write me - tinyurl.com/yjs64g36
Oct 27, 2021 @ 3:15 pm
Hello dear! my name is Evelyn..
If you want to meet me, I'm here - tinyurl.com/ydun3hp3
Nov 5, 2021 @ 9:09 am
hey baby. my name Lauren!!!
I love oral sex! Write me - tinyurl.com/ygqxenap
Nov 14, 2021 @ 10:22 pm
hallo baby.. my name Mary!
Do you want to see a beautiful female body? Here are my erotic photos - tinyurl.com/yhtxq5lg
Dec 19, 2021 @ 11:23 pm
Hi dear!! Im looking a man!
I want sex! Here are my photos - is.gd/M7qBFG
Dec 27, 2021 @ 2:02 am
hallo !! my name Megan!
I love oral sex! Write me - chilp.it/d870a00
Jan 12, 2022 @ 10:10 am
Hey baby!!! Im looking a man!
I love sex. Write me - u.to/j-bKGw
Jan 22, 2022 @ 1:13 pm
I can agree with Judyhb in this topic. Her name may really be Evelyn, but she choosed another nickname out of shame. Kind of sad, Evelyn is a nice name..
Also, I want sex! Don't have any photos though :/
Sep 3, 2022 @ 7:19 pm
Good write ups. With thanks! https://definitionessays.com/ degree thesis
May 7, 2023 @ 4:16 pm
How Are You

Hello, I wish for to subscribe for this webpage to get most recent updates, thus where can i do it please help out.

https://cutt.ly/x55XjOQ

Best Regards
Sep 22, 2023 @ 11:11 am
hallo baby! Im looking a lover!
If you want to meet me, I'm here - is.gd/CZZI2g
Pan Afuki
Dec 25, 2023 @ 12:12 pm
Matt Mahoney is the trashcan matt or trashcan man. "MY LIFE FOR YOU FLAGG!". We will do the FAGGY PANTS and follow it up with RLE. A close second is Albert Reddit's GAY GZIP, or GAY ZIP, or simply ARZ. We do the faggy pants and it go like this and like that and do the RLE and there we are.