1.Lyhenne -ja termiluettelo 12. Johdanto 13. Kompressoinnin perusteet 44. Häviömättömän kompression sovellutuksia 54.1 Musiikin pakkaus 14.2 V.42bis 1 4.3 GIF 85. Häviöllisen kompression käyttö 1 5.1 JPEG 9 5.2 MPEG 96. Yhteenveto 17. Lähteet 11

1. Lyhenne -ja termiluettelo

CCITT

Kansainvälinen telealan neuvottelukunta.

INTERAKTIIVINEN

Vuorovaikutteinen. Esimerkiksi WWW on interaktiivinen järjestelmä, jossa käyttäjä päsee vaikuttamaan tapahtumien kulkuun.

ITU

YK:n alainen kansainvälinen televiestintäliitto.

JPEG

Joint Photographic Experts Group. JPEG on suosittu valokuvien pakkaustapa. JPEG-kuvat ovat usean WWW-selaimen hyväksymä kuvatiedostomuoto.

Modem (MODulator-DEModulator)

Modeemi. Käyttäjän tietokoneeseen liitetty laite, jonka avulla digitaalista dataa voi lähettää analogista väylää kuten puhelinlinjaa pitkin.

MPEG (Moving Pictures Expert Group)

MPEG on videokuvan pakkaukseen liittyvä standardi.

Multimedia

Tietokonejärjestelmät, joissa yhdistetään ääntä, videokuvaa ja dataa.

Reaaliaikainen

Reaali- eli tosiaikainen. Tapahtumakohtaisten tietojen nopea siirto ja käsittely samaan aikaan tapahtuman kanssa tallennuksen ja uudelleensiirron tai eräkäsittelyn sijasta.

WWW (World Wide Web) Internetissä oleva järjestelmä, jolla kaikkialla maailmassa olevat multimedia-asiakirjat yhdistetään hypertekstilinkeillä. Tämän ansiosta asiakirjojen tietoihin pääsee helposti riippumatta siitä, missä ne fyysisesti sijaitsevat.

2. Johdanto

Datan kompressoinnilla tarkoitetaan prosessia, jossa tietyn informaation ilmaisuun tarvittavan datan määrää saadaan pienennettyä alkuperäisestä. Tiedon kompressoinnista on tullut yhä tärkeämpi ja oleellisempi osatekijä nykyaikaisessa tietoyhteiskunnassa. Digitalisoituminen ja siihen perustuvien hyödykkeiden kuten henkilökohtaisten tietokoneiden määrä on ollut rajussa kasvussa jo usampia vuosia, eikä kehityksen tasaantumista ole lähiaikoina näkyvissä. Itse asiassa multimedian rynnistäessä koko painollaan markkinoille tulee siirrettävän tiedon määrä nousemaan yhä enemmän. Interaktiivisuuden ja siihen kiinteästi liittyvän reaaliaikaisuuden täyttäminen tulee täten olemaan yhä hankalampaa. Esimerkkinä voidaan mainita Internet ja siihen kiinteästi liittyvä WWW-selailu, jonka jouhea toimivuus vaatii tietyn reaaliaikaisuuden täyttymistä.

Yksinkertaisin ratkaisu joustavan käytön turvaamiseksi olisi tietenkin siirtoyhteyksien kapasiteetin nosto sirrettävän datan suhteessa, mutta tämä ratkaisu ei ole pidemmällä aikavälillä katsoen taloudellisesti kannattavalla pohjalla. Koska datan siirtotienä joudutaan käyttämään usein hyvinkin alkellista ja huonokuntoista mediaa kuten puhelinlinjoja tulisi hyödynnettävä kaista käyttää mahdollisimman tehokkaasti. Tiedon kompressointi on ratkaisu edellisiin ongelmiin ja yksi tehokkaimmista ja taloudellisimmista keinoista lisätä siirto -ja tallennuskapasitettia.

3. Kompressoinnin perusteet

