Creo recordar que no comenté nada en el blog pero hace unos meses estuve haciendo un compresor de imagenes sin perdida, basado en huffman y diferencia de pixeles, ya hablaré de ello en otra entrada.
Este fin de semana he recordado dicho proyecto y he decidido implementar un compresor de imagenes con perdida. Para ello he usado un algoritmo parecido al que usa JPG, esto es, divido la imagen en bloques de 8x8, le aplico la DCT y recorro el resultado en zig zag y lo voy añadiendo a un array, a continuación aplico una codificación Run-Length Encoding.
La imagen original tiene un tamaño de 8x8x3 que hacen un total de 192 bytes, sin contar bytes de cabecera, y la imagen una vez comprimida ocupa 12 bytes. Tengo que decir que es una imagen especial que se comprime muy bien. En aplicaciones reales la compresión será algo menor.
Hay que tener en cuenta también que al resultado de esta compresión aún no se le aplica huffman por lo que la compresión final será algo mayor.
Estas últimas semanas he estado trabajando en lo que inicialmente se trataba de un port del motor de renderizado en javascript AL3D pero que al final va a tratarse de una siguiente versión del mismo motor de renderizado.
ALMath ha sido totalmente portado a C++ aunque actualmente para el motor de renderizado se usa la librería matematica GLM.
Actualmente incorpora un pequeño subconjunto de funcionalidades de AL3D pero ya incorpora algunas mejoras con respecto a la versión de javascript. Las características que soporta actualmente son las siguientes:
Cargador de mallas (en formato obj) y sin texturas
Luz direccional predefinida en los shaders sin posibilidad de cambiarse
Camara ortográfica y perspectiva
Bounding Volumes en tiempo de carga. OBB y AABB
Selección de mallas mediante Ray Casting (a direferencia de la versión de javascript que usaba trucos de opengl para realizar la seleccón).
La idea es introducir técnicas que se usan en motores avanzados como Deferred Shading y cuando esté acabada la versión de C++ evolucionar la versión de javascript.
Por lo general no suelo escribir sobre programación en general, pero este tema siempre me ha parecido bastante interesante.
Actualmente estoy programando un algoritmo de compresión de video/imagen sin perdida que se basa en árboles y predictores. La primera iteración del algoritmo fue hacerlo funcionar sin preocuparse demasiado en la optimización. Al ser un algoritmo basado en árboles la primera iteración del algoritmo usaba recursividad para recorrer los árboles.
Una vez que funciona el algoritmo me propuse eliminar la recursividad. El algoritmo debe funcionar de forma fluida en microcontroladores (poca memoria y poca potencia).
La recursividad en computación y para que se entienda facilmente es llamar a una función X dentro de la misma función X. Por lo general los métodos recursivos constan de un caso base y un caso general. El caso base es el que termina la recursividad y el caso general el que hace llamadas recursivas. Aquí tenemos una función que recorre un arbol en profundidad e imprime el contenido de las hojas.
Aquí el caso base es el tercer if, en dicho if no hay llamadas a la función, cuando sale de dicho if se termina la función y el programa continua ejecutandose en esta misma función, ya que posteriormente se habia hecho una llamada a esta misma función.
La recursividad funciona gracias a la pila o stack, esta estructura de datos es del tipo LIFO (Last In First Out) que significa que el último que entra en la pila es el primero que se coge cuando se vaya a sacar un elemento, podemos hacer un simil con un conjunto de plato apilados, cuando vayamos a dejar un plato lo dejaremos arriba del todo y cuando vayamos a necesitar un plato lo cogeremos de arriba. He hablado anteriormente sobre la pila en este blog, como por ejemplo en la categoría security: http://bitybyte.angelluispg.es/category/security/ donde hablo sobre vulnerabilidades de la pila y en esta entrada http://bitybyte.angelluispg.es/2016/07/10/emulacion-de-una-cpu/ donde emulo creo una CPU e implemento una pila.
Cuando hacemos llamadas a procedimientos desde lenguajes de alto nivel lo que se está haciendo a nivel de máquina es empujar los parametros de dicha función a la pila, incrementar el registro SP (Stack Pointer) y hacer un call a la función. Podemos eliminar la recursividad si implementamos una pila software y usamos dicha pila. Usar esta segunda aproximación es mas eficiente, ya que no tenemos que realizar el call a la función.
Los lenguajes de alto nivel suelen implementar una pila en su librería, no es el caso de C, en donde si queremos una pila tendremos que programarla nosotros mismos. Aquí dejo mi implementación de pila.
Básicamente lo que hacemos es usar nuestra pila en vez la del sistema. Es mejor ver el ejemplo en vez de explicarlo. Aquí se puede ver el mismo algoritmo de recorrido de árboles en profundidad pero esta vez de forma iterativa
Vemos como se han eliminado las llamadas a la función y ahora se hace uso de la pila software que se ha implementado.
