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

В качестве решения этой проблемы Функции ускоренного тестирования сегмента (FAST) представляет собой метод определения углов, который можно использовать для извлечения характерных точек, а затем использовать для отслеживания и сопоставления объектов. во многих задачах компьютерного зрения. Угловой детектор FAST был первоначально разработан Эдвардом Ростеном и Томом Драммондом и опубликован в 2006 году. Наиболее многообещающим преимуществом углового детектора FAST является его вычислительная эффективность. Более того, когда применяются методы машинного обучения, может быть достигнута превосходная производительность с точки зрения времени вычислений и ресурсов. Угловой детектор FAST очень подходит для обработки видео в реальном времени из-за его высокой скорости работы.

Это часть 7-й серии Feature Detection and Matching. Другие статьи включены

Обнаружение функций с помощью FAST

Алгоритм объясняется ниже:

  • Выберите пиксель p на изображении, который нужно идентифицировать как точку интереса или нет. Пусть его интенсивность будет Ip.
  • Выберите соответствующее пороговое значение t.
  • Рассмотрим круг из 16 пикселей вокруг тестируемого пикселя. (Это круг Брезенхема радиуса 3.)
  • Теперь пиксель p является углом, если в круге существует набор из n смежных пикселей (из 16 пикселей), которые все ярче, чем Ip + t, или все темнее, чем Ip - t. (Авторы использовали n = 12 в первой версии алгоритма)
  • Чтобы алгоритм работал быстрее, сначала сравните интенсивность пикселей 1, 5, 9 и 13 круга с Ip. Как видно из рисунка выше, по крайней мере три из этих четырех пикселей должны удовлетворять критерию порога, чтобы точка интереса существовала.
  • Если хотя бы три из четырех значений пикселей - I1, I5, I9, I13 не выше или ниже Ip + t , тогда p не является точкой интереса (угол). В этом случае отклоните пиксель p как возможную точку интереса. В противном случае, если хотя бы три пикселя находятся выше или ниже Ip + t, проверьте все 16 пикселей и проверьте, подпадают ли под критерий 12 смежных пикселей.
  • Повторите процедуру для всех пикселей изображения.

У алгоритма есть несколько ограничений. Во-первых, для n ‹12 алгоритм работает не очень хорошо во всех случаях, потому что когда n‹ 12 количество обнаруженных точек интереса очень велико. Во-вторых, порядок, в котором запрашиваются 16 пикселей, определяет скорость работы алгоритма. Для решения этих проблем в алгоритм был добавлен подход машинного обучения.

Подход к машинному обучению

  • Выберите набор изображений для обучения (желательно из целевого домена приложения)
  • Запустите алгоритм FAST на каждом изображении, чтобы найти характерные точки.
  • Для каждой характерной точки сохраните 16 пикселей вокруг нее как вектор. Сделайте это для всех изображений, чтобы получить векторную характеристику p.
  • Каждый пиксель (скажем, x) в этих 16 пикселях может иметь одно из следующих трех состояний:

  • В зависимости от этих состояний вектор признаков P подразделяется на 3 подмножества Pd, Ps, Pb.
  • Определите переменную Kp, которая имеет значение true, если p является точкой интереса, и false, если p не представляет интереса.
  • Используйте алгоритм ID3 (классификатор дерева решений), чтобы запросить каждое подмножество, используя переменную Kp, чтобы узнать истинный класс.
  • Алгоритм ID3 работает по принципу минимизации энтропии. Запросите 16 пикселей таким образом, чтобы истинный класс был найден (точка интереса или нет) с минимальным количеством запросов. Или, другими словами, выберите пиксель x, который содержит больше всего информации о пикселе p. Энтропия для набора P математически может быть представлена ​​как:

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

Немаксимальное подавление

Еще одна проблема - обнаружение нескольких точек интереса в соседних местах. Это решается с помощью не максимального подавления.

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

Ограничения алгоритма FAST

Другие методы обнаружения углов работают совершенно иначе, чем метод FAST, и удивительным результатом является то, что FAST не обнаруживает углы на компьютерных изображениях, которые идеально выровнены по осям x и оси Y. Поскольку обнаруженный угол должен иметь кольцо с более темными или более светлыми значениями пикселей вокруг центра, которое включает оба края угла, четкие изображения не работают.

Это связано с тем, что для алгоритма FAST требуется кольцо контрастных пикселей более чем на три четверти вокруг центра угла. В изображении, созданном компьютером, оба края прямоугольника в углу находятся в кольце используемого пикселя, поэтому тест на угол не проходит. Обходной путь к этой проблеме - добавить размытие (применяя фильтр Гаусса) к изображению, чтобы углы были менее точными, но их можно было обнаружить.

Реализация

Мне удалось реализовать FAST с помощью OpenCV. Вот как я это сделал:

Ссылка на Github для кода: https://github.com/deepanshut041/feature-detection/tree/master/fast

использованная литература

  • Вишванатан, Дипак. «Функции ускоренного сегментного тестирования (FAST)». (2011).
  • Эдвард Ростен и Том Драммонд, «Машинное обучение для высокоскоростного обнаружения углов» на 9-й Европейской конференции по компьютерному зрению, т. 1. 2006. С. 430–443.
  • Эдвард Ростен, Рид Портер и Том Драммонд, «Быстрее и лучше: подход машинного обучения к обнаружению углов» в IEEE Trans. Анализ шаблонов и машинный интеллект, 2010, том 32, стр. 105–119.
  • Https://docs.opencv.org/3.0-beta/doc/py_tutorials/py_feature2d/py_fast/py_fast.html
  • Https://in.udacity.com/course/computer-vision-nanodegree--nd891

Спасибо за прочтение! Если вам понравилось, нажмите кнопку хлопка ниже и следите за Data Breach, чтобы получать больше обновлений.