Une thèse ? Et tu travailles sur quoi ?

Triangulation (CC-By James Mallos)Une fois n’est pas coutume, je vais vous parler de mon boulot. Je fais habituellement une distinction nette entre ma vie « publique » (en gros, le Geektionnerd) et ma vie professionnelle (quant à la vie privée, je me la garde), mais il n’y pas de mal à faire une petite exception de temps en temps ! Pour ceux qui l’ignorent, je suis thésard en informatique à l’Inria. Et lorsque je me présente ainsi, vient fatalement la question « et tu travailles sur quoi ? ».

Outch. J’aime autant vous dire que si la question tient en 5 mots, la réponse est loin d’être simple à formuler… Et qu’il y a de grandes chances que vous n’y compreniez rien. Ne le prenez mal, ce n’est pas de la condescendance, mais c’est comme ça que la science fonctionne : plus les connaissances scientifiques humaines avancent, et plus les domaines de recherche universitaire deviennent à la fois très spécifiques (on travaille sur une et une seule toute petite chose très précise perdue dans l’immensité des domaines de recherche possibles) et très pointus (en gros, on est 15 dans le monde à bosser sur ce petit machin très précis). J’ai d’ailleurs un article en tête pour présenter ce principe de façon plus concrète plus tard, mais ce n’est pas le sujet.

Cet article va donc être long. Me vient à l’esprit un petit dialogue très drôle du film « On connaît la chanson » :

– Et une thèse euh… Sur quoi ?
– Sur les chevaliers-paysans de l’an mil au lac de Paladru.
– Mais euh, y’a des gens que ça intéresse ?
– Nan, personne.
– Pourquoi t’as choisi ce sujet alors ?
– Pour faire parler les cons !

Voilà. Alors je vous rassure, je ne fais pas une thèse pour faire parler les cons (faudrait quand même être bizarrement motivé, d’autant que les cons parlent très bien sans qu’on les sollicite). Mais si vous lisez le sujet de ma thèse, comme ça, ça ne va sans doute pas vous parler des masses. Allez, pour le fun, ouvrez les guillemets :

« Robust surface reconstruction from defect-laden data »

Alors, ça pète hein ? Pour les non-anglophones, cela veut à peu près dire « Reconstruction de surfaces robuste à partir de données pleines de défauts ». Ça vous fait une belle jambe, non ? Et encore, ça pourrait être pire : là, en lisant, on comprend tous les mots et on peut avoir une vague idée de ce que cela signifie. Parce que dans un autre registre, j’ai des collègues qui doivent « marcher rapidement dans des triangulations » ou trouver des « structures de données efficaces dans les triangulations en haute-dimension » (ouais, on aime beaucoup trianguler là où je bosse). Ça calme. Et encore, même là, ça reste des maths appliquées. Lisez-donc un sujet de mathématiques fondamentales, pour voir.

Si tu avances quand j’trianguleuh
Comment veux-tu, comment veux-tu…

Bon bref, n’empêche que même si le titre n’est pas parlant pour tout le monde, il est tout à fait possible d’expliquer le sujet avec des mots simples. Parce que, je me répète, mais dans mon cas, ce sont des maths appliquées, qu’on bosse dans le monde réel et que, même si le bouzin scientifique qui se cache derrière est du genre coriace, le but recherché est en fait d’une simplicité surprenante.

Mais on va y aller mollo. Tout est dans le sujet (ou presque), alors allons-y terme à terme, dans l’ordre d’importance. Je vais aller au plus simple, histoire qu’aucune connaissance scientifique poussée ne soit nécessaire pour comprendre.

Surface reconstruction

Reconstruire une surface ? Mais pour quoi faire ? On l’a déconstruite, avant ?

La reconstruction de surface, c’est un un domaine très vaste de la science informatique. La biblio dans ce domaine est trèèèèès longue (j’en sais quelque chose, la première mission du thésard étant de faire le point sur « l’état de l’art »). Il y a beaucoup de méthodes avec beaucoup d’adaptations, chacune fonctionnant très bien dans beaucoup de cas et très mal dans beaucoup d’autres cas aussi. Beaucoup de beaucoup donc. Ajoutez à cela la difficulté de mesurer quantitativement la qualité d’une surface reconstruite (c’est-à-dire autrement qu’en regardant si la surface est belle ou pas), et vous avez une idée de l’ampleur du problème.

