RANSAC

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

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

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

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

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

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

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

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

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

Кількість ітерацій можна оцінити через бажану ймовірність успіху. Нехай ${\displaystyle p}$ — імовірність того, що алгоритм хоча б один раз вибере придатну вибірку, ${\displaystyle w}$ — частка точок, які узгоджуються з правильною моделлю, а ${\displaystyle n}$ — мінімальна кількість точок, необхідна для оцінювання її параметрів. Тоді ймовірність того, що всі ${\displaystyle n}$ випадково вибраних точок належать до правильної моделі, дорівнює ${\displaystyle w^{n}}$. Відповідно, ймовірність отримати принаймні одну неправильну точку в такій вибірці становить ${\displaystyle 1-w^{n}}$.

Якщо виконати ${\displaystyle k}$ незалежних ітерацій, імовірність жодного разу не отримати повністю придатну вибірку дорівнює

${\displaystyle 1-p=(1-w^{n})^{k}.}$

Звідси рекомендовану кількість ітерацій оцінюють як

${\displaystyle k={\frac {\log(1-p)}{\log(1-w^{n})}}.}$

На практиці частка ${\displaystyle w}$ заздалегідь невідома, тому використовують її приблизну оцінку або перераховують необхідну кількість ітерацій під час роботи алгоритму. Чим меншою є очікувана частка правильних даних або чим більше точок потрібно для побудови однієї моделі, тим більше ітерацій необхідно. Наведене співвідношення припускає незалежний вибір точок; у разі вибірки без повернення отримане значення ${\displaystyle k}$ можна розглядати як консервативну верхню оцінку.^[1]

Реалізація у 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);

• Перетворення Гафа

1. ↑ Fischler, Martin A.; Bolles, Robert C. (1981). Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Communications of the ACM. 24 (6): 381—395. doi:10.1145/358669.358692.