Färgcellskomprimering

Color Cell Compression är en bildkomprimeringsalgoritm med förlust som utvecklades av Campbell et al., 1986, som kan anses vara en tidig föregångare till moderna texturkomprimeringsalgoritmer, såsom S3 Texture Compression och Adaptive Scalable Texture Compression . Det är nära besläktat med Block Truncation Coding , en annan bildkomprimeringsalgoritm med förlust, som föregår Color Cell Compression, genom att den använder den dominerande luminansen hos ett block av pixlar för att dela upp nämnda pixlar i två representativa färger. Den primära skillnaden mellan Block Truncation Coding och Color Cell Compression är att den förra utformades för att komprimera gråskalebilder och den senare utformades för att komprimera färgbilder. Block Truncation Coding kräver också att standardavvikelsen för färgerna på pixlar i ett block beräknas för att komprimera en bild, medan Color Cell Compression inte använder standardavvikelsen. Båda algoritmerna kan dock komprimera en bild till effektivt 2 bitar per pixel.

Original okomprimerad 24-bitars per pixel färgbild

CCC-komprimerad bild, men med endast 24-bitars till 15-bitars färgkvantisering kombinerat med en luminansbitmapp för 2,875 bitar per pixel (utan palett/uppslagstabell)

256 ingångspalett/uppslagstabellimplementering av CCC-algoritmen med 2 bitar per pixel med paletten byggd med K-means-klustring

Resultat av resultatet av Mandrill-standardtestbilden komprimerad med CCC-algoritmen vid 2-bitars per pixel med en 256 ingångspalett/uppslagstabell genererad med en naiv 15-bitars färghistogramalgoritm

Algoritm

Kompression

Algoritmen för färgcellskomprimering bearbetar en bild i åtta steg, även om ett av stegen (steg #6) är valfritt. Det antas här att ingången är en 24 bitar/pixel bild, vilket antas i den ursprungliga tidskriftsartikeln, även om andra bitdjup kan användas.

1. För varje 8-bitars RGB-oktetttrippel som ingår i varje 24-bitars färgvärde i ingångsbilden, beräknas NTSC- luminansen ${\textstyle y} med hjälp av följande formel:$
   $$y=0,30\ gånger röd+0,59\ gånger grön+0,11\ gånger blå$$
2. Bilden är nu uppdelad i 4-pixel med 4-pixelblock, och det aritmetiska medelvärdet av luminansen för varje pixel i blocket används för att välja ett representativt luminansvärde.
3. Varje block med pixlar delas sedan in i två grupper. En grupp består av pixlar i det aktuella blocket där varje pixels luminans är större än eller lika med den representativa luminansen för det aktuella blocket. Den andra gruppen av pixlar består av pixlar i det aktuella blocket där varje pixels luminans är mindre än den representativa luminansen för det aktuella blocket. Huruvida en pixel i det aktuella blocket tillhör en viss grupp bestäms av ett binärt "0"- eller ett "1"-värde i en annan, separat bitmapp med 16 poster .
4. Två representativa 24-bitars färger väljs nu för varje block av pixlar genom att beräkna två aritmetiska medel. Det första aritmetiska medelvärdet är det aritmetiska medelvärdet av alla pixlar som tillhör den första gruppen av pixlar där luminansen för varje pixel är en "1" i luminansbitmappen. Den andra 24-bitars representativa färgen väljs på liknande sätt genom att ta det aritmetiska medelvärdet av alla 24-bitars färgpixlar i den andra gruppen där varje pixel motsvarar en "O" i luminansbitmappen.
5. Luminansbitmappen lagras på en tillfällig plats och sedan läggs de två 24-bitars representativa färgerna för det aktuella blocket till i bitmappen. I detta skede har bilden komprimerats till en bitmapp med 16 poster med två 24-bitars binära värden bifogade. Den totala storleken på det komprimerade blocket är nu 16 bitar för luminansbitmappen och två 24-bitars binära kvantiteter för varje representativ färg, vilket ger en total storlek på 64 bitar, som, när de divideras med 16 (antalet pixlar i blocket ), ger 4 dvs 4 bitar per pixel.
6. Varje komprimerat pixelblock modifieras genom att var och en av de två 24-bitars representativa färgerna trunkeras till 15 bitar. Detta steg är valfritt, och algoritmen kan avslutas vid denna tidpunkt, om så önskas, eftersom de komprimerade blocken i detta skede har en total storlek på ${\textstyle 16+2\ gånger 15=46}$ bitar, som, dividerat med 16, ger 2,875 bitar per pixel. Om detta steg utförs kan de 15-bitars trunkerade färgvärdena användas i nästa steg för att skapa ett mindre histogram. Dessutom, eftersom varje 15-bitars binär färgvektor förmodligen är lagrad i ett 16-bitars ord, kan den 16:e biten användas för att förbättra bildkvaliteten genom att specificera vilken av två uppslagstabeller som ska användas.
7. Ett histogram av alla 24-bitars färger i den ursprungliga 24-bitars färgbilden, eller de trunkerade 15-bitars färgvektorerna, skapas. I en naiv implementering konsulteras histogrammet för att välja 256 av de mest använda färgerna som sedan läggs in i en 256-entry-array, där varje post består av tre oktetter av ett 24-bitars per pixel färgvärde. Histogrammetoden för att välja de mest lämpliga färgerna för den ursprungliga färgbilden med 24-bitars per pixel kan istället ersättas av en vektorkvantiseringsklassalgoritm som median cut- algoritmen eller K-means clustering som vanligtvis ger bättre resultat.
8. uppslagstabellen med 256 poster som bäst matchar de två representativa färgerna för varje block. De två 8-bitarsindex som pekar på färger i uppslagstabellen är nu bifogade till 16-bitars luminansbitmappen. Detta ger en total komprimerad storlek på ${\textstyle 16+8+8=32}$ bitar, vilket, dividerat med 16, ger 2 bitar per pixel.

Dekompression

Dekompression är väldigt enkelt och okomplicerat. För att rekonstruera varje komprimerat 4-pixel för 4-pixelblock, konsulteras 16-bitars luminansbitmappen för varje block. Beroende på om ett element i bitmappen är 1 eller 0, väljs ett av de två 8-bitarsindexen i uppslagstabellen och hänvisas sedan bort och motsvarande 24-bitars per pixel färgvärde hämtas.

Prestanda och bildkvalitet

Trots sin mycket enkla mekanism ger algoritmen förvånansvärt bra resultat på fotografiska bilder, och den har fördelen att den är mycket snabb att avkoda med begränsad hårdvara. Även om den vida överträffas i komprimeringsförhållande av senare blocktransformeringskodningsmetoder såsom JPEG , har den fördelen av mycket enkel dekomprimering och snabb slumpmässig åtkomst till den komprimerade bilden.

Apple Video (RPZA) och S3 Texture Compression använder samma princip för att koda 4×4-pixelblock baserat på två representativa färger. De förfinar CCC genom att utöka varje post i luminansbitmappen till två bitar, där de ytterligare två värdena representerar ett viktat medelvärde: en tredjedel av en färg och två tredjedelar av den andra. För att kringgå S3:s patent skapades biblioteket Super Simple Texture Compression ( S2TC ) för att koda CCC-data i ett format som är kompatibelt med S3TC-avkodare och för att omtolka S3TC som CCC med mindre kvalitetsförlust.

Se även

• Indexerad färg
• Adaptiv skalbar texturkomprimering
• S3 Texture Compression