Tesis:
Graph search and its application to image matching
- Autor: ARTIEDA TRIGUEROS, Jorge
- Título: Graph search and its application to image matching
- Fecha: 2017
- Materia: Sin materia definida
- Escuela: E.T.S. DE INGENIEROS INDUSTRIALES
- Departamentos: AUTOMATICA, INGENIERIA ELECTRONICA E INFORMATICA INDUSTRIAL
- Acceso electrónico: http://oa.upm.es/47346/
- Director/a 1º: SAN SEGUNDO CARRILLO, Pablo
- Resumen: La principal innovación presentada en esta tesis es una innovadora técnica de filtrado para la asociación de puntos característicos entre pares de imágenes. Esta técnica tiene en cuenta múltiples hipótesis en la asociación de puntos. Este algoritmo, al que hemos llamado CCMM usa técnicas de grafos para evaluar de forma eficiente la compatibilidad entre un conjunto de posibles parejas. En concreto el problema se reduce a la búsqueda de un máximo clique en un grafo donde se utilizan la últimas y más eficientes técnicas para su resolución. Otra innovación que se presenta en este trabajo es un algoritmo hecho a medida para la búsqueda exacta de cliques en los grafos generados por el algoritmo CCMM. Este algoritmo recibe el nombre de BBMCW y utiliza una formulación del problema basada en cadenas de bits a las que se les asigna unos centinelas que marcan el comienzo y el fin del bloque de bits. Estos bloques tienen una estructura semi-dispersa que surge de la forma en que se generan los grafos en el algoritmo CCMM. Se aplica el algoritmo CCMM a la reconstrucción tridimensional de escenas a partir de imágenes monoculares obteniendo una mejora en los resultados y mejorando la estabilidad del algoritmo. En el marco de la reconstrucción tridimensional esta tesis presenta otra innovación en un paso concreto de la reconstrucción. Este paso es la inicialización del algoritmo de optimización que está demostrado ser un paso crítico en la reconstrucción. Este trabajo presenta varias estrategias compararemos con el algoritmo actualmente usado en el estado del arte. La estrategia de ordenado basada en la mínima distancia calculada a lo largo de un grafo creado a partir de los errores ha demostrados mejorar el rendimiento de la estrategia utilizada actualmente por el estado del arte. ABSTRACT The main innovation presented in this thesis is a novel filtering technique for visual feature matching that takes into account multiple hypothesis. This algorithm, named CCMM, uses graph techniques to efficiently evaluate feasibility and joint compatibility of a set of possible matches. Specifically, the problem is reduced to a maximum clique search over an association graph and state-of-the-art algorithms are applied to solve it. Another contribution of this work is the tailoring of an exact clique solver for this application; the new algorithm is denoted BBMCW. BBMCW uses a bitstring formulation with sentinel bits to limit the boundaries of the semi-sparse bit-blocks that arise from the specific structure of the CCMM graphs. The CCMM algorithm is then applied to the Structure from Motion problem. There, it improves the reconstruction results and helps to maintain overall stability. In the context of the Structure from Motion problem, this thesis presents a further contribution concerning the initialization of the bundle adjustment optimization step. In the first place, it shows that initialization is critical for a successful reconstruction of the scene. Moreover, this work also describes several novel strategies for initialization and compares the scene reconstructions with those obtained by known strategies. The reported results show that ordering frames according to the minimum distance to a central point in an error graph improves state-of-the-art bundle adjustment.