Особенности ускоренного тестирования сегментов

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

Сегментный тестовый детектор

Пиксели, используемые угловым детектором FAST

Детектор углов FAST использует круг из 16 пикселей ( круг Брезенхема радиуса 3), чтобы определить, является ли точка-кандидат p на самом деле углом. Каждый пиксель в круге помечен целым числом от 1 до 16 по часовой стрелке. Если набор из N смежных пикселей в круге все ярче, чем интенсивность пикселя-кандидата p (обозначаемого I _p ) плюс пороговое значение t, или все темнее, чем интенсивность пикселя-кандидата p минус пороговое значение t, тогда p классифицируется как угол. Условия можно записать так:

• Условие 1: набор из N смежных пикселей S, $\forall x\in S$, $I_{x}>I_{p}+t$ (темный угол на светлом фоне)
• Условие 2: Набор из N смежных пикселей S, $\forall x\in S$, $I_{x}<I_{p}-t$ (светлый угол на темном фоне)

Таким образом, когда любое из двух условий выполнено, кандидат p может быть классифицирован как угловой. Существует компромисс между выбором N, количеством смежных пикселей и пороговым значением t. С одной стороны, количество обнаруженных угловых точек не должно быть слишком большим, с другой стороны, высокая производительность не должна достигаться за счет жертвования вычислительной эффективностью. Без улучшения машинного обучения N обычно выбирается равным 12. Для исключения неугловых точек можно применить метод высокоскоростного тестирования.

Высокоскоростной тест

Высокоскоростной тест на отбраковку неугловых точек проводится путем проверки 4 образцовых пикселей, а именно пикселей 1, 9, 5 и 13. Поскольку должно быть как минимум 12 смежных пикселей, которые все ярче или темнее потенциального угла, поэтому из этих 4 пикселей в примере должно быть как минимум 3 ярче или темнее угла-кандидата. Сначала проверяются пиксели 1 и 9, если оба I ₁ и I ₉ находятся в пределах [I _p - t, I _p + t], то кандидат p не является углом. В противном случае дополнительно исследуются пиксели 5 и 13, чтобы проверить, являются ли три из них ярче, чем I _p + t, или темнее, чем I _p - t. Если существует 3 из них, которые либо ярче, либо темнее, остальные пиксели затем проверяются для окончательного заключения. И, по словам изобретателя в его первой статье, в среднем для проверки потенциального углового пикселя необходимо 3,8 пикселя. По сравнению с 8,5 пикселями для каждого предполагаемого угла, 3,8 — это действительно значительное сокращение, которое может значительно улучшить производительность.

Однако у этого метода тестирования есть несколько недостатков:

1. Высокоскоростной тест не может быть хорошо обобщен для N < 12. Если N < 12, возможно, что кандидат p является угловым, и только 2 из 4 тестовых пикселей в качестве примера одновременно ярче I _p + t или темнее I _п - т.
2. Эффективность детектора зависит от выбора и порядка выбранных тестовых пикселей. Однако маловероятно, что выбранные пиксели являются оптимальными, поскольку учитывается распределение углов.
3. Обнаружено несколько объектов, расположенных рядом друг с другом

Улучшение с помощью машинного обучения

Чтобы устранить первые два слабых места высокоскоростного тестирования, машинного обучения вводится подход , который помогает улучшить алгоритм обнаружения. Этот подход машинного обучения работает в два этапа. Во-первых, обнаружение угла с заданным 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 (аналогично)
• б, I _p→x ≥ I _p + t (ярче)

Затем выбрав x (одинаковый для всех p), разбивает P (набор всех пикселей всех обучающих изображений) на 3 разных подмножества, P _d , P _s , P _b где:

• п _d знак равно {p ∈ P : S _p→x = d }
• P _s знак равно {p ∈ P : S _p→x = s }
• п _б = {p ∈ P : S _p→x = b }

Во-вторых, алгоритм дерева решений , алгоритм ID3, применяется к 16 локациям для достижения максимального получения информации . Пусть K _p — булева переменная, которая указывает, является ли p углом, тогда энтропия K p _{используется} для измерения информации о том, что p является углом. Для набора пикселей Q общая энтропия K _Q (не нормализованная) равна:

