Кездейсоқ үлгілік келісім (RANSAC) әдісі

Кіріспе

Статистикалық әдіс

Кездейсоқ үлгіде консенсус (RANSAC) – бұл математикалық модельдің параметрлерін бағалауға арналған итеративті әдіс, ол ауытқушы деректер жиынтығынан қолданылады, мұнда ауытқушы деректер бағалау мәндеріне ешқандай әсер етпейді. Сондықтан, оны ауытқушы деректерді анықтау әдісі деп те қарастыруға болады. Бұл алгоритм детерминистік емес, яғни ол белгілі бір ықтималдықпен ғана қолайлы нәтиже береді, ал бұл ықтималдық итерациялар саны артық болған сайын ұлғаяды. Алгоритм алғаш рет 1981 жылы SRI International ұйымында Фишлер және Боллес есімді ғалымдар тарапынан жарияланды. Олар RANSAC-ты орналасуды анықтау мәселесін (LDP) шешу үшін қолданды, онда мақсат – белгілі орналасқан жерлерге проекцияланатын кеңістіктегі нүктелерді анықтау. RANSAC қайталанатын кездейсоқ ішкі жиындыларды пайдаланады. Негізгі болжам бойынша, деректер «ішкі мәндерден», яғни модель параметрлерінің белгілі бір жиынтығымен түсіндірілетін деректерден тұрады, бірақ шуға ұшырауы мүмкін, және «ауытқушы деректерден» – модельге сәйкес келмейтін деректерден. Ауытқушы деректер, мысалы, шудың шекті мәндерінен, қате өлшемдерден немесе деректерді түсіндіру туралы дұрыс емес гипотезалардан туындауы мүмкін. RANSAC сондай-ақ, егер (әдетте шағын) ішкі мәндер жиынтығы болса, осы деректерді ең жақсы түсіндіретін немесе сәйкес келетін модельдің параметрлерін бағалауға болатын процедура бар деп есептейді.

Мысал

Қарапайым мысал – екі өлшемді кеңістікте бақылаулар жиынына түзу сызық жүргізу. Егер бұл жиын сызыққа шамамен сәйкес келетін нүктелер, яғни инлиерлер, және осы сызыққа сәйкес келмейтін нүктелер, яғни аутлиерлерден тұрса, түзу сызықты сәйкестендірудің қарапайым ең кіші квадраттар әдісі әдетте инлиерлер мен аутлиерлерді қоса алғандағы деректерге нашар сәйкес келетін түзу сызық береді. Бұл себебі ол барлық нүктелерге, соның ішінде аутлиерлерге де ең жақсы сәйкес келеді. Ал RANSAC аутлиерлерді жоюға тырысып, есептеуінде тек инлиерлерді пайдаланатын сызықтық модельді табуға ұмтылады. Бұл деректердің бірнеше кездейсоқ іріктемелеріне сызықтық модельдерді сәйкестендіру арқылы және деректердің ең жақсы сәйкес келетін кіші жиынына жататын модельді қайтару арқылы іске асырылады. Инлиерлер инлиерлер мен аутлиерлердің кездейсоқ араласуына қарағанда сызықтық байланыста болуға бейім болғандықтан, тек инлиерлерден тұратын кездейсоқ іріктеме ең жақсы модельге сәйкес келеді. Бірақ іс жүзінде инлиерлердің кіші жиынының кездейсоқ іріктелетініне кепілдік жоқ, және алгоритмнің сәтті болу ықтималдығы деректердегі инлиерлердің үлесіне және алгоритмнің бірнеше параметрлерін таңдауға байланысты.

Шолу

