Сопоставляем изображения с помощью ключевых точек

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

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

Поиск ключевых точек и сопоставление изображений — начальный этап перехода от 2D задач к 3D. Сопоставив между собой множество изображений сцены, мы сможем восстановить трёхмерную структуру объектов в ней. Но для этого важно иметь «хорошие» ключевые точки.

Ключевые точки

Они выделяются благодаря своим важным свойствам:

1. Repetability (воспроизводимость): на разных изображениях ключевая точка всегда находится на одном и том же месте.
2. Reliability (надёжность): точка находится на важном и характерном месте и не изменяется даже при небольших трансформациях изображения.

Получается, что ключевая точка непоколебима! Она обязательно найдётся на разных изображениях объекта, даже если они повернуты или масштабированы.

Дескрипторы

У каждой ключевой точки есть дескриптор.

«Хорошие» дескрипторы узнать несложно: у разных ключевых точек они должны быть сильно различны, а у одинаковых – максимально схожи.

Алгоритмы нахождения ключевых точек

Алгоритмы нахождения ключевых точек претерпели эволюцию: начинали с простых и не всегда эффективных методов, а в итоге добрались до deep learning’а.

Начнём с классики — SIFT

Один из первых и самых известных алгоритмов для нахождения ключевых точек – это SIFT (Scale-Invariant Feature Transform). Его будем использовать, когда не требуется решить что-то сверхсложное и нужно быстро и легко найти ключевые точки.

Как работает SIFT?

1. Картинка сворачивается с фильтром (по теории это вторая производная гауссианы). На практике сворачивают картинку с обычной гауссианой, а потом берут разность между двумя картинками с разным ядром. Получается почти тоже самое, но быстрее. Потом на результатах находят экстремумы – области с наибольшей и наименьшей интенсивностью. Таким образом, мы получаем «круги», центр которых будет темнее / ярче края. А значение константы сигма (то есть размер второй производной гауссианы) показывает размер этого blob’а.

1. Теперь, зная размер ключевой точки, мы можем посчитать дескрипторы и поворот точек. Для этого используем Histogramms of oriented gradients (HoG). Идея следующая: разобьём область под ключевой точкой на 16 квадрантов, посчитаем градиенты по картинке (почти как фильтр собеля), оставим только направление (их будет 8, верх, право верх, право и т.д.), для каждого квадранта посчитаем гистограммы направлений, а потом просто сделаем конкатенацию гистограмм. Для поиска поворота ключевой точки найдём направление с наибольшим значением и будем считать, что это верх ключевой точки.

Чтобы избавиться от помех, сверху можно применить некоторые дополнительные методы:

• CrossCheck: проверяем, что две точки являются взаимно ближайшими друг для друга (для точки A ближайшая B и для точки B ближайшая A).
• Lowe’s ratio test: смотрим, что первый ближайший сосед стоит сильно дальше второго.

Почему SIFT не справляется?

1. Сложные задачи, а порой даже довольно простые сцены, часто вызывают у него затруднения – для корректного срабатывания требуется большое пересечение между кадрами.
2. Алгоритм не устойчив к изменению угла обзора, по построению он устойчив к размеру и повороту. Даже если мы просто применим аффинное преобразование к изображению — качество упадёт.
3. Сложности возникают и с похожими паттернами: на одинаковом паттерне (обои, например) у разных ключевых точек будут одинаковые дескрипторы, из-за чего нормально сопоставить изображения не получится.

Зато SIFT быстрый, его легко запустить, и ему не нужен GPU. Поэтому он используется в качестве бейзлайн решения.

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

Современные подходы. Deep Learning!

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

Давайте рассмотрим каждый подход отдельно.

SuperPoint

«Одна голова хорошо, а две – лучше» – такова архитектура модели SuperPoint. Она основана на свёрточной нейросети (CNN), аналогичной VGG, с двумя выходными «головами»:

1. Одна «голова» отвечает за классификацию ключевых точек: определяет, является пиксель ключевой точкой или нет.
2. Вторая «голова» генерирует дескрипторы для каждого пикселя. Здесь каждый дескриптор – это вектор размерностью 128. Наша цель – сделать так, чтобы полученные дескрипторы отвечали главному принципу дескрипторов (помните, какому? 🙂).

Для обучения модели используются два основных лосса:

1. Кросс-энтропия для классификации ключевых точек.
2. Hinge Loss для дескрипторов. Лосс из metric learning, им будем стягивать дескрипторы у одинаковых ключевых точек.

По необходимости вместо этих лоссов могут использоваться и другие – *место для ваших экспериментов*.

Как всё же обучать SuperPoint?

Шаг 1: генерируем синтетику.

Создаём изображения, на которых будет понятно, где нужно разместить ключевые точки. Квадраты, линии, чёрточки, сетки, всё на фоне гауссового шума. В жизни это непонятно, а здесь будет легко (ставим точку на угол квадрата). Выучиваем сеть на этих данных и называем её MagicPoint.

Шаг 2: к этому шагу мы уже имеем достаточно надёжные, но пока невоспроизводимые ключевые точки. Например, точка может пропасть при изменении ракурса. Для решения этой проблемы применяется homography adaptation. Здесь тоже работаем по шагам:

1. Берём одну картинку и по-разному её трансформируем, то есть применяем случайные аффинные преобразования.
2. После этого прогоняем через MagicPoint эти картинки, а предсказанные точки объединяем. Таким образом, получаем разметку на предсказание (теперь воспроизводимых) ключевых точек.

