Integración de dispositivos Android y uso de sensores en ...

F

Tecnologías en Informática

Integración de dispositivos Android y uso de sensores en un sistema de

localización en interiores

Memoria deItinerario de

UNIVERSIDAD DE MURCIA FACULTAD DE INFORMÁTICA

Máster en Nuevas Tecnologías en Informática



Memoria del Trabajo Fin de MásterItinerario de Redes y telemática

Autor: Rubén Alberto Rubio Muñoz

[email protected]

Tutores:

Óscar Cánovas Reverte

Murcia, junio de 2011



de Máster

1


AGRADECIMIENTOS

A Óscar, por darme una oportunidad más de trabajar en algo que me encanta y ayudarme a sacar lo mejor de mí mismo, cosa que no es siempre tarea fácil.

A Antonio, por hacerme sentir un elemento útil y valorado dentro de un grupo de trabajo y por ayudarme a salir adelante cada vez que me quedaba encallado.

A mis amigos de la Hermandad Robot, por haber sido mi segunda familia durante tantos años. A los que quedan aquí, pero también a los que se fueron. A los que se buscaron la vida en Madrid, al que pronto volverá de Suecia y, en especial, al que tuvo el valor de dejarlo todo y presentarse en Chile siguiendo su corazón.

A mi familia, que siempre ha estado y estará ahí para cuanto necesite.

Gracias.

2

Máster en Nuevas Tecnología en Informática

ABSTRACT

Location based services have experienced a great expansion during the past few years, both at research and commercial level.

Smartphones are mobile devices with great capabilities and specifications, similar to personal computers, with some additional advantages. They are more user-friendly and very comfortable to carry anywhere. These terminals are experiencing a wide adoption, due to their commercial success, and they arise much research interest in order to take the most of their potential.

The main goal of this project is to integrate the use of smartphones in an already developed infrastructure used to provide location based services for indoor environments. This infrastructure is modular and flexible, so it can easily grow with new functionalities, and it can perform location techniques without interfering with existing IEEE 802.11 data networks.

This project will try to exploit the resources within the smartphones. To be precise, it will use available sensors to increase the efficiency of the location process, avoid transmissions when they are not necessary and save battery, among other advantages. These sensors will be accelerometers, digital compasses and the camera. It is essential to study these sensors in order to know if they are suitable for the infrastructure and to know how to apply them.

Several techniques have been studied in order to adopt the use of sensors. Inertial sensors are used to perform motion analysis to infer the physical state of the device, while the photos taken with the camera are processed with an object detection algorithm, providing a collection of features. As we will see, the integration of this algorithm into our location system provides significant accuracy improvements.

3


ÍNDICE GENERAL

1. INTRODUCCIÓN ............................................................................................................ 6

1.1. MOTIVACIÓN .......................................................................................................................... 6

1.2. OBJETIVOS ............................................................................................................................. 8

1.3. ESTRUCTURA DEL DOCUMENTO .................................................................................................. 9

2. ESTADO DEL ARTE ....................................................................................................... 11

2.1. LOCALIZACIÓN EN INTERIORES MEDIANTE RSSI EN WLAN ............................................................ 11

2.2. SENSORES INERCIALES Y MAGNÉTICOS ....................................................................................... 13

2.2.1. Acelerómetros ............................................................................................................ 13

2.2.2. Giróscopos .................................................................................................................. 15

2.2.3. Magnetómetros ......................................................................................................... 15

2.3. TÉCNICAS DE APOYO A LA LOCALIZACIÓN MEDIANTE SENSORES INERCIALES ...................................... 16

2.3.1. Filtro de Kalman ......................................................................................................... 16

2.3.2. Dead reckoning .......................................................................................................... 17

2.3.3. Técnicas de clasificación ............................................................................................ 18

2.4. SENSORES PARA VISIÓN ARTIFICIAL ........................................................................................... 20

2.5. TÉCNICAS DE APOYO A LA LOCALIZACIÓN MEDIANTE VISIÓN ARTIFICIAL ........................................... 20

2.5.1. SIFT ............................................................................................................................. 20

2.5.2. Ferns ........................................................................................................................... 23

2.5.3. Operador Sobel .......................................................................................................... 24

2.6. SMARTPHONES ..................................................................................................................... 25

2.6.1. Especificaciones y características............................................................................... 25

2.6.2. Sistemas operativos ................................................................................................... 26

2.7. SISTEMAS DE LOCALIZACIÓN CON FUSIÓN DE SENSORES ................................................................ 27

2.8. CONCLUSIONES SOBRE EL ESTADO DEL ARTE ............................................................................... 28

3. DISEÑO DE LA SOLUCIÓN PROPUESTA ......................................................................... 30

3.1. ARQUITECTURA DE LA SOLUCIÓN PROPUESTA ............................................................................. 30

3.2. APOYO A LA LOCALIZACIÓN MEDIANTE SENSORES INERCIALES ........................................................ 33

3.3. APOYO A LA LOCALIZACIÓN MEDIANTE VISIÓN ARTIFICIAL ............................................................. 35

3.4. BALANCEO DE CARGA ENTRE CLIENTE Y SERVIDOR........................................................................ 38

4. IMPLEMENTACIÓN ...................................................................................................... 39

4.1. ASPECTOS DE IMPLEMENTACIÓN DE LA ARQUITECTURA EN EL CLIENTE ............................................ 39

4.2. APOYO A LA LOCALIZACIÓN MEDIANTE SENSORES INERCIALES ........................................................ 40

4.3. APOYO A LA LOCALIZACIÓN MEDIANTE VISIÓN ARTIFICIAL ............................................................. 41

4


4.4. VISIÓN GLOBAL DEL FUNCIONAMIENTO DEL SISTEMA ................................................................... 42

5. VALIDACIÓN Y PRUEBAS REALIZADAS .......................................................................... 44

6. CONCLUSIONES Y VÍAS FUTURAS ................................................................................. 46

6.1. CONCLUSIONES ..................................................................................................................... 46

6.2. TRABAJO FUTURO .................................................................................................................. 46

5


ÍNDICE DE FIGURAS

Figura 1: Zona de despliegue del sistema de localización actual .................................................... 13

Figura 2: Esquema de un acelerómetro ..................................................................................................... 14

Figura 3: Representación de un perceptrón simple ............................................................................. 19

Figura 4: Reconocimiento robusto de objetos mediante SIFT ......................................................... 21

Figura 5: Diferencia de gaussianas a distintas escalas ........................................................................ 21

Figura 6: Identificación de máximos y mínimos a distintas escalas .............................................. 22

Figura 7: Descriptores detectados en una imagen ................................................................................ 22

Figura 8: Uso de ferns en el entramiento .................................................................................................. 24

Figura 9: Arquitectura general del sistema .............................................................................................. 30

Figura 10: Flujo de ejecución de la solución propuesta ...................................................................... 31

Figura 11: Distribución de clusters ............................................................................................................. 36

Figura 12: Clasificación utilizando dos conjuntos de muestras diferentes ................................ 41

Figura 13: Funcionamiento global de la localización con fusión de sensores ........................... 43

Figura 14: Precisión de la localización para varias combinaciones de sensores ..................... 44

Figura 15: Latencia temporal del proceso de localización ................................................................ 45

6


1. INTRODUCCIÓN

1.1. MOTIVACIÓN El uso de la tecnología inalámbrica IEEE 802.11 ha ido creciendo en la última década, pasando de ser una tecnología orientada a mejorar la productividad de algunas empresas a estar casi omnipresente en nuestra sociedad. La gran aceptación de las redes Wi-Fi ha servido de combustible para su amplia adopción, no ya solo en entornos empresariales, sino también domésticos. Esta expansión ha hecho que la tecnología madure rápidamente y ha conseguido, asimismo, que el coste del hardware inalámbrico asociado haya decaído en gran medida, con lo que se sigue favoreciendo y asegurando su expansión.

Todo este incremento en la utilización de Wi-Fi, traducido en la disponibilidad de infraestructuras inalámbricas de alta calidad a precios más que razonables, es el factor clave de la explosión comercial de IEEE 802.11, pero también del interés académico a la hora de desarrollar iniciativas que exploten todo el potencial de estas redes inalámbricas.

Por otra parte, el uso de tecnologías de posicionamiento, como GPS, nos es cada vez más familiar, hasta el punto de que muchos teléfonos móviles cuentan ya con esta característica de serie. Desgraciadamente, estas tecnologías cuentan con algunas limitaciones, por las cuales no son aplicables a ciertos entornos urbanos o de interiores, entornos en los que su utilización podría ser muy interesante, ya que son aquellos en los que pasamos la mayor parte de nuestro tiempo.

Es en este ámbito en el que se hace interesante el desarrollo de un sistema de localización que nos ofrezca el comportamiento de un servicio de posicionamiento totalmente funcional situado en interiores de edificios, basado íntegramente en una tecnología tan expandida como Wi-Fi.

A día de hoy hay mucho esfuerzo de investigación y desarrollo en técnicas de localización basadas en Wi-Fi, lo cual ha facilitado la aparición de varios sistemas comerciales de posicionamiento basados por completo en IEEE 802.11. Todo este interés general en la creación de más y mejores sistemas de localización nos lleva a pensar que la localización es potencialmente una aplicación con mucho futuro en el terreno de las redes inalámbricas.

Es fácil entender por qué los servicios de localización son tan deseables. Una empresa que disponga de un sistema de localización en interiores contará con una característica muy valiosa y diferenciadora de la competencia. Además, cierto personal, como administradores de red o empleados de seguridad, podría beneficiarse directamente de algunas de las múltiples aplicaciones posibles de estos sistemas, que facilitarían su trabajo. Algunos ejemplos de estas funcionalidades son:

7


- La necesidad de localizar ciertos bienes de una empresa o ciertos miembros de su personal para incrementar la productividad

- Disminuir las pérdidas debidas al robo de determinados bienes

- Coordinar la localización de dispositivos con las políticas de seguridad de la empresa

- Mejorar las capacidades de la red WLAN

- Proporcionar a los clientes un servicio de localización

Pero las aplicaciones de los servicios de localización no terminan en entornos empresariales, sino que se pueden extender a mejorar las alternativas de ocio (por ejemplo, añadiendo localización a una partida de paintball), a la domótica y, en general, a cualquier ámbito que uno pueda imaginar.

Para maximizar la flexibilidad de estas aplicaciones hay que pensar en la variedad de los dispositivos que se desea localizar. Hasta ahora, la investigación relacionada con la localización en interiores se orienta, principalmente, al posicionamiento de equipos portátiles con capacidad de cómputo que cualquier usuario puede manejar y, en menor medida, de dispositivos ligeros, como tags inalámbricos, sin capacidad de cómputo. Sin embargo, es deseable ir más allá e incluir en estos servicios de localización en otra índole de dispositivos, concretamente los smartphones, cuyo uso se expande día tras día en nuestra sociedad.

Los smartphones (o teléfonos inteligentes, como son conocidos comercialmente en España) son terminales móviles que cuentan en los últimos años con una gran aceptación por parte de los usuarios. Estos teléfonos cuentan con especificaciones y capacidades similares a las de un ordenador personal, con la ventaja obvia de que se pueden transportar cómodamente en el bolsillo. El uso de este tipo de dispositivos está sufriendo una profunda proliferación en los últimos años, pues su demanda comercial se está viendo incrementada, y se están investigando numerosas formas de aprovechar todo su potencial. En este proyecto, en particular, se explotarán las posibilidades de estos dispositivos a la hora de formar parte de un servicio de localización en interiores. Además, es obvia la ventaja y la flexibilidad que supone disponer de una aplicación que cualquier persona pueda instalar en su terminal móvil personal y utilizar sin mayor complicación.

Las aplicaciones prácticas de este proyecto son numerosas e interesantes. Además de permitir a un usuario conocer su propia posición en un edificio que le es desconocido y de conocer la ubicación de otros usuarios y servicios del sistema (aplicaciones que surgen como implicaciones más obvias del sistema), el proyecto tiene un potencial muy amplio en lo que a cuestiones de domótica se refiere, pudiendo mostrar al usuario en cada momento, dependiendo de su ubicación física y de los recursos que haya a su alrededor, opciones para abrir y cerrar puertas, encender y apagar luces o utilizar cualquier otro sistema domótico, todo ello utilizando su propio teléfono móvil. Como se ha comentado antes, las aplicaciones son tantas como queramos imaginar.

8


Por todo lo comentado hasta ahora es fácil comprender por qué se ha depositado hasta ahora tanto interés en desarrollar sistemas de localización en interiores, en la mayoría de los casos basados en técnicas que trabajan únicamente con señales electromagnéticas para efectuar la estimación de la posición de los usuarios. El problema de este enfoque es que está limitado por cuestiones tecnológicas, como ruido e interferencias. De ahí que surja interés en adoptar esquemas que complementen a las señales inalámbricas.

Para integrar estos esquemas podemos aprovechar el potencial de los smartphones, concretamente en lo que al uso de sus sensores se refiere. Como veremos, los smartphones están equipados con diferentes sensores, los cuales tienen aplicaciones que pueden incidir directamente en la precisión y eficiencia de nuestro sistema de localización.

