Journée annuelle 2009 - Résumés Conférences

Méthodes numériques pour la reconstruction de surfaces à partir de nuages de points
Pierre Alliez

La reconstruction de surfaces est un problème fondamental pour l'ingénierie numérique, l'exploration géologique, et l'imagerie médicale. C'est également un enjeu scientifique important depuis l'évolution rapide des technologies d'acquisition de mesures (palpeurs, scanners, télémètres, photogrammétrie, imageurs).

Dans cet exposé on se limitera au cas de la reconstruction de surfaces à partir de nuages de points. Etant donnée une surface S dont on ne connait qu'une approximation (un échantillonnage) par un ensemble fini de points K, il s'agit de reconstruire une surface homéomorphe à S à partir de K, avec les mêmes propriétés topologiques (nombres de Betti, type d'homotopie) et géométriques (courbures, métrique). Sans connaissance à priori sur S, le problème est bien entendu mal posé: à partir seulement de K il existe une variété infinie de surfaces S proches de K. Une première stratégie consiste à restreindre l'espace de recherche à l'ensemble des surfaces lisses. Une autre consiste à fournir un catalogue explicite de formes élémentaires comme connaissance à priori. Dans une première vague de travaux les spécialistes du calcul géométrique ont réussi à formaliser mathématiquement le problème. Ces résultats ont abouti à des algorithmes efficaces et fournissant une reconstruction fidèle dans le cas de mesures précises et exhaustives.

Toutefois, de nombreux capteurs mesurent les données avec une incertitude importante (on parle de bruit) et de manière incomplète. Le bruit correspond à la fois aux défauts de la chaine d'acquisition et de traitement (bruit optique, bruit électronique, conversions de signaux) et aux conditions d'acquisition (reflets parasites, faisceaux laser tangent à la surface mesurée, interactions laser-matière). Les méthodes de photogrammétrie, quant à elles, peuvent fournir autant de points aberrants (outliers) que de points pertinents (inliers). L'incomplétude des données provient des conditions d'acquisition en termes d'occultations, d'angles variables et plus simplement d'absence de contrôle efficace de couverture. Ce constat a motivé une seconde vague de travaux visant à concevoir des méthodes dites robustes car résistant à la dégradation des conditions d'échantillonnage. Parmi ces travaux, on détaillera deux méthodes procédant par calcul d'une fonction implicite 3D, dont une surface de niveau approche le nuage de points mesuré. La première résout l'équation de Poisson à partir des points initiaux augmentés de normales orientées. Le second résout un problème aux valeurs propres généralisé à partir des points initiaux augmentés de normales non orientées. On positionnera ces méthodes dans le contexte récent de travaux de recherche visant à toujours plus de résistance aux points aberrants.

 

Les surfaces à courbure intégrale bornée au sens d'Alexandrov
Marc Toyanov

Dans les années 1940-1970, Alexandrov et l'"Ecole de Leningrad" ont développé une théorie très riche des surfaces singulières. Il s'agit de surfaces topologiques, munie d'une métrique intrinsèque pour laquelle on peut définir une notion de courbure qui est une mesure de Radon. Cette classe de surfaces a de bonnes propriétés de convergence et elle est remarquablement stable par rapport à diverses constructions géométriques (recollements etc.). Elle englobe les surfaces polyédrales ainsi que les surfaces Riemanniennes de classe C2 ; ces deux classes formant des parties denses de l'espace des surfaces d'Alexandrov. Toute surface singulière qu'on peut raisonnablement imaginer est une surface d'Alexandrov et de nombreuses propriétés géométriques des surfaces lisses s'étendent et se généralisent aux surfaces d'Alexandrov.

Le but de cet exposé est de donner une introduction non technique à la théorie d'Alexandrov, de donner des exemples et quelques-uns des faits fondamentaux de la théorie. Nous présenterons également un théorème de classification des surfaces (compactes) d'Alexandrov.

 

Géométrie et analyse discrètes
Jean-Pierre Réveillès

La nécessité, apparue avec les premiers écrans graphiques des années 80, de traiter et d'afficher au mieux sur ces structures pixellisées les objets géométriques élémentaires, a conduit à introduire et à étudier quelques analogues purement discrets de ceux-ci. L'approche arithmétique (par inéquations diophantiennes) s'est révélée être aussi performante que celles qui mettaient au premier plan les préoccupations de complexité algorithmique, tout en plaçant avantageusement cette problématique dans un champ strictement mathématique.

Les droites et hyperplans discrets définis par les inéquations , où le vecteur et les entiers et sont donnés, qui ont été les premiers tests de validité de cette géometrie discrète, ont rapidement fait naître quelques problèmes spécifiquement discrets comme celui de leur reconnaîssance, puis ceux de la polygonalisation des courbes discrètes et de la polyédrisation des surfaces discrètes.

Les relations évidentes entre ces concepts et les notions très classiques de fractions continues, de groupe spécial linéaire, de fonction génératrice, ou celles plus spécialisées de mots de Sturm ou de polynômes d'Ehrhart ont amené de nombreux chercheurs à revisiter ces concepts sous un angle plus géométrique.

Le traitement numérique (et algorithmique) des objets discrets définis arithmétiquement est également tout à fait distinct des méthodes employées pour approcher leurs analogues construits à l'aide de nombres réels. Toutefois, en suivant l'algorithmique liée à des séquences d'objets discrets convergeant vers leurs analogues continus, ces deux modes de calculs peuvent être mis en relation. Cette technique permet d'introduire les notions discrètes, en particulier de dérivabilité, qui sont au coeur de l'analyse.

 

Curvatures of Discrete Curves and Surfaces
John Sullivan

The basic notions in differential geometry are curvatures, for instance those of a smooth curve or surface in space.  If we approximate the smooth object by a polygonal curve or polyhedral surface, then there are many possible discretizations of curvature, all of which converge to the smooth notion.  The idea behind the relatively new field of Discrete Differential Geometry is that one should pick a discretization which - even at the discrete level - captures some of the properties of the smooth notion, such as integral relations.  We consider the simplest possible examples - the curvature of a curve and the mean and Gauss curvatures of a surface - and use these to show that there is no one best notion of discrete curvature.  Instead, the proper discretization depends on which features of the smooth picture one wants to see at the discrete level.