En una imagen digital puede haber tres tipos de redundancia:
Redundancia en el código. Código de Huffman
Redundancia entre píxeles.
LZW
RLE
Representación por bloques.
Representación en árbol cuaternario.
Representación por borde de la imagen.
Redundancia psicovisual.
Codificación sin pérdida en imágenes en escala de grises
Codificación sin pérdida en imágenes binarias
Conjuntos derivados
Planos de bits
Transformada de FourierTransformada de Hadamard
Transformada de Walsh-HadamardTransformada discreta coseno
Codificación con pérdida en imágenes en escala de grises
Codificación sin pérdida en imágenes en escala de grises
Codificación sin pérdida en imágenes en escala de grises
Representaciones de los conjuntos derivados
Se entiende por conjuntos derivados de unas imágenes como aquellas que se obtienen a partir de unas dadas.
Ejemplo: La unión, intersección, complemenario.
Objetivo: A partir de imágenes representadas del mismo modo (filas, bloques, bordes) obtener las representaciones de los conjuntos derivados.
Aquí, por simplicidad, sólo trataremos imágenes binarias S y T.
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Nota: En el libro de Rosenfeld y Kak (Digital Picture Processing), hay una sección dedicada a algoritmos de conversión entre representaciones (Capítulo 11).
Representaciones de los conjuntos derivados
Operaciones lógicas en imágenes binarias:
Inverso de una imagen: a cada píxel p aplicar la operación NOT(p) donde NOT(0)=1 y NOT(1)=0.
Intersección de dos imágenes A y B: p(A) AND p(B) donde el píxel de la intersección es negro si y sólo en ambas imágenes era negro.
Unión: p(A) OR p(B) donde el píxel de la unión es negro si y sólo en alguna de las imágenes era negro.
Resta, B – A: NOT(A) AND B donde un píxel es negro si era negro en B pero no lo era en A.
Unión menos la intersección (excluyente): A XOR B donde un píxel es negro si lo era en A ó en B pero no en ambos.
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Representaciones de los conjuntos derivados
Dada la representación de la longitud de la secuencia de S (y de T).
La longitud de secuencia del inverso de S se obtiene simplemente invirtiendo la designación del primer valor de cada fila.
Algoritmo para obtener L (lista de secuencia) la intersección de S y T a partir de sus respectivas listas L1 y L2 .
Si tanto L1 como L2 comienzan con secuencias de 1’s, también lo hace L; en otro caso, L comienza con 0.
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Representaciones de los conjuntos derivados
Algoritmo para obtener L=c: c1 c2 c3 … , la lista de secuencia de la intersección de S y T a partir de sus respectivas listas:
S1=a: a1, a2 a3 … y T1=b: b1 b2 b3 …, siendo a,b=0,1
Si tanto a como b valen 1, entonces c vale 1 y c1 es el mínimo entre a1 y b1.
Si tanto a como b valen 0, entonces c vale 0 y c1 es el máximo entre a1 y b1.
Si a vale 0 y b vale 1, entonces c vale 0 y c1 es a1 (análogamente, si a vale 1 y b vale 0).
A continuación, rescribimos las nuevas secuencias S1 y T1 que surgen al eliminar los primero c1 píxeles y volvemos a empezar para calcular c2 .
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Representaciones de los conjuntos derivados
Ejercicios:
Describir un algoritmo para
obtener la unión de dos
imágenes usando la
representación MAT.
b) Idem para describir el árbol cuaternario de la inversa de una imagen.
c) Idem para describir los códigos de fisura de la inversa de una imagen
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Un método sencillo para la descomposición de una imagen en escala de grises de L bits en un conjunto de imágenes binarias consiste en separar los L dígitos de cada píxel y formar L imágenes de 1 bit cada píxel (planos de bits).
Es decir, si el nivel de gris asociado a un píxel es
se toma cada uno de los coeficientes ak para formar el k-ésimo plano de bits, k=0,…,L-1.
Después, cada una de las imágenes binarias puede ser representada en alguna de las formas descritas anteriormente.
Codificación en planos de bits de una imagen en escala de grises
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Inconveniente: pequeñas variaciones en los niveles de gris tienen un impacto significativo en la complejidad de los planos de bits.
Por ejemplo, si en la imagen inicial hay un píxel de intensidad 127 (0111111) junto a otro de 128 (1000000), en todos los mapas de bits correspondientes habrá un salto de 0 a 1 (ó de 1 a 0).
Código de Gray
Codificación en planos de bits de una imagen en escala de grises
Un método de descomposición alternativo (que reduce el efecto de pequeñas variaciones de niveles de gris) consiste en representar primero la imagen mediante un código de Gray de L bits.
Si los dígitos en binario del número son
aL-1aL-2…a1a0
El mismo número en código de Gray es
gL-1gL-2…g1g0
donde gi=ai+ai+1 mod 2 si i< L-1 y y gL-1=aL-1
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Codificación en planos de bits de una imagen en escala de grises
Los cuatro planos de bits más significativos de esta imagen, correspondientes a los coeficientes a7, a6, a5, a4. La segunda fila de imágenes corresponde a los planos de bits usando el código de Gray.
ELIMINANDO REDUNDANCIA ENTRE PIXELES
Compresión de imágenes digitales
Eliminando:
Redundancia en el código.
Redundancia entre píxeles.
Redundancia psicovisual.
ALMACENAMIENTO DE IMÁGENES DIGITALES
ELIMINANDO REDUNDANCIA PSICOVISUAL
Compresión de imágenes eliminando la redundancia psicovisual
Al contrario de lo que sucedía con los métodos anteriores, la codificación con pérdida se basa en la idea de comprometer la precisión de la imagen descomprimida con el fin de lograr una mayor compresión.
Se hace necesario indicadores que nos permitan medir el error que se comete después de comprimir y descomprimir con respecto a la imagen original. Por ejemplo, el error cuadrático medio en una imagen MxN, viene dado por:
Las técnicas de compresión con pérdida que estudiaremos son las técnicas de
codificación por transformación en bloques (Block Transform Coding).
ELIMINANDO REDUNDANCIA PSICOVISUAL
(Gp:) f(x,y) la imagen original y (x,y) la imagen obtenida después de comprimir y descomprimir
Codificación por transformación en bloques
La imagen se divide en bloques nxn y en cada uno de ellos se realiza una codificación por transformación.
En la codificación por transformación, se utiliza una transformada lineal, reversible, para hacer corresponder la imagen con un conjunto de coeficientes de la transformada, que después se cuantifican y se codifican.
En la mayor parte de las imágenes naturales, un número significativo de coeficientes (en el dominio transformado) tiene pequeñas magnitudes y se pueden cuantificar de forma poco precisa (o se pueden eliminar totalmente) sin que ello suponga una distorsión apreciable en la imagen.
ELIMINANDO REDUNDANCIA PSICOVISUAL
Página siguiente  |