Calibra ión débil en paralelo a partir de unase uen ia de imágenes.LCC. Ariel Antonio Bri eño Coronado.aranbri ogmail. om

Maestría en Cien ias Matemáti as.Fa ultad de Matemáti asUniversidad Autónoma de Yu atán2008

ii

De lara ión.En umplimiento de uno de los requisitos para la titula ión en la Maestría en Ma-temáti as de la Universidad Autónoma de Yu atán, dirijo el presente do umento omotesis de Maestría para obtener el grado de Maestro en Cien ias Matemáti as.De laro que esta tesis fue realizada enteramente por mi y des ribe mi propio trabajode investiga ión on ex ep ión de las partes que así se indiquen.

LCC. Ariel Antonio Bri eño CoronadoMérida, Yu atánMéxi o1 de Abril de 2008.iii

iv

Agrade imientos.A Dios, por darme la vida.A mi familia, por ayudarme a vivir y enseñarme las osas buenas de la vida. Gra iastambién por soportarme.A todos los ompañeros de mi vida estudiantil, porque pasé gratos momentos onellos.A mi asesor, el Dr. Arturo Espinosa Romero, por ayudarme on su amistad, expe-rien ia y apoyo para el desarrollo de esta tesis. Es un amigo al que estimo mu hoy siempre atento a sus enseñanzas.Al Dr. Ri ardo Legarda Sáenz, por asesorarme en el desarrollo de esta tesis. Du-rante el tiempo que estuve trabajando on él, fue pasando de ser profesor a ser unamigo uyos omentarios son siempre valorados.Al Dr. Luis Alberto Muñoz Ubando, porque on su amistad mi interés se enfo óal área de visión omputa ional.A los Do tores men ionados un espe ial agrade imiento porque on su llegada aFMAT no tuve la ne esidad de ir lejos de mi lugar de origen para tener ex elentesprofesores y amigos que me ayudaron a ono er los prin ipios de pro esamiento deimágenes y visión omputa ionalA la Fa ultad de Matemáti as de la Universidad Autónoma de Yu atán, porqueen su laboratorio LI2CoV iR se desarrolló la mayor parte de esta tesis.A todas las personas que on sus re omenda iones, hi ieron que la elabora ión deesta tesis, se terminara satisfa toriamente.El trabajo desarrollado en esta tesis fue apoyado por una be a para asistente de investi-ga ión del proye to CONACYT lave SEP-2004-C01-47893, uyo responsable té ni oes el Dr. Arturo Espinosa Romero. v

vi

Resumen.El objetivo prin ipal de esta tesis es ono er las ventajas del enfoque de algoritmosparalelos en visión tridimensional, que usualmente se plantean omo pro edimientosse uen iales. El do umento presenta un estudio a er a de la paraleliza ión de algoritmosde alibra ión débil de imágenes, usando una se uen ia de 2 o más imágenes.Para ada etapa en el pro eso de alibra ión, se analiza las oportunidades de para-leliza ión, se muestran los algoritmos se uen iales, los paralelos y se presentan tambiénlos resultados de las implementa iones así omo las mejoras que se al anzaron y pro-por iona una idea lara de lo que se puede lograr on un enfoque de paraleliza ión enaprove hamiento de la omputadoras a tuales las uales tienen más de dos nú leos depro esamiento.El pro eso que se des ribe a lo largo de este do umento tiene un enfoque modular,i.e., se pueden ambiar de a uerdo a ne esidades, ualquier etapa en el pro eso de ali-bra ión. Gra ias al enfoque modular se tuvo la posibilidad de analizar ada etapa para ono er el omportamiento de los algoritmos paralelos en la arquite tura en la ual seimplementaron.Podemos resumir las fases del pro eso de alibra ión desarrollado en este trabajoen tres etapas prin ipales: dete ión de esquinas, orresponden ia entre las imágenesy depura ión de las orresponden ias. Cada una de las etapas se des ribe de maneraindependiente, pero siempre manteniéndolas dentro del ontexto del objetivo entral.Los resultados mostraron mejoras en el rendimiento on la paraleliza ión de los algo-ritmos implementados y las grá as en los apítulos desde el 3 hasta el 6 lo demuestran.

vii

viii

Índi e generalDe lara ión. iiiAgrade imientos. vResumen. viiÍndi e de guras xivÍndi e de uadros xvLista de algoritmos xvii1. Introdu ión. 11.1. Motiva ión del trabajo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2. Objetivo de la tesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3. Trabajo rela ionado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4. Metodología. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5. A er a de la omputadora paralela. . . . . . . . . . . . . . . . . . . . . . 101.6. Des rip ión del do umento. . . . . . . . . . . . . . . . . . . . . . . . . . 102. Fundamentos. 132.1. Modelos de omputadoras . . . . . . . . . . . . . . . . . . . . . . . . . . 142.1.1. Modelo de máquina se uen ial. . . . . . . . . . . . . . . . . . . . 142.1.2. Modelos de omputadoras paralelas. . . . . . . . . . . . . . . . . 142.1.3. Clasi a ión de omputadoras paralelas. . . . . . . . . . . . . . . 172.2. Lenguajes de programa ión paralela. . . . . . . . . . . . . . . . . . . . . 192.3. ¾Cómo evaluar los algoritmos paralelos? . . . . . . . . . . . . . . . . . . 202.4. Visión geométri a. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.4.1. Geometría epipolar. . . . . . . . . . . . . . . . . . . . . . . . . . 222.4.2. Matriz fundamental. . . . . . . . . . . . . . . . . . . . . . . . . . 232.4.3. Estima ión de la matriz fundamental. . . . . . . . . . . . . . . . 24ix

