Codificación de truncamiento de bloques

La codificación por 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 la cantidad de niveles de gris en cada bloque, manteniendo la misma media y desviación estándar . Es un precursor temprano de la popular técnica de hardware DXTC , aunque el método de compresión BTC se adaptó 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 video. ^{[ 2 ]}

BTC fue propuesto inicialmente por los profesores Mitchell y Delp en la Universidad de Purdue. ^{[ 3 ]} Otra variante 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, se conserva el primer momento absoluto junto con la media. AMBTC es computacionalmente más simple que BTC y también suele resultar en un menor error cuadrático medio (MSE). AMBTC fue propuesto por Maximo 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 (los valores "a" y "b" se distribuyen en más píxeles); sin embargo, la calidad también disminuye 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 de Mars Pathfinder . ^{[ 5 ]}

Procedimiento de compresión

Una imagen de píxeles se divide en bloques, generalmente de 4×4 píxeles. Para cada bloque, se calculan la media y la desviación estándar de los valores de los píxeles; estas estadísticas suelen variar de un bloque a otro. Los valores de los píxeles seleccionados para cada bloque reconstruido, o nuevo, se eligen de manera que cada bloque de la imagen comprimida con BTC tenga (aproximadamente) la misma media y desviación estándar que el bloque correspondiente de la imagen original. La compresión se logra mediante una cuantización de dos niveles en el bloque, que se realiza de la siguiente manera:

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

Aquí $x(i,j)$ son elementos de píxeles del bloque original y $y(i,j)$ son elementos del bloque comprimido. En otras palabras, esto se puede explicar así: si el valor de un píxel es mayor que la media, se le asigna el valor "1"; de lo 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.

Este bloque de 16 bits se almacena o transmite junto con los valores de la media y la desviación estándar. 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:

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

$b={\bar {x}}+\sigma {\sqrt {\cfrac {mq}{q}}}$

Dónde $\sigma$ 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 mayores que la media ( ${\bar {x}}$ )

Para reconstruir la imagen o crear una aproximación, los elementos con valor 0 se reemplazan por el valor "a" y los elementos con valor 1 se reemplazan por el valor "b".

$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, ya 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 utilizar. ^{[ 6 ]}

Ejemplo

Codificador

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

${\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, trabajar con esto puede parecer bastante aburrido, ya que los números son todos bastante similares; esta es la naturaleza de la compresión con pérdida y por qué puede funcionar tan bien para las imágenes. Ahora necesitamos calcular dos valores a partir de estos datos: la media y la desviación estándar. La media se puede calcular como 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 como 4,36. A partir de esto, los valores de "a" y "b" se pueden calcular usando las ecuaciones anteriores. Resultan ser 236,935 y 245,718 respectivamente. El último cálculo que se debe hacer en el lado de la codificación es configurar la matriz para transmitir a 1 y 0 para que cada píxel pueda transmitirse como un solo bit.

${\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 necesitamos hacer es reasignar los valores "a" y "b" a los píxeles 1 y 0. Esto nos dará el siguiente bloque:

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

Como se puede observar, el bloque se ha reconstruido con los valores "a" y "b" como números enteros (ya que las imágenes no están definidas para almacenar números de coma flotante). Al analizar la teoría, este es un buen momento para calcular la media y la desviación estándar del bloque reconstruido. Estas deben ser iguales a la media y la desviación estándar originales. Recuerde usar números enteros; de lo contrario, se producirá un error de cuantificación considerable, dado que previamente cuantificamos todo a números enteros en el codificador.

Véase también

Compresión de celdas de color (una variante más reciente de la codificación por truncamiento de bloques)

Referencias

↑ 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 de la Región 10 del IEEE de 1990 sobre Sistemas Informáticos y de Comunicación. Actas de la conferencia . pág. 555. doi : 10.1109/TENCON.1990.152671 . ISBN 0-87942-556-3. S2CID 62015990 .
↑ Healy, D.; Mitchell, O. (1981). "Compresión de ancho de banda de vídeo digital mediante codificación de truncamiento de bloques". IEEE Transactions on Communications . 29 (12): 1809. Bibcode : 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". IEEE Transactions on Communications . 27 (9): 1335. Bibcode : 1979STIA...8011525D . doi : 10.1109/TCOM.1979.1094560 .
↑ Lema, M.; Mitchell, O. (1984). "Codificación de truncamiento de bloques de momento absoluto y su aplicación a imágenes en color". IEEE Transactions on Communications . 32 (10): 1148. doi : 10.1109/TCOM.1984.1095973 .
↑ "Descripción del instrumento de la cámara del rover" . NASA . Consultado el 18 de mayo de 2021 .
↑ Leis, J 2008, ELE4607 Comunicaciones Digitales Avanzadas, Módulo 3: Codificación de Imagen y Vídeo. Diapositivas de la clase, Universidad del Sur de Queensland, 2008.
↑ Grupo de Codificación y Análisis Fractal de Waterloo

Enlaces externos

Contenido multimedia relacionado con la codificación de truncamiento de bloques en Wikimedia Commons.

[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 de la Región 10 del IEEE de 1990 sobre Sistemas Informáticos y de Comunicación. Actas de la conferencia . pág. 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". IEEE Transactions on Communications . 29 (12): 1809. Bibcode : 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". IEEE Transactions on Communications . 27 (9): 1335. Bibcode : 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". IEEE Transactions on Communications . 32 (10): 1148. doi : 10.1109/TCOM.1984.1095973 .

[5] "Descripción del instrumento de la cámara del rover" . NASA . Consultado el 18 de mayo de 2021 .

[6] Leis, J 2008, ELE4607 Comunicaciones Digitales Avanzadas, Módulo 3: Codificación de Imagen y Vídeo. Diapositivas de la clase, Universidad del Sur de Queensland, 2008.

[7] Grupo de Codificación y Análisis Fractal de Waterloo

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]