Konsensus dotyczący próby losowej — Random sample consensus

Konsensus próby losowej ( RANSAC ) to iteracyjna metoda szacowania parametrów modelu matematycznego na podstawie zbioru obserwowanych danych, które zawierają wartości odstające , gdy wartości odstające nie mają wpływu na wartości oszacowań. W związku z tym można go również interpretować jako metodę wykrywania wartości odstających. Jest to algorytm niedeterministyczny w tym sensie, że daje rozsądny wynik tylko z pewnym prawdopodobieństwem, które to prawdopodobieństwo wzrasta w miarę dopuszczalności większej liczby iteracji. Algorytm został po raz pierwszy opublikowany przez Fischlera i Bollesa w SRI International w 1981 roku. Użyli RANSAC do rozwiązania problemu określania lokalizacji (LDP), którego celem jest określenie punktów w przestrzeni, które rzutują na obraz na zestaw punktów orientacyjnych z znane lokalizacje.

RANSAC wykorzystuje powtarzające się losowe podpróbkowanie . Podstawowym założeniem jest to, że dane składają się z „inlierów”, tj. danych, których rozkład można wyjaśnić pewnym zestawem parametrów modelu, choć mogą one być zaszumione, oraz „odstających”, czyli danych, które nie pasują do modelu. Wartości odstające mogą pochodzić na przykład z ekstremalnych wartości szumu lub z błędnych pomiarów lub błędnych hipotez dotyczących interpretacji danych. RANSAC zakłada również, że mając (zazwyczaj mały) zestaw elementów pośredniczących, istnieje procedura, która może oszacować parametry modelu, który optymalnie wyjaśnia lub pasuje do tych danych.

Przykład

Prostym przykładem jest dopasowanie linii w dwóch wymiarach do zestawu obserwacji. Zakładając, że ten zbiór zawiera zarówno elementy wewnętrzne, tj. punkty, które w przybliżeniu można dopasować do linii, jak i odstające, punkty, których nie można dopasować do tej linii, prosta metoda najmniejszych kwadratów dopasowywania linii generalnie da w wyniku linię ze złym dopasowaniem do linii. dane, w tym wewnętrzne i odstające. Powodem jest to, że jest optymalnie dopasowany do wszystkich punktów, w tym do odstających. Z drugiej strony RANSAC próbuje wykluczyć wartości odstające i znaleźć model liniowy, który w swoich obliczeniach wykorzystuje tylko wartości pośrednie. Odbywa się to poprzez dopasowanie modeli liniowych do kilku losowych próbek danych i zwrócenie modelu, który najlepiej pasuje do podzbioru danych. Ponieważ czynniki pośrednie wydają się być bardziej powiązane liniowo niż losowa mieszanina zmiennych pośrednich i odstających, losowy podzbiór składający się wyłącznie z zmiennych pośrednich będzie miał najlepsze dopasowanie do modelu. W praktyce nie ma gwarancji, że podzbiór informacji wstępnych będzie losowo próbkowany, a prawdopodobieństwo powodzenia algorytmu zależy od proporcji danych pośrednich w danych, a także od wyboru kilku parametrów algorytmu.

  • Zestaw danych z wieloma wartościami odstającymi, dla których należy dopasować linię.

  • Dopasowana linia z RANSAC; wartości odstające nie mają wpływu na wynik.

Przegląd

Algorytm RANSAC to technika ucząca szacowania parametrów modelu przez losowe próbkowanie obserwowanych danych. Mając zestaw danych, którego elementy danych zawierają zarówno inlier, jak i outliers, RANSAC wykorzystuje schemat głosowania, aby znaleźć optymalny wynik dopasowania. Elementy danych w zestawie danych służą do głosowania na jeden lub wiele modeli. Implementacja tego schematu głosowania opiera się na dwóch założeniach: że hałaśliwe cechy nie będą konsekwentnie głosować na żaden pojedynczy model (kilka wartości odstających) i jest wystarczająco dużo cech, aby uzgodnić dobry model (kilka brakujących danych). Algorytm RANSAC składa się zasadniczo z dwóch kroków, które są powtarzane iteracyjnie:

  1. W pierwszym kroku ze zbioru danych wejściowych losowo wybierany jest podzbiór próbki zawierający minimalną ilość danych. Dopasowany model i odpowiadające mu parametry modelu są obliczane przy użyciu tylko elementów tego przykładowego podzbioru. Liczność podzbioru próbek jest najmniejsza, wystarczająca do wyznaczenia parametrów modelu.
  2. W drugim kroku algorytm sprawdza, które elementy całego zbioru danych są zgodne z modelem, którego instancją są oszacowane parametry modelu uzyskane w kroku pierwszym. Element danych będzie uważany za wartość odstającą, jeśli nie będzie pasował do modelu dopasowania utworzonego przez zestaw szacowanych parametrów modelu w ramach pewnego progu błędu, który określa maksymalne odchylenie przypisywane wpływowi szumu.

