RANSAC

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25. helmikuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

RANSAC ( lyhenne RANdom Sample Consensus ) on vakaa menetelmä mallin parametrien arvioimiseksi satunnaisotoksiin perustuen . RANSAC-järjestelmä kestää kohinaista syöttödataa. Menetelmää ehdottivat vuonna 1981 Fischler ja Bolles.

Usein on tietojenkäsittelytehtävä, jossa on tarpeen määrittää mallin parametrit, joiden on täytettävä lähtötiedot. Kaikki lähtötiedot voidaan jakaa kahteen tyyppiin: mallia tyydyttävät hyvät kohdat, "ei-outliers" tai "inlayers" ( englanniksi inlier ) ja väärät pisteet, kohinat ovat satunnaisia sisällytyksiä alkuperäiseen dataan, "outliers" tai "outlayers" ( englanti ) .outlier

Esimerkki

Tarkastellaan yksinkertaisinta esimerkkiä algoritmin toiminnasta: suoran viivan kirjoittaminen 2D-pisteeseen . Olettaen, että tiedoissa on poikkeavuuksia, parametrien estimoiminen tavallisella tavalla, kuten pienimmän neliösumman , johtaa virheellisen mallin laskemiseen, koska malli rakennetaan kaikista pisteistä. RANSAC-menetelmä ottaa lähtökohtana vain kaksi suoran rakentamiseen tarvittavaa pistettä ja rakentaa niiden avulla mallin, jonka jälkeen se tarkistaa estimointifunktiolla tietyllä kynnysarvolla kuinka monta pistettä vastaa mallia.

Tietojoukko, johon rivi sovitetaan. päästöt ovat runsaat.
RANSAC-algoritmin ehdottama suora. poikkeamat eivät vaikuta tulokseen.

Algoritmin kuvaus

Algoritmin syöte on:

alkuperäinen tietojoukko $X$
toiminto , jonka avulla voit laskea mallin parametrit pisteiden tietojoukosta $M$ $\theta$ $P$ $n$
funktio pisteiden vastaavuuden arvioimiseksi tuloksena olevaan malliin $E$
arviointitoiminnon kynnys $t$
menetelmäiteraatioiden määrä _ $k$

Koko algoritmi koostuu yhdestä silmukasta, jonka jokainen iteraatio voidaan jakaa loogisesti kahteen vaiheeseen.

Ensimmäinen vaihe on pisteiden valinta ja mallin laskeminen.
- Alkupisteiden joukosta valitaan satunnaisesti n erilaista pistettä. $X$
- Valittujen pisteiden perusteella malliparametrit lasketaan funktiolla , rakennettua mallia kutsutaan yleensä hypoteesiksi. $\theta$ $P$ $M$
Toinen vaihe on hypoteesien testaus.
- Jokaisen pisteen osalta sen yhteensopivuus hypoteesin kanssa tarkistetaan arviointifunktiolla ja kynnysarvolla $E$ $t$
- Jokainen piste on merkitty inlayer- tai outlier-merkillä
- Kaikkien pisteiden tarkistuksen jälkeen tarkistetaan, onko hypoteesi tällä hetkellä paras, ja jos on, se korvaa aiemman parhaan hypoteesin.

Silmukan loppuun jää viimeinen paras hypoteesi.

Menetelmän tulokset ovat:

Mallin parametrit $\theta$ $P$
Lähdetietopisteet, jotka on merkitty lisäkerroksilla tai poikkeavilla arvoilla.

Lähtötietojen arviointi