Entre estos sensores se encuentran los inerciales, que permiten conocer varios detalles del dispositivo que los lleva instalados, tales como su velocidad e inclinación, los cuales servirían por sí solos para llevar a cabo una primera estimación de la trayectoria del dispositivo. No obstante, no son los únicos sensores que se pueden aprovechar para beneficio del sistema de localización, pues muchos de estos teléfonos también cuentan con una brújula digital, útil también para conocer la orientación de los movimientos de los usuarios y, por último, también se puede aprovechar la propia cámara de fotos, elemento que se ha vuelto casi obligatorio en el ámbito de la telefonía móvil. Así, creando una base de datos con imágenes del entorno de aplicación, ésta podrá compararse con las imágenes recogidas por la cámara del teléfono y obtener así una nueva estimación de la posición. Se aprecian pues claramente las posibilidades que ofrecen estos dispositivos a la hora de mejorar la experiencia del usuario en un servicio de localización.

1.2. OBJETIVOS Esta Tesis de Máster tiene como objetivo principal la integración de smartphones, concretamente de dispositivos Android, en una infraestructura de localización en interiores basada en el estándar IEEE 802.11 ya desarrollada como parte de un proyecto anterior [37]. Esta infraestructura es abierta, modular y flexible, con lo que se pueden crear nuevas aplicaciones y servicios independientes entre sí sobre ella sin tener que modificarla. Además, el sistema permite llevar a cabo las labores de localización sin interferir en el uso habitual de acceso a datos de una infraestructura IEEE 802.11 habitual.

Lo más interesante de los smartphones, más allá de su comodidad de transporte y uso, es que cuentan con más posibilidades de las que puede parecer en un principio. Así pues, este proyecto no se limitará a crear un cliente para móviles Android compatible con la infraestructura de localización existente, sino que se tiene como objetivo explotar las características de estos aparatos, concretamente en lo que al uso de sensores se refiere.

Si bien se pueden conseguir unos resultados satisfactorios utilizando, como hasta ahora, las medidas de intensidad de señal de los puntos de acceso que se encuentran en las inmediaciones del dispositivo a localizar, para maximizar el aprovechamiento de los

9


smartphones analizaremos cada uno de los sensores disponibles, siempre que éstos puedan considerarse útiles como complemento a las técnicas de localización.

Se intentará orientar el uso de los sensores a aliviar la carga del servidor de localización evitando comunicaciones innecesarias entre el cliente y el servidor (con el consiguiente ahorro de energía del dispositivo y liberación del medio de transmisión inalámbrico asociados).

De la misma manera, y al trabajar con los sensores de los smartphones, se intentará también aplicar aquellas técnicas que complementen a la localización mediante RSSI (Received Signal Strength Indicator, o intensidad de la señal inalámbrica) que hay implementada hasta ahora, de manera que se mejore en la medida de lo posible la precisión del sistema de localización.

A la hora de analizar las técnicas que hacen uso de los sensores será muy importante hacer un estudio sobre lo exigentes que son en lo que a uso de recursos computacionales se refiere. El resultado de este estudio servirá para determinar si las técnicas deben integrarse en los propios smartphones o si, por el contrario, es más apropiado trasladarlas al servidor.

Para llevar a cabo todo lo anterior será muy propicio el estudio de sistemas reales que trabajen sobre la idea de fusionar los datos de distintos sensores a fin de intentar mejorar su rendimiento, de manera que éste sea un sistema relevante.

Cabe también decir que todo este proyecto se llevará a la práctica en práctica en el Departamento de Ingeniería y Tecnología de Computadores, en la tercera planta de la Facultad de Informática de la Universidad de Murcia.

Por último, hay que señalar que los resultados obtenidos a lo largo de la realización de este Trabajo Fin de Máster han dado como fruto un artículo [39] que se encuentra actualmente pendiente de publicación.

1.3. ESTRUCTURA DEL DOCUMENTO Este documento está estructurado en seis capítulos, que se comentan brevemente a continuación:

- El Capítulo 1 sirve de introducción al trabajo que nos ocupa.

- En el Capítulo 2 se intenta dotar de contexto al proyecto mediante una revisión del estado del arte, en la cual se describen y analizan tecnologías y soluciones a nivel de investigación para la localización en interiores con fusión de sensores.

- En el Capítulo 3 se detalla el diseño del sistema, señalando y argumentando las decisiones tomadas.

10


- El Capítulo 4 comprende la parte de implementación, en la cual se verán las herramientas utilizadas a la hora de desarrollar los apartados vistos en el Capítulo 3.

- El Capítulo 5 se centra en mostrar las pruebas de validación realizadas, mostrando los resultados conseguidos a lo largo de la realización del proyecto.

- En el Capítulo 6 se muestran las conclusiones tomadas tras todo el ciclo de vida del proyecto, junto a las vías de trabajo futuras que quedan abiertas tras su finalización.

11


2. ESTADO DEL ARTE Se denomina sensor a un dispositivo sensible a una determinada magnitud física, de tal forma que las variaciones de dicha magnitud producen algún tipo de cambio en el dispositivo. Los sensores pueden ser de muy diversas índoles, y no tienen que formar necesariamente de ningún sistema electrónico. Así, un termómetro de mercurio es un ejemplo claro de sensor, como también lo es un pistón neumático.

En esta sección nos centraremos en describir los principales sensores que son susceptibles de encontrarse en smartphones. Será necesario en estos sensores, obviamente, que transformen los datos recogidos en variables eléctricas, y más concretamente digitales, para poder trabajar con ellas. Nos centraremos, como se verá, en los sensores inerciales (acelerómetros y giróscopos), los sensores magnéticos (brújulas digitales) y los sensores presentes en las cámaras fotográficas digitales (CMOS y CCD). Si bien la antena WiFi podría considerarse un sensor más, dada la anterior definición, la obviaremos pues no es el objeto de este trabajo.

Hay que señalar, antes de entrar en materia, que la calidad de un sensor puede variar increíblemente, y que por lo tanto podemos encontrar sensores de la misma clase cuyo precio varíe desde unos pocos euros hasta varios miles. Como es lógico, los fabricantes de terminales móviles están interesados en minimizar el precio de sus productos, con lo que debemos tener en cuenta que estos sensores van a adolecer, por norma general, de unos niveles importantes de ruido y una precisión baja y es posible que, en ocasiones, no sea posible su aprovechamiento óptimo debido a estos defectos.

Además de explicar el funcionamiento de los citados sensores, se pretende comentar también las técnicas más importantes que, haciendo uso de la salida de los sensores, pueden aportarnos beneficios a la hora de integrarlas en nuestro sistema de localización.

Por último, un propósito importante de este capítulo es aportar referencias y pruebas que respalden las decisiones de diseño tomadas a lo largo del ciclo de vida del proyecto.

2.1. LOCALIZACIÓN EN INTERIORES MEDIANTE RSSI EN WLAN Antes de abordar en detalle los sensores y sus técnicas asociadas, que constituyen el arco central de este trabajo, es conveniente hacer un pequeño repaso a la localización en interiores mediante la intensidad de la señal o RSSI [48], la cual supone el punto de partida de este proyecto y es lo que se pretende mejorar y optimizar.

Aunque se han utilizado muchas tecnologías inalámbricas para desarrollar técnicas de localización en interiores, es IEEE 802.11 [23] la que más interesante resulta por su capacidad de reutilizar y aprovechar la infraestructura WIFI existente hoy en día en la mayoría de los edificios. Por otra parte, las técnicas basadas en RSSI son las que menos requerimientos hardware imponen, en contraposición con otras como las basadas en

12


mediciones de tiempo, que requieren un alto grado de sincronización, no siempre alcanzable, y las basadas en el ángulo de llegada, que precisan de hardware específico.

Ya situados dentro de las técnicas de localización mediante RSSI y haciendo uso de la tecnología IEEE 802.11, existen varias maneras de proceder. La primera de ellas es la lateración. Esta técnica se basa en que el hecho de que las señales electromagnéticas se propagan y atenúan en el espacio siguiendo unos modelos definidos y conocidos. Así pues, teóricamente, si conocemos la intensidad con la que se envía una señal y la intensidad con la que llega al destino, conociendo el modelo de propagación podemos calcular la distancia entre estos dos puntos. Si contamos con varios puntos conocidos (que serán nuestros puntos de acceso) y la RSSI con la que llega una señal de determinado usuario a cada uno de ellos, podemos calcular la distancia a cada uno de ellos y, conociendo esta distancia, inferir la ubicación del usuario.

Otra importante técnica que puede hacer uso de la RSSI es la técnica de las “huellas de radiación”. Esta técnica se basa en la estabilidad temporal que presentan las señales electromagnéticas en una misma ubicación en distintos instantes y en la variabilidad espacial de las señales en lugares diferentes. La técnica cuenta con dos fases bien diferenciadas. La primera de ellas es una fase de calibración o aprendizaje en la que se construye un mapa de radiación de la zona en donde se quiere desplegar la infraestructura. La segunda fase, que podríamos denominar fase de operación, consiste en la localización propiamente dicha. Cuando un usuario se desplaza por la zona de interés, se compara su “huella de radiación” con las del mapa que se construyó en la anterior fase y se estima su posición en base a la similitud de las medidas. La forma de definir esta similitud variará según el algoritmo utilizado. Se puede usar desde una simple distancia euclídea hasta algún algoritmo probabilístico que haga uso de redes bayesianas. Es precisamente esta independencia del algoritmo uno de los puntos más atractivos de las huellas de radiación, pues nos permite desarrollar una serie de servicios de localización independientes entre sí, con especificaciones y granularidades diferentes según las necesidades de los distintos usuarios.

El problema de las técnicas que utilizan la RSSI es que su eficiencia está limitada por la tecnología inalámbrica subyacente. En el caso de IEEE 802.11, su variabilidad espacial, unida a la presencia de ruido y posibles interferencias de otras señales hacen que el error medio que se suele conseguir con esta tecnología varíe en torno a 1.5 metros [12]. De esto se deduce que resulte interesante buscar técnicas de apoyo que colaboren con la RSSI para alcanzar mejores prestaciones, y es por esto que impera investigar las posibilidades de los sensores y cómo éstos pueden favorecer a nuestro sistema de localización.

La localización en interiores es un campo que despierta mucho interés comercial, de ahí que podamos comprobar que muchas empresas ofrecen despliegues de sistemas de localización en interiores. Empresas como Cisco [13], AeroScout [1] o Ekahau [15], entre otras. Un dato muy interesante es que ninguno de estos sistemas de localización comerciales desarrolla una solución que implique la fusión de distintos sensores, a pesar

13


de que sea un campo en el que se está trabajando a nivel de investigación. Esta es otra razón por la que resulta interesante este nuevo enfoque multisensor para la localización en interiores.

En el caso de la infraestructura de localización con la que se cuenta en este proyecto como punto de partida, se desplegó la técnica de huellas de radiación [37], diseñada con 94 puntos en los que los usuarios pueden ser localizados, con una separación de un metro y medio entre cada punto, según las recomendaciones vistas en el trabajo de King [25]. Sobre ella se probaron varios algoritmos de localización [38], ofreciendo los mejores resultados aquellos algoritmos probabilísticos. Se fue además un paso más allá adoptando un algoritmo al que, tomando como base el funcionamiento de un algoritmo probabilístico de localización, se le integró un modelo teórico del movimiento de los usuarios, basado en el Modelo Oculto de Markov [26]. Las pruebas realizadas en tiempo real con este esquema ofrecen un error medio inferior a 2.5 metros. La zona de despliegue, sita en la tercera planta de la Facultad de Informática, mide aproximadamente 1050 metros cuadrados y en ella hay seis puntos de acceso funcionando tanto para el acceso normal de datos como para ofrecer el servicio de localización. Se pueden ver en la siguiente imagen tanto los puntos de las huellas de radiación como los puntos de acceso en el entorno de despliegue:

Figura 1: Zona de despliegue del sistema de localización actual

2.2. SENSORES INERCIALES Y MAGNÉTICOS Veamos a continuación una pequeña introducción a los principales sensores inerciales y magnéticos.

2.2.1. ACELERÓMETROS Los sensores inerciales (acelerómetros y giróscopos) son los microsensores mecánicos más importantes en la actualidad, por su expansión y uso en cantidad de aplicaciones. Si bien las aplicaciones en los automóviles tienen la mayor parte del mercado, también es

14


común verlos últimamente en otros dispositivos, como en mandos de consolas y, lo que nos es más interesante aquí, smartphones.

Los acelerómetros, como su propio nombre deja ver, sirven para medir la aceleración de un dispositivo. Suelen utilizarse en grupos de tres, uno por cada eje espacial, de manera que cada uno de los sensores es capaz de medir la componente de la aceleración en su eje. Cuando el dispositivo se encuentre estático, los acelerómetros medirán las componentes en cada eje de la aceleración de la gravedad, con lo que se podrá calcular muy fácilmente la inclinación del dispositivo. Por otra parte, cuando el dispositivo se encuentre en movimiento medirá la aceleración total del dispositivo (incluyendo, por supuesto, la aceleración de la gravedad). Así, podrán medirse vibraciones e impactos, pues son fenómenos que provocan cambios en la aceleración de un dispositivo. Además, a partir de la aceleración y el tiempo podemos obtener la velocidad del dispositivo, y sabiendo la velocidad podemos obtener también la posición.

Un acelerómetro suele regirse por el siguiente esquema:

Figura 2: Esquema de un acelerómetro

Como se ve en la figura, un acelerómetro cuenta con una masa de pruebas y un resorte

