Из Википедии, бесплатной энциклопедии
  (Перенаправлено из RANSAC )
Перейти к навигации Перейти к поиску

Консенсус случайной выборки ( RANSAC ) - это итерационный метод оценки параметров математической модели на основе набора наблюдаемых данных, содержащих выбросы , когда выбросы не должны влиять на значения оценок. Следовательно, его также можно интерпретировать как метод обнаружения выбросов. [1] Это недетерминированный алгоритм в том смысле, что он дает разумный результат только с определенной вероятностью, причем эта вероятность увеличивается с увеличением количества итераций. Алгоритм был впервые опубликован Фишлером и Боллесом в SRI International. в 1981 году. Они использовали RANSAC для решения задачи определения местоположения (LDP), цель которой состоит в том, чтобы определить точки в пространстве, которые проецируются на изображение в набор ориентиров с известными местоположениями.

Основное предположение состоит в том, что данные состоят из «выбросов», т. Е. Данных, распределение которых может быть объяснено некоторым набором параметров модели, хотя и может быть подвержено шуму, и «выбросов», которые представляют собой данные, которые не соответствуют модели. Выбросы могут возникать, например, из-за экстремальных значений шума или из-за ошибочных измерений или неверных гипотез об интерпретации данных. RANSAC также предполагает, что для заданного (обычно небольшого) набора вставок существует процедура, которая может оценивать параметры модели, которая оптимально объясняет или соответствует этим данным.

Пример [ править ]

Простым примером является подгонка линии в двух измерениях к набору наблюдений. Предполагая, что этот набор содержит как выбросы, т. Е. Точки, которые приблизительно могут соответствовать линии, так и выбросы, точки, которые не могут соответствовать этой линии, простой метод наименьших квадратовпри подгонке линии обычно получается линия с плохим соответствием данным, включая выбросы и выбросы. Причина в том, что он оптимально подходит для всех точек, включая выбросы. RANSAC, с другой стороны, пытается исключить выбросы и найти линейную модель, которая использует в своих расчетах только выбросы. Это делается путем подгонки линейных моделей к нескольким случайным выборкам данных и возврата модели, которая наилучшим образом соответствует подмножеству данных. Поскольку следы имеют тенденцию быть более линейно связанными, чем случайная смесь вставок и выбросов, случайное подмножество, полностью состоящее из вставок, будет лучше всего соответствовать модели. На практике нет гарантии, что подмножество инлирующих объектов будет выбрано случайным образом,и вероятность успеха алгоритма зависит от доли вставок в данных, а также от выбора нескольких параметров алгоритма.

  • Набор данных с множеством выбросов, для которых необходимо подогнать линию.

  • Оборудованная линия с RANSAC; выбросы не влияют на результат.

Обзор [ править ]

Алгоритм RANSAC - это метод обучения для оценки параметров модели путем случайной выборки наблюдаемых данных. Учитывая набор данных, элементы данных которого содержат как выбросы, так и выбросы, RANSAC использует схему голосования для поиска оптимального результата подбора. Элементы данных в наборе данных используются для голосования за одну или несколько моделей. Реализация этой схемы голосования основана на двух предположениях: что зашумленные функции не будут последовательно голосовать за какую-либо отдельную модель (несколько выбросов) и есть достаточно функций, чтобы прийти к согласию в отношении хорошей модели (несколько отсутствующих данных). Алгоритм RANSAC состоит из двух итеративно повторяющихся шагов:

  1. На первом этапе из входного набора данных случайным образом выбирается образец подмножества, содержащий минимальные элементы данных. Подгоночная модель и соответствующие параметры модели вычисляются с использованием только элементов этого подмножества выборки. Мощность выборочного подмножества является наименьшей, достаточной для определения параметров модели.
  2. На втором этапе алгоритм проверяет, какие элементы всего набора данных соответствуют модели, созданной с помощью оцененных параметров модели, полученных на первом этапе. Элемент данных будет рассматриваться как выброс, если он не соответствует модели подгонки, созданной набором оцененных параметров модели в пределах некоторого порога ошибки, который определяет максимальное отклонение, связанное с влиянием шума.

