[PYTHON] [Ich habe studiert] RANSAC-Geschichte

In drei Zeilen

• In der Natur gibt es viel Rauschen in den Daten
• Lärm kann es schwierig machen, das Gesetz zu finden
• RANSAC ignoriert solche Geräusche gut

Hallo. Heute werde ich Ihnen eine Geschichte über Informatik schicken, die ich an der Graduiertenschule mache. Neulich dachte ich plötzlich: "Übrigens hatte ich nie richtig gelernt", also habe ich RANSAC studiert und implementiert.

Was ist RANSAC?

Bei der Aufnahme natürlicher Daten wie Bilder in der Hochschulforschung können die Daten "Ausreißer" enthalten, die aufgrund von Rauschen oder anderen Ursachen erheblich von den Regeln abzuweichen scheinen. Ausreißer stören das Finden des Gesetzes in den Daten. In einem solchen Fall ist RANSAC eine Methode zur Schätzung des Gesetzes (Parameters) durch Ignorieren der Ausreißer.

... wenn es um Konzepte geht, ist es schwer zu verstehen. Schauen wir uns also ein konkretes Beispiel an. Im Folgenden wird das Gesetz als "Modell" gelesen.

Schätzung des geraden Modells

Betrachten Sie das Problem der Schätzung der Geraden einer bestimmten Punktgruppe. Die Punktgruppe ist entlang dieser geraden Linie verteilt, aber es gibt eine Mischung von Ausreißern, die in 100 Stichproben einen Schritt nach oben springen.

Das Diagramm sieht so aus.

(Generierter Code von 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)])

Da die gerade Linie durch y = ax + b dargestellt wird, ist dieses Problem gleichbedeutend mit dem Finden der Werte von a und b. Diesmal sei der wahre Wert von a 0,5 und der wahre Wert von b 0,3.

Wenn Sie versuchen, dies (a, b) normal zu finden, wird es vom "Ausreißer" gezogen und die geschätzte gerade Linie wird stark hochgezogen. Zum Beispiel würde die orthodoxste Methode, die als Methode der kleinsten Quadrate bezeichnet wird, so aussehen.

Rot ist die wahre Gerade und Grün ist die geschätzte Gerade. Die geschätzten Parameter sind (a, b) = (0,20, 7,4). Auf diese Weise wird die geschätzte grüne Gerade aufgrund des Einflusses der Ausreißer stärker nach oben gezogen als die echte rote Gerade.

(Generierter Code von Python. Mit einem Burn-In-Ansatz)

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)

Mit RANSAC gelöst

Wenn Sie normalerweise so danach fragen, stört der "Ausreißerwert" und es funktioniert nicht, sodass der Ausreißerwert ignoriert wird. RANSAC verwendet den folgenden Algorithmus.

1. Wählen Sie zufällig mehr "kleine" Stichproben aus dem Datensatz aus, als zur Bestimmung des Modells erforderlich sind (diesmal sind die Unbekannten (a, b), also zwei oder mehr).
2. Ableitung eines außergewöhnlichen Modells aus der erhaltenen "kleinen Anzahl" von Proben, beispielsweise nach der Methode der kleinsten Quadrate.
3. Wenden Sie ein temporäres Modell auf die Daten an. Wenn nicht viele Ausreißer vorhanden sind, fügen Sie es dem "richtigen Modellkandidaten" hinzu.
4. Wiederholen Sie 2-3 mehrmals
5. Unter den erhaltenen "richtigen Modellkandidaten" wird derjenige als das wahre Modell festgelegt, das am besten zu den Daten passt.

Wenn in Schritt 3 viele Ausreißer vorhanden sind, ignorieren Sie diese, da die Stichprobe in Schritt 2 die Ausreißer erfasst hat. Auf diese Weise ist es möglich, den wahren Wert zu erhalten, indem der Einfluss des Ausreißerwerts ausgeschlossen wird. Mit anderen Worten, es ist der Vorgang, die Punktgruppe zu finden, die das wahre Modell unter den Punktgruppen der Daten am besten darstellt, und die gerade Linie von dieser Punktgruppe zu finden.

Die in diesem RANSAC erhaltenen geraden Linien sind wie folgt.

Grün ist die geschätzte gerade Linie. Sie können sehen, dass es nahe an der Verteilung der Daten liegt. Sie können sehen, dass (a, b) = (0,496228 ..., 0,299107 ...) ziemlich nahe am wahren Wert liegt.

Der Code in Python sieht so aus.

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)

Zusammenfassung

Dieses Mal habe ich den RANSAC-Algorithmus am Beispiel eines linearen Zwei-Parameter-Modells aufgegriffen. Es ist ein sehr wichtiger Algorithmus, da er in verschiedenen Veröffentlichungen erscheint.

Ursprünglich mochte ich viele Algorithmen, aber für etwas mehr als ein Jahr, nachdem ich in die Graduiertenschule eingetreten war, beschäftigte ich mich mit verschiedenen Algorithmen als Black Box, wobei der Schwerpunkt auf der Praxis wie der Implementierung lag. Von nun an werde ich gelegentlich den Inhalt jedes Algorithmus berühren Ich möchte ihm auch nachjagen.

Dieser Code wird hier übrigens im Format eines ipython notebook zusammengefasst.

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