elástico. La masa se mueve como consecuencia de una aceleración (o deceleración), y el dispositivo convierte este movimiento en un impulso eléctrico que contiene el valor de la aceleración. Posteriormente, el resorte devuelve la masa a su estado original.

En el contexto de este proyecto, el acelerómetro resulta un instrumento especialmente útil. Puede informarnos con mucha facilidad acerca de la condición del terminal y, si éste no se encuentra en movimiento, no es necesario lanzar todo el proceso de localización de nuevo. Así ahorraremos envío de nuevas tramas al servidor de localización y, dado que las comunicaciones inalámbricas son las actividades que más energía consumen en este tipo de dispositivos, alargaremos la vida útil de la batería del teléfono, un recurso muy importante que hay que economizar tanto como sea posible.

Por otra parte, y si los acelerómetros son lo suficientemente buenos, pueden utilizarse para llevar a cabo un procedimiento conocido como dead reckoning, que consiste en lanzar a cabo un proceso de navegación “a ciegas”, es decir, sin apoyarse en datos externos (como la WiFi) y basándose únicamente en modelos matemáticos, como se verá en detalle

15


más adelante. El problema de este método es el error cuadrático medio que lleva asociado, pero se aprecia claramente cómo sus propiedades pueden usarse como un importante complemento a la localización, si utilizamos periódicamente la WiFi para calibrar la posición del dispositivo y utilizamos dead reckoning a partir de ella.

2.2.2. GIRÓSCOPOS Los giróscopos son dispositivos cuya finalidad es medir el cambio de orientación de los dispositivos en los que se encuentran instalados. Al igual que ocurre con los acelerómetros, suelen verse en grupos de tres, uno por cada eje espacial. Cuando el dispositivo se encuentra estático podemos medir con él la orientación, como si de una brújula se tratase, pues los giróscopos, cuando no afecta sobre ellos ningún otro movimiento, tienden a alinearse con el meridiano terrestre, con lo que apuntan hacia el norte. Este norte es el norte celestial, y no el magnético. Una ventaja muy importante que surge a partir de este detalle es que, al contrario que ocurre con las brújulas, los giróscopos no se ven influenciados por la presencia de campos magnéticos.

Por otra parte, cuando el giróscopo se encuentra en movimiento, es capaz de medir la velocidad de giro de un objeto y, a partir de ella y del ángulo inicial (obtenido gracias a que conocemos el ángulo que forma el dispositivo con el norte celestial), el ángulo de giro del objeto.

El funcionamiento de los giróscopos se basa en un fenómeno físico muy particular conocido como movimiento de precesión. La precesión es la tendencia de un elemento a seguir girando con respecto al eje de rotación, y si hay fuerzas que afectan el cuerpo, éste tiende a girar en ejes perpendiculares a las fuerzas aplicadas, en lugar de en la misma dirección de dichas fuerzas, que sería lo más natural.

En el ámbito de este proyecto, los giróscopos pueden ser útiles como complemento a los acelerómetros, dado que conociendo tanto la aceleración como la orientación de un dispositivo podemos establecer perfectamente su trayectoria (siempre sin olvidarnos del error cuadrático medio asociado a los sistemas de navegación inerciales).

2.2.3. MAGNETÓMETROS Los magnetómetros son dispositivos que sirven para cuantificar el campo magnético ambiental, y detectar la posición que ocupa el teléfono respecto a él.

Al igual que ocurre con los sensores que hemos visto hasta ahora, suelen funcionar en grupos de tres, alineados con los ejes espaciales. De esta manera podemos conocer el campo magnético independientemente de la posición del terminal.

En este proyecto podrían funcionar, al igual que los giróscopos, para proporcionar información sobre la orientación. Esto tiene aplicaciones más allá del cálculo de la trayectoria, que es lo que se viene diciendo hasta ahora. Por ejemplo, si podemos asegurar que un dispositivo se está desplazando hacia el norte, podemos indicarle al servidor de localización que, a la hora de estimar la nueva posición del dispositivo, solo tenga en

16


cuenta las ubicaciones que se encuentran al norte de la actual. De esta manera aliviaríamos la carga del servidor y optimizaríamos el tiempo de ejecución de las consultas.

2.3. TÉCNICAS DE APOYO A LA LOCALIZACIÓN MEDIANTE SENSORES INERCIALES Se recoge en esta sección una pequeña colección de técnicas que se consideran aplicables en entornos en los que se cuenta con sensores inerciales, bien por ser lo suficientemente genéricas o por estar concebidas para éstos. De la misma manera, para cada técnica, se comentará ligeramente cómo puede favorecer y mejorar las prestaciones de un sistema de localización en interiores, justificando así su interés en este proyecto.

2.3.1. FILTRO DE KALMAN El filtro de Kalman [45] es un algoritmo basado en métodos matemáticos que, tomando como entrada ciertas medidas posiblemente ruidosas, proporciona como salida un estado más cercano a la realidad que el que obtendríamos únicamente mediante las mediciones. Es un algoritmo genérico, con lo que cuenta con numerosas aplicaciones tecnológicas. En concreto, podemos utilizarlo con las medidas de los sensores inerciales con los que cuentan los smartphones.

El filtro de Kalman trabaja con el estado del sistema, que describe de una forma aproximada el mundo real, o aquella parte que nos interesa para nuestra aplicación. El algoritmo cuenta con dos componentes básicos: el modelo y las mediciones. El modelo consiste en los estados o propiedades físicas que se utilizan para simular el sistema y la evolución de sus estados. Las mediciones sirven para hacer efectivas las transiciones entre estados.

Veamos una representación genérica del algoritmo:

1: �� , Σ��, �� , ��: 2: �� 3: Σ�� Σ�� !� 4: �� Σ�� "� �"�Σ�� "� � #�� 5: �� $ "�� 6: Σ� � �% $ ��"��Σ�� 7: �� , Σ� El algoritmo toma como entrada las estimaciones del instante anterior, así como la matriz de covarianza, que contiene el ruido acumulado. También toma como entrada las nuevas medidas de los sensores y, de manera opcional, un vector de control. El funcionamiento del algoritmo en sí cuenta con dos partes bien diferenciadas. La primera de ellas, conocida como fase de predicción, representada en el algoritmo por las líneas 2 y 3, consiste en actualizar el estado del sistema según el modelo diseñado (que, en nuestro caso, será un modelo ideal de movimiento del usuario). El modelo se especifica en la

17


matriz A y el ruido asociado a él en la matriz R. En esta fase aún no se utilizan las mediciones de los sensores, que no entran en juego hasta la segunda fase, conocida como fase de actualización, que abarca las líneas 4 a 6. Durante esta fase se corrige el modelo del sistema según las medidas tomadas por los sensores. Esta corrección depende en gran medida de la confianza que hayamos depositado en el modelo del sistema y de lo ruidosos que sean los sensores utilizados para tomar las medidas (y, consecuentemente, en la confianza depositada en ellos). Así pues, un filtro de Kalman que esté diseñado con una gran confianza en su modelo del sistema y que considere que las mediciones son muy ruidosas ofrecerá como siguiente estado del sistema uno más cercano al del modelo, tomando menos en consideración las mediciones de los sensores. Es, por lo tanto, de vital importancia un correcto ajuste de estas ponderaciones.

Así, conociendo la posición de un usuario en determinado instante, mediante el filtro de Kalman podemos inferir su posición en cada momento, utilizando como entrada del algoritmo el estado en el instante anterior y las nuevas mediciones.

Como se ha dicho, como parte del estado del sistema el filtro de Kalman proporciona una matriz de covarianza que nos sirve como indicador del ruido acumulado que está adquiriendo la estimación. Es interesante hacer uso de algún otro sistema de apoyo a la navegación (por ejemplo, el uso del sistema de localización mediante RSSI para fijar un nuevo punto de partida) cuando esta matriz supere ciertos valores, ya que el ruido se irá acumulando.

Esta técnica tiene aplicaciones directas en el ámbito de la localización en interiores, pues un smartphone podría valerse, como se ha comentado, de este algoritmo para inferir su posición sin necesidad de comunicarse con el servidor de localización nada más que cuando lo necesitase, por ser excesivo el ruido de las inferencias.

2.3.2. DEAD RECKONING Dead reckoning [36], denominada en castellano navegación “a ciegas” o navegación por estima, nace en el contexto de la navegación marítima. Se trata de una técnica de navegación basada en inferencia que se apoya únicamente en sensores inerciales, que pueden combinar acelerómetros, giróscopos y magnetómetros. Es, pues, una técnica menos robusta que el filtro de Kalman pero más sencilla e inmediata de implementar.

La idea de esta técnica es que, si contamos con la información de a la velocidad a la que nos desplazamos y conocemos nuestra orientación, podemos conocer nuestra trayectoria de una manera muy sencilla utilizando trigonometría básica. El único dato adicional que hemos de conocer es el punto de partida para así poder inferir teóricamente nuestra posición en todo momento.

Así pues, dead reckoning es el proceso de estimar la posición actual basándonos en la orientación y la velocidad de una posición anterior. Sea v1 el vector de movimiento que combina la velocidad y la orientación y representa la transición de la posición conocida, P0,

18


a la posición estimada, P1. Podríamos expresar el resultado de la posición tras las n primeras transiciones con la siguiente ecuación:

(2.1) &' � &( � ∑ �*+ � *,�'+-� Donde ve representa el vector de error asociado a las mediciones de velocidad y orientación. Se aprecia claramente que el error se irá incrementando medición tras medición, con lo que será necesario algún sistema de ayuda a la navegación que ajuste la posición una vez que el error comience a ser intratable. Es por esto que, además, se hace indispensable utilizar algún filtro que alivie el error intrínseco con el que cuentan los sensores que, además, en el caso de los smartphones puede ser muy acusado, ya que no son de la mejor calidad.

En el contexto de la localización en interiores, la aplicación de esta técnica ofrecería una gran autonomía al terminal móvil. Podría ahorrarse gran cantidad de energía si se limitasen las comunicaciones a solicitar al servidor de localización que calculase la ubicación del usuario únicamente en aquellos momentos en los que el error acumulado superase determinado umbral, tomando la técnica de dead reckoning como nueva P0 la localización calculada por el servidor y volviendo a comenzar todo el proceso. También se aliviaría así la carga computacional del servidor, haciendo el sistema más escalable.

2.3.3. TÉCNICAS DE CLASIFICACIÓN Otra forma en la que podemos aprovechar la presencia de sensores inerciales de una forma más sencilla y que ofrece un enfoque distinto a los comentados hasta ahora es mediante alguna técnica de clasificación. La idea general es que, al tomar como entrada la salida que ofrecen los sensores, podemos inferir si dichos datos son propios de un dispositivo que está en movimiento o de uno que se encuentra en reposo y aprovechar esta información como mejor convenga, según la aplicación. Como se ve, estas técnicas son mucho menos potentes que las comentadas hasta ahora, pero en según qué contextos pueden ser más que apropiadas.

La técnica más sencilla para conseguir este propósito es el perceptrón o clasificador lineal [11]. El perceptrón es la red neuronal más simple y su funcionamiento consta de dos fases. La primera de ellas es la fase de aprendizaje, en la que se entrena al perceptrón con una serie de entradas conocidas, que en nuestro caso podrían ser las salidas de los sensores, indicando en cada caso su clasificación. Esta fase produce un vector de pesos que se utilizará posteriormente, en la fase de operación. El significado matemático de este vector de pesos se representa gráficamente en la siguiente figura:

19


Figura 3: Representación de un perceptrón simple

Si consideramos A y B los conjuntos de entrenamiento de dos clases diferentes (las que queremos clasificar con nuestro perceptrón), el vector de pesos conseguido en la fase de aprendizaje es la línea que los separa y su ecuación es w · x + b = 0, siendo en este caso w y x vectores bidimensionales.

Hay que notar en este punto que la principal restricción que ofrece esta técnica es que, para que la fase de aprendizaje converja y se obtenga un vector de pesos que clasifique correctamente los conjuntos de entrenamiento, es necesario que éstos sean linealmente separables, es decir, que exista una recta que los separe en el plano bidimensional. Dicho de una manera más generalizada, debe existir un hiperplano que los separe en un espacio n-dimensional.

Una vez hemos obtenido nuestro vector de pesos podemos proceder con la fase de operación. En este caso, cuando obtengamos una nueva entrada y queramos clasificarla, habremos de hacer lo siguiente:

(2.2) .�/� � 01 2� 3 4 / � 5 6 00 � �� 8�2� 9 Donde w es el vector de pesos obtenido en la fase de aprendizaje, x es el vector con la entrada del perceptrón (por ejemplo, las salidas de los diferentes sensores) y b un término independiente y constante que no depende de la entrada, calculado también en la fase de aprendizaje. Así, en tiempo de ejecución, el perceptrón puede clasificar una entrada x de una manera inmediata, aplicando una única y simple función matemática. Según la salida de la función sea 1 o 0, querrá decir que el perceptrón ha clasificado la entrada de una forma u otra. En nuestro caso, podríamos aplicarlo haciendo que se infiera si un dispositivo está en movimiento o se encuentra estático.

