«

»

May 03

04 – поиск преобразования между особыми точками и немного моделирования

Сопоставление изображений

Когда изображения не сопоставляются

Когда изображения не сопоставляются

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

Что же позволяет нам проявлять столь похвальную прозорливость? У Эйфелевой башни есть некоторые характерные особенности которые мы можем безошибочно определить на всех снимках, не взирая на различия в освещении, ракурсе съемки или перекрытия (людьми или постройками). Более того – на основании снимка мы можем примерно прикинуть откуда он был сделан и определить условия съемки. (Нет, это не столько для того чтобы ощутить свое всемогущество – такая возможность пригодится при 3д реконструкции объектов и сцен, или построении панорам).

Если немного отвлечься от сладких грез о Париже и вернуться к нехитрым выкладкам из теории компьютерного зрения получается вот что: на изображении мы можем выделить характерные точки. Если изображений в нашем распоряжении несколько – мы можем попытаться определить – есть ли на них общие особые точки. Если мы найдем некоторое количество общих особых точек – тогда мы сможем полнее описать наблюдаемую сцену – в случае если сменился ракурс обзора. Это поможет определить как переместились особые точки по сравнению с предыдущим кадром (для описания движения объекта или частей объекта) – т.е. сможем оценить изображение уже на более высоком уровне.

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

Заранее нельзя сказать каким образом получен набор изображений для анализа – потому следует рассматривать все возможные варианты преобразований, отбирая те преобразования, при которых совпадает максимальное количество особых точек.

Общий алгоритм поиска преобразования между двумя изображениями на основе особых точек:

  • Находим особые точки
  • Вычисляем дескрипторы особых точек
  • Сопоставляем точки по дескрипторам – получая соответствия точек
  • По этому набору соответствий вычислить модель преобразования (не забывая про ошибки измерения положения точек)

Особая точка на первом изображении потенциально может соответствовать любой из особых точек второго изображения (мы же не можем заранее предсказать как изменилась сцена или сместилась эта точка). Потому, при анализе используются наборы из возможных пар соответствий. Проверять каждую особую точку на соответствие со всеми особыми точками второго изображения – способ конечно надежный но слишком уж ресурсоемкий. Для ускорения анализа сейчас принято составлять гипотезы для набора разных точек в совокупности – MND – mutual neighbor distance и проверять, насколько они согласуются друг с другом. Например, разбивая изображения на отдельные участки – сетку, или отбирая пары случайным образом . Те точки, которые соответствуют модели преобразования называются inliers, те которые нет – выбросы – outliers. Дескрипторы сравниваются как обычно – SSD, SAD, кросс-кореляцией, пересечением гистограмм.

Надо отметить, что потенциально может быть полезно и попиксельное сопоставление (при поиске по шаблону или построении панорам) – однако для практики это скорей экзотика. Полноты описания ради – функции оценки попиксельного сопоставления – SSD, SAD, градиентный спуск, многомасштабное сопоставление.

Моделируя изображения

Для того, чтобы описать объект или целую сцену редко необходима вся информация о цвете и текстуре. В конце-концов, несколькими контурами а ля “палка палка огуречик” можно схематично изобразить и ледовое побоище и утро в сосновом бору. Что позволяет заявлять о том, что львиную долю изображений можно как-то аппроксимировать в виде набора простых (геометрических) моделей (линии, окружности). Простые модели, в свою очередь, можно составлять из набора особых точек. Как это сделать?

Существует целое семейство задач связанных с параметрами модели изображения на основе особых точек – model fitting – “подгонка” модели. Методы решения разделяют на робастные (выбросы не оказывают влияния на результирующую модель) и не робастные (неустойчивые к выбросам – например заданы точки удовлетворяющие модели и надо вычислить параметры этой модели)

1) Неробастные методы

Подгонка прямых линий
При заданном наборе точек, мы ищем прямую наилучшим образом их аппроксимирующую.
Решение – методом наименьших квадратов что упрощенно решается через сингулярное разложение – SVD (singular value decomposition).

В случае обобщенной модели, когда задан набор признаков и необходимо найти ее параметры используется все тот же метод наименьших квадратов, однако он уже называется DLT – Direct Linear Transform (или метод максимального правдоподобия, или минимизация суммы квадратов отклонения. Метод полных квадратов показывает наилучшие результаты. Однако для сложной модели, при использовании этого метода производится оптимизация алгебраической ошибки лишенной физического смысла, меж тем как для каждой модели есть и разумная ошибка, имеющая физический смысл. Методы минимизирующие эту ошибку называется gold standard.

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

2) Робастные методы
а) M-оценки – с целью уменьшение влияния далеких точек вводится некоторая функция модели. Решается с помощью метода взвешенных наименьших квадратов. Недостатки – необходимо хорошее первое приближение, как найти минимум целевой функции.

На практике, такие задачи разбиваются на две части:
выбрать приближение – функцию, а потом итеративно его уточнять (как пример – взвешенный итеративный МНК).

b) RANSACRANdom SAmple Consensus
Параметры модели оцениваются не по всем данным, а по малой части не содержащей выбросы. Заранее неизвестно, какая часть не содержит выбросы – случайно делаем выборки несколько раз и для каждой выборки оцениваем модель и ее качество.

Регулируется несколькими параметрами:
– размер – минимальное количество точек для оценки параметров (например для прямой – две точки)
– количество выборок
– требуемая вероятность что правильная точка будет правильно классифицирована

Хорошо и часто работает на практике. Применяется для сопоставления изображений.
Недостатки:
не всегда удается хорошо оценить параметры по минимальной выборке
– много настраиваемых параметров (если порог не корректен – будут проблемы)
– иногда требуется слишком много итераций
– не срабатывает при очень высокой доле выбросов
– часто есть лучший способ нежели равновероятно выбирать точки

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

В вариации M-SAC для оценки порога используются M-оценки – это дает прирост точности и не влияет на вычислительную сложность.

Альтернатива RANSAC – LMS (Least median squares). Из его минусов – может выбрать неверную гипотезу. Не работает если больше половины точек выбросы. Потому на практике малопригоден.

Еще одна альтернатива RANSAC – схемы голосования (voting scheme). Пространство параметров называется фазовым пространством. Схемы голосования используются для поиска семейства кривых заданных параметрически.

Каждый признак голосует за все модели которым удовлетворяет. Те модели, за которые проголосовало наибольшее число признаков мы принимаем за искомый результат. Мы считаем, что выбросы\шумные данные не будут голосовать согласованно. Практической реализацией схем голосования будут преобразования специального вида, прореживающие наборы специальных точек на два класса – принадлежащих заданной преобразованием модели и нет.

Самое известное преобразование – преобразование Хафа (Hough Transform). Эффективно в случае если на изображении мало точек для перебора.

Альтернатива – преобразование Радона (Radon transform). Эффективен если мало возможных конфигураций кривых.

Схемы голосования могут эффективно работать в условиях перекрытий и производить поиск нескольких экземпляров объектов за проход. Есть некоторая устойчивость к шуму. Однако сложно выбрать правильный размер сетки и большое количество параметров приводит к фазовому пространство высокой размерности.

1 ping

  1. Практическое введение в компьютерное зрение | Мои IT-заметки

    […] локальные особенности – за что зацепиться взгляду 04 – поиск преобразования между особыми точками и не… 05 – машинное обучение для классификации […]

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>