Algoritmo de compresión de vídeo WAVELET.

Cualquier imagen ingresada en una computadora se digitaliza y se almacena en él en forma de un llamado mapa de bits o, en otras palabras, una matriz, cada elemento del cual describe el color de un punto en la imagen original.

El número de elementos de la matriz (puntos de imagen) depende de la resolución seleccionada durante la digitalización.

Sin embargo, almacenarlo en esta forma no es rentable debido al uso de una gran cantidad de memoria de la computadora.

Por lo tanto, en la actualidad se han desarrollado numerosos algoritmos de codificación (compresión) de mapas de bits, cuya efectividad depende de las propiedades de la imagen (obviamente, para almacenar un «cuadrado negro» no es en absoluto necesario almacenar una matriz de puntos negros , pero es suficiente almacenar tres números: ancho, alto y color).

Todos estos algoritmos se dividen en dos grupos: codificación sin pérdidas (cuando el mapa de bits original se restaura completamente como resultado del procedimiento de decodificación) y codificación sin pérdidas. En una aplicación más amplia, los algoritmos del primer grupo a menudo se denominan archivo de datos.

Consideremos con más detalle el algoritmo de compresión de imágenes con pérdida de información.

La pérdida de información en este caso significa que la imagen restaurada no coincidirá exactamente con la original, pero las diferencias serán casi invisibles para el ojo humano (en tales casos, la «calidad de compresión» generalmente se establece mediante un parámetro con posibles valores ​​de 0 a 100. donde 100 denota la compresión mínima, es decir, la mejor calidad, y la imagen restaurada es prácticamente indistinguible de la original, mientras que 0 &#8212 es la compresión máxima a la que aún se pueden conservar los detalles principales del original. distinguidas en la imagen restaurada).

Hoy en día, la mayoría de las imágenes de tonos continuos (imágenes que contienen muchos colores ligeramente diferentes) almacenadas en computadoras se codifican utilizando el algoritmo JPEG.

Las principales etapas de este algoritmo son las siguientes. La imagen se divide en patrones de 8×8 píxeles.

Para cada patrón (matriz) se realiza una transformación de coseno discreta. A continuación, de las frecuencias resultantes, utilizando una tabla de ponderación especial, se seleccionan las más significativas para la percepción visual.

Este procedimiento se llama cuantificación y es la única etapa en la que se produce la pérdida de información. .

A continuación, la matriz de frecuencias seleccionadas se representa de forma compacta y se codifica mediante el llamado método de entropía (de Huffman o aritmético).

La diferencia entre nuestro algoritmo es el uso de WAVELET en lugar de la transformada de coseno discreta, así como la aplicación de la transformación a la imagen completa, no a la plantilla de 8×8.

Entonces, ¿qué es WAVELET?

La palabra «WAVELET» denota una pequeña ola.

Por pequeño queremos decir que esta función tiene una longitud finita.

«Wave» también refleja el hecho de que la función WAVELET oscila.

WAVELET — Se trata de una familia de funciones locales en tiempo y frecuencia, y en la que todas las funciones se obtienen de una mediante sus desplazamientos y estiramientos a lo largo del eje del tiempo (de modo que “se suceden”), lo que permite analizar señal en todos los puntos.

Los matemáticos a veces llaman ráfagas WAVELET, lo que las caracteriza de cierta manera.

La primera característica de WAVELET es que tienen la propiedad de localidad simultánea en frecuencia y tiempo.

Fue esta propiedad la que los hizo tan adecuados para su uso.

Y WAVELET comenzó a disfrutar de la mayor popularidad cuando se descubrió otra propiedad de ellos — disponibilidad de un algoritmo de conversión rápida.

Desde el punto de vista de la implementación, la transformada WAVELET es un tipo de codificación de subbanda y se lleva a cabo filtrando la señal con un banco de filtros en forma de árbol.

Se puede decir sin exagerar que WAVELET revolucionó la teoría y la práctica del procesamiento de señales no estacionarias

Actualmente, WAVELET ha encontrado su aplicación en las siguientes áreas:

<. ul>

La práctica de utilizar WAVELET para resolver problemas de compresión y procesamiento de imágenes, que son de naturaleza no estacionaria, ha recibido especial atención. desarrollo.

En esta área, el uso de transformaciones WAVELET permitió lograr una reducción simultánea de la complejidad y aumentar la eficiencia de los codificadores.

Las siguientes figuras muestran la imagen original y la restaurada después de la compresión utilizando el algoritmo JPEG y el algoritmo WAVELET.

Es fácil ver que con tamaños casi idénticos de archivos codificados, la calidad de la «imagen WAVELET» significativamente mayor.

El requisito de uniformidad para la calidad de la imagen conduce a un aumento en el tamaño de 1,5 a 2 veces.

En las figuras se puede ver la selectividad concentrada característica de WAVELET durante la compresión. Presta atención al número del coche y a los contornos de las rosas.

Este fenómeno se explica por las características de las transformaciones WAVELET, mencionadas brevemente anteriormente.

Basado en el principio de incertidumbre de Heisenberg, que determina la imposibilidad de obtener una representación temporal-frecuencia arbitrariamente precisa de la señal. , solo podemos hacer un compromiso, es decir, si necesitamos valores de tiempo precisos, tenemos que sacrificar información de frecuencia, y viceversa, si necesitamos conocer valores de frecuencia, no podremos obtener valores de tiempo precisos.

A diferencia de la transformada de Fourier en ventana, que hasta cierto punto era el único medio para obtener una representación veraz en el tiempo y la frecuencia de la señal, la transformada WAVELET nos brinda la oportunidad de ajustar las «dimensiones&#187 de la señal. ventana de escaneo, lo que le permite adaptarse a la señal, resolviendo así el llamado problema de resolución.

Las transformaciones WAVELET en el plano tiempo-frecuencia se pueden representar en forma de rectángulos de diferentes anchos y alturas, teniendo la misma área.

Cada rectángulo contribuye igualmente al plano tiempo-frecuencia, pero con diferentes proporciones de frecuencia y tiempo.

En el caso de una transformada en ventana. El ancho de la ventana de Fourier se selecciona de una vez por todas para analizar la señal completa. Ésta es la principal desventaja de este tipo de transformación, de la que se elimina por completo la transformación WAVELET.

Basado en materiales de búsqueda en Internet sobre el tema Wavelet — transformación