• H(Q) = ( c + n ) log ₂ ( c + n ) - засор ₂ c - nlog ₂ n
  • где c = |{i ∈ Q: K _i истинно}| (количество углов)
  • где n = |{ i ∈ Q: K _i ложно}| (количество неугловых)

Тогда прирост информации можно представить как:

• Hg _{= H (} P) - H(Pb ₎ - H(Ps ₎ - H( _Pd )

К каждому подмножеству применяется рекурсивный процесс, чтобы выбрать каждый x, который может максимизировать прирост информации. Например, сначала выбирается x для разделения P на Pd _, Ps _, Pb _с наибольшим количеством информации; затем для каждого подмножества P _d , P _s , P _b выбирается другой y, чтобы обеспечить наибольший прирост информации (обратите внимание, что y может быть таким же, как x ). Этот рекурсивный процесс заканчивается, когда энтропия равна нулю, так что либо все пиксели в этом подмножестве являются угловыми, либо неугловыми.

Это сгенерированное дерево решений затем можно преобразовать в программный код, такой как C и C++ , который представляет собой всего лишь набор вложенных операторов if-else. В целях оптимизации оптимизация на основе профиля для компиляции кода используется . Скомпилированный код позже используется в качестве детектора углов для других изображений.

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

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

«Поскольку тест сегмента не вычисляет функцию углового отклика, немаксимальное подавление не может быть применено непосредственно к результирующим объектам». Однако, если N фиксировано, для каждого пикселя p сила угла определяется как максимальное значение t, которое составляет угол pa. Таким образом, можно использовать два подхода:

• Алгоритм двоичного поиска можно применить для поиска наибольшего t, для которого p все еще является углом. Таким образом, каждый раз для алгоритма дерева решений устанавливается другое t. Когда ему удается найти наибольшее t, это t можно рассматривать как угловую силу.
• Другой подход представляет собой итерационную схему, в которой каждый раз t увеличивается до наименьшего значения, из которого проходит тест.

FAST-ER: повышенная повторяемость

Детектор FAST-ER — это усовершенствование детектора FAST, использующее метаэвристический алгоритм, в данном случае моделирующий отжиг . Чтобы после оптимизации структура дерева решений была оптимизирована и подходила для точек с высокой повторяемостью. Однако, поскольку имитация отжига представляет собой метаэврисический алгоритм, каждый раз алгоритм будет генерировать другое оптимизированное дерево решений. Поэтому лучше эффективно использовать большое количество итераций, чтобы найти решение, близкое к реальному оптимальному. с частотой 3 ГГц требуется около 200 часов По словам Ростена, на Pentium 4 , что соответствует 100 повторениям 100 000 итераций для оптимизации детектора FAST.

Сравнение с другими детекторами

В исследовании Ростена Детекторы FAST и FAST-ER оцениваются на нескольких различных наборах данных и сравниваются с угловыми детекторами DoG , Harris , Harris-Laplace , Shi-Tomasi и 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

Библиография

• Ростен, Эдвард; Том Драммонд (2005). «Слияние точек и линий для высокопроизводительного отслеживания». Десятая Международная конференция IEEE по компьютерному зрению (ICCV'05), Том 1 (PDF) . Том. 2. стр. 1508–1511. CiteSeerX   10.1.1.60.4715 . дои : 10.1109/ICCV.2005.104 . ISBN  978-0-7695-2334-7 . S2CID   1505168 .
• Ростен, Эдвард; Рид Портер; Том Драммонд (2010). «БЫСТРЕЕ и лучше: подход машинного обучения к обнаружению углов». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 32 (1): 105–119. arXiv : 0810.2434 . дои : 10.1109/TPAMI.2008.275 . ПМИД   19926902 . S2CID   206764370 .
• Ростен, Эдвард; Том Драммонд (2006). «Машинное обучение для высокоскоростного обнаружения углов». Компьютерное зрение – ECCV 2006 (PDF) . Конспекты лекций по информатике. Том. 1. С. 430–443. CiteSeerX   10.1.1.64.8513 . дои : 10.1007/11744023_34 . ISBN  978-3-540-33832-1 . S2CID   1388140 . {{cite book}}: |journal= игнорируется ( помогите )

Внешние ссылки

• Домашняя страница Advanced Vision