RANSAC for outlier detection

Abstract

Up-to-date digital photogrammetry involves operations on huge data sets, and with classical image processing procedures it might be time consuming to find out the best solution. One of the key tasks is to detect outliers in given data, eg for curve fitting or image matching. The problem is hard as the number of outliers is usually large, possibly larger than 50 %, thus powerful estimation techniques are needed. We demonstrate one of these techniques, namely Random Sample Consensus (RANSAC), for fitting a model to sample data, especially for fitting a straight line through a set of given points. Experiments with up to 80 % outliers prove the efficiency of RANSAC. The results are representative for image analysis in digital photogrammetry.

Nūdienos skaitmeninė fotogrametrija nagrinėja fotografinių vaizdų, kuriuose gausu duomenų, apdorojimo procedūras, todėl automatiškai rasti geriausią sprendimą ilgai trunka, būtina talpi kompiuterinė atmintis. Atliekant fotonuotraukų sugretinimą (matching), vienas iš pagrindinių uždavinių yra teisingai identifikuoti duomenų elementus. Sprendžiant šį uždavinį, kyla klaidingų duomenų, kurių paprastai yra daug (gali būti daugiau nei 50 %), eliminavimo problema. Tam tikslui turi būti parinkta tinkama duomenų įvertinimo metodika. Analizuojama statistinis duomenų įvertinimo metodas RANSAC (Random Sample Consensus), skirtas sudarytajam modeliui suderinti su parinktaisiais duomenimis, t. y. šiuo atveju nagrinėjama tiesios linijos, einančios per turimą taškų visumą, radimo ypatumai. RANSAC efektyvumui nustatyti atliktas eksperimentas – įvertintos tiesios linijos generavimo procedūros, kai nurodoma minimali tikimybė bei paklaidos dydis (žr. 5 pav., 2 lentelę). Eksperimento metu nustatyta, kad teisingo sprendimo tikimybė bus mažesnė, jei duomenų modelis bus mažesnis, o matavimų paklaidos didesnės. Tyrimo rezultatai parodė, kad net ir esant 80 % klaidingų duomenų (outliers), taikyti RANSAC yra labai efektyvu − įvedus teisingus parametrus, gaunamas optimalus sprendimas. RANSAC taikymo klaidingiems duomenims aptikti, atliekant automatinį vaizdų sugretinimą, galimybių tyrimas turėtų būti tęsiamas ateityje.