Discussion :

[shrek.romaneo]

Bonjour à tous,

Dans le cadre d'un projet, je dois recréer une surface à partir de 5 points de mesure.

Comme un dessin vaut mieux que milles paroles, le voici :



Les chiffres placés à coté des points rouges correspondent aux valeurs relevées sur ces points.

Je souhaites dans un premier temps passer de 5 points (rouges) à 9 points (rouges + bleus) car j'ai déjà une procédure d'interpolation par spline cubique pour passer des 9 points (rouge + bleus) à plus (genre 25 points).

N'hésitez pas à me contacter si ma problématiques est mal posée

Merci aux âmes charitables qui accepterons de se pencher sur mon problème.

<-------- J'adore ce smiley !!!

[Médinoc]

Je pense que le mieux est de déduire les quatre angles séparément.

Par exemple, pour le coin supérieur droit, tu ne devrais pas avoir besoin du 5 gauche ni du 3, donc tu te retrouves juste à faire un calcul sur un quadrilatère dont tu connais trois coins...

[shrek.romaneo]

Merci Médinoc pour ta réponse rapide, mais je ne vois pas trop comment faire pour calculer les cotés indépendamment les uns des autres.

Pourrais-tu m'éclairer à ce sujet?

Merci bcp ...

[Médinoc]

Ça dépend des données que tu as exactement...
Mais à partir des coordonnées des 4 points + celles du point central, tu devrais pouvoir déterminer ça...

[FR119492]

Salut!
Juste une petite question pour bien comprendre ton problème: est-ce que le rectangle que tu as dessiné est isolé du reste du monde ou est-ce qu'il fait partie d'une "grille" plus vaste?
Jean-Marc Blanc

[shrek.romaneo]

FR119492: Salut!
Juste une petite question pour bien comprendre ton problème: est-ce que le rectangle que tu as dessiné est isolé du reste du monde ou est-ce qu'il fait partie d'une "grille" plus vaste?
Jean-Marc Blanc

Pour répondre à ta question, le rectangle dessiné est "isolé du monde".