RANSAC алгоритмі – байқалған деректердің кездейсоқ үлгісін алу арқылы модель параметрлерін бағалаудың оқу әдісі. Деректер жиынтығында инлидерлер мен аутлаерлер болғанда, RANSAC дауыс беру схемасын қолданады. Деректер жиынтығындағы деректер элементтері бір немесе бірнеше модельдерге дауыс беру үшін пайдаланылады. Бұл дауыс беру схемасын іске асыру екі болжамға негізделген: шулы деректер ешбір модельге тұрақты түрде дауыс бермейді (аутлаерлердің аздығы) және жақсы модельді анықтау үшін жеткілікті деректер бар (жетіспейтін деректердің аздығы). RANSAC алгоритмі негізінен екі қадамнан тұрады, олар итеративті қайталанады: Бірінші қадамда кіріс деректер жиынтығынан минималды деректер элементтерін қамтитын үлгілік кіші жиынтық кездейсоқ таңдалады. Модель параметрлері бар сәйкестік модель осы үлгілік кіші жиынның элементтерін ғана пайдалана отырып есептеледі. Үлгілік кіші жиынның өлшемі (мысалы, осы кіші жиынтағы деректердің мөлшері) модель параметрлерін анықтау үшін жеткілікті. Екінші қадамда алгоритм кіріс деректер жиынтығының қай элементтері бірінші қадамда алынған модель параметрлерімен есептелген модельге сәйкес келетінін тексереді. Егер деректер элементі модельге сәйкес келмесе, онда ол инлидерлердің максималды ауытқуын анықтайтын қате шегі шегінде аутлаер ретінде қарастырылады. (Бұл ауытқудан тыс деректер элементтері аутлаерлер болып табылады.) Сәйкестік модель үшін алынған инлидерлер жиынтығы консенсус жиынтығы деп аталады. RANSAC алгоритмі жоғарыда аталған екі қадамды белгілі бір итерациядағы алынған консенсус жиынтығында жеткілікті инлидерлер болғанға дейін қайталайды. RANSAC алгоритміне кіріс деректер – бақыланған деректер мәндерінің жиынтығы, бақылауларға сәйкес келетін модель және аутлаерлерді анықтайтын сенім параметрлері болып табылады. Аталған RANSAC алгоритмінің жалпы сипаттамасынан гөрі егжей-тегжейлі қарастырғанда, RANSAC келесі қадамдарды қайталау арқылы мақсатына жетеді: Бастапқы деректердің кездейсоқ кіші жиынтығын таңдаңыз. Бұл кіші жиынтықты гипотетикалық инлидерлер деп атаңыз. Гипотетикалық инлидерлер жиынтығына модель орнатылады. Барлық деректер орнатылған модельмен салыстырылады. Белгілі бір модельге тән шығын функциясына сәйкес бағаланған модельге жақсы сәйкес келетін барлық деректер нүктелері (түпнұсқалық деректер) консенсус жиынтығы (яғни модель үшін инлидерлер жиынтығы) деп аталады. Консенсус жиынтығының бөлігі ретінде жеткілікті сандағы деректер нүктелері жіктелсе, бағаланған модель жеткілікті жақсы болады. Модель консенсус жиынтығының барлық мүшелерін пайдалану арқылы оны қайта бағалау арқылы жетілдірілуі мүмкін. Модельдің консенсус жиынтығына қаншалықты сәйкес келетінін өлшейтін сәйкестік сапасы модельдің сәйкестігін итерациялардың жалғасуымен (мысалы, келесі итерацияда осы өлшемені сәйкестік сапасының критерийлері ретінде орнату арқылы) жақсарту үшін қолданылады. Модель параметрлерінің жеткілікті жақсы жиынтығына жету үшін бұл процедура белгіленген санда қайталанады, әр жолы консенсус жиынтығының бөлігі өте аз нүктелер болғандықтан модель қабылданылмайды немесе бұрынғы консенсус жиынтығынан үлкен консенсус жиынтығымен жетілдірілген модель алынады.

