RANSAC

Estimation d'une droite avec RANSAC - image Wikipédia

Ransac est une technique permettant d’estimer un modèle mathématique à partir d’un ensemble de données, tel que pourrait le faire la méthode des moindres carrés. Cette dernière marche très bien si l’ensemble des données sont très proches du modèle attendu. Cependant si des valeurs aberrantes (aussi appelées « outliers ») font parti des données, celles ci vont fausser l’estimation du modèle.

Ransac fonctionne de la manière suivante (avec indications en italique pour l’estimation d’une droite) :

  1. On sélectionne n points aléatoirement. 2 points suffisent pour estimer une droite.
  2. On estime le modèle mathématique. On estime les coefficients de la droite passant par les deux points.
  3. On test les autre points afin de voir combien de données valident le modèle. Concrètement on teste la distance entre un point et le modèle, si cette distance est inférieur à un seuil fixé, alors le point valide le modèle. On compte combien de points on validé le modèle
  4. Le modèle est validé si suffisamment de point sont validés, sinon on repart en 1.

Une fois le modèle déterminé par m points, on peut affiner le modèle en utilisant la méthode des moindres carrés sur le sous-ensemble de m points qui ne contient alors plus de valeur aberrantes.

J’utilise RANSAC afin d’estimer une transformation 2D rigide (rotation dans le plan, translation en x et en y et mise à l’échelle uniforme selon x et y) parmi un ensemble de correspondance de point :

Ransac

Ensemble de points mis en correspondance. Les inliers trouvés par RANSAC sont dessinés en rouge.

Le code source C# est disponible ici : Ransac.