Aproximación rala de imágenes naturales basada en optimización no convexa y aplicaciones a restauración

Resumen

Las necesidades actuales han potenciado el rápido crecimiento de las aplicaciones del procesamiento de imágenes, Al principio, estos problemas se aproximaban de una forma totalmente heurística. Actualmente, cada vez se da más importancia a desarrollar buenos modelos de las imágenes que permitan una aplicación genérica a gran variedad de tareas. Nuestro cerebro puede discriminar la información relevante en una imagen distorsionada, ya que los objetos del mundo que nos rodean tienen una determinada estructura típica que se refleja en las imágenes naturales (aquellas que representan el mundo que nos rodea), mientras que las imágenes aleatorias no tienen, en general, ninguna estructura. Para realizar de manera automática este tipo de procesamiento, e s de vital importancia contar con un buen conocimiento a priori sobre la estructura típica de las imágenes naturales. Inspirándonos en lo que sabemos del procesamiento de los estímulos visuales en el cerebro, queremos representar las imágenes con el menor número posible de muestras, para facilitar así su descripción estadística, captación, procesamiento y/o almacenamiento. La capacidad de expresar información con pocos elementos se puede ver considerablemente aumentada si transformamos los píxeles a un nuevo dominio redundante (que tiene más coeficientes que píxeles hay en la imagen). Dado un vector y un conjunto de vectores que define n un dominio redundante, el problema de aproximación rala consiste en minimizar una cierta medida del error cometido al expresar el vector dado combinando linealmente un número dado de vectores (desconocidos) del conjunto. Debido a la complejidad de este problema, las aproximaciones tradicionales han consistido en encontrar las condiciones teóricas bajo las cuales estas técnicas resuelven óptimamente el problema. Existe una tercera clase de métodos basados en umbralización iterativa. Han demostrado ser más eficientes y dar mejores resultados, tanto en su capacidad de compactación de la energía como en su aplicación a problemas de restauración, que los heurísticos voraces o las estrategias clásicas de optimización. Algunas de sus variantes más exitosas todavía no están bien fundamentadas en la teoría, ni su rendimiento bien estudiado en cuanto a la aplicación a restauración de imágenes. En esta Tesis se estudian dos métodos de este último tipo, que nunca han sido derivados como solución a un problema de optimización. La derivación que proponemos demuestra que es relativamente sencillo aplicar técnicas conocidas de optimización para encontrar mínimos locales al problema de aproximación rala directamente. El primero de ellos lleva a cabo una minimización del error de aproximación, dado un valor de una determinada norma Lp del vector que pondera la importancia de cada vector del conjunto escogido para formar la aproximación. Su convergencia se demuestra describiéndolo como un método basado en proyecciones ortogonales alternas entre dos conjuntos. Llamamos a este método Lp-AP. Estudiamos los casos p = O, para el que el método es sub-óptimo, y p = 1 , para el que obtenemos el mínimo global. El énfasis de nuestro s experimentos está en realizar pruebas exhaustivas para analizar su comportamiento en condiciones prácticas de procesamiento de imágenes. Veremos que el método LO-AP es claramente superior a Ll-AP y a los métodos voraces en términos de compactación de energía. El segundo método se deriva en base al descenso en la dirección opuesta al gradiente en versiones cada vez menos suavizadas de una función continua y restringida equivalente a la función de coste (discontinua y sin restringir) del problema de aproximación rala. Llamamos LO-GM a este método. Veremos que 1 os resultados de compactación de LO-GM mejoran a los de LO-AP, siendo comparable con el estado de la técnica en aproximación rala. También presentamos una versión convexa de este método, a la que llamamos Ll-GM. Por último, hemos adaptado los métodos propuestos para resolver problemas de restauración. En concreto, proponemos el u so de LO-AP para eliminar artefactos de cuantificación espacial , y de LO-GM para la interpolación de píxeles o zonas perdidas de la imagen, para la interpolación de imágenes de color a partir de mosaicos y para el incremento de detalle o super-resolución. Veremos que obtenemos buenos resultados para estos problemas, siendo competitivos o superiores a otros métodos elegidos como buenos representantes del estado de la técnica actual heurísticos voraces o en relajar la función de coste asociada para que sea convexa. Además, se ha puesto mucho esfuerzo enencontrar las condiciones teóricas bajo las cuales estas técnicas resuelven óptimamente el problema. Existe una tercera clase de métodos basados en umbralización iterativa. Han demostrado ser más eficientes y dar mejores resultados, tanto en su capacidad de compactación de la energía como en su aplicación a problemas de restauració n, que los heurísticos voraces o las estrategias clásicas de op timización. Algunas de sus variantes más exitosas todavía no es tán bien fundamentadas en la teoría, ni su rendimiento bien est udiado en cuanto a la aplicación a restauración de imágenes. En esta Tesis se estudian dos métodos de este último tipo, que nunca han sido derivados como solución a un problema de optimiz ación. La derivación que proponemos demuestra que es relativame nte sencillo aplicar técnicas conocidas de optimización para en contrar mínimos locales al problema de aproximación rala direct amente. El primero de ellos lleva a cabo una minimización del e rror de aproximación, dado un valor de una determinada norma Lp del vector que pondera la importancia de cada vector del conju nto escogido para formar la aproximación. Su convergencia se de muestra describiéndolo como un método basado en proyecciones or togonales altern as entre dos conjuntos. Llamamos a este método Lp-AP. Estudiamo s los casos p = O, para el que el método es sub-óptimo, y p = 1 , para el que obtenemos el mínimo global. El énfasis de nuestro s experimentos está en realizar pruebas exhaustivas para analiz ar su comportamiento en condiciones prácticas de procesamiento de imágenes. Veremos que el método LO-AP es claramente superior a Ll-AP y a los métodos voraces en términos de compactación de energía. El segundo método se deriva en base al descenso en la dirección opuesta al gradiente en versiones cada vez menos sua vizadas de una función continua y restringida equivalente a la función de coste (discontinua y sin restringir) del problema de aproximación rala. Llamamos LO-GM a este método. Veremos que 1 os resultados de compactación de LO-GM mejoran a los de LO-AP, siendo comparable con el estado de la técnica en aproximación r ala. También presentamos una versión convexa de este método, a la que llamamos Ll-GM. Por último, hemos adaptado los métodos p ropuestos para r esolver problemas de restauración. En concreto, proponemos el u so de LO-AP para eliminar artefactos de cuantificación espacial , y de LO-GM para la interpolación de píxeles o zonas perdidas de la imagen, para la interpolación de imágenes de color a part ir de mosaicos y para el incremento de detalle o super-resoluci ón. Veremos que obtenemos buenos resultados para estos problemas, siendo competitivos o superiores a otros métodos elegidos como buenos representantes del estado de la técnica actual.