RANSAC

RANSAC est une abréviation pour "RANdom SAmple Consensus". C'est une méthode itérative pour estimer les paramètres d'un modèle mathématique à partir d'un ensemble de données observées qui contient des valeurs aberrantes.



Catégories :

Algorithme - Statistiques

Page(s) en rapport avec ce sujet :

  • de N correspondances aléatoires suivant le modèle de fond.... Dans [8], l'algorithme AC- RANSAC est utilisé à partir de ... formation donnée par S, une seule mise en correspon- dance par point d'intérêt peut être choisie dans un... (source : math-info.univ-paris5)
  • données 3D du point M à partir de deux vues, qui s'applique quelles que soient les matrices..... L'implémentation de l'algorithme RANSAC est le suivant :... (source : vincent.jantet.free)
  • Les param`etres de la méthode sont fixes pour l'ensemble des séquences ou calculés ` a partir des données. Le nombre ini- tial de points caractéristiques suivis... (source : lirmm)

RANSAC est une abréviation pour "RANdom SAmple Consensus". C'est une méthode itérative pour estimer les paramètres d'un modèle mathématique à partir d'un ensemble de données observées qui contient des valeurs aberrantes ("outliers"). C'est un algorithme non-déterministe dans le sens où elle produit un résultat correct uniquement avec une certaine probabilité, cette probabilité augmentant à mesure que le nombre d'itérations est grand. L'algorithme a été publié pour la première fois par Fischler et Bolles en 1981.

L'hypothèse de base est que les données sont constituées de "inliers", à savoir les données dont la distribution peut être expliquée par un ensemble de paramètres d'un modèle, et de "outliers" qui sont des données qui ne correspondent pas au modèle choisi. Qui plus est , les données peuvent être soumises au bruit. Les valeurs aberrantes (outliers) peuvent venir, par exemple, des valeurs extrêmes du bruit, de mesures erronées ou d'hypothèses fausses quant à l'interprétation des données. RANSAC suppose aussi que, étant donné un ensemble (généralement petit) d'inliers, il existe une procédure qui permet d'estimer les paramètres d'un modèle de telle façon à expliquer de manière optimale ces données.

Exemple

Un exemple simple est l'ajustement d'une ligne 2D à une série d'observations. On suppose que cet ensemble contient à la fois des inliers, c'est-à-dire, les points qui peuvent être approximativement ajustés à une ligne, et les outliers (valeurs aberrantes), les points qui sont éloignés de ce modèle de ligne. Un simple traitement par une méthode des moindres carrés donnera une ligne qui est mal ajustée aux inliers. En effet, la droite s'ajustera de manière optimale à l'ensemble des points, y compris les valeurs aberrantes (outliers). RANSAC, par contre, peut générer un modèle qui ne tiendra compte que des inliers, à condition que la probabilité de choisir uniquement que des inliers dans le choix des données soit suffisamment élevée. Cependant, il n'y a aucune garantie d'obtenir cette situation, et il existe un certain nombre de paramètres de l'algorithme qui doivent être soigneusement choisis pour maintenir ce niveau de probabilité suffisamment élevée.

Présentation

Les données d'entrée de l'algorithme RANSAC sont un ensemble de valeurs des données observées, un modèle paramétré qui peut expliquer ou être ajusté aux observations, et des paramètres d'intervalle de confiance.

RANSAC atteint son objectif en sélectionnant itérativement un sous-ensemble aléatoire des données d'origine. Ces données sont d'hypothétiques inliers et cette hypothèse est ensuite testé comme suit :

  1. Un modèle est ajusté aux inliers hypothétiques, c'est-à-dire que l'ensemble des paramètres libres du modèle sont estimés à partir de cet ensemble de données.
  2. Toutes les autres données sont ensuite testées sur le modèle auparavant estimé. Si un point correspond bien au modèle estimé alors il est reconnu comme un inlier candidat.
  3. Le modèle estimé est reconnu comme correct si suffisamment de points ont été classés comme inliers candidats.
  4. Le modèle est re-estimé à partir de cet ensemble des inliers candidats.
  5. Finalement, le modèle est évalué par une estimation de l'erreur des inliers comparé au modèle.

Cette procédure est répétée un nombre fixe de fois, chaque fois produisant soit un modèle qui est rejeté parce que trop peu de points sont classés comme inliers, soit un modèle réajusté et une mesure d'erreur correspondante. Dans ce dernier cas, on conserve le modèle réévalué si son erreur est plus faible que le modèle précédent.

L'algorithme

L'algorithme RANSAC générique, en pseudocode, fonctionne comme suit :

entrées :
    data - un ensemble d'observations
    modele - un modèle qui peut être ajusté à des données
    n - le nombre minimum de données nécessaires pour ajuster le modèle
    k - le nombre maximal d'itérations de l'algorithme
    t - une valeur seuil pour déterminer si un une donnée correspond à un modèle
    d - le nombre de données proches des valeurs nécessaires pour faire valoir que le modèle correspond bien aux données
sorties :
    meilleur_modèle - les paramètres du modèle qui correspondent le mieux aux données (ou zéro si aucun bon modèle a été trouvé)
    meilleur_ensemble_points - données à partir desquelles ce modèle a été estimé
    meilleure_erreur - l'erreur de ce modèle par rapport aux données

