RANSAC ( zkr. RANdom SAmple Consensus ) je stabilní metoda pro odhad parametrů modelu na základě náhodných vzorků . Schéma RANSAC je odolné vůči zašumění vstupních dat. Metoda byla navržena v roce 1981 Fischlerem a Bollesem.
Často se vyskytuje úloha zpracování dat, ve které je nutné určit parametry modelu, které musí splňovat výchozí data. Všechna počáteční data lze rozdělit do dvou typů: dobré body, které splňují model, „neodlehlé hodnoty“ nebo „vložené vrstvy“ ( anglicky inlier ) a falešné body, šumy jsou náhodné zahrnutí v původních datech, „odlehlé hodnoty“ nebo „odlehlé vrstvy“ ( anglicky ) .outlier
Zvažte nejjednodušší příklad toho, jak algoritmus funguje: vepsání přímky do 2D bodu . Za předpokladu, že data obsahují odlehlé hodnoty, způsobí odhad parametrů standardním způsobem, jako jsou nejmenší čtverce , nesprávný výpočet modelu, protože model je sestaven ze všech bodů. Metoda RANSAC bere jako základ pouze dva body nutné k sestavení přímky a s jejich pomocí sestaví model, načež pomocí odhadové funkce s danou prahovou hodnotou zkontroluje, kolik bodů odpovídá modelu.
Sada dat, do které se má vejít čára. emise jsou hojné.
Přímka navržená algoritmem RANSAC. odlehlé hodnoty neovlivňují výsledek.
Vstupem algoritmu je:
Celý algoritmus se skládá z jedné smyčky, jejíž každou iteraci lze logicky rozdělit do dvou fází.
Na konci smyčky zbývá poslední nejlepší hypotéza.
Výsledky metody jsou:
Hodnota parametru by měla být stanovena v závislosti na konkrétních požadavcích v závislosti na datech, ve většině případů až po experimentálních vyhodnoceních. Počet iterací lze určit před provedením algoritmu teoretickým odhadem. Nechť je pravděpodobnost, že algoritmus RANSAC při nějaké iteraci , při výběru bodů, na kterých je model založen, vezme pro výpočty pouze vložky z počátečního souboru dat. V takové situaci bude model sestavený z těchto bodů pravděpodobně docela přesný. Na základě toho můžeme použít pravděpodobnost p k odhadu přesnosti algoritmu. Nechť je pravděpodobnost výběru jedné vrstvy z celkového počtu bodů, tj . kde je počet vrstev a celkový počet bodů. Ve většině případů není procento vložek před spuštěním algoritmu známo, ale téměř vždy lze provést nějaký hrubý odhad. Pravděpodobnost nezávislého výběru n vrstev z počátečních dat je v tomto případě , a pravděpodobnost, že alespoň jeden bod z množiny je odlehlý, tedy že bude sestaven nesprávný model, je . Pravděpodobnost, že během iterací algoritmus nikdy nevybere vložky je , tato situace znamená, že nebude sestaven přesný model a pravděpodobnost této události je . Takto
Vyjádřeme počet iterací , které potřebujeme k
Výhodou algoritmu RANSAC je jeho schopnost poskytnout spolehlivý odhad parametrů modelu, to znamená schopnost odhadnout parametry modelu s vysokou přesností, i když v původním souboru dat existuje významný počet odlehlých hodnot.
Jednou z nevýhod metody RANSAC je absence horní hranice času potřebného k výpočtu parametrů modelu. Pokud použijeme maximální počet iterací jako nějaký časový limit, nemusí být výsledné řešení optimální a je také velmi malá pravděpodobnost, že žádný model nebude odpovídat původním datům. Přesný model lze určit s určitou pravděpodobností, která se zvětšuje, čím více iterací se používá. Další nevýhodou metody RANSAC je, že je nutné nastavit konkrétní prahovou hodnotu, aby bylo možné algoritmus provést. A konečně, metoda RANSAC může určit pouze jeden model pro konkrétní soubor dat. Stejně jako u každého přístupu založeného na jediném modelu je zde problém: když jsou ve vstupních datech přítomny dva (nebo více) modelů, RANSAC nemusí najít žádný.
Algoritmus RANSAC se často používá v počítačovém vidění , například k řešení problému shody obrazu a odhadu základní matice pro určení parametrů polohy kamery.