Мы видели несколько детекторов функций, и многие из них действительно хороши. Но если смотреть с точки зрения приложения в реальном времени, они недостаточно быстры. Лучшим примером может служить мобильный робот SLAM (одновременная локализация и отображение), который имеет ограниченные вычислительные ресурсы.
В качестве решения этой проблемы Функции ускоренного тестирования сегмента (FAST) представляет собой метод определения углов, который можно использовать для извлечения характерных точек, а затем использовать для отслеживания и сопоставления объектов. во многих задачах компьютерного зрения. Угловой детектор FAST был первоначально разработан Эдвардом Ростеном и Томом Драммондом и опубликован в 2006 году. Наиболее многообещающим преимуществом углового детектора FAST является его вычислительная эффективность. Более того, когда применяются методы машинного обучения, может быть достигнута превосходная производительность с точки зрения времени вычислений и ресурсов. Угловой детектор FAST очень подходит для обработки видео в реальном времени из-за его высокой скорости работы.
Это часть 7-й серии Feature Detection and Matching. Другие статьи включены
- Введение в обнаружение и сопоставление признаков
- Введение в угловой детектор Харриса
- Введение в SIFT (масштабно-инвариантное преобразование признаков)
- Введение в SURF (ускоренные и надежные функции)
- Введение в BRIEF (бинарные устойчивые независимые элементарные функции)
- Введение в ORB (Ориентированный БЫСТРЫЙ и повернутый КРАТКИЙ ОБЗОР)
Обнаружение функций с помощью 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