Les algorithmes de la visualisation 3D sur site

Pour continuer notre étude des techniques utilisées en réalité augmentée sur site, nous vous présentons maintenant les algorithmes utilisés pour la mettre en place.

La réalité augmentée demande la résolution de plusieurs problématiques, parmi lesquelles la détermination de la position de l’information par rapport à l’utilisateur, et le rendu de cette information de façon à l’insérer virtuellement dans l’environnement de la façon le plus immersive possible.

Nous adoptons ici une approche essentiellement algorithmique qui ne s’attarde pas sur les mathématiques, afin de donner une vision facilement abordable des techniques actuelles.

Algorithmes de détermination de la position de l’information

La réalité augmentée suppose de déterminer la position d’affichage d’une information dans le milieu de l’utilisateur. Il est donc nécessaire de connaître non pas la position absolue de cette information (ce qui serait aisé dans le cas d’une information statique), mais il faut déterminer la position relative de cette information par rapport à l’utilisateur.

Plusieurs techniques sont actuellement utilisées à cette fin.

Détermination par géolocalisation de l’utilisateur

Connaissant la position absolue d’une information à afficher, déterminer son emplacement par rapport à l’utilisateur ne demande plus qu’à trouver la position absolue de ce dernier. En calculant la différence entre ces coordonnées, tout en prenant en compte l’orientation de l’utilisateur, la position relative cherchée peut être déterminée très simplement.

Cette technique, actuellement très utilisée, se révèle efficace dans le cas d’informations statiques dans l’espace et ne demandant que peu de précision. En effet, comme expliqué dans notre précédent article, les moyens grand public de localisation d’un utilisateur (GPS, balises Wifi ou Bluetooth, réseaux mobiles etc.) ne fournissent qu’une précision très relative, de quelques mètres au mieux. Il est donc nécessaire de recourir à des moyens alternatifs pour toute application nécessitant une précision supérieure..

Détermination par détection de marqueurs

Dans le cas d’appareils comportant un système d’acquisition d’image, ce qui à défaut d’être systématique est comme vu dans les précédents articles très courant, les images captées peuvent être analysées pour détecter la position où afficher l’information. Une technique très répandue et qui fait ses preuves consiste à placer un marqueur à l’emplacement où cette information doit être insérée.

Exemple de marqueur utilisable pour la réalité augmentée. Source : http://flickr.com/photos/cogdog/5122441278 (CC BY-SA 2.0)

Détecter ce marqueur peut être effectué en utilisant des algorithmes d’analyse d’image classiques : détection de droites et segments, puis de coins, vérification de la correspondance avec la forme attendue (ici un carré), et validation avec la couleur du contenu. Vous trouverez ci-dessous une vidéo de l’INFI présentant les différentes étapes d’une technique de détection de marqueur qu’ils ont développée :

Très utilisée pour sa précision et la relative efficacité des calculs, cette technique présente cependant plusieurs désavantages :

  • Nécessité de pouvoir placer un marqueur à l’emplacement souhaité, ce qui n’est pas possible dans le cas d’une information dynamique
  • Nécessité de garder une bonne visibilité sur le marqueur, ce qui est problématique dans des environnements sombres par exemple
  • Nécessité de garder une résolution suffisante d’image pour identifier le marqueur ; cela signifie que le système ne peut plus fonctionner si on s’éloigne trop de celui-ci, ou si sa taille n’est pas suffisante

Afin de répondre à des problématiques de luminosité et de dynamisme du marqueur, des solutions ont été proposées en utilisant la localisation de sources lumineuses, avec un codage d’information possible par leur couleur ou leur clignotement. Cependant, l’impossibilité d’appliquer un marqueur de taille raisonnable reste limitante dans de nombreux cas.

Détermination par reconnaissance de formes

Par extension du système de détection de marqueurs, la détermination d’une position relative par reconnaissance de formes consiste à rechercher dans l’image non pas un marqueur apposé à cet effet sur un objet, mais simplement l’objet en lui-même. Il s’agit d’une opération complexe : les formes à reconnaître sont généralement observées sous un angle particulier, à une échelle différente des images de références qu’on peut définir, et avec une qualité variable.

