Compresión de imágenes

Para esta tarea de compresión de imágenes he decidido implementar una combinación del algoritmo de Huffman con un método de reducción de colores.

Reducción de colores

Para reducir los colores lo que se realizo es por parámetros definir el "paso" de los colores, por ejemplo de 20, lo primero que se hizo fue agarrar todas las posiciones de los píxeles que tienen un valor de color de 0 a 19, entonces se busca el valor de color que es mas frecuente y ese es el que se usa en vez de todos los demás entonces en vez de utilizar por ejemplo 0, 1, 2 o 3 en color, si el color 2 es el más frecuente en la figura ese es el que voy a utilizar.
Cuando el paso es 20, en vez de tener una lista con 255 colores posibles se tiene una con 13.

Huffman

Codificar
Después se escribió un archivo binario, que contenía todos los códigos de los píxeles en el ejemplo anterior que mencioné se puede decir que solo había 13 códigos posibles ya que elegimos un paso de 20, entonces el árbol no estaba muy extenso, si no se hubiera hecho lo de la reducción de colores se hubieran tenido 255 códigos posibles lo cual no es algo satisfactorio. Este fue el objetivo de la reducción de colores que no se tuviera un árbol  muy extenso.

Decodificar
Y se leyó el archivo binario, y teniendo el árbol fue fácil descomprimir, se realizó igual que la tarea pasada, se fueron buscando los colores que estuvieran en el diccionario para ir pintando los colores.

Resultados:

Tabla de frecuencias

Porcentaje de compresión

Tiempo

