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

Детектор проверки сегмента

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

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

Испытание на высоких скоростях

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

Имеется, однако, некоторые недостатки для этого метода тестирования: Высокоскоростной тест плохо обобщается для N < 12. Если N < 12, может оказаться, что кандидат p является углом и только 2 из 4 тестовых пикселов будут либо ярче Ip + t, либо темнее Ip - t. Эффективность детектора зависит от выбора и порядка этих выбранных тестовых пикселов. Однако маловероятно, что выбранные пикселы являются оптимальными, учитывая распределение появления углов. Множественные признаки обнаруживаются рядом друг с другом.

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

Для кандидата p, каждое местонахождение на круге x ∈ {1, 2, 3, ..., 16} может быть обозначено как p→x. Состояние каждого пиксела, Sp→x, должно находится в одном из трёх состояний: d, Ip→x ≤ Ip - t (темнее) s, Ip - t ≤ Ip→x ≤ Ip + t (похоже) b, Ip→x≥ Ip + t (ярче)

Затем выбирается x (один и тот же для всех p), который разбивает P (множество всех пикселов обучающих изображений) на три подмножества: Pd = {p ∈ P : Sp→x = d } Ps = {p ∈ P : Sp→x = s } Pb = {p ∈ P : Sp→x = b }

Затем к 16 локациям применяется алгоритм ID3 построения дерева решений для достижения максимального информационного выигрыша. Пусть Kp будет булевой переменной, которая указывает, является ли пиксел p углом, тогда энтропия Kp используется для измерения информативности пиксела p как угла. Для множества пикселов Q полная энтропия KQ (не нормализованная) равна: H(Q) = ( c + n ) log2( c + n ) - clog2c - nlog2n где c = |{ i ∈ Q: Ki is true}| (число углов) где n = |{ i ∈ Q: Ki is false}| (число неуглов)

Информационный выигрыш может быть затем представлен как: Hg= H(P) - H(Pb) - H(Ps) - H(Pd)

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

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

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

Подавления немаксимумов «Поскольку проверка сегмента не вычисляет функцию отклика угла, подавление немаксимумов не может быть напрямую применено к полученным признакам.» Однако, если N фиксировано, для каждого пиксела p сила угла определяется как максимальное значение t, при котором p является углом. Следовательно, можно использовать два подхода: Можно применить двоичный поиск для нахождения наибольшего t, при котором p всё ещё является углом. Таким образом, каждый раз для алгоритма дерева решений устанавливается другое t. Когда удаётся найти наибольшее t, его можно считать силой угла. Другой подход — это итерационная схема, при которой каждый раз t увеличивается до наименьшего значения, проходящего тест.

Применение подавления немаксимумов для сокращения множества кандидатов оставляет только кандидатов имеющих локально максимальные оценки. Для каждого кандидата его оценка сравнивается с оценками соседних кандидатов в окне 3x3 и любой кандидат, чья оценка не является максимальной в этой окрестности, подавляется и отбрасывается. Этот процесс устраняет дублирующиеся обнаружения, сгруппированные вокруг одного и того же углового местоположения.

FAST-ER: Улучшенная повторяемость Детектор FAST-ER (Enhanced repeatability) является улучшением детектора FAST с использованием метаалгоритма, в данном случае — имитации отжига. Авторы используют алгоритм ID3 для классификации особых точек (является ли точка-кандидат особой точкой) с помощью деревья решений. Алгоритм ID3 оптимизирует порядок, в котором обрабатываются пикселы, в результате чего получается наиболее вычислительно эффективный детектор.

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

Базовый детектор FAST демонстрирует примерно 50-60% повторяемости при умеренных преобразованиях, таких как повороты на 30° и изменения масштаба до 2 раз. Однако производительность значительно снижается при размытии или изменении освещения, часто падая ниже 40% на последовательностях с гауссовым размытием (σ > 2) или меняющимися условиями освещения. Вариант FAST-ER, оптимизированный с помощью машинного обучения для повышения повторяемости, улучшает этот показатель до 80% при умеренных изменениях точки обзора и масштаба.

Примечания

Литература

часть 1

Ссылка Advanced Vision homepage

Категория:Выделение признаков (компьютерное зрение)