{'fraction_non_alphanumeric': 0.05395921419737107, 'fraction_numerical': 0.01702764115396784, 'mean_word_length': 3.7949248379533858, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
How to Transform and Filter Images using Iterated Function Systems

We present a general theory of fractal transformations and show how it leads to a new type of method for filtering and transforming digital images. This work substantially generalizes earlier work on fractal tops. The approach involves fractal geometry, chaotic dynamics, and an interplay between discrete and continuous representations. The underlying mathematics is established and applications to digital imaging are described and exemplified.

1. Introduction. Fractal transformations are mappings between pairs of attractors of iterated function systems. They are defined with the aid of code space structures, and can be quite simple to handle and compute. They can be applied to digital images when the attractors are rectangular subsets of R 2 . They are termed "fractal" because they can change the box-counting, Hausdorff, and other dimensions of sets and measures upon which they act. In this paper we substantially generalize and develop the theory and we illustrate how it may be applied to digital imaging. Previous work was restricted to fractal transformations defined using fractal tops.
Fractal tops were introduced in [2] and further developed in [5,6,7,11]. The main idea is this: given an iterated function system with a coding map and an attractor, a section of the coding map, called a tops function, can be defined using the "top" addresses of points on the attractor. Given two iterated function systems each with an attractor, a coding map, and a common code space, a mapping from one attractor to the other can be constructed by composing the tops function, for the first iterated function system, with the coding map for the second system. Under various conditions the composed map, from one attractor to the other, is continuous or a homeomorphism. In the cases of affine and projective iterated function systems, practical methods based on the chaos game algorithm [8] are feasible for the approximate digital computation of such transformations. Fractal tops have applications to information theory and to computer graphics. They have been applied to the production of artwork, as discussed for example in [4], and to real-time image synthesis [18]. In the present paper we extend the theory and applications.
Much of the material in this paper is new. The underlying new idea is that diverse sections of a coding map may be defined quite generally, but specifically enough to be useful, by associating certain dynamical systems with the iterated function system. These sections provide novel collections of fractal transformations; by their means we generalize the theory and applications of fractal tops. We establish properties of fractal transformations, including conditions under which they are continuous. The properties are illustrated by examples related to digital imaging.
A notable result, Theorem 5.3, states the existence of nontrivial fractal homeomorphisms between attractors of some affine overlapping iterated function systems. The proof explains how to construct them. An example of one of these new homeomorphisms, applied to a picture of Lena, is illustrated in Figure 1.1.
In Section 2 we review briefly the key definitions and results concerning pointfibred iterated function systems on compact Hausdorff spaces. Since this material is not well-known, it is of independent interest. The main result is Theorem 2.4. This can be viewed as a restatement of some ideas in [13]; it describes the relationship between the coding map and the attractor of a point-fibred iterated function system.
In Section 3 we define, and establish some general properties of, fractal transformations constructed using sections of coding maps. In Theorem 3.2 we present some general properties of coding maps. Then we use coding maps to define fractal transformations and, in Theorem 3.4, we provide sufficient conditions for a fractal transformation to be continuous or homeomorphic.
In Section 4 we define two different types of section of a coding map: (i) with the aid of a masked dynamical system; and (ii) with the aid of fractal tops. Theorem 4.3 establishes the connection between the masked dynamical system and a masked section of the coding map. Theorem 4.5 includes a statement concerning the relationship between the masked section to the coding map and the shift map. Here we also establish the relationship between fractal tops and masked systems. A key result, Theorem 4.7, gives a condition under which the ranges of different masked sections intersect in a set of measure zero. This enables the approximate storage of multiple images in a single image, as illustrated in Figure 5.7.
In Section 5 we apply and illustrate the theoretical structures of Sections 2,3, and 4, in the context of digital imaging. Our goal is to illustate the diversity of imaging techniques that are made feasible by our techniques, and to suggest that fractal transformations have a potentially valuable role to play in digital imaging. In Section 5.1 we illustrate how fractal transformations may be applied to image synthesis, that is to making artificial interesting and even beautiful pictures. Specifically we explain how the technique of color-stealing [2] extends to masked systems. In Section 5.2 we apply fractal homeomorphisms, using Theorem 3.4, to transform digital images, for image beautification, roughening, and special effects; in particular, we present and illustrate Theorem 5.3 which extends the set of known affine fractal homeomophisms. In Section 5.3 we consider the idea of composing a fractal transformation, discretization, and the inverse of the transformation to make idempotent image filters. In Section 5.4 we apply Theorem 4.7 to the approximate storage or encryption of multiple images in a single image. In Section 5.5 we provide a second technique for combining several images in one: it combines invariant measures of a single iterated function system with several sets of probabilities, to make a single "encoded" image: approximations to the original images are revealed by the application of several fractal homeomorphisms.
2. Point-fibred iterated function systems. Let X be a nonempty compact Hausdorff space, and let K(X) be the set of nonempty compact subsets of X. It is known that K(X) endowed with the Vietoris topology is a compact Hausdorff space, see for example [14,Theorem 2.3.5,p.17]. This encompasses the well-known fact that if X is a compact metric space then K(X) endowed with the Hausdorff metric is a compact metric space. Let I = {1, 2, ...N } be a finite index set with the discrete topology. Let {f i : X → X|i ∈ I} be a sequence of continuous functions. Following [2], is called an iterated function system over X.
Following [13, Definition 4.1.4, p.84] we define a map Π : for all sequences σ = σ 1 σ 2 σ 3 ... belonging to I ∞ . The map is well-defined because Π(σ) is the intersection of a nested sequence of nonempty compact sets. The following definition is based on [13, Definition 4.3.6, p.97]. Definition 2.1. Let F := (X; f 1 , . . . f N ) be an iterated function system over a compact Hausdorff space X. If Π(σ) is a singleton for all σ ∈ I ∞ then F is said to be point-fibred, and the coding map of F is defined by where A ⊂ X denotes the range of π.
Theorem 2.2, due to Kieninger, plays a central role in this paper. It generalizes a classical result of Hutchinson [10] that applies when X is a compact metric space and each f ∈ F is a contraction.
Theorem 2.2. Let I ∞ have the product topology. If F is a point-fibred iterated function system on a compact Hausdorff space X then the coding map π : I ∞ → A is continuous.
Proof. This follows from [13,Proposition 4.3.22, p.105]. We define By slight abuse of notation we use the same symbol F for the iterated function system, the maps that it comprises, and the latter function. We define F 0 = i X , the identity map on X, and F k = F • F k−1 for k = 1, 2, ... . The following definition is a natural generalization of the notion of an attractor of a contractive iterated function system, see for example [15, definition on p.1193 and Theorem 11.1, p.1206], [13, p.107], and also [8]. Definition 2.3. Let F be an iterated function system on a compact Hausdorff space X. An attractor of F is A ∈ K(X) with these properties: for all B ⊂ U with B ∈ K(X). (The limit is with respect to the Vietoris topology on The relationship between coding maps and attractors is provided by noting that for a ∈ X. This leads to the following theorem. Theorem 2.4. If F is a point-fibred iterated function system on a compact Hausdorff space X then (i) F : K(X) → K(X) has a unique fixed-point A ∈ K(X), i.e. F (A) = A; (ii) A is the unique attractor of F; (iii) A is equal to the range of the coding map π, namely A = π(I ∞ ); (iv) the basin of A is X; Proof. This follows from [13, Proposition 4.4.2, p.107, see also Proposition 3.4.4, p.77].
The following remark tells us that if an iterated function system possesses an attractor then it is point-fibred when restricted to a certain neighborhood of the attractor. Necessary and sufficient conditions for an iterated function system of projective transformations to possess an attractor are given in [9].
Remark 2.5. Let A be an attractor of an iterated function system F on a compact Hausdorff space X, and let B be the basin of A. Then, following [15], F defines an iterated closed relation r := {(x, f (x)) : x ∈ X, f ∈ F} ⊂ X × X, and A is an attractor of r. By [15, Theorem 7.2, p.1193] there exists a compact neighborhood V of A such that A ⊂ Int X (V ) and F (V ) ⊂ Int X (V ). (Int X (S) denotes the interior of the set S ⊂ X in the subspace topology induced on S by X.) It follows that Definition 2.6. Let F be a point-fibred iterated function system on a compact Hausdorff space. The set I ∞ is called the code space of F. A point σ ∈ I ∞ is called an address of π(σ) ∈ A.
In the rest of this paper the underlying space X is a compact Hausdorff space. Also in the rest of this paper the symbols F, G, H denote point-fibred iterated function systems on compact Hausdorff spaces. We will say that an iterated function system is injective when all of the maps that it comprises are injective. We will say that an iterated function system is open when all of the maps that it comprises are open.

Fractal transformations.
Here we present a generalized theory of fractal transformations and establish some continuity properties. Fractal transformations are defined using sections of coding maps. We are concerned with continuity properties; for example, Theorem 3.4 (i) provides a sufficient condition for a fractal transformation to be continuous.
Definition 3.1. Let π : I ∞ → A be the coding map of F. A subset Ω ⊂ I ∞ is called an address space for F if π(Ω) = A and π| Ω : Ω → A ⊂ X is one-to-one. The corresponding map is called a section of π.
Theorem 3.2 summarises the properties of sections of π. Theorem 3.2. Let F = (X; f 1 , f 2 , ..., f N ) be a point-fibred iterated function system on a compact Hausdorff space, with attractor A, code space I ∞ , and coding map π : (ii) By Theorem 2.2 π : I ∞ → A is continuous. It follows that τ −1 = π| Ω : Ω → A is continuous.
(vi) Suppose that A is connected and A is not a singleton. It follows that Ω is not a singleton. It follows that Ω is not connected. (Since Ω contains more than one point and is a subset of I ∞ , which is totally disconnected when it contains more than one point, it follows that Ω is not connected.) Now suppose τ : A → Ω is continuous. Then τ is a homeomorphism. It follows that A is not connected. But A is connected. So τ : A → Ω is not continuous.
In Definition 3.3 we define a type of transformation between attractors of iterated function systems by composing sections of coding maps with coding maps. We call these transformations "fractal" because they can be very rough; specific examples demonstrate that the graphs of these transformations, between compact manifolds, can possess a non-integer Hausdorff-Besicovitch dimension.
.., g N ) be a point-fibred iterated function system over a compact Hausdorff space Y. Let A G be the attractor of G. Let π G : I ∞ → A G be the coding map of G. The corresponding fractal transformation is defined to be In Theorem 3.4 we describe some continuity properties of fractal transformations. These properties make fractal transformations interesting for applications to digital imaging.
Theorem 3.4. Let F and G be point-fibred iterated function systems as in Defi- It follows by a well-known theorem in topology, see for example [16,Proposition 7.4,p. 195 (ii) Assume that Ω G = Ω F is an address space for G, and that, whenever σ, ω ∈ Ω F , π F (σ) = π F (ω) ⇐⇒ π G (σ) = π G (ω). Then by (i) both of the mappings Remark 3.5. Suppose that the equivalence relations ∼ F and ∼ G on I ∞ , induced by π F : I ∞ → A G and π G : I ∞ → A G respectively, are the same. Then it is well known that, using compactness, the quotient topological space See [1] for discussion of relationships between the topology of an attractor and the equivalence class structure induced by a coding map.

Construction of sections of π.
In order to construct a fractal transformation we need to specify a section of π. In order to construct a section of π we have to construct an address space Ω; that is, we need to specify one element from each of the sets in the collection {π −1 (x) : x ∈ A}. To do this in a general way seems to be difficult; for example, if is non-denumerable for all x ∈ O. However there are two particular related methods. These methods yield interesting structure; for example, in both cases the resulting address space Ω ⊂ I ∞ is mapped into itself by the shift operator, see Theorem 4.5 (ii). They are as follows.
(a) (Masked iterated function system method.) This method requires that F is injective. Define a dynamical system on T : A F → A F with the aid of inverses of the functions in F. Follow orbits of T to define τ F : A F → Ω F ; in effect one uses a Markov partition associated with T to define Ω F .
(b) (Fractal tops method.) Use the dictionary order relation on I ∞ to select a unique element of π −1 (x) for each x ∈ A F . This method applies when F is not required to be injective. When F is injective, it is a special case of (a). To date, the fractal tops method seems to be the easiest to convert to computational algorithms and applications.
. This enable us, in Definition 4.2, to define an associated dynamical system on the attractor.
Definition 4.2. Let {M i : i ∈ I} be a mask for an injective point-fibred iterated function system F with attractor A. The associated masked dynamical system for F is Theorem 4.3 associates a unique section of π with a masked dynamical system. Theorem 4.3. Let F be an injective point-fibred iterated function system with attractor A. Let T : A → A be a masked dynamical system for F, associated with Then We begin by proving that, for all K ≥ 1 and j = 1, 2, ..., K − 1, we have Hence equation 4.1 is true for j = J + 1. This completes the induction on j.
It follows that Definition 4.4. Let F be an injective point-fibred iterated function system. The address space Ω M ⊂ I ∞ provided by Theorem 4.3 is called a masked address space for F. The corresponding section of π, say τ : A → Ω M , is called a masked section of π.
Masked address spaces and masked sections have all of the properies of address spaces and sections, such as those in Theorem 3.2, and associated fractal transformations have the properties in Theorem 3.4. But these objects have additional properties that derive from the existence and structure of the masked dynamical system. Some of these additional properties are described in Theorem 4.5. (iii) the following diagram commutes Similarly, for any given K, there is n K such that T p (x (n) ) ∈ M σp for all p ≤ K and all n ≥ n K . It follows that, for any given K, σ (n) p = σ p for all p ≤ K and all n ≥ n K . It follows that σ (n) ∞ n=1 converges to σ, i.e. τ x (n) ∞ n=1 converges to τ (x). It follows that τ : A → Ω M is continuous at x.
To prove the converse we assume that it is not true that T k−1 (x) ∈ Int A (M τ (x) k ) for all k = 1, 2, ... . It follows that there is some Here as in the first part of the proof, we write τ (x) = σ = σ 1 σ 2 σ 3 .... It follows that there is a sequence {y j } ∞ j=1 that converges to T K (x) with It follows that τ : A → Ω M is not continuous. The desired conclusion follows at once.
We remark that masked dynamical systems are related to Markov partitions in the theory of dynamical systems. See for example [12,Proposition 18.7.8,p.595].
In general a masked dynamical system T : A → A depends on the mask M. By suitable choice of mask we can sometimes obtain a dynamical system with a desired feature such as continuity, or which relates the iterated function system to a known dynamical system, as illustrated in the following example.
x ∈ M 2 is continuous. This is the well-known one-parameter tent map dynamical system, see for example [12, Exercise 2.4.1, p.78]. We note that, for any x ∈ (0, 1) there exist a positive integer n such that T k (x) ∈ 2t−1 2t 2 , 1 2t for all k ≥ n (see Fig. 4.1). As a consequence, if Λ denotes the set of masked addresses of points in 2t−1 2t 2 , 1 2t then the masked address space for F is Theorem 4.7 concerns the relationship between masked address spaces corresponding to distinct masks. It has an application to packing multiple images into a single image, as illustrated in Example 5.7.
Theorem 4.7. Let F be a point-fibred iterated function system with attractor A. Let T : A → A be a masked dynamical system for F corresponding to mask M. Let µ be a measure on A. Let M be a mask for F such that Let τ M and τ M be the masked sections of π corresponding to M and M . Then

(b)
The fractal tops method. "Fractal tops" is the name we use to refer to the mathematics of tops functions, tops code spaces, tops dynamical systems, and associated fractal transformations; see for example [6,7]. Here we show that, in the case where F is injective, fractal tops arise as a special case of masked iterated function systems. Specifically, a tops code space is a special case of masked address space, a tops function is a special case of a section of π, and a tops dynamical system is a special case of a masked dynamical system. The computations associated with fractal tops tend to be less complicated than those for masked systems.
Define a dictionary ordering (see for example [17, p.26]) on I ∞ as follows: if σ, ω ∈ I ∞ , σ = ω, then where k is the least index for which σ k = ω k , for all σ, ω ∈ I ∞ . With this ordering, every subset of I ∞ possesses a greatest lower bound and a least upper bound. Since π : I ∞ → A ⊂ X is continuous and I ∞ is compact, π −1 (x) = {σ ∈ I ∞ : π(σ) = x} possesses a unique largest element, max π −1 (x), for each x ∈ A. This allows us to define an address space Ω ⊂ I ∞ for F by The corresponding section of π is If F is injective then the tops dynamical system is a masked dynamical system, corresponding to the mask defined by The fact that τ (x) can be computed from the set π −1 (x) without reference to other points on the orbit of x simplifies the computation of τ (x) in applications, see for example [5,6]. Note that we can use the orbits of a tops dynamical system to calculate the top address of any point x ∈ A according to τ (x) = σ 1 σ 2 ... where Define a picture to be a function of the form where C is a color space. The set D is the domain of the picture. We are concerned with situations where D is a subset of an attractor of an iterated function system. Let F be an injective iterated function system with attractor A ⊂ R 2 . Let F be an iterated function system with attractor A ⊂ R 2 and the same code space I ∞ as for F. Let M be a mask for F and let τ M be the corresponding section of π −1 . Let π be the coding map for F . Then we can define a mapping Φ from the space of pictures on A into the space of pictures on A according to We refer to this procedure as color-stealing because colors from the picture P are mapped onto the attractor A to define the new picture P = Φ M (P ).
It follows from Theorem 4.5 (i) that the transformation π • τ M is continuous at all points x ∈ A whose orbits lie in A\ ∪ ∞ k=0 F k (∪ i∈I ∂M i ), where ∂M i denotes the boundary of M i . In some cases, such as those in Example 5.1, ∪ ∞ k=0 F k (∪ i∈I ∂M i ) is a set of Lebesgue measure zero, so the transformation is continuous almost everywhere. This explains patches of similar colors tends to exist in pictures that are obtained by color-stealing from real world photos, where patches of similar colors occur for physical reasons.
Example 5.1. Figure 5.1 illustrates color-stealing using (i) fractal tops (left), and (ii) a masked iterated function system (right) that is not a tops system. The picture B from which colors are stolen is Lena embedded in a black surround, shown in the middle panel. In (i) F is an affine iterated function system whose attractor A is a filled square, the domain of B , such that {f i (A )} 4 i=1 is a set of tiles that tile A by rectangles. In (i) F is the projective iterated function system (RP 2 ; f 1 , f 2 , f 3 , f 4 ), where f n (x, y) = ( a n x + b n y + c n g n x + h n y + j n , d n x + e n y + k n g n x + h n y + j n ) for n = 1, 2, 3, 4; n a n b n c n d n e n k n g n h n j  and F is an affine IFS whose attractor is a filled square; see also [5, p.2]. In (ii) the iterated function system F and mask M are the same as in Example 5.5, while F is a perturbed version of G in Example 5.5.

Fractal homeomorphisms for image beautification, roughening, and special effects. Under the conditions of Theorem 3.4 (ii) the fractal transformation
T F G is a homeomorphism. Such homeomorphisms can be applied to pictures to yield new pictures that have the same topological properties as the original. For example the connectivity properties of the set defined by a particular color will be preserved, as will be the property that certain colors lie in an arbitrary neighborhood of a point. But geometrical properties, such as Hausdorff dimension and collinearity, may not be preserved and, indeed, may be significantly changed.
Techniques for constructing and computing fractal homeomorphisms using fractal tops, with projective, affine, and bilinear IFSs, have been discussed in [2,5,6,7,18]. Families of fractal homeomorphisms, built from such transformations in R 2 , may be established by using code space arguments. Typically, the attractors of the iterated function systems in question are non-overlapping, which simplifies the proofs: in some situations one only needs to show that the equivalence classes of addresses agree on certain straight line segments. The resulting families of transformations are described by a finite sets of real parameters. These parameters may be adjusted to achieve desired effects such as increased roughness, or continuous (but non-differentiable) transformation from a meaningless picture into a meaningful one. Both of these effects are illustrated in Example 5.2.
Example 5.2. This transformation acts affinely on any straight line that is parallel to either the xaxis or the y-axis. For example, if B| AB : AB → P Q is the restriction to AB of B and if Q : R 2 → R 2 is the affine function defined by Q(x, y) = P + x(Q − P ) + y(S − P ), The four quadrilaterals IEAH, IEBF, IGCD, IGDH, define four bilinear transformations and a corresponding iterated function system whose attractor is a filled square. Provided that the quadrilaterals are close enough to quadrants of the square, the iterated function systems is point-fibred. then Q| AB = B| AB . Sufficient conditions for a bilinear iterated function system to be point-fibred are given in [7]. Each homeomorphism in Figure 5.3 is generated using a pair of iterated function systems of the form in Figure 5.2; each such pair has the same address structure.
The following theorem provides practical sufficient conditions for a bilinear IFS to be hyperbolic.
It is more difficult to establish conditions under which pairs of masked overlapping iterated function systems, built from geometrical functions such as affines on R 2 , yield homeomorphisms. In order to establish that a pair of masked iterated function systems provides a fractal transformation that is a homeomorphism, it is necessary to establish that the two masked address spaces agree. Interesting non-trivial cases involve overlapping iterated function systems, and cannot be reformulated as fractal tops. A beautiful family of such examples is provided by Theorem 5. Proof. This is an outline. Let = [0, 1] 2 ⊂ R 2 . Define affine transformations by x + y ≤ 1} and S + = R 2 \S − . We consider the dynamical system This possesses a "repeller", a compact set R ⊂ , such that In order to define R, we define R is well-defined because it is the intersection of a decreasing sequence of nonempty compact sets. (It is quite easy to see that R is the graph of a monotone function from  . This shows approximations, in shades of grey, to the "repeller" R of the dynamical system Q : R 2 → R 2 described in the outline proof of Theorem 5.3. An escape-time algorithm, similar to the ones discussed in [3,Ch. 7], was used to make this image, with a = 2/3 and b = 1/2. These statements imply the theorem. Remark 5.4. Clearly essentially the same result and proof applies for any analogous pair of overlapping strictly increasing functions on [0, 1]. Figure 5.4 illustrates the "repeller". It is a subset of the attractor of the iterated function system ( ; (ax, by), (bx + 1 − b, ay + 1 − a)), and may be used to compute p * as illustrated in Figure 5 . Then, by Theorem 5.3, there is a value of p = p * ∈ ( 1 2 , 2 3 ), such that the condition in Theorem 3.4 (ii) holds, and if p = p * then T F G : X → X then is a homeomorphism. The value of p * is where A * ⊂ X is the attractor of H := (X; ( 2 3 x, 1 2 y), ( 1 2 x + 1 2 , 2 3 y + 1 3 )) illustrated in Figure 5

Application to image filtering.
Here we restrict attention to iterated function systems defined on X = [0, 1] 2 ⊂ R 2 . We are concerned with fractal transformations from [0, 1] 2 to itself, associated with a pair of iterated function systems of the form We suppose that A F = A G = [0, 1] 2 . In applications to digital imaging, [0, 1] 2 is discretized. Here we refer to the the locations of pixels as discretized coordinates. We suppose that discretized versions of A F and A G have resolutions r F and r G respectively.
Let P F : A F → A F be a projection operator, namely a function with the property P F • P F (x) = P F (x) for all x ∈ A F . For example, If T F G : A F → A G is a homeomorphism between the non-discretized spaces then A trivial but instructive example is provided by choosing F and G to be the same, with N = 4 and f 1 (x, y) = (0.5x, 0.5y), f 2 (x, y) = (0.5x + 0.5, 0.5y), f 3 (x, y) = (0.5x + 0.5, 0.5y + 0.5), f 4 (x, y) = (0.5x, 0.5y + 0.5).
If r F = r G /2 then P G is the filter that corresponds to downsampling followed by doubling the width and height of each pixel.
Example 5.6. Let X= {(x, y) ∈ R 2 |0 ≤ x, y ≤ 1}, p ∈ (0, 1), q = 1 − p, and h 1 (x, y) = (px, py), h 2 (x, y) = (qx + p, py), h 3 (x, y) = (qx + p, qy + p), h 4 (x, y) = (px, qy + p). The family of IFSs H p := (X; h 1 , h 2 , h 3 , h 4 ) has attractor X and address structure that is independent of p ∈ (0, 1). If we set F = H 0.5 and G = H 0.6 then T F G : X→X is a homeomorphism. The result of applying the fractal homeomorphism T F G to a digital (512 × 512) picture of Lena (left) is illustrated in the middle panel of Figure 5.6. In effect the middle image is obtained by composing a projection P F , onto a 512 × 512 pixel grid, with T F G . The image on the right is the result of applying T GF to the middle image. that is, the right-hand image is the result of applying the projection operator, that we may refer to as a "fractal filter", T GF • P F • T F G to the original Lena.
5.4. Application to packing multiple images into a single image. Suppose we have a collection of masks {M j } on A such that the conditions of Lemma 4.7 are holds true for any pair of masks. Let the second iterated function system F be such that almost all points of the attractor A have a unique address. Thus by Lemma 4.7 for almost all x ∈ A and j = k. Therefore we can consider the collection of pictures Φ Mj (B ) as an almost disjoint fractal decomposition of the picture B .
This leads us to the following trick. By means of fractal transformations we map different pictures to different almost disjoint components of B . By inverting the transformations we retrieve (approximations to) the original pictures, as illustrated in the following example. and G = ( , f 1 (x, y) = (y, 0.5(1 − x)), f 2 (x, y) = (y, 0.5 + 0.5x)).
We define a family of masks for F by is the attractor of both systems. We denote the corresponding masked fractal transformation T F G : → by T  5.5. Measure theory image packing. Here we describe a different method for encoding several images within a single image. The method strives to create a single image that is simultaneously "homeomorphic", under different fractal transformations, to several different given images. An example of such a single "encoded" image is shown in the middle panel of Figure 5.8; two different fractal homeomorphisms applied to it (but in the digital realm) yield the images on the right and the left. The underlying idea is that different invariant measures, belonging to the same iterated function system, but associated with different probabilities, are mutually "singular continuous", and are concentrated on different sets, albeit they have the same support. The method uses the chaos game algorithm, both to encode and decode.
Consider for example the IFS F = ([0, 1]; f 1 (x) = 0.5x, f 2 (x) = 0.5x + 0.5). If we associate probabilities p 1 = 0.5 and p 2 = 0.5 with f 1 and f 2 respectively, then the associated Markov operator has invariant probability measure µ equal to uniform Lebesgue measure supported on [0, 1], concentrated on the set of points whose binary expansions contain equal proportions of zeros and ones. On the other hand, if we associate probabilities p 1 = 0.1 and p 2 = 0.9, then the associated Markov operator has invariant probability measure µ that is also supported on [0, 1], but singular continuous and concentrated on the set of points whose binary expansions contain nine times as many ones as zeros. Hence, if the chaos game is applied to F using the first set of probabilities, the points of the resulting random orbit will tend to be disjoint from those obtained by of applying the chaos game using the second set of probabilities. The precise manner in which the orbits of the two systems concentrate is governed by convergence rates associated with the central limit theorem. The same idea can be applied to "store" several images in a single image E: a stored image is retrieved by applying the appropriate fractal transformation to E.
The goal is to "store" two standard digital color images, Pepper and Lena, each 512 × 512, in a single color image E, also 512 × 512 . The image E is supported on and associated with two probability measures, µ H and µ H , invariant under H with probabilities P and P respectively.
(1) In order to "encode" Pepper, we run a coupled chaos game algorithm with F associated with Pepper, supported on a copy of , and H associated with E, with (supposedly) i.i.d. probabilities P ; that is, we compute a random sequence of points {(X k , Z k ) ∈ × : k = 0, 1, 2, ...K} where K = 10 6 , where X 0 = (0, 0) ∈ (associated with Pepper) and Z 0 = (0, 0) ∈ (associated with E) and X k = f σ k (X k−1 ), Z k = h σ k (Z k−1 ) for k = 1, 2, ..., K, where σ k = i with probability p i . At each step the pixel containing Z k in the (initially blank) image E is plotted in the color of Pepper at the pixel containing X k . At the end of this process E consists of an "encoded" version of Pepper.
(2) In order to "encode" Lena, we again run a coupled chaos game algorithm with G associated with Lena, supported on a copy of , and H associated with E (already "painted" with an encoding of Pepper) with probabilities P ; that is, we compute a sequence of points {(Y k , Z k ) ∈ × : k = 0, 1, 2, ...K} where K = 500, 000, where Y 0 = (0, 0) ∈ (associated with Lena) and Z 0 = (0, 0) ∈ (associated with E) and Y k = f σ k (Y k−1 ), Z k = h σ k ( Z k−1 ) for k = 1, 2, ..., K, where σ k = i with probability p i . At each step the pixel containing Z k in the image E is plotted in the color of Lena at the pixel containing Y k . (The pixel is overwritten by the latest colour value.) We have used half as many iterations in the encoding of Lena as we did for Pepper, because a proportion of the points that correspond to Pepper are overwritten by points corresponding to Lena.
An image E that is a realization of steps (1) and (2) is shown in the central panel of Figure 5 In practice, to obtain the decoded images, shown on the left and right hand sides of Figure 5.8, we use the chaos game algorithm again, as follows.
(3) In order to "decode" Pepper, we run a coupled chaos game algorithm, with probabilities P, with F associated with an image (initially blank), supported on a copy of , and H associated with E (now encoding both Pepper and Lena). That is, we compute a random sequence of points {(X k , Z k ) ∈ × : k = 0, 1, 2, ...K} where K = 10 6 , where X 0 = (0, 0) ∈ (associated with Pepper) and Z 0 = (0, 0) ∈ (associated with E) and X k = f σ k (X k−1 ), Z k = h σ k (Z k−1 ) for k = 1, 2, ..., K, where σ k = i with probability p i . At each step the pixel containing X k in the (initially blank) copy of is plotted in the color of E at the pixel containing Z k . The result of such a decoding, starting from the encoded E illustrated in the middle panel, is shown in the left panel in Figure 5.8.
(4) In order to decode Lena, we run a coupled chaos game algorithm, with probabilities P , with G associated with an image (initially blank but to become the decoded image), supported on a copy of , and H associated with E. That is, we compute a random orbit {(Y k , Z k ) ∈ × : k = 0, 1, 2, ...K} where K = 10 6 , where Y 0 = (0, 0) ∈ (associated with Pepper) and Z 0 = (0, 0) ∈ (associated with E) and Y k = f σ k (X k−1 ), Z k = h σ k ( Z k−1 ) for k = 1, 2, ..., K, where σ k = i with probability p i . At each step the pixel containing Y k in the (initially blank) copy of is plotted in the color of E at the pixel containing Z k . The result of following this decoding algorithm, starting from the encoded E in the middle panel, is shown in the left panel in Figure 5.8.