Компьютерная Графика и Мультимедиа Сетевой журнал

Очень часто при решении какой-нибудь задачи обработки данных приходится сталкиваться с необходимостью определить параметры модели (to estimate model parameters), которой должны удовлетворять имеющиеся исходные данные. В реальной жизни, когда исходные данные зашумлены (noisy data), и среди них могут встречаться и ложные, совершенно случайные значения, это может оказаться совсем непросто.

Почему же так происходит? Дело оказывается в самом принципе работы любого вычислительного алгоритма определения параметров модели. Алгоритму задаются исходные данные, и он рассчитывает параметры модели, которой будут удовлетворять исходные данные. Очевидно, что зашумленность исходных данных обязательно скажется на точности модели. Даже если все данные изначально были правильны (т.е. все должны были удовлетворять одной и той же модели – по англ. inliers), то из-за ошибок в определении модели часть исходных данных может вообще перестать удовлетворять модели, и данные будут признаны ложными (станут выбросами – outliers). А уж если среди данных, которые использовались для вычисления модели, попались ложные, то получившаяся модель вообще будет неправильной, и большинство данных не будут ей удовлетворять.

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

Но поскольку это невозможно, мы должны использовать какую-нибудь схему, которая была бы более-менее устойчива к зашумленности исходных данных и к наличию среди правильных значительного количества ложных данных. Такие схемы называются методами устойчивой оценки параметров модели (robust estimators) или "устойчивыми оценщиками". Пожалуй, самым известным подходом к созданию устойчивых оценщиков является использование случайных выборок подмножеств данных из всего набора исходных данных.

Прежде чем приступать к рассмотрению самих устойчивых оценщиков сформулируем постановку задачи с математической точки зрения.

Пусть имеется набор T исходных данных, состоящий из N элементов. Известно, что большинство его элементов должно удовлетворять некоторой параметрической модели Model(P) с параметрами P, причем количество параметров |P| = p. Имеется алгоритм, позволяющий вычислить параметры модели P по набору данных из k элементов. Необходимо вычислить значения параметров такие, что данный набор исходных данных T удовлетворял модели наилучшим образом.

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

Отдельно выделим еще два ранее уже упомянутых термина. Элемент, удовлетворяющий данной модели M(P) называется inlier для данной модели. Элемент, который не удовлетворяет данной модели M(P) называется outlier для данной модели. По-русски термин переводится как "выброс", но ради единообразия будет употребляться английский вариант.

Поскольку нам известно, что исходные данные удовлетворяют некоторой искомой модели, разделим все элементы исходных данных на "просто" inlier и outlier. Если отдельно не указано, относительно какой модели мы определяем inlier/outlier, то подразумевается, что относительно искомой.

Особо отметим одно общее ограничение на исходные данные. Если количество outlier слишком велико, то даже искомая модель будет плохо соответствовать исходным данным. Результатом устойчивой оценки в этом случае может быть признана модель, которая наилучшим образом удовлетворяет всем элементам, и inlier и outlier, а значит, которая может быть далека от искомой.

Количество исходных данных всегда ограничено. Поэтому получить искомое решение можно и простым "тупым" (dumb) перебором всех подмножеств из k элементов из T, вычислением на каждом из них модели, и последующей проверкой всех полученных моделей на всем T. Но количество вариантов подмножеств получается астрономическим, и результата мы никогда не дождемся.

Поэтому нужен какой-нибудь более разумный алгоритм перебора подмножеств и получения модели. Таким методом и стал случайный перебор исходных данных. Ведь если отделить inlier от outlier невозможно, то все элементы с точки зрения алгоритма одинаковы – они могут быть с некоторой вероятностью как inlier, так и outlier. А значит, если мы выберем случайным образом k элементов из исходных, и вычислим на них модель, то с некоторой вероятностью (если выбранные элементы не окажутся выбросами, и будут не очень сильно зашумлены) она будет весьма близка к исходной, а значит, может быть решением задачи. Если мы будем выбирать такие случайные наборы некоторое количество раз, то среди них построенных моделей, возможно, попадется близкая к исходной. Если известно примерное содержание outlier в исходных данных, то можно даже вычислить вероятность, с которой один из случайно выбранных наборов M даст искомую модель.

Первым и самым широко известным алгоритмом устойчивой оценки, в котором была реализована эта идея, стал RANSAC (Random Sample Consensus), предложенный в 1981 году Фишлером и Боллесом [1].

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

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

В этой статье рассматривается три таких алгоритма, два из которых были опубликованы в прошлом году. Это:

Теперь рассмотрим каждый из методов более подробно.

В методе RANSAC реализована самая общая схема устойчивой оценки с помощью выбора случайных подмножеств данных. Она очень проста и элегантна. Возьмем подмножество K из k элементов из T. Вычислим на нем модель M(P(K)). Проверим все элементы T на соответствие модели M(P(K)). Определим количество inlier в T для данной модели. Повторим весь этот процесс заданное количество раз. Та модель, которой соответствует наибольшее число inlier-ов и будет результатом работы алгоритма.

Каждый элемент при выборе очередного подмножества выбирается с равной вероятностью. Количество подмножеств, которые необходимо попробовать, можно вычислить следующим образом:

,где Г – требуемая вероятность выбора хорошего подмножества за время работы; k – количество элементов в наборе, необходимое для вычисления модели; e – процент выбросов в наборе Т; m – количество проверяемых подмножеств

