Memoria (spa) - Universidad De Zaragoza

Transcript

Proyecto Fin de Carrera Dise˜ no de mapas de navegabilidad para entornos de interior mediante visi´ on omnidireccional Jas´on Omedes LLorente Directores: Gonzalo L´opez-Nicol´as Jos´e Jes´ us Guerrero Campo Ingenier´ıa Industrial Automatizaci´ on Industrial y Rob´ otica Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza Junio de 2012 2 Dise˜ no de mapas de navegabilidad para entornos de interior mediante visi´ on omnidireccional RESUMEN En este trabajo se estudia el problema de detectar el suelo y las paredes de una escena a partir de una u ´nica imagen tomada en el interior de un edificio. Aunque existen m´etodos equivalentes que utilizan im´agenes convencionales, las im´agenes omnidireccionales resultan particularmente u ´tiles para esta tarea debido a su amplio campo de vista. No obstante, debido a la mayor complejidad geom´etrica de las im´agenes omnidireccionales es necesario el dise˜ no de algoritmos espec´ıficos. Tambi´en se aborda el problema para el caso de una c´amara en movimiento, que requiere el dise˜ no de t´ecnicas adicionales. El presente PFC se enfoca en cuatro actividades principales: 1. Dise˜ no y evaluaci´on de un nuevo m´etodo para la estimaci´on de los puntos de fuga (VPs) y la clasificaci´on de l´ıneas extra´ıdas sobre im´agenes catadi´optricas. En esta actividad se propone un nuevo m´etodo para clasificar las l´ıneas extra´ıdas de una imagen omnidireccional seg´ un las tres direcciones principales que dominan en la escena y se realiza una comparativa con los m´etodos ya existentes. 2. Desarrollo de un m´etodo innovador para obtener la estructura principal de una escena de interiores a partir de una u ´nica imagen omnidireccional. Este m´etodo propuesto utiliza la informaci´on extra´ıda a partir de las l´ıneas y los puntos de fuga, que combinados con un conjunto de restricciones geom´etricas, nos permiten segmentar en la imagen las regiones que forman parte del suelo y las paredes verticales sobre las direcciones principales. 3. Propagaci´on secuencial de la aplicaci´on propuesta sobre im´agenes pr´oximas para aumentar la robustez del resultado con una c´amara en movimiento. Se propone una extensi´on del m´etodo para mejorar la estimaci´on final mediante el uso de homograf´ıas que permiten propagar las hip´otesis resultantes secuencialmente eliminando posibles errores en la clasificaci´on. 4. Obtenci´on de resultados. Las t´ecnicas desarrolladas se han evaluado experimentalmente con im´agenes reales obtenidas de una base de datos disponible en internet. Los resultados experimentales demuestran el buen funcionamiento y la robustez del m´etodo propuesto. 3 4 ´Indice general 1. Introducci´ on 1.1. Marco de trabajo . . . . 1.2. Estado del arte . . . . . 1.3. Objetivos . . . . . . . . 1.4. Estructura de contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 10 13 14 2. El modelo de la esfera 17 2.1. Proyecci´on de una recta . . . . . . . . . . . . . . . . . . . . . . . . 21 3. Extracci´ on y clasificaci´ on de c´ onicas 3.1. Clasificaci´on sobre imagen catadi´optrica 3.1.1. C´alculo de c´onicas . . . . . . . . 3.1.2. C´alculo de los puntos de fuga . . 3.2. Clasificaci´on sobre la esfera . . . . . . . 3.2.1. C´alculo de c´onicas . . . . . . . . 3.2.2. C´alculo de los puntos de fuga . . 3.3. M´etodo propuesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Obtenci´ on de la distribuci´ on espacial de una escena 4.1. M´etodo jer´arquico de generaci´on de hip´otesis . . . . . . 4.1.1. Selecci´on de puntos clave . . . . . . . . . . . . 4.1.2. Hip´otesis inicial del contorno central . . . . . . 4.1.3. Proceso jer´arquico para generaci´on de hip´otesis 5. Aplicaci´ on secuencial mediante homograf´ıas 5.1. Homograf´ıa . . . . . . . . . . . . . . . . . . 5.1.1. Homograf´ıa a partir de l´ıneas . . . . 5.2. Selecci´on de emparejamientos . . . . . . . . 5.2.1. Emparejamiento de puntos . . . . . 5.2.2. Emparejamiento de l´ıneas . . . . . . 5.3. Medida de similitud . . . . . . . . . . . . . . 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 25 25 25 27 27 27 29 . . . . 33 34 34 36 39 . . . . . . 45 45 47 48 49 50 53 ´INDICE GENERAL 6 5.4. Hip´otesis ponderada . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5. Propagaci´on de hip´otesis . . . . . . . . . . . . . . . . . . . . . . . . 55 57 6. Experimentos 59 6.1. Evaluaci´on del nuevo m´etodo para clasificaci´on de l´ıneas . . . . . . 60 6.2. Evaluaci´on de la recuperaci´on estructural con una imagen . . . . . . 60 6.3. Evaluaci´on del m´etodo mediante aplicaci´on de homograf´ıas . . . . . 63 7. Conclusiones 67 Anexos 71 A. Geometr´ıa de la hip´ erbola 73 A.1. Definici´on geom´etrica de la hip´erbola . . . . . . . . . . . . . . . . . 73 A.2. Ecuaci´on expl´ıcita de la hip´erbola . . . . . . . . . . . . . . . . . . . 74 A.3. Definici´on de semi-latus-rectum . . . . . . . . . . . . . . . . . . . . 75 B. El sistema hipercatadi´ optrico como sistema central B.1. Ley de reflexi´on . . . . . . . . . . . . . . . . . . . . . B.2. Soluci´on para espejo hiperb´olico . . . . . . . . . . . . B.2.1. C´alculo del vector normal . . . . . . . . . . . B.2.2. Demostraci´on de sistema catadi´optrico central . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 80 81 81 82 C. Modelo de proyecci´ on para un sistema central hiperb´ olico 83 C.1. Proyecci´on de un punto sobre el hiperboloide de revoluci´on . . . . . 83 C.2. Proyecci´on de x en la c´amara perspectiva . . . . . . . . . . . . . . 85 D. Conceptos fundamentales de geometr´ıa para l´ıneas c´ onicas 89 D.1. Ajuste de una c´onica en el N-plano a partir de dos puntos y la calibraci´on interna . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 D.1.1. Caso general . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 D.1.2. Configuraci´on singular . . . . . . . . . . . . . . . . . . . . . 92 D.2. Distancia de un punto a una c´onica . . . . . . . . . . . . . . . . . . 94 D.2.1. Distancia algebraica . . . . . . . . . . . . . . . . . . . . . . 94 D.2.2. Distancia basada en el gradiente . . . . . . . . . . . . . . . . 94 D.2.3. Distancia basada en la l´ınea polar . . . . . . . . . . . . . . . 96 D.2.4. Discusi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 D.3. Intersecci´on de c´onicas . . . . . . . . . . . . . . . . . . . . . . . . . 98 D.3.1. El tri´angulo autopolar com´ un a dos c´onicas . . . . . . . . . 98 D.3.2. Intersecci´on de dos c´onicas usando el tri´angulo autopolar . . 100 ´INDICE GENERAL 7 E. Descriptor SIFT E.1. Construcci´on de un espacio de Escalas . . . . . . E.1.1. Diferencia de gaussianas: D(x, y, σ) . . . . E.1.2. Detecci´on de extremos locales . . . . . . . E.2. Localizaci´on de keypoints . . . . . . . . . . . . . E.2.1. Supresi´on de puntos de bajo contraste . . E.2.2. Supresi´on de puntos situados en los bordes E.3. Asignaci´on de orientaci´on . . . . . . . . . . . . . E.4. Descriptor de puntos claves . . . . . . . . . . . . F. Ampliaci´ on de Resultados F.1. Resultados en corredores . . . . F.2. Resultados en pasillos complejos F.3. Resultados en habitaciones . . . F.4. Resultados con fallos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 . 114 . 115 . 116 . 117 G. Manual de usuario H. Art´ıculo IAS 2012 H.1. Introduction . . . . . . . . . . . . . . . . H.2. Vanishing Point Estimation through Line H.3. Hierarchical Layout Hypothesis Method . H.3.1. Selection of Set of Points . . . . . H.3.2. Generation of Conics . . . . . . . H.3.3. Initial Boundaries Hypothesis . . H.3.4. Hierarchical Expansion Process . H.4. Results . . . . . . . . . . . . . . . . . . . H.5. Conclusion and Future Work . . . . . . . 103 103 105 105 107 107 107 109 110 . . . . . . . . 119 . . . . . . Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 124 125 126 127 127 128 129 131 132 ´Indice de figuras 135 ´Indice de tablas 141 Bibliograf´ıa 143 8 ´INDICE GENERAL Secci´ on 1 Introducci´ on 1.1. Marco de trabajo La obtenci´on de la distribuci´on estructural de la escena a partir de una imagen es una tarea sencilla para cualquier persona, sin embargo, no es f´acil para un sistema de inteligencia artificial. Al mismo tiempo, es una herramienta muy potente, ya que conocer los l´ımites entre suelo y paredes proporciona informaci´on valiosa en tareas de navegaci´on aut´onoma, detecci´on de obst´aculos o reconstrucci´on 3D. En concreto, este trabajo se enmarca dentro del proyecto de investigaci´on VISPA (Non-conventional Vision Systems for Personal Assistance) del grupo de rob´otica de la Universidad de Zaragoza, que tiene como objetivo el desarrollo de t´ecnicas de visi´on por computador combinadas con metodolog´ıas del campo de la rob´otica para formar parte de un sistema de asistencia personal. Parte de la informaci´on visual incluye informaci´on tomada por c´amaras no convencionales, como en este caso un sistema catadi´optrico formado por una c´amara y un espejo (figura 1.1). Se busca encontrar un sistema que pueda ser transportado por una persona y que sirva para complementar, m´as que reemplazar capacidades humanas, para ayudar a personas con discapacidad en su sistema cognitivo visual, personas con dificultad de orientaci´on o personas sin discapacidad que se mueven sobre entornos desconocidos o que requieran una ayuda extra a la hora de desempe˜ nar ciertas tareas. Las im´agenes omnidireccionales tienen grandes ventajas en este entorno debido a su amplio campo de vista que permite recopilar informaci´on de todas las direcciones y es de gran utilidad a la hora de detectar obst´aculos. 9 10 1.2. Estado del arte Figura 1.1: Casco con c´amara omnidireccional para tareas de asistencia personal. 1.2. Estado del arte El problema de obtener la distribuci´on estructural ha sido estudiado en distintas ocasiones y continua atrayendo los esfuerzos de muchos investigadores (Fig. 1.2). La mayor´ıa de las contribuciones funcionan bajo la hip´otesis de un mundo tipo Manhattan [11], que asume que la escena tiene 3 direcciones principales ortogonales entre s´ı. Los entornos de interior normalmente satisfacen esta condici´on por lo que se entiende la aplicaci´on extensiva de esta hip´otesis. Algunos ejemplos son [18], que utiliza l´ıneas extra´ıdas a partir de c´amaras perspectivas y a las que aplica condiciones geom´etricas para buscar el mejor ajuste al entorno, o [17] que representando las habitaciones como cubos en 3D intenta reconocer los l´ımites entre pared y suelo en habitaciones llenas de objetos. Tambi´en se encuentran otros trabajos como [25] que usa filtros bayesianos sobre un conjunto de hip´otesis paredsuelo sin la asunci´on de un mundo tipo Manhattan, aunque en este caso, sigue habiendo 3 direcciones principales pero a las que no se les impone la condici´on de ortogonalidad. En los u ´ltimos a˜ nos, el uso de c´amaras omnidireccionales se ha consolidado en aplicaciones de rob´otica. El motivo de ello es que muchos de los problemas de visi´on artificial aplicada a la rob´otica se ven fuertemente condicionados por el campo de vista. Las c´amaras convencionales trabajan con campos de vista que oscilan entre los 40 - 60o y el modelo anal´ıtico de c´amara proyectiva tiene su l´ımite te´orico en 180o . Buscando superar esta limitaci´on se han desarrollado recientemente diversos sistemas que permiten abarcar ´angulos de 360o . Desde el punto de vista constructivo existen diversos tipos de c´amaras omnidireccionales. 1. Introducci´ on 11 Figura 1.2: Recuperaci´on estructural de una escena en im´agenes convencionales [25]. Resultado etiquetado manualmente. Uno de ellos es la c´amara rotatoria, que consiste en una c´amara convencional con un sistema mec´anico que permite el movimiento a lo largo de una trayectoria circular tomando una imagen de toda la escena. Otra configuraci´on de c´amara omnidireccional consiste en un conjunto de c´amaras convencionales situadas con una orientaci´on adecuada para abarcar el mayor campo de vista posible. Los sistemas di´optricos, que son c´amaras convencionales con lentes de granangular, como la lente de ojo de pez. La clase de c´amaras omnidireccionales a la que prestaremos especial atenci´on es la que engloba a los sistemas catadi´optricos. Este tipo de sistemas combinan c´amaras convencionales con espejos. Los sistemas catadi´optricos han sido estudiados por Baker y Nayar [1] quienes demostraron que los espejos el´ıpticos, parab´olicos e hiperb´olicos son los u ´nicos que pueden ser combinados con c´amaras convencionales constituyendo sistemas catadi´optricos centrales (SCC). Esta propiedad relaciona los rayos incidentes en un sistema catadi´optrico central de manera un´ıvoca con los puntos de la imagen tomada por el sistema. Los sistemas catadi´optricos m´as usuales son el hiper-catadi´optrico, compuesto de un espejo hiperb´olico y una c´amara perspectiva y el para-catadi´optrico formado por un espejo parab´olico y una c´amara ortogr´afica. Estos sistemas, construidos bajo las restricciones geom´etricas correspondientes, se comportan como sistemas catadi´optricos centrales (Fig. 1.3). El uso de estos sistemas puede verse en aplicaciones como la localizaci´on, realidad virtual, navegaci´on, SLAM, reconstrucci´on 3D, odometr´ıa visual, etc. 12 1.2. Estado del arte

 
      
    


  

  
  
 
 
  
    
       
   Figura 1.3: Ejemplo de sistema catadi´optrico central con espejo hiperb´olico. El primer foco, F1, est´a situado dentro del espejo, y el segundo foco, F2, coincide con el centro o´ptico dentro de la lente. Para cualquiera de estas aplicaciones, y especialmente en las de rob´otica es necesario recoger informaci´on m´etrica del entorno. Esta informaci´on depende directamente de la calibraci´on del sistema y de su modelo de proyecci´on. Existen diversos modelos, tanto geom´etricos como anal´ıticos, que consideran la proyecci´on de sistemas catadi´optricos. Geyer y Daniilidis [13] proponen un modelo unificado capaz de modelar la proyecci´on de cualquier sistema catadi´optrico central. Este modelo fue extendido por Barreto y Araujo [3] y es conocido como el Modelo de la Esfera. En la actualidad es el modelo m´as utilizado. 1. Introducci´ on 1.3. 13 Objetivos Para este trabajo, el uso de c´amaras omnidireccionales es muy importante debido al amplio campo de vista, lo que ayuda a una mejor detecci´on de los puntos de fuga y permite observar una mayor longitud de las rectas de la escena. Por otro lado, en los sistemas catadi´optricos centrales, las l´ıneas rectas de la escena se proyectan como c´onicas sobre la imagen, incrementando la complejidad geom´etrica, de forma que la mayor´ıa de los algoritmos existentes para c´amaras convencionales no puedan aplicarse. Por ello es necesario el desarrollo de nuevos m´etodos que tengan en cuenta las caracter´ısticas de este tipo de im´agenes (figura 1.4). Partiendo del trabajo [23], proponemos un nuevo m´etodo escena, m´as robusto ya que no depende de encontrar esquinas (que son dif´ıciles de detectar), y mucho m´as r´apido, debido a que los m´etodos de clasificaci´on o combinaci´on de esquinas para formar la hip´otesis de suelo consum´ıan mucho tiempo. El trabajo propuesto para la recuperaci´on estructural utiliza de partida una u ´nica imagen omnidireccional, de la que se extraen l´ıneas caracter´ısticas, y se clasifican en tres direcciones principales dependiendo de su orientaci´on. Estas l´ıneas contienen informaci´on redundante por lo que seleccionamos u ´nicamente un conjunto de puntos que posteriormente permiten generar una primera hip´otesis de la forma de la escena considerando que esta tiene 4 paredes, para despu´es expandir (o no) esta habitaci´on hip´otesis de acuerdo a la distribuci´on de los datos. Finalmente, se aplica un proceso secuencial basado en homograf´ıas de forma que las distintas hip´otesis de im´agenes consecutivas compartan informaci´on entre s´ı consiguiendo resultados m´as homog´eneos y precisos. Figura 1.4: Comparaci´on entre imagen tomada por una c´amara convencional y una c´amara omnidireccional donde se pueden observar las caracter´ısticas definidas en la literatura. Ambas fotos tomadas en la plaza de las Ingenier´ıas, que separa el edificio Torres Quevedo y el edificio Betancourt. 14 1.4. 1.4. Estructura de contenidos Estructura de contenidos Tras esta introducci´on, la estructura del presente proyecto es la siguiente: en el cap´ıtulo 2 se introduce el modelo proyectivo de la esfera, cuyos conceptos tienen gran importancia en el desarrollo del resto del proyecto. Los tres siguientes cap´ıtulos contienen la principal aportaci´on del trabajo, y un esquema gr´afico de los distintos pasos puede observarse en la figura 1.5. El cap´ıtulo 3 se centra en el dise˜ no de un nuevo m´etodo de extracci´on y clasificaci´on de las l´ıneas extra´ıdas de una imagen catadi´optrica con la obtenci´on de sus respectivos puntos de fuga y se compara con dos de los m´etodos existentes en la literatura. En el cap´ıtulo 4 se presenta un m´etodo innovador que utiliza la informaci´on de las l´ıneas clasificadas en el cap´ıtulo anterior para generar una hip´otesis del contorno del suelo y las paredes de la escena observadas en la imagen. Esta hip´otesis se ve mejorada mediante un proceso secuencial basado en homograf´ıas, explicado en el cap´ıtulo 5, que busca conseguir resultados m´as robustos y homog´eneos. Los resultados para los tres principales cap´ıtulos de este proyecto ( 3, 4 y 5) son presentados en el cap´ıtulo 6. Por u ´ltimo, en el cap´ıtulo 7 se exponen las conclusiones obtenidas del proyecto as´ı como l´ıneas futuras de investigaci´on sobre este tema. 1. Introducci´ on 15 Figura 1.5: Esquema de las etapas principales del algoritmo desarrollado junto a los procesos m´as importantes de cada una. 16 1.4. Estructura de contenidos Secci´ on 2 El modelo de la esfera El modelo de la esfera es un modelo geom´etrico abstracto que unifica la geometr´ıa de proyecci´on caracter´ıstica de los sistemas catadi´optricos centrales, que relacionan puntos de la escena con puntos en la imagen. Estos sistemas est´an formados por la combinaci´on entre espejos y c´amaras convencionales, donde las caracter´ısticas geom´etricas del espejo vienen reflejadas en los par´ametros ξ y ψ como se indica en la tabla 2.1 . Concretamente el tipo de sistema viene determinado por el par´ametro del espejo ξ. Donde ξ = 0 para c´amara perspectiva, ξ = 1 para c´amara para-catadi´optrica, 0 < ξ < 1 para hiper-catadi´optrica y ξ < 0 cuando se modela un sistema con distorsi´on radial. El sistema de referencia de este modelo toma como origen de coordenadas O el origen del sistema catadi´optrico central que se est´a modelando, cuya posici´on var´ıa dependiendo del tipo de sistema utilizado. En el caso de un sistema hipercatadi´optrico, el origen de coordenadas O se sit´ ua en uno de los focos de la hip´erbola generatriz, en el caso de el sistema para-catadi´optrico corresponde al foco de la par´abola y en el caso de sistema perspectivo coincide con el centro ´optico de la c´amara. ˆ sobre la La proyecci´on de un punto gen´erico del entorno Xw en un punto x imagen catadi´optrica, se explica mediante un proceso de tres pasos. Siendo Xw un punto del entorno expresado en coordenadas homog´eneas Xw = (Xw , Yw , Zw , 1) respecto a un sistema de referencia absoluto, se le puede asociar un rayo proyectivo x en el sistema de referencia de la c´amara mediante la matriz de proyecci´on P x = PXw = R[I| − C0 ]Xw (2.1) donde R y CO representan la rotaci´on y el desplazamiento del sistema de coordenadas del modelo con respecto al sistema de coordenadas absolutas. 17 18 Espejo parab´olico Espejo hiperb´olico Espejo el´ıptico ξ 1 ψ 1 + 2p √d+2p √ d d2 +4p2 √ d d2 +4p2 d2 +4p2 d−2p √ d2 +4p2 Espejo plano 0 d: distancia entre focos 4p:latus rectum 1 Tabla 2.1: Par´ametros del espejo para el modelo de la esfera Para simplificar, y sin perdida de generalidad, asumiremos que el modelo catadi´optrico y el sistema de coordenadas absolutas es el mismo por lo que P = [I|0], de forma que el rayo proyectivo resultante es el resultado de unir el punto Xw con el origen de coordenadas O.      
 
  
  Figura 2.1: Modelo de la Esfera para sistemas catadi´optricos. Sea S la esfera de radio unidad centrada en el origen de coordenadas O, se calcula la proyecci´on del rayo x sobre la esfera como la intersecci´on de ambos en dos puntos x+ y x− , de los cuales solo uno es f´ısicamente coherente. Estos puntos son proyectados sobre un plano de proyecci´on virtual π (denominado n-plano), a trav´es del centro ´optico virtual Cp = (0, 0, −ξ)T , 2. El modelo de la esfera 19 obteniendo los puntos x ¯+ y x ¯− . Si solo tenemos en cuenta la soluci´on f´ısicamente coherente, esto se puede resumir en aplicar la funci´on no lineal  sobre el rayo proyectivo x. x ¯ = (x) (2.2) ⎞ x ⎠ (x) = ⎝  y 2 2 2 z+ξ x +y +z (2.3) ⎛ (N´otese que al trabajar con ecuaciones homog´eneas la expresi´ on presentada es  t y y x equivalente a (x) = √x2 +y2 +z2 √x2 +y2 +z2 √x2 +y2 +z2 + ξ que es la que se deduce de proyectar la intersecci´on de la esfera a trav´es del centro ´optico Cp ). El tercer y u ´ltimo paso consiste en aplicar la transformaci´on lineal Hc para proyectar el plano virtual π que contiene el punto x ¯ al plano πIM , para as´ı obtener el punto final x ˆ en coordenadas de la imagen catadi´optrica. ⎛ x ˆ = Hc x ¯ (2.4) Hc = Kc Rc Mc (2.5) ψ−ξ 0 ⎝ 0 ξ−ψ Mc = 0 0 ⎛ fx ⎝ 0 Kc = 0 ⎞ ⎛ ⎞ 0 −η 0 0 0 ⎠=⎝ 0 η 0 ⎠ 1 0 0 1 ⎞ sskew u0 fy v0 ⎠ 0 1 (2.6) (2.7) donde Kc contiene los par´ametros intr´ınsecos de la calibraci´on de la c´amara perspectiva: fx = f /k y fy = f /l son el resultado de dividir la distancia focal de la c´amara (f ) entre las dimensiones de un pixel (k × l) respectivamente, u0 y v0 indican las coordenadas del centro de la imagen, y sskew es la desviaci´on de los ejes, habitualmente cero. Rc representa la orientaci´on de la c´amara respecto al espejo, y Mc incluye los par´ametros del espejo ξ y ψ, que en la pr´actica se sustituyen por un u ´nico par´ametro η. En la mayor´ıa de los casos se puede asumir que la c´amara y el espejo est´an 20 alineados (Rc = I) y la matriz de ⎛ −ηfx ⎝ 0 Hc = 0 transformaci´on, se puede expresar: ⎞ ⎛ ⎞ 0 u0 γ x 0 u0 ηfy v0 ⎠ = ⎝ 0 γy v0 ⎠ 0 1 0 0 1 (2.8) En el que γx = −ηfx y γy = ηfy son las distancias focales generalizadas del sistema catadi´optrico completo (espejo m´as c´amara). Hay que tener en cuenta que la calibraci´on de los sistemas catadi´optricos se suele determinar como un conjunto y por tanto el par´ametro η no se determina expl´ıcitamente, sino que est´a impl´ıcito dentro de las distancias focales generalizadas. Una vez obtenido el punto x ˆ = (ˆ x, yˆ, zˆ)T , la relaci´on entre ´este y las coordenadas Eucl´ıdeas de la imagen (u, v) se calcula dividiendo el vector entre la tercera componente. yˆ xˆ v= zˆ zˆ Igual que hemos realizado la proyecci´on de un punto del entorno en la imagen, se puede realizar el proceso inverso, con la limitaci´on de que se pierde la informaci´on de profundidad, por lo que la proyecci´on de un punto de la imagen catadi´optrico se corresponde a un rayo del entorno. Esta relaci´on inversa se lleva a cabo multiplicando por la inversa de la matriz Hc y por la funci´on no lineal definida en la ecuaci´on 2.9 que proyecta los puntos pertenecientes al plano π en un rayo orientado. ⎛ ⎞ √ z¯ξ+ z¯2 +(1−ξ 2 )(¯ x2 +¯ y2 ) x¯ ⎟ ⎜ √ x¯22 +¯y2 +¯2z2 2 2 ⎜ ⎟ )(¯ x +¯ y ) (2.9) −1 (¯ x) = ⎜ z¯ξ+ z¯ +(1−ξ ⎟ y ¯ 2 2 2 ⎝ ⎠ √ 2 x¯ +¯y2 +¯z2 2 z¯ξ+ z¯ +(1−ξ )(¯ x +¯ y ) z¯ − ξ x ¯2 +¯ y 2 +¯ z2 u= Ambos procesos, directo e inverso, pueden resumirse con el siguiente esquema (figura 2.2):
  
 

     
 
 
       
        
 Figura 2.2: Pasos de la proyecci´on del Modelo de la Esfera. 2. El modelo de la esfera 2.1. 21 Proyecci´ on de una recta En este apartado se presenta la aplicaci´on del modelo de la esfera a la proyecci´on de l´ıneas de la escena sobre la imagen catadi´optrica. Una recta r, en el espacio 3D, est´a formada por un conjunto infinito de puntos alineados. Por lo que proyectar una recta ser´ıa el equivalente de proyectar cada uno de los puntos que la compone. Cada uno de estos puntos tiene asociado un rayo proyectivo que cruza por el origen de coordenadas del sistema catadi´optrico central O. Sea Π el plano definido por la recta r y el origen de coordenadas del sistema catadi´optrico central O (punto de vista efectivo), que contiene los rayos proyectivos asociados a cada punto de la recta y descrito en coordenadas homog´eneas absolutas como Π = (nx , ny , nz , 0)T . Asumiendo una vez m´as que el sistema de coordenadas absolutas y el del sistema catadi´optrico coincide, por lo que P = [I| 0], entonces el plano Π puede representarse como n = PΠ = (nx , ny , nz )T . Obs´ervese que al igual que la recta r est´a contenida en el plano Π, existe otro infinito n´ umero de rectas que pueden pertenecer a este plano y debido a esto, tendr´an la misma proyecci´on en una imagen. El c´ırculo formado por la intersecci´on del plano Π y la esfera recibe el nombre de gran c´ırculo. 
   

   

 Figura 2.3: Proyecci´on de una recta mediante el modelo de la esfera. Los puntos de la escena Xw , pertenecientes a la recta r, son representados como puntos x, pertenecientes al gran c´ırculo, y satisfacen nT x = 0. Como vimos x) entonces nT −1 (¯ x) = 0. Desarrollando esta expresi´on anteriormente, x = −1 (¯ ¯ x = 0 siendo Ω ¯ se llega a una igualdad que puede expresarse de la forma x ¯T Ω¯ la expresi´on matricial homog´enea de la c´onica sobre el plano gen´erico virtual π 22 2.1. Proyecci´ on de una recta situado a una distancia unidad del origen de coordenadas O. ⎞ ⎛ 2 nx ny (1 − ξ 2 ) nx nz nx (1 − ξ 2 ) − n2z ξ 2 ¯ = ⎝ nx ny (1 − ξ 2 ) n2y (1 − ξ 2 ) − n2z ξ 2 ny nz ⎠ Ω nx nz ny nz n2z (2.10) Este proceso puede ser explicado de forma geom´etrica como la proyecci´on de los puntos pertenecientes al gran c´ırculo, formado por la intersecci´on entre el plano Π y la esfera, a trav´es del centro ´optico virtual Cp . Esta proyecci´on forma un cono ¯ que coincide con la definida en que corta al plano virtual π en una l´ınea c´onica Ω la ecuaci´on 2.10. ˆ que Por u ´ltimo se aplica la transformaci´on lineal Hc para obtener la c´onica Ω es la proyecci´on de la linea r sobre la imagen catadi´optrica. ¯ −1 ˆ = H−T Ω c ΩHc (2.11) De la misma manera se puede aplicar el proceso inverso que proyecta las l´ıneas c´onicas de la imagen de vuelta a la esfera, proceso muy u ´til en el resto de cap´ıtulos de este proyecto, tanto como para la clasificaci´on de c´onicas del cap´ıtulo 3 como para hacer operaciones entre ´estas a partir de sus vectores normales que las definen en el modelo de la esfera. Secci´ on 3 Extracci´ on c´ onicas y clasificaci´ on de El primer paso para empezar a trabajar con im´agenes, es decidir con qu´e tipo de informaci´on nos interesa trabajar y c´omo podemos realizar su extracci´on para aplicarla en otros procesos. Nuestro objetivo final es saber distinguir qu´e partes de la imagen son suelo y cu´ales son paredes, y al igual que en la mayor´ıa de los algoritmos desarrollados para im´agenes convencionales, la mejor forma de realizar esta tarea es mediante la extracci´on y clasificaci´on de l´ıneas de la imagen. Extracci´ on El problema de extracci´on de l´ıneas ya est´a estudiado y existen varios m´etodos para su aplicaci´on. Aunque los resultados obtenidos por los distintos m´etodos son muy parecidos, en este trabajo se har´a uso del denominado Canny Edge Detector [10] que presenta un buen comportamiento frente a la detecci´on de trazos conectados. Posteriormente a la aplicaci´on de este detector de l´ıneas sobre la imagen de entrada se emplea una m´ascara que elimina las partes de la foto que carecen de informaci´on. Dichas zonas son el centro de la imagen donde se encuentra reflejado el objetivo de la c´amara, y las zonas que caen fuera del alcance del espejo y aparecen en negro. Una vez hecho esto, los diferentes trazos conectados se guardan como componentes que luego ser´an procesados. 23 24 Clasificaci´ on Hay que notar que, como ya se mencion´o en la secci´on 2, las l´ıneas rectas de la escena son representadas por l´ıneas c´onicas en la imagen catadi´optrica, a excepci´on de las c´onicas degeneradas en rectas que aparecen en forma de l´ıneas radiales cruzando por el centro de la imagen. El objetivo ahora es ser capaz de detectar estas c´onicas y de clasificarlas seg´ un su orientaci´on relativa, es decir, reconocer si son l´ıneas verticales u horizontales de la escena y en que direcci´on est´an situadas. En lo referente a visi´on omnidireccional dos m´etodos para realizar esta tarea son seguir trabajando sobre la imagen catadi´optrica [8] o proyectar las l´ıneas extra´ıdas sobre la esfera unitaria [4] del modelo propuesto en el cap´ıtulo 2. A continuaci´on se explican las diferencias entre los distintos m´etodos. Los algoritmos est´an disponibles como c´odigo abierto y programados en Matlab. Para poder hacer una comparaci´on justa entre ambos vamos a trabajar con im´agenes de la base de datos COGN IRON [26], a la cual tambi´en se puede acceder de forma libre, de la misma manera que a la calibraci´on del sistema catadi´optrico utilizado para la toma de estas im´agenes. En este caso el sistema est´a compuesto por una c´amara perspectiva con una resoluci´on de 1024 × 768 p´ıxeles y un espejo convexo hiperb´olico cuyos par´ametros geom´etricos aportados por el fabricante son de a=42.088 b=25.0911 y de 61 mm de di´ametro exterior. El par´ametro del espejo seg´ un el modelo de la esfera es ξ = 0,9337. 1 Ver detalles en Anexo A 3. Extracci´ on y clasificaci´ on de c´ onicas 3.1. 25 Clasificaci´ on sobre imagen catadi´ optrica Para ser capaces de definir una l´ınea c´onica necesitamos 5 puntos que la definan, y si estos puntos no est´an bien distribuidos a lo largo de toda la curva, la estimaci´on puede no ser correcta. En [9] se demuestra como si se dispone de los par´ametros de calibraci´on del sistema, s´olo dos puntos son necesarios para ser capaces de computar estas l´ıneas. 3.1.1. C´ alculo de c´ onicas Usando la t´ecnica de dos puntos, se propone un m´etodo robusto que mediante la aplicaci´on de RANSAC [16] (RANdom SAmple Consensus), plantea la extracci´on del mayor n´ umero de c´onicas correspondientes a segmentos rectos de la escena. Para ello, a cada uno de los componentes (grupos de puntos conectados), se le aplican los siguientes pasos: 1. Entre los puntos que forman el componente, se seleccionan dos aleatoriamente a partir de los cuales se genera una c´onica. 2. A continuaci´on, se mide la distancia entre la c´onica generada y el resto de los puntos pertenecientes al grupo. Los puntos cuya distancia es menor a un umbral de decisi´on votan por esta c´onica. Este proceso se repite un n´ umero de veces determinado estad´ısticamente, y al terminar se selecciona la c´onica con mayor n´ umero de votos. 3. Se aplican de nuevo los pasos anteriores a los puntos que no han votado a la c´onica seleccionada para detectar una nueva c´onica. Y se repite este proceso hasta que el n´ umero de puntos que no votan por ninguna de las c´onicas seleccionadas es menor a un umbral. 3.1.2. C´ alculo de los puntos de fuga Una vez se han extra´ıdo las c´onicas que definen los tramos rectos de la escena se procede al an´alisis de los puntos de fuga de estas c´onicas, los cuales facilitaran la futura clasificaci´on. El punto de fuga es el lugar geom´etrico en el que las rectas paralelas en una direcci´on dada convergen. En im´agenes convencionales, es un punto impropio situado en el infinito. Sin embargo, cuando trabajamos con im´agenes catadi´optricas, las rectas se transforman en c´onicas y estas c´onicas se cortan entre s´ı en uno o dos puntos dentro de la imagen. Dada esta propiedad, si encontramos 26 3.1. Clasificaci´ on sobre imagen catadi´ optrica los puntos donde varias c´onicas intersectan, podremos deducir el paralelismo entre los distintos segmentos de la imagen. Supongamos que m es el n´ umero de c´onicas detectadas en la imagen omnidireccional, y que ni es la normal que las representa en el plano normalizado. Para cada par de c´onicas nj , nk (siendo un total de m(m − 1)/2 pares), se calcula la intersecci´on entre ellas 2 . Y luego para cada una de las l´ıneas restantes ni calculamos su distancia a los puntos de corte formados por nj y nk . Si la l´ınea ni es paralela al par de c´onicas, la distancia a los puntos ser´a inferior a un umbral y entonces la l´ınea ni vota al posible punto de fuga formado por el corte entre nj , nk . Los puntos de fuga m´as votados son considerados como direcciones dominantes, y las l´ıneas se clasifican en funci´on a su distancia a ellos (figura 3.1). El caso general para entornos de interior es encontrar 3 puntos de fuga. Uno central correspondiente a la direcci´on vertical, y otros dos pares de puntos que representan una direccional horizontal cada par. (a) (b) Figura 3.1: Resultados de Clasificaci´on sobre la Imagen: (a) Componentes conectados (colores vivos) junto a las c´onicas que los aproximan (azul). (b) Clasificaci´on de los elementos conectados seg´ un direcciones principales. En este caso se detectan 4, pero u ´nicamente tres son representativas: Verticales(azul), Horizontales en X (rojo), Horizontales en Y (verdes). 2 Explicado en profundidad en el Anexo D 3. Extracci´ on y clasificaci´ on de c´ onicas 3.2. 27 Clasificaci´ on sobre la esfera En este otro modelo se trabaja sobre la esfera unitaria. El primer paso es utilizar el proceso inverso de proyecci´on para llevar todos los componentes (grupos de puntos conectados) detectados en la imagen catadi´optrica a la esfera. 3.2.1. C´ alculo de c´ onicas Sean P1i = (X1i , Y1i , Z1i ) y PNi = (XNi , YNi , ZNi ) los puntos situados en los extremos de un componente de N p´ıxeles, estos dos puntos definen un gran c´ırculo  1 × OP  N siendo O el centro de la esfera. Se representado por su normal ni = OP considera que un punto Psi = (Xsi , Ysi , Zsi ) de esta cadena de puntos pertenece al gran c´ırculo de normal ni si:   (Xsi , Ysi , Zsi ) · ni  ≤ U mbralSeparacion (3.1) Si el 95 % de los p´ıxeles de el componente pertenecen al gran c´ırculo, entonces el conjunto de puntos completo es considerado una c´onica, equivalente a un segmento recto de la escena. En caso contrario, dividimos el componente en dos subgrupos en el punto donde:   arg max (Xsi , Ysi , Zsi ) · ni  (3.2) si Este proceso de separaci´on termina cuando todos los trozos en los que se divide el componente pertenecen a una l´ınea, o cuando la longitud de los trozos son inferiores a determinada n´ umero de p´ıxeles. 3.2.2. C´ alculo de los puntos de fuga Como ya se coment´o, los puntos de fuga en la imagen catadi´optrica son el lugar geom´etrico donde dos o m´as c´onicas intersectan. Similarmente, en la esfera dos c´onicas son representadas por dos grandes c´ırculos y estos cortan entre s´ı en dos puntos ant´ıpodos de la esfera. Estos dos puntos corresponden a la direcci´on de los puntos de fuga y los caracterizaremos por el vector u. Llamemos n1 y n2 a las normales dos grandes c´ırculos en la esfera. Su intersecci´on viene dada por la expresi´on u = n1 × n2 y corresponde a la direcci´on de los puntos ant´ıpodos. Ahora se considerar´a que un gran c´ırculo de normal ni tiene la misma direcci´on que n1 y n2 si: 1 − ni · u ≤ U mbralSimilaritud (3.3) 28 3.2. Clasificaci´ on sobre la esfera Repitiendo este proceso con cada normal ni , y para cada combinaci´on de 2 normales, podemos calcular una lista de vectores u, donde aquel con mayor n´ umero de l´ıneas paralelas es el que representa la direcci´on dominante en la imagen. Si eliminamos esta direcci´on y las l´ıneas paralelas que la votaban, podemos repetir el proceso para encontrar sucesivas direcciones dominantes. N´otese que si m es el n´ umero de c´onicas detectadas, el n´ umero total de combinaciones a probar es de m(m − 1). En la gran mayor´ıa de entornos se comprueba que las direcciones con mayor n´ umero de votantes se corresponden con la direcci´on vertical y dos horizontales ortogonales (figura 3.2). (a) (b) Figura 3.2: Resultados de Clasificaci´on sobre la Esfera Unitaria: (a) Componentes conectados (colores vivos) junto a las c´onicas que los aproximan (azul). (b) Clasificaci´on de los elementos conectados seg´ un direcciones principales. Verticales(azul), Horizontales en X (rojo), Horizontales en Y (verdes). 3. Extracci´ on y clasificaci´ on de c´ onicas 3.3. 29 M´ etodo propuesto Cada uno de estos m´etodos tiene una ventaja y una desventaja. El primer m´etodo ( 3.1) resulta ser muy r´apido, pero los resultados de la clasificaci´on no son todo lo precisos que se desear´ıa. Por contra, la precisi´on de clasificaci´on con el modelo que trabaja en la esfera ( 3.2) es mucho m´as fiable, pero el problema no escala bien en funci´on del n´ umero de normales presentes en la imagen y se hace demasiado lento para las escenas con las que trabajamos. En este apartado se propone un nuevo m´etodo que parte de las c´onicas extra´ıdas mediante el m´etodo que trabaja con modelo de la esfera con el objetivo de mantener la buena precisi´on del algoritmo, pero se hace un enfoque distinto para conseguir ejecutarlo en un tiempo m´ınimo. Este proyecto se centra en la extracci´on de la distribuci´on estructural en entornos de interior, por lo que es totalmente aceptable partir de dos supuestos. El primero es la hip´otesis de que nos encontramos ante el caso de ciudad de Manhattan[11], que asume que el entorno en el que nos movemos est´a compuesto por estructuras 3D donde existen 3 direcciones principales ortogonales entre s´ı. Caso razonable dado que los escenarios construidos por el hombre suelen estar dotados de esta caracter´ıstica. La segunda hip´otesis consiste en asumir que el sistema catadi´optrico es perfectamente perpendicular al suelo, hip´otesis que tampoco es descabellada ya que, en la gran mayor´ıa de los casos, los sensores de visi´on se encuentran situados sobre robots que se desplazan por el suelo mediante ruedas con movimiento plano. Para simplificar los c´alculos, asumamos que las tres direcciones principales del escenario coinciden con la base Eucl´ıdea e1 = (1, 0, 0), e2 = (0, 1, 0) y e3 = (0, 0, 1), de forma que las l´ıneas horizontales de la escena sean paralelas a los vectores e1 y e2 respectivamente, y las verticales sean paralelas a e3 . Al proyectar estas l´ıneas en la esfera unitaria, las intersecciones entre el plano de proyecci´on y la esfera forman grandes c´ırculos definidos por la normal al plano que los contiene. En este caso las normales que definen a los planos de proyecci´on de las l´ıneas paralelas a e1 ser´an de la forma n⊥e1 = (0, ny , nz ). Lo mismo ocurre con las l´ıneas paralelas a e2 y e3 , donde las normales a sus planos de proyecci´on son respectivamente n⊥e2 = (nx , 0, nz ) y n⊥e3 = (nx , ny , 0). Esta distribuci´on se ve reflejada en la figura 3.3. N´otese que las direcciones en las que apuntan estas normales siempre forman tres “c´ırculos”(en realidad existen peque˜ nas desviaciones) ortogonales entre s´ı, por lo que, aunque las bases no coincidan con la base Eucl´ıdea, seguiremos teniendo la 30 3.3. M´ etodo propuesto
  
 
   Figura 3.3: En la imagen de la izquierda se representan 3 trazos en la misma direcci´on de la base Eucl´ıdea (e1 ,e2 ,e3 ) los cuales se proyectan en la esfera mediante planos de proyecci´on representados por las normales (n⊥e1 , n⊥e2 , n⊥e3 ) respectivamente y se muestran como un punto de su color. En las dos siguientes im´agenes se ense˜ na como quedar´ıa una posible distribuci´on de varias normales proyectadas sobre la esfera ante caso Eucl´ıdeo y caso general dada una rotaci´on R. misma distribuci´on, pero girada un ´angulo α sobre el eje Z, un ´angulo β sobre el eje X y otro ´angulo γ sobre el eje Y. Vista esta propiedad, el m´etodo de clasificaci´on consiste en representar sobre la esfera las normales que definen los grandes c´ırculos en los que se proyectan las l´ıneas c´onicas extra´ıdas de la imagen catadi´optrica. Estas normales tendr´an una distribuci´on muy similar a la explicada anteriormente, por lo que el objetivo es encontrar cu´ales son los c´ırculos en los que apuntan, o lo que es lo mismo, calcular la rotaci´on que marca la diferencia entre la base Eucl´ıdea (e1 ,e2 ,e3 ) y la base de la escena (v1 ,v2 ,v3 ). Si consideramos ahora la segunda hip´otesis, por la que el eje Z de el sistema catadi´optrico es perpendicular al suelo en todo momento, podemos simplificar el algoritmo de b´ usqueda ya que el giro sobre los ejes X e Y ser´a nulo, por lo que β = 0 y γ = 0. Los pasos a seguir para realizar la clasificaci´on y extracci´on de los puntos de fuga son los siguientes: 1. Al asumir perpendicularidad entre el eje Z del sistema catadi´optrico y el suelo, los ´angulos de inclinaci´on β = 0 y γ = 0, y las normales de las l´ıneas pertenecientes a la direcci´on Z vienen dadas por n⊥e3  (nx , ny , 0). Por esto, todas las c´onicas cuyas normales tienen componente nz menor a un threshold 3. Extracci´ on y clasificaci´ on de c´ onicas 31 1 0.8 1 0.6 0.8 0.4 0.6 0.2 0 0.4 −0.2 0.2 −0.4 0 −1 −0.6 −0.5 1 0 0.5 0 0.5 1 −0.5 −0.8 −1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 −1 Figura 3.4: Izquierda: Distribuci´on de las normales sobre la esfera unitaria a partir de datos reales. Derecha: Clasificaci´on de las normales de la izquierda seg´ un las 3 direcciones principales. Los puntos gordos corresponden a la intersecci´ on entre grandes c´ırculos, es decir, los puntos de fuga. (experimentalmente 0,2 es un buen valor), son autom´aticamente clasificadas como pertenecientes a la direcci´on Z. 2. Se elimina la componente nz de las normales restantes. De esta forma se pueden representar sobre un plano 2D, d´onde la mayor´ıa de los datos se proyectados componen una distribuci´on en forma de cruz, girada un ´angulo α. 3. Mediante RANSAC se busca el ´angulo α que caracteriza a las dos direcciones error , d´onde principales ortogonales entre s´ı, de manera que ´estas minimicen inliers los inliers son el n´ umero de normales de entre el total que votan por una de las dos direcciones, y el error es la distancia entre cada inlier a la direcci´on que vota. 4. Las l´ıneas se clasifican en una direcci´on u otra dependiendo de la distancia de sus normales a las direcciones calculadas como dominantes. 5. Finalmente el punto de fuga para la direcci´on Z lo situamos en el centro de la imagen y los otros puntos de fuga vienen definidos por las zonas donde las direcciones dominantes intersectan con la esfera en el hemisferio (Z = 0). Ver figura 3.4 En la figura 3.5 se muestra al resultado obtenido al completar el proceso de clasificaci´on (derecha), y se compara con los m´etodos definidos anteriormente. 32 3.3. M´ etodo propuesto (a) (b) (c) Figura 3.5: Comparaci´on entre la clasificaci´on obtenida por los m´etodos descritos. (a) Clasificaci´on sobre imagen catadi´ optrica, tiempo en clasificar 1.5 sec. (b) Clasificaci´on sobre la esfera, tiempo en clasificar 120 sec. (c) M´etodo propuesto, tiempo en clasificar 0.5 sec Debido a la mejor precisi´on en cuanto a la clasificaci´on de l´ıneas, que se mostrar´a en el cap´ıtulo de resultados 6, y a la rapidez de ejecuci´on, de aqu´ı en adelante se utilizar´a el m´etodo propuesto para llevar a cabo la extracci´on de informaci´on. Secci´ on 4 Obtenci´ on de la distribuci´ on espacial de una escena En esta secci´on se aborda la parte del trabajo dedicada a la extracci´on de la distribuci´on espacial a partir de una sola imagen catadi´optrica, de forma que sea posible la detecci´on autom´atica del suelo, las paredes y la localizaci´on y orientaci´on respectiva entre estos elementos de la escena (Figura 4.1). La informaci´on de partida son las c´onicas extra´ıdas y clasificadas, as´ı como los puntos de fuga obtenidos en el procedimiento explicado en el cap´ıtulo anterior.          Figura 4.1: Ejemplo de una imagen tomada con un sistema hipercatadi´optrico y el resultado deseado despu´es de aplicar el algoritmo. En la imagen, el color azul representa el suelo, el color rojo representa paredes paralelas en una direcci´on dominante, y el color verde paredes paralelas en una direcci´on dominante ortogonal a la anterior. 33 34 4.1. 4.1. M´ etodo jer´ arquico de generaci´ on de hip´ otesis M´ etodo jer´ arquico hip´ otesis de generaci´ on de Ya se ha visto el proceso de extracci´on y clasificaci´on de informaci´on, mediante el cual se han obtenido un conjunto de l´ıneas a partir de la imagen catadi´optrica y clasificado seg´ un una de las tres direcciones principales que caracterizan la escena. Etiquetemos estas direcciones como direcci´ on Z a la representada por l´ıneas de color azul y cuyas l´ıneas son las proyecciones de los segmentos verticales de la escena 3D, y direcciones X e Y a las representadas por rojo y verde respectivamente, las cuales son las proyecciones de los segmentos horizontales ortogonales entre s´ı (figura 3.5). Tambi´en se han extra´ıdo los puntos de fuga, caracterizados por ser los puntos geom´etricos donde se intersectan las l´ıneas paralelas, es decir, las pertenecientes a un mismo grupo. El objetivo de esta secci´on es utilizar la informaci´on previamente descrita en conjunto a una serie de restricciones geom´etricas a partir de las cuales plantear hip´otesis que se aproximen lo m´aximo posible a la verdadera forma de la escena real, de forma que se pueda distinguir donde se encuentran los limites entre suelo y paredes. 4.1.1. Selecci´ on de puntos clave El trabajo propuesto en [23] prestaba especial atenci´on a encontrar esquinas que posteriormente sirvieran para delimitar la zona por donde se expande el suelo de la escena real que estamos estudiando. Estas esquinas vienen definidas por puntos donde intersectan segmentos verticales/horizontales entre s´ı. Sin embargo, las esquinas que definen los contornos reales del suelo de la escena estudiada son indetectables en muchos casos, con la dificultad a˜ nadida de que por el contrario, muchas esquinas que no pertenecen al suelo, sino a elementos como muebles o ventanas, son mucho m´as f´aciles de detectar y por tanto pueden llevar a considerar hip´otesis err´oneas. Es por esto que en este trabajo se va a hacer uso de otro tipo de puntos para plantear futuras hip´otesis sobre la localizaci´on del suelo de la escena. Haciendo un estudio de diversas im´agenes a las cuales les ha sido aplicado el proceso de la secci´on 3, se puede observar como las l´ıneas pertenecientes a la direcci´ on Z (representadas en azul), son m´as robustas que las l´ıneas pertenecientes a las direcciones horizontales. Esto quiere decir que la informaci´on que aportan los segmentos verticales es m´as fiable ya que en la gran mayor´ıa de los casos 4. Obtenci´ on de la distribuci´ on espacial de una escena 35 todas estas l´ıneas nacen desde el suelo y se extienden de forma radial hacia los bordes de la imagen. Por otro lado, las l´ıneas horizontales son m´as susceptibles al ruido o a ser clasificadas de forma incorrecta, de forma que suelos y paredes con gran concentraci´on de segmentos (v´ease muchos tipos de baldosas o ladrillos) har´an aparecer l´ıneas innecesarias sobre la imagen, resultando en una dificultad a˜ nadida en cuanto a la correcta localizaci´on del l´ımite pared-suelo. De forma contraria, tambi´en se dan multiples casos en los que el l´ımite que tendr´ıa que estar representando la transici´on pared-suelo no ha podido ser extra´ıdo, por lo que prestar mucha confianza a estas l´ıneas no es la mejor opci´on. Recordando la secci´on 3.1, ya se vio c´omo con tan s´olo dos puntos es posible definir una l´ınea c´onica sobre la imagen catadi´optrica. Tambi´en se ha mencionado que todas las l´ıneas de la escena han de pasar por un punto de fuga, esto quiere decir que los bordes que delimitan el contorno entre suelo y pared tambi´en han de pasar por uno de estos puntos de fuga. Juntando estas dos afirmaciones se deduce que tan solo necesitamos un punto que pertenezca al l´ımite pared-suelo para definir la c´onica que lo delimita. Ahora bien, obviamente si el objetivo es encontrar d´onde est´a situado el l´ımite de separaci´on entre pared y suelo, no podemos saber cuando un punto pertenece a ´este o no, por lo que es necesario dise˜ nar un algoritmo que sea capaz de deducir las regiones m´as probables en las que deben encontrarse estos puntos. Se hace evidente que la informaci´on aportada por las l´ıneas almacenadas en los tres grupos definidos con anterioridad es redundante y tan solo unos pocos puntos pertenecientes a ´estas son necesarios para generar las hip´otesis de contorno. De esta forma se definen los siguientes tres nuevos grupos (figura 4.2): De cada l´ınea que formaba parte del grupo de segmentos verticales (azules), se selecciona el punto m´as cercano al centro de la imagen, con objetivo de que este punto recaiga en la zona limitante entre suelo y pared. El conjunto de estos puntos formar´a el nuevo grupo GZ . Tomando las l´ıneas pertenecientes al grupo de segmentos horizontales en direcci´on X (rojos), se seleccionan u ´nicamente aquellas que est´an cercanas a alguno de los puntos del nuevo grupo GZ , y estas l´ıneas ser´an discretizadas tomando puntos cada cierto intervalo de longitud, los cuales pasar´an a formar parte del grupo GX . Se repite el mismo proceso anterior para las l´ıneas horizontales en direcci´on Y formando el grupo GY . 36 4.1. M´ etodo jer´ arquico de generaci´ on de hip´ otesis Figura 4.2: Discretizaci´ on de l´ıneas en puntos. Se puede apreciar como solo las l´ıneas horizontales (rojas y verdes) cercanas a las verticales (azules) son incluidas en el proceso. Figura 4.3: Formas m´as comunes de los suelos presentes en escenas de interior. La zona sombreada en rojo representa el cuadrado b´ asico central. 4.1.2. Hip´ otesis inicial del contorno central Una vez que se tienen los datos necesarios para generar hip´otesis de las posibles zonas donde se encuentra el borde entre pared y suelo surge un nuevo problema, no se sabe cuantos bordes estamos buscando y un programa de ordenador no puede identificar el n´ umero de paredes que componen una habitaci´on, sin alguna informaci´on adicional. Sin embargo, los entornos de interior suelen estar construidos seg´ un una serie de patrones. Se puede distinguir entre pasillos o habitaciones, los primeros com´ unmente son alargados en forma de I, o con ramificaciones en uno de sus extremos cuando nos acercamos al final, normalmente adquiriendo forma de L o de T. En cuanto a habitaciones se refiere, la forma cuadrangular es la forma por excelencia, pudiendo contar ´esta con irregularidades en alguna de sus caras. La figura 4.3 muestra algunos de los ejemplos m´as comunes. 4. Obtenci´ on de la distribuci´ on espacial de una escena
 37


 Figura 4.4: Imagen virtual simulando la hip´otesis de cuatro paredes. Se pueden observar las 4 regiones definidas al segmentar la imagen mediante las l´ıneas imaginarias que unen los puntos de fuga. Una caracter´ıstica que todos estos tipos de escena tienen en com´ un es que pueden ser definidas por un cuadril´atero central del que pueden surgir ramificaciones o ampliaciones. Todo cuadril´atero tiene sus caras paralelas dos a dos, y cada una de ´estas caras paralelas debe caer a cada uno de los lados formados por la l´ınea imaginaria que une sus correspondientes puntos de fuga (figura 4.4), debido a la definici´on de punto de fuga c´omo lugar geom´etrico donde convergen las l´ıneas paralelas. Conociendo ´esta propiedad, se toma como punto de partida, para buscar el ´area que define el suelo de la escena, la hip´otesis de que esta habitaci´on est´a compuesta u ´nicamente por cuatro paredes (las correspondientes al cuadril´atero generador), independientemente de que la escena real est´e compuesta por dicho n´ umero de muros o no. Y en pasos posteriores ya se proceder´a al ajuste m´as fino de el n´ umero de componentes estructurales para encontrar el resultado que mejor encaja con la distribuci´on real. Como se ha comentado, las cuatro l´ıneas c´onicas que van a definir el suelo de ´esta primera hip´otesis de 4 paredes, se sabe que se encuentran en regiones determinadas, por lo que podemos tratar la b´ usqueda de cada una de ellas como un subproblema aislado. Cada uno de estos subproblemas consiste en elegir los puntos de los grupos GX , GY y GZ que caen en cada una de las regiones definidas en la figura 4.4 (S1, ..., S4) seg´ un el lado del suelo que estamos buscando. Los lados 1 y 3 ser´an las l´ıneas que definen los l´ımites del suelo con orientaci´on X, y por tanto se usar´an los puntos de los grupos GZ y GX para buscar c´onicas a cada lado de la l´ınea imaginaria (S1 y S3) formada al unir los V P s en direcci´on X (Fig. 4.5 (izquierda)) . Los bordes 2 y 4 definir´an los bordes con orientaci´on Y , y las c´onicas se 38 4.1. M´ etodo jer´ arquico de generaci´ on de hip´ otesis Figura 4.5: Puntos de los grupos GZ (azul), GX (rojo) and GY (verde) separados para los 4 posibles casos. Los segmentos discontinuos rojo y verde son las l´ıneas imaginarias que unen los respectivos VPs y dividen la imagen en dos partes. buscar´an a cada lado de la l´ınea imaginaria formada al unir los V P s en direcci´on Y (S2 y S4) usando los puntos de los grupos GZ y GY (Fig. 4.5 (centro)) . Generaci´ on de c´ onicas Para buscar las c´onicas y debido a que no conocemos que puntos se sit´ uan sobre la regi´on del suelo, vamos a utilizar RANSAC como forma de identificar las c´onicas m´as votadas, candidatas a representar el borde deseado. Otra propiedad geom´etrica de las im´agenes catadi´optricas es que los 4 puntos de fuga definen un c´ırculo. Este c´ırculo corresponde a los puntos de la escena situados a la misma altura que la c´amara, por lo que los puntos que caen en el interior de este c´ırculo estar´an a una altura inferior y por tanto pueden corresponder a puntos del suelo, mientras que los que est´an en el exterior del c´ırculo es seguro que no pueden pertenecer al suelo y son eliminados de manera que no formen parte de la votaci´on en la b´ usqueda de c´onicas. Recordar que, solo son necesarios dos puntos, un VP y uno de los puntos de los grupos GX , GY , GZ reci´en formados. El producto vectorial entre un VP y cualquiera de los puntos pi genera un vector normal ni , que define una c´onica Ω, despu´es de la transformaci´on proyectiva HC [2]: obteniendo finalmente Ω ⎞ ⎛ ⎞ ⎛ S ⎞ Pix V PxS n ix S ⎝ ⎝ ⎝ ⎠ ⎠ PiSy ⎠ V Py n iy = × ni = S n iz V Pz PiSz ⎛ (4.1) 4. Obtenci´ on de la distribuci´ on espacial de una escena 39 ⎤ n2ix (1 − ξ 2 ) − n2iz ξ 2 nix niy (1 − ξ 2 ) nix niz n2iy (1 − ξ 2 ) − n2iz ξ 2 niy niz ⎦ Ωi = ⎣ nix niy (1 − ξ 2 ) ni x ni z n iy n iz n2iz (4.2) i = HC −t Ωi HC −1 Ω (4.3) ⎡ La distancia entre cada punto pj y la c´onica generada por el punto pi con el punto de fuga VP, se mide usando una aproximaci´on a [24]. Se calcula la l´ınea se calcula la perpendicular a la l´ınea polar, polar de un punto pj en la c´onica Ω, especificando que pase sobre el punto pj . Este segmento perpendicular corta a la c´onica en dos puntos q+ y q− , la m´ınima distancia eucl´ıdea entre pj y q+ o q− corresponde a la distancia entre punto y c´onica1 . Con todos aquellos puntos que tengan una distancia menor a un umbral de la c´onica, se estima una c´onica media y se repite el proceso hasta que converge (no se encuentran m´as puntos cercanos). Los puntos pj que votan a ´esta c´onica media son eliminados de la lista, y se selecciona un nuevo punto pi de entre los restantes para generar una nueva c´onica, repitiendo el proceso hasta que todos los puntos votan al menos a una c´onica (figura 4.6). De entre las c´onicas m´as votadas para formar los l´ımites del suelo de la hip´otesis de habitaci´on de 4 paredes se eligen aquellas m´as cercanas al centro de la imagen. Esto se debe a que al estar buscando el cuadrado central, es preferible seleccionar un cuadrado m´as peque˜ no que luego tiene posibilidades de ser ampliado en el proceso de expansi´on (Secci´on 4.1.3). El proceso de b´ usqueda de c´onicas se repite para cada uno de los cuatro casos expuestos, de forma que los puntos que intervienen en la b´ usqueda vienen restringidos por el caso en el que nos encontramos. La figura 4.6 muestra las c´onicas extra´ıdas ante cada caso as´ı como los l´ımites ganadores que forman los contornos de la primera hip´otesis de cuatro paredes. 4.1.3. Proceso jer´ arquico para generaci´ on de hip´ otesis Denotemos c´omo B1 , B2 , B3 y B4 las cuatro fronteras entre pared y suelo que se acaban de obtener para definir el contorno del suelo de la primera hip´otesis de cuatro paredes. El ´area entre cada uno de estos bordes y el exterior de la imagen define cuatro sectores. Estos sectores corresponden a las paredes de la hip´otesis inicial, y si ´esta coincide con la escena real, los sectores estar´an definiendo las paredes de la escena. 1 Explicado en detalle en el Anexo D 40 4.1. M´ etodo jer´ arquico de generaci´ on de hip´ otesis Figura 4.6: A la izquierda se muestran las c´onicas generadas m´as votadas para uno de los cuatro casos. En la imagen central se pueden observar todas las c´onicas extra´ıdas donde cada color representa cada uno de los casos. La foto de la derecha corresponde con el resultado obtenido para la primera hip´otesis de 4 paredes. Sin embargo, lo m´as probable es que esta primera hip´otesis solo sea la parte central de la imagen real, por lo que los sectores que definen las aprendes actuales podr´an ser expandidos. Se entiende como expansi´on el proceso mediante el cual se busca reemplazar cada una de las fronteras Bi por otro conjunto de l´ıneas c´onicas que agranden el ´area del suelo de la primera hip´otesis de manera que estas sucesivas hip´otesis de contorno generadas por las posibles ampliaciones de suelo aproximen mejor a la habitaci´on real que se est´a analizando. Ampliar las fronteras Bi se traduce en buscar ramificaciones en las caras del cuadril´atero central, procedimiento similar al de buscar la hip´otesis inicial de cuatro paredes, pero esta vez en vez de repetir todos los pasos explicados en la secci´on 4.1.2, se parte de las c´onicas ya extra´ıdas en dicha secci´on. Para cada uno de los sectores definidos por los bordes B1 , B2 , B3 y B4 se seleccionan aquellas c´onicas que contienen votantes. La foto de la derecha de la figura 4.7 muestra como en el sector definido por el l´ımite B2 se seleccionan en verde aquellas c´onicas que cruzan el sector y contienen inliers sobre ´este, por el contrario, las c´onicas marcadas de color blanco son c´onicas contenidas en el sector pero no contienen inliers que voten por ellas dentro de ´este. De las c´onicas seleccionadas, con un m´aximo de 3 l´ıneas (2 laterales y una central) y combin´andolas con el borde del contorno inicial (Bi ) del sector al que pertenecen, se conformar´ıa el cuadril´atero que define el posible ´area a a˜ nadir en el proceso de ampliaci´on de cada lateral. Sin embargo, por diversas cuestiones, no siempre se va a poder encontrar estas tres l´ıneas que conforman el cuadril´atero de ampliaci´on. En general, a la hora de expandir una de las caras de la hip´otesis inicial, las opciones ante las que nos encontramos se pueden resumir en 3 casos: Se dan condiciones bien definidas que nos permiten encontrar c´onicas suficiente para generar los 3 nuevos bordes, y por tanto habr´a expansi´on 4. Obtenci´ on de la distribuci´ on espacial de una escena 41 Figura 4.7: A la izquierda: resultado obtenido para la primera hip´otesis de 4 paredes d´onde se ven los bordes B1 , B2 , B3 y B4 que definen 4 sectores. A la derecha: Ampliaci´on del sector 2, d´onde se observan las c´onicas seleccionadas (verde) y las no seleccionadas (blanco) candidatas a generar la secci´on que expandir´a el suelo. Notar c´omo la correcta combinaci´on entre B2 dos c´onicas laterales y una central (marcado en amarillo) conforman una expansi´on perfecta. en el sector actual. No se encuentran c´onicas centrales o las que se encuentran est´an muy pr´oximas a Bi . Esto significa que el borde Bi corresponde con el l´ımite real entre la pared y el suelo por lo que no hay necesidad de buscar una expansi´on en ese sector. Se encuentra c´onica central pero no en uno de los laterales. Esto puede deberse a que por ruido o alg´ un otro fallo, exista la l´ınea pero no se haya detectado. O que nos encontremos ante la presencia de una esquina oculta, es decir, una de las paredes se encuentra en un a´ngulo de visi´on muerto para la c´amara y es tapada por otra pared. Para generalizar el problema pero contemplando cada uno de los casos se sigue el diagrama de flujo de la imagen 4.8 explicado a continuaci´on. 1. Se selecciona uno de los sectores formados por la primera hip´otesis. 2. Se seleccionan y ordenan las c´onicas de su interior en tres grupos, 2 laterales y uno central. Si no se encuentran l´ıneas pertenecientes al grupo central nos encontramos ante el segundo caso; no hay expansi´on para el sector actual y pasamos al siguiente. 3. Si se han encontrado c´onicas en lado central, pero no se han encontrado en los laterales, y una de las c´onicas centrales tiene m´as votantes que el borde actual Bi , se reemplaza el contorno Bi por la nueva c´onica resultando en la expansi´on de dicha cara. 42 4.1. M´ etodo jer´ arquico de generaci´ on de hip´ otesis



                            % #$%  "      %            %             *                                        !                      %                                       & 
      %     !  '            (    )     Figura 4.8: Diagrama de flujo seguido para por el algoritmo para obtener la hip´otesis final. 4. Si se han encontrado c´onicas en el lado central, y en ambos laterales, elegir de cada grupo la que m´as votantes tenga, y junto al borde Bi se crea una posible hip´otesis de ampliaci´on. Sin embargo, si solo se han encontrado c´onicas en uno de los laterales, se genera una c´onica que pase por el punto de fuga que caracteriza el sector (aqu´el que cae dentro de ´este) y el punto votante que, perteneciendo a la l´ınea seleccionada del grupo central, tiene el mayor ´angulo posible con respecto a la l´ınea imaginaria que une el VP y el centro de la imagen. Una vez se tiene las 3 c´onicas, se crea la posible hip´otesis de ampliaci´on. 5. Se comprueba si dentro de este ´area de ampliaci´on hay un n´ umero alto de puntos que votan a otras c´onicas. En caso contrario, ´esta es una buena hip´otesis de expansi´on y pasamos al siguiente sector. 6. Si hay m´as de un determinado n´ umero de votantes es debido a que pese a que las c´onicas elegidas hayan sido m´as votadas, est´an pertenecen a alguna pared u objeto. Por esta raz´on una de las 3 c´onicas que formaban la hip´otesis actual 4. Obtenci´ on de la distribuci´ on espacial de una escena 43 de ampliaci´on se sustituye por otra m´as proxima al centro de la imagen y se vuelve a generar otra hip´otesis de ampliaci´on. 7. El paso 5 y 6 se repiten hasta que la hip´otesis se considera buena o hasta que no hay c´onicas para crear nuevas regiones para ampliar, por lo que no se ejecutara ampliaci´on. En la siguiente figura (Fig. 4.9), se muestra el proceso de expansi´on para la hip´otesis de 4 paredes obtenida en la imagen 4.6. Figura 4.9: 1)Ampliaci´on del primer sector. 2a)Primera hip´otesis del segundo sector, al haber inliers en el interior hay que reducir. 2b)Segunda hip´otesis del sector 2, esta vez corresponde con la ampliaci´on. 3)Ampliaci´on del tercer sector. 4)No se encuentran ampliaciones, esto es debido a que el borde ya estaba en el lugar correcto. F)Hip´otesis final despu´es de las ampliaciones de las cuatro caras. Se observa que en algunas de sus caras el a´rea ampliada podr´ıa haber sido mayor para aumentar el ´ındice de similitud, pero puesto que en esta secci´on solo contamos con la informaci´on de una imagen es preferible restringir el ´area considerada como suelo, a no ampliarla y pensar que existe m´as suelo que el que hay en realidad. M´as resultados de aplicar el proceso completo de recuperaci´on estructural de la escena pueden consultarse en el cap´ıtulo 6 de resultados experimentales. 44 4.1. M´ etodo jer´ arquico de generaci´ on de hip´ otesis Secci´ on 5 Aplicaci´ on secuencial homograf´ıas mediante En las secciones previas se ha descrito el m´etodo propuesto para estimar la distribuci´on espacial de un escenario a partir de una sola imagen omnidireccional capturada por un sistema hyper-catadi´optrico. En el cap´ıtulo de experimentos 6.2 se muestra como este m´etodo conduce a buenos resultados, pero debido a cambios de iluminaci´on, ruido en la imagen y diversas adversidades no se puede garantizar una extracci´on ´optima para cada una de las im´agenes analizadas. Por otra parte, la aplicaci´on final de este algoritmo est´a orientada a su utilizaci´on con secuencias de im´agenes, donde los cambios entre sucesivos fotogramas se suponen relativamente peque˜ nos. Por lo tanto, se puede asumir que la distribuci´on estructural obtenida por este m´etodo aplicado a una sucesi´on de im´agenes deber´a variar de forma coherente a lo largo de un mismo entorno. Para poder llevar a cabo estos procesos por los que mejorar la precisi´on del m´etodo en im´agenes donde los resultados no son lo suficientemente robustos, y poder hacer la informaci´on extra´ıda de cada una de las im´agenes de la secuencia lo m´as homog´enea posible, se har´a uso de homograf´ıas. 5.1. Homograf´ıa A continuaci´on se definen las caracter´ısticas principales del modelo geom´etrico de la homograf´ıa a trav´es de dos vistas. Dos im´agenes perspectivas se pueden relacionar geom´etricamente a trav´es de una homograf´ıa H ∈ R3×3 [7]. Esta transformaci´on proyectiva H relaciona los puntos pertenecientes a un plano de 45 46 5.1. Homograf´ıa la escena observados desde distintos puntos de vista. Sean R y t la matriz de rotaci´on y el vector de translaci´on entre dos posiciones O y O∗ del sistema catadi´optrico central (figura. 5.1). Obs´ervese que el plano virtual perspectivo asociado a la c´amara en las distintas posiciones tambi´en se ve afectado por el mismo movimiento (R, t).                    
       

   


 Figura 5.1: Homograf´ıa entre dos puntos de vista O y O∗ . Considerando que la l´ınea 3D  est´a situada sobre un plano Π definido por Π = [nF d], donde nF es la normal del plano Π con respecto a O, y d es la distancia desde Π hasta el origen O [15]. N´otese que cualquier punto de la escena perteneciente al plano Xw ∈ Π con coordenadas Xw = [Xw , Yw , Zw ]T con respecto al origen O y con coordenadas Xw ∗ = [Xw ∗ , Yw ∗ , Zw ∗ ]T con respecto al origen O∗ se proyecta en la esfera en los puntos Xs y Xs ∗ respectivamente para las dos posiciones de la c´amara. Y la relaci´on entre estos puntos proyectados en la esfera unitaria viene dada por Xs ∗ ∝ HXs donde H es la matriz 3 × 3 de homograf´ıa. (5.1) 5. Aplicaci´ on secuencial mediante homograf´ıas 47 Para calcular la matriz de homograf´ıa entre dos im´agenes en el caso general sin imponer ninguna restricci´on, se necesitan un m´ınimo de cuatro correspondencias de puntos entre ambas im´agenes, a partir de los cuales se resuelve un sistema lineal para obtener la matriz H [16]. La homograf´ıa calibrada est´a pues relacionada con el movimiento de la c´amara (rotaci´on R, translaci´on t) y su situaci´on con respecto al plano por la siguiente expresi´on: H = R(I + tnTF /d) (5.2) donde nTF es la normal del plano y d is la distancia desde ´este hasta el origen. 5.1.1. Homograf´ıa a partir de l´ıneas Aunque lo m´as habitual es estimar la homograf´ıa que relaciona dos im´agenes a partir de puntos correspondientes, tambi´en se puede calcular mediante rectas emparejadas. Sean dos puntos del espacio X1 y X2 pertenecientes a la linea  que est´a contenida en el plano Π definido en la secci´on anterior. Esta linea puede ser perfectamente definida por la normal al plano, que se calcula como: nL = X1 × X2 X1 × X2  (5.3) Por lo tanto, cualquier punto perteneciente a esta linea cumple nTL Xi = Xi nL = 0. De acuerdo a la ecuaci´on 5.1, la relaci´on de un punto del espacio visto desde dos posiciones distintas viene dada por Xi ∗ ∝ HXi . Considerando a la vez la ecuaci´on reci´en presentada nTL Xi = 0, la relaci´on con Xi ∗ viene representada ∗ por nTL H−1 Xi ∗ = 0 [14]. A su vez tambi´en se cumple que nTL Xi ∗ = 0 deduci´endose la expresi´on que relaciona una l´ınea observada desde dos posiciones distintas T n∗L ∝ H−T nL (5.4) N´otese que la matriz de homograf´ıa que se utiliza para relacionar l´ıneas es la misma que la que relaciona puntos, pero inversa y transpuesta. Los par´ametros a determinar son ocho sin especificar la escala. Cada emparejamiento de l´ıneas proporciona dos ecuaciones lineales en t´erminos de la matriz de homograf´ıa. Por lo tanto, se necesitan un m´ınimo de cuatro correspondencias para determinar la soluci´on u ´nica de H. 48 5.2. Selecci´ on de emparejamientos 5.2. Selecci´ on de emparejamientos Sin ninguna restricci´on adicional, se necesitan cuatro emparejamientos, sean de puntos o de l´ıneas, para definir la matriz de homograf´ıa que relaciona todos los elementos pertenecientes a un plano observado desde dos posiciones diferentes. Sin embargo, es posible imponer condiciones adicionales que permiten eliminar t´erminos de la matriz H 3 × 3 [19]. Condici´ on de movimiento plano: Se considera que la c´amara se mueve sobre un plano horizontal, por lo que la matriz de giro se restringe a rotar sobre el eje vertical, y el vector de desplazamiento constar´a u ´nicamente de movimiento en coordenadas x e y. ⎡ ⎤ cos θ sin θ 0 R = ⎣− sin θ cos θ 0⎦ (5.5) 0 0 1 nF = [nF x , nF y , nF z ]T = [0, 0, 1]T (5.6) t = [tx , ty , tz ]T = [tx , ty , 0]T (5.7) Y recordando la expresi´on de H = R(I + tnTF /d): ⎤ ⎡ cos θ sin θ tx /d H = ⎣− sin θ cos θ ty /d⎦ 0 0 1 (5.8) La matriz resultante ha pasado a tener cuatro inc´ognitas, por lo que ya solo ser´ıan necesarios dos emparejamientos para tener el sistema de ecuaciones lineales totalmente definido. Imposici´ on de rotaci´ on: Un problema que se tiene al aplicar el algoritmo imagen a imagen es que las direcciones X e Y son intercambiables de una ejecuci´on a otra. Esto se arregla haciendo “tracking”de los puntos de fuga. Adicionalmente, este tracking proporciona informaci´on de giro entre im´agenes (´angulo de rotaci´on θ), la cual podemos aprovechar para introducir en H de forma que las u ´nicas inc´ognitas restantes son: tx , ty y d, pero est´an agrupadas en dos t´erminos y como para esta aplicaci´on no interesa conocer su valor particular se consigue un sistema de ecuaciones resoluble a partir de un solo emparejamiento. 5. Aplicaci´ on secuencial mediante homograf´ıas 5.2.1. 49 Emparejamiento de puntos La primera opci´on es utilizar emparejamiento por puntos. Para esto es necesario disponer de puntos pertenecientes al mismo plano en ambas im´agenes a las que se les aplica la homograf´ıa. Debido a las condiciones impuestas para poder reducir el n´ umero de par´ametros, el plano al que deben pertenecer es el plano del suelo. Figura 5.2: Caracter´ısticas extra´ıdas y posibles emparejamientos entre im´agenes de una escena tomadas desde posiciones distintas despu´es de aplicar la m´ascara. Surgen dos dificultades. A priori se desconoce que puntos pertenecen a este plano, pues es lo que se quiere averiguar. La informaci´on que tenemos no asegura correspondencia de una imagen a otra, por lo que ser´a necesaria nueva informaci´on. La obtenci´on de nueva informaci´on puede ser proporcionada a partir del extractor de caracter´ısticas SIFT[20] [12]. Este es un buen descriptor para esta aplicaci´on ya que es invariante con la escala, un factor muy importante cuando se trabaja con im´agenes catadi´optricas. Asegurar que las caracter´ısticas extra´ıdas por el descriptor SIFT pertenecen al plano del suelo no es posible, pero s´ı que se puede aumentar las posibilidades de que esto ocurra. Se sabe que el c´ırculo resultante de unir los puntos de fuga entre s´ı corresponde a puntos situados a la misma altura que la c´amara, de forma que los puntos 50 5.2. Selecci´ on de emparejamientos interiores a este c´ırculo estar´an a una altura inferior y existen posibilidades de que pertenezcan al suelo. Pero es seguro que los puntos que caen en el exterior de este c´ırculo al estar m´as altos que la c´amara no puede pertenecer el suelo, por lo que aplicando una m´ascara que elimine este ´area exterior se incrementa las opciones de que las caracter´ısticas extra´ıdas pertenezcan al plano de inter´es. Adem´as al reducir las dimensiones de la imagen la velocidad de computo se incrementa. De las caracter´ısticas extra´ıdas no todas se emparejan correctamente. Para asegurar que la homograf´ıa est´a calculada tan precisa como sea posible se aplica un proceso de RANSAC de la siguiente forma: 1. Se elige una correspondencia (Xi → Xi ∗ ) aleatoriamente. 2. Se calcula una matriz de homograf´ıa H a partir del emparejamiento seleccionado. 3. Se aplica la Homograf´ıa a todos los emparejamientos XH ∗ = HX y se aceptan como correspondencias v´alidas para dicha homograf´ıa aquellas cuya distancia eucl´ıdea d = X ∗ − XH ∗  sea inferior a un umbral. 4. Se aplica una rejilla a la imagen (bucketing) y se elige como ganadora a la matriz H con mayor n´ umero de correspondencias votantes y adem´as estas se encuentren distribuidas en al menos cuatro de las secciones formadas por la rejilla (figura 5.3). 5.2.2. Emparejamiento de l´ıneas Los mayores problemas del emparejamiento por puntos son el tener que hacer uso de informaci´on adicional, solamente u ´ til para calcular la homograf´ıa y que no se puede asegurar completamente que esta informaci´on pertenezca al plano del suelo. La segunda opci´on permite obtener la matriz de transformaci´on H a partir de l´ıneas, m´etodo que tiene grandes ventajas sobre el de emparejamiento por puntos. El motivo de aplicar homograf´ıa es poder relacionar las hip´otesis de suelo de sucesivas im´agenes, extra´ıdas en la secci´on 4.1.3 de forma que estas concuerden el m´aximo posible para evitar posibles errores del algoritmo. Las hip´otesis de suelo de cada imagen est´an formadas por la uni´on de varias l´ıneas c´onicas, a partir de las cuales podemos extraer la homograf´ıa deseada. 5. Aplicaci´ on secuencial mediante homograf´ıas 51 Figura 5.3: Emparejamientos votantes de la homograf´ıa ganadora. Los c´ırculos rojos corresponden a las caracter´ısticas detectadas en la imagen actual. Los puntos verdes son los emparejamientos obtenidos al aplicar la homograf´ıa H a sus correspondientes obtenidos desde el otro punto de vista (figura 5.2). Obs´ervese que existe la gran ventaja de que estas l´ıneas no hay que extraerlas espec´ıficamente para calcular la homograf´ıa, sino que ya se dispone de ellas y adem´as por definici´on han de pertenecer al plano del suelo. De esta forma solo tenemos que encontrar un emparejamiento de entre las l´ıneas que forman el contorno del suelo para definir la matriz H. Sea nL la normal que define una l´ınea en la imagen I, y n∗L la normal que representa el emparejamiento de nL visto en la imagen I ∗ , estas l´ıneas est´an relacionadas por: n∗L ∝ H−T nL d´onde la matriz H es la deducida en la ecuaci´on 5.8: ⎤ ⎡ cos θ sin θ tx /d H = ⎣− sin θ cos θ ty /d⎦ 0 0 1 (5.9) (5.10) 52 5.2. Selecci´ on de emparejamientos ⎛ ⎜ H−T = ⎝ cos θ cos θ 2 +sin θ 2 − sin θ cos θ 2 +sin θ 2 −(cos θ t˙x /d−sin θ t˙y /d) cos θ 2 +sin θ 2 sin θ cos θ 2 +sin θ 2 cos θ cos θ 2 +sin θ 2 −(cos θ t˙y /d+sin θt˙x /d) cos θ 2 +sin θ 2 ⎞ ⎛ ⎞ 0 0 ⎟ ⎠ 1 (5.11) cos θ sin θ 0 ⎝ − sin θ cos θ 0 ⎠ h32 1 h31 = Desarrollando la matriz inversa y transpuesta de H; H−T = [hij ] con i, j = 1, 2, 3, se observa que ´esta sigue dependiendo u ´nicamente de dos par´ametros desconocidos (h31 y h32 ) compuestos por una combinaci´on lineal de los par´ametros de H pero cuyo valor individual es irrelevante. La ecuaci´on 5.9 es equivalente a n∗L × H−T nL = 0, de d´onde se deduce el siguiente sistema de ecuaciones: ⎞   h31 ny ny nz ny − nx nz sin θ − ny nz cos θ ⎝ 0 nx ny ⎠ h32 = ∗ ∗ ∗ ∗ ∗ −nx nx −ny nx nx nz cos θ − ny nz sin θ − nz nx 0 1 (5.12) que se puede resolver mediante Descomposici´on en Valores Singulares (SVD), obteniendo as´ı h31 y h32 , que se utilizan para componer la matriz H−T , y al deshacer la inversion y transposici´on se recupera H.  ∗ ∗ ∗ ∗ ∗  ⎛ A priori no se conoce como est´an emparejadas las distintas l´ıneas de ambas hip´otesis, por lo que una opci´on ser´ıa calcular las homograf´ıas obtenidas para todas las posibles combinaciones entre las normales de ambas im´agenes. Si cada hip´otesis de suelo est´a compuesto por un n´ umero N de paredes comprendido entre 4 y 16, el m´aximo n´ umero de combinaciones posibles ser´ıa de 256. Sin embargo, muchas combinaciones no tienen sentido f´ısico (l´ıneas de puntos opuestos de la imagen), por lo que solo es necesario calcular homograf´ıas para aquellas l´ıneas cuyas normales indiquen similitud (algoritmo 1). 5. Aplicaci´ on secuencial mediante homograf´ıas 53 Algorithm 1 C´alculo de Homograf´ıa Require: hipotesis, hipotesis∗ Ensure: Homograf´ıa 1: for i := 1 → N do 2: for j := 1 → N ∗ do 3: if ni · nj ∗ ≥ 0,8 then 4: H=CalcularHomograf´ıa(ni , nj ∗ ) 5: Similitud=CalcularSimilitud(hipotesis, hipotesis∗ ,H) 6: if Similitud > MejorSimilitud then 7: Homograf´ıa = H 8: MejorSimilitud = Similitud 9: end if 10: end if 11: end for 12: end for 13: return Homograf´ıa 5.3. Medida de similitud En la secci´on 5.2.1, se calcula cuan adecuada es una matriz de homograf´ıa mediante el c´omputo de la distancia entre los emparejamientos una vez se les aplica la transformaci´on H. Calcular la similitud entre l´ıneas no es tan sencillo (Fig. 5.4), en primer lugar porque ni siquiera se sabe si las hip´otesis que se est´an emparejando tienen el mismo n´ umero de bordes. Ante la dificultad de comparar las l´ıneas entre s´ı, se plantea discretizar los contornos de las figuras a comparar en puntos, de forma que podamos calcular al distancia media entre los puntos de ambas. Para esto, todas las figuras bajo an´alisis han de tener el mismo n´ umero N de puntos y han de estar referenciadas a un mismo a´ngulo α, es decir, tomando como ´angulo de referencia α al correspondiente con el punto de fuga de la direcci´on X (V PX ), el primer punto de la hip´otesis uno, p11 , corresponder´a al punto que se encuentre con un ´angulo equivalente al del V PX de dicha hip´otesis, de la misma angulo es forma el primer punto de la hip´otesis m, pm 1 , corresponde al punto cuyo ´ equivalente al del V PX de la hip´otesis m (figura. 5.5). Una vez discretizados los contornos, se aplica sobre los puntos del contorno que define la hip´otesis de la imagen I (pI1 , ..., pIN ), la posible homograf´ıa Hi que relaciona esta imagen I con la imagen I ∗ . 54 5.3. Medida de similitud Figura 5.4: Resultados de homograf´ıas. En la primera imagen se muestra la hip´otesis de suelo (en rojo) para una imagen I. En el resto de figuras, se muestra la hip´ otesis∗ de suelo (en ∗ blanco) seg´ un la imagen I observada de una posici´on desplazada con respecto a I. En rojo se adjunta el resultado de aplicar diversas homograf´ıas que transforman la hip´ otesis desde la imagen I a la imagen I ∗ . La escena de arriba a la derecha muestra el resultado de aplicar una homograf´ıa donde la similitud es alta. Las im´agenes de la fila inferior corresponden a homograf´ıas fallidas. La similitud entre ambas hip´otesis en funci´on de la homograf´ıa Hi viene definida por la distancia media entre la proyecci´on de los puntos (pI1 , ..., pIN ) de la imagen ∗ ∗ I sobre la imagen I ∗ y los puntos de la hip´otesis de la imagen I ∗ (pI1 , ..., pIN ).  ∗ ∗  distancia(Hi ) = Hi [pI1 , ..., pIN ] − [pI1 , ..., pIN ] (5.13) De esta forma, la matriz de homograf´ıa Hi que consiga la menor distancia media entre puntos de los contornos comparados, ser´a considerada la homograf´ıa ganadora que relaciona las im´agenes I e I ∗ . Este proceso se repite con cada una de las m im´agenes que van a participar en el proceso de promediado sobre la imagen I ∗ 5. Aplicaci´ on secuencial mediante homograf´ıas 55


 




 





 Figura 5.5: Contorno de la hip´otesis de una imagen I discretizado en N puntos. Se aplica homograf´ıa Hi y se calcula la distancia entre puntos con la ecuaci´on 5.13 para comprobar cuan buena es esta homograf´ıa. 5.4. Hip´ otesis ponderada Una vez las distintas hip´otesis de cada imagen que van a participar en el promedio se encuentran proyectadas sobre la imagen I ∗ a analizar, ya pueden ser comparadas. Esta comparaci´on se lleva a cabo mediante el mismo proceso definido en la secci´on 5.3, con la diferencia de que en vez de buscar la homograf´ıa que hace lo m´as parecidas posibles las dos hip´otesis comparadas, esta vez ya se parte de que las hip´otesis han sido proyectadas mediante la homograf´ıa m´as votada y ahora se comparan los contornos de m im´agenes consecutivas proyectadas sobre la imagen I ∗ para hacer que el contorno promedio de esta imagen sea lo m´as parecido al resto. As´ı pues, el primer paso es calcular la distancia media entre cada hip´otesis i y el resto de las m hip´otesis proyectadas sobre la imagen I ∗ m    i [p1 , ..., piN ] − [pj1 , ..., pj ] DistanciaM edia(i) = N (5.14) j=1 de forma que la hip´otesis con menor distancia media al resto ser´a la que posea mayor n´ umero de caracter´ısticas similares y ser´a elegida como contorno promedio inicial. Esto es especialmente u ´til en caso de que dentro del conjunto de hip´otesis el n´ umero de paredes que conforma cada una sea distinto entre ´estas, por ejemplo en etapas de transici´on entre escenarios (habitaci´on-pasillo), d´onde parte de hip´otesis votaran por permanecer en el primer escenario, mientras que otra parte empezar´an 56 5.4. Hip´ otesis ponderada a votar para realizar la transici´on, as´ı pues en el momento que uno es m´as votado que otro, la hip´otesis promedio de contorno inicial determinar´a en cual de los casos nos encontramos. HipotesisP romedio = Hipotesis(arg min |DistanciaM edia(i)|) (5.15) i Este contorno promedio inicial contiene la mayor parte de la informaci´on estructural de lo que ser´a la hip´otesis final de la imagen actual, pero actualmente sus caracter´ısticas solo corresponden con las extra´ıdas a la imagen a la que pertenece. Para que realmente el contorno del resultado final concuerde al m´aximo con el global de contornos, vamos a realizar un promedio entre las componentes que los conforman. definidas en Recordando que cada contorno esta formado por l´ıneas c´onicas Ω la esfera por su normal n, el primer paso ser´a proyectar las normales de todas las hip´otesis participantes, sobre la imagen I ∗ , multiplicando por la inversa de la transpuesta de sus respectivas matrices de homograf´ıa obtenidas en la secci´on 5.3. Una vez proyectadas todas estas c´onicas, se toma como referencia el contorno medio inicial y las normales del resto de hip´otesis que sean suficientemente similares a las normales del contorno base ser´an promediadas para conformar el resultado final (figura 5.6). Figura 5.6: Izquierda. Ejemplo de una hip´otesis con defectos (el suelo abarca zonas que deber´ıan ser pared). Centro: Sobre la hip´otesis de suelo actual (negro) se proyectan hip´otesis de im´agenes anteriores, y se elige la que m´as concuerda con el resto del conjunto(rojo). Derecha: Se promedia la hip´otesis ganadora (rojo) con las cercanas para dar el resultado final. 5. Aplicaci´ on secuencial mediante homograf´ıas 57 Algorithm 2 C´alculo del Resultado Final mediante el promedio de hip´otesis Require: ContornoInicial, nh |∀h ∈ {1 → N umeroHipotesis} Ensure: ContornoP romedio 1: ContornoPromedio=ContornoInicial 2: for i := 1 → N umeroP aredes ContornoInicial do 3: ni = ContornoInicial(i) {Normal que define a la pared “i”} 4: for h := 1 → N umeroHipotesis do 5: for j := 1 → N umeroP ared Hipotesis(h) do 6: nh,j = Hipotesis(h, j) {Normal de la pared “j” de la hip´otesis “h”} 7: producto = ni · nh,j {Indica si los contornos son cercanos} 8: if producto ≥ 0,98 then 9: ContornoPromedio(i)=ContornoPromedio(i)+Hip´otesis(h,j) 10: Normalizar=Normalizar+1 11: end if 12: end for 13: end for 14: ContornoPromedio(i)=ContornoPromedio(i)/ContornoP romedio(i) 15: end for 16: return ContornoPromedio 5.5. Propagaci´ on de hip´ otesis El conjunto de procesos explicados en las secciones previas se repite para cada imagen perteneciente a la secuencia para transformar la hip´otesis obtenida del an´alisis individual de dicha imagen, en un resultado final que hace mucho m´as robusto y homog´eneo el conjunto. Pese a que el resultado final se supone mejor que el obtenido individualmente, ser´ıa un error sustituirlo a la hora de propagarlo en la secuencia, ya que al hacer esto cada vez que se introdujera un cambio en la escena ser´ıa eliminado por el resto de hip´otesis anteriores y as´ı sucesivamente impidiendo introducir modificaciones. Para evitar esta rigidez ante cambios, pero a su vez mantener el m´etodo robusto ante ruido, se propone no sustituir pero si guardar como informaci´on adicional un n´ umero k de los resultados finales m´as recientes e incluirlos en futuras votaciones, de forma que este n´ umero k ha de ser menor que el n´ umero m total de hip´otesis que intervienen en la votaci´on, y teniendo en cuenta que cuanto mayor sea k, menos flexible ser´a el m´etodo ante cambios en la estructura de la escena. En nuestros experimentos se considera que m = 7 aporta suficiente informaci´on para hacer un buen promedio, ya que cuanto mayor n´ umero de hip´otesis 58 5.5. Propagaci´ on de hip´ otesis promediadas m´as lento se hace el proceso y m´as riesgo de incluir errores en las homograf´ıas que se vuelven menos precisas al relacionar im´agenes distantes. A su vez hacemos k = 2 para aumentar la robustez pero sin restringir la adaptaci´on a cambios del entorno. Los beneficios de este u ´ltimo paso del algoritmo pueden verse reflejados en las comparaciones entre secuencias que se realizan en la secci´on de experimentos 6.3. Secci´ on 6 Experimentos En el presente proyecto nos hemos centrado en tres contribucionesprincipales. El planteamiento de un nuevo m´etodo de clasificaci´on de l´ıneas y puntos de fuga a partir de l´ıneas extra´ıdas de una imagen catadi´optrica. Desarrollo de un algoritmo innovador para extraer suelos y paredes de la escena bajo estudio. Ampliaci´on del algoritmo anterior para aplicarlo de forma secuencial mediante el uso de homograf´ıas para conseguir resultados m´as homog´eneos. En este cap´ıtulo se van a evaluar los resultados obtenidos para cada una de estas tres aportaciones utilizando la base de datos puesta a disposici´on por el proyecto COGNIRON [26], que se puede descargar libremente en su p´agina web. Las im´agenes omnidireccionales disponibles en esta base de datos han sido tomadas por una c´amara con espejo hiperb´olico dispuestos sobre un robot m´ovil conducido a trav´es un entorno de interior. La calibraci´on de la c´amara omnidireccional y los datos de obtenidos de un laser, sonar y odometr´ıa de los sensores del robot tambi´en est´an disponibles. Una buena caracter´ıstica de esta base de datos es que el objetivo de la c´amara oculta solamente una peque˜ na parte del centro de la imagen y al recorrer habitaciones amplias los l´ımites entre las paredes y suelo son visibles, lo que permite su detecci´on. ´ Esta cuenta con una gran variedad de escenarios, de los que se han elegido im´agenes de forma aleatoria para comprobar la eficacia de los algoritmos desarrollados y al no contar con un groundtruth con el que poder comparar los resultados obtenidos, hemos creado uno etiquetando de forma manual las fotos sobre las que hemos ejecutado nuestro m´etodo. En esta secci´on se presentan diversos resultados representativos, mientras que en el anexo F se muestran los resultados adicionales de una experimentaci´on m´as extensa. 59 60 6.1. Evaluaci´ on del nuevo m´ etodo para clasificaci´ on de l´ıneas 6.1. Evaluaci´ on del nuevo clasificaci´ on de l´ıneas m´ etodo para A continuaci´on se muestran distintos resultados obtenidos de aplicar los m´etodos introducidos en el cap´ıtulo 3. Obs´ervese c´omo el primer m´etodo (clasificaci´on de l´ıneas sobre la imagen) no consigue unos resultados tan robustos como los otros dos, sin embargo el tiempo de ejecuci´on es considerablemente bajo, siendo ´este de alrededor de 1 segundo. Por otro lado, el segundo (clasificaci´on sobre la esfera) y tercer m´etodo (el propuesto en este trabajo) consiguen resultados bastante similares, siendo el factor clave en su diferenciaci´on el tiempo de ejecuci´on. Mientras que el m´etodo n´ umero dos consume alrededor de 100 segundos por foto, nuestro algoritmo logra una clasificaci´on de l´ıneas igual de buena en tan solo 0.5 segundos. Adem´as el m´etodo propuesto asegura perfecta ortogonalidad, de forma que siempre vamos a encontrar las l´ıneas pertenecientes a las 3 direcciones principales. Sin embargo, debido a la forma en la que esta programado, el m´etodo dos puede realizar clasificaciones err´oneas en algunos casos al detectar ambos puntos de fuga X e Y en el mismo lugar, como se puede ver en la imagen de la fila 4 en la figura 6.1. 6.2. Evaluaci´ on de la recuperaci´ on estructural con una imagen Algunos de los resultados1 en diferentes tipos de escenas de interior son mostrados en la figura 6.2. Los dos primeros ejemplos corresponden a pasillos con forma T y L (c´omo los que se describen en la figura 4.3 de la secci´on 4.1.2), las paredes no est´an muy saturadas de objetos, por lo que los resultados son precisos. En el segundo ejemplo cabe destacar que se observa una esquina oculta en la parte superior de la imagen. La tercera foto est´a tomada en una habitaci´on cuyas paredes son de cristal (partes superior e inferior de la imagen); debido a este tipo de paredes aparecen zonas muy brillantes en la escena, pero a´ un con esta dificultad se consigue una buena aproximaci´on de la estructura. En el cuarto caso se muestra un recibidor con un escritorio y una estanter´ıa. Nuestro algoritmo es capaz de reconocer estos obst´aculos, sin embargo, no llega a detectar la puerta abierta que se encuentra en la parte superior de la imagen, probablemente debido al exceso de iluminaci´on que entra a trav´es de ´esta. 1 En el anexo F se pueden encontrar m´as resultados. 6. Experimentos 61 Figura 6.1: Comparativa entre los tres m´etodos presentados en el cap´ıtulo 3 aplicado a cinco im´agenes diferentes. (a) Clasificaci´on sobre imagen catadi´optrica. (b) Clasificaci´on sobre la esfera. (c) M´etodo propuesto. 62 6.2. Evaluaci´ on de la recuperaci´ on estructural con una imagen Figura 6.2: Ejemplos experimentales obtenidos para 5 escenas diferentes. (a) Imagen original. (b) Clasificaci´on de l´ıneas y extracci´on de puntos que votar´ an en la elecci´on de bordes. (c) Salida final de nuestro algoritmo. (d) Resultado deseado, etiquetado manualmente. La u ´ltima escena corresponde a una habitaci´on abarrotada de muebles y objetos, los colores son muy oscuros, lo que dificulta la extracci´on de l´ıneas en algunas ´areas. A su vez, muchas de las l´ıneas m´as largas y mejor definidas recaen sobre objetos rectos como son las mesas, lo que podr´ıa llevar a una mala identificaci´on de la estructura, pero como podemos ver los resultados obtenidos son bastante buenos. 6. Experimentos 63 Tabla 6.1: Valores de del rendimiento obtenidos para las im´agenes mostradas en la Fig. 6.2 Precision Recall F1 Image1 0.973 0.887 0.928 Image2 0.984 0.969 0.977 Image3 0.896 0.992 0.942 Image4 0.964 0.937 0.950 Image5 0.904 0.878 0.891 Para comparar los resultados de nuestro algoritmo, hemos generado a mano una serie de resultados deseados. Definimos como verdaderos positivos (tp) el numero de p´ıxeles que ambas tienen en com´ un, falsos positivos (fp) al n´ umero de p´ıxeles identificados como suelo por nuestro m´etodo, pero que no corresponden al suelo en el ground truth, y falsos negativos (fn) al n´ umero de p´ıxeles que no son identificados como suelo cuando el ground truth muestra que s´ı que tendr´ıan que tp tp ), recall ( tp+f ) ser. A partir de estos valores, podemos calcular precision ( tp+f p n 2 precision recall y F1 ( precision+recall ) para varias im´agenes, Tabla H.1. 6.3. Evaluaci´ on del m´ etodo mediante aplicaci´ on de homograf´ıas Por u ´ltimo, con el objetivo de mejorar los resultados obtenidos a partir de una sola imagen se aplican homograf´ıas, de forma que varias im´agenes de una secuencia son comparadas entre s´ı y comparten informaci´on para conseguir resultados m´as robustos y homog´eneos. A continuaci´on se muestran dos secuencias de ejemplo. La primera secuencia 6.3 cuenta con 7 im´agenes consecutivas donde se aprecia como al aplicar las homograf´ıas los resultados finales obtenidos permanecen casi inalterados. En realidad si que existen peque˜ nas variaciones en estos resultados pero al haber tan poca variaci´on entre im´agenes resultan casi imperceptibles. La segunda secuencia 6.4 est´a compuesta por 14 im´agenes consecutivas. En este caso se seleccionan las im´agenes pertenecientes a una zona de transici´on donde la forma del pasillo en el que nos encontramos cambia de tener forma en T a tener una forma lineal en I. Se puede observar como las primeras im´agenes de la secuencia encajan con la forma del pasillo pero al irnos introduciendo en la zona de transici´on el proceso secuencial intenta conservar la forma inicial del pasillo lo que ocasiona unos resultados err´oneos en la etapa inicial (im´agenes 10, 11 y 12 de la secuencia), aunque r´apidamente reconocemos el cambio de habitaci´on y la hip´otesis del resultado cambia adapt´andose a los nuevos contornos. 64 6.3. Evaluaci´ on del m´ etodo mediante aplicaci´ on de homograf´ıas Figura 6.3: Secuencia de 7 im´agenes seguidas. La primera fila muestra resultados obtenidos sin aplicar la homograf´ıa. En la segunda fila se puede ver c´omo incluyendo el uso de las homograf´ıas los resultados son m´as homog´eneos y se corrigen los posibles errores de las hip´otesis originales. Figura 6.4: Las dos primeras filas muestran una secuencia de 14 im´agenes sin aplicar homograf´ıa. N´otese como rojo y verde alterna entre im´agenes por no poder asegurar concordancia entre puntos de fuga. Las dos filas inferiores muestran la misma secuencia al aplicar la homograf´ıa. Aqu´ı se puede observar como las paredes conservan el mismo c´odigo de colores. Las u ´ltimas im´ agenes muestran transici´on entre pasillo en T y pasillo en I. Pese a los posibles errores que se ocasionan en las transiciones entre habitaciones, los resultados obtenidos al aplicar el proceso secuencial de homograf´ıas implican una mejora considerable en la precisi´on del m´etodo. Obs´ervese como en la figura 6.4 las primeras im´agenes de la secuencia en la que 6. Experimentos 65 no se aplica homograf´ıa difieren considerablemente de una a otra. Sin embargo, con el uso de las homograf´ıas es posible eliminar los errores de identificaci´on de la estructura de la escena de forma que se obtienen unos resultados mucho m´as robustos. Adem´as este proceso puede ser programado en paralelo, de forma que mientras se pondera la informaci´on de la imagen actual con el resto de im´agenes de la secuencia, al mismo tiempo se puede ir extrayendo la hip´otesis de contorno de la siguiente imagen. 66 6.3. Evaluaci´ on del m´ etodo mediante aplicaci´ on de homograf´ıas Secci´ on 7 Conclusiones El objetivo de este proyecto fin de carrera ha sido desarrollar un algoritmo capaz de extraer la estructura 3D de una imagen omnidireccional tomada en entornos de interior. Para ello, se parte del trabajo realizado por Didem [23] sobre el mismo tema pero con un distinto planteamiento al presentado en ese proyecto. A su vez, se cuenta con dos m´etodos aplicables a la detecci´on y clasificaci´on de l´ıneas, uno dise˜ nado por [5] y otro desarrollado por compa˜ neros del laboratorio de la Universidad de Zaragoza [8], ambos accesibles en forma de utilidades para Matlab, a partir de los cuales se desarrolla el resto de este proyecto. Se ha generado nuevo c´odigo optimizado con el que realizar extracci´on y clasificaci´on de l´ıneas y puntos de fuga para im´agenes catadi´optricas, y se propone un nuevo m´etodo para la detecci´on de la distribuci´on estructural de una escena. Como resultados se present´o un art´ıculo de investigaci´on a la conferencia internacional “12th International Conf erence on Intelligent Autonomous Systems”[22], que ha sido aceptado y ser´a presentado entre el 26 y 29 de junio del 2012. Adicionalmente, se ha desarrollado un nuevo algoritmo que mediante el uso de homograf´ıas permite propagar a lo largo de una secuencia de im´agenes los resultados obtenidos por el m´etodo anterior de forma que corrige posibles fallos de ´este y consigue resultados m´as robustos y homog´eneos ´ para una c´amara en movimiento. Esta ampliaci´on ha sido presentada a las “XXXIII Jornadas N acionales de Autom´ atica”[21] y estamos pendientes de su aceptaci´on. El trabajo desarrollado en [23] se fundamenta en la localizaci´on de esquinas, definidas como los puntos geom´etricos donde intersectan varios segmentos horizontales entre s´ı, u horizontales con verticales. Posteriormente, se buscan posibles combinaciones entre estas esquinas para generar hip´otesis del ´area donde se encuentra el suelo de la escena observada. Las esquinas que definen el contorno del suelo son dif´ıciles de encontrar sobre la imagen, y al contrario, esquinas que 67 68 no pertenecen al contorno del suelo, como pueden ser esquinas de objetos que aparecen en la imagen, son detectables f´acilmente. Esto hace que el m´etodo tenga dificultades a la hora de conseguir una buena clasificaci´on y los procesos de iteraci´on entre todas las combinaciones de esquinas posibles hace que el proceso sea muy lento. Estos inconvenientes son la principal motivaci´on para buscar un m´etodo alternativo que consiga una extracci´on de los contornos de la escena precisa y se ejecute en un tiempo reducido de forma que sea posible incorporarlo en sistemas de navegaci´on en tiempo real. Para conseguir este objetivo se comienza por el dise˜ no de un nuevo m´etodo de clasificaci´on de las l´ıneas extra´ıdas mediante el c´odigo aportado por [6]. En primer lugar se realizan una serie de modificaciones por las que ajustar los par´ametros de la c´amara utilizada, de forma que las ecuaciones, en un principio dise˜ nadas para sistemas para-catadi´optricos, se reescriben para ser utilizadas por sistemas hipercatadi´optricos, con lo que se gana generalidad en el m´etodo. El segundo paso es la implementaci´on de un sistema original para clasificar las l´ıneas y los puntos de fuga aprovechando las propiedades geom´etricas de estas l´ıneas. En el cap´ıtulo 3.3 se muestra como ´este nuevo m´etodo consigue resultados similares de clasificaci´on mejorando notablemente el tiempo de ejecuci´on. Es importante resaltar que en el m´etodo propuesto se parte de la hip´otesis de verticalidad de la c´amara, condici´on que se cumple en la gran mayor´ıa de escenarios d´onde la c´amara va montada sobre un veh´ıculo. Si esta condici´on no se cumpliese aumentan los grados de libertad y el coste computacional, pero el m´etodo propuesto podr´ıa ser tambi´en utilizado. Como el resultado buscado es la creaci´on de un mapa de navegabilidad denso pr´oximo a la posici´on actual , y no un algoritmo qde estimaci´on de un mapa (SLAM), en la segunda parte del proyecto se presenta un m´etodo innovador aprovechando las caracter´ısticas de las im´agenes catadi´optricas para llevar a cabo la detecci´on de la estructura de la escena. Mediante un estudio de im´agenes en diversas situaciones, se llega a la conclusi´on de que los segmentos de l´ıneas horizontales extra´ıdos son demasiado abundantes y es dif´ıcil reconocer cuales son los importantes. Al contrario, la gran mayor´ıa de los segmentos correspondientes a l´ıneas verticales est´an bien definidos, y se cumple la caracter´ıstica de que habitualmente nacen desde la regi´on que separa pared y suelo. Por esta raz´on se le da especial importancia a ´este tipo de l´ıneas, y a partir de ´estas y de un conjunto de consideraciones geom´etricas que caracterizan las na una secuencia de procesamiento de la im´agen im´agenes catadi´optricas, se dise˜ para conseguir extraer un contorno sobre la imagen, que define los l´ımites entre pared y suelo de la escena real. Hay que tener en cuenta que los objetos distribuidos a lo largo de la habitaci´on pueden generar gran variedad de esquinas, las cuales son 7. Conclusiones 69 dif´ıciles de detectar de forma autom´atica, por lo que el m´etodo propuesto busca las fronteras que mejor encajen pero a su vez tengan la geometr´ıa m´as sencilla posible. Los resultados obtenidos por el algoritmo desarrollado que utiliza una u ´ nica imagen son bastante buenos, pero en ocasiones, se cometen errores en ciertas im´agenes debido a que la extracci´on de l´ıneas usando el detector Canny [10] no siempre es precisa, por lo que el ruido en la imagen o la omisi´on de segmentos detectados es inevitable. Por ello, el siguiente paso de nuestra propuesta consiste en propagar el algoritmo desarrollado sobre una secuencia de im´agenes tomadas por una c´amara en mvoimiento. De esta manera, las escenas en las que la regi´on del suelo ha sido bien interpretado ayudaran a compensar aquellas en las que se han introducido errores. Este proceso de propagaci´on sobre la secuencia de im´agenes se lleva a cabo mediante homograf´ıas que se calculan a partir de l´ıneas correspondientes entre las im´agenes. De esta forma, se parte de informaci´on ya disponible y no se mal emplea tiempo ni memoria en la adquisici´on de informaci´on adicional con funcionalidad exclusiva en este proceso. Se observa como al incluir esta parte al algoritmo los resultados mejoran considerablemente. Los experimentos se han realizado sobre la base de datos disponible en Internet, COGNIRON [26], que cuenta con una gran diversidad de escenarios lo que permite comprobar el rendimiento y robustez del m´etodo propuesto. 70 Trabajo futuro Como trabajo futuro se podr´ıan considerar diferentes bases de datos para comprobar la robustez del m´etodo ante im´agenes tomadas por diferentes tipos de c´amaras y en diferentes tipos de entornos. Adicionalmente, pueden ampliarse las restricciones geom´etricas empleadas para llevar a cabo la detecci´on de la distribuci´on estructural a partir de una u ´nica imagen, para reducir errores y ser capaces de detectar objetos o elementos que se encuentren en orientaciones diferentes a las tres direcciones principales de la escena. Una vez determinados los l´ımites entre las paredes con el suelo, y conocida la altura a la que se encuentra la c´amara del sistema catadi´optrico que toma las im´agenes, es posible determinar la posici´on 3D de los puntos de la escena. De esta manera, podr´ıamos convertir la representaci´on circular de navegabilidad de este tipo de im´agenes, en un modelo 3D a escala, que aplicado a una secuencia completa de im´agenes podr´ıa llegar a representar un mapa del interior de un edificio. ´Indice de figuras 1.1. Casco con c´amara omnidireccional para tareas de asistencia personal. . . . . . 10 1.2. Recuperaci´on estructural de una escena en im´agenes convencionales [25]. Resultado etiquetado manualmente. . . . . . . . . . . . . . . . . . . . . 11 1.3. Ejemplo de sistema catadi´optrico central con espejo hiperb´olico. El primer foco, F1, est´a situado dentro del espejo, y el segundo foco, F2, coincide con el centro ´optico dentro de la lente. . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4. Comparaci´on entre imagen tomada por una c´amara convencional y una c´amara omnidireccional donde se pueden observar las caracter´ısticas definidas en la literatura. Ambas fotos tomadas en la plaza de las Ingenier´ıas, que separa el edificio Torres Quevedo y el edificio Betancourt. . . . . . . . . . . . . . . . 13 1.5. Esquema de las etapas principales del algoritmo desarrollado junto a los procesos m´as importantes de cada una. . . . . . . . . . . . . . . . . . . . . . . . 15 2.1. Modelo de la Esfera para sistemas catadi´optricos. . . . . . . . . . . . . . . 18 2.2. Pasos de la proyecci´on del Modelo de la Esfera. . . . . . . . . . . . . . . . 20 2.3. Proyecci´on de una recta mediante el modelo de la esfera. . . . . . . . . . . . 21 3.1. Resultados de Clasificaci´on sobre la Imagen: (a) Componentes conectados (colores vivos) junto a las c´onicas que los aproximan (azul). (b) Clasificaci´on de los elementos conectados seg´ un direcciones principales. En este caso se detectan 4, pero u ´nicamente tres son representativas: Verticales(azul), Horizontales en X (rojo), Horizontales en Y (verdes). . . . . . . . . . . . . . . . . . . . . . 26 3.2. Resultados de Clasificaci´on sobre la Esfera Unitaria: (a) Componentes conectados (colores vivos) junto a las c´ onicas que los aproximan (azul). (b) Clasificaci´on de los elementos conectados seg´ un direcciones principales. Verticales(azul), Horizontales en X (rojo), Horizontales en Y (verdes). . . . . . . . . . . . . . . 135 28 ´INDICE DE FIGURAS 136 3.3. En la imagen de la izquierda se representan 3 trazos en la misma direcci´on de la 3.4. base Eucl´ıdea (e1 ,e2 ,e3 ) los cuales se proyectan en la esfera mediante planos de proyecci´ on representados por las normales (n⊥e1 , n⊥e2 , n⊥e3 ) respectivamente y se muestran como un punto de su color. En las dos siguientes im´ agenes se ense˜ na como quedar´ıa una posible distribuci´on de varias normales proyectadas sobre la esfera ante caso Eucl´ıdeo y caso general dada una rotaci´on R. . . . . 30 Izquierda: Distribuci´ on de las normales sobre la esfera unitaria a partir de datos reales. Derecha: Clasificaci´on de las normales de la izquierda seg´ un las 3 direcciones principales. Los puntos gordos corresponden a la intersecci´ on entre grandes c´ırculos, es decir, los puntos de fuga. . . . . . . . . . . . . . . . . 31 3.5. Comparaci´on entre la clasificaci´on obtenida por los m´etodos descritos. (a) Clasificaci´on sobre imagen catadi´ optrica, tiempo en clasificar 1.5 sec. (b) Clasificaci´on sobre la esfera, tiempo en clasificar 120 sec. (c) M´etodo propuesto, tiempo en clasificar 0.5 sec . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.1. Ejemplo de una imagen tomada con un sistema hipercatadi´optrico y el resultado 4.2. 4.3. 4.4. deseado despu´es de aplicar el algoritmo. En la imagen, el color azul representa el suelo, el color rojo representa paredes paralelas en una direcci´ on dominante, y el color verde paredes paralelas en una direcci´on dominante ortogonal a la anterior. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Discretizaci´ on de l´ıneas en puntos. Se puede apreciar como solo las l´ıneas horizontales (rojas y verdes) cercanas a las verticales (azules) son incluidas en el proceso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Formas m´as comunes de los suelos presentes en escenas de interior. La zona . . . . . . . . . . sombreada en rojo representa el cuadrado b´ asico central. 36 Imagen virtual simulando la hip´otesis de cuatro paredes. Se pueden observar las 4 regiones definidas al segmentar la imagen mediante las l´ıneas imaginarias que unen los puntos de fuga. . . . . . . . . . . . . . . . . . . . . . . . . 37 4.5. Puntos de los grupos GZ (azul), GX (rojo) and GY (verde) separados para los 4 posibles casos. Los segmentos discontinuos rojo y verde son las l´ıneas imaginarias que unen los respectivos VPs y dividen la imagen en dos partes. . . . . . . . 38 4.6. A la izquierda se muestran las c´onicas generadas m´as votadas para uno de los cuatro casos. En la imagen central se pueden observar todas las c´onicas extra´ıdas donde cada color representa cada uno de los casos. La foto de la derecha corresponde con el resultado obtenido para la primera hip´otesis de 4 paredes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 ´INDICE DE FIGURAS 137 4.7. A la izquierda: resultado obtenido para la primera hip´otesis de 4 paredes d´onde se ven los bordes B1 , B2 , B3 y B4 que definen 4 sectores. A la derecha: Ampliaci´on del sector 2, d´onde se observan las c´onicas seleccionadas (verde) y las no seleccionadas (blanco) candidatas a generar la secci´on que expandir´a el suelo. Notar c´omo la correcta combinaci´on entre B2 dos c´onicas laterales y una central (marcado en amarillo) conforman una expansi´on perfecta. . . . . . . 4.8. Diagrama de flujo seguido para por el algoritmo para obtener la hip´otesis final. 4.9. 1)Ampliaci´on del primer sector. 2a)Primera hip´otesis del segundo sector, al haber inliers en el interior hay que reducir. 2b)Segunda hip´otesis del sector 2, esta vez corresponde con la ampliaci´ on. 3)Ampliaci´on del tercer sector. 4)No se encuentran ampliaciones, esto es debido a que el borde ya estaba en el lugar correcto. F)Hip´otesis final despu´es de las ampliaciones de las cuatro caras. . . . 5.1. 5.2. 5.3. Homograf´ıa entre dos puntos de vista O y O∗ . 41 42 43 . . . . . . . . . . . . . . . 46 Caracter´ısticas extra´ıdas y posibles emparejamientos entre im´agenes de una escena tomadas desde posiciones distintas despu´es de aplicar la m´ascara. . . . 49 Emparejamientos votantes de la homograf´ıa ganadora. Los c´ırculos rojos corresponden a las caracter´ısticas detectadas en la imagen actual. Los puntos verdes son los emparejamientos obtenidos al aplicar la homograf´ıa H a sus correspondientes obtenidos desde el otro punto de vista (figura 5.2). . . . . . 51 5.4. Resultados de homograf´ıas. En la primera imagen se muestra la hip´otesis de suelo (en rojo) para una imagen I. En el resto de figuras, se muestra la hip´ otesis∗ de suelo (en blanco) seg´ un la imagen I ∗ observada de una posici´on desplazada con respecto a I. En rojo se adjunta el resultado de aplicar diversas homograf´ıas que transforman la hip´ otesis desde la imagen I a la imagen I ∗ . La escena de arriba a la derecha muestra el resultado de aplicar una homograf´ıa donde la similitud es alta. Las im´agenes de la fila inferior corresponden a homograf´ıas fallidas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.5. Contorno de la hip´otesis de una imagen I discretizado en N puntos. Se aplica homograf´ıa Hi y se calcula la distancia entre puntos con la ecuaci´on 5.13 para comprobar cuan buena es esta homograf´ıa. . . . . . . . . . . . . . . . . . 55 5.6. Izquierda. Ejemplo de una hip´otesis con defectos (el suelo abarca zonas que deber´ıan ser pared). Centro: Sobre la hip´otesis de suelo actual (negro) se proyectan hip´otesis de im´agenes anteriores, y se elige la que m´as concuerda con el resto del conjunto(rojo). Derecha: Se promedia la hip´otesis ganadora (rojo) con las cercanas para dar el resultado final. . . . . . . . . . . . . . . . . . 56 6.1. Comparativa entre los tres m´etodos presentados en el cap´ıtulo 3 aplicado a cinco im´agenes diferentes. (a) Clasificaci´on sobre imagen catadi´optrica. (b) Clasificaci´on sobre la esfera. (c) M´etodo propuesto. . . . . . . . . . 61 138 ´INDICE DE FIGURAS 6.2. Ejemplos experimentales obtenidos para 5 escenas diferentes. (a) Imagen original. (b) Clasificaci´on de l´ıneas y extracci´on de puntos que votar´ an en la elecci´on de bordes. (c) Salida final de nuestro algoritmo. (d) Resultado deseado, etiquetado manualmente. . . . . . . . . . . . . . . . . . . . . 62 6.3. Secuencia de 7 im´agenes seguidas. La primera fila muestra resultados obtenidos sin aplicar la homograf´ıa. En la segunda fila se puede ver c´omo incluyendo el uso de las homograf´ıas los resultados son m´as homog´eneos y se corrigen los posibles errores de las hip´otesis originales. . . . . . . . . . . . . . . . . . . . . . . 64 6.4. Las dos primeras filas muestran una secuencia de 14 im´agenes sin aplicar homograf´ıa. N´otese como rojo y verde alterna entre im´agenes por no poder asegurar concordancia entre puntos de fuga. Las dos filas inferiores muestran la misma secuencia al aplicar la homograf´ıa. Aqu´ı se puede observar como las paredes conservan el mismo c´odigo de colores. Las u ´ltimas im´agenes muestran transici´on entre pasillo en T y pasillo en I. . . . . . . . . . . . . . . . . . 64 A.1. Figura con los par´ametros que definen la hip´erbola. . . . . . . . . . . . . . A.2. Descripci´on gr´afica del par´ametro b. . . . . . . . . . . . . . . . . . . . . A.3. Definici´on gr´afica de los par´ametros p y d. . . . . . . . . . . . . . . . . . 73 75 76 B.1. Representaci´on de sistema catadi´optrico central donde todos los rayos incidentes pasan por el foco del espejo hiperb´olico. De izquierda a derecha: Espejo parab´olico, el´ıptico e hiperb´olico. . . . . . . . . . . . . . . . . . . . . . . B.2. Imagen gen´erica de la reflexi´on de un rayo sobre un espejo. . . . . . . . . . C.1. Proyecci´on de un punto en la imagen utilizando un modelo de espejo hiperb´olico. De los dos puntos generados (xIM1 , xIM2 ) solo uno es f´ısicamente correcto. . . C.2. Equivalencia entre modelo de la esfera unitaria y el m´etodo de proyecci´on empleando un espejo hiperb´olico. . . . . . . . . . . . . . . . . . . . . . . D.1. Intersecci´on de la proyecci´on de dos rectas del espacio en dos puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . plano. D.2. Intersecci´on de dos c´onicas en cuatro puntos y el tri´angulo autopolar. D.3. Intersecci´on de la proyecci´on de dos rectas del espacio en dos puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . plano. 79 80 86 88 en el n- . . . . . . . . . 97 98 en el n- . . . . . 101 E.1. Pir´amide gaussiana compuesta por 5 escalas y 6 octavas. . . . . . . . . . . E.2. Pir´amide de diferencia de gaussianas. . . . . . . . . . . . . . . . . . . . . E.3. En rojo: P´ıxel en estudio. En verde: Vecinos en escala actual. En amarillo: Vecinos de escala anterior y posterior. . . . . . . . . . . . . . . . . . . . E.4. Keypoints detectados (en verde). . . . . . . . . . . . . . . . . . . . . . . E.5. En verde: Keypoints iniciales. En rojo: Keypoints no descartados. . . . . . . 104 105 106 106 108 ´INDICE DE FIGURAS 139 E.6. Arriba: Ventana 16x16 alrededor del keypoint. Abajo izquierda: m(x,y). Abajo derecha: θ(x,y). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 E.7. Izquierda: Regi´on de gradientes 16 × 16. Centro: Ventana circular gaussiana. Derecha: Histograma final del keypoint. . . . . . . . . . . . . . . . . . . . 110 E.8. Izquierda: Subdivisiones 4x4. Centro: Ventanas circulares gaussianas. Derecha: Descriptor compuesto por 16 histogramas de 8 celdas. . . . . . . . . . . . . 111 F.1. Ejemplos experimentales obtenidos para 4 corredores. Fila 1: Transici´on entre pasillo y habitaci´on. Fila 2) Corredor vertical. Fila 3) Pasillo horizontal con gran diferencia de luminosidad. Fila 4) Corredor saturado de objetos y decoraci´on en las paredes. . . . . . . . . . . . . . . . . . . F.2. Ejemplos experimentales obtenidos para 4 pasillos con formas complejas. Fila 1: Pasillo con desviaci´on hacia abajo y unas escaleras (amarillo) que no pertenecen a ninguna direcci´on dominante. Fila 2) Punto de encuentro entre varios corredores. Fila 3) Final de un pasillo que se bifurca en otros dos cuyas amplitudes son distintas. Puerta semiabierta (amarillo) no pertenece a direcciones principales. Fila 4) Pasillo con desviaci´on hacia abajo y muy saturado de objetos. . . . . . . . . . . . . . . . . . . . . F.3. Ejemplos experimentales obtenidos para 5 escenas de habitaciones. Fila 1: Habitaci´on con cristaleras y diferencias de iluminaci´on. Fila 2) Sala con impresora cuyas l´ıneas pueden confundirse con las del suelo . Fila 3) Habitaci´on con columna en el centro. Fila 4) Biblioteca con mesas y sillas donde las direcciones principales no est´an muy claras. Fila 5) Comedor con muchos objetos y l´amparas colgadas en el techo. . . . . . . . . . . F.4. Cuatro ejemplos donde se dan fallos en la obtenci´on de la distribuci´on estructural. Fila 1) Se confunde el suelo con la l´ınea de una mesa en la parte superior de la imagen. Fila 2) Se detectan demasiadas l´ıneas ruidosas en el suelo, lo que provoca pensar que el corredor es m´as estrecho de lo que en realidad es. Fila 3) No se detecta la columna situada en el centro de la imagen. Fila 4) En este pasillo la pared que conforma la parte inferior de la imagen est´a muy saturada de l´ıneas, y al no extraer bien la l´ınea que define el l´ımite entre pared y suelo, se genera una ampliaci´on en el proceso de expansi´on que no deber´ıa haberse realizado. La mayor´ıa de estos errores ser´an eliminados mediante la aplicaci´on de homograf´ıas. 114 115 116 117 H.1. In the sphere model, every line from the image is represented by its normal on the sphere. The figure represents the sphere where each point corresponds to a normal vector (Colorcode: X=Red, Y=Green, Z=Blue). From left to right: Sphere with perfect data; Sphere of a real image; classification of the previous data using our algorithm in the horizontal plane. Big dots represent VPs. . . . . . . . . . . . . . . . . . . . . . . 125 ´INDICE DE FIGURAS 140 H.2. Left: Lines extracted by Canny Edge detector after pruning step. Right: H.3. H.4. H.5. H.6. H.7. Same lines grouped in the 3 dominant directions according to our classification. Big dots represent VPs. . . . . . . . . . . . . . . . . . . Left: Selection of points as explained in Section H.3.1. Right: Graphic explanation for distance measurement between point and conic in Section H.3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Most common room/hall shapes (top view). Red grid represents the basic square we are seeking in section H.3.3. . . . . . . . . . . . . . . . . . First two images show points from groups GZ , GX and GY under constraints exposed in section. H.3.3, where blue, red and green dots correspond to GZ , GX and GY points respectively. Dashed red and green lines are the imaginary lines, going through the VPs, which divide the image in 2 parts. Finally, black conics represent the most voted boundaries for each case. Right image shows the result of combining those boundaries to generate the first hypothesis. . . . . . . . . . . . . Left: Synthetic example depicting the possible cases (B1 and B2 are expandable regions, B3 will not be expanded, and B4 corresponds to an occluded corner). Black line represents the actual room boundaries, first hypothesis in dashed blue, and final expansions in dashed red. Right: final result of a real example. . . . . . . . . . . . . . . . . . . . . . . Examples of experimental results obtained for five different images. (a)Input images. (b) Line classification and extracted points which vote for boundary selection. (c) Output images by our algorithm. (d) Ground truth, manually labeled. . . . . . . . . . . . . . . . . . . . . . . . . . 126 128 129 130 131 133 ´Indice de tablas 2.1. Par´ametros del espejo para el modelo de la esfera . . . . . . . . . . . . . . 18 6.1. Valores de del rendimiento obtenidos para las im´agenes mostradas en la Fig. 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 A.1. Par´ametros de la hip´erbola . . . . . . . . . . . . . . . . . . . . . . . . . 77 H.1. Performance values obtained for images of Fig. H.7 . . . . . . . . . . . 132 141 142 ´INDICE DE TABLAS Bibliograf´ıa [1] S. Baker and S. K. Nayar. A theory of single-viewpoint catadioptric image formation. International Journal of Computer Vision, 35:175–196, 1999. [2] J. Barreto. General Central Projection Systems: Modeling, Calibration and Visual Servoing. PhD thesis, 2003. [3] J. P. Barreto and H. Araujo. Issues on the geometry of central catadioptric image formation. In IEEE Conf. on Computer Vision and Pattern Recognition, pages 422–427, 2001. [4] J. C. Bazin, Y. Jeong, P. Y. Laffont, I. S. Kweon, C. Demonceaux, and P. Vasseur. An original approach for automatic plane extraction by omnidirectional vision. In IEEE/RSJ Int. Conf. on Int. Robots and Systems, pages 752–758, 2010. [5] J. C. Bazin, I. Kweon, C. Demonceaux, and P. Vasseur. Rectangle extraction in catadioptric images. In International Conference on Computer Vision, pages 1–7, 2007. [6] J. C. Bazin, I. Kweon, C. Demonceaux, and P. Vasseur. A robust top-down approach for rotation estimation and vanishing points extraction by catadioptric vision in urban environment. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 346–353, 2008. [7] S. Benhimane and E. Malis. Homography-based 2d visual servoing. In ICRA, pages 2397–2402, 2006. [8] J. Bermudez, L. Puig, and J. J. Guerrero. catadioptric systems. In OMNIVIS, 2010. Line extraction in central hyper- [9] J. Bermudez-Cameo, L. Puig, and J. J. Guerrero. Hypercatadioptric line images for 3d orientation and image rectification. Robotics and Autonomous Systems, 60(6):755–768, 2012. [10] J. F. Canny. A variational approach to edge detection. In AAAI, pages 54–58, 1983. [11] J. M. Coughlan and A. L. Yuille. Manhattan world: Compass direction from a single image by bayesian inference. In Int. Conf. on Computer Vision, pages 941– 947, 1999. 143 144 BIBLIOGRAF´IA [12] J. Enebral Gonz´alez. Detection and automatic keypoint association in different applications. Universiat Politecnica de Catalunya, 2009. [13] C. Geyer and K. Daniilidis. A unifying theory for central panoramic systems and practical applications. In ECCV (2), pages 445–461, 2000. [14] J. J. Guerrero and C. Sag¨ u´es. From lines to homographies between uncalibrated images. In IX Spanish Symposium on Pattern Recognition and Image Analysis, pages 233–240, 2001. [15] H. Hadj-Abdelkader, Y. Mezouar, N. Andreff, and P. Martinet. Decoupled homography-based visual servoing with omnidirectional cameras. In IROS, pages 2332–2337, 2006. [16] R. I. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press, second edition, 2004. [17] V. Hedau, D. Hoiem, and D. Forsyth. Recovering the spatial layout of cluttered rooms. In IEEE International Conference on Computer Vision, pages 1849–1856, 2009. [18] D. Lee, M. Hebert, and T. Kanade. Geometric reasoning for single image structure recovery. In IEEE Conference on Computer Vision and Pattern Recognition, pages 2136–2143, June 2009. [19] G. L´opez-Nicol´as, J. J. Guerrero, and C. Sag¨ u´es. Multiple homographies with omnidirectional vision for robot homing. Robotics and Autonomous Systems, 58(6):773–783, 2010. [20] D. G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004. [21] J. Omedes, G. L´opez-Nicol´as, and J. J. Guerrero. Detecci´ on de suelo y paredes con visi´on monocular para navegaci´ on por interiores. In XXXIII Jornadas de Autom´ atica, pages 1–8, Vigo, Septiembre(enviado), 2012. [22] J. Omedes, G. L´opez-Nicol´as, and J. J. Guerrero. Omnidirectional vision for indoor spatial layout recovery. In 12th IAS Intelligent Autonomous Systems Conference, pages 1–5, Jeju Island, June, 2012. [23] N. D. Ozisik, G. L´opez-Nicol´as, and J. J. Guerrero. Scene structure recovery from a single omnidirectional image. In ICCV Workshops, pages 359–366, 2011. [24] P. Sturm and P. Gargallo. Conic fitting using the geometric distance. In Proceedings of the Asian Conference on Computer Vision, Tokyo, Japan, pages 784–795, 2007. [25] G. Tsai, C. Xu, J. Liu, and B. Kuipers. Real-time indoor scene understanding using bayesian filtering with motion cues. In ICCV, pages 121–128, 2011. BIBLIOGRAF´IA [26] Z. Zivkovic, O. Booij, and B. Krose. From images to rooms. Autonomous Systems, 55(5):411–418, 2007. 145 Robotics and