Majeure "Mathématiques et Informatique"
Enseignement d'approfondissement
"Images: Analyse et Synthèse"
Reconnaissance de Polyèdres
Enseignement d'approfondissement / Majeure math-info

Xavier DECORET
 

françois.decoret@poly.polytechnique.fr

En raison du coût (en temps et en argent) de la modélisation d’un objet en 3 dimensions, les concepteurs d’outils 3D ont recherché et développé des méthodes permettant de « reconstruire » un objet 3D à partir d’un ou plusieurs objets 2D, ces derniers étant facile et peu onéreux à obtenir. Il s’agit en général de reconstituer l’information manquante (la 3ème dimension ou profondeur), en recoupant différentes vues d’un même objet.
Or le cerveau humain est dans certain cas capable à partir d’une seule vue, de reconstruire un objet volumique à partir de sa projection plane.

Ainsi, nous voyons tous un cube sur la figure 1. Et pourtant il existe une infinité d’objets dont la projection donnerait cette image.
Cependant, en se donnant implicitement certaines règles excluant les cas pathologiques, l’œil « voit » la forme générique d’un cube.

Notre objectif est donc de doter une machine d’un tel comportement. Nous nous sommes inspirés pour cela de l’ouvrage de Kokichi Sugihara : « Machine Interpretation of Line Drawings »
 

La reconstruction d'un objet polyédrique à partir d'une scène passe par plusieurs étapes:

Interprétation de la forme
On montre, sous certaines hypothèses visant à éliminer les cas pathologiques, qu'il n'y a que 4 interprétations ou étiquettages possibles pour une arrête:

Si on étiquette chaque arrête, on donne ainsi une idée générale de la forme de l'objet.

On va donc essayer d'attribuer des labels à chaque arrête.
La méthode brutale produirait 4^l étiquettages possible pour l'objet où l est le nombre d'arrêtes.
Une méthode plus pertinente consiste à remarquer que pour une jonction à 3 arrêtes, il n'y a pas 3^4=81 étiquettages possibles mais 12. En attribuant ainsi des labels aux jonctions en respectant la règle locale de cohérence qui dit qu'une arrête doit avoir la même étiquette dans l'étiquettage des 2 junctions qui sont à ses extremités, on réduit drastiquement le nombre d'interpétations.

Ainsi, voici les 4 interprétations possibles pour la figure ci-dessous:

.

Extraction de la structure spatiale

Pour une "forme", c'est à dire une interprétaion ou étiquettage, donné on doit maintenant reconstituer l'information manquante, c'est à dire trouver les valeurs des inconnues suivantes

Ces inconnues sont liées par des relations du type (le sommet i appartient à la face j) et (le sommet k est devant/derrière la face/le sommet l).
Ces relations sont imposées par l'étiquettage et ont la propriété d'être linéaire. On montre alors que la reconstruction se ramène à la résolution d'un système où A et B sont des matrices connues appelées matrices d'incidence et matrice de forme, et x le vecteurs d'inconnues.

Résolution du système

Principalement, il s'agit de résoudre A sous la contrainte imposées par B.
Le rang de la matrice A donne une indication du nombre de degrés de liberté lors de la reconstruction. C'est ces degrés qui traduisent le fait qu'une infinité de polyèdres admettent pour projection l'image initiale.
Dans le cas de l'interprétation en bas à droite de la pyramide, il y a par exemple 7 degrés de liberté:
On peut fixer les 3 paramètres de la face qui constitue l'arrière plan (dont la pyramide est détachée comme l'indique les labels flèches sur les bords!), puis les altitudes des 3 sommets du grand triangle et enfin l'altitude d'un sommet du petit triangle. Les autres sommets sont alors imposés.
Lors du choix de ces degrés de liberté, il faut bien sûr respecter la contrainte B.x > 0.

Voici maintenant quelques photos d'objets 3D reconstitués et visionnés sous geomview.
Cliquez sur une photo pour charger le fichier .OFF descriptif.