Consensus sur un échantillon aléatoire: Estimation robuste en vision par ordinateur

Par Fouad Sabry

Qu'est-ce que le consensus sur échantillon aléatoire

Le consensus sur échantillon aléatoire, également connu sous le nom de RANSAC, est une méthode itérative utilisée pour estimer les paramètres d'un modèle mathématique basé sur une collection. de données observées qui incluent des valeurs aberrantes. Cette méthode est utilisée dans les situations où les valeurs aberrantes ne peuvent avoir aucun impact sur les valeurs des estimations. La conclusion est qu’il est également possible de le considérer comme un outil de détection des valeurs aberrantes. Un algorithme est considéré comme non déterministe s’il est capable de générer un résultat approprié uniquement avec une certaine probabilité, et cette probabilité augmente à mesure que le nombre d’itérations autorisées via la méthode augmente. En 1981, ce sont Fischler et Bolles, qui travaillaient chez SRI International, qui ont initialement publié l'algorithme. Afin de résoudre le problème de détermination de localisation (LDP), qui est un problème dans lequel l'objectif est de trouver les points dans l'espace qui se projettent sur une image, puis de convertir ces points en un ensemble de points de repère avec des positions connues, ils ont utilisé RANSAC.

Comment vous en bénéficierez

(I) Informations et validations sur les sujets suivants :

Chapitre 1 : Consensus sur un échantillon aléatoire

Chapitre 2 : Estimateur

Chapitre 3 : Moindres carrés

Chapitre 4 : Valeurs aberrantes

Chapitre 5 : Validation croisée (statistiques)

Chapitre 6 : Erreurs et résidus

Chapitre 7 : Modèle de mélange

Chapitre 8 : Statistiques robustes

Chapitre 9 : Assemblage d'images

Chapitre 10 : Rééchantillonnage (statistiques)

(II) Répondre aux principales questions du public sur le consensus des échantillons aléatoires.

(III) Exemples concrets d'utilisation de consensus sur un échantillon aléatoire dans de nombreux domaines.

À qui s'adresse ce livre

Professionnels, étudiants de premier cycle et des cycles supérieurs, passionnés, amateurs et ceux qui veulent y aller au-delà des connaissances ou des informations de base pour tout type de consensus sur un échantillon aléatoire.

 

 

• Langue: Français
• Éditeur: Un Milliard De Personnes Informées [French]
• Date de sortie: 30 avr. 2024

Aperçu du livre

Consensus de l'échantillon aléatoire

Estimation robuste en vision par ordinateur

Fouad Sabry est l'ancien responsable régional du développement commercial pour les applications chez Hewlett Packard pour l'Europe du Sud, le Moyen-Orient et l'Afrique. Fouad est titulaire d'un baccalauréat ès sciences des systèmes informatiques et du contrôle automatique, d'une double maîtrise, d'une maîtrise en administration des affaires et d'une maîtrise en gestion des technologies de l'information, de l'Université de Melbourne en Australie. Fouad a plus de 25 ans d'expérience dans les technologies de l'information et de la communication, travaillant dans des entreprises locales, régionales et internationales, telles que Vodafone et des machines professionnelles internationales. Actuellement, Fouad est un entrepreneur, auteur, futuriste, axé sur les technologies émergentes et les solutions industrielles, et fondateur de l'initiative One Billion Knowledge.

Un milliard de connaissances

Consensus de l'échantillon aléatoire

Estimation robuste en vision par ordinateur

Fouad Sabry

Copyright

Consensus © de l'échantillon aléatoire 2024 par Fouad Sabry. Tous droits réservés.

Aucune partie de ce livre ne peut être reproduite sous quelque forme que ce soit ou par quelque moyen électronique ou mécanique que ce soit, y compris les systèmes de stockage et de récupération d'informations, sans l'autorisation écrite de l'auteur. La seule exception est celle d'un critique, qui peut citer de courts extraits dans une critique.

Couverture dessinée par Fouad Sabry.

Bien que toutes les précautions aient été prises dans la préparation de ce livre, les auteurs et les éditeurs n'assument aucune responsabilité pour les erreurs ou omissions, ou pour les dommages résultant de l'utilisation des informations contenues dans le présent document.

Table des matières

Chapitre 1 : Consensus de l'échantillon aléatoire

Chapitre 2 : Estimateur

Chapitre 3 : Moindres carrés

Chapitre 4 : Valeur aberrante

Chapitre 5 : Validation croisée (statistiques)

