Устойчивые Ускоренные Признаки (, SURF) — это локальный детектор признаков и дескриптор, имеющий запатентованные применения. Он используется для решения таких задач, как распознавание образов, регистрация изображения, классификация, или трёхмерная реконструкция. Частично он был вдохновлён на создание появлением дескриптора преобразования признаков, инвариантного к масштабу (SIFT). Стандартная версия SURF работает в несколько раз быстрее SIFT, и, по утверждению авторов, более устойчива к различным преобразованиям изображений, чем SIFT.

SURF решает две задачи — поиск признаков и создание их дескрипторов, инвариантных к масштабу и вращению. Это означает, что описание точки интереса будет одинаковым, даже если образец изменит размер и будет повёрнут.

Описание Для обнаружения ключевых точек SURF использует целочисленную аппроксимацию определителя гессиана, который можно вычислить с помощью трёх целочисленных операций, используя предварительно вычисленное . Дескриптор признаков основан на сумме откликов вейвлетов Хаара вокруг точки интереса. Их также можно вычислить с помощью интегрального изображения. Гессиан инвариантен относительно вращения, но не инвариантен масштабу, потому SURF использует разномасштабные фильтры для нахождения гессианов.

Дескрипторы SURF применялись для локализации и распознавания объектов, людей или лиц, для реконструкции 3D-сцен, для отслеживания объектов и для извлечения точек интереса.

SURF был впервые опубликован Гербертом Бэем, Тинне Тюйтелаарсом и Люком Ван Голом и представлен на в 2006 году. Применение алгоритма запатентовано в США. «Вертикальная» версия SURF (называемая U-SURF) не инвариантна к повороту изображения, поэтому вычисляется быстрее и лучше подходит для приложений, где камера остаётся более или менее горизонтальной.

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

Алгоритм и признаки Алгоритм SURF основан на тех же принципах и шагах, что и SIFT, но детали реализации каждого этапа отличаются. Алгоритм состоит из трёх основных частей: обнаружение точек интереса, описание локальной окрестности и сопоставление.

Обнаружение точек интереса SURF использует фильтры квадратной формы в качестве аппроксимации размытия по Гауссу. (В подходе SIFT используются каскадные фильтры для обнаружения инвариантных к масштабу характерных точек, где разница Гауссиан вычисляется на последовательно масштабированных изображениях.) Фильтрация изображения с помощью квадрата значительно ускоряется при использовании :

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

SURF использует детектор пятен, основанный на матрице Гессе, для поиска точек интереса. Определитель матрицы Гессе служит мерой локального изменения вокруг точки, и выбираются те точки, где этот детерминант максимален. В отличие от детектора «лапласиан гауссиана», разработанного Миколайчиком и Шмидом, SURF также использует детерминант Гессе для выбора масштаба, как это делает и Линдеберг. Для точки в изображении матрица Гессе в точке и масштабе определяется как:

где и т.д. — это свёртка производной второго порядка Гауссиана с изображением в точке .

Прямоугольный фильтр размера 9×9 является аппроксимацией Гауссиана с σ=1,2 и представляет собой самый низкий уровень (наивысшее пространственное разрешение) для карт отклика пятен.

Представление в масштабном пространстве определение местоположения ключевых точек Точки интереса могут быть найдены в различных масштабах, отчасти потому, что поиск соответствий часто требует сравнения изображений, где они видны в разных масштабах. В других алгоритмах выделения признаков масштабное пространство обычно реализуется как пирамида изображений. Изображения многократно сглаживаются гауссовым фильтром, затем они подвергаются субдискретизации для получения следующего более высокого уровня пирамиды. Таким образом, рассчитываются несколько уровней или ступеней с различными размерами масок:

Масштабное пространство разбивается на октавы, где каждая октава представляет собой последовательность карт откликов, охватывающих удвоение масштаба. В SURF наименьший уровень пространства масштабов получается из выходных данных фильтров размером 9×9.