L’algorithme SIFT (Scale-Invariant Feature Transform) est actuellement le plus utilisé à cet effet. Il permet d’extraire d’une image un ensemble de descripteurs indépendants de l’échelle, du cadrage, de l’angle d’exposition ou de la luminosité. Les points de référence extraits de l’image captée peuvent alors être comparés avec ceux de l’image d’origine pour déterminer s’il y a correspondance.

Exemple d’application de l’algorithme SIFT pour faire correspondre les descripteurs de deux images. Source : wikimedia

Une alternative est l’algorithme SURF (Speeded Up Robust Features). Inspiré par SIFT, cet algorithme est plus rapide que ce dernier, et permet d’après ses auteurs d’obtenir des résultats plus robustes.

Bien que très prometteuse car s’affranchissant de presque toutes les limitations énumérées précédemment, la reconnaissance d’objets quelconques est très peu utilisée en réalité augmentée à cause de sa complexité et fiabilité très relative. En effet, la détection d’un objet 3D, observable sous plusieurs angles, est un problème encore plus complexe que ce que nous avons pu voir dans le cas d’images 2D, et activement en étude. On peut citer par exemple les travaux de Lee, Wonwoo, Nohyoung Park and Woontack Woo présentées à l’ICAT (International Conference on Artificial Reality and Telexistence) de 2011, aboutissant au résultat de la vidéo suivante :

Algorithmes de rendu de l’information

La plupart des notions évoquées ci-dessous ne sont pas propres à la réalité augmentée sur site mais celle-ci ajoute une contrainte, l’utilisation sur terminal mobile (limitation de la puissance à cause de la batterie et de l’absence de ventilation active, langages adaptés…)

La perception

Commençons par le début : le cerveau reçoit diverses informations depuis ses capteurs sensoriels (dans le cadre de cette étude de la réalité augmentée sur site nous nous concentrerons sur la vue). Chaque fibre de nerf optique amène une fraction de l’information, et le cerveau reconstruit son environnement à partir de ces bribes. Une fois cette représentation effectuée c’est l’analyse : le cerveau cherche à déduire des informations des éléments de son environnement. Et inconsciemment, le cerveau va chercher à identifier un objet, sa distance par rapport à l’individu, le temps nécessaire pour l’atteindre, etc. Toutes ces déductions vont perturber l’analyse visuelle. et demander un temps de traitement plus long.

En cas de réception simultanée d’informations sensorielles; le cerveau va en définir une comme plus importante, donc prioritaire. Les informations secondaires sont alors modulées en fonction de leur lien, de la cohérence de l’ensemble qu’elles forment avec l’information principale , ce qui peut donner à une fusion plus ou moins rapide si la cohérence est plus moins forte ou à un rejet, une dissociation. Même si la détection de la cohérence d’un ensemble augmente avec l’expérience du cerveau il est indispensable de maintenir le plus de cohérence naturelle entre  l’image réelle et les informations augmentées pour une compréhension rapide et sans effort. L’entretien de la cohérence comprend de nombreuses problématiques : éclairage de la scène, positionnement spatial des éléments ajoutés par l’augmentation…

Exemple : expérience de Baddock. La distinction des petits N prend moins de temps (20 % de moins environ) que celle des petits Z (qui sont moins cohérents avec le grand N). Faites le test !

Cohérence dynamique : le flou cinétique (“motion blur”)

… ou flou de mouvement est le flou visible sur une photographie ou une animation dû au mouvement rapide du sujet par rapport à l’appareil de prise d’image pendant l’enregistrement. Ce mouvement est une combinaison des mouvements relatifs du sujet et de l’appareil. Le flou cinétique est notamment recherché dans l’animation, pour simuler un effet de vitesse ou bien limiter les saccades pour l’animation d’un évènement rapide, notamment dans la contrainte de temps réel du jeu vidéo.

effet de vitesse : http://vimeo.com/27406291

