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.

RANSAC taikymas klaidingiems duomenims aptikti

Santrauka. Nūdienos skaitmenine fotogrametrija nagrinėja fotografinių vaizdų, kuriuose gausu duomenų, apdorojimo procedūras, todėl automatiškai rasti geriausia 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. Analizuojamas 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 turima tašku visuma, radimo ypatumai. RANSAC efektyvumui nustatyti atliktas eksperimentas – įvertintos tiesios linijos generavimo procedūros, kai nurodoma minimali tikimybe bei paklaidos dydis (žr. 5 pav., 2 lentele). Eksperimento metu nustatyta, kad teisingo sprendimo tikimybe bus mažesne, jei duomenų modelis bus mažesnis, o matavimu paklaidos didesnes. Tyrimo rezultatai parode, kad net ir esant 80 % klaidingu 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.

First published online: 03 Aug 2012

Keyword : statistics, uncertainty, probability, parameter estimation, outliers, inliers, matching