Zufallsstichprobenkonsens: Robuste Schätzung in der Computer Vision

Von Fouad Sabry

Was ist Zufallsstichprobenkonsens?

Random Sample Consensus, auch RANSAC genannt, ist eine iterative Methode, die zur Schätzung der Parameter eines mathematischen Modells basierend auf einer Sammlung verwendet wird der beobachteten Daten, die Ausreißer enthalten. Diese Methode wird in Situationen verwendet, in denen die Ausreißer keinen Einfluss auf die Werte der Schätzungen haben dürfen. Die Schlussfolgerung ist, dass es auch als Werkzeug zur Erkennung von Ausreißern angesehen werden kann. Ein Algorithmus gilt als nicht deterministisch, wenn er nur mit einer bestimmten Wahrscheinlichkeit ein geeignetes Ergebnis erzeugen kann und diese Wahrscheinlichkeit umso größer ist, je mehr Iterationen die Methode zulässt. Im Jahr 1981 waren Fischler und Bolles, die bei SRI International arbeiteten, diejenigen, die den Algorithmus erstmals veröffentlichten. Um das Location Determination Problem (LDP) zu lösen, bei dem es darum geht, die Punkte im Raum zu finden, die auf ein Bild projiziert werden, und diese Punkte dann in eine Reihe von Orientierungspunkten mit bekannten Positionen umzuwandeln, verwendeten sie RANSAC.

Wie Sie davon profitieren werden

(I) Einblicke und Validierungen zu den folgenden Themen:

Kapitel 1: Konsens bei zufälligen Stichproben

Kapitel 2: Schätzer

Kapitel 3: Kleinste Quadrate

Kapitel 4: Ausreißer

Kapitel 5: Kreuzvalidierung (Statistik)

Kapitel 6: Fehler und Residuen

Kapitel 7: Mischungsmodell

Kapitel 8: Robuste Statistiken

Kapitel 9: Bildzusammenfügung

Kapitel 10: Resampling (Statistik)

(II) Beantwortung der häufigsten öffentlichen Fragen zum Zufallsstichprobenkonsens.

(III) Beispiele aus der Praxis für die Verwendung von Zufallsstichprobenkonsens in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die es wollen über grundlegende Kenntnisse oder Informationen für jede Art von Zufallsstichprobenkonsens hinausgehen.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 30. Apr. 2024

Buchvorschau

Kapitel 1: Konsens bei Zufallsstichproben

Um die Parameter eines mathematischen Modells aus einem Satz von beobachteten Daten zu schätzen, die Ausreißer enthalten, kann der iterative Prozess verwendet werden, der als Zufallsstichprobenkonsens (RANSAC) bekannt ist. Als solches kann es auch als eine Technik zur Identifizierung von Ausreißern angesehen werden. Dieser Algorithmus ist nicht deterministisch, da er nur mit einer bestimmten Wahrscheinlichkeit ein geeignetes Ergebnis generiert, die mit der Anzahl der zulässigen Iterationen steigt. 1981 stellten Fischler und Bolles von SRI International den Algorithmus zum ersten Mal der Öffentlichkeit vor. Mit RANSAC konnten sie das Location Determination Problem (LDP) lösen, bei dem es darum geht, die Punkte im Raum zu finden, die auf einem Bild als Sammlung von Landmarken mit festen Koordinaten abgebildet werden.

RANSAC ist eine Methode, bei der viele Male zufällige Teilstichproben verwendet werden. Ausreißer sind Daten, deren Verteilung durch eine Reihe von Modellparametern erklärt werden kann, wenn auch mit erheblichem Rauschen, während Ausreißer Daten sind, die gemäß einer grundlegenden Annahme über die Daten nicht mit dem Modell übereinstimmen. Beispiele für Quellen von Ausreißern sind zu hohe Werte des Rauschens, fehlerhafte Messungen und falsch interpretierte Daten. RANSAC impliziert auch die Existenz eines Prozesses, der die Parameter eines Modells schätzen kann, das diese Daten ideal erklärt oder anpasst, wenn eine (oft begrenzte) Menge von Ausreißern vorhanden ist.

Die zweidimensionale Linienanpassung ist eine einfache Veranschaulichung dieses Prinzips. Wenn diese Sammlung sowohl Ausreißer (Punkte, die grob an eine Linie angepasst werden können) als auch Ausreißer (Punkte, die nicht an diese Linie angepasst werden können) enthält, führt die Methode der kleinsten Quadrate zum Anpassen von Linien wahrscheinlich zu einer Linie, die schlecht an die Daten angepasst ist. Das Modell ist optimal auf alle Datenpunkte abgestimmt, auch auf die extremen. RANSAC versucht jedoch, ein lineares Modell zu finden, das die Ausreißer nicht berücksichtigt und stattdessen nur die Ausreißer in seine Berechnungen einbezieht. Um dies zu erreichen, werden viele zufällige Stichproben der Daten verwendet, um lineare Modelle anzupassen, und das Modell, das die größte Anpassung an einen Teil der Daten bietet, wird dann zurückgegeben. Eine zufällige Teilmenge, die vollständig aus Ausreißern besteht, hat die beste Modellanpassung, da Ausreißer mit größerer Wahrscheinlichkeit linear verbunden sind als eine zufällige Mischung aus Ausreißern und Ausreißern. Die Wahrscheinlichkeit, dass der Algorithmus erfolgreich ist, hängt vom Prozentsatz der Ausreißer in den Daten und der Auswahl zahlreicher Algorithmusparameter ab, und tatsächlich gibt es keine Garantie dafür, dass eine Teilmenge von Ausreißern zufällig ausgewählt wird.