Existen varias técnicas de clasificación que refinan la idea del perceptrón simple. Tomemos por ejemplo la técnica conocida como máquinas de vectores soporte [47]. Esta técnica no se limita a conseguir un hiperplano que separe los dos conjuntos de entrenamiento, sino que en su fase de aprendizaje se plantea un problema de optimización y se busca el hiperplano que maximice la distancia de separación entre las dos clases, pues es el que permite discernirlos de forma más clara.

20


Otra técnica que va un poco más allá es la de redes de vectores soporte [14]. Este método toma como base el de las máquinas de vectores soporte, pero además asume que es imposible que los conjuntos de entrenamiento sean linealmente separables. En este caso se intenta que el hiperplano obtenido sea capaz de clasificar los conjuntos de aprendizaje con el mínimo número de errores posible.

2.4. SENSORES PARA VISIÓN ARTIFICIAL Otros sensores con los que cuentan todos los smartphones son las cámaras fotográficas o, más concretamente los sensores CMOS [16] o CCD [42] (equivalentes digitales a la película tradicional).

El funcionamiento de estos sensores se basa en el efecto fotoeléctrico (la conversión de luz en corriente eléctrica). Funcionan con una gran cantidad de fotodiodos, que son los encargados de producir una corriente que variará en función de la intensidad de luz recibida. Estos diodos capturan únicamente la intensidad lumínica, con lo que se suele emplear un filtro conocido como máscara de Bayer para la distinción de los colores. Mediante esta máscara algunos diodos tienen un filtro para recoger solo la luz roja, otros para la verde y otros para la azul, de modo que se puede reconstruir la imagen.

A priori, puede parecer que las cámaras fotográficas pueden tener poca relación con un sistema de localización. No obstante, si nos paramos a analizar cómo nos ubicamos las personas en el espacio y cómo somos capaces de conocer nuestra propia localización, nos damos cuenta de que la visión (y, por ende, la imagen) tiene un papel muy importante. De esta manera, es factible la idea de mantener una base de datos con imágenes de la zona de aplicación del sistema y comparar una foto capturada por el smartphone en un momento dado con las que se encuentran almacenadas. De esta manera podríamos afianzar la seguridad que tenemos en la posición que se infiere únicamente con información de la WiFi.

2.5. TÉCNICAS DE APOYO A LA LOCALIZACIÓN MEDIANTE VISIÓN ARTIFICIAL De la misma manera que hemos visto una colección de técnicas que se consideran aplicables en entornos de localización en los que se cuenta con sensores inerciales, veamos a continuación algunas otras técnicas que, utilizando las cámaras fotográficas de los terminales inteligentes, pueden ayudarnos a la hora de desplegar un sistema de localización en interiores.

2.5.1. SIFT Esta técnica, denominada Scale Invariant Feature Transform [30] [31], es un sistema de reconocimiento de objetos en imágenes. Se trata de una técnica de extracción de descriptores de imagen muy robusta, pues los descriptores son invariantes a cambios en la escala de las imágenes, rotación, y parcialmente invariantes a cambios de iluminación, con lo que el reconocimiento de objetos que proporciona es muy potente. También ofrece robustez ante la eventualidad de que los objetos se encuentren parcialmente ocultos. De

21


igual manera, se puede conseguir identificar determinada escena o localización. Veamos un ejemplo de su funcionamiento:

Figura 4: Reconocimiento robusto de objetos mediante SIFT

El procesamiento de imágenes de SIFT cuenta con tres fases:

1.- Detección de puntos clave. Estos puntos deben ser invariantes a la escala de la imagen, con lo que se aplicará un filtro de diferencia de gaussianas a la misma imagen en distintas escalas.

Figura 5: Diferencia de gaussianas a distintas escalas

Teniendo las diferencias de gaussianas se buscarán máximos y mínimos en las diferentes escalas. En la siguiente imagen vemos la representación de un máximo o un mínimo. Lo será si su intensidad es mayor (o menor) que todos los puntos a su alrededor y también que los correspondientes puntos en las escalas anterior y siguiente. Éstos serán los puntos clave que buscamos.

22


Figura 6: Identificación de máximos y mínimos a distintas escalas

2.- Estimación precisa de cada uno de los puntos clave detectados en la fase anterior.

3.- Eliminar los puntos clave que se consideren inestables por tener el valor absoluto de su máximo o mínimo por debajo de determinado umbral.

Este procesamiento de la una imagen ofrece como salida gran colección de vectores de descriptores, invariantes a los factores ya comentados, como se puede apreciar en la siguiente imagen:

Figura 7: Descriptores detectados en una imagen

Cada vector de los que se aprecian en la imagen ofrece la dirección dominante de la intensidad de la iluminación en cada punto.

De una imagen de 500x500 se pueden extraer, aproximadamente, 2000 descriptores, si bien este número puede variar según el contenido de la imagen. El proceso de cálculo y extracción de descriptores puede implicar un tiempo computacional considerable, de uno o varios segundos, dependiendo del procesador utilizado.

De cara a mejorar un sistema de localización, podríamos esbozar sin entrar en detalle el uso de esta técnica de la siguiente manera: en primer lugar, habría que llevar a cabo una fase de aprendizaje en la que se tomarían fotografías del escenario de aplicación del

23


sistema de localización, hallando los descriptores SIFT de cada una de ellas y albergándolos en una base de datos. Después, durante el despliegue de la localización, podríamos hacer uso de un smartphone que tomase fotografías del escenario en el que se encuentra, hallar sus descriptores SIFT y encontrar una imagen cuyos descriptores coincidan con los de la recientemente capturada.

Se observa, pues, que el uso de imágenes proporciona un nuevo paradigma en el ámbito de las técnicas de localización que es interesante investigar, poniendo especial énfasis en la optimización del tiempo de extracción de descriptores, pues introduciendo este retardo de dos segundos ponemos en peligro la posibilidad de aplicar este enfoque de localización a entornos que requieran el cálculo de la ubicación de sus usuarios en tiempo real.

2.5.2. FERNS Hemos visto en el apartado anterior una técnica muy robusta para el reconocimiento de objetos y la extracción de descriptores de imágenes, capaz de identificar objetos aprendidos aunque estuviesen desplazados, girados, e incluso parcialmente ocultos. El coste computacional de esta robustez, como se ha visto, implica que la obtención de descriptores pueda suponer un par de segundos de ejecución. Sería deseable, en el momento en que estamos utilizando smartphones, hacer uso de técnicas menos exigentes computacionalmente hablando.

La técnica que se describe en esta sección ofrece esto mismo: una forma computacionalmente eficiente de extraer descriptores de imágenes y efectuar detección de objetos o escenas. Se basa en la idea de hacer pequeñas series de tests binarios sobre las imágenes. De hecho, los autores definen un fern [34] [35] como un conjunto de descriptores binarios muy sencillos, tanto es así que cada descriptor binario solo indica si determinado píxel tiene mayor intensidad que otro.

Como suele ocurrir en este tipo de aplicaciones, si queremos hacer un proceso de matching de descriptores para averiguar a qué clase corresponden futuras imágenes que tomemos, lo primero que tendremos que hacer es un proceso de entrenamiento que recoja las clases que queremos identificar. La forma de entrenar las clases mediante el uso de ferns sigue la idea que se representan en la siguiente figura:

24


Figura 8: Uso de ferns en el entramiento

Cada fi representa un test binario. Su salida será 1 si el píxel marcado con rojo tiene menor intensidad que el píxel marcado con azul y 0 si su intensidad es mayor (o viceversa). Si encadenamos n test tendremos 2n posibles salidas (entre 0 y 2n-1).

A la hora de entrenar un sistema basado en el uso de ferns deberemos determinar las clases que queremos identificar, aplicar las series de test binarios a un conjunto de imágenes de aprendizaje y obtener la distribución de las salidas de los tests. Posteriormente, cuando queramos clasificar una imagen, efectuaremos sobre ella estos mismos tests binarios y, según su salida, podremos inferir su clase.

Esta técnica, como se puede apreciar, es muy eficiente computacionalmente hablando. El coste de esta eficiencia, como se puede suponer, es la pérdida de robustez frente a otras técnicas más complejas, como la analizada en el capítulo anterior.

2.5.3. OPERADOR SOBEL El operador Sobel [41] es una técnica utilizada en el procesamiento de imágenes y tiene mucha utilidad en la detección de bordes. Suele aplicarse a imágenes en escala de grises, punto por punto, y ofrece para cada uno de ellos el gradiente de su intensidad. Este gradiente es una representación de la forma en la que cambian los niveles de brillo en la imagen. Si la fotografía cuenta con colores y bordes bien definidos, el cambio de un color a otro será muy brusco y el gradiente muy alto. De igual manera, si la distribución de colores es más homogénea no se detectarán bordes y el gradiente será más bajo. Esta técnica nos ofrece, pues, una forma de saber si determinada imagen es muy borrosa y desenfocada, ya que de serlo los bordes presentes en ella se encontrarán muy difuminados.

Para calcular el operador Sobel de una imagen hemos de aplicar dos máscaras a cada píxel, una para hallar el gradiente horizontal y otra para el vertical. Estas máscaras se aplican de la siguiente manera:

(2.3) :; � <1 0 $12 0 $21 0 $1> 4 �

25


(2.4) :? � < 1 2 10 0 0$1 $2 $1> 4 �

En donde A representa, para cada píxel, la matriz de 3x3 que tiene la intensidad de dicho píxel en la posición central y las intensidades de sus píxeles colindantes en las posiciones de alrededor. La magnitud del gradiente se calcula combinando las aproximaciones de los gradientes horizontal y vertical de la siguiente manera:

(2.5) : � @:;A � :?A

Sumando las magnitudes de cada uno de los píxeles podemos obtener un indicador de la bondad de la imagen, si consideramos que una imagen buena es una imagen bien definida y una mala una borrosa.

Una ventaja importante de esta técnica es su velocidad, ya que para imágenes con una resolución de 640x480 el coste temporal con un procesador de un smartphone puede tardar unas pocas decenas de milisegundos.

En nuestro ámbito de aplicación, y gracias al operador Sobel, podemos ser capaces de averiguar de una manera eficiente si una imagen es muy borrosa, en cuyo caso podemos desestimarla rápidamente y evitar posteriores procesamientos y envíos, con el consiguiente ahorro de recursos computacionales y de red.

2.6. SMARTPHONES

2.6.1. ESPECIFICACIONES Y CARACTERÍSTICAS Veremos a continuación una tabla con una serie de smartphones comerciales junto con sus especificaciones técnicas, pues es interesante, de cara a desarrollar aplicaciones que van a funcionar en dispositivos de este tipo, conocer qué clase de posibilidades y limitaciones presentan. Se presentan únicamente las características que resultan interesantes en este ámbito, si bien cuentan con muchas otras prestaciones, extraídas de las páginas web de los distintos fabricantes [3] [10] [18] [22] [40].

Modelo S.O. Frecuencia RAM Cámara Acelerómetro Giróscop

o

Magnetómetr

o

HTC Desire Android 1 GHz 576 MB

5 MPx Sí No Sí

HTC Legend

Android 600 MHz 384 MB

5 MPx Sí No Sí

iPhone 4 iOS 1 GHz 512 MB

5 MPx Sí Sí Sí

BlackBerry Bold 9900

BlackBerry OS

1.2 GHz 728 MB

5 MPx Sí No Sí

Samsung Galaxy S2

Android 1.2 GHz 512 MB

8 MPx Sí Sí Sí

Nexus One Android 1 GHz 512 MB

5 MPx Sí No Sí

26


Observamos unas características muy similares entre los terminales de gama alta. La frecuencia de los procesadores oscila en torno al gigahercio, la capacidad de la memoria RAM ronda los 512 MB y las cámaras son, generalmente, de cinco megapíxeles. La principal diferencia entre terminales es la presencia del giróscopo, que es un sensor más exclusivo que no aparece tan frecuentemente como el resto.

Con estas características podremos llevar a cabo la mayoría de técnicas que hemos visto a lo largo del capítulo, que en su mayoría suponen una carga ligera al procesador. La excepción sería el cálculo de descriptores SIFT, que a buen seguro supondría una sobrecarga importante en este tipo de dispositivos.

2.6.2. SISTEMAS OPERATIVOS La gran complejidad de los smartphones ha obligado a fabricantes y desarrolladores a crear una serie de sistemas operativos específicamente diseñados para manejarlos. Entre estos sistemas destacan, por su expansión en el mercado, Symbian OS, BlackBerry OS, Windows Phone, iOS y Android, que vamos a presentar brevemente.

Symbian OS [44] es un sistema operativo desarrollado en conjunto por una gran cantidad de fabricantes de telefonía móvil, como son Nokia, Sony Ericsson Siemens y muchos más. Este gran respaldo por parte de tantas empresas de telefonía es lo que ha impulsado su expansión, pues cuenta con una gran cantidad de terminales que lo llevan incorporado, con lo que desarrollar una aplicación para Symbian implica asegurarse de que será compatible con los terminales de una gran cantidad de usuarios. Su lado negativo es que muchos consumidores habituales de terminales Symbian no suelen estar interesados en las nuevas prestaciones de los smartphones, como la descarga de aplicaciones, con lo que en realidad el mercado que tienen es menor de lo que dictan sus cifras.

BlackBerry OS [10] funciona únicamente en dispositivos BlackBerry, y está orientado más al uso de profesionales que al de los consumidores medios, de ahí que sea más común verlos únicamente en entornos empresariales, para proporcionar a los empleados un gestor de correo electrónico, agenda, etcétera, y poco en otros ámbitos más domésticos. Este hecho también implica menos desarrollo de aplicaciones para este sistema.

