Sisältö

1  Diskreetti kosinimuunnos

1.1  Yksiulotteinen kosinimuunnos

Olkoon f = (f₀,f₂,¼,f_N-1) N-ulotteinen vektori, jonka alkiot ovat reaalilukuja. Tällöin määritellään sen diskreetti kosinimuunnos (DCT) kaavalla

Kuva Kuva 1: Diskreetin kosinimuunnoksen kantavektorit tapauksessa N = 8

Molempien muunnosten laskeminen käyttämällä perusmääritelmää vaatii kertaluokkaa O(N²) laskutoimitusta, mutta on kehitetty my”s algoritmeja, joilla laskennan määrää voidaan vähentää. Matlabissa kosinimuunnos lasketaan diskreetin Fourier-muunnoksen avulla. Jos merkitään w_N = e^-i2p/N, missä i on imaginaariyksikk” (i² = -1), niin vektorin f = (f₁,¼,f_N-1) diskreetti Fourier-muunnos (DFT) määritellään kaavalla

Jos N-vektorille suoritetaan DFT suoraan määritelmään perustuen, on vaadittava laskutoimitusten määrä kertaluokkaa O(N²). Muunnoksella on kuitenkin erikoisominaisuuksia, joita hy”dyntämällä laskutoimitusten lukumäärä saadaan pudotettua kertaluokkaan O(N logN). Kaikkein nopeimmin DFT saadaan muodostettua, jos N on muotoa N = 2^L. Näistä nopeammista algoritmeistä käytettään nimitystä FFT (Fast Fourier Transform). Näin ollen Matlabissa kosinimuunnos lasketaan käyttäen hyväksi nopeaa Fourier-muunosta jonka jälkeen kertoimet skaalataan kosinimuunnoksen kertoimiksi.

1.2  Kaksiulotteinen kosinimuunnos

Olkoon A M ×N-kokoinen kuva, missä M on rivien ja N sarakkeiden lukumäärä. Täll”in diskreetti kaksiulotteinen kosinimuunnos (DCT2) määritellään kaavalla

Kuten yksiulotteinen, myös kaksiulotteinen kosinimuunnos kuvaa syötteenä annettavan tiedon ennalta määrättyjen kantavektoreiden avulla. Nyt kantavektorit vaan ovat kaksiulotteisia kuvia. Kuvassa (2) on piirretty kaikki 64 kosinimuunnoksen kantavektoria. Harmaasävyt on skaalattu siten, että tummin esittää pienintä arvoa -1 ja vaalein sävy arvoa 1.

Kuva Kuva 2: Diskreetin kosinimuunnoksen kantavektorit 8 ×8-tapauksessa

Kaksiulotteisen kosinimuuunnoksen toteuttaminen ei kuitenkaan poikkean paljon yksiulotteisesta tapauksesta, sillä se saadaan muodostettua kuvalle tekemällä ensin DCT sarakkeille ja tämän jälkeen sama muunnoksen riveille.

2  JPEG-pakkauksen simulointia Matlabilla

2.1  Pakkausalgoritmi

JPEG-pakkausalgoritmille annetaan syötteenä esimerkiksi 256 harmaasävyn kuva tai 24-bittinen RGB-värikuva. Kuvien koko olkoon N ×M pikseliä, Matlabissa tämä tarkoittaa N riviä ja M saraketta. Kukin väritasoista esitetään N ×M-kokoisena matriisina, jossa alkio on kokonaisluku väliltä 0 ¼255. Varsinainen käsittely tehdään kullekin komponentille erikseen. JPEG-pakatun kuvan muodostaminen koostuu seuraavista toimenpiteistä:

1. Muunnetaan värikuvilla RGB-esitys YUV-avaruuteen
2. Muutetaan kokonaisluvut välille -128 ¼127 vähentämällä arvoista luku 128
3. Käsitellään kuvaa 8 ×8-kokoisissa lohkoissa tekemällä jokaiselle lohkolle DCT2-operaatio
4. Lohkosta saatavat kosinimuunnoksen kertoimet kvantisoidaan 8-bittisiksi kokonaisluvuiksi välille -128 ¼127.
5. Koodataan kvantisoidut kertoimet tiedostoon.

