Estimation paramétrique multi-modèle robuste: une introduction

A. C. Belon

Nous revisitons ici une méthode d'estimation paramétrique utilisées en vision par ordinateur: une variante de la méthode de Kanatani, présentée ici comme un simple problème d'optimisation. On utilise :

• des équations de mesures et des contraintes sur les paramètres non linéaires,
• une stratégie d'estimation robuste en présence de mesures erronnées,
• la mise en concurrence de plusieurs modèles au sein d'une hiérarchie.

Nous allons fournir ici une présentation résumée de [1,2] peut-être plus accessible et en discuter les implications. Cette méthode utilise un algorithme de projection basé sur des décompositions de Cholesky permettant une résolution numérique locale stable et efficace de l'ensemble des équations de contraintes non linéaires. Un module d'estimation robuste de paramètres appartenant à une hiériarchie de modèles y a été intégré à partir de cet algorithme initial.

Introduction

Les principaux problèmes rencontrés lors de l'estimation de paramètres viennent du fait que l'on doit prendre en compte différents aspects.

1. L'estimation est non linéaire.
   En effet, les objets géométriques et cinématiques ne sont pas représentés par un simple vecteur dans un espace euclidien. Pour paramétriser un objet, il faut donc :
   • utiliser différentes représentations et en changer au cours du processus d'estimation,
   • ou introduire des contraintes dans la représentation, en utilisant des équations implicites, ce que nous faisons ici.

2. Les mesures sont approximatives et contiennent des artefacts.
   Les mesures obtenues sont souvent à la fois :
   • approximatives (bruitées, pas toujours précises,...),
   • elles contiennent des artefacts (outliers = mesures erronées, données aberrantes,...),
   • ou contiennent un mélange d'objets différents (inliers = plusieurs groupes de mesures sont mélangés et doivent être distingués).

3. La singularité de certaines données.
   Un ensemble de données peut être singulier du fait que :
   • le paramètre n'est pas défini dans une situation donnée,
   • l'ensemble des données ne permet pas d'obtenir une estimation valable (par exemple, il n'est pas possible d'estimer un plan si tous les points donnés sont colinéaires).
   On veut donc pouvoir détecter ces singularités afin d'estimer un modèle plus spécifique.
   La recherche d'un modèle minimal est aussi recommandée car, moins il y a de paramètres à estimer, plus le nombre de mesures requises est faible et plus l'estimation est numériquement robuste.
   

Utilisation de paramètres physiques

On veut aborder le problème de l'estimation non linéaire en utilisant un critère de minimisation.
Il apparaît qu'une méthode simple mais spécifique, basée sur une spécification des paramètres physiques introduits dans le processus peut être plus efficace que des algorithmes de minimisation sophistiqués.
L'idée principale est de représenter l'objet paramétré par un vecteur des paramètres dont la variation est considérée étape par étape, ce qui est une stratégie appropriée pour des estimations locales, des adaptations à des variations d'échelle limitée à une valeur par défaut, une estimation interactive où l'estimation initiale donnée par l'utilisateur est à redéfinir, des traitements de suivi, ...

Plus précisément, on propose qu'au niveau de la spécification, chaque valeur numérique du paramètre à estimer
(i) soit bornée i.e. $q^i$ et (ii) ait une précision finie $q_{min}^i \le q^i \le q^i_{max}$ i.e. $q^i_\epsilon \ll q^i_{max} - q_{min}^i$

A côté de ces spécifications, on va associer à un tel paramètre ``physique'' :
(iii) une valeur par défaut $\forall \epsilon^i, \mid \epsilon^i \mid < q^i_\epsilon, q^i \equiv q^i + \epsilon^i$ plus un
(iv) nom et une
(v) unité physique(seconde, pixel, ...).

Résoudre le problème en tant que projection locale

Position du problème

On considère le problème ``simple'' d'estimer une quantité statique ${\bf q}$ d'un ensemble de $M$ mesures ${\bf m}_i$.