Parametrin arvo tulee määrittää tiedoista riippuen erityisvaatimuksista riippuen, useimmiten vasta kokeellisten arvioiden jälkeen. Iteraatioiden lukumäärä voidaan määrittää teoreettisella estimoinnilla ennen kuin algoritmi suoritetaan. Olkoon todennäköisyys, että RANSAC-algoritmi jossain iteraatiossa , valitessaan mallin perustana olevat pisteet, ottaa alkuperäisestä datajoukosta vain inlayers laskelmia varten. Tällaisessa tilanteessa näistä pisteistä rakennettu malli on todennäköisesti melko tarkka. Tämän perusteella voimme käyttää todennäköisyyttä p arvioimaan algoritmin tarkkuutta. Olkoon todennäköisyys valita yksi kerros pisteiden kokonaismäärästä, eli missä on kerrosten lukumäärä ja pisteiden kokonaismäärä. Useimmissa tapauksissa inlayer-osien prosenttiosuutta ei tiedetä ennen algoritmin käynnistymistä, mutta lähes aina voidaan tehdä jokin karkea arvio. Todennäköisyys sille, että lähtötiedoista valitaan itsenäisesti n lisäkerrosta, on tässä tapauksessa ja todennäköisyys, että ainakin yksi piste joukosta on outlier eli että rakennetaan väärä malli, on . Todennäköisyys, että iteraatioiden aikana algoritmi ei koskaan valitse inlayeria, on , tämä tilanne tarkoittaa, että tarkkaa mallia ei rakenneta, ja tämän tapahtuman todennäköisyys on . Tällä tavalla $t$ $k$ $s$ $n$ $w$ $w=I/T$ $I$ $T$ $w$ $q=C_{I}^{n}/C_{T}^{n}=I!(Tn)!/(T!(In)!)$ ${\näyttötyyli (1-q)}$ $k$ $n$ ${\näyttötyyli (1-q)^{k))$ $(1-p)$

{\näyttötyyli 1-p=(1-q)^{k))

Ilmoitetaan tarvittavien iteraatioiden lukumäärä k

$k={\frac {\log(1-p)}{\log(1-q)))$

RANSAC-algoritmin edut ja haitat

RANSAC-algoritmin etuna on sen kyky antaa luotettava arvio mallin parametreista, eli kyky estimoida mallin parametrit suurella tarkkuudella, vaikka alkuperäisessä aineistossa olisi huomattava määrä poikkeavuuksia.

Yksi RNSAC-menetelmän haitoista on se, että malliparametrien laskemiseen tarvittavalle ajalle ei ole ylärajaa. Jos käytämme aikarajana iteraatioiden maksimimäärää, tuloksena oleva ratkaisu ei välttämättä ole optimaalinen, ja on myös hyvin pieni todennäköisyys, että mikään malli ei vastaa alkuperäistä dataa. Tarkka malli voidaan määrittää tietyllä todennäköisyydellä, joka kasvaa mitä enemmän iteraatioita käytetään. Toinen RANSAC-menetelmän haittapuoli on, että on tarpeen asettaa tietty kynnysarvo algoritmin suorittamiseksi. Lopuksi RANSAC-menetelmä voi määrittää vain yhden mallin tietylle tietojoukolle. Kuten missä tahansa yhden mallin lähestymistavassa, tässä on ongelma: kun syöttötiedoissa on kaksi (tai useampia) mallia, RANSAC ei välttämättä löydä yhtään mallia.

Sovellus

RANSAC - algoritmia käytetään usein tietokonenäössä , esimerkiksi ratkaisemaan kuvansovitusongelma ja perusmatriisiestimaatio kameran sijaintiparametrien määrittämiseksi.

Linkit

Martin A. Fischler ja Robert C. Bolles. Satunnaisotoskonsensus: Paradigma mallien sovittamiseen kuva-analyysin ja automaattisen kartografian sovelluksilla // Comm . ACM:stä: päiväkirja. - 1981. - Kesäkuu ( nide 24 ). - s. 381-395 . - doi : 10.1145/358669.358692 .
David A. Forsyth ja Jean Ponce. Computer Vision, moderni lähestymistapa (uuspr.) . - Prentice Hall , 2003. - ISBN ISBN 0-13-085198-1 .
Richard Hartley ja Andrew ZissermanUsean näkymän geometriaComputer Visionissa . – 2. - Cambridge University Press , 2003.
PHS Torr ja DW Murray. Perusmatriisin estimointimenetelmien kehittäminen ja vertailu // International Journal of Computer Vision : päiväkirja. - 1997. - Voi. 24 . - s. 271-300 . - doi : 10.1023/A:1007927408552 .
Ondrej Chum (2005), Two-View Geometry Estimation by Random Sample and Consensus , PhD Thesis , < http://cmp.felk.cvut.cz/~chum/Teze/Chum-PhD.pdf > . Haettu 30. toukokuuta 2010. Arkistoitu 16. elokuuta 2009 Wayback Machinessa
Anton Konushin, vakaat algoritmit malliparametrien arvioimiseksi satunnaisnäytteisiin , tietokonegrafiikkaan ja multimediaan perustuen , < http://cgm.computergraphics.ru/content/view/47 > Arkistoitu 30. tammikuuta 2009 Wayback Machinessa