Es una implementación de este algoritmo de compresión fractal de imágenes publicado en IEEE en mi época universitaria
Se hace uso de la librería de triangulación incremental de Delaunay usada en la aplicación de Morphing
Algoritmo a alto nivel:
- Compresión:
- La compresión fractal se caracteriza por que no se guardan valores de píxeles, sino relaciones entre regiones de la imagen (entre triángulos en este caso).
- Se divide la imagen en una triangulación, con los triángulos de dominio.
- Se divide la imagen en otra triangulación, con los triángulos (mayores) para el codebook.
- Las triangulaciones son dinámicas, se usa el algoritmo split and merge en función de la varianza de los píxeles de los triángulos.
- Una vez se tiene la triangulación para el codebook, se eligen los 2^n triángulos más representativos, que serán el codebook, donde el valor de n incidirá drásticamente en el tiempo de compresión, y un poco en el ratio de compresión y en la calidad obtenida.
- Luego, para cada triángulo de dominio, se busca el mapeo óptimo con un triángulo del codebook (con un criterio de mínimo error cuadrático medio (MSE))
- El mapeo óptimo entre triángulos se busca haciendo combinaciones de:
- Permutaciones de los vértices (6 posibilidades)
- Buscando un offset para la media
- Buscando un factor de escala entre 0 y 1 para aplicarlo a la desviación de la media (entre 0 y 1, para evitar la divergencia del proceso iterativo de descompresión)
Esos parámetros deberán cuantizarse con pocos bits, para que el tiempo y ratio de compresión sean razonables, en compromiso con la calidad obtenida.
- Información almacenada en el archivo comprimido para cada uno de los canales:
- La información para reproducir las dos triangulaciones:
- Triángulos que hacen split en cada iteración
- Vértices eliminados por el merge (al final de las iteraciones de split)
- La elección de los 2^n triángulos del codebook
- El mapeo óptimo de cada triángulo de dominio:
- Con qué triángulo del codebook mapea (n bits)
- La permutación de vértices óptima (6 combinaciones, 3 bits)
- Offset (los autores indican que 6 bits es un buen compromiso)
- Escala (los autores indican que 6 bits es un buen compromiso)
- Descompresión (para cada canal):
- Se obtienen los triángulos de las dos triangulaciones.
- Se obtienen los triángulos del codebook.
- Se itera hasta que converja:
- El mapeo de todos los triángulos de dominio, desde sus mapeos óptimos con los triángulos del codebook
Tras cursar el máster de I.A., me veo en condiciones de innovar en la obtención de los triángulos más representativos para el codebook, aplicando nada más y nada menos que un K-medoids.
La innovación no sé si mejora o si empeora el algoritmo, pero evita que tenga que programarlo yo (que en principio parecía complicado de programar).
Se divide el procesamiento en los canales de la imagen (normalmente RGB).
Se hace uso de multiprocesamiento (un hilo para cada canal).
