Resumen de Free from curve and surface reconstruction through simulated annealing-based metaheuristic techniques
- español
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.
- English
Reverse engineering has become ubiquitous in the computer-aided design and manufacturing industry (CAD/CAM). One of the most sought after tools in many industries and scientific fields is the ability to build a digital model from a 3D-scanned real world object. In this Thesis, we propose a methodology to automatically find an optimal free-form model that fits a given point cloud.
Our methodology is based on three techniques, namely: least-squares regression, the Simulated Annealing optimization algorithm and two information sciences criteria. The first step consist of transforming the geometrical problem of reconstructing the shape of data into an optimization problem taking advantage of the least-squares regression procedure. The resulting problem turns to be a non-linear system of very difficult solution. To overcome the minimization of such a challenging functional we make use of the Simulated Annealing algorithm, a powerful meta-heuristic that mimics the thermodynamics behind the cooling of a metal. By means of this stochastic-driven optimization method, we retrieve the functional architecture of our baseline spline model. These two steps are repeated for a range of baseline splines of varying complexity. Finally, we search the best among these candidate models by means of either the Akaike or Bayes Information Criteria