Zestaw elementów pośrednich uzyskanych dla dopasowanego modelu nazywa się zestawem konsensusu. Algorytm RANSAC będzie iteracyjnie powtarzał powyższe dwa kroki, aż uzyskany zestaw konsensusu w określonej iteracji będzie miał wystarczającą liczbę elementów wewnętrznych.

Dane wejściowe do algorytmu RANSAC to zbiór obserwowanych wartości danych, sposób dopasowania pewnego rodzaju modelu do obserwacji oraz pewne parametry ufności . RANSAC osiąga swój cel, powtarzając następujące kroki:

  1. Wybierz losowy podzbiór oryginalnych danych. Nazwij ten podzbiór hipotetycznymi informacjami pośrednimi .
  2. Do zestawu hipotetycznych wkładek dopasowywany jest model.
  3. Wszystkie inne dane są następnie testowane z dopasowanym modelem. Te punkty, które dobrze pasują do oszacowanego modelu, zgodnie z pewną funkcją straty specyficzną dla modelu , są uważane za część zbioru konsensusu .
  4. Oszacowany model jest dość dobry, jeśli wystarczająco wiele punktów zostało sklasyfikowanych jako część zbioru konsensusu.
  5. Następnie model można ulepszyć poprzez ponowne oszacowanie go przy użyciu wszystkich członków zbioru konsensusu.

Procedurę tę powtarza się określoną liczbę razy, za każdym razem tworząc albo model, który jest odrzucany, ponieważ zbyt mało punktów jest częścią zbioru konsensusu, albo udoskonalony model wraz z odpowiadającym rozmiarem zbioru konsensusu. W tym drugim przypadku zachowujemy dopracowany model, jeśli jego zbiór konsensusu jest większy niż poprzednio zapisany model.

  • RANSAC: Inliers i Outliers.

Algorytm

Ogólny algorytm RANSAC działa w następujący sposób: 

Given:
    data – A set of observations.
    model – A model to explain observed data points.
    n – Minimum number of data points required to estimate model parameters.
    k – Maximum number of iterations allowed in the algorithm.
    t – Threshold value to determine data points that are fit well by model.
    d – Number of close data points required to assert that a model fits well to data.

Return:
    bestFit – model parameters which best fit the data (or null if no good model is found)

iterations = 0
bestFit = null
bestErr = something really large

while iterations < k do
    maybeInliers := n randomly selected values from data
    maybeModel := model parameters fitted to maybeInliers
    alsoInliers := empty set
    for every point in data not in maybeInliers do
        if point fits maybeModel with an error smaller than t
             add point to alsoInliers
        end if
    end for
    if the number of elements in alsoInliers is > d then
        // This implies that we may have found a good model
        // now test how good it is.
        betterModel := model parameters fitted to all points in maybeInliers and alsoInliers
        thisErr := a measure of how well betterModel fits these points
        if thisErr < bestErr then
            bestFit := betterModel
            bestErr := thisErr
        end if
    end if
    increment iterations
end while

return bestFit

Parametry

Wartość progowa do określenia, kiedy punkt danych pasuje do modelu t oraz liczba zbliżonych punktów danych wymaganych do stwierdzenia, że ​​model dobrze pasuje do danych d, są określane na podstawie określonych wymagań aplikacji i zbioru danych, i ewentualnie na podstawie eksperymentalnych ocena. Liczbę iteracji k można jednak określić jako funkcję pożądanego prawdopodobieństwa sukcesu p przy użyciu wyniku teoretycznego. Niech p będzie pożądanym prawdopodobieństwem, że algorytm RANSAC dostarczy użyteczny wynik po uruchomieniu. RANSAC zwraca pomyślny wynik, jeśli w pewnej iteracji wybierze tylko dane pośrednie z zestawu danych wejściowych, gdy wybierze n punktów, z których estymowane są parametry modelu. Niech będzie prawdopodobieństwo wyboru elementu pośredniczącego za każdym razem, gdy wybierany jest pojedynczy punkt, to znaczy