Kompressiotekniikat voidaan karkeasti ajatellen jakaa kahteen eri luokkaan. Tietoa häviömättömään ja tietoa hävittävään kompressioon. Monessa sovellutuksessa ainoa tapa tiedon koon pienentämiseen on käyttää hävittämätöntä kompressiota.

Hävittämätön kompressio tarkoittaa, että purettu data on tarkalleen yhdenmukaista verrattuna alkuperäiseen. Tätä tekniikka voidaan käyttää esimerkiksi tekstin ja tietokoneohjelmien käsittelyyn. Tyypillisesti tällä tavalla saadaan alkuperäinen materiaali pienennettyä noin 2-10 kertaisesti.

Yksi suosituimmista tekniikoista tiedon määrän pienentämiseen on Huffman-koodaus, jonka idean jatko-opiskelija David Huffman julkaisi jo vuonna 1951. Kuitenkin vasta 70-luvulla puolijohdetekniikan ja mikropiirien kehitys oli saavuttanut sellaisen vaiheen, jossa Huffman-koodauksesta saatiin huomattavaa hyötyä. Huffman-koodaus on yksi niistä kulmakivstä, joita käytetään hyväksi kaikkialla tietotekniikassa ja tiedonsiirrossa.

Huffman-koodauksessa datavirta jaetaan tietyn mittaisiksi jaksoiksi. Tietotekniikassa jakson koko on useimmiten 8 bittiä. Jokaisen bittijaksojen todennäköisyys lasketaan ja Huffmanin koodipuu rakennetaan. Tämän koodipuun mukaan suuremmalla todennäköisyydellä ilmenevät bittijaksot voidaan ilmaista pienemmällä määrällä bittejä kuin harvemmin esiintyvät. Huffman-koodausta voidaan menestyksellisesti käyttää kuvien kompressointiin.

Käyttämällä dynaamista koodipuuta saavutetaan entistä parempia tuloksia verrattuna stattisen koodipuun käyttöön. Dynaamisessa tapauksessa koodipuuta muutetaan jatkuvasti kompression edetessä.

Toinen päätyyppi kompressoinnissa on niin kutsuttu hävittävä kompressio. Toisin kuin edellisessä kappaleessa kuvattu hävittämätön ja täten virheetön kompressio hävittävä kompressio kompromisoi lopputulosta verrattuna alkuperäiseen dataan. Mikäli lopputuloksen tarkkuus ei ole kovin kriittinen voidaan saavuttaa hyvinkin merkittäviä säästöjä datan määrässä. Esimerkiksi monet tätä metodia käyttävät ohjelmat pystyvät pienentämään monokromaattisia kuvia suhteessa 30:1 ja kuvia joita on käsitelty suhteessa 20:1 tai 10:1 voi erikoistapauksissa olla liki mahdotonta erottaa alkuperäisestä vedoksesta paljaalla ihmissilmällä. Täysin virheettömään lopputulokseen monkromaattisten kuvien kohdalla päästään harvoin kuitenkaan parempaan kompressiosuhteeseen kuin 3:1.

Kappaleessa 4 tutustumme häviöttömään kompression sovellutuksiin ja kappaleessa 5 keskitymme häviölliseen metodin käyttöön.

4. Häviömättömän kompression sovellutuksia

4.1 Musiikin pakkaus

Häviämättömän kompression perusideana on, että purettu data on tarkalleen identtistä alkuperäiseen verrattuna. Tämän tekniikan eräinä sovellutuksina voidaan pitää audio -ja kuvainformaation pakkausta. On pidettävä mielessä, että jos käsiteltävä data on täysin mielivaltaista ja ennalta-arvaamatonta niin sitä ei voida pakata. Musiikki kuitenkin noudattaa tiettyjä sääntöjä, jotka mahdollistavat sen käsittelemisen. Näitä lainalaisuuksia ovat:

1.	Audiosignaalien energia on paaosin keskittynyt mataliin taajuuksiin.
2.	Signaalin amplitudit muodostavat ajallisia lokaaleja, eli dynaaminen alue muuttuu hitaasti musiikkisignaalissa.
3.	Samat aaltomuodot ja kuviot toistuvat.
4.	Monikanavaisessa signaalissa eri kanavat sisältävät yleensä samaa tietoa.

Tämänhetkiset audiokompressorit hyödyntävät tavallisesti vain kahta ensimmäistä ominaisuutta. Hävittämätöntä audiopakkausta tarvitaan silloin kuin alkuperäiseen signaalin ei saa tulla pienintäkään laatua heikentävää muutosta. Esimerkkeinä tällaisista tilanteista ovat studioiden masternauhat ja eri instrumenttien digitaaliset samplaukset, joita käytetään digitaalisessa musiikissa.

Tarkastelemme seuraavaksi kahden erityyppisen kompressio-ohjelman suorituskykyä musiikin pakkaamisessa. Näistä ensimmäinen on Shorten ja toinen Gnu zip.

Shorten on ohjelma, joka on nimenomaan kehitetty audiodatan kompressointiin. Se tukee sekä hävittämätöntä että hävittävää tapaa pakkauksessa. Ohjelman on kehittänyt Tony Robinson ja se on saatavilla lähdekoodeineen osoitteesta: Error! Bookmark not defined.

Shorten distribuutio sisältää myös teknisen raportin TR.156, joka selostaa kuinka ohjelman algoritmi toimii. Peruskomponettina käytetään Huffman-koodausta.

Gnu zip on perinteinen yleiskäyttöinen pakkausohjelma. Lähes kaikki suositut data-kompressio-ohjelmat kuten zip,pkzip,arj… käyttävät lähes samaa algoritmia, joten niiden vertailutulokset ovat hyvin samankaltaisia. Gzip käyttää niin sanottua LZ77 tekniikkaa, jonka peruspilareista löytyy staattinen Huffman-koodaus. Gzip on saatavissa osoitteesta:

Testidatana on käytetty CD-tasoista ääntä 44.1 kHz näytteenottotaajuudella. Työasemana Silicon Graphics Indy 100MHz R4600PC prosessorilla. Näytekappaleiden kuvaus:

Nimi:		Pituus:		Laatu:			Tyyppi:
access.aif	10499484 tavua	16-bittinen stereo	musiikki
queen.aif	10668828 tavua	16-bittinen stereo	musiikki
speechm.aif	294742 tavua	16-bittinen mono	puhe
swnlake.aif	10555932 tavua	16-bittinen stereo	musiikki

Kaikki näytteet lukuunottamatta speechm.aif ovat pituudeltaan runsaan minuutin luokkaa.

Gzip -9 (maksimi kompressio)

Tiedosto:	Koko (tavuina):	Pakkaussuhde:	Pakkausaika (s):

access.aif	10105917		96.3%		44.85	
queen.aif	9397135		88.1%		48.23
speechm.aif	240776		81.7%		1.41
swnlake.aif	9256588		87.7%		51.64

Pakkaussuhde = pakattu/alkuperäinen Vertailemalla ylläolevaa taulukkoa alkuperäisten näytteiden pituuteen huomataan, että gzip kompressoi 16-bittistä audiodataa hyvin maltillisesti. 16-bittinen puhenäyte kompressoituu parhaiten. Sekä purku että pakkaus voidaan hoitaa reaaliaikaisesti kokeen työasemalla.

Shorten

Tiedosto:	Koko (tavuina):	Pakkaussuhde:	Pakkausaika (s):

access.aif	8459141		80.6%		13.27	
queen.aif	6854485		64.2.%		12.83
speechm.aif	138653		47.0%		0.34
swnlake.aif	5364197		50.8%		12.47