Набор инлир, полученных для подгоночной модели, называется консенсусным набором. Алгоритм RANSAC будет итеративно повторять два вышеупомянутых шага до тех пор, пока полученный консенсус, установленный на определенной итерации, не будет иметь достаточное количество переходов.

Входными данными для алгоритма RANSAC является набор значений наблюдаемых данных, способ подгонки какой-либо модели к наблюдениям и некоторые параметры достоверности . RANSAC достигает своей цели, повторяя следующие шаги:

  1. Выберите случайное подмножество исходных данных. Назовите это подмножество гипотетическими вставками .
  2. Модель соответствует набору гипотетических вставок.
  3. Затем все остальные данные сравниваются с подобранной моделью. Те точки, которые хорошо соответствуют предполагаемой модели, в соответствии с некоторой функцией потерь конкретной модели , считаются частью согласованного набора .
  4. Предполагаемая модель является достаточно хорошей, если достаточно много точек были классифицированы как часть консенсусного набора.
  5. Впоследствии модель может быть улучшена путем повторной оценки с использованием всех членов консенсусного набора.

Эта процедура повторяется фиксированное количество раз, каждый раз создавая либо модель, которая отклоняется из-за того, что слишком мало точек является частью консенсусного набора, либо уточненная модель вместе с соответствующим размером консенсусного набора. В последнем случае мы сохраняем уточненную модель, если ее согласованный набор больше, чем ранее сохраненная модель.

  • RANSAC: выбросы и выбросы.

Алгоритм [ править ]

Общий алгоритм RANSAC работает следующим образом:

Данный: data - набор наблюдений. модель - Модель для объяснения наблюдаемых точек данных. n - Минимальное количество точек данных, необходимых для оценки параметров модели. k - Максимальное количество итераций, разрешенных в алгоритме. t - Пороговое значение для определения точек данных, которые хорошо соответствуют модели. d - Количество близких точек данных, необходимых для подтверждения того, что модель хорошо соответствует данным.Возвращаться: bestFit - параметры модели, которые наилучшим образом соответствуют данным (или null, если подходящей модели не найдено)итераций = 0bestFit = nullbestErr = что-то действительно большоев то время как  итерации < k  делают mightInliers: = n случайно выбранных значений из данных mightModel: = параметры модели подходят для MaybeInliers alsoInliers: = пустой набор для каждой точки данных, не входящих в список mightInliers ,  если точка подходит, возможно, модель с ошибкой меньше t добавить точку в также конец,  если количество элементов в alsoInliers> d, то // Это означает, что мы, возможно, нашли хорошую модель // теперь проверим, насколько он хорош. betterModel: = параметры модели подходят ко всем точкам в mightInliers и alsoInliers thisErr: = показатель того, насколько хорошо betterModel соответствует этим точкам если thisErr <bestErr, то bestFit: = betterModel bestErr: = thisErr конец, если  конец, если инкрементные итерацииконец покавернуть bestFit

Параметры [ править ]

Пороговое значение для определения того, когда точка данных соответствует модели t , и количество близких точек данных, необходимых для подтверждения того, что модель хорошо соответствует данным d , определяются на основе конкретных требований приложения и набора данных и, возможно, на основе экспериментальных данных. оценка. Однако количество итераций k можно определить как функцию желаемой вероятности успеха p, используя теоретический результат. Пусть p будет желаемой вероятностью того, что алгоритм RANSAC даст полезный результат после выполнения. RANSAC возвращает успешный результат, если на некоторой итерации он выбирает только вставки из входного набора данных при выборе n.точки, по которым оцениваются параметры модели. Пусть будет вероятность выбора вхождения каждый раз, когда выбирается одна точка, т. Е.

= количество вставок в данных / количество точек в данных