Reconstruction donc, mais à partir de quoi ? De points. De centaines, de milliers, et plus souvent de millions et de dizaines de millions de points. On appelle ça un nuage de points (point cloud). Il peut être brut (un point est alors juste un point géométrique classique, représenté par 2 coordonnées dans le plan ou 3 dans l’espace) ou être enrichi par de l’information supplémentaire, comme des vecteurs normaux (qui donnent une idée de l’orientation locale de la surface). Mais gardons le cas le plus simple, le nuage de points brut. On aura donc tout simplement N informations de la forme (x, y, z). Voyons ce que ça peut donner si on visualise ça :

C’est beau non ? Vous pouvez reconnaître un tore (et c’est moi qui l’ai fait en plus). 50000 points, ce qui est peu, mais largement suffisant vu la simplicité de l’objet. Là, il s’agit d’un nuage généré par un programme (dont je parlerai dans un prochain article), mais bien sûr, on dispose également de très nombreux exemples de nuages de points acquis sur des objets réels par des scans au laser. Le site de l’université de Stanford est par exemple très célèbre pour proposer une bibliothèque de surfaces et de nuages de points provenant d’objets réels (le Stanford Bunny est presque légendaire, si vous jetez un œil à quelques articles sur la reconstruction ou sur d’autres sujets qui touchent à la 3D, vous risquez de le croiser souvent – un peu comme Lenna pour le traitement d’images).

Oui, les chercheurs aiment bien regarder des playmates et des lapins quand ils bossent. Y’a un problème ?

On parle donc de reconstruction, non pas parce qu’on a déconstruit la surface, mais parce que les systèmes d’acquisition dont nous disposons ne capturent que des points. Si l’on veut passer à un objet surfacique, pas le choix, il faut traiter ce nuage pour retrouver la surface qu’on a scannée.

Mais dis-donc, on voit très bien que c’est un tore, ton nuage de points ! C’est simple de retrouver la surface à partir de ça, non ?

Hé oui, mais si vous voyez le tore, c’est que votre cerveau est sacrément bien foutu et que vous êtes très intelligent (si si, j’insiste). Rappelez-vous de ce que je vous ai dit dans un précédent article et qui est fondamental : l’ordinateur est con.

Quelle que soit la forme que prend votre nuage de points, sans autre information, votre ordinateur ne verra jamais rien d’autre qu’une suite de coordonnées (x, y, z). Il faut donc lui expliquer comment on trouve une surface à partir d’un ensemble de point. Vous voyez le problème ? On parle de deux objets complétements différents. Un point, c’est simple, c’est x, y et z. Et une surface, vous la définiriez comment, vous ? Et comment vous passeriez de l’un à l’autre ? Bon, en réalité, il existe beaucoup de manières de représenter une surface en langage informatique. Mais passer du point à la surface, c’est loin d’être anodin.

Et en plus, ça va devenir bien pire.

Robust

Robuste ? On va faire de la reconstruction antiatomique ?

En quelque sorte. Le nuage de points que je vous ai montré dans la partie précédente, c’est de la rigolade. Vous ne trouvez pas ? Moi si. La forme est ridiculement simple, le nuage de points est très dense, il est uniforme (à peu près la même densité de points partout sur la surface) et il ne manque pas de données. Bref, le pied.

Figurez-vous que dans la vraie vie, les nuages de points ont le culot d’être parfois complétement pourris (si si, je vous assure). Déjà, on va reconstruire des objets réels avec des formes beaucoup plus complexes (allez voir la bibliothèque de Stanford – mais y’a bien pire que ça, imaginez qu’on décide de scanner le Parthénon ou la tour Eiffel), et le nuage peut avoir des quantités de défauts que vous n’imaginez même pas.

Seulement voilà, si votre utilisateur a besoin de reconstruire une surface, vous ne pouvez pas juste lui dire « ton nuage de points est pourri, j’peux pas ». Quand on traite des données réelles, il faut être prêt à tout, surtout au pire. On va voir dans la section suivante ce qu’est ce « pire ».

Defect-laden

