Compresión de celdas de color

El algoritmo de compresión de celdas de color procesa una imagen en ocho pasos, aunque uno de ellos (el paso n.° 6) es opcional. Aquí se asume que la entrada es una imagen de 24 bits/píxel, tal como se indica en el artículo original, si bien podrían utilizarse otras profundidades de bits .

1. Para cada triplete de octetos RGB de 8 bits contenido en cada valor de color de 24 bits en la imagen de entrada, la luminancia NTSC${\textstyle y}$se calcula utilizando la siguiente fórmula: ^{[ 1 ] [ 2 ] [ 3 ]}$${\displaystyle y=0.30\times red+0.59\times green+0.11\times blue}$$
2. La imagen ahora se subdivide en bloques de 4 píxeles por 4 píxeles, y se utiliza la media aritmética de la luminancia de cada píxel en el bloque para seleccionar un valor de luminancia representativo. ^{[ 1 ] [ 2 ] [ 3 ]}
3. Cada bloque de píxeles se divide en dos grupos. Un grupo está formado por los píxeles del bloque actual cuya luminancia es mayor o igual a la luminancia representativa del bloque. El segundo grupo está formado por los píxeles del bloque actual cuya luminancia es menor que la luminancia representativa del bloque. La pertenencia de un píxel del bloque actual a un grupo determinado se determina mediante un valor binario "0" o "1" en otro mapa de bits independiente de 16 entradas . ^{[ 1 ] [ 2 ] [ 3 ]}
4. Ahora se seleccionan dos colores representativos de 24 bits para cada bloque de píxeles calculando dos medias aritméticas. La primera media aritmética es la media aritmética de todos los píxeles que pertenecen al primer grupo de píxeles donde la luminancia de cada píxel es un "1" en el mapa de bits de luminancia. El segundo color representativo de 24 bits se selecciona de manera similar, tomando la media aritmética de todos los píxeles de color de 24 bits en el segundo grupo donde cada píxel corresponde a un "0" en el mapa de bits de luminancia. ^{[ 1 ] [ 2 ] [ 3 ]}
5. El mapa de bits de luminancia se almacena en una ubicación temporal y luego se agregan al mapa de bits los dos colores representativos de 24 bits para el bloque actual. En esta etapa, la imagen se ha comprimido en un mapa de bits de 16 entradas con dos valores binarios de 24 bits agregados. El tamaño total del bloque comprimido es ahora de 16 bits para el mapa de bits de luminancia y dos cantidades binarias de 24 bits para cada color representativo, lo que da como resultado un tamaño total de 64 bits, que, cuando se divide por 16 (el número de píxeles en el bloque), da como resultado 4, es decir, 4 bits por píxel. ^{[ 1 ] [ 2 ] [ 3 ]}
6. Cada bloque comprimido de píxeles se modifica truncando cada uno de los dos colores representativos de 24 bits a 15 bits. Este paso es opcional, y el algoritmo puede terminar en este punto, si se desea, ya que los bloques comprimidos en esta etapa tienen un tamaño total de${\textstyle 16+2\times 15=46}$bits, que, al dividirse por 16, dan como resultado 2,875 bits por píxel. Si se realiza este paso, los valores de color truncados de 15 bits se pueden usar en el siguiente paso para crear un histograma más pequeño . Además, dado que cada vector de color binario de 15 bits se almacena presumiblemente en una palabra de 16 bits, el bit 16 se puede usar para mejorar la calidad de la imagen especificando cuál de las dos tablas de búsqueda se debe usar. ^{[ 1 ] [ 2 ] [ 3 ]}
7. Se crea un histograma de todos los colores de 24 bits en la imagen original de 24 bits, o en los vectores de color truncados de 15 bits. En una implementación simple, se consulta el histograma para elegir 256 de los colores más utilizados, que luego se colocan en una matriz de 256 entradas, donde cada entrada consta de tres octetos de un valor de color de 24 bits por píxel. El método del histograma para seleccionar los colores más apropiados para la imagen original de 24 bits por píxel puede reemplazarse por un algoritmo de cuantización vectorial, como el algoritmo de corte de mediana o el agrupamiento K-means, que generalmente produce mejores resultados. ^{[ 1 ] [ 2 ] [ 3 ]}
8. El paso final consiste en tomar el bloque actual de píxeles y determinar qué color de 24 bits por píxel en la tabla de búsqueda de 256 entradas coincide más estrechamente con los dos colores representativos para cada bloque. Los dos índices de 8 bits que apuntan a los colores en la tabla de búsqueda se agregan ahora al mapa de bits de luminancia de 16 bits. Esto produce un tamaño total comprimido de${\textstyle 16+8+8=32}$bits, que, al dividirse por 16, dan como resultado 2 bits por píxel. ^{[ 1 ] [ 2 ] [ 3 ]}

La descompresión es muy sencilla y directa. Para reconstruir cada bloque comprimido de 4 píxeles x 4 píxeles, se consulta el mapa de bits de luminancia de 16 bits para cada bloque. Dependiendo de si un elemento del mapa de bits es 1 o 0, se selecciona uno de los dos índices de 8 bits en la tabla de búsqueda, se desreferencia y se recupera el valor de color correspondiente de 24 bits por píxel. ^{[ 1 ] [ 2 ] [ 3 ]}