Náhodná shoda vzorků - Random sample consensus

Náhodná shoda vzorků (RANSAC) je iterační metoda odhadnout parametry matematického modelu ze souboru pozorovaných dat, který obsahuje odlehlé hodnoty, pokud má být odlehlým hodnotám přiznán žádný vliv na hodnoty odhadů. Proto jej lze také interpretovat jako metodu detekce odlehlých hodnot.^[1] Jedná se o nedeterministický algoritmus v tom smyslu, že vytváří rozumný výsledek pouze s určitou pravděpodobností, přičemž tato pravděpodobnost se zvyšuje, protože je povoleno více iterací. Algoritmus byl poprvé publikován Fischlerem a Bollesem v SRI International v roce 1981. Použili RANSAC k vyřešení problému s určováním polohy (LDP), kde cílem je určit body v prostoru, které promítají na obraz do sady orientačních bodů se známými místy.

Základní předpoklad je, že data se skládají z „inliers“, tj. Dat, jejichž rozdělení lze vysvětlit nějakou sadou parametrů modelu, i když mohou podléhat šumu, a „outliers“, což jsou data, která se k modelu nehodí. Odlehlé hodnoty mohou pocházet například z extrémních hodnot šumu nebo z chybných měření nebo nesprávných hypotéz o interpretaci dat. RANSAC také předpokládá, že vzhledem k (obvykle malé) sadě inliers existuje postup, který dokáže odhadnout parametry modelu, který tato data optimálně vysvětluje nebo zapadá.

Příklad

Jednoduchý příklad je montáž linky ve dvou rozměrech na sadu pozorování. Za předpokladu, že tato sada obsahuje jak inliery, tj. Body, které lze přibližně připevnit na linii, a odlehlé hodnoty, body, které nelze na tuto linii namontovat jednoduchá metoda nejmenších čtverců pro liniové přizpůsobení obecně vytvoří linii se špatným přizpůsobením dat včetně inliers a outliers. Důvod je ten, že je optimálně přizpůsoben všem bodům, včetně odlehlých hodnot. RANSAC se na druhé straně pokouší vyloučit odlehlé hodnoty a najít lineární model, který při výpočtu používá pouze inliery. To se provádí přizpůsobením lineárních modelů několika náhodným vzorkům dat a vrácením modelu, který nejlépe vyhovuje podmnožině dat. Protože inliery mají tendenci být více lineárně příbuzné než náhodná směs inliers a outliers, náhodná podmnožina, která se skládá výhradně z inliers, bude mít nejlepší přizpůsobení modelu. V praxi neexistuje záruka, že bude podmnožina inliers náhodně vzorkována a pravděpodobnost úspěchu algoritmu závisí na poměru inliers v datech a na volbě několika parametrů algoritmu.

• 

  Soubor dat s mnoha odlehlými hodnotami, pro které musí být linka osazena.

• 

  Vybavená řada s RANSAC; odlehlé hodnoty nemají žádný vliv na výsledek.

Přehled

Algoritmus RANSAC je učební technika pro odhad parametrů modelu náhodným vzorkováním pozorovaných dat. Vzhledem k datové sadě, jejíž datové prvky obsahují inliers i outliers, používá RANSAC hlasovací schéma k nalezení optimálního výsledku. Datové prvky v datové sadě se používají k hlasování pro jeden nebo více modelů. Implementace tohoto hlasovacího schématu je založena na dvou předpokladech: že hlučné funkce nebudou hlasovat konzistentně pro žádný jednotlivý model (několik odlehlých hodnot) a existuje dostatek funkcí k dohodě na dobrém modelu (několik chybějících údajů). Algoritmus RANSAC je v podstatě složený ze dvou kroků, které se iterativně opakují:

1. V prvním kroku je ze vstupní datové sady náhodně vybrána ukázková podmnožina obsahující minimální datové položky. Přizpůsobovací model a odpovídající parametry modelu se počítají pouze pomocí prvků této ukázkové podmnožiny. Mohutnost podmnožiny vzorků je nejmenší dostatečná k určení parametrů modelu.
2. Ve druhém kroku algoritmus kontroluje, které prvky celé datové sady jsou konzistentní s modelem vytvořeným pomocí odhadovaných parametrů modelu získaných z prvního kroku. Datový prvek se bude považovat za odlehlou hodnotu, pokud se nehodí na model přizpůsobení vytvořený sadou odhadovaných parametrů modelu v rámci určité prahové hodnoty chyby, která definuje maximální odchylku přičitatelnou účinku šumu.

Sada inliers získaných pro model přizpůsobení se nazývá konsensuální sada. Algoritmus RANSAC bude iterativně opakovat výše uvedené dva kroky, dokud získaný konsenzus nastavený v určité iteraci nebude mít dostatek inliers.