Figure 1: Estimation d'un paramètre.

Plus précisément, on veut estimer une quantité vectorielle réelle à $n$ dimensions, soit un paramètre ${\bf q} \in {\cal R}^n$, étant donnés :

• un ensemble de $p$ contraintes implicites, non linéaires que l'on écrit ${\bf c}_0({\bf q})=0_p$ ; ainsi, les paramètres appartiennent à un espace spécifique ${\cal C}$, défini par ces équations.
• une estimation initiale approximative ${\bf q}_0$, i.e. on considère que ${\bf q}$ est proche de ${\bf q}_0$ pour une distance donnée $\vert\vert{\bf q} - {\bf q}_0\vert\vert^2_{{\bf Q}_0}$.
• un ensemble de $M$ mesures approximatives $({\bf m}_1, \cdots, {\bf m}_i, \cdots, {\bf m}_M)$ avec ${\bf m}_i \in {\cal R}^{n_i}$,
  . on considère que les vraies mesures $\bar{\bf m}_i$ sont proches de celles observées ${\bf m}_i$ pour une distance donnée $\vert\vert\bar{\bf m}_i - {\bf m}_i\vert\vert^2_{{\bf Q}_i}$
  . et, pour chaque mesure, un ensemble de $p_i$ équations de mesure ${\bf c}_i({\bf m}_i, {\bf q})=0_{p_i}$ définit la relation entre mesure et paramètre.
  

de telle sorte que les mesures approximatives sont corrigées par l'algorithme comme schématisé ici:

Figure 2: Description du problème d'estimation.

La notion de données ``approximatives'' est formalisée en utilisant les semi-distances quadratiques :

$$\vert\vert{\bf x} - {\bf y}\vert\vert^2_{\bf Q} = ({\bf x}-{\bf y})^T{\bf Q}({\bf x}-{\bf y})$$

pour $x \in {\cal R}^{n}$ et $y \in {\cal R}^{n}$ où Q est une matrice symétrique semi-définie positive. On l'appelle matrice d'information quadratique.
Si aucune estimation initiale n'est disponible, on peut simplement écrire $\bf {q}_0 = \bf {Q}_0 = 0$.

Définir l'estimation en tant que problème de minimisation

On peut formaliser le problème en tant que problème d'optimisation, c'est-à-dire estimer le paramètre $\tilde{\bf q}$ et les mesures $(\tilde{\bf m}_1, \cdots, \tilde{\bf m}_i, \cdots, \tilde{\bf m}_M)^T$ qui :

