COMPRESIÓN
AUTORREGRESIVA Y CASI SIN
PERDIDA
Autores:
Antonio Fernández Carpio
Francisco José Lamela Rincón
CONTENIDO
•
•
•
•
•
Introducción.
Conceptos y notacion básica.
Ecuaciones.
Algoritmos.
Conclusiones.
INTRODUCCIÓN
•¿Què es?
•¿Para qué sirve?
•Utilidades.
INTRODUCCIÓN
¿Qué es?
Es un pretratamiento que prepara las imágenes para
obtener mejores resultados al serles aplicados otros
métodos de compresión sin pérdida.
INTRODUCCIÓN
¿Para qué sirve?
Permite la compresión de una imagen asumiendo
que el valor de cada píxel puede ser cambiado en
función de un pequeño e. Compresión sin pérdida
corresponde a un e=0.
Pequeños valores de e pueden mejorar
sustancialmente la compresión de una imagen
sin cambios perceptibles por el ojo humano.
INTRODUCCIÓN
•Utilidades:
Un ejemplo claro es la compresión de
imágenes médicas donde mantener todos los
detalles de la imagen es muy importante.
CONCEPTOS Y NOTACIÓN BÁSICA
Se utilizará el modelo autorregresivo de
quinto orden.
u = 1L + 2 B +3 LB + 4 L2 +5 B2) u + r
Donde:
u = Imagen original.
B y L representan un pixel de abajo y a la izquierda respectivamente.
r = matriz residual.
i son los componentes del vector  que se utilizarán junto a la matriz
residual r para recobrar la imagen original.
representa el suelo o parte entera.
CONCEPTOS Y NOTACIÓN BÁSICA
La compresión autorregresiva está basada
en el hecho de que dados r y  podemos
recuperar la imagen u reconstruyendo la
intensidad de cada píxel u[i, j] a partir de
sus vecinos de abajo y a la izquierda.
ECUACIONES
•Ecuaciones NLAR.
•Minimización de la varianza
residual.
•Optimización de los parámetros
del modelo.
ECUACIONES (NLAR)
Ecuación principal:
u = 1L + 2 B +3 LB + 4 L2 +5 B2) u + r
Con esta ecuación se obtiene la matriz residual de
la imagen.
A través de ella se puede recobrar la imagen
original en el proceso de descompresión.
ECUACIONES (NLAR)
Las i son las componentes del vector 
=[1,2,3,4,5]T
Los valores óptimos para se obtienen por:
 = (vTv)-1(vTu)