= liczba inlierów w danych / liczba punktów w danych

Częstym przypadkiem jest to, że nie jest dobrze znany z góry, ale można podać pewną przybliżoną wartość. Zakładając, że n punktów potrzebnych do oszacowania modelu jest wybieranych niezależnie, jest prawdopodobieństwem, że wszystkie n punktów to wartości inlier i jest prawdopodobieństwem, że co najmniej jeden z n punktów jest wartością odstającą, przypadek, który implikuje, że zostanie oszacowany zły model od tego punktu. To prawdopodobieństwo do potęgi k jest prawdopodobieństwem, że algorytm nigdy nie wybierze zbioru n punktów, z których wszystkie są inlierami i musi to być takie samo jak . W konsekwencji,

co po logarytmowaniu obu stron prowadzi do:

Wynik ten zakłada, że n punktów danych jest wybieranych niezależnie, to znaczy punkt, który został wybrany raz, jest zastępowany i może być wybrany ponownie w tej samej iteracji. Często nie jest to rozsądne podejście i wyprowadzoną wartość k należy przyjąć jako górną granicę w przypadku, gdy punkty są wybierane bez zamiany. Na przykład, w przypadku znalezienia linii, która pasuje do zestawu danych zilustrowanego na powyższym rysunku, algorytm RANSAC zazwyczaj wybiera dwa punkty w każdej iteracji i oblicza maybe_modeljako linię między punktami, a wtedy krytyczne jest, aby te dwa punkty były różne .

Aby uzyskać dodatkową pewność, odchylenie standardowe lub ich wielokrotności można dodać do k . Odchylenie standardowe k jest zdefiniowane jako

Zalety i wady

Zaletą RANSAC jest jego zdolność do solidnej estymacji parametrów modelu, tj. może oszacować parametry z wysokim stopniem dokładności, nawet jeśli w zbiorze danych występuje znaczna liczba wartości odstających . Wadą RANSAC jest to, że nie ma górnej granicy czasu potrzebnego do obliczenia tych parametrów (z wyjątkiem wyczerpania). Gdy liczba obliczonych iteracji jest ograniczona, otrzymane rozwiązanie może nie być optymalne, a nawet może nie być dobrze dopasowane do danych. W ten sposób RANSAC oferuje kompromis; obliczanie większej liczby iteracji zwiększa prawdopodobieństwo wytworzenia rozsądnego modelu. Co więcej, RANSAC nie zawsze jest w stanie znaleźć optymalny zestaw, nawet dla zestawów średnio zabrudzonych i zwykle źle się sprawdza, gdy liczba wkładek jest mniejsza niż 50%. Zaproponowano rozwiązanie Optimal RANSAC, które poradzi sobie z obydwoma tymi problemami i jest w stanie znaleźć optymalny zestaw dla zestawów silnie zanieczyszczonych, nawet dla współczynnika inlier poniżej 5%. Inną wadą RANSAC jest to, że wymaga ustawienia progów specyficznych dla problemu.

RANSAC może oszacować tylko jeden model dla określonego zestawu danych. Podobnie jak w przypadku każdego podejścia opartego na jednym modelu, gdy istnieją dwie (lub więcej) instancje modelu, RANSAC może nie znaleźć żadnego z nich. Hough transformacji jest alternatywna technika wytrzymałe szacowania, które mogą być przydatne, gdy więcej niż jeden przykład model jest obecny. Inne podejście do dopasowania wielu modeli jest znane jako PEARL, które łączy próbkowanie modelu z punktów danych, jak w RANSAC, z iteracyjną ponowną estymacją wartości wewnętrznych i dopasowaniem wielu modeli sformułowanym jako problem optymalizacji z globalną funkcją energii opisującą jakość ogólne rozwiązanie.

Aplikacje

Algorytm RANSAC jest często używany w wizji komputerowej , np. do jednoczesnego rozwiązania problemu korespondencji i oszacowania podstawowej macierzy związanej z parą kamer stereo; zobacz także: Struktura z ruchu , funkcja skalowania niezmienna przekształcać , szwy obrazu , sztywny segmentacja ruchu .

Rozwój i ulepszenia

