Komprese barevných buněk - Color Cell Compression
Color Cell Compression je ztrátový algoritmus komprese obrazu vyvinutý Campbellem a kol. V roce 1986, který lze považovat za předchůdce moderních algoritmů komprese textur, jako je S3 Texture Compression a Adaptive Scalable Texture Compression . Úzce souvisí s Block Truncation Coding , dalším ztrátovým algoritmem komprese obrazu, který předchází kompresi barevných buněk, v tom, že používá dominantní jas bloku pixelů k rozdělení uvedených pixelů do dvou reprezentativních barev. Primární rozdíl mezi blokovým zkrácením a komprimací barevných buněk spočívá v tom, že první byl navržen pro kompresi obrázků ve stupních šedi a druhý pro kompresi barevných obrázků. Blokové zkrácení také vyžaduje, aby byla standardní odchylka barev pixelů v bloku vypočítána za účelem komprese obrázku, zatímco komprese barevných buněk standardní odchylku nepoužívá. Oba algoritmy však mohou komprimovat obraz až na efektivně 2 bity na pixel.
Algoritmus
Komprese
Algoritmus komprese barevných buněk zpracovává obraz v osmi krocích, i když jeden z kroků (krok č. 6) je volitelný. Zde se předpokládá, že vstup je obraz 24 bitů / pixel, jak se předpokládá v původním článku časopisu, i když lze použít i jiné bitové hloubky .
- Pro každou 8bitovou trojici oktetů RGB obsaženou v každé 24bitové hodnotě barvy ve vstupním obrazu je jas NTSC vypočítán pomocí následujícího vzorce:
- Obraz je nyní rozdělen na bloky 4 pixely na 4 pixely a pro výběr reprezentativní hodnoty jasu se použije aritmetický průměr jasu každého pixelu v bloku.
- Každý blok pixelů je poté rozdělen do dvou skupin. Jedna skupina se skládá z pixelů v aktuálním bloku, kde je svítivost každého pixelu větší nebo rovna reprezentativní svítivosti pro aktuální blok. Druhá skupina pixelů se skládá z pixelů v aktuálním bloku, kde je jas každého pixelu menší než reprezentativní jas pro aktuální blok. To, zda pixel v aktuálním bloku patří do určité skupiny, je určeno binární hodnotou „0“ nebo hodnotou „1“ v jiné samostatné bitmapě se 16 vstupy .
- Pro každý blok pixelů jsou nyní vybrány dvě reprezentativní 24bitové barvy výpočtem dvou aritmetických průměrů. První aritmetický průměr je aritmetický průměr všech pixelů patřících do první skupiny pixelů, kde jas každého pixelu je v bitmapě jasu „1“. Druhá 24bitová reprezentativní barva je vybrána podobně, přičemž se vezme aritmetický průměr všech 24bitových barevných pixelů ve druhé skupině, kde každý pixel odpovídá „0“ v bitmapě jasu.
- Bitmapa jasu je uložena na dočasném místě a poté jsou k bitmapě připojeny dvě 24bitové reprezentativní barvy pro aktuální blok. V této fázi byl obraz komprimován do 16ti bitmapové mapy s připojenými dvěma 24bitovými binárními hodnotami. Celková velikost komprimovaného bloku je nyní 16 bitů pro bitmapu jasu a dvě 24bitové binární veličiny pro každou reprezentativní barvu, čímž se získá celková velikost 64 bitů, která, když se dělí 16 (počet pixelů v bloku) ), poskytuje 4 tj. 4 bity na pixel.
- Každý komprimovaný blok pixelů je upraven zkrácením každé ze dvou 24bitových reprezentativních barev na 15 bitů. Tento krok je volitelný a algoritmus může být v tomto okamžiku ukončen, pokud je to žádoucí, protože komprimované bloky v této fázi mají celkovou velikost bitů, která, když se dělí 16, poskytuje 2,875 bitů na pixel. Pokud je tento krok proveden, pak lze v dalším kroku použít 15bitové zkrácené hodnoty barev k vytvoření menšího histogramu. Jelikož je každý 15bitový binární barevný vektor pravděpodobně uložen v 16bitovém slově, lze 16. bit použít ke zlepšení kvality obrazu určením, která z těchto dvou vyhledávacích tabulek by měla být použita.
- Vytvoří se histogram všech 24bitových barev v původním 24bitovém barevném obrázku nebo zkrácených 15bitových barevných vektorů. V naivní implementaci je histogram konzultován, aby vybral 256 nejčastěji používaných barev, které jsou poté vloženy do 256-vstupního pole, kde každý záznam sestává ze tří oktetů s hodnotou barvy 24 bitů na pixel. Metodu histogramu pro výběr nejvhodnějších barev pro původní barevný obrázek 24 bitů na pixel lze místo toho nahradit algoritmem třídy vektorové kvantizace, jako je algoritmus mediánu řezu nebo shlukování K-means, které obvykle přináší lepší výsledky.
- Poslední krok spočívá v převzetí aktuálního bloku pixelů a určení, která barva 24 bitů na pixel ve vyhledávací tabulce 256 vstupů nejvíce odpovídá dvěma reprezentativním barvám pro každý blok. Dva 8bitové indexy ukazující na barvy ve vyhledávací tabulce jsou nyní připojeny k 16bitové bitmapě jasu. Tím se získá celková komprimovaná velikost bitů, která po rozdělení na 16 poskytne 2 bity na pixel.
- Pro každou 8bitovou trojici oktetů RGB obsaženou v každé 24bitové hodnotě barvy ve vstupním obrazu je jas NTSC vypočítán pomocí následujícího vzorce:
Dekomprese
Dekomprese je velmi snadná a přímá. K rekonstrukci každého komprimovaného bloku 4 pixely na 4 pixely je pro každý blok konzultována 16bitová bitmapa jasu. V závislosti na tom, zda je prvek bitmapy 1 nebo 0, je vybrán jeden ze dvou 8bitových indexů do vyhledávací tabulky a poté dereferencován a načtena odpovídající hodnota barvy 24 bitů na pixel.
Výkon a kvalita obrazu
Navzdory svému velmi jednoduchému mechanismu poskytuje algoritmus překvapivě dobré výsledky na fotografických obrázcích a jeho výhodou je velmi rychlé dekódování s omezeným hardwarem. Ačkoli je v kompresním poměru daleko překonán pozdějšími metodami kódování blokových transformací, jako je JPEG , má výhodu velmi jednoduché dekomprese a rychlého náhodného přístupu ke komprimovanému obrazu.
