Komprese barevných buněk - Color Cell Compression


Komprese barevných buněk je ztrátový komprese obrazu algoritmus vyvinutý Campbellem et al.,[1][2][3] v roce 1986, který lze považovat za předchůdce moderních algoritmů komprese textur, jako je Komprese textury S3 a Adaptivní škálovatelná komprese textury. Je to úzce spjato s Blokové zkrácení kódování,[4] další ztrátový algoritmus komprese obrazu, který předchází kompresi barevných buněk, v tom, že používá dominantní jas bloku pixelů rozdělit uvedené pixely do dvou reprezentativních barev. Primární rozdíl mezi blokovým zkrácením a kompresí 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 standardní odchylka barev pixelů v bloku se vypočítá za účelem komprese obrazu, zatímco komprese barevných buněk nepoužívá standardní odchylku. Oba algoritmy však mohou komprimovat obraz až na efektivně 2 bity na pixel.

Detail mandrilky s různými barvami
Originální nekomprimovaný barevný obrázek 24 bitů na pixel
Komprimovaný obrázek výše uvedeného standardního zkušebního obrazu Mandrill
Komprimovaný obraz CCC, ale s použitím pouze 24bitové až 15bitové barevné kvantizace kombinované s bitmapou jasu pro 2,875 bitů na pixel (bez palety / vyhledávací tabulky)
Viz titulek
Implementace 256 vstupních palet / vyhledávací tabulky algoritmu CCC na 2 bity na pixel s paletou vytvořenou pomocí shlukování K-means
Viz titulek
Výsledek výstupu standardního testovacího obrazu Mandrill komprimovaného algoritmem CCC při 2 bitech na pixel s 256 vstupními paletami / vyhledávací tabulkou generovanou pomocí naivního algoritmu 15bitového barevného histogramu

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 vstupem je obraz 24 bitů / pixel, jak se předpokládá v původním článku časopisu, i když jiný bitové hloubky lze použít.

  1. Pro každý 8bitový trojnásobek RGB oktetu obsažený v každé 24bitové barevné hodnotě ve vstupním obrazu, NTSC jas se počítá pomocí následujícího vzorce:[1][2][3]
  2. Obrázek je nyní rozdělen na bloky o velikosti 4 pixely a 4 pixely, a, aritmetický průměr jasu každého pixelu v bloku se používá k výběru reprezentativní hodnoty jasu.[1][2][3]
  3. 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 jas každého pixelu větší nebo roven reprezentativní jasu 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é položce se 16 vstupy bitmapa.[1][2][3]
  4. 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 použije aritmetický průměr všech 24bitových barevných pixelů ve druhé skupině, kde každý pixel odpovídá „0“ v bitmapě jasu.[1][2][3]
  5. 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.[1][2][3]
  6. Každý komprimovaný blok pixelů je upraven pomocí zkrácení 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é po rozdělení na 16 poskytnou 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.[1][2][3]
  7. 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 střední řez algoritmus, který obvykle přináší lepší výsledky.[1][2][3]
  8. Posledním krokem je převzetí aktuálního bloku pixelů a určení, která barva 24 bitů na pixel je v položce 256 vyhledávací tabulka nejvíce odpovídají 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é, když se dělí 16, poskytnou 2 bity na pixel.[1][2][3]

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é odhlášeno a načte se odpovídající hodnota barvy 24 bitů na pixel.[1][2][3]


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,[1][2][3] a jeho výhodou je velmi rychlé dekódování s omezeným hardwarem. Ačkoli daleko překonán kompresní poměr 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.

Viz také

Reference

  1. ^ A b C d E F G h i j k Campbell, G .; Defanti, T. A .; Frederiksen, J .; Joyce, S. A .; Leske, L. A. (1986). Msgstr "Plně barevné kódování dvou bitů / pixelů". Sborník 13. ročníku konference Počítačová grafika a interaktivní techniky - SIGGRAPH '86. p. 215. doi:10.1145/15922.15910. ISBN  978-0-89791-196-2.
  2. ^ A b C d E F G h i j k Pins, Markus (1991). Rozšíření algoritmu komprese barevných buněk. Počítačová animace '91. str. 241–251. doi:10.1007/978-4-431-66890-9_17. ISBN  978-4-431-66892-3.
  3. ^ A b C d E F G h i j k Lamparter, Bernd Effelsberg, Wolfgang (červen 2005). Vylepšená komprese barevných buněk: Runtime efektivní schéma komprese pro softwarové video. Multimédia: Advanced Teleservices a architektury vysokorychlostní komunikace. Přednášky z informatiky. 868. 181–190. doi:10.1007/3-540-58494-3_16. ISBN  978-3-540-58494-0.CS1 maint: více jmen: seznam autorů (odkaz)[trvalý mrtvý odkaz ]
  4. ^ Wennersten, P .; Ström, J. (2009). „Tabulka založená na kompresi alfa“ (PDF ). Fórum počítačové grafiky. 28 (2): 687. doi:10.1111 / j.1467-8659.2009.01409.x.