Discussion :

[vinzzzz]

Hello,

Je souhaite superposer au mieux deux formes géométriques ayant les propriétés suivantes:
- Ces formes sont des triangles quelconques ou des quadrilatères
- Chaque sommet possède donc une position, ainsi qu'un "champ de force" autour de celui-ci, l'intensité de la force en un point D de l'espace diminuant avec la distance au sommet en utilisant une fonction gaussienne

Je souhaite donc pouvoir aligner deux formes, non pas en minimisant le RMSD entre les deux figures (auquel cas l'algorithme de Kabsch est suffisant à ma connaissance), mais en maximisant la covariance des champs superposés.

Quelqu'un connaîtrait-il un algorithme permettant de faire ça ?

Mes recherches n'ont rien donné... Pour le moment je vois bien un algo génétique (ou équivalent), mais je me dit qu'il existe peut être quelque chose de plus formel et surtout performant.

Merci!

[Invité]

salut,

Donc déjà un peu en retard.
histoire de pas respecter le bon vieil adage et d'être cohérent, je vais pas attendre la nuit.
On note P(a,b)=e^(-(x-a)^2-(y-b)^2)
qui correspond au potentiel scalaire exercé par le point P de centre a,b.

On a en x,y le potentiel scalaire G=somme_i P(a_i,b_i)
où notre polygone est définit par les i points P(a_i,b_i)

Ensuite la covariance est donnée par cov(X,Y)=E(XY)-E(X)E(Y)
Si on discrétise G, ca équivaut à sommer sur x et y les occurrences G pour les couples x,y.

ie E(X)=int xyG(x,y)dxdy=somme_i int xyP(a_i,b_i)dxdy
Le calcul de cette dernière se décompose assez trivialement sur x et y:
I = int xyP(a_i,b_i)dxdy = int ye^(-(y-b_i)^2 [int (xe^(-(x-a_i)^2)dx]dy
I = a_ib_iPi
cad E(X)=Pisomme_i a_ib_i
De l'autre côté avec la figure qu'on translate d'un vecteur (u,v) afin de superposer pour maximiser (blabla), on a
G(x,y,u,v) = somme_j P(a_j-u,b_j-v) où j décrit l'ensemble des points du polygone
on a de même
E(Y)=int G(x,y,u,v)dxdy = somme_j int P(a_j-u,b_j-v)dxdy
et on déduit assez facilement
E(Y)=Pisomme_j (a_j-u)(b_j-v)

Reste à calculer E(X,Y)
l'intégrale revient à sommer le terme sur dxdy
P(a_i,b_i)P(a_j-u,b_j-v)
idem
E(X,Y)=somme_i somme_j int P(a_i,b_i)P(a_j-u,b_j-v) dxdy
calcul de J=int P(a,b)P(c,d) dxdy
J=f(u,v)1/16(a+c+u)(b+c+d)
avec f(u,v) = e^(1/2(a+c+u)^2-a^2-(c+u)^2 + 1/2(b+d+v)^2-b^2-(d+v)^2)

Reste ensuite à chercher le gradient de tout ce beau monde...
A supposer qu'il n'y ait pas d'erreurs de calculs et que l'espérance de X est bien celle calculée (xyP(a,b)).