Шаг 3: обучаем сетку.

Математически процесс выглядит так:

Матрица M – результат применения homography adaptation к изображению. Мы можем взять ключевые точки с одной матрицы и спроецировать их на другую. Сопоставив дескрипторы между двумя версиями изображения, будем оценивать расстояние между ними: если расстояние маленькое, то это одна и та же точка, и такие дескрипторы и нужно в конечном счёте стянуть. В итоге нейросеть обучается на основе сопоставления расстояний между точками и их дескрипторов, минимизируя ошибку в сопоставлении.

SiLK

Это более современный метод, в котором сохраняется простая архитектура: обычная CNN, похожий на VGG без maxpool (оставлены только свёрточные слои и ReLU-активации).

Лосс-функции

Здесь применяются две лосс-функции: одна для классификации, а другая — для нахождения дескрипторов.

1. Descriptor loss. Идея следующая: дескрипторы должны соответствовать друг другу. Мы стремимся к тому, чтобы для каждой точки её ближайший сосед на другом снимке был правильно определён, и наоборот (это называется cycle-consistency). То есть дескрипторы будут стягиваться друг к другу: точка A к точке B и точка B к точке A. Мы знаем, какие дескрипторы должны быть стянуты, так как заранее применили варпинг изображения и поняли, какие точки перешли друг в друга.
2. Лосс для классификации. Если пара дескрипторов действительно совпадает, и при этом оба дескриптора являются друг для друга ближайшими, то это «хорошая» точка, и ей классификатор предсказывает единичку. По мере обучения модель учится понимать, какие ключевые точки действительно «хорошие». Сначала предсказания случайны, но постепенно модель начинает более точно выделять надёжные точки.

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

Чем хорош SiLK и SuperPoint? Он достаточно быстрый и его легко дообучать. Нужны просто изображения из вашего целевого домена, а сам процесс обучения не требует разметки, он Self Supervised.

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

Поэтому далее мы перейдём к более современным методам.

SuperGlue

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

Архитектура:

1. На вход алгоритма подаются исходные ключевые точки и дескрипторы, полученные с помощью различных методов (например, SIFT или SuperPoint).
2. В основе модели лежит графовая свёрточная сеть, которая использует трансформер для установления связи между ключевыми точками на разных изображениях.
3. Модель решает задачу сопоставления каждой ключевой точки с точкой на другом изображении.
4. Для кодирования координат ключевых точек используются позиционные эмбеддинги, в то время как сами дескрипторы подаются в трансформер напрямую без изменений.
5. Self-attention оценивает взаимосвязи между дескрипторами внутри одного изображения, а cross-attention – между разными изображениями. После нескольких итераций дескрипторы обновляются, и формируются новые матрицы для их сопоставления.
6. Для вычисления окончательного сопоставления применяется дифференцируемый Sinkhorn-алгоритм, который нормализует строки и столбцы матрицы сопоставления для нахождения наилучших пар.

Особенности:

• Необходимость реальных данных для обучения. SuperGlue supervised метод. Разметку получают, прогоняя изображения через SfM, определяя позиции камер и карты глубин.
• Эффективная работа с разными условиями освещения, углами и масштабами.
• Применимость для сложных задач сопоставления изображений.

LoFTR

LoFTR упрощает архитектуру по сравнению с SuperGlue, объединяя все этапы обучения в единую сеть, которая обучается на реальных данных в режиме supervised. Фактически мы получаем Dense Keypoints, то есть мы можем сопоставлять хоть каждый пиксель друг с другом (вообще можем, но на деле у сети это не получится сделать).

Архитектура:

1. Для извлечения признаков используются ResNet и FPN.
2. Трансформер применяется как и в SuperGlue, но с линейной вариацией self-attention для уменьшения сложности, поскольку число «ключевых точек» (размерность карты признаков с ResNet) будет достаточно большим.

Обучение:

1. На первом этапе (coarse level) модель работает аналогично SuperGlue: дескрипторы с позиционными энкодингами проходят через комбинацию self- и cross-attention, после чего вычисляется скалярное произведение между всеми точками. В отличие от SuperGlue, здесь применяется softmax по строкам и столбцам вместо Sinkhorn-алгоритма. Упрощение (аппроксимация) Sinkhorn позволяет быстро и просто получить матрицу назначения.
2. На втором этапе для увеличения точности сопоставления ключевых точек происходит вырезание областей вокруг найденных точек и повторное сопоставление на более точных картах признаков.

Преимущества:

• Упрощённый пайплайн и обучение на одном датасете. Вместо двух разных сетей (SupePoint + SupeGlue) — один удобный пайлайн.
• Успешная работа модели с плохо текстурируемыми участками, поскольку она работает на каждом пикселе изображения в dense манере.

Единственный минус – тяжеловесный и медленный Dense-метод.

Заключение

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

1. SIFT – базовый подход для работы с ключевыми точками, который эффективен для плотного покрытия кадров.
2. SuperPoint и SiLK – нейросетевые аналоги SIFT, которые лучше справляются с поворотами и разнообразными сценами.
3. SuperGlue и LoFTR – end-to-end алгоритмы для сопоставления изображений, которые хорошо работают на сложных датасетах и сценах, но требуют размеченных обучающих данных.