Ein Dataset mit mehreren Ausreißern, für das eine lineare Regressionsanalyse erforderlich ist.

RANSAC-Regression; Ausreißer haben keinen Einfluss auf den Mittelwert.

Der RANSAC-Algorithmus ist eine datengetriebene Lernmethode zur Schätzung von Modellparametern aus Beobachtungsstichproben. RANSAC verwendet die Abstimmungsmethode, um das am besten passende Ergebnis für einen bestimmten Datensatz zu erhalten, dessen Datenelemente sowohl Ausreißer als auch Ausreißer enthalten. Die Datenpunkte des Datasets werden als Stimmzettel für ein oder mehrere Modelle verwendet. Diese Abstimmungstechnik wird unter zwei Annahmen implementiert: (a) Es gibt genügend Merkmale, um sich auf ein anständiges Modell zu einigen, und (b) die verrauschten Merkmale stimmen nicht konsistent für ein einzelnes Modell (wenige Ausreißer) (wenige fehlende Daten). Der RANSAC-Algorithmus besteht im Wesentlichen aus zwei Phasen, die beide iterativ ausgeführt werden:

In der ersten Phase wird eine zufällige Teilmenge des Eingabedatensatzes ausgewählt, die als Stichprobe dient. Die Elemente dieser Teilstichprobe werden verwendet, um ein Anpassungsmodell mit Modellparametern zu berechnen. Die Modellparameter können nur mit den Daten aus der Kardinalität der Teilstichprobe berechnet werden.

In der zweiten Phase des Prozesses wird überprüft, welche Teile des vollständigen Datensatzes mit dem Modell übereinstimmen, das durch die geschätzten Modellparameter instanziiert wird. Wenn eine Information innerhalb einer vorgegebenen Fehlerspanne nicht mit dem Modell übereinstimmt, wird sie als Ausreißer klassifiziert. (Die Datenpunkte außerhalb dieses Bereichs werden als Ausreißer betrachtet.)

Die Gruppe von Ausreißern, die zur Kalibrierung des Modells verwendet werden, wird als Konsensmenge bezeichnet. Bis ein Konsenssatz mit einer ausreichenden Anzahl von Ausreißern gebildet ist, wiederholt der RANSAC-Algorithmus iterativ die beiden vorhergehenden Schritte.

Beobachtete Datenwerte, ein Modell, das zu diesen Beobachtungen passt, und Konfidenzparameter, die auf Ausreißer hinweisen, sind die Eingaben für den RANSAC-Algorithmus. Der RANSAC-Algorithmus erreicht sein Ziel, indem er iterativ die folgenden Schritte ausführt, auf die im Folgenden eingegangen wird:

Wählen Sie nach dem Zufallsprinzip eine Stichprobe der Originaldaten aus. Sie können sich diese Gruppe als fiktive Ausreißer vorstellen.

Die Menge potenzieller Ausreißer wird als Eingabe für eine Modellierungsprozedur verwendet.

Es folgt eine Verifizierung aller Daten mit dem eingebauten Modell. Die Konsensmenge ist die Teilmenge der ursprünglichen Datenpunkte, die die Verlustfunktion für das geschätzte Modell minimiert (d. h. die Menge der Ausreißer für das Modell).

Wenn ein ausreichend großer Anteil der Beobachtungen in den Konsenssatz passt, kann das geschätzte Modell als von angemessener Qualität angesehen werden.

Es ist möglich, dass eine Neuschätzung des Modells mit Daten aus dem gesamten Konsenssatz zu besseren Ergebnissen führen würde. Die Schärfung der Modellanpassung im Laufe der Zeit erfolgt mit Hilfe der Anpassungsqualität, einem Maß dafür, wie gut das Modell zum Konsenssatz passt (z. B. indem dieses Maß bei der nächsten Iteration als Anpassungsqualitätskriterium festgelegt wird).

Jede Iteration dieses Prozesses führt entweder zur Ablehnung eines Modells, weil zu wenige Punkte Teil des Konsenssatzes sind, oder zu einem überarbeiteten Modell mit einer größeren Konsenssatzgröße als die vorherige Iteration. Dieser Vorgang wird so lange wiederholt, bis ein ausreichend guter Modellparametersatz gefunden ist.

Ausreißer und Ausreißer in RANSAC. Dieses Beispiel für eine lineare Punkt-für-Punkt-Anpassung enthält 7 Ausreißer (Datenpunkte, die unter bestimmten Kriterien gut mit dem Modell übereinstimmen). Da sich die meisten Datenpunkte um eine lineare Linie gruppieren, ist die Anpassung schlecht (d. h. mehr Ausreißer).

