A Charitable Research Foundation Devoted to Education, Consumer Protection, Scientific Advancement and Freedom...

  document Index | first magazine Section | main Archives

                                 ÿabout donations þ join H home ª media i about ( contact   

Fractals and Benoit Mandelbrot  

A Computer Science Discovery often considered kin to Prime Numbers.


Fractals are a very important discovery of an astute mathematician at IBM, one Benoit Mandelbrot. In 1977, Mandelbrot found that certain mathematical formula can define a shape which when displayed, appears to contain smaller representations of itself similar in nature (geometry and shape) within itself. His analysis of why this occurred lead to a series of calculations that allow images to be created that have virtually infinite self-definition, the more you zoom in on them, the more detail is exposed bearing strong similarity to the image that contains them.

Fractals themselves, are visually stimulating to look at. The picture to the right is called a "Mandelbrot".  However, their ability to carry or modify data is extremely useful to computer science in encoding, decoding, and ciphers.  For example, by using Fractal Geometry Mathematics, one can reduce a fairly complex image shape down to a very small, compressed object which if later is decompressed, sufficiently resembles the original shape, that it is recognizable by the human mind with considerable accuracy.

If that process is done to a series of still images in a video stream, when recomposed and played back in the same sequences as the original video, will resemble the original video they were composed of sufficiently, to allow the human mind to grasp the content despite the distortion of the image that ultimately takes place during the process.

One company, Fractal Geometries, in the mid 90's, teamed up with what today is known as Real Networks, to adapt this technology so as to create video that could play back along a single 33.6 to 56K bit per second dial up stream, when such were popular on the Internet, and DSL and Cable were not yet caught on.

While the playback was not very high quality when viewed at the low speeds of a 56K or slower modem line, combining it with progressive scan compression and motion detection compression, a realistic representation of an original 60 FPS NTSV Television Video was able to be transmitted at approximately 53KBPS to a user of Real Player, admittedly at about half speed and poor quality (but not much worse than early TV back in the 30's and 40's).

Early Bell Laboratories studies were able to transmit video at 1MHz across three pairs of copper wire, however it required over 3 seconds to accumulate a single still frame at a time.  Later studies in the Video Compression Lab at AT&T Bell Labs in Crawford Corners, NJ, found that using two 56K (128KBPS) Digital ISDN lines, a video signal could be sent at 5-12.5 frames per second, using the early Bell Picturephone type device as a source as well as other video devices and advanced data compression technology.  Not having this 128K Digital throughput in the average 48-53KBPS Trellis Coded LZW compressed Dial Up telephone line to the Internet, the adaptation of fractal compression (which searches for similarities within video images) made it possible to watch a somewhat distorted image at as low as 28KBPS, leading to eventual adoption of video as a medium that could be watched across the Internet, even using slow modem driven lines.  The presentation below, a lecture by Benoit Mandelbrot at MIT, uses an adaptation of Mendelbrot's Fractals to display MPEG-2 Video, particularly visible in the Low Speed 56K Transmission link.

It was this breakthrough which led Real Networks into the marketplace with a commercially viable player for low speed line use when viewing Television, in the mid 90's. Thus, the competition to dominate the Desktop Internet Video Marketplace was born, in a competition between Real Player, Microsoft Media Player, Apple Quicktime Player and various other companies. 

Discovering this ability in Fractals and incorporating the method into a compression algorithm, gave Real an early lead by enabling snail like dial up telephone lines to play back digital video which ordinarily might require 440KBPS or faster signals..  But, as in all things, Mandelbrot's discovery was not purely an invention, just an observation based on the prior work of someone in the uses of fractal mathematics.  That exercise, of all things, was strongly brought to bear by Code Breakers trying to decode messages, used by the early Decoders group at the famed Cryptology Lab at Bletchley Park in England during WWII.

Scientists who migrated to America from Germany after the war who came to work for IBM, stumped by how Allies had managed to decode German radio transmissions successfully, leading to Nazi Germany's defeat, had commissioned studies at IBM in its Yorktown Heights research center to examine various methods for encoding, decoding, encrypting and decrypting information.  Byproduct to that secret study, Benoit Mandelbrot stumbled on to the use of certain equations such as the series invented by Gaston Julia, called the "Julia Set" which is based on the form: z^2 + c, where c is a complex constant with real and imaginary numbers in representing shapes. This, after lengthy experimentation, led to the mathematical exposure of Fractals at IBM for the very first time since same was first explored by the Code Breakers in the 1940's.

This occurred decades after it had surfaced in England for use examining German radio transmissions looking for details that would escape normal filtering methods, using the famed British COLOSSUS computers, invented by Sir Thomas Flowers, the inventor of the Programmable Electronic Computer.  It is ironic that some have suggested that those who commissioned the study at IBM were trying to figure out how it was all done, since methods like that don't become obsolete, particularly if kept a secret long enough. 

Ironic because during WWII, IBM was, covertly, Nazi Germany's primary provider of computation and tabulation technology. Germany was defeated, in part, by the discoveries made by the British Mathematicians and Codebreakers at Bletchley Park and the Colossus Computers invented by Sir Thomas Flowers that made it possible to perform such calculations thousands of times faster than the human mind was able.  While the discovery of Fractals helped illuminate one of the many angles that led to Nazi Germany's defeat, science today still hasn't figured out the vast majority of the secrets, which have been kept a secret since 1941. Some have breathed a sigh of relief that IBM has not made much progress in that area.


Was IBM's Mandelbrot the inventor of Fractals?
Answer: No, not really.

No, not exactly.  British cartographers trying to map the English Coastline, noted in early King's history, that there was a peculiar phenomenon that occurred as they tried to create more and more detailed maps for the King.  As they charted the coastline, they noted in their records that the closer in they zoomed to include more and more details in minutia on larger maps of each coastal segment, when they measured the length of the British coast, it got longer and longer, as a result of the inclusion of more irregular details.  This phenomenon was unknown to mankind, and became the object of many mathematical theories of the era.  For, how could the coastline some 5000+ miles long, measure 8000 miles or even longer, the more they zoomed in on it? 

Unknowingly, British Mathematicians had discovered one of the key aspects of a fractal: the more you zoom in on its detail, the more details emerge.  This is unlike the average photograph, which tends to loose detail as one zooms in on it, due to its fixed resolution nature. You can see an example of this loss of detail by using any of the Aerial Photo View Mapping systems on the Internet, that let you zoom in on any address.  The closer you get, the less detail, unlike in the case of a Fractal, and unlike in the case of the King's cartographers and their own notation regarding the byproduct of more detailed, larger maps.

Later on, the French mathematician Gaston Julia discovered even more characteristics regarding what have since become known as Fractal Mathematical Polynomial Equation Sets (or Julia and Mandelbrot Sets). He wondered what a complex polynomial function would look like visually, such as the ones named after him (z^2 + c, where c is a complex constant with real and imaginary numbers) if recursed upon itself until it achieved a certain level, if colored and plotted in space.

His idea translated as follows.  One takes the x and y coordinates of a point in space, and assign them to z as in x + y*i, where i is the square root of negative one (a non-real number). Then: squaring this number, and add c as a constant. Then insert the resulting pair of real and imaginary numbers recursively back into z, performing the whole equation over and over, again and again.  If you keep doing that until the result is greater than a certain magnitude number: the number of times one must execute the formula to get it to leave it's own "orbit" can be assigned a color.  Turn the point (x, y) that was calculated that assigned color, unless the resulting coordinates are not yet out of their own orbit, in which case make it black. The results: a very visually interesting shape which, as you expand it, displays more and more details that resemble the original shape.

Mandelbrot studied Julia Sets and notes of the King's Cartographers, as a byproduct of research that was being driven by notes that were released when Britain declassified Project MK-Ultra, at Bletchley Park, in the mid 70's, and even though only scant bits of information were released to the public, these two led Mandelbrot to discover the very interesting effects of Fractals, later more fully exemplified by Mathematicians and Computer Graphics Artists all around the world. 

For information about Mandelbrot, kindly watch this 1 hour 20 minute lecture:

220K/Second Broadband version:
BENOIT MANDELBROT Lecturing on Self Similarity and Fractals and Science, Engineering and Finance (roughness and beauty) at MITWORLD in November 2001

56K (Dial up Version):
http://mfile.akamai.com/12800/rm/mitworld.download.akamai.com/12800/mitw-mandelbrot-27nov01-56k.ram

<- Requires REAL PLAYER (which, of course, uses Mandelbrot's discovery!)


download Real by clicking on
the link above. You will need
to register with REAL NETWORKS


Examples of Fractals.

The Julia Set.  Gaston Julia created a very interesting phenomenon with his unique recursive polynomial evaluation of real and imaginary numbers.  Here is an interesting video zoom in on a Julia Set, which continues to expose similarity details as it drills down inside of the visual. 
  CLICK HERE TO VIEW IT >

Spanky.  Noel Griffin, on the Canadian Laboratory of Particle Physics has collected an enormous library of Fractal Related Images and trivia. 
  CLICK HERE TO GO THERE >

DataCompression. DataCompression has compiled a study of Fractals and their relationship to different disciplines in compression of data streams in computer science.
  CLICK HERE TO GO THERE >

SummerSoft's Lavendar-C - Data Encryption using Fractal Mathematics
  CLICK HERE TO GO THERE >

Fractal Merkel Trees as apply to Data Encryption from "RSAC"
  CLICK HERE TO GO THERE >

Fractals and Physics by Volkhard Normeier
  CLICK HERE TO GO THERE >


Fractals used in Video Compression Acceleration.

Subject: [77] Introduction to Fractal compression (long)
SOURCE: http://www.faqs.org/faqs/compression-faq/part2/

Written by John Kominek <kominek@links.uwaterloo.ca>

Seven things you should know about Fractal Image Compression
(assuming that you want to know about it).

   1. It is a promising new technology, arguably superior to JPEG --
      but only with an argument.
   2. It is a lossy compression method.
   3. The fractals in Fractal Image Compression are Iterated Function
      Systems.
   4. It is a form of Vector Quantization, one that employs a virtual
      codebook.
   5. Resolution enhancement is a powerful feature but is not some
      magical way of achieving 1000:1 compression.
   6. Compression is slow, decompression is fast.
   7. The technology is patented.

That's the scoop in condensed form. Now to elaborate, beginning with a little
background.


 A Brief History of Fractal Image Compression
 -----------------------------------------------

The birth of fractal geometry (or rebirth, rather) is usually traced to IBM
mathematician Benoit B. Mandelbrot and the 1977 publication of his seminal
book The Fractal Geometry of Nature. The book put forth a powerful thesis:
traditional geometry with its straight lines and smooth surfaces does not
resemble the geometry of trees and clouds and mountains. Fractal geometry,
with its convoluted coastlines and detail ad infinitum, does.

This insight opened vast possibilities. Computer scientists, for one, found a
mathematics capable of generating artificial and yet realistic looking landscapes,
and the trees that sprout from the soil. And mathematicians had at
their disposal a new world of geometric entities.

It was not long before mathematicians asked if there was a unity among this
diversity. There is, as John Hutchinson demonstrated in 1981, it is the branch
of mathematics now known as Iterated Function Theory. Later in the decade
Michael Barnsley, a leading researcher from Georgia Tech, wrote the popular
book Fractals Everywhere. The book presents the mathematics of Iterated Functions
Systems (IFS), and proves a result known as the Collage Theorem. The
Collage Theorem states what an Iterated Function System must be like in order
to represent an image.

This presented an intriguing possibility. If, in the forward direction, fractal
mathematics is good for generating natural looking images, then, in the
reverse direction, could it not serve to compress images? Going from a given
image to an Iterated Function System that can generate the original (or at
least closely resemble it), is known as the inverse problem. This problem
remains unsolved.

Barnsley, however, armed with his Collage Theorem, thought he had it solved.
He applied for and was granted a software patent and left academia to found
Iterated Systems Incorporated (US patent 4,941,193. Alan Sloan is the co-
grantee of the patent and co-founder of Iterated Systems.)  Barnsley announced
his success to the world in the January 1988 issue of BYTE magazine. This
article did not address the inverse problem but it did exhibit several images
purportedly compressed in excess of 10,000:1. Alas, it was not a breakthrough.
The images were given suggestive names such as "Black Forest" and "Monterey
Coast" and "Bolivian Girl" but they were all manually constructed. Barnsley's
patent has come to be derisively referred to as the "graduate student algorithm."

Graduate Student Algorithm
   o Acquire a graduate student.
   o Give the student a picture.
   o And a room with a graphics workstation.
   o Lock the door.
   o Wait until the student has reverse engineered the picture.
   o Open the door.

Attempts to automate this process have met little success. As Barnsley admitted
in 1988: "Complex color images require about 100 hours each to encode and
30 minutes to decode on the Masscomp [dual processor workstation]." That's 100
hours with a _person_ guiding the process.

Ironically, it was one of Barnsley's PhD students that made the graduate
student algorithm obsolete. In March 1988, according to Barnsley, he arrived
at a modified scheme for representing images called Partitioned Iterated
Function Systems (PIFS). Barnsley applied for and was granted a second patent
on an algorithm that can automatically convert an image into a Partitioned
Iterated Function System, compressing the image in the process. (US patent
5,065,447. Granted on Nov. 12 1991.) For his PhD thesis, Arnaud Jacquin imple-
mented the algorithm in software, a description of which appears in his land-
mark paper "Image Coding Based on a Fractal Theory of Iterated Contractive
Image Transformations." The algorithm was not sophisticated, and not speedy,
but it was fully automatic. This came at price: gone was the promise of
10,000:1 compression. A 24-bit color image could typically be compressed from
8:1 to 50:1 while still looking "pretty good." Nonetheless, all contemporary
fractal image compression programs are based upon Jacquin's paper.

That is not to say there are many fractal compression programs available.
There are not. Iterated Systems sell the only commercial compressor/decompressor,
an MS-Windows program called "Images Incorporated." There are also an
increasing number of academic programs being made freely available. Unfortunately,
these programs are -- how should I put it? -- of merely academic quality.

This scarcity has much to do with Iterated Systems' tight lipped policy about
their compression technology. They do, however, sell a Windows DLL for programmers.
In conjunction with independent development by researchers else-
where, therefore, fractal compression will gradually become more pervasive.
Whether it becomes all-pervasive remains to be seen.

Historical Highlights:
   1977 -- Benoit Mandelbrot finishes the first edition of The Fractal
           Geometry of Nature.
   1981 -- John Hutchinson publishes "Fractals and Self-Similarity."
   1983 -- Revised edition of The Fractal Geometry of Nature is
           published.
   1985 -- Michael Barnsley and Stephen Demko introduce Iterated
           Function Theory in "Iterated Function Systems and the Global
           Construction of Fractals."
   1987 -- Iterated Systems Incorporated is founded.
   1988 -- Barnsley publishes the book Fractals Everywhere.
   1990 -- Barnsley's first patent is granted.
   1991 -- Barnsley's second patent is granted.
   1992 -- Arnaud Jacquin publishes an article that describes the first
           practical fractal image compression method.
   1993 -- The book Fractal Image Compression by Michael Barnsley and Lyman
           Hurd is published.
        -- The Iterated Systems' product line matures.
   1994 -- Put your name here.


 On the Inside
 --------------

The fractals that lurk within fractal image compression are not those of the
complex plane (Mandelbrot Set, Julia sets), but of Iterated Function Theory.
When lecturing to lay audiences, the mathematician Heinz-Otto Peitgen introduces
the notion of Iterated Function Systems with the alluring metaphor of a
Multiple Reduction Copying Machine. A MRCM is imagined to be a regular copying
machine except that:

  1. There are multiple lens arrangements to create multiple overlapping
     copies of the original.
  2. Each lens arrangement reduces the size of the original.
  3. The copier operates in a feedback loop, with the output of one
     stage the input to the next. The initial input may be anything.

The first point is what makes an IFS a system. The third is what makes it
iterative. As for the second, it is implicitly understood that the functions
of an Iterated Function Systems are contractive.

An IFS, then, is a set of contractive transformations that map from a defined
rectangle of the real plane to smaller portions of that rectangle. Almost
invariably, affine transformations are used. Affine transformations act to
translate, scale, shear, and rotate points in the plane. Here is a simple
example:


     |---------------|              |-----|
     |x              |              |1    |
     |               |              |     |
     |               |         |---------------|
     |               |         |2      |3      |
     |               |         |       |       |
     |---------------|         |---------------| 


                           Before                                                         After

     Figure 1. IFS for generating Sierpinski's Triangle.

This IFS contains three component transformations (three separate lens ar-
rangements in the MRCM metaphor). Each one shrinks the original by a factor of
2, and then translates the result to a new location. It may optionally scale
and shift the luminance values of the rectangle, in a manner similar to the
contrast and brightness knobs on a TV.

The amazing property of an IFS is that when the set is evaluated by iteration,
(i.e. when the copy machine is run), a unique image emerges. This latent image
is called the fixed point or attractor of the IFS. As guaranteed by a result
known as the Contraction Theorem, it is completely independent of the initial
image. Two famous examples are Sierpinski's Triangle and Barnsley's Fern.
Because these IFSs are contractive, self-similar detail is created at every
resolution down to the infinitesimal. That is why the images are fractal.

The promise of using fractals for image encoding rests on two suppositions: 1.
many natural scenes possess this detail within detail structure (e.g. clouds),
and 2. an IFS can be found that generates a close approximation of a scene
using only a few transformations. Barnsley's fern, for example, needs but
four. Because only a few numbers are required to describe each transformation,
an image can be represented very compactly. Given an image to encode, finding
the optimal IFS from all those possible is known as the inverse problem.

The inverse problem -- as mentioned above -- remains unsolved. Even if it
were, it may be to no avail. Everyday scenes are very diverse in subject
matter; on whole, they do not obey fractal geometry. Real ferns do not branch
down to infinity. They are distorted, discolored, perforated and torn. And the
ground on which they grow looks very much different.

To capture the diversity of real images, then, Partitioned IFSs are employed.
In a PIFS, the transformations do not map from the whole image to the parts,
but from larger parts to smaller parts. An image may vary qualitatively from
one area to the next (e.g. clouds then sky then clouds again). A PIFS relates
those areas of the original image that are similar in appearance. Using Jac-
quin's notation, the big areas are called domain blocks and the small areas
are called range blocks. It is necessary that every pixel of the original
image belong to (at least) one range block. The pattern of range blocks is
called the partitioning of an image.

Because this system of mappings is still contractive, when iterated it will
quickly converge to its latent fixed point image. Constructing a PIFS amounts
to pairing each range block to the domain block that it most closely resembles
under some to-be-determined affine transformation. Done properly, the PIFS
encoding of an image will be much smaller than the original, while still
resembling it closely.

Therefore, a fractal compressed image is an encoding that describes:
   1. The grid partitioning (the range blocks).
   2. The affine transforms (one per range block).

The decompression process begins with a flat gray background. Then the set of
transformations is repeatedly applied. After about four iterations the attractor
stabilizes. The result will not (usually) be an exact replica of the original, but reasonably close.


 Scalelessness and Resolution Enhancement
 -------------------------------------------

When an image is captured by an acquisition device, such as a camera or scanner,
it acquires a scale determined by the sampling resolution of that device.
If software is used to zoom in on the image, beyond a certain point you don't
see additional detail, just bigger pixels.

A fractal image is different. Because the affine transformations are spatially
contractive, detail is created at finer and finer resolutions with each iteration.
In the limit, self-similar detail is created at all levels of resolution,
down the infinitesimal. Because there is no level that 'bottoms out'
fractal images are considered to be scale-less.

What this means in practice is that as you zoom in on a fractal image, it will
still look 'as it should' without the staircase effect of pixel replication.
The significance of this is cause of some misconception, so here is the right
spot for a public service announcement.

                        /--- READER BEWARE ---\

Iterated Systems is fond of the following argument. Take a portrait that is,
let us say, a grayscale image 250x250 pixels in size, 1 byte per pixel. You
run it through their software and get a 2500 byte file (compression ratio =
25:1). Now zoom in on the person's hair at 4x magnification. What do you see?
A texture that still looks like hair. Well then, it's as if you had an image
1000x1000 pixels in size. So your _effective_ compression ratio is 25x16=400.

But there is a catch. Detail has not been retained, but generated. With a
little luck it will look as it should, but don't count on it. Zooming in on a
person's face will not reveal the pores.

Objectively, what fractal image compression offers is an advanced form of
interpolation. This is a useful and attractive property. Useful to graphic
artists, for example, or for printing on a high resolution device. But it does
not bestow fantastically high compression ratios.

                        \--- READER BEWARE ---/

That said, what is resolution enhancement? It is the process of compressing an
image, expanding it to a higher resolution, saving it, then discarding the
iterated function system. In other words, the compressed fractal image is the
means to an end, not the end itself.

 The Speed Problem
 ---------------------

The essence of the compression process is the pairing of each range block to a
domain block such that the difference between the two, under an affine trans-
formation, is minimal. This involves a lot of searching.

In fact, there is nothing that says the blocks have to be squares or even
rectangles. That is just an imposition made to keep the problem tractable.

More generally, the method of finding a good PIFS for any given image involves
five main issues:
   1. Partitioning the image into range blocks.
   2. Forming the set of domain blocks.
   3. Choosing type of transformations that will be considered.
   4. Selecting a distance metric between blocks.
   5. Specifying a method for pairing range blocks to domain blocks.

Many possibilities exist for each of these. The choices that Jacquin offered
in his paper are:

   1. A two-level regular square grid with 8x8 pixels for the large
      range blocks and 4x4 for the small ones.
   2. Domain blocks are 16x16 and 8x8 pixels in size with a sub-sampling
      step size of four. The 8 isometric symmetries (four rotations,
      four mirror flips) expand the domain pool to a virtual domain
      pool eight times larger.
   3. The choices in the last point imply a shrinkage by two in each
      direction, with a possible rotation or flip, and then a translation
      in the image plane.
   4. Mean squared error is used.
   5. The blocks are categorized as of type smooth, midrange, simple
      edge, and complex edge. For a given range block the respective
      category is searched for the best match.

The importance of categorization can be seen by calculating the size of the
total domain pool. Suppose the image is partitioned into 4x4 range blocks. A
256x256 image contains a total of (256-8+1)^2  = 62,001 different 8x8 domain
blocks. Including the 8 isometric symmetries increases this total to 496,008.
There are (256-4+1)^2 = 64,009 4x4 range blocks, which makes for a maximum of
31,748,976,072 possible pairings to test. Even on a fast workstation an exhaustive
search is prohibitively slow. You can start the program before departing
work Friday afternoon; Monday morning, it will still be churning away.

Increasing the search speed is the main challenge facing fractal image compression.


 Similarity to Vector Quantization
 ---------------------------------

To the VQ community, a "vector" is a small rectangular block of pixels. The
premise of vector quantization is that some patterns occur much more frequently
than others. So the clever idea is to store only a few of these common
patterns in a separate file called the codebook. Some codebook vectors are
flat, some are sloping, some contain tight texture, some sharp edges, and so
on -- there is a whole corpus on how to construct a codebook. Each codebook
entry (each domain block) is assigned an index number. A given image, then, is
partitioned into a regular grid array. Each grid element (each range block) is
represented by an index into the codebook. Decompressing a VQ file involves
assembling an image out of the codebook entries. Brick by brick, so to speak.

The similarity to fractal image compression is apparent, with some notable
differences.
   1. In VQ the range blocks and domain blocks are the same size; in an
      IFS the domain blocks are always larger.
   2. In VQ the domain blocks are copied straight; in an IFS each domain
      block undergoes a luminance scaling and offset.
   3. In VQ the codebook is stored apart from the image being coded; in
      an IFS the codebook is not explicitly stored. It is comprised of
      portions of the attractor as it emerges during iteration. For that
      reason it is called a "virtual codebook." It has no existence
      independent of the affine transformations that define an IFS.
   4. In VQ the codebook is shared among many images; in an IFS the
      virtual codebook is specific to each image.

There is a more refined version of VQ called gain-shape vector quantization in
which a luminance scaling and offset is also allowed. This makes the similari-
ty to fractal image compression as close as can be.


 Compression Ratios
 ---------------------

Exaggerated claims not withstanding, compression ratios typically range from
4:1 to 100:1. All other things equal, color images can be compressed to a
greater extent than grayscale images.

The size of a fractal image file is largely determined by the number of trans-
formations of the PIFS. For the sake of simplicity, and for the sake of comparison
to JPEG, assume that a 256x256x8 image is partitioned into a regular
partitioning of 8x8 blocks. There are 1024 range blocks and thus 1024 trans-
formations to store. How many bits are required for each?

In most implementations the domain blocks are twice the size of the range
blocks. So the spatial contraction is constant and can be hard coded into the
decompression program. What needs to be stored are:

   x position of domain block        8     6
   y position of domain block        8     6
   luminance scaling                 8     5
   luminance offset                  8     6
   symmetry indicator                3     3
                                    --    --
                                    35    26 bits


In the first scheme, a byte is allocated to each number except for the symmetry
indicator. The upper bound on the compression ratio is thus (8x8x8)/35 =
14.63. In the second scheme, domain blocks are restricted to coordinates
modulo 4. Plus, experiments have revealed that 5 bits per scale factor and 6
bits per offset still give good visual results. So the compression ratio limit
is now 19.69. Respectable but not outstanding.

There are other, more complicated, schemes to reduce the bit rate further. The
most common is to use a three or four level quad tree structure for the range
partitioning. That way, smooth areas can be represented with large range
blocks (high compression), while smaller blocks are used as necessary to
capture the details. In addition, entropy coding can be applied as a back-end
step to gain an extra 20% or so.


 Quality: Fractal vs. JPEG
 -------------------------

The greatest irony of the coding community is that great pains are taken to
precisely measure and quantify the error present in a compressed image, and
great effort is expended toward minimizing an error measure that most often is
-- let us be gentle -- of dubious value. These measure include signal-to-noise
ratio, root mean square error, and mean absolute error. A simple example is
systematic shift: add a value of 10 to every pixel. Standard error measures
indicate a large distortion, but the image has merely been brightened.

With respect to those dubious error measures, and at the risk of over-simplification,
the results of tests reveal the following: for low compression
ratios JPEG is better, for high compression ratios fractal encoding is better.
The crossover point varies but is often around 40:1. This figure bodes well
for JPEG since beyond the crossover point images are so severely distorted
that they are seldom worth using.

Proponents of fractal compression counter that signal-to-noise is not a good
error measure and that the distortions present are much more 'natural looking'
than the blockiness of JPEG, at both low and high bit rates. This is a valid
point but is by no means universally accepted.

What the coding community desperately needs is an easy to compute error measure
that accurately captures subjective impression of human viewers. Until then, your
eyes are the best judge.
 


The Chairman's Conclusion about Fractals
  By Dr. Jack A. Shulman

In 1979, part way through the development of a flight control supercomputer system later used by the Department of Defense in a classified bomber application, I was heard to remark that I'd adapted recursive similarities since 1975, to create a self expanding system of adaptive supercomputers, which could subdivide the control of flight elements and assign them to iterative self similar subcomponents, creating a Geodesic like array of parallel computers within larger arrays of parallel computers within larger arrays of parallel computers.

It wasn't until Benoit Mandelbrot published on Fractals, that I realized that neuro-computing and the associative structure of the human brain was comprised of logic within logic arranged not unlike my supercomputers, in an array of Cognition, Abstraction, Inference and Induction micro engines, in essence, neuro-ganglial pills all arranged to create circumlocution and form a network of knowledge which had associations within it that were the same as larger associations in its outer layers that had significant self similarities contained iteratively within them to a very atomic degree. The parallels with Mandelbrot's Fractals in 1977 amazed me.  I marveled at the mind's immediate cognitive ability to instantly recognize those similarities in the wondrous spires of Fractal that the neo-Mandelbrotists were producing on computer graphics screens that zoomed in on the details within details within details endlessly.

While the Mind is perhaps not Fractal-ic per say, Fractals simultaneously trigger the Cognitive function of Similarity Recognition and Comparison in a unique, creating an almost physical stimulus regarding "beauty and roughness" to quote Mandelbrot.  The notion of iterative self similarity Mandelbrot frequently refers to (clearly, he is fascinated with the notion) does seem to apply as "a way to explain" the means that Sleep uses to recompose the short term memories into long term memories, holographically sweeping clean redundant copies of similar logic, and replacing them with references to longer term individual copies of the basic logic that applies, with weights and measurements added for good measure. Even then, Sleep's compression algorithm is also not Fractal-ic.

Nonetheless, Fractals have turned out to be a key to understanding the Cognitive functions of the mind, and even to study the patterns of correct and incorrect logical abstraction and inference, found within it, for many similarities within similarities demonstrate how the recursive nature of Human Association often is sufficiently vague or sufficiently weak, to simply allow us to draw the wrong conclusions.

Nonetheless, the mere study of Fractals, itself, is mind opening, particularly when considering how to create images of infinite self-definition, a problem such as viewing the surface of the Earth from space.  One may be able to see the shoreline, but can one see the baby horseshoe sand crabs scampering across by zooming in on the image produced by Aerial photography today?

I have a very strong belief that eventually, humanity will learn how to collect nearly infinite detail using sensor based technology, that science will progress to such a degree that eventually when we zoom in on a video image from Space, we will eventually be able to see not only the shore and the crabs, but the individual grains of sand and even the atomic structure within a single one.

And I am also of the belief that in order to store this myriad of imagery in holographic form, we are going to have to borrow heavily from the exceptional work of Benoit Mandelbrot, and that which he has inspired in others. For in my vision of the eventual nearly infinite resolution of some future orbital camera, and its metaphor looking OUT into the Universe through some form of successor to Hubble (or perhaps an upgraded Hubble ST itself?) we are talking about having to store an enormous amount of information and then, all of us will be thankful to Benoit Mandelbrot once again!

    - Dr. Jack A. Shulman, Chairman, ACSA


The above aggregation of information, pictures, and incorporated references is called an "Articulum Mosaica".  It was compiled by student interns at the ACSA, under the supervision of the office of the Chairperson who had created the original compilation.  No commercial purpose was intended for its publication, it is published here strictly for non-profit educational reasons.
 

Disclaimer:  The information on this website is presented for educational purposes only.  Information has been obtained from qualified sources who have based their assessments on the information provided them that could be confirmed.  Any inaccuracies or incorrect assertions are wholly disclaimed and unintentional.

 
Search our website or the internet:    

Google
web     ACSA

Copyright © 2005  American Computer Science Association Inc., ("ACSA") Please review our usage and legal pages listed above. In addition to traditional web presence role, this website also contains published content in a news and research format obtained from third parties, for which ACSA disclaims responsibility. ACSA is a charitable public interest research group and tax exempt private foundation under U.S. I.R.C. 501(c)3. Your donations may be exempt from federal or other taxation, however: please consult with your CPA or other Tax Counsel for further information.   General Contact: email us, or:

ATN: Andrew Vanoceur, Chairman,
General Delivery Box ACSA,
Los Alamos, New Mexico 87544-9999 USA
866-836-1932

a l w a y s   u n d e r   c o n s t r u c t i o n