Repositorio Institucional de Documentos

Lear Lear Lear Proyecto Fin de Carrera Lear ning of Objects Models for RoboE Proyecto Fin de Carrera ning of Objects Models for RoboE Proyecto Fin de Carrera ning of Objects Models for RoboE Proyecto Fin de Carrera ning of Objects Models for RoboE Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque Escuela de Repositorio Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque Juan Domingo Tardó Escuela de Repositorio Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque Juan Domingo Tardó Escuela de Repositorio Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque Juan Domingo Tardó Ingeniería Escuela de Repositorio Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque Arjen den Hamer Juan Domingo Tardó Ingeniería Escuela de Repositorio Proyecto Fin de Carrera ning of Objects Models for RoboE database Antonio Esteban Lansaque Arjen den Hamer Juan Domingo Tardó Ingeniería Escuela de I ngeniería Repositorio de Proyecto Fin de Carrera ning of Objects Models for RoboE database Autor Antonio Esteban Lansaque Director Arjen den Hamer Codirector Juan Domingo Tardó Ingeniería ngeniería de Proyecto Fin de Carrera ning of Objects Models for RoboE database Autor Antonio Esteban Lansaque Director Arjen den Hamer Codirector Juan Domingo Tardó Ingeniería ngeniería 201 la Universidad Proyecto Fin de Carrera ning of Objects Models for RoboE database Autor /es Antonio Esteban Lansaque Director Arjen den Hamer Codirector Juan Domingo Tardó informática ngeniería 201 3 Universidad Proyecto Fin de Carrera ning of Objects Models for RoboE database /es Antonio Esteban Lansaque Director Arjen den Hamer Codirector Juan Domingo Tardó informática ngeniería y A 3 Universidad Proyecto Fin de Carrera ning of Objects Models for RoboE database Antonio Esteban Lansaque Arjen den Hamer Codirector Juan Domingo Tardó informática y A Universidad Proyecto Fin de Carrera ning of Objects Models for RoboE database Antonio Esteban Lansaque Arjen den Hamer Juan Domingo Tardó s Solano informática y A rquitectura Universidad Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque Arjen den Hamer s Solano informática rquitectura Universidad de http://zaguan.unizar.es Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque s Solano rquitectura de http://zaguan.unizar.es Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque s Solano rquitectura Zaragoza http://zaguan.unizar.es Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque s Solano rquitectura Zaragoza http://zaguan.unizar.es Proyecto Fin de Carrera ning of Objects Models for RoboE Antonio Esteban Lansaque Zaragoza http://zaguan.unizar.es Proyecto Fin de Carrera ning of Objects Models for RoboE Zaragoza – http://zaguan.unizar.es Proyecto Fin de Carrera ning of Objects Models for RoboE – Zaguan http://zaguan.unizar.es Proyecto Fin de Carrera ning of Objects Models for RoboE arth Zaguan http://zaguan.unizar.es arth Zaguan http://zaguan.unizar.es arth Zaguan http://zaguan.unizar.es arth arth Learning of Objects Models for RoboEarth database Resumen Philips Innovation Services y el grupo de rob´otica de la Universidad de Zaragoza est´an cooperando en el proyecto europeo de RoboEarth, cuyo objetivo es crear una base de datos en Internet donde diferentes tipos de robots puedan compartir modelos y estrategias de manipulaci´on de objetos. El objetivo de este trabajo es el de construir una herramienta capaz de reconstruir modelos en 3D de diferentes tipos de objetos para almacenarlos en la base de datos de RoboEarth. Los modelos son obtenidos escaneando los objetos con c´amaras RGB-D como la kinect que proveen im´agenes y nubes de puntos en 3D. La librer´ıa VSLAM (Visual Simultaneous Localization and Mapping) desarrollada por UNIZAR se usa para calcular la trayectoria de la c´amara y para obtener un conjunto de keyframes. Las nubes de puntos pertenecientes a los keyframes son las que una vez registradas forman el modelo en 3D del objeto. Las nubes de puntos que son utilizadas para reconstruir los modelos no solo contienen los puntos correspondientes al objeto sino que tambi´en contienen puntos del entorno donde fueron tomadas. Por tanto, el primer paso para reconstruir el objeto es el de eliminar de las nubes los puntos que pertenecen al entorno y no al objeto. Una vez que los puntos del entorno han sido eliminado de las nubes, se realiza el proceso de registrado. Para reconstruir los modelos en 3D de objetos se han estudiado dos m´etodos diferentes. El primero de los m´etodos es un m´etodo basado en puntos de inter´es como SURF o ORB. El segundo de los m´etodos se basa en el conocido Iterative Closest Point (ICP). The research leading to these results has received funding from the European Union Seventh Framework Programme FP7/2007-2012 under grant agreement number 248942 RoboEarth. ´ Indice general 1. Introducci´on 4 1.1. Motivaci´on ............................................ 4 1.2. Conceptos b´asicos para registrar y segmentar nubes de puntos . . . . . . . . . . . . . . . . 5 1.2.1. Nubedepuntos...................................... 5 1.2.2. Matriz de transformaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3. Registrado de nubes de puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.4. Segmentaci´on de nubes de puntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Objetivodelproyecto ...................................... 6 1.4. Resumen.............................................. 7 1.4.1. M´etodo basado en puntos de inter´es . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4.2. M´etodo basado en Iterative Closest Point . . . . . . . . . . . . . . . . . . . . . . . 8 2. Segmentaci´on de nubes de puntos 10 2.1. Segmentaci´on antes del registrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1. Eliminaci´ondelfondo .................................. 10 2.1.2. Eliminaci´ondelplano .................................. 11 2.2. Segmentaci´on despu´es del registrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3. Registrado de nubes de puntos 14 3.1. M´etodo basado en puntos de inter´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.1. Emparejamiento inicial entre dos nubes de puntos . . . . . . . . . . . . . . . . . . 14 3.1.2. RANSAC ......................................... 15 3.1.3. M´ınimos cuadrados iterativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2. Iterative Closest Point (ICP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4. Comparaci´on de m´etodos 22 4.1. Test1 ............................................... 22 4.2. Test2 ............................................... 23 5. Conclusiones y recomendaciones 26 5.1. Conclusiones ........................................... 26 5.2. Recomendaciones......................................... 27 2 Cap´ıtulo 1 Introducci´on 1.1. Motivaci´on El incremento de la capacidad computacional y de la posibilidad de encontrar sensores de bajo coste han impulsado el desarrollo de nuevas aplicaciones de visi´on por computador. Un campo en particular que se beneficia de esta tendencia es la rob´otica. Un ejemplo pr´actico de una de estas aplicaciones podr´ıa ser una aspiradora aut´onoma que reconoce objetos para averiguar el lugar donde se encuentra y as´ı ajustar el modo en el que tiene que limpiar. Un problema importante pero a la vez dif´ıcil de solucionar en rob´otica es el de obtener informaci´on de entornos en aplicaciones no industriales donde el sistema opera en entornos desconocidos. Una aproximaci´on para que robots puedan interactuar con el entorno es que estos pudieran compartir conocimiento mediante una base de datos que les permitiera obtener informaci´on como mapas de navegaci´on, estrategias de manipulaci´on de objetos o modelos de objetos. RoboEarth [17] es una red y base de datos donde los robots pueden compartir informaci´on y aprender unos de otros. (Figura 1.1). El prop´osito principal de RoboEarth es el de proporcionar a los robots el conocimiento necesario para interactuar con entornos desconocidos. Figura 1.1: Estructura de RoboEarth. El objetivo que se quiere conseguir con el trabajo desarrollado en esta memoria es el da la creaci´on de modelos en 3D de objetos. Estos modelos ser´an utilizados para almacenarlos en la base de datos de 4 RoboEarth. Una vez que estos objetos hayan sido a˜nadidos a la base de datos de RoboEarth, diferentes tipos de robots podr´an conectarse a la base de datos para recuperar estos modelos. De este modo, los robots podr´an reconocer los objetos en un entorno cualquiera y as´ı ser capaces de manipularlos. 1.2. Conceptos b´asicos para registrar y segmentar nubes de puntos El prop´osito de esta secci´on es introducir algunos conceptos importantes que ser´an necesarios en los siguientes cap´ıtulos de esta memoria. Al lector al que le sean familiares estos conceptos, esta secci´on le puede servir para refrescar conceptos o puede continuar directamente con la siguiente secci´on del cap´ıtulo. Los conceptos que ser´an desarrollados son: nube de puntos, matriz de transformaci´on, registrado de nube de puntos y segmentaci´on de nubes de puntos. 1.2.1. Nube de puntos Una nube de puntos es el punto de partida para la mayor´ıa de algoritmos descritos en esta memoria. Una nube de puntos Pes simplemente un conjunto de puntos en 3D que est´an definidos por tres coordenadas (X, Y, Z). Por lo tanto, una nube de puntos puede ser vista como un conjunto de puntos que est´an definidos en el espacio eucl´ıdeo. P={(x, y, z)0, ..., (x, y, z)i, ..., (x, y, z)n}(1.1) Las nubes de puntos pueden ser obtenidos de esc´aneres o c´amaras que detectan la profundidad como la kinect. Depende del esc´aner si hay informaci´on extra en la nube de puntos a parte de la informaci´on espacial. Por ejemplo, cuando se usan esc´aneres RGB-D para crear la nube de puntos, la informaci´on RGB de los puntos tambi´en est´a presente en la nube de puntos. Prgb ={(x, y, z, rgb)0, ..., (x, y, z, rgb)i, ..., (x, y, z, rgb)n}(1.2) 1.2.2. Matriz de transformaci´on La matriz de transformaci´on T es una matriz que mapea un punto pen otro punto p0de acuerdo con la siguiente ecuaci´on p0 1=Tp 1(1.3) donde p= [x, y, z]Typ0= [x0, y0, z0]T. Una matriz de transformaci´on describe una rotaci´on y una traslaci´on de un punto en el espacio al mismo tiempo. As´ı, la matriz de transformaci´on Tdefinida en la ecuaci´on 1.3 puede ser desglosada en t´erminos de una rotaci´on y una translaci´on T=R t 0 1(1.4) donde la matriz 3x3 izquierda superior (R) se corresponde con la matriz de rotaci´on y el vector 3x1 superior derecho (t) se corresponde con el vector de traslaci´on. 1.2.3. Registrado de nubes de puntos Cuando una c´amara toma im´agenes mientras se mueve a trav´es de un entorno, las im´agenes son tomadas desde diferentes puntos de vista. En muchos casos, puede ser interesante representar las nubes de puntos en un sistema de referencia com´un para compensar el movimiento de la c´amara. El proceso de encontrar y aplicar la transformaci´on que convierte diferentes nubes de puntos en un mismo sistema de referencia (sistema que define inequ´ıvocamente todos los puntos que pertenecen al 5 sistema) se llama registrado de nubes de puntos. Dadas dos nubes de puntos M(conjunto modelo) y D(conjunto a registrar) obtenidas en un mismo entorno pero desde diferente puntos de vista, se buscan puntos correspondientes entre ambas nubes de puntos. As´ı, el registrado de las nubes de puntos (Figura 1.2) se reduce a encontrar la transformaci´on T que minimiza el error de alineaci´on entre los puntos correspondientes argmin T(n X i=0 ||T·di−mi||2)(1.5) donde diymirepresentan los puntos de la correspondencia i-´esima entre las nubes de puntos DyM. Figura 1.2: Ejemplo de un conjunto modelo, de un conjunto a registrar y de las correspondencias entre los conjuntos. Una vez encontrada la transformaci´on T, el nuevo modelo quedar´a formado por la uni´on del modelo anterior y la nube de puntos: M=M∪T·Pi(1.6) En el caso de utilizar como referencia del modelo la de la ´ultima nube de puntos, el modelo quedar´a: M=Pi∪T−1·M(1.7) 1.2.4. Segmentaci´on de nubes de puntos El objetivo de esta memoria es generar modelos 3D de objetos. Sin embargo, los objetos est´an presente en un entorno que no forma parte del objeto. Para separar el objeto del entorno, se realiza un proceso llamado segmentaci´on. Segmentaci´on es el proceso de separar una nube de puntos en distintos grupos. En esta memoria, se define segmentaci´on como el proceso de eliminar todo punto que pertenece al entorno y no al objeto de una nube de puntos. 1.3. Objetivo del proyecto El objetivo de este proyecto es el de reconstruir modelos en 3D de objetos (Figura 1.3) que ser´an almacenado en la base de datos de RoboEarth. El modelo es creado registrando Nnubes de puntos obtenidas desde diferentes puntos de vista. Estas nubes de puntos se encuentran en un entorno que se segmenta para que las Nnubes de puntos solo contengan los puntos pertenecientes al objeto. 6 Cap´ıtulo 3 Registrado de nubes de puntos El prop´osito de esta secci´on es el de definir m´etodos que reconstruyan modelos de objetos en 3D registrando nubes de puntos desde diferentes puntos de vista. Para registrar dos nubes de puntos, se tiene que encontrar una matriz de transformaci´on Tque mapee los puntos de las nubes de puntos con respecto al mismo sistema de referencia. Se han investigado dos m´etodos que calculan esta transformaci´on T. El primer m´etodo usa keypoints y sus descriptores para obtener correspondencias entre las nubes de puntos y as´ı calcular la transformaci´on T. El m´etodo desde un punto de vista global se explica en la secci´on 3.1. El segundo m´etodo se basa en el conocido algoritmo ICP (Iterative Closest Point) y se describe en la secci´on 3.2. 3.1. M´etodo basado en puntos de inter´es En la Figura 1.4, se presenta una visi´on general del proceso que registra varias nubes de puntos usando keypoints. Adem´as, en la secci´on 1.2.1 de esta memoria se describe una version esquematizada del m´etodo que ser´a explicada al detalle en esta secci´on. 3.1.1. Emparejamiento inicial entre dos nubes de puntos Las nubes de puntos obtenidas por la kinect no contienen informaci´on espacial para todos los puntos pero si contienen la informaci´on RGB. Por lo tanto, la imagen que usaremos para obtener los puntos de inter´es y los descriptores la podemos recuperar directamente de las nubes de puntos a registrar. Una vez hemos obtenido la imagen y la hemos transformado a escala de grises, se obtienen los puntos de inter´es de esta ultima. El tipo de puntos de inter´es que hemos elegido para la reconstrucci´on de los modelos 3D de objetos son SURF [1] y ORB [13]. Los puntos de inter´es se obtienen de la imagen 2D. Pero dada una coordenada en la imagen 2D, podemos obtener la posici´on en 3D. Por esta raz´on, a partir de ahora usaremos las coordenadas 3D para la construcci´on del conjunto de emparejamientos iniciales. Una vez que se calculan los puntos de inter´es en 3D y los descriptores correspondientes, el emparejamiento inicial entre los puntos de inter´es de dos nubes de puntos diferentes puede comenzar. El proceso para obtener el emparejamiento inicial se realiza entre dos nubes de puntos diferentes (nube1 y nube2), y sus respectivos puntos de inter´es y descriptores. La b´usqueda de los emparejamientos consta de los siguientes pasos: 1. se busca el vecino m´as pr´oximo de todos los puntos de inter´es de la nube1 en la nube2 usando sus respectivos descriptores. Esta b´usqueda se realiza atendiendo a la norma L2en el caso de puntos de inter´es SURF y atendiendo a la distancia de Hamming en el caso de puntos de inter´es ORB. 2. se realiza el mismo proceso que en el caso anterior pero en sentido contrario. Es decir, se busca el vecino m´as pr´oximo de todos los puntos de inter´es de la nube2 en la nube1. 3. si el vecino mas pr´oximo de un punto de inter´es p12 de la nube1 en la nube2 y el vecino m´as pr´oximo de un punto de inter´es p21 de la nube2 en la nube1 coinciden, estamos hablando de que 14 hemos encontrado una posible coincidencia entre los puntos de inter´es p12 yp21. El conjunto de emparejamientos iniciales est´a formado por todos los puntos de inter´es que satisfacen la misma condici´on que los puntos de inter´es p12 yp21. Figura 3.1: Ejemplo de emparejamientos iniciales usando SURF. 3.1.2. RANSAC En la secci´on anterior se explica como obtener un conjunto de emparejamiento inicial. Sin embargo en la pr´actica, es muy probable que aparezcan espurios que pueden hacer que la estimaci´on de la matriz de transformaci´on Tno sea la estimaci´on ´optima. Para evitar la aparici´on de estos espurios y obtener una estimaci´on correcta, primero se aplica RANSAC al conjunto inicial de emparejamientos. RANSAC [6] es el algoritmo m´as conocido para estimar los par´ametros de modelos matem´aticos de un conjunto de datos que contiene espurios. RANSAC fue definido por Martin A. Fischler y Robert C. Bolles en 1981. La raz´on por la que RANSAC es tan usado es porque RANSAC puede estimar los par´ametros de un modelo aunque tenga un n´umero significante de espurios. Como se muestra en la Figura 3.2, la presencia de espurios puede provocar estimaciones err´oneas. Sin embargo, usando RANSAC, los espurios de un modelo pueden ser detectados y eliminados para obtener as´ı un modelo mucho m´as preciso. Figura 3.2: La linea roja representa el modelo que minimiza el error total. La linea azul describe el modelo obtenido usando RANSAC. La idea b´asica para calcular el conjunto de correspondencias sin espurios entre dos nubes de puntos aplicando RANSAC es la siguiente: 1. elegir tres emparejamientos aleatorios del conjunto de emparejamientos inicial 2. obtener la transformaci´on Tque mapea los tres emparejamientos elegidos aleatoriamente. 3. aplicar la transformaci´on Ta todos los emparejamientos y ver cuantos de ellos casar´ıan con un cierto umbral de aceptaci´on. 15 4. los pasos anteriores se repiten Nveces. RANSAC devuelve el conjunto que mas emparejamientos mapeados contiene de las Niteraciones. El algoritmo explicado con mas detalle se presenta en el Algoritmo 1. Algorithm 1 RANSAC Require: Conjunto de coincidencias iniciales (emparejamientos) N´umero de iteraciones que RANSAC se ejecutar´a (N) Umbral para descartar espurios (dmin) N´umero de correspondencias m´ınimas para obtener T(numEmparejamientosNecesarios) Ensure: Conjunto de coincidencias sin espurios (mejorConjunto) mejorConjunto ← ∅ for i←0to Ndo muestras ←seleccionar numEmparejamientosNecesarios aleatoriamente de emparejamientos T←calcular transformaci´on T (usando el conjunto muestras) conjuntoTransformado ←aplicar Ta todo punto origen del conjunto emparejamientos for all coincidencia in conjuntoTransformado do Calcular la distancia eucl´ıdea (d) entre coorespondencias if d<dmax then inliers ←inliers +coincidencia end if end for if |inliers|>|mejorConjunto|then mejorConjunto ←inliers end if end for return mejorConjunto No todos los puntos devueltos por la kinect tienen informaci´on espacial. Por lo tanto, existen puntos de inter´es que podr´ıan tener una correspondencia en 2D pero no en 3D. Por consiguiente, hay menos emparejamientos en 3D de los que habr´ıa en 2D. Para solucionar esta falta de puntos de inter´es, si queremos registrar una nube de puntos Picon el modelo M={P0, ..., Pi−1}, el proceso de emparejamiento inicial se realiza entre la la nube de puntos Piy las r(con rdefinido por el usuario) nubes de puntos registradas en pasos anteriores del algoritmo Pi−1, ..., Pi−r. De este modo conseguimos un mayor n´umero de emparejamientos iniciales que permite obtener mejores resultados. Una vez que est´a definido como obtener un conjunto de correspondencias sin espurios entre dos nubes de puntos diferentes, a continuaci´on se describe el algoritmo completo para obtener la transformaci´on Tque mapea una nube de puntos Pi con un modelo M={P0, ..., Pi−1} Algorithm 2 Algoritmo para obtener la transformaci´on T Require: Nubes de puntos a registrar (Pi) Modelo (M={P0, ..., Pi−1}) Numero de nubes con respecto a las que buscar emparejamientos (r) Ensure: transformacion (T) que mapea Pien M allInliers ← ∅ for all nube in Pi−r..Pi−1do correspondencias ←encontrarCorrespondencias(Pi,nube) inliers ←RANSAC(correspondencias) allInliers ←allInliers ∪inliers end for T←calcularTransformacion(allInliers) return T 16 3.1.3. M´ınimos cuadrados iterativos Como fue descrito en el Capitulo 1, el objetivo del registrado de nubes de puntos es el de encontrar la transformaci´on Tque mapea una nube de puntos D(conjunto a registrar) en el modelo M     t00 t01 t02 t03 t10 t11 t12 t13 t20 t21 t22 t23 0 0 0 1     | {z } T     xi yi zi 1     |{z} D =    x0 i y0 i z0 i 1     |{z} M (3.1) El objetivo de esta secci´on es la de obtener todos los par´ametros tij de la matriz Tde la ecuaci´on 3.1. Por lo tanto, el problema de encontrar la transformaci´on Tse reduce a resolver el sistema de ecuaciones 3.1 donde [xi, yi, zi,1]Ty [x0 i, y0 i, z0 i,1]Trepresentan los puntos de cada una de las coincidencias calculadas de acuerdo con la secci´on anterior. La matriz Tcontiene 12 par´ametros desconocidos pero el sistema es un sistema con 6 grados de libertad (GDL). Estos 6 GDL son los ´angulos de Euler (α,βand γ) y el vector de traslaci´on(x,y,z). Los ´angulos de Euler describen la orientaci´on de la c´amara que tomo la nube de puntos a registrar y el vector de traslaci´on describe la posici´on de esta misma. Esta transformaci´on Tno es un operador lineal debido a que la mayor´ıa de los elementos de la matriz est´an compuestos por senos y cosenos. Las funciones seno y coseno son funciones que no presentan cambios bruscos en sus valores, por eso el sistema de ecuaciones 3.1 puede ser reordenado en t´erminos de los par´ametros α,β, γ, x, y yz. Esto puede se puede realizar linealizando previamente la transformaci´on T. Una vez que la matriz Tes linealizada y el sistema de ecuaciones reordenado de tal forma que α,β, γ, x, y yzse conviertan en las nuevas inc´ognitas, el sistema es resuelto usando un m´etodo que iterativamente calcula la transformaci´on usando m´ınimos cuadrados. Linealizaci´on Cada elemento tij de la matriz de transformaci´on Tse define como una funci´on no lineal (Ecuaci´on 3.2) con 6 GDL (Θ = {α, β, γ, x, y, z}). Para obtener la expresi´on en t´erminos de Θ cada uno de los elementos tij de la matriz Tes linealizado [11]. Para realizar esta linealizaci´on se usan series de Taylor de primer orden. La serie de Taylor de primer orden alrededor del punto Θ0={α0, β0, γ0, x0, y0, z0}de cada uno de los elementos tij se define en la ecuaci´on 3.2 tij (α, β, γ, x, y, z) = tij (Θ0) + ∂tij ∂α dα +∂tij ∂β dβ +∂tij ∂γ dγ +∂tij ∂x dx +∂tij ∂y dy +∂tij ∂z dz (3.2) donde dα =α−α0dβ =β−β0dγ =γ−γ0 dx =x−x0dy =y−y0dz =z−z0 (3.3) Una vez definida la linealizaci´on, sustituimos la ecuaci´on 3.2 en cada uno de los elementos de la matriz 3.1 y reagrupamos t´erminos de tal forma que el vector de inc´ognitas pasen a ser las variables dα,dβ, dγ, dx, dy ydz. Este nuevo sistema de ecuaciones esta definido a continuaci´on A·dΘ = b⇒          ∂t00 ∂α xi+∂t01 ∂α yi+∂t02 ∂α zi ∂t00 ∂β xi+∂t01 ∂β yi+∂t02 ∂β zi ∂t00 ∂γ xi+∂t01 ∂γ yi+∂t02 ∂γ zi100 ∂t10 ∂α xi+∂t11 ∂α yi+∂t12 ∂α zi ∂t10 ∂β xi+∂t11 ∂β yi+∂t12 ∂β zi ∂t10 ∂γ xi+∂t11 ∂γ yi+∂t12 ∂γ zi010 ∂t20 ∂α xi+∂t21 ∂α yi+∂t22 ∂α zi ∂t21 ∂β xi+∂t22 ∂β yi+∂t23 ∂β zi ∂t21 ∂γ xi+∂t22 ∂γ yi+∂t23 ∂γ zi001                 dα dβ dγ dx dy dz        =   x0 i−t00 −t01 −f02 y0 i−t10 −t11 −f12 z0 i−t20 −t21 −f22    (3.4) El nuevo sistema de ecuaciones 3.4 define las ecuaciones para un emparejamiento i-´esimo ya que el sistema de ecuaciones completo tiene 3 ecuaciones por cada una de las correspondencias del conjunto de emparejamientos sin espurios (una ecuaci´on por cada una de las componentes de los puntos en 3D). Una vez que se ha calculado la version linealizada del sistema de ecuaciones 3.1, podemos usar m´etodos de ´algebra lineal para iterativamente obtener los valores de la variable Θ. 17 M´ınimos cuadrados Como fue descrito en la secci´on anterior, cada una de las coincidencias calculadas a˜nade tres ecuaciones al sistema de ecuaciones 3.4. Por tanto, el sistema esta formado por un n´umero de ecuaciones mucho mayor que el n´umero de inc´ognitas. Por esa raz´on, el sistema de ecuaciones es resuelto usando m´ınimos cuadrados para encontrar el par´ametro dΘ que minimizan las distancia entre las correspondencias de dos nubes de puntos diferentes. La distancia que hemos elegido para minimizar el problema ha sido la distancia eucl´ıdea: ||[x0 0−x0, y0 0−y0, z0 0−z0, . . . , x0 n−xn, y0 n−yn, z0 n−zn]T||2(3.5) donde [x0 i, y0 i, z0 i]Ty [xi, yi, zi]Trepresentan las coordenadas de un emparejamiento i-´esimo entre el modelo My la nube de puntos a registrar Drespectivamente. Ahora podemos reescribir el sistema de ecuaciones 3.4 como un problema de m´ınimos cuadrados en funci´on de dΘ. As´ı, la funci´on que queremos minimizar es f(x) = ||b−A·dΘ||2(3.6) De acuerdo con el sistema de ecuaciones 3.4, la solucion dΘ que minimiza la funcion se define como un peque˜no paso en la b´usqueda del m´ınimo global. Por lo tanto, el m´etodo se ejecuta iterativamente hasta que se encuentra el m´ınimo global de la funci´on. Hay que enfatizar que para aplicar el m´etodo de m´ınimos cuadrados se ha realizado una linealizaci´on de la matriz T. Como resultado, la soluci´on del m´etodo depende fuertemente del punto inicial Θ0={α0, β0, γ0, tx0, ty0, tz0}usado para la linealizaci´on que deber´ıa ser un valor cercano al valor optimo deseado, ya que de otro modo podr´ıamos obtener un m´ınimo local en vez del m´ınimo global. Resumiendo, dada una estimaci´on inicial (Θ0) cercana al valor ´optimo (Θ) que queremos obtener, el m´etodo de m´ınimos cuadrados iterativo se describe en los siguientes puntos: 1. la matriz Ay el vector bse construyen de acuerdo con el valor del par´ametro Θky los puntos de los emparejamientos de los que part´ıamos, de acuerdo al sistema de ecuaciones 3.4 2. se resuelve el sistema de ecuaciones construido usando m´ınimos cuadrados 3. la soluci´on obtenida dΘ (peque˜no paso para converger al m´ınimo global) se a˜nade al valor del par´ametro estimado Θk Θk+1 = Θk+dΘ (3.7) 4. si la diferencia entre dos soluciones consecutivas es menor que un umbral definido por el usuario, el algoritmo ha convergido a la soluci´on (Θ = Θk+1). Sino, volvemos al paso uno usando como estimaci´on el nuevo par´ametro calculado Θk+1. 3.2. Iterative Closest Point (ICP) Como alternativa al m´etodo basado en puntos de inter´es descrito en la secci´on anterior, ahora se va a presentar el Iterative Closest Point. El ICP, como en el m´etodo anterior, calcula la matriz de transformaci´on Tque mapea una nube de puntos Pen otra nube de puntos que llamaremos modelo M. En la Figura 1.5 se puede ver gr´aficamente el proceso que sigue el m´etodo basado en ICP. Adem´as en la secci´on 1.4.2 se presenta una versi´on esquematizada de dicho m´etodo. El Iterative Closest Point es un algoritmo que fue propuesto por Besl and McKay en los a˜nos 90. Desde que fue propuesto, muchas variedades del ICP han aparecido pero en este proyecto nos centraremos solo en la versi´on cl´asica descrita en [2]. 18 Dadas dos nubes de puntos MyP={p0, ..., pn}, el ICP calcula iterativamente la matriz de transformaci´on Tque minimiza el error entre puntos correspondientes de las nubes MyP argmin T(n X i=0 ||T·pi−mi||2)(3.8) donde mies el vecino m´as cercano del punto pien el modelo M. La idea principal del ICP cl´asico (Algoritmo 3) se puede resumir en dos pasos: 1. construir el conjunto de correspondencias bas´andonos en la distancia m´as cercana de los puntos de Pien Musando una estimaci´on inicial T0. 2. calcular la matriz de transformaci´on Tque minimiza la distancia entre las correspondencias (Ecuaci´on 3.8) Como cualquier m´etodo de descenso de gradiente, el ICP converge con una mayor seguridad a una buena soluci´on cuanto mejor sea la estimaci´on de la transformaci´on inicial T0. De otro modo, es probable que el ICP converga a m´ınimo local que de como resultado un mal registrado de nubes de puntos. Algorithm 3 Algoritmo ICP Require: Modelo M Nube de puntos a registrar P={p0, ..., pq} Transformaci´on inicial T0 Ensure: Matriz de transformaci´on Tque alinea Pcon M T←T0 while not converga do for i←1to Ndo mi←vecinoMasCercano(T·pi, M) if ||mi−T·pi|| ≤ distmax then wi←1 else wi←0 end if end for T←argminTPiwi||T·pi−mi||2 end while return T El ICP asume que las nubes de puntos a registrar no tienen porque estar completamente solapadas. Por lo tanto, algunos puntos entre las nubes de puntos no tendr´an correspondencia. Por esta raz´on, un umbral (distmax) se a˜nade al ICP. De este modo, solo los puntos cuya distancia eucl´ıdea con su emparejamiento sea menor que el umbral distmax son considerados como correspondencias. La elecci´on del umbral distmax representa una soluci´on de compromiso entre convergencia y precisi´on: un valor peque˜no puede resultar en mala convergencia porque el algoritmo no encuentra suficientes correspondencias para calcular la matriz de transformaci´on T(Figura 3.3). 19 Figura 3.3: Esta figura muestra que si el objeto esta mas lejos que distmax, el ICP no puede encontrar correspondencias. Por lo tanto, no puede calcular la matriz de transformacion T. valores grandes pueden dar como resultado correspondencias err´oneas entre puntos que no est´en solapados. De este modo, la transformaci´on calculada no es la ´optima (Figura 3.4). Figura 3.4: Las lineas verdes representan correspondencias correctas. Las lineas rojas describen correspondencias err´oneas. Esta figura muestra que si distmax tiene un valor grande el algoritmo encuentra correspondencias entre zonas no solapadas. La mejor elecci´on de distmax para el proceso de registrado de nube de puntos es el menor valor que da como resultado un buen registrado. La elecci´on depende de cuanto de buena es la estimaci´on de la posici´on de la c´amara. Cuanto mejor sea la estimaci´on, m´as puede ser el umbral distmax. A la hora de registrar nubes de puntos usando el ICP hay que tener en mente algunos peque˜nos trucos que mejoran mucho el resultado final. Cuando se calcula la posici´on de la c´amara, se comete un peque˜no error. El error entre dos posiciones consecutivas de la c´amara es peque˜no pero estos errores se van acumulando poco a poco. Como resultado, el error acumulado entre la primera nube de puntos a registrar y la ultima puede ser considerable. Para evitar este fen´omeno (Figura 3.5), en vez de transformar la nube de puntos Pen el modelo M, lo que hacemos es transformar el modelo Men la nube de puntos P(M=T−1·M+P). As´ı, podemos asignar a distmax un valor mas peque˜no. Ademas, para obtener mejores resultados, el ICP se aplica a nubes de puntos a las que se les ha extra´ıdo el entorno en el que se encontraban. Como se ha explicado antes el ICP intenta minimizar la distancia eucl´ıdea de las correspondencias de las nubes de puntos a registrar. En comparaci´on con el objeto, el entorno tiene una cantidad mucho m´as grande de puntos que el objeto. Por lo tanto, podr´ıa ocurrir que el entrono se ha alineado perfectamente pero el objeto no. 20 Figura 3.5: Esta figura describe el problema de los errores acumulados en el proceso de estimaci´on de posici´on de la c´amara. 21 Cap´ıtulo 4 Comparaci´on de m´etodos En el cap´ıtulo 3, se explican dos m´etodos diferentes para el registrado de nubes de puntos: m´etodo basado en puntos de inter´es y m´etodo basado en Iterative Closest Point. El objetivo de esta secci´on es el de hacer una comparaci´on de ambos m´etodos desde una perspectiva practica teniendo en cuenta los siguientes puntos: 1. Precisi´on. Este es el punto m´as importante a la hora de comparar ambos m´etodos. Para hacer esta comparaci´on de precisi´on, el modelo del objeto reconstruido por todos los m´etodos sera testado visualmente para ver las diferencias entre ellos. 2. Velocidad. Aunque la velocidad en el proceso no es un punto clave, la eficiencia computacional es una caracter´ıstica que los m´etodos deber´ıan cumplir y que puede ayudar a decidir cual de los m´etodos es m´as adecuado para un determinado objeto. La comparaci´on de los modelos 3D reconstruidos se realizar´a para dos objetos diferentes que nos permitir´an enumerar los puntos fuertes y d´ebiles de ambos m´etodos. Cada uno de los dos m´etodos comparados, tendr´a a su vez dos casos de estudio. En el estudio del m´etodo basado en puntos de inter´es un caso se estudia para puntos de inter´es SURF y otro para puntos de inter´es ORB. En el m´etodo basado en el ICP, el estudio se realiza para nubes cuya resoluci´on se ha disminuido y para nubes cuya resoluci´on no se ha modificado. 4.1. Test 1 Para el primer test, hemos escogido una caja. El modelo en 3D final de la caja para los cuatro casos de estudio, se ha reconstruido utilizando 55 nubes de puntos tomadas desde diferentes puntos de vista. El objeto a reconstruir se encontraba sobre una mesa con ning´un objeto m´as en ella. Los resultados obtenidos para los cuatros casos de estudio se muestran en la Figura 4.1. En esta figura podemos observar que los casos a), c) y d) convergen a una soluci´on similar y de precisi´on bastante aceptable. En el ´unico caso en el que el resultado no es tan bueno es en el caso b) esto es debido a que para su reconstrucci´on fueron utilizadas nubes de puntos con una resoluci´on m´as baja. El objetivo de usar nubes de puntos con una resoluci´on m´as baja era el de obtener un modelo en 3D en un menor tiempo y comprobar si obten´ıamos los mismos resultados que usando nubes de puntos sin disminuir su resoluci´on. En este punto, centr´andonos en la precisi´on solo un modelo ha sido descartado. Por lo tanto, para decidir cual es el mejor m´etodo para este objeto tendremos que analizar la velocidad de reconstrucci´on del modelo. En la Figura 4.2 se muestra los diferentes tiempos de reconstrucci´on del modelo. En esta figura podemos ver claramente que el m´etodo basado en ICP es mucho m´as lento que el m´etodo basado en puntos de inter´es. Por lo tanto, podemos afirmar que para objetos con texturas la mejor opci´on es el m´etodo basado en puntos de inter´es porque es tan preciso como el m´etodo basado en ICP pero sin embargo es varias veces m´as r´apido. 22 [16] Bastian Steder, Radu Bogdan Rusu, Kurt Konolige, and Wolfram Burgard, Point feature extraction on 3d range scans taking into account object boundaries, Robotics and Automation (ICRA), 2011 IEEE International Conference on, IEEE, 2011, pp. 2601–2608. [17] Markus Waibel, Michael Beetz, Javier Civera, Raffaello D’Andrea, Jos Elfring, Dorian Galvez-Lopez, Kai Haussermann, Rob Janssen, JMM Montiel, Alexander Perzylo, et al., Roboearth, Robotics & Automation Magazine, IEEE 18 (2011), no. 2, 69–82. [18] John R Williams and Kevin Amaratunga, Introduction to wavelets in engineering, International journal for numerical methods in engineering 37 (1994), no. 14, 2365–2388. 29