Repositorio Institucional de Documentos

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´eJes´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 ´unica imagen tomada en el interior de un edificio. Aunque existen m´etodos equivalentes que utilizan im´agenes convencionales, las im´agenes omnidireccionales resultan particularmente ´utiles 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 ´unica 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 9 1.1. Marcodetrabajo ............................ 9 1.2. Estadodelarte ............................. 10 1.3. Objetivos ................................ 13 1.4. Estructura de contenidos ........................ 14 2. El modelo de la esfera 17 2.1. Proyecci´ondeunarecta ........................ 21 3. Extracci´on y clasificaci´on de c´onicas 23 3.1. Clasificaci´on sobre imagen catadi´optrica ............... 25 3.1.1. C´alculo de c´onicas ....................... 25 3.1.2. C´alculodelospuntosdefuga ................. 25 3.2. Clasificaci´on sobre la esfera ...................... 27 3.2.1. C´alculo de c´onicas ....................... 27 3.2.2. C´alculodelospuntosdefuga ................. 27 3.3. M´etodopropuesto............................ 29 4. Obtenci´on de la distribuci´on espacial de una escena 33 4.1. M´etodo jer´arquico de generaci´on de hip´otesis............. 34 4.1.1. Selecci´ondepuntosclave ................... 34 4.1.2. Hip´otesis inicial del contorno central ............. 36 4.1.3. Proceso jer´arquico para generaci´on de hip´otesis ....... 39 5. Aplicaci´on secuencial mediante homograf´ıas 45 5.1. Homograf´ıa ............................... 45 5.1.1. Homograf´ıa a partir de l´ıneas ................. 47 5.2. Selecci´ondeemparejamientos ..................... 48 5.2.1. Emparejamientodepuntos .................. 49 5.2.2. Emparejamiento de l´ıneas ................... 50 5.3. Medida de similitud . .......................... 53 5 6´ INDICE GENERAL 5.4. Hip´otesisponderada .......................... 55 5.5. Propagaci´on de hip´otesis........................ 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´onestructuralconunaimagen...... 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´ondesemi-latus-rectum .................... 75 B. El sistema hipercatadi´optrico como sistema central 79 B.1. Ley de reflexi´on............................. 80 B.2. Soluci´on para espejo hiperb´olico.................... 81 B.2.1. C´alculodelvectornormal ................... 81 B.2.2. Demostraci´on de sistema catadi´optricocentral........ 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´amaraperspectiva .............. 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´oninterna ........................... 89 D.1.1.Casogeneral........................... 91 D.1.2. Configuraci´onsingular ..................... 92 D.2. Distancia de un punto a una c´onica.................. 94 D.2.1.Distanciaalgebraica ...................... 94 D.2.2.Distanciabasadaenelgradiente................ 94 D.2.3. Distancia basada en la l´ıneapolar............... 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 103 E.1. Construcci´on de un espacio de Escalas . ...............103 E.1.1. Diferencia de gaussianas: D(x, y, σ)..............105 E.1.2. Detecci´on de extremos locales . ................105 E.2. Localizaci´ondekeypoints .......................107 E.2.1. Supresi´ondepuntosdebajocontraste ............107 E.2.2. Supresi´ondepuntossituadosenlosbordes..........107 E.3. Asignaci´on de orientaci´on .......................109 E.4. Descriptor de puntos claves ......................110 F. Ampliaci´on de Resultados 113 F.1.Resultadosencorredores........................114 F.2. Resultados en pasillos complejos . ...................115 F.3.Resultadosenhabitaciones.......................116 F.4.Resultadosconfallos ..........................117 G. Manual de usuario 119 H. Art´ıculo IAS 2012 123 H.1.Introduction...............................124 H.2. Vanishing Point Estimation through Line Detection . . . ......125 H.3.HierarchicalLayoutHypothesisMethod................126 H.3.1.SelectionofSetofPoints....................127 H.3.2.GenerationofConics......................127 H.3.3. Initial Boundaries Hypothesis . ................128 H.3.4. Hierarchical Expansion Process . ...............129 H.4.Results..................................131 H.5.ConclusionandFutureWork......................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 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 ξ=0parac´amara perspectiva, ξ=1para 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 Ose 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. La proyecci´on de un punto gen´erico del entorno Xwen un punto ˆx sobre la imagen catadi´optrica, se explica mediante un proceso de tres pasos. Siendo Xwun punto del entorno expresado en coordenadas homog´eneas Xw= (Xw,Y w,Z w,1) respecto a un sistema de referencia absoluto, se le puede asociar un rayo proyectivo xen el sistema de referencia de la c´amara mediante la matriz de proyecci´on P x=PXw=R[I|−C0]Xw(2.1) donde RyCOrepresentan la rotaci´on y el desplazamiento del sistema de coordenadas del modelo con respecto al sistema de coordenadas absolutas. 17 18 ξ ψ Espejo parab´olico 11+2p Espejo hiperb´olico d √d2+4p2 d+2p √d2+4p2 Espejo el´ıptico d √d2+4p2 d−2p √d2+4p2 Espejo plano 0 1 d: distancia entre focos 4p:latus rectum 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 Xwcon el origen de coordenadas O.                    Figura 2.1: Modelo de la Esfera para sistemas catadi´optricos. Sea Sla esfera de radio unidad centrada en el origen de coordenadas O,se calcula la proyecci´on del rayo xsobre la esfera como la intersecci´on de ambos en dos puntos x+yx−, 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 z+ξx2+y2+z2 ⎞ ⎠(2.3) (N´otese que al trabajar con ecuaciones homog´eneas la expresi´on presentada es equivalente a (x)=x √x2+y2+z2 y √x2+y2+z2 y √x2+y2+z2+ξtque es la que se deduce de proyectar la intersecci´on de la esfera a trav´es del centro ´optico Cp). El tercer y ´ultimo paso consiste en aplicar la transformaci´on lineal Hcpara proyectar el plano virtual πque contiene el punto ¯x al plano πIM,paraas´ı obtener el punto final ˆx en coordenadas de la imagen catadi´optrica. ˆx =Hc¯x (2.4) Hc=KcRcMc(2.5) Mc=⎛ ⎝ψ−ξ00 0ξ−ψ0 001 ⎞ ⎠=⎛ ⎝−η00 0η0 001 ⎞ ⎠(2.6) Kc=⎛ ⎝fxsskew u0 0fyv0 001 ⎞ ⎠(2.7) donde Kccontiene los par´ametros intr´ınsecos de la calibraci´on de la c´amara perspectiva: fx=f/k yfy=f/l son el resultado de dividir la distancia focal de la c´amara (f) entre las dimensiones de un pixel (k×l) respectivamente, u0yv0 indican las coordenadas del centro de la imagen, y sskew es la desviaci´on de los ejes, habitualmente cero. Rcrepresenta la orientaci´on de la c´amara respecto al espejo, yMcincluye los par´ametros del espejo ξyψ, que en la pr´actica se sustituyen por un ´unico 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 transformaci´on, se puede expresar: Hc=⎛ ⎝−ηfx0u0 0ηfyv0 001 ⎞ ⎠=⎛ ⎝γx0u0 0γyv0 001 ⎞ ⎠(2.8) En el que γx=−ηfxyγy=ηfyson 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,larelaci´on entre ´este y las coordenadas Eucl´ıdeas de la imagen (u, v) se calcula dividiendo el vector entre la tercera componente. u=ˆx ˆzv=ˆy ˆ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 Hcy por la funci´on no lineal definida en la ecuaci´on 2.9 que proyecta los puntos pertenecientes al plano πen un rayo orientado. −1(¯x)=⎛ ⎜ ⎜ ⎜ ⎝ ¯zξ+√¯z2+(1−ξ2)(¯x2+¯y2) ¯x2+¯y2+¯z2¯x ¯zξ+√¯z2+(1−ξ2)(¯x2+¯y2) ¯x2+¯y2+¯z2¯y ¯zξ+√¯z2+(1−ξ2)(¯x2+¯y2) ¯x2+¯y2+¯z2¯z−ξ ⎞ ⎟ ⎟ ⎟ ⎠(2.9) 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 21 2.1. 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 ry 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,n y,n z,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,n y,n z)T.Obs´ervese que al igual que la recta rest´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 nTx=0. Como vimos anteriormente, x=−1(¯x) entonces nT−1(¯x) = 0. Desarrollando esta expresi´on se llega a una igualdad que puede expresarse de la forma ¯xT¯ Ω¯x = 0 siendo ¯ Ω 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. ¯ Ω=⎛ ⎝n2 x(1 −ξ2)−n2 zξ2nxny(1 −ξ2)nxnz nxny(1 −ξ2)n2 y(1 −ξ2)−n2 zξ2nynz nxnznynzn2 z ⎞ ⎠(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 corta al plano virtual πen una l´ınea c´onica ¯ Ωque coincide con la definida en la ecuaci´on 2.10. Por ´ultimo se aplica la transformaci´on lineal Hcpara obtener la c´onica ˆ Ωque es la proyecci´on de la linea rsobre la imagen catadi´optrica. ˆ Ω=H−T c ¯ ΩH−1 c(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 ´util 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 y clasificaci´on de c´onicas El primer paso para empezar a trabajar con im´agenes, es decidir con qu´etipo 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 COGNIRON [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.0911yde61mmde di´ametro exterior. El par´ametro del espejo seg´un el modelo de la esfera es ξ=0,9337. 1Ver detalles en Anexo A 3. Extracci´on y clasificaci´on de c´onicas 25 3.1. 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 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´aenelcap´ıtulo de resultados 6, y a la rapidez de ejecuci´on, de aqu´ıen adelante se utilizar´aelm´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. M´etodo jer´arquico de generaci´on de hip´otesis 4.1. M´etodo jer´arquico de generaci´on de hip´otesis 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 eYa 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 quetodaslasl´ı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 ´unicamente 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 Lo 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 ´unicamente 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,GYyGZque 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 GZyGXpara buscar c´onicasacadaladodelal´ınea imaginaria (S1 y S3) formada al unir los VPs en direcci´on X(Fig. 4.5 (izquierda)) . Los bordes 2 y 4 definir´an los bordes con orientaci´on Y,ylasc´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 VPs en direcci´on Y(S2 y S4) usando los puntos de los grupos GZyGY(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,GZreci´en formados. El producto vectorial entre un VP y cualquiera de los puntos pigenera un vector normal ni, que define una c´onica Ω, obteniendo finalmente  Ω despu´es de la transformaci´on proyectiva HC[2]: ni=⎛ ⎝ nix niy niz ⎞ ⎠=⎛ ⎝ VPS x VPS y VPS z ⎞ ⎠×⎛ ⎝ PS ix PS iy PS iz ⎞ ⎠(4.1) 4. Obtenci´on de la distribuci´on espacial de una escena 39 Ωi=⎡ ⎣ n2 ix(1 −ξ2)−n2 izξ2nixniy(1 −ξ2)nixniz nixniy(1 −ξ2)n2 iy(1 −ξ2)−n2 izξ2niyniz nixnizniynizn2 iz ⎤ ⎦(4.2)  Ωi=HC −tΩiHC −1(4.3) La distancia entre cada punto pjylac´onica generada por el punto picon el punto de fuga VP, se mide usando una aproximaci´on a [24]. Se calcula la l´ınea polar de un punto pjen la c´onica  Ω, se calcula la perpendicular a la l´ınea polar, especificando que pase sobre el punto pj. Este segmento perpendicular corta a la c´onica en dos puntos q+yq−,lam´ınima distancia eucl´ıdea entre pjyq+oq− 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 pjque votan a ´esta c´onica media son eliminados de la lista, y se selecciona un nuevo punto pide entre los restantes para generar una nueva c´onica, repitiendo el proceso hasta que todos los puntos votanalmenosaunac´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´ıdasantecadacasoas´ı 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,B3yB4las 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. 1Explicado 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 Bipor 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 Bise 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,B3yB4se 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 B2se 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 ´areaaa˜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´aexpansi´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,B3yB4que 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 B2dos 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 Bicorresponde 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´ıneaperonosehaya detectado. O que nos encontremos ante la presencia de una esquina oculta, es decir, una de las paredes se encuentra en un ´angulo 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 Bipor la nueva c´onica resultando en la expansi´on de dicha cara. 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 H3×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´unicamente de movimiento en coordenadas xey. R=⎡ ⎣cos θsin θ0 −sin θcos θ0 001 ⎤ ⎦(5.5) nF=[nFx,n Fy,n Fz]T=[0,0,1]T(5.6) t=[tx,t y,t z]T=[tx,t y,0]T(5.7) Y recordando la expresi´on de H=R(I+tnT F/d): H=⎡ ⎣cos θsin θt x/d −sin θcos θt y/d 001 ⎤ ⎦(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 XeYson 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 Hde forma que las ´unicas inc´ognitas restantes son: tx,tyyd, 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 49 5.2.1. 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 tomadasdesdeposicionesdistintasdespu´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 Ha partir del emparejamiento seleccionado. 3. Se aplica la Homograf´ıa a todos los emparejamientos XH ∗=HXy 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 Hcon 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 ´util 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 Ha 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 Ha 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 nLla normal que define una l´ınea en la imagen I,yn∗ Lla normal que representa el emparejamiento de nLvisto en la imagen I∗, estas l´ıneas est´an relacionadas por: n∗ L∝H−TnL(5.9) d´onde la matriz Hes la deducida en la ecuaci´on 5.8: H=⎡ ⎣cos θsin θt x/d −sin θcos θt y/d 001 ⎤ ⎦(5.10) 52 5.2. Selecci´on de emparejamientos H−T=⎛ ⎜ ⎝ cos θ cos θ2+sin θ2 sin θ cos θ2+sin θ20 −sin θ cos θ2+sin θ2 cos θ cos θ2+sin θ20 −(cos θ˙ tx/d−sin θ˙ ty/d) cos θ2+sin θ2 −(cos θ˙ ty/d+sin θ˙ tx/d) cos θ2+sin θ21 ⎞ ⎟ ⎠ =⎛ ⎝cos θsin θ0 −sin θcos θ0 h31 h32 1 ⎞ ⎠ (5.11) Desarrollando la matriz inversa y transpuesta de H;H−T=[hij]coni, j = 1,2,3, se observa que ´esta sigue dependiendo ´unicamente de dos par´ametros desconocidos (h31 yh32) compuestos por una combinaci´on lineal de los par´ametros de Hpero cuyo valor individual es irrelevante. La ecuaci´on 5.9 es equivalente a n∗ L×H−TnL=0,ded´onde se deduce el siguiente sistema de ecuaciones: nxny ∗nyny ∗nzny ∗−nxnz ∗sin θ−nynz ∗cos θ −nxnx ∗−nynx ∗nxnz ∗cos θ−nynz ∗sin θ−nznx ∗⎛ ⎝h31 h32 1 ⎞ ⎠=0 0 (5.12) que se puede resolver mediante Descomposici´on en Valores Singulares (SVD), obteniendo as´ıh31 yh32, 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 Nde 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 →Ndo 2: for j:= 1 →N∗do 3: if ni·nj ∗≥0,8then 4: H=CalcularHomograf´ıa(ni,n j ∗) 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 Nde puntos y han de estar referenciadas a un mismo ´angulo α, es decir, tomando como ´angulo de referencia αal correspondiente con el punto de fuga de la direcci´on X (VP X), el primer punto de la hip´otesis uno, p1 1, corresponder´a al punto que se encuentre con un ´angulo equivalente al del VP Xde dicha hip´otesis, de la misma forma el primer punto de la hip´otesis m,pm 1, corresponde al punto cuyo ´angulo es equivalente al del VP Xde 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(pI 1, ..., pI N), la posible homograf´ıa Hique relaciona esta imagen Icon 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.Enrojose adjunta el resultado de aplicar diversas homograf´ıas que transforman la hip´otesis desde la imagen IalaimagenI∗. 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 Hiviene definida por la distancia media entre la proyecci´on de los puntos (pI 1, ..., pI N) de la imagen Isobre la imagen I∗y los puntos de la hip´otesis de la imagen I∗(pI∗ 1, ..., pI∗ N). distancia(Hi)= Hi[pI 1, ..., pI N]−[pI∗ 1, ..., pI∗ N] (5.13) De esta forma, la matriz de homograf´ıa Hique consiga la menor distancia media entre puntos de los contornos comparados, ser´a considerada la homograf´ıa ganadora que relaciona las im´agenes IeI∗. Este proceso se repite con cada una de las mim´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 Idiscretizado en Npuntos. Se aplica homograf´ıa Hiy 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´ıaquehacelo 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 mim´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 iy el resto de las mhip´otesis proyectadas sobre la imagen I∗ DistanciaMedia(i)= m  j=1  [pi 1, ..., pi N]−[pj 1, ..., pj N] (5.14) 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 ´util 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. HipotesisPromedio =Hipotesis(arg min i|DistanciaMedia(i)|) (5.15) 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. Recordando que cada contorno esta formado por l´ıneas c´onicas  Ω definidas en la esfera por su normal n,elprimerpasoser´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→NumeroHipotesis} Ensure: ContornoPromedio 1: ContornoPromedio=ContornoInicial 2: for i:= 1 →NumeroParedes ContornoInicial do 3: ni=ContornoInicial(i){Normal que define a la pared “i”} 4: for h:= 1 →NumeroHipotesis do 5: for j:= 1 →NumeroPared 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)/ContornoPromedio(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 kde los resultados finales m´as recientes e incluirlos en futuras votaciones, de forma que este n´umero kha de ser menor que el n´umero mtotal de hip´otesis que intervienen en la votaci´on, y teniendo en cuenta que cuanto mayor sea k,menos flexible ser´aelm´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 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 ´ultimas im´agenes muestran transici´on entre pasillo en Ty 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´ounart´ıculo de investigaci´on a la conferencia internacional “12th International Conference 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 Nacionales 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.Enelcap´ı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 al´ı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 im´ agenes catadi´optricas, se dise˜na una secuencia de procesamiento de la im´agen 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 ´unica 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 ´unica 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 3Dde 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 ´unicamente 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). .............. 28 135 136 ´ INDICE DE FIGURAS 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..... 30 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,esdecir,lospuntosdefuga. ................ 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 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 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. ................................ 36 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. .......... 36 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. ........................ 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,B3yB4que 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´ael suelo. Notar c´omo la correcta combinaci´on entre B2dos c´onicas laterales y una central (marcado en amarillo) conforman una expansi´on perfecta. ...... 41 4.8. Diagrama de flujo seguido para por el algoritmo para obtener la hip´otesis final. 42 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. ... 43 5.1. Homograf´ıa entre dos puntos de vista OyO∗................ 46 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. ... 49 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 Hasus 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 IalaimagenI∗. 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 Idiscretizado en Npuntos. Se aplica homograf´ıa Hiy 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 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,andC.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 145 [26] Z. Zivkovic, O. Booij, and B. Krose. From images to rooms. Robotics and Autonomous Systems, 55(5):411–418, 2007.