Image Anal Stereol 2012;31:109-120
Original Research Paper
ON RANDOM ITERATED FUNCTION SYSTEMS WITH GREYSCALE MAPS
Matthew Demers1, Herb Kunze153*2 and Davide La Torre3
University of Guelph, Department of Mathematics & Statistics, Guelph, Ontario, Canada; 2University of Guelph, Department of Mathematics & Statistics, Guelph, Ontario, Canada; 3University of Milan, Department of Economics, Business and Statistics, Milan, Italy
e-mail: mdemers@uoguelph.ca; hkunze@uoguelph.ca; davide.latorre@unimi.it (Received January 18, 2012; revised April 27, 2012; accepted May 8, 2012)
ABSTRACT
In the theory of Iterated Function Systems (IFSs) it is known that one can find an IFS with greyscale maps (IFSM) to approximate any target signal or image with arbitrary precision, and a systematic approach for doing so was described. In this paper, we extend these ideas to the framework of random IFSM operators. We consider the situation where one has many noisy observations of a particular target signal and show that the greyscale map parameters for each individual observation inherit the noise distribution of the observation. We provide illustrative examples.
Keywords: random fixed point equations, random iterated function systems, collage theorem.
INTRODUCTION
In fractal imaging compression and coding based on Generalized Fractal Transforms (GFT), one seeks to approximate a target image or signal by the fixed points of a contractive fractal transform operator. The usual formulation involves a fixed set of geometric contraction maps along with a corresponding set of greyscale adjustment maps. The inverse problem requires one to find the best greyscale map parameters for a given target image. The solution process is referred to as "collage coding" because of the visual effect of the contraction maps; it applies the collage theorem, a simple consequence of Banach's fixed point theorem. The approximation of the target image or signal can be generated through iteration of the fractal transform (see Hutchinson, 1981; Barnsley et a I., 1985; Barnsley and Demko, 1985; Barnsley, 1989; Barnsley and Hurd, 1993; Forte and Vrscay, 1995; 1999; Iacus and La Torre, 2005b;a; Kunze et al,, 2008; La Torre et a I,, 2009; La Torre and Vrscay, 2011 for more details and applications).
In Forte and Vrscay (1995), the authors showed that one can find an iterated function system with greyscale maps (IFSM) to approximate any target signal or image with arbitrary precision, and they provided a suboptimal but systematic approach for doing so.
The goal of this paper is to extend the work in Forte and Vrscay (1995) to the framework of random IFSM operators. We consider the situation where one has many noisy observations of a particular target signal and show that the greyscale map parameters
for each individual observation inherit the noise distribution of the observation.
Prior to these results, we present several short background sections. First, we discuss the deterministic collage coding framework and quickly summarize the related IFSM setting. Then we present the random collage coding framework. Finally, we formulate the random IFSM operator framework and present some illustrative numerical examples.
FIXED POINT EQUATIONS AND COLLAGE THEOREM
In this section, we present some basic contraction map results that will be used in later sections. Let (X,dx) denote a complete metric space. Then T: X — X is contractive if there exists ace [0,1) such that
dx (Tx, Ty) < cdx {x, y) for all x, y € X . (1)
We normally refer to the infimum of all c values satisfying Eq. 1 as the contraction factor of T.
Theorem 1 (Banach): Let (X.dx) be a complete metric space. Also let T : X —> X be a contraction mapping with contraction factor c <G [0,1). Then there exists a unique leX such that x = Tx. Moreover, for any a* <g X, dx(Tnx,x) —> 0 as n —>
Theorem 2 (Continuity theorem for fixed points, Centore and Vrscay, 1994): Let (X,dx) be a complete metric space and J), I? be two contractive mappings
with contraction factors c\ and c2 and fixed points vi and y2, respectively. Then
dx(y\,yi) <
1
1 -min{ci,c2}
<fr,sup(7ï,72) (2)
where
dx,sup(Ti,T2) = supdx(T\(x), T2(x)) . (3)
xeX
Banach's fixed point theorem provides a mechanism to solve tht forward problem of the fixed point equation x = Tx: Given a contraction T, construct, or at least approximate, its fixed point x. And the continuity theorem establishes that small changes in a contraction mapping produce small changes in the associated fixed points.
A formal mathematical inverse problem associated with the fixed point equation x = Tx is: Given a target element a* and an e > 0, find a contraction map T(e) (perhaps from a suitable family of operators) with fixed point x(e) such that d{x,x{e)) < e. In the case that one is able to solve such an inverse problem to arbitrary precision, i.e., e 0, then one may identify the target x as the fixed point of a contractive operator T on X.
In practical applications, however, it is not generally possible to find such solutions to arbitrary accuracy nor is it even feasible to search for such contraction maps. Instead, one makes use of the following result, which is a simple consequence of Banach's fixed point theorem.
Theorem 3 ("Collage theorem", Barnsley et al, 1985): Let (X. d) be a complete metric space and T : X — X a contraction mapping with contraction factor c € [0,1). Then for any a* <g X,
d{x,x) < —d(x,Tx) ,
(4)
where a* is the fixed point ofT.
The approximation error d(x,x) is bounded above by the so-called collage distance d(x,Tx). Most practical methods of solving such inverse problems, for example, fractal image coding (Fisher, 1995; Lu, 2003), search for an operator T for which the collage distance is as small as possible, while ensuring that c is sufficiently far away from one. In other words, these methods seek an operator T that maps the target x as close as possible to itself. This inverse problem solution procedure, often referred to as collage coding, is most often performed by considering a parametrized
family of contraction maps Tx, A £ Ac Pi", and then minimizing the collage distance d(x. Txx).
Finally, we mention another interesting result which is a simple consequence of Banach's fixed point theorem.
Theorem 4 ("Anti-collage theorem ", Vrscay and Saupe, 1999): Let (X.d) be a complete metric space and T : X — X a contraction mapping with contraction factor c <g [0,1). Then for any a* <g X,
d{x,x) > J~^—d(x,Tx) where x is the fixed point ofT.
(5)
FORMAL SOLUTION TO THE INVERSE PROBLEM FOR ITERATED FUNCTION SYSTEMS WITH GREYSCALE MAPS
The method of iterated function systems with greyscale maps (IFSM), as formulated by Forte and Vrscay (1995), can be used to approximate a given element u of L2([0,1]). We consider the case in which u : [0,1] — [0,1] and the space
X = {u: [0,1] [0, l],u € L2[0,1]}
(6)
The ingredients of an A?-map IFSM on X are
(Forte and Vrscay, 1995; 1999)
1.	a set of N contractive mappings w = {wi,w2,...,wN}, Wi : [0,1] [0,1], satisfying the covering condition Ui=iM,;([0,1]) = [0,1], and most often affine in form:
Wi(x) = six + cii, 0 < Sj < 1, i=l,2,...,N;
(7)
2.	a set of associated functions - the greyscale maps -0 = {011021 • • • i 0n}> 0! : M —> R. Affine maps are usually employed:
0/(0 = (Xit + pi, with the conditions
a,-,ft e [0,1]
and
N
o<J>+A-< l
i= 1
(8)
(9)
Associated with the A/-map IFSM (w. (j)) is the fractal transform operator T, the action of which on a function u <G X is given by
n
(Tu)(x) = Yd'<l>M^\x))), (11) i=1
where the prime means that the sum operates on all those terms for which wt 1 is defined.
Theorem 5 (Forte and Vrscay, 1995): /': X — X and for any u,v € X we have
d2(Tu,Tv) <Cd2(u,v)	(12)
where
n !
C=£ifo,-.	(13)
i= 1
When C < 1, then T is contractive on X, implying the existence of a unique fixed point ¡1 e X such that u = Tu.
The squared collage distance function associated with an AT-map IFSM may be written as a quadratic form,
A2 =zTAz + bTz + c,	(14)
where z = (a\..../3|.... ./3/j. We observe that in the special that the sets w;([0,1]), i = 1,... ,N, are non-overlapping, for each i the values of a, and /3, that minimize A2 can be determined by solving a separate minimization problem using least squares.
The inverse problem associated with IFSM can, in principle, be solved to arbitrary accuracy, using a procedure defined in Forte and Vrscay (1995). The maps Wk are chosen from an infinite set W of fixed affine contraction maps on [0,1] which satisfy the following properties.
Definition 1 We say that W generates an m-dense and nonoverlapping family A of subsets of I if for every e > 0 and every Bel there exists a finite set of integers ik< ik> 1. 1 <k<N, such that
(i)	A = Uf=1w^(7) C B,
(ii)	m(B\A) < s, and
(Hi) m(wik(I)nwil(I))=0ifk^l, where m denotes Lebesgue measure.
Let
Wn = {wu...wn}	(15)
be the N truncations of w. Let <3> v = {¿>1..... (¡)m } be the N-vector of affine grey level maps. Let zn be the solution of the previous quadratic optimization problem and min = A%{zn)- In Forte and Vrscay (1995), the following result was proved.
Theorem 6
AN,min -^OasN^co.
Using the Collage Theorem, the inverse problem may be solved to arbitrary accuracy. A practical choice for the contraction maps w onX = [0,1] is
M'ij(x) = 2-\x + j - 1), i = 1,2,..., j = 1,2,...,2\
RANDOM FIXED POINT EQUATIONS
Let (Q,^,P) denote a probability space and (X.d) a metric space. A mapping T : Q x X —> X is called a random operator if for any x € X the function T(.,x) is measurable. A measurable mapping x : Q —> X is called a random fixed point of a random operator T if j is a solution of the equation
T(w,x{w)) =x{w) .	(16)
for a.e. a> e Q. A random operator T is called continuous (Lipschitz, contraction) if for a.e. w G Q we have that T(w,.) is continuous (Lipschitz, contraction). There are many papers in the literature that deal with such equations for single-valued and set-valued random operators (see Bharucha-Reid, 1972; Itoh, 1979; Papageorgiou, 1988; Lin, 1995; Liu, 1997; Shahzad, 2001; 2004a;b). Solutions of random fixed point equations and inclusions are usually produced by means of stochastic generalizations of classical fixed point theory.
Let	be a probability space and let
(X,dx) be a complete metric space. Let'/ : Q x X — X be a given operator. We look for the solution of the equation
T(<o,x(<o))=x(<o)	(17)
for a.e. co e Q.\A and P(A) = 0. Suppose that the operator T satisfies the inequality
d(T((o,x),T(a>,y)) < c(co)d(x,y) , (18)
where c(co) : Q —> X. When T satisfies this property, we say that T is a c(o)-Lipschitz operator. If c(co) < c < 1 a.e., with to <G Q\A and P(A) = 0 then we say that T is a c(o)-contraction. In this case for to <G Q\A there exists a unique point j(o>) <G X. It is clear that the uniqueness makes sense except for sets of measure zero. Once again, the inverse problem can be formulated as: Given a function x: Q —> X and a family of operators 7\ : Q x X —> X, find A such that x is the solution of random fixed point equation
Tx(co,x((o)) =x(a>) .	(19)
We may now state the following random analogs to Theorems 1-4.
Corollary 1 ( "Regularity conditions "): Let (Q, P) be a probability space and (X,dx) be a complete metric space. Let T : Q x X —> X be a given c(a>)-contraction. Then dx(x(a>i),j(®2)) <
JL?supd(T((Oi,x),T(a>2,x))
xeX
Corollary 2 ("Continuity Theorem"): Let (Q,^,P) be a probability space and let (X.dx) be a complete metric space. Let T\ : Q x X —> X and T2 : Q x X —> X be c\((o)- and c2(a>)-contractions respectively. Then
dx(xi((o),x2((o)) < 1
supdx(Ti(CO,x),T2((0,x)) .
l-mm{cuc2} xeX
Theorem 7 ("Collage Theorem"): Let (Q.-f.F) he a probability space and let (X,dx) be a complete metric space. Let i : Q x X — X be a given c(a>)-contraction. Then
1
l+c
dx(x[(o),T((o,x((o))) <dx(x((o),x(co)) <
1
1 — c
dx{x{co),T(co,x{co))) ,
a.e. (0 <G Q, where x(a>) is the solution ofT((o,x(a>)) = x((0).
The above described approach to deal with random fixed point equations does not guarantee, in general, the measurability of the function x : Q —> X with respect to the sigma algebra . In order to overcome this difficulty, we provide an abstract formulation of the same problem which guarantees the measurability
of J.
Recall that (X,d) is said to be a Polish space if it is a separable complete metric space. In random fixed point theory, separability plays an important role. Two important examples of Polish metric spaces which will be useful in the following are C([a,b]) and I?(\a.b\). Consider now the space Y of all measurable functions x : Q —> X. If we define the operator 7' : K — K as (Ty)(co) = T(co,x(co)) the solutions of this fixed point equation on Y are the solutions of the random fixed point equation T(co,x(co)) = x(co). Suppose that the metric dx is bounded, that is dx(x\,x2) < K for all xi,x2 € X. So the function y"(a>) = dx{xi(co),x2(co)) : Q —> R is an element of (Q) for all x\,x2 <G Q. We can then define on the space Y the following function
dY{xi,x2)= / dx(xi(o)),x2(o)))do). (20) Jn
It can be shown that the space {Y,dy) is a complete metric space. The following result holds.
Theorem 8 (Itoh, 1977): LetX be a Polish space, and T:QxX — X be a mapping such that for each co <G Q the function T(a>,.) is c((o)-Lipschitz and for each a* <g X the function T(.,x) is measurable. Let x : Q —> X be a measurable mapping; then the mapping q : Q — X defined by %(co) = T(co,x(co)) is measurable.
The previous theorem (Eq. 8) holds if T(co, •) is only continuous (see, for instance, Himmelberg, 1975).
Corollary 3 Let X be a Polish space and T : Q x X —> X be a mapping such that for each co € il the function T(a>,-) is a c(a>)-contraction. Suppose that for each x G X the function T(-,x) is measurable. Then there exists a unique solution of the equation fx = x that is T(co,x(co)) = x(co) for a.e. m <G Q.
In these results separability plays a crucial role. In fact using this hypothesis and Theorem 8 one can prove that the function %{(») = T(co,x(co)) is measurable, that is T : Y — Y. Other random fixed point theorems for contraction mappings in Polish spaces can be found in Spacek (1955); Hans (1957); Bharucha-Reid (1972). The inverse problem can be formulated as: Given a function x : Q —> X and a family of operators f-L : Y — Y find A such that x is the solution of random fixed point equation
fix = x.
that is,
Tx(m,x((o)) =x(co) .
(21)
(22)
Now, with the collage and continuity theorems, we may state the following.
Corollary 4 Let X be a Polish space and T : Q x X —> X be a mapping such that for each co <G Q the function T(a>,-) is a c(a>)-contraction. Suppose that for each x GX the function T(-,x) is measurable. Then for any x <e Y,
J I dy{x,fx) < dy{x,x) < —dy(x,fx) , (23)
where a* is the fixed point of f, that is, x(a>) := T((o,x(co)).
FORMAL SOLUTION TO THE INVERSE PROBLEM FOR RANDOM ITERATED FUNCTION SYSTEMS WITH GREYSCALE MAPS
We now formulate a Random IFSM fractal transform that is analogous to the deterministic fractal transform in Eq. 11.
Let (Q,^,P) be a probability space and consider now the following operator T :X xO^I defined by
T(o3,u) = (Tu)(x)
n i= 1
= (r«)+j3(fi>),
where ß (®) = , 'ßi(o)). That is, we suppose that the greyscale maps take the form
= out + ßi(<o) ,	(24)
where ßt are random variables with mean ¡a, and \ßi{(o)\ < 8 a.e. co e Q, and that
ok, 8 € [0,1]	(25)
with
n
0<£(a,- + S)<l.	(26)
i= 1
We randomize only the ßt parameters since the randomness in the other term of T(o3, u) is transmitted by the function u. Let
Y = {u: Q —> X, u is measurable} (27)
and consider the function
y(fi)) := dx (in (co), 112(03)) = \\ui(a>) - u2((o)\\2.
From the hypotheses it is clear that \jf{(o) € L1 (Q). We know that (Y,dy) is a complete metric space where
dy(til, 112) = / \\lll{co) — U2{co)\\2d(0 . (28) JQ.
Obviously, the function %(eo) := (T*u)(eo) + ß(eo) belongs to Y because T* is Lipschitz on X and the ß is measurable. If we define T :Y -^Y where Tu c, wc have
dY(Tui,Tu2) =
f IKr^X®) +ß(co) -(T*u2)(co)-ß((o)\\2d(o = Jn
/ \\ui(co) — U2{(0)\\2d(0 = Cdy{ui,U2) ■
JQ.
So there exists u G Y such that Tu = u, that is, 11(03) = T(03,11(03)) for a.e. 03 <G Q. That is,
ii(03,x) = (T*u(03))(x) + p(03)
n
= Y,'0Ci(u(03,wil(x))) +pi(<0) (29)
i= 1
for a.e. .v G [0,1]. The inverse problem of finding the random variables ¡$¡(03), perhaps to arbitrary accuracy, is note possible given the random nature of the problem. Instead, we suppose that the function u(o3,x) : Q x [0,1] —> R is integrable and let
u(x) = / [ll(03)}(x)d03 = / U(03,x)d03 . (30)
Jo.	Jq.
Thus Eq. 29 becomes
n
il(x) = £'od(u(wil(x))) + m . (31)
i= 1
That is, the expectation value of u(o3,x) is the solution of a deterministic A^-map IFSM on X (cf. Eq. 11). We observe in Eq. 31 another motivation for not randomizing the parameters at: the expectation of the product «,//(■) becomes complicated.
Suppose that we have N observations, u(o3\), 11(032), ..., u(03n), of the variable 11(03). Choose a set of greyscale maps, as in Eq. 15. We collage code each observation, 11(03^), k = 1,... ,n, to find the set of minimal collage parameters a^ and ¡5ik, k = 1,... ,n, i = l,...,N. As a result of our earlier discussion, if the observations differ only by a uniform additive noise factor, we expect that the distribution of the pu; parameters, k = 1 ...,n will inherit that distribution, with mean jjj.
NUMERICAL EXAMPLES
This section provides several numerical examples which illustrate the above formulation and "mean property."
Example: We define the IFS maps
M'ij(x) = 2-\x + j - 1), i = 1,... ,4, j = 1,2,... ,2'",
with associated greyscale maps <p,j(t ) = ccijt + /3( /. In this example, we consider the target function
u(x) = 0.8j2 + 0.1 .	(32)
We construct N observations of the function by adding constant noise to it:
uk(x) = u(x) + vk, k=l,...,N ,
where |v*| < 0.1 with mean zero. The picture in Fig. 1 presents ten realizations with constant and place-dependent noise.
Table 1. Grey scale map mean parameters ocij in the case of constant additive noise.
Table 2. Greyscale map mean parameters fyj in the case of constant additive noise.
coefficient
50
100
200
coefficient
50
100
200
«1,1 «1,2 «2,1 «2,2 «2,3 «2,4 «3,1 «3,2 «3,3 «3,4 «3,5 «3,6 «3,7 «3,8 «4,1 «4,2 «4,3 «4,4 «4,5 «4,6 «4,7 «4,8 «4,9 «4,10 «4,11 «4,12 «4,13 «4,14 «4,15 «4,16
0.25000 0.25732 0.06250 0.06983 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04790 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10655 0.11388
0.25000 0.25730 0.06250 0.06982 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04789 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10650 0.11390
0.25000 0.25730 0.06250 0.06982 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04789 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10650 0.11390
0U
Pi,2 02,1
02,2
02.3
02.4
03.1
03.2
03.3
03.4
03.5
03.6
03.7
03.8
04.1
04.2
04.3
04.4
04.5
04.6
04.7
04.8
04.9
04.10
04.11
04.12
04.13
04.14
04.15
04.16
0.07105 0.07157 0.08881 0.08948 0.09054 0.09200 0.09325 0.09451 0.09733 0.10171 0.10766 0.11517 0.12424 0.13487 0.09436 0.09796 0.10781 0.12391 0.14626 0.17486 0.20971 0.25081 0.29816 0.35176 0.41161 0.47771 0.55006 0.62866 0.71351 0.80461
0.07261 0.07312 0.09077 0.09142 0.09247 0.09391 0.09530 0.09655 0.09935 0.10372 0.10965 0.11715 0.12620 0.13682 0.09644 0.10002 0.10986 0.12594 0.14828 0.17686 0.21170 0.25278 0.30012 0.35371 0.41354 0.47963 0.55196 0.63055 0.71538 0.80647
0.07199 0.07250 0.08998 0.09065 0.09170 0.09315 0.09448 0.09573 0.09854 0.10292 0.10885 0.11635 0.12542 0.13604 0.09561 0.09920 0.10904 0.12513 0.14747 0.17606 0.21090 0.25200 0.29934 0.35293 0.41277 0.47886 0.55120 0.62979 0.71463 0.80573
Fig. 1. Ten realizations for constant additive noise and place-dependent additive noise.
Tables 1 and 2 presents the mean value of each greyscale map parameter obtained by collage coding the separate realizations. The calculations were performed for 50, 100, and 200 realizations, using Maple.
Tables 3 and 4 present the greyscale parameters obtained upon collage coding the mean observation
1 N
k=l
We see that, the corresponding values in the tables agree increasingly well as the number of realizations
increase. In all cases, for any fixed choices of i and
j, the value of aLJ is the same across all simulations
and across the two tables. In fractal imaging, the a
parameters represent a contrast adjustment and the ¡5
parameters represent a brightness adjustment. In this
example, the different realizations differ only by a
vertical shift, so the corresponding fractal codes differ
only in the brightness parameters. We also observe that
values in the tables agree to at least two decimal places
with the IFSM parameters for the unnoised signal,
which makes sense since the additive noise has mean
zero.
Table 3. Grey scale map parameters (Xij for the mean obsen'ation in the case of constant additive noise.
coefficient	50	100	200
«1,1	0.25000	0.25000	0.25000
«1,2	0.25730	0.25730	0.25730
«2,1	0.06250	0.06250	0.06250
«2,2	0.06982	0.06982	0.06982
«2,3	0.07715	0.07715	0.07715
«2,4	0.08447	0.08447	0.08447
«3,1	0.01562	0.01562	0.01562
«3,2	0.02295	0.02295	0.02295
«3,3	0.03028	0.03028	0.03028
«3,4	0.03760	0.03760	0.03760
«3,5	0.04493	0.04493	0.04493
«3,6	0.05226	0.05226	0.05226
«3,7	0.05958	0.05958	0.05958
«3,8	0.06691	0.06691	0.06691
«4,1	0.00391	0.00391	0.00391
«4,2	0.01124	0.01124	0.01124
«4,3	0.01857	0.01857	0.01857
«4,4	0.02590	0.02590	0.02590
«4,5	0.03323	0.03323	0.03323
«4,6	0.04056	0.04056	0.04056
«4,7	0.04789	0.04789	0.04789
«4,8	0.05523	0.05523	0.05523
«4,9	0.06256	0.06256	0.06256
«4,10	0.06989	0.06989	0.06989
«4,11	0.07722	0.07722	0.07722
«4,12	0.08455	0.08455	0.08455
«4,13	0.09188	0.09188	0.09188
«4,14	0.09921	0.09921	0.09921
«4,15	0.10650	0.10650	0.10650
«4,16	0.11390	0.11390	0.11390
Table 4. Grey scale map parameters fyj for the mean obsen'ation in the case of constant additive noise.
coefficient	50	100	200
0U	0.07105	0.07261	0.07199
01,2	0.07157	0.07312	0.07250
02,1	0.08881	0.09076	0.08998
02,2	0.08948	0.09142	0.09065
02,3	0.09054	0.09247	0.09170
02,4	0.09200	0.09391	0.09315
03,1	0.09325	0.09530	0.09448
03,2	0.09451	0.09654	0.09573
03,3	0.09733	0.09935	0.09854
03,4	0.10171	0.10372	0.10292
03,5	0.10766	0.10965	0.10885
03,6	0.11517	0.11715	0.11635
03,7	0.12424	0.12620	0.12542
03,8	0.13487	0.13682	0.13604
04,1	0.09436	0.09644	0.09561
04,2	0.09796	0.10002	0.09920
04,3	0.10781	0.10986	0.10904
04,4	0.12391	0.12594	0.12513
04,5	0.14626	0.14828	0.14747
04,6	0.17486	0.17686	0.17606
04,7	0.20971	0.21170	0.21090
04,8	0.25081	0.25278	0.25200
04,9	0.29816	0.30012	0.29934
04,10	0.35176	0.35371	0.35293
04,11	0.41161	0.41354	0.41277
04,12	0.47771	0.47963	0.47886
04,13	0.55006	0.55196	0.55120
04,14	0.62866	0.63055	0.62979
04,15	0.71351	0.71538	0.71463
04,16	0.80461	0.80647	0.80573
Example: We repeat the preceding example, this time adding place-dependent noise to produce the N realizations:
uk(x) = u(x) + Vk(x), k = l,...,N ,
where u(x) = 0.8x2 +0.1, as before, |v*-(jc)| < 0.1 for all x, and, for each fixed a\ v/+i) are samples from the
re-scaled distribution ,+(0,0.01). The right picture in Fig. 1 presents ten realizations. The results are presented in Tables 5-8, with the first table presenting the means of the greyscale map parameters obtained by collage coding the realizations separately and the second table presenting the greyscale map parameters obtained by collage coding the mean observation, u*{x).
Table 5. Greyscale map mean parameters aitj in the case of place-dependent additive noise with a normal distribution.
Table 6. Greyscale map mean parameters pi,j in the case of place-dependent additive noise with a normal distribution.
coefficient
50
100
200
coefficient
50
100
200
a1,1 a1,2 02,1
a2,2
a2,3 a2,4 a3,1 a3,2 a3,3 a3,4 a3,5 a3,6 a3,7 a3,8 a4,1 a4,2 a4,3 a4,4 a4,5 a4,6 a4,7 a4,8 a4,9
04.10
04.11
04.12
04.13
04.14
04.15
04.16
0.24783 0.25505 0.06121 0.06938 0.07708 0.08467 0.01528 0.02500 0.03001 0.03565 0.04367 0.05363 0.06107 0.06887 0.00145 0.01221 0.01686 0.02663 0.03320 0.03973 0.05133 0.05110 0.06367 0.07064 0.08009 0.08196 0.08840 0.09788 0.10892 0.11107
0.24817 0.25544 0.06223 0.07046 0.07851 0.08460 0.01578 0.02240 0.03025 0.03681 0.04528 0.05390 0.05783 0.06726 0.00175 0.00770 0.02246 0.02713 0.02775 0.03700 0.05263 0.05331 0.06415 0.07165 0.08117 0.08116 0.08420 0.09744 0.11101 0.11086
0.24656
0.25412
0.06291
0.07104
0.07958
0.08452
0.01762
0.02327
0.0279
0.03749
0.04503
0.05448
0.05697
0.06449
0.00103
0.00599
0.02139
0.02261
0.02702
0.04394
0.05698
0.05169
0.05847
0.07154
0.08127
0.08289
0.08868
0.09734
0.11136
0.10584
Pu
Pi,2 p2,1 p2,2 P2,3 P2,4 P3,1 P3,2 P3,3 P3,4 P3,5 P3,6 P3,7 P3,8 P4,1 P4,2 P4,3 P4,4 P4,5 P4,6 P4,7 P4,8 P4,9 P4,10 P4,11 P4,12 P4,13 P4,14 P4,15 P4,16
0.07567 0.07616 0.09393 0.09424 0.09511 0.09649 0.09838 0.09875 0.10234 0.10740 0.11273 0.11915 0.12841 0.13923 0.10043 0.10254 0.11348 0.12806 0.15160 0.18088 0.21230 0.25745 0.30314 0.35598 0.41463 0.48285 0.55575 0.63338 0.71795 0.81047
0.07569 0.07611 0.09383 0.09417 0.09500 0.09693 0.09843 0.09962 0.10268 0.10717 0.11245 0.11994 0.12973 0.14004 0.09999 0.10497 0.11149 0.12842 0.15332 0.18174 0.21107 0.25764 0.30231 0.35589 0.41407 0.48257 0.55723 0.63320 0.71599 0.81016
0.07636 0.07662 0.09400 0.09423 0.09509 0.09764 0.09808 0.09961 0.10412 0.10756 0.11306 0.12040 0.13083 0.14117 0.09986 0.10664 0.11200 0.13100 0.15423 0.17955 0.20814 0.25772 0.30508 0.35696 0.41363 0.48226 0.55612 0.63350 0.71530 0.81133
Table 7. Grey scale map parameters (Xij for the mean obsen'ation in the case of place-dependent additive noise with a normal distribution.
Table 8. Grey scale map parameters Pi j for the mean obsen'ation in the case of place-dependent additive noise with a normal distribution.
coefficient
50
100
200
coefficient
50
100
200
«1,1 «1,2 «2,1 «2,2 «2,3 «2,4 «3,1 «3,2 «3,3 «3,4 «3,5 «3,6 «3,7 «3,8 «4,1 «4,2 «4,3 «4,4 «4,5 «4,6 «4,7 «4,8 «4,9 «4,10 «4,11 «4,12 «4,13 «4,14 «4,15 «4,16
0.24995 0.25722 0.06152 0.06984 0.07725 0.08506 0.01534 0.02503 0.03006 0.03564 0.04381 0.05365 0.06127 0.06899 0.00143 0.01229 0.01675 0.02668 0.03321 0.03973 0.05143 0.05118 0.06371 0.07061 0.08008 0.08206 0.08855 0.09792 0.10897 0.11104
0.25030 0.25759 0.06250 0.07086 0.07870 0.08504 0.01568 0.02235 0.03031 0.03679 0.04543 0.05386 0.05801 0.06750 0.00178 0.00781 0.02249 0.02705 0.02780 0.03692 0.05280 0.05356 0.06419 0.07159 0.08115 0.08141 0.08437 0.09758 0.11110 0.11083
0.24878 0.25626 0.06312 0.07153 0.07967 0.08488 0.01744 0.02321 0.02814 0.03740 0.04513 0.05433 0.05702 0.06477 0.00084 0.00629 0.02141 0.02266 0.02719 0.04373 0.05710 0.05175 0.05859 0.07149 0.08136 0.08320 0.08873 0.09738 0.11133 0.10592
0u 01,2 02,1
02,2
02.3
02.4
03.1
03.2
03.3
03.4
03.5
03.6
03.7
03.8
04.1
04.2
04.3
04.4
04.5
04.6
04.7
04.8
04.9
04.10
04.11
04.12
04.13
04.14
04.15
04.16
0.07489 0.07536 0.09382 0.09407 0.09504 0.09634 0.09837 0.09874 0.10232 0.10740 0.11268 0.11914 0.12833 0.13918 0.10045 0.10251 0.11352 0.12803 0.15160 0.18087 0.21227 0.25742 0.30313 0.35599 0.41464 0.48282 0.55569 0.63338 0.71793 0.81049
0.07491 0.07532 0.09373 0.09402 0.09493 0.09677 0.09847 0.09964 0.10265 0.10717 0.11239 0.11996 0.12967 0.13996 0.10002 0.10494 0.11147 0.12844 0.15330 0.18177 0.21101 0.25755 0.30230 0.35590 0.41408 0.48248 0.55716 0.63317 0.71595 0.81017
0.07554 0.07583 0.09392 0.09405 0.09505 0.09751 0.09814 0.09963 0.10403 0.10759 0.11303 0.12046 0.13081 0.14106 0.09993 0.10653 0.11200 0.13098 0.15416 0.17964 0.20810 0.25768 0.30504 0.35697 0.41360 0.48216 0.55611 0.63351 0.71530 0.81130
Example: We repeat the preceding example a last time, with the place-dependent noise Vk{.x) being samples from a beta distribution 0(1,2). The results are presented in Tables 9-12, with the first table presenting the means of the greyscale map parameters
obtained by collage coding the realizations separately and the second table presenting the greyscale map parameters obtained by collage coding the mean observation, u*{x).
Table 9. Greyscale map mean parameters aitj in the case of place-dependent additive noise with a beta distribution.
Table 10. Greyscale map mean parameters pij in the case of place-dependent additive noise with a beta distribution.
coefficient
50
100
200
coefficient
50
100
200
«1,1 «1,2 «2,1 a2,2
a2,3 a2,4 a3,1 a3,2 a3,3 a3,4 a3,5 a3,6 a3,7 a3,8 a4,1 a4,2 a4,3 a4,4 a4,5 a4,6 a4,7 a4,8 a4,9 a4,10 a4,11 a4,12 a4,13 a4,14 a4,15 a4,16
0.25000 0.25732 0.06250 0.06983 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04790 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10655 0.11388
0.25000 0.25732 0.06250 0.06983 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04790 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10655 0.11388
0.25000 0.25732 0.06250 0.06983 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04790 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10655 0.11388
Pu
Pi,2 p2,1 p2,2 P2,3 P2,4 P3,1 P3,2 p3,3 P3,4 P3,5 P3,6 P3,7 P3,8 P4,1 P4,2 P4,3 P4,4 P4,5 P4,6 P4,7 P4,8 P4,9 P4,10 P4,11 P4,12 P4,13 P4,14 P4,15 P4,16
0.27162 0.27019 0.33953 0.33824 0.33735 0.33684 0.35650 0.35580 0.35666 0.35909 0.36308 0.36863 0.37574 0.38441 0.36075 0.36239 0.37028 0.38442 0.40481 0.43145 0.46434 0.50348 0.54887 0.60051 0.65840 0.72254 0.79293 0.86957 0.95245 1.04160
0.28736 0.28577 0.35920 0.35776 0.35671 0.35605 0.37716 0.37630 0.37701 0.37928 0.38311 0.38851 0.39547 0.40399 0.38165 0.38313 0.39087 0.40485 0.42509 0.45158 0.48431 0.52330 0.56853 0.62002 0.67776 0.74174 0.81198 0.88846 0.97120 1.06020
0.31950 0.31760 0.39937 0.39762 0.39625 0.39528 0.41934 0.41817 0.41856 0.42052 0.42404 0.42912 0.43577 0.44397 0.42433 0.42550 0.43292 0.44660 0.46652 0.49269 0.52511 0.56378 0.60870 0.65988 0.71730 0.78097 0.85089 0.92706 1.00950 1.09820
Table 11. Grey scale map parameters Cdj for the mean obsen'ation in the case of place-dependent additive noise with a beta distribution.
Table 12. Grey scale map parameters Pi j for the mean obsen'ation in the case of place-dependent additive noise with a beta distribution.
coefficient
50
100
200
coefficient
50
100
200
«1,1 «1,2 «2,1 «2,2 «2,3 «2,4 «3,1 «3,2 «3,3 «3,4 «3,5 «3,6 «3,7 «3,8 «4,1 «4,2 «4,3 «4,4 «4,5 «4,6 «4,7 «4,8 «4,9 «4,10 «4,11 «4,12 «4,13 «4,14 «4,15 «4,16
0.25000 0.25732 0.06250 0.06983 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04790 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10655 0.11388
0.28736 0.28577 0.35920 0.35776 0.35671 0.35605 0.37716 0.37630 0.37701 0.37928 0.38311 0.38851 0.39547 0.40399 0.38165 0.38313 0.39087 0.40485 0.42509 0.45158 0.48431 0.52330 0.56853 0.62002 0.67776 0.74174 0.81198 0.88846 0.97120 1.06020
0.25000 0.25732 0.06250 0.06983 0.07715 0.08447 0.01563 0.02295 0.03028 0.03760 0.04493 0.05226 0.05958 0.06691 0.00391 0.01124 0.01857 0.02590 0.03323 0.04056 0.04790 0.05523 0.06256 0.06989 0.07722 0.08455 0.09188 0.09921 0.10655 0.11388
0u 01,2 02,1
02,2
02.3
02.4
03.1
03.2
03.3
03.4
03.5
03.6
03.7
03.8
04.1
04.2
04.3
04.4
04.5
04.6
04.7
04.8
04.9
04.10
04.11
04.12
04.13
04.14
04.15
04.16
0.27162 0.27019 0.33953 0.33824 0.33735 0.33684 0.35650 0.35580 0.35666 0.35909 0.36308 0.36863 0.37574 0.38441 0.36075 0.36239 0.37028 0.38442 0.40481 0.43145 0.46434 0.50348 0.54887 0.60051 0.65840 0.72254 0.79293 0.86957 0.95245 1.04160
0.28736 0.28577 0.35920 0.35776 0.35671 0.35605 0.37716 0.37630 0.37701 0.37928 0.38311 0.38851 0.39547 0.40399 0.38165 0.38313 0.39087 0.40485 0.42509 0.45158 0.48431 0.52330 0.56853 0.62002 0.67776 0.74174 0.81198 0.88846 0.97120 1.06020
0.31950 0.31760 0.39937 0.39762 0.39625 0.39528 0.41934 0.41817 0.41856 0.42052 0.42404 0.42912 0.43577 0.44397 0.42433 0.42550 0.43292 0.44660 0.46652 0.49269 0.52511 0.56378 0.60870 0.65988 0.71730 0.78097 0.85089 0.92706 1.00950 1.09820
We remark that, in all examples, the mean function u*(x) constructed from the N observations may be viewed as a kind of denoising of the noisy signals.
In closing, we mention that the extension of the ideas in this paper to images (as opposed to signals) is the focus of some current work. We mention here that the ideas link naturally to the idea of image denoising, which has been the focus of much work in image science, including work from a fractal-based direction Ghazel et al, (2003).
REFERENCES
Barnsley MF, Ervin V, Hardin D, Lancaster J (1985).
Solution of an inverse problem for fractals and other
sets. Proc Nat Acad Sci USA 83:1975-77.
Barnsley MF (1989). Fractals everywhere. New York: Academic Press.
Barnsley MF, Demko S (1985). Iterated function systems and the global construction of fractals. Proc Roy Soc London Ser A 399:243-75. Barnsley MF, Hurd L (1993). Fractal image compression.
Massachussetts: A.K. Peters. Bharucha-Reid AT (1972). Random integral equations. Mathematics in Science and Engineering. 96, New York: Academic Press. Centore P, Vrscay ER (1994). Continuity of attractors and invariant measures for Iterated Function Systems. Canad Math Bull 37(3):315-29.
Fisher Y(1995). Fractal image compression, theory and application. New York: Springer-Verlag.
Forte B, Vrscay ER (1995). Solving the inverse problem for function and image approximation using iterated function systems. In: Dynamics of Continuous, Discrete and Impulsive Systems 1(2).
Forte B, Vrscay ER (1999). Theory of generalized fractal transforms. In: Fisher Y, ed. Fractal Image Encoding and Analysis. NATO ASI Series F. Vol. 159. New York: Springer Verlag.
Ghazel M, Freeman GH and Vrscay ER (2003). Fractal image denoising. IEEE Trans Image Proc 12(12):1560-78.
Hans O (1957). Reduzierende zufallige Transformationen. Czechoslovak Math J 7(82):154-8.
Himmelberg CJ (1975). Measurable relations. Fund Math 87:53-72.
Hutchinson J (1981). Fractals and self-similarity. Indiana Univ J Math 30:713-47.
Iacus S, La Torre D (2005). A comparative simulation study on the IFS distribution function estimator. Nonlinear Anal Real World Appl 6(5):858-73.
Iacus S, La Torre D (2005). Approximating distribution functions by iterated function systems. J Appl Math Dec Sci 1:33-46.
Itoh S (1977). A random fixed point theorem for a multivalued contraction mapping. Pacific J Math 68(1):85-90.
Itoh S (1979). Random fixed point theorems with an application to random differential equations in Banach spaces. J Math Anal App 67:261-73.
Kunze H, La Torre D, Vrscay ER (2008). From iterated function systems to iterated multifunction systems.
Commun Appl Nonlinear Anal 15(4):1-15.
La Torre D, Vrscay ER, Ebrahimi M, Barnsley M (2009). Measure-valued images, associated fractal transforms and the affine self-similarity of images. SIAM J Imaging Sci 2(2):470-507.
La Torre D, Vrscay ER (2011). Generalized fractal transforms and self-similarity: recent results and applications. Image Anal Stereol 30(2):63-76.
Lin TC (1995). Random approximations and random fixed point theorems for continuous 1-set-contractive random maps. Proc Amer Math Soc 123(4):1167-76.
Liu LS (1997). Some random approximations and random fixed point theorems for 1-set-contractive random operators. Proc Amer Math Soc 125(2):515-21.
Lu N (2003). Fractal imaging. New York: Academic Press.
Papageorgiou NS (1988). Random fixed points and random differential inclusions. Int J Math Sci 11(3):551-59.
Shahzad N (2001). Random fixed points of set-valued maps. Nonlinear Anal 45(6):689-92.
Shahzad N (2004). Random fixed points of pseudo-contractive random operators. J Math Anal Appl 296(1):302-8.
Shahzad N (2004). Random fixed points of K-set and pseudo-contractive random maps. Nonlinear Anal 57(2):173-81.
Spacek A (1955). Zufallige Gleichungen. Czechoslovak Math J 5(80):462-66.
Vrscay ER, Saupe D (1999). Can one break the 'collage barrier' in fractal image coding? In: Dekking M, Levy-Vehel J, Lutton E, Tricot C eds. Fractals: Theory and Applications in Engineering, London: Springer-Verlag. 307-23.