Книги по разным темам Pages:     | 1 | 2 | Обзор робастных схем оценки параметров моделей на основе случайных выборок Антон Конушин, Кирилл Мариничев, Владимир Вежневец Лаборатория Компьютерной Графики и Мультимедиа, Факультет ВМК, Московский Государственный Университет им. Ломоносова, Москва, Россия {ktosh, kirmar, vvp}@graphics.cs.msu.ru медианы квадратов (Least Median of Squares) [3],[14], а также Аннотация семейство методов на основе случайных выборок (RANSAC)[1].

Робастные схемы оценки параметров модели являются мощным и широко используемым инструментом в области 2. ОБЩАЯ СХЕМА РОБАСТНЫХ МЕТОДОВ машинного зрения. Практически в каждой работе используется та или иная схема робастной оценки. За 23 года, ОЦЕНКИ НА ОСНОВЕ СЛУЧАЙНЫХ ВЫБОРОК прошедших с момента появления первой робастной схемы на В 1981 году для решения задачи робастной оценки основе случайных выборок, было предложено множество параметров Фишером и Болесом был предложен алгоритм различных алгоритмов, развивающих тот или иной этап RANdom SAmpling Consensus (RANSAC). Он решает задачу базовой схемы. В данной работе предлагается обзор оценки исследуемой модели за счет поиска наилучшей существующих методов робастных схем оценки параметров.

проводится сравнение эффективности части из них. гипотезы в среди множества всех возможных гипотез, порожденных исходными данными. Понятно, что за разумное Keywords: robust estimation, RANSAC, outliers, line fitting, время возможно рассмотреть только небольшую часть maximum likelihood, MAP, homography estimation гипотез. Для максимизизации вероятности получения гипотезы, построенной по выборке без выбросов, необходимо 1. ВВЕДЕНИЕ проводить поиск только среди гипотез, построенных по выборке из минимально необходимого для оценки числа Одной из ключевых задач машинного зрения является элементов (назовем это число размерностью модели). Но сопоставление информации, содержащейся в изображении поскольку даже таких гипотез слишком много, то случайным некоторой математической модели. Общую задачу оценки образом выбирается только N из них. Алгоритм RANSAC параметров модели по имеющимся данным можно записать состоит из N повторений следующего цикла:

следующим образом. Нужно определить вектор параметров, такой чтобы 1) Построение выборки из m элементов;

Sk x 2) Построение гипотезы на основе выборки ;

k Sk F(x, ) = 0; (1) 3) Оценка степени согласия гипотезы на Rk k где - информация, содержащаяся в изображении, x F(x, ) множестве всех исходных данных ;

x задает исследуемую математическую модель. Классическим примером задачи оценки параметров является аппроксимация После построения и оценки всех N гипотез, из них набора точек прямой линией. В таком случае - это набор x выбирается гипотеза с наилучшей оценкой точек, - уравнение прямой, - параметры прямой.

F(x, ), которая и принимается за результат робастной R = max(Rk ) k =1,N Традиционные методы оценки параметров, такие как метод оценки.

максимального правдоподобия или метод максимизации апостериорной вероятности исходят из следующего 3. ВАРИАНТЫ ФУНКЦИИ ОЦЕНКИ ГИПОТЕЗЫ предположения об исследуемой модели и исходных данных - все данные порождены исследуемой моделью и x = {xi} 3.1 Базовая схема RANSAC зашумлены некоторой помехой, математическое В базовой схеме RANSAC качество гипотезы определяется ожидание которой, а дисперсия M ( ) = количеством элементов исходных данных ей. Указанное предположение верно не D() =, = const удовлетворяющих. Степень согласия (а точнее несогласия) гипотезы и исходных данных вычисляется следующим всегда. В случае, если часть исходных данных порождена не образом:

исследуемой моделью, а, например, ошибками измерений (такие данные называются outliers - выбросами), результат 0 ri 2 < T оценки параметров модели с помощью метода максимального, R( ) = p(ri ( )2) p(ri2 ) =,i = 1,n (2) правдоподобия может оказаться сколь угодно далек от i 1 ri > T реальных параметров модели. Для решения указанной проблемы разработан ряд методов робастной оценки где - невязка точки и оцениваемой гипотезы, T - ri( )2 xi параметров, учитывающих присутствие выбросов в исходных фиксированный порог, изначально заданный из некоторых данных - М-оценки (M-estimators) [14], схемы голосования общих соображений или свойств исходных данных. В случае, (например преобразование Хафа [2],[14]), метод наименьшей если невязка точки превышает порог T, точка считается xi xi 3.5 MAPSAC выбросом. Гипотеза с наименьшей величиной Оценка максимального правдоподобия не учитывает R( ) дополнительно известной нам априорной информации о выбирается как наилучшая.