• minimisent la somme des distances définies :
  
  $$\mbox{min}_{(\tilde {\bf q}, \tilde{\bf m}_1, \cdots, \tilde{... ...vert\vert \tilde{\bf m}_i - {\bf m}_i \vert\vert^2_{{\bf Q}_i}$$
  
  

• étant données les différentes équations :
  
  $${\bf c}_0(\tilde{\bf q}) = 0 \;\mbox{et}\; \forall i \in \{1..M\} \; {\bf c}_i(\tilde{\bf q}, \tilde{\bf m}_i) = 0$$
  
  

De manière équivalente, le problème d'estimation peut être formulé comme un critère composé de multiplicateurs de Lagrange ${\bf\lambda} = ({\bf\lambda}_0, \cdots, {\bf\lambda}_i, \cdots)^T$ :

$$\mbox{min}_{(\tilde {\bf q}, \tilde{\bf m}_1, \cdots, \tilde... ...mbda}_i^T \, {\bf c}_i(\tilde{\bf q}, \tilde{\bf m}_i) \right]$$ (1)

tandis que, dans le cas optimal ${\cal L}^2 = {\cal L}^2_\lambda$ peut toujours être écrit, pour une matrice $\tilde{\bf Q}$ donnée :

$${\cal L}^2 = {\cal L}^2(\tilde{\bf q})+ \frac{1}{2} \vert\ve... ...e{\bf Q}} + o(\vert\vert {\bf q} - \tilde{\bf q} \vert\vert^2)$$ (2)

Quantifier la précision de l'estimation

Dans cette dernière équation, on ne définit pas seulement l'estimation du paramètre $\tilde{\bf q}$, mais aussi une distance quadratique du paramètre estimé paramétré par $\tilde{\bf Q}$. Cela permet d'évaluer la précision de l'estimation comme une distance quadratique.
La méthode est assez directe bien qu'un peu compliquée :

$$\tilde{\bf Q} = {\bf Q}_0 + \sum_{i=1}^M \left.\frac{\partia... ...artial {\bf q}}\right\vert _{(\tilde{\bf q}, \tilde{\bf m}_i)}$$ (3)

où les notations ${\bf M}^+$ et ${\bf M}^-$ sont définies dans la section suivante.

Normaliser le critère estimé

Le problème d'estimation de ${\bf q}$ a $n$ inconnues et $p$ équations. Il y a donc $n-p$ degrés de liberté.
De plus, pour chaque mesure ${\bf m}_i$, il y a $p_i$ équations de contrainte donc chaque mesure du biais ${\bf\upsilon}_i= \tilde{\bf m}_i - {\bf m}_i$ a $p_i$ degrés de liberté.
Une valeur normalisée du critère est donc :

$$\frac{{\cal L}^2}{d} \;\;\;\mbox{with}\;\;\; d = n-p+\sum_{i} p_i$$ (4)

où on a divisé par le nombre total de degrés de liberté.

Pourquoi un tel formalisme?

Cette façon de définir l'estimation de paramètres vient du fait que :

• l'estimation de paramètres est performante même s'il y a trop (l'information est redondante) ou trop peu (le paramètre n'est que partiellement observable) de mesures,
• on peut combiner des mesures de géométrie ou de dynamique différentes, en utilisant les distances normalisées.

Cette estimation est un problème de projection

Puisque nous devons minimiser ce critère en respectant à la fois les estimations de paramètres et de mesures, le problème précédent peut être réécrit en utilisant les notations précédentes :

$$\mbox{min}_{\bf x} \mbox{max}_{\bf\lambda} \; {\cal L}^2_\la... ...0 \vert\vert^2_{\bf Q} + {\bf\lambda}^T \, {\bf c}({\bf x})$$ (5)

avec ${\bf x}_0 = ({\bf q}_0, {\bf m}_1, \cdots, {\bf m}_i, \cdots, {\bf m}_M)$ et ${\bf x} = (\tilde{\bf q}, \tilde{\bf m}_1, \cdots,\tilde {\bf m}_i, \cdots, \tilde{\bf m}_M)$ ; ainsi ${\bf c}({\bf x}) = ({\bf c}_0 ({\bf q}), \cdots, {\bf c}_i ({\bf q}, {\bf m}_i),\cdots)$ si on suppose que ces équations sont deux fois différentiables, puisque ${\bf Q} = \left(\begin{array}{ccc} {\bf Q}_0 & {\bf0} & \cdots \\ {\bf0} & {\bf Q}_1 & \cdots \\ \cdots & \cdots & \cdots \\ \end{array} \right)$ est une matrice diagonale.

Ainsi, le problème est un simple problème de projection, i.e. le critère donné signifie qu'on veut trouver la quantité ${\bf x}$ (i) la plus proche de ${\bf x}_0$ pour la distance quadratique paramétrisée par ${\bf Q}$ et (ii) dans l'ensemble ${\cal C}$ défini par ${\bf c}({\bf x})=0$, comme schématisé dans la figure suivante :

Figure 3: L'estimation non linéaire en tant que problème de projection.

Ce problème a une solution unique si ${\cal C}$ est un ensemble convexe ou linéaire et, on a une solution locale si ${\cal C}$ est, en quelque sorte, régulier, par exemple si la fonction ${\bf x} \to {\bf c}({\bf x})$ est deux fois différentiable avec des dérivées du second ordre finies dans un voisinage de ${\bf x}_0$ contenant la projection.

Résolution au premier ordre

On considère l'approximation linéaire des équations non linéaires autour d'un point ${\bf x}^\bullet$ :

$$0 = {\bf C} \, {\bf x} - {\bf d} + o(\kappa \vert\vert{\bf ... ...bf d} = {\bf C} \, {\bf x}^\bullet - {\bf c}({\bf x}^\bullet)$$ (6)

où $\kappa$ représente l'amplitude de la dérivée au second ordre de ${\bf c}({\bf x})$, associée à l'équation normale du critère en ${\bf x}^\bullet$ :

$$0 = \frac{\partial {\cal L}^2_\lambda}{\partial {\bf x}}^T = {\bf Q} \, ({\bf x} - {\bf x}_0) + {\bf C}^T \, {\bf\lambda}$$ (7)

On obtient un algorithme effectif permettant de calculer ${\bf x}$ en tant que solution par itération du système linéaire approximatif :

$$\left(\begin{array}{cc} {\bf Q} & {\bf C}^T \\ {\bf C} & ... ...ay}{c} {\bf Q} \, {\bf x}_0 \\ {\bf d} \end{array}\right)$$ (8)

On introduit quelques améliorations à cette méthode:
(a) utiliser des quantités partiellement définies,
(b) travailler avec des ensembles d'équations redondants ou singuliers,
(c) permettre, dans certains cas, la convergence de la méthode vers une valeur, pas nécessairement optimale mais, au moins, une estimation très réaliste.

Décomposition en racines carrées des matrices symétriques semi-définies positives

La décomposition de Cholesky, ou en racines carrées, d'une matrice ${\bf S}$ symétrique définie positive est un produit de matrices tel que ${\bf S}={\bf LL^T}$, où ${\bf L}$ est une matrice triangulaire inférieure On définit deux généralisations de la décomposition standard, dans le cas où la matrice n'est pas définie positive :

${\bf S}^+$ La décomposition en racines carrées ``la plus proche''.

Il s'agit ici de la décomposition en racines carrées d'une matrice ${\bf S}^+ = {\bf S}+\upsilon{\bf e}_k{\bf e}^T_k$ pour un $\upsilon$ minimal.

${\bf S}^-$ La décomposition en racines carrées ``réduite''.

C'est la décomposition en racines carrées de la sous-matrice de ${\bf S}$ pour laquelle les lignes et les colonnes dont les éléments diagonaux sont petits, sont supprimés.

Calcul du projecteur local

L'équation (7) nous donne : ${\bf x} = {\bf x}_0 - {\bf Q}^+ \, {\bf C}^T \, {\bf\lambda}$ et, en considérant l'équation (6) en ${\bf\lambda}$ : $({\bf C} \, {\bf Q}^+ \, {\bf C}^T) \, {\bf\lambda} = {\bf C} \, {\bf x}_0 - {\bf d} + o(\kappa \vert\vert{\bf x} - {\bf x}^\bullet\vert\vert)$ ,
on obtient la forme explicite :

$$\begin{array}{rcl} {\bf x} &=& {\bf P}_{{\bf x}_0}({\bf x}... ...f C}^T)^- \, ({\bf C} \, {\bf x}_0 - {\bf d})\\ \end{array}$$ (9)

On peut alors estimer l'erreur au premier ordre :

$${\cal E}^2 = \vert\vert{\bf x} - \bar{\bf x}\vert\vert^2_{\b... ...rt) + o(\kappa \vert\vert{\bf x} - {\bf x}^\bullet\vert\vert)$$ (10)

$\bar{\bf x}$ étant une estimation non biaisée de ${\bf x}$, i.e. $c(\bar{\bf x})=0$.

Itération non linéaire et convergence

Dans le cas où on obtient la convergence, on peut calculer les séries ${\bf x}_{n+1} = {\bf P}_{{\bf x}_0}({\bf x}_n)$. Pour éviter que l'estimation devienne instable, on propose d'utiliser l'algorithme :

$$\begin{array}{ll} \mbox{\bf Input :} & {\bf x}_0, {\bf Q},... ...\bf x}_{n} - \bar{\bf x}\vert\vert^2_{\bf Q} \\ \end{array}$$ (11)

