Функции ускоренного тестирования сегментов (FAST) - это метод обнаружения углов, который можно использовать для извлечения характерных точек, а затем использовать для отслеживания и сопоставления объектов во многих задачах компьютерного зрения . Угловой детектор FAST был первоначально разработан Эдвардом Ростеном и Томом Драммондом и опубликован в 2006 году. [1] Наиболее многообещающим преимуществом углового детектора FAST является его вычислительная эффективность. Ссылаясь на свое название, он действительно быстрее, чем многие другие известные методы извлечения признаков, такие как разность гауссиан (DoG), используемые SIFT , SUSAN и Harris.детекторы. Более того, когда применяются методы машинного обучения, может быть достигнута превосходная производительность с точки зрения времени вычислений и ресурсов. Угловой детектор FAST очень подходит для обработки видео в реальном времени из-за его высокой скорости работы.
Сегментный тестовый детектор
Детектор углов FAST использует круг из 16 пикселей ( круг Брезенхема с радиусом 3), чтобы определить, является ли точка-кандидат p на самом деле углом. Каждый пиксель в круге помечен целым числом от 1 до 16 по часовой стрелке. Если набор из N смежных пикселей в круге все ярче, чем интенсивность пикселя-кандидата p (обозначается I p ) плюс пороговое значение t, или все темнее, чем интенсивность пикселя-кандидата p минус пороговое значение t, то p классифицируется как угол. Условия можно записать как:
- Условие 1: набор из N смежных пикселей S, , интенсивность x> I p + порог, или
- Условие 2: набор из N смежных пикселей S, ,
Таким образом, когда выполняется одно из двух условий, кандидата p можно классифицировать как угол. Существует компромисс между выбором N, количества смежных пикселей и порогового значения t. С одной стороны, количество обнаруженных угловых точек не должно быть слишком большим, с другой стороны, высокая производительность не должна достигаться за счет снижения вычислительной эффективности. Без усовершенствования машинного обучения N обычно выбирается равным 12. Для исключения неугловых точек можно применить метод высокоскоростного тестирования.
Скоростной тест
Высокоскоростной тест для отбраковки неугловых точек проводится путем проверки 4 примерных пикселей, а именно пикселей 1, 9, 5 и 13. Поскольку должно быть не менее 12 смежных пикселей, которые все ярче или темнее, чем предполагаемый угол, поэтому должно быть не менее 3 пикселей из этих 4 пикселей примера, которые все ярче или темнее, чем угол кандидата. Сначала проверяются пиксели 1 и 9, если и I 1, и I 9 находятся в пределах [I p - t, I p + t], то кандидат p не является углом. В противном случае пиксели 5 и 13 дополнительно исследуются, чтобы проверить, являются ли три из них ярче, чем I p + t, или темнее, чем I p - t. Если существует 3 из них, которые являются более яркими или темными, остальные пиксели затем исследуются для окончательного вывода. И, по словам изобретателя в его первой статье [2], в среднем требуется 3,8 пикселя для проверки возможного углового пикселя. По сравнению с 8,5 пикселями для каждого угла кандидата, 3,8 - действительно большое сокращение, которое может значительно улучшить производительность.
Однако у этого метода тестирования есть несколько недостатков:
- Высокоскоростной тест не может быть хорошо обобщен для N <12. Если N <12, возможно, что кандидат p является углом, и только 2 из 4 примеров тестовых пикселей оба ярче I p + t или темнее, чем I п - т.
- Эффективность детектора зависит от выбора и порядка этих выбранных тестовых пикселей. Однако маловероятно, что выбранные пиксели являются оптимальными из-за проблем с распределением углов.
- Обнаружены несколько объектов рядом друг с другом
Улучшение с помощью машинного обучения
Чтобы устранить первые два слабых места высокоскоростного тестирования, вводится подход машинного обучения, помогающий улучшить алгоритм обнаружения. Этот подход машинного обучения работает в два этапа. Во-первых, обнаружение угла с заданным N обрабатывается на наборе обучающих изображений, которые предпочтительно из области целевого приложения. Углы обнаруживаются с помощью простейшей реализации, которая буквально извлекает кольцо из 16 пикселей и сравнивает значения интенсивности с соответствующим порогом.
Для кандидата p каждое положение на окружности x ∈ {1, 2, 3, ..., 16} можно обозначить как p → x. Состояние каждого пикселя S p → x должно находиться в одном из следующих трех состояний:
- d, I p → x ≤ I p - t (темнее)
- s, I p - t ≤ I p → x ≤ I p + t (аналогично)
- b, I p → x ≥ I p + t (ярче)
Затем выбор x (одинакового для всех p) разбивает P (набор всех пикселей всех обучающих изображений) на 3 разных подмножества, P d , P s , P b, где:
- P d = {p ∈ P: S p → x = d}
- P s = {p ∈ P: S p → x = s}
- P b = {p ∈ P: S p → x = b}
Во-вторых, алгоритм дерева решений, алгоритм ID3 применяется к 16 точкам для достижения максимального информационного выигрыша . Пусть K p будет логической переменной, которая указывает, является ли p углом, тогда энтропия K p используется для измерения информации о том, что p является углом. Для набора пикселей Q полная энтропия K Q (ненормированная) равна:
- H (Q) = (c + n) журнал 2 (c + n) - засорение 2 c - n log 2 n
- где c = | {i ∈ Q: K i истинно} | (количество углов)
- где n = | {i ∈ Q: K i ложно} | (количество не углов)
Прирост информации можно представить в виде:
- H g = H (P) - H (P b ) - H (P s ) - H (P d )
К каждому подмножеству применяется рекурсивный процесс, чтобы выбрать каждый x, который может максимизировать получение информации . Например, сначала выбирается x, чтобы разделить P на P d , P s , P b с наибольшим количеством информации; затем для каждого подмножества P d , P s , P b выбирается другой y, чтобы дать наибольший выигрыш в информации (обратите внимание, что y может быть таким же, как x). Этот рекурсивный процесс заканчивается, когда энтропия равна нулю, так что либо все пиксели в этом подмножестве являются углами, либо неуглами.
Это сгенерированное дерево решений затем может быть преобразовано в программный код, такой как C и C ++, который представляет собой просто набор вложенных операторов if-else. В целях оптимизации для компиляции кода используется оптимизация по профилю . Собранный код позже используется в качестве детектора углов для других изображений.
Обратите внимание, что углы, обнаруженные с помощью этого алгоритма дерева решений , должны немного отличаться от результатов с использованием детектора тестирования сегмента. Это связано с тем, что эта модель дерева решений зависит от обучающих данных, которые не могут охватить все возможные углы.
Не максимальное подавление
«Так как сегментный тест не вычисляет функцию отклика угла, не максимальное подавление не может применяться непосредственно к результирующим элементам». Однако, если N фиксировано, для каждого пикселя p сила угла определяется как максимальное значение t, которое делает угол pa. Таким образом, можно использовать два подхода:
- Алгоритм двоичного поиска может быть применен , чтобы найти наибольший т , для которых р по - прежнему угол. Таким образом, каждый раз для алгоритма дерева решений устанавливается другое t. Когда ему удается найти наибольшее t, это t можно рассматривать как силу угла.
- Другой подход - это итерационная схема, где каждый раз t увеличивается до наименьшего значения, которое проходит проверку.
FAST-ER: повышенная повторяемость
Детектор FAST-ER является усовершенствованием детектора FAST, использующим метаэвристический алгоритм, в данном случае моделируемый отжиг . Чтобы после оптимизации структура дерева решений была оптимизирована и подходила для точек с высокой повторяемостью. Однако, поскольку имитация отжига является метаэврическим алгоритмом, каждый раз алгоритм будет генерировать другое оптимизированное дерево решений. Поэтому лучше провести эффективно большое количество итераций, чтобы найти решение, близкое к реальному оптимальному. По словам Ростена, для оптимизации детектора FAST требуется около 200 часов на Pentium 4 с частотой 3 ГГц, что составляет 100 повторений 100 000 итераций.
Сравнение с другими детекторами
В исследовании Ростена [3] детекторы FAST и FAST-ER оцениваются на нескольких различных наборах данных и сравниваются с угловыми детекторами DoG , Харриса , Харриса-Лапласа , Ши-Томази и SUSAN .
Установки параметров для извещателей (кроме FAST) следующие:
Детектор | Установка параметра | Значение |
---|---|---|
Собака | ||
Шкалы на октаву | 3 | |
Начальное размытие σ | 0,8 | |
Октавы | 4 | |
СЬЮЗЕН | Порог расстояния | 4.0 |
Харрис, Ши-Томази | Размытие σ | 2,5 |
Харрис-Лаплас | Начальное размытие σ | 0,8 |
Харрис размытие | 3 | |
Октавы | 4 | |
Шкалы на октаву | 10 | |
Общие параметры | ε | 5 пикселей |
- Результат теста повторяемости представлен в виде усредненной площади под кривыми повторяемости для 0-2000 углов на кадр по всем наборам данных (кроме аддитивного шума):
Детектор | А |
---|---|
БЫСТРЕЕ | 1313,6 |
БЫСТРО-9 | 1304,57 |
СОБАКА | 1275,59 |
Ши и Томази | 1219,08 |
Харрис | 1195,2 |
Харрис-Лаплас | 1153,13 |
БЫСТРО-12 | 1121,53 |
СЬЮЗЕН | 1116,79 |
Случайный | 271,73 |
- Тесты скорости проводились на компьютере Pentium 4-D с тактовой частотой 3,0 ГГц. Набор данных делится на обучающий набор и тестовый набор. Обучающая выборка состоит из 101 монохромного изображения с разрешением 992 × 668 пикселей. Тестовый набор состоит из 4968 кадров монохромного видео формата 352 × 288. И вот результат:
Детектор | Скорость пикселей обучающего набора | Скорость пикселей тестового набора |
---|---|---|
БЫСТРО n = 9 | 188 | 179 |
БЫСТРО n = 12 | 158 | 154 |
Исходный FAST n = 12 | 79 | 82,2 |
БЫСТРЕЕ | 75,4 | 67,5 |
СЬЮЗЕН | 12,3 | 13,6 |
Харрис | 8,05 | 7,90 |
Ши-Томази | 6.50 | 6.50 |
Собака | 4,72 | 5.10 |
Рекомендации
- ^ Ростен, Эдвард; Драммонд, Том (2006). «Машинное обучение для высокоскоростного обнаружения углов». Компьютерное зрение - ECCV 2006 . Конспект лекций по информатике. 3951 . С. 430–443. DOI : 10.1007 / 11744023_34 . ISBN 978-3-540-33832-1. S2CID 1388140 .
- ^ Эдвард Ростен, Видеоаннотации в реальном времени для дополненной реальности
- ^ Эдвард Ростен, БЫСТРЕЕ и лучше: подход машинного обучения к обнаружению углов
Библиография
- Ростен, Эдвард; Том Драммонд (2005). Точки соединения и линии для высокопроизводительного отслеживания (PDF) . Международная конференция IEEE по компьютерному зрению . 2 . С. 1508–1511. CiteSeerX 10.1.1.60.4715 . DOI : 10.1109 / ICCV.2005.104 . ISBN 978-0-7695-2334-7.
- Ростен, Эдвард; Рид Портер; Том Драммонд (2010). «БЫСТРЕЕ и лучше: подход машинного обучения к обнаружению углов». IEEE Transactions по анализу шаблонов и машинному анализу . 32 (1): 105–119. arXiv : 0810.2434 . DOI : 10.1109 / TPAMI.2008.275 . PMID 19926902 .
- Ростен, Эдвард; Том Драммонд (2006). Машинное обучение для высокоскоростного определения углов (PDF) . Европейская конференция по компьютерному зрению . Конспект лекций по информатике. 1 . С. 430–443. CiteSeerX 10.1.1.64.8513 . DOI : 10.1007 / 11744023_34 . ISBN 978-3-540-33832-1.
Внешние ссылки
- Домашняя страница Advanced Vision