Color Cell Compression 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 un precursor de los algoritmos modernos de compresión de texturas, como S3 Texture Compression y Adaptive Scalable Texture. La compresión . Está estrechamente relacionado con la codificación de truncamiento de bloques , [4] otro algoritmo de compresión de imágenes con pérdida, que es 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 por 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 última 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 usa la desviación estándar. Sin embargo, ambos algoritmos pueden comprimir una imagen hasta 2 bits por píxel.
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. Se asume aquí que la entrada es una imagen de 24 bits / píxel, como se asume en el artículo original de la revista, aunque se podrían usar otras profundidades de bits .
- Para cada triple de octeto RGB de 8 bits contenido en cada valor de color de 24 bits en la imagen de entrada, la luminancia NTSCse calcula utilizando la siguiente fórmula: [1] [2] [3]
- La imagen se subdivide ahora en bloques de 4 píxeles por 4 píxeles, y la media aritmética de la luminancia de cada píxel del bloque se utiliza para seleccionar un valor de luminancia representativo. [1] [2] [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 que 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 del bloque actual pertenece a un grupo determinado se determina mediante un valor binario "0" o "1" en otro mapa de bits de 16 entradas independiente . [1] [2] [3]
- Ahora se seleccionan dos colores representativos de 24 bits para cada bloque de píxeles calculando dos medios aritméticos. 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]
- El mapa de bits de luminancia se almacena en una ubicación temporal y luego los dos colores representativos de 24 bits para el bloque actual se añaden al mapa de bits. En esta etapa, la imagen se ha comprimido en un mapa de bits de 16 entradas con dos valores binarios de 24 bits adjuntos. El tamaño total del bloque comprimido ahora es de 16 bits para el mapa de bits de luminancia y dos cantidades binarias de 24 bits para cada color representativo, lo que arroja 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]
- Cada bloque de píxeles comprimido 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 debits, que, cuando se dividen entre 16, producen 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]
- Se crea un histograma de todos los colores de 24 bits de la imagen de color de 24 bits original o de los vectores de color truncados de 15 bits. En una implementación ingenua, 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 de histograma para seleccionar los colores más apropiados para la imagen de color original de 24 bits por píxel puede ser reemplazado por un algoritmo de clase de cuantificación vectorial como el algoritmo de corte mediano o agrupación de K-medias [ cita requerida ] que generalmente produce mejores resultados. [1] [2] [3]
- El paso final consiste en tomar el bloque de píxeles actual y determinar qué color de 24 bits por píxel en la tabla de búsqueda de 256 entradas se asemeja más a los dos colores representativos de cada bloque. Los dos índices de 8 bits que apuntan a los colores de la tabla de búsqueda se añaden ahora al mapa de bits de luminancia de 16 bits. Esto produce un tamaño comprimido total debits, que, cuando se dividen entre 16, producen 2 bits por píxel. [1] [2] [3]
- Para cada triple de octeto RGB de 8 bits contenido en cada valor de color de 24 bits en la imagen de entrada, la luminancia NTSCse calcula utilizando la siguiente fórmula: [1] [2] [3]
Descompresión
La descompresión es muy fácil y sencilla. Para reconstruir cada bloque comprimido de 4 píxeles por 4 píxeles, se consulta el mapa de bits de luminancia de 16 bits de 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 desreferencia y se recupera el valor de color correspondiente de 24 bits por píxel. [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 superado con creces en relación de compresión por los métodos de codificación de transformación de bloques posteriores como JPEG , tiene la ventaja de una descompresión muy simple y un acceso aleatorio rápido a la imagen comprimida.
Ver también
- Color indexado
- Compresión de textura adaptable y escalable
- Compresión de textura S3
Referencias
- ^ a b c d e f g h i j k 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.
- ^ a b c d e f g h yo j k Alfileres, Markus (1991). Extensiones del algoritmo de compresión de celdas de color . Animación por computadora '91 . págs. 241-251. doi : 10.1007 / 978-4-431-66890-9_17 . ISBN 978-4-431-66892-3.
- ^ a b c d e f g h yo j k Lamparter, Bernd Effelsberg, Wolfgang (junio de 2005). Compresión de celdas de color ampliada: un esquema de compresión eficiente en tiempo de ejecución para video de software . Multimedia: Teleservicios avanzados y arquitecturas de comunicación de alta velocidad . Apuntes de conferencias en informática. 868 . págs. 181-190. doi : 10.1007 / 3-540-58494-3_16 . ISBN 978-3-540-58494-0.CS1 maint: varios nombres: lista de autores ( enlace )[ enlace muerto permanente ]
- ^ 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 .