Matlabin komennot ovat vektoroituja, joten melkein kaikille komennoille voidaan antaa syötteenä matriisi. Näin ollen esimerkiksi skalaarin ja matriisin yhteenlasku tuottaa matriisin, jossa alkuperäisen matriisin jokaiseen alkioon on lisätty sama luku. Vastaavasti esimerkiksi matriisin kosini tuottaa tuloksena matriisin, jonka alkiot ovat alkuperäisen matriisin alkioiden kosineja. Kertolasku sitä vastoin ei toimi oletusarvoisesti alkioittain vaan tällöin sovelletaan matriisien kertolaskua, jolloin siis matriisien dimensioiden tulee olla yhteenspoivat. Ainoa poikkeus on tapaus, jolloin kerrotaan matiisi ja skalaari, jolloin jokainen matriisin alkio kerrotaan kyseisellä skalaarilla. Näin ollen sekä YUV-muunnos että luvun -128 vähentäminen voidaan suorittaa Matlabissa vastaavalla tavalla kuin kahdelle reaaliluvulle: YUV-muunnos määritellään

Varsinaista pakkausta varten matriisista poimitaan 8 ×8-lohkoja, joille suoritetaan DCT2-operaatio. Matlabin (versio 4) kosinimuunnos ei ilmeisesti kuitenkaan sisällä skaalaustekijöitä a_i ja b_j, joten kertoimet on vielä jaettu luvulla 16. Muuten kertoimien itseisarvo on välillä on liian suuri, jotta ne saataisiin edes kvantisoitua välille -128 ¼127.

Matlab-toteutusta varten tehokkain tapa kvantisoinnille on määritellä ensin kvantisointimatriisit ja sen jälkeen jakaa DCT2:n tuottamat kertoimet alkioittain. Kuvassa (3) on JPEG-standardin mukaiset kvantisointikertoimet. Näistä vasemmanpuoleista käytetään Y-komponenteille ja oikeanpuoleista U ja V-komponenteille.

    16 11 10 16  24  40  51  61     17 18 24 47 99 99 99 99
    12 12 14 19  26  58  60  55     18 21 26 66 99 99 99 99
    14 13 16 24  40  57  69  56     24 26 56 99 99 99 99 99
    14 17 22 29  51  87  80  62     47 66 99 99 99 99 99 99
    18 22 37 56  68 109 103  77     99 99 99 99 99 99 99 99
    24 35 55 64  81 104 113  92     99 99 99 99 99 99 99 99
    49 64 78 87 103 121 120 101     99 99 99 99 99 99 99 99
    72 92 95 98 112 100 103  99     99 99 99 99 99 99 99 99

2.2  Kuvan purkaminen

JPEG-datan purku toteutetaan päinvastaisessa järjestyksessä kuin pakkaaminen. Syötteenä ovat kvantisoidut kertoimet, joten ensimmäinen vaihe on suorittaa dekvantisointi. Jokaisessa 8 ×8-lohkossa keroimet ensin kerrotaan alkioittain kvantisointimatriiseilla ja aikaisemmin esille tulleella skaalauskertoimella 16, jonka jälkeen suoritetaan IDCT2-operaatio. Tämän jälkeen kertoimet pyöristetään lähimpään kokonaislukuun, lisätään 128 ja muutetaan data lopuksi takaisin RGB-avaruuteen. Ohjelmassa kuitenkin ilmeni, että kertoimet eivät aivan pysy välillä 0,¼,255, joten tämän jälkeen vielä leikattiin arvot siten, että yli 255 menevät arvot tiputettiin alaspäin arvoon 255 ja alle 0 menevät arvot nostettiin arvoon 0. Näin myös puretun datan arvot saatiin sallitulle alueelle.

2.3  Progressiivinen esitys