qui permet de trouver un point proche de l'évaluation précédente. On voit, en effet, qu'il s'agit de calculer ${\bf x}_n = (1-\alpha) \, {\bf x}_{n-1} + \alpha \, {\bf P}_{{\bf x}_0}({\bf x}_{n-1})$ pour $\alpha=1,1/2,1/4,\cdots$.

Interface de ce modèle d'estimation

A l'entrée :

• une estimation initiale et un ensemble de mesures :
  ${\bf x}_0 = ({\bf q}_0, {\bf m}_1, \cdots, {\bf m}_i, \cdots, {\bf m}_M)$,
• leur matrice d'information quadratique : $({\bf Q}_0, {\bf Q}_1, \cdots, {\bf Q}_i, \cdots, {\bf Q}_M)$,
• les équations de mesure et celles du paramètre :
  ${\bf c}({\bf x}) = ({\bf c}_0 ({\bf q}), \cdots, {\bf c}_i ({\bf q}, {\bf m}_i),\cdots)$, avec ${\bf x} = ({\bf q}, {\bf m}_1, \cdots, {\bf m}_i, \cdots, {\bf m}_M)$.

En sortie :

• un paramètre estimé et les mesures corrigées :
  $\tilde{\bf x} = (\tilde{\bf q}_0, \tilde{\bf m}_1, \cdots, \tilde{\bf m}_i, \cdots, \tilde{\bf m}_M)$,
