Relocalisation par Vision (Computer Vision)
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 computer vision et de bases de données, de développement web et mobile, d’orientation et de systèmes de positionnement, de bâtiments et de villes et de bien plus encore :)
Après avoir abordé les principaux enjeux de la géo-pose et de la navigation en réalité augmentée, nous allons examiner les perspectives ouvertes par la vision par ordinateur (computer vision) pour créer un système de positionnement universel.
Le blogpost est un peu long 😅 puisque repartant du SLAM nous allons poser les bases techniques de la relocalisation par vision avant de comparer les approches de certains grands acteurs du secteur et d’évoquer les défis technologiques les plus récents sur ce thème. Bonne lecture et contactez-nous si vous avez des questions ou commentaires research@getwemap.com !
Le SLAM : mesurer les déplacements relatifs d’un smartphone
Depuis 2017 les systèmes d’exploitation iOS et Android permettent de créer des applications utilisant la réalité augmentée, grâce aux technologies ArKit et ArCore.
Lorsqu’elles utilisent la caméra arrière du téléphone, les applications de réalité augmentée proposent le plus souvent de positionner un élément virtuel dans un décor réel comme s’il y était “vraiment”.
Cette expérience est rendue possible grâce à des algorithmes de SLAM (Simultaneous Localization And Mapping) qui sont au cœur des systèmes ArKit et ArCore.
Ces algorithmes de suivi peuvent estimer le déplacement du smartphone dans l’espace en utilisant la caméra et détecter les surfaces : c’est ce qui permet de donner l’impression que l’objet virtuel est bien “ancré” dans la scène 3D quand l’utilisateur bouge avec son téléphone.
Les algorithmes de SLAM calculent de manière itérative la position et l’orientation (pose) du téléphone grâce à des points clés et des descripteurs, qui permettent une reconstruction 3D de l’environnement. L‘avantage de cette odométrie visuelle : les algorithmes de SLAM ne nécessitent aucune information a priori sur l’environnement.
Utiliser le SLAM pour se positionner
Bien que les algorithmes de SLAM soient très performants aujourd’hui - notamment grâce à la fusion avec la centrale inertielle - ils ne permettent pas d’obtenir une géo-pose du téléphone. La géo-pose étant la position et l’orientation du dispositif par rapport au repère terrestre (par exemple: latitude, longitude, altitude, quaternion…).
Comme nous l’avons vu dans un précédent blogpost, le système actuel de géolocalisation que nous avons mis au point pour la navigation en réalité augmentée se base sur deux types de signaux :
- les signaux de géolocalisation absolus qui permettent d’obtenir directement des informations pour le calcul de la géo-pose du téléphone. On retrouve notamment les signaux issus du GNSS (Global Navigation Satellite System), des points d’accès Wi-Fi et bluetooth (trilatération/fingerprint), du scan de QR codes géolocalisés, de l’accéléromètre et du magnétomètre.
- les signaux de géolocalisation relatifs qui permettent d’obtenir des informations dans un repère non géo-référencé. On peut compter sur la pose issue, outre du SLAM, du PDR (Pedestrian Dead Reckoning) ou encore des signaux provenant du gyroscope et du baromètre.
Nous fusionnons ces signaux avec des données cartographiques grâce au map-matching afin d’obtenir la meilleure géo-pose possible dans une multitude de situations (voir blogpost).
Le SLAM étant un système de positionnement relatif (la nouvelle position est connue relativement à la précédente), s’il est utilisé pour de la navigation sur des longues distances, il va souffrir de dérive. Cette dérive dépend beaucoup du contexte, mais peut facilement atteindre des erreurs de 3–4 mètres et d’une dizaine de degrés sur une cinquantaine de mètres parcourus.
Le SLAM est actuellement une de nos sources de localisation pour les déplacements relatifs. Afin de minimiser cette dérive inhérente à l’odométrie visuelle sur les longues distances, nous fusionnons le SLAM avec les signaux de positionnement externes et avec les données du réseau piéton — qui sont aussi utilisées par notre calculateur d’itinéraires.
Dans l’éco-système de Wemap, le SLAM est un élément central du positionnement relatif mais il n’est pas systématique. En effet nous utilisons ArCore (Android) et ArKit (Apple) mais ces SDKs ne sont disponibles que sur les seules générations les plus récentes de smartphone et ne peuvent être utilisés depuis le web : si l’environnement matériel et logiciel est dans la capacité d’exploiter le SLAM, nous l’utilisons. Pour le moment, nous n’envisageons pas de créer notre propre SLAM en web : la rapidité de l’environnement d’exécution n’est pas propice à son implémentation et la limitation d’accès aux capteurs ne permet pas d’acquérir une donnée métrique. Cependant, selon les dernières avancées du WebXR; d’ici quelques mois, ArCore et ArKit seront bientôt disponibles dans les navigateurs web.
Les dernières avancées scientifiques dans le domaine de la vision, nous amènent aujourd’hui à un nouvel objectif : celui d’étendre l’utilisation de la caméra afin d’en faire bénéficier notre système de positionnement absolu.
La relocalisation par vision : premiers concepts
Pour définir la notion de relocalisation par vision, prenons un exemple simple :
Un opérateur parcourt tout un magasin avec un dispositif d’acquisition vidéo équipé d’une ou de plusieurs caméras. Ces images sont analysées puis un nuage de points 3D du magasin est créé grâce à un algorithme et enregistré dans le cloud. C’est la phase offline.
Un client à besoin de se géolocaliser dans le magasin. Il prend son téléphone, ouvre l’application du magasin et, en relevant son téléphone, affiche une vue caméra du rayon dans lequel il se trouve. En moins d’une seconde une photo est envoyée dans le cloud, analysée par le serveur de relocalisation qui calcule la position et l’orientation dans laquelle la photo a été prise et les renvoie au téléphone. Le client peut alors commencer une expérience de réalité augmentée géolocalisée ou visualiser sa position sur une carte 2D. C’est la phase online.
Ce processus est celui de la relocalisation par vision.
Le processus de relocalisation par vision est composé de deux phases : (1) la phase offline, où s’effectue une acquisition de l’environnement, et (2) la phase online, où la position est restituée.
La phase offline consiste à créer un nuage de points 3D géolocalisés à partir des images acquises par le dispositif vidéo. Les deux grandes approches qui traitent le problème de reconstruction 3D en vision par ordinateur sont le SfM (Structure from Motion) et le SLAM. Les deux approches se ressemblent par leurs algorithmes mais leurs domaines d’applications sont souvent différents. Le SLAM a été historiquement conçu pour fonctionner en temps réel et utiliser le flux vidéo provenant d’une caméra. Les algorithmes de type SfM utilisent a contrario des images acquises à des distances et des angles de vue raisonnablement différents, puis la reconstruction est effectuée post-traitement. Chacune des deux approches a des avantages et des inconvénients en fonction des scénarios à couvrir (contexte, luminosité, surface à couvrir…).
Une fois le nuage de point créé il est alors géo-référencé puis sauvegardé sur un serveur.
La phase online est celle qui concerne l’utilisateur final. L’utilisateur est d’abord invité à parcourir son environnement avec sa caméra, ce qui permet de prendre une courte vidéo de son environnement proche. Une (ou plusieurs) images sont extraites de la vidéo car elles comportent beaucoup de points caractéristiques. Chaque image est alors envoyée au serveur de relocalisation, elle est comparée avec l’ensemble des images qui ont permis la construction du nuage de points 3D (best matching). La ou les images qui sont estimées les plus proches — de celle qui a été envoyée par l’utilisateur — sont utilisées pour calculer la géo-pose de cette nouvelle image (triangulation). Cette géo-pose est ensuite renvoyée au dispositif de l’utilisateur puis utilisée à des fins de réalité augmentée, navigation ou géolocalisation.
Note : Le calcul de la géo-pose via le serveur de relocalisation peut parfois prendre un peu de temps (> 100 ms) à cause de la complexité des calculs et de la vitesse de connexion. Pendant cette période, l’utilisateur peut avoir fait beaucoup de mouvements (surtout en rotation) avec son dispositif. Il est donc souhaitable de coupler un tel système de relocalisation avec un système de SLAM (typiquement ArCore/ArKit) pour prendre le relai et calculer les transformations dans cet intervalle de temps.
L’émergence de la relocalisation par vision sur smartphone
La relocalisation par vision est une approche qui existe déjà depuis quelques années dans le milieu de la recherche et notamment dans le domaine de la robotique, qui permet de concevoir d’utiliser la vision par ordinateur (computer vision) dans des environnements contrôlés (mouvement de l’appareil, taille de l’espace considéré, etc). Le smartphone utilisable dans un environnement illimité et avec des degrés de liberté dans toutes les directions cumule les difficultés pour les informaticiens.
C’est en 2019 que l’on découvre pour la première fois la relocalisation par vision sur smartphone, principalement grâce à Google et son produit “Google Maps AR (beta)” qui utilise la technologie VPS (Visual Positioning Service) pour préciser en extérieur le blue dot et l’orientation grâce aux images de la caméra.
Une telle application a été rendue possible à la fois grâce à des algorithmes de relocalisation par vision robustes, mais aussi et surtout grâce à la quantité d’images que Google a récolté pendant des années avec les voitures utilisées pour leur produit StreetView.
Nous n’en sommes encore qu’aux prémisses des services de positionnement ou des expériences de réalité augmentée que permettra cette reconnaissance de l’environnement : les technologies sous-jacentes sont encore en maturation et la relocalisation est proposée dans des scénarios limités.
En effet les défis posés par la relocalisation en termes de computer vision sont multiples. En particulier les algorithmes de construction de points 3D que nous connaissons aujourd’hui exigent de faire des compromis entre rapidité, précision et environnement d’utilisation.
Les différents acteurs de la réalité augmentée ne vont pas nécessairement avoir besoin du même pipeline pour construire leurs nuages de points 3D géolocalisés.
Ainsi, Google avait déjà dans sa banque de données des photos 360 issues de leur produit Google Street View. Ces photos ont la particularité (i) d’avoir été acquises par des caméras placées sur le toit d’une voiture et (ii) d’être géolocalisées par GNSS. C’est pourquoi Google a vraisemblablement utilisé un algorithme de type SfM pour la construction de son nuage de points. L’utilisation de fonctions d’optical flow — typiques du SLAM — aurait fourni de mauvais résultats car les images ont été prises à des distances et des angles sensiblement différents.
Or en vision par ordinateur, les comparaisons d’images ne sont possibles que si les types de caméras (perspective, fisheye ou 360) sont similaires. Cela implique, dans un cas comme celui de Google, de devoir adapter le pipeline pour prendre en compte ces transformations géométriques et optiques complexes de sorte que phase offline et phase online puissent être réalisées sur des appareils très différents.
A contrario, chez le développeur de jeux Niantic, bien que proche de l’univers Google, ce sont les joueurs qui font l’acquisition (phase offline) directement avec leur smartphones (caméra perspective + position GNSS). Dans ce cas, l’algorithme à utiliser pour la reconstruction du nuage de points est plutôt du type SLAM. Les images sont issues d’une vidéo et sont strictement ordonnées, il est alors possible d’utiliser des fonctions d’optical flow pour améliorer et accélérer le processus de reconstruction.
Niantic veut créer une “plateforme du monde réel” pour crowdsourcer les phases offline et partager des expériences de réalité augmentée (Niantic a d’ailleurs fait l’acquisition de 6d.ai en 2020).
Depuis 2019 d’autres géants du web ce sont aussi lancés dans la course à un nuage de points 3D global parmi lesquels :
- Facebook qui a annoncé vouloir cartographie la planète pour leurs lunettes AR et a fait l’acquisition des start-ups Scape Technologies et Mapillary en 2020 ;
- Huawei qui lance Cyberverse, un système de cartographie 3D dans le cloud pour la réalité augmentée ;
- et bien sûr Apple et Microsoft avec les Azure Spatial Anchors.
Chacun de ces géants déclare vouloir créer un système de relocalisation propriétaire et générer son propre nuage de points 3D planétaire. Malheureusement la réutilisation de ce nuage de points 3D depuis des applications mobiles sera réservée aux différents produits de ces marques (Google Maps AR, Pokémon GO, etc) ou sera limitée en termes de fonctionnalités (Apple, Microsoft ASA, etc). Par ailleurs une telle approche ne va pas sans soulever de nombreuses questions de vie privée et de propriété de l’information.
Plutôt que de construire des services fermés et propriétaires nous pensons que la relocalisation par vision doit relever d’une approche ouverte avec une mise en commun des ressources.
De la même manière qu’aujourd’hui OpenStreetMap crée un commun de données cartographiques mondiales auquel même les plus grands acteurs s’associent, un nouveau consensus est possible dans le monde libre et open source pour la relocalisation par vision. C’est pour cela que Wemap a rejoint l’association OpenARCloud pour garantir une inter-opérabilité des données et des techniques de “spatial computing” et que nous sommes partenaires de XR4All qui promeut des frameworks open source en computer vision appliquée à la réalité augmentée. Nous reviendrons sur ces enjeux sectoriels et ces principes dans un futur post.
La relocalisation par vision : vers un système de positionnement “universel” ?
Au sein de la technologie Wemap la relocalisation est abordée en tant que signal absolu qui vient compléter un système de positionnement en l’absence d’alternative. En extérieur le signal GNSS et le magnétomètre fusionnés suffisent en première approximation. C’est pourquoi nous concentrons nos travaux sur la relocalisation par vision là où le GNSS n’est pas disponible et, en particulier, dans les espaces intérieurs.
La relocalisation par vision est une solution incontournable dans plusieurs types de lieux où le signal GNSS est absent ou très dégradé : gares, centre commerciaux, magasins, bureaux.
Contrairement aux captures en extérieur où le changement d’éclairage (dû à la position du soleil) est une source majeure de problèmes pour la comparaison des descripteurs, les environnements dans lesquels nous travaillons ont une source de lumière beaucoup plus contrôlée. Cela évite d’effectuer des acquisitions à différents moments de la journée comme il est courant de le faire en extérieur.
Les challenges propres aux scénarios d’utilisation en intérieur sont nombreux, pour n’en citer que quelques uns :
- Les espaces “manufacturés” tels que les couloirs des gares sont des zones très sombres avec des motifs souvent très répétitifs ce qui la reconnaissance très difficile ;
- Les environnements intérieurs peuvent être changeants avec des rythmes rapides et sans prévisibilité (au contraire des éléments de scène extérieurs tels que les arbres, voitures ou formes humaines, dont le traitement en computer vision est déjà très documenté). Ainsi dans un magasin, régulièrement les produits sont retirés et ajoutés aux étagères, la scène est très dynamique ;
- Les halls des centres commerciaux sont des espaces souvent bondés et la présence de ces personnes cache souvent des zones clés qui sont décisives pour la relocalisation ;
- Les vitrines sont des surfaces réfléchissantes qui sont presque impossibles à prendre en compte dans les algorithmes de vision.
Pour isoler ces zones d’incertitudes et garantir une robustesse au système que nous mettons en place, nous nous focalisons sur le fait de proposer des descripteurs robustes et spécifiques aux différents scénarios d’utilisation en intérieur. Ces sujets sont très étudiés par la communauté scientifique actuelle [voir Alismail et al., Riazuelo et al.]. Pour ces raisons, nous travaillons avec certains des meilleurs instituts français de la recherche dans le domaine de la reconstruction par vision.
In fine, comme c’est le cas pour les autres signaux de positionnement absolu utilisés au sein de Wemap, nous fusionnons les données de l’approche par vision avec d’autres signaux tels que le Wi-Fi, le Bluetooth, le champ magnétique, etc. Cela permet à la fois d’être plus rapide lorsque les zones à couvrir sont très grandes, et de régler les problèmes d’ambiguïté lorsque des motifs se ressemblent.
Conclusion
Les défis techniques liés à la variété des environnements visuels sont nombreux. La relocalisation par vision sera une solution modulaire, avec des approches algorithmiques dépendantes des lieux d’utilisation : espaces publics, bureaux, extérieur, etc.
A terme, même sans solution algorithmique unique qui couvre tous les environnements et scénarios d’utilisation, la relocalisation par vision va devenir une solution centrale dans tout système de positionnement universel.
Dès aujourd’hui grâce à la relocalisation par vision nous pouvons amener des expériences et des services innovants de navigation, de guidage et de réalité augmentée dans des lieux dépourvus de localisation.
Vous voulez en savoir plus ou vous avez des questions sur la relocalisation par vision, écrivez-nous à research@getwemap.com :)