Vstupem do algoritmu RANSAC je sada hodnot pozorovaných dat, způsob přizpůsobení pozorování nějakým modelem a některé důvěra parametry. RANSAC dosahuje svého cíle opakováním následujících kroků:

1. Vyberte náhodnou podmnožinu původních dat. Nazvěte tuto podmnožinu hypotetické inliery.
2. Sada hypotetických vložek je vybavena modelem.
3. Všechny ostatní údaje jsou poté testovány na namontovaném modelu. Ty body, které dobře zapadají do odhadovaného modelu, podle některých specifických modelů funkce ztráty, jsou považovány za součást sada konsensu.
4. Odhadovaný model je přiměřeně dobrý, pokud bylo dostatečně mnoho bodů klasifikováno jako součást souboru konsensu.
5. Poté může být model vylepšen jeho novým odhadem pomocí všech členů konsensuální sady.

Tento postup se opakuje fixní počet opakování pokaždé, když se vytvoří model, který je odmítnut, protože příliš málo bodů je součástí sady konsensu, nebo vylepšený model spolu s odpovídající velikostí sady konsensu. V druhém případě zachováme vylepšený model, pokud je jeho sada konsensu větší než dříve uložený model.

• 

  RANSAC: Inliers and Outliers.

Algoritmus

Obecný algoritmus RANSAC funguje následovně:

Zadáno: data - soubor pozorování. model - Model pro vysvětlení pozorovaných datových bodů. n - Minimální počet datových bodů potřebných k odhadu parametrů modelu. k - Maximální počet iterací povolených v algoritmu. t - Prahová hodnota pro určení datových bodů, které jsou vhodné pro daný model. d - Počet blízkých datových bodů potřebných k tvrzení, že model vyhovuje datům. Návrat: bestFit - parametry modelu, které nejlépe vyhovují datům (nebo null, pokud není nalezen dobrý model) iterace = 0bestFit = nullbestErr = něco opravdu velkéhozatímco iterace < k dělat    possibleInliers: = n náhodně vybraných hodnot z dat možnáModel: = parametry modelu přizpůsobené možnáInliers alsoInliers: = prázdná sada pro každý bod v datech není v možnáInliers dělat        -li bod zapadá možnáModel s chybou menší než t přidá bod k alsoInliers konec pro    -li počet prvků v alsoInliers je> d pak        // To znamená, že jsme možná našli dobrý model // nyní otestujte, jak dobrý je. betterModel: = parametry modelu přizpůsobené všem bodům v snadInliers a alsoInliers thisErr: = míra toho, jak dobře se do těchto bodů lépe model hodí -li thisErr pak            bestFit: = betterModel bestErr: = thisErr skončit, pokud    skončit, pokud    iterace přírůstkuskončit chvílivrátit se bestFit

Parametry

Prahová hodnota pro určení, kdy se datový bod hodí k modelu ta počet blízkých datových bodů potřebných k tvrzení, že model dobře zapadá do dat d jsou stanoveny na základě konkrétních požadavků aplikace a datové sady a případně na základě experimentálního vyhodnocení. Počet iterací klze však určit jako funkci požadované pravděpodobnosti úspěchu p pomocí teoretického výsledku. Nechat p být požadovanou pravděpodobností, že algoritmus RANSAC po spuštění poskytne užitečný výsledek. RANSAC vrátí úspěšný výsledek, pokud v nějaké iteraci vybere ze vstupní sady dat pouze inliery, když zvolí n body, ze kterých se odhadují parametry modelu. Nechat ${ displaystyle w}$ pravděpodobnost výběru inlieru pokaždé, když je vybrán jeden bod, tj.

${ displaystyle w}$ = počet inliers v datech / počet bodů v datech

Běžným případem je to ${ displaystyle w}$ není předem dobře známo, ale lze uvést určitou hrubou hodnotu. Za předpokladu, že n body potřebné pro odhad modelu jsou vybírány samostatně, ${ displaystyle w ^ {n}}$ je pravděpodobnost, že vše n body jsou inliers a ${ displaystyle 1-w ^ {n}}$ je pravděpodobnost, že alespoň jeden z n points je odlehlý případ, což znamená, že z této množiny bodů bude odhadnut špatný model. Ta pravděpodobnost k moci k je pravděpodobnost, že algoritmus nikdy nevybere množinu n body, které jsou všechny inliery, a to musí být stejné jako ${ displaystyle 1-p}$. Tudíž,

${ displaystyle 1-p = (1-w ^ {n}) ^ {k} ,}$

ke kterému po vynesení logaritmu obou stran dojde

${ displaystyle k = { frac { log (1-p)} { log (1-w ^ {n})}}}$