Donde la matriz v viene definida por:
v = (Lu, Bu, LBu, L2u, B2u)
Cada componente de la matriz se obtiene a traves de:
LmBn u[i,j] = u[i-m, j-n]
ECUACIONES (NLAR)
255
255
0
0
0
0
0
0
255
0
255
0
255
255
0
255
255
0
0
255
0
0
0
0
0
255
0
0
0
0
255
0
255
0
0
0
255
0
0
255
0
0
255
0
0
0
0
0
0
0
0
255
0
255
0
255
255
0
255
0
0
0
255
0
Vamos a tratar esta matriz como ejemplo. Para ello,
tomaremos primero un píxel de un extremo, y luego uno
interior.
ECUACIONES (NLAR)
255
255
0
0
0
0
0
0
255
0
255
0
255
255
0
255
255
0
0
255
0
0
0
0
0
255
0
0
0
0
255
0
255
0
0
0
255
0
0
255
0
0
255
0
0
0
0
0
0
0
0
255
0
255
0
255
255
0
255
0
0
0
255
0
El píxel a tratar es el 0,0 .
Tenemos que tener en cuenta que a la matriz la rodea un
marco de ceros.
ECUACIONES (NLAR)
0
0
0
0
0
0
0
0
0
0
0
0
255 255
0
0
0
0
0
0
0
0
255
0
255
0
0
255
0
0
255
0
0
255
0
0
0
0
0
0
0
255
0
0
0
0
255
0
0
0
255
0
0
0
255
0
0
255
0
0
0
0
255
0
0
0
0
0
0
0
0
0
0
255
0
255
0
255
0
0
255
0
255
0
0
0
255
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
255 255
Para calcular cada píxel nos basamos en sus vecinos
izquierdos y de debajo.
ECUACIONES (NLAR)
Cada componente de la matriz se obtiene a traves de:
LmBn u[i,j] = u[i-m, j-n]
Para calcular el píxel [0][0] de la matriz v se haría:
V[0][0]=(matriz[0-1][0], matriz[0][0-1],matriz[0-1][0-1],matriz[0-2][0],matriz[0][0-2])
Por lo tanto, V[0][0]=(0,0,0,0,0). Es decir, un vector de 5
columnas. Esto habría que hacerlo para todos los elementos de la
matriz de entrada.
ECUACIONES (NLAR)
255
255
0
0
0
0
0
0
255
0
255
0
255
255
0
255
255
0
0
255
0
0
0
0
0
255
0
0
0
0
255
0
255
0
0
0
255
0
0
255
0
0
255
0
0
0
0
0
0
0
0
255
0
255
0
255
255
0
255
0
0
0
255
0
El píxel a tratar es el de color verde, es decir el [6][4].
Ahora no nos salimos de la matriz, y por tanto no hay que
tener en cuenta el marco de ceros.
ECUACIONES (NLAR)
255
255
0
0
0
0
0
0
255
0
255
0
255
255
0
255
255
0
0
255
0
0
0
0
0
255
0
0
0
0
255
0
255
0
0
0
255
0
0
255
0
0
255
0
0
0
0
0
0
0
0
255
0
255
0
255
255
0
255
0
0
0
255
0
Ahora, para tratar el píxel de color verde, es decir , el
píxel [6][4]. Tenemos que fijarnos en los píxeles de
debajo y de la izquierda, igual que en el ejemplo anterior.
ECUACIONES (NLAR)
Cada componente de la matriz se obtiene a traves de:
LmBn u[i,j] = u[i-m, j-n]
Para calcular el píxel [6][4] de la matriz v se haría:
V[6][4]=(matriz[6-1][4], matriz[6][4-1],matriz[6-1][4-1],matriz[6-2][4],matriz[6][4-2])
V[6][4]=(matriz[5][4], matriz[6][3],matriz[5][3],matriz[4][4],matriz[6][2])
Por lo tanto, V[6][4]=(0,0,255,0,255). Es decir, un vector de 5
columnas. Esto habría que hacerlo para todos los elementos de la
matriz de entrada.
ECUACIONES
(MINIMIZACIÓN DE LA VARIANZA RESIDUAL)
La varianza residual es:
Var[x,y](e)=(r[x,y] + e)2 + (r[x + 1,y] – e1)2
+ (r[x,y + 1] – e2)2
+ (r[x + 1,y + 1] – e3)2
+ (r[x + 2,y] – e4)2
+ (r[x,y + 2] – e5)2
La mejor opción para escoger un e tal que minimice la varianza es:
emin =(-r[x,y] + r[x + 1,y] 1 + r[x,y + 1] 2
+ r[x + 1,y + 1]3 + r[x + 2,y] 4
+ (r[x,y + 2]5)/(1 + 12 + 22 + 32 + 42 + 52)
ECUACIONES
(Optimización de los parámetros del modelo)
Este paso sólo se realiza cuando la imagen es dependiente de
del modelo autorregresivo elegido.
Una imagen es dependiente del modelo AR
cuando se pueden calcular
los coeficientes beta asociados a la imagen u.
Para esto tomamos ũ= u + du
du es la parte de la imagen orginal que se va a perder.
ECUACIONES
(Optimización de los parámetros del modelo)
Tenemos que tener en cuenta que los parámetros
beta óptimos calculados para u, no tienen por que ser
los óptimos para ũ, por lo que hay que volver a
calcularlos, de la misma manera que lo calculamos
para la u.
ALGORITMOS
• Algoritmo para minimizar la varianza residual.
• Algoritmo general NLAR.
ALGORITMOS
(Minimización de la varianza residual)
Escoger un e > 0 .
Inicializar la matriz du a ceros.
Para píxel [i,j] en la matriz u hacer:
Calcular el emin.
Encontrar el mayor k ≤ 1 tal que | du[i,j] + kemin| ≤ e
Si k > 0 hacer:
e = kemin
Du[i,j]  du[i,j] + e
r[i,j]  r[i,j] + e
r[i + 1,j]  r[i + 1,j] + e1
r[i,j + 1]  r[i,j + 1] + e2
r[i + 1,j + 1]  r[i + 1,j + 1] + e3
r[i + 2,j]  r[i +2,j] + e4
r[i,j + 2]  r[i,j + 4] + e5
ALGORITMOS
(Algoritmo general NLAR)
Escoger un error e> 0
Inicializar du como una matriz nula.
Hacer
Generar ũ = u + du
Reducir la varianza con el algoritmo anterior
píxel por píxel hasta que no se pueda reducir más
Reemplazar u por ũ = u + du
Generar ř = ũ – (ΣijLiBj) ũ
Comprimir ř con algun método convencional de compresion
sin perdida, como por ejemplo el Método Huffman.
CONCLUSIONES
• Con este método se reduce la varianza residual,
lo que hace que se reduzca la entropía de dicha
imagen.
• El incremento de ereduce la entropía, varianza
residual y el rango de intensidad de la matriz residual
r, usada para reconstruir la imagen original junto con
los coeficientes beta.
CONCLUSIONES
• Preserva el rango de intensidad original
• Mayor control de la información perdida.
• Para relativamente pequeños elos cambios
realizados en la imagen son imperceptibles.
• Puede ser usado para la restauración y la
reducción del ruido.
CONCLUSIONES
e
Entropía
NLAR
Entropía
JPEG
Entropía
Wavelet
Mejora NLAR
frente JPEG
(%)
Mejora NLAR
frente Wavelet
(%)
1
4.36
5.20
5.16
20
18
2
4.09
4.53
4.52
11
10
3
3.87
4.05
3.99
5
3
4
3.68
3.65
3.60
-1
-2
Descargar

COMPRESION AUTORREGRESIVA Y CASI SIN PERDIDA