Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

RANSAC абр RANdom SAmple Consensus це ітеративний метод що використовується для оцінки параметрів математичної моделі дл

RANSAC

RANSAC

RANSAC (абр. RANdom SAmple Consensus) це ітеративний метод, що використовується для оцінки параметрів математичної моделі для набору спостережуваних даних, які містять викиди.

Це недетермінований алгоритм, в тому сенсі, що він знаходить прийнятне рішення тільки з певною імовірністю, імовірність зростає відповідно до зростання кількості ітерацій. Алгоритм вперше був опублікований Fischler і Bolles в SRI International в 1981. Вони використовували алгоритм в задачах визначення положення (англ. Location Determination Problem, LDP), де головна задача — визначити положення точок у просторі, знаючи їхні проєкції на площину зображення.

Алгоритм ґрунтується на припущенні, вихідні дані складаються з викидів і не-викидів. Не-викиди задовольняють математичну модель з певним набором параметрів, тоді як викиди є результатом шумів, і не задовольняють моделі. RANSAC також припускає, що існує процедура, яка по невеликому набору не-викидів може оцінити параметри моделі, що оптимально відповідає вхідним даним.

Приклад

Простим прикладом є знаходження лінії по набору точок для двовимірного випадку. Припускаючи, що набір даних складається з не-викидів — тобто точок, які приблизно можуть бути наближені прямою, і викидів — точок, що не можуть бути наближені прямою. Якщо використовувати звичайний метод найменших квадратів якість наближення буде поганою. Причиною цьому є те, що метод буде намагатися підібрати коефіцієнти так, щоб задовольнити всім точкам включно з викидами. RANSAC з іншого боку, у випадку, якщо імовірність вибрати з набору даних тільки не-викиди достатньо висока, може створити модель, яка буде обчислена тільки на не-викидах.

  • image
    Набір даних з великою кількістю викидів.
  • image
    Лінія знайдена за допомогою алгоритму RANSAC; викиди не вплинули на результат.

Опис алгоритму

  1. Вибрати випадкову підмножину з вхідних даних. Назвемо її потенційні не-викиди.
  2. Підібрати параметри моделі для набору потенційних не-викидів.
  3. Всі інші точки перевіряються на приналежність до прямої. Точки які з деякою точністю належать до прямої назвемо набором погоджених точок.
  4. Модель вважається достатньо вдалою, якщо достатньо великий відсоток точок належить до набору погоджених точок.
  5. Далі модель може бути уточнена використовуючи всі точки з набору погоджених точок.

Ця операція проводиться певну кількість разів, як результат обираємо модель з найбільшим набором погоджених точок.

  • image
    RANSAC: викиди і не-викиди.

Реалізація у Matlab

Реалізація у Matlab для знаходженні лінії у 2D за допомогою алгоритму RANSAC:

 function [bestParameter1,bestParameter2] = ransac_demo(data,num,iter,threshDist,inlierRatio)  % data: a 2xn dataset with #n data points  % num: the minimum number of points. For line fitting problem, num=2  % iter: the number of iterations  % threshDist: the threshold of the distances between points and the fitting line  % inlierRatio: the threshold of the numer of inliers     %% Plot the data points  figure;plot(data(1,:),data(2,:),'o');hold on;  number = size(data,2); % Total number of points  bestInNum = 0; % Best fitting line with largest number of inliers  bestParameter1=0;bestParameter2=0; % parameters for best fitting line  for i=1:iter  %% Randomly select 2 points  idx = randperm(number,num); sample = data(:,idx);   %% Compute the distances between all points with the fitting line   kLine = sample(:,2)-sample(:,1);  kLineNorm = kLine/norm(kLine);  normVector = [-kLineNorm(2),kLineNorm(1)];  distance = normVector*(data - repmat(sample(:,1),1,number));  %% Compute the inliers with distances smaller than the threshold  inlierIdx = find(abs(distance)<=threshDist);  inlierNum = length(inlierIdx);  %% Update the number of inliers and fitting model if better model is found   if inlierNum>=round(inlierRatio*number) && inlierNum>bestInNum  bestInNum = inlierNum;  parameter1 = (sample(2,2)-sample(2,1))/(sample(1,2)-sample(1,1));  parameter2 = sample(2,1)-parameter1*sample(1,1);  bestParameter1=parameter1; bestParameter2=parameter2;  end  end    %% Plot the best fitting line  xAxis = -number/2:number/2;   yAxis = bestParameter1*xAxis + bestParameter2;  plot(xAxis,yAxis,'r-','LineWidth',2);

Див. також

Ця стаття не містить . Ви можете допомогти поліпшити цю статтю, додавши посилання на . Матеріал без джерел може бути піддано сумніву та вилучено. (жовтень 2022)

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

RANSAC abr RANdom SAmple Consensus ce iterativnij metod sho vikoristovuyetsya dlya ocinki parametriv matematichnoyi modeli dlya naboru sposterezhuvanih danih yaki mistyat vikidi Ce nedeterminovanij algoritm v tomu sensi sho vin znahodit prijnyatne rishennya tilki z pevnoyu imovirnistyu imovirnist zrostaye vidpovidno do zrostannya kilkosti iteracij Algoritm vpershe buv opublikovanij Fischler i Bolles v SRI International v 1981 Voni vikoristovuvali algoritm v zadachah viznachennya polozhennya angl Location Determination Problem LDP de golovna zadacha viznachiti polozhennya tochok u prostori znayuchi yihni proyekciyi na ploshinu zobrazhennya Algoritm gruntuyetsya na pripushenni vihidni dani skladayutsya z vikidiv i ne vikidiv Ne vikidi zadovolnyayut matematichnu model z pevnim naborom parametriv todi yak vikidi ye rezultatom shumiv i ne zadovolnyayut modeli RANSAC takozh pripuskaye sho isnuye procedura yaka po nevelikomu naboru ne vikidiv mozhe ociniti parametri modeli sho optimalno vidpovidaye vhidnim danim PrikladProstim prikladom ye znahodzhennya liniyi po naboru tochok dlya dvovimirnogo vipadku Pripuskayuchi sho nabir danih skladayetsya z ne vikidiv tobto tochok yaki priblizno mozhut buti nablizheni pryamoyu i vikidiv tochok sho ne mozhut buti nablizheni pryamoyu Yaksho vikoristovuvati zvichajnij metod najmenshih kvadrativ yakist nablizhennya bude poganoyu Prichinoyu comu ye te sho metod bude namagatisya pidibrati koeficiyenti tak shob zadovolniti vsim tochkam vklyuchno z vikidami RANSAC z inshogo boku u vipadku yaksho imovirnist vibrati z naboru danih tilki ne vikidi dostatno visoka mozhe stvoriti model yaka bude obchislena tilki na ne vikidah Nabir danih z velikoyu kilkistyu vikidiv Liniya znajdena za dopomogoyu algoritmu RANSAC vikidi ne vplinuli na rezultat Opis algoritmuVibrati vipadkovu pidmnozhinu z vhidnih danih Nazvemo yiyi potencijni ne vikidi Pidibrati parametri modeli dlya naboru potencijnih ne vikidiv Vsi inshi tochki pereviryayutsya na prinalezhnist do pryamoyi Tochki yaki z deyakoyu tochnistyu nalezhat do pryamoyi nazvemo naborom pogodzhenih tochok Model vvazhayetsya dostatno vdaloyu yaksho dostatno velikij vidsotok tochok nalezhit do naboru pogodzhenih tochok Dali model mozhe buti utochnena vikoristovuyuchi vsi tochki z naboru pogodzhenih tochok Cya operaciya provoditsya pevnu kilkist raziv yak rezultat obirayemo model z najbilshim naborom pogodzhenih tochok RANSAC vikidi i ne vikidi Realizaciya u MatlabRealizaciya u Matlab dlya znahodzhenni liniyi u 2D za dopomogoyu algoritmu RANSAC function bestParameter1 bestParameter2 ransac demo data num iter threshDist inlierRatio data a 2xn dataset with n data points num the minimum number of points For line fitting problem num 2 iter the number of iterations threshDist the threshold of the distances between points and the fitting line inlierRatio the threshold of the numer of inliers Plot the data points figure plot data 1 data 2 o hold on number size data 2 Total number of points bestInNum 0 Best fitting line with largest number of inliers bestParameter1 0 bestParameter2 0 parameters for best fitting line for i 1 iter Randomly select 2 points idx randperm number num sample data idx Compute the distances between all points with the fitting line kLine sample 2 sample 1 kLineNorm kLine norm kLine normVector kLineNorm 2 kLineNorm 1 distance normVector data repmat sample 1 1 number Compute the inliers with distances smaller than the threshold inlierIdx find abs distance lt threshDist inlierNum length inlierIdx Update the number of inliers and fitting model if better model is found if inlierNum gt round inlierRatio number amp amp inlierNum gt bestInNum bestInNum inlierNum parameter1 sample 2 2 sample 2 1 sample 1 2 sample 1 1 parameter2 sample 2 1 parameter1 sample 1 1 bestParameter1 parameter1 bestParameter2 parameter2 end end Plot the best fitting line xAxis number 2 number 2 yAxis bestParameter1 xAxis bestParameter2 plot xAxis yAxis r LineWidth 2 Div takozhPeretvorennya GafaCya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno zhovten 2022

Дата публікації:
Топ