Windows Phone [49], anteriormente conocido como Windows Mobile, es la propuesta de Microsoft para teléfonos inteligentes. Si bien empezó con una orientación hacia el entorno empresarial, similar al modelo de BlackBerry, ha cambiado de rumbo con su última versión, Windows Phone 7, acercándose más al usuario medio, pero rompiendo la compatibilidad con todos los modelos anteriores. Este hecho, unido a la juventud de esta última versión del sistema operativo, ha hecho que de momento no alcance una expansión significativa.

iOS [3] es el sistema operativo móvil de Apple, y su expansión se limita a los dispositivos iPhone, iPad y iPod Touch. Al contrario de lo que ocurría con Symbian, sus usuarios medios tienen una forma de afrontar la telefonía móvil más en sintonía con las

27


posibilidades de los smartphones, con lo que el esfuerzo de desarrollo de una aplicación en este sistema se suele ver mejor aprovechada.

Android [2] es el sistema operativo para móviles de Google y, aun siendo el más joven de los comentados hasta el momento, es el que está experimentando una expansión más brusca en la actualidad. Además, el perfil medio de sus usuarios es más similar al de los de iOS, lo que sumado a su mayor número de consumidores conlleva mucho interés en el desarrollo de aplicaciones compatibles con esta plataforma.

2.7. SISTEMAS DE LOCALIZACIÓN CON FUSIÓN DE SENSORES Veremos a continuación un pequeño análisis de sistemas de localización existentes a nivel de investigación que pueden resultar interesantes en nuestro ámbito por conjugar la localización clásica mediante RSSI con el uso de sensores y teléfonos móviles, y que ofrecen distintas ideas y formas de proceder.

La propuesta presentada por Hille [21] utiliza imágenes de la cámara del teléfono móvil para extraer descriptores de lo que los autores denominan “landmarks”, que no son otra cosa que aquellos puntos en donde intersecan las paredes con el suelo. Para la extracción de descriptores se utiliza una técnica conocida como Ransac [17], muy costosa computacionalmente hablando.

Este sistema parte de una fase de entrenamiento en la que se construye una base de datos con los descriptores de los landmarks. Además, esos descriptores se hacen corresponder con su ubicación real de en el mapa del entorno. Posteriormente, en la fase de operación, se utiliza un algoritmo de localización basado en RSSI para determinar, no la posición exacta del usuario, sino la zona aproximada en la que se encuentra y la cámara del teléfono móvil envía la imagen que acaba de tomar al servidor. Con la información obtenida gracias a la RSSI se puede acotar la búsqueda de imágenes en la base de datos y su correspondiente proceso de matching para no tener que hacer una búsqueda exhaustiva y limitarse a comparar la imagen que ha enviado el usuario con aquellas que se estiman cercanas. Según la correspondencia de los descriptores se obtiene finalmente la ubicación y la orientación del usuario.

El error medio de localización que ofrece esta técnica es de solo 30 centímetros, lo cual queda muy por debajo de lo tecnológicamente alcanzable usando WiFi, con lo que vemos que estas técnicas son muy interesantes para mejorar las prestaciones de la localización. Como punto negativo hemos de señalar que la técnica tarda aproximadamente diez segundos en completar un ciclo completo de localización, desde que el móvil envía la información de sus sensores hasta que recibe su ubicación, lo cual imposibilita su uso en aplicaciones que requieran un seguimiento en tiempo real.

En [19] se nos presenta otra técnica que combina la localización por radiofrecuencia con procesamiento de imágenes. Si bien lo hace de una manera algo más rudimentaria que el sistema anterior. Se basa en la idea de poner una serie de marcas (similares a los códigos QR utilizados en diversas aplicaciones de telefonía) en el suelo a lo largo de todo el

28


entorno de aplicación. Estas marcas llevarán codificada su propia ubicación, de manera que cuando el teléfono móvil capte alguna de ellas sabrá la zona en donde se encuentra. Como es lógico, la precisión del sistema será mayor cuanto más densidad presenta la distribución de marcas por el suelo.

Este sistema, con un despliegue suficiente de marcas, se podría conseguir una muy buena precisión, así como unos tiempos de procesado razonables. El problema es que no es realista asumir que va a ser posible poblar el suelo de cualquier edificio con estas marcas.

Otro enfoque distinto a los anteriores que también combina el uso de distintos sensores es el que se describe en [7]. Este trabajo toma una idea similar a la de las huellas de radiación, que se basaba en la idea de que cada sitio tenía unas características únicas en cuanto a intensidad de señales inalámbricas. En este caso, además, los autores parten de la base de que cada lugar tiene también unas características únicas de color e iluminación.

Para extraer la huella de color e iluminación se toman en consideración únicamente las fotografías tomadas al suelo (podemos saber en todo momento la orientación del teléfono gracias a los acelerómetros), y se extraen los colores dominantes y la intensidad de la luz. Así, se puede crear una base de datos con las características de color e iluminación de la zona de despliegue y, en la fase de operación, analizar las imágenes del usuario y compararlas con las de la base de datos.

De una forma parecida se realizan mapas de huellas de sonido (con el micrófono) y movimiento (con los acelerómetros), basándose también en la idea de que el ruido ambiental variará según el lugar en donde nos encontremos, así como la forma en que las personas se desplazan.

El problema de esta técnica es que, por su concepción, ofrecerá estimaciones a nivel de habitación, sin mayor precisión (lo cual puede ser más que suficiente en muchas aplicaciones), y su rendimiento depende mucho de que el entorno de aplicación cuente con lugares lo suficientemente heterogéneos.

2.8. CONCLUSIONES SOBRE EL ESTADO DEL ARTE En este capítulo se ha pretendido ilustrar, de una manera lo más clara y objetiva posible, la situación actual del ámbito de aplicación de este proyecto, tanto a nivel de tecnologías y técnicas aplicables existentes en teoría como en sistemas existentes a nivel de investigación.

Hemos visto que los teléfonos inteligentes o smartphones, en plena expansión comercial, son cada vez más potentes y, a pesar de sus limitaciones, son capaces de ejecutar aplicaciones de cierta envergadura. Además, cuentan con una serie de sensores que ofrecen gran cantidad de posibilidades a la hora de incrementar las posibilidades y la eficiencia de los sistemas de localización, con lo que su estudio ha quedado sobradamente justificado.

29


De la misma manera, una vez presentados los principales sensores presentes en los teléfonos móviles, hemos analizado algunas técnicas que nos permitirán explotarlos todo lo posible. Estas técnicas son las que se tomarán en consideración en la fase de diseño para que formen parte de nuestro sistema.

Por último, hemos visto algunos sistemas de localización que integran el uso de sensores y que están siendo desarrollados a nivel de investigación. En general, podríamos decir que los sistemas que hacen uso de visión artificial son demasiado lentos para llevarlos a la práctica en despliegues que requieran una localización en tiempo real, lo cual ya nos adelanta que el tiempo será un recurso muy importante a tener en cuenta y que habrá que procurar economizarlo por todos los medios, dedicando a ello el esfuerzo necesario.

Dado que todas estas propuestas que incluyen fusión de sensores existen solo a nivel de investigación y no comercial, vemos aquí una motivación especial en conseguir buenos resultados, dado que este enfoque de localización es muy novedoso e interesante de cara a futuros despliegues en entornos reales.

30


3. DISEÑO DE LA SOLUCIÓN PROPUESTA

3.1. ARQUITECTURA DE LA SOLUCIÓN PROPUESTA Como se ha comentado varias veces en los anteriores capítulos, este proyecto surge

dentro del contexto de la arquitectura de un sistema de localización en interiores basado en WLAN desarrollado con anterioridad y actualmente en expansión.

Para ilustrar correctamente tanto el alcance de este trabajo como su contexto y su lugar dentro de la arquitectura general dentro de la cual se integra, veamos en la siguiente figura un esquema, basado en las ideas de las arquitecturas propuesta en [20] y [43], que representa las principales entidades del sistema global así como las relaciones entre ellas:

Figura 9: Arquitectura general del sistema

Este proyecto va a estar más íntimamente relacionado con las entidades inferiores, que son las relacionadas con los sensores. La entidad Sensor hace referencia al hardware de los dispositivos que van a ser localizados, en concreto a sus sensores, y también a los drivers que capturan y ofrecen los datos en bruto de los sensores RSSI, los inerciales y las cámaras fotográficas digitales. El presente trabajo se centra en la capa denominada Sensor manager, encargada de recoger los datos en bruto que se ofrecen en la capa Sensor y realizar con ellos algún tipo de procesamiento, de manera que sean útiles en el proceso de

31


localización. Algunos ejemplos de funcionalidad de la capa Sensor manager son calibrar los valores de RSSI según la interfaz inalámbrica del dispositivo que los haya recogido, extraer descriptores de imágenes, filtrar el ruido de los sensores inerciales, etcétera. Este procesamiento se puede llevar a cabo tanto en los propios dispositivos que se van a localizar como en el servidor de localización. Dependerá, en cualquier caso, de la potencia de cómputo de cada dispositivo y de lo exigentes que sean los procedimientos utilizados, computacionalmente hablando. Por último, una vez que los datos han sido procesados convenientemente, la información resultante se ofrece al Context model, y acabará alojada en la base de datos para su posterior uso durante el proceso de localización.

Una vez sabemos dónde se sitúa este proyecto dentro del sistema de localización al que pertenece estamos en situación de analizar a un nivel general su arquitectura, y en las siguientes secciones podremos estudiar más a fondo sus funciones y características.

El diagrama de flujo de la solución se presenta en el siguiente esquema, y representa el esqueleto de lo que será la aplicación a desarrollar:

Figura 10: Flujo de ejecución de la solución propuesta

Para entender correctamente la figura hemos de saber qué nomenclatura se utiliza en ella, que será la siguiente:

- Los módulos cuya etiqueta comienza con get hacen referencia a la extracción de datos en bruto directamente de los sensores. Como es lógico, esta funcionalidad ha de

32


ser implementada forzosamente en los smartphone, ya que los sensores vienen integrados en ellos.

- Los módulos etiquetados con sleep quieren decir que se dan las condiciones apropiadas para que el smartphone detenga su ejecución regular durante un determinado intervalo de tiempo o hasta que se den unas condiciones concretas. Estos periodos sirven para no agotar demasiado rápidamente la batería del teléfono móvil.

- Los módulos cuya etiqueta comienza por put indican que se ha de enviar la información inferida a partir de la salida de los sensores a la base de datos. Como se comentó anteriormente, esta información provendrá de un procesamiento al que se someterán los datos en bruto, y este procesamiento se realizará en el propio smartphone o en un servidor habilitado para tal efecto, dependiendo en cada caso de las características de las técnicas implementadas.

Ahora que se entiende a qué se refiere cada uno de los bloques de la anterior figura, es fácil comprenderla en su conjunto. El proceso comienza con la recolección de los datos de los sensores, salvo el del acelerómetro, ya que para lanzar el proceso de localización se asume que el usuario siempre comienza en movimiento. El módulo getRSSI no es otra cosa que un escaneo de la red inalámbrica para detectar los puntos de acceso alcanzables en las inmediaciones, así como información relevante asociada, como la RSSI con la que se reciben. Si no conocemos ninguno de los puntos de acceso encontrados, significa que nos hemos alejado demasiado de la zona de despliegue de la infraestructura de localización (o que no nos encontrábamos en ella en primera instancia), así que podemos dormir el móvil de manera temporal, esperando a que el usuario se acerque a la zona en la que está habilitado el servicio de localización. Por el contrario, si los APs nos resultan conocidos, podemos continuar con la ejecución, que implica captar una imagen de la cámara del teléfono. En este punto llegamos a otro condicional. Se trata de averiguar, mediante alguna técnica apropiada, si la imagen es útil para efectuar su procesado y posterior almacenamiento en la base de datos. Así, la imagen se procesará y almacenará en la base de datos según este test, pero la información extraída de la WiFi lo hará de todas formas, así como la de los acelerómetros. En este punto dejamos inactivo al terminal inalámbrico y monitorizamos los acelerómetros. Se obtendrá en este momento la salida de los sensores inerciales a intervalos regulares y se procesarán para inferir si el terminal se encuentra o no en movimiento. De permanecer estático se seguirán monitorizando los acelerómetros hasta que se detecte el movimiento o expire un temporizador, momento en el cual se relanzará todo el proceso.

Ya sabemos, a un alto nivel, cómo funciona el sistema. Vamos a ver cuáles son las técnicas utilizadas para el procesamiento de los datos de los sensores.

33


3.2. APOYO A LA LOCALIZACIÓN MEDIANTE SENSORES INERCIALES En el capítulo anterior hemos analizado varias técnicas capaces de aprovechar la presencia de los sensores inerciales presentes en los smartphones. En esta sección vamos a ver cuáles de ellas se han podido aprovechar y su diseño.

La primera técnica que hemos analizado, que es también la más potente de ellas, es el filtro de Kalman. Como se comentó en el capítulo anterior, el filtro de Kalman es un algoritmo muy potente que, tomando como entrada un modelo teórico de movimiento y la salida de los sensores inerciales, es capaz de suavizar el ruido que éstos tienen asociado e inferir el movimiento del terminal.

