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

Abstract

RESUMEN: 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). 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.

ABSTRACT: 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.