Hier ist etwas Pseudocode, der den grundlegenden RANSAC-Algorithmus implementiert:

Gegeben:

data – Eine Reihe von Beobachtungen.

model – Ein Modell zur Erklärung der beobachteten Datenpunkte.

n – Die Mindestanzahl von Datenpunkten, die für die Schätzung der Modellparameter erforderlich sind.

k – Die maximale Anzahl von Iterationen, die im Algorithmus zulässig sind.

t – Ein Schwellenwert zum Bestimmen von Datenpunkten, die gut an das Modell angepasst sind (Inlier).

d – Die Anzahl der nahen Datenpunkte (Inliers), die erforderlich sind, um zu bestätigen, dass das Modell gut zu den Daten passt.

Rückgabe:

bestFit – Die Modellparameter, die am besten zu den Daten passen (oder null, wenn kein gutes Modell gefunden wird).

Iterationen = 0

bestFit = null

bestErr = something really large // Dieser Parameter wird verwendet, um die Modellparameter im Laufe der Iterationen auf die beste Datenanpassung zu bringen.

während Iterationen < k

maybeInliers := n zufällig ausgewählte Werte aus Daten

maybeModel := Modellparameter, die an maybeInliers angepasst sind

confirmedInliers := leerer Satz

für jeden Punkt in den Daten

if point fits maybeModel mit einem Fehler kleiner als t then

Punkt zu confirmedInliers hinzufügen

Ende, wenn

Ende für

Wenn die Anzahl der Elemente in confirmedInliers > d ist , dann

Dies impliziert, dass wir möglicherweise ein gutes Modell gefunden haben.

Testen Sie nun, wie gut es ist.

betterModel := Modellparameter, die an alle Punkte in confirmedInliers angepasst sind

thisErr := ein Maß dafür, wie gut betterModel diese Punkte erfüllt

wenn thisErr < bestErr dann

bestFit := betterModel

bestErr := thisErr

Ende, wenn

Ende, wenn

Iterationen inkrementieren

beenden, während

return bestFit

Der Pseudocode, gespiegelt in Python. Darüber hinaus adressieren diese auf der kleinsten Quadrate basierende LinearRegressor-Definition, die RANSAC-Anwendung und die resultierende grafische Darstellung ein 2D-Regressionsproblem:

Von Kopieren Importieren Kopieren

numpy als NP importieren

aus numpy.random importieren default_rng

rng = default_rng()

Klasse RANSAC:

def __init__(self, n=10, k=100, t=0.05, d=10, model=None, loss=None, metric=None):

Selbst.n = n # 'n': Minimale Anzahl von Datenpunkten zur Schätzung von Parametern

Selbst.k = k # 'k': Maximal zulässige Iterationen

Selbst.t = t # 't': Schwellenwert, um festzustellen, ob die Punkte gut passen

Selbst.d = d # 'd': Anzahl der engen Datenpunkte, die erforderlich sind, um zu bestätigen, dass das Modell gut passt

Selbst.model = model # 'model': Klasse, die 'fit' und 'predict' implementiert

Selbst.loss = loss # 'loss': Funktion von 'y_true' und 'y_pred', die einen Vektor zurückgibt

Selbst.metric = metric # 'metric': Funktion von 'y_true' und 'y_pred' und gibt eine Gleitkommazahl zurück

Selbst.best_fit = Keine

Selbst.best_error = np.Inf

def fit(self, X, y):

for _ in range(self.k):

IDs = RNG.permutation(X.shape0])

maybe_inliers = ids[: self.n

maybe_model = copy(self.Modell).fit(Xmaybe_inliers], ymaybe_inliers])

Schwellenwert = (

Selbst.Verlust(YIDS][Selbst.n :], maybe_model.predict(Xids][self.n :]))

< selbst.t

)

inlier_ids = idsself.n :][np.flatNonzero(thresholded).flatten()]

Wenn inlier_ids.Größe > selbst.D:

inlier_points = np.hstack([maybe_inliers, inlier_ids])

better_model = copy(self.Modell).fit(Xinlier_points], yinlier_points])

this_error = Selbst.metrik(

yinlier_points], better_model.predict(Xinlier_points])

)

wenn this_error < selbst.best_error:

Selbst.best_error = this_error

Selbst.best_fit = maybe_model

Kehren Sie selbst zurück

def predict(self, X):

Kehren Sie selbst zurück.best_fit.vorhersagen(X)

def square_error_loss(y_true, y_pred):

Hin- und Rückflug (y_true - y_pred) ** 2

def mean_square_error(y_true, y_pred):

return np.sum(square_error_loss(y_true, y_pred)) / y_true.Formen0

Klasse LinearRegressor:

def __init__(self):

Selbst.params = Keine

def fit(self, X: np.ndarray, y: np.ndarray):

r, _ = X.Form

X = np.hstack([np.ones((r,