Repositorio Institucional de Documentos

Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es ! Proyecto Fin de Carrera Desarrollo de un sistema de seguimiento de usuarios con iPhone para visualizarlos en un modelo 3D Autor/es Jorge Pérez Lahera Director/es y/o ponente Ana Cristina Murillo Arnal Sune Lehmann Jørgensen Michael Frederiksen Escuela de Ingeniería y Arquitectura 2012 Desarrollo(de(un(sistema(de(seguimiento(de(usuarios( con(iPhone(para(visualizarlos(en(un(modelo(3D( RESUMEN' El( objetivo( de( este( proyecto( es( desarrollar( un( sistema( de( seguimiento( de( usuarios(con(un(iPhone(y(un(modelo(3D(del(campus(de(la(Technical(University(of( Denmark.(El(usuario(podrá(activar(el(seguimiento(tras(abrir(una(aplicación(en(el( iPhone( siempre( y( cuando( se( encuentre( en( alguna( de( las( áreas( donde( haya( un( modelo( 3D( disponible.( Los( usuarios( que( hayan( activado( el( seguimiento( serán( mostrados(en((estos(modelos(3D(en(forma(de(avatares.(Los(modelos(3D(junto(con( los(avatares(pueden(ser(visualizados(usando(cualquier(navegador(de(escritorio( en(la(página(web(realsite.dk.( ( Los(sensores(GPS(de(los(Smartphones(no(son(normalmente(muy(precisos.(Para( desarrollar( buenos( algoritmos( en( el( sistema( de( seguimiento( requerido,( la( precisión( de( este( sensor( tiene( que( ser( analizada.( Por( esta( razón( el( proyecto( empieza(con(un(extenso(estudio(de(la(precisión(de(los(sistemas(de(localización(en( el( iPhone( y( de( los( parámetros( que( pueden( configurarse.( Se( estudian( tanto( posiciones(fijas(como(en(movimiento.(Este(estudio(revela(que(el(error(medio(en( posiciones(estáticas(es(en(torno(a(8(metros(y(bastante(mayor(para(las(posiciones( en(movimiento.(Sin(embargo(es(muy(rápido(determinando(la(primera(posición(lo( cual(lo(hace(en(menos(de(10(segundos(en(la(mayoría(de(los(casos.(Utilizando(los( resultados( de( este( estudio,( se( han( diseñado( varios( filtros( para( eliminar( las( posiciones(menos(precisas.(Además,(también(se(ha(desarrollado(una(técnica(que( permite(detectar(cuando(el(usuario(entra(dentro(de(un(edificio(sin(usar(ninguna( información(adicional(más(que(la(que(los(servicios(de(localización(ofrecen.( ( Las( dos( partes( mas( importantes( de( este( sistema( han( sido( desarrolladas( en( su( totalidad(en(este(proyecto(fin(de(carrera.(Estas(son(una(aplicación(para(el(sistema( operativo( móvil( iOS( y( un( algoritmo( para( representar( a( los( avatares( de( los( usuarios(en(los(modelos(3D.(La(aplicación(recoge(las(posiciones(de(los(usuarios,( utilizando(el(GPS(del(dispositivo,(las(filtra,(las(guarda(y(las(manda(a(un(servidor( de( internet( donde( son( almacenadas( en( una( base( de( datos.( También( permite( visualizar( las( sesiones( anteriores( en( las( que( el( seguimiento( ha( sido( activado( y( tomar(una(foto(que(será(utilizada(en(el(avatar(del(usuario.(La(representación(de( los( avatares( en( el( modelo( no( se( puede( llevar( a( cabo( con( las( posiciones( que( el( dispositivo( iOS( obtiene( ya( que( no( son( suficientemente( precisas.( Por( lo( que( se( diseñó(un(algoritmo(que(genera(a(partir(de(las(posiciones(GPS(recibidas(una(ruta( realista,( factible( y(libre( de( obstáculos( en(el( modelo.( Un( detalle(importante(por( ejemplo,( es( que( hace( que( los( avatares( utilicen( escaleras( y( puertas( de( edificios( cuando( se( detecta( que( han( cambiado( de( altitud( o( entrado( a( un( edificio( respectivamente.( ii Índice general 1. Introducción 1 1.1. Motivación .............................. 2 1.2. Colaboración con Utopian City_Scape . . . . . . . . . . . . . . . 4 1.3. Requerimientos del proyecto . . . . . . . . . . . . . . . . . . . . . 4 1.4. Estructura de esta memoria . . . . . . . . . . . . . . . . . . . . . 4 2. Estudio de la precisión de los servicios de localización en iOS 7 2.1. Introducción.............................. 7 2.2. Configuración experimental . . . . . . . . . . . . . . . . . . . . . 9 2.3. Análisis de posiciones estáticas . . . . . . . . . . . . . . . . . . . 10 2.3.1. Comparación del error horizontal para diferentes precisionesdeseadas ......................... 10 2.3.2. Precisión observada versus estimada . . . . . . . . . . . . 12 2.3.3. Tiempo para la primera posición (time to first-fix) . . . . 12 2.3.4. Comparación entre diferentes dispositivos . . . . . . . . . 13 2.4. Análisis de posiciones en movimiento . . . . . . . . . . . . . . . . 15 2.4.1. Como medir la ruta real . . . . . . . . . . . . . . . . . . . 15 2.4.2. Error horizontal calculado . . . . . . . . . . . . . . . . . . 16 2.4.3. Filtrado de las posiciones más imprecisas . . . . . . . . . 17 2.4.4. Tiempo y velocidad entre diferentes posiciones . . . . . . 20 2.4.5. Detectar cuando el usuario entra a un edificio . . . . . . . 20 3. Representación de las rutas en el modelo 3D 23 3.1. Descripción del problema . . . . . . . . . . . . . . . . . . . . . . 23 3.1.1. Transformación de coordenadas . . . . . . . . . . . . . . . 24 3.1.2. Atravesando edificios y posiciones encima de los edificios . 24 3.1.3. Cambios de altitud en la ruta . . . . . . . . . . . . . . . . 24 3.1.4. Cambio rápido de dirección . . . . . . . . . . . . . . . . . 25 iv ÍNDICE GENERAL 3.2. Herramientas y conceptos relacionados . . . . . . . . . . . . . . . 25 3.3. Solucióndiseñada........................... 26 3.3.1. Requerimientos del sistema . . . . . . . . . . . . . . . . . 26 3.3.2. Transformación de coordenadas geográficas a DTU y viceversa ............................ 27 3.3.3. Algoritmos diseñados para representar el avatar en el modelo 28 3.4. Resultados............................... 33 4. Sistema final 35 4.1. Arquitectura del sistema . . . . . . . . . . . . . . . . . . . . . . . 35 4.2. Aplicaciónmóvil ........................... 36 4.3. Aplicación en el servidor . . . . . . . . . . . . . . . . . . . . . . . 38 4.4. Reproductor en realsite.dk . . . . . . . . . . . . . . . . . . . . . . 39 5. Conclusión 41 A. Routes maps and graphs 43 A.1. Routes which go inside a building . . . . . . . . . . . . . . . . . . 43 A.2. Outdoor routes with curves . . . . . . . . . . . . . . . . . . . . . 48 A.3.Straightroutes ............................ 52 B. Definition of DTU local coordinate system 55 C. Routes maps and graphs after executing the algorithm 59 D. Memoria en inglés 69 Bibliografía 181 Capítulo 1 Introducción Este proyecto fin de carrera fue llevado a cabo en la empresa Utopian city_scape (UCS), Copenhague, como parte de un acuerdo de colaboración con la Technical University of Denmark (DTU). El alumno de la EINA era estudiante de intercambio Erasmus en la DTU durante el curso 2011 – 2012 durante el que realizó este proyecto. UCS ha estado desarrollando modelos 3D de complejos de edificios durante los últimos cinco años. Ejemplos de estos son los modelos del campus de la DTU o de la fábrica de Carlsberg. El propósito de esta empresa es el desarrollar modelos 3D interactivos usando tecnología de videojuegos. Todos estos modelos 3D son accesibles usando la página web de la compañía (realsite.dk). Pero ahora UCS quiere dar un paso adelante conectando estos modelos con el mundo real aprovechando la popularización de los Smartphones. El objetivo de este proyecto fin de carrera es desarrollar un sistema que obtendrá las posiciones de los usuarios y los representará en el modelo 3D del área correspondiente. Todos las pruebas desarrolladas en este proyecto han sido desarrolladas en el área del campus de la DTU ya que UCS ha desarrollado un modelo 3D muy preciso de ella. 2 Introducción 1.1. Motivación 2011 fue el primer año en la historia en el cual se distribuyeron más smartphones que PCs1. De acuerdo con este estudio llevado a cabo por Catalyst, el número de smartphones y tablets distribuidos fue de 488 millones mientras que el de portátiles y ordenadores de escritorios fue de 414 millones. Estos dispositivos contienen un gran número de sensores como GPS, acelerómetro y brújula digital. Además, permiten a los usuarios estar conectados a internet de forma continua utilizando las redes celulares. Un estudio del mercado de los smartphones puede encontrarse en el apéndice D capítulo 1.1. La proliferación de estos smartphones esta cambiando la forma en la que los usuarios se conectan a internet, nuevos servicios han sido creados utilizando estas plataformas en los últimos años. Entre estos servicios uno de los más populares son los servicios basados en localización o LBS de sus siglas en inglés. Ejemplos de estos son la redes sociales Foursquare2oFacebookplaces 3,lascualespermiten alosusuarioscompartirsulocalizaciónconsusamigos.Otrosejemplosdeestos servicios son las aplicaciones (llamadas apps en este documento) de seguimiento de usuarios, las cuales son similares al sistema desarrollado en este proyecto fin de carrera como son Endomondo4,Runkeeper 5,Runtastic 6yGlympe 7.Mientras que las tres primeras sirven para monitorizar la actividad deportiva. La última sirve para compartir la posición del usuario en tiempo real. Sin embargo, el sistema desarrollado en este proyecto, a diferencia de los sistemas de seguimiento descritos anteriormente y de la mayoría que se encuentran en la actualidad en el mercado no utiliza un mapa plano para representar a los usuarios. Usa un modelo 3D de alta precisión del área en el que se llevo a cabo el seguimiento del usuario. Esto hace que este sistema sea tan innovador que no se han encontrado sistemas similares en el mercado. Aunque la mayoría de mapas electrónicos que son normalmente utilizados en ordenadores o Smartphones son planos como Google Maps o OpenStreetMap, el uso de mapas 3D se esta convirtiendo más popular en los últimos años. Google Maps tiene mapas 3D de las ciudades más importantes del mundo. Además otras compañías como Upnext8 producen mapas 3D de ciudades. El pasado junio, Apple anunció que la nueva versión de iOS, iOS 6, introducirá unos nuevos mapas 3D desarrollados por la 1http://www.engadget.com/2012/02/03/canalys-more-smartphones-than-pcs-shipped-in-2011/ 2https://foursquare.com/ 3http://www.facebook.com/about/location/ 4http://www.endomondo.com/login 5http://runkeeper.com/ 6http://www.runtastic.com/ 7http://glympse.com/ 8http://upnext.com 1.1 Motivación 3 propia compañía. Un ejemplo de estos mapas 3D se muestra en la Figura 1.1. Todos estos movimientos indican que los mapas 3D son el futuro de los mapas digitales. Figura 1.1: Nuevos mapas 3D en iOS 6a ahttp://www.apple.com/ios/ios6/#maps UCS ha estado desarrollando modelos 3D durante más de cinco años. El seguimiento de usuarios usando estos modelos 3D producirá una novedosa representación de la realidad que nunca ha sido desarrollada anteriormente. Este proyecto fin de carrera es una prueba de este concepto. El uso de modelos 3D precisos añade información adicional al seguimiento de usuarios que puede ser utilizada para aumentar la precisión como es demostrado en este proyecto. El sistema puede diferenciar donde están los edificios y el terreno, por lo tanto el usuario puede ser colocado en cada momento en el lugar correcto. Otra información que puede ser fácilmente obtenida es la altura de cualquier punto en el modelo, la pendiente de una superficie, la localización de las carreteras, las puertas de los edificios y las escaleras etc. Toda esta información junto con algoritmos inteligentemente diseñados puede transformar rutas muy imprecisas en rutas creíbles que pueden ser representadas en un modelo 3D de alta precisión. 10 Estudio de la precisión de los servicios de localización en iOS En el iPhone, los datos fueron obtenidos utilizando una aplicación que fue desarrollada completamente como parte de este proyecto fin de carrera. Esta aplicación permite empezar y terminar el seguimiento, al mismo tiempo que guarda todas las posiciones recibidas en una base de datos en la memoria interna del teléfono. También permite observar las sesiones que están guardadas en la base de datos en un mapa y exportarlas al ordenador o enviarlas al servidor de UCS. Parte del código desarrollado en esta aplicación fue utilizado en el desarrollo de la aplicación para el sistema final. El Garmin permite exportar las rutas obtenidas a un ordenador en forma de ficheros GPX. De esta forma la latitud, longitud y el tiempo fueron obtenidos para cada posición. El fichero GPX fue analizado usando gpxpy (GPX file parser)2.TodosloscálculosfuerondesarrolladosenPhyton 3.Exceptolaconversión de coordenadas geográficas a UTM (Universal Transverse Mercator) que fue desarrollado en Java utilizando el datum WGS84 (World Geodetic System 1984). Todas las gráficas mostradas en esta memoria se obtuvieron utilizando la librería de Python matplotlib 4.Lascoordenadasdelasposicionesestáticas analizadas fueron obtenidas de mapas de alta precisión proporcionados por UCS. 2.3. Análisis de posiciones estáticas Esta sección analiza la precisión y la repercusión sobre esta de varios parámetros que los sistemas de localización en iOS proporcionan para posiciones estáticas. Además, mide el tiempo para la primera posición y compara la precisión del iPhone con la del reloj Garmin. 2.3.1. Comparación del error horizontal para diferentes precisiones deseadas Los servicios de localización en iOS permiten al desarrollador configurar la precisión deseada para la localización en metros. Esta sección analiza la influencia de este parámetro, el cual se configura mediante la propiedad desiredAccuracy, sobre la precisión real. Los valores analizados en este estudio son los que proporciona el sistema operativo por defecto y pueden ser observados en la tabla 2.1. 2https://github.com/tkrajina/gpxpy 3http://www.python.org 4http://matplotlib.sourceforge.net 2.3 Análisis de posiciones estáticas 11 Tabla 2.1: Valores de la propiedad desiredAccuracy utilizados en este análisis Name of the accuracy constant value kCLLocationAccuracyBestForNavigation -2 kCLLocationAccuracyBest -1 kCLLocationAccuracyNearestTenMeter 10 (custom value) 50 En la figura 2.2 se puede observar el error horizontal en metros para las diferentes precisiones deseadas. Como era de esperar, se puede observar que los resultados son muy parecidos para las precisiones best for navigation, best and nearest 10 m,mientrasquesonalgomásimprecisosparanearest 50 m.Aunquelamayoría de las posiciones tienden a estar en la diagonal que van del primer al tercer cuadrante, no se puede sacar ninguna conclusión de ello debido a las limitaciones del experimento. La tabla 2.2 muestra los números exactos de este error. Como puede comprobarse la diferencias entre utiliza los tres parámetros más precisos son mínimas. Incluso siendo algo mejores para nearest 10m.Applerecomienda en la documentación oficial solo utilizar best for navigation en el caso de que el dispositivo este conectado a una fuente de energía por lo que tanto best como nearest 10m son buenos valores a utilizar en el sistema que se esta desarrollando en este proyecto. Figura 2.2: Gráfica de las distintas posiciones recibidas para diferentes precisiones deseadas 12 Estudio de la precisión de los servicios de localización en iOS Tabla 2.2: Error horizontal en metros para las diferentes precisiones deseadas analizadas Accuracy min max mean RMSE Best for navigation 1.3581 23.3408 9.1048 11.2679 Best 0.5834 19.5479 9.2488 11.6861 Nearest 10 m 0.4516 43.0338 8.7107 11.3551 Nearest 50 m 0.7861 57.5612 17.2975 26.0383 Zandbergen desarrollo un estudio similar utilizando un iPhone 3G[Zan09], obteniendo un error medio de 6.9 m, con un error mínimo de 0.4 m máximo de 18.5 m. En nuestro caso el error medio es 2 metros mayor, esta diferencia se puede atribuir principalmente a que en el estudio de Zandbergen el dispositivo estaba colocado en una posición ideal mientras que en nuestro caso estaba colocado en el bolsillo del pantalón. 2.3.2. Precisión observada versus estimada Los mismos datos experimentales que en la sección anterior fueron utilizados en esta sección para comprobar como de preciso es el parámetro horizontalAccuracy que iOS proporciona. Este parámetro representa una aproximación del error en metros que esa posición tiene. Durante este análisis se obtuvieron posiciones cuyo error variaba de 15 m a 149000 m. Los valores más comunes son por debajo de 100 m. La figura 2.3 muestra el error real, el cual se ha calculado, frente al error estimado por iOS. Las conclusiones que se pueden sacar de esta gráfica son que el error predicho es siempre mayor al real. Aunque la correlación entre el predicho y el real es muy baja, existe como se puedo observar en el capítulo 2.4.3 en el apéndice D. Para lo que realmente es útil este parámetro es para diferenciar las posiciones muy imprecisas de las que no lo son tanto ya que estas suelen tener valores de este mayores de 100m. 2.3.3. Tiempo para la primera posición (time to first-fix) Apartedelaprecisióndelasposicionesrecibidas,eltiempoquesetardaen obtener la primera posición es un parámetro también muy importante. Esto se mide normalmente con el llamado en ingles time to first fix (TTFF). En este estudio solo el inicio frío (cold start en inglés) es considerado, el cual mide el 2.3 Análisis de posiciones estáticas 13 Figura 2.3: Comparación entre el error horizontal estimado por iOS y el real tiempo en recibir la primera posición cuando el dispositivo no tiene ninguna información que ayuda a la localización almacenada en la memoria. Puesto que Apple no proporcionan ninguna información de cómo los sistemas de localización almacenan la información. Hay que considerar que los resultados de este estudio dependen enormemente de la velocidad de la conexión a internet disponible durante el test. Ya que gran parte de la información que los sistemas de localización utilizan es descargada de internet. El estudio fue llevado a cabo para tres áreas, en cada una de ellas se calculó la posición en interior y exterior. Este estudio considera como primera posición la primera que tiene un error horizontal igual o mejor de 100 m. Como puede observarse en los resultados de la tabla 2.3, en todos los casos se recibe una posición suficientemente precisa en los primero 15 segundos y en la mayor parte de los casos en menos de 10. Por lo que podemos concluir que la velocidad yladisponibilidaddelossistemasdelocalizacióneniOSsondosdesusmejores características. 2.3.4. Comparación entre diferentes dispositivos Para terminar con el análisis de las posiciones estáticas, el iPhone 3GS el cual ha sido utilizado para todo el análisis es comparado con el Garmin forerunner 14 Estudio de la precisión de los servicios de localización en iOS Tabla 2.3: Tiempo en segundos para recibir una posición con un error horizontal estimado menor que 100 m Location Time (s) indoor Time (s) outdoor 308 5.45 6.58 321 9.74 3.27 404 4.81 13.21 mean 6.67 7.69 405CZ. Como puede observarse en la figura 2.4, las posiciones obtenidas con el Garmin son en casi todos los casos más precisas que las del iPhone. Un hecho a remarcar es que todas las posiciones obtenidas por el reloj Garmin se encuentran dentro del círculo de radio 10m. Esto significa que cuando el Garmin proporciona una posición esta tiene siempre una precisión de por lo menos 10 m. Como puede observarse en la tabla 2.4, las posiciones que el iPhone calcula son en media 1.7 metros más imprecisas. Además el error medio en este análisis para el iPhone es 1 metro menor, por lo que se puede concluir que el Garmin es en media por lo menos 2 metros más preciso que el iPhone. Figura 2.4: Gráfica de las distintas posiciones recibidas por iPhone 3GS y Garmin forerunner 405 en metros 2.4 Análisis de posiciones en movimiento 15 Tabla 2.4: Comparación del error horizontal entre un iPhone 3GS y un Garmin forerunner 405 en metros Device min max mean RMSE iPhone 0.7970 55.3629 6.9375 8.8528 Gramin watch 1.4947 8.9773 5.263 5.8425 2.4. Análisis de posiciones en movimiento Esta sección analiza la precisión que el iPhone 3GS tiene en posiciones en movimiento. La precisión real, la estimada, el tiempo entre posiciones recibidas y entre posiciones diferentes recibidas fueron analizados para encontrar patrones repetitivos para diferentes acciones que pueden suceder en una ruta como que el usuario entre en un edificio. 2.4.1. Como medir la ruta real En el primer problema que surge cuando se quiere medir el error en una ruta es como se puede medir la ruta real. Ya que para medir el error real hay que tener en cuenta no solo las posiciones por las que paso el usuario sino también en que momento paso por cada posición. Una primera solución podría ser dejar el tiempo fuera del análisis como se realizo en el estudio [ZB11]. Pero en una aplicación de seguimiento como la que se esta desarrollando en este proyecto el tiempo es un parámetro clave por lo que tiene que ser tenido en cuenta en el análisis. Además en este análisis se observo que iOS tiende a proporcionar la misma posición varias veces hasta que proporciona una nueva, cual puede indicar que el tiempo proporcionado en estas posiciones no es muy preciso. Así pues se necesita medir las posiciones de la ruta real y el instante temporal en el que se paso por ellas. Debido a los medios de los que se dispone en este análisis la forma más sencilla de hacer esto era utilizando otro receptor GPS más preciso que el iPhone. El Garmin forerunner 405 CX fue utilizado para esta función. Este dispositivo es más de 2 metros más preciso que el iPhone en posiciones estáticas como observó en la sección anterior pero mucho más preciso en posiciones en movimiento como se puede observar en el apéndice A. Proporciona nuevas posiciones en menos tiempo y estas son más precisas que las proporcionadas por el iPhone. 16 Estudio de la precisión de los servicios de localización en iOS Se calculo el error para cada posición que el iPhone proporciono, asumiendo que la velocidad entre dos posiciones consecutivas del Garmin era constante. Así pues el instante en el que el iPhone recibió la posición es calculado para obtener un punto en la ruta del garmin. La distancia entre estos dos puntos se calcula como la distancia euclídea de sus coordenadas UTM. Para representar las rutas en un mapa se utilizo Google static maps API 5. Como puede verse en el apéndice A, 9 rutas fueron medidas durante los meses de febrero y marzo del 2012 para el desarrollo de este proyecto. 2.4.2. Error horizontal calculado Analizando el error medio de los tres diferentes tipos de rutas que son presentados en la tabla 2.6, puede observarse que tienen diferentes valores. Éste es mayor para las rutas que cruzan un edificio que par el resto. Este resultado es el esperado ya que el dispositivo recibe las señales procedentes de los satélites GPS mucho más atenuadas cuando entra dentro de un edificio, aumentándose el error de las posiciones recibidas. Las rutas rectas deberían tener mejor error medio que las rutas con curvas pero como puede observarse esto solo se cumple para una de las rutas rectas. La ruta “From Nils Koppels Alle to Knuth-Wintherfeldts biking” tiene un error medio de 30.32 lo que la hace la ruta con más error medio entre todas las exteriores analizadas. Analizando esta ruta en el apéndice A, se puede observar que esta ruta es la única que recibe una nueva posición cada segundo. Así que se puede asumir que el tiempo que iOS proporciona para cada posición a esta frecuencia no es el mas preciso. Tabla 2.5: Error horizontal para las diferentes rutas analizadas Route Min Max Mean RMSE Rutas que entran dentro de un edificio From 308 to 342 7.46 188.34 26.59 38.80 From 341 to 101 2.28 175.08 30.86 40.05 From 343 to 308 1.04 133.87 36.23 44.07 From library to 229 6.13 132.91 35.49 47.02 Rutas exteriores con curvas From 115 to library 4.24 99.34 24.94 30.97 From 229 to 115 3.24 61.52 26.33 29.92 From Nordvej to 302 biking 4.62 93.08 26.57 33.60 Rutas exteriores rectas From Knuth-Wintherfeldts to Nils Koppels Alle walking 3.76 41.47 17.83 19.02 From Nils Koppels Alle to Knuth-Wintherfeldts biking 4.69 218.90 30.32 38.33 All 1.04 218.90 27.13 35.10 5Static Maps API V2 Developer Guide https://developers.google.com/maps/ documentation/staticmaps/ 2.4 Análisis de posiciones en movimiento 17 Como puede observarse el error medio para todas las rutas es de 27.3 m, el cual es bastante mayor que el obtenido en posiciones estáticas. Esto se debe a dos razones, a que realmente el error es mayor y a que el método utilizado para calcularlo introduce un error adicional. Como puede verse en el histograma en la figura 2.5, la mayor parte de las posiciones tienen un error comprendido entre 10 y 20 m. Figura 2.5: Histograma del error horizontal para todas las rutas 2.4.3. Filtrado de las posiciones más imprecisas Aunque Apple no proporciona ninguna información de cómo diferenciar entre que sistema de posicionamiento ha sido utilizado en cada posición. En este estudio se ha diseñado un sistema basado en la observación de las posiciones recibidas. Si la posición ha sido obtenida utilizando posicionamiento Wi-Fi este valor es de 65 o 100 mientras que si se ha obtenido utilizando posicionamiento celular es un numero sin decimales y normalmente mayor que 1.000. Mientras que en el caso de que la posición ha sido obtenido utilizando GPS este parámetro tiene siempre posiciones decimales. Este descubrimiento va a ser muy útil a la hora de decidir que posiciones deben de ser filtradas. En todos los mapas de esta memoria las líneas azules indican las rutas obtenidas con el Garmin, las rojas son las obtenidas por el iPhone y las verdes son las obtenidas después de aplicar un filtro a las rutas de este último. Como se puede observar en los mapas del apéndice A en la rutas rojas hay partes en las que la ruta es bastante precisa pero hay otras en la que no lo es. Dos ejemplos de estas se pueden observar en la figura 2.6. Estas posiciones deben ser filtradas para obtener un seguimiento de los usuarios mas preciso ya que no proporcionan ninguna información relevante y hacen el seguimiento mucho menos preciso. Analizando las gráficas de error que se encuentra en el apéndice A, se descubrió 18 Estudio de la precisión de los servicios de localización en iOS Figura 2.6: Filtro WiFi. Dos ejemplos de posiciones muy imprecisas (dentro de los círculos amarillos) en las rutas: from 343 to 308 (izquierda) and from Nils Koppels Alle to Knuth-Wintherfeldts (derecha) Tabla 2.6: Error horizontal para diferentes filtros de error y Wi-Fi en metros Error filter Wi-Fi filter Min Max Mean RMSE 1000 01.04 218.90 27.13 35.10 200 01.04 105.53 24.85 29.67 150 01.04 105.53 24.35 29.09 100 01.04 105.53 24.21 28.91 100 21.04 105.53 24.19 28.90 100 31.04 105.53 24.19 28.90 100 41.04 105.53 23.91 28.38 100 51.04 105.53 23.91 28.38 100 61.04 105.53 23.99 28.46 100 72.35 105.53 23.98 28.48 que todas estas posiciones tenían un error horizontal estimado muy elevado. En la mayor parte de los casos era mayor de 700m y siempre mayor que 100m. estas posiciones son obtenidas utilizando GPS con mala calidad de señal o posicionamiento celular. Como puede verse en la tabla 2.6, simplemente filtrando las posiciones con error estimado mayor de 100 m el error medio desciende de 27.1 m a 24.2 m. Pero, analizando los datos se observo que posiciones como las que se muestran en la parte izquierda de la figura 2.7 eran muy imprecisas aunque su error estimado era menor que 100m. Se descubrió que estas posiciones se obtenían mediante posicionamiento Wi-Fi. Pero no todas estas posiciones tienen que ser eliminadas ya que cuando el usuario se encuentra dentro de un edificio estas son 2.4 Análisis de posiciones en movimiento 19 Figura 2.7: Dos ejemplos en los que se ha eliminado posiciones obtenidas utilizando posicionamiento Wi-FI (dentro de los círculos amarillos) en las rutas: from 341 to 101 (arriba) and from 343 to 308 (abajo) las posiciones más precisas que se obtienen. Así pues, el filtro Wi-Fi diseñado solo deja pasar las posiciones Wi-Fi que aparecen seguidas en grupos de tamaño igual o menor que el indicado. Este filtro fue diseñado para ejecutarse después del filtro de error horizontal estimado. Como se puede observar en la tabla 2.6, los mejores resultados se obtienen para filtro de error de 100 m y filtro Wi-Fi de 4 o 5. El error medio a sido mejorado casi 4 m, simplemente ejecutando filtros simples. 26 Representación de las rutas en el modelo 3D de escritorio en realsite.dk. Este ha sido desarrollado utilizando Unity 3D1,el cual se utiliza en el desarrollo de videojuegos y contenido 3D interactivo. Tiene unas herramientas de path finding que podrían haber sido de mucha utilidad, pero necesitan que el terreno sea un objeto estático y en realsite es un objeto dinámico. Por lo que no se podía utilizar estar herramientas. Así pues todos los algoritmos para posicionar a los usuarios en el modelo tenían que ser desarrollados utilizando métodos disponibles en la librería physics2.Estalibreríaposee métodos simples de interacción de objetos como por ejemplo el métdo RayCast3. 3.3. Solución diseñada 3.3.1. Requerimientos del sistema Como ya ha sido comentado en la sección anterior, es necesario diseñar unos algoritmos que representen a los usuarios en el modelo correctamente. Los requerimientos de este sistema son una mezcla de los que UCS impuso y los resultados del estudio del capítulo 2: El usuario se debe de poder mover por las nuevas posiciones sin quedar atascado y parecer real. El sistema tiene que trabajar en realsite no solo con el modelo 3D del campus de la DTU pero también con otros modelos. La ruta obtenida tiene que estar lo más cerca posible de la real. Todos los algoritmos tiene que desarrollarse en Unity usando el lenguaje de programación C#. Los algoritmos desarrollados en este proyecto cumplen todos estos requerimientos. 1http://unity3d.com/ 2http://unity3d.com/support/documentation/ScriptReference/Physics.html 3http://unity3d.com/support/documentation/ScriptReference/Physics.Raycast.html 3.3 Solución diseñada 27 3.3.2. Transformación de coordenadas geográficas a DTU yviceversa La conversión de coordenadas se realiza en el servidor en lugar de en el reproductor de realsite, por lo que tuvo que ser desarrollada en jaca. El modelo 3D de la Technical University of Denmark usa como sistema de referencia un sistema coordenado cuyo punto 0,0 está en el centro del campus. UCS disponía de un documento procedente de la empresa que tomo las medidas del campus, el cual puede verse en el apéndice B. Las fórmulas que se calcularon para realizar el cambio de coordenadas de DTU a UTM pueden verse a continuación: ✓DTUx DTUy◆=✓cos(✓)sin(✓) sin(✓) cos(✓)◆✓UTMx UTMy◆+✓x y◆ ✓UTMx UTMy◆=1  cos(✓)sin(✓) sin(✓)sin(✓)sin(✓)3 cos(✓)sin(✓)!✓DTUxx DTUy+y◆ =0,9998133 ✓= 14,3472 x= 834864,7242936 y= 6172294,56110385 Ya que iOS y la mayoría de dispositivos que miden la posición utilizan coordenadas geográficas, hay que realizar la conversión de estas coordenadas a coordenadas UTM. Esta conversión no es directa, ya que hay muchas soluciones gratuitas en internet para este problema algunas de ellas pueden encontrarse en 456 . Geographic/UTM Coordinate Converter fue la solución seleccionada, tuvo que ser traducida de JavaScript a Java y modificada para que Copenhague estuviera en la zona 32U en lugar de en la 33U que es en la que en realidad se encuentra, ya que esta zona era la utilizada en el sistema de referencia. 4Coordinate conversions made easy https://www.ibm.com/developerworks/java/ library/j-coordconvert/ 5Geographic/UTM Coordinate Converter http://home.hiwaay.net/~taylorc/toolbox/ geography/geoutm.html 6Convert Between Geographic and UTM Coordinates http://www.uwgb.edu/dutchs/ usefuldata/ConvertUTMNoOZ.HTM 28 Representación de las rutas en el modelo 3D 3.3.3. Algoritmos diseñados para representar el avatar en el modelo El sistema diseñado fue dividido en cinco algoritmos diferentes que son ejecutados uno después de otro. Cada uno de estos algoritmos soluciona alguno de los problemas de los expuestos en el capítulo anterior y no estropea lo solucionado por los algoritmos que han sido ejecutados anteriormente. Los algoritmos son ejecutados en el mismo orden que son presentados en este capítulo. En todos los mapas presentados en este capítulo la línea azul es la ruta obtenida por el Garmin, mientras que la líneas roja y verde son las obtenidas con el iPhone y tras las la transformación respectivamente. Una explicación más detallada de todos los algoritmos se puede encontrar en el capítulo 3.3.3 del apéndice D. 3.3.3.1. Paso 1: añadir las entradas de los edificios cuando el usuario entra a uno Figura 3.3: Un ejemplo de ruta donde dos entradas de edificios son añadidas alarutaporqueelusuarioestabadentrodeunedificio(dentrode los círculos amarillos) Como fue comentado en la sección 2.4.5, después de aplicar un filtro de error de 100 m y un filtro Wi-Fi de 4 posiciones, detectar cuando el usuario está dentro de un edificio es tan fácil como detectar las posiciones Wi-Fi sobrantes. Así pues el algoritmo desarrollado en esta parte realiza las siguientes funciones: 1. Detecta las posiciones Wi-Fi en la ruta y borra las que están dentro de un edificio. 3.3 Solución diseñada 29 2. Añade la entrada del edifico que entre el primer punto que esta dentro de un edifico y el anterior. Realiza lo mismo para la salida pero con el último punto. 3. Añade un salto en la ruta entre las dos posiciones de las puertas. Un ejemplo de la ruta resultante tras ejecutar este algoritmo se puede ver en la figura 3.3. Este algoritmo es ejecutado en primer lugar porque las posiciones Wi-Fi no pueden ser filtradas antes de ejecutarlo y además puede estropear alguno de los problemas que los algoritmos posteriores solucionan. Las nuevas rutas no contienen ninguna información de donde se situaba el usuario cuando estaba dentro del edificio, pero esto no es una pérdida de información ya que estas posiciones son generalmente muy poco precisas. 3.3.3.2. Paso 2: filtrado de las rutas usando el algoritmo de Douglas- Peucker Como fue explicado en la sección 3.1.4, el problema cambio rápido de dirección se producía cuando las posiciones no estaban muy separadas unas de otras. Así pues algún algoritmo de simplificación de curvas tenía que ser desarrollado, ejemplos de estos algoritmos pueden verse en [DD73], [BKR92], [Ram72]. Entre ellos el que proporcionaba mejores resultados en este caso y por lo tanto el algoritmo implementado fue el algoritmo de Doublas-Peucker [DD73]. Este algoritmo es un algoritmo recursivo que reduce el número de puntos necesario para representar una curva manteniendo la precisión. Si a la ruta se le han añadido puertas de edificios, la ruta es dividida por los saltos antes de ejecutar este algoritmo de forma que las posiciones de las puertas no son filtradas. Un ejemplo de ejecución de este algoritmo se puede ver en la figura 3.4. En nuestro caso un valor de ✏de 5 m solucionaba completamente el problema. 3.3.3.3. Paso 3: ajuste de la ruta con la red de calles Como se comentó en la sección 3.2, todos los algoritmos de map matching necesitan una red de carreteras con la que trabajar. Ya que no se podía obtener una del modelo directamente, un fichero de AutoCAD, que fue usado en el desarrollo del modelo, fue utilizado para obtener esta red. Esta red contiene las principales 30 Representación de las rutas en el modelo 3D Figura 3.4: Algoritmo de Douglas-Peuckera ahttp://softsurfer.com/Archive/algorithm_0205/Pic_DP-2.gif calles del campus en forma de segmentos. Por lo que no todas las posiciones pueden ser proyectadas en esta red solo las que realmente pasaron por esas calles, ya que la red de calles real es mucho más grande. El algoritmo de map matching desarrollado es una variante del algoritmo 2 presentado en [CEW00]. El algoritmo proyecta una posición en la red de calles si la proyección esta más cerca que un umbral y si la diferencia entre la orientación de ambas es menor que 30 grados. El umbral de distancia es 20 o 30 m dependiendo si el punto anterior ha sido proyectado en ese segmento o no. La proyección es calculada como la intersección entre el segmento perpendicular al segmento de la red que pasa por el punto analizado. Un ejemplo de la ejecución de este algoritmo puede verse en la figura 3.5. 3.3 Solución diseñada 31 Figura 3.5: Ejemplo de rutas mejoradas usando el algoritmo de map matching 3.3.3.4. Paso 4: corrección de las diferencias de altitud Como fue comentado en la sección 3.1.3, el campus de la DTU no es completamente plano, hay varios lugares en los que hay muros que el carácter no puede escalar. Para pasar estos muros el usuario puede utilizar escaleras que se encuentran en el exterior o en el interior de edificios. Nuestro algoritmo considera los dos casos. El algoritmo detecta si dos puntos consecutivos están a una diferencia de altitud mayor de 4 m. Si lo están añade una serie de puntos que hacen que el carácter suba por las escaleras o entre y salga de un edificio. En el caso de las escaleras exteriores un fichero con las posiciones que tienen que ser añadidas fue creado manualmente ya que las escaleras están incluidas en el mismo objeto que el terreno en el modelo. Esto hacía imposible detectarlas usando los métodos de 32 Representación de las rutas en el modelo 3D Figura 3.6: Ejemplo de como arreglar las diferencias de altitud en dos rutas añadiendo escaleras exteriores (izquierda) o puertas (derecha) Unity. Para las entradas de los edificios se detectaba si había algún edificio cerca del cambio de altitud y si este tenía una puerta en una altura y la otra en la otra. Un ejemplo de la ejecución de este algoritmo se puede ver en la figura 3.6. 3.3.3.5. Paso 5: evitar obstáculos conocidos (edificios) en la trayectoria El objetivo de este algoritmo es generar la ruta final libre de obstáculos, la cual pueda ser seguida por un carácter en el modelo sin chocar con ningún obstáculo. Este problema fue expuesto en la sección 3.1.2. Este algoritmo hace dos tareas fundamentalmente, añade puntos cerca de las esquinas de los edificios para rodearlos y elimina todas las posiciones que están encima de edificios. Pero estos últimos no son borrados directamente, son utilizados antes de ser borrados. Los puntos que son añadidos están 2 m en el eje x e y lejos de las esquinas de los edificios. El algoritmo tenia que ser capaz de añadir un número indeterminado de puntos para rodear los edificios, además los edificios suelen estar unidos unos con otros por lo que tiene que ser capaz de resolver edificios con formas complejas y no solo con forma rectangular. Para cumplir estos criterios el algoritmo diseñado es un algoritmo recursivo. El algoritmo comprueba si hay algún obstáculo en la línea que une dos puntos 3.4 Resultados 33 Figura 3.7: Ejemplos de ejecución del algoritmo que evita chocar con edificios consecutivos, si lo hay comprueba si hay obstáculos entre el primer punto y alguna de las esquinas del objeto obstáculo. Si no la hay, el punto es añadido alarutayelalgoritmosevuelveaejecutarrecursivamente.Sihayobstáculo, se toma ese obstáculo y se vuelve a ejecutar el algoritmo que comprueba las esquinas. Si hay varias esquinas que producen caminos libres de obstáculos el que produce un camino más corto es el que se añade a la ruta. La figura 3.7 muestra dos ejemplos de la ejecución de este algoritmo. 3.4. Resultados El sistema presentado en la sección anterior cumple todos los requerimientos que fueron presentados en la sección 3.3.1 para todas las rutas analizadas. Las rutas obtenidas junto con las originales y las de referencia pueden verse en el apéndice C. Para calcular el error de las rutas calculadas fueron contempladas varias soluciones: utilizar la misma solución que en la sección 2.4, utilizar la distancia de Hausdorff[FDA08] o utilizar la distancia de Fréchet [AM06]. La primera opción fue elegida entre otras razones para que los resultados fueran comparables con los del estudio de la sección 2.4. Para calcular el error de esta manera había que calcular el instante que se recibieron las posiciones que son añadidas a la ruta por este sistema. Este instante temporal fue calculado asumiendo velocidad constante entre las nuevas posiciones añadidas y usando los instantes temporales de las posiciones que pasaron el filtro de la ruta original. 34 Representación de las rutas en el modelo 3D Route name Number from 308 to 342 0 from 341 to 101 1 from 343 to 308 2 from library to 229 3 from 115 to library 4 from 229 to 115 5 from Nordvej to 302 biking 6 from Knuth-Wintherfeldts to Nils Koppels Alle walking 7 from Nils Koppels Alle to Knuth-Wintherfeldts biking 8 Figura 3.8: Comparación del error horizontal entre las rutas originales y las mejoradas con el sistema Como puede verse en la figura 3.8, el error medio es mejorado en 4 de las 9 rutas analizadas tras ejecutar el algoritmo. Pero analizando los mapas del apéndice C se puede ver que de esas 4 rutas en las que se empeora el error medio, solo en dos casos las rutas son menos precisas que antes de ejecutar los algoritmos. Estas dos rutas son “from 308 to 342” y “from 341 to 101”, durante las cuales el usuario entro dentro de varios edificios y por lo tanto los resultados que el iPhone proporcionó eran bastante imprecisos. Que el error sea mayor en rutas que son más precisas solo indica que el instante temporal de las posiciones no es el correcto, ya que como fue analizado en la sección 2.4.4 el tiempo que iOS proporciona junto con las posiciones no es muy preciso. En el resto de las siete rutas, las rutas no solo eran más precisas que las rutas antes de ejecutar el algoritmo sino que en algunas partes eran incluso más precisas que las que proporcionó el Garmin. Capítulo 4 Sistema final Esta sección describe la implementación final del sistema. Las diferentes partes que han sido explicadas en los capítulos anteriores, más una nueva aplicación para iOS han sido unidas para formar un sistema completamente funcional. Hay que tener en cuenta que este sistema es más una prueba de concepto que permitirá a UCS desarrollar sistemas más avanzados usando esta tecnología en el futuro. 4.1. Arquitectura del sistema Como se puede ver en la figura 4.1, el sistema esta compuesto de tres partes principales, la aplicación para iOS que captura y envia las posiciones del usuario, el servidor con la base de datos que las almacena y la página web (realsite.dk) donde se transforman los datos y se visualizan los avatares de los usuarios en los modelos 3D. En este sistema el alumno ha desarrollado completamente la aplicación para iOS, el algoritmo para la conversión de coordenadas que es ejecutado en el servidor y el código que mejora las rutas que es ejecutado en el visualizador de las rutas de la página web. La integración de las distintas partes desarrolladas por el alumno y los servicios ya existentes de la empresa fue desarrollada por ambas partes, los trabajadores de la empresa y el alumno. 42 Conclusión se puede observar que siete de las nueve rutas son más precisas que la original. El sistema proporciona una ruta por la que pude ser movido por el modelo un avatar sin quedar atascado para las nueve rutas analizadas. Para finalizar se presenta el sistema final. Este esta compuesto de la aplicación para iOS, el servidor web con la base de datos y el reproductor del modelo 3D. Los resultados del sistema final son muy prometedores y Utopian City_Scape ha expresado su intención de continuar con su desarrollo en el futuro. Apéndice A Routes maps and graphs A.1. Routes which go inside a building 44 Routes maps and graphs Error filter Wi-Fi filter Min Max Mean RMSE 1000 07.46 188.34 26.59 38.80 200 07.46 60.55 23.11 26.91 150 07.46 60.55 22.62 26.40 100 07.46 60.55 22.62 26.40 100 27.46 60.55 22.62 26.49 100 37.46 60.55 22.62 26.49 100 47.46 60.55 22.62 26.49 100 57.46 60.55 22.62 26.49 100 67.46 60.55 24.16 28.02 100 77.66 60.55 24.80 29.07 Figura A.1: Route map and error and time graphs. From 308 to 342 A.1 Routes which go inside a building 45 Error filter Wi-Fi filter Min Max Mean RMSE 1000 02.28 175.08 30.86 40.05 200 02.35 93.29 26.25 31.16 150 02.35 93.29 24.96 29.51 100 02.35 93.29 24.35 28.64 100 22.35 93.29 24.35 28.64 100 32.35 93.29 24.35 28.64 100 42.35 59.39 22.81 25.58 100 52.35 59.39 22.81 25.58 100 62.35 59.39 22.81 25.58 100 72.35 59.39 22.81 25.58 Figura A.2: Route map and error and time graphs. From 341 to 101 46 Routes maps and graphs Error filter Wi-Fi filter Min Max Mean RMSE 1000 01.04 133.87 36.23 44.07 200 01.04 65.52 31.58 36.17 150 01.04 65.52 30.30 34.76 100 01.04 65.52 29.90 34.49 100 21.04 65.52 29.87 34.59 100 31.04 65.52 29.87 34.59 100 41.04 65.52 29.87 34.59 100 51.04 65.52 29.87 34.59 100 61.04 65.52 29.87 34.59 100 73.66 65.52 30.63 35.89 Figura A.3: Route map and error and time graphs. From 343 to 308 A.1 Routes which go inside a building 47 Error filter Wi-Fi filter Min Max Mean RMSE 1000 06.13 132.91 35.49 47.02 200 06.13 90.78 29.57 36.78 150 06.13 90.78 28.37 35.89 100 06.13 90.78 28.37 35.89 100 26.13 90.78 28.37 35.89 100 36.13 90.78 28.37 35.89 100 46.13 90.78 28.37 35.89 100 56.13 90.78 28.37 35.89 100 66.13 90.78 28.37 35.89 100 76.13 90.78 28.37 35.89 Figura A.4: Route map and error and time graphs. From library to 229 48 Routes maps and graphs A.2. Outdoor routes with curves A.2 Outdoor routes with curves 49 Error filter Wi-Fi filter Min Max Mean RMSE 1000 04.24 99.34 24.94 30.97 200 04.24 42.39 21.84 24.25 150 04.24 42.39 21.18 23.66 100 04.24 42.39 21.18 23.66 100 24.24 42.39 21.18 23.66 100 34.24 42.39 21.18 23.66 100 44.24 42.39 21.18 23.66 100 54.24 42.39 21.18 23.66 100 64.24 42.39 21.18 23.66 100 74.24 42.39 21.18 23.66 Figura A.5: Route map and error and time graphs. From 115 to library 50 Routes maps and graphs Error filter Wi-Fi filter Min Max Mean RMSE 1000 03.24 61.52 26.33 29.92 200 03.24 61.52 25.39 28.77 150 03.24 61.52 24.64 28.30 100 03.24 61.52 24.64 28.30 100 23.24 61.52 24.64 28.30 100 33.24 61.52 24.64 28.30 100 43.24 61.52 24.64 28.30 100 53.24 61.52 24.64 28.30 100 63.24 61.52 24.64 28.30 100 73.24 61.52 24.64 28.30 Figura A.6: Route map and error and time graphs. From 229 to 115 A.2 Outdoor routes with curves 51 Error filter Wi-Fi filter Min Max Mean RMSE 1000 04.62 93.08 26.57 33.60 200 04.62 93.08 26.57 33.60 150 04.62 93.08 26.33 33.46 100 04.62 93.08 26.33 33.46 100 24.62 93.08 26.33 33.46 100 34.62 93.08 26.33 33.46 100 44.62 93.08 26.33 33.46 100 54.62 93.08 26.33 33.46 100 64.62 93.08 26.33 33.46 100 74.62 93.08 26.33 33.46 Figura A.7: Route map and error and time graphs. From Nordvej to 302 biking 58 Definition of DTU local coordinate system Apéndice C Routes maps and graphs after executing the algorithm 60 Routes maps and graphs after executing the algorithm Improved with the algorithm Min Max Mean RMSE Yes 6.54 75.48 29.97 35.07 No 7.46 32.91 17.58 19.36 Figura C.1: Route map and error graphs. From 308 to 342 61 Improved with the algorithm Min Max Mean RMSE Yes 4.76 143.17 49.70 63.36 No 2.35 59.39 22.53 25.38 Figura C.2: Route map and error graphs. From 341 to 101 62 Routes maps and graphs after executing the algorithm Improved with the algorithm Min Max Mean RMSE Yes 5.14 37.15 24.39 25.75 No 1.04 50.37 26.85 30.03 Figura C.3: Route map and error graphs. From 343 to 308 63 Improved with the algorithm Min Max Mean RMSE Yes 11.01 45.02 25.02 26.81 No 9.55 90.78 31.35 39.52 Figura C.4: Route map and error graphs. From library to 229 64 Routes maps and graphs after executing the algorithm Improved with the algorithm Min Max Mean RMSE Yes 11.70 41.39 18.91 21.23 No 4.24 41.39 19.84 22.23 Figura C.5: Route map and error graphs. From 115 to library 65 Improved with the algorithm Min Max Mean RMSE Yes 2.89 44.64 18.70 22.66 No 3.24 44.64 21.72 25.86 Figura C.6: Route map and error graphs. From 229 to 115 66 Routes maps and graphs after executing the algorithm Improved with the algorithm Min Max Mean RMSE Yes 6.70 78.68 34.58 39.67 No 4.62 93.08 26.08 33.27 Figura C.7: Route map and error graphs. From Nordvej to 302 67 Improved with the algorithm Min Max Mean RMSE Yes 4.85 37.63 19.29 21.07 No 3.76 33.49 17.74 18.86 Figura C.8: Route map and error graphs. From Knuth-Wintherfeldts to Nils Koppels Alle Summary (Danish) Formålet med denne afhandling er at udvilke et sporingssystem, ved hjælp af en iOS-enhed og en 3D model af DTU Campus. Idéen med systemet er at brugerne tænder for app’en, når de befinder sig inden for et område med en tilgængelig 3D model. App’en sender brugernes placering til en Internet server. 3D modellerne er tilgængelige gennem en hjemmeside (realsite.dk), hvor brugernes avatarer vil blive brugt til at spore brugerne i realtid. GPS sensorer i Smarphones er normalt ikke ret præcise. For at udvikle den bedste algoritme til sporing, med den bedst mulige præcision, er det nødvendigt først at analysere nøjagtigheden af enheden. Derfor begynder denne afhandling med en omfattende undersøgelse af sensoren og de parametre, der kan konfigureres i iOS placeringsservices. Alle de problemer der blev løst i forløbet med denne afhandling, bliver præsenteret i de efterfølgende afsnit. De to vigtigste dele af det forslåede system er fuldt implementerede, som en del af denne afhandling. Den første del er selve iPhone app’en, som henter og filterer brugernes placeringer. Derudover giver det brugerne mulighed for at uploade et billede, der bliver brugt på deres avatar. Den anden implementerede del er en algoritme til at repræsentere brugernes avatar i 3D modellen; de rå GPS målinger kan ikke placeres direkte, da de er meget upræcise. Nogle af de interessante forbedringer er, at systemet kan opdage om brugeren er indendørs eller udendørs. Det leder avataren til en dør i bygningen, hvis de bevæger sig indendørs eller udendørs. Systemet kan også tage højde for hvis der er stor højdeforskel; i det tilfælde bruger avataren trapperne. iv Preface This thesis was prepared at the department of Informatics and Mathematical Modelling at the Technical University of Denmark in fulfillment of the requirements for acquiring an M.Sc. in Telecommunications engineering. The thesis was made in collaboration with Utopian city_scape as part of the Erasmus exchange program during the Spring semester of 2012. It was supervised by Michael Frederiksen, Sune Lehmann and Jakob Eg Larsen. The thesis deals with high accuracy tracking systems using smartphone’s GPS sensor. The thesis consists of a prototype development of a tracking system using a 3D model and a smartphone. The system collects the locations of the users using the smartphone GPS sensor, improves them and represents the avatars of the users in the 3D model. Lyngby, 31-July-2012 Jorge Pérez Lahera vi Acknowledgements I am grateful to all the people at Utopian city_scape for letting me do the master thesis in their offices. They guided and supervised me during all the process. I would like to thank my supervisors in DTU and University of Zaragoza for helping my in the most difficult moments. Without them everything would have been different. Thank to my family and friends who have supported and encouraged me during all this period. viii Contents Summary (English) i Summary (Danish) iii Preface v Acknowledgements vii 1 Introduction 1 1.1 Motivation .............................. 2 1.2 Collaboration with Utopian City_Scape . . . . . . . . . . . . . . 6 1.3 Projectrequirements......................... 6 1.4 Projectarchitecture ......................... 7 1.5 Thesisstructure............................ 7 2 Accuracy study of iOS location services 9 2.1 Introduction to the different location systems . . . . . . . . . . . 9 2.1.1 Satellite positioning . . . . . . . . . . . . . . . . . . . . . 9 2.1.2 Wi-Fi positioning . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.3 Cellular positioning . . . . . . . . . . . . . . . . . . . . . 13 2.2 Location services in iOS . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Experimental settings . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.1 Analyzed devices . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.2 Data collection and evaluation criteria . . . . . . . . . . . 18 2.4 Analysis of Static Measurements . . . . . . . . . . . . . . . . . . 24 2.4.1 GPS data processing . . . . . . . . . . . . . . . . . . . . . 24 2.4.2 Horizontal accuracy comparison between different desired accuraciesiniOS....................... 25 2.4.3 Observed versus estimated accuracy in iPhone . . . . . . 30 xCONTENTS 2.4.4 Time to first-fix in iPhone . . . . . . . . . . . . . . . . . 32 2.4.5 Comparison between different devices . . . . . . . . . . . 35 2.5 Analysis of Measurements in motion . . . . . . . . . . . . . . . . 37 2.5.1 How to measure the real route . . . . . . . . . . . . . . . 37 2.5.2 GPS data processing . . . . . . . . . . . . . . . . . . . . . 38 2.5.3 Calculated horizontal error . . . . . . . . . . . . . . . . . 39 2.5.4 Filtering out inaccurate locations . . . . . . . . . . . . . . 42 2.5.5 Time and speed between different locations . . . . . . . . 45 2.5.6 Trying to detect when the user goes inside a building . . . 48 3 Representing the routes in the 3D model 51 3.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.1.1 Coordinates conversion . . . . . . . . . . . . . . . . . . . 52 3.1.2 Crossing buildings and points in the top of the buildings . 52 3.1.3 Changes of altitude along the route . . . . . . . . . . . . . 53 3.1.4 Fast change of heading . . . . . . . . . . . . . . . . . . . . 54 3.2 Tools and concepts required . . . . . . . . . . . . . . . . . . . . . 54 3.2.1 Pathfinding.......................... 54 3.2.2 Mapmatching ........................ 55 3.2.3 Unity and the development environment . . . . . . . . . . 56 3.3 Solutiondesigned........................... 58 3.3.1 System requirements . . . . . . . . . . . . . . . . . . . . . 58 3.3.2 Converting from geographic to DTU coordinates and vice versa.............................. 59 3.3.3 Algorithms developed to represent the avatar in the model 61 3.4 Results................................. 72 3.5 Future improvements . . . . . . . . . . . . . . . . . . . . . . . . . 74 4 Final functional system 77 4.1 System architecture . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.2 Mobileapplication .......................... 79 4.2.1 Function............................ 79 4.2.2 Obtaining and processing location data . . . . . . . . . . 79 4.2.3 Userinterface......................... 80 4.2.4 Communication with the server . . . . . . . . . . . . . . . 84 4.3 Serverside............................... 85 4.4 Player in realsite.dk . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.5 Potential improvements . . . . . . . . . . . . . . . . . . . . . . . 87 5 Conclusion 89 A Product Brief iPhone A-GPS chip 91 CONTENTS xi B Routes maps and graphs 95 B.1 Routes which goes inside a building . . . . . . . . . . . . . . . . . 95 B.2 Outdoor routes with curves . . . . . . . . . . . . . . . . . . . . . 100 B.3 Straightroutes ............................104 C Definition of DTU local coordinate system 107 D Routes maps and graphs after executing the algorithm 111 Bibliography 121 xii CONTENTS 1.4 Project architecture 7 •Server to store, process and send the locations to the 3D model player. •3D model player to see the routes, which includes algorithms to enhance the raw routes received according to the 3D model details. 1.4 Project architecture The final developed system is composed of three main parts, the mobile application, the Internet server and the 3D model player. The mobile application is in charge of obtaining the user locations using the GPS of the phone and sending it to the UCS server. In order to do that, the app recognizes in which 3D model the user is placed and asks for a route name. The positions that the app receives are filtered and sent to the server in real time. The server stores these locations for each route in a database. Each model has its own coordinate system; thus the server performs the transformation from geographic coordinates to the coordinates of each of these models. The 3D model player is accessible through the company website (realsite.dk), which can be accessed using a PC browser. The algorithm to improve the routes is executed in this side. Therefore, the server sends the locations to the player. The user will be represented in this player in real time when he is using the app. 1.5 Thesis structure So far, this introduction has unveiled the motivation to do this project, the project requirements and architecture. Moreover, it explained how the collaboration with the company and the student worked during the whole project. Chapter 2 is an accuracy study of the location services in iOS. The analysis includes not only static positions but also recordings while moving. For the static positions, the mean horizontal error for different configured accuracy levels is compared. Moreover, the estimated accuracy and the time to first-fix are analyzed. Regarding the positions recording in motion, several routes were made in the DTU campus for this analysis. The mean error and the time between different locations were studied. Furthermore, a noise filter and an indoor detector were designed which are used in the following chapters. Chapter 3 shows the algorithms that were designed to represent the routes in the model since an avatar can not move in the model following the original route. It presents how the coordinates are converted from geographic coordinates to 8 Introduction DTU coordinates and vice versa. The result routes are analyzed and compared with the original ones. To conclude this section, possible future improvements of the algorithm are discussed. Chapter 4 presents the final system integrated with realsite.dk. Chapter 5 summarizes the whole report and emphasizes the most important results presented. Chapter 2 Accuracy study of iOS location services 2.1 Introduction to the different location systems In this first section, the different ways that smartphones are used to get the location of the user is going to be briefly explained. All the modern smartphones use a hybrid location system, this means that three different positioning technologies can be used to obtain the user locations. These systems are satellite positioning (A-GPS), Wi-Fi positioning and cellular positioning. 2.1.1 Satellite positioning Satellite positioning is a technology in which several satellites are used to estimate the user location. The most well known satellite-positioning system nowadays is GPS (Global Positioning System). The GPS system was designed by the United States Department of Defense (DoD), has been in Fully Operational Capability (FOC) from July 1995. It was originally composed of 24 satellites but currently it consists of 321. This assures that a mobile device equipped 1GPS Constellation Status ftp://tycho.usno.navy.mil/pub/gps/gpstd.txt 10 Accuracy study of iOS location services Figure 2.1: Example of hybrid positioning systema ahttp://www.skyhookwireless.com/howitworks/loader_howitworks.swf with a GPS receiver will catch up signals from at least four different satellites [ZA06][ML08]. The GPS satellites broadcast two signals in the L1 (1575.42 MHz) and L2 (1227.60 MHz) bands, which broadcast time and orbital information; the locations are being calculated through this information. Two services are provided: the Standard Positioning Service (SPS) and the Precise Positioning Service (PPS). SPS is the one that is used by the entire end costumer GPS enabled products and is the one that is used in the devices analyzed in the project, while PPS offers enhanced accuracy but it can only be used by authorized users for instance the US army [Hub]. The majority of GPS-enabled smartphones, including all models of iPhone, employs a technology, which is called Assisted GPS (A-GPS) [GS05]. With this technology a remote GPS location server performs many functions that usually are performed in a full GPS receiver. This server provides the A-GPS device with satellite orbit and clock information and position computation. The mobile device does not need to decode the GPS messages or perform a search for visible satellites when the system is starting, the server assists the device in these tasks. These improve the power consumption and the time-to-first-fix [ML08] over the traditional GPS receivers [Zan09]. The signal propagation errors limit the GPS accuracy. These are the typical errors that may be encountered in all satellite communications. The signal in the path from the satellite to the mobile device does not have a constant speed, 2.1 Introduction to the different location systems 11 this produces a inconsistent propagation delay. Moreover, the signal bounces offobstacles before arriving to the device antenna; this produces signal quality degradation due to multipath fading errors. Neither GPS nor A-GPS works well in high-density urban areas and in indoor locations due to poor satellite visibility and signal attenuations. High-sensitivity GPS (HSGPS) chip sets try to solve this problem and are implemented in many new A-GPS receivers. But even with this chipsets there are many locations where the device is not able to find the current position. Hence, other positioning systems apart from GPS have to be implemented in smartphones if the user has to receive a position in all the locations. Almost all smartphones deploy Wi-Fi positioning and cellular positioning in addition to A-GPS, which are explained in the following sections. 2.1.2 Wi-Fi positioning This technology uses WiFi access points (APs) to determine the user location. Over the last several years millions of wireless networks have been deployed everywhere. Nowadays, it is hard to find a place inside a city where there is no WiFi APs available, a study about APs density can be found in [JL07]. Each AP has a unique identifier that is called BSSID which is the MAC address of the AP and in order to be visible for other devices beacon frames are sent periodically. These facts make WiFi access a very appropriate location system in the places where A-GPS is less accurate or even can not give a location which is in high density urban areas and indoor locations. Thus, the WiFi positioning enabled device records BSSID and signal strength of all the available networks at a particular location to obtain the locations. This allows encrypted and weak signals to be used. As it is described in [Kue05], the WiFi positioning algorithms can be upstream or downstream and are divided into three main categories: proximity sensing, lateration and fingerprinting. In proximity sensing the position of the AP with best signal strength is adopted. Lateration method tries to measure the distance between the AP and the device using the path loss experienced by the beacon packets during transmission. While with fingerprinting, the set of APs and the signal strengths for these APs that the device receives in a location (“fingerprint”) is compared with patterns that have been measured before at known locations. The pattern that is more similar to the fingerprint that the device is measuring meanwhile is adopted as the actual position [Hub]. Fingerprinting technologies have two big advantages over the other techniques. 12 Accuracy study of iOS location services They do not require the exact location of the APs and do not try to model signal strength. These advantages have made fingerprinting the preferred technology for big scale WiFi positioning in metropolitan areas. In order fingerprinting technologies to be available in an area, the WiFi signals have to be observed at known locations in that area, this is called calibration phase or offline phase, as it can be seen in Figure 2.2. During this phase, a WiFi receiver is hooked up to a GPS device and the WiFi signals are recorded with the GPS positions as the device moves through an area. This WiFi fingerprints for known locations are stored in a database and compared with the signals that the device receives when it is in an unknown location, the location is determined finding the closest match, this phase is called positioning or online phase. There are several matching techniques that have been developed for this, but the most widely used is the K-nearest neighbor estimation because of its computational simplicity and performs well in contrast with other techniques [Zan09] [SC05]. Figure 2.2: Collection of data for WiFi and Cellular positioninga ahttp://www.skyhookwireless.com/howitworks/loader_howitworks.swf Several WiFi positioning systems are currently in the market, the most remarkable one is the one that is created by Skyhook Wireless which is used by ample well known companies. It was also used in iOS until April 2010. Other alternatives are Navizon and PlaceEngine. Moreover, Apple and Google have their own WiFi positioning system23 . 2In April, Apple Ditched Google And Skyhook In Favour Of Its Own Location Databases http://techcrunch.com/2010/07/29/apple-location/ 3Copy of Google’s submission today to several national data protection authorities on vehicle-based collection of wifi data for use in Google location based services http://static.googleusercontent.com/external_content/untrusted_dlcp/www.googl e.com/en//googleblogs/pdfs/google_submission_dpas_wifi_collection.pdf 2.1 Introduction to the different location systems 13 2.1.3 Cellular positioning It is more than 20 years since the first GSM call, made by Finnish Prime Minister Harri Holkeri4.Sincethen,ahugeexpansionofcellularnetworkshasbeen developed in the world, to an extent of having almost worldwide coverage nowadays. The two main cellular networks that are in operation in the world are The Global System for Mobile Communication (GSM) and the Universal Telecommunication System (UMTS), which are commonly called 2G and 3G networks, respectively. Moreover, the new 4G networks which is called LTE is starting its deployment but it is far from the actual coverage that 2G and 3G have, and it will take several years to achieve it. The cellular positioning techniques that are explained in this section are only applicable for 2G and 3G networks. Cellular networks are divided into cells, which have a hexagonal shape since a theoretical point of view. Each of these cells has a base station (BS) in the middle. The mobile phone of the user is connected to one of these base stations which is usually the one that has a better signal strength and switches between them automatically. The simplest way of cellular positioning is to use the location of this BS as the user location. This method is called cell identification (cell ID). The precision of this method is conditioned by the cell size, which varies from urban to rural areas. These base stations can have mainly two different kinds of antennas, omnidirectional and directional antennas. If the antenna is directional, the cell is divided into sectors, which means that the user location can be obtained with better precision. Other techniques have been developed for improving cell identification. One of them it is called enhanced cell ID (E-CID), this method measures the time that the signal takes to arrive from the device to the base station which is measured by the base station and is called time advance. The mobile device is usually within the range of multiple base stations; several techniques try to take advantage of that. These techniques are Time Difference of Arrival (TDOA) or Angle of Arrival (AOA) [Kue05]. Same as for WiFi positioning, fingerprinting techniques have also been developed [SB04] and [CMYA06]. Although the accuracy of cellular positioning is lower than GPS or WiFi, the availability of the cellular networks are much higher. Moreover, it is very energy efficient because it uses data and hardware that it is available all the time in the phone, the phone is always connected to the cellular network. Thus, it does not need to switch on any other hardware like GPS or WiFi. 4GSM turns 20 today, still rocking the world http://www.engadget.com/2011/07/01/gsm-t urns-20-today-still-rocking-the-world/ 14 Accuracy study of iOS location services 2.2 Location services in iOS The iPhone 3G, which was released on 11 July 20085,wasthefirstcommercial device presenting the hybrid positioning system [Zan09]. But, nowadays almost all the smartphones implement this technology. As already mentioned, this system acquires the user location choosing the best option for each situation between satellite, WiFi or cellular positioning. This is done automatically by the operating system; neither the users nor the developers have to care about it. In previous versions of iOS the Maps app shows different pins depending on the type of location that it was used but in the recent versions (currently 5.01) all the positioning systems show the same pin and the only clue that can be used to differentiate them is the accuracy that the location services provides. Until April 2010, Apple relies on Skyhook and Google data to provide WiFi and Cellular positioning systems respectively. But starting with iOS 3.2, which was released in April 2010, Apple uses its own databases to provide location-based services (LBS)6.AsApplestatesintheofficial documentation, this database is maintained by iOS users.“If Location Services is on, your device will periodically send the geo-tagged locations of nearby Wi-Fi hotspots and cell towers in an anonymous and encrypted form to Apple, to augment the crowd-sourced database of Wi-Fi hotspot and cell tower locations.”7. After this short introduction about the location services in iOS from now until the end of this section, the technical details and the parameters that the location API allows the developer to configure will be explained. The only way the developer can access the positioning features in iOS is using the Core Location API provided by Apple. This API provides the location using the hybrid positioning system but the developer can not choose which of the three systems is going to be used directly, only the desired accuracy can be chosen. The Core Location framework provides three different services to monitor the device’s location: the significant-change, standard location and region monitoring location services. In this project, only the standard location service is going to be studied because it is the most easily configurable and thereby it can be the most accurate. For the purposes of this study accuracy is one of the main constraints because the model is very accurate, thus for this project the significant-change and region monitoring are not feasible solutions8. 5iPhone 3G announced iPhone 3G announced iPhone 3G announced http://www.tuaw.com /2008/06/09/iphone-3g-announced/ 6In April, Apple Ditched Google And Skyhook In Favour Of Its Own Location Databases http://techcrunch.com/2010/07/29/apple-location/ 7iOS 5: Understanding Location Services http://support.apple.com/kb/HT4995 8Location Awareness Programming Guide https://developer.apple.com/library/ios/doc 2.2 Location services in iOS 15 The standard location service is available on all devices and in all versions of iOS, thus it is the most common way to get the user’s location. Before using it, you have to configure the desired accuracy and the minimum distance between two locations that produce a new location in your app. In order to start using the standard location service you have to create an instance of the class CLLocationManager.Afterthat,youhavetoconfigureits desiredAccuracy and distanceFilter properties. Once this is done, assign a delegate to the object, which implements CLLocationManagerDelegate Protocol9 and calls the startUpdatingLocation method to begin receiving location notifications. One of the experiments with the iPhone location service that are included in this master thesis tries to measure the impact that the parameter desiredAccuracy has in the locations that the API provides. In the Apple documentation, the next paragraph can be found: “When tracking changes to the user’s location, the distanceFilter property can be used to filter out update messages from the location manager to it’s delegate. However, such messages may still be delivered if more accurate measurements are acquired. Also, the distanceFilter does not impact the hardware’s activity - i.e., there is no savings of power by setting a larger distanceFilter because the hardware continues to acquire measurements. This simply affects whether those measurements are passed on to the location manager’s delegate. Power can only be saved by turning offthe location manager.”10 As can be seen, the parameter distanceFilter just defines a filter to filter the locations that are received before the delegate is called. That is why, for all the experiments developed in this section this parameter was set to zero. Using this configuration, the app was able to store all the locations that the location manager receives. The number of unique and equal positions and the time difference between them are going to be analyzed in the following sections because it may contain valid information, such as the user is not moving unless the vast majority of the locations that delegate receives change. The desiredAccuracy parameter does not guarantee any accuracy as it was stated by apple in this readme: umentation/UserExperience/Conceptual/LocationAwarenessPG/LocationAwarenessPG.pdf 9CLLocationManagerDelegate Protocol Reference https://developer.apple.com/library /ios/#documentation/CoreLocation/Reference/CLLocationManagerDelegate_Protocol/CL LocationManagerDelegate/CLLocationManagerDelegate.html 10LocateMe ReadMe.txt https://developer.apple.com/library/ios/#samplecode/Locate Me/Listings/ReadMe_txt.html 16 Accuracy study of iOS location services “Core Location does not guarantee that a measurement matching the desiredAccuracy will be delivered. Rather, a best effort is made, and may be constrained both by the capabilities of the device and the location and environment from which it is used. ... a GPS equiped device will often provide better than 10 meter accuracy, but not underground.”10 This fact is going to be analyzed in the Section 2.4.2 using different values for the desiredAccuracy property. His property belongs to the data type CLLocationAccuracy which is a double that “represents the accuracy of a coordinate value in meters”11. There are several constants defined for this property the fourth most accurate ones are kCLLocationAccuracyBestForNavigation, kCLLocationAccuracyBest, kCLLocationAccuracyNearestTenMeters and kCLLocationAccuracyHundredMeters which define a value of -2, -1, 10 and 100 respectively. Moreover, this property can be set to any positive double value. Once the location services have been started, whenever a new location is available the locationManager reports it to the locationManager:didUpdateToLocation:- fromLocation: method of its delegate12. The locations are stored in objects, which belongs to the class CLLocation. These objects have five location attributes, which are coordinate, altitude, horizontalAccuracy, verticalAccuracy and timestamp. The names of it are self-explanatory, thus an explanation of its meaning is not necessary. There are other two properties, which are speed and course. All these seven parameters were stored and analyzed; the results are shown in the following sections. This report analyzes the parameters coordinates, horizontal accuracy and timestamp. But it does not analyze other ones such as verticalAccuracy, speed and course. These parameters were not used for several reasons. The altitude and the verticalAccuracy do not provide any useful information because the 3D model has a better estimation of the altitude that the one than the GPS can provide. Moreover the vertical Accuracy was in all the cases bigger than 20 meters. As for the speed and course, their value was not available in the majority of the time. It had a value of 0 and -1 respectively. It can be assumed that this values were more time available using the new models of iPhone which are iPhone 4 and iPhone 4S. But since the system has to work in all model of iOS devices is useless develop an algorithm which needed data is not available all the time. 11Core Location Data Types Reference https://developer.apple.com/library/ios/#docum entation/CoreLocation/Reference/CoreLocationDataTypesRef/Reference/reference.html 12CLLocationManagerDelegate Protocol Reference https://developer.apple.com/library /ios/#documentation/CoreLocation/Reference/CLLocationManagerDelegate_Protocol/CL LocationManagerDelegate/CLLocationManagerDelegate.html 2.3 Experimental settings 23 Figure 2.6: Left: initial tab screen. Right: initial tab screen while harvesting data Figure 2.7: Left: routes tab. Middle: route info window. Right: map window 24 Accuracy study of iOS location services 2.4 Analysis of Static Measurements This section analyzes the accuracy several parameters that the location services provides in iOS. Moreover, it measures the time to first-fix and compares the accuracy of the iPhone and the Garmin watch. 2.4.1 GPS data processing Once the data which the iPhone and the Garmin watch provides were stored in text files with a known structure, open the text file using java and python to process the locations is fairly straightforward. The first step in the calculations was to convert the geographic to UTM (Universal Transverse Mercator) coordinates. As can be seen in the Figure 2.8, the geographic coordinates represent the locations in the hearth using three parameters, latitude, longitude and altitude. Latitude represents the angle between the equatorial plane and line perpendicular to the ellipsoid at that point. While the longitude is the angle between the meridian passing through that point and the prime meridian19. Figure 2.8: Geographic coordinates systema aA guide to coordinate systems in Great Britain http://www.ordnancesurvey.co.uk/oswe bsite/gps/docs/A_Guide_to_Coordinate_Systems_in_Great_Britain.pdf 19Geodetic Datum Overview http://www.colorado.edu/geography/gcraft/notes/datum/da tum_f.html 2.4 Analysis of Static Measurements 25 At the beginning of the study, the Haversine formula was used to calculate the distance between the real coordinates that the device was and the coordinates that the location services provided, the real horizontal error20.Butthisformula calculates the distance, it does not provide any information about the direction of this error. Moreover, in order to be able to plot scatter plots with the real position and the position that GPS provides using a Cartesian coordinate system, the geographic coordinates were converted to UTM coordinates. The distance between two points in UTM coordinates is the shortest Euclidean distance in meters, this was used to calculate the horizontal error. Unlike geographic coordinates UTM is used to represent the locations in a map. The datum used for GPS positioning is called WGS84 (World Geodetic System 1984). Thus, this is the datum that was used to convert from geographic coordinates to UTM. Further details about this conversion can be found in Section 3.3.2.1. The java code developed for this part for each location convert all the geographic coordinates into UTM coordinates and calculate the difference in both axes (x and y) between them and the real position that the device was placed during the experiment. The real UTM coordinates were obtained using digital DTU maps that Utopian City_Scape provided which were said to be very accurate. This program generates a new text file with the same information than the previous one but with the x and y coordinates centered in the real position instead of in the UTM coordinates system. This data was the data used to generate all graphs that area available in the results section. The graphs were generated using the python library Matplotlib21. 2.4.2 Horizontal accuracy comparison between different desired accuracies in iOS As aforementioned CLLocationManager allows the developer to configure the desired accuracy for the locations that provides. This parameter is a double, which represents the accuracy that the app needs in the positions that receives. For this comparison four different values for this parameter have been chosen as can be seen in the Table 2.1. All the locations chosen for this experiment were placed in outdoor locations in the DTU area. Only 3 out of 1893 locations were obtained through Wi-Fi po- 20Calculate distance, bearing and more between two latitude/longitude points http://ww w.ig.utexas.edu/outreach/googleearth/latlong.html#ellipsoid 21http://matplotlib.sourceforge.net/ 26 Accuracy study of iOS location services Table 2.1: desiredAccuracy values used in the analysis Name of the accuracy constant value kCLLocationAccuracyBestForNavigation -2 kCLLocationAccuracyBest -1 kCLLocationAccuracyNearestTenMeter 10 (custom value) 50 sitioning and none of them were obtained using Cellular positioning. Although the Location Manager does not provide this information directly, the type of positioning system used can be guessed using the value of the horizontal accuracy. Zandbergen in [Zan09] states that if the location is obtained using Wi-Fi or cellular positioning the altitude is not reported. During this analysis, this statement has been found incorrect since for all the locations that were gathered for this analysis an altitude was provided. The previous mentioned article is from 2009, so we can think that Apple have fixed this in this three years. Doing some indoor and outdoor testing’s, the horizontal accuracy that the Location Manager provides in Wi-Fi positioning has been found to be 65 while in cellular positioning it is an integer number usually bigger than 1.000. If A-GPS is used horizontal accuracy is usually smaller than 100 and it is a float number with 14 decimal positions. This can likely be attributed to the algorithm to calculate the accuracy in GPS is much more accurate that the one that it is used in the other two methods. Therefore, this section analyzes the accuracy of the A-GPS in the iPhone and not the other location systems. Figure 2.9 shows a scatter plot of the horizontal error calculated as was explained in the previous sections. The X and Y axes correspond with the X and Y coordinates of UTM. At a first glance, it can be seen that the best for navigation, best and nearest 10 m accuracies parameters provide similar results while the nearest 50 m provides slightly worse results. Other remarkably fact that can be seen in the graph is that the great majority of the positions are placed in the surroundings of the diagonal that cross from negative X and Y to positive X and Y. Moreover there are more positions in the right part of the graph than in the left one. Since, with this data we can conclude that the GPS positions provided by iOS location services were more likely to be in the south, north and east area from the correct position than to the west. But due to the limitations of this test we can not conclude that this is going to happen in all the situations. Table 2.2 summarizes the horizontal error calculations done for this experiment. As it was commented before the horizontal error for the best for navigation, best and nearest 10 m accuracies are very similar. The best minimum value among them is 45 cm surprisingly for the desired accuracy nearest 10 m while the 2.4 Analysis of Static Measurements 27 Figure 2.9: Scatter plot of horizontal accuracy for different desired accuracy in iOS in meters maximum is for the same desired accuracy and it is 43 m. As for the mean the best mean error was performed by the desired accuracy nearest 10 m and it is 8.7 m, although the values for “best for navigation” and “best” are very close. The RMSE values are for the three accuracies 11. . The better results for desired accuracy nearest 10m instead of for best for navigation or best which are supposed to be more accuracy could be explained using the way that the test were performed. In each location the test for each accuracy were performed one after the other starting with best for navigation continuing with best, nearest 10 m and nearest 50 m. As Apple states in its official iOS 5 website, the GPS accuracy improves during time since it can take several minutes to locate all the visible satellites22. Therefore, this can be the explanation of why the results are better in best than in best for navigation. The results for the desired accuracy nearest 50 m are slightly worse than for the other three as it was expected. The horizontal error average is 17.3 m, which is more than twice the one obtained for nearest ten meters. Zandbergen did a similar study with an iPhone 3G which includes the same A-GPS chip, it can be seen in [Zan09]. He obtained a horizontal error mean of 22iOS 5: Understanding Location Services http://support.apple.com/kb/HT4995 28 Accuracy study of iOS location services Table 2.2: Horizontal positional accuracy for different desired accuracy in iOS under real conditions in meters Accuracy min max mean RMSE Best for navigation 1.3581 23.3408 9.1048 11.2679 Best 0.5834 19.5479 9.2488 11.6861 Nearest 10 m 0.4516 43.0338 8.7107 11.3551 Nearest 50 m 0.7861 57.5612 17.2975 26.0383 6.9 m, minimum error of 0.4 and maximum of 18.5 m. The mean error is 1.8 m smaller that the one that has been obtained in this study. This can likely be attributed to two different reasons. The main one is that in Zandbergen‘s study the iPhone was placed in an ideal position in a tripod while in this study the iPhone was placed in a jeans pocket. This produces that clothes attenuate the GPS signal that the iPhone receives in our experiment. The second reason it is that the Zandbergen‘s experiments last for 20 min while our lasts for four times two minutes. The GPS improves the accuracy during the time, thus the accuracy in larger experiments has to be better. Apple states in its documentation10,that the horizontal accuracy is often better than 10 m which is proved in this analysis. Figure 2.10: Horizontal error distribution for the different desired accuracy in iOS Figure 2.10 shows the distribution of the horizontal error for the different desired 2.4 Analysis of Static Measurements 29 accuracies. As can be seen the distribution for the desired accuracies best for navigation, best and nearest 10 m is very similar. It can be said that it is almost the same. The horizontal errors from 0 to 10 are highly probable while from 10 to 15 are not very common. From 15 to 20 are likely again and bigger than 20 m are very unlikely. As for nearest 50 m, the most common error is between 0 and 10 but there are errors bigger than 10 that are probable as well, such as from 30 to 35 or from 50 to 55. The same data show in other way can be seen in Table 2.3. As can be seen using the three most accurate options the probability that the horizontal accuracy for a received location is smaller than 20 m is almost 1. As for a horizontal accuracy of 10 m is almost 0.7. Table 2.3: Percent of locations whose horizontal accuracy is smaller than a certain threshold (shown in each column) Accuracy <5 <10 <20 <50 Best for navigation 31.11% 71.61% 97.70% 100.00% Best 38.95% 66.52% 100.00% 100.00% Nearest 10 m 42.62% 68.35% 99.79% 100.00% Nearest 50 m 34.17% 67.92% 68.97% 78.62% The battery consumption was supposed to be included in the study. Apple provides a tool which is called Instruments23 to do this kind of analysis. This program has a template, which is called energy diagnostic that provides a diagnostic regarding energy usage. This template was used to store the information about the battery consumption during the different tests. The energy usage level shows the relative energy usage on a scale of 0 - 20. Not big differences were found executing the app with the different desired accuracies. In all the cases this parameter varies from 13 to 18 while the GPS was enabled. There was almost no difference during the periods of time that the GPS was enabled and disabled as can be seen in Figure 2.11. This is not a correct result since the GPS is said to be one of the most power consuming hardware in the smartphones. For this reason, this parameter was considered not accurate enough to be included in the analysis. The conclusion of this section is that the difference between the three most accurate desired Accuracy parameters is insignificant. Best for navigation, best and nearest 10 m provides very similar results in the entire tests, thus the selection of one or another in the final app is not going to change the results. But Apple does not recommend to use the parameter best for navigation unless the device is plugged in24. Therefore, best for navigation cannot be used for 23Instruments User Guide http://developer.apple.com/library/ios/documentation/Dev eloperTools/Conceptual/InstrumentsUserGuide/InstrumentsUserGuide.pdf 24Core Location Constants Reference http://developer.apple.com/library/ios/#DOCUMEN TATION/CoreLocation/Reference/CoreLocationConstantsRef/Reference/reference.html 30 Accuracy study of iOS location services Figure 2.11: Instruments screen shoot which shows battery and GPS probes. Red or black color bar shows when the GPS is enabled or disabled respectively the final system. Although the difference between nearest 10 m and best were so small, best is going to be used as the desired accuracy parameter. Since the GPS is not accurate enough for the high accuracy tracking that is the aim of this application, the best accuracy that the iPhone can provide has to be used. Moreover in the battery consumption analysis was shown that the difference in the battery consumption between the different parameters was insignificant. 2.4.3 Observed versus estimated accuracy in iPhone One of the most important parameters that Location Manager provides is horizontalAccuracy;thisparameterprovidesanestimationofhowaccuratethe provided location is. As it has been observed in the testings, this parameter can vary from 15 m to 149000 m. Although the normal values that have been observed in the DTU testing are usually below 100 m after few seconds after the location manager is started. But one question that may arise when we are speaking about estimated accuracy is how accurate this estimation is. This is what it is going to be analyzed in this section. The data set used in this section is the same one that was used in the previous one. The error calculated in the previous section was used to plot it in relation with the horizontalAccuracy that the location manager provides for each location. Apple does not provide any information about how this horizontalAccuracy is calculated but in conventional GPS devices this parameter is calculated using some algorithm derived from Dilution of Precision (DOP)25, which is based on the number of satellites that have been used to calculate the location. A scatter plot with the data can be seen in Figure 2.12. 25Dilution of Precision http://www.nrem.iastate.edu/class/assets/nrem446_546/week3/ Dilution_of_Precision.pdf 2.4 Analysis of Static Measurements 31 The first two conclusions that arise while seeing the graphs are that the predicted horizontalAccuracy is always bigger than the real one and the correlation between the predicted error and the real one is very weak, same results were obtained in [ZB11]. These two facts make the provided location even less accurate since the point of view of the developer. The location is known not to be very accurate but if the horizontalAccuracy would be accurate, the position could be somehow corrected. In this case, the comparison between two positions could be useful. But neither the location nor the estimated error are accurate, this is the worst possible scenario. Looking the Figure 2.12 carefully, it can be seen that although the correlation between the two variables is very low, higher estimated error are likelier to have higher real errors. Other relevant fact is that the estimated error tends to have primarily three values that are 17.07, 47.42 and 76.36 m. Moreover, there is not correlation between the different desired accuracies values and the estimated error as it was commented in the previous section. Therefore, histograms have been plotted for all the desired accuracies together for the three more common estimated errors. Figure 2.12: Comparison between estimated (by the location services) and real horizontal error These histograms can be seen in Figure 2.13, it can be observed that there is some correlation between the estimated and the real error. But the difference between 17 and 47 m are very small. As can be seen the only difference is that arealerrorbetween15and20mfor47mislikelierthaninthecaseof17m, 32 Accuracy study of iOS location services but in both the most probable real error is between 0 and 10 m. As it has been exposed the estimated error is not that accurate as it should be for values smaller than 60 m. But it can be useful for filtering out the positions that have an estimated error very high and that are almost always very inaccurate. These positions are usually the ones that are obtained using cellular positioning. The accuracy of these positions is enough for many kinds of applications that only needs to know in which are the user is but they are not accurate enough for high accuracy tracking. The conclusion of this section is that although the correlation between the estimated and the real error is low, it exists. Moreover, the estimated error can be very useful to discard the locations that are very inaccurate because they usually have a high estimated error, higher than 100m. Figure 2.13: Real horizontal error distribution for the different estimated horizontal errors 2.4.4 Time to first-fix in iPhone Apart from the accuracy, the time that the location services needs to provide an accurate position is a very important parameter. This is usually measured with the time to first fix (TTFF), which is the time that a GPS receiver needs to search for the available satellites and provides the current position. TTFF is usually classified into three different start types, which are cold, warm and hot. These parameters are not defined in any standard; the different GPS manufacturers provide their own definitions [ML08]. For this analysis only cold start is under consideration because Apple does not provide any information about how the downloaded location information for the hybrid system is kept in the internal memory. In April 2011, two researchers found that iPhone stored all the WiFi networks and cell towers around you in an unencrypted database in the internal memory26.Afterthat,Applepublished 26Tracking File Found in iPhones http://www.nytimes.com/2011/04/21/business/21data.h 2.5 Analysis of Measurements in motion 39 the time that the given iPhone position was received is used to calculate the point at that time in the Garmin path. For this calculation, it has been assumed that the movement between two Garmin positions was constant during the time and in a straight line. These calculations are made using UTM coordinates. Thus, the horizontal error is just the Euclidean distance in meters between the two coordinates. To try to obtain both routes synchronized, the iPhone and Garmin watch were started to obtain locations at the same. The Garmin watch provides in the GPX file when the route was started and when each location was received. Thus it was pretty easy to synchronize both. Although as can be seen in the final results this synchronization is not perfect and will introduce some error. That is why the calculated error has to be seen as a relative error that can be useful to compare between different point selections within the same route. It can not be seen as a real accurate error, which can be used to compare between different routes. Not only the maps were plotted, but also some graphs showing the error and the time for the different routes. The most important graphs can be seen in the Appendix B. These graphs were plotted using the python library Matplotlib 32. The locations that the iPhone provides were filtered out following several criteria that will be explained in the following sections. All the calculations were done for all this set of points. Moreover, only the unique positions were considered for this analysis. Since the parameter distanceFilter was set to zero in the entire test, the location manager provides the same position many times after it provides a new one. The time rate that this positions are received is going to be analyzed as well. But, for the error calculation the repeated positions are ignored. Two positions that are equal but with a different predicted horizontal accuracy are considered as different positions. 2.5.3 Calculated horizontal error As can be seen in Appendix B, nine routes were performed in the DTU area during the months of February and March 2012 for the development of this master thesis. In this section, the total error calculated for these routes are going to be presented. This section shows the main results for all the routes, although the results for each of the nine routes in detail can be seen in Appendix B. The analysis performed in this section was done in the same way as it was done for the static locations. The calculated horizontal error is studied with the 32http://matplotlib.sourceforge.net/ 40 Accuracy study of iOS location services scatter plots, numerical values of the distribution and the histograms. The scatter plot can be seen in 2.16. As can be seen in the scatter plot, the location of the different positions does not follow any pattern. It can be seen that the points tend to be placed in the diagonal between the first and the third quadrant more often than other places. But this tendency is very weak, thus it will be ignored from now on in this master thesis. Same tendency was found for the static positions, but in this case the pattern was more obvious. Other conclusion that can be obtained from the scatter plot is that the correlation between the predicted and the real error is very weak. The same conclusion was obtained in the case of the static positions. Figure 2.16: Scatter plot of horizontal accuracy for all the routes The results shown in Table 2.7 were obtained using all the unique positions that the iPhone obtained but the ones that have a predicted accuracy higher than 1000 m. The location manager usually provides these locations when the location service is started and are sometimes outside DTU and far away from the real location, thus it does not make any sense to include it in the analysis. The nine routes can be divided in three types of routes: routes that go inside a building, outdoor routes with curves and straight routes. The four first routes that appear in the table belong to the first group, routes which go inside a building. These routes are from 308 to 342, from 341 to 101, from 343 to 308 and from library to 229. The second group is outer routes that are from 115 2.5 Analysis of Measurements in motion 41 Table 2.6: Horizontal accuracy for the different routes in meters Route Min Max Mean RMSE From 308 to 342 7.46 188.34 26.59 38.80 From 341 to 101 2.28 175.08 30.86 40.05 From 343 to 308 1.04 133.87 36.23 44.07 From library to 229 6.13 132.91 35.49 47.02 From 115 to library 4.24 99.34 24.94 30.97 From 229 to 115 3.24 61.52 26.33 29.92 From Nordvej to 302 biking 4.62 93.08 26.57 33.60 From Knuth-Wintherfeldts to Nils Koppels Alle walking 3.76 41.47 17.83 19.02 From Nils Koppels Alle to Knuth-Wintherfeldts biking 4.69 218.90 30.32 38.33 All 1.04 218.90 27.13 35.10 to library, from 229 to 115 and from Nordvej to 302 biking. The last group is straight routes that is composed of two routes From Knuth-Wintherfeldts to Nils Koppels Alle walking and From Nils Koppels Alle to Knuth-Wintherfeldts biking. Analyzing the mean errors for these three different groups of routes in the Table 2.7, it can be observed that have different mean values. The mean value for the routes that cross a building is always bigger than the outdoor routes one. This result was expected since when the mobile go inside a building the GPS signal are lost and it takes a while to detect it again once it is outside. During this period without GPS signal either Wi-Fi positioning or inaccurate GPS positions are received, this produce degradation in the mean error. The straight routes should have better mean error than the outdoor with curves. This is true in the case of the route for Knuth-Wintherfeldts to Nils Koppels Alle that has the lowest mean error between all the studied routes. But the route from Nils Koppels Alle to Knuth-Wintherfeldts has a mean error, which is quite high. This has not a direct explanation but the time between unique positions in this route is the fastest between all the analyzed, one second. And the horizontal error has a high value and consecutive a low value all the time, thus it can be think that the iPhone does not provide very accurate timestamp of the locations with this time rate. It can be observed that the mean error for all the routes is 27.13 m, which is much higher than the one obtained for the static locations in the Section 2.4.2. Just looking the maps it can be seen that the error is higher than in the static positions since the rate which the locations are received is not high enough for provide an accurate route and the positions that are received are not accurate neither. However, the real error should be smaller than this because as it was explained before the route reference is not the real one, it is an estimation. 42 Accuracy study of iOS location services As can be seen in the Figure 2.17, the distribution of the horizontal error, the error between 10 and 20 meters are the most likely to happen. Errors higher than 20 meters are less probably as the error value increases. Moreover, error smaller than 10 meters are less probable as the error value decreases. Figure 2.17: Horizontal error distribution for all the routes The conclusion of this section is that the iPhone has a bigger horizontal error for measurements in motion than for static ones. Moreover, the straight routes have a smaller error than the ones that makes curves. The routes that combine curves and crossing building are the ones that have a bigger horizontal error. As the histogram shows the most likely horizontal errors are between 10 and 20 m. 2.5.4 Filtering out inaccurate locations As it was analyzed in Section 2.4.3, the predicted horizontal error that the location manager provides is not really accurate for small values (smaller than 100m). But it can be very useful to know if the position is really inaccurate and if the position is based in GPS positioning, Wi-Fi positioning or Cellular positioning. As can be seen in the Appendix B in the red routes, which includes all the positions that the iPhone obtained. There are parts of the routes where the iPhone provides pretty accurate positions, and there are other parts especially at the beginning and when a building is crossed that the positions are very inaccurate. These positions can have error of several hundred meters, which is inacceptable for high accuracy tracking applications which is the aim of this master thesis. Two examples of these very inaccurate positions can be seen in Figure 2.18. In all the route maps in this master thesis the blue line is the route that the Garmin Watch provided, the red one is the route that the iPhone obtained using all the 2.5 Analysis of Measurements in motion 43 Figure 2.18: Two examples of very inaccurate positions (inside yellow circle) in routes: from 343 to 308 (left) and from Nils Koppels Alle to Knuth-Wintherfeldts (right) positions and the green one is the one that is obtained after applying horizontal error and Wi-Fi positioning filter. The points that have high horizontal accuracy values are marked with a yellow circle. These types of positions have to be filtered out in order to obtain a more accurate tracking since it does not provide any relevant information. Analyzing the error graphs that are available in the Appendix B it was discovered that all this positions had a very high predicted horizontal accuracy. It was usually higher than 700 m and always higher than 100m. This positions are obtained using GPS but with few satellites available or using cellular positioning. As it was discovered during the development of this report, the predicted accuracy of the positions that are obtained using cellular positioning is always high, usually higher than 1000 m, and this predicted accuracy is always an integer instead of a float number. The predicted accuracy of the two examples that are shown in Figure 2.18 are floats number, thus it can be guessed that these positions are obtained using satellite positioning but with weak signal strength. As can be seen in Table 2.7, just removing the positions with accuracy higher than 100 m the results are way better especially in the routes that the results were very inaccurate. But, it was observed that sometimes when the GPS positions are not very accurate the location services switches to Wi-Fi positioning when you are outside. This fact worsens the tracking since these Wi-Fi positions are usually more than 50 m far from the real position. In the Figure 2.19, it can be seen two part of two of the analyzed routes with this Wi-Fi positions removed on the right or not removed on the left. Removing some of the positions obtained using Wi-Fi positioning was found to 44 Accuracy study of iOS location services Table 2.7: Horizontal accuracy for all the routes with different error and Wi-Fi filters in meters Error filter Wi-Fi filter Min Max Mean RMSE 1000 01.04 218.90 27.13 35.10 200 01.04 105.53 24.85 29.67 150 01.04 105.53 24.35 29.09 100 01.04 105.53 24.21 28.91 100 21.04 105.53 24.19 28.90 100 31.04 105.53 24.19 28.90 100 41.04 105.53 23.91 28.38 100 51.04 105.53 23.91 28.38 100 61.04 105.53 23.99 28.46 100 72.35 105.53 23.98 28.48 be a very good idea, but some of them are very useful for example to detect when the user is inside a building. Moreover, in the case of the device is inside abuildingtheWi-Fipositioningpositionswerefoundtobethemostaccurate available. To try to find the perfect valance between these two situations, a Wi-Fi positioning filter was defined as the minimum number of Wi-Fi positions that have to be provided in a row to use it. For instance, if the filter is 4 only the Wi-Fi positioning that is received in groups of four or more will be used and the ones that are received in groups of three or less will be removed and not used for the route calculations. As in a row it refers to that not other positions but Wi-Fi positioning ones are received between them. The Wi-Fi positioning filter has to be applied after the horizontal error positioning, since the location services sometimes provides positions with accuracy higher than 100 m when the user is inside a building. As was commented before in this report the Wi-Fi positions can be differentiated because the predicted horizontal error is equal to 65 m in almost all of them. Several Wi-Fi positioning filters were analyzed to try to find the best number for this parameter using all the routes. The results can be seen in Table 2.7. As can be seen in the table, the best result were obtained for error filter of 100 m and Wi-Fi filter of either 4 or 5. The mean error was improved almost 4 meters which is an awesome result since only two easy of implement filters have to be used to obtain these results. Error filters smaller than 100 are not considered since as it was seen in Section 2.4.3 the correlation between predicted error smaller than 100 m and the real error is very weak, thus positions with predicted error 76 can be more accurate than other positions with smaller predicted error. The green route in the maps that are shown in the Appendix B were obtained using an error filter of 100 m and a Wi-Fi filter of 4 meters. As can be seen the routes are much more accurate that the ones that the iPhone directly provides. 2.5 Analysis of Measurements in motion 45 Figure 2.19: Two examples of removing Wi-Fi positions (inside yellow circle) in routes: from 341 to 101 (above) and from 343 to 308 (below) 2.5.5 Time and speed between different locations In this section, the frequency which new coordinates are received is going to be analyzed. The routes used for this section have been filtered with an horizontal error filter of 100 m and Wi-Fi filter of 4 samples, since they are the filters that provide better results as it was seen in the previous section. Moreover, all the repeated positions have been filtered, thus the routes only contains unique positions for this section. As was commented in previous sections, the iOS location manager usually provides the same coordinates many times and this fact is undesired for a time analysis like this. In these cases, the time for the first position, which includes this coordinates, have been used as the timestamp for this position. Sometimes, the location manager does not change the coordinates but change the predicted accuracy. In case of better predicted accuracy, this is 46 Accuracy study of iOS location services Table 2.8: Time between unique positions for all the routes in seconds Route Name Min Max Mean RMSE From 308 to 342 0.06 72.56 16.23 26.59 From 341 to 101 0.50 104.11 7.89 19.25 From 343 to 308 0.99 140.00 23.90 39.77 From library to 229 1.62 104.85 32.83 45.96 From 115 to library 7.00 64.00 23.44 29.34 From 229 to 115 1.58 61.96 29.83 34.06 From Nordvej to 302 biking 0.99 30.00 4.61 7.19 From Knuth-Wintherfeldts to Nils Koppels Alle walking 0.93 51.65 3.47 7.47 From Nils Koppels Alle to Knuth-Wintherfeldts biking 0.97 38.00 1.63 3.79 Total 0.06 140.00 6.50 15.80 updated but not the timestamp. The time when each location is received is important for two main reasons. The first one is that it can be used to calculate the speed at which the user was moving; this speed should be used to move the users in the model correctly. The other reason is that it is useful to know the period of time between locations to design the route-improving algorithm correctly, this is explained in the next chapter. Figure 2.20: Time between position distribution for all the routes As can be seen in the Figure 2.20, the most likely times between new positions are 1 or 2 seconds. Many new positions were received in a period of time between 2 and 20 seconds. It is not very likely more than 20 seconds between new positions but as can be seen in the distribution it can happen. This has to 2.5 Analysis of Measurements in motion 47 Table 2.9: Speed between positions for all the routes in kilometer per hour Route Name Min Max Mean RMSE From 308 to 342 0.48 245.17 16.68 50.21 From 341 to 101 0.02 45.03 18.06 20.65 From 343 to 308 0.88 91.34 10.68 23.08 From library to 229 0.64 70.15 13.17 22.80 From 115 to library 2.67 9.80 5.98 6.38 From 229 to 115 2.78 43.24 10.10 14.72 From Nordvej to 302 biking 0.77 37.96 15.96 17.59 From Knuth-Wintherfeldts to Nils Koppels Alle walking 0.99 13.88 6.54 6.93 From Nils Koppels Alle to Knuth-Wintherfeldts biking 1.72 37.63 18.95 19.77 Total 0.02 245.17 13.66 19.11 Table 2.10: Absolute speed for all the routes calculated as the total time used to make the whole route in kilometer per hour Route Name Absolute Speed From 308 to 342 4.18 From 341 to 101 6.31 From 343 to 308 4.22 From library to 229 4.28 From 115 to library 4.70 From 229 to 115 6.21 From Nordvej to 302 biking 12.82 From Knuth-Wintherfeldts to Nils Koppels Alle walking 6.17 From Nils Koppels Alle to Knuth-Wintherfeldts biking 15.20 be taken into account in the development of the algorithm that represents the users in the model. The Table 2.8 shows the same data that was represented in the graph but for every route. As can be seen, the mean time including all the routes is 6.50 seconds, which is not really high, but for many individual routes this mean time is higher, and the maximum time was 140 seconds, which is really high. If we think in terms of the route groups that were explained before we can see that the time between positions have some correlation between routes that are from the same type. The routes that go inside a building have the highest maximum value, which makes sense since when the user goes inside the GPS signals are lost and the location manager starts to provide inaccurate positions which are filtered out in our system. Moreover, it can be observed that the routes that are straight or by bike have a mean time way smaller than the rest. The conclusion that we can obtain from this is that the GPS works better in these situations. 48 Accuracy study of iOS location services Not only the time is needed to calculate the speed but also the distance between the coordinates. Using both the speed between each position has been calculated, the results can be seen in Table 2.9. Taking into account that the routes were made approximately in a constant speed, walking or biking, it can be stated that the speeds that it is shown in Table 2.9 are really inaccurate. The means have no correlation between the different routes and the min and max speeds have a big difference. For this reasons the instant speed between two locations can not be used to represent the users in the model. Since the values for the instant speed are not accurate the absolute speed for each route has been calculated and can be seen in Table 2.10. These results are pretty accurate and the difference between the walking and the biking routes can be observed. The conclusion of this section is that the timestamp that the location manager provides for each location is not precise. Therefore, it can not be used to calculate the instant speed between two locations. For the representation of the users in the model the speed should be calculated for a group of several locations instead of between each two. 2.5.6 Trying to detect when the user goes inside a building In order to represent the users in the model in a more realistic way, it would be really useful to be able to detect when the user is inside a building. As it was commented in the previous sections if a position is obtained using Wi-Fi positioning the horizontal error that location manager provides is 65. If the user is inside a building accurate GPS positions cannot be obtained, therefore the location manager should use Wi-Fi positioning since it is the most accurate way the location can be obtained. It can be thought that if the received position is obtained using Wi-Fi positioning, the user is inside a building. But analyzing the routes this was found not to be truth because sometimes the location manager provides Wi-Fi positioning locations when the user is outside because the GPS ones are not accurate enough. After applying the Wi-Fi filter that was explained in Section 2.5.4 with a value of 4, all these Wi-Fi positioning positions that were obtained when the user was outdoor are filtered out. Only the Wi-Fi positions that were obtained when the user was inside pass the filter. They are always in groups of 4 or more positions because if there were positions between them the horizontal error filter would filter it. Because they have a high-predicted horizontal error due to the unavailability of reliable GPS signals. 3.2 Tools and concepts required 55 Although path finding algorithms cannot be used directly in this project, the problem that has to be solved is somehow a path finding problem. One of the objectives for this section is to find an obstacles free path between any two points in the 3D model. This can be seen as a short distance path finding problem. It varies from the classical path finding problem because the character has to move following the GPS positions received from the phone. An example of a system similar to the one developed for this master thesis can be found in [MYW10]. This article describes the implementation of a Pac-Man Game on campus using the locations that are harvested using a smartphone. Unlike our project, the system designed in this article does not make any transformation in the locations that are received from the smartphone. Other path finding practical implementation can be found in [MCP]. In this article the character is moved using the voice and the exact path is calculated using path finding algorithms. A technique for generating human motion path in 3D environments can be found in [SB00]. Both studies use a grid map for the path finding algorithm. This map has to be generated manually in our case as well. Thus this technique can note be used directly in our project. 3.2.2 Map matching Map matching is the process of correlating a sequence of user’s positions with the road network. It can handle different data types such as point-to-line, line- to-line and polyline to polyline. In this project point-to-line is going to be used. Regarding temporal-response characteristics, map matching can be classified into online and offline map matching. The online methods work with the received data in real time, while the offline ones work after the whole set of data has been collected. One part of the algorithm that has been developed in this project is a map matching algorithm that only works in case the road network is available. This algorithm is explained in Section 3.3.3.3. There are many studies in this field that solve different problems. Sometimes neither the location nor the network data are accurate, Christopher, David and Alain proposed several map matching offline algorithms that studied this problem using personal navigation assistants [CEW00]. Jagadeesh, Srikanthan and Zhang developed an online algorithm for real-time vehicle location that only uses GPS data [GRJZ04]. Marchal, Hackney and Axhausen designed an efficient algorithm that relies in the same than the two previous one, GPS data and network topology [FM04]. Other map matching approach for travel/activity research needs can be found in [Zho]. Other offline map matching approach can be found in [TG11]. It uses Douglas- 56 Representing the routes in the 3D model Peucker [DD73] algorithm to obtain key waypoints in the trajectory. This same algorithm was used in this master thesis. As it was commented before in this master thesis, sometimes the location services are not able to give an accurate position during a long period of time. A map matching algorithm was proposed in Seul National University for these cases [YJs05]. Road Reduction Filter (RRF) [GT99] is a method of detecting the road in which a vehicle is traveling along. This method compares road centerlines and trajectories described by the GPS positions. Further development of this algorithm can be found in [GTAH01]. The map matching algorithm that was developed for this master thesis is in 2D because the road network was provided in 2D, moreover the altitude in the GPS positions is very inaccurate. Regarding this reasons in our particular case using a 3D algorithm would not improve the accuracy. But for other applications where the road network is bigger it can improve the accuracy. Using a map matching 3D algorithm implies to have information of the network in 3D. Menglei propose a way of modelling the road network in 3D in [YZ10]. 3.2.3 Unity and the development environment Unity is a development engine that allows developers to create games and other interactive 3D content. Using Unity you can join your 3D models and assets to create interactive 3D content. This part of the master thesis was developed in Unity, since it is the tool that Utopian city_scape uses for the development of the web player in realsite. Therefore, the integration with realsite was easier than using other tools. The version of unity used for this project was the free version of Unity 3. Unity allows developers to program in C# or JavaScript, all the libraries can be used in both languages. C# was selected for this project, because it is the language that is used in realsite. The model as it is implemented in realsite is too heavy to be run in unity. Each building in DTU 3D model has two different versions, a high quality version and a low quality one. Therefore, a DTU 3D model combining high and low quality buildings was set up manually for the purpose of this master thesis. Some screenshots of this model during the development phase can be seen in Figure 3.3. To represent the routes in the model some object had to be moved through the route points. This object could have been any game object from unity or some 3D model imported into unity such as a human avatar. For the development phase, a sphere was used as can be seen in Figure 3.3. It was selected for 3.2 Tools and concepts required 57 Figure 3.3: Four screenshots of the development phase of the project in Unity simplicity since it is available directly in Unity. Moreover, once the algorithm it is done this is very easy to change. Each game object in unity can have a script attached to it that controls it. Thus, the ball has a C# script attached to it that is in charge of executing the route improvement algorithm and moving the ball around the DTU 3D model using the route result. The ball has a camera attached at the back of it that is moving with the ball. With this system, the user can see how the ball moves in the model following the improved route. As it was commented in Section 3.2.1, the problem that it is trying to be solved cannot be solved using path finding algorithms because of the unavailability of an environment map. But Unity has some path finding tools that allow the developer to build a navigation map, which is called navigation mesh (navmesh), in the editor1. This tool would have been really useful but it could not be used. To create the navigation mesh, the terrain has to be a static object, but every object is dynamic in realsite’s web player. Therefore, the path finding algorithm has to be developed from scratch using methods available in unity’s physics library2. Every object in unity has a Transform3. It stores the position, rotation and 1http://unity3d.com/support/documentation/Manual/Navmesh%20and%20Pathfinding.h tml 2http://unity3d.com/support/documentation/ScriptReference/Physics.html 3http://unity3d.com/support/documentation/ScriptReference/Transform.html 58 Representing the routes in the 3D model scale of the object and allows manipulating their values. If the object has any children, you can loop through them using the Transform of the parent. This was used in the project because each DTU building is composed of many children objects. The transform provides the name of the object that was used to differentiate between buildings and terrain or to detect doors in buildings. Each building and the terrain in realsite has a MeshCollider4attached. This allows to do collision detection using for example the RayCast method5. This method was used for detecting the existence of objects between points in the model. SphereCast method was used for the same purpose. These two methods return a struct, which is called RaycastHit. This struct provides the point of collision and the transform of the collided object in case of collision among others. 3.3 Solution designed 3.3.1 System requirements As it was described before, the routes cannot be represented directly in the model directly. The character would get stuck all the time, moreover there are positions that are unreachable such as the roof of the buildings. Therefore, a system has to be implemented to generate a new route that could be represented in the model. The requirements required for this system were the following: 1. The new route can be represented in the model and looks feasible. 2. The system has to work not only in the DTU 3D model but also in other 3D models that UCS has developed such as the Carlsberg area one. Thus, it has to be easily scalable. 3. The obtained route should be as close to the real route as possible. 4. The system has to be developed in Unity using C#. 5. All the algorithms have to be developed using libraries available in the free version of Unity and compatibles with realsite.dk. The solution for this problem proposed in this project is a novel algorithm that follows all the requirements proposed above and fixes all the problems presented 4http://unity3d.com/support/documentation/ScriptReference/Collider.html 5http://unity3d.com/support/documentation/ScriptReference/Physics.Raycast.html 3.3 Solution designed 59 in Section 3.1. The algorithm is a hybrid solution, with multiple steps. It includes not only a map matching algorithm but also other algorithms that can be considered as path finding algorithms. Although, they are not typical path finding solutions, these normally use an environment map and algorithms such as A*. The system was divided in five different steps that are executed one after another. Thus, the result of each algorithm is the input data for the next one. Although, it is not the most efficient way of solving this problem. It is the easiest to implement. Moreover, this project does not study the performance of the algorithm. This can be done in future improvements of the system. Each of the five different steps of the algorithm are explained in Section 3.3.3 in detail. 3.3.2 Converting from geographic to DTU coordinates and vice versa As it was described at the beginning of this chapter, the first problem that needed to be solved was the coordinate conversion from geographic to DTU coordinates. This conversion is explained in this section, although it is performed in the server side unlike the other algorithms, which are executed in client side player. 3.3.2.1 From UTM to DTU coordinates The only reference that was available about the DTU coordinate system is shown in Appendix C. As it can be seen it shows the transformation between UTM and DTU coordinates. Specifically, the UTM coordinates are in zone 32 and uses Euref 89 datum. The article suggests using the Helmert transformation. The Helmet transformation formula that was used to solve the problem was found in [Bes03] and [Teu88]. Using the Helmet formula and the data that is available in Appendix C the following formulas were obtained: ✓DTUx DTUy◆=✓cos(✓)sin(✓) sin(✓) cos(✓)◆✓UTMx UTMy◆+✓x y◆ 60 Representing the routes in the 3D model ✓UTMx UTMy◆=1  cos(✓)sin(✓) sin(✓)sin(✓)sin(✓)3 cos(✓)sin(✓)!✓DTUxx DTUy+y◆ =0.9998133 ✓= 14.3472 x= 834864.7242936 y= 6172294.56110385 These formulas were programmed in java and tested during the development of this master thesis. They were found to provide a very accurate transformation of the coordinates. 3.3.2.2 From geographic to UTM coordinates Once the transformation between UTM coordinates and DTU coordinates were solved, the next step was to solve the conversion between geographic and UTM coordinates. This conversion involves a huge number of calculations, as can be seen in [oOGP11] and 6. Therefore, the program of the algorithm it was going to be very time consuming. Since it is a very common transformation there are a lot of free resources on the Internet that solve this problem and they are already tested. Thus, instead of fully program the transformation a transformation already programmed was searched on the Internet and modified for the desired specifications in this problem. The datum used in the conversion that is available in Appendix C is Euref89 which differs from the one that the GPS uses which is WGS 84. A long search in the Internet ended up with the conclusion that Euref89 and WGS 84 are almost the same and that can be assumed that WGS 84 is used when Euref89 is used. As it could be observed with the conversion designed in this project this assumption is completely correct. Since the error in the conversion is negligible. Some of the conversions found on the Internet can be found in 789 .After 6Converting UTM to Latitude and Longitude (Or Vice Versa) http://www.uwgb.edu/dutch s/usefuldata/utmformulas.htm 7Coordinate conversions made easy https://www.ibm.com/developerworks/java/library /j-coordconvert/ 8Geographic/UTM Coordinate Converter http://home.hiwaay.net/~taylorc/toolbox/geo graphy/geoutm.html 9Convert Between Geographic and UTM Coordinates http://www.uwgb.edu/dutchs/usef uldata/ConvertUTMNoOZ.HTM 3.3 Solution designed 61 trying some of them, it was found that not all of them provides the same results, for instance the code that can be found in IBM website provided results several meters far from the real location, which is why this code was discarded. Geographic/UTM Coordinate Converter provided the best results; the locations were transformed perfectly. This was the selected code, the author claims in the website that the code can be used without restrictions. But the source code is in JavaScript, thus the code was translated from JavaScript to Java. To do that just some variables names and the method headers were modified. Although, Copenhagen are is in UTM zone 33U, the coordinate conversion, which can be seen in Appendix C, was projected into zone 32U. This is the zone used in the Danish mapping system. The code was modified to fulfill this requirement. During the development of this master thesis the conversion from geographic coordinates to DTU coordinates was tested many times. It worked perfectly in all the cases. 3.3.3 Algorithms developed to represent the avatar in the model The five stages, which compose the developed system, are explained in detail in the following sections. They are executed in the same order that they are exposed. In other words, the first algorithm that is executed is “Adding Building Entrances when the user is inside a building” and the last one is “Avoiding hitting buildings”. The different algorithms are executed in the order that makes that one algorithm cannot break what the previous algorithms fixed. But the previous algorithms will break thinks that the following algorithms will fix. For example all the algorithms can add new collisions with buildings to the route. That is why the last algorithm to be executed is “ Avoiding hitting buildings”. This order has the advantage that each algorithm only has to fix its problem and forget about the other ones because they will be fixed later. To show examples of the different algorithms in the following section, Google maps images are presented. These images were obtained using the Static maps API10. But the algorithms were executed in Unity with the 3D model. Thus, Google maps it is only used for the representation of these results. The representation in the model was more complicated to produce. A video would be necessary to show it properly. In the images, the blue line is the route obtained using the Garmin watch. While, the red and the green one are the ones obtained 10https://developers.google.com/maps/documentation/staticmaps/ 62 Representing the routes in the 3D model with the iPhone. The green one is the result after execute all the algorithms in Unity with the 3D model. 3.3.3.1 Step 1: adding Building Entrances when the user is inside a building As it was commented in Section 2.5.6, after applying an accuracy filter of 100m and a Wi-Fi positioning filter of 4 positions it is fairly easy to detect when the user was inside a building. The Wi-Fi positions that passed the Wi-Fi positioning filter which are in groups of 4 or more are the ones that were obtained when the user was inside a building in almost all the cases. Using this property, an algorithm was developed that do the following tasks: 1. It detects the Wi-Fi positioning positions in the route. 2. It removes the Wi-Fi positions that are inside a building. 3. It adds the building entrances of the building that is between the first Wi-Fi position that is inside a building and the previous one. It does the same for the first position that is outside a building between the Wi-Fi positioning ones. 4. It adds a jump in the route between the two positions of the doors. One practical example of this algorithm working can be seen in Figure 3.4, the blue line represents the route received from the GPS watch while the red one and the green one represent the iPhone route before the algorithm and after respectively. As can be seen, the algorithm has added the doors of the buildings 328 and 308 that are the doors that the user uses in the route. Thus, the algorithm works correctly in this example. Other examples have been tested obtaining the same results. This is the first executed algorithm for several reasons. The first one is that the Wi-Fi positioning positions cannot be filtered out before executing this algorithm. Otherwise some useful positions could be removed and the building in which the user was could be detected wrongly. Moreover, this is the only algorithm that uses the horizontal accuracy parameter. As it was demonstrated before, the correlation between the horizontal accuracy parameter and the real horizontal accuracy for values smaller than 100 m is really low. That makes this parameter useless for the rest of the algorithms. Therefore, this parameter is used in these algorithms and removed after it. 3.3 Solution designed 63 Figure 3.4: One example where two building doors (marked with a yellow circle) have been added to the route because the user was inside the building Once a building is detected using the RayCast method, the transform of the part of the building that is hit can be obtained using the RayCastHit struct 11. Using the parent of this transform, all the different parts of the building can be obtained. If the 3D model of the building has building entrance, the name of the entrance part contains the word entrance. This was the used method to detect where the entrances of a building are. But the center of the doors is usually a point that is not reachable for the character. Therefore, a new point that the character can reach has to be calculated. Four points that are one meter far of the center of the bounds of the door were calculated. The closest point to the previous position of the route was chosen. Following the implementation of this algorithm, the user jumps from one building door to the next one. Thus, the new route does not contain any information about where the user was inside the building. This is not a big problem, because the location services are really inaccurate inside the buildings. Which building is the user inside is the most accuracy that you can get. Moreover the inside of the buildings is not designed in the model. Therefore it makes no sense to position the user inside the buildings because it is empty. 11http://unity3d.com/support/documentation/ScriptReference/RaycastHit 64 Representing the routes in the 3D model 3.3.3.2 Step 2: filtering the routes using Douglas-Peucker algorithm After all the other algorithms were developed, the fast change of heading problem was the most important problem to solve. This problem was explained in Section 3.1.4. The best way of solving it is designing a filter that removes all these positions that are close one to another. Several studies have been done in curve simplification algorithms examples of these are [DD73], [BKR92], [Ram72]. Between them the Douglas-Peucker Algorithm [DD73] was found to be the one that provides better results for geographic information from GPS devices. Further studies using this algorithm has been developed to improve the performance of it [JH]. The first version of the Douglas-Peucker Algorithm was the filter implemented for this project. The Douglas-Peucker Algorithm is a recursive algorithm that reduces the number of points needed to represent a curve maintaining the accuracy. Other studies in the map matching field used this algorithm [TG11] as well. The algorithm recursively divides the line if the distance between the line segment with the first and last points as endpoints and a point is bigger than ✏. In our case, ✏ has a value of 5 m. This value was observed to work well for our system. Figure 3.5 shows an example of the algorithm working. The C# implementation of this algorithm developed for this master thesis can be seen below: public static ArrayList douglasPeucker( ArrayList route) { double dmax = 0 ; int index = 0; for (int i=1; i<route.Count; i++){ double d=perpedicularDistance( (Vector3)route[i], (Vector3)route[0], (Vector3)route[route.Count 1]); if (d > dmax) { dmax = d ; index = i ; } } ArrayList result = new ArrayList (); if (dmax > epsilon ) { ArrayList recursiveResult1 = douglasPeucker(route .GetRange(0 , index +1)); ArrayList recursiveResult2 = douglasPeucker(route .GetRange(index , route .Count index )); result .AddRange(recursiveResult1 .GetRange(0, recursiveResult1 .Count 1)); result .AddRange(recursiveResult2 ); }else {result .Add(route [0]); result .Add(route[route.Count 1]); } return result ; } If the route contains doors of buildings that have been added by the previous algorithm, the route is split before the Douglas-Peucker algorithm is executed. Each part of the route is treated as a new route. With this system, the Douglas- Peucker algorithm cannot filter out the positions that the previous algorithm added. After some testing of this algorithm, it was found to produce really good results in our system. The fast change of heading problem was completely solved with