Od 1981 r. RANSAC stał się podstawowym narzędziem w społeczności komputerowej wizji i przetwarzania obrazu. W 2006 roku, z okazji 25. rocznicy powstania algorytmu, na Międzynarodowej Konferencji na temat Wizji Komputerowej i Rozpoznawania Wzorców (CVPR) zorganizowano warsztaty podsumowujące najnowsze wkłady i zmiany w pierwotnym algorytmie, mające głównie na celu poprawę szybkości działania algorytmu , solidność i dokładność oszacowanego rozwiązania oraz zmniejszenie zależności od stałych zdefiniowanych przez użytkownika.

RANSAC może być czuły na wybór prawidłowego progu szumu, który określa, które punkty danych pasują do modelu z określonym zestawem parametrów. Jeśli taki próg jest zbyt wysoki, to wszystkie hipotezy są oceniane na równi (dobre). Z drugiej strony, gdy próg szumu jest zbyt mały, oszacowane parametry wydają się być niestabilne (tj. po prostu przez dodanie lub usunięcie punktu odniesienia do zestawu elementów pośrednich, oszacowanie parametrów może się zmieniać). Aby częściowo zrekompensować ten niepożądany efekt, Torr i in. zaproponował dwie modyfikacje RANSAC o nazwie MSAC (M-estimator SAmple and Consensus) i MLESAC (Maximum Likelihood Estimation SAmple and Consensus). Główną ideą jest ocena jakości zbioru konsensusu (tj. danych pasujących do modelu i pewnego zbioru parametrów) obliczenie jego prawdopodobieństwa (podczas gdy w pierwotnym sformułowaniu Fischlera i Bollesa ranga była licznością takiego zbioru). Tordoff proponuje rozszerzenie do MLESAC, które uwzględnia wcześniejsze prawdopodobieństwa związane z wejściowym zbiorem danych. Powstały algorytm nosi nazwę Guided-MLESAC. W podobny sposób Chum zaproponował kierowanie procedurą próbkowania, jeśli znane są pewne informacje a priori dotyczące danych wejściowych, tj. czy dane prawdopodobnie będą inlierem, czy outlierem. Proponowane podejście nosi nazwę PROSAC, PROgressive SAmple Consensus.

Chum i in. zaproponowali również randomizowaną wersję RANSAC o nazwie R-RANSAC, aby zmniejszyć obciążenie obliczeniowe w celu zidentyfikowania dobrego zestawu konsensusu. Podstawową ideą jest wstępna ocena dobroci aktualnie tworzonego modelu przy użyciu tylko ograniczonego zestawu punktów zamiast całego zestawu danych. Rozsądna strategia wskaże z dużą pewnością, kiedy należy ocenić dopasowanie całego zestawu danych lub kiedy model można łatwo odrzucić. Rozsądnie jest sądzić, że wpływ tego podejścia jest bardziej istotny w przypadkach, w których odsetek osób pośredniczących jest duży. Rodzaj strategii zaproponowany przez Chuma i in. nazywa się schematem pierwokupu. Nistér zaproponował paradygmat o nazwie Preemptive RANSAC, który umożliwia dokładne oszacowanie w czasie rzeczywistym struktury sceny i ruchu kamery. Główna idea tego podejścia polega na wygenerowaniu ustalonej liczby hipotez, tak aby porównanie odbywało się w odniesieniu do jakości wygenerowanej hipotezy, a nie względem jakiejś bezwzględnej metryki jakości.

Inni badacze próbowali radzić sobie z trudnymi sytuacjami, w których skala szumu nie jest znana i/lub występuje wiele egzemplarzy modelu. Pierwszy problem został poruszony w pracy przez Wanga i Sutera. Toldo i in. reprezentują każdą daną z charakterystyczną funkcją zbioru losowych modeli, które pasują do punktu. Następnie wiele modeli ujawnia się jako klastry, które grupują punkty wspierające ten sam model. Algorytm grupowania, zwany J-linkage, nie wymaga wcześniejszego określenia liczby modeli ani ręcznego dostrajania parametrów.

RANSAC został również dostosowany do rekurencyjnych aplikacji szacowania stanu, w których pomiary wejściowe są zniekształcone przez wartości odstające, a podejścia z filtrem Kalmana, które opierają się na rozkładzie Gaussa błędu pomiaru, są skazane na niepowodzenie. Takie podejście nazywa się KALMANSAC.

Powiązane metody

Uwagi

Bibliografia