Pakkaussuhde = pakattu/alkuperäinen Kuten huomataan Shorten selviytyy huomattavasti paremmin kuin gzip niin musiikin kuin puheenkin kompressoinnissa. Voidaan kuitenkin päätellä, että hävittämätön audiokompressointi on suhteellisen hankalaa. 16-bittinen musiikki sisältää siinä mielessä paljon kohinaa, jota ei voida kyseisellä menetelmällä pakata jolloin lopputuloskin jää vaatimattomaksi. On kuitenkin mahdollista käyttämällä tehokkaampia algoritmeja päästä parempaan kompressiosuhteeseen kuin edellisissä esimerkeissä. Alkuperäsien data puolittaminen pitäisi olla hyvinkin mahdollista. Ongelman ytimenä on löytää musiikista tarpeeksi pitkiä toistuvia kuvioita, joita käsittelemällä saavutettaisiin paras lopputulos.

4.2 V.42bis

Eräänä mielenkiintoisena häviämättömän kompressoinnin sovellutuksena voidaan pitää myös V.42bis standardia, jonka laajamittaiseen käyttöön on kuitenkin ilmentynyt odottomattomia esteitä. Alun perin V.42bis kompressiostandardi esiteltiin CCITT:n toimesta (nykyinen ITU-T). Kompressiostandardi oli suunniteltu lisäominaisuus v.42 virhekorjausprotokollaa käyttäville modeemeille. Sen päämääränä on lisätä datavirtaa käyttämälla erästä Lempel-Ziv-Welch (LZW) kompressiometodin muunnosta. Käytännössä V.42bis standardi on tarkoitus implementoida modeemin piirilevylle, mutta se voidaan myös rakentaa ohjelmistopohjaiseksi jolloin se "keskustelee" tavallisen kompressoimattoman modeemin kanssa.

V.42bis voi lähettää dataa joko kompressoituna tai kompressoimattomana riippuen datasta. Kuten aikaisemmin on mainittu on olemassa tietoa jota ei voida pakata. Esimerkiksi jos lähettettävä tiedosto kompressoidaan ensin ei sen käsittelystä toiseen kertaan saavuteta mittään hyötyä - päinvastoin tiedoston koko mitä ilmeisimmin kasvaa tämän seurauksena. Jotta välttyttäisiin valmiiksi pakatun tiedon uudelleenkäsittelystä on algoritmin jatkuvasti monitoroitava datan pakkautuvuutta. Mikäli havaitaan että lähettettävä data on kooltaan pienempi ilman kompressiota siirtyy modeemi läpinäkyvään tilaan. Samalle vastapuolelle ilmoitetaan ennalta sovitulla koodilla, että lähetettävä tieto siirretään koskemattomana bittivirtana.

Kun tietoa siirretään läpinäkyvässä muodossa lähettäjä ei varsinaisesti kytke pois LZW kompressiota vaan laskee jatkuvasti onko sen käyttämisestä hyötyä. Mikäli kompression käyttö ilmenee tietyssä vaiheessa taas edullisemmaksi vaihtoehdoksi siirtyy lähettävä osapuoli pakkaavaan tilaan ilmoittaen samalla tästä vastapuolelle. Täten V.42bis standardi osaa automaattisesti sopeutua käsiteltävän tiedon piirteisiin.

Miksi sitten kukaan modeeminvalmistaja ei ole sisällyttänyt kyseistä ominaisuutta laitteisiinsa? Vastaus piilee patentti- ja lisenssointiongelmissa. V.42bis on patentoitu ja sen lisensointisäännöt ovat hyvin monimutkaisia. Lisensoinnin joutuu yleensä suorittamaan usealta taholta ja esimerkiksi British Telecom on vaatinut noin 30,000 punnan korvausta lisenssistä. Tämän johdosta kukaan modeeminvalmistaja ei ole sisällyttänyt sitä tuotteeseensa.

4.3 GIF