Para determinar si esta técnica es aplicable en nuestro entorno se han llevado a cabo una serie de pruebas empíricas, que han ofrecido conclusiones poco alentadoras. Según se ha podido comprobar, los sensores inerciales presentes en los teléfonos inteligentes son de una gama demasiado baja y sus niveles de ruido, si bien pueden ser tolerables en otro tipo de aplicaciones como conocer la orientación e inclinación del dispositivo con una confianza razonable, no han resultado apropiados para inferir la localización de un usuario, pues el error asociado por el ruido ha resultado ser más de lo tolerable, y el modelado teórico del movimiento de los usuarios es difícil de acotar, con lo que los resultados obtenidos han hecho desestimar el uso de esta técnica.

Algo similar ha ocurrido con la segunda técnica estudiada, el dead reckoning. Al ser una técnica que se basa únicamente en el uso de los sensores inerciales para inferir la posición de un usuario dada una posición anterior, y teniendo en cuenta que los niveles de ruido de los sensores inerciales de los acelerómetros se consideran inadecuados para este tipo de aplicaciones, se ha decidido no implementar esta técnica.

Nos queda, por último, analizar las técnicas de clasificación comentadas en el capítulo anterior. Hemos visto tres técnicas: el perceptrón simple, las máquinas de vectores soporte y las redes de vectores soporte.

Para decidir cuál de las tres técnicas utilizar hemos tenido que apoyarnos, de nuevo, en pruebas empíricas. Ya que lo que queremos es crear una técnica de clasificación capaz de indicarnos si estamos en movimiento o en reposo, hemos tomado una serie de muestras de las salidas de los acelerómetros en movimiento y otra serie de muestras en reposo, y se han analizado los resultados. Por una parte, los conjuntos resultantes son linealmente separables, con lo que podemos descartar la técnica de redes de vectores soporte. Por otra parte, los conjuntos están muy cercanos. Tanto que la diferencia entre elegir un hiperplano que separe de forma óptima los conjuntos y escoger uno al azar no es apreciable, con lo que lo más apropiado es utilizar el perceptrón simple, cuya implementación es considerablemente más rápida y sencilla.

Una vez sabemos qué técnica vamos a utilizar, hablemos de cómo vamos a aplicarla. Hemos visto que todos los smartphones comerciales cuentan con acelerómetros, que además son de tres ejes y ofrecen, para cada eje, su aceleración instantánea. A partir de

34


dos medidas instantáneas de aceleración, si conocemos el intervalo de tiempo entre ellas, podemos calcular la velocidad del terminal en cada eje, ya que:

(3.1) v = a / t

Como lo que nos interesa es la velocidad en el plano XY para así eliminar las componentes verticales de la velocidad (por ejemplo si un usuario mueve su móvil hacia arriba sin desplazarse), hemos de calcular su proyección. Para ello necesitamos dos ángulos, el pitch y el roll, que se pueden calcular muy sencillamente con la salida de los acelerómetros de la siguiente manera:

(3.2) pitch = arcsin(acelerómetro eje Y / gravedad)

(3.3) roll = arcsin(acelerómetro eje X / gravedad)

Teniendo estos ángulos, calcular las proyecciones en el plano XY de la velocidad es un procedimiento trigonométrico básico, y teniendo las proyecciones X e Y es igualmente sencillo calcular el módulo de la velocidad.

Volviendo al diseño del perceptrón, tenemos en cada lectura de los acelerómetros la velocidad a la que se mueve el usuario en el plano XY. Como ya hemos dicho, los acelerómetros cuentan con ruido, de manera que, para aliviar su efecto, vamos a tomar una ventana con las diez últimas medidas de velocidad. Calcularemos la media y la desviación típica de estas diez medidas, y serán las dos variables que utilizaremos en el perceptrón. Por lo tanto, cuando hablemos en adelante de una muestra, haremos referencia esta media y esta desviación típica.

Identificaremos dos estados: en reposo y en movimiento. Estos son los estados que diferenciará nuestro perceptrón. Se tomarán, en la fase de aprendizaje, 150 muestras de un usuario sosteniendo el terminal de forma estática y otras 150 en movimiento, y con ellas se calculará el hiperplano que representará el perceptrón. Una vez completado este entrenamiento se ofrecerá al perceptrón la media y la desviación típica de las diez últimas muestras tomadas en el terminal, y se podrá así inferir si el usuario está en movimiento o en reposo.

Como se vio en el capítulo anterior, la ejecución del perceptrón implica una única y simple expresión matemática, con lo que no será un problema ni una carga para la potencia de cómputo de ningún smartphone.

Se ha diseñado también un pequeño filtro basado en heurísticas para suavizar ligeramente el ruido de la salida de los acelerómetros. Se basa en la idea de que la mínima variación que se recoja entre dos medidas sucesivas será muy probablemente ruido, así que podemos sustraer dicha variación a la salida de los sensores. Por ejemplo, si dos medidas consecutivas de un acelerómetro producen 0 y 0.03, ese 0.03 es probablemente ruido. Si ahora obtenemos una lectura de 0.04 restaremos ese 0.03, obteniendo 0.01. Como se ve, se alivian ligeramente las variaciones de la salida de los acelerómetros utilizando

35


muy pocos recursos y funciona especialmente bien para diferenciar situaciones estáticas de situaciones de movimiento, pues se estabiliza mucho el estado de reposo. Esta técnica se aplica de forma independiente a cada uno de los tres acelerómetros.

3.3. APOYO A LA LOCALIZACIÓN MEDIANTE VISIÓN ARTIFICIAL Procedamos ahora con aquellas técnicas vistas que explotaban la presencia de cámaras fotográficas en los smartphones, y veamos cuáles hemos incorporado en nuestro diseño y de qué manera.

La primera de ellas era la técnica SIFT, que extraía descriptores de imágenes y era capaz de ejecutar una detección de objetos y escenarios bastante robusta ante posibles variaciones del entorno, como iluminación, ángulo, etcétera. Esta gran robustez a la hora de identificar lugares es algo que sustenta muchísimo interés en nuestro ámbito de aplicación, y es por esto que se ha decidido que ha de formar parte de este diseño.

El algoritmo para extraer los descriptores SIFT de una imagen se basa en la aplicación de una pirámide gaussiana, que tiene varios parámetros variables a considerar, y que pueden influenciar considerablemente en su desempeño. Habrá que llevar a cabo un análisis empírico del algoritmo para determinar cuáles son los mejores parámetros de entrada en nuestro ámbito de aplicación, concretamente los valores del número de octavas, el índice de la primera octava y el número de niveles por octava de la pirámide gaussiana. Una vez definidos estos parámetros se podrá proceder con la fase de aprendizaje.

Como se dijo en el capítulo anterior, la infraestructura de localización existente funciona con un mapa de huellas de radiación con 94 huellas, que son los puntos en donde pueden estar los usuarios. A la hora de llevar a cabo la fase de aprendizaje de esta técnica vamos a tomar imágenes de cada uno de estos puntos, extraer sus descriptores y alojarlos en la base de datos, donde se consultarán para realizar el proceso de matching en la fase de operación. En concreto, en las zonas de pasillos se tomarán dos fotografías por cada punto, con las dos orientaciones posibles de los usuarios en los pasillos, salvo en algunos puntos concretos del mapeado en los que, por converger varios pasillos distintos, se tomarán tres. Estas imágenes tendrán un tamaño de 640x480 píxeles. En laboratorios y despachos se tomarán panorámicas con unas dimensiones de 2900x360.

Una vez determinado todo esto, solo queda hablar de la fase de operación. Durante esta fase, los móviles tomarán fotos, se extraerán los descriptores de dichas fotos y se llevará a cabo un proceso de matching con los descriptores de la base de datos. Según los autores de la técnica, el proceso de extracción de descriptores tarda entre uno y dos segundos en un procesador de 2 GHz, con lo que se desestima la posibilidad de integrar este cómputo en los smartphones, ya que el tiempo que tardaría en ejecutar la extracción sería abusivo e imposibilitaría ejecutar aplicaciones de localización en tiempo real. Así pues, el proceso de extracción de descriptores ha de llevarse a cabo en el servidor, y debe

36


estudiarse la forma de optimizarlo, por ejemplo mediante su paralelización, a fin de reducir todo lo posible su tiempo de cómputo.

Durante la fase de operación hay que tener en cuenta algunas consideraciones en el proceso de matching. Un parámetro importante es el número de coincidencias necesarias entre los descriptores de dos imágenes para considerar que se trata de imágenes tomadas en el mismo punto. Habrá que experimentar con distintos valores para escoger el que mejor se comporte.

Otro punto importante del proceso de matching es el espacio de búsqueda. Si cada vez que se toma una imagen comparamos sus descriptores con los de todas las imágenes de la base de datos gastaremos inútilmente muchos ciclos de CPU. Sería más apropiado restringir el espacio de búsqueda. Para eso podemos aprovechar un trabajo ya realizado en un proyecto anterior [37], en donde se analizaron métodos para estimar el error en la localización en interiores mediante RSSI. Se utilizó una técnica de clustering de huellas de radiación [27] que tenía como propósito informar de qué zonas del entorno de aplicación eran parecidas desde el punto de vista de las RSSI recibidas y, por lo tanto, propensas a causar errores de localización. La aplicación de esta técnica permitió distinguir cuatro zonas en las que las señales electromagnéticas se comportan de una manera similar, y se muestran en la siguiente figura:

Figura 11: Distribución de clusters

Estos cuatro clusters serán los cuatro espacios de búsqueda que utilizaremos a la hora de realizar el matching de los descriptores. En lugar de efectuar la búsqueda en todas las imágenes tomadas durante el entrenamiento utilizaremos uno o dos de estos clusters, con lo que se ahorrará tiempo de cómputo. Para decidir cuál (o cuales, pues hay zonas de intersección) es el cluster en el que se va a efectuar la búsqueda se tomará la posición estimada por el algoritmo de localización basado en RSSI.

37


Queda señalar que cada descriptor es un vector de 128 dimensiones, con lo que las búsquedas exhaustivas para llevar a cabo el proceso de matching con el algoritmo del vecino más cercano van a ser demasiado costosas, incluso habiendo reducido el tamaño del conjunto en donde se va a buscar, es por eso que será más apropiado utilizar algún algoritmo que devuelva el vecino más cercano con una gran probabilidad. Se utilizará para ello el algoritmo presentado en [5] y [6], que utiliza una búsqueda basada en el uso de árboles k-dimensionales y proporciona una búsqueda aproximada del vecino más cercano mucho más rápida que la búsqueda exhaustiva.

Otra de las técnicas de procesamiento de imágenes vistas en el capítulo anterior es el operador de Sobel, muy útil a la hora de decirnos si una imagen es borrosa o no. Se trata de una técnica muy ligera computacionalmente hablando, de manera que podremos incluirla en los propios smartphones. Gracias al operador Sobel podremos llevar a cabo un rápido procesamiento de la imagen y, si se considera que es demasiado borrosa, la desecharemos, evitando así su transmisión y posterior extracción de descriptores, ahorrando así tiempo y recursos.

El operador Sobel ofrece para cada píxel un gradiente que nos aporta mucha información sobre la dirección del incremento del brillo, por ejemplo. En nuestro ámbito de aplicación no nos interesa tanto toda esta información que nos ofrece, sino únicamente contar con un valor que nos permita estimar si la imagen es aprovechable o no. Teniendo esto en mente vamos a modificar ligeramente las ecuaciones del cálculo del gradiente vistas en el capítulo anterior por versiones que no utilizan operaciones en punto flotante, para así hacer la técnica todavía más eficiente. Así, en lugar de la siguiente expresión:

(3.4) : � @:;A � :?A

Utilizaremos ésta otra: (3.5) : � |:;| � |:?| Se perderá así toda la información asociada a los gradientes, que no nos interesa, pero se conservará la relación entre el valor obtenido y la bondad de la imagen.

Para determinar el umbral del gradiente a partir del cual se considera que una imagen es válida se propone utilizar un procedimiento empírico calculando el gradiente de una serie de imágenes, algunas borrosas y otras no, y determinar el valor a partir del cual se obtiene un número significativo de descriptores de las imágenes.

La implementación de la técnica de los ferns también resulta interesante, pues parece ofrecer buenos resultados y tiene unos requerimientos computacionales muy moderados, que pueden ser aptos para su ejecución en los propios smartphones. Se deja, por ello, su implementación como un posible trabajo futuro siguiendo la línea de este proyecto.

38


3.4. BALANCEO DE CARGA ENTRE CLIENTE Y SERVIDOR Una vez hemos analizado toda esta serie de técnicas y hemos comentado la potencia de cálculo que requiere cada una de ellas, se llega a la conclusión de que no será posible ejecutarlas todas en los propios smartphones,. Esta razón implica que se requiera un balanceo de carga de la funcionalidad del sistema entre los terminales móviles y el propio servidor.

Lo ideal es que las técnicas se implementen en el propio smartphone, de manera que cuando la información salga de él los datos de los sensores ya se encuentren procesados y listos para alojarse en la base de datos. Únicamente enviaremos los datos sin procesar cuando no sea posible la otra alternativa.