« Plein de défauts ». Hé oui. À cause des imperfections de mesure, des méthodes de balayage des scanners (plusieurs scans recalés, par exemple) et de quantités d’autres raisons, notre nuage de points peut présenter une myriade de défauts différents. On regroupe traditionnellement ces défauts en plusieurs classes :

  • Le bruit : je compte faire prochainement un article complet sur le bruit au sens scientifique (bruit autre que sonore donc), mais pour faire simple, il s’agit d’un décalage entre les données réelles et celles que vous avez récupérées au scanner. Parce que votre scanner n’est pas infiniment précis, lorsque vous acquérez un point qui est à 5m pile, votre scanner vous donnera peut-être une valeur de 4,8m ou de 5,1m par exemple (l’incertitude étant plus ou moins grande selon la précision de votre scanner). Il y a beaucoup de sources de bruit, l’imprécision du scanner en est une, mais le simple fait d’utiliser des nombres flottants finis sur un ordinateur est déjà créateur de bruit par rapport à des nombres réels.
  • Les outliers : désolé pour les puristes francophiles, je ne connais pas de traduction, on utilise toujours ce terme même en français (on peut parler de donnée aberrante, il me semble). Par opposition aux inliers, qui sont les points corrects qui correspondent aux données, les outliers sont, pour être clair, des points qui n’ont rien à faire là. Mais voilà, ils sont là. Une mouche ou une poussière qui passe devant le scanner ? Ou tout simplement un scanner capricieux qui voit des objets invisibles ? Bref, ce sont des points qui peuvent apparaître aléatoirement et qui ne correspondent pas à votre objet. En cela, ils sont très différents du bruit : le bruit donne des points inexacts mais proches des données réelles, les outliers sont des points totalement aberrants. Ils sont normalement peu nombreux par rapport aux inliers, mais si votre méthode de reconstruction est très sensible à chaque unique point, vous imaginez la catastrophe quand on en croise un…
  • Les données manquantes : des trous dans les données. Imaginez une statue posée au sol. Vous ne pouvez pas scanner la partie en-dessous de la statue, il y a un trou dans vos données. Mais il faut quand même pouvoir reconstruire le reste. Si vous faites un scanner à la main, vous pouvez aussi rater une partie de l’objet par mégarde. Bien sûr, on ne peut jamais réinventer les données qui manquent, mais il faut trouver un moyen de combler ces trous efficacement.
  • Les variations dans la densité de points : vous scannez 15 fois l’avant de votre objet et 1 fois l’arrière. Bon, vous n’êtes pas malin, aussi. Mais, résultat, vous avez 15 fois plus de points sur l’avant que sur l’arrière, pour une surface d’aire équivalente : la densité de points devient très variable. Ça n’a l’air de rien, mais si votre méthode de reconstruction est robuste au bruit et aux outliers, elle va peut-être considérer l’arrière de votre face comme un nuage d’outliers ! Hé bien oui, des points très peu denses comparés au reste, ça peut très vite passer pour des données aberrantes…

Ce sont les 4 principaux types de défauts qu’on rencontre. Aujourd’hui, on sait plutôt bien gérer le bruit et les outliers. Ce n’est pas toujours aussi évident pour les données manquantes et les variations de densité. De manière générale, il semble très compliqué d’être robuste à tous ces défauts à la fois (je dis bien « il semble », parce qu’il n’est pas impossible qu’on y arrive un jour, mais pour le moment, il faut – en gros – choisir à quoi on veut être robuste). La méthode sur laquelle je bosse actuellement est robuste aux 3 premiers défauts, ce qui n’est déjà pas si mal.

Et ça donne quoi ?

Hé bien regardez la capture d’écran ci-dessous ! Une jolie surface reconstruite à partir du nuage de points sur le tore que j’avais montré plus haut.

Hééé, mais tu te fous de nous ? Tu disais que tu devais être robuste aux défauts, et là tu nous sors une reconstruction depuis un nuage de points presque parfait ! C’est même toi qui l’a dit !

Si vous vous êtes fait cette réflexion, c’est bien, vous suivez ! Sinon ce n’est pas grave, on va dire que vous êtes indulgents avec moi, ce qui est très aimable de votre part (même si c’est discutable côté rigueur scientifique).

Nous allons donc joyeusement pourrir ce joli nuage de points. Qu’est-ce qu’on dit ?

Yoopyyyyyy ! Pourrissons les nuages de points !

Sous vos yeux ébahis, nous allons le bruiter légèrement :

C’est tout ? C’est pas un gros vacarme, ton bruit…

Bon okay, on va lui bruiter sa mère quelque chose de méchant (là ce serait donc un chercheur atteint d’un Parkinson particulièrement violent qui tiendrait le scanner) :

Alors, il fait moins le malin, notre nuage, là ! Et en plus, je lui ai mis 10% d’outliers dans sa face (bon c’est tellement bruité qu’on ne les distingue pas vraiment du reste).

