Block Truncation Coding ( BTC ) es un tipo de técnica de compresión de imágenes con pérdida para imágenes en escala de grises . Divide las imágenes originales en bloques y luego usa un cuantificador para reducir el número de niveles de gris en cada bloque mientras mantiene la misma desviación estándar y media . Es uno de los primeros predecesores de la popular técnica DXTC de hardware , aunque el método de compresión BTC se adaptó por primera vez al color mucho antes que DXTC utilizando un enfoque muy similar llamado Compresión de celda de color . [1] BTC también se ha adaptado a la compresión de video. [2]
BTC fue propuesto por primera vez por los profesores Mitchell y Delp en Purdue University. [3] Otra variación de BTC es la codificación de truncamiento de bloque de momento absoluto o AMBTC , en la que en lugar de utilizar la desviación estándar, el primer momento absoluto se conserva junto con la media. AMBTC es computacionalmente más simple que BTC y también suele dar como resultado un error cuadrático medio (MSE) más bajo. AMBTC fue propuesto por Máximo Lema y Robert Mitchell. [4]
El uso de subbloques de 4 × 4 píxeles da una relación de compresión de 4: 1, suponiendo que se utilicen valores enteros de 8 bits durante la transmisión o el almacenamiento. Los bloques más grandes permiten una mayor compresión (los valores "a" y "b" se distribuyen en más píxeles), sin embargo, la calidad también se reduce con el aumento del tamaño del bloque debido a la naturaleza del algoritmo.
El algoritmo BTC se utilizó para comprimir las imágenes del rover Mars Pathfinder . [5]
Procedimiento de compresión
Una imagen de píxeles se divide en bloques de normalmente 4 × 4 píxeles. Para cada bloque se calcula la desviación media y estándar de los valores de los píxeles; estas estadísticas generalmente cambian de un bloque a otro. Los valores de píxel seleccionados para cada bloque reconstruido o nuevo se eligen de modo que cada bloque de la imagen comprimida BTC tenga (aproximadamente) la misma desviación media y estándar que el bloque correspondiente de la imagen original. Una cuantificación de dos niveles en el bloque es donde obtenemos la compresión y se realiza de la siguiente manera:
Aquí son elementos de píxeles del bloque original y son elementos del bloque comprimido. En palabras, esto se puede explicar como: Si un valor de píxel es mayor que la media, se le asigna el valor "1", en caso contrario, "0". Los valores iguales a la media pueden tener un "1" o un "0" dependiendo de la preferencia de la persona u organización que implementa el algoritmo.
Este bloque de 16 bits se almacena o transmite junto con los valores de desviación estándar y media. La reconstrucción se realiza con dos valores "a" y "b" que conservan la media y la desviación estándar. Los valores de "a" y "b" se pueden calcular de la siguiente manera:
Dónde es la desviación estándar, m es el número total de píxeles en el bloque yq es el número de píxeles mayor que la media ()
Para reconstruir la imagen, o crear su aproximación, los elementos asignados a 0 se reemplazan con el valor "a" y los elementos asignados a 1 se reemplazan con el valor "b".
Esto demuestra que el algoritmo es asimétrico en el sentido de que el codificador tiene mucho más trabajo que hacer que el decodificador. Esto se debe a que el decodificador simplemente reemplaza unos y ceros con el valor estimado, mientras que el codificador también debe calcular la media, la desviación estándar y los dos valores a utilizar. [6]
Ejemplo
Codificador
Tome un bloque de 4 × 4 de una imagen, en este caso la imagen de prueba de la montaña: [7]
Como cualquier pequeño bloque de una imagen, parece bastante aburrido trabajar con él, ya que los números son bastante similares, esta es la naturaleza de la compresión con pérdida y cómo puede funcionar tan bien para las imágenes. Ahora necesitamos calcular dos valores a partir de estos datos, es decir, la desviación estándar y la media. La media se puede calcular en 241,875, este es un cálculo simple que no debería requerir más explicación. La desviación estándar se calcula fácilmente en 4,36. A partir de esto, los valores de "a" y "b" se pueden calcular utilizando las ecuaciones anteriores. Resultan ser 236.935 y 245.718 respectivamente. El último cálculo que debe hacerse en el lado de la codificación es configurar la matriz para transmitir a unos y ceros para que cada píxel se pueda transmitir como un solo bit.
Descifrador
Ahora, en el lado del decodificador, todo lo que tenemos que hacer es reasignar los valores "a" y "b" a 1 y 0 píxeles. Esto nos dará el siguiente bloque:
Como puede verse, el bloque se ha reconstruido con los dos valores de "a" y "b" como enteros (porque las imágenes no están definidas para almacenar números de coma flotante). Al trabajar en la teoría, este es un buen punto para calcular la desviación estándar y media del bloque reconstruido. Deben ser iguales a la media y la desviación estándar originales. Recuerde usar números enteros, de lo contrario se involucrará mucho error de cuantificación, ya que previamente cuantificamos todo a números enteros en el codificador.
Ver también
- Compresión de celdas de color (un derivado más reciente de la codificación de truncamiento de bloques)
Referencias
- ^ Liou, D. -M .; Huang, Y .; Reynolds, N. (1990). "Un nuevo sistema de imagen basado en microordenador con técnica C / sup 3 /". IEEE TENCON'90: 1990 IEEE Region 10 Conference on Computer and Communication Systems. Actas de la conferencia . pag. 555. doi : 10.1109 / TENCON.1990.152671 . ISBN 0-87942-556-3.
- ^ Healy, D .; Mitchell, O. (1981). "Compresión de ancho de banda de vídeo digital mediante codificación de truncamiento de bloques". Transacciones IEEE sobre comunicaciones . 29 (12): 1809. Código Bibliográfico : 1981ITCom..29.1809H . doi : 10.1109 / TCOM.1981.1094938 .
- ^ Delp, E .; Mitchell, O. (1979). "Compresión de imágenes mediante codificación de truncamiento de bloques". Transacciones IEEE sobre comunicaciones . 27 (9): 1335. Bibcode : 1979STIA ... 8011525D . doi : 10.1109 / TCOM.1979.1094560 .
- ^ Lema, M .; Mitchell, O. (1984). "Codificación de truncamiento de bloque de momento absoluto y su aplicación a imágenes en color". Transacciones IEEE sobre comunicaciones . 32 (10): 1148. doi : 10.1109 / TCOM.1984.1095973 .
- ^ "Descripción del instrumento de la cámara Rover" . NASA . Consultado el 18 de mayo de 2021 .
- ^ Leis, J 2008, ELE4607 Comunicaciones digitales avanzadas, Módulo 3: Codificación de imágenes y videos. Diapositivas de conferencias, Universidad del Sur de Queensland, 2008.
- ^ Grupo de análisis y codificación fractal de Waterloo
enlaces externos
- Medios relacionados con la codificación de truncamiento de bloques en Wikimedia Commons