Värisolupakkaus - Color Cell Compression
Colour Cell Compression on häviöllinen kuvan pakkausalgoritmi, jonka Campbell et ai., Vuonna 1986 kehitti, voidaan pitää nykyaikaisen tekstuuripakkausalgoritmien, kuten S3-tekstuurikompression ja adaptiivisen skaalautuvan tekstuuripakkauksen, varhaisena edelläkävijänä . Se liittyy läheisesti Block Katkaisumerkki Coding , toinen häviöllinen kuvan pakkaus algoritmi, joka edeltää Väri Cell Compression, että se käyttää hallitseva luminanssi lohkon pikselien osioon mainitut pikselit kahden edustavan väriä. Ensisijainen ero lohkon katkaisukoodauksen ja värisolujen pakkauksen välillä on se, että ensimmäinen on suunniteltu pakkaamaan harmaasävykuvia ja jälkimmäinen värikuvia. Lohkon katkaisukoodaus edellyttää myös, että lohkossa olevien pikselien värien keskihajonta lasketaan kuvan pakkaamiseksi, kun taas Värisolujen pakkaus ei käytä keskihajontaa. Molemmat algoritmit voivat kuitenkin pakata kuvan alas 2 bittiin / pikseli.
Algoritmi
Puristus
Värisolujen pakkausalgoritmi käsittelee kuvaa kahdeksassa vaiheessa, vaikka yksi vaiheista (vaihe 6) on valinnainen. Oletetaan tässä, että tulo on 24 bittiä / pikseli kuva, kuten alkuperäisessä lehtiartikkelissa oletetaan, vaikka muita bittisyvyyksiä voitaisiin käyttää.
- Jokaiselle 8-bittiselle RGB-oktettikolmikolle, joka on jokaisessa 24-bittisessä väriarvossa tulokuvassa, NTSC- luminanssi lasketaan seuraavan kaavan avulla:
- Kuva on nyt jaettu 4 pikseliin 4 pikselin lohkoina, ja lohkon kunkin pikselin luminanssin aritmeettista keskiarvoa käytetään edustavan luminanssiarvon valitsemiseen.
- Jokainen pikselilohko jaetaan sitten kahteen ryhmään. Yksi ryhmä koostuu nykyisen lohkon pikseleistä, joissa kunkin pikselin luminanssi on suurempi tai yhtä suuri kuin nykyisen lohkon edustava luminanssi. Toinen pikseliryhmä koostuu nykyisen lohkon pikseleistä, joissa kunkin pikselin luminanssi on pienempi kuin nykyisen lohkon edustava luminanssi. Se, kuuluuko nykyisen lohkon pikseli tiettyyn ryhmään, määräytyy binaarisen "0" - tai "1" -arvon perusteella toisessa erillisessä 16 merkinnän bittikartassa .
- Kullekin pikselilohkolle valitaan nyt kaksi edustavaa 24-bittistä väriä laskemalla kaksi aritmeettista keskiarvoa. Ensimmäinen aritmeettinen keskiarvo on kaikkien ensimmäiseen pikseliryhmään kuuluvien pikselien aritmeettinen keskiarvo, jossa kunkin pikselin luminanssi on "1" luminanssibittikartassa. Toinen 24-bittinen edustava väri valitaan samalla tavalla ottamalla kaikkien 24-bittisten väripikselien aritmeettinen keskiarvo toisessa ryhmässä, jossa kukin pikseli vastaa "0" luminanssibittikartassa.
- Luminanssibittikartta tallennetaan väliaikaiseen sijaintiin ja sitten nykyisen lohkon kaksi 24-bittistä edustavaa väriä liitetään bittikarttaan. Tässä vaiheessa kuva on pakattu 16 merkinnän bittikartaksi, johon on liitetty kaksi 24-bittistä binaariarvoa. Pakatun lohkon kokonaiskoko on nyt 16 bittiä luminanssin bittikartalle ja kaksi 24-bittistä binäärimäärää kutakin edustavaa väriä varten, jolloin saadaan 64 bitin kokonaiskoko, joka jaettuna 16: lla (lohkossa olevien pikselien lukumäärä) ) tuottaa 4 eli 4 bittiä per pikseli.
- Kutakin pakattua pikselilohkoa muokataan katkaisemalla molemmat 24-bittiset edustavat värit 15 bitiksi. Tämä vaihe on valinnainen, ja algoritmi voi päättyä tässä vaiheessa haluttaessa, koska tässä vaiheessa pakatuilla lohkoilla on bittikoko, joka jaettuna 16: lla tuottaa 2,875 bittiä per pikseli. Jos tämä vaihe suoritetaan, 15-bittisiä typistettyjä väriarvoja voidaan käyttää seuraavassa vaiheessa pienemmän histogrammin luomiseen. Lisäksi koska jokainen 15-bittinen binäärivärivektori on oletettavasti tallennettu 16-bittiseen sanaan, niin 16. bittiä voidaan käyttää parantamaan kuvan laatua määrittämällä kumpi kahdesta hakutaulukosta tulisi käyttää.
- Histogrammi kaikista 24-bittisistä väreistä alkuperäisessä 24-bittisessä värikuvassa tai katkaistut 15-bittiset värivektorit luodaan. Naiivisessa toteutuksessa histogrammia käytetään valitsemaan 256 yleisimmin käytettyä väriä, jotka sitten laitetaan 256 merkintäryhmään, jossa kukin merkintä koostuu kolmesta oktetista 24-bittistä pikselin väri-arvoa. Histogrammimenetelmä sopivimpien värien valitsemiseksi alkuperäiselle 24-bittiselle pikselivärikuvalle voidaan sen sijaan korvata vektorikvantisointiluokan algoritmilla, kuten mediaanileikkausalgoritmi tai K- keskimääräinen klusterointi, joka tuottaa yleensä parempia tuloksia.
- Viimeinen vaihe koostuu nykyisen pikselilohkon ottamisesta ja sen määrittämisestä, mikä 24-bittinen pikseliväri 256 merkinnän hakutaulukossa vastaa parhaiten kunkin lohkon kahta edustavaa väriä. Hakutaulukon kaksi väreihin osoittavaa 8-bittistä indeksiä on nyt liitetty 16-bittiseen luminanssibittikarttaan. Tämä tuottaa pakatun bittikokonaisuuden, joka jaettuna 16: lla tuottaa 2 bittiä per pikseli.
- Jokaiselle 8-bittiselle RGB-oktettikolmikolle, joka on jokaisessa 24-bittisessä väriarvossa tulokuvassa, NTSC- luminanssi lasketaan seuraavan kaavan avulla:
Dekompressiota
Pakkauksen purku on erittäin helppoa ja suoraviivaista. Jokaisen pakatun 4-pikselin rekonstruoimiseksi 4-pikselilohkona, 16-bittinen luminanssibittikartta etsitään kullekin lohkolle. Riippuen siitä, onko bittikartan elementti 1 vai 0, valitaan toinen hakutaulukon kahdesta 8-bittisestä indeksistä ja sen jälkeen viitataan ja vastaava 24-bittinen per pikseliväri-arvo haetaan.
Suorituskyky ja kuvanlaatu
Hyvin yksinkertaisesta mekanismistaan huolimatta algoritmi tuottaa yllättävän hyviä tuloksia valokuvista, ja sillä on se etu, että se on erittäin nopea purkaa rajoitetulla laitteistolla. Vaikka pakkaussuhde on selvästi ylitetty myöhemmillä lohkonmuunnoskoodausmenetelmillä, kuten JPEG , sillä on etuna erittäin yksinkertainen purku ja nopea satunnainen pääsy pakattuun kuvaan.