Chapitre 6 : Erreurs et résidus

Chapitre 7 : Modèle de mélange

Chapitre 8 : Des statistiques robustes

Chapitre 9 : Assemblage d'images

Chapitre 10 : Rééchantillonnage (statistiques)

Appendice

À propos de l'auteur

Chapitre 1 : Consensus de l'échantillon aléatoire

Afin d'estimer les paramètres d'un modèle mathématique à partir d'un ensemble de données observées qui comprend des valeurs aberrantes, le processus itératif connu sous le nom de consensus d'échantillon aléatoire (RANSAC) peut être utilisé. En tant que tel, il peut également être considéré comme une technique d'identification des valeurs aberrantes. Cet algorithme est non déterministe puisqu'il ne génère qu'un résultat convenable avec une probabilité donnée, qui augmente avec le nombre d'itérations autorisées. En 1981, Fischler et Bolles de SRI International ont rendu l'algorithme public pour la première fois. Avec RANSAC, ils ont pu résoudre le problème de détermination de l'emplacement (LDP), qui consiste à trouver les points dans l'espace qui correspondent à une image sous la forme d'un ensemble de points de repère avec des coordonnées fixes.

RANSAC est une méthode qui utilise le sous-échantillonnage aléatoire à plusieurs reprises. Les valeurs aberrantes sont des données dont la distribution peut être expliquée par un ensemble de paramètres du modèle, bien qu'avec un bruit considérable, tandis que les valeurs aberrantes sont des données qui ne correspondent pas au modèle, selon une hypothèse fondamentale sur les données. Parmi les sources de valeurs aberrantes, citons les valeurs excessives du bruit, les mesures erronées et les données mal interprétées. RANSAC implique également l'existence d'un processus permettant d'estimer les paramètres d'un modèle qui explique ou ajuste idéalement ces données, compte tenu d'un ensemble (souvent limité) d'inliers.

L'ajustement linéaire bidimensionnel est une illustration simple de ce principe. Si cette collection comprend à la fois des points entrants (points qui peuvent être grossièrement ajustés à une ligne) et des points aberrants (points qui ne peuvent pas être ajustés à cette ligne), la méthode des moindres carrés d'ajustement des lignes donnera probablement une ligne mal ajustée aux données. Le modèle est adapté de manière optimale à tous les points de données, même les plus extrêmes. Cependant, RANSAC cherche à trouver un modèle linéaire qui n'inclut pas les valeurs aberrantes et n'utilise que les valeurs aberrantes dans ses calculs. Pour ce faire, de nombreux échantillons aléatoires de données sont utilisés pour ajuster les modèles linéaires, et le modèle qui fournit le meilleur ajustement à une partie des données est ensuite renvoyé. Un sous-ensemble aléatoire composé entièrement d'inliers aura le meilleur ajustement du modèle, car les inliers sont plus susceptibles d'être connectés linéairement qu'un mélange aléatoire d'inliers et de valeurs aberrantes. La probabilité de réussite de l'algorithme dépend du pourcentage d'inliers dans les données et de la sélection de nombreux paramètres de l'algorithme, et en fait, il n'y a aucune garantie qu'un sous-ensemble d'inliers sera choisi au hasard.

Jeu de données comportant plusieurs valeurs aberrantes qui nécessitent une analyse de régression linéaire.

Régression RANSAC ; Les valeurs aberrantes n'ont aucun effet sur la moyenne.

L'algorithme RANSAC est une méthode d'apprentissage basée sur les données pour estimer les paramètres du modèle à partir d'échantillons d'observation. RANSAC utilise la méthode de vote pour obtenir le résultat le mieux ajusté pour un jeu de données donné dont les éléments de données incluent à la fois des valeurs internes et aberrantes. Les points de données du jeu de données sont utilisés comme bulletins de vote pour un ou plusieurs modèles. Cette technique de vote est mise en œuvre sous deux présomptions : (a) il y a suffisamment de caractéristiques pour s'accorder sur un modèle décent, et (b) les caractéristiques bruitées ne voteront pas systématiquement pour un seul modèle (peu de valeurs aberrantes) (peu de données manquantes). L'algorithme RANSAC se compose principalement de deux étapes, qui sont toutes deux exécutées de manière itérative :

Un sous-ensemble aléatoire du jeu de données en entrée est choisi pour servir d'échantillon dans la première phase. Les éléments de ce sous-échantillon sont utilisés pour calculer un modèle d'ajustement avec des paramètres de modèle. Les paramètres du modèle peuvent être calculés à l'aide des données de cardinalité du sous-échantillon.