• la matrice d'information quadratique $\tilde{\bf Q}$ en fonction du paramètre estimé,
• l'erreur résiduelle ${\bf\upsilon}^2$ sur l'estimation,
• la distance normalisée ${\bf D}^2$ à partir de l'estimation d'origine.

Résoudre le problème en tant qu'estimation locale robuste

On implémente une méthode d'estimation aléatoire. On sélectionne aléatoirement un ensemble de mesures, en espérant qu'une d'entre elles, au moins, ne contient pas d'outlier. On détectera le ``bon'' échantillon du fait que son estimation semble la plus cohérente.

Implémenter une méthode d'estimation aléatoire

1. On sélectionne un nombre minimal de mesures $M$, telles que $n = p+\cdots+p_i+\cdots$ sans information initiale, i.e. ${\bf Q}_0=0$. Cela suppose ${\bf m}_i = \tilde{\bf m}_i$. En résolvant le problème de projection, on obtient une estimation $\tilde{\bf q}$ du paramètre, compatible avec cet ensemble de mesures. On peut estimer la probabilité d'avoir sélectionné un ensemble correct de mesures en fonction de $\nu$, pourcentage de mesures valides et de $T$, le nombre d'échantillonnages :
   

   $$P = \left[1 - \left[ 1 - \left( 1 - \frac{\nu}{100} \right)^{M} \right]^{T} \right]$$ (12)

   
   

2. Avant cela, on calcule, pour chaque mesure, un indicateur de sa cohérence par rapport au paramètre estimé. On peut facilement se servir de l'erreur quadratique normalisée pour la i^ème mesure :
   

   $${\cal L}_i^2 = \frac{\vert\vert {\bf m}_i - \tilde{\bf m}_i \vert\vert^2_{{\bf Q}_i} + {\cal E}_i^2}{p_i}$$ (13)

   
   

3. Pour estimer la validité du $\tilde{\bf q}$ trouvé, les stratégies utilisées sont :
   • soit trouver un nombre suffisant de ``bonnes'' mesures en comptant le pourcentage de mesures $\nu$ dont l'erreur est au-dessous d'un seuil fixé.
   • soit trouver une erreur suffisamment petite en considérant l'erreur maximale des $\nu\%$ premières mesures qui ont la plus petite erreur.
   Dans ces deux cas, on doit :

   (i)

   choisir un nombre fixé $T_{max}$ d'itérations et on prend la meilleure mesure.

   (ii)

   réitérer jusqu'à obtenir une estimation valable.

