Compresión de imágenes eliminando
la redundancia de código
Sea P una imagen en escala de grises (con L niveles de grises: 0,1,2,...,L-1) de N píxeles.
Sea Nk la cantidad de píxeles que tienen el mismo nivel de gris k. Entonces, el promedio de bits necesario para representar cada píxel es:
åk<L l(k)
p(k)
donde l(k) es el número de bits necesarios para almacenar el color k y
p(k)=Nk / N,
es decir, p(k) es la probabilidad de cada píxel de tener el color k.
Por ejemplo, si L=8 entonces el promedio de bits necesario para representar cada píxel es 3, usando un código binario de longitud constante.
Si, por el contrario, usamos un código de longitud variable tal que a aquellos valores con más probabilidad se le asigna un menor número de bits, se consigue que el promedio sea menor.
Código de Huffman
Paso 1. Ordenar los valores de grises según la probabilidad de que ocurran (de mayor a menor).
Paso 2. Crear una tabla donde se van sumando sucesivamente las dos probabilidades más pequeñas, hasta que no se pueda más.
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.
Ejemplo: Consideremos una imagen con 6 niveles de grises:0,1,2,3,4,5 tal que
| p(0)=0,1 | p(1)=0,4 | p(2)=0,06 | p(3)=0,1 | p(4)=0,04 | p(5)=0,3 |
Observemos que si usamos el código natural, necesitamos 3 bits para codificar cada valor:
| Valor | Valor codificado |
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
Vemos que el promedio de bits necesario es 3.
Ahora creamos la tabla para obtener el código de Huffman:
Formamos el árbol binario a partir de la tabla:
