3 de enero de 2016

Filtro Paeth con OMP

Voy a comenzar el blog explicando el algoritmo Paeth, que se usa en el formato de imagen sin pérdida PNG, es un filtro que se aplica antes de aplicar la compresión DEFLATE, se puede mezclar con otros, de manera que una imagen PNG puede tener una líneas filtradas con Paeth u otros filtros del estándard.

Es un algoritmo que resta cada píxel al píxel adyacente más cercano (anterior, superior o esquina izquierda), se aplica a cada color por separado y esto produce una imagen con números más cercanos a cero. Para una definición más detallada os remito a la Wikipedia.

El filtro Paeth, consiste en crear una imagen nueva aplicando las siguiente operación sobre cada píxel y cada canal:

El valor x es el píxel actual, b el de arriba, a el anterior y c el de la esquina izquierda.

c | b
a | x

En caso de la primera fila y la primera columna, al no tener valores anteriores, se asigna pa, pb y pc a 0. En el caso de superar 255, se debe hacer el modulo y las operaciones de p, pa, pb y pc deben ser sin modulo, por ejemplo, en un entero como en el código anterior.

Como podemos ver, este algoritmo es muy paralelizable, ya que no necesitamos los datos de iteraciones anteriores para la interación actual. A continuación la versión inicial del codigo:

En la función paeth_filter hemos cambiado las fórmulas para hacer menos cálculos y usar una variable menos. En la función paeth, hemos hecho tres bucles para evitar los if que penalizan la predicción de saltos, primero hacemos el primer píxel, después la primera línea, el siguiente bucle será la primera columna y finalmente iteramos sobre el resto de la imagen.

Paralelizar este código es bastante sencillo, crearemos los threads justo después de asignar el valor del primer píxel, los dos primeros bucles se pueden paralelizar sin problemas y entre ellos se pueden hacer a la vez, hay que sincronizar antes de entrar al tercer bucle, ya que se usan datos de la primera fila y la primera columna. Aquí el código:

Con esto conseguimos paralelizar paeth, aún y así, hay que tener en cuenta que las imagenes suelen ser pequeñas y puede interesar más paralelizar todo el proceso desde fuera, una imagen o varias en cada thread, por eso, esta solución será óptima para imágenes grandes.

Haz clic aquí para bajar el código completo. (Incluye lectura y guardado de imagen PPM y implementa tanto la función Paeth como su inversa además de una función de promedio parecida a Paeth).

No hay comentarios:

Publicar un comentario