\documentclass[finnish,11pt]{article}
\usepackage{t1enc,a4,babel,latexsym,epsfig}

\setlength{\textwidth}{160mm}
\setlength{\oddsidemargin}{0mm}
\setlength{\evensidemargin}{0mm}
\setlength{\textheight}{240mm}
\setlength{\topmargin}{-10mm}
\setlength{\parskip}{2ex}
\setlength{\parindent}{0pt}
\input{mathfont}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\HX}{\HH(X,d)}
\newcommand{\HRR}{\HH(\R^2,\mbox{euklidinen})}
\newcommand{\PP}{\mathcal{P}}
\newcommand{\PX}{\PP(X,d)}
\newcommand{\PRR}{\PP(\R^2,\mbox{euklidinen})}
\newcommand{\WW}{\mathcal{W}}
\newcommand{\wh}{w_\mathcal{H}}
\newcommand{\xxx}{\mathbf{x}}
\newcommand{\yyy}{\mathbf{y}}
\input{kbmakrot}
\newtheorem{maar}{M��ritelm�}[section]
\newtheorem{lause}{Lause}[section]
\newtheorem{esim}{Esimerkki}[section]
\newenvironment{tod}
  {\par\textbf{Todistus}\,\,}{\hfill$\Box$\vspace{1ex}\par}


\begin{document}

\thispagestyle{empty}
\vspace*{\fill}
\begin{center}
{\LARGE Mat-1.142 Matematiikan seminaari\\[2ex]
Iteroitujen funktiosysteemien k�yt�st� kuvan kompressoinnissa}

