Масштабно-инвариантная трансформация признаков (, SIFT) является алгоритмом выявления признаков в компьютерном зрении для выявления и описания локальных признаков в изображениях. Алгоритм был запатентован в Канаде университетом Британской Колумбии и опубликован Дэвидом Лоу в 1999. Приложения включают , и роботизированную навигацию, , трёхмерное моделирование, распознавание жестов, трекинг, идентификацию диких животных и позиционный трекинг.

Сначала в SIFT извлекаются ключевые точки объектов из набора контрольных изображений и запоминаются в базе данных. Объект распознаётся в новом изображении путём сравнивания каждого признака из нового изображения с признаками из базы данных и нахождения признаков-кандидатов на основе евклидова расстояния между векторами признаков. Из полного набора соответствий в новом изображении отбираются поднаборы ключевых точек, которые наиболее хорошо согласуются с объектом по его местоположению, масштабу и ориентации. Определение подходящих блоков признаков осуществляется быстро с помощью эффективной реализации хеш-таблицы обобщённого преобразования Хафа. Каждый блок из 3 или более признаков, согласующийся с объектом и его положением, подлежит дальнейшей подробной проверке соответствия модели, и резко отклоняющиеся блоки отбрасываются. Наконец, вычисляется вероятность, что определённый набор признаков говорит о присутствии объекта, что даёт информацию о точности совпадения и числе возможных промахов. Объекты, которые проходят все эти тесты, могут считаться правильными с высокой степенью уверенности.

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

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

SIFT, «Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image» («Метод и аппараты для обнаружения инвариантных по масштабу признаков в изображении и использование их для нахождения объекта в изображении»), патент Дэвида Лоу на алгоритм SIFT, Март 23, 2004 может надёжно выделить объекты даже при наличии шума и частичном перекрытии, поскольку описатель признака SIFT инвариантен , ориентации, изменению освещённости и частично инвариантен аффинным искажениям. Эта секция описывает исходный алгоритм SIFT и упоминает несколько конкурирующих техник, доступных для распознавания объектов с шумом и с частичным перекрытием.

SIFT-дескриптор основан на измерениях изображения в терминах рецепторных полей, для которых устанавливаются локальные инвариантные по масштабу опорные кадры путём выбора локального масштаба. Общее теоретическое объяснение алгоритма дано в статье проекта Scholarpedia о SIFT.

Задача Техника Преимуществоместо ключа / масштаб / поворотРазность гауссианов / пирамида масштабов пространства / назначение направленийточность, стабильность, инвариантность к масштабу и поворотугеометрическое искажениеразмывание / повторная выборка локальных плоскостей ориентации изображенияаффинная инвариантностьиндексирование и сопоставлениеближайший сосед / поиск «Best Bin First»Эффективность / скоростьИдентификация кластеровГолосование преобразования Хафанадёжные модели положенияПроверка адекватности модели / выявление выбросовЛинейный метод наименьших квадратовлучшая устойчивость к ошибкам с меньшим соответствиемОдобрение гипотезыАнализ байесовской вероятностинадёжность

Основные шаги

Обнаружение масштабно-инвариантных признаков Метод Лоу для генерации признаков изображения преобразует изображение в большой набор векторов признаков, каждый из которых инвариантен относительно (параллельного) переноса изображения, масштабирования и вращения, частично инвариантен изменению освещения и устойчив к локальным геометрическим искажениям. Эти признаки имеют похожие свойства с нейронами в основной зрительной коре, которые кодируют основные формы, цвет и выявление движения объекта в зрении приматов. Ключи местоположения определяются как максимум и минимум функции разности гауссианов, применённой в масштабном пространстве к серии сглаженных и повторно сделанных изображений. Точки-кандидаты с малой контрастностью и точки вдоль краёв отбрасываются. Локализованным ключевым точкам назначаются господствующие ориентации. Эти шаги обеспечивают большую стабильность ключевых точек для сопоставления и распознавания. SIFT-дескрипторы, устойчивые к локальным аффинным нарушениям, получают затем путём рассмотрения пикселей вокруг ключевого места размыванием и повторной выборкой плоскостей ориентации локального изображения.