itérateur := 0
meilleur_modèle := aucun
meilleur_ensemble_points := aucun
meilleure_erreur := infini
tant que itérateur < k
    points_aléatoires := n valeurs choisies au hasard à partir des données
    modèle_possible := paramètres du modèle correspondant aux points_aléatoires
    ensemble_points := points_aléatoires

    Pour chaque point des données pas dans points_aléatoires
        si le point s'ajuste au modèle_possible avec une erreur inférieure à t
            Ajouter un point à ensemble_points
    
    si le nombre d'éléments dans ensemble_points est > d
        (ce qui implique que nous avons peut-être trouvé un bon modèle,
        on teste maintenant dans quelle mesure il est correct)
        modèle_possible := paramètres du modèle réajusté à tous les points de ensemble_points
        erreur := une mesure de la manière dont ces points correspondent au modèle_possible
        si erreur < meilleure_erreur
            (nous avons trouvé un modèle qui est mieux que tous les précédents,
            le garder jusqu'à ce qu'un meilleur soit trouvé)
            meilleur_modèle := modèle_possible
            meilleur_ensemble_points := ensemble_points
            meilleure_erreur := erreur
     
    incrémention de litérateur

retourne meilleur_modèle, meilleur_ensemble_points, meilleure_erreur

Variantes envisageables de l'algorithme RANSAC :

Les paramètres

Les valeurs des paramètres t et d doivent être fixées conformément aux exigences spécifiques liées à l'application ainsi qu'à la totalité de données. qui peuvent être peut-être fondées sur l'évaluation expérimentale. Le paramètre k (le nombre d'itérations), cependant, peut être déterminée à partir d'un résultat théorique. Soit p la probabilité que l'algorithme RANSAC pendant une itération sélectionne seulement des inliers dans la totalité des données d'entrée, quand il choisit les n points à partir desquels les paramètres du modèle seront estimés. Quand cela se produit, le modèle qui en résulte est susceptible d'être pertinent, par conséquent p donne la probabilité que l'algorithme produise un résultat correct. Soit w, la probabilité de choisir un inlier à chaque fois qu'un seul point est choisi, c'est-à-dire

w = nombre d'inliers dans les données / nombre de points dans les données

Un cas habituel est que w ne soit pas connu à l'avance, mais une valeur approximative peut être estimée. En supposant que les n points nécessaires pour l'estimation d'un modèle sont choisies de manière indépendante, wn est la probabilité que la totalité des n points correspond à des inliers et 1 − wn est la probabilité qu'au moins un des n points est un cas atypique (outlier), un cas qui implique qu'un mauvais modèle sera estimé à partir de cet ensemble de points. Cette probabilité à la puissance de k est la probabilité que l'algorithme ne choisissent jamais un ensemble de n points qui seraient tous des inliers et cela doit être égale à 1 − p. Donc,

1 − p = (1 − wn) k

qui, en prenant le logarithme des deux côtés, conduit à


k = \frac{\log(1 - p)}{\log(1 - wˆn)}

Il convient de noter que ce résultat suppose que les n points de données sont choisis de façon indépendante, c'est-à-dire, qu'un point qui a été choisi une fois est remis et peut être choisi à nouveau dans la même itération. Cela n'est pas fréquemment une approche pertinente et la valeur calculée pour k devrait être pris comme une limite supérieure dans le cas où les points sont choisis sans remise. A titre d'exemple, dans le cas de la recherche d'une ligne qui s'ajuste à la série de données illustrée sur la figure ci-dessus, l'algorithme RANSAC choisit le plus souvent deux points à chaque itération et calcule le modèle_possible comme la ligne qui relie ces deux points et il est alors important que les deux points soient différents.

Pour gagner en qualité, l'écart type ou des multiples de ce dernier peuvent être ajouté à k. L'écart type de k est définie comme

SD(k) = \frac{\sqrt{1 - wˆn}}{wˆn}

Avantages et inconvénients

Un avantage de RANSAC est sa capacité à faire des statistiques robustes des paramètres du modèle, c'est-à-dire, qu'il peut estimer les paramètres avec un degré élevé de précision, même si une quantité importante de valeurs aberrantes (outliers) est présente dans la totalité de données. Un inconvénient de RANSAC est qu'il n'y a pas de limite supérieure sur le temps qu'il faut pour calculer ces paramètres. Lorsque un temps limite supérieure est utilisé (un nombre maximal d'itérations), la solution obtenue peut ne pas être la solution optimale. Un autre inconvénient de RANSAC est qu'elle suppose de fixer des seuils spécifiques au problème traité.

RANSAC ne peut estimer qu'un seul modèle à un ensemble de données spécifique. Comme pour tout approche à modèle unique, quand deux (ou plusieurs) modèles cœxistent, RANSAC peut ne parvenir à trouver ni l'un ni l'autre.

Applications

L'algorithme RANSAC est fréquemment utilisée dans le domaine de la vision par ordinateur, par exemple, pour résoudre simultanément les problèmes de mise en correspondance et d'estimer la matrice principale liée à une paire stéréo de caméras.

Références

Liens externes

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/RANSAC.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu