Projet Réalisé par David
Sebag (promo 97)
Le projet à pour but de reproduire ce que le cerveau humain fait si bien : comprendre une représentation planaire d'un objet polyédrique, ou autrement dit, d'extraire l'information de profondeur d'une image d'après ce qu'elle représente.
Pour cela, nous suivrons la méthode développée par Kokichi Sugihara dans Machine Interpretation of Line Drawings.
La première étape consiste à trouver une interprétation de la figure. Cela peut être réalisé en associant à chaque arête une étiquette. Elles sont au nombre de quatre :
|
 |
Si on se restreint alors à des trièdres par exemple ( pas plus de trois arêtes ne se joignent en un même sommet ), chaque sommet peut a priori être étiqueté de 80 façons différentes. Ce qui, pour une figure simple comme un cube qui contient 7 sommets visibles, conduit à vérifier 80^7 étiquetages ! Heureusement, toutes les jonctions ne sont pas réalisables et seules 16 parmi elles le sont. Cela réduit fortement le dictionnaire des jonctions et permet l'étiquetage d'une figure en un temps raisonnable.
Pour un tétraèdre, il existe 3 étiquetages possibles obtenus simplement par un algorithme de relaxation. Il représente respectivement : un tétraèdre seul dans les airs, un tétraèdre posé sur une table et un "sol" dont un trou aurait été creusé en forme de tétraèdre.
|
|
|
|
La seconde étape consiste à trouver, à partir de l'étiquetage d'une figure, l'information manquante. A chaque sommet puis chaque arête est associée quelques équations et inéquations mettant en évidence l'information contenue dans l'étiquetage. Les inconnues sont les côtes des sommets et les coefficients des plans des faces. Le système obtenu est de la forme : Aw = 0 et Bw > 0, où A et B sont deux matrices et w est le vecteur inconnu. Il est résolu simplement par la méthode du simplexe. Le résultat est ensuite écrit dans un fichier au format OFF pour visualisation.
D'autre part, si l'acquisition de l'image se fait par caméra CCD par exemple, il se peut que la position des sommets soit légèrement différente de ce qu'elle devrait. Il se peut alors que le système ne possède plus de solution et donc que la figure soit jugée incorrecte. Une méthode est donc proposée ici pour pallier à cet inconvénient.
Elle consiste à trouver un ensemble de contraintes pour lesquels le système possède une solution. La position des sommets concernés est obtenue par intersection des plans dont les équations sont solutions du système "allégé".
Voici ce qui est obtenu pour quelques figures.
|
. |
|
|
|
|
Dans le cas d'une pyramide dont le sommet à été tronqué, une condition nécessaire à la reconstructibilité est que les arêtes "issues" du sommet soient concourantes. Si ce n'est pas le cas (comme ci-dessous) une correction est effectuée, si bien que cette propriété est retrouvée sur la figure corrigée.
