1
Tema 8: ALMACENAMIENTO
I N G E N I E R Í A I N F O R M Á T I C A
C U R S O 2 0 1 5 - 2 0 1 6
2
• Como ya hemos estudiado, representar una imagen de n x n píxeles
mediante una representación matricial requiere:
- n2 bits si la imagen es binaria.
- n2 x k bits si la imagen es en escala de grises con L = 2k niveles de gris (= n2 x log2(L) ).
- 3 x n2 x k bits si la imagen es a color (RGB) con L = 2k niveles de gris (= 3 x n2 x log2(L) ).
Tema 8: Almacenamiento de imágenes digitales
3
• Ejemplo:
- Imagen de 128 x 128 con 64 niveles de gris: 128 x 128 x 6 = 98.304 bits = 12 KB.
- Imagen de 1024 x 1024 con 256 niveles de gris: 1024 x 1024 x 8 = 8.388.608 bits = 1024 KB = 1 MB.
Tema 8: Almacenamiento de imágenes digitales
4
• Sean nP y nQ el número de bits necesarios para almacenar dos representaciones distintas, P y Q, de una misma imagen.
Redundancia relativa de P (respecto de Q):
RD = 1 – (1 / CR) donde CR = nP / nQ es el radio de compresión. • Ejemplo:
Si CR = 10, la representación P necesita 10 bits por cada bit de la representación Q. RD = 0,9, luego el 90% de los datos en la representación P es redundante.
Tema 8: Almacenamiento de imágenes digitales
5
• Redundancia de código: Código en un sistema de símbolos usado para representar la información. A veces, las longitudes de las palabras usadas en el código es mayor de lo necesario. • Redundancia entre píxeles:
Debido a la correlación espacial entre un píxel y sus vecinos. • Redundancia psicovisual:
Cierta información tiene menor importancia que otra en el proceso de visión normal. Se dice que esta información es psicovisualmente redundante.
Tema 8: Almacenamiento de imágenes digitales
6
Tema 8: Almacenamiento de imágenes digitales
7
• La compresión de imágenes consiste en eliminar uno o más de estas redundancias.
• Se pueden clasificar las distintas formas de compresión de imágenes
en: - aquellas que no producen errores (o pérdida de información) en la imagen; - aquellas que sí lo producen. • Los procesos de compresión que eliminan la redundancia de código
y/o entre píxeles no producen errores. Aquellos que eliminan la redundancia psicovisual, sí.
Tema 8: Almacenamiento de imágenes digitales
8
• Redundancia en el código:
- Código de Huffman • Redundancia entre píxeles: - LZW - Representación por filas. - Representación por árbol cuaternario. - Planos de bits. • Redundancia psicovisual:
- Transformadas de la imagen.
Tema 8: Almacenamiento de imágenes digitales
9
• Redundancia en el código: - P = imagen de N píxeles es escala de grises con L niveles de gris.
- 𝑁𝑘 = cantidad de píxeles con el mismo nivel de gris k. - 𝑙 𝑘 = número de bits necesarios para almacenar el nivel de gris k. Promedio de bits necesarios para representar cada pixel:
Tema 8: Almacenamiento de imágenes digitales
𝑙 𝑘 𝑁𝑘𝐿−1𝑘=0
𝑁= 𝑙 𝑘 𝑝(𝑘)
𝐿−1
𝑘=0
10
• Redundancia en el código: Ejemplo
Imagen con 6 niveles de gris {a1, a2, …, a6} tal que las probabilidades de cada píxel de tener el color ak son mostradas en la siguiente tabla: Si usamos un código binario de longitud constante, el promedio de bits necesario para almacenar un píxel es 3 bits.
Tema 8: Almacenamiento de imágenes digitales
p(a1) = 0,1 p(a2) = 0,4 p(a3) = 0,06 p(a4) = 0,1 p(a5) = 0,04 p(a6) = 0,3
Valor Valor codificado
a1 000
a2 001
a3 010
a4 011
a5 100
a6 101
11
• Redundancia en el código: Código de Huffman
- Idea: Código de longitud variable tal que aquellos valores con más probabilidad se le asigna un menor número de bits. Así, se consigue que el promedio sea menor. - El procedimiento consta de cuatro pasos:
Tema 8: Almacenamiento de imágenes digitales
12
• Redundancia en el código: Código de Huffman
- Paso 1: Ordenar los valores de grises según la probabilidad de que ocurran (de mayor a menor) y considerar la lista de probabilidades ordenadas. - Paso 2: Crear una tabla donde se van sumando sucesivamente las dos probabilidades más pequeñas y se reordenan los resultados, repitiendo el proceso hasta llegar a la probabilidad 1. - Paso 3: Crear un árbol binario a partir de la tabla donde los hijos son las probabilidades de partida. - Paso 4: A partir del árbol, crear el nuevo código.
Tema 8: Almacenamiento de imágenes digitales
13
• Redundancia en el código: Código de Huffman. Ejemplo
Tema 8: Almacenamiento de imágenes digitales
p(a1) = 0,1 p(a2) = 0,4 p(a3) = 0,06 p(a4) = 0,1 p(a5) = 0,04 p(a6) = 0,3
Símbolo Probabilidad 1 2 3 4
a2 0,4
a6 0,3
a1 0,1
a4 0,1
a3 0,06
a5 0,04
14
• Redundancia en el código: Código de Huffman. Ejemplo
Tema 8: Almacenamiento de imágenes digitales
p(a1) = 0,1 p(a2) = 0,4 p(a3) = 0,06 p(a4) = 0,1 p(a5) = 0,04 p(a6) = 0,3
Símbolo Probabilidad 1 2 3 4
a2 0,4 0,4 0,4 0,4 0,6
a6 0,3 0,3 0,3 0,3 0,4
a1 0,1 0,1 0,2 0,3
a4 0,1 0,1 0,1
a3 0,06 0,1
a5 0,04
15
1
0,6 0,4
0,3 0,3
Símbolo Probabilidad 1 2 3 4
a2 0,4 0,4 0,4 0,4 0,6
a6 0,3 0,3 0,3 0,3 0,4
a1 0,1 0,1 0,2 0,3
a4 0,1 0,1 0,1
a3 0,06 0,1
a5 0,04
0,2 0,1
0,1 0,1
0,06 0,04
Tema 8: Almacenamiento de imágenes digitales
16
1
0,6 0,4
0,3 0,3
Símbolo Probabilidad 1 2 3 4
a2 0,4 0,4 0,4 0,4 0,6
a6 0,3 0,3 0,3 0,3 0,4
a1 0,1 0,1 0,2 0,3
a4 0,1 0,1 0,1
a3 0,06 0,1
a5 0,04
0,2 0,1
0,1 0,1
a2
a6
a1
a4
a3 a5
0,06 0,04
Tema 8: Almacenamiento de imágenes digitales
17
1
0,6 0,4
0,3 0,3
0,2 0,1
0,1 0,1
0
0
0
0
1
1
1
1
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
a2
a6
a1
0,04
1 0 a4
a3 a5
0,06
Tema 8: Almacenamiento de imágenes digitales
18
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
• Promedio de bits:
3 x 0,1 + 1 x 0,4 + 5 x 0,06 + 4 x 0,1 + 5 x 0,04 + 2 x 0,3 = 2,2 bits
Mayor probabilidad = menor nº de bits
Menor probabilidad = mayor nº de bits
Tema 8: Almacenamiento de imágenes digitales
19
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
• Promedio de bits = 2,2 bits
Símbolo Codificado natural
a1 000
a2 001
a3 010
a4 011
a5 100
a6 101
• Promedio de bits = 3 bits
Tema 8: Almacenamiento de imágenes digitales
20
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
• Promedio de bits = 2,2 bits
Símbolo Codificado natural
a1 000
a2 001
a3 010
a4 011
a5 100
a6 101
• Promedio de bits = 3 bits
Tema 8: Almacenamiento de imágenes digitales
- Radio de compresión: CR = 3 bits / 2,2 bits = 1,36 bits
- Redundancia relativa: RD = 1 – (1 / 1,36) = 0,26, luego el 26% del código natural es redundante.
21
• Redundancia en el código: Decodificación de Huffman. Cualquier cadena del código es decodificable de manera única. cadena: 010100111100
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
Tema 8: Almacenamiento de imágenes digitales
22
• Redundancia en el código: Decodificación de Huffman. Cualquier cadena del código es decodificable de manera única. cadena: 010100111100 a3
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
Tema 8: Almacenamiento de imágenes digitales
23
• Redundancia en el código: Decodificación de Huffman. Cualquier cadena del código es decodificable de manera única. cadena: 010100111100 a3 a1
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
Tema 8: Almacenamiento de imágenes digitales
24
• Redundancia en el código: Decodificación de Huffman. Cualquier cadena del código es decodificable de manera única. cadena: 010100111100 a3 a1 a2 a2
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
Tema 8: Almacenamiento de imágenes digitales
25
• Redundancia en el código: Decodificación de Huffman. Cualquier cadena del código es decodificable de manera única. cadena: 010100111100 a3 a1 a2 a2 a6
Símbolo Probabilidad Código Huffman
a1 0,1 011
a2 0,4 1
a3 0,06 01010
a4 0,1 0100
a5 0,04 01011
a6 0,3 00
Tema 8: Almacenamiento de imágenes digitales
26
• EJERCICIO: Esta imagen de 8 bits posee sólo 4 niveles de gris
distintos con probabilidades 0’25, 0’47, 0’25 y 0’03, respectivamente. - ¿Se podría dar una representación más económica con un código de longitud constante? - ¿Se podría mejorar con un código de longitud variable? - ¿Cuál sería el radio de compresión y la cantidad de datos redundantes?
Tema 8: Almacenamiento de imágenes digitales
27
• Redundancia en el código:
- Código de Huffman • Redundancia entre píxeles: - LZW - Representación por filas. - Representación por árbol cuaternario. - Planos de bits. • Redundancia psicovisual:
- Transformadas de la imagen.
Tema 8: Almacenamiento de imágenes digitales
28
• Redundancia entre píxeles: Código LZW. Claves:
- La compresión se produce por darse reiteradamente la sustitución de una cadena de caracteres por un solo símbolo del código. - Conforme se realiza la codificación, se va creando un diccionario en el que se recogen los nuevos símbolos de código. - En general, reduce la redundancia entre píxeles, excepto si el diccionario es excesivamente largo, en cuyo caso puede resultar contraproducente.
Tema 8: Almacenamiento de imágenes digitales
29
• Redundancia entre píxeles: Código LZW.
Dada una “frase” de un alfabeto de M letras, el pseudocódigo sería: 1. Inicializar una tabla (diccionario), asignando a cada letra un código de
0 a M-1. 2. Inicializar P = primera letra de la frase. 3. Sea S = siguiente carácter en la frase. 4. Si PS es una palabra del diccionario, P = PS e ir al paso 3. En caso contrario añadir PS al diccionario asignándole un código n no utilizado, P = S e ir al paso 3.
Tema 8: Almacenamiento de imágenes digitales
30
• CÓDIGO LZW: 1: Inicializar una tabla (diccionario), asignando a cada letra un código de 0 a M-1 2: Inicializar P = primera letra de la frase. 3: Sea S = siguiente carácter en la frase. 4: Si PS es una palabra del diccionario, P = PS e ir al paso 3. En caso contrario, añadir PS al diccionario asignándole un código no utilizado, P = S e ir al paso 3.
P S Diccionario Código
A 0
B 1
C 2
A B AB 3
B A BA 4
A C AC 5
C A CA 6
A B
AB A ABA 7
A
Tema 8: Almacenamiento de imágenes digitales
• Redundancia entre píxeles: Código LZW. Ejemplo
Alfabeto de 3 letras {A,B,C}. Codificar la palabra ABACABA.
31
• CÓDIGO LZW: 1: Inicializar una tabla (diccionario), asignando a cada letra un código de 0 a M-1 2: Inicializar P = primera letra de la frase. 3: Sea S = siguiente carácter en la frase. 4: Si PS es una palabra del diccionario, P = PS e ir al paso 3. En caso contrario, añadir PS al diccionario asignándole un código no utilizado, P = S e ir al paso 3.
P S Diccionario Código
A 0
B 1
C 2
A B AB 3
B A BA 4
A C AC 5
C A CA 6
A B
AB A ABA 7
A
Tema 8: Almacenamiento de imágenes digitales
Alfabeto de 3 letras {A,B,C}. Codificar la palabra ABACABA.
ABACABA = 010230
• Redundancia entre píxeles: Código LZW. Ejemplo
32
- Imagen 4 x 4 de 8-bits (256 niveles de gris)
- Asumimos un diccionario de 512 palabras (9 bits).
Tema 8: Almacenamiento de imágenes digitales
39 39 126 126
39 39 126 126
39 39 126 126
39 39 126 126
• Redundancia entre píxeles: Código LZW. Ejemplo
33
Tema 8: Almacenamiento de imágenes digitales
• Redundancia entre píxeles: Código LZW. Ejemplo
34
- Luego, la imagen queda codificada por la lista de códigos:
39-39-126-126-256-258-260-259-257-126
Es decir, 10 códigos a 9 bits cada uno = 90 bits. - Sin embargo, la representación matricial necesitaría 4 x 4 x 8 = 128 bits de almacenamiento.
Tema 8: Almacenamiento de imágenes digitales
• Redundancia entre píxeles: Código LZW. Ejemplo
35
• Redundancia entre píxeles: RLE
- Se trata de una técnica desarrollada sobre 1950 y se conoce como run- length encoding, o RLE. - Este tipo de representación o compresión es apropiado para imágenes en las que aparecen intensidades repetidas a lo largo de las filas de la imagen. - Así, cada secuencia de la misma intensidad se codifica por un par que especifica la longitud y el nivel de gris que se repite en la secuencia. - En los casos en los que hay pocas repeticiones, la técnica en realidad resulta en un aumento de datos.
Tema 8: Almacenamiento de imágenes digitales
36
• Redundancia entre píxeles: RLE
- Supongamos que la fila tiene una longitud n, y que hay r secuencias. Puesto que son necesarios log2n bits para especificar la longitud de una secuencia (puede tener cualquier longitud entre 1 y n), el número de bits necesarios para especificar todas las longitudes de secuencias de la fila es r log2 n. - Si hay L posibles niveles de gris, cada fila requiere r (log2 n + log2 L)=r log2 (n L) bits , en contraposición con los n log2L bits que son necesarios cuando la fila es tratada como una cadena de longitud n.
Tema 8: Almacenamiento de imágenes digitales
37
Tema 8: Almacenamiento de imágenes digitales
1 0 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 1 1 1 0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 1 1 0 1 1 1 0 0 0 0
0 0 1 1 1 0 0 0 0 0 1 1 1 0 0
Imagen binaria 2D
Representación matricial
Fila Valor inicial de
la fila
Longitudes de las secuencias alternadas
1 1 1 1 11 2
2 0 4 3 1 3 4
3 0 6 3 6
4 0 4 3 1 3 4
5 0 2 3 5 3 2
Correspondencia Runs
Sólo hay que indicar el primer elemento de la fila y las longitudes de las secuencias alternadas: 1 +r log2 n bits / fila
38
• Redundancia entre píxeles: Árbol cuaternario Método (para imágenes binarias): - El nodo raíz del árbol representa la imagen entera. - Si la imagen tiene un solo valor, etiquetamos el nodo raíz con ese valor y paramos; - En caso contrario, añadimos 4 descendientes al nodo raíz, representando los 4 cuadrantes de la imagen. - Repetimos el proceso para cada uno de esos nuevos nodos.
Tema 8: Almacenamiento de imágenes digitales
39
Tema 8: Almacenamiento de imágenes digitales
• Redundancia entre píxeles: Árbol cuaternario. Ejemplo
- Imagen binaria 23 x 23 . Árbol cuaternario de altura 3. - El espacio para almacenar el árbol es proporcional al número de nodos. - Mal comportamiento respecto a traslaciones de la imagen.
40
• Redundancia entre píxeles: Planos de bits - Descomposición de una imagen en escala de grises de L bits en L imágenes de 1 bit cada píxel (binarias) que podrían, por ejemplo, codificarse mediante RLE.
- Sea k el nivel de gris asociado a un píxel: k = aL-1 2
L-1 + aL-2 2L-2 + … + a1 21 + a0 20
- Tomando cada uno de los coeficientes aj, formamos el j-ésimo plano de bits, j = 0, …, L-1. Plano aj = Imagen binaria donde el valor de cada píxel es 0 o 1, dependiendo de lo que valga aj al pasar el valor de intensidad del píxel al código binario.
Tema 8: Almacenamiento de imágenes digitales
41
• Redundancia entre píxeles: Planos de bits. Ejemplo - Imagen de 256 niveles de gris (la intensidad de cada píxel se descompone en 8 bits) - 8 planos de 1 bit. - Píxel con valor 194 194 = 1 x 27 + 1 x 26 + 0 x 25 + 0 x 24 + 0 x 23 + 0 x 22 + 1 x 21 + 0 x 20 = = 11000010
Tema 8: Almacenamiento de imágenes digitales
42
plano a7 plano a6 plano a5 plano a4
Planos de los 4 bits más significativos.
Tema 8: Almacenamiento de imágenes digitales
• Redundancia entre píxeles: Planos de bits
43
Tema 8: Almacenamiento de imágenes digitales
• Redundancia entre píxeles: Planos de bits
Inconveniente: Pequeñas variaciones en los niveles de gris tienen un impacto significativo en la complejidad de los planos de bits. - Ejemplo: En la imagen inicial hay un píxel de intensidad 127 junto a otro de intensidad 128: 127 = 01111111 128 = 10000000 En todos lo mapas de bits habrá un salto de 0 a 1 ó de 1 a 0.
44
Tema 8: Almacenamiento de imágenes digitales
• Redundancia entre píxeles: Planos de bits
Alternativa: Representar primero la imagen mediante un código de Gray de L bits. - Si los dígitos en binario son: aL-1 aL-2 … a1 a0 El mismo número en código de Gray es: gL-1 gL-2 … g1 g0
gj = aj + aj+1 mod 2 si j < L-1 gL-1 = aL-1
Número
Código binario
Código de Gray
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
45
Tema 8: Almacenamiento de imágenes digitales
Planos de los 4 bits más significativos. La segunda fila de imágenes corresponde a los planos de bits usando el código de Gray.
46
Tema 8: Almacenamiento de imágenes digitales
Planos de los 4 bits menos significativos. La segunda fila de imágenes corresponde a los planos de bits usando el código de Gray.
47
• Redundancia en el código:
- Código de Huffman • Redundancia entre píxeles: - LZW - Representación por filas. - Representación por árbol cuaternario. - Planos de bits. • Redundancia psicovisual:
- Transformadas de la imagen.
Tema 8: Almacenamiento de imágenes digitales
48
• La iluminación de una región, tal y como se percibe por el ojo,
depende de otros factores aparte de la luz reflejada. Esto ocurre porque el ojo no responde con igual sensibilidad a toda la información visual.
• Cierta información tiene menor importancia que otra en el proceso
de visión normal.
• Se dice que esta información es psicovisualmente redundante y
se puede eliminar sin que altere la calidad de la percepción de la imagen.
Tema 8: Almacenamiento de imágenes digitales
49
• El método principal para eliminar redundancia psicovisual es el
basado en transformadas por bloques de la imagen, lo que da lugar a una compresión con pérdida de información.
Tema 8: Almacenamiento de imágenes digitales
50
Al contrario de lo que sucedía con los métodos anteriores, son necesarios indicadores que nos permitan medir el error que se comete después de comprimir y descomprimir con respecto a la imagen original. Por ejemplo:
• Error cuadrático medio en una imagen M x N:
1
𝑀𝑁 (𝑓 𝑥, 𝑦 − 𝑓(𝑥, 𝑦))2𝑁−1
𝑦=0𝑀−1𝑥=0
donde 𝑓(𝑥, 𝑦) es la imagen original y 𝑓 𝑥, 𝑦 la imagen obtenida después de comprimir y descomprimir.
Tema 8: Almacenamiento de imágenes digitales
51
• La transformada por excelencia para la compresión de imágenes es la Transformada Discreta del Coseno ó TDC.
• La TDC se usa en el estándar de compresión JPEG (del inglés
Joint Photographic Experts Group, nombre del comité de expertos que lo creó).
• Un estándar de compresión define una serie de procedimientos para comprimir y descomprimir imágenes que se establecen como estándares internacionales para la compresión.
Tema 8: Almacenamiento de imágenes digitales
52
• Estándar de compresión JPEG:
- Método más adecuado para fotografías e imágenes de tonos continuos similares que contengan muchos colores. - Mantiene una calidad en la imagen muy elevada. - Define, entre otros, el sistema de codificación llamado “sequential baseline system”, que consta de los siguientes pasos:
Tema 8: Almacenamiento de imágenes digitales
53
• Estándar de compresión JPEG:
1. Se pasa la imagen del formato RGB a uno en el que se separen las
informaciones de luminosidad y color. El ojo humano es mucho más sensible a la luminosidad que al color, por lo que usualmente, como paso previo, se reduce la resolución en los canales del color (opcional).
2. Se divide la imagen en bloques de 8 x 8 y se transforma cada bloque mediante la TDC.
3. Se realiza un proceso de cuantificación (lo que hace que sea un método de compresión con pérdida de datos).
4. Se codifica el conjunto de datos obtenidos usando un método que no produce pérdidas (Run Length Encoding + Huffman).
Tema 8: Almacenamiento de imágenes digitales
54
• Estándar de compresión JPEG. Paso 1: De RGB a YCbCr RGB: las imágenes se almacenan en 3 canales independientes (rojo, verde y azul) que toman valores de 0 a 255, dependiendo de la intensidad. YCbCr: (Lumninance, Chrominance Blue, Chrominance Red), representa una división entre la luminosidad o cantidad de luz percibida (Y) y la información sobre los colores azul y rojo (Cb, Cr).
Tema 8: Almacenamiento de imágenes digitales
55
• Estándar de compresión JPEG. Paso 1: De RGB a YCbCr El ojo humano es menos sensible a los matices de color que a la cantidad de luz percibida. Por eso, un primer paso consiste en reducir la información almacenada en los canales del color (Cb, Cr). Por ejemplo, si la reducimos a la mitad, en el caso de una imagen 8 x 8 en formato YCbCr, la reduciremos a un canal Y de 8 x 8 y sendos canales Cb y Cr de 4 x 4 (lo que se denota por 4:2:2). Para calcular los valores nuevos de estos canales podemos hallar la media aritmética de los valores de cada 4 píxeles.
Tema 8: Almacenamiento de imágenes digitales
56
• Estándar de compresión JPEG. Paso 1: De RGB a YCbCr Este es un trozo de imagen original y comprimida JPEG, ampliadas para ver las diferencias. Como vemos, los colores rojo y azul en la imagen original se han visto alterados en la imagen JPEG.
Tema 8: Almacenamiento de imágenes digitales
57
• Estándar de compresión JPEG. Paso 1: De RGB a YCbCr Para evitar este efecto, algunos programas ofrecen este paso de manera opcional en la compresión JPEG. De esta forma, los colores no se ven tan degradados y la imagen original y comprimida son prácticamente iguales.
Tema 8: Almacenamiento de imágenes digitales
58
• Estándar de compresión JPEG. Pasos 2: Cálculo TDC - Es la herramienta clave en el estándar de compresión JPEG. - La imagen se descompone en sumas de cosenos (y no de senos y cosenos como en la de Fourier) y sólo toma valores reales.
Tema 8: Almacenamiento de imágenes digitales
59
• Estándar de compresión JPEG. Pasos 2: Cálculo TDC - La TDC de una función de una variable f(x) es:
- La transformada inversa: donde
Tema 8: Almacenamiento de imágenes digitales
60
• Estándar de compresión JPEG. Pasos 2 : Cálculo TDC - La TDC de una función bidimensional f(x,y): para u y v entre 0 y N-1. - La transformada inversa: para x y y entre 0 y N-1.
Tema 8: Almacenamiento de imágenes digitales
61
• Estándar de compresión JPEG. Pasos 2: Cálculo TDC - El núcleo de la TDC es simétrico y separable: Por tanto, la TDC se puede expresar matricialmente como:
C=M F Mt
para cierta matriz M.
Tema 8: Almacenamiento de imágenes digitales
N
babbag
2
)12(cos)(),(
62
• Estándar de compresión JPEG. Pasos 2: Cálculo TDC - Ejemplo: Para el caso N=8, se tiene Y la matriz M se define como aquella que en la posición (i,j) contiene al elemento g(i,j): M=
Tema 8: Almacenamiento de imágenes digitales
16
)12(cos)(),(
babbag
63
• Estándar de compresión JPEG. Pasos 2: Cálculo TDC - Ejemplo:
Tema 8: Almacenamiento de imágenes digitales
Imagen I Matriz F (intensidades de gris)
64
• Estándar de compresión JPEG. Pasos 2: Cálculo TDC - Ejemplo: - Como podemos observar, los valores mayores se encuentran en la parte triangular superior-izquierda de la matriz.
Tema 8: Almacenamiento de imágenes digitales
C = M F Mt =
65
• Estándar de compresión JPEG. Pasos 3: Normalización - Para almacenar la matriz C se realiza un proceso de normalización que consiste en: - Buscar una función N(u,v) (matriz de normalización) tal que C*(u,v) = Redondeo (C(u,v) / N(u,v)) sea una matriz con “muchos” ceros. - C* es la matriz que se almacena.
Tema 8: Almacenamiento de imágenes digitales
66
• Estándar de compresión JPEG. Pasos 3: Normalización - JPEG recomienda la siguiente matriz de normalización estandarizada para imágenes con 256 niveles de intensidad: N(u,v)=
Tema 8: Almacenamiento de imágenes digitales
67
• Estándar de compresión JPEG. Pasos 3: Normalización - Aplicando esta normalización a nuestro ejemplo obtenemos que la matriz que debemos almacenar es: C*(u,v) =
Tema 8: Almacenamiento de imágenes digitales
68
• Estándar de compresión JPEG. Pasos 3: Normalización - Es en el paso de normalización donde radica la pérdida de información. Dependiendo de cómo normalicemos C*, conseguiremos comprimir más pero, a la vez, perder más información. - Para poder aplicar la TDC según el estándar JPEG, debemos dividir la imagen original en matrices cuadradas de 8 x 8 píxeles. - Cada matriz C de 8 x 8 píxeles obtenida aplicando la TDC a cada subimagen de dimensión 8 x 8 se aproxima por otra más sencilla C* mediante el proceso de normalización.
Tema 8: Almacenamiento de imágenes digitales
69
• Estándar de compresión JPEG. Pasos 4: Codificación.
Almacenamiento de la imagen normalizada. - Para almacenar C* se sigue un recorrido en zig-zag de la matriz para obtener una lista con los ceros acumulados al final. Orden del recorrido
Tema 8: Almacenamiento de imágenes digitales
70
• Estándar de compresión JPEG. Pasos 4: Codificación.
Almacenamiento de la imagen normalizada. - Para almacenar C* se sigue un recorrido en zig-zag de la matriz para obtener una lista con los ceros acumulados al final. - Se usa Run Length Encoding para codificar la lista resultante, ya que suele tener muchas secuencias de ceros. - En combinación con esta técnica, se usa un código de Huffman para codificar el resultado. Aunque podemos utilizar una compresión de Huffman propia, existen unas tablas estandarizadas que nos permiten obtener un código de Huffman para cualquier valor.
Tema 8: Almacenamiento de imágenes digitales
• Estándar de compresión JPEG. Pasos 4: Codificación. - Ejemplo: C*= 29,9,-7,5,-12,-4,-6,-5,6,-3,2,-2,1,1,-1,0,1,0,0,1,0,0,0, 1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,F. Con la letra F (de fin) indicamos que desde ese elemento hasta el final de la lista son todos ceros (hasta completar los 64 elementos de la lista). El término DC (29 en el ejemplo) se codifica haciendo la diferencia con el de la subimagen anterior. La codificación de los términos AC (el resto) se realizan siguiendo unas tablas estandarizadas.
71
Tema 8: Almacenamiento de imágenes digitales
• Estándar de compresión JPEG. Descompresión: - Paso 1: Descodificarla para obtener la matriz normalizada C*. -Paso 2: “Deshacemos” la normalización: C’(u,v) = C*(u,v) N(u,v), donde N(u,v) es la matriz de normalización. - Paso 3: Aplicamos la transformada inversa de C’ para obtener F’.
72
Tema 8: Almacenamiento de imágenes digitales
• Estándar de compresión JPEG. Descompresión:
73
Tema 8: Almacenamiento de imágenes digitales
Matriz diferencia
Matriz descomprimida Matriz original
74 • Estándar de compresión JPEG.
Tema 8: Almacenamiento de imágenes digitales
Top Related