Tento výsledek předpokládá, že n datové body jsou vybírány nezávisle, to znamená, že bod, který byl jednou vybrán, je nahrazen a může být znovu vybrán ve stejné iteraci. To často není rozumný přístup a odvozená hodnota pro k je třeba brát jako horní limit v případě, že jsou body vybrány bez náhrady. Například v případě nalezení řádku, který odpovídá datové sadě znázorněné na výše uvedeném obrázku, algoritmus RANSAC obvykle zvolí dva body v každé iteraci a vypočítá Možná_model protože čára mezi body a to je pak rozhodující, že dva body jsou odlišné.

Chcete-li získat další důvěru, standardní odchylka nebo jejich násobky lze přidat k. Směrodatná odchylka k je definován jako

${ displaystyle operatorname {SD} (k) = { frac { sqrt {1-w ^ {n}}} {w ^ {n}}}}$

Výhody a nevýhody

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Září 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Výhodou RANSACu je jeho schopnost dělat robustní odhad^[2] parametrů modelu, tj. dokáže odhadnout parametry s vysokou mírou přesnosti, i když je jich významný počet odlehlé hodnoty jsou obsaženy v datové sadě. Nevýhodou RANSACu je, že neexistuje žádná horní hranice času potřebného k výpočtu těchto parametrů (kromě vyčerpání). Když je počet vypočítaných iterací omezený, získané řešení nemusí být optimální a nemusí to být ani takové, které se hodí k datům dobrým způsobem. Tímto způsobem nabízí RANSAC kompromis; výpočtem většího počtu iterací se zvyšuje pravděpodobnost vytvoření rozumného modelu. Navíc RANSAC není vždy schopen najít optimální sadu ani pro středně znečištěné sady a obvykle je špatný, když je počet inomerů menší než 50%. Optimální RANSAC ^[3] bylo navrženo k řešení obou těchto problémů a je schopné najít optimální sadu pro silně znečištěné sady, dokonce i pro poměr inlierů pod 5%. Další nevýhodou systému RANSAC je, že vyžaduje stanovení prahových hodnot specifických pro daný problém.

RANSAC může odhadnout pouze jeden model pro konkrétní datovou sadu. Pokud jde o jakýkoli přístup jednoho modelu, když existují dvě (nebo více) instance modelu, RANSAC nemusí najít ani jednu. The Hough transformace je jedna alternativní technika robustního odhadu, která může být užitečná, když je přítomna více než jedna instance modelu. Další přístup k montáži více modelů je známý jako PEARL,^[4] který kombinuje modelové vzorkování z datových bodů jako v RANSAC s iterativním přehodnocením inliers a multimodální fiting formulovaný jako optimalizační problém s globální energetickou funkcí popisující kvalitu celkového řešení.

Aplikace

Algoritmus RANSAC se často používá v počítačové vidění, např. současně řešit problém s korespondencí a odhadněte základní matice vztahující se k dvojici stereofonních kamer; viz také: Struktura z pohybu, měřítko-neměnná transformace funkcí, šití obrazu, tuhá segmentace pohybu.

Vývoj a vylepšení

Od roku 1981 se RANSAC stal základním nástrojem v EU počítačové vidění a komunita zpracování obrazu. V roce 2006, u příležitosti 25. výročí algoritmu, byl uspořádán workshop na International Konference o počítačovém vidění a rozpoznávání vzorů (CVPR) k shrnutí nejnovějších příspěvků a variací k původnímu algoritmu, které mají většinou zlepšit rychlost algoritmu, robustnost a přesnost odhadovaného řešení a snížit závislost od uživatelem definovaných konstant.

RANSAC může být citlivý na výběr správné prahové hodnoty šumu, která definuje, které datové body se hodí pro model vytvořený pomocí určité sady parametrů. Pokud je taková prahová hodnota příliš velká, pak mají všechny hypotézy tendenci být hodnoceny stejně (dobře). Na druhou stranu, když je prahová hodnota šumu příliš malá, mají odhadované parametry tendenci být nestabilní (tj. Pouhým přidáním nebo odebráním vztažného bodu k sadě inliers může odhad parametrů kolísat). Pro částečnou kompenzaci tohoto nežádoucího účinku Torr et al. navrhla dvě modifikace RANSAC s názvem MSAC (M-estimator SAmple and Consensus) a MLESAC (Maximum Likelihood Estimation SAmple and Consensus).^[5] Hlavní myšlenkou je vyhodnotit kvalitu konsensuálního souboru (tj. Dat, která se hodí k modelu a určité sadě parametrů) a vypočítat jeho pravděpodobnost (zatímco v původní formulaci Fischlera a Bollese byla hodnost kardinálností takového souboru). Tordoff navrhuje rozšíření MLESAC, které zohledňuje předchozí pravděpodobnosti spojené se vstupní datovou sadou.^[6] Výsledný algoritmus se nazývá Guided-MLESAC. Podobným způsobem navrhl Chum řídit postup vzorkování, pokud jsou známy nějaké apriorní informace týkající se vstupních dat, tj. Zda je pravděpodobné, že datum bude inlier nebo outlier. Navrhovaný přístup se nazývá PROSAC, PROGRESIVNÍ BEZPLATNÝ Konsenzus.^[7]