Таким образом, в отличие от предыдущих методов, пространства масштабов в SURF реализуются путём применения фильтров в виде прямоугольных областей разного размера. Соответственно, масштабное пространство анализируется путём увеличения размера фильтра, а не итеративного уменьшения размера изображения. Выходные данные упомянутого фильтра 9×9 считаются начальным слоем масштаба при s =1,2 (что соответствует производным Гаусса с σ = 1,2). Последующие слои получаются путем фильтрации изображения с постепенно увеличивающимися масками, учитывая дискретную природу интегральных изображений и специфическую структуру фильтра. Это приводит к фильтрам размером 9×9, 15×15, 21×21, 27×27,.... Для локализации точек интереса в изображении и по масштабам применяется подавление не-максимумов в окрестности 3×3×3. Затем максимумы определителя матрицы Гессе интерполируются по масштабу и пространству изображения методом, предложенным Брауном и др. Интерполяция масштабного пространства в данном случае особенно важна, поскольку разница в масштабе между первыми слоями каждой октавы относительно велика.

Дескриптор После нахождения точек интереса SURF формирует дескрипторы, представляющие собой набор из 64 (или 128) чисел для каждой точки. Эти числа отображают направление градиента вокруг точки интереса. Поскольку точка интереса представляет собой максимум гессиана, в окрестности точки должны быть участки с разными градиентами. Направление градиента окрестностей точки интереса считается относительно градиента вокруг точки в целом, чем достигается инвариантность относительно вращения. Цель дескриптора — дать уникальное и надёжное описание признака изображения, например, путём описания распределения интенсивности пикселов в окрестности точки интереса. Большинство дескрипторов вычисляются локально, поэтому описание получается для каждой ранее определённой точки интереса.

Размерность дескриптора напрямую влияет как на его вычислительную сложность, так и на надёжность/точность сопоставления точек. Короткий дескриптор может быть более устойчивым к изменениям внешнего вида, но может не обеспечивать достаточной дискриминации и, следовательно, давать слишком много ложных срабатываний.

Первый шаг заключается в фиксации воспроизводимой ориентации на основе информации из круговой области вокруг точки интереса. Затем строится квадратная область, выровненная по выбранной ориентации, и из неё извлекается дескриптор SURF.

Присвоение ориентации Для достижения инвариантности к вращению, ориентация точки интереса должна быть найдена. Вычисляются отклики вейвлета Хаара как по оси x, так и по оси y в круговой окрестности радиусом вокруг точки интереса, где — это масштаб, при котором была обнаружена точка интереса. Полученные отклики взвешиваются гауссовой функцией, центрированной в точке интереса, затем строятся как точки в двумерном пространстве, с горизонтальным откликом по абсциссе и вертикальным откликом по ординате. Доминирующая ориентация оценивается путём вычисления суммы всех откликов в скользящем окне ориентации размером π/3. Горизонтальные и вертикальные отклики в окне суммируются. Две суммированные реакции затем дают локальный вектор ориентации. Самый длинный такой вектор в целом определяет ориентацию точки интереса. Размер скользящего окна — это параметр, который необходимо тщательно выбирать для достижения желаемого баланса между надёжностью и угловым разрешением.

Дескриптор на основе суммы откликов вейвлета Хаара Для описания области вокруг точки извлекается квадратная область, центрированная на интересующей точке и ориентированная в соответствии с выбранным выше направлением. Размер этого окна составляет 20s.

Интересующая область разбивается на более мелкие квадратные подобласти размером 4x4, и для каждой из них извлекаются отклики вейвлета Хаара в 5x5 регулярно расположенных точках выборки. Отклики взвешиваются с помощью Гауссовой функции (для повышения устойчивости к деформациям, шуму и сдвигам).

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

См. также Преобразование признаков, инвариантное к масштабу (SIFT) Гистограмма расположения и ориентации градиента (GLOH) (, LESH) Выделение пятен Выделение признаков (компьютерное зрение)

Примечания

Источники Andrea Maricela Plaza Cordero, Jorge Luis Zambrano-Martinez, " Estudio y Selección de las Técnicas SIFT, SURF y ASIFT de Reconocimiento de Imágenes para el Diseño de un Prototipo en Dispositivos Móviles", 15º Concurso de Trabajos Estudiantiles, EST 2012 A. M. Romero and M. Cazorla, "Comparativa de detectores de característicasvisuales y su aplicación al SLAM ", X Workshop de agentes físicos, Setiembre 2009, Cáceres

J an Knopp, Mukta Prasad, Gert Willems, Radu Timofte, and Luc Van Gool, "Hough Transform and 3D SURF for Robust Three Dimensional Classification", European Conference on Computer Vision (ECCV), 2010

Ссылки SURF on GitHub Website of SURF: Speeded Up Robust Features First publication of Speeded Up Robust Features (2006) Revised publication of SURF (2008)

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