La primera técnica que hemos visto de las que vamos a incorporar es la del perceptrón simple. Esta técnica transforma la salida de los acelerómetros en una abstracción del modelo del movimiento de los usuarios. Concretamente, traduce los datos de estos sensores inerciales a uno de los dos estados, “en reposo” o “en movimiento”. Ya se comentó que la implementación de esta técnica implica la ejecución de una única expresión matemática, con lo que es muy ligera y no habrá problema alguno en integrarla en el terminal. Además, al ejecutarla en el terminal se obtienen ventajas. Se puede aprovechar la nueva representación del movimiento del usuario para evitar que el móvil envíe información cuando se encuentra en reposo, ya que su localización no habrá cambiado y será inútil recalcularla, con el ahorro energético que esto implica. Otra ventaja directa es que la información procesada (es decir, la clase en la que se categoriza el movimiento del usuario) ocupa mucho menos espacio que todas las salidas de los acelerómetros, así que ahorraremos también en transmisiones, ahorrando batería y recursos de red.

En cuanto a la técnica SIFT de procesamiento de imágenes, se encarga de tomar una imagen como entrada y proporcionar sus descriptores como salida. Como ya dijimos, esta técnica es muy costosa en recursos computacionales, con lo que su inclusión en el dispositivo móvil queda descartada. Será necesario, por lo tanto, enviar la imagen sin procesar al servidor, que será el encargado que lanzar la extracción de descriptores y alojarlos en la base de datos.

La última técnica que hemos visto, la del operador Sobel, no ofrece como salida información que resulte útil para la localización en sí, sino para desechar imágenes que resultan demasiado borrosas para que sean aprovechables. Si desarrollásemos esta técnica en el servidor podríamos evitar extraer los descriptores SIFT de las imágenes borrosas, pero resulta más beneficioso hacerlo en el terminal para ahorrar, además, la transmisión inalámbrica de la imagen. Como se vio en su correspondiente sección, la técnica es ligera y, además, se ha diseñado una versión aún más liviana que evita las operaciones en punto flotante. Por todo esto queda claro que se obtendrán mayores beneficios al incluirla en el smartphone.

39


4. IMPLEMENTACIÓN

4.1. ASPECTOS DE IMPLEMENTACIÓN DE LA ARQUITECTURA EN EL CLIENTE Para llevar a cabo la implementación de la aplicación cliente y para su posterior experimentación para la extracción de resultados se ha contado con dos dispositivos móviles: HTC Desire y HTC Legend. Estos smartphones funcionan bajo la plataforma Android.

Las características principales de desarrollo en Android son que cuenta con una SDK de libre distribución, con lo que cualquiera puede descargarla y desarrollar aplicaciones que funcionen en este sistema operativo, lo que implica también una gran comunidad de usuarios online. También es destacable que todo el código desarrollado para Android debe estar escrito en Java, al igual que las librerías proporcionadas para desarrolladores. Es por esto que toda la funcionalidad del cliente (la extracción de datos de los sensores, su procesamiento cuando corresponda y el envío al servidor) estará expresada en dicho lenguaje de programación.

Una implicación importante que surge a raíz de utilizar Android como plataforma en los terminales es la limitación a la hora de llevar a cabo comunicaciones que este sistema operativo impone. En concreto, en Android únicamente podemos comunicarnos por un conjunto limitado de protocolos, como HTTP, RTP o SIP, y no se nos permite en ningún caso abrir sockets directamente para diseñar nuestros propios protocolos. Esta es una razón importante por la cual las comunicaciones entre cliente y servidor se van a realizar utilizando REST, que es un protocolo cliente/servidor sin estado que viaja sobre HTTP, haciendo uso de sus métodos (GET, POST…) que permite desarrollar aplicaciones muy fácilmente extensibles. Para transportar la información de los sensores se utilizará la especificación JSON [24]. El diseño de estos objetos JSON y de las comunicaciones en general entre cliente y servidor queda fuera del alcance de este trabajo, entrando en el ámbito de otro proyecto cuyo desarrollo se ha producido en paralelo a éste.

Se enumeran a continuación algunas otras cuestiones relevantes de la implementación de la aplicación del cliente:

1.- La aplicación se ha intentado paralelizar todo lo posible a fin de ahorrar tiempo de ejecución. Por una parte, los diferentes sensores de los que se recopilan datos a lo largo del flujo de ejecución pueden ser accedidos de forma paralela. Por otra parte, los envíos de los datos de los distintos sensores, que se realizarán vía REST mediante métodos POST HTTP independientes, también se harán de forma paralela, mediante diferentes threads.

2.- Se han probado dos métodos para capturar las imágenes. El primero de ellos consiste en una toma fotográfica regular, mientras que el segundo consiste en extraer un frame del preview que ofrecen las aplicaciones móviles que hacen uso de la cámara.

40


En ambos casos, para conseguir una imagen definida, hay que invocar al autofocus antes de tomarla. Se ha optado finalmente por tomar un frame del preview dado que es un proceso más rápido y no implica pérdida de calidad.

3.- La aplicación del cliente debe seguir funcionando en segundo plano cuando se salga de ella, salvo que el usuario indique lo contrario de forma explícita. Hay que tener en cuenta en este punto que Android no permite el uso de la cámara en segundo plano, con lo que en este caso solo podremos hacer uso de la RSSI para el proceso de localización y de los acelerómetros para evitar envíos cuando el usuario no se encuentra en movimiento.

4.2. APOYO A LA LOCALIZACIÓN MEDIANTE SENSORES INERCIALES La única técnica que se ha implementado de cara a aprovechar los sensores inerciales de los smartphones, como se vio en el capítulo anterior, ha sido la del perceptrón simple. Como es lógico, se ha implementado íntegramente en Java, dado que se encuentra integrada en la aplicación para los smartphones. Cuando se comentó su diseño se vio que había algunas otras consideraciones de implementación abiertas, que deberían llevarse a cabo mediante experimentación.

Como comentamos, se tomará la salida de los acelerómetros de los dispositivos, evento que en nuestro caso ocurre cinco veces por segundo. En cada muestreo se calculará la proyección de la velocidad del usuario en el plano XY, y se tomará una ventana con las diez últimas velocidades recogidas, calculando la media y la desviación típica del conjunto. Esta media y esta desviación típica será cada muestra que se proporcione al perceptrón, tanto durante su fase entrenamiento como durante su fase de operación, en la que se intentará inferir si el usuario está estático o en movimiento.

La fase de entrenamiento consiste en capturar muestras de entrenamiento para cada una de las dos clases de movimiento, concretamente 150 muestras estáticas, con el teléfono sujeto sin desplazarse, y 150 muestras en las que el usuario se desplazaba por el entorno.

Una vez capturadas estas 300 muestras (cada una de ellas formada por la media y la varianza de las diez últimas velocidades instantáneas), se han utilizado para entrenar al perceptrón. Este proceso se ha realizado dos veces, utilizando dos patrones de movimiento diferentes. Se muestran los dos perceptrones conseguidos junto con las muestras tomadas:

41


Figura 12: Clasificación utilizando dos conjuntos de muestras diferentes

El perceptrón de la izquierda, como se ve, utilizó un patrón de movimiento que asumía movimientos más rápidos en el usuario, mientras que los del perceptrón de la derecha fueron más lentos, de ahí que su media y su desviación típica sean menores.

Una vez probados ambos perceptrones en el entorno de aplicación se ha llegado a la conclusión de que el que ofrece mejores resultados es el de la derecha, ya que el otro perceptrón, al haber sido entrenado con movimientos más rápidos, falla en ocasiones al realizar el usuario desplazamientos más lentos.

4.3. APOYO A LA LOCALIZACIÓN MEDIANTE VISIÓN ARTIFICIAL Veremos en esta sección los detalles a nivel de implementación que resulta relevante comentar sobre las técnicas utilizadas de apoyo a la localización mediante visión artificial, en concreto SIFT y el operador Sobel.

Para implementar la primera de ellas, la técnica de extracción de descriptores SIFT, se ha utilizado una librería ya codificada, la librería SIFTGPU [50], que cuenta con implementaciones tanto en GLSL (OpenGL Shading Language) como en CUDA (Compute Unified Device Architecture) de la técnica SIFT. Esta librería requiere, para su correcto funcionamiento, la presencia de una tarjeta con un procesador gráfico dedicado. Se ha utilizado para ello una nVidia GeForce 9800GT, que soporta tanto GLSL como CUDA, y ha sido instalada en un Intel(R) Pentium(R) Dual-Core CPU E2160, que ejerce de servidor de localización. La librería SIFTGPU se encuentra escrita en C++, con lo que para utilizarla sin problemas de compatibilidad se va a escribir en este lenguaje de programación la aplicación que la invoca.

Como se comentó en el capítulo de diseño, había que determinar algunos parámetros de entrada para el algoritmo de extracción de descriptores SIFT. En concreto queríamos determinar el número de octavas, el índice de la primera octava y el número de niveles por octava. Después de probar diferentes valores se ha determinado que los mejores valores para nuestro entorno son 5 octavas, la primera de ellas igual a 0, y 5 niveles por octava.

42


También necesitamos decidir cuál implementación utilizar de las dos ofrecidas por la librería SIFTGPU. Tras probar ambas hemos comprobado que la primera de ellas, la implementación en GLSL, tarda aproximadamente un segundo de media en extraer los descriptores de una imagen de 640x480 píxeles. Por su parte, la versión en CUDA tarda menos de 100 milisegundos de media en realizar el mismo procedimiento. Queda claro, pues, que se utilizará la versión en CUDA.

Para llevar a cabo el método de búsqueda se utilizará también una librería ya implementada, llamada ANN (Approximate Nearest Neighbour) [32], utilizando la versión de árboles k-dimensionales. Como esta librería es de uso general, se modificará para poder indexar imágenes.

La otra técnica que hemos utilizado es la del operador Sobel. Esta técnica está integrada en el código de la aplicación del dispositivo móvil, por lo que su implementación ha sido realizada en Java.

4.4. VISIÓN GLOBAL DEL FUNCIONAMIENTO DEL SISTEMA Hemos visto ya con bastante grado de detalle, tanto en el capítulo de diseño como en éste, cómo se van a comportar cada uno de los elementos del sistema, pero lo hemos analizado de una manera aislada, comentando y acotando las responsabilidades de cada módulo.

Sería muy conveniente, pues, ver una abstracción del funcionamiento global del sistema, desde que un smartphone envía los datos recabados por sus diferentes sensores hasta que una aplicación solicita la ubicación de dicho dispositivo. Nótese que, según el entorno de aplicación, la aplicación de localización puede estar o no integrada en el propio dispositivo móvil. Habrá entornos en los que un usuario quiera conocer su propia posición, y otros en los que será alguna entidad externa (por ejemplo, una empresa que quiere saber dónde se encuentran sus trabajadores). Es por esto que, conceptualmente, tenemos que separar estas dos funciones.

Esta visión global del comportamiento del sistema se detalla en la Figura 13. En ella vemos un diagrama con las diferentes entidades que participan en el proceso de localización. En el smartphone se expresa el flujo de ejecución mostrado anteriormente en la Figura 10. Se han intentado explicitar en el diagrama todos aquellos eventos que ocurren de forma paralela. En concreto la toma de los sensores, ya que la RSSI y las imágenes se capturan de forma independiente, y los envíos al servidor, que se ejecutan en diferentes threads. Una vez acaba el ciclo de envío de los sensores, el smartphone procede a monitorizar el acelerómetro y a ejecutar el algoritmo del perceptrón hasta que el usuario se encuentre en movimiento o expire un timeout, momento en el cual se relanzará todo el proceso.

43


SmartphoneLocation

Server

Sensor Manager

Server

Location

AppDataBase

getRSSI getImage

Sobel operator

send RSSI

send Image

send Acc

send RSSI

send Acc

SIFT

send Descriptors

getAcc

perceptron

WHILE not motion or not timeout

get user Location

get user RSSI

get user Acc

get user Descriptors

Location algorithm

send user Location

get RSSI fingerprints

get SIFT descriptors

Figura 13: Funcionamiento global de la localización con fusión de sensores

Una vez alojada la información de los sensores en la base de datos, cuando una aplicación quiera conocer la posición de determinado usuario se la pedirá al servidor. Éste deberá solicitar a la base de datos la información de las huellas de radiación para ejecutar el algoritmo de localización, así como los descriptores SIFT para ejecutar el algoritmo de matching, y una vez cargados en memoria no será necesario volver a solicitarlos. Se solicita también la información de los sensores y, en ese momento, está en situación de proporcionar la localización del usuario a la aplicación que la solicitó.

Nótese que en el diagrama se asume que el uso del operador Sobel determina que la imagen es útil para su procesamiento. De no ser así, el diagrama permanecería prácticamente igual, pero sin la transmisión de la imagen ni, lógicamente, su posterior procesamiento.

44


5. VALIDACIÓN Y PRUEBAS REALIZADAS Hemos visto hasta ahora el proceso de análisis de alternativas, diseño de la solución y aspectos de implementación. No obstante, aún falta validar este sistema de localización multisensor, y para ello es necesario demostrar tanto su precisión como su desempeño, mostrando para ello varias pruebas realizadas en el entorno de aplicación, tanto de usuarios estáticos como en movimiento.

Si recordamos el mapa visto en la Figura 1, las pruebas estáticas se han realizado en el punto 63, mientras que las pruebas en movimiento se han llevado a cabo siguiendo el camino que va desde el punto 33 hasta el 49, posteriormente hasta el 50 y, por último, hasta el 60. Todo el proceso se ha ejecutado con tres variantes: usando únicamente la RSSI, usando la RSSI con el apoyo de los acelerómetros y usando todos los sensores en conjunto (WiFi, acelerómetros y cámara). Los resultados se muestran en la figura siguiente:

Figura 14: Precisión de la localización para varias combinaciones de sensores

Como vemos, los acelerómetros tal y como los utilizamos no aportan beneficios a la hora de disminuir el error, pues están concebidos en este diseño para ahorrar batería en los smartphones. Incluso en el caso de que el usuario se encuentre estático perdemos un poco de precisión. Esto ocurre porque, al no moverse el usuario, se envían menos muestras al servidor de localización, con lo que tiene menos información para inferir la posición del usuario. En cualquier caso, el error sigue estando por debajo del metro y medio.

Es más que reseñable el caso de apoyarnos en el uso de imágenes. Gracias al desempeño de la técnica de los descriptores SIFT conseguimos disminuir el error medio de localización hasta 0.2 y 0.62 metros, cuando el usuario está estático y cuando se mueve, respectivamente.

Queda analizar el rendimiento de la solución. Veamos para ello la siguiente figura:

45


Figura 15: Latencia temporal del proceso de localización

Se aprecia que el uso de imágenes tiene un importante impacto en el tiempo en que se tarda en llevar a cabo todo el proceso de localización, y llega a ser el triple del que nos tomaba calcular la posición de un usuario únicamente mediante RSSI.

La principal causa de este retardo es la toma de los datos de los sensores, especialmente de la imagen, ya que el procedimiento de enfoque de la cámara puede ser lento, llegando a tardar hasta un segundo y medio (nótese en la figura que el primer segundo se ejecuta en paralelo a la toma de la RSSI). Se espera que los tiempos de captura de sensores se mejoren en futuras mejoras tanto de los smartphones como de sus sistemas operativos. También influyen las transmisiones inalámbricas, llegando a tomar el envío de la imagen de 700 milisegundos de media. El cálculo del gradiente y el cálculo de descriptores SIFT implican cada uno, aproximadamente, 200 milisegundos, y el proceso de matching unos 160 milisegundos cuando el usuario está estático y unos 260 cuando se encuentra en movimiento, ya que se analizan más imágenes en ese caso.

Tras analizar estos resultados podemos afirmar que esta propuesta permite llevar a cabo una localización muy precisa, con una duración que, si bien puede no ser aceptable en las aplicaciones más exigentes de localización en tiempo real, es más que suficiente para la mayoría de entornos. Estos buenos resultados han motivado la redacción de un artículo de investigación pendiente de publicación [39].

46


6. CONCLUSIONES Y VÍAS FUTURAS

6.1. CONCLUSIONES A lo largo de la realización de este proyecto se ha trabajado con una serie de sensores de muy distinta índole, analizando en cada caso técnicas cuyo despliegue podría implicar una mejora en la eficiencia y prestaciones de un sistema de localización funcional que hasta ahora utilizaba técnicas basadas únicamente en RSSI. Tanto los sensores como las técnicas estudiadas han sido de tipos muy heterogéneos, lo cual ha dado lugar a un conocimiento amplio y variado.

Al analizar el estado del arte hemos estudiado algunas soluciones a nivel de investigación, que trabajaban con la idea de aplicar sensores a sistemas de localización desde diferentes puntos de vista. Estas soluciones, sin embargo, no eran lo suficientemente buenas, ya sea porque tardaban demasiado tiempo en llevar a cabo la localización, porque implicaban demasiados cambios en el entorno de explotación o porque no ofrecían una precisión mayor de la que ofrecen los métodos basados en RSSI por sí solos. Todo esto nos lleva a concluir que este ámbito de aplicación aporta una innovación importante y que suscita mucho interés desarrollar soluciones aplicables en entornos reales, para lo cual es necesario mejorar los resultados existentes.

Después de haber trabajado con smartphones se ha llegado a la conclusión de que se trata de dispositivos muy potentes para su reducido tamaño, pero que innegablemente están limitados. Es por esto que, pese a que lo ideal sería realizar todo el procesamiento dentro de ellos, hay algunos casos en los que, por la gran carga computacional que implican los algoritmos utilizados, no queda más remedio que ejecutarlos fuera del smartphone. De ahí que el balanceo de carga entre smartphone y servidor de localización haya sido un punto importante que estudiar.

Otra característica de los terminales inteligentes es la presencia de sensores en éstos. Tras experimentar con los distintos sensores, más en concreto con los inerciales, se ha llegado a la conclusión de que su calidad no es la suficiente como para ofrecer una estimación de movimiento que nos resulte útil para propósitos de localización, sino que están pensados para fines más modestos, como por ejemplo medir la inclinación del dispositivo o para diferenciar entre estados estáticos y en movimiento.

Tras haber realizado las pruebas pertinentes del sistema se ha comprobado que el uso de imágenes implica un alto coste computacional, y se deben orientar esfuerzos a aliviarlo, de manera que se consiga la misma precisión que hasta ahora en un sistema apto para su uso en tiempo real.

6.2. TRABAJO FUTURO Si bien, como hemos visto, se han conseguido unos resultados bastante buenos durante la realización de este trabajo, resulta interesante mejorarlos aún más, comparando las

47


técnicas utilizadas con otras de la misma índole, a fin de reducir todo lo posible el error medio, pero sobre todo el tiempo de localización.

Se debe, por ejemplo, comparar la búsqueda mediante árboles k-dimensionales que se utiliza en este momento para realizar el matching de descriptores con otras propuestas similares, como [4], [9], o [33].

No solo se puede ahorrar tiempo en el proceso de búsqueda, sino también en el proceso de extracción de descriptores SIFT. En [46] se propone una solución que extrae una cantidad menor de features de las imágenes, con lo que también el proceso de matching será más rápido.

También se ha de estudiar la implementación en los smartphones de la técnica de los ferns, capaz de llevar a cabo un buen reconocimiento de objetos y escenas utilizando pocos recursos computacionales.

Otro tipo de líneas de trabajo futuro pueden ser la creación de clientes para otras plataformas móviles, desarrollo de aplicaciones móviles de realidad aumentada basadas en la localización e inclusión de seguridad en la infraestructura (control de acceso a los servicios, cifrado de comunicaciones, etcétera).

48


REFERENCIAS

[1] AeroScout. http://aeroscout.com/

[2] Android, http://www.android.com/

[3] Apple, http://www.apple.com/

[4] S. Ajioka, S. Tsuge, M. Shishibori, and K. Kita. Fastmultidimensional nearest neighbor search algorithm using priority queues. Electrical Engineering in Japan, 164(3):69–77, 2008.

[5] S. Arya and D. M. Mount. Approximate nearest neighbor queries in fixed dimensions. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 1993.

[6] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In ACM-SIAM Symposium on Discrete Algorithms, pages 573–582, 1994.

[7] M. Azizyan, I. Constandache, R. R. Choudhury. SurroundSense: Mobile Phone Localization via Ambience Fingerprinting, In Proc. MOBICOM 2009, pages 261–272, Beijing, China, September 2009.

[8] P. Bahl and V. N. Padmanabhan. RADAR: An In-Building RF-based User Location and Tracking System. In Proc. INFOCOM 2000, pages 775–784, Tel Aviv, Israel, March 2000.

[9] J. Beis and D. G. Lowe. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In Proc. CVPR 1997, pages 1000–1006, Puerto Rico, June 1997. IEEE Computer Society.

[10] BlackBerry, http://www.blackberry.com/

[11] H. D. Block. The perceptron: a model for brain functioning. I, pp. 135–150. MIT Press, Cambridge, MA, USA, 1988.

[12] G. Chandrasekaran, M. A. Ergin, J. Yang, S. Liu, Y. Chen, M. Gruteser, and R. P. Martin. Empirical Evaluation of the Limits on Localization Using Signal Strength. In Proc. SECON 2009, pages 333–341, Rome, Italy, June 2009.

[13] Cisco Systems. Wi-Fi Location-Based Services - Design and Deployment considerations, 2006.

[14] C. Cortes and V. Vapnik. Support-vector networks. In Machine Learning, pages 273–297, 1995.

[15] Ekahau. http://ekahau.com/

49


[16] E. R. Fossum, CMOS image sensors: electronic camera-on-a-chip. In IEEE Transactions on Electron Devices, pages 1689–1698, 1997.

[17] M.A. Fischler, R.C. Bolles, Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. In Communications of the ACM, pages 381-395, 1981.

[18] Google Phone, http://www.google.com/phone

[19] K. Hattori, R. Kimura, N. Nakajima, T. Fujii, Y. Kado, B. Zhang, T. Hazugawa, and K. Takadama. Hybrid indoor location estimation system using image processing and wifi strength. In Proc. WNIS 2009, pages 406–411, Shanghai, China, 2009. IEEE Computer Society.

[20] J. Hightower. The location stack: A layered model for location in ubiquitous computing. In Proc. WMCSA 2002, pages 22–28, Callicoon, NY, USA, 2002. IEEE Computer Society Press.

[21] H. Hile and G. Borriello. Positioning and orientation in indoor environments using camera phones. IEEE Comput. Graph. Appl., 28:32–39, July 2008.

[22] HTC, http://www.htc.com/

[23] IEEE Std 802.11. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1999.

[24] JavaScript Object Notation, http://www.json.org/

[25] T. King, T. Haenselmann, S. Kopf, and W. Effelsberg. Overhearing the wireless interface for 802.11-based positioning systems. In Proc. PERCOM 2007, pages 145–150, White Plains, NY, USA, 2007. IEEE Computer Society.

[26] K. Konolige and K. Chou. Markov Localization using Correlation. In Proc. IJCAI 1999, pages 1154–1159, Stockholm, Sweden, 1999. Morgan Kaufmann Publishers Inc.

[27] H. Lemelson, M. B. Kjaergaard, R. Hansen, and T. King. Error Estimation for Indoor 802.11 Location Fingerprinting. In Proc. LoCA 2009, pages 138–155, Tokyo, Japan, May 2009.

[28] V. Lepetit, P. Fua. Keypoint Recognition using Randomized Trees. In IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1465-1479, 2006.

[29] S. Liang. Java Native Interface: Programmer's Guide and Specification, 1999.

[30] D. G. Lowe. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, Volume 60, pages 91–110, 2004.

50


[31] D. G. Lowe. Object Recognition from Local Scale-Invariant Features. In Proc. ICCV 1999, pages 1150–1157, Kerkyra, Greece, September 1999. IEEE Computer Society.

[32] D. M. Mount and S. Arya. Ann a library for approximate nearest neighbor searching. In Proc. Center for Geometric Computing Second Annual Fall Workshop Computational Geometry, 1997.

[33] M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In Proc. VISAPP 2009, pages 331–340, Lisboa, Portugal, February 2009.

[34] M. Özuysal, M. Calonder, V. Lepetit, P. Fua. Fast Keypoint Recognition using Random Ferns. In IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 448-461, 2009.

[35] M. Özuysal, P. Fua, V. Lepetit. Fast Keypoint Recognition in Ten Lines of Code. In IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8, 2007.

[36] C. Randell, C. Djiallis, H. Muller. Personal position measurement using dead reckoning, In Proc. Seventh IEEE International Symposium on Wearable Computers, pages 166-175, 2003.

[37] R. A. Rubio. Desarrollo de un sistema de localización basado en WLAN y dispositivos embebidos de pequeño tamaño, Proyecto Fin de Carrera, Universidad de Murcia, 2010.

[38] A. J. Ruiz, O. Cánovas. Integrating probabilistic techniques for indoor localization of heterogeneous clients, 2011 (Pendiente de publicación).

[39] A. J. Ruiz. O. Cánovas, R. A. Rubio, P. E. López de Teruel. Indoor localization of smartphones assisted by WiFi signals and scale invariant features from images, 2011 (Pendiente de publicación).

[40] Samsung, http://www.samsung.com/

[41] I. Sobel. Neighbourhood coding of binary images fast contour following and general array binary processing, In Computer Graphics and Image Processing, pages 127–135, 1978.

[42] E. G. Stevens. Charge-coupled device (CCD) image sensor operable in either interlace or non-interlace mode, 1992.

[43] G. Stevenson, J. Ye, S. Dobson, and P. Nixon. Loc8: A location model and extensible framework for programming with location. IEEE Pervasive Computing, 9:28–37, January 2010.

[44] Symbian, http://symbian.nokia.com/

[45] S. Thrun, W. Burgard, D. Fox. Gaussian filters. Probabilistic Robotics, MIT Press, 2005.

51


[46] P. Turcot and D. Lowe. Better matching with fewer features: The selection of useful features in large database recognition problems. In Proc. ICCV 2009, Kyoto, Japan, September 2009.

[47] V.N. Vapnik. Statistical Learning Theory, 1998.

[48] A. Varshavsky, S. Patel. Location in ubiquitous computing, Ubiquitous computing fundamentals, pages 285-320, 2009.

[49] Windows Phone, http://www.microsoft.com/windowsphone/

[50] C. Wu, SiftGPU: A GPU Implementation of Scale Invariant Feature Transform (SIFT), http://www.cs.unc.edu/~ccwu/siftgpu/

Integración de dispositivos Android y uso de sensores en ...

Documents

Transcript of Integración de dispositivos Android y uso de sensores en ...