Модель із мінімальної вибірки, а не з усіх даних
У червні 1981 року Мартін Фішлер і Роберт Боллс опублікували RANSAC. Замість того щоб усереднювати всі виміри, метод бере мінімальну кількість точок, потрібну для гіпотези, будує модель і рахує, скільки решти з нею узгоджується. У досліді з двадцяти орієнтирів, п'ять із яких були грубо помилковими, метод знайшов правильний розв'язок з другої трійки точок і не взяв жодної помилкової.
Чому це важливо
Геометрію стало можливо рахувати на виході детекторів, які помиляються. Найменші квадрати цього не витримують за побудовою: одна груба помилка тягне оцінку за собою. Звідси починається практичний стереозір, суміщення знімків і пізніше SLAM, бо всі вони живуть на помилкових відповідностях.
У тому самому досліді евристика на найменших квадратах, яка по черзі викидає найгіршу точку, зупинилася на розв'язку з 18 відповідностей, три з яких були грубо помилкові. Стаття наводить таблицю сподіваної кількості спроб E(k) = w⁻ⁿ: за частки правильних точок w = 0.5 і вибірки з трьох точок це 8.0 спроби. Окремо виведено k = log(1 − z)/log(1 − b); для w = 0.5, вибірки з чотирьох точок і 90-відсоткової певності це дає k = 35.7. Для задачі положення камери за трьома точками доведено верхню межу в чотири розв'язки. Запис не стверджує «23 ітерацій для надійності 0.95 за 50 % викидів». Такого числа в статті немає: наведені вище 8.0 і 35.7 — це те, що надруковано.