Kleurcelcompressie - Color Cell Compression
Color Cell Compression is een verlieslatend algoritme voor beeldcompressie dat in 1986 is ontwikkeld door Campbell et al. En dat kan worden beschouwd als een vroege voorloper van moderne algoritmen voor textuurcompressie, zoals S3 Texture Compression en Adaptive Scalable Texture Compression . Het is nauw verwant aan Block Truncation Coding , een ander verlieslatend algoritme voor beeldcompressie, dat ouder is dan Color Cell Compression, doordat het de dominante luminantie van een blok pixels gebruikt om de pixels in twee representatieve kleuren te verdelen. Het belangrijkste verschil tussen Block Truncation Coding en Color Cell Compression is dat de eerste is ontworpen om afbeeldingen in grijstinten te comprimeren en de laatste is ontworpen om kleurenafbeeldingen te comprimeren. Block Truncation Coding vereist ook dat de standaarddeviatie van de kleuren van pixels in een blok wordt berekend om een afbeelding te comprimeren, terwijl Color Cell Compression niet de standaarddeviatie gebruikt. Beide algoritmen kunnen een afbeelding echter comprimeren tot effectief 2 bits per pixel.
Algoritme
Compressie
Het algoritme Color Cell Compression verwerkt een afbeelding in acht stappen, hoewel een van de stappen (stap # 6) optioneel is. Aangenomen wordt hier dat de invoer een 24 bits / pixel afbeelding is, zoals aangenomen in het originele tijdschriftartikel, hoewel andere bitdieptes gebruikt zouden kunnen worden.
- Voor elk 8-bits RGB-octet-triple vervat in elke 24-bits kleurwaarde in het invoerbeeld, wordt de NTSC- luminantie berekend met behulp van de volgende formule:
- Het beeld is nu onderverdeeld in blokken van 4 pixel bij 4 pixel, en het rekenkundig gemiddelde van de luminantie van elke pixel in het blok wordt gebruikt om een representatieve luminantiewaarde te selecteren.
- Elk blok pixels wordt vervolgens in twee groepen verdeeld. Een groep bestaat uit pixels in het huidige blok waarbij de luminantie van elke pixel groter is dan of gelijk is aan de representatieve luminantie voor het huidige blok. De tweede groep pixels bestaat uit pixels in het huidige blok waarbij de luminantie van elke pixel kleiner is dan de representatieve luminantie voor het huidige blok. Of een pixel in het huidige blok tot een bepaalde groep behoort, wordt bepaald door een binaire "0" of een "1" -waarde in een andere, afzonderlijke bitmap met 16 ingangen .
- Twee representatieve 24-bits kleuren worden nu geselecteerd voor elk blok pixels door twee rekenkundige middelen te berekenen. Het eerste rekenkundig gemiddelde is het rekenkundig gemiddelde van alle pixels die tot de eerste groep pixels behoren, waarbij de luminantie van elke pixel een "1" is in de luminantiebitmap. De tweede 24-bits representatieve kleur wordt op dezelfde manier geselecteerd door het rekenkundig gemiddelde te nemen van alle 24-bits kleurenpixels in de tweede groep, waarbij elke pixel overeenkomt met een "0" in de luminantiebitmap.
- De luminantiebitmap wordt op een tijdelijke locatie opgeslagen en vervolgens worden de twee 24-bits representatieve kleuren voor het huidige blok aan de bitmap toegevoegd. In dit stadium is de afbeelding gecomprimeerd tot een bitmap met 16 ingangen waaraan twee 24-bits binaire waarden zijn toegevoegd. De totale grootte van het gecomprimeerde blok is nu 16 bits voor de luminantiebitmap en twee 24-bits binaire grootheden voor elke representatieve kleur, wat een totale grootte van 64 bits oplevert, die, wanneer gedeeld door 16 (het aantal pixels in het blok ), levert 4 dwz 4 bits per pixel op.
- Elk gecomprimeerd blok pixels wordt gemodificeerd door het afknotten van elk van de twee 24-bits representatief kleuren 15 bits. Deze stap is optioneel en het algoritme kan desgewenst op dit punt eindigen, aangezien de gecomprimeerde blokken in dit stadium een totale grootte van bits hebben, die, wanneer gedeeld door 16, 2,875 bits per pixel oplevert. Als deze stap wordt uitgevoerd, kunnen de 15-bits afgekapte kleurwaarden in de volgende stap worden gebruikt om een kleiner histogram te maken. Aangezien elke 15-bits binaire kleurenvector vermoedelijk wordt opgeslagen in een 16-bits woord, kan de 16e bit worden gebruikt om de beeldkwaliteit te verbeteren door te specificeren welke van de twee opzoektabellen moet worden gebruikt.
- Er wordt een histogram gemaakt van alle 24-bits kleuren in de originele 24-bits kleurenafbeelding of de afgekapte 15-bits kleurvectoren. In een naïeve implementatie wordt het histogram geraadpleegd om 256 van de meest gebruikte kleuren te kiezen, die vervolgens in een 256-entry-array worden geplaatst, waarbij elke entry bestaat uit drie octetten van een 24-bit per pixel kleurwaarde. De histogrammethode voor het selecteren van de meest geschikte kleuren voor het originele 24-bits per pixel kleurenbeeld kan in plaats daarvan worden vervangen door een vectorkwantiseringsklasse-algoritme, zoals het median cut- algoritme of K-mean-clustering, wat gewoonlijk betere resultaten oplevert.
- De laatste stap bestaat uit het nemen van het huidige pixelblok en het bepalen welke 24-bits per pixelkleur in de opzoektabel met 256 ingangen het meest overeenkomt met de twee representatieve kleuren voor elk blok. De twee 8-bits indices die naar kleuren in de opzoektabel wijzen, worden nu toegevoegd aan de 16-bits luminantiebitmap. Dit levert een totale gecomprimeerde grootte van bits op, die, wanneer gedeeld door 16, 2 bits per pixel oplevert.
- Voor elk 8-bits RGB-octet-triple vervat in elke 24-bits kleurwaarde in het invoerbeeld, wordt de NTSC- luminantie berekend met behulp van de volgende formule:
Decompressie
Decompressie is heel eenvoudig en ongecompliceerd. Om elk gecomprimeerd blok van 4 pixel bij 4 pixel te reconstrueren, wordt voor elk blok de 16-bits luminantiebitmap geraadpleegd. Afhankelijk van het feit of een element van de bitmap 1 of 0 is, wordt een van de twee 8-bits indices in de opzoektabel geselecteerd en vervolgens gedereferentieerd en wordt de bijbehorende 24-bits kleurwaarde per pixel opgehaald.
Prestaties en beeldkwaliteit
Ondanks zijn zeer eenvoudige mechanisme, levert het algoritme verrassend goede resultaten op fotografische afbeeldingen, en het heeft het voordeel dat het zeer snel te decoderen is met beperkte hardware. Hoewel de compressieverhouding ver overtroffen wordt door latere coderingsmethoden voor bloktransformatie, zoals JPEG , heeft het het voordeel van een zeer eenvoudige decompressie en snelle willekeurige toegang tot het gecomprimeerde beeld.
