En trois lignes

Il y a beaucoup de bruit dans les données dans le monde naturel
Le bruit peut rendre difficile la recherche de la loi
RANSAC ignore bien ce bruit

Bonjour. Aujourd'hui, je vais vous envoyer une histoire sur l'informatique que je fais à l'école supérieure. L'autre jour, j'ai soudain pensé: «Au fait, je n'avais jamais étudié correctement», alors j'ai étudié et mis en œuvre RANSAC.

Qu'est-ce que RANSAC

Lors de la prise de données naturelles telles que des images dans la recherche universitaire, les données peuvent contenir des «valeurs aberrantes» qui semblent s'écarter considérablement des règles en raison du bruit ou d'autres causes. Les valeurs aberrantes interfèrent avec la recherche de la loi dans les données. Dans un tel cas, RANSAC est une méthode d'estimation de la loi (paramètre) en ignorant les valeurs aberrantes.

... c'est difficile à comprendre quand on parle de concepts, alors regardons un exemple concret. Ci-après, la loi est lue comme «modèle».

Estimation du modèle en ligne droite

Considérons le problème de l'estimation de la ligne droite le long d'un groupe de points donné. Le groupe de points est distribué le long de cette ligne droite, mais 100 échantillons sont mélangés avec des valeurs aberrantes qui sautent d'un niveau.

Le graphique ressemble à ceci.

(Code généré par python)

# true values
_a = 0.5
_b = 0.3

# samples
# samples
points = np.array([[x, _a * x + _b + .1 * np.random.randn() + (np.random.randint(100) == 0) * np.random.rand() * 1000] for x in np.arange(0, 10, 0.01)])

Puisque la ligne droite est représentée par y = ax + b, ce problème est synonyme de recherche des valeurs de a et b. Cette fois, laissez la vraie valeur de a à 0,5 et la vraie valeur de b à 0,3.

Si vous essayez de trouver ceci (a, b) normalement, il sera tiré par la «valeur aberrante» et la ligne droite estimée sera grandement tirée vers le haut. Par exemple, la méthode la plus orthodoxe appelée méthode des moindres carrés ressemblerait à ceci.

Le rouge est la vraie ligne droite et le vert est la ligne droite estimée. Les paramètres estimés sont (a, b) = (0,20, 7,4). De cette façon, la ligne droite verte estimée est tirée plus haut que la vraie ligne droite rouge en raison de l'influence des valeurs aberrantes.

(Code généré par python. Avec une approche de rodage)

def leastSquare(data):
    # Simulated Annealing
    tau = 100
    bestfit = None
    besterr = float('inf')
    model = np.zeros(2)
    while tau >= 0.0001:
        for _ in range(10):
            grad = errorGrad(model, data)
            grad /= np.linalg.norm(grad)
            grad *= -1
            model += grad * tau
            
        tau *= 0.1
    return model

a, b = leastSquare(points)

Résolu avec RANSAC

Si vous le demandez normalement comme ceci, la "valeur aberrante" interférera et ne fonctionnera pas, donc la valeur aberrante sera ignorée. RANSAC utilise l'algorithme suivant.

Sélectionnez au hasard plus de "petits" échantillons de l'ensemble de données que nécessaire pour déterminer le modèle (cette fois, les inconnues sont (a, b), donc deux ou plus)
Dérivation d'un modèle temporaire à partir du "petit nombre" d'échantillons obtenu, par exemple par la méthode des moindres carrés
Appliquez un modèle temporaire aux données, et s'il n'y a pas beaucoup de valeurs aberrantes, ajoutez-le au "bon modèle candidat"
Répétez 2-3 plusieurs fois
Parmi les «candidats modèles corrects» obtenus, celui qui correspond le mieux aux données est défini comme le vrai modèle.

S'il y a beaucoup de valeurs aberrantes à l'étape 3, ignorez-les car l'exemple de l'étape 2 a détecté les valeurs aberrantes. En faisant cela, il est possible d'obtenir la valeur vraie en excluant l'influence de la valeur aberrante. En d'autres termes, il s'agit de trouver le groupe de points qui représente le mieux le vrai modèle parmi les groupes de points des données et de trouver la ligne droite à partir de ce groupe de points.

Les lignes droites obtenues dans ce RANSAC sont les suivantes.

Le vert est la ligne droite estimée. Vous pouvez voir qu'il est proche de la distribution des données. Vous pouvez voir que (a, b) = (0.496228 ..., 0.299107 ...) est assez proche de la vraie valeur.

Le code en python ressemble à ceci.

def ransac(data,
        # parameters for RANSAC
        n = 2, # required sample num to decide parameter
        k = 100, # max loop num
        t = 2.0, # threshold error val for inlier
        d = 800 # requrired inlier sample num to be correnct param
    ):

    good_models = []
    good_model_errors = []
    iterations = 0
    while iterations < k:
        sample = data[np.random.choice(len(data), 2, False)]
        param = getParamWithSamples(sample)

        inliers = []
        for p in data:
            if (p == sample).all(1).any(): continue
            if getError(param, p) > t:
                continue
            else:
                inliers.append(p)


        if len(inliers) > d:
            current_error = getModelError(param, data)
            good_models.append(param)
            good_model_errors.append(current_error)

        iterations += 1
        
    best_index = np.argmin(good_model_errors)
    return good_models[best_index]

a, b = ransac(data)

Résumé

Cette fois, j'ai repris l'algorithme RANSAC en prenant un modèle linéaire à deux paramètres comme exemple. C'est un algorithme très important car il apparaît dans divers articles.

À l'origine, j'aimais beaucoup d'algorithmes, mais pendant un peu plus d'un an après mon entrée aux études supérieures, j'ai eu affaire à divers algorithmes comme une boîte noire avec un accent sur la pratique comme la mise en œuvre, donc à partir de maintenant je toucherai occasionnellement le contenu de chaque algorithme. Je veux aussi le poursuivre.

Au fait, ce code est résumé ici au format de notebook ipython.

https://github.com/smurakami/study-ransac/blob/master/ransac.ipynb

[J'ai étudié] L'histoire de RANSAC

En trois lignes

Qu'est-ce que RANSAC

Estimation du modèle en ligne droite

Résolu avec RANSAC

Résumé