Обычный случай - это то, что заранее не известно, но можно дать приблизительную оценку. Предполагая, что n точек, необходимых для оценки модели, выбираются независимо, это вероятность того, что все n точек являются выпадающими, и вероятность того, что хотя бы одна из n точек является выпадающей, случай, который подразумевает, что будет оценена плохая модель. с этого момента установлен. Эта вероятность в степени k - это вероятность того, что алгоритм никогда не выберет набор из n точек, которые все являются промежуточными, и это должно быть то же самое, что и . Как следствие,

что после логарифмирования обеих сторон приводит к

Этот результат предполагает, что n точек данных выбираются независимо, то есть точка, которая была выбрана один раз, заменяется и может быть выбрана снова в той же итерации. Часто это неразумный подход, и полученное значение k следует принимать в качестве верхнего предела в случае, если точки выбираются без замены. Например, в случае поиска линии, которая соответствует набору данных, показанному на приведенном выше рисунке, алгоритм RANSAC обычно выбирает две точки на каждой итерации и вычисляет их maybe_modelкак линию между точками, и тогда очень важно, чтобы эти две точки были разными. .

Чтобы получить дополнительную уверенность, к k можно добавить стандартное отклонение или его кратные . Стандартное отклонение k определяется как

Преимущества и недостатки [ править ]

Преимуществом RANSAC является его способность выполнять робастную оценку [2] параметров модели, т. Е. Он может оценивать параметры с высокой степенью точности даже при значительном количестве выбросов.присутствуют в наборе данных. Недостатком RANSAC является отсутствие верхней границы времени, необходимого для вычисления этих параметров (кроме исчерпания). Когда количество вычисляемых итераций ограничено, полученное решение может быть не оптимальным, и оно может даже не соответствовать данным в хорошем смысле. Таким образом, RANSAC предлагает компромисс; за счет вычисления большего числа итераций вероятность создания разумной модели увеличивается. Более того, RANSAC не всегда может найти оптимальный набор даже для умеренно загрязненных наборов, и обычно он плохо работает, когда количество вставок меньше 50%. Оптимальный RANSAC [3]был предложен для решения обеих этих проблем и способен найти оптимальный набор для сильно загрязненных наборов, даже для входящего отношения менее 5%. Другой недостаток RANSAC заключается в том, что он требует установки пороговых значений для конкретных проблем.

RANSAC может оценить только одну модель для определенного набора данных. Что касается любого подхода на основе одной модели, когда существует два (или более) экземпляра модели, RANSAC может не найти ни одного из них. Преобразование Хафа - это один из альтернативных методов надежной оценки, который может быть полезен, когда присутствует более одного экземпляра модели. Другой подход к подгонке нескольких моделей известен как PEARL, [4], который сочетает в себе выборку модели из точек данных, как в RANSAC, с итеративной переоценкой исходных данных и подгонкой нескольких моделей, формулируемой как задача оптимизации с глобальной функцией энергии, описывающей качество общего решения.

Приложения [ править ]

Алгоритм RANSAC часто используется в компьютерном зрении , например, для одновременного решения проблемы соответствия и оценки фундаментальной матрицы, относящейся к паре стереокамер; см. также: Структура из движения , масштабно-инвариантное преобразование функций , сшивание изображений , жесткая сегментация движения .

Развитие и улучшения [ править ]

С 1981 года RANSAC стал основным инструментом в сообществе компьютерного зрения и обработки изображений. В 2006 году, к 25-летию алгоритма, на Международной конференции по компьютерному зрению и распознаванию образов (CVPR) был организован семинар, на котором были обобщены самые последние достижения и варианты исходного алгоритма, в основном предназначенные для повышения скорости алгоритма. , надежность и точность оцененного решения и уменьшение зависимости от констант, определяемых пользователем.