(Je mets à jour la figure en fonction de vos remarques, pour ajouter le plus d'info possible).

Merci

[pseudocode]

Pour répondre à ta question, le rectangle dessiné est "isolé du monde".

Là c'est plus de l'interpolation, mais de l'extrapolation.

[Médinoc]

Attends, c'est un vrai rectangle dans un espace 3D?
Je croyais que c'était un parallélogramme dans un espace 2D! (ou 3D, ça ne change pas grand-chose).

[shrek.romaneo]

Désolé de ne pas avoir été clair dès le début.

Effectivement c'est un carré représenté en 3D sur l'image (d'où le repère 3D en haut à gauche).

Et effectivement, encore, mon soucis vient de l'extrapolation (5 vers 9). J'ai employé le terme "interpolation" car l'étape suivante (interpolation 9 vers 100) à déjà été implémentée.

Merci

[Médinoc]

Eh bien, si c'est un carré ou rectangle, il faut déjà être sûr que:

• (0, 0) est bien au milieu du segment [(-10, 0) (10, 0)]
• (0, 0) est bien au milieu du segment [(0, -10) (0, 10)]

Car comme il y a de la redondance, il faut être sûr. Au minimum, si on oublie l'idée de milieu, il faut vérifier que les points sont alignés.

Ensuite, je suis sûr qu'il y a un calcul simple pour à partir de trois points, déduire le quatrième. Pour un rectangle dans le plan, on n'a besoin que de deux points opposés, et avec trois points, dans l'espace, s'il y a un angle droit, il est facile à trouver (du moins, mathématiquement, on peut passer par un produit scalaire. informatiquement, ça peut être plus dûr étant donné les erreurs d'arrondi). À partir d'un triangle, il y a trois parallélogrammes possibles, mais à partir d'un triangle rectangle, il n'y a qu'un seul rectangle possible.

[FR119492]

Salut!
Une idée qui me passe par la tête:

Tu notes
a1 la valeur connue en bas
a2 la valeur connue à gauche
a3 la valeur connue au centre
a4 la valeur connue à droite
a5 la valeur connue en haut

x1 la valeur cherchée en bas à gauche
x2 la valeur cherchée en bas à droite
x3 la valeur cherchée en haut à gauche
x4 la valeur cherchée en haut à droite

Commence par envisager le problème inverse: tu connais les x et tu cherches les a. Par interpolation linéaire, tu as:
x1 + x2 = 2 * a1
x1 + x3 = 2 * a2
x2 + x4 = 2 * a3
x3 + x4 = 2 * a5
x1 + x2 + x3 + x4 = 4 * a3

Ensuite, pour la résolution de ton problème, tu prends les 5 équations à 4 inconnues écrites ci-dessus. Comme la matrice de ce système est rectangulaire, celui-ci est surdéterminé. Pour le résoudre, tu utilises la méthode SVD, ou, ce qui revient au même, la pseudo-inverse de Moore-Penrose. Tu obtiens ainsi la "moins mauvaise" solution.

Jean-Marc Blanc

[OliveK]

C'est bien de l'extrapolation, tout le soucis est dans la fonction avec laquelle tu vas extrapoler, et là il n'y a pas de vérité...

- une extrapolation linéaire comme au dessus te donnera un plan mais qui ne pourra pas passer par tous tes points : il faut trouver A (dimension 3) qui donne Y = [X1 X2 1].A

- pour passer partout il faut utiliser par exemple un polynôme d'ordre 2 qui te donne 5 coefficients à caler avec tes 5 points, ici A est tel que Y = [X1 X2 X1² X2² 1].A

- d'un point de vue géométrique, comme le post précédent en raisonnant sur les milieux des segments et sur les distances aux points correspondants - c'est linéaire, on retrouve le même résultat que l'extrapolation linéaire

- toujours d'un point de vue géométrique, en raisonnant sur chaque sous-rectangle : comme le point (10,10) est le symétrique du point (0,0) par rapport au segment entre les points (10,0) et (0,10) on peut supposer qu'il en est de même pour les points-images, et souhaiter obtenir 4 losanges dans l'espace

Cf les images jointes associées à chaque cas (j'avais une heure à tuer)

Bref l'extrapolation ça dépend vraiment de ce qu'on pense avoir comme allure générale.

[shrek.romaneo]

Merci beaucoup pour tous ces commentaires.

OliveK : Je pense que la 2nd image que tu me proposes représentent le mieux le type d'image que je suis sensé obtenir.
En effet, le point central aura une valeur plus élevée que les points en "périphérie".
Par contre, cela ne sera symétrique comme l'image le suppose mais c'est typiquement le type d'image à obtenir.

- pour passer partout il faut utiliser par exemple un polynôme d'ordre 2 qui te donne 5 coefficients à caler avec tes 5 points, ici A est tel que Y = [X1 X2 X1² X2² 1].A

Par contre je ne vois pas trop à quoi se réfèrent les X1, X2, Y et A dont tu parles.

Pourrais-tu m'éclairer un peu plus la dessus ?

Merci encore....

[souviron34]

comme on te l'a dit, le mieux dans ce cas est une approximation d'un polynôme de degré 2.

Un spline bi-cubique marchera bien..

Tu fais un tableau avec tes 5 points, tu initialises ton spline dessus, et tu utilises la routine d'interpolation pour interpoler...

[OliveK]

Par contre je ne vois pas trop à quoi se réfèrent les X1, X2, Y et A dont tu parles.

J'ai appelé X1 et X2 les coordonnées des points du plan, sur ton graphe ça correspondrait plutôt à x et y.
Mon Y, c'est la hauteur correspondante, autrement dit ton z.
A c'est le vecteur des coefficients du polynôme interpolé. Y = XA est une notation usuelle en régression linéaire.

Ça veut dire que tu dois trouver les nombres a1, a2, a3, a4, a5 tels que pour tes 5 points tu aies :
a1.x + a2.y + a3.x² + a4.y² + a5 = z.

Ça te donne un système de 5 équations (tes 5 points) à 5 inconnues (les a1, a2...), il y a une solution unique (dans ce cas) qui correspond à la 2ème image de mon précédent post. C'est une régression linéaire dont la solution s'obtient avec une pseudo-inverse, ou bien en fonction de ton niveau, avec le pivot de Gauss.

Ensuite, pour trouver le z correspondant à un nouveau couple (x,y) il suffit d'appliquer ce polynôme dont tu viens de déterminer les coefficents, si l'allure de la surface te convient tu obtiendras les points que tu veux. Note que tu n'auras pas besoin de l'interpolation par spline cubique, puisque tu auras déjà l'équation de la surface qui correspond à un simple polynôme de degré 2. Interpoler dessus ne ferait que retrouver cette équation.

L'image n'est pas totalement symétrique, la surface contient les 5 points rouges qui ne présentent a priori aucun axe de symétrie.

[shrek.romaneo]

Merci OlivK pour tes conseils.

Je viens d'appliquer ta méthode à un cas concret (qui me sert de test de validation de l'algorithme).



Comme tu peux le voir, je me retrouve avec 25% d'erreur sur la valeur en haut à droite.

Je viens de voir que sur la ligne [18,611 ; 19,366 ; 22,615] on a pas une "parabole inversée" (orientée vers le bas) mais une parabole "non inversée" (ou orientée vers haut).
Je suppose que ça doit y faire ...

Du coup, je me demande si cette extrapolation est celle qui me convient.

Merci pour votre aide...

[OliveK]

Les 5 points que tu indiques correspondent à une parabole pure (et pour cause, il y a 5 coefficients à régler avec 5 points, donc ça passe pile-poil).
Après, si tu as d'autres points où la surface devrait passer, utilise-les aussi pour déterminer la surface.
Tes 5 points du début ne sont pas assez représentatifs, il est plutôt difficile de deviner une parabole dans un sens là où les 5 points donnent une parabole dans l'autre. C'est un peu comme si tu voulais trouver l'équation d'une courbe complexe en ne disposant que de points alignés.

[souviron34]

je me permet cependant de ré-itérer : spline bi-cubique...

[shrek.romaneo]

je me permet cependant de ré-itérer : spline bi-cubique...

excuse-moi, après quelques recherches sur notre ami , je n'ai pas trouvé d'info concrètes sur l'utilisation de spline bi-cubique.

Pourrais-tu m'éclairer un peu plus la dessus?

Merci bcp

[souviron34]

Un coup de Google (en anglais), donne en moins de 3 secondes :

tu trouveras plein d'explications et de pointeurs et de code au moins là-dedans :

http://en.wikipedia.org/wiki/Bicubic_interpolation

plus quelques trucs comme (je le re-dis, c'est une source excellente) :

GraphicsGems

Plus Numerical Recipes et autres...

(et ça donne aussi Béziers, etc etc)