23-05-2012, 11:25 AM
Fractal Image Compression
[attachment=22813]
ABSTRACT
This paper gives and introduction on Image Coding based on Fractals and
develops a simple algorithm to be used as a reference design.
The Fractal Coding System described in this project was developed from
the ideas proposed by Arnaud Jacquin in his paper published in IEEE
Trans. “Image Coding Based on Fractal Theory of Iterated Contractive
Image Transformation”
Two implementations of the proposed Fractal Encoding Technique have
been developed. One using an ELF TMS320C31 board from SPOX by
Rahmi Hezar (PhD student at Georgia Institute of Technology) and the
second using MATLAB DSP Simulator by Alex Candela (Field Application
Engineer at Texas Instruments)
1. Introduction
With the advance of the information age the need for mass information storage and fast
communication links grows. Storing images in less memory leads to a direct reduction in
storage cost and faster data transmissions. These facts justify the efforts, of private
companies and universities, on new image compression algorithms.
Images are stored on computers as collections of bits (a bit is a binary unit of information
which can answer “yes” or “no” questions) representing pixels or points forming the
picture elements. Since the human eye can process large amounts of information (some
8 million bits), many pixels are required to store moderate quality images. These bits
provide the “yes” and “no” answers to the 8 million questions that determine the image.
Most data contains some amount of redundancy, which can sometimes be removed for
storage and replaced for recovery, but this redundancy does not lead to high
compression ratios. An image can be changed in many ways that are either not
detectable by the human eye or do not contribute to the degradation of the image.
The standard methods of image compression come in several varieties. The current
most popular method relies on eliminating high frequency components of the signal by
storing only the low frequency components (Discrete Cosine Transform Algorithm). This
method is used on JPEG (still images), MPEG (motion video images), H.261 (Video
Telephony on ISDN lines), and H.263 (Video Telephony on PSTN lines) compression
algorithms.
Fractal Compression was first promoted by M.Barnsley, who founded a company based
on fractal image compression technology but who has not released details of his
scheme. The first public scheme was due to E.Jacobs and R.Boss of the Naval Ocean
Systems Center in San Diego who used regular partitioning and classification of curve
segments in order to compress random fractal curves (such as political boundaries) in
2 Literature Number: BPRA065
two dimensions [BJ], [JBJ]. A doctoral student of Barnsley’s, A. Jacquin, was the first to
publish a similar fractal image compression scheme [J].
2. What is Fractal Image Compression?
Imagine a special type of photocopying machine that reduces the image to be copied by
half and reproduces it three times on the copy (see Figure 1). What happens when we
feed the output of this machine back as input? Figure 2 shows several iterations of this
process on several input images. We can observe that all the copies seem to converge
to the same final image, the one in 2©. Since the copying machine reduces the input
image, any initial image placed on the copying machine will be reduced to a point as we
repeatedly run the machine; in fact, it is only the position and the orientation of the
copies that determines what the final image looks like.
Input Image Output Image
Feed Back loop
Figure 1: A copy machine that makes three reduced copies of the input image [Y]
The way the input image is transformed determines the final result when running the
copy machine in a feedback loop. However we must constrain these transformations,
with the limitation that the transformations must be contractive (see contractive box), that
is, a given transformation applied to any two points in the input image must bring them
closer in the copy. This technical condition is quite logical, since if points in the copy
were spread out the final image would have to be of infinite size. Except for this condition
the transformation can have any form.
In practice, choosing transformations of the form
w
x
y
a
c
b
d
x
y
e
f i
i
i
i
i
i
i
é
ë ê
ù
û ú
=
é
ë ê
ù
û ú
é
ë ê
ù
û ú
+
é
ë ê
ù
û ú
(1)
is sufficient to generate interesting transformations called affine transformations of the
plane. Each can skew, stretch, rotate, scale and translate an input image.
An Introduction to Fractal Image Compression 3
A common feature of these transformations that run in a loop back mode is that for a
given initial image each image is formed from a transformed (and reduced) copies of
itself, and hence it must have detail at every scale. That is, the images are fractals. This
method of generating fractals is due to John Hutchinson [H], and more information about
the various ways of generating such fractals can be found in books by Barnsley and
Peitgen, Saupe, and Jurgens [P1, P2].
Initial Image First Copy Second Copy Third Copy
Figure 2: The first three copies generated on the copying machine Figure 1. [Y]
Barnsley suggested that perhaps storing images as collections of transformations could
lead to image compression. His argument went as follows: the image in Figure 3 looks
complicated yet it is generated from only 4 affine transformations.
4 Literature Number: BPRA065
Figure 3: Fractal Fern
Each transformation wi is defined by 6 numbers, ai, bi, ci, di, ei, and fi , see eq(1), which do
not require much memory to store on a computer (4 transformations x 6 numbers /
transformations x 32 bits /number = 768 bits). Storing the image as a collection of pixels,
however required much more memory (at least 65,536 bits for the resolution shown in
Figure 2). So if we wish to store a picture of a fern, then we can do it by storing the
numbers that define the affine transformations and simply generate the fern whenever
we want to see it. Now suppose that we were given any arbitrary image, say a face. If a
small number of affine transformations could generate that face, then it too could be
stored compactly. The trick is finding those numbers.
Contractive Transformations
A transformation w is said to be contractive if for any two points P1, P2, the distance
d(w(P1),w(P2) ) < sd(P1,P2)
for some s < 1, where d = distance. This formula says the application of a contractive
map always brings points closer together (by some factor less than 1).
The Contractive Mapping Fixed Point Theorem
This theorem says something that is intuitively obvious: if a transformation is contractive
then when applied repeatedly starting with any initial point, we converge to a unique fixed
point.
If X is a complete metric space and W: X®X is contractive, then W has a unique
fixed point ½W½.
An Introduction to Fractal Image Compression 5
This simple looking theorem tells us how we can expect a collection of transformations to
define an image.
[b]3. Why the name “Fractal”
The image compression scheme describe later can be said to be fractal in several
senses. The scheme will encode an image as a collection of transforms that are very
similar to the copy machine metaphor. Just as the fern has detail at every scale, so does
the image reconstructed from the transforms. The decoded image has no natural size, it
can be decoded at any size. The extra detail needed for decoding at larger sizes is
generated automatically by the encoding transforms. One may wonder if this detail is
“real”; we could decode an image of a person increasing the size with each iteration, and
eventually see skin cells or perhaps atoms. The answer is, of course, no. The detail is
not at all related to the actual detail present when the image was digitized; it is just the
product of the encoding transforms which originally only encoded the large-scale
features. However, in some cases the detail is realistic at low magnifications, and this
can be useful in Security and Medical Imaging applications. Figure 4 shows a detail from
a fractal encoding of “Lena” along with a magnification of the original.
4. How much Compression can Fractal achieve?
The compression ratio for the fractal scheme is hard to measure since the image can be
decoded at any scale. For example, the decoded image in Figure 3 is a portion of a 5.7
to 1 compression of the whole Lena image. It is decoded at 4 times it’s original size, so
the full decoded image contains 16 times as many pixels and hence this compression
ratio is 91.2 to 1. This many seem like cheating, but since the 4-times-later image has
detail at every scale, it really is not.
[attachment=22813]
ABSTRACT
This paper gives and introduction on Image Coding based on Fractals and
develops a simple algorithm to be used as a reference design.
The Fractal Coding System described in this project was developed from
the ideas proposed by Arnaud Jacquin in his paper published in IEEE
Trans. “Image Coding Based on Fractal Theory of Iterated Contractive
Image Transformation”
Two implementations of the proposed Fractal Encoding Technique have
been developed. One using an ELF TMS320C31 board from SPOX by
Rahmi Hezar (PhD student at Georgia Institute of Technology) and the
second using MATLAB DSP Simulator by Alex Candela (Field Application
Engineer at Texas Instruments)
1. Introduction
With the advance of the information age the need for mass information storage and fast
communication links grows. Storing images in less memory leads to a direct reduction in
storage cost and faster data transmissions. These facts justify the efforts, of private
companies and universities, on new image compression algorithms.
Images are stored on computers as collections of bits (a bit is a binary unit of information
which can answer “yes” or “no” questions) representing pixels or points forming the
picture elements. Since the human eye can process large amounts of information (some
8 million bits), many pixels are required to store moderate quality images. These bits
provide the “yes” and “no” answers to the 8 million questions that determine the image.
Most data contains some amount of redundancy, which can sometimes be removed for
storage and replaced for recovery, but this redundancy does not lead to high
compression ratios. An image can be changed in many ways that are either not
detectable by the human eye or do not contribute to the degradation of the image.
The standard methods of image compression come in several varieties. The current
most popular method relies on eliminating high frequency components of the signal by
storing only the low frequency components (Discrete Cosine Transform Algorithm). This
method is used on JPEG (still images), MPEG (motion video images), H.261 (Video
Telephony on ISDN lines), and H.263 (Video Telephony on PSTN lines) compression
algorithms.
Fractal Compression was first promoted by M.Barnsley, who founded a company based
on fractal image compression technology but who has not released details of his
scheme. The first public scheme was due to E.Jacobs and R.Boss of the Naval Ocean
Systems Center in San Diego who used regular partitioning and classification of curve
segments in order to compress random fractal curves (such as political boundaries) in
2 Literature Number: BPRA065
two dimensions [BJ], [JBJ]. A doctoral student of Barnsley’s, A. Jacquin, was the first to
publish a similar fractal image compression scheme [J].
2. What is Fractal Image Compression?
Imagine a special type of photocopying machine that reduces the image to be copied by
half and reproduces it three times on the copy (see Figure 1). What happens when we
feed the output of this machine back as input? Figure 2 shows several iterations of this
process on several input images. We can observe that all the copies seem to converge
to the same final image, the one in 2©. Since the copying machine reduces the input
image, any initial image placed on the copying machine will be reduced to a point as we
repeatedly run the machine; in fact, it is only the position and the orientation of the
copies that determines what the final image looks like.
Input Image Output Image
Feed Back loop
Figure 1: A copy machine that makes three reduced copies of the input image [Y]
The way the input image is transformed determines the final result when running the
copy machine in a feedback loop. However we must constrain these transformations,
with the limitation that the transformations must be contractive (see contractive box), that
is, a given transformation applied to any two points in the input image must bring them
closer in the copy. This technical condition is quite logical, since if points in the copy
were spread out the final image would have to be of infinite size. Except for this condition
the transformation can have any form.
In practice, choosing transformations of the form
w
x
y
a
c
b
d
x
y
e
f i
i
i
i
i
i
i
é
ë ê
ù
û ú
=
é
ë ê
ù
û ú
é
ë ê
ù
û ú
+
é
ë ê
ù
û ú
(1)
is sufficient to generate interesting transformations called affine transformations of the
plane. Each can skew, stretch, rotate, scale and translate an input image.
An Introduction to Fractal Image Compression 3
A common feature of these transformations that run in a loop back mode is that for a
given initial image each image is formed from a transformed (and reduced) copies of
itself, and hence it must have detail at every scale. That is, the images are fractals. This
method of generating fractals is due to John Hutchinson [H], and more information about
the various ways of generating such fractals can be found in books by Barnsley and
Peitgen, Saupe, and Jurgens [P1, P2].
Initial Image First Copy Second Copy Third Copy
Figure 2: The first three copies generated on the copying machine Figure 1. [Y]
Barnsley suggested that perhaps storing images as collections of transformations could
lead to image compression. His argument went as follows: the image in Figure 3 looks
complicated yet it is generated from only 4 affine transformations.
4 Literature Number: BPRA065
Figure 3: Fractal Fern
Each transformation wi is defined by 6 numbers, ai, bi, ci, di, ei, and fi , see eq(1), which do
not require much memory to store on a computer (4 transformations x 6 numbers /
transformations x 32 bits /number = 768 bits). Storing the image as a collection of pixels,
however required much more memory (at least 65,536 bits for the resolution shown in
Figure 2). So if we wish to store a picture of a fern, then we can do it by storing the
numbers that define the affine transformations and simply generate the fern whenever
we want to see it. Now suppose that we were given any arbitrary image, say a face. If a
small number of affine transformations could generate that face, then it too could be
stored compactly. The trick is finding those numbers.
Contractive Transformations
A transformation w is said to be contractive if for any two points P1, P2, the distance
d(w(P1),w(P2) ) < sd(P1,P2)
for some s < 1, where d = distance. This formula says the application of a contractive
map always brings points closer together (by some factor less than 1).
The Contractive Mapping Fixed Point Theorem
This theorem says something that is intuitively obvious: if a transformation is contractive
then when applied repeatedly starting with any initial point, we converge to a unique fixed
point.
If X is a complete metric space and W: X®X is contractive, then W has a unique
fixed point ½W½.
An Introduction to Fractal Image Compression 5
This simple looking theorem tells us how we can expect a collection of transformations to
define an image.
[b]3. Why the name “Fractal”
The image compression scheme describe later can be said to be fractal in several
senses. The scheme will encode an image as a collection of transforms that are very
similar to the copy machine metaphor. Just as the fern has detail at every scale, so does
the image reconstructed from the transforms. The decoded image has no natural size, it
can be decoded at any size. The extra detail needed for decoding at larger sizes is
generated automatically by the encoding transforms. One may wonder if this detail is
“real”; we could decode an image of a person increasing the size with each iteration, and
eventually see skin cells or perhaps atoms. The answer is, of course, no. The detail is
not at all related to the actual detail present when the image was digitized; it is just the
product of the encoding transforms which originally only encoded the large-scale
features. However, in some cases the detail is realistic at low magnifications, and this
can be useful in Security and Medical Imaging applications. Figure 4 shows a detail from
a fractal encoding of “Lena” along with a magnification of the original.
4. How much Compression can Fractal achieve?
The compression ratio for the fractal scheme is hard to measure since the image can be
decoded at any scale. For example, the decoded image in Figure 3 is a portion of a 5.7
to 1 compression of the whole Lena image. It is decoded at 4 times it’s original size, so
the full decoded image contains 16 times as many pixels and hence this compression
ratio is 91.2 to 1. This many seem like cheating, but since the 4-times-later image has
detail at every scale, it really is not.