La deuxième étape du processus consiste à vérifier quelles parties de l'ensemble de données sont en accord avec le modèle instancié par les paramètres estimés du modèle. Si une information n'est pas conforme au modèle dans une marge d'erreur prédéterminée, elle est classée comme une valeur aberrante. (Les points de données situés en dehors de cette plage sont considérés comme des valeurs aberrantes.)

Le groupe de valeurs aberrantes utilisé pour calibrer le modèle est connu sous le nom d'ensemble de consensus. Jusqu'à ce qu'un ensemble de consensus soit formé avec un nombre suffisant de valeurs aberrantes, l'algorithme RANSAC répétera de manière itérative les deux étapes précédentes.

Les valeurs de données observées, un modèle pour s'adapter à ces observations et des paramètres de confiance indiquant les valeurs aberrantes sont les entrées de l'algorithme RANSAC. L'algorithme RANSAC atteint son objectif en effectuant de manière itérative les étapes suivantes, qui sont détaillées ci-dessous :

Choisissez un échantillon des données d'origine au hasard. Vous pouvez considérer ce groupe comme les valeurs aberrantes fictives.

L'ensemble des valeurs aberrantes potentielles est utilisé comme entrée d'une procédure de modélisation.

Une vérification de toutes les données par rapport au modèle ajusté suit. L'ensemble de consensus est le sous-ensemble de points de données d'origine qui minimise la fonction de perte pour le modèle estimé (c'est-à-dire l'ensemble des inliers pour le modèle).

Si une proportion suffisamment importante d'observations s'inscrit dans l'ensemble consensuel, le modèle estimé peut être considéré comme de qualité adéquate.

Il est possible que la réestimation du modèle avec les données de l'ensemble du consensus donne de meilleurs résultats. L'affinement de l'ajustement du modèle au fil du temps sera effectué à l'aide de la qualité de l'ajustement, une mesure de la façon dont le modèle s'adapte à l'ensemble de consensus (par exemple, en définissant cette mesure comme critère de qualité de l'ajustement lors de l'itération suivante).

Chaque itération de ce processus aboutit soit au rejet d'un modèle parce que trop peu de points font partie de l'ensemble de consensus, soit à un modèle révisé avec une taille d'ensemble de consensus supérieure à celle de l'itération précédente. Ce processus est répété jusqu'à ce qu'un jeu de paramètres de modèle suffisamment bon soit trouvé.

Valeurs aberrantes et internes dans RANSAC. Cet exemple d'ajustement linéaire point par point comprend 7 valeurs aberrantes (points de données bien ajustés avec le modèle selon certains critères). Étant donné que la plupart des points de données se regroupent autour d'une ligne linéaire, l'ajustement est médiocre (c'est-à-dire qu'il y a plus d'intérieurs).

Voici un pseudo-code qui implémente l'algorithme de base de RANSAC :

Donné:

data – Un ensemble d'observations.

model – Un modèle pour expliquer les points de données observés.

n – Le nombre minimal de points de données requis pour estimer les paramètres du modèle.

k – Le nombre maximal d'itérations autorisées dans l'algorithme.

t : valeur seuil permettant de déterminer les points de données qui sont bien ajustés par le modèle (inlier).

d – Le nombre de points de données proches (inliers) nécessaires pour affirmer que le modèle s'adapte bien aux données.

Rendre:

bestFit : paramètres du modèle qui peuvent le mieux correspondre aux données (ou null si aucun bon modèle n'est trouvé).

itérations = 0

bestFit = null

bestErr = quelque chose de vraiment grand // Ce paramètre est utilisé pour affiner les paramètres du modèle afin d'obtenir le meilleur ajustement des données au fur et à mesure des itérations.

Alors que les itérations < k font

maybeInliers := n valeurs sélectionnées au hasard à partir de données

maybeModel := paramètres du modèle ajustés à maybeInliers

confirmedInliers := jeu vide

pour chaque point de données , faites

si le point correspond à maybeModel avec une erreur inférieure à t alors

ajouter un point à confirmedInliers

fin de si

fin pour

si le nombre d'éléments dans confirmedInliers est > d alors

Cela implique que nous avons peut-être trouvé un bon modèle.

Maintenant, testez à quel point c'est bon.

betterModel := paramètres du modèle ajustés à tous les points de confirmedInliers