The RANSAC algorithm is a learning technique to estimate parameters of a model by random sampling of observed data. Given a dataset whose data elements contain both inliers and outliers, RANSAC uses the voting scheme to find the optimal fitting result. Data elements in the dataset are used to vote for one or multiple models. The implementation of this voting scheme is based on two assumptions: that the noisy features will not vote consistently for any single model (few outliers) and there are enough features to agree on a good model (few missing data). The RANSAC algorithm is essentially composed of two steps that are iteratively repeated:
In the first step, a sample subset containing minimal data items is randomly selected from the input dataset. A fitting model with model parameters is computed using only the elements of this sample subset. The cardinality of the sample subset (e. g., the amount of data in this subset) is sufficient to determine the model parameters. In the second step, the algorithm checks which elements of the entire dataset are consistent with the model instantiated by the estimated model parameters obtained from the first step. A data element will be considered as an outlier if it does not fit the model within some error threshold defining the maximum data deviation of inliers. (Data elements beyond this deviation are outliers.) The set of inliers obtained for the fitting model is called the consensus set. The RANSAC algorithm will iteratively repeat the above two steps until the obtained consensus set in certain iteration has enough inliers. The input to the RANSAC algorithm is a set of observed data values, a model to fit to the observations, and some confidence parameters defining outliers. In more details than the aforementioned RANSAC algorithm overview, RANSAC achieves its goal by repeating the following steps:

Select a random subset of the original data. Call this subset the hypothetical inliers. A model is fitted to the set of hypothetical inliers. All data are then tested against the fitted model. All the data points (of the original data) that fit the estimated model well, according to some model specific loss function, are called the consensus set (i. e., the set of inliers for the model). The estimated model is reasonably good if sufficiently many data points have been classified as a part of the consensus set. The model may be improved by re estimating it by using all the members of the consensus set. The fitting quality as a measure of how well the model fits to the consensus set will be used to sharpen the model fitting as iterations goes on (e. g., by setting this measure as the fitting quality criteria at the next iteration). To converge to a sufficiently good model parameter set, this procedure is repeated a fixed number of times, each time producing either the rejection of a model because too few points are a part of the consensus set, or a refined model with a consensus set size larger than the previous consensus set.

Артықшылықтары мен кемшіліктері

RANSAC-тің артықшылығы – модель параметрлерін берік бағалау қабілеті, яғни деректер жиынтығында көптеген сыртқы мәндер (outlier) болған жағдайда да параметрлерді жоғары дәлдікпен бағалай алады. RANSAC-тің кемшілігі – осы параметрлерді есептеуге кететін уақытқа белгілі бір шек жоқ (толық тексеруден басқа). Егер есептелген итерациялар саны шектелсе, алынған шешім оңтайлы болмауы мүмкін, тіпті деректерге жақсы сәйкес келмеуі де мүмкін. Осылайша, RANSAC мүмкіндік береді; итерациялардың санын арттыру арқылы жақсы модельдің табылу ықтималдығы артады. Сонымен қатар, RANSAC орташа ластанған жиынтықтар үшін де оптималды жиынтықты табуға әрқашан қабілетті болмайды және инлиерлер саны 50%-дан төмен болған кезде нашар жұмыс істейді. Оптималды RANSAC бұл екі мәселені шешу үшін ұсынылды және ол күшті ластанған жиынтықтар үшін, тіпті 5%-дан төмен инлиер қатынасы үшін де оптималды жиынтықты таба алады. RANSAC-тің тағы бір кемшілігі – ол проблемаға қатысты нақты шектік мәндерді белгілеуді қажет етеді. RANSAC тек бір деректер жиынтығы үшін бір модельді бағалай алады. Бір модельге негізделген әдіс ретінде, егер екі (немесе одан көп) модель болса, RANSAC олардың ешқайсысын таба алмауы мүмкін. Хоуг трансформациясы – бірнеше модель болған кезде пайдалы болатын басқа бір берік бағалау әдісі. Көп модельді сәйкестендірудің тағы бір әдісі PEARL деп аталады, ол RANSAC-тегі дерек нүктелерінен модельдік үлгі алуды инлиерлерді итеративті қайта бағалаумен біріктіреді, ал көп модельді сәйкестендіру жалпы шешімнің сапасын сипаттайтын жаһандық энергия функциясы бар оңтайландыру мәселесі ретінде құрылады.

Қолданбалар

