Free from curve and surface reconstruction through simulated annealing-based metaheuristic techniques

Résumé

En esta tesis doctoral se propone la aplicación de técnicas metaheurísticas basadas en Simulated Annealing para la reconstrucción eficiente y automática de curvas y superficies de forma libre. Este problema tiene un interés evidente en muchos campos de la ciencia y la ingeniería, desde problemas de visualización científica hasta la tomografía computerizada o la resonancia magnética. Es también una tecnología clave en los procesos de diseño y la producción industrial asistidos por computador (CAD/CAM). Como resultado del uso de escáneres y otras metodologías de adquisición se obtienen nubes de puntos, por lo general de tamaño masivo y sujetas a diversos tipos de ruidos. La obtención de los parámetros relevantes para la reconstrucción lleva a un problema de optimización continuo, no lineal, de muy alta dimensión para nubes muy grandes de puntos dato y que normalmente es multimodal. Por ello, es un problema de muy difícil resolución. De hecho, tanto las técnicas clásicas de optimización como las heurísticas han fracasado hasta la fecha a la hora de obtener una solución satisfactoria y de forma totalmente automática del problema general. Para solventar estas dificultades, en esta tesis doctoral proponemos el uso de técnicas metaheurísticas basadas en Simulated Annealing, un método surgido a partir del proceso termodinámico del recocido de metales usando simulaciones de Monte Carlo y ampliamente utilizado para la resolución de problemas de optimización, tanto continuos como discretos. En primer lugar se realiza un análisis del estado del conocimiento en cuanto a métodos de optimización estocástica se refiere, para posteriormente estudiar las aportaciones más relevantes en torno al algoritmo de Simulated Annealing. Finalmente para cada tipo de problema de reconstrucción resuelto, se propone una variante de Simulated Annealing, con importantes aportaciones al estado del conocimiento en cada una de las principales fases del algoritmo. Dichas técnicas meta-heurísticas, encuadradas en el paradigma de la optimización estocástica, se combinan con técnicas clásicas de regresión mediante mínimos cuadrados para obtener un modelo de forma libre, por lo general una variedad B-spline (racional o no), que aproxime la nube de puntos original. A fin de obtener un modelo que sea óptimo desde un punto de vista del compromiso de fidelidad a los datos y complejidad, se utilizan diversos criterios de ciencias a de la información, de entre los que cabe destacar tanto el criterio de información de Akaike y como el Bayesiano. A fin validar la calidad de la metodología propuesta se resuelven una serie de ejemplos, con diversos grados y tipos de dificultad (geométrica, optimización etc.), mediante el uso de nuestro método basado en el Simulated Annealing, comprándolo con otros algoritmos de optimización estocástica en la vanguardia del estado del conocimiento. Por último se realiza un estudio de las principales líneas de investigación surgidas a partir del trabajo realizado.