Olkoon f neliöllisesti integroituva funktio, joka on määritelty jossakin alueessa S. Haluamme esittää funktion kantafunktioiden \phimn, m,n=0,1, ..., avulla. Kantafunktiot ovat ortonormaaleja, jos
\int\intS \phimn(x,y) \phirs*(x,y) dx dy = \deltamr \deltans.
Haemme kehitelmää
\summ=0M-1\sumn=0N-1 amn \phimn(x,y)
siten, että virhe e2 (sampling error) on mahdollisimman pieni:
e2 = \int\intS | f(x,y) - \summ=0M-1 \sumn=0N-1 amn \phimn(x,y) |2 dx dy.
Tämä toteutuu, kun
amn = \int\intS f(x,y)\phimn*(x,y) dx dy.
Kantafunktioiden joukkoa sanotaan täydelliseksi, jos jokaiselle neliöllisesti integroituvalle funktiolle virhe e --> 0, kun termien määrä kasvaa.
Standardiesitys: Kantafunktiot ovat suorakaiteita:
\phimn(x,y) =
\sqrt(MN/AB), jos mA/M <= x <= (m+1)A/M ja nB/N <= y <= (n+1)B/N,
0 muuten.
Kerroin amn on yksinkertaisesti funktion f keskiarvo suorakaiteessa, jossa \phimn != 0.
Fourier'n esitys: Kantafunktiot ovat
\phimn(x,y) = (1/ \sqrt(AB)) e2i\pi (mx/A + ny/B),
missä A ja B ovat kuvan leveys ja korkeus.
Optimaalinen esitys: Onko olemassa kantaa, jossa virhe e2 on mahdollisimman pieni. Virheen minimointi johtaa ominaisarvotehtävään
\int\int Rff(x,x',y,y')\phim,n(x',y') dx' dy' = \gammamn\phimn(x,y),
jonka ratkaisuna saadaan optimaaliset kantafunktiot. Ne tunnetaan Karhusen ja Loeven funktioina.
Jos p(z) on todennäköisyys, että intensiteetti on z, kvantisointivirhe on
\deltaq2 = \sumk=1K \intzkzk+1 (z-qk)2p(z) dz.
Minimoidaan tätä:
\pd\deltaq2 / \pd zk =
(zk-qk-1)2p(zk)-(zk-qk)2p(zk)=0, k=2,3, ..., K,
\pd\deltaq2 / \pd qk =
-2\intzkzk+1 (z-qk)p(z) dz = 0, k=1,2, ..., K.
eli
zk = qk-1+qk / 2, qk = \intzkzk+1 zp(z) dz / \intzkzk+1p(z) dz.
Jos p(z) on vakio, saadaan tasaväliset rajat.
Käytännössä kvantisointi tapahtuu suoraan laitteistotasolla, jolloin rajat ovat yleensä tasavälisiä, vaikka se ei antaisikaan optimaalista lopputulosta.
Usein naapuripikselit ovat korreloituneita, joten tilaa hukataan tallettamalla tietoa, jonka informaatiosisältö on pieni.
Tiivistämistä voi tehdä monella tavalla:
Tietoa hukkaava (kohinainen) menetelmä säilyttää vain oleellisimmat piirteet; yleensä menetetään pienimmät yksityiskohdat.
Jos harmaatason qi todennäköisyys on pi, kuvaan sisältyvän informaation määrä on
H=-\sumi=1K pi log2 pi.
Tämä on alaraja sille, kuinka monta bittiä pikseliä kohti tarvitaan, jotta alkuperäinen kuva pystytään säilyttämään.
Transformaatiotiivistys: Esitetään kuva kantafunktioiden kombinaationa ja säilytetään vain merkittävimmät termit. Järkevien kantafunktioiden valinta edellyttää kuitenkin tietoa itse kuvasta.
Karhusen ja Loeven muunnos (KL-muunnos): Jos kuva esitetään KL-funktioiden kombinaationa, kertoimet ovat riippumattomia. Kantafunktioiden etsiminen on periaatteessa raskas ominaisarvotehtävä. Jos autokorrelaatiofunktio oletetaan tunnetuksi, voidaan kantafunktioille johtaa lausekkeet.
Fourier'n muunnos: Helppo laskea, mutta yleensä tarvitaan enemmän termejä kuin KL-muunnoksessa, jotta päästäisiin samaan kuvan laatuun.
Hadamardin muunnos: Hyvin tehokas muunnos, jonka kantamatriisit koostuvat pelkästään luvuista +1 ja -1 (ja normitusvakiosta).
N×N kuvalle, missä N on kakkosen potenssi kantamatriisit ovat
\phi(u,v)(m,n)= 1/N (-1)b(u,v,m,n),
missä
b(u,v,m,n) = \sumk=0log2N-1(bk(u)bk(v)+bk(m)bk(n)),
ja bk(x) on luvun x k:s bitti.
Jakson pituus -koodaus (Run length coding): Pikselit korvataan pareilla (v,n), missä v on pikselin arvo ja n on niiden peräkkäisten pikselien määrä, joilla on sama arvo. Säästää paljon tilaa, jos kuvassa on suuria tasaisia pintoja.
Huffman-koodaus: Usein esiintyvät arvot korvataan lyhyillä koodeilla ja harvinaiset pitemmillä.
Fraktaalikoodaus: Luonnossa esiintyvät kohteet ovat harvoin yksinkertaisia geometrisia objekteja, vaan niillä on itsesimilaarinen rakenne (yksityiskohta suurennettuna näyttää samantapaiselta kuin suurempi osa kohdetta). Fraktaalitiivistys perustuu iteroituihin funktiosysteemeihin (IFS, iterated function systems, ks. esim.\ Barnsley: Fractals everywhere, Academic Press 1988.). IFS on satunnaiskulku, jonka kussakin pisteessä valitaan satunnaisesti (mutta sopivilla painoilla) jokin mahdollisista muunnoksista seuraavan pisteen laskemiseksi. Laskennallisesti erittäin raskas, mutta voi tiivistää mutkikkaan metsää, kukkia tai pilviä esittävän kuvaan muutamaan tuhanteen tavuun.
program ifs
! Plot attractor of an iterative process
! | x | | a b || x | | e |
! | | = | || | + | |
! | y | | c d || y | | f |
! There are maxn different sets for the coefficients
! p(i) is the probability that set i will be used
! sp is the cumulative probability distribution
use plot
implicit none
integer, parameter:: maxn=4, npoints=30000
real, dimension(maxn) :: a,b,c,d,e,f,p
real, dimension(0:maxn) :: sp
real, dimension(npoints) :: xx, yy
integer i
a = (/ 0.00, 0.85, 0.20, -0.15 /)
b = (/ 0.00, 0.04, -0.26, 0.28 /)
c = (/ 0.00, -0.04, 0.23, 0.26 /)
d = (/ 0.16, 0.85, 0.22, 0.24 /)
e = (/ 0.00, 0.00, 0.00, 0.00 /)
f = (/ 0.00, 1.60, 1.60, 0.44 /)
p = (/ 0.01, 0.85, 0.07, 0.07 /)
sp = 0.0
do i=1, maxn
sp(i) = sp(i-1)+p(i)
end do
sp(maxn) = 1.01
call iterate2(xx, yy, npoints)
call init("xx.ps", 5.0, 5.0, 40.0, 40.0)
call plotpoints(xx, yy, npoints)
call finish()
contains
subroutine iterate2(xx, yy, npoints)
! random iteration algorithm
integer, intent(in) :: npoints
real, dimension(npoints) :: xx, yy
integer i, k
realx, y, xprev, yprev, r
xprev=0.0 ; yprev=0.0
do i=1,npoints
call randomnumber(r)
do k=1,maxn
if (r < sp(k)) exit
end do
x=a(k)*xprev+b(k)*yprev+e(k)
y=c(k)*xprev+d(k)*yprev+f(k)
xx(i) = x ; yy(i) = y
xprev=x ; yprev=y ;
end do
end subroutine
end program
eps (Encapsulated PostScript) Tekstiä, oikeastaan ohjelmointikieli, helppo siirtää. Sopii hyvin vektorigrafiikkaan, huonommin pikselikuviin. Kielen kehittyneiden rakenteiden avulla monimutkaisiakin kuvia voi toteuttaa hyvin lyhyesti. Esitystapa on riippumaton tulostuslaitteen resoluutiosta. Kuvan rasterointi on tulostimen tehtävä. Adoben lisenssi nostaa PS-tulostimien hintaa.
tif (Tagged Image format) Pikselikuva, ei pakattu, tiedostot isoja.
gif (CompuServe graphics interchange format) Pakattu kuva, ei hukaa informaatiota.
jpeg (Joint Photographic Experts Group file interchange format) Informaatiota hukkaava pakattu kuva. Tarkkuus kärsii hieman, mutta tilansäästö huomattava.
mpeg (Motion Picture Experts Group file interchange format) Liikkuvan kuvan pakkausmenetelmä. Tietyn pikselin väri ei yleensä muutu kahden kuvan välillä, joten koko kuvan sijasta talletetaan vain niissä tapahtuvat muutokset.
pdf (Portable Document Format) Lähinnä julkaisualan uusi standardi. Tiedosto ASCII-tekstiä, joten helposti siirrettävissä.
Linuxin
66146 Apr 15 13:40 forest.bmp ==>
524554 Apr 15 13:42 forest.tif
218378 Apr 15 13:41 forest.eps
75115 Apr 15 13:40 forest.gif
24881 Apr 15 13:43 forest.jpg
826 Dec 17 1997 color.ps ==>
2908547 Apr 15 13:59 color.tif
1454166 Apr 15 14:00 color.bmp
551223 Apr 15 14:01 color.gif
137581 Apr 15 14:17 color.eps
47422 Apr 15 13:59 color.jpg
| x |
x= | y |
| 1 |
Muunnokset voidaan silloin esittää 3×3-matriiseina:
| x' | | x | | y' | = M | y | | 1 | | 1 |
| 1 0 tx |
M = | 0 1 ty |
| 0 0 1 |
| sx 0 0 |
M = | 0 sy 0 |
| 0 0 1 |
| cos f sin f 0 |
M = | -sin f cos f 0 |
| 0 0 1 |
Pikselikuvien geometriset muunnokset
1) Suora muunnos:
x --> M x = x'.
Ei käy, sillä
2) Käänteinen muunnos: kullekin (x', y') etsitään pikseli (x,y), joka kuvautuu pisteeseen (x',y') ja annetaan sen arvo pikselille (x',y'). Parempi, ei jätä tyhjiä pikseleitä. Edelleen jotkut alkuperäisen kuvan pikselit voivat kuvautua useammalle pikselille, jotkin eivät millekään.
3) Käänteinen interpolaatio: haetaan (x,y) kuten edellä; x eivät y yleensä ole kokonaislukuja, joten interpoloidaan pistettä (x,y) vastaava pikselin arvo. Toimii yleensä hyvin, varsinkin jos kuva on kohtuullisen jatkuva. Terävät reunat voivat muuttua epätarkoiksi.
4) Uudelleen konstruointi: esitetään alkuperäinen kuva funktiona, jonka avulla lasketaan uudet pikselien arvot. Työlästä, mutta antaa parhaan tuloksen.
f(x,y) --> f'(x,y)=\intS f(x-x',y-y') g(x',y') dx' dy',
missä S is pieni origin ympäristö. Monet suotimet ovat konvoluutiomuotoa, jolloin voidaan käsitellä joko alkuperäistä kuvaa tai sen Fourier'n muunnosta.
Ei-rekursiivinen suodin: kaikki uudet arvot lasketaan pelkästään alkuperäisen kuvan avulla.
Rekursiivinen suodin: korvataan kukin pikseli uudella arvolla heti kun se on laskettu; muunnettu kuva voidaan tallettaa alkuperäisen päälle.
Alipäästösuodin: poistetaan tiettyä rajaa korkeammat taajuudet. Helpoin toteuttaa Fourier'n muunnoksen avulla. Suotimella on tasoittava vaikutus. Koska rect-funktion Fourier'n muunnos on sinc-funktio, alkuperäisen kuvan tasoitus (konvoluutio rect-funktion kansa) ei poista korkeita taajuuksia kokonaan.
Alipäästösuotimia:
| 1 1 1 |
1/9 | 1 1 1 |
| 1 1 1 |
| 0 1 0 |
1/5 | 1 1 1 |
| 0 1 0 |
| 0 1 0 |
1/6 | 1 2 1 |
| 0 1 0 |
Alipäästösuodatus alkuperäiselle signaalille ei poista kaikkia korkeita taajuuksia.
Alipäästösuodatus signaalin Fourier'n muunnokselle.
Ylipäästösuodin: poistetaan matalat taajuudet. Kuvaa terävöittävä vaikutus. Vastaa derivointia.
Esim. Laplacen operaattori on ylipäästösuodin
\nabla2f(i,j) = \Deltax2f(i,j)+\Deltay2f(i,j)
=(f(i+1,j)+f(i-1,j)+f(i,j+1)+f(i,j-1))-4f(i,j).
eli
| 0 1 0 | | 1 -4 1 | | 0 1 0 |
Mediaanisuodin: Keskiarvo pienentää piikkejä (kuten kosmisia säteitä), mutta ei poista niitä, vaan levittää niiden energian laajemmalle alueelle. Parempi ratkaisu on korvata pikseli pienen ympäristön mediaanilla. Tämä ei sumenna reunoja eikä vaikuta monotonisesti muuttuviin alueisiin.
Signaali ja mediaanisuotimella suodatettu signaali.
p(x,y)=\int\int h(x-x', y-y')f(x',y') dx' dy' + \nu(x,y),
missä \nu on kohina. Laskemalla kummankin puolen Fourier'n muunnos saadaan
P(u,v)=H(u,v)F(u,v)+N(u,v),
missä H on kuvanmuodostusjärjestelmän siirtofunktio (transfer function).
Alkuperäinen kuva voidaan yrittää palauttaa
F(u,v)= M(u,v) (P(u,v)-N(u,v)),
missä suodin M on (luento ??)
M(u,v) =
1/H(u,v), jos u2+v2 <= r2zbr>
1, muuten.
Alkuperäinen ja PSF:llä dekonvoloitu kuva.
Maksimientropiamenetelmä
Toinen menetelmä perustuu entropian käsitteeseen
Hf=-\summ\sumn f(m,n) \ln f(m,n).
Jos kokonaisenergia
f\rm tot = \summ\sumn f(m,n)
pysyy vakiona, entropia on sitä pienempi, mitä enemmän arvot f(m,n) vaihtelevat.
Kohina voi saada myös negatiivisia arvoja. Lisätään kohinaan vakio C siten, että \nu(m,n)+C on aina positiivinen:
H\nu = -\summ\sumn (\nu(m,n)+C) ln(\nu(m,n)+C),
Maksimientropiakorjaus tehdään maksimoimalla lauseketta
H=Hf + a H\nu,
missä a on tasoituksen määrää kuvaava vakio. Lisäksi tarvitaan kaksi rajoitusta:
1) Kokonaisenergian ftot täytyy säilyä vakiona.
2) Havaitun kuvan p täytyy olla alkuperäisen kuvan f ja psf:n h konvoluutio + kohina:
p(q,r)=\summ\sumn h(q-m,r-n) f(m,n) + \nu(m,n).
Ratkaisuna saadaan f ja \nu.
p(i,j)=f(i,j)+\epsilon n(i,j),
missä
n(i,j)=f(i+1,j)+f(i-1,j)+f(i,j+1)+f(i,j-1).
Vähennetään Laplace-operaattoriin verrannollinen lauseke:
p(i,j) - k\nabla2 p(i,j)
= (1+4k) p - k (p(i+1,j)+p(i-1,j)+p(i,j+1)+p(i,j-1))
= (1+4k)f(i,j) + (1+4k)\epsilon n(i,j)-kn(i,j)
-k \epsilon (n(i+1,j)+n(i-1,j)+n(i,j+1)+n(i,j-1)).
Jos k ja \epsilon ovat pieniä, viimeinen termi voidaan unohtaa. Jos k=\epsilon/(1-4\epsilon), kaksi muuta termiä katoaa, jolloin
p(i,j)- k\nabla2p(i,j) = (1+4k)f(i,j),
joten alkuperäinen kuva on rekonstruoitu vakiokerrointa vaille.
Vas. ylh.: Dekonvoloitu kuva.
Oik. ylh.: Kuva tasoitettu yhdeksän pisteen painotetun
keskiarvon avulla.
Vas. alh.: Laplace-suodatettu kuva.
Oik. alh.: Alkuperäisestä kuvasta on vähennetty Laplace-suodatettu kuva.
+ Säästää aikaa, hikeä ja kyyneleitä
+ Aliohjelmat testattuja ja luotettavia
+ Tehokkuus optimoitu
- Ei aina sovellu kovin hyvin omaan tehtävään
- Kaupallisista kirjastoista ei saa lähdekoodia, ei voi muuttaa eikä siirtää erilaiseen ympäristöön
BLAS, Lapack ilmaisia, lähdekoodi vapaasti saatavissa ja levitettävissä.
Nag, IMSL kaupallisia, saatavana useisiin eri ympäristöihin. Melko kalliita, yleensä vuosittainen lisenssimaksu.
Suurten tietokoneiden valmistajilla usein omille laitteille viritettyjä kirjastoja.
Netlib sisältää runsaasti eri alojen ilmaisia kirjastoja.
CSC:n koneilla käytettävissä suuri määrä eri alojen kirjastoja ja ohjelmia. Verkkosivuilta löytyy lisää linkkejä.
Yksinkertaisia vektori- ja matriisioperaatioita:
Lapack
Rutiinit reaali- ja kompleksiarvoisille matriiseille.
Ainakin tuhatkunta rutiinia.
Vielä laajempi kuin IMSL.
Kirjaston mukana esimerkkiohjelma jokaisen aliohjelman käytöstä.