3. Dete tor de esquinas KLT. 273.1. KLT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.1.1. Algoritmo se uen ial KLT. . . . . . . . . . . . . . . . . . . . . . 293.1.2. Algoritmo paralelo KLT. . . . . . . . . . . . . . . . . . . . . . . . 293.2. Experimentos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3. Dis usión de resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 384. Corresponden ia entre imágenes. 414.1. Estable imiento del problema de orresponden ia. . . . . . . . . . . . . . 414.1.1. Modelos de deforma ión lo al. . . . . . . . . . . . . . . . . . . . . 424.1.2. Transforma ión de los valores de intensidad. . . . . . . . . . . . . 434.1.3. Criterio de Suma de Diferen ias Cuadradas, SSD. . . . . . . . . . 444.1.4. Criterio de Correla ión Cruzada de media Cero Normalizada, ZNCC 454.2. Algoritmo de orresponden ias. . . . . . . . . . . . . . . . . . . . . . . . 464.2.1. Algoritmo se uen ial de orresponden ia. . . . . . . . . . . . . . 464.2.2. Algoritmo paralelo de orresponden ias. . . . . . . . . . . . . . . 494.3. Experimentos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.4. Dis usión de resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 535. Estima ión robusta RANSAC. 555.1. RANSAC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.1.1. Distan ia umbral al modelo. . . . . . . . . . . . . . . . . . . . . . 575.1.2. Número de muestras. . . . . . . . . . . . . . . . . . . . . . . . . . 575.1.3. Tamaño su iente del onjunto onsenso. . . . . . . . . . . . . . 575.1.4. Determina ión del número de muestras adaptativamente. . . . . . 585.2. Paraleliza ión del RANSAC. . . . . . . . . . . . . . . . . . . . . . . . . . 585.2.1. Análisis de Paraleliza ión. . . . . . . . . . . . . . . . . . . . . . . 595.3. Estima ión de la matriz fundamental. . . . . . . . . . . . . . . . . . . . 615.4. Experimentos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.4.1. Experimentos on datos sintéti os. . . . . . . . . . . . . . . . . . 615.5. Experimento on datos reales. . . . . . . . . . . . . . . . . . . . . . . . . 635.6. Dis usión de resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 686. Algoritmo de alibra ión paralelo. 716.1. Se uen ia ordenada de las etapas de alibra ión. . . . . . . . . . . . . . . 716.2. Algoritmo alternativo de alibra ión paralela. . . . . . . . . . . . . . . . 726.2.1. Forma ión de los grupos. . . . . . . . . . . . . . . . . . . . . . . . 746.2.2. Flujo de las imágenes. . . . . . . . . . . . . . . . . . . . . . . . . 756.2.3. Pruebas de alibra ión usando grupos de pro esos. . . . . . . . . 756.3. Dis usión de resultados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 787. Resumen y on lusiones. 837.1. Resumen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83x

A. Modelo de la ámara. 85A.1. Modelo simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85A.2. Calibra ión intrínse a. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87A.3. Matriz de proye ión. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87B. Visión geométri a. 89B.1. Con eptos preliminares. . . . . . . . . . . . . . . . . . . . . . . . . . . . 89B.2. Medidas de distan ias a la matriz fundamental. . . . . . . . . . . . . . . 90B.2.1. Distan ia de Sampson . . . . . . . . . . . . . . . . . . . . . . . . 90B.2.2. Distan ia epipolar simétri a . . . . . . . . . . . . . . . . . . . . . 91Bibliografía 92

xi

xii

