Compresión de celdas de color

Algoritmo de compresión de imágenes en color con pérdida

La compresión de celdas de color es un algoritmo de compresión de imágenes con pérdida desarrollado por Campbell et al., ^{[1] [2] [3]} en 1986, que puede considerarse uno de los primeros precursores de los algoritmos de compresión de texturas modernos, como la compresión de texturas S3 y la textura escalable adaptativa. Compresión . Está estrechamente relacionado con Block Truncation Coding , ^[4] otro algoritmo de compresión de imágenes con pérdida, anterior a la compresión de celdas de color, ya que utiliza la luminancia dominante de un bloque de píxeles para dividir dichos píxeles en dos colores representativos. La principal diferencia entre la codificación de truncamiento de bloques y la compresión de celdas de color es que la primera fue diseñada para comprimir imágenes en escala de grises y la segunda para comprimir imágenes en color. Además, la codificación de truncamiento de bloques requiere que se calcule la desviación estándar de los colores de los píxeles en un bloque para comprimir una imagen, mientras que la compresión de celdas de color no utiliza la desviación estándar. Sin embargo, ambos algoritmos pueden comprimir una imagen hasta 2 bits por píxel.

Imagen original en color sin comprimir de 24 bits por píxel

Imagen comprimida CCC, pero utilizando solo cuantificación de color de 24 bits a 15 bits combinada con un mapa de bits de luminancia de 2,875 bits por píxel (sin paleta/tabla de búsqueda)

Implementación de paleta de 256 entradas/tabla de búsqueda del algoritmo CCC a 2 bits por píxel con la paleta construida utilizando agrupación de K-medias

Resultado de la salida de la imagen de prueba estándar de Mandrill comprimida con el algoritmo CCC a 2 bits por píxel con una paleta de 256 entradas/tabla de búsqueda generada utilizando un sencillo algoritmo de histograma de color de 15 bits.

Algoritmo

Compresión

El algoritmo de compresión de celdas de color procesa una imagen en ocho pasos, aunque uno de los pasos (paso 6) es opcional. Aquí se supone que la entrada es una imagen de 24 bits/píxel, como se supone en el artículo de revista original, aunque se podrían usar 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 se calcula utilizando la siguiente fórmula: ^{[1] [2] [3]} ${\textstyle y}$ $${\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 la media aritmética de la luminancia de cada píxel en el bloque se utiliza para seleccionar un valor de luminancia representativo. ^{[1] [2] [3]}
3. Luego, cada bloque de píxeles se divide en dos grupos. Un grupo consta de píxeles en el bloque actual donde la luminancia de cada píxel es mayor o igual a la luminancia representativa del bloque actual. El segundo grupo de píxeles consta de píxeles en el bloque actual donde la luminancia de cada píxel es menor que la luminancia representativa del bloque actual. Si un píxel en el bloque actual pertenece a un determinado grupo se determina mediante un valor binario "0" o "1" en otro mapa de bits separado 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 añaden 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 añadidos. 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 produce un tamaño total de 64 bits que, cuando se divide por 16 (el número de píxeles en el bloque ), produce 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 bits que, cuando se divide por 16, produce 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 utilizar para mejorar la calidad de la imagen especificando cuál de las dos tablas de búsqueda se debe utilizar. ^{[1] [2] [3]} ${\textstyle 16+2\times 15=46}$
7. Se crea un histograma de todos los colores de 24 bits de la imagen en color de 24 bits original, o de los vectores de color de 15 bits truncados. En una implementación sencilla, 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. En cambio, el método de histograma para seleccionar los colores más apropiados para la imagen en color original de 24 bits por píxel se puede reemplazar por un algoritmo de clase de cuantificación vectorial, como el algoritmo de corte de mediana o la agrupación de K-medias ^{[ cita necesaria ]} 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 con los dos colores representativos de cada bloque. Los dos índices de 8 bits que apuntan a los colores en la tabla de búsqueda ahora se agregan al mapa de bits de luminancia de 16 bits. Esto produce un tamaño total comprimido de bits que, cuando se divide por 16, produce 2 bits por píxel. ^{[1] [2] [3]} ${\textstyle 16+8+8=32}$

Descompresión

La descompresión es muy fácil y directa. Para reconstruir cada bloque comprimido de 4 píxeles por 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 y luego se elimina la referencia y se recupera el valor de color de 24 bits por píxel correspondiente. ^{[1] [2] [3]}

Rendimiento y calidad de imagen

A pesar de su mecanismo muy simple, el algoritmo produce resultados sorprendentemente buenos en imágenes fotográficas, ^{[1] [2] [3]} y tiene la ventaja de ser muy rápido de decodificar con hardware limitado. Aunque es superado con creces en relación de compresión por métodos posteriores de codificación por transformación de bloques como JPEG , tiene la ventaja de una descompresión muy simple y un acceso aleatorio rápido a la imagen comprimida.

Apple Video (RPZA) y S3 Texture Compression emplean el mismo principio de codificación de bloques de 4×4 píxeles basados ​​en dos colores representativos. Refinan CCC expandiendo cada entrada en el mapa de bits de luminancia a dos bits, donde los dos valores adicionales representan un promedio ponderado: un tercio de un color y dos tercios del otro. Para solucionar la patente de S3, se creó la biblioteca Super Simple Texture Compression ( S2TC ) para codificar datos CCC en un formato compatible con los decodificadores S3TC y reinterpretar S3TC como CCC con una pérdida de calidad menor.

Ver también

• Color indexado
• Compresión de textura escalable adaptativa
• Compresión de textura S3

Referencias

1. Campbell, G.; Defanti, TA; Frederiksen, J.; Joyce, SA; Leske, LA (1986). "Codificación a todo color de dos bits/píxeles". Actas de la decimotercera conferencia anual sobre gráficos por computadora y técnicas interactivas: SIGGRAPH '86 . pag. 215. doi : 10.1145/15922.15910. ISBN 978-0-89791-196-2. S2CID  18392630.
2. Pines abcdefghijk, Markus (1991). "Extensiones del algoritmo de compresión de celdas de color". Animación por ordenador '91 . págs. 241-251. doi :10.1007/978-4-431-66890-9_17. ISBN 978-4-431-66892-3.
3. Lamparter, Bernd Effelsberg, Wolfgang (junio de 2005). "Compresión extendida de celdas de color: un esquema de compresión eficiente en tiempo de ejecución para vídeo de software". Multimedia: Teleservicios Avanzados y Arquitecturas de Comunicación de Alta Velocidad. Apuntes de conferencias sobre informática. vol. 868, págs. 181-190. doi :10.1007/3-540-58494-3_16. ISBN 978-3-540-58494-0.{{cite book}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )^{[ enlace muerto permanente ]}
4. Wennersten, P.; Ström, J. (2009). "Compresión alfa basada en tablas" (PDF) . Foro de gráficos por computadora . 28 (2): 687. doi :10.1111/j.1467-8659.2009.01409.x. S2CID  7743813.