Codificación de truncamiento de bloques

La codificación de truncamiento de bloques ( 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 utiliza un cuantificador para reducir el número de niveles de gris en cada bloque manteniendo la misma desviación media y estándar . Es un predecesor temprano 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 celdas de color . ^[1] BTC también se ha adaptado a la compresión de vídeo. ^[2]

BTC fue propuesto por primera vez por los profesores Mitchell y Delp de la Universidad Purdue. ^[3] Otra variación de BTC es la codificación de truncamiento de bloques 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 generalmente también da 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 proporciona 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 (valores "a" y "b" repartidos 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 media y la desviación estándar de los valores de píxeles; Estas estadísticas generalmente cambian de un bloque a otro. Los valores de píxeles seleccionados para cada bloque reconstruido o nuevo se eligen de modo que cada bloque de la imagen comprimida BTC tenga (aproximadamente) la misma media y desviación estándar que el bloque correspondiente de la imagen original. Una cuantización de dos niveles en el bloque es donde obtenemos la compresión y se realiza de la siguiente manera:

${\displaystyle y(i,j)={\begin{cases}1,&x(i,j)>{\bar {x}}\\0,&x(i,j)\leq {\bar {x}}\end{cases}}}$

Aquí hay elementos de píxeles del bloque original y son elementos del bloque comprimido. En palabras, esto se puede explicar de la siguiente manera: si el valor de un 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" según la preferencia de la persona u organización que implementa el algoritmo. ${\displaystyle x(i,j)}$ ${\displaystyle y(i,j)}$

Este bloque de 16 bits se almacena o transmite junto con los valores de media y desviación estándar. La reconstrucción se realiza con dos valores "a" y "b" que preservan la media y la desviación estándar. Los valores de "a" y "b" se pueden calcular de la siguiente manera:

${\displaystyle a={\bar {x}}-\sigma {\sqrt {\cfrac {q}{m-q}}}}$

${\displaystyle b={\bar {x}}+\sigma {\sqrt {\cfrac {m-q}{q}}}}$

Donde es la desviación estándar, m es el número total de píxeles en el bloque y q es el número de píxeles mayor que la media ( ) ${\displaystyle \sigma }$ ${\displaystyle {\bar {x}}}$

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".

${\displaystyle x(i,j)={\begin{cases}a,&y(i,j)=0\\b,&y(i,j)=1\end{cases}}}$

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 los 1 y 0 con el valor estimado, mientras que el codificador también debe calcular la media, la desviación estándar y los dos valores a usar. ^[6]

Ejemplo

Codificador

Tome un bloque de 4×4 de una imagen, en este caso la imagen de prueba de la montaña: ^[7]

${\displaystyle {\begin{matrix}245&239&249&239\\245&245&239&235\\245&245&245&245\\245&235&235&239\end{matrix}}}$

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 con las imágenes. Ahora necesitamos calcular dos valores a partir de estos datos, es decir, la media y la desviación estándar. La media se puede calcular en 241,875; este es un cálculo simple que no debería requerir más explicaciones. La desviación estándar se calcula fácilmente en 4,36. A partir de esto se pueden calcular los valores de "a" y "b" utilizando las ecuaciones anteriores. Resultan 236.935 y 245.718 respectivamente. El último cálculo que debe realizarse en el lado de la codificación es configurar la matriz para transmitir en 1 y 0 para que cada píxel pueda transmitirse como un solo bit.

${\displaystyle {\begin{matrix}1&0&1&0\\1&1&0&0\\1&1&1&1\\1&0&0&0\end{matrix}}}$

Descifrador

Ahora, en el lado del decodificador, todo lo que tenemos que hacer es reasignar los valores "a" y "b" a los píxeles 1 y 0. Esto nos dará el siguiente bloque:

${\displaystyle {\begin{matrix}245&236&245&236\\245&245&236&236\\245&245&245&245\\245&236&236&236\end{matrix}}}$

Como puede verse, el bloque ha sido reconstruido con los dos valores de "a" y "b" como números enteros (porque las imágenes no están definidas para almacenar números de punto flotante). Cuando se trabaja en la teoría, este es un buen punto para calcular la media y la desviación estándar del bloque reconstruido. Deben ser iguales a la media y la desviación estándar originales. Recuerde usar números enteros; de lo contrario, habrá muchos errores 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

1. Liou, D.-M.; Huang, Y.; Reynolds, N. (1990). "Un nuevo sistema de imágenes basado en microcomputadora con técnica C / sup 3 /". IEEE TENCON'90: Conferencia IEEE Región 10 de 1990 sobre sistemas informáticos y de comunicación. Actas de congresos . pag. 555. doi :10.1109/TENCON.1990.152671. ISBN 0-87942-556-3. S2CID  62015990.
2. 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.
3. Delp, E.; Mitchell, O. (1979). "Compresión de imágenes mediante codificación de truncamiento de bloques". Transacciones IEEE sobre Comunicaciones . 27 (9): 1335. Código bibliográfico : 1979STIA...8011525D. doi :10.1109/TCOM.1979.1094560.
4. Lema, M.; Mitchell, O. (1984). "Codificación de truncamiento de bloques 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.
5. "Descripción del instrumento de la cámara móvil". NASA . Consultado el 18 de mayo de 2021 .
6. 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.
7. 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