JPEG-standardi mahdollistaa myös progressiivisen esityksen, jossa kertoimien koodausjärjestys ei ole lohko kerrallaan vaan jokaisesta lohkosta haetaan yksi kerroin ja koodataan kaikkien lohkojen vastaavat kertoimet peräkkäin. Näin saadaan kuvanlatauksen aikaisessa vaiheessa approksimaatio kokonaan puretulle datalle ja mitä enemmän kertoimia puretaan sitä parempi kuva saadaan. Kertoimet otetaan tiedostoon mukaan siksak-järjestyksessä, joka on esitetty kuvassa (4). Perustelu järjestykselle on se, että suurimmat, eniten merkitsevät kertoimet, sijaitsevat yleensä vasemmassa ylänurkassa. Näin ollen ne yritetään saada syötettyä dekoodaajalle mahdollisimman aikaisessa vaiheessa, jotta saataisiin muodostettua mahdollisimman hyvä arvio lopulliselle kuvalle. Matlab-koodissa progressiivisuutta pyrittiin jäljittelemään siten, että vaiheessa n asetetaan siksak-järjestyksessä arvon n jälkeen tulevat kertoimet nolliksi ja muodostetaan jäljelle jäävillä kertoimilla käänteinen kosinimuunnos.

                     1  2  6  7 15 16 28 29
                     3  5  8 14 17 27 30 43
                     4  9 13 18 26 31 42 44
                    10 12 19 25 32 41 45 54
                    11 20 24 33 40 46 53 55
                    21 23 34 39 47 52 56 61
                    22 35 38 48 51 57 60 62
                    36 37 49 50 58 59 63 64

3  Testaus

Testataan ensin pakkauksen toimimista muutamilla synteettisesti tuotetuilla 8 ×8-lohkoilla. Kuvassa (5) on esimerkkinä lohko, jossa on valkoinen suorakulmio keskellä (ylin taulukko). Sen alapuolella näkyvät DCT-kertoimet. Niistä voidaan havaita, että vain kolme kvantisoitua kerrointa ovat nollasta poikkeavia. Erityisesti kerroin, joka sijaitsee kohdassa (1,3), on muita suurempi. Syykin tälle on selvä: kuvassa (2) olevista kaksiulotteisista kantavektoreista juuri kohdan (1,3) vektori vastaa paljon muodoltaan esimerkkikuvaa, joten koko kuva saadaan suurimmaksi osaksi muodostettua skaalaamalla kyseistä vektoria.

Alkuperäinen    0 0 255 255 255 255 0 0
kuva            0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0

Kvantisoidut    -1 0 -133 0 0 0 11 0
DCT-kertoimet    0 0    0 0 0 0  0 0
                 0 0    0 0 0 0  0 0
                 0 0    0 0 0 0  0 0
                 0 0    0 0 0 0  0 0
                 0 0    0 0 0 0  0 0
                 0 0    0 0 0 0  0 0
                 0 0    0 0 0 0  0 0

Rekonstruoitu   0 0 255 254 254 255 0 0
kuva            0 0 255 254 254 255 0 0
                0 0 255 254 254 255 0 0
                0 0 255 254 254 255 0 0
                0 0 255 254 254 255 0 0
                0 0 255 254 254 255 0 0
                0 0 255 254 254 255 0 0
                0 0 255 254 254 255 0 0

Muutetaan esimerkkilohkoa siten, että jäljelle jää neliö kuvan keskelle. Kuvassa (6) on esitetty vastaavat tiedot kuin edellä. Kuten havaitaan, jää tällä kertaa melko suuria DCT-kertoimia useita. Jos tarkasteleekin kuvaa (2), havaitsee, ettei kantavektoreista löydy sellaista vaihtoehtoa, joka kuvaisia tarkasti yhtenäistä aluetta lohkon keskellä. Näin ollen se joudutaan koostamaan usean lohkon kombinaationa. Tämä aiheuttaa myös sen, että rekonstruoidessa kuvaa dekvantisoiduilla kertoimilla syntyy myös virheellisiä pikseliarvoja enemmän kuin mitä esimerkiksi edellisessä tapauksessa.

