Discussion :

[paradize3]

Bonjour!

Une petite question... J'ai MxN 3D points (typiquement 3x3 ou 5x5) regulierement repartis (enfin ils forment une "grille" si on les regarde progete sur le plan XY - le Z varie et la valeur du milieu est la plus grande).
La surface peut etre approximee par une surface bicubique, et je m'interresse au maxima de cette surface...
Pour le moment ce que je fais est tres simple: je subdivise ma grile de facon beaucoup plus fine, je calcule tous les Z intermediaires avec un filtre d'interpolation bicubique, et ensuite je cherche le maxima.

Ca marche tres bien mais j'aimerai si possible obtenir le maxima (avec la contrainte qu'il est sur la grille) de facon plus directe ou plus efficace?

Merci

Greg

[souviron34]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
max = 0
imax = -1
jmax = -1
 
pour tout i de 0 à N
  pour tout j de 0 à M
     si z(i,j) > max
         max = z(i,j)
         imax = i
         jmax = j
     fin si
  fin pour
fin pour

ou alors il y a quelque chose que j'ai pas compris...

[pseudocode]

ou alors il y a quelque chose que j'ai pas compris...

Je pense qu'il veut une solution "sub-pixel", c'est à dire avec des coordonnées non entière.

Ceci dit, si tu connais la surface "bicubique", le point recherché est un zéro de la dérivée.

[souviron34]

Je pense qu'il veut une solution "sub-pixel", c'est à dire avec des coordonnées non entière.

pas sûr

Ca marche tres bien mais j'aimerai si possible obtenir le maxima (avec la contrainte qu'il est sur la grille) de facon plus directe ou plus efficace?

[pseudocode]

pas sûr

C'est vrai que c'est pas clair.

Enfin, je suppose que la "grille" dont il parle n'est pas la même que son patch MxN du départ.

[paradize3]

desole du retard, je veux bien sur dire une resolution sous-pixel J'ai attache un example d'une telle surface (Les etoiles bleues sont les points originaux, la verte est le maxima de la surface d'interpolation).

je vois bien qu'il s'agit de calculer des derivees de la surface etc.. mais j'ai du mal a formaliser!
En gros:
- je cherche a etablir une equation de la surface bicubic, connaissant 9 points au minimum
- resoudre la derivee pour trouver les maxima

J'ai essaye de resoudre avec une equation de surface quadratic (bien plus simple a formaliser hehe), et ca marche assez bien dans la plus part des cas... mais malheureusement pas assez precis dans certains cas.

Merci

[pseudocode]

En gros:
- je cherche a etablir une equation de la surface bicubic, connaissant 9 points au minimum
- resoudre la derivee pour trouver les maxima

Pour définir une surface bicubique, il faut 16 coefficients. Donc 16 points, ou alors 4 points + 12 dérivées, ou ....

[paradize3]

Pour définir une surface bicubique, il faut 16 coefficients. Donc 16 points, ou alors 4 points + 12 dérivées, ou ....

on peut estimer les derivees par differences finies... bref, admettons qu'on a obtenu les 16 coefficients optimaux pour nos n points, et on obtient donc l'eq. de la surface bicubique (cf fichier attache).
Pour trouver le maxima j'aimerai donc resoudre le systeme:

dp/dx = 0 et dp/dy = 0

malheureusement c'est un systeme d'equations cubiques et donc j'ai un peu de mal a resoudre analytiquement...

merci!

Greg

[pseudocode]

malheureusement c'est un systeme d'equations cubiques et donc j'ai un peu de mal a resoudre analytiquement...

Analytiquement, j'ai aussi du mal à le résoudre.

Une solution numérique (genre Newton-Raphson) n'est pas suffisante ?

[paradize3]

mmh j'aurai bien aime une solution analytique qui me donnerai le resultat directos.. mais bon, je vais y aller avec une methode iterative pour le moment... merci quand meme!

Greg

[pseudocode]

mmh j'aurai bien aime une solution analytique qui me donnerai le resultat directos..

Il faudrait demander à un spécialiste, mais je ne suis pas bien sûr que l'on puisse trouver simplement les points critiques d'une fonction multivariable.

[souviron34]

y a toujours un truc que je comprend pas..

Admettons, on fait du sub-pixel.

Tu as bien le pixel contenant le maxima, donc..

Une simple interpolation bilinéaire marchera..

[paradize3]

souviron: non. dans ce cas une surface d'interpolation bicubique correspond mieux a la realite qu'une bilineaire p.e.

Dans dans ce cas il n'y a donc pas de raison que le maxima soit exactement sur un pixel..

[souviron34]

souviron: non. dans ce cas une surface d'interpolation bicubique correspond mieux a la realite qu'une bilineaire p.e.

Dans dans ce cas il n'y a donc pas de raison que le maxima soit exactement sur un pixel..

mais une inerpolation bilinéaire ne te donnera pas un pixel, mais un sous-pixel...


Ce que je dis, c'est que si tu sais que ton maximax est dans le pixel i,j

En faisant une interpolation bilineaire sur (i-1,j-1), (i-1,j), (i-1,j+1),(i,j-1),(i,j),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1), ou n'importe quelle combinaison de 4, tu auras une bonne idée au sous-ixel près..

M'enfin, c'est ce que moi je ferais..

[paradize3]

justement le max n'est pas exactement sur un pixel, mais plutot entre des pixels. Avec une interp bilineaire le max sera bien sur toujours exactement sur un pixel - ce quii ne correspond pas a la realite ...enfin bref j'ai essaye avec une optimisation de newton, et en 2-3 iterations j'ai une solution bien assez precise.

Merci

salutations,

Greg

[souviron34]

justement le max n'est pas exactement sur un pixel, mais plutot entre des pixels.

je crois qu'on ne se comprend pas..

NON le max ne sera pas tjs sur un pixel exact, puisque c'est une interpolation..

Comme l'a dit pseudocode, il te faut de 8 à 16 coeffs...

Mais le résultat ne sera pas sur un pixel, mais sur des fractions X;xxx, y.yyy de pixels..

[paradize3]

Souviron, j'ai mes coefficients, et comme je l'ai dit quelques iterations de newton me donnent une bonne solution, le probleme est donc resolu.

Je reagissait juste a la remarque sur l'interpolation bilineaire que tu avais sugeree: par definition elle ne donnera jamais un maxima entre des pixels - imagine le cas 2D avec trois points, le maxima sera forcement exactement sur l'un des points si tu utilises une interp. lineaire, ce qui ne serait pas le cas avec une courbe du 2eme degre ou plus.

Greg

[souviron34]

Je reagissait juste a la remarque sur l'interpolation bilineaire que tu avais sugeree: par definition elle ne donnera jamais un maxima entre des pixels - imagine le cas 2D avec trois points, le maxima sera forcement exactement sur l'un des points si tu utilises une interp. lineaire, ce qui ne serait pas le cas avec une courbe du 2eme degre ou plus.

J'ai du mal à voir comment a*(x1,y1)+b*(x2,y2)+c*(x3,y3) donnera quelque chose qui tombera sur (x1,y1) ou (x2,y2) ou (x3,y3) si a , b et c sont différents de zéro...

[paradize3]

Souviron,

Je crois qu'on se comprend mal sur quelque chose...
J'ai attaché une image avec trois points et une interpolation quadratique vs linéaire...
on voit bien que le maxima est bien forcément l'un des trois points si on considère une interpolation linéaire?

Greg

[souviron34]

j'avais dit bi-linéaire..