модели и данных. В работе [6] дана Байесовская формулировка робастной оценки параметров путем Базовая функции оценки гипотез RANSAC обладает максимизации апостериорной вероятности.

серьезными недостатками. При неправильно установленном пороге T гипотеза, построенная по содержащей выбросы 3.6 Сравнение функций оценки гипотез выборке, могла быть оценена наравне с гипотезой по выборке без выбросов. Также, если порог устанавливается слишком Функция оценки гипотез M-SAC позволяет выбирать более низким, то за выбросы могут быть приняты и данные, корректные гипотезы чем RANSAC без дополнительной порожденные исследуемой моделью. Если порог ставится вычислительной сложности, как показано в [4],[5]. Однако, слишком высоким, то многие выбросы не будут обнаружены.

оценка максимального правдоподобия MLESAC, несмотря на Поэтому при развитии робастных схем большое внимание возросшую вычислительную сложность дает только уделялось созданию функций оценки гипотез, лишенных этих сравнимые с M-SAC результаты [9]. Оценка MAPSAC недостатков.

позволяет использовать максимум информации для оценки гипотез, и поэтому должна быть наиболее точной. Но для большинства задач, в которых необходимо применение 3.2 LMS робастных оценок, не существует эффективной априорной В отличие от базовой схемы, метод наименьшей медианы оценки гипотез. В условиях неизвестной априорной квадратов (least median of squares) [3] не требует задания информации оценка апостериорной вероятности сводится к оценке максимального правдоподобия. Таким образом, если порога T. В качестве критерия согласия модели и данных для конкретной задачи можно оценить априорную используется следующая функции:

вероятность гипотез, то наилучший результат будет R( ) = median(ri ( )2), i = 1,n (3) достигнут при использовании MAPSAC, в противном случае можно ограничиться M-SAC.

Однако схема LMS успешно работает при доле выбросов в исходных данных не более 50%, в то время как базовая схема 4. ВАРИАНТЫ СХЕМЫ ВЫБОРКИ RANSAC может успешно работать с большей долей выбросов.

Количество всевозможных выборок элементов исходных Sk данных чрезвычайно велико, и за разумное время можно 3.3 M-SAC проверить только незначительную их часть. Поэтому вероятность верной оценки требуемой модели напрямую Помимо зависимости от априорно задаваемого порога, T зависит от вероятности получения гипотезы, построенной по базовая функция оценки гипотез имеет еще один недостаток выборке не содержащей выбросов. Эта вероятность - она не оценивает то, насколько хорошо данные без определяется способом построения выборки. С момента выбросов соответствуют исследуемой модели. По аналогии с появления базовой схемы было предложено несколько M-оценками [14] в работе [4] было предложено каждому вариантов модификации способа выборки, некоторые из выбросу назначать фиксированный штраф, а вклад всех которых [7], [8] предлагают прямо противоположные остальных точек сделать пропорциональном квадрату модификации.

ошибки:

ri 2 ri 2 T R( ) = p(ri ( )2), p(ri2) =,i = 1,n (4) 4.1 Базовая схема RANSAC 2 i T ri > T В базовой схеме каждая точка может быть включена в текущую выборку с равной вероятностью [1]. Если доля Sk Как было показано в работе [4], эта модификация позволяет выбросов в исходных данных равна, то вероятность [0,1] находить модели с более высоким качеством без того, что все элементы в выборке не являются выбросами, дополнительных накладных расходов по скорости.

равна. Таким образом эффективность равномерной (1- )m выборки экспоненциально убывает при увеличении размера 3.4 MLESAC выборки.

Функция оценки гипотез M-SAC не является в полной мере статистически обоснованной оценкой. В работе [5] предлагается модификация метода максимального 4.2 Модификация Жанга правдоподобия для данных, содержащих выбросы. В этом При использовании базовой схемой с равномерной выборкой методе в явном виде учитывается параметр, [0,1] вероятны ситуации, когда расстояния между выбранными задающий долю выбросов в общей выборке. Для точками будут сравнимы с погрешностью, вносимой помехой одновременного вычисления параметров модели и доли. В таком случае гипотеза будет далека от исследуемой выбросов применяется схема ожиданияЦмаксимизации модели и будет отвергнута как ложная. Для исключения (expectation maximization, EM). подобных ситуаций, в [7] была предложена регулярнослучайная схема построения выборки. Пространство, занимаемое множеством исходных точек 5. МОДИФИКАЦИИ СХЕМЫ ОЦЕНКИ МОДЕЛИ x = {xi} разбивается на p корзинок, регулярным образом Для выбора верной гипотезы с высокой вероятностью покрывающую область определения элементов. При требуется проверить внушительное число гипотез составлении выборки случайным образом выбирается k построенных по разным выборкам исходных данных.

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