Alkuperäinen    0 0   0   0   0   0 0 0
                0 0   0   0   0   0 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0 255 255 255 255 0 0
                0 0   0   0   0  0  0 0
                0 0   0   0   0  0  0 0

Kvantisoidut    -64 0 -67 0 0 0  5 0
DCT-kertoimet     0 0   0 0 0 0  0 0
                -48 0  27 0 0 0 -3 0
                  0 0   0 0 0 0  0 0
                  0 0   0 0 0 0  0 0
                  0 0   0 0 0 0  0 0
                  6 0  -2 0 0 0  1 0
                  0 0   0 0 0 0  0 0

Rekonstruoitu    0  5   0   1   1   0  5  0
kuva             0 10   0  10  10   0 10  0
                12  0 255 249 249 255  0 12
                 0  0 255 255 255 255  0  0
                 0  0 255 255 255 255  0  0
                12  0 255 249 249 255  0 12
                 0 10   0  10  10   0 10  0
                 0  5   0   1   1   0  5  0

Otetaan seuraavaksi vielä esimerkki aidosti 24-bittisellä värikuvalla, joka on kuvassa (7) ylimpänä vasemmalla. Kuvan koko on 128 ×200, joten koodattavia lohkoja on 400. Kertoimia tulee siis yhteensä 3 ×64 ×400 = 76 800. Kuvalle laskettiin joka lohkolle kvantisoidut DCT-kertoimet, joista loppujen lopuksi 6307 oli nollasta poikkeavia, ja muodostettiin näistä progressiivisisen esityksen vaiheita eri arvoilla. Kuvassa (7) näkyy vaiheita eri n:n arvoilla sekä näistä laskettu MSE alkuperäiseen kuvaan verrattuna. Arvolla n = 1 jokaisesta lohkoa edustaa kyseisen lohkon värien keskiarvo, kuvasta voi kuitenkin jo päätellä, mitä se mahdollisesti edustaa. Arvolla n = 4 hahmo erottuu jo paremmin, DCT-lohkojen väliset erot ovat kuitenkin varsin selvät. Tapaus n = 16 tuottaa jo varsin hyvän kuva, suurimmat erot tulevat näkyviin reunojen kohdalla, esimerkiksi takin keskellä. Arvo n = 32 ja täysi rekonstruktio parantavat lähinnä yksityiskohtien tarkkuutta. MSE:n ero näiden kahden tapauksen välillä ei kuitenkaan ole kovin suuri, viimeinen kuva voi kuitenkin pahimmillaan vaatia kaksi kertaa sen tilan kuin vaihe n = 32.

Alkuperäinen kuva	n = 1, MSE=2644
n = 4, MSE=730	n = 16, MSE=265
n = 32, MSE=67	n = 64, MSE=61

Kuva 7: 128 ×200-kokoisen kuvan progressiivisen esityksen vaiheita

Lopuksi on vielä testattu edellisen esimerkkikuvan 8 ×8-kokoisella yksityiskohdalla. Lohko on otettu vasemmanpuoleisen silmän yläreunasta, jolloin lohkoon jää reuna. Tälle lohkolle on tehty myös progressiivisen esityksen vaiheita kuten edellä. Kuvassa (7) vasemmalla ylhäällä alkuperäinen kuva, kolme välivaihetta sekä täydellinen rekonstruktio. Kuten voidaan havaita, ei rajaa tummemmasta valkoiseen saada palautettua vain muutamalla kertoimella, vasta arvolla n = 8 alkaa raja erottumaan. Arvolla n = 16 se kuitenkin erottuu jo selvästi, eikä täydellinen rekonstruktio tuo kovin suurta parannusta lohkon laatuun.

Alkuperäinen kuva
n = 4, MSE=4389	n = 8, MSE=657
n = 16, MSE=244	n = 64, MSE=169

Kuva 8: 8 ×8-kokoisen lohkon progressiivisen esityksen vaiheita