ALGORITMOS GENÉTICOS PARA LA GEOREFERENCIACIÓN DE IMÁGENES CON IDENTIFICACIÓN AUTOMÁTICA DE PUNTOS DE CONTROL TERRESTRES CÉSAR MONTENEGRO PORTILLO MÁSTER EN INVESTIGACIÓN EN INFORMÁTICA, FACULTAD DE INFORMÁTICA, UNIVERSIDAD COMPLUTENSE DE MADRID Trabajo Fin Máster en Ingeniería Informática para la Industria Calificación: 9.5 (Sobresaliente) Septiembre 2011 Director: Gonzalo Pajares Martinsanz María Guijarro Mata-García Autorización de Difusión CÉSAR MONTENEGRO PORTILLO Septiembre 2011 El abajo firmante, matriculado en el Máster en Investigación en Informática de la Facultad de Informática, autoriza a la Universidad Complutense de Madrid (UCM) a difundir y utilizar con fines académicos, no comerciales y mencionando expresamente a su autor el presente Trabajo Fin de Máster: “ALGORITMOS GENÉTICOS PARA LA GEOREFERENCIACIÓN DE IMÁGENES CON IDENTIFICACIÓN AUTOMÁTICA DE PUNTOS DE CONTROL TERRESTRES ”, realizado durante el curso académico 2010-2011 bajo la dirección de Gonzalo Pajares Martinsanz y de María Guijarro Mata-García en el Departamento de Ingeniería del Software e Inteligencia Artificial, y a la Biblioteca de la UCM a depositarlo en el Archivo Institucional E-Prints Complutense con el objeto de incrementar la difusión, uso e impacto del trabajo en Internet y garantizar su preservación y acceso a largo plazo. Resumen en castellano Gracias a la Visión por Computador podemos analizar sucesos que ocurren a gran escala, como el desplazamiento de glaciares, inundaciones, o vertidos de productos contaminantes en ríos y costas. El objetivo de este trabajo es proporcionar una técnica que sea capaz de georeferenciar fotografías oblicuas tomadas con un equipo de bajo coste. El proceso se realiza a partir de una serie de imágenes oblicuas y un modelo digital de elevación (DEM, Digital Elevation Model), analizando cada imagen por separado para obtener las coordenadas de los puntos más significativos comunes entre ellas para establecer la relación matemática a partir de la cual pueden georeferenciarse las mencionadas imágenes. El procedimiento que se plantea tiene como fundamento el diseño de un algoritmo genético con el que podremos ajustar tanto la posición teórica como la dirección hacia la que apuntaba el eje óptico del sistema correspondiente acoplado a la cámara. El objetivo consiste en obtener los valores reales que permitan el ajuste con el fin de lograr la buscada relación matemática entre la imagen y el DEM y lo más precisa posible. Palabras clave Georeferenciación, DEM, fotografía oblicua, algoritmos genéticos, NSGA II, detección de bordes, detección de puntos de interés. Abstract Thanks to Computer Vision, we are able to analyze big scale events, as glacier movements, floods, or contaminant spills at rivers or shores. The aim of this paper is to provide with a technique capable of georeferencing oblique terrestrial photography with low cost equipment. All the process will be done with the input of some oblique pictures and a Digital Elevation Model (DEM), analyzing each one to obtain significant points to establish a relationship from where the pictures can be georeferenced. The process suggested it's based on the design of a Genetic Algorithm, which will be able to adjust both theoric position and aim of our optical system. The aim is to obtain the mathematical relationship between the image and the DEM as precise as possible. Keywords Georeferencing, DEM, terrestrial photography, genetic algorithm, NSGA II, edge detection, interest point detection. Índice de contenidos Capítulo 1 - Introducción...............................................................................................................3 1.1 Identificación del problema..................................................................................................3 1.2 Objetivos de la investigación................................................................................................4 1.3 Aportaciones a la investigación ...........................................................................................5 1.4 Organización de la memoria ................................................................................................5 Capítulo 2 - División del problema de la georeferenciación.........................................................7 2.1 Introducción..........................................................................................................................7 2.2 Datos de entrada....................................................................................................................7 2.2.1 Modelo Digital de Terreno.............................................................................................7 2.3 Fotografía Oblicua................................................................................................................8 2.4 Posición y orientación...........................................................................................................9 2.5 Selección de coordenadas...................................................................................................11 2.6 Ajuste de la relación entre puntos.......................................................................................12 Capítulo 3 - Resolución del problema.........................................................................................13 3.1 Descripción de la solución propuesta.................................................................................13 3.2 Identificación de los puntos de interés ...............................................................................13 3.3 Algoritmo para la corrección..............................................................................................21 3.3.1 Algoritmos genéticos multiobjetivo.............................................................................22 3.3.2 Evolución Flexible.......................................................................................................27 3.3.3 Correspondencia..........................................................................................................29 Capítulo 4 – Análisis de los resultados........................................................................................31 4.1 Introducción........................................................................................................................31 4.2 Resultados de la detección de cimas...................................................................................31 4.3 Resultado del algoritmo genético.......................................................................................33 4.4 Problema de distorsión de las imágenes.............................................................................38 Capítulo 5 - Conclusiones y trabajo futuro..................................................................................43 5.1 Conclusiones.......................................................................................................................43 5.2 Trabajo futuro.....................................................................................................................43 1 Agradecimientos A Gonzalo Pajares, María Guijarro y a la división del SIANI de la Universidad de Las Palmas de Gran Canaria, por facilitarme ampliamente la información utilizada, y por su disposición para ayudarme en todo momento con este proyecto. Al Laboratorio de puertos de la ETSI de Caminos Canales y Puertos de la UPM por proponerme el proyecto y facilitarme los medios necesarios. 2 Capítulo 1 - Introducción 1.1 Identificación del problema La georeferenciación es el proceso por el cual, a partir de los datos de un modelo o imagen disponibles con anterioridad, se lleva a cabo un proceso que asigna esos datos a una nueva imagen que carece de ellos. Para llevar a cabo este proceso, es necesario identificar estructuras significativas, pertenecientes en ambos casos a la misma entidad física de la escena, tanto en los datos conocidos como en los que se están generando por primera vez con el fin de establecer una función de transformación que nos permita la transferencia directa de los datos conocidos a la nueva imagen de datos desconocidos. Técnicamente la georeferenciación se refiere a la dotación de información geográfica a una determinada imagen a partir de datos del terreno cuya información geográfica es conocida de antemano. La georeferenciación de imágenes hoy por hoy se reduce en su mayor parte a imágenes obtenidas desde satélite o avión, y a pesar de no ser un problema trivial, es una temática que dispone de muchas herramientas ya desarrolladas a partir de diversos trabajos de investigación realizados [1][2][3], en los que algunas problemáticas a resolver entre otras son, además de georeferenciar la imagen, en la proyección de la fotografía plana sobre un modelo de la superficie terrestre sometido a curvatura como vemos descrito por ejemplo en [4]. El problema de este tipo de fotografía es que es muy cara, y no se puede obtener una tasa de muestreo adecuada para algunos eventos de los cuales el ciclo de vida es muy corto, o simplemente necesitamos muestrear con mayor frecuencia. En esta línea se sitúan sucesos tales como inundaciones, que en algunos casos pueden ser eventos fugaces que duran horas pudiendo ser interesante estudiar la evolución de la misma, o incendios que avanzan rápidamente con el viento, y conviene estudiar cómo se propaga en un entorno preciso donde pueda analizarse tanto el tiempo como el espacio con precisión científica. Puesto que no podemos disponer de un satélite sobre cualquiera de estos eventos cuando deseemos, ni podemos usar un avión con la frecuencia deseada, a menos que dispongamos de un gran capital para sufragar los costes, nos vemos en la necesidad de buscar una herramienta lo más económica posible y capaz de extraer la suficiente información y con la precisión requerida, sobre el objeto de nuestros estudios. 3 La georeferenciación de fotografías oblicuas no es un tema nuevo, un trabajo interesante en este terreno es el realizado por Corripio [5], quien desarrolló una herramienta capaz de georeferenciar imágenes para estudiar las variaciones en superficie de acumulación de nieve en un terreno montañoso donde se encuentra un glaciar en Mont Brulé (Francia), tomando fotografías desde un punto concreto con la orientación adecuada, y analizando el albedo de cada una de las zonas. El problema de este método es que la participación humana es elevada, ya que se requiere identificar varios aspectos a mano, estos aspectos son la posición y eje óptico de la cámara, los puntos de referencia en la imagen obtenida, y la correspondencia de dichos puntos en un modelo virtual del terreno fotografiado; puede llevar a errores suponer que todas las fotografías son tomadas exactamente con la misma posición y orientación, obteniendo un error perceptible puesto que es una persona quien realiza las fotografías y siempre hay una mínima variación en cualquiera de los seis grados de libertad de la cámara en un entorno tridimensional. De este modo, si en todo el proceso, éste es el único punto donde la acción del hombre puede crear errores en la representación de la información, es donde habrá que detenerse con más atención, y buscar una solución capaz de corregir dichos errores hasta un nivel de satisfacción adecuado. En esta idea se centra el trabajo de investigación que se propone. 1.2 Objetivos de la investigación Los principales objetivos generales objeto de la investigación realizada son los que se expresan a continuación: 1. Aprender a manejar referencias bibliográficas, así como la forma de abordar las investigaciones. 2. Dividir el problema global de georeferenciación en problemas más sencillos de soluciones factibles. 3. Identificar diferentes tácticas para afrontar cada problema. 4. Estudiar ventajas y desventajas de los métodos. 5. Analizar los resultados obtenidos. 6. Comprobar si el conjunto de soluciones al problema pueden formar una única solución sin supervisión. 4 1.3 Aportaciones a la investigación Como resumen de todo lo anterior las aportaciones de investigación realizadas en el presente trabajo son las siguientes: • Diseño de un filtro de imágenes capaz de extraer los picos significativos o relevantes de un terreno montañoso • Diseño de un algoritmo capaz de extraer las coordenadas de los picos mencionados de un modelo digital terrestre dada la posición y orientación de la cámara, así como parámetros intrínsecos del sistema óptico acoplado a la cámara, destacando como ejemplo la distancia focal. • Diseño e implementación de un algoritmo genético capaz de corregir pequeños errores producidos tanto por sistemas de geolocalización como por el hombre. • Estudiar la precisión y bondad de los resultados obtenidos. • Sentar las bases de trabajos futuros, y proponer nuevas vías de investigación en base a los resultados obtenidos. 1.4 Organización de la memoria El presente trabajo se organiza de modo que en el capítulo dos se describen los datos necesarios para llevar a cabo el proceso. En el capítulo tres se proporciona una aproximación para la solución del problema. En el capítulo cuatro se analizan los resultados obtenidos. Finalmente en el capítulo cinco se obtienen las conclusiones pertinentes. 5 6 Capítulo 2 - División del problema de la georeferenciación 2.1 Introducción En este capítulo se analizan los datos de entrada, así como la selección de las coordenadas necesarias en el Modelo Digital del Terreno (DEM), ambos absolutamente necesarios para llevar a cabo el proceso de georeferenciación. Una vez obtenidos los puntos que se corresponden tanto en la imagen a georeferenciar como en el propio DEM, se debe llevar a cabo un ajuste en la posición y eje óptico de la cámara, para que dichos puntos se solapen, este ajuste lo veremos en el siguiente capítulo mediante una solución basada en algoritmos genéticos. 2.2 Datos de entrada Como entrada para nuestro sistema de georeferenciación tendremos los datos que se mencionan a continuación: • Modelo digital del Terreno (DEM) de la zona a analizar. • Fotografía oblicua • Posición y orientación aproximadas de la cámara durante el proceso de captura de la imagen. 2.2.1 Modelo Digital de Terreno Se denomina Modelo Digital a una estructura numérica de datos que representa la distribución espacial de una variable cuantitativa y continua, como puede ser la temperatura, la presión atmosférica o en nuestro caso la cota. En particular, cuando la variable a representar es la cota o altura del terreno se denomina Modelo Digital de Elevaciones o DEM (Digital Elevation Model), por sus siglas en inglés, que será la terminología utilizada en este trabajo por su amplia difusión en la comunidad científica tanto a nivel nacional como internacional. Para este estudio se han utilizado los DEM de la parte norte de Las Palmas de Gran Canaria, Modelo Digital del Terreno obtenido a partir del Mapa Topográfico 1:5.000 (años 2004- 2006) mediante procesos de selección, triangulación y muestreo conforme a una malla de 10x10 metros. El DEM se suministra en formato de texto plano con una coordenada xyz por línea. Las 7 coordenadas x e y de cada punto se corresponden con el centro de la celda de 10x10 metros empleada en el proceso de interpolación para obtener el valor de la coordenada z. Estos DEM se caracterizan por poseer la siguiente información técnica: Sistema de Referencia ITRF93, Elipsoide WGS84, Red Geodésica REGCAN95 (versión 2001), Sistema de representación UTM Huso 28 (extendido) (www.grafcan.es). En la figura 2.1 se muestra un ejemplo de los DEM utilizados en este trabajo de investigación. Figura 2.1 Representación del DEM: secciones utilizadas 2.3 Fotografía Oblicua Para este estudio se han realizado fotografías con una cámara Canon Ixus 55, de 5 Mpíxeles, con una distancia focal mínima de 35mm. Esta composición nos permite disponer de un ángulo de visión de 37.8º en vertical y 54.4º a lo ancho. Las fotografías se han tomado sin atender a lograr una posición óptima, es más, se ha procurado producir errores para corregirlos mediante la técnica propuesta como aporte de la investigación y en previsión de que en general dichos errores van a estar presentes en cualquier toma de imágenes realizada tanto de forma manual como automática y por tanto es necesario y 8 http://www.grafcan.es/ conveniente asumirlos como tal. De esta forma los errores son más evidentes y el efecto de la corrección resulta ser más notable. En la Figura 2.2 se muestra una imagen del primer escenario a tratar con la solución que se propone en este trabajo de investigación. Figura 2.2 Imagen de la Isleta de Las Palmas 2.4 Posición y orientación Para la localización se ha usado el sistema GPS (Global Position System) de tipo garmin legend hcx que nos proporciona datos con un error máximo de 10m según la descripción del fabricante, mientras que la dirección la introducimos manualmente en un visor del DEM desarrollado con este propósito durante el presente trabajo de investigación. En la figura 2.3 se muestra una imagen del visor de DEM creado, y en la figura 2.4 el dispositivo GPS utilizado en las coordenadas de captura de la imagen de la figura 2.2; a continuación podemos observar en la figura 2.5 una captura desde las coordenadas indicadas en el GPS en el escenario virtual creado por el visor y teniendo en cuenta los DEM. 9 Figura 2.3 Vista del DEM coloreado Podemos observar en la Figura 2.4 la posición desde donde se toma la fotografía y el error estimado por el localizador. Figura 2.4 Localizador GPS 10 El DEM se representa como el conjunto de puntos que vemos en la figura 2.5, desde una posición determinada. Podemos apreciar el perfil de la isleta de Las Palmas de Gran Canaria, similar a la perspectiva de la figura 2.2, sobre la que trabajaremos posteriormente. Figura 2.5 Vista del DEM original 2.5 Selección de coordenadas El problema principal de la georeferenciación, es la selección de puntos que se correspondan en las imágenes que queremos georeferenciar con los del medio georeferenciado, en nuestro caso, el DEM. Vemos por lo tanto que se deben realizar independientemente dos tareas, una sobre la fotografía, y otra sobre el propio DEM, con el objetivo de obtener puntos con una característica común. Esto es, una característica relevante que debe aparecer en ambos, teniendo como finalidad su emparejamiento de cara al posterior proceso de georeferenciación. Por lo tanto, mediante estas dos tareas obtendremos una serie de puntos bidimensionales correspondientes a los puntos característicos localizados sobre la propia fotografía, mientras que del DEM obtendremos puntos 3D, con características similares. 11 2.6 Ajuste de la relación entre puntos Dado que las herramientas utilizadas no son precisas al 100%, tenemos que ser capaces de corregir los errores introducidos por los sistemas de medida y localización. El localizador GPS, según las especificaciones técnicas del fabricante, puede generar un error aproximado de 10m, lo que sin duda va a afectar a la perspectiva de la fotografía tomada. No obstante, la dirección de la cámara, a priori, no se registrará de ninguna forma, ya que uno de los objetivos es asumir esta situación para que el sistema pueda utilizarse de forma generalizada. De esta forma, resulta prácticamente imposible establecer una correspondencia directa entre lo que vemos a través de la fotografía y lo que se observa en el DEM. Es necesario por tanto, diseñar un método capaz de corregir los errores que repercuten sobre la posición y dirección de la cámara. Esto constituye precisamente la aportación fundamental de investigación que se realiza en este trabajo mediante la propuesta que se formula basada en el algoritmo genético diseñado con tal propósito. 12 Capítulo 3 - Resolución del problema 3.1 Descripción de la solución propuesta La solución al problema de la georeferenciación que se propone en este trabajo se divide en tres partes o fases independientes, éstas son: 1. Identificación de puntos de interés en la imagen y en el DEM. 2. Corrección del error de posicionamiento y dirección de la cámara en el momento de captura. 3. Comprobación del ajuste solapando la perspectiva del DEM sobre la imagen. Éstos son los procesos que en [5] se realizan a mano, y que en esta investigación pretendemos automatizar. Cada uno de los procesos propuestos para llevar a cabo los procedimientos anteriores se analizan en profundidad en las siguientes secciones. 3.2 Identificación de los puntos de interés La identificación de los puntos de interés a localizar tanto en la imagen como en el DEM constituye una de las fases más importantes del proceso de georeferenciación ya que a través de estos puntos se establece la relación de la imagen con el DEM. En nuestro caso, dado que la información que nos facilita el DEM proviene únicamente del terreno, y no de las edificaciones o vegetación, debemos obviar la zona que contiene todos esos elementos carentes de interés, que podrían ralentizar el proceso con datos inservibles. Un DEM posee cientos de miles de coordenadas, por lo que realizar cálculos sobre todas ellas, resulta excesivamente costoso desde el punto de vista computacional, por lo tanto, nos vemos obligados a reducir información, tratando de que no desaparezca información relevante. En las imágenes los puntos pertenecientes a las zonas que separan unos objetos de otros suelen ser de interés, dado que permiten distinguir zonas bien diferenciadas. Por esta razón, se propone como operador capaz de identificar tales puntos los denominados operadores de Sobel [6], diseñados específicamente para la extracción de puntos de borde. 13 Los operadores de Sobel o de forma genérica simplemente el operador de Sobel aplicado sobre una imagen digital en escala de grises, calcula el gradiente de la intensidad de brillo de cada punto de la imagen o píxel dando la dirección del mayor incremento posible (de más gris a más claro) además calcula la magnitud de cambio en esa dirección, es decir, devuelve un vector con su módulo y dirección que informa sobre la magnitud del cambio y su dirección en una localización dada y por tanto de la existencia o no de un punto que indica la transición entre dos regiones, es decir de un borde. El resultado muestra si los cambios en cada punto analizado son abruptos o suaves, y a su vez con qué intensidad un punto determinado representa un borde en la imagen y también la orientación a la que tiende ese punto considerado borde. En la práctica, el cálculo de la magnitud del gradiente es más sencillo que la interpretación de la dirección. Matemáticamente, el gradiente de una función de dos variables, en el caso que nos ocupa la función intensidad de la imagen con las variables espaciales x e y, para cada punto es un vector bidimensional cuyas componentes están dadas por las primeras derivadas en la dirección vertical y horizontal. Para cada punto de la imagen, el gradiente del vector apunta en dirección del incremento máximo posible de intensidad, y la magnitud del gradiente del vector corresponde a la cantidad de cambio de intensidad en esa dirección. Lo anterior implica que el resultado de aplicar el operador de Sobel sobre la región de una imagen con intensidad constante resulta ser un vector nulo, y el resultado de aplicarlo sobre un punto de borde es un vector que apunta en sentido de los puntos más oscuros hacia los más claros. Matemáticamente, el operador utiliza dos núcleos o máscaras de dimensión 3×3 que recorren la imagen original para calcular sendas aproximaciones de las derivadas. Uno de tales núcleos se utiliza para detectar los cambios en dirección horizontal y otro en vertical. Según las expresiones dadas en la ecuación (3.1), las derivadas basadas en los operadores de Sobel son: 3 6 9 1 4 7 7 8 9 1 2 3 ( 2 ) ( 2 ) ( 2 ) ( 2 ) x y G z z z z z z G z z z z z z = + + − + + = + + − + + (3.1) A partir de las cuales se puede calcular el módulo y la dirección del gradiente como sigue, 2 2 -1; ( )=tan y x y x G G G x, y G ϕ= +G (3.2) 14 donde los distintos valores de z en la región de la figura 3.1(a) son los niveles de intensidad de los píxeles solapados por las máscaras en cualquier localización de la imagen. Para obtener los valores de las componentes del vector gradiente en el punto definido por el píxel central de la región se utilizan las expresiones (3.1) con lo que la magnitud y el ángulo se pueden obtener a partir de (3.1) y (3.2), es decir obtenemos un valor del gradiente en dicho punto. Para calcular el siguiente valor, las máscaras se mueven a la siguiente posición del nuevo píxel y se repite el proceso, después de haber barrido todas las posibles posiciones, el resultado es una imagen gradiente. Una vez que se ha obtenido la magnitud del gradiente, se puede decidir si un determinado punto es de borde o no aplicando la ecuación (3.3) previa definición de un umbral T, obteniendo así una imagen binaria g(x,y) como resultado. Figura 3.1 (a) Región de la imagen de dimensión 3x3; (b) Máscara usada para obtener Gx en el punto central de la región 3x3; (c) Máscara usada para obtener Gy en el mismo punto. Estas máscaras se denominan operadores de Sobel 1 2 3 4 5 6 7 8 9 1 0 1 -1 2 1 2 0 2 0 0 0 1 0 1 1 2 1 ( ) ( ) ( ) z z z z z z z z z a b c − − −           −           −      [ ] [ ] 1 ( , ) ( , ) 0 ( , ) si G f x y T g x y si G f x y T  >=  ≤ (3.3) Dependiendo del problema y del entorno será más acertado buscar un determinado tipo de bordes u otro, en nuestro caso, las fotografías son tomadas de un entorno de mar y montañas, por lo que se intentó buscar correspondencia por la silueta que dibuja la costa, como se puede observar en la figura 3.2 donde se muestra una captura aérea de la isleta de Las Palmas en el escenario virtual creado a partir del DEM y el resultado de aplicar los operadores de Sobel: A pesar de poder obtenerse bien la línea de costa, surgían varios problemas con este método, el primero es que las mareas provocan grandes cambios incluso en terrenos tan montañosos, donde la carrera de marea es corta, haciendo más complicado el problema si tenemos que considerar la altura de la marea en el instante de la obtención de cada fotografía. Además, las imágenes tomadas sin una altura notable sobre la zona de interés, hace que a grandes distancias sea 15 imposible, o muy difícil, dibujar una línea de costa aceptable; sólo se podría usar este método en fotografías aéreas, o desde un punto muy elevado respecto del objetivo. Figura 3.2 Línea de costa obtenida mediante los operadores de Sobel Agotada la posibilidad que nos brinda el límite entre la tierra y el mar, abordamos el problema de analizar la línea de horizonte que forma el terreno montañoso. Mediante los operadores de Sobel y sin necesidad de otros detectores de bordes u otras características identificativas, obtenemos una clara línea divisoria entre el cielo y la tierra. En la figura 3.3 podemos observar con claridad la línea del horizonte del terreno montañoso tras aplicar los operadores de Sobel. Por consiguiente, en el campo de aplicación que nos ocupa, éste resulta ser un buen punto de partida para encontrar puntos representativos de la imagen; podríamos aislar la línea de horizonte ya que define a la perfección la posición desde la que estamos observando el terreno, a menos que observemos una estructura perfectamente simétrica, pudiendo obtener así dos imágenes iguales desde dos posiciones diferentes, algo prácticamente inexistente en la naturaleza. El problema es que dicha línea de horizonte puede tener miles de puntos dependiendo de la resolución de la imagen y de las características de la escena en sí misma, con lo que cada vez que queramos comprobar si la posición de la cámara es correcta o no, nos veríamos obligados a comprobar todos y cada uno de dichos puntos. Esto supone un grave problema computacional ya que el tiempo de cálculo se dispararía; nos vemos obligados, por lo tanto, a seguir restringiendo todavía más la 16 característica representativa que define los puntos de interés. Bajo esta consideración, las características más sencillas a la par que representativas, son los picos de los montes de la imagen. Estos picos se sitúan en el espacio 3D lo suficientemente separados como para que cualquier variación de los seis grados de libertad de la cámara pueda ser detectada. Figura 3.3 Línea de horizonte obtenida mediante los operadores de Sobel Para detectar estas cimas, se desarrolló un sencillo algoritmo que busca los valores máximos de la línea de horizonte. Un máximo no es más que un punto que resulta tener más elevación que sus vecinos inmediatos, siempre desde el punto de vista de la geometría de la imagen, por lo que el algoritmo recorre la imagen de izquierda a derecha y de arriba a abajo hasta que encuentra el primer punto de borde, que sin duda corresponderá a un máximo de la línea que define el perfil montañoso. Una vez creada la primera cima, sabemos que ningún punto estrictamente por debajo de su posición será una cima, por lo que no es necesario proseguir con esta búsqueda del valor máximo absoluto. El siguiente punto de borde que encontremos, tendrá que estar separado de la primera cima detectada una cantidad determinada de píxeles horizontalmente, para evitar así pequeñas cimas como piedras en la cuerda de una montaña. En caso de no estar lo suficientemente separado, quiere decir que el punto encontrado está dominado por la cima, de este modo la cima se define de forma que pasa a abarcar desde la posición donde se encontró el píxel de valor máximo hasta el nuevo punto, aumentando así el área que domina la cima por debajo, siendo innecesaria su comprobación. En caso de estar lo suficientemente separado de todas las cimas existentes, se creará una cima nueva en ese punto. El siguiente pseudocódigo sintetiza lo expresado previamente, 17 Mientras (quedan puntos de borde) si (distancia(cima,punto)>valorMinimo) cima=nueva cima(punto) listaCimas->add(cima) fin Mientras Con este método somos capaces de obtener los puntos de las cimas de los montes de la imagen con una cierta eficacia. En la parte derecha de la figura 3.4 se visualizan dos puntos de cima identificados mediante el procedimiento descrito previamente, que corresponden a las cimas representadas en la imagen de la misma figura a la izquierda. Mediante este procedimiento se obtienen dos puntos 2D perfectamente localizados de la imagen a georeferenciar, siendo además lo suficientemente representativos como para detectar una variación en su representación en el caso de mover la cámara a otras posiciones diferentes. A continuación repetimos la misma tarea en un ámbito más complejo, en el espacio 3D que define nuestro DEM. Para obtener de la misma forma las cimas de los montes de la zona del DEM correspondiente a la imagen, hemos de simular primero una cámara de las características de la utilizada para fotografiar la escena. En la figura 3.5 se muestra la proyección de perspectiva que define la formación de la imagen sobre el plano. Esta proyección es la utilizada en el modelo 3D del DEM. Figura 3.4 Identificación de las cimas de los montes 18 Figura 3.5 Esquema simplificado de la formación de una imagen. Mediante el esquema de la figura 3.6 relativa a la formación de imágenes por medio de proyección de perspectiva y considerando una cámara ideal de tipo “pinhole”, podemos deducir cómo tenemos que tratar cada punto del DEM. Considerando dicho modelo en un espacio 3D tal y como se muestra en la figura 3.6, es posible obtener la proyección de un punto tridimensional P sobre la imagen para obtener el punto imagen P’. Una vez obtenida la proyección de todos los puntos visibles del DEM sobre nuestro plano, es evidente que existe demasiada información, por lo que es necesario eliminar información redundante o superflua para quedarnos exclusivamente con la información relevante. Puesto que podemos estar seguros de que los puntos situados por debajo de otro en la imagen 2D, no van a ser nunca cimas de ningún monte, tomamos los máximos de cada columna de la imagen, es decir, el primer punto de cada columna examinándolas de arriba-abajo, de esta forma obtenemos una línea de horizonte, y a continuación aplicamos el algoritmo usado previamente en la fotografía para reconocer las cimas como en la figura 3.4, sobre los valores proyectados a partir del DEM. En la figura 3.7 se muestra el resultado de aplicar el proceso descrito sobre el DEM correspondiente a la isleta de Las Palmas de Gran Canaria, mediante el cual se obtienen primero los puntos que forman la línea de horizonte del terreno, y a partir de ahí los puntos de interés, marcados en la parte inferior de la imagen. 19 Figura 3.6 Esquema simplificado de la proyección de perspectiva de puntos 3D sobre el plano imagen. Una vez hemos obtenido estos puntos 2D, buscamos los puntos 3D que se corresponden con éstos, teniendo por lo tanto las coordenadas de las cimas visibles desde el punto donde suponemos que se sitúa la cámara. Dado que la imagen del DEM son puntos, hemos obtenido un error que se representa como una cima extra, pero el algoritmo de corrección será capaz de ignorar estos errores. De este modo hemos obtenido tanto los puntos 2D correspondientes a las cimas de la imagen del terreno, como los 3D correspondientes a las cimas en el DEM; estos valores serán la entrada del algoritmo genético planteado como solución al problema de georeferenciación. 20 Figura 3.7 Proceso de obtención de cimas de la una fotografía virtual con las características de la cámara utilizada para las fotografías del terreno. 3.3 Algoritmo para la corrección A pesar de la correspondencia establecida entre los puntos característicos de la imagen y los obtenidos en el DEM, pueden existir discrepancias entre ellos, lo que sin duda conducirá a posteriores errores en la georeferenciación. Los posibles fallos que se pueden dar para corregir son los que se enumeran a continuación, siendo necesario iniciar un proceso de corrección con el fin de minimizar los posibles errores derivados de ellos: • Desplazamiento de la posición de la cámara. 21 • Desplazamiento de la dirección donde apunta la cámara. • Alabeo de la cámara. • Diferente número de cimas encontradas. Para subsanar los errores procedentes de las tres primeras causas de error, es obvio que bastaría con realizar una transformación inversa a la que origina el error. El problema proviene del hecho de que no conocemos los parámetros de la transformación inversa, entre otras razones se encuentra la que se debe a la posibilidad de encontrar diferente número de cimas, debido a una inclinación excesiva de la cámara por ejemplo, este hecho impide algo tan sencillo como puede ser el ajuste de la primera cima de la imagen con la primera del DEM. Para corregir los errores introducidos por la posición de la cámara, la dirección de observación y la rotación, se propone la utilización de un algoritmo genético. Los algoritmos genéticos basan su funcionamiento en la evolución natural, donde los individuos más aptos sobreviven dando lugar a una descendencia basada en la combinación de genes de los progenitores. En el trabajo de investigación aquí desarrollado hemos decidido aprovechar la potencia de los algoritmos genéticos para búsquedas de soluciones en espacios extensos, en concreto, los conocidos como multiobjetivo, cuya descripción se realiza seguidamente con el fin de orientarlo hacia la solución del problema planteado. 3.3.1 Algoritmos genéticos multiobjetivo La optimización se refiere a encontrar una o más soluciones factibles que corresponden a valores extremos de uno o más objetivos, siendo de gran importancia en la práctica, especialmente en diseño en ingeniería, experimentos científicos y toma de decisiones empresariales. Si un problema de optimización implica únicamente a una función objetivo, se denomina optimización mono-objetivo. Por el contrario, si dicha optimización implica a más de una función objetivo, se denomina optimización multiobjetivo[7] [8] [9]. Nos basaremos en los dos algoritmos genéticos que mejores resultados ofrecen para los problemas multiobjetivo, SPEA-II [10] y NSGA-II [11][12]. Los algoritmos genéticos multiobjetivo (múltiples objetivos) o también conocidos como multicriterio (múltiples criterios) son algoritmos en los que básicamente se varía el criterio de selección. En un algoritmo monobjetivo, la selección se fundamenta a partir de los valores de cada uno de los cromosomas o soluciones candidatas. Cuando el propósito es obtener soluciones 22 óptimas desde el punto de vista de varios objetivos o criterios que entran en conflicto mutuo (la mejora en uno de ellos sólo es posible a costa del empeoramiento en otro), es necesario un planteamiento multiobjetivo. Para determinar qué soluciones sobreviven a cada ciclo de la evolución en un algoritmo genético monobjetivo, basta con comparar la función objetivo única y determinar si queremos que sobreviva o no. Por el contrario, en los algoritmos genéticos multiobjetivo no podemos simplemente comparar una de las funciones objetivo, sino que tenemos que tener todas en cuenta, para esto utilizaremos la regla de la dominancia de forma que “una solución A domina a otra B, o también dicho de otra forma B es dominada por A” siempre que se cumplan las siguientes condiciones sobre el conjunto de soluciones no-dominadas: a) Cualquier par de soluciones debe ser no-dominada con respecto a la otra b) Cualquier solución no perteneciente a este conjunto debe ser dominada por al menos un miembro del conjunto de soluciones no-dominadas. 3.3 Diferencias de la optimización multi-objetivo con la mono-objetivo: • Existen dos metas en la optimización en lugar de una única (búsqueda de solución óptima). • Son metas ortogonales: búsqueda de soluciones lo más cerca posible del denominado frente de Pareto [13], que mantienen un conjunto de soluciones diverso a lo largo del mismo. En la figura 3.8 se muestra un ejemplo ilustrativo donde vemos que la primera línea más cercana al origen 0.0 de coordenadas, representa el frente de Pareto, es decir, la línea de mejores soluciones del espacio de resultados, mientras el resto de líneas representan el resto de soluciones. • Existen dos espacios de búsqueda; el espacio de decisión y el espacio funcional. • Ausencia de usos artificiales (tratamiento del problema directamente como multi- objetivo sin trasformación previa a mono-objetivo. 23 Figura 3.8 Orientación del proceso de búsqueda en un problema de minimización dos criterios. Algoritmo NSGA-II El algoritmo NSGA-II descrito en [14] y [15] mantiene las soluciones del mejor frente hallado incluyéndolas dentro de la siguiente generación (elitismo). La ordenación de cada individuo está basada en el criterio de no-dominancia correspondiente al NSGA. Además, esta propuesta introduce un algoritmo más rápido para ordenar la población que requiere O (mN2) cálculos en lugar de O(mN3) requeridos por la versión anterior del mismo algoritmo, siendo m el número de objetivos y N el tamaño de la población. Este algoritmo realiza una clasificación de la población en frentes, tal como el NSGA, a través de un valor de rango, el cual es función de la posición de cada frente respecto al total de la población, si bien sustituye la reclasificación de los individuos de cada frente, hecha en el NSGA mediante un agrupamiento conocida como “radio share”, por una comparación de tamaños de los cuboides (distancia “crowding”) en los que cada individuo está contenido, figura 3.9. La distancia de crowding es evaluada considerando el tamaño del mayor paralelogramo que circunda cada individuo sin incluir cualquier otro de la población dentro de un mismo rango. Este parámetro mantiene la diversidad en la población y de ese modo los individuos pertenecientes al mismo frente y con mayor distancia crowding le son asignados una mejor evaluación respecto a aquellos con menor distancia crowding, evitando así el uso del factor de compartición de aptitud. Una muestra de la incidencia que está adquiriendo actualmente la optimización evolutiva multi-criterio en la comunidad científica se puede inferir a partir del hecho de que el método propuesto en [15] ha sido catalogado como de alta relevancia y prestigio. 24 Figura 3.9 Clasificación por frentes y clasificación por agrupamiento. Propuesta de solución al problema de georeferenciación En concreto, para resolver el problema de la georeferenciación propuesto en este trabajo usaremos el algoritmo genético NSGA-II, que nos permite una búsqueda de solución multi- objetivo, necesaria para resolver el problema. Un individuo por lo tanto, se compone de una serie de valores, que se corresponden con los posibles desplazamientos que puede sufrir la posición de la cámara, más los posibles desplazamientos que puede sufrir el punto situado sobre el eje óptico de la cámara, es decir la orientación hacia la que apunta la cámara y la rotación angular que podría sufrir la cámara desde un punto de vista de su desplazamiento lateral. Todos los individuos nacen a partir de una semilla, que son las posiciones de entrada del sistema, obtenida mediante el localizador GPS y el ajuste manual en el visor 3D del DEM, tal y como se mencionó en el capítulo dos. Bajo esta consideración se permite una ligera desviación en alguno o algunos de sus parámetros. A partir de aquí se realiza la transformación de los puntos 3D respecto a las nuevas posiciones, obteniendo así una imagen virtual correspondiendo exactamente a lo que se vería desde esa posición. Una vez hecho esto se compara con la imagen que esperábamos obtener, es decir, los puntos de la propia imagen. Todo esto es posible gracias a que se conoce tanto el modelo de la cámara como los parámetros de proyección de perspectiva descritos previamente según las figuras 3.5 y 3.6. Individuo: PosXYZ: Posición de la cámara (tres variables X,Y,Z). DirXYZ: Posición del punto hacia donde apunta la cámara (tres variables X,Y,Z). 25 RotX: Rotación de alabeo de la cámara (una variable X) Esto supone la existencia de siete variables para definir una solución con precisión, que desde el punto de vista de tratamiento de datos informáticos debe ser al menos del tipo “double”, con lo que podríamos obtener una cantidad de soluciones desbordante, e incluso si limitamos la variabilidad y la precisión a +/- 100 con dos decimales tendríamos 1027 soluciones. Para hacer frente a la elevada cantidad de soluciones, conduciremos la evolución combinando las siguientes funciones objetivos. Funciones Objetivo: Para evaluar la validez de un individuo, solaparemos los puntos obtenidos en el capítulo tres tanto de la imagen como del DEM, y calcularemos las siguientes funciones objetivo: • Distancia Media: esta distancia se obtiene calculando la media de las distancias euclídeas de los puntos característicos identificados en la imagen al punto más cercano del DEM, evaluados sobre todos los puntos característicos y finalmente promediados. • Distancia mínima: a pesar de la importancia de que la distancia media sea baja, es también imprescindible que al menos uno de los puntos esté lo más ajustado posible, ya que así evitamos un reparto de los puntos sin coincidencias optimizando únicamente la distancia media del conjunto. • Número de aciertos: cantidad de puntos que encuentran su homólogo (distan menos de una cantidad determinada de un punto del otro sistema, DEM o imagen) • Cantidad de puntos del modelo que son visibles: para evitar que el punto de visión se desplace demasiado, perdiendo así la perspectiva de algunos puntos del modelo, y pudiendo llegar a una solución más sencilla (menos puntos a relacionar), maximizamos la cantidad de puntos vistos desde cada posición. Podemos añadir todos los objetivos que queramos, los algoritmos genéticos multi-objetivo funcionan como un monobjetivo cuando los criterios seleccionados no son contrarios entre sí, ya que un cambio que beneficie a uno de los criterios, beneficiará al otro también. De este modo, podemos añadir objetivos sin miedo a provocar un malfuncionamiento, aunque ciertamente se 26 ralentizará la evolución, ya que cada solución tendrá que someterse a más funciones objetivo, y por lo tanto incluirá más operaciones. Funciones de cruce: Las funciones de cruce modificarán todas las variables de los individuos, estas modificaciones se harán en tres órdenes de magnitud para tener alcance a soluciones “lejanas” sin perder la precisión a la hora de ajustar la solución definitiva. De esta forma tenemos siete funciones que incrementan cada una de las siete variables, más otras siete que las decrementan, y todas ellas en tres órdenes de magnitud diferentes. A estas cuarenta y dos funciones se les añade la que combina la información de dos individuos, dando lugar a un individuo con la posición de cámara de un progenitor y eje óptico de otro progenitor. Además existen funciones de cruce que varían la posición de la cámara desplazándola por el eje óptico a fin de acercarse o alejarse de aquello que queremos visualizar. La manera de seleccionar las cuarenta y cinco funciones de cruce resultantes ese realiza mediante la técnica de evolución flexible, que se describe a continuación. Funciones de Mutación Por último tenemos las funciones de mutación, que en este caso, se limitarán a alterar alguno de los parámetros del individuo, aumentándolo o disminuyéndolo una cantidad aleatoria entre 0 y 1. 3.3.2 Evolución Flexible La evolución flexible es la técnica que se centra en evitar el estancamiento de la evolución mediante la combinación de varias funciones de cruce, favoreciendo además el rumbo de la evolución cuando está siendo exitosa [16]. Debido a la complejidad de los problemas a los que nos enfrentamos, el espacio de soluciones se presenta con una gran cantidad de mínimos locales, en los que el algoritmo puede caer y estancarse, dando por buena una solución que realmente no lo es. En la evolución flexible se monitoriza la evolución para detectar un estancamiento prematuro según un criterio definido, de forma que se puedan tomar medidas para evitarlo. Estas medidas son por lo general, el cambio forzado de las funciones de cruce cuando se detecta 27 estancamiento, mientras que cuando no se detecta estancamiento se procura mantener las funciones utilizadas en el ciclo anterior de la evolución. Bajo esta filosofía hemos englobado los siguientes componentes: Funciones de cruce: las cuarenta y cinco funciones de cruce que varían los parámetros del individuo en tres órdenes de magnitud, corrigen el alabeo y alejan o acercan el sistema óptico al objetivo. Funciones de selección: selección de los individuos más adecuados para someterse a funciones de cruce y producir así descendencia mediante diferentes criterios, como por ejemplo de forma aleatoria ponderando según el orden de la lista de individuos ordenados de menor a mayor de acuerdo al resultado en una de las funciones objetivo, o seleccionando únicamente individuos pertenecientes al pareto óptimo. Máxima población: cantidad de individuos que sobreviven en una iteración del algoritmo. Al aumentar este parámetro, conseguimos que la posibilidad de que los individuos que salen del mínimo local, y a priori son peores soluciones, puedan seguir mejorando para encontrar una solución mejor en el sentido óptimo, explorando fuera del mínimo local. Esta medida repercute sobre la carga de trabajo del algoritmo, ya que al haber más individuos en cada iteración, los procesos de selección, cruce y evaluación tardan más, computacionalmente hablando. Otro aspecto negativo de esta medida es que la memoria del sistema puede saturarse, por lo que cuanta más información alberguen los individuos, menor podrá ser el máximo de población. En el problema que estamos tratando de resolver existe un mínimo local en cada una de las posiciones XYZ de la cámara, ya que para cada una de ellas, existe una dirección XYZ para el eje óptico, donde el emparejamiento de los puntos es mejor, por tanto se trata de un mínimo local para nuestro problema. Para decidir cuándo se estanca la evolución en alguno de estos mínimos locales, tenemos que definir un criterio de estancamiento, en este caso determinaremos que existe estancamiento cuando el mejor individuo de cada función objetivo no varía en un paso de la 28 evolución. De este modo definiremos varios límites de número de ciclos de estancamiento máximos para que se aplique la flexibilidad en cada uno de los componentes. Cuando alcance el primer límite se activa la variación en uno de los componentes, si no se consigue incumplir el criterio de estancamiento, se alcanzará el siguiente límite y se variará el siguiente componente, y así sucesivamente hasta forzar variabilidad en todos. Para este problema definimos: Ciclos estancado > 5: variabilidad de funciones de selección. Ciclos estancado > 15: variabilidad de funciones de cruce. Ciclos estancado > 25: máxima población. Dejamos para el último punto la medida de aumentar la población máxima, dado que es la más desesperada; el objetivo consiste en proporcionar capacidad extra al algoritmo para que durante un número determinado de iteraciones, las soluciones que a priori no son las mejores, no sean borradas, ya que en algunos casos son las soluciones que realizan la exploración alejándose del mínimo local en el que nos encontramos estancados, dándole varios ciclos para buscar el siguiente mínimo. 3.3.3 Correspondencia Puesto que no se ha podido disponer de una posición y eje óptico con precisión milimétrica, no podemos calcular un error respecto de estos parámetros fácilmente representables en unidades científicas, tendremos que ajustarnos por lo tanto a parámetros obtenidos a partir de la correspondencia entre el modelo DEM y las imágenes tomadas. Las funciones objetivo nos indican cuánto de buena es una solución de la población, de este modo podemos tener una valoración cuantitativa de lo bien o mal que se solapan la imagen y la perspectiva del DEM, teniendo en cuenta las modificaciones sugeridas por el algoritmo genético propuesto. Estas funciones objetivo serán parámetros obtenidos a partir de la correspondencia descrita anteriormente, y nos permitirán descartar aquellas soluciones que den como resultado un valor mayor en un parámetro que queramos minimizar, o menor en uno que queramos maximizar. Podemos comprobar también cuánto de satisfactorio es un resultado analizado de forma visual, siendo una valoración más subjetiva al plasmar la vista del DEM original, con las 29 modificaciones para la posición y eje óptico sugeridas por el algoritmo genético, sobre la fotografía real tomada del entorno. 30 Capítulo 4 – Análisis de los resultados 4.1 Introducción Mediante el planteamiento llevado a cabo en este trabajo, se trata de dar solución al problema de la georeferenciación de imágenes de forma automática identificando en primer lugar aquellos puntos relevantes correspondientes a las cimas de las colinas o montañas, posteriormente se realiza un ajuste mediante algoritmos genéticos entre estos puntos y los homólogos obtenidos a partir del DEM. A continuación se analizan los resultados derivados de la investigación en relación a ambos aspectos, añadiendo también el problema que introduce el sistema óptico debido a las distorsiones propias de tales sistemas. Para la evaluación del método propuesto se ha utilizado la cámara Canon Ixus 55, descrita en el capítulo dos, con la que se han obtenido 60 imágenes, que son las que se han georeferenciado. La resolución en píxeles de tales imágenes es de 2048x1536. La característica común de estas imágenes es que todas ellas poseen cimas de colinas o montañas como elementos determinantes. Los resultados que se muestran a continuación se basan sobre una o dos de tales imágenes que resultan ser suficientemente representativas del total, de forma que la valoración de resultados es válida y extensible para el conjunto de las imágenes utilizadas. 4.2 Resultados de la detección de cimas El método diseñado para la detección de cimas genera unos resultados ciertamente satisfactorios cuando la imagen se capta en condiciones aceptables en el sentido de que se procura que sea una imagen bien contrastada con salientes significativos. Por el contrario, cuando la imagen posee baja calidad, en términos de contraste, la extracción de bordes puede producir fallos debido a la inexistencia de bordes relevantes. Esta misma situación puede producirse con una perspectiva donde las cimas aparecen confusas con el horizonte. En ambos casos la tasa de fallos aumenta, como no podía ser menos, dando lugar bien a la detección de falsas cimas o a la ausencia de detección de cimas verdaderas. Cuando las cimas de las zonas analizadas son arboladas, presentan otro problema adicional, ya que puede detectarse una cima errónea que luego el DEM no contempla, es por esto que las imágenes analizadas en esta investigación son únicamente de cimas rocosas. 31 La situación ideal para este algoritmo son aquellas imágenes en las que aparecen las cimas con un grado de elevación significativo y además puntiagudas ya que en cimas con perfiles curvados, la cima detectada a partir de dos imágenes tomadas desde diferente altura, da lugar a dos cimas distintas separadas entre sí una cierta distancia D como se puede apreciar en el esquema de la figura 4.1 es decir, cuanto menos escarpado es el paisaje, más errores de este tipo pueden aparecer. Podemos ver en la figura 4.1 cómo la inclinación puede llegar a tener un papel muy importante, aunque por lo general, los perfiles de las cumbres no suelen ser tan perfectamente circulares, ni el error en la fotografía tan grande. Figura 4.1 Error producido debido a la curvatura de las cimas. En la figura 4.2 podemos observar tres imágenes tomadas con tres inclinaciones diferentes de la cámara desde la misma posición, donde llegan a aparecer cuatro cimas en un sentido, mientras que en otro sentido no aparece ninguna cima extra. A pesar de esta situación, el método propuesto es capaz de identificar correctamente los puntos de las cimas en las imágenes en relación al DEM, de esta forma en las imágenes de la izquierda y central se identifican dos puntos, mientras que en la de la derecha son cuatro los puntos identificados en ambos casos. No obstante, a tenor de lo expuesto, en el conjunto de imágenes analizadas, la tasa de error entre los puntos de las cimas identificados se sitúa en torno al 5%. 32 En cuanto a las cimas obtenidas a partir de los DEM, son fiables hasta donde lo es el propio DEM, ya que ni su precisión es milimétrica, ni la resolución es la óptima, con lo que pueden existir pequeños errores, que no afectan verdaderamente al funcionamiento del algoritmo. Figura 4.2 Proceso de obtención de cimas del DEM. 4.3 Resultado del algoritmo genético Para validar el algoritmo genético probaremos con dos imágenes, la ya mencionada de la isleta de Las Palmas de Gran Canaria, y otra de los Roques Grande y Chico del Rincón en Tenteniguada. En la figura 4.3 se muestran las soluciones durante una evolución con una configuración de dos funciones objetivo (distancia media y distancia mínima descritas en el capítulo anterior), y otra con una configuración de tres funciones objetivo (distancia media, distancia mínima y distancia al origen de coordenadas descritas también en el capítulo anterior) en el gráfico 3D, figura 4.4. 33 En ambos gráficos podemos observar la distribución de los puntos que representan cada uno de los individuos, siendo su posición la valoración recibida por cada una de las funciones objetivo de la evolución. Al ser un problema consistente en la minimización de dos objetivos, el frente de Pareto que corresponde a los puntos rojos, se sitúa en la parte inferior izquierda, acercándose al eje de coordenadas. Figura 4.3: Mapa de individuos en un instante de la evolución con dos funciones objetivo En la figura 4.3, aparece representado en rojo el frente de Pareto óptimo, y en azul el resto de soluciones existentes en el momento de obtención de la gráfica, que refleja el estado y evolución del sistema. El algoritmo genético trabaja únicamente con los puntos obtenidos mediante los operadores de Sobel y los derivados del DEM, con el fin de aligerar la carga computacional, de modo que no considera todos los puntos del DEM. Una vez plasmados ambos conjuntos de puntos sobre un 34 mismo plano, podemos apreciar si existe solape de los puntos o no. En el caso de la figura 4.5 los puntos azules se corresponden con los puntos obtenidos a partir de la imagen, y los puntos rojos mediante el DEM. Debido al solape es difícil apreciar que los puntos de la imagen están bajo los del DEM, y sólo se aprecian con claridad cuando el algoritmo no consigue solapar alguno de los puntos. Figura 4.4 Mapa de individuos en un instante de la evolución con tres funciones objetivo A la hora de analizar los resultados de forma cualitativa, podemos observar cómo se solapan los puntos de la imagen con los del DEM, figura 4.5, a pesar de existir uno de los puntos desfasado ligeramente. Como se deduce de la figura 4.6, aparecen zonas con una tasa de error mayor que otras. En la imagen de la izquierda se observa que no hay prácticamente error, ya que podemos observar cómo los puntos del DEM siguen el perfil de la montaña, mientras que en la segunda y tercera el error se acentúa, saliéndose los puntos del DEM del contorno de la montaña, o quedándose los puntos por debajo del límite. En la figura 4.7 podemos ver una vista completa de la zona de terreno montañoso donde vemos que a pesar de existir el error descrito anteriormente, existe una aproximación al objetivo. 35 Figura 4.5 Puntos de correspondencia de la imagen con el DEM Analizando cuantitativamente los resultados, comprobamos que el error no llega a ser cero, presentan un error medio de 10 a 30 píxeles de separación entre los puntos de la imagen y los puntos del DEM, ignorando aquellos puntos que no tienen correspondencia, es decir, que fueron detectados en la imagen de entrada y no en el DEM, o viceversa. Figura 4.6 Fallo producido en las cimas. 36 Figura 4.7 Vista centrada en el terreno. En la figura 4.8 se muestra un gráfico sobre la evolución del criterio de distancia media, a lo largo del tiempo de la evolución de un problema planteado al algoritmo genético, a cada ciclo evolutivo se dibuja un punto en la gráfica con el valor de la distancia media de la mejor solución para ese criterio en el momento dado; el resultado es la función descendente que se observa en la figura. Vemos cómo la gráfica va estancándose y saliendo del estancamiento a medida que avanza la evolución. Esto es debido a que existen zonas en las que el mejor individuo es siempre el mismo a lo largo de evoluciones sucesivas, provocando así un estancamiento. El valor de la distancia media, que consideramos como error, toma un valor medio de las diferentes imágenes tomadas desde diferentes perspectivas de la isleta es de 15 píxeles, que a pesar de ser una imagen de 1536x2048 píxeles y poder identificarse como un error pequeño cuantitativamente, cualitativamente se puede considerar como un error demasiado grande al examinar cómo se solapa con las imágenes correspondientes. Es sabido que los Algoritmos Evolutivos no garantizan encontrar la mejor solución en los problemas a los que se enfrentan, ni tampoco son algoritmos deterministas, estas dos deficiencias de la técnica se ven reflejadas en nuestro algoritmo, no obteniendo siempre la misma solución ni tampoco siempre el mismo error en las soluciones, pese a ser bastante regular en este último aspecto. Esto se debe a la gran cantidad de posibles soluciones a las que nos enfrentamos en este problema. 37 Figura 4.8 Distancia media a lo largo de la evolución. Los errores indicados previamente, se deben en cierta medida a las distorsiones introducidas por el sistema óptico. Por lo que si se consideran dichas distorsiones estos errores podrían minimizarse sin lugar a dudas. Ya en el trabajo realizado por Corripio [5] se resalta el problema de la distorsión producida por los sistemas ópticos con los que están equipadas las cámaras de captura de imágenes, debido a las lentes imperfectas que los componen. Esto es así porque por muy buena que sea la óptica del sistema, no se deja de utilizar lentes convergentes con curvaturas que distorsionan ligera e irremediablemente la imagen. 4.4 Problema de distorsión de las imágenes El modelo de formación de imágenes bajo proyección de perspectiva, según las figuras 3.5 y 3.6 es ideal y no se corresponde fielmente a la realidad, ya que las cámaras poseen lentes curvadas que permiten mayor ángulo de visión a costa de distorsionar en mayor o menor medida la imagen procedente de la escena tridimensional [17]. Esta distorsión no es significativa para el uso habitual de las cámaras utilizadas en este trabajo, pero sí que lo es para nuestro caso, ya que una leve distorsión en una fotografía tomada de un valle, a grandes distancias puede suponer un error mucho más importante. Además de la curvatura de las lentes, éstas tienen defectos que producen 38 aberraciones en la propia imagen y que si queremos trabajar con cierta precisión, hemos de tener en cuenta y corregirlas. Todas estas distorsiones no son consideradas a la hora de obtener una imagen virtual de nuestro DEM desde una posición y orientación determinadas, ya que nuestra cámara simulada no posee dichas aberraciones, y por lo tanto, la correspondencia directa de píxeles a celdas no sería fiel a la realidad. Para averiguar la magnitud de la distorsión se obtienen las imágenes a partir de una cámara con una distancia focal fija para cada calibración, hemos de observar una plantilla con un patrón conocido, de esta forma, podemos estimar qué píxeles están donde deberían y cuáles no, para intentar obtener en consecuencia una solución a la problemática expuesta previamente. Existen varios patrones y diferentes métodos para abordar este problema, en nuestro caso usaremos el clásico patrón de cuadrados blancos y negros distribuidos como un tablero de ajedrez, figura 4.9, formado por cuadrados de dimensiones conocidas. De modo simplificado, llamamos aberración de la lente a lo que en realidad es la suma de las aberraciones de las lentes de las que se compone el objetivo utilizado. Cuando el objetivo de una monitorización es el posterior análisis, es impensable pretender llevar a cabo un proceso de georeferenciación espacial directa de una imagen si aparecen aberraciones. Existen diferentes tipos de aberraciones ópticas como las descritas a continuación [17]: • Aberración esférica: debido a la curvatura de la lente, los rayos de luz que inciden más cerca de los bordes, convergen más cerca del objetivo que llegan al eje principal. • Aberración de astigmatismo: se denomina así a los casos en los que no se pueden enfocar objetos verticales y horizontales simultáneamente. • Aberración de coma: ocurre cuando los rayos que convergen oblicuamente, lo hacen en el plano focal, pero no en el lugar que les corresponde. • Aberración de curvatura de campo: el plano focal de un objetivo no es totalmente plano, sino que forma una superficie cóncava hacia el objetivo. • Aberración de distorsión: deformación de las líneas verticales y horizontales. 39 Figura 4.9 Patrón de tablero de ajedrez distorsionado. Si observamos una fotografía de un patrón conocido, realizada con la cámara que hemos usado para este trabajo, podemos constatar las distorsiones comentadas anteriormente, trazando simplemente una línea recta con un editor de imágenes, estas distorsiones son mayores en los bordes de la imagen, figura 4.10.Vemos un fragmento de la parte interior de la figura 4.9 ampliado, sobre el que hemos trazado una línea roja con un editor gráfico, esta línea, es recta, y nos permite observar cómo un patrón originalmente formado por cuadrados blancos y negros de aristas rectas, se convierte en un patrón de cuadrados con aristas ligeramente curvadas. Si la línea roja estuviera pintada sobre el patrón real, seguiría las aristas que conforman la base de los cuadrados del fragmento mostrado, pero al ser pintado sobre la imagen obtenida por la cámara, las deformaciones producidas por ésta se delatan. Como se ha mencionado previamente, este problema ya se resaltó en el trabajo realizado por Corripio [5], donde para evitarlo se consideró sólo una parte de la imagen, la central, ya que dichas aberraciones son mucho menores y no generan problemas a la hora de hacer la correspondencia de puntos. 40 Figura 4.10 Zoom en la distorsión, la línea roja es la línea recta y la base de los cuadrados deberían estar sobre ella. Tras diversas pruebas con las imágenes utilizadas en este trabajo de investigación en relación a la eficiencia del algoritmo evolutivo propuesto, se constata que eliminando aquellos puntos que se encuentran en los bordes de la imagen, y quedándonos únicamente con los centrales, obtenemos unos resultados notablemente superiores a los obtenidos anteriormente. De esta forma, los errores se reducen a una media de 2 píxeles, como podemos observar en la figura 4.11, que representa la distancia media del mejor individuo de la población según ese criterio en cada ciclo de evolución, en el eje horizontal tenemos los ciclos evolutivos, y en el eje vertical el valor de distancia media del mejor individuo de la población en ese ciclo. Para este ejemplo hemos tomado una imagen además del escenario ya visto, para aislar en el centro de la fotografía los puntos de interés con los que se hará la correspondencia, consiguiendo un solape mucho mejor que en el anterior escenario en el que los puntos de interés estaban dispersos a lo largo de toda la imagen, alejados del centro, y por tanto sufriendo más los efectos de la distorsión, figura 4.12. Además hemos tomado la entrada del localizador GPS como precisa al 100%, no siendo necesario desplazar entonces la posición del sistema óptico, tan solo el eje. Podemos observar cómo el solape de los puntos es prácticamente perfecto, se han eliminado además los puntos no visibles por la perspectiva, quedando detrás de zonas más elevadas, de modo que quede más limpio el DEM. 41 Figura 4.11 Distancia media a lo largo de la evolución. Figura 4.12 Imagen con DEM solapado 42 Capítulo 5 - Conclusiones y trabajo futuro 5.1 Conclusiones Como conclusión podríamos extraer, que ayudarnos de algoritmos genéticos para ajustar los parámetros espaciales de la cámara, puede resultar una apuesta acertada; la capacidad de los algoritmos genéticos para buscar en espacios de soluciones extensos, o como en este caso, infinito, hace que corregir dichos parámetros pueda realizarse de una forma eficiente, es decir, sin necesidad de analizar todo el espacio de soluciones. Sin embargo, debido a los márgenes de error de los datos de entrada, y a la amplitud del espacio de soluciones, no es suficiente basarse en un algoritmo NSGA-II o un SPEA-II, sino que sería necesario un método que, a pesar de poder estar basado en los algoritmos anteriores, se valiera de otras técnicas para afrontar de forma más precisa este problema. El hecho de diseñar un proceso automático basado en la propuesta formulada en este trabajo, abre sin duda, importante perspectivas que pueden ser desarrolladas para su aplicación a otros tipos de imágenes. De hecho, esta técnica podría aplicarse a distintos ámbitos fotográficos, ya sea en fotografías oblicuas o aéreas cambiando únicamente el criterio de detección de puntos de interés de las imágenes y el DEM, que en este caso es apropiado para la detección de las cimas, pero para otro problema puede ser completamente inservible, por ejemplo detección de puntos de interés en la línea de costa. A pesar de todo, el camino de los algoritmos genéticos para este problema no termina aquí, todavía pueden mejorarse tanto las funciones objetivo cómo incluir nuevas metodologías en el comportamiento de los individuos para conseguir una evolución más efectiva. Además, debe mejorarse la corrección de las imágenes, ya que se pierde mucha información si por cada imagen recortamos los márgenes. 5.2 Trabajo futuro El trabajo de investigación desarrollado se ha fundamentado en el hecho de la existencia de elementos tales como cimas o montículos que permiten establecer puntos significativos entre las imágenes y el DEM para la georeferenciación. Esto indica claramente, que el proceso no es 43 aplicable en imágenes carentes de tales elementos, por esta razón una propuesta de futuro consiste en desarrollar nuevas estrategias que permitan identificar puntos significativos incluso ante la ausencia de cimas en las imágenes. La idea consiste en tratar de generalizar el proceso hasta donde sea posible. En este trabajo se ha propuesto como técnica de ajuste la optimización basada en algoritmos genéticos, bajo esta perspectiva cabe la posibilidad de utilizar otras técnicas de ajuste basadas probablemente en técnicas de optimización, tales como enfriamiento simulado[18] [19] o redes neuronales de Hopfield [20] [21] entre otras posibles opciones. El objetivo sería reducir al máximo los errores residuales que no se han podido resolver totalmente mediante la aplicación de la técnica basada en algoritmos genéticos. Estos dos métodos poseen la ventaja de que su evolución puede ser perfectamente controlada mediante las variaciones observadas en una función de energía que se define a tal efecto. Otra técnica a contemplar es la optimización anidada [22], dado que tenemos múltiples pequeños problemas de optimización para cada posición de la cámara, podría ser interesante para evitar evaluar individuos que pertenezcan a una posición que ya ha sido optimizada. Por otro lado, se ha puesto de manifiesto cómo el sistema óptico introduce aberraciones y distorsiones ópticas que afectan directamente a los resultados. Una de las opciones para minimizar estos errores estriba en el hecho de aplicar procesos de calibración de cámaras para determinar los parámetros intrínsecos de las mismas y corregir así los errores debidos a tales distorsiones y aberraciones [17]. 44 Bibliografía [1] M. Cramer, D. Stallmann, N.Haala “Direct georeferencing using gps/Inertial exterior orientations for photogrametric applications” IAPRS, Vol. XXXIII, Amsterdam, 2000 [2] Bäumker, M., Heimes, F.J., “New Calibration and Computing Method for Direct Georeferencing of Image and Scanner Data Using the Position and Angular Data of an Hybrid Inertial Navigation System”, OEEPE Workshop, Integrated Sensor Orientation, Hannover 2001 [3] Müller, Ru., Lehner, M., Müller Ra., Reinartz, P., Schroeder, M., Vollmer, B., 2002. A program for direct georeferencing of airborne and spaceborne line scanner images, ISPRS, Commission I Mid-Term Symposium, Denver, CO, USA, 10-15 November 2002 [4] C. Ressl, "The Impact of Conformal Map Projections on Direct Georeferencing," presented at Photogrammetric Computer Vision, Vienna, 2002. [5] J. G. Corripio “Snow surface albedo estimation using terrestrial photography”, Int. J. Remote Sensing, 20 December, 2004 [6] Pajares, G. y de la Cruz, J.M. Visión por Computador: imágenes digitales y aplicaciones. RA- MA, 2007 [7] C.A. Coello Coello, “A Short Tutorial on Evolutionary Multiobjective Optimization”, Lecture Notes in Computer Science, Evolutionary Multi-criterion Optimization 2001, pp. 21-40. [8] D. Van Veldhuizen, G. Lamont, “Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art”, Evolutionary Computation, 8-2 (2000) pp. 125-147. [9] D. Van Vedhuizen, G. Lamont, “Multiobjective Evolutionary Algorithm Research: A History and Analysis”. Technical Report TR-98-03, Department of Electrical and Computer Engineering, Air Force Institute of Technology, Wright-Patterson AFB, Ohio (1998). [10] E. Zitzler, M.Laumanns, L. Thiele, “SPEA2: Improving the Strength Pareto Evolutionary Algorithm” TIK-Report 103 May 2001 [11] J. Mendoza, L. Villaleiva, M. Castro and E. Lopez. "Evaluación de Algoritmos Evolutivos Multiobjetivos para la Toma de Decisiones en el Problema de Reconfiguración de Redes Eléctricas de Media Tensión". XVIII Congreso de la Asociación Chilena de Control Automático ACCA. Santiago, Chile. 2008. [12] O. Roudenko, “Application des Algorithmes Evolutionnaires aux Problemes d'Optimisation Multi-Objectif avec Contraintes”, phD Thesis, Marzo 2004, Ecole Polytechnique. 45 [13] A. Messac, A. Ismail-Yahaya, C.A. Mattson, “The normalized normal constraint method for generating the Pareto Frontier”, Structural and Multidisciplinary Optimization, 25 (2003) pp. 86-98. [14] K. Deb, S. Agrawal, A. Pratap, T. Meyarivan, “A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multiobjective Optimization: NSGA-II”, Sixth International Conference on Parallel Problem Solving from Nature (PPSN-VI), Paris (2000), pp. 849- 858. [15] K. Deb, A. Pratap, S. Agrawal, T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation 6 (2), 182-197, 2002. [16] S. Alonso, J. Jiménez, H. Carmona, B. Galván, G. Winter, B. González “ Comportamiento de un Algoritmo Evolutivo Flexible para problemas de optimización continua” In Proc MAEB 2009 [17] Tsai, R.Y. (1987). “A Versatile Camera Calibration Technique for High-Accuracy 3D Machine Vision Metrology Using Off-the-Self TV Cameras and Lenses.”, IEEE Trans. Robotics Automation, 3(4) August 1987 . [18] Kirkpatrick, S., 1984. Optimization by simulated annealing: quantitative studies. Journal of Statistical Physics 34 (5-6), 975-984. [19] Laarhoven van, P.J.M., Aarts, E.H. L., 1988. Simulated Annealing: theory and applications, first ed. Kluwer Academic Publishers, Boston, MA. [20]J.J. Hopfield and D.W. Tank, “Computing with neural circuits: a model,” Science, vol. 233, pp. 625-633, 1986. [21] G. Joya, M.A. Atencia and F. Sandoval, “Hopfield neural networks for optimization: study of the different dynamics,” Neurocomputing, vol 43, pp. 219-237, 2002. [22] Blas J. Galván “Optimización del Diseño de sistemas técnicos en base a criterios de Confiabilidad usando Algoritmos Evolutivos anidados” In Proc. VII Congreso de Confiabilidad. 2006. 46 Capítulo 1 - Introducción 1.1 Identificación del problema 1.2 Objetivos de la investigación 1.3 Aportaciones a la investigación 1.4 Organización de la memoria Capítulo 2 - División del problema de la georeferenciación 2.1 Introducción 2.2 Datos de entrada 2.2.1 Modelo Digital de Terreno 2.3 Fotografía Oblicua 2.4 Posición y orientación 2.5 Selección de coordenadas 2.6 Ajuste de la relación entre puntos Capítulo 3 - Resolución del problema 3.1 Descripción de la solución propuesta 3.2 Identificación de los puntos de interés 3.3 Algoritmo para la corrección 3.3.1 Algoritmos genéticos multiobjetivo 3.3 Diferencias de la optimización multi-objetivo con la mono-objetivo: Algoritmo NSGA-II Propuesta de solución al problema de georeferenciación Individuo: Funciones Objetivo: Funciones de cruce: Funciones de Mutación 3.3.2 Evolución Flexible 3.3.3 Correspondencia Capítulo 4 – Análisis de los resultados 4.1 Introducción 4.2 Resultados de la detección de cimas 4.3 Resultado del algoritmo genético 4.4 Problema de distorsión de las imágenes Capítulo 5 - Conclusiones y trabajo futuro 5.1 Conclusiones 5.2 Trabajo futuro