Graphic Interchange Format, eli lyhyesti GIF on ehkä yleisimmin läytössä oleva hävittämätön kuvaformaatti. On olemassa kaksi GIF erittelyä. Alkuperäinen GIF eli GIF87a julkistettiin vuonna 1987 ja sitä parannettiin vuonna 1989 GIF89a laajennuksella. GIF tiedostot voivat sisältää vain 8-bittisiä harmaasävykuvia tai 8-bittisiä värikuvia joiden värit ovat valittavissa 24-bitin paletista. Koska kuvien esittämiseen ei ole kuin 8-bittiä rajoittuu yhtä aikaa käytettävien värien määrä 256:een. Tätä voidaan pitää nykyaikaisten standardien mukaan riittämättömänä.

Kuvadata GIF tiedostossa kompressoidaan käyttämällä Lempel-Ziv (LZW) algoritmia ja syksynä 1994 Unisys Corporation , joka oli kyseisen algoritmin patentin omistaja alkoi vaatimaan lisensoimista LZW:n käytöstä. Tämä käytäntö ja 8-bittinen värirajoitus on ratkaisevasti vähentänyt formaatin käyttöä. Etuna on kuitenkin se, että lähes jokainen tietokonegrafiikkaohjelma tukee kyseistä koodaustapaa.

5. Häviöllisen kompression käyttö

Kun halutaan päästä parempaan kompressiotulokseen verrattuna hävittämättömillä algoritmeilla saavutettuihin on siirryttävä käyttämään hävittäviä kompressiomenetelmiä. Tosin kuin hävittämättömillä menetelmillä saatu täysin virheetön kopio alkuperäsestä tiedostosta ei hävittävällä metodilla päästä samaan tulokseen alkuperäiseen dataan verrattuna. Hävittävä pakkausmetodi siis hukkaa dataa, mutta saavuttaa huomattavasti paremman lopputuloksen pakkaussuhteessa. 5.1 JPEG ISO.n määrittelemä JPEG koodausehdotus on tarkoitettu still-kuvien kompressoimiseksi. Perusrakenne JPEG koodauksessa on mukautuva DCT koodaus, jossa kuva jaetaan sovitun kokoisiin alkioihin. Alkioiden koko on tavallisesti 8 x 8 kuvaelementtiä. DCT koodauksen jälkeen siirrytään kvantisointiin. Kuvan kvantisointia seuraa tuttu Huffmanin-pakkausmenetelmä, jonka jälkeen varsinainen kuva saadaan muodostettua. Kuva 1.

Digitoitu

JPEG toimii joko täysvärikuvissa tai harmaasävykuvissa. Se ei myöskään käsittele mustavalkokuvia kovin hyvin. JPEG toimii parhaiten kuvissa joissa on ole kovin voimakkaita kontrastin muutoksia. Kuvat joissa on yhtäkkisiä värinmuutoksia eivät täten sovellu sille hyvin. Kompressoinnissa on valittavana useita parametreja, joita säätelemällä voidaan kuvan kokoa ja laatua muuttaa hyvinkin radikaalisti. Heikkolaatuinen mutta yhä täysin tunnistettavissa oleva kuva voi olla sata kertaa pienempi kuin alkuperäinen 24-bittinen otos. Lähes virheetön tulos saavutetaan kuitenkin kuvalla, jonka koko on jopa kolme kertaa pienempi kuin alkuperäinen kappale. JPEG kompressiosta on olemassa myös erityinen hävittämätön versio, jossa saavutetaan noin 2:1 pakkaustaso.

5.2 MPEG