Сопоставление признаков и индексация Индексация состоит из запоминания SIFT-ключей и идентификации соответствующих ключей из нового изображения. Лоу использовал модификацию алгоритма k-мерного дерева, который называется методом поиска (BBF), который может идентифицировать ближайшего соседа с большой вероятностью, используя лишь ограниченное количество вычислений. Алгоритм BBF использует модифицированный порядок поиска для алгоритма k-мерного дерева, так что области в пространстве признаков просматриваются в порядке их ближайшего расстояния от запрашиваемого местоположения. Этот порядок поиска требует использование основанной на куче очереди с приоритетом для эффективного определения порядка просмотра. Лучший кандидат для каждой ключевой точки находится путём установления его ближайшего соседа в базе данных ключевых точек из тренировочных изображений. Ближайшие соседи определяются как ключевые точки с минимальным евклидовым расстоянием от заданного вектора дескриптора. Вероятность, что соответствие корректно, можно определить путём вычисления отношения расстояния от ближайшего соседа к расстоянию до второго по расстоянию соседа.

Лоу отбрасывал все соответствия, в которых отношение расстояний больше 0,8, что исключает 90 % неверных соответствий, отбрасывая при этом менее 5 % правильных соответствий. Для дальнейшего улучшения эффективности алгоритм поиска «best-bin-first» останавливается после проверки первых 200 ближайших соседних кандидатов. Для базы данных с 100000 ключевыми точками это обеспечивает увеличение скорости по сравнению с точным поиском соседей на 2 порядка, при этом неверный выбор не выходит за 5 % от правильных соответствий.

Идентификация кластера голосованием преобразования Хафа Преобразование Хафа используются для кластеризации надёжной модели гипотез для поиска ключей, которые согласуются с конкретной модели. Преобразование Хафа выявляет кластеры признаков с согласованным толкованием с помощью голосования за каждый признак для всех положений объекта, которые согласуются с признаком. Когда кластеры признаков найдены с голосами за то же положение объекта, вероятность верной интерпретации много выше, чем для любого отдельного признака. Создаётся запись в хеш-таблице, которая содержит предполагаемое положение, ориентацию и масштаб из гипотезы соответствия. Осуществляется поиск по хеш-таблице для идентификации всех кластеров с минимум 3 элементами в области и области сортируются по уменьшению размера.

Каждая из ключевых точек SIFT определяет 2D местоположение, масштаб и ориентацию и каждая ключевая точка в базе данных имеет запись с её параметрами, относящимися к тренировочному изображению, в котором она была найдена. Аналогичное преобразование, вытекающее из этих 4 параметров, является только аппроксимацией к полному пространству положений с 6 степенями свободы для 3-мерных объектов и также не учитывает любые гибкие деформации. Таким образом, Лоу использовал для местоположения размеры областей в 30 градусов для ориентации, множителем 2 для масштаба и коэффициентом 0,25 для размера максимальной проекции тренировочного изображения (используя предсказанный масштаб). Для SIFT ключей, сгенерированных с большим масштабом, придаётся удвоенный вес по сравнению с ключами для меньшего масштаба. Это означает, что больший масштаб в состоянии отфильтровать с бо́льшей степенью вероятности соседей для проверки в меньшем масштабе. Это также улучшает эффективность распознавания, придавая бо́льший вес мене зашумлённому масштабу. Чтобы избежать проблемы эффектов границы при назначении области, каждая ключевая точка смотрит на голоса для 2 ближайших областей в каждом направлении, что даёт в общей сложности 16 значений для каждой гипотезы и дальнейшее размытие разброса положения.

Проверка модели методом наименьших квадратов Каждый установленный кластер является предметом процедуры проверки, в которой осуществляется решение для параметров аффинного преобразования, связанных с моделью изображения. Аффинное преобразование точки модели [x y]T в точку изображения [u v]T может быть записано следующим образом

где параллельный перенос равен [tx ty]T, а аффинное вращение, масштаб и растяжение представлено параметрами m1, m2, m3 и m4. Для получения параметров преобразования уравнение может быть переписано так, что все неизвестные оказались в вектор-столбце.

Равенство показывает одиночное сопоставление, но любое число соответствий может быть добавлено, где каждое соответствие добавляет две строки в первую и последнюю матрицу. По меньшей мере 3 соответствия нужны для получения решения. Мы можем записать эту линейную систему как

где A является известной матрицей (обычно m > n), x является неизвестным n-мерным вектором параметров, а b является известным m-мерным вектором измерений.

Таким образом, минимизирующий вектор является решением нормального уравнения

Решение системы линейных уравнений даётся в терминах матрицы , называемой для A, в виде

,

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

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