La réalité augmentée géolocalisée, les enjeux de la navigation depuis le navigateur web
Nous avons commencé une série de billets de blog sur les défis de la construction d’un navigateur du monde réel, au niveau technique bien sûr, mais aussi en termes d’interface homme-machine, de données, etc.
Nous y parlons de capteurs mobiles, de cartes, de l’apprentissage machine et de bases de données, de développement web et mobiles, d’orientation et de systèmes de positionnement, de bâtiments et de villes et de bien plus encore :)
Pour continuer, nous allons parler des enjeux techniques du système de géolocalisation hybride que nous avons mis en place pour réaliser de la réalité augmentée géolocalisée (Geo AR). Nous expliquerons ici comment notre système utilise la fusion de données provenant des capteurs du téléphone mais aussi la cartographie.
Pour rappel, afin de réaliser de la Geo AR, l’approche la plus répandue consiste à associer des données provenant : (1) du GNSS (GPS, GLONASS, Galileo…) et (2) de la centrale inertielle (accéléromètre, gyroscope, magnétomètre). Le GNSS permet de connaître la position du téléphone alors que la centrale inertielle permet d’estimer l’orientation du téléphone (nord, est, haut, bas…). La combinaison de la position et de l’orientation est appelée géo-pose.
Notre précédent blog post a fait l’objet d’une étude poussée sur la fusion des capteurs de la centrale inertielle afin d’obtenir une bonne orientation du téléphone dans un navigateur web, vous pouvez le relire ici. Dans ce nouveau blog post nous allons nous focaliser sur l’estimation de la seconde composante de la géo-pose : la position du smartphone.
Comment fonctionne l’estimation de la position d’un smartphone ?
Depuis une dizaine d’années, on a pu voir naître de nombreuses applications qui utilisent la géolocalisation (cartes interactives, publicité ciblée, informations locales…). Comment cette position est-elle calculée ? Et comment pouvons nous l’utiliser pour faire de la Geo AR ? Nous tentons d’y répondre.
La position du smartphone
La position d’un smartphone est toujours considérée par rapport à un repère bien défini, celui que nous utilisons pour nos cartes et la Geo AR est le repère terrestre. Dans la majorité des cas, une position sur le repère terrestre est définie par le système géodésique WGS84 (latitude, longitude, altitude). Par exemple la position de Paris est définie par {latitude=48.85°, longitude=2.34°, altitude=35m}. Pour la suite, nous appellerons une position définie sur le repère terrestre, une position absolue. La position absolue du smartphone peut facilement être récupérée si celui-ci est équipé d’un capteur de navigation par satellites, Global Navigation Satellite System (GNSS) en anglais.
Le positionnement par GNSS et ses limites
En fonction du capteur GNSS embarqué dans le smartphone, celui-ci est capable de recevoir les signaux de différentes constellations de satellites : GPS (américain), GLONASS (russe), BeiDou (chinois) et Galileo (européen). Ces signaux sont processés par le téléphone puis un algorithme de trilatération en déduit une position absolue. C’est le temps de propagation des ondes radios entre le satellite et le smartphone qui est utilisé pour reconstruire la position.
Les données provenant du GNSS peuvent être de bonne qualité (< 5 mètres) quand le dispositif se trouve dans un espace dégagé (un champ, une plage…). Si l’onde radio entre le satellite et le téléphone est obstruée ou déviée par un objet (bâtiment, falaise…), l’estimation de la position est altérée. Par exemple, en ville on peut facilement se retrouver avec une précision moyenne autour de 15 mètres.
À l’intérieur d’un bâtiment, l’utilisation du GNSS devient presque impossible. L’utilisateur peut recevoir des signaux quand il est proche d’une fenêtre mais plus rien dès qu’il s’en éloigne. Il faut donc trouver d’autres moyens de positionner le dispositif quand l’utilisateur est en intérieur.
Les autres techniques de positionnement
Dans cet article, l’objectif n’est pas de décrire en détail toutes les techniques de géolocalisation existantes mais seulement de présenter certaines d’entre elles utiles pour la Geo AR. Si vous souhaitez rentrer dans les détails du sujet, je vous recommande de vous référer à ce document.
À ce jour, le GNSS est la seule approche qui permet de se géolocaliser sur toute la planète. Il existe cependant d’autres systèmes de géolocalisation qui couvrent des surfaces bien plus petites. Ils ont notamment été créés pour géolocaliser des objets là où les signaux GNSS ne peuvent être reçus. Par exemple, les routeurs WiFi et les beacons bluetooth sont des dispositifs qui émettent constamment des signaux radios, ils peuvent être utilisés pour déterminer la position du smartphone. Notamment, Google les utilise (en complément du GNSS) pour la localisation sur Android. Dans la littérature, on observe une précision de ces approches autour de 5–7 mètres.
Leur fiabilité dépend surtout de la densité des balises installées et de l’environnement dans lequel elles fonctionnent (hall, couloirs, multi-étages…).
Généralement, ces systèmes “locaux” renvoient des positions définies sur un repère choisi par l’installateur. L’installateur définit un point d’origine ainsi qu’une orientation, puis, toutes les positions renvoyées sont relatives à ce point d’origine, par exemple {x = 53.2m, y = 18.9m, z = 1.5m}. L’avantage de ce type de système est que lorsque la position et l’orientation d’un seul des points du repère sont connus dans le repère terrestre (étape appelée géo-référencement), le système est capable d’estimer toutes les futures positions dans le repère terrestre. Nous appelons ce type de système de positionnement : absolu indirect.
Les spécificités du positionnement pour l’AR
Jusqu’à aujourd’hui, les systèmes de géolocalisation ont majoritairement été conçus pour visualiser la position de l’utilisateur sur une carte 2D. La position est souvent représentée par un point bleu et un cercle de confiance qui correspond à l’incertitude du calcul. En utilisant les systèmes décrits précédemment, c’est à dire une précision de positionnement moyenne de 5 à 15 mètres, l‘utilisateur arrive rapidement à se repérer sur une carte. Le cercle de confiance est un élément au moins aussi important que le point bleu, car il permet à l’utilisateur de compenser théoriquement une éventuelle erreur du système de positionnement.
Intéressons nous maintenant au positionnement en Geo AR. Pour rappel, le principe est de proposer du contenu virtuel (dans un moteur de rendu 3D) qui vient en surimpression au contenu réel (le flux vidéo de la caméra). Afin que l’immersion soit totale, tout l’enjeu de cette approche consiste à estimer le plus précisément possible la géo-pose de la caméra pour que le contenu virtuel et le flux vidéo ne fassent qu’un à l’écran.
Voici deux points qui font que cet enjeu est d’autant plus important en AR qu’en vue carte 2D :
- À la différence d’une carte 2D et son cercle de confiance, en AR il n’y a pas de manière de visualiser l’imprécision grâce à un élément d’UI. La géo-pose estimée par le moteur de positionnement est directement celle utilisée par le moteur de rendu. Une erreur de quelques mètres ou quelques degrés dans le système de positionnement pourrait avoir comme conséquence une grande imprécision au niveau de l’environnement virtuel : des objets décalés, des données manquantes, un chemin qui rentre dans un mur… L’utilisateur pourrait alors manquer l’information qu’il est venu chercher en utilisant l’AR.
- Le second point concerne la faible fréquence des mises à jour des positions. Typiquement, une position provenant d’un des systèmes absolus décrit ci-dessus est reçue toutes les 3 secondes, ce qui correspond à une mise à jour de la position dans la scène virtuelle toutes les 3 secondes aussi. Sur une carte 2D, un petit saut de position toutes les 3 secondes ne pose pas trop de problème de visualisation; cependant, en Geo AR, on a besoin d’une bien plus grande fréquence pour que l’expérience soit fluide et immersive.
C’est à ce moment là que les systèmes de positionnement relatif vont devenir d’une grande aide pour la Geo AR. Un système de positionnement relatif est une méthode de navigation qui consiste à estimer une nouvelle position à partir de sa dernière position connue et des données renvoyées par les capteurs. Ces systèmes sont à la fois précis et fluides mais ne sont d’aucune utilité pour la navigation s’ils fonctionnent seuls, c’est pour cela qu’ils doivent à minima être couplé à un système de positionnement absolu.
Le système le plus courant est la navigation à l’estime pour piéton, ou Pedestrian Dead Reckoning (PDR) en anglais. Son fonctionnement consiste à associer les données provenant d’un podomètre (détection de pas + taille du pas) et d’un magnétomètre (boussole) afin de reconstruire le parcours du dispositif. Par exemple : {un pas de 75cm, à 28° nord}, 500ms plus tard : {un pas de 73cm, à 26° nord} …
Il existe un second système de positionnement relatif qui est de plus en plus utilisé par nos smartphones, c’est l’odométrie visuelle avec centrale inertielle ou Visual Inertial Odometry (VIO) en anglais. Le dispositif calcule une nouvelle position grâce au flux vidéo de la caméra, à l’accéléromètre et au gyroscope. On retrouve ce type d’algorithmes dans des librairies sur étagère comme ArCore (Google) et ArKit (Apple).
Le PDR permet d’obtenir une nouvelle position à chaque nouveau pas, c’est à dire environ 2Hz. Pour le VIO, le taux de rafraîchissement est encore plus élevé, une nouvelle position est estimée à 30Hz environ.
La fusion des systèmes de positionnement relatif et absolu devient alors très intéressante. Cela permet, d’une part, d’avoir une mise à jour des positions beaucoup plus fréquemment que le positionnement absolu seul, et d’autre part, d’isoler les zones d’incertitudes créées par les sauts du système absolu pour améliorer la précision.
L’estimation du positionnement dans les web browsers
L’utilisation des approches décrites ci-dessous sont quasiment toutes utilisables depuis une application native iOS ou Android (seul l’analyse des signaux Wifi pour la géolocalisation n’est pas disponible sous iOS). Les web browsers quant à eux ne fournissent que très peu d’accès capteurs aux développeurs. Nous avons vu dans le précédent blog post comment utiliser les évenements devicemotion, deviceorientation et deviceabsoluteorientation pour obtenir des données issues de la centrale inertielle. Le consortium du web propose régulièrement de nouvelles spécifications pour ouvrir l’accès aux capteurs (Geolocation API, Wifi Information API, Web Bluetooth API, Sensor APIs, WebXR Device API…), mais malheureusement, les web browsers ne les intègrent pas toujours. Seule la Geolocation API et les événements de type “device[…]” sont assez génériques pour être utilisables par une web app aujourd’hui. Nous reviendrons sur leurs utilisations dans la prochaine section.
Les contraintes
Bien qu’il nous soit possible de récupérer certaines données pour la géolocalisation via les fonctions disponibles sur les navigateurs, il n’est pas toujours évident de les exploiter pour créer un moteur de positionnement pour la Geo AR :
- La Geolocation API permet de s’abonner à des mises à jour de position grâce à la méthode watchPosition. Cette position, au format WGS84, peut être issue de différentes technologies (GNSS, WiFi, Cellular, IP?) ou même de la fusion de certaines d’entre elles. Malheureusement, il est impossible de connaître sa source exacte, le fonctionnement de la Geolocation API est une boîte noire. Cela pose un problème dans le développement d’algorithmes de géolocalisation, car, vu qu’il est impossible de dissocier les sources, la fusion avec les autres technologies ne peut être que grossière. Par exemple, on ne pas se fier à la fonction watchPosition pour savoir si l’utilisateur est dans un bâtiment ou à l’extérieur; contrairement au capteur GNSS natif qui, en l’absence de données renvoyées nous laisse supposer de la présence de l’utilisateur à l’intérieur d’un bâtiment (car les murs bloquent les signaux).
- Pour développer un algorithme de PDR, il est nécessaire d’avoir accès à l’accéléromètre, le gyroscope et l’orientation du smartphone. Cela est possible mais les contraintes sont les mêmes que celles décrites dans le précédent blog post.
- Bien que Google pousse l’intégration d’ArCore dans le Web, il n’y a pas vraiment d’API de VIO sur étagère pour le web directement utilisable aujourd’hui. On pourrait avoir envie de refaire ces algorithmes, mais leurs complexités et les limites d’accès aux capteurs dues au web rendent leur implémentation peu performante.
- L’arrivée des web workers a permis aux web app une plus grande flexibilité grâce au support du multi-threading. Cependant, ni la centrale inertielle, ni la caméra ne sont accessibles dans un web worker. Bien que les données puissent être transférées par message à un web worker, si le thread principal fait un gros calcul qui bloque l’envoie des messages, beaucoup de données seront perdues et certains algorithmes comme la reconstruction de l’orientation ne garantissent plus de bons résultats.
Malgré ces limitations, la création d’un moteur de positionnement pour la Geo AR reste possible. L’utilisation des données cartographiques permettra d’en améliorer la performance.
La cartographie pour aider le positionnement
Que ce soit en extérieur ou en intérieur, modéliser notre environnement pour le représenter sur une carte prend du temps, beaucoup de temps. Pour autant, ce temps passé qui permet naturellement d’obtenir une jolie carte peut aussi améliorer le moteur de positionnement. Il existe deux approches qui peuvent être utilisées dans notre contexte.
La première -qui est très gourmande en ressources CPU- est le filtre particulaire. Le principe est (1) de générer aléatoirement des particules autour de la position initiale (typiquement une distribution Gaussienne), (2) de faire avancer toutes les particules dans la direction de déplacement, (3) donner une très faible probabilité ou retirer les particules qui ont traversé un élément infranchissable (comme un mur), (4) re-générer des particules pour atteindre le même nombre (de particules) que l’étape initiale, puis recommencer le processus à l’étape (2).
La seconde approche, le Point to Network fait l’hypothèse que l’utilisateur se déplace sur un réseau de segments. Ce réseau de segments peut être soit généré automatiquement, soit relevé à la main depuis la carte. Le principe est de projeter la position estimée sur le segment du réseau le plus proche et de considérer cette nouvelle position comme la position de l’utilisateur. Pour éviter certains problèmes, une amélioration consiste à ignorer (dans l’algorithme) les segments du réseau qui ne sont pas dans la même direction que le déplacement.
C’est cette approche qui est très majoritairement utilisée par nos GPS de voiture. Pour les piétons, son utilisation est plutôt complexe car il est difficile de modéliser tout l’environnement par des segments, par exemple : les places piétonnes ou les halls de bâtiments. Cependant, quand l’utilisateur doit suivre un itinéraire bien défini (navigation), l’approche devient alors très intéressante.
Notre Approche
Le champ de recherche sur les systèmes de positionnement et de navigation est aujourd’hui très actif. Les dernières avancées dans ce domaine sont régulièrement publiées dans la conférence internationale IPIN (Indoor Positioning and Indoor Navigation) [disclaimer : je fais partie du comité de relecture d’IPIN]. Il y a régulièrement des compétitions pour évaluer et comparer le comportement des algorithmes en environnement réel (centre commerciaux, usines, magasins…). Cependant la recherche et le développement d’algorithmes embarqués dans un smartphone en général d’une part et le web et la réalité augmentée d’autre part (cf. supra) concentrent les challenges technologiques, ce qui nous a conduit à développer une approche originale, nourrie des avancées les plus récentes du domaine.
Par exemple, les algorithmes de détection de pas de la littérature ont l’habitude de segmenter le mode dans lequel le téléphone est tenu (à l’oreille, dans un sac, à la main devant soi, dans la poche…) pour avoir une détection de bonne qualité. Dans notre cas, tous ces modes ne sont pas nécessaires, ils pourraient même rajouter de l’instabilité. Cependant il est important que nous considérions les mouvements de type “réalité augmentée”, c’est à dire, essayer de ne pas avoir de détection de pas quand l’utilisateur interroge l’environnement virtuel autour de lui sans bouger. Et croyez-moi, ce n’est pas facile d’isoler ce comportement quand les seuls signaux accessibles sont ceux de l’accéléromètre et du gyroscope ! Pour cela, nous avons effectué des tests auprès d’échantillons d’utilisateurs pour observer leur comportement avec un smartphone et une application de réalité augmentée (naviguer sans AR, naviguer avec AR, interroger les alentours pour découvrir des informations virtuelles…), le tout en enregistrant les données des capteurs. En même temps, nous avons annoté les différentes phases de déplacement de l’utilisateur afin de s’en servir comme vérité terrain pour la comparaison d’algorithmes.
C’est grâce à ce type d’analyses que nous avons pu faire évoluer nos algorithmes pour progressivement gagner en précision.
Néanmoins, nous ne voulons pas perdre de vue notre objectif : guider un utilisateur dans le monde réel grâce à la réalité augmentée. Avoir une bonne précision est une bonne chose, mais ce n’est pas toujours suffisant pour permettre à l’utilisateur de se repérer correctement dans l’espace et vivre une expérience pleinement immersive. C’est pourquoi, nous avons choisi de faire au sein des heuristiques des arbitrages entre la précision du moteur de positionnement et l’immersivité du moteur de la scène virtuelle. Par exemple, lorsque l’on demande à l’utilisateur de suivre l’itinéraire qui lui est proposé, on doit prendre une hypothèse pour distinguer un écart d’un éloignement délibéré. Cela se traduit chez nous par donner une plus grande confiance au système de map-matching, quitte à perdre un petit peu en précision.
Une autre bonne pratique qui est utilisée pour le positionnement sur carte est l’interpolation des positions, elle est notamment utilisée pour rendre plus fluide la navigation du point bleu. Elle est d’autant plus importante en AR car un saut de la position entraîne également un saut de la scène virtuelle et donc une mauvaise expérience utilisateur. C’est pour cette raison que nous l’avons aussi intégrée.
Finalement, notre approche vise à combiner à la fois la portabilité et la performance et notre système fonctionne donc tant en environnement web qu’en environnement natif. Afin de bénéficier des avantages qu’offre un fonctionnement en natif nous avons conçu notre système pour qu’il puisse également intégrer les ressources et données qui sont accessibles en natif telles que le WiFi, le Bluetooth et le VIO. Les données issues de ces technologies sont directement transférées à notre moteur de positionnement, où elles sont prises en compte pour améliorer la précision. Le moteur a été conçu pour s’adapter automatiquement aux différents types de données qu’il reçoit et proposer la meilleure expérience possible quel que soit l’environnement d’utilisation.
Conclusion
Le web est un environnement complexe où les limitations d’accès aux capteurs contraignent le développement d’algorithmes de géolocalisation, cependant il est quand même possible de proposer à l’utilisateur une expérience AR légère et immersive. Les filtres décrits ci-dessus (hormis le VIO) ne sont pas très gourmands en ressources comparé à une approche basée sur le traitement d’image, cela donne un avantage conséquent pour leur implémentation en web. Contactez-nous si vous souhaitez avoir de plus amples informations.
