Discussion :

[ocroquette]

Bonjour,

je travaille sur le problème concret suivant, et j'avoue ne pas savoir où commencer (les études sont lointaines...)...

Soit un ensemble de N images, par exemple, des bouts de cartes routières. Le but est de coller ces bouts de cartes ensemble pour constituer une carte plus grande. Pour cela, un opérateur humain fournit des points de référence sur des paires de sous-cartes. Par exemple, il situe un croisement sur la carte 1 ainsi que la carte 2, un passage à niveau visible sur la carte 1 et 3, et un château d'eau visible sur la carte 2 et 3...
Je cherche un algorithme qui permet de trouver le collage optimal des sous-cartes, basés sur les points de références fournis.

En termes plus mathématiques, le positionnement des sous-cartes est une matrice de transformation. On a N matrices (une pour chaque image) : M1..Mn

Pour chaque point, on a (toujours avec l'exemple ci-dessus)
("=~" veut dire ici "proche de")

M1 . (coord croisement dans image1) =~ M2 . (coord croisement dans image2)
M1 . (coord passage à niveau dans image1) =~ M3 . (coord passage à niveau dans image3)
M2 . (coord château d'eau dans image2) =~ M3 . (coord château d'eau dans image3)

Bien sûr, il faut bien plus que 2 points pour placer 3 images, mais il se peut que l'utilisateur en donne bien plus, ce qui a pour but de diminuer l'impact des erreurs de saisie ou dans les cartes.

Dans le cas qui m'intéresse, les matrices M sont la multiplication de :

• une matrice de translation
• une matrice de rotation
• une matrice d'homothétie

Mon but est donc de trouver un algorithme qui permette de trouver la solution optimale. Au niveau de la métrique, je pense à la somme des distances (ou le carré) entre la référence et la solution :
dist( M1 . (coord croisement dans image1), M2 . (coord croisement dans image2) ) + ...

Avez-vous connaissances de tels algorithmes, ou bien des mots-clés qui m'aideraient dans ma recherche ?

Merci d'avance

Olivier



les points de référence et leur emplacement avec l

[Nebulix]

chaque pt d'intérêt q, de coordonnées x[q,m],y[q,m] dans la carte m aura
dans la carte globale les coordonnées ;
X[q,m]= TX[m]+h[m]*(x[q,m]*cos(r[m])-y[q,m]*sin(r[m]))
...
où TX[m],TY[m] la translation de m, h son homothetie, r sa rotation
yaka minimiser la somme des(X[q,m]-X[q,m'])²
On risque des pb de convergence si on veut tout faire d'un coup. Il vaut mieux
commencer par des paires et faire éventuellement un fit global à la fin.
Evidemment TX[1],ty[1],r[1]=0, h[1]=1