Databases Reference
In-Depth Information
Fractal Compression
There are several different ways to approach the topic of fractal compression. Our approach
is to use the idea of fixed-point transformation. A function
f
(
·
)
is said to have a fixed point
x
0
if
f
(
x
0
)
=
x
0
. Suppose we restrict the function
f
(
·
)
to be of the form
ax
+
b
. Then, except
for when
a
=
1, this equation always has a fixed point:
ax
0
+
b
=
x
o
b
⇒
x
0
=
(36)
1
−
a
This means that if we want to transmit the value of
x
0
, we can instead transmit the values of
a
and
b
and obtain
x
0
at the receiver using (
36
). We do not have to solve this equation to
obtain
x
0
. Instead, we can take a guess at what
x
0
should be and then refine the guess using
the recursion
x
(
n
+
1
)
0
ax
(
n
)
0
=
+
b
(37)
Example18.6.1:
Suppose that instead of sending the value
x
0
2, we send the values of
a
and
b
as 0.5 and
1.0. The receiver starts out with a guess for
x
0
as
x
(
0
)
=
=
1. Then
0
x
(
1
)
0
ax
(
0
)
0
=
+
=
.
b
1
5
x
(
2
)
0
ax
(
1
)
0
=
+
b
=
1
.
75
x
(
3
)
0
ax
(
2
)
0
=
+
b
=
1
.
875
x
(
4
)
0
ax
(
3
)
0
=
+
=
.
b
1
9375
x
(
5
)
0
ax
(
4
)
0
=
+
b
=
1
.
96875
x
(
6
)
0
ax
(
5
)
0
=
+
b
=
1
.
984375
(38)
and so on. As we can see, with each iteration we come closer and closer to the actual
x
0
value of 2. This would be true no matter what our initial guess was, at least for this type of
function.
Thus, the value of
x
0
is accurately identified by specifying the fixed-point equation. The
receiver can retrieve the value either by the solution of (
36
) or via the recursion (
37
).
Let us generalize this idea. Suppose that for a given image
(treated as an array of
I
integers), there exists a function
f
(
·
)
such that
f
(
I
)
=
I
. If it is cheaper in terms of bits
to represent
f
(
·
)
than it is to represent
, we can treat
f
(
·
)
as the compressed representation
I
of
.
This idea was first proposed byMichael Barnsley and Alan Sloan [
246
] based on the idea of
self-similarity. Barnsley and Sloan noted that certain natural-looking objects can be obtained
as the fixed point of a certain type of function. If an image can be obtained as a fixed point of
I
