LIFT: Learned Invariant Feature Transform

    image


    Введение


    В последние годы вездесущие нейронные сети находят все больше и больше применений в различных областях знаний, вытесняя классические алгоритмы, использовавшиеся многие годы. Не стала исключением и область компьютерного зрения, где год за годом все больше и больше задач решаются при помощи современных нейронных сетей. Настало время написать об еще одном павшем бойце в войне "Традиционное зрение vs. Глубокое Обучение". Долгие годы на задаче поиска локальных особенностей изображений (так называемых ключевых точек) безраздельно властвовал алгоритм SIFT(Scale-invariant Feature Transform), предложеный в далеком 1999 году, многие сложили головы в попытках превзойти его, но удалось это лишь Deep Learning'у. Итак, встречайте, новый алгоритм поиска локальных особенностей — LIFT (Learned Invariant Feature Transform).


    Need for Data


    image


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


    • Инвариантность к расположению на картинке.
    • Инвариантность к углу поворота.
    • Инвариатность к масштабу.

    Окей, значит нам нужен датасет, содержащий кучу точек, где для каждой особой точки будет много сэмплов, полученных с разных ракурсов. Можно, конечно, взять произвольных картинок, нарезать с них точек, а затем применяя синтетически сгенерированные афинные преобразования получить датасет сколь угодно большого размера. Но синтетика плоха тем, что всегда есть некоторые ограничения по точности моделирования
    реальных кейсов. Реальные наборы данных, удовлетворяющих нашим требованиям, возникают при решении некоторых прикладных задач компьютерного зрения. Например, при 3D реконструкции сцен, снятых с нескольких ракурсов, мы делаем примерно следующее:


    • Для каждого изображения сцены находим особые точки.
    • Находим соответствия между особыми точками с разных изображений.
    • Но основе этой информации вычисляем пространственное расположение каждого кадра (параметризуемое через $[R, t]$ т.е. поворот и трансляцию относительно начала координат).
    • При помощи процедуры триангуляции находим 3D положения всех особых точек.
    • Используя развесистую оптимизацию аки Bundle Adjustment (чаще всего алгоритм, производные от метода Левенберга-Марквардта), получаем более точную информацию о расположении точек в пространстве.
    • Всякий разный постпроцессинг. Например, можно натянуть полигональную модель на облако точек, для получения гладких поверхностей.

    Как побочный продукт работы такого алгоритма, мы получаем облако точек, где каждой 3D точке соответствует несколько её 2D положений(проекций) на кадрах сцены. Вот такое облако — это как раз тот датасет, который нам нужен. Особо не заморачиваясь тонкостями Structure From Motion, авторы работы взяли пару имеющихся в публичном доступе датасетов для 3D реконструкции, прогнали их через публично доступный инструмент для построения облака точек (VisualSFM), и далее в своих экспериментах пользовались полученным набором данных. Как утверждается, натренированная на таком наборе сетка также обобщается и на другие типы сцен.


    Сетки, сетки, сетки


    image


    С датасетом мы разобрались, поэтому пора переходить к самому интересному, а именно — изучению сеток. Всю сетку можно разделить на 3 логических блока:


    • Detector — отвечает за поиск особых точек на всем изображении в целом.
    • Rotation Estimator — определяет ориентацию точки и доворачивает патч вокруг неё так, чтобы угол поворота стал равен нулю.
    • Descriptor — принимает на вход патч, по которому строит уникальный(тут как получится) вектор, описывающий этот патч. Эти вектора уже можно использовать, например, для того, чтобы посчитать Евклидово расстояние между парой точек и понять, похожи они или нет.

    Сначала рассмотрим инференс для этой модели в целом, а затем все блоки по отдельности и как именно они тренируются.


    Inference


    image
    Поиск особых точек и вычисление их дескрипторов происходит в несколько этапов:


    • Для начала строим пирамиду изображения (т.е. приводим исходное изображение к нескольким масштабам, для получения инвариантных к скейлу фич) для исходного изображения.
    • Каждый слой пирамиды прогоняем через сеть-детектор и вычисляется пирамида Score Map'ов.
    • При помощи процедуры Non-Maximum Suppression находим наиболее сильные кандидаты в особые точки.
    • Для каждой особой точки вырезаем патч, включающий в себя особую точку и некоторую её окрестность.
    • Выравниваем ориентацию каждого патча при помощи Orientation Estimator'а.
    • Вычисляем дескриптор для каждого выровненного патча.
    • Используем полученные дескрипторы для стандартной процедуры feature matching'а.

    Descriptor


    Еще со времен SIFT-фич известно, что даже если мы не особо хорошо умеем находить действительно уникальные точки, но можем построить для каждой из них крутой дескриптор, то скорей всего поставленную задачу мы решить сможем. Поэтому, начнем обзор с конца, а именно с построения дескриптора для уже найденной особой точки. Вообще говоря, любая сверточная сетка, принимая на вход картинку (патч), на выходе выдает некое описание этой картинки, которое уже можно использовать в качестве дескриптора. Но, как показывает практика, нет нужды брать огромную сеть, такую как, например, VGG16, ResNet-152, Inception etc., нам достаточно и маленькой сети: 2-3 сверточных слоя с активациями в виде гиперболических тангенсов
    и прочей мелочовки типа батч нормализаций и т.п.


    Для определенности, обозначим нашу дескриптор-сеть $d = h_{p}(p_{\theta})$, где $h(...)$ — сверточная сеть дескриптора, $p$ — её параметры, $p_{\theta}$ — патч с нулевым углом наклона (полученый от Rotation Estimator'а).


    Для каждой особой точки составим две пары:


    • $(p_{\theta}^{1}, p_{\theta}^2)$ — пара патчей, соответствующих проекциям одной и той-же особой точки.
    • $(p_{\theta}^{1}, p_{\theta}^3)$ — пара патчей, где первый принадлежит особой точке, а второй (негативный семпл) нет. При этом, «негативный» патч выбирается из некоторой окрестности, не слишком далекой, от позитива. В процессе тренировки окрестность уменьшается, чтобы негативные семплы становились все сложнее.

    В процессе обучения будем минимизировать loss-функцию следующего вида:


    $L_{desc} (p_{\theta}^k, p_{\theta}^l) = \begin{cases} \|h_p(p_{\theta}^k) - h_p(p_{\theta}^l) \|_{2}, для\ позитивов \\ max(0, C - \|h_p(p_{\theta}^k) - h_p(p_{\theta}^l) \|_{2}), для\ негативов \end{cases}$


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


    Rotation Estimator


    Так как мы можем наблюдать одну и ту же точку не только из разных точек пространства, но и под разными углами наклона, мы должны уметь строить одинаковый дескриптор для одной и той же особой точки, независимо от того, с какого угла мы её наблюдаем. Но вместо того, чтобы учить Descriptor запоминать все возможные углы наклона для одной и той же точки, предлагается использовать промежуточный вычислительный блок, который будет определять ориентацию патча в пространстве (Rotation Estimator) и "доворачивать" патч до некоторого своего инвариантного к повороту состояния (Spatial Transform). Конечно, можно было бы воспользоваться блоком вычисления ориентации патча в пространстве, взятым из алгоритма построения SIFT фич, но за окном 21 век и теперь принято всякую задачу компьютерного зрения сводить к машинному обучению. Вот и мы воспользуемся еще одной сверточной нейронной сетью для решения этой задачи.


    Итак, обозначим нашу нейронную сеть как: $\theta = g_{\phi}(p)$, где $\phi$ — параметры сети, а $p$ — исходный патч.


    В качестве обучающе выборки возьмем пары патчей $P^1$, $P^2$, принадлежащих одной особой точке, но имеющие разные углы наклона, а так-же их пространственные координаты $x^1$, $x^2$.


    В процессе обучения будем минимизировать следующую loss-функцию:


    $L_{orientation}(P^1, x^1, P^2, x^2) = \| h_p(G(P^1, x^1)) - h_p(G(P^2, x^2)) \|_2$


    где $G(P, x)$ — патч, полученный после процедуры коррекции его ориентации, $G(P, x) = Rot(P, x, g_{\phi}(Crop(P, x)))$.


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


    Detector


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


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


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


    $S = f_{\mu}(P) = \sum_n^N \beta_n \max_m^M(W_{mn}*P +b_{mn})$


    а затем, вычислить положение особой точки:


    $x = softargmax(S)$


    где $softargmax$ — это функция, вычисляющая взвешенный центр масс с весами, являющимися результатом вычисления $softmax$:


    $softargmax(S)=\frac{\sum_{y}\exp(\beta S(y))y}{\sum_{y}\exp(\beta S(y))}$


    где y — позиция внутри Score Map'ы, $\beta$ — гиперпараметр, отвечающий за коэффициент "размытия" softmax-функции.


    При тренировке детектора будем брать по четыре патча $(P^1, P^2, P^3, P^4)$, где $P^1, P^2$ — проекции одной и той-же особой точки, $P^3$ — проекция другой особой точки, $P^4$ — патч не принадлежащий особой точке. Для набобра таких патчей будем минимизировать следующую loss-функцию:


    $L_{detector}(P^1, P^2, P^3, P^4) = \gamma L_{class}(P^1, P^2, P^3, P^4) + L_{pair}(P^1, P^2)$


    где $\gamma$ — параметр балансировки для двух членов loss-функции.
    Член лосса, отвечающий за корректную классификацию на позитивы и негативы:


    $L_{class}(P^1, P^2, P^3, P^4) = \sum_{i=1}^{4}\alpha_i max(0, 1 - softmax(f_{\mu}(P^i))y_i)^2$


    Член лосса, отвечающий за точную локализацию особых точек:


    $L_{pair}(P^1, P^2)=\|h_p(G(P^1, softargmax(f_{\mu}(P^1)))) - h_p(G(P^2, softargmax(f_{\mu}(P^2)))) \|_2$


    Тренировка


    image


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


    Эксперименты


    image

    Сравнив с имеющимися ранее методами нахождения особых точек, авторы пришли к выводу, что их подход является state of the art.


    А результаты работы их сети можно посмотреть на следующем видео:



    Заключение


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


    Ссылки



    Спасибо за внимание.


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

    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 12
    • +2

      Как прекрасно, что у нас появляются оригинальные работы по тематике deep learning! А то все переводы, переводы...

      • +1
        Если я правильно понял, то эта статья все же вольный пересказ существующей работы. Извиняюсь если не прав.
        • 0

          Ага, обзор статьи по итогам её обсуждения в чатике.

      • 0
        Спасибо за статью! Очень круто, что получается такой сложный пайплайн end-to-end тренировать. И опять же интересен подход — используем для создания ground truth существующие, но очень дорогие методы, а потом тренируем модель, которая может работать везде.

        Можно каких-то ссылок добавить на реализацию-оригинал статьи-итд?
        • 0
          Можно каких-то ссылок добавить на реализацию-оригинал статьи-итд?

          Добавил пару полезных ссылок.

        • 0
          Вот интересно, если скормить этой штуке в качестве датасета определенный класс объектов, например лица, то вероятно получим некое подобие ландмарков, далее PCA и получим что-то вроде обучаемых моделей активной формы для произвольного класса объектов.
          • 0

            Народ вроде бы говорит, что задача поиска ландмарков для лиц уже решена… куда там еще улучшать?

            • 0
              А можно работу с state-of-the-art результатми? А то последний раз я пробовал dlib, и местный детектор не особо был точен на глазах
              • 0

                Я лицами особо не занимаюсь, но, вроде бы, сейчас Open Face и dlib — это как раз и есть state of the art из публично доступных фреймворков (в последний, кстати, сейчас активно запиливают deep learning).

                • +1
                  Недавно копался. Пока в dlib поиск лиц DL, а особые точки были не DL. Причём поиск не был подключаем для питона, только плюсы.
                  Это не мешает существовать другим открытым работам, где поиск и точек и лиц существует.
              • 0
                Да, но требуется датасет, размеченный человеческим существом :) а так можно было бы всю задачу скинуть на машину, т.к. по данным можно лучше вывести какие точки брать для данного объекта.
                • 0

                  Может быть что-то и должно получиться, хотя тут мне кажется, что GAN'ы могут дать результат и получше для feature selection'а.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.