Índi e de guras1.1. Des rip ión esquemáti a del servi io de re onstru ión 3D instalado porEPOCH. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.1. Modelo de omputadora de Von Neumann. . . . . . . . . . . . . . . . . . 152.2. Modelo de omputadora paralela on memoria ompartida. . . . . . . . 162.3. Modelo de omputadora paralela on memoria distribuida. . . . . . . . . 172.4. Geometría epipolar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1. División de una imagen para el uso del dete tor de esquinas paralelo KLT 303.2. Grá as de tiempos on el algoritmo paralelo KLT . . . . . . . . . . . . 343.3. Rapidez al anzada del algoritmo paralelo KLT . . . . . . . . . . . . . . . 353.4. E ien ia del algoritmo paralelo KLT . . . . . . . . . . . . . . . . . . . . 363.5. Costo en el algoritmo paralelo KLT . . . . . . . . . . . . . . . . . . . . . 373.6. Esquinas en ontradas on KLT . . . . . . . . . . . . . . . . . . . . . . . 384.1. Deforma ión trasla ional y afín. . . . . . . . . . . . . . . . . . . . . . . . 424.2. Ejemplo de regiones W y Ω para SSD ó ZNCC . . . . . . . . . . . . . . 474.3. Ejemplos del uso de SSD y ZNCC . . . . . . . . . . . . . . . . . . . . . . 484.4. Tiempos de asigna ión de orresponden ias . . . . . . . . . . . . . . . . 514.5. Rapidez del algoritmo de orresponden ia . . . . . . . . . . . . . . . . . 524.6. E ien ia del algoritmo de orresponden ia . . . . . . . . . . . . . . . . 534.7. Costo impli ado en el algoritmo paralelo de orresponden ia . . . . . . . 545.1. Datos sintéti os de prueba para RANSAC . . . . . . . . . . . . . . . . . 625.2. Resultados de la eje u ión de RANSAC on datos sintéti os . . . . . . . 645.3. Grá a de tiempos logrados on el algoritmo paralelo RANSAC . . . . . 655.4. Grá a de rapidez lograda on el algoritmo paralelo RANSAC . . . . . . 665.5. Grá a de e ien ia lograda on el algoritmo paralelo RANSAC . . . . . 685.6. Grá a de osto impli ado on el algoritmo paralelo RANSAC . . . . . . 695.7. Apli a ión de RANSAC de un onjunto de orresponden ias . . . . . . . 706.1. Análisis de alibra ión en onjuntos de imágenes. . . . . . . . . . . . . . 736.2. Forma ión de grupos de trabajo y omuni a ión . . . . . . . . . . . . . . 746.3. Flujo de las imágenes en al algoritmo paralelo alternativo de alibra ión. 776.4. Compara ión entre los dos algoritmos de alibra ión . . . . . . . . . . . 78xiii

6.5. Pro eso de alibra ión. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796.6. Análisis de alibra ión en onjuntos de imágenes. . . . . . . . . . . . . . 81A.1. Hombre dibujando un Lute. . . . . . . . . . . . . . . . . . . . . . . . . . 85A.2. Proye ión perspe tiva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86A.3. Apli a ión de los parámetros internos . . . . . . . . . . . . . . . . . . . . 88

xiv

Índi e de uadros3.1. Tiempos del algoritmo paralelo KLT . . . . . . . . . . . . . . . . . . . . 333.2. Rapidez al anzada en la eje u ión paralela del KLT . . . . . . . . . . . . 353.3. E ien ia del algoritmo paralelo KLT . . . . . . . . . . . . . . . . . . . . 373.4. Costo impli ado en el algoritmo paralelo KLT . . . . . . . . . . . . . . . 384.1. Tiempos de la eje u ión de asigna ión de orresponden ias . . . . . . . . 504.2. Rapidez del algoritmo de orresponden ia . . . . . . . . . . . . . . . . . 514.3. E ien ia obtenida on el algoritmo paralelo de orresponden ias . . . . 524.4. Costo impli ado en el algoritmo paralelo de orresponden ias . . . . . . 535.1. Tiempos del algoritmo paralelo RANSAC . . . . . . . . . . . . . . . . . 655.2. Rapidez del algoritmo paralelo RANSAC . . . . . . . . . . . . . . . . . . 665.3. E ien ia derivada del algoritmo paralelo RANSAC . . . . . . . . . . . . 675.4. Costo impli ado en el algoritmo paralelo RANSAC . . . . . . . . . . . . 686.1. Compara ión de tiempos entre dos algoritmos de alibra ión . . . . . . . 77

xv

xvi

Lista de Algoritmos2.1. Algoritmo de los 8 puntos normalizados. . . . . . . . . . . . . . . . . . . . 253.1. Algoritmo se uen ial del dete tor de esquinas KLT . . . . . . . . . . . . . 293.2. Algoritmo paralelo del dete tor de esquinas KLT . . . . . . . . . . . . . . 324.1. Asigna ión de orresponden ias a partir del mapa de valores . . . . . . . 474.2. Algoritmo de asigna ión de orresponden ias a partir un par de listas deesquinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.3. Algoritmo distribuido de asigna ión de orresponden ias . . . . . . . . . . 495.1. Algoritmo de estima ión robusta RANSAC . . . . . . . . . . . . . . . . . 565.2. Cál ulo adaptativo de las itera iones de RANSAC . . . . . . . . . . . . . 585.3. Algoritmo de estima ión robusta RANSAC on ál ulo adaptativo de lasitera iones N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.4. Algoritmo paralelo RANSAC en una máquina on memoria distribuida . 606.1. Algoritmo de alibra ión. . . . . . . . . . . . . . . . . . . . . . . . . . . . 726.2. Algoritmo de alibra ión empleando grupos de pro esos. . . . . . . . . . . 76

xvii