требующих использования всех исходных данных для оценки гипотезы, либо позволяющих значительно сократить количество подобных оценок.

4.3 NAPSAC Экспоненциальный рост количества необходимых выборок в базовой схеме не позволяет эффективно ее использовать для 5.1 Рандомизированный RANSAC с Td,d оценки моделей большой размерности. В работе [8] было тестом теоретически обосновано, что вероятность выбрать УневыбросФ в окрестности другого Уне-выбросаФ выше, чем при В 2002 году, в работе [10] было предложено ввести элемент выборке каждого элемента с равной вероятностью. На основе случайности также и схему проверки гипотез. Перед этой идеи была предложена неоднородная схема выборки.

проверкой каждой гипотезы осуществляется -тест.

Td,d Только первый элемент каждой выборки выбирается x' Согласно ему, из исходных данных с равномерной случайно, все остальные элементы выборки берутся из вероятностью выбирается d элементов, и проверяется, не окрестности этого элемента. Если в нет x x содержится ли среди них хотя бы один выброс относительно необходимого для выборки количества элементов, то текущей гипотезы. Если хотя бы один выброс присутствует, выбирается новый первый элемент. Данная схема позволяют гипотеза считается не прошедшей тест, и отбрасывается.

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

пространственной близости элементов выборки (см. раздел 4.2).

5.2 Превентивный RANSAC Доля гипотез не содержащих выбросов, значительно меньше доли выбросов в исходных данных. Поэтому требуется много 4.4 Метод Тордоффа и Мюррея времени, прежде чем выборка без выбросов будет найдена по Описанные выше схемы не используют априорной базовой схеме. В системах реального времени требуется же информации об исходных данных при построении выборки.

фиксированное время работы алгоритма. Поэтому была Если же для каждого элемента данных имеется некоторая предложена превентивная схема RANSAC [11], согласно оценка достоверности этого элемента, такую информацию которой вначале создаются все N гипотез. После этого можно использовать для увеличения вероятности получения выбирается случайным образом элемент исходных данных, и выборок не содержащих выбросов. Авторы работы [9] все гипотезы оцениваются только на нем. После оценки предлагают способ получения такой оценки для задачи гипотезы сортируются в порядке качества, и самые плохие отслеживания перемещения точечных особенностей в гипотезы могут быть отброшены. Затем выбирается видеопоследовательности. Имея такую оценку можно следующей элемент, и процедура продолжается до истечения выбирать элементы при построении выборки с вероятностью отведенного времени. Лучшая гипотеза берется в качестве пропорциональной их достоверности.

результата.

4.5 Сравнение различных схем построения 5.3 Сравнение схем оценок модели выборок Очевидно, что оценка гипотезы с использованием всех При создании оптимальной схемы построения гипотез исходных данных более точна, чем оценка только по части из необходимо учитывать две основные проблемы:

них. Однако, как показывают работы [10] и [11], потенциально низкая вероятность построения выборки без дополнительная рандомизация схемы оценки модели выбросов и возможность оценки некачественных гипотез по позволяет за счет незначительного снижения вероятности неудачной выборке свободной от выбросов. Предложенные нахождения корректной гипотезы, значительно уменьшить методы без использования дополнительной априорной время работы алгоритма. В большинстве случаев, схемы с информации ([7], [8]) позволяют частично решить одну из рандомизацией оценки показывают сравнимый с обычной проблем за счет усугубления другой. Только использование схемой оценки результат. Но при фиксированном и априорной информации о достоверности исходных данных, небольшом времени выполнения алгоритма, когда позволяющей вычислить вероятности того, что произвольный невозможно оценить большое число гипотез на всех элемент является выбросом, позволяет повысить вероятность исходных данных, превентивный RANSAC дает наилучший построения лудачной выборки [9]. Однако получение такой результат.

оценки требует статистики достоверности элементов данных, накопление которой осуществляется по-разному для каждой конкретной задачи.

эффективных методов оценок априорной информации о 6. ДРУГИЕ МОДИФИКАЦИИ гипотезах и выбросах в исходных данных для конкретных Поскольку вероятность построения выборки без выбросов задач, в которых необходимо применение робастных схем.

Pages:     | 1 | 2 |    Книги по разным темам