Введение

Статистический метод

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

Пример

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

Обзор

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

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

Выбрать случайное подмножество исходных данных. Назовем это подмножество гипотетическими инлайерами. К набору гипотетических инлайеров подгоняется модель. Затем все данные тестируются на соответствие подобранной модели. Все точки данных (исходных данных), которые хорошо соответствуют оцененной модели в соответствии с некоторой специфичной для модели функцией потерь, называются консенсусным множеством (т.е. множеством инлайеров для модели). Оцененная модель достаточно хороша, если достаточное количество точек данных было классифицировано как часть консенсусного множества. Модель может быть улучшена путем повторной оценки с использованием всех членов консенсусного множества. Качество подгонки, как мера того, насколько хорошо модель соответствует консенсусному множеству, будет использоваться для уточнения подгонки модели по мере выполнения итераций (например, путем установки этой меры в качестве критерия качества подгонки на следующей итерации). Для сходимости к достаточно хорошему набору параметров модели эта процедура повторяется фиксированное количество раз, каждый раз приводя либо к отклонению модели из-за недостаточного количества точек в консенсусном множестве, либо к усовершенствованной модели с консенсусным множеством большего размера, чем предыдущее.

Преимущества и недостатки

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

Приложения

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

Развитие и улучшения

С 1981 года RANSAC стал фундаментальным инструментом в сообществе компьютерного зрения и обработки изображений. В 2006 году, к 25-летию алгоритма, на Международной конференции по компьютерному зрению и распознаванию образов (CVPR) был организован семинар для обобщения последних достижений и вариаций оригинального алгоритма, направленных главным образом на повышение скорости работы, устойчивости и точности оцениваемого решения, а также на снижение зависимости от констант, задаваемых пользователем. RANSAC может быть чувствителен к выбору корректного порога шума, определяющего, какие точки данных соответствуют модели, инстанцированной с определенным набором параметров. Если этот порог слишком велик, то все гипотезы, как правило, оцениваются одинаково (как хорошие). С другой стороны, при слишком малом пороге шума, оцениваемые параметры становятся неустойчивыми (то есть, простое добавление или удаление точки из набора инлайеров может приводить к колебаниям оценки параметров). Чтобы частично компенсировать этот нежелательный эффект, Torr и др. предложили две модификации RANSAC, известные как MSAC (M-оцениватель, выборка и консенсус) и MLESAC (оценка максимального правдоподобия, выборка и консенсус). Основная идея заключается в оценке качества консенсусного множества (то есть данных, соответствующих модели и определенному набору параметров) путем вычисления его правдоподобия (в то время как в оригинальной формулировке Фишлера и Боллеса рангом считалась кардинальность этого множества). Tordoff предложил расширение MLESAC, учитывающее априорные вероятности, связанные с входным набором данных. Полученный алгоритм получил название Guided MLESAC. В том же ключе Chum предложил направлять процедуру выборки, если известна некоторая априорная информация о входных данных, то есть, вероятно ли, что данная точка является инлайером или аутлайером. Предложенный подход называется PROSAC, PROgressive SAmple Consensus. Chum и др. также предложили рандомизированную версию RANSAC, названную R RANSAC, для снижения вычислительной нагрузки при идентификации хорошего консенсусного множества. Основная идея заключается в первоначальной оценке качества текущей инстанцированной модели, используя лишь уменьшенный набор точек вместо всего набора данных. Эффективная стратегия позволит с высокой уверенностью определить, когда следует оценивать соответствие всего набора данных, а когда модель можно сразу отбросить. Разумно полагать, что влияние этого подхода более существенно в случаях, когда процент инлайеров велик. Тип стратегии, предложенный Chum и др., называется схемой преэмпции. Nistér предложил парадигму под названием Preemptive RANSAC, позволяющую осуществлять робастную оценку структуры сцены и движения камеры в реальном времени. Основная идея подхода состоит в генерации фиксированного числа гипотез, чтобы сравнение происходило на основе качества сгенерированной гипотезы, а не по отношению к некоторой абсолютной метрике качества. Другие исследователи пытались справиться со сложными ситуациями, когда масштаб шума неизвестен и/или присутствует несколько экземпляров модели. Первая проблема была решена в работе Wang и Suter. Toldo и др. представляют каждый элемент данных с помощью характеристической функции множества случайных моделей, которым соответствует эта точка. Затем несколько моделей выявляются в виде кластеров, объединяющих точки, поддерживающие одну и ту же модель. Алгоритм кластеризации, называемый J-связностью, не требует предварительного указания количества моделей и не нуждается в ручной настройке параметров. RANSAC также был адаптирован для приложений рекурсивной оценки состояния, где входные измерения искажены выбросами, а подходы, основанные на фильтре Калмана, которые полагаются на гауссовское распределение ошибки измерения, обречены на провал. Такой подход получил название KALMANSAC.