Théorème 2: l’application affine 44, AMC sur les 
éléments de A, si elle existe, est inversible si et seulement si FA 
contient au moins 3 points non-alignés. 
La recherche du meilleur ensemble A parmi toutes les 
parties de PgxPr est un probléme combinatoire plus complexe, 
il peut être résolu en associant un coût à chaque partie de 
PrxPr et en recherchant la partie ayant le coût minimal. 
III.3.2 Fonction de coüt 
Il s’agit ici de définir une fonction coût sur l'ensemble 
des parties de PzxPr, qui soit minimale pour l’ensemble 
optimal recherché : 
Soit A une partie de PgxPr, vérifiant les conditions des 
théorèmes 1 et 2, nous pouvons lui associer une transformation 
$4, l'AMC sur les couples de A. La fonction coût que nous 
proposons est la somme de deux termes. Le premier rend 
compte des erreurs commises par la transformation $4 pour 
chacun des éléments de A. Le second favorise les appariements 
en pénalisant d’un coût élémentaire les primitives de la carte 
n’ayant pas été appariées. Finalement, le coût associé à 
l’ensemble A prend la forme suivante : 
> 5p,(0)?+ Xr 
ae A c€ E, 
eit CA n mrs eA- vs (5) 
oü EA est le complémentaire de E4 dans E. 
La division par card (A) permet les appariements 
multiples pour une primitive de la carte ou de l'image SPOT. 
IIT.3.3 Génération et propagation d’ hypothéses 
Le nombre de sous-ensembles de PzxPr (QNM ,avec N 
et M variant de 50 à 100 pour des scènes de 10km x 10km, cf 
tableau 1) n’autorise pas le calcul du coût de chacun d’entre 
eux, une méthode par génération et propagation d’hypothèse 
permet de réduire la combinatoire du problème. 
Un amer étant défini comme l’appariement d’un point de la 
carte et d’un point de l’image SPOT, à chaque couple de 
primitives appariées est associé un amer défini par les centres 
des disques de chaque primitives, que ce soit une 
agglomération ou un carrefour. 
Le principe de la méthode de génération et propagation 
d’hypothèse est le suivant : 
Génération : deux amers quelconques n’ayant pas de point 
commun fournissent une transformation initiale $o, qui est la 
similitude unique définie par ces deux amers (une similitude est 
la composée d’une rotation,d’une homothétie et d’une 
translation, ie. a, = b2 et a2 = —b, dans les équations (1) ). 
Propagation cette transformation $g va permettre de 
déterminer de nouveaux appariements, en acceptant les couples 
de primitives (c , d ) tels que la distance du point $o(c) au 
point d soit inférieure à un seuil donné. Avec ces amers une 
nouvelle transformation ¢; sera calculée. $, est l’application 
affine définie par une AMC sur les amers. Cette procédure est 
itérée jusqu'à la convergence de l'ensemble des amers et de la 
transformation associée. 
Evaluation : le coüt de l'ensemble final d'amers est calculé. 
Toutes les hypothèses possibles étant engendrées et 
propagées, celle conduisant à l' ensemble d' appariements ayant 
le coût le plus faible est conservée. 
Remarque: il est possible, dans notre application, 
d'initialiser le processus de propagation par une similitude, ce 
qui ne nécessite que 2 amers, car la transformation affine finale 
attendue entrée l'image SPOT et la carte est proche d'une 
similitude. C'est-à-dire que les angles de rotations 8; et 6, sont 
peu différents, de même pour les coefficients d'homothétie k 
et k2 (voir figure 6), typiquement : 
388 
louer] Sor OU EE de YO) 
- < e rer 1. 
LE en min ( k; , k) 
Ce processus de génération et de propagation d'hypothéses 
étant défini, il convient de préciser quelles sont les primitives 
qui seront utilisées pour engendrer, propager et évaluer les 
hypothèses. 
III.3.4 Choix d'une stratégie 
L’optimisation du processus de mise en 
correspondance, tant au niveau de la stabilité que du temps de 
calcul, est déterminée par le choix des primitives pour chacune 
des trois phases: génération, propagation et évaluation des 
hypotheses. L'utilisation d'un type de primitive lors de l'une 
de ces trois phases dépend de la stabilité de cette primitive, du 
nombre de ces primitives et de la précision de leur localisation. 
Génération le nombre d'hypothéses engendrées étant 
proportionnel au carré du nombre de primitives de chaque 
image utilisées dans la phase de génération, il est souhaitable 
de resteindre cette phase aux primitives les plus stables. 
D'autre part, il est important que les hypothéses engendrées 
permettent de récupérer d'autres appariements de primitives, ce 
qui nécessite un positionnement relativement fiable des 
primitives, et entraine l'élimination des primitives trop grosses, 
par exemple les villes trop importantes. 
Propagation les primitives utilisées pour propager les 
hypothéses sont déterminantes à la fois pour le temps de calcul 
nécessaire à chaque propagation et pour la qualité du recalage 
final. Supprimer des primitives pour accélérer le processus 
risque de perturber la stabilité de la mise en correspondance. 
Evaluation : les primitives sur lesquelles reposent l'évaluation 
des hypothéses doivent permettrent de rendre compte, via le 
calcul du coût défini par la formule (8), de la qualité du 
recalage obtenu pour chaque hypothése propagée. A notre avis, 
les primitives utilisées pour évaluer ‘une hypothèse doivent 
nécessairement avoir été utilisées pour propager cette 
hypothèses. 
Afin d’appuyer le processus de mise en correspondance sur 
les primitives les plus stables et de limiter les temps de calcul, 
la stratégie retenue ici consiste à engendrer les hypothèses avec 
les seules agglomérations et de les propager et de les évaluer 
avec les deux types de primitives (agglomérations et 
carrefours). 
Remarque : nous avons accordé la même importance au 
primitives extraites de la carte et de l’image SPOT, que ce soit 
les agglomérations ou les carrefours. D’autres stratégies 
peuvent être envisagées où les primitives de l’une ou l’autre 
image auraient un rôle prépondérant. 
Diverses solutions sont envisagables pour réduire les temps 
de calcul. Pour notre application, nous avons choisi de ne pas 
propager les hypothèses pour lesquelles la transformation 
initiale $9 ne vérifie pas les restrictions apportées sur les 
paramètres de la transformation recherchée (voir équations (3)). 
Il ne s’agit pas ici d’une optimisation de la méthode, mais 
d’une simple élimination, avant propagation, des hypothèses 
les plus mauvaises. 
111.4 Calcul de la transformation finale 
Aprés l'étape de mise en correspondance, nous 
disposons d’un ensemble d'appariements de primitives 
provenant de la carte et de l'image SPOT. Le recalage calculé 
à l'aide de la transformation ¢ associée a l’ensemble 
d'appariements reste grossier du fait du manque de précision 
sur la localisation exacte d'une primitive, que ce soit une 
agglomération ou un carrefour (voir le recalage intermédiaire 
sur la figure 11). D’où la nécessité de calculer des amers précis 
à partir des appariements de primitives. Nous proposons ici un 
schéma global pour le calcul d’un amer précis pour chaque 
appariement d’un carrefour de la carte avec un carrefour de 
l’image SPOT. 
L 
après 
effect 
carref 
probl 
AxB 
pour 
agglo 
isomc 
ensen 
plusie 
L 
» Pré 
» Sél 
tec. 
* Cal 
dar 
inte 
L 
les ar 
rigidit 
succe 
des eı 
de pr 
persp: 
III.5 
transf 
points 
Sc 
recala 
Soien 
manu 
AMC 
la mo 
désigr 
Le 
perme 
param 
la m 
points 
IV. 1 
I 
l'appli 
couple 
scene 
10km