Définir la validité d'une estimation

Les méthodes robustes permettent d'éliminer facilement les outliers mais cela ne marche pas s'il y a plusieurs ensembles d'inliers, c'est-à-dire si la distribution est multi-modèles.

On suppose que si l'on a une distribution multi-modèles et une estimation qui combine plus d'une distribution ou qui inclut des outliers, l'histogramme d'erreur sera plus large autour de zéro tandis que, pour un ensemble unique d'inliers, l'histogramme sera plus reserré autour de zéro.

Figure 4: La forme de la distribution de l'erreur en présence d'outliers.

Une telle distribution se caractérise par :

1. $\alpha$, l'amplitude de la distribution en zéro,
2. $\gamma$, la convexité de la distribution en zéro,
3. $\beta$, le biais introduit par les outliers en zéro.

On veut maximiser à la fois $\alpha$ et $\gamma$.

La validité du modèle peut être définie par :

$${\cal R} = \frac{1}{M} \, \left[ \mu_0 - 2 \, \frac{\mu_1}{{\cal L}^2_\bullet} \right] < 1$$ (14)

Détecter une bonne estimation

Il n'y a pas de solution générale pour savoir quand arrêter le processus. Voici différentes stratégies :

Parallelisation.

On fait tourner le process avec une priorité qui décroît avec le temps. On fait en sorte d'avoir rapidement une estimation plausible et on continue s'il reste du temps.

Interaction de l'utilisateur.

A chaque nouvelle solution trouvée, celle-ci peut être présentée à l'utilisateur qui peut l'accepter ou/et continue le process.

Seuillage automatique

On peut utiliser la meilleure courbe de validité estimée pour déterminer automatiquement un seuil.

(i)

soit on stoppe quand il n'y a plus d'amélioration,

(ii)

soit on détecte un saut dans la courbe qui dénote un ensemble de bonnes mesures.

Affiner l'estimation

Finalement, on affine l'estimation de paramètres sur les mesures dont l'erreur est au-dessous du seuil, en reprenant la minimisation de ${\cal L}^2$.

Utiliser une hiérarchie de modèles afin d'estimer les paramètres

Minimiser le critère non linéaire ne suffit pas à obtenir une bonne estimation d'un paramètre :

1. Estimer un paramètre ne signifie pas seulement calculer une valeur numérique mais choisir quel modèle correspond le mieux aux données.
2. Puisque l'on trouve seulement une estimation locale du paramètre, la condition initiale est déterminante car le processus de minimisation peut ne pas converger.

Définir une hiérarchie de modèles

Pour faire face à ces deux problèmes, on utilise un ensemble de modèles pour effectuer l'estimation de paramètres:

1. Chaque problème d'estimation doit avoir un modèle nul comme référence (modèle avec le plus de contraintes).
2. Chaque modèle est une généralisation d'autres modèles (ses parents) en enlevant ou remplaçant certaines contraintes.

Il y a aussi un modèle général sans équation (et sans intérêt!).

Figure 5: Représenter une hiérarchie de modèles.

On considère que :

• pour tous les modèles, on doit estimer un paramètre commun ${\bf q}$ avec les mêmes équations de mesure ${\bf c}_i({\bf q},{\bf m}_i)$,
• deux modèles diffèrent par leurs contraintes ${\bf c}_0({\bf q})$ sur le paramètre, i.e. par le nombre $p$ d'équations.

D'un modèle à un autre

On a des équations entre le paramètre estimé ${\bf q}$ d'un modèle plus spécifique ${\cal M}$ et le paramètre estimé $\tilde{\bf q}$ d'un modèle plus général $\tilde{\cal M}$.

Décider entre deux modèles

