Tik-61.181 Informaatiotekniikan erikoiskurssi I, syksy 98

Arvostelu

Aritmeettinen koodaus

Aritmeettisessa koodauksessa pakattu bittijono tulkitaan reaaliluvuksi nollan ja ykkösen välillä. Täytyy pitää huoli siitä, että päätös siitä kummalle puolelle rajaa luku sijoittuu voidaan tehdä äärellisessä ajassa. Koodissa tämä on varmistettu siten, että raja pyöristetään koko ajan samaan tarkkuuteen kuin millä lukua esitetään. Samaten on pidettävä huoli siitä, että pakkausvaiheessa rajoja käsitellään täsmälleen samalla tavalla kuin purkuvaiheessa.

Laskentatarkkuuden säilyttämiseksi bittejä tulostetaan sitä mukaa kun päätös niistä pystytään tekemään. Toisin sanoen, jos yläraja on enintään puoli tai alaraja vähintään puoli, voidaan tulostaa bitti. Samalla rajat skaalataan kahdella.

Periaatteessa on mahdollista, että ala- ja yläraja lähestyvät mielivaltaisen lähelle puolta, mutta kumpikaan ei saavuta sitä. Tämä johtaisi laskentatarkkuuden pienenemiseen ja sen estämiseksi väli skaalataan kahdella myös, jos alaraja on vähintään 1/4 ja yläraja enintään 3/4. Tällaisten skaalausten määrä pannaan muistiin muuttujaan 'memorybits' ja otetaan huomioon, kun seuraavan kerran voidaan tulostaa bitti. Skaalauksen ansiosta välin pituus on aina suurempi kuin 1/4, joten laskentatarkkuus säilyy.

Muutama huomio koodeista

• Muuttuja 'bufsize' kertoo kuinka monen bitin tarkkuudella tulkittava luku esitetään. Periaatteessa koodi toimii, vaikka käytettäisiin vain yhtä bittiä, mutta siinä ei tietenkään ole paljon järkeä. Yläraja saadaan matlabin liukulukujen tarkkuudesta: 53 bittiä (1 bitti menee etumerkille ja 10 eksponentille).
• Purkuvaiheessa bittijonoon lisätään nollia, jotta bitit eivät loppuisi kesken. Yhtä hyvin voitaisiin lisätä ykkösiä tai satunnaisia bittejä.
• Koodi on toteutettu vain Bernoulli-mallille. Yleistys muille malleille onnistuu helposti muuttamalla seuraavan pikselin ennustusta ja frekvenssien päivitystä.
• Kun purkuvaiheessa verrataan tulkittua lukua rajaan, tasatilanteessa toimitaan ikään kuin tulkittu luku olisi korkeampi kuin raja. Näin siksi, että myöhemmin luettavat bitit voivat ainoastaan kasvattaa lukua.
• Kuten koodeista näkee, pakkaus ja purku ovat varsin symmetrisiä. Rajojen käsittely on tehtävä identtisesti, jotta sekä pakkaaja että purkaja olisivat samaa mieltä rajoista.
• Pakkauksen lopuksi täytyy varmistaa, että purkaja pystyy varmistamaan luvun olevan rajojen välissä, siis vaikka luku jatkuisi pelkillä nollilla tai pelkillä ykkösillä. Ylimääräisistä biteistä johtuva koodin pituuden kasvu on kuitenkin aina vähemmän kuin kaksi bittiä (voi siis olla 1,9999.. bittiä).

Mallit

Kaikki olivat toteuttaneet kuvan kaksiulotteisuuden huomioivan mallin Markov-mallina, jonka asteluku on vähintään kaksi. Ratkaisu on helppo ja prediktiivisten jakaumien johto seuraa helpohkosti yleistyksenä Bernoulli-mallin vastaavasta (jotkut olivat ilmeisesti oikaisseet intuition avulla ja päätyneet oikeaan tulokseen). Kun siis mallin parametrien prioreina käyttää beta-jakaumia (jotka ovat näiden mallien tapauksessa konjugaattiprioreita), prediktiivinen jakauma palautuu funktioksi havaituista frekvensseistä.

Kuvista tuskin on kovin paljon priori-informaatiota. Teoreettinen epäinformatiivinen priori olisi sellainen, jossa frekvenssit alustetaan puolikkailla. On ehkä syytä olettaa, että kuvissa mustien ja valkoisten pikselien suhde olisi hiukan lähempänä puolta, joten Bernoulli-mallissa on varsin järkevää alustaa frekvenssit esimerkiksi ykkösiksi. On luultavasti syytä olettaa, että 1.-asteen Markov-mallissa mustaa pikseliä seuraa todennäköisemmin musta kuin valkoinen ja päinvastoin, joten on perusteltua alustaa frekvenssit hieman epäsymmetrisesti. Vastaava pätee 2D-mallille.

Vertailu optimaaliseen

Aritmeettinen koodaus pääsee erittäin lähelle optimaalista. Esimerkkikoodi laskee optimaalisen pakkauksen olevan Lena-kuvalle n. 2362,9 bittiä ja lentokoneelle n. 1936,6 bittiä ja antaa kuville 2364 bittiä ja 1937 bittiä pitkät koodit. Jos laskentatarkkuus on kovin pieni, voidaan tietysti sattumalta saavuttaa joko optimaalista lyhyempiä tai pidempiä koodeja (keskimäärin kuitenkin pidempiä), mutta tästä ei voi mitään kovin syvällisiä johtopäätöksiä tehdä.

Hyvät tulokset eri mallien koodinpituuksille olivat 2364 ja 1937 Bernoulli-mallilla (Lena ja lentokone), 1299 ja 1364 1.-asteen Markov-mallilla ja 1106 ja 1081 2D-mallilla. Koska 1.-asteen Markov-malli ei ole kuvan 'transponoinnin' suhteen symmetrinen, voivat pituudet sitä käyttäessä olla myös luokkaa 1772 ja 1485. 2D-mallit eivät tyypillisesti ole kovin herkkiä transponoinnille ja Bernoulli-malli vielä vähemmän. Itse asiassa kaikki pikselit voisi sekoittaa mihin järjestykseen vain ja Bernoulli-mallin pitäisi antaa samat tulokset.