\vspace{4ex}{\large 
Kenrick Bingham\footnote{{\tt http://www.hut.fi/\~{}kenny/}}
\vspace{2ex} 

9.5.1996}

\vspace{8ex}
\mbox{\epsfig{file=bzonebw2.eps, width=5cm}}
\end{center}
\vfill\vfill
\pagebreak



\section{Johdanto}

Fraktaaleja piirrett�ess� k�ytet��n annettua yksinkertaista 
matemaattista s��nt�� monimutkaisen kuvan luomiseen.
Kuvan kompressoinnissa eli tiivist�misess� edet��n toiseen suuntaan: 
kuva pyrit��n esitt�m��n lyhyesti ja yksinkertaisesti.

Olisi siis luonnollinen ajatus yritt�� etsi� annetulle kuvalle
yksinkertaista matemaattista s��nt��, jolla voidaan kuvailla tuota kuvaa.

Iteroidut funktiosysteemit (engl.\ {\em iterated function system}\/, IFS)
tarjoavat t�h�n er��n menetelm�n, kun tyydyt��n hieman informaatiota
h�vitt�v��n (engl.\ {\em lossy}\/) tiivist�miseen.



\section{Iteroidut funktiosysteemit ja niiden attraktorit}

\subsection{Kuvat ja metriset avaruudet}

Tarkastellaan ensin IFS:ien teoriassa tarvittavia perusk�sitteit�.
Niist� mainitaan koko joukko ominaisuuksia ja lauseita,
jotka j�tet��n todistamatta.
Todistuksia l�ytyy l�hteest� \cite{everywhere}.

Kuva m��ritell��n usein tason v�rijakaumaksi.
Tarkastellaan yksinkertaisuuden vuoksi mustavalkokuvaa $\cal K$, 
jossa osa tason pisteist� on mustia, osa valkoisia. 
T�ten kutakin kuvaa $\cal K$ vastaa yksik�sitteisesti joukko
$K=\{\xxx\in\R^2\,|\,\xxx \mbox{ on musta $\cal K$:ssa}\}$.

K�yt�nn�n kuvat ovat yleens� paitsi ��rellisen kokoisia, jolloin
$K$ on rajoitettu joukko, my�s ��rellisell� tarkkuudella esitettyj�,
jolloin $K$ voidaan olettaa suljetuksi, ja siis kompaktiksi.

Iteroitujen funktiosysteemien teoria toimii yleisemminkin 
t�ydellisiss� metrisiss� avaruuksissa.
M��ritell��n sit� varten yleisempi ``kuva-avaruus'' $\HX$:
\begin{maar}
Olkoon $(X,d)$ t�ydellinen metrinen avaruus.
T�ll�in $\HX$ on $X$:n kompaktien ep�tyhjien osajoukkojen joukko.
\end{maar}
Kuva voidaan nyt m��ritell� seuraavasti:
\begin{maar}
{\em Kuva} on joukon $\HH(\R^2, euklidinen)$ alkio.
\end{maar}

Pisteen et�isyys kompaktista, ep�tyhj�st� joukosta m��ritell��n 
luonnollisella tavalla.
\begin{maar}
Pisteen $x\in X$ et�isyys joukosta $A\in\HX$ on
\[
d(x,A)=\min\left\{d(x,y)\,|\,y\in A\right\}.
\]
\end{maar}
Pisteen et�isyys joukosta on hyvin m��ritelty, sill�
et�isyys $d$ saavuttaa jatkuvana funktiona pienimm�n arvonsa
kompaktissa joukossa $A$. 
Samasta syyst� voidaan m��ritell� my�s et�isyys kompaktista
joukosta toiseen.

\begin{maar}
Et�isyys joukosta $A\in\HX$ joukkoon $B\in\HX$ on
\[
d(A,B)=\max\left\{d(x,B)\,|\,x\in A\right\}.
\]
\end{maar}

Se ei siis suinkaan kerro, mik� on lyhin et�isyys $A$:sta $B$:hen, vaan
kuinka kauas $B$:st� p��st��n liikuttaessa joukossa $A$.
Et�isyys joukosta toiseen ei yleisesti ole symmetrinen.

\begin{esim}
Olkoot $A=[0,1]$ ja $B=[2,4]$.
T�ll�in $d(A,B)=d(0,B)=d(0,2)=2$, mutta $d(B,A)=d(4,A)=d(4,1)=3$.
\end{esim}

Sit�, kuinka paljon metrisen avaruuden kaksi ep�tyhj��, kompaktia osajoukkoa
``poikkeavat toisistaan'', mittaa nyt niiden v�linen Hausdorff-et�isyys.

\begin{maar}
Joukkojen $A\in\HX$ ja $B\in\HX$ {\em Hausdorff-et�isyys} on
\[
h(A,B)=\max\left\{d(A,B),\,d(B,A)\right\}.
\]
\end{maar}

Hausdorff-et�isyys soveltuu hyvin kahden joukon eroavuuden mitaksi,
sill� se on metriikka.

\begin{lause}\label{hontma}
  Olkoon $(X,d)$ t�ydellinen metrinen avaruus.
  T�ll�in $d$:n indusoima Hausdorff-et�i\-syys $h$ on metriikka $\HX$:ss�. 
  Metrinen avaruus $(\HX,h)$ on t�ydellinen.
\end{lause}
Merkit��n jatkossa metrist� avaruutta $(\HX,h)$ lyhyesti $\HX$:ll�.


\subsection{Kontraktiokuvaukset}

\begin{maar}
Olkoon $(X,d)$ metrinen avaruus. Kuvaus $w:X\to X$ on
{\em kontraktiokuvaus ($X$:ss�)}, 
jos on olemassa sellainen vakio $s\in[0,1)$, ett�
\[
d(w(x),w(y))\le s\cdot d(x,y) \quad \forall x,y\in X.
\]
T�ll�in $s$ on $w$:n {\em kontraktiivisuuskerroin}.
\end{maar}
Kontraktiokuvauksia ovat siis $s$-Lipschitz-kuvaukset, miss� $0\le s<1$.

\begin{esim}
Olkoon $f:\C\to\C$ kompleksianalyyttinen kontraktiokuvaus, jonka
kontraktiivisuuskerroin on $s$, ja olkoon $z_0$ sen kiintopiste.
T�ll�in $f$:n kertojalle $\lambda=f'(z_0)$ p�tee 
\[
  |\lambda|=|f'(z_0)|
  =\left|\lim\limits_{z\to z_0}\frac{f(z)-f(z_0)}{z-z_0}\right|
  =\lim\limits_{z\to z_0}\bigg(
    \underbrace{|f(z)-f(z_0)|}_{\le s|z-z_0|}\frac{1}{|z-z_0|}\bigg)
\le s.
\]
Siis $z_0$ on attraktiivinen kiintopiste, kuten kontraktiokuvauslauseesta
(\ref{kontrlause}) kohta k�y ilmi. \cite{cg}

Koska sama p��ttely toimii my�s muualla kuin kiintopisteiss�,
$f$:n derivaatta on rajoitettu, ja siis Liouvillen lauseen mukaan vakio. 
T�ten $f$:n t�ytyy olla ensimm�isen asteen polynomi.
Kompleksi\-analyyttisi� kontraktiokuvauksia ei n�in ollen ole kovin paljon.
\end{esim}

\begin{lause}[Kontraktiokuvauslause]\label{kontrlause}
  Olkoon $(X,d)$ t�ydellinen metrinen avaruus ja olkoon $w:X\to X$ 
  kontraktiokuvaus. T�ll�in $w$:ll� on t�sm�lleen yksi
  kiintopiste $x_w\in X$. Se on attraktiivinen kiintopiste,
  jonka attraktioallas on koko $X$.
\end{lause}

\begin{esim}
  Lauseen \ref{hontma} mukaan $\HX$ on t�ydellinen metrinen avaruus.
  Kontraktiokuvaus $W:\HX\to\HX$, jonka kontraktiivisuuskerroin on $s$, 
  kuvaa kaksi joukkoa, joiden Hausdorff-et�isyys on $a$, 
  joukoiksi, joiden Hausdorff-et�isyys on enint��n $sa$.

  L�hdett�ess� mielivaltaisesta joukosta $B\in\HX$ iteroimaan $W$:ll�
  saadaan jono joukkoja, jotka l�hestyv�t er�st� raja-arvoa $A$, ts.\ 
  \[
    \forall\;\varepsilon>0\;\exists \mbox{ sellainen } n_0\in\N,\mbox{ ett� }
    n>n_0 \;\Rightarrow\; h(W^{\circ n}(B),A)<\varepsilon.
  \]
\end{esim}

Kuvan kompressoiminen iteroituja funktiosysteemej� k�ytt�en tapahtuu
yksinkertaisesti sanoen seuraavasti: Etsit��n kontraktiokuvausta
$W:\HRR\to\HRR$, jonka kiintopiste $A$ muistuttaa haluttua joukkoa $K$.
T�ll�in koska $K\approx A$, $W(K)\approx W(A)=A\approx K$.
Haettavasta kontraktiokuvauksesta tiedet��n siis, ett� se kuvaa $K$:n
melko hyvin itsens� p��lle.

Millaisia sitten ovat $\HRR$:n kontraktiokuvaukset?
Euklidisten avaruuksien, kuten $\R^2$:n, kontraktiokuvaukset ovat tuttuja: 
niit� ovat mm. differentioituvat kuvaukset, 
joiden Jacobin matriisin normi on kaikkialla alle yhden. 
Esimerkiksi pienent�v�t affiinit kuvaukset ovat kontraktiokuvauksia.
Osa $\HRR$:n kontraktiokuvauksista saadaan tason kontraktiokuvauksien
indusoimina.

\begin{lause}\label{indusointi}
  Olkoon $w:X\to X$ kontraktiokuvaus, jonka kontraktiivisuuskerroin on $s$.
  T�ll�in seuraavasti m��ritelty kuvaus $\wh:\HX\to\HX$,
  \[
    \wh(B)=\{w(x)\,|\,x\in B\} \qquad\forall B\in\HX
  \]
  on kontraktiokuvaus, ja sen kontraktiivisuuskerroin on $s$.
\end{lause}
\begin{tod}
  T�m�n luonnollisen lauseen todistus perustuu siihen, ett� kahden joukon
  $A$ ja $B\in\HX$ Hausdorff-et�isyys kertoo, kuinka kaukana toisessa
  joukossa on pisteit�, jotka eiv�t kuulu toiseen joukkoon.
  Koska $w$:ll� kuvattaessa kaikki pisteparit kuvautuvat l�hemm�s toisiaan,
  my�s n�m� $A$:n ja $B$:n ``kauimmaiset'' pisteet l�hestyv�t toisiaan.
\end{tod}
Huomattakoon, ett� kontraktiokuvauslauseen (\ref{kontrlause}) mukaan
l�hdett�ess� nyt iteroimaan kuvausta $\wh$ mielivaltaisesta l�ht�joukosta 
$B\in\HRR$ l�hestyt��n er�st� joukkoa $A=\lim\wh^{\circ n}B\in\HRR$.
Koska t�ll� tavalla indusoitu $\wh$ kuitenkin ``kutistaa''
kuvaamaansa joukkoa l�pimitaltaan enint��n $s$-kertaiseksi
(ja siis $n$:ll� iteraatiolla enint��n $s^n$-kertaiseksi), kuvajoukon
l�pimitta l�hestyy nollaa. T�ten $A$ koostuu yhdest� pisteest�,
mik� ei kuulosta kovin lupaavalta, sill� tavoitteena oli p��ty� joukkoon,
joka muistuttaisi k�sitelt�v�� kuvaa.

Kuvailtaessa IFS:ien k�ytt�� kuvan kompressoinnissa todettiin, ett�
etsit��n kontraktiokuvauksia, joilla $K$:n kuva saadaan osumaan hyvin
$K$:n p��lle. Hausdorff-et�isyyden mieless� ``hyvin''
edellytt��, ett� $K$:n kuvan pisteit� ei kuvaudu kovin kauas $K$:sta,
ts.\ ett� $d(W(K),K)=\max\{d(x,K)\,|\,x\in W(K)\}<\varepsilon$,
kun $\varepsilon$ on pieni.
T�llainen onnistuu jopa tarkasti, ainakin jos $K$:lla on 
sis�pisteit�:\footnote{��rellisell� tarkkuudella esitetyill� 
kuvilla on v�ltt�m�tt� sis�pisteit�, sill� ne koostuvat kuvapisteist�,
jotka eiv�t ole ideaalisia pisteit�.}
valitaan $K$:n sis�piste, jolla on $K$:ssa $r$-s�teinen ymp�rist� $V$,
kutistetaan $K$ homoteettisesti l�pimitaltaan enint��n $2r$:n kokoiseksi
ja siirret��n $V$:n sis�lle.

Joukko $K$ voidaan siis yhdell� kontraktiokuvauksella kuvata itsens� sis�lle,
mutta Hausdorff-et�isyys edellytt�� my�s, ett� 
$d(K,W(K))=\max\{d(x,W(K))\,|\,x\in K\}<\varepsilon$, siis ett�
$K$ saataisiin my�s peitetyksi kuvallaan ``melkein kokonaan'' eli 
mielivaltaisen tihe�sti. 
Se ei yleens� onnistu $\R^2$:n kontraktiokuvauksella samanaikaisesti, 
koska kontraktiokuvaus kutistaa.

Etsitt�v�n kuvauksen $W$ ei tarvitse kuitenkaan indusoitua mist��n 
$\R^2$:n kontraktiokuvauksesta.
Jos yhdell� kontraktiokuvauksella voidaan peitt�� vain osa $K$:sta, ottamalla
yhdiste $K$:n kuvista useassa kontraktiokuvauksessa se saadaan peitetyksi
mielivaltaisen tihe�sti.
Kyseess� ei tietenk��n ole en�� kontraktiokuvaus $\R^2$:ssa, sill�
usean kopion my�t� h�vi�� funktion yksiarvoisuus. Asia voidaan
kuitenkin esitt�� joukkofunktiolla, joka pysyy edelleen
kontraktiokuvauksena.

\begin{lause}
  Olkoot $w_i:\HX\to\HX$, $i=1,2,\ldots,N$ kontraktiokuvauksia.
  Olkoon kunkin $w_i$:n kontraktiivisuuskerroin $s_i$.
  T�ll�in seuraavasti m��ritelty kuvaus $W:\HX\to\HX$
  \[
    W(B)=w_1(B)\cup w_2(B)\cup\cdots\cup w_N(B)=\bigcup\limits_{i=1}^N w_i(B)
  \]
  on kontraktiokuvaus, jonka kontraktiivisuuskerroin on 
  $s=\max\{s_i\,|\,i\in\{1,2,\ldots,N\}\}$.
\end{lause}
\begin{tod}
  Joukkojen $A$ ja $B$ ``kauimmaisten pisteiden'' et�isyys muuttuu
  kullakin funktiolla $w_i$ kuvattaessa $s_i$-kertaiseksi,
  suurimmillaan siis $s$-kertaiseksi.
\end{tod}


\subsection{Iteroidut funktiosysteemit}

%Iteroitu funktiosysteemi ja sen attraktori voidaan nyt m��ritell�.

\begin{maar}
  {\em Iteroitu funktiosysteemi (IFS)} on pari 
  $((X,d),\WW)$, miss�
  $(X,d)$ on metrinen avaruus ja $\WW$ 
  joukko kontraktiokuvauksia $w_i:X\to X$. 
  Sen kontraktiivisuuskerroin on $s=\max\{s_i\,|\,i\in\{1,2,\ldots,N\}\}$,
  miss� kukin $s_i$ on $w_i$:n kontraktiivisuuskerroin.
\end{maar}

\begin{maar}
  IFS:n $((X,d),\{w_1,w_2,\ldots,w_n\})$ {\em attraktori} on funktion
  $W:\HX\to\HX$,
  \[
    W(B)=w_1(B)\cup w_2(B)\cup\cdots\cup w_N(B)=\bigcup\limits_{i=1}^N w_i(B),
  \]
  kiintopiste.
\end{maar}

Aikaisemmin esitetty ajatus $K$:n peitt�misest� usealla kutistetulla
``kopiolla'' itsest��n osoittautuu j�rkev�ksi.

\begin{lause}[Kollaasilause]\label{kollaasi}
  Olkoon $K\in\HX$ annettu metrisen avaruuden kompakti, ep�tyhj� osajoukko.
  Olkoon $\left((X,d),\{w_1,w_2,\ldots,w_N\}\right)$ IFS, jonka
  kontraktiivisuuskerroin on $s\in[0,1)$, ja olkoon $A$ sen attraktori.
  Silloin
  \[ 
  h(K,A)\le 
  \frac{1}{1-s}\,h\left(K,\bigcup\limits_{i=1}^N w_i(K)\right).
  \]
\end{lause}
\begin{tod}
\[
  h(K,A)\le h(K,W(K))+\underbrace{h(W(K),W(A))}_{\le s\cdot h(K,A)}
              +h(\underbrace{W(A)}_{=A},A))
  =h(K,W(K))+s\cdot h(K,A)
\]
\end{tod}
\pagebreak

Jos siis l�ydet��n IFS, jolla pystyt��n peitt�m��n $K$ hyvin, niin t�m�n IFS:n
attraktori muistuttaa $K$:ta; sit� paremmin, mit� kontraktiivisempi tuo IFS on.
Kuvan kompressoiminen fraktaalien avulla voidaan nyt m��ritell� 
ytimekk��mmin: Etsit��n IFS:��, jonka attraktori muistuttaa annettua kuvaa.

Huomattakoon, ett� erikoistapauksessa, 
jossa kontraktiokuvaukset ovat vakiokuvauksia $w_i(z)=c_i$,
mink� tahansa joukon $B$ kuva on ��rellinen pistejoukko 
$C=\{c_i\,|\,i=1,2,\ldots,N\}$,
joka on my�s IFS:n attraktori. Kontraktiivisuuskerroin on 0, ja
kollaasilause saa muodon $h(K,C)\le 1\cdot h(K,C)$.
Jos ��rellisell� tarkkuudella esitetty kuva $K$ tulkitaan $n$:n pisteen
joukoksi, voidaan valita $n$:n vakiokuvauksen muodostama IFS, jonka 
attraktori on t�sm�lleen $K$.
Tuollaisen IFS:n esitt�miseen tarvitaan kuitenkin v�hint��n yht� paljon
informaatiota kuin $K$:n esitt�miseen, joten mit��n tiivist�mist� ei tapahdu.

Kun taas IFS koostuu ``l�hes identiteettikuvauksista'', $s$ on l�hes 1.
T�ll�in tekij� $\frac{1}{1-s}$ on hyvin suuri, mik� kuvastaa sit�,
ett� vaikka $K$ kuvautuu varsin tarkkaan itselleen, $K$ voi olla
hyvinkin kaukana IFS:n attraktorista.


\section{Sopivan IFS:n etsiminen}

\subsection{K��nteinen ongelma}
Annetun IFS:n attraktorin likim��r�inen laskeminen on siis suhteellisen
suoraviivainen teht�v�. 
Yksinkertaisinta on l�hte� iteroimaan sen kontraktiokuvauksien
yhdistett� jostakin l�ht�joukosta. Koska laskut tehd��n k�yt�nn�ss� yleens�
tietokoneella ja liuku- tai murtoluvuilla, algoritmiin voidaan tehd� 
joitakin teknisi� parannuksia.

K��nteinen ongelma, sopivan IFS:n l�yt�minen annetulle kuvalle 
ei sen sijaan ole triviaali teht�v�.
Yksinkertaisten kuvien esitt�miseen riitt�� muutama kontraktiokuvaus,
mutta my�s jotkut visuaalisesti monimutkaiset, ``fraktaalimaiset'' kuvat 
ovat hyvin yksinkertaisten IFS:ien attraktoreita. 
Esimerkiksi kuvassa \ref{vaahtera} on IFS:n 
\[
\left((\C,\mbox{tasometriikka}),\{w_1,w_2,w_3,w_4\}\right), \qquad\quad  
\left\{\begin{array}{l}
  w_1(z)=0{,}6z+0{,}18+0{,}36i \\
  w_2(z)=0{,}6z+0{,}18+0{,}12i \\
  w_3(z)=(0{,}4-0{,}3i)z+0{,}27+0{,}36i \\
  w_4(z)=(0{,}4+0{,}3i)z+0{,}27+0{,}09i
\end{array}\right.
\]
attraktori.

\begin{figure}[h]
  \centering
  \mbox{\epsfig{file=bzonebw2.eps, width=5cm}}
  \caption{Er��n yksinkertaisen IFS:n attraktori}
  \label{vaahtera}
\end{figure}


\subsection{Jatkuva riippuvuus parametreista}

Mahdollisia iteroituja funktiosysteemej� ja niiss� k�ytett�vi� 
kontraktiokuvauksia on hyvin paljon.
Joukkoa, josta kontraktiokuvauksia etsit��n, on siis rajoitettava.
Yksi mahdollisuus on valita kontraktiokuvausparvi, joka riippuu
muutamasta parametrista.

\begin{maar}
  Olkoon $(P,d_p)$ metrinen avaruus ja $(X,d)$ t�ydellinen metrinen avaruus.
  Kuvaus $w:P\times X\to X$ on {\em kontraktiokuvausparvi ($X$:ss�)}, jos
  $w(p,\cdot):X\to X$ on kontraktiokuvaus kullakin $p\in P$.
  Jos $w(\cdot,x):P\to X$ on jatkuva kullakin kiinte�ll� $x\in X$,
  sanotaan, ett� $w$ {\em riippuu jatkuvasti parametrista $p$}.
\end{maar}

\begin{esim}
Er�s kontraktiokuvausparvi $\R^2$:ssa on kutistavien tasoaffiniteettien parvi
\[
w:\left(\R^4\times\R^2\right)\times\R^2\to\R^2, \quad
w((A,\mathbf{b}),\xxx)=A\xxx+\mathbf{b}, \quad ||A||<1.
\]
Kompleksitasossa $\C$ voitaisiin valita kutistavien homotetioiden, kiertojen
ja siirtojen parvi, joka voidaan esitt�� ensimm�isen asteen polynomeilla
$z\mapsto az+b$, $|a|<1$.

\end{esim}
%\begin{lause}   %%%%%%%% Lemma 2
%  Olkoon $(P,d_p)$ metrinen avaruus ja $(X,d)$ t�ydellinen metrinen avaruus.
%  Olkoon $w:P\times X\to X$ $P$-parametrinen kontraktiokuvausparvi,
%  jonka kontraktiivisuuskerroin on $s\in[0,1)$. 
%  (Toisin sanoen kullakin $p\in P$ saadaan kontraktiokuvaus 
%  $w(p,\cdot):X\to X$.) 
%  Olkoon $w(x,p)$ jatkuva $p$:n suhteen kullakin kiinte�ll� 
%  $x\in X$. 
%  T�ll�in $w(p,\cdot):n$:n kiintopiste riippuu jatkuvasti $p$:st�,
%  ts.\ $x_w:P\to X$ on jatkuva.
%\end{lause}

\begin{lause}\label{parametrijatkuvuus}
  Olkoot $(P,d_p)$ ja $(X,d)$ metrisi� avaruuksia; 
  $(P,d_p)$ kompakti ja $(X,d)$ t�ydellinen. Olkoon 
  $((X,d), \{w_1(p,\cdot),w_2(p,\cdot),\ldots,w_N(p,\cdot)\}$ 
  IFS kullakin $p\in P$ ja riippukoon kukin $w_i$ jatkuvasti parametrista $p$.
  T�ll�in IFS:n attraktori $A=A(p)$ riippuu $p$:st� jatkuvasti 
  Hausdorff-metriikassa.
\end{lause}

Huomattakoon, ett� $P$:n kompaktiuden vaatiminen ei k�yt�nn�n laskuissa ole 
rajoitus, sill� parametrit ovat yleens� liukulukuja, joiden joukko on kompakti.
(Kompaktiutta tarvitaan lauseen todistuksessa, jotta $w_i$:t saadaan
tasaisesti jatkuviksi.)

Sopivaa IFS:�� voidaan nyt l�hte� etsim��n varioimalla parametria $p$
tietokoneella yrityksen ja erehdyksen menetelm�ll�, mahdollisesti jollakin
sopivalla optimointistrategialla tehostettuna.


\subsection{Jatko-opiskelija-algoritmi}

Kokeiltavien kontraktiokuvausten joukon rajoittaminen voi kuitenkin
usein olla tuhoisaa. Jos k�sitelt�v� kuva $K$ sattuu olemaan sellaisen 
hyvin yksinkertaisen IFS:n attraktori, jonka kontraktiokuvaukset on 
rajattu pois kokeiltavien kuvausten joukosta, saatetaan pienemm�st� 
kontraktiokuvausjoukosta joutua valitsemaan suuri m��r� kuvauksia,
jotta attraktori vastaisi $K$:ta hyvin.

T�st� syyst� sopivan IFS:n koneellinen etsiminen on vaikeaa.
Inhimillisell� heuristiikalla saattaa l�yt�� tiettyyn kuvaan hyv�n IFS:n, 
jota kone ei pysty rajoitetusta kontraktiokuvausparvestaan l�yt�m��n.
Alan kieless� esiintyykin ironinen k�site ``jatko-opiskelija-algoritmi'', 
joka toimii seuraavasti:
\begin{enumerate}
\item Otetaan matematiikan jatko-opiskelija.
\item Annetaan h�nelle k�sitelt�v� kuva $K$.
\item Lukitaan h�net huoneeseen ja p��stet��n h�net pois vasta, 
      kun h�n on l�yt�nyt yksinkertaisen 
      IFS:n, jonka attraktori muistuttaa $K$:ta.
\end{enumerate}

IFS:n etsiminen k�sin ei tietenk��n sovi suurien kuvam��rien k�sittelyyn.
Se on luovaa ty�t�, jota voidaan verrata vaikkapa kirjailijan ty�h�n:
Kirjailijakin pyrkii l�yt�m��n tehokkaan tavan v�litt�� viestins�, oli
se sitten tietoa, mielikuvia tai kauneusarvoja.



\section{Sovellukset}


\subsection{Harmaas�vy- ja v�rikuvat}  

Edell� on k�sitelty mustavalkokuvia.
Harmaas�vy- ja v�rikuvien k�sitteleminen on varsin erilaista.
V�rikuville on j�rkev�� tehd� ensin v�rierottelu, jolloin saadaan
kolme harmaas�vykuvaa.\footnote
{Kolme harmaas�vykuvaa vastaavat sitten esimerkiksi alkuper�isen kuvan 
RGB-, CMY- tai HSV-komponentteja. Sama prosessi tehd��n joka tapauksessa 
kuvia tulostettaessa. \cite{bpt}} Voidaan siis rajoittua
tarkastelemaan harmaas�vykuvia.

Yksinkertainen ratkaisu on palauttaa harmaas�vykuva rasteroimalla 
mustavalkokuvaksi, jolle voidaan soveltaa edell� esitettyj� menetelmi�.

Toinen mahdollisuus on laajentaa k�sitelty� teoriaa \cite{everywhere}.
IFS:n k�site laajennetaan IFS:ksi todenn�k�isyyksill�, IFST,
jossa jokaiseen kuvaukseen $w_i$ liitet��n todenn�k�isyys $p_i$,
joille siis p�tee $\sum p_i=1$. N�m� todenn�k�isyydet kertovat,
kuinka suuri painoarvo kullakin $w_i$:ll� on.
IFST:n kontraktiivisuuskerroin on sama kuin vastaavan IFS:n.

Mittateoriaa soveltamalla saadaan kutakin IFST:t� kohti konstruoitua 
ns. {\em invariantti mitta $\mu$} $(X,d)$:ss�, 
joka kuvaa sit�, kuinka tummia eri osat kuvassa ovat. \cite{rudin}
Tarkemmin sanoen kun $B$ on kompaktin metrisen avaruuden $X$ 
mitallinen osajoukko, 
$\mu(B)$ kertoo, kuinka suuri osa kuvan ``kokonaistummuudesta''\footnote
{Kokonaistummuuden voidaan ajatella tarkoittavan vaikkapa kuvan
tulostamiseen k�ytetty� v�riainetta.} 
on joukon $B$ alueella. Mitta $\mu$ on siis normeerattu siten, ett�
$\mu(X)=1$.

Harmaas�vykuvaa ei nyt esit� tason osajoukko, vaan {\em mitta},
joka on er��nlainen v�rijakauma.
$\HX$:n sijaan liikutaan mittojen muodostamassa
kompaktissa metrisess� avaruudessa $\PX$, jossa k�ytetty ns.\ Hutchinsonin
metriikka kertoo karkeasti sanoen, kuinka paljon kahta mittaa
vastaavat kuvat poikkeavat toisistaan.

IFST indusoi nyt Markovin operaattoriksi kutsutun kontraktiokuvauksen
$M:\PX\to\PX$, joka samoin kuin edell� muodostaa kuvasta
pienennettyj� kopioita, mutta lis�ksi jakaa kuvan tummuuden
eri kopioiden kesken todenn�k�isyyksien suhteessa. Jos useampi
kopio osuu p��llekk�in, niiden tummuudet lasketaan yhteen.

Kontraktiokuvauksella $M$ on nyt kiintopistelauseen nojalla kiintopiste $\mu$,
jota kutsutaan IFST:n attraktoriksi. Kollaasilauseelle (\ref{kollaasi}) saadaan
variantti my�s mitoille: Jos mitta pystyt��n kuvaamaan itselleen hyvin 
(Hutchinsonin metriikan mieless�) IFST:ll�,
jonka kontraktiivisuuskerroin on $s$, niin t�m� mitta muistuttaa
ao.\ IFST:n attraktoria $\frac{1}{1-s}$ kertaa yht� hyvin.

K�yt�nn�ss� $\mu$:n kuva voidaan piirt�� seuraavasti ns.\
{\em satunnaisiteraatioalgoritmilla}:
L�hdet��n mielivaltaisesta l�ht�pisteest� $x_0$ ja valitaan
kontraktiokuvauksista $w_1,w_2,\ldots,w_N$ yksi siten, ett� kunkin
$w_i$:n valinnan todenn�k�isyys on $p_i$, ja merkit��n sit� $w_{i_1}$:ll�. 
N�in saadaan piste $x_1=w_{i_1}(x_0)$. 
Valitaan samoin $w_{i_2}$, jolloin saadaan piste $x_2=w_{i_2}(x_1)$.
Kun t�t� toistetaan, saadaan jono pisteit� $(x_i)$.
Niiden jakauma l�hestyy $\mu$:n tummuusjakaumaa todenn�k�isyydell�
yksi, ts.\ melkein kaikilla $w_{i_1}$:n, $w_{i_2}$:n jne.\ valinnoilla.

K�yt�nn�ss� kuvaesitykset koostuvat yleens� pikseleist�, 
jolloin $\mu$:n kuva voidaan nyt piirt�� laskemalla riitt�v�n monta
pistett� jonon $(x_i)$ alkup��st� ja v�ritt�m�ll� pikselit
niiden jakauman mukaan, sit� tummemmaksi, mit� useampi
piste ao.\ pikselin alueelle on osunut.



\subsection{Neli�isometriat}

Johtuen diskreetist� tavasta, jolla tietokonekuvat yleens� esitet��n ja jolla
tietokoneet k�sittelev�t tietoa, seuraava l�hestymistapa osoittautuu
k�yt�nn�lliseksi keinoksi etsi� sopivaa IFST:t�.\cite{ifsafdoc}

Jaetaan k�sitelt�v� kuva $K$, joka on yleens� suorakulmion
muotoinen, samankokoisiin neli�ihin $K_1, K_2, \ldots, K_M$.
Muodostetaan joukko kontraktiokuvauksia siten, ett�
pienennet��n aina $2\times2$ vierekk�isen neli�n alue yhden neli�n
kokoiseksi (kontraktiivisuuskertoimeksi saadaan $\frac{1}{2}$),
sovelletaan yht� kahdeksasta neli�isometriasta (kierrot, peilaukset
vaaka- ja pystypuolittajan sek� diagonaalien suhteen sek� 
identiteetti)\footnote{Neli�isometriat vastaavat siis dihedraaliryhm�n
$D_4$ alkioita.}
ja siirret��n yhden neli�n p��lle. 

N�in saadut kuvaukset ovat
kontraktiokuvauksia $\R^2$:ssa, sill� k�sitellyn nelj�n neli�n
ulkopuoliset pisteet voidaan ajatella kuvattavan neli�n laidalle
lokaalisti vakiokuvauksella.

\begin{figure}[h]
  \centering
  \mbox{\epsfig{file=blocks.eps, width=5cm}}
  \caption{Nelj� neli�t� pienennet��n yhden kokoiseksi}
  \label{blocks}
\end{figure}

Edell� kuvailluista kontraktiokuvauksista valitaan IFST:hen 
paras sellainen osajoukko, ett� kaikki neli�t $K_i$ tulevat peitetyiksi,
ja ett� sopivilla todenn�k�isyyksill� saadaan tummuudet pysym��n 
l�hes samoina.
(Ks.\ kuva \ref{blocks}.)


\subsection{Tuloksia}

Kun IFS-menetelm� kuvien tiivist�miseen esiteltiin julkisuudessa 
vuonna 1988 \cite{byte}, v�itteit� sill� saavutettavista valtavista
kompressiosuhteista alkoi esiinty�. Tekniikkaa kehitt�nyt Michael Barnsley
on patentoinut IFS-tekniikkaan liittyvi� keksint�j��n ja 
perustanut Iterated Systems-yhti�n\footnote{\tt http://www.iterated.com/} 
tuotteistamaan ja markkinoimaan niit�. \cite{patentit}

Kuten muillakin kompressointitavoilla, saavutettavat tulokset
riippuvat voimakkaasti k�sitelt�v�st� kuvasta. Jos kuva on valmiiksi
jonkin yksinkertaisen IFS:n attraktorin approksimaatio 
(kuten kuvan \ref{vaahtera} vaahteranlehti),
IFS-tekniikalla saavutetaan ainakin IFS:�� k�sin etsien 
hyvin suuria kompressiosuhteita,
vaikka perinteisill� tiivistysmenetelmill� (esim.\ JPEG)
tulokset pysyv�t kohtuullisella kuvanlaadulla tavanomaisen 20:1:n tienoilla.

Tavanomaisilla kuvilla ja etsitt�ess� IFS:�� automatisoidusti
kompressiosuhteet vaihtelevat 4:1:n ja 100:1:n v�lill�.
Perinteisill� tiivistysmenetelmill� saadut tulokset ovat samaa luokkaa.

IFS-menetelm� vaatii my�s melko runsaasti laskentaty�t�, erityisesti
kompressointivaiheessa, mutta my�s purettaessa.
Se ei siis ole nopeudessakaan ylivoimainen perinteisiin kilpailijoihinsa
n�hden.




\subsection{Lis�� fraktaaleja}

Sanaa fraktaali ei ole edell� m��ritelty t�sm�llisesti.
Fraktaaleiksi kutsutaan usein olioita, joilla esiintyy samankaltaista
ep�triviaalia hienorakennetta mittakaavasta toiseen.

Vaikka monien IFS:ien attraktorit ovat fraktaalimaisia, my�s muunlaisia
olioita kutsutaan fraktaaleiksi. 
Mandelbrotin joukko, joka tulee monelle ensimm�iseksi mieleen sanasta 
fraktaali, ei tiett�v�sti ole mink��n IFS:n attraktori.
IFS:ill�k��n ei siis pystyt� esitt�m��n kuin osa kaikista
mahdollisista fraktaaleista.


\vspace{12ex}
\begin{thebibliography}{2}

  \bibitem{everywhere} Michael Barnsley, {\em Fractals Everywhere},
    Academic Press, 1988.

  \bibitem{byte} Michael Barnsley, A. Sloan, {\em A Better Way to 
    Compress Images}, Byte Magazine: 215-233, January 1988.

  \bibitem{cg} Lennart Carleson, Theodore W.\ Gamelin,
    {\em Complex Dynamics}, Universitext, Springer-Verlag, 1993.

  \bibitem{faq17} Jean-loup Gailly,
    {\em comp.compression Frequently Asked Questions (part 1/3) 
    -- [17] What is the state of fractal compression?},
    {\tt http://www.cis.ohio-state.edu/hypertext/faq/usenet/\linebreak[4]
    compression-faq/part1/faq-doc-14.html}, 1996.

  \bibitem{faq77} John Kominek, 
    {\em comp.compression Frequently Asked Questions (part 2/3) 
    -- [77] Introduction to Fractal compression (long)},
    {\tt http://www.cis.ohio-state.edu/hypertext/faq/\linebreak[4]
    /usenet/compression-faq/part2/faq-doc-8.html}, 1994.

  \bibitem{ifsafdoc} 
    Giovambattista Pulcini, Valerio Verrando, Riccardo Rossi, Carlo Meloni, 
    {\em Fractal Image Compression through Iterated Function Systems},
    {\tt ftp://ftp.webcom.com/pub/verrando/\linebreak[4]ftp/ifsdoc05.zip},
    1995.

  \bibitem{rudin}
    Walter Rudin, {\em Principles of Mathematical Analysis},
    McGraw-Hill, 1953.

  \bibitem{bpt}
    Hannu Saarelma -- Pirkko Oittinen, {\em Basics of Printing Techonology},
    Otatieto, 1995.

  \bibitem{y} {\em Fractal Image Encoding} (WWW link page),
    {\tt http://inls.ucsd.edu/y/Fractals/}

  \bibitem{patentit} {\tt http://inls.ucsd.edu/y/Fractals/\#patents}

\end{thebibliography}

\end{document}