MPEG on yleisesti hyväksytty standardi liikkuvan kuvan pakkaamiseen. Itse asiassa MPEG jakautuu tällä hetkellä neljään eri tasoon. Namä tasot ovat pääpiirteiltään seuraavan kaltaisia. MPEG-1: Liikkuvan kuvan ja siihen liittyvän audion koodaus aina tasolle 1.5 Mbit/s. Status: Kansainvälinen standardi Is-11172, valmistunut lokakuussa 1992. MPEG-2: Yleinen "de facto" koodaus elävälle kuvalle ja siihen liityvälle audiolle. Status: Komitean luonnos CD 13818 kuten määritelty dokumenteissa MPEG93, N601, N602, N603, marraskuussa 1993. MPEG-3: Ei ole olemassa enää. Sulautettu MPEG-2:een. MPEG-4: Eritäin matalan siirtokaistan audiovisuaalinen koodaus. Satus: Esitetty marraskuussa 1994. Työluonnos esitelty marraskuussa 1996.Vielä kehittelyasteella.
Sekä MPEG-1 että MPEG-2 on jakautuvat kolmeen osaan. Systeemi, video ja audio-osaan. Systeemispesifikaatio yhdistää erillisen video ja audiosignaalin yhdeksi kokonaisuudeksi.

Koska suuri osa informaatiosta liikkuvassa kuvassa voidaan päätellä edeltävästä kuvasta käytetään tätä ominaisuutta hyväksi MPEG standardissa. MPEG standardi määrittelee kolme eri tyyppistä kuvaa. Intra eli I-kuvat on koodattu käyttämällä vain senhetkisen kuvan informaatiota. Predicted eli P-kuvat koodataan kuitenkin käyttämällä lähteenä edellistä I -tai P-kuvaa. Bi-directional kuvat käyttävät sekä edellisiä että tulevia kuvia referenssikohteena. Tätä metodia kutsutaan nimellä interpicture coding ja sitä käytetään liikkeen kompensoimiseksi.

MPEG standardi määrää myös ajoitusmekanismin, joka varmistaa audion ja videon synkronisoinnin.

6. Yhteenveto

Perinteisissä hävittämättömissä kompressiomenetelmissä ollaan saavuttamssa piste, jossa kompressoidun datan kokoa ei juurikaan saada enää pienennettyä. On kuitenkin odotettavissa, että kompressiomenetelmät tulevat räätälöitymään yhä yksilöllisempiin tarkoitusiin. Tästö voidaan pitää esimerkkinä musiikin pakkaamiseen tarkoitettuja algoritmeja. Koska musiikki sisältää varsin usein toistuvaa perusrytmiä voitaisiin tätä ominaisuutta hyödyntämällä päästä aikaisempaa parempiin tuloksiin. Työ ei kuitenkaan tule olemaan helppoa mikä luo arvoa onnistuneille menetelmille. Taloudelliset edut tulevat samalla mutkistamaan jo tällä hetkellä ilmenevää patenttien ja lisenssien viidakkoa, mistä ei välttämättä loppukuluttajalle ole hyötyä.

Suhteellisen uusi mutta lupaava metodi pakkauksen alalla saattaa olla fraktaalien käyttö. Fraktaaleilla voidaan simuloida maisemia tai muita luonnollisia kuvia ja se saavuttaa usein hyviä kompressiosuhteita sellaisissa kuvissa joissa perinteiset menetelmät epäonnistuvat. Menetelmän heikkoutena voidaan pitää sen vaatimaa suurta laskutehoa. Toinen epäkohta on fraktaalikompression huono soveltuvuus esim. ASCII tekstin kompressoiniin. Oikealla tavalla käytettynä voidaan kuitenkin kyseisellä menetelmällä päästä hyvin suurin kompressiosuhteisiin, jopa 1:10000, ja kuvaa voidaan tarkentaa äärettömästi laskentakapasiteetin mukaan.

7. Lähteet

1: Risto Hämeen-Anttila, Pertti Hölttä, Seppo Niinioja, Tietoliikennejärjestelmät, 1993

2: GIF, Graphics Interchange Format Specification, CompuServe Incorporated, June 15 1987,

3: Tiedon kompressonnin seminaari 1995

4: Rafael C. Gonzales, Richard E. Woods, Digital Image Processing, 1993

5: JPEG-1 DIS, Draft International Standard, DIS 10918, CCITT Rec. T.81, Working Group 10, New York, Jan.2, 1992.

6: http://www.cs.ruu.nl/wais/html/na-dir/compression-faq/