Un modèle plus général est choisi par rapport à un modèle plus spécifique si et seulement si le coût décroît selon un facteur $0 < \Phi(d, d') \leq 1$.

Intégrer une estimation robuste dans le multi-modèles

Afin d'implémenter une telle méthode en effectuant une estimation robuste, on suppose que :
(i) Etant donné un modèle valide (estimé sans outlier) pour un ensemble de mesures minimal, un modèle plus général qui requiert plus de mesures dans son ensemble minimal, peut toujours considérer les mesures de ses parents comme non outliers parce qu'elles vérifient aussi un sous-ensemble des équations de modèles avec lesquelles elles sont cohérentes.
(ii) Etant donné un modèle valide et une généralisation de celui-ci, des mesures additionnelles pour estimer le modèle général doivent être en dehors de l'ensemble des mesures appliquées au modèle le plus simple. Ceci restreint le nombre de mesures et augmente la chance de sélectionner aléatoirement une bonne estimation. Cela peut éviter de sélectionner des configurations singulières de points pour un modèle donné.

Implémenter des multi-modèles robustes

Afin d'implémenter ces idées :

1. L''état'' d'un modèle est représenté par :
   (i) le paramètre estimé $\tilde{\bf q}$ et sa précision relative $\tilde{\bf Q}$,
   (ii) les index des points échantillonnés pour estimer l'état,
   (iii) les index des points non cohérents, i.e. des outliers pour ce modèle,
   
2. tandis que le ``modèle'' est spécifié par :
   (i) son nom,
   (ii) ses contraintes et coût intrinsèque,
   (iii) une liste d' ``alternatives'' i.e. des modèles moins spécifiques avec moins de contraintes,
   (iv) leur facteur de coût relatif $\Phi$,
   (v) une liste de ``modèles'' qui sont parents de ceux-ci.

En utilisant cette structure de données, les idées précédentes sont implémentées par l'algorithme suivant :

Initialisation

  Prendre le modèle nul avec une valeur du paramètre ${\bf q}_0$ initiale fournie par l'utilisateur, dans une liste candidate.

Iteration

  Pour chaque modèle de la liste :

• sélectionner aléatoirement un ensemble de mesures ``additionnelles'' dans l'ensemble de points non cohérents avec le modèle parent (s'il y en a un),
• estimer :
  1. le paramètre du modèle en utilisant le paramètre du modèle parent comme valeur initiale ${\bf q}_0$, en résolvant le problème de projection et en utilisant l'algorithme (11),
  2. la cohérence de chaque mesure, en résolvant le problème de projection et en utilisant l'algorithme (11),
  3. l'efficacité du modèle, comme on l'a décrit dans (14).
• Si ce modèle est plus valable que le précédent, le paramètre estimé pour ce modèle :
  • remplace les estimations faites auparavant pour ce modèle,
  • puis:
    1. on seuille l'ensemble des outliers, comme illustré dans la Fig. 4 en tenant compte des discussions précédentes,
    2. on affine l'estimation du paramètre du modèle, en appliquant l'algorithme (11) au projecteur,
    3. on répéte les étapes 1 et 2, afin de stabiliser l'estimation,
    4. on évalue son coût, à partir de (4).
  • Si le coût est inférieur à celui du parent, ses alternatives sont introduites dans la liste candidate.
  • le modèle est enlevé de la liste candidate.
• Sinon on répète l'itération en sélectionnant aléatoirement un modèle de la liste candidate.

Fin et Sortie

 
Le modèle, dont le coût minimal appartient à un seuil donné, est choisi comme modèle le ``meilleur''.

Bibliographie

1

T. Vieville, D. Lingrand, and F. Gaspard.
Implementing a variant of the Kanatani's estimation method.
RR 4050, INRIA, Nov. 2000.

2

T. Vieville, D. Lingrand, and F. Gaspard.
Implementing a multi-model estimation method.
The International Journal of Computer Vision, 44(1), 2001.