RANSAC может быть чувствительным к выбору правильного порога шума, который определяет, какие точки данных соответствуют модели, созданной с определенным набором параметров. Если такой порог слишком велик, то все гипотезы оцениваются одинаково (хорошо). С другой стороны, когда порог шума слишком мал, оцениваемые параметры имеют тенденцию быть нестабильными (т. Е. При простом добавлении или удалении элемента данных к набору переходов оценка параметров может колебаться). Чтобы частично компенсировать этот нежелательный эффект, Torr et al. предложили две модификации RANSAC, называемые MSAC (M-оценка SAmple и Consensus) и MLESAC (оценка максимального правдоподобия SAmple и Consensus). [5]Основная идея состоит в том, чтобы оценить качество консенсусного набора (то есть данных, которые соответствуют модели и определенному набору параметров), вычисляя его вероятность (тогда как в исходной формулировке Фишлера и Боллеса рангом была мощность такого набора). Расширение MLESAC, которое учитывает априорные вероятности, связанные с входным набором данных, предлагает Тордофф. [6] Полученный алгоритм получил название Guided-MLESAC. В том же духе Чам предложил направлять процедуру выборки, если известна некоторая априорная информация относительно входных данных, то есть, является ли данная величина вероятным выбросом или выбросом. Предлагаемый подход называется PROSAC, Progressive SAmple Consensus. [7]

Chum et al. также предложил рандомизированную версию RANSAC под названием R-RANSAC [8], чтобы уменьшить вычислительную нагрузку для определения хорошего согласованного набора. Основная идея состоит в том, чтобы первоначально оценить качество модели, созданной в настоящее время, используя только сокращенный набор точек вместо всего набора данных. Обоснованная стратегия с высокой степенью уверенности подскажет, когда нужно оценить соответствие всего набора данных или когда модель можно легко отбросить. Разумно думать, что влияние этого подхода более актуально в тех случаях, когда процент вставок велик. Тип стратегии, предложенный Chum et al. называется схемой вытеснения. Нистер предложил парадигму под названием превентивный RANSAC [9]что позволяет в реальном времени надежно оценивать структуру сцены и движение камеры. Основная идея подхода состоит в генерировании фиксированного количества гипотез, чтобы сравнение происходило с точки зрения качества сгенерированной гипотезы, а не с какой-либо метрикой абсолютного качества.

Другие исследователи пытались справиться с трудными ситуациями, когда масштаб шума неизвестен и / или присутствует несколько экземпляров модели. Первая проблема была рассмотрена в работе Ванга и Сутера. [10] Толдо и др. представляют каждый элемент данных с характеристической функцией набора случайных моделей, которые соответствуют точке. Затем несколько моделей отображаются в виде кластеров, которые группируют точки, поддерживающие одну и ту же модель. Алгоритм кластеризации, называемый J-связью, не требует предварительного указания количества моделей и не требует ручной настройки параметров. [11]

RANSAC также был адаптирован для приложений рекурсивной оценки состояния, где входные измерения искажаются выбросами, а подходы с фильтром Калмана, основанные на гауссовском распределении ошибки измерения, обречены на неудачу. Такой подход получил название КАЛЬМАНСАК. [12]

Связанные методы [ править ]

  • MLESAC (Консенсус выборки для оценки максимального правдоподобия) - максимизирует вероятность того, что данные были сгенерированы на основе модели, подобранной по выборке, например, смешанной модели выбросов и выбросов.
  • MAPSAC (Максимальный консенсус апостериорной выборки) - расширяет MLESAC, чтобы включить априорную вероятность подбираемых параметров и максимизировать апостериорную вероятность
  • КАЛЬМАНСАК - причинный вывод состояния динамической системы
  • Ресэмплинг (статистика)