Chum a kol. také navrhl randomizovanou verzi RANSACu nazvanou R-RANSAC ^[8] snížit výpočetní zátěž a určit dobrou sadu konsensu. Základní myšlenkou je zpočátku vyhodnotit správnost aktuálně vytvořeného modelu pomocí pouze redukované sady bodů namísto celé datové sady. Dobrá strategie s vysokou jistotou prozradí, kdy je třeba vyhodnotit přizpůsobení celého souboru dat nebo kdy lze model snadno vyřadit. Je rozumné si myslet, že dopad tohoto přístupu je relevantnější v případech, kdy je procento inliers velké. Typ strategie navrhovaný Chumem a kol. se nazývá předkupní schéma. Nistér navrhl paradigma zvané Preemptivní RANSAC^[9] který umožňuje v reálném čase robustní odhad struktury scény a pohybu kamery. Základní myšlenka tohoto přístupu spočívá ve generování pevného počtu hypotéz, aby se srovnání odehrálo s ohledem na kvalitu vytvořené hypotézy, spíše než s nějakou absolutní metrikou kvality.

Jiní vědci se pokusili vyrovnat se s obtížnými situacemi, kdy stupnice šumu není známa a / nebo je přítomno více modelových případů. První problém řešili v práci Wang a Suter.^[10] Toldo a kol. představují každý vztažný bod s charakteristickou funkcí sady náhodných modelů, které odpovídají bodu. Pak se více modelů odhalí jako klastry, které seskupují body podporující stejný model. Algoritmus shlukování, nazývaný J-propojení, nevyžaduje předchozí specifikaci počtu modelů, ani nevyžaduje ruční ladění parametrů.^[11]

RANSAC byl také přizpůsoben pro aplikace pro odhad rekurzivního stavu, kde jsou vstupní měření poškozena odlehlými hodnotami a přístupy Kalmanova filtru, které se spoléhají na Gaussovo rozdělení chyby měření, jsou odsouzeny k selhání. Takový přístup se nazývá KALMANSAC.^[12]

Související metody

• MLESAC (Maximum Likelihood Estimate Sample Consensus) - maximalizuje pravděpodobnost že data byla generována z modelu vybaveného vzorkem, např. A směsný model odlehlých a odlehlých hodnot
• MAPSAC (Maximum A posterior Sample Consensus) - rozšiřuje MLESAC o začlenění a předchozí pravděpodobnost parametrů, které mají být namontovány, a maximalizuje zadní pravděpodobnost
• KALMANSAC – kauzální závěr státu a dynamický systém
• Převzorkování (statistika)

Poznámky

Reference

• Martin A. Fischler a Robert C. Bolles (červen 1981). „Náhodná shoda vzorků: Paradigma pro přizpůsobení modelu aplikacím pro analýzu obrazu a automatickou kartografii“ (PDF). Comm. ACM. 24 (6): 381–395. doi:10.1145/358669.358692. S2CID  972888.
• David A. Forsyth a Jean Ponce (2003). Počítačové vidění, moderní přístup. Prentice Hall. ISBN  978-0-13-085198-7.
• Richard Hartley a Andrew Zisserman (2003). Geometrie více pohledů v počítačovém vidění (2. vyd.). Cambridge University Press.
• Strutz, T. (2016). Přizpůsobení dat a nejistota (praktický úvod do vážených nejmenších čtverců a dále). 2. vydání, Springer Vieweg. ISBN  978-3-658-11455-8.
• P.H.S. Torr & D.W. Murray (1997). „Vývoj a srovnání robustních metod pro odhad základní matice“. International Journal of Computer Vision. 24 (3): 271–300. doi:10.1023 / A: 1007927408552. S2CID  12031059.
• Ondrej Chum (2005). „Odhad geometrie dvou pohledů náhodným vzorkem a konsensem“ (PDF). PHD práce.
• Sunglok Choi; Taemin Kim & Wonpil Yu (2009). „Hodnocení výkonu rodiny RANSAC“ (PDF). Ve sborníku z konference British Machine Vision Conference (BMVC).

• Anders Hast; Johan Nysjö; Andrea Marchetti (2013). „Optimal RANSAC - Směrem k opakovatelnému algoritmu pro nalezení optimální sady“ (PDF). Deník WSCG. 21 (1): 21–30.
• Hossam Isack; Yuri Boykov (2012). „Energeticky založené geometrické tvarování více modelů“ (PDF). International Journal of Computer Vision. 97 (2: 1): 23–147. CiteSeerX  10.1.1.381.2434. doi:10.1007 / s11263-011-0474-7. S2CID  5461268.