le motion blur dans le jeu vidéo :

http://www.youtube.com/watch?v=_QIIY2cl2Ds

Dans la réalité augmentée en particulier, la question du flou cinétique est épineuse car les terminaux mobiles conservent une puissance graphique bien inférieure à celle d’une console de salon ou un ordinateur, qui ont toujours des difficultés à bien gérer ce phénomène.

Exemples : a) images témoin b) flou de translation/rotation sans direction c) flou de translation vers la gauche/rotation horaire d) flou de translation vers la droite/rotation antihoraire

Ajouter du flou revient à dégrader l’image et à y ajouter un bruit => A = Bx + C. Donc une opération de convolution relativement coûteuse. Des techniques d’optimisation sont en cours de recherche, comme la possibilité de travailler le flou que sur certaines images d’une animation et non image par image, quand c’est possible.

Effets d’éclairage – cohérence des ombres et reflets

Exemple : l’importance des reflets pour la représentation des objets

Exemple : l’importance des ombres pour la localisation des objets

L’immersion d’un objet  dans son environnement comprend la luminosité : un objet reçoit de la lumière, ce qui produit une ombre et éventuellement un reflet sur l’objet. La question est ensuite de connaître la position des sources lumineuses, mais le cerveau est habitué à ce que la lumière provienne “d’en haut”, ce qui simplifie la programmation.

Exemple : la perception de la première est concave, de la seconde, qui est la première retournée, convexe, simplement par l’ajout de zones plus claires.

Positionner les objets virtuels

C’est tout l’enjeu de la réalité augmentée sur site : il s’agit de placer les objets aux bonnes coordonnées spatiales, et de les dimensionner en fonction de la distance d’affichage. Un exemple avec le positionnement de ptérodactyles virtuels dans le champ de vision :

http://youtu.be/gvFA3jonFD0?t=41s

Dans un second temps, il s’agit de conserver une cohérence avec l’environnement et de gérer notamment les occlusions de visibilité entre objets réels et virtuels (ainsi qu’entre objets virtuels !).

Exemple : l’avion virtuel passe derrière la statue, son image a été occultée par celle de la statue

Pour déterminer ainsi une occlusion une solution consiste à déterminer des modèles 3D des objets réels à partir de plusieurs images. Pour limiter les calculs on peut au contraire tromper l’oeil en effectuant sur la zone d’intersection une fusion des images ou encore en l’assombrissant.

L’utilisateur du terminal de réalité augmentée peut déplacer son appareil dans toutes les directions à toutes les vitesses. Il est pratiquement impossible pour le système de prédire les mouvements de l’utilisateur et les traitements à apporter aux objets virtuels ajoutés. Des estimateurs comme un filtre de Kalman permettent toutefois d’anticiper  un peu, mais l’utilisateur doit toujours réfréner ses mouvements.

En résumé un système de réalité augmentée suit les étapes suivantes :

Etapes utilisées par un système de réalité augmentée, ici avec un positionnement GPS

Et avec quoi je code ?

Ressources bibliographiques

  • 3D Outdoor Augmented Reality for Architecture and Urban Planning – Arnis Cirulis, Kristaps Brigis Brigmanis
  • Shadow Algorithms Data Miner – Andrew Woo, Pierre Moulin
  • Techniques de l’Ingénieur : Dossier perception de l’espace – Jacques Jouhaneau
  • A fast render algorithm of virtual and real motion blur consistence in augmented reality – Deyi Ma, Yimin Chen, Chen Huang, Qiming Li, Congli Ye, Yun Li, Yangbin Chen
  • http://magrite.loria.fr/pages/Occlusions/index.html
  • SIFT et SURF, Olivier Augereau : http://www.olivier-augereau.com/blog/?p=73
  • Site officiel de SURF : http://www.vision.ee.ethz.ch/~surf/
  • Lee, Wonwoo, Nohyoung Park, and Woontack Woo. “Depth-assisted real-time 3D object detection for augmented reality.” ICAT’11 (2011): 126-132.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>