При увеличении количества выбросов в наборе T выше 50% необходимое число подмножеств резко возрастает. Если для k=7, e=50%, Г = 95% необходимо выбрать 382 подмножеств, но для е=60% уже 1827, а для е=70% больше 13500!

Оценка, является или нет данный элемент исходных данных inlier-ом, производится следующим образом. Если ошибка соответствия элемента модели превышает некоторый порог, то этот элемент признается outlier-ом. Метод, по которому вычисляется ошибка соответствия элемента модели, выбирается отдельно для каждой конкретной задачи.

Алгоритм RANSAC записывается в следующем виде:

Шаг 1: Для заданных k, e, Г повторить m раз

Шаг 1.1: Выбрать подмножество из k элементов, каждый элемент с одинаковой вероятностью

Шаг 1.2: Вычислить параметры модели для текущего подмножества

Шаг 1.3: Определить количество inlier

Шаг 2: Выбрать решение с максимальным количеством inlier

Результат работы схемы RANSAC признается приближением исходной модели, и все inlier, удовлетворяющие ей, признаются inlier исходной модели. Параметры модели - решения, выданной RANSAC, теперь могут быть уточнены с использованием всех определенных inlier.

Схему работы RANSAC можно сформулировать и в более общем виде:

Шаг 1: Повторить m раз

Шаг 1.1: Выбрать подмножество из k элементов

Шаг 1.2: Определить параметры модели для текущего подмножества

Шаг 1.3: Определить соответствие T модели

Шаг 2: Определить наиболее соответствующую T модель из вычисленных

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

В самом RANSAC в качестве алгоритма выбора подмножество взят выбор k элементов, каждый из которых выбирается с одинаковой вероятностью из всего множества. А степень соответствия модели и данных определяется по количеству inlier.

 

В алгоритме RANSAC вклад всех outlier в оценку соответствия данных модели одинаков, т.к. подсчитывается только общее их количество. Все inlier также вносят одинаковый вклад в качество. Поэтому могут возникать случаи, когда одной модели соответствует L inlier, и очень точно, а другой L+1, но во которой большинство inlier удовлетворяют ей едва-едва. Но выбрана в этой ситуации будет именно вторая модель. Хотя вероятнее, что именно первая модель более точно описывает исходные данные.

Именно поэтому в алгоритме. MLESAC одинаковый вклад всех элементов заменяется непрерывной функцией максимального подобия (maximum likehood):

, где d – ошибка соответствия модели , сигма – стандартная дисперсия.

Чем меньше значение функции максимального подобия, тем модель точнее описывает исходные данные. Все oulier по-прежнему вносят одинаковый вклад в оценку соответствия (иначе один сильно отклонившийся outlier мог бы испортить оценку исходной модели). А все inlier уже вносят свой вклад пропорционально соответствию модели.

Оценка качества модели становится гораздо более точной, и повышает общее качество работы алгоритма.

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

При формировании очередного подмножества в методе NAPSAC случайным образом выбирается только первый элемент. Все остальные k-1 берутся из гиперсферы – окрестности первого элемента. Если в ней не находится нужного количества элементов – первый элемент отбраковывается, и подмножество дальше не строится.

Радиус гиперсферы рассчитывается по следующей формуле:

, где - содержание inlier в Т, v – границы, в пределах которых изменяются координаты элементов T


Схему этапа выбора очередного поднабора для NAPSAC можно записать следующим образом:

Авторы этого алгоритма обратили внимание на то, что оценка каждой новой модели происходит с использованием всех элементов T. Каждая, даже самая плохая модель оценивается за одинаковое время. Это очень неэффективно и требует много времени. Схема R-RANSAC исправляет этот недостаток за счет новой двухэтапной схемы проверки решения. Первый этап проверки позволяет быстро определить потенциально плохие решения, и сэкономить время на последующей обработке всех элементов. Для каждого нового решения случайным образом выбирается d элементов из T, которые и проверяются на соответствие модели. Если хотя бы один из них не соответствует модели, она признается плохой, и дальше не рассматривается. Если все d элементов ей удовлетворяют, то на втором этапе проверяются уже весь набор.

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

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

Где – время вычисления модели по набору, e – содержание Inlier, а вот - вычисляется из вероятности прохождения набором, содержащим outlier, первого этапа проверки. Поскольку оценка последнего параметра на практике невозможно, оценка чисто теоретическая.

На практике d выбирается очень небольшим. Обычно берется 1 или 2.

Методы RANSAC используются в большинстве работ по компьютерном зрению, связанных со слежением за особенностями и с восстановлением трехмерной модели по последовательности изображений.

Например, при отслеживании перемещений характерных точек от кадра к кадру (feature tracking), необходимо вычислить параметры движения камеры от кадра к кадру по набору сопоставлений точек на одном и на другом кадре. Сопоставление точек – положение некой точки на первом кадре плюс положение ее же на втором кадре, т.е. всего две пары двумерных координат. Часть сопоставлений обычно определяется неправильно. Такие сопоставления будут являться outlier для искомой модели движения камеры.

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

Соответствие сопоставлений модели можно определить, например, следующим образом. Берем точку сопоставления на одном кадре, рассчитывает точку, которая должна ей соответствовать на другом кадре, и вычисляем отклонение рассчитанной и истинной точки на втором кадре друг от друга. Порог отклонения, превышение которого превращает сопоставление в outlier обычно берется в пределах [0.5 – 2] пикселя.