Hé béh… Maintenant il a une sale tête ton tore…

Oui, mais je vais vous décevoir : la reconstruction ne va pas être fabuleuse non plus. Parce qu’on a beau être robustes, on ne va pas faire de miracle sur un nuage comme celui-là. La robustesse consiste ici à ne pas produire de forme anarchique ou aberrante (ce qui pourrait arriver avec un nuage aussi moche) et à approximer au mieux des données très imparfaites. Le résultat :

Le tore a chopé un peu de cellulite, mais ça reste acceptable (notez que je n’ai pas créé de trou dans les données mais la méthode fonctionnerait également dans ce cas : on aurait un petit « airbag » au niveau du trou), on retrouve la topologie de l’objet et une surface proche de l’originale. Vous pouvez quand même remarquer une chose : à la base, on voyait très bien le tore à partir du nuage de points, notre cerveau le reconstruisait en quelque sorte automatiquement, mais l’ordinateur ne voyait rien. Grâce à la technique qu’on a mise en œuvre, l’ordinateur devient même capable de reconstruire la surface quand nous-même ne la voyons plus si facilement que ça. C’est un exemple de ce que je racontais dans mon article sur l’ordinateur, lorsque je parlais de combiner l’intelligence humaine avec la vitesse de l’ordinateur : ici, on arrive à rendre l’ordinateur plus performant que notre vision !

Voilà ! Vous avez un petit aperçu de ce sur quoi je bosse la majorité de mon temps (et dont vous ne soupçonnez pas l’existence en lisant le Geektionnerd). J’espère que ce petit exposé un peu long (mais condensé et simplifié au maximum) vous a plu. Et pour finir, il y a toujours l’inévitable question…

À quoi ça sert ?

À plein de choses ! En imagerie médicale, par exemple, pour reconstruire des modèles 3D d’organes en utilisant les techniques d’imagerie habituelles…

Et dans un tout autre domaine, sachez que la reconstruction de scènes urbaines a le vent en poupe en ce moment : imaginez que Google (ou d’autres, mais ce sera très probablement Google qui le proposera en premier au grand public) utilise des scans au laser au lieu de photos lorsque ses voitures parcourent les villes pour Google Street View… Hé bien un jour, vous pourrez très certainement vous balader virtuellement dans les rues des villes, non plus avec de simples photos mais dans un véritable environnement 3D reconstruit à partir de ces données de points et de techniques similaires à celle que je viens de vous présenter.

Cool, non ?

(Bon, et je remarque que j’ai évoqué 3 futurs articles dans cet article-là. Y’a du boulot…)

Si ce que je vous ai présenté vous intéresse et qu’un peu de maths avancés en anglais ne vous font pas peur, vous pouvez jeter un œil à l’article Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets : la technique de reconstruction que j’ai utilisée pour mes captures d’écran est une sorte de variante de celle décrite dans ce papier.

Crédits photos :
* Triangulation (CC-By James Mallos)
* Captures d'écrans originales (CC-By-Sa Simon Giraudot)