Заметки [ править ]

  1. ^ Место данных и неопределенности, Т. Strutz, Springer Фивег (2е издание, 2016)
  2. ^ Надежная статистика, Питер. J. Huber, Wiley, 1981 (переиздано в мягкой обложке, 2004 г.), стр. 1.
  3. ^ Андерс Hast, Йохан Nysjö, Андреа Маркетти (2013). «Оптимальный RANSAC - к повторяемому алгоритму поиска оптимального набора». Журнал WSCG 21 (1): 21–30.
  4. ^ Hossam Isack, Юрий Бойков (2012). «Геометрическая многомодельная аппроксимация на основе энергии». Международный журнал компьютерного зрения 97 (2: 1): 23–147. DOI : 10.1007 / s11263-011-0474-7 .
  5. ^ PHS Torr и A. Zisserman , MLESAC: новый надежный инструмент оценки с приложением для оценки геометрии изображения , Journal of Computer Vision and Image Understanding 78 (2000), no. 1, 138–156.
  6. ^ BJ Tordoff и DW Мюррей, Guided-MLESAC: Быстрее изображения преобразования, используя оценку соответствия априорные , IEEE Transactions на шаблон анализа и Machine Intelligence 27 (2005), нет. 10, 1523–1535.
  7. ^ Соответствие с PROSAC - прогрессивный образец консенсуса , Труды конференции по компьютерному зрению и распознаванию образов (Сан-Диего), том. 1, июнь 2005 г., стр. 220–226.
  8. ^ О. Чам и Дж. Мэйтас, Рандомизированный RANSAC с тестом Td, d, 13-я Британская конференция по машинному зрению, сентябрь 2002 г. http://www.bmva.org/bmvc/2002/papers/50/
  9. ^ Д. Нистер, Превентивный RANSAC для оценки живой структуры и движения , Международная конференция IEEE по компьютерному зрению (Ницца, Франция), октябрь 2003 г., стр. 199–206.
  10. ^ Х. Ван и Д. Сутер, Надежная оценка параметрической модели с адаптивным масштабом для компьютерного зрения ., IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004), no. 11, 1459–1474
  11. ^ Р. Толдо и А. Фузиелло, Оценка устойчивых множественных структур с помощью jlinkage , Европейская конференция по компьютерному зрению (Марсель, Франция), октябрь 2008 г., стр. 537–547.
  12. ^ А. Ведальди, Х. Джин, П. Фаваро и С. Соатто, КАЛЬМАНСАК: Надежная фильтрация на основе консенсуса , Труды Международной конференции по компьютерному зрению (ICCV), том. 1. 2005, с. 633–640.

Ссылки [ править ]

  • Мартин А. Фишлер и Роберт К. Боллес (июнь 1981 г.). «Консенсус по случайным выборкам: парадигма соответствия модели приложениям для анализа изображений и автоматизированной картографии» (PDF) . Comm. ACM . 24 (6): 381–395. DOI : 10.1145 / 358669.358692 . S2CID  972888 .
  • Дэвид А. Форсайт и Жан Понсе (2003). Компьютерное зрение, современный подход . Прентис Холл. ISBN 978-0-13-085198-7.
  • Ричард Хартли и Эндрю Зиссерман (2003). Множественная геометрия просмотра в компьютерном зрении (2-е изд.). Издательство Кембриджского университета.
  • Струтц, Т. (2016). Подгонка данных и неопределенность (практическое введение в взвешенный метод наименьших квадратов и другие аспекты) . 2-е издание, Springer Vieweg. ISBN 978-3-658-11455-8.
  • PHS Torr и DW Murray (1997). «Разработка и сравнение робастных методов оценки фундаментальной матрицы». Международный журнал компьютерного зрения . 24 (3): 271–300. DOI : 10,1023 / A: 1007927408552 . S2CID  12031059 .
  • Ондрей Чум (2005). «Двусторонняя оценка геометрии с помощью случайной выборки и консенсуса» (PDF) . Кандидатская диссертация .
  • Сунглок Чой; Тэмин Ким и Вонпил Ю (2009). «Оценка производительности семейства RANSAC» (PDF) . В материалах Британской конференции по машинному зрению (BMVC) .
  • Андерс Хаст; Йохан Нисйо; Андреа Маркетти (2013). «Оптимальный RANSAC - к повторяемому алгоритму для поиска оптимального набора» (PDF) . Журнал WSCG . 21 (1): 21–30.
  • Хоссам Исак; Юрий Бойков (2012). «Геометрическая многомодельная аппроксимация на основе энергии» (PDF) . Международный журнал компьютерного зрения . 97 (2: 1): 23–147. CiteSeerX  10.1.1.381.2434 . DOI : 10.1007 / s11263-011-0474-7 . S2CID  5461268 .