Código:

	#!/usr/bin/python
	from Tkinter import *
	from PIL import Image, ImageTk
	import math
	import sys
	import filtros
	import random
	import ImageFont, ImageDraw
	import Image
	import time
	import os
	import matplotlib.pyplot as plt
	DEBUG = False
	class Nodo:
	"""nodo hoja
	"""
	def __init__(self, simbolo, peso):
	self.simbolo = simbolo
	self.peso = peso
	self.der = None
	self.izq = None
	self.padre = None
	self.x = 0
	self.y = 50
	self.ancho = 3000
	self.largo = None
	def crea_arbol(frec, ordenados):
	"""hace el arbol de acuerdo a las frecuencias
	regresa la raiz del arbol
	"""
	nodos = []
	izq = None
	der = None
	for i in ordenados:
	nodos.append(Nodo(i, frec[i]))
	while True:
	if len(nodos)>1:
	izq = nodos[0]
	nodos = nodos[1:]
	der = nodos[0]
	nodos = nodos[1:]
	x = Nodo(str(izq.simbolo)+str(der.simbolo), izq.peso + der.peso)
	x.izq = izq
	x.der = der
	nodos.append(x)
	der.padre = x
	izq.padre = x
	nodos = sorted(nodos, key=lambda x: x.peso)
	if DEBUG:
	print "*papa %s %s, *izq %s %s *der %s %s" %(x.peso, x.simbolo,
	x.izq.peso,x.izq.simbolo,
	x.der.peso,x.der.simbolo)
	elif len(nodos)==1:
	padre = Nodo(str(izq.simbolo)+str(der.simbolo), izq.peso + der.peso)
	padre.izq = izq
	padre.der = der
	nodos = []
	if DEBUG:
	print "*papa %s %s, *izq %s %s *der %s %s" %(padre.peso, padre.simbolo, padre.izq.peso,padre.izq.simbolo, padre.der.peso, padre.der.simbolo)
	else:
	break
	return padre
	def codigos(hojas):
	"""obtiene los codigos haciendo un recorrido desde la
	hoja a la raiz
	"""
	lista = []
	dic = {}
	for i in hojas:
	byte = ""
	padre = i.padre
	actual = i
	while True:
	if padre:
	pass
	else:
	break
	if actual == padre.izq:
	byte = byte + "1"
	else:
	byte = byte + "0"
	actual = padre
	padre = padre.padre
	lista.append((i.simbolo, i.peso, byte[::-1]))
	dic[i.simbolo]=byte[::-1]
	print lista
	print "RGB\t Frecuencia\t Codigo"
	for i in lista:
	print "%s\t%s\t\t%s" %(i[0], i[1], i[2])
	return lista, dic
	def obtiene_hojas(nodos):
	"""obtiene las hojas del arbol, recibe como entrada
	toda la lista de nodos
	"""
	hojas = []
	for nodo in nodos:
	if nodo.der == None and nodo.izq == None:
	hojas.append(nodo)
	print "Numero de hojas %s" %(len(hojas))
	return hojas
	def recorrer(padre, lista_nodos, lista_pesos):
	"""recorrido en preorden solo para obtener la lista de
	todos los nodos
	"""
	if padre != None:
	lista_nodos.append(padre)
	lista_pesos.append(padre.peso)
	recorrer(padre.izq, lista_nodos, lista_pesos)
	recorrer(padre.der, lista_nodos, lista_pesos)
	return lista_nodos, lista_pesos
	def escribe_tabla(codigos):
	"""escribe el diccionario en un archivo
	"""
	f = open("tabla_frecuencias.txt", "w")
	for i in codigos:
	f.write("%s %s\n" %(i[0], i[2]))
	def escribe_codigos(imagen, codigos):
	"""se escriben los RGB
	"""
	pixeles = imagen.load()
	x, y = imagen.size
	f = open("frase_codificada.txt", "w")
	for a in range(x):
	for b in range(y):
	f.write("%s" %codigos[pixeles[a,b][0]])
	f.write("\n")
	f.close()
	f = open("frase_codificada.txt")
	texto = f.read()
	return len(texto)
	def decodificar(raiz, colores,x,y):
	"""decodifica los valores RGB
	"""
	f = open("frase_codificada.txt")
	frase_codificada = f.read()
	#print frase_codificada
	frase_encontrada = ""
	padre = raiz
	while len(frase_codificada)>0:
	s = str(frase_codificada[0])
	frase_codificada = frase_codificada[1:]
	if s == "0":
	raiz = raiz.der
	else:
	raiz = raiz.izq
	if raiz.der == None and raiz.izq == None:
	frase_encontrada = str(frase_encontrada)+str(raiz.simbolo)
	raiz = padre
	a = True
	c = []
	while(len(frase_encontrada)) > 0:
	s = ""
	a = True
	while a:
	s = s + frase_encontrada[0]
	frase_encontrada = frase_encontrada[1:]
	if int(s) in colores:
	c.append(int(s))
	a = False
	print c
	#se regresan los valores RGB decodificados
	return frase_encontrada
	def canastas(imagen, pas):
	"""canastas para tomar por intervalos
	los valores
	"""
	inicio = time.time()
	imagen = filtros.hacer_gris(imagen)
	pixeles = imagen.load()
	x, y = imagen.size
	colores = {}
	frec = {}
	for a in range(x):
	for b in range(y):
	valor = pixeles[a,b][0]
	valor = int(valor - float(valor%pas))
	if valor in colores:
	colores[valor].append((a,b))
	frec[valor] += 1
	else:
	colores[valor] = []
	colores[valor].append((a,b))
	frec[valor] = 1
	nueva_im = Image.new("RGB", (x, y))
	nueva = nueva_im.load()
	for i in colores:
	for j in colores[i]:
	nueva[j[0], j[1]] = i,i,i
	nueva_im.save('2.png', "png")
	imagen.save('1.png', "png")
	print "TABLA DE FRECUENCIAS"
	ordenados = sorted(frec, key=frec.get)
	for i in ordenados:
	print i
	raiz = crea_arbol(frec, ordenados)
	lista_pesos = []
	lista_nodos = []
	lista_nodos, lista_pesos = recorrer(raiz, lista_nodos, lista_pesos)
	print "Recorrido en preorden %s" %lista_pesos
	#obtengo hojas del arbol
	hojas = obtiene_hojas(lista_nodos)
	#se obtienen los codigos para cada simbolo
	lista_codigos, dic_codigos = codigos(hojas)
	#se escribe una tabla con sus frecuencias
	escribe_tabla(lista_codigos)
	#se pasan los valores RGB a los codigos encontrados
	len_codificado = escribe_codigos(nueva_im, dic_codigos)
	#se decodifica
	frase_decodificada = decodificar(raiz, colores,x,y)
	tiempo_total = time.time() - inicio
	return tiempo_total
	def main():
	try:
	imagen_path = sys.argv[1]
	print imagen_path
	imagen = filtros.abrir_imagen(imagen_path)
	except:
	print "No seleccionaste una imagen"
	return
	tiempos = []
	peso1 = []
	peso2 = []
	com = []
	for pas in range(20,60,40):
	tiempos.append(canastas(imagen, pas))
	ori = int(os.stat("1.png").st_size)
	res = int(os.stat("2.png").st_size)
	porcentaje = (res * 100 ) / float(ori)
	print "Se comprimio ", 100 - porcentaje, "%."
	peso1.append(ori)
	peso2.append(res)
	print tiempos, peso1, peso2
	l2 = plt.plot(tiempos, 'b', label='Tiempo')
	plt.legend(loc='upper left', numpoints = 1)
	plt.ylabel('tiempo')
	plt.xlabel('pasos')
	plt.title("Tiempo de ejecucion")
	plt.show()
	l2 = plt.plot(peso1, 'b', label='resultado')
	l1 = plt.plot(peso2, 'r', label='original')
	plt.legend(loc='upper left', numpoints = 1)
	plt.ylabel('peso')
	plt.xlabel('pasos')
	plt.title("Pesos")
	plt.show()
	main()

view raw gistfile1.py hosted with ❤ by GitHub

Las imágenes decodificadas:

Original

 Paso 20

Paso 60

Original

Paso 60

Conclusiones

Se puede observar que se obtienen mejores resultados cuando se utilizan menos valores RGB sin embargo se pierde más calidad en la imagen, pero el método puede tener aplicaciones cuando lo que se necesita es que el archivo pese poco y no se requiere una muy calidad de la imagen. También que el tiempo baja conforme se aumenta el paso para codificar.