9 réflexions au sujet de « Une thèse ? Et tu travailles sur quoi ? »

  1. Très intéressant ! Hihi, un ancien cÔllègue. Tu es dans quelle équipe-projet? Difficile de vulagariser (non non, pas de vulgarités) un sujet de thèse, surtout quand les mots qui « fabriquent » le titre ne parlent pas à la plupart d’entre nous, où quand on ne trouve pas d’équivalent français à des termes anglais moulte fois utilisés par la communauté. Certains titres leur billet « comment expliquer ma thèse à ma grand-mère ».
    J’ai jamais trop aimé le mot « thésard ». D’ailleurs, dans la langue française, rares sont les mots jolis qui finissent par ‘ard’. Il y a de sales noms d’oiseaux, mais j’ai dit « pas de vulgarités ». « Doctorant » sonne un peu mieux. Sinon, à l’américaine « Pi Éch Di ».

    Oui, « donnée aberrante » se dit comme il te semble. C’est utilisé comme vocabulaire de « stateux » (ou des gens qui font des maths statistiques). Ne voulais-tu pas dire « atteint de Parkinson » plutôt qu’Alzheimer?😉

    Ce que tu développes pour ton doctorat est sous GPL ou bien ?🙂
    Bon courage et bonne continuation !

    1. (Je suis dans Geometrica dans le centre de Sophia Antipolis.)

      Arf, oui Parkinson, c’est corrigé, merci😉

      Ce que je développe pour la reconstruction est sous licence que dalle pour le moment, vu que je ne l’ai pas (encore) diffusé. Mais si diffusion il y a (faudrait que je me colle à un peu de nettoyage si je veux le diffuser ce code – c’est du code de recherche bien cradingue :p), ce sera clairement sous licence libre (enfin j’ai aussi récupéré des bouts de code à droite à gauche donc il faudrait que je demande si les auteurs sont d’accord avant).

  2. Pour faire simple, tu aides les ordinateurs (robots, voiture automatique, détecteur médical, industriel…) à reconnaitre leur environnement (le jour où les robots travailleront avec des laserscanner).

    >>> Et dans un tout autre domaine, sachez que la reconstruction de scènes urbaines a le vent en poupe en ce moment : imaginez que Google (ou d’autres, mais ce sera très probablement Google qui le proposera en premier au grand public) utilise des scans au laser au lieu de photos lorsque ses voitures parcourent les villes pour Google Street View… Hé bien un jour, vous pourrez très certainement vous balader virtuellement dans les rues des villes, non plus avec de simples photos mais dans un véritable environnement 3D reconstruit à partir de ces données de points et de techniques similaires à celle que je viens de vous présenter.

    Et la PAPA-Mobile, c’est quoi ? Tu ne vas pas dire que tu ne connais pas, ainsi que l’ensemble des projets du laboratoire MATIS de l’IGN (cf http://recherche.ign.fr/labos/matis/accueilMATIS.php).

    J’adooore les chercheurs qui s’ignorent entre-eux😀

    Pour outliers, les aberrations m’ont l’air pas mal comme nom en français, même si je pourrais aussi proposé point fou ou simplement fautes de mesures.

    Et puis, dans le traitement de la mesure, en plus du bruit, tu as aussi les biais, si vraiment tu veux impressionner tout le monde😉

    1. Correction, je cite le laboratoire MATIS, sans insister que ces modélisations 3D de villes, ça commence à faire déjà quelques années que les Systèmes d’Informations Géographiques, équipant notamment les services d’urbanismes des villes sont passés à la 3D.

      Et puis Google Street View, c’est une chose, mais cliquons sur l’icône Google Earth, et les bâtiments sont en 3D et on peut se balader dans la ville.

      Bien sûr, quelle est la part de l’informatique et celle du petit indien qui va modéliser à la main ces données, c’est à vous de deviner…

      Bienvenu dans le futur, bienvenue en 2012🙂

      1. Je n’ai pas dit que ça n’existait pas, j’ai dit que Google serait sans doute le premier à le proposer au grand public. Et quand bien même cela existe dans une certaine mesure, la science ce n’est pas du 0 et du 1, il y a encore un milliard de choses à améliorer dans tous les domaines. Donc dire « la reconstruction de scènes urbaines, c’est bon c’est fait, circulez y’a rien à voir, lol on est en 2012 quand même », c’est un non-sens.

        Dans Google Earth, je peux me tromper mais je doute fort que les bâtiments soient reconstruits automatiquement depuis des scans, a priori ce sont des modèles construits « à la main » (d’autant plus quand ce sont de bêtes cubes – à part pour les monuments historiques).

        Et les « chercheurs qui s’ignorent », je te renvoie à ce que je disais sur la diversité des domaines. C’est bien triste, mais non on ne peut pas connaître les travaux de tout le monde. On se concentre sur ce sur quoi on bosse, ce qui prend déjà un temps fou. En l’occurrence, je ne bosse *pas* sur les scènes urbaines (le dernier paragraphe était un exemple d’ouverture), donc non je n’ai pas fait la biblio sur ce sujet (ceci dit merci pour le lien, c’est toujours intéressant pour la culture).

  3. « Une thèse ? Et tu travailles sur quoi ? »

    En fait, l article n est pas du tout celui que je m attendais à lire, en voyant le tire :

    J ai interprété le titre en
    « Une thèse ? Mais… tu travailles alors ? ou pas ? enfin… je veux dire, à coté de ta thèse ? »
    (qui est un passe-temps, un amusement, comme chacun sait)

    Une question récurrente du site (récemment fermé) http://www.thesedemerde.fr/


    Avec cette fermeture, les thésards qui ont une TDM, un SDM (sujet), un MDM (maitre), une EDM (équipe), n’ont même plus de site spécialisé où se remonter le moral…

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s