RANSAC алгоритмі компьютерлік көруде жиі қолданылады, мысалы, сәйкестік мәселесін бірден шешу және стереокамералар жұбына қатысты негізгі матрицаны бағалау үшін; сондай-ақ қараңыз: Қозғалыстан құрылымды анықтау, масштабқа тәуелсіз ерекшеліктерді түрлендіру, кескіндерді тігіп қосу, қатаң қозғалыс сегментациясы.

Даму және жетілдіру

1981 жылдан бері RANSAC компьютерлік көру және бейне өңдеу қауымдастығының негізгі құралына айналды. 2006 жылы алгоритмнің 25 жылдығына арналған компьютерлік көру және үлгілерді тану жөніндегі халықаралық конференцияда (CVPR) семинар ұйымдастырылды. Семинарда бастапқы алгоритмге енгізілген соңғы үлестер мен өзгерістер талқыланды, олардың көпшілігі алгоритмнің жылдамдығын арттыруға, есептелген шешімнің сенімділігі мен дәлдігін жоғарылатуға және пайдаланушы анықтаған тұрақтыларға тәуелділікті азайтуға бағытталған. RANSAC белгілі бір параметрлер жиынтығымен құрылған модельге сәйкес келетін дерек нүктелерін анықтау үшін дұрыс шу шегін таңдауға сезімтал. Егер бұл шек тым жоғары болса, барлық гипотезалар бірдей жақсы деп бағаланады. Ал шу шегі тым төмен болса, есептелген параметрлер тұрақсыз болады (яғни, ішкі нүктелер жиынтығына бір дерек нүктесін қосу немесе алып тастау нәтижесінде параметрлердің бағасы өзгеруі мүмкін). Бұл жағымсыз әсерді ішінара жою үшін Torr және авторлар MSAC (M бағалаушысы, үлгі және консенсус) және MLESAC (максималды ықтималдық бағалауы, үлгі және консенсус) деп аталатын RANSAC-тің екі модификациясын ұсынды. Негізгі идея – консенсус жиынтығының сапасын бағалау (яғни, модельге және белгілі бір параметрлер жиынтығына сәйкес келетін деректер) оның ықтималдығын есептеу (ал Фишлер мен Боллстің бастапқы тұжырымдамасында рейтинг мұндай жиынтықтың кардиналдығы болды). Tordoff кіріс деректер жиынтығымен байланысты алдын ала ықтималдықтарды ескеретін MLESAC-тің кеңейтілген нұсқасын ұсынды. Нәтижесінде пайда болған алгоритм Guided MLESAC деп аталды. Осыған ұқсас, Чам кіріс деректері туралы кейбір априорлық ақпарат белгілі болған жағдайда, мысалы, дерек нүктесінің ішкі немесе сыртқы мән болуы мүмкін болса, үлгі алу процедурасын басқаруды ұсынды. Ұсынылған тәсіл PROSAC, PROgressive Sample Consensus деп аталды. Чам және авторлар жақсы консенсус жиынтығын анықтау үшін есептеу жүктемесін азайту мақсатында RANSAC-тің кездейсоқ нұсқасын, R RANSAC деп атады. Негізгі идея – қазіргі үлгінің жақсылығын бастапқыда барлық деректер жиынтығының орнына, төмендетілген нүктелер жиынтығын қолдана отырып бағалау. Дұрыс стратегия, бүкіл деректер жиынтығының сәйкестігін бағалау қажеттігін немесе модельді дереу қабылдамау қажеттігін жоғары сенімділікпен анықтайды. Бұл тәсілдің әсері ішкі нүктелердің үлесі жоғары жағдайларда маңыздырақ болуы мүмкін. Чам және авторлар ұсынған стратегияның түрі алдын алу схемасы деп аталады. Nistér сценаның құрылымы мен камераның қозғалысын нақты уақытта сенімді бағалауға мүмкіндік беретін Preemptive RANSAC деп аталатын парадигманы ұсынды. Тәсілдің негізгі идеясы – салыстыру абсолютті сапа метрикасына емес, жасалған гипотезаның сапасына қатысты болуы үшін, гипотезалардың белгіленген санын жасаудан тұрады. Басқа зерттеушілер шу деңгейі белгісіз және/немесе бірнеше модель мысалы бар қиын жағдайларды шешуге тырысты. Бұл мәселені Ван мен Сьютер өз жұмысында қарастырды. Toldo және авторлар әрбір дерек нүктесін сол нүктеге сәйкес келетін кездейсоқ модельдер жиынтығының сипаттамалық функциясымен бейнеледі. Содан кейін бірнеше модельдер кластерлер түрінде ашылады, олар бір модельді қолдайтын нүктелерді топтастырады. J байланысы деп аталатын кластерлеу алгоритмі модельдер санын алдын ала анықтауды қажет етпейді, сондай-ақ параметрлерді қолмен реттеуді қажет етпейді. RANSAC рекурсивті күйді бағалау қолданбалары үшін де бейімделді, онда кіріс өлшемдері сыртқы мәндермен бұзылады және өлшеу қателігінің Гаусс таралуына сүйенетін Калман сүзгісі тәсілдері сәтсіздікке ұшырайды. Мұндай тәсіл KALMANSAC деп аталады.

Since 1981 RANSAC has become a fundamental tool in the computer vision and image processing community. In 2006, for the 25th anniversary of the algorithm, a workshop was organized at the International Conference on Computer Vision and Pattern Recognition (CVPR) to summarize the most recent contributions and variations to the original algorithm, mostly meant to improve the speed of the algorithm, the robustness and accuracy of the estimated solution and to decrease the dependency from user defined constants. RANSAC can be sensitive to the choice of the correct noise threshold that defines which data points fit a model instantiated with a certain set of parameters. If such threshold is too large, then all the hypotheses tend to be ranked equally (good). On the other hand, when the noise threshold is too small, the estimated parameters tend to be unstable ( i. e. by simply adding or removing a datum to the set of inliers, the estimate of the parameters may fluctuate). To partially compensate for this undesirable effect, Torr et al. proposed two modification of RANSAC called MSAC (M estimator SAmple and Consensus) and MLESAC (Maximum Likelihood Estimation SAmple and Consensus). The main idea is to evaluate the quality of the consensus set ( i. e. the data that fit a model and a certain set of parameters) calculating its likelihood (whereas in the original formulation by Fischler and Bolles the rank was the cardinality of such set). An extension to MLESAC which takes into account the prior probabilities associated to the input dataset is proposed by Tordoff. The resulting algorithm is dubbed Guided MLESAC. Along similar lines, Chum proposed to guide the sampling procedure if some a priori information regarding the input data is known, i. e. whether a datum is likely to be an inlier or an outlier. The proposed approach is called PROSAC, PROgressive SAmple Consensus. Chum et al. also proposed a randomized version of RANSAC called R RANSAC to reduce the computational burden to identify a good consensus set. The basic idea is to initially evaluate the goodness of the currently instantiated model using only a reduced set of points instead of the entire dataset. A sound strategy will tell with high confidence when it is the case to evaluate the fitting of the entire dataset or when the model can be readily discarded. It is reasonable to think that the impact of this approach is more relevant in cases where the percentage of inliers is large. The type of strategy proposed by Chum et al. is called preemption scheme. Nistér proposed a paradigm called Preemptive RANSAC that allows real time robust estimation of the structure of a scene and of the motion of the camera. The core idea of the approach consists in generating a fixed number of hypotheses so that the comparison happens with respect to the quality of the generated hypothesis rather than against some absolute quality metric. Other researchers tried to cope with difficult situations where the noise scale is not known and/or multiple model instances are present. The first problem has been tackled in the work by Wang and Suter. Toldo et al. represent each datum with the characteristic function of the set of random models that fit the point. Then multiple models are revealed as clusters which group the points supporting the same model. The clustering algorithm, called J linkage, does not require prior specification of the number of models, nor does it necessitate manual parameters tuning. RANSAC has also been tailored for recursive state estimation applications, where the input measurements are corrupted by outliers and Kalman filter approaches, which rely on a Gaussian distribution of the measurement error, are doomed to fail. Such an approach is dubbed KALMANSAC.