Масштабно-инвариантная трансформация признаков

Соответствие особых точек найденных с помощью SIFT.

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

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

Обзор

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

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

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

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

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

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

Обнаружение масштабно-инвариантных признаков

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

Сопоставление признаков и индексация

Индексация состоит из запоминания SIFT-ключей и идентификации соответствующих ключей из нового изображения. Лоу использовал модификацию алгоритма k-мерного дерева, который называется методом поиска best-bin-first (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 может быть записано следующим образом

${\begin{bmatrix}u\\v\end{bmatrix}}={\begin{bmatrix}m1&m2\\m3&m4\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}+{\begin{bmatrix}tx\\ty\end{bmatrix}}$

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

${\begin{bmatrix}x&y&0&0&1&0\\0&0&x&y&0&1\\....\\....\end{bmatrix}}{\begin{bmatrix}m1\\m2\\m3\\m4\\tx\\ty\end{bmatrix}}={\begin{bmatrix}u\\v\\.\\.\end{bmatrix}}$

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

$A{\hat {\mathbf {x} }}\approx \mathbf {b} ,$

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

Таким образом, минимизирующий вектор ${\hat {\mathbf {x} }}$ является решением нормального уравнения

$A^{T}\!A{\hat {\mathbf {x} }}=A^{T}\mathbf {b} .$

Решение системы линейных уравнений даётся в терминах матрицы $(A^{T}A)^{-1}A^{T}$, называемой псеводообратной матрицей для A, в виде

${\hat {\mathbf {x} }}=(A^{T}\!A)^{-1}A^{T}\mathbf {b} .$,

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

Выявление выбросов

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

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

Признаки

Обнаружение и описание локальных признаков изображения может помочь в распознавании объекта. SIFT-признаки локальны и основываются на проявлениях объекта в конкретных особых точек. Они инвариантны по изменению масштаба изображения и вращению. Они также стабильны к изменениям в освещении, шумам и небольшим изменениям точки наблюдения. Кроме этих свойств, они высоко различимы, относительно легко извлекаются и позволяют идентификацию объекта с малой вероятности ошибки. Их относительно легко находить в (большой) базе данных локальных признаков, но, однако, высокая размерность признаков может вызвать трудности, поэтому используются вероятностные алгоритмы, такие как k-мерные деревья с поиском best-bin-first (BBF). Описание объекта с помощью SIFT-признаков также устойчиво относительно частичного перекрытия, поскольку даже трёх SIFT-признаков объекта достаточно для вычисления места и положения объекта. Распознавание может быть осуществлено за близкое к реальному время, по меньшей мере для малых баз данных современного компьютерного оборудования.

Алгоритм

Выявление экстремумов масштабного пространства

Мы начинаем с выявления точек, которые называются ключевыми точками в рамках SIFT. Изображение сворачивается с фильтрами Гаусса в различных масштабах, а затем вычисляется разность последовательных размытых по Гауссу изображений. Ключевые точки затем отбираются как максимум/минимум разности гауссианов, которые встречаются в различных масштабах. Разность гауссианов $D\left(x,y,\sigma \right)$ задаётся выражением

$D\left(x,y,\sigma \right)=L\left(x,y,k_{i}\sigma \right)-L\left(x,y,k_{j}\sigma \right)$,

где $L\left(x,y,k\sigma \right)$ является свёрткой исходного изображения $I\left(x,y\right)$ с размытием по Гауссу $G\left(x,y,k\sigma \right)$ в масштабе $k\sigma$, то есть,

$L\left(x,y,k\sigma \right)=G\left(x,y,k\sigma \right)*I\left(x,y\right)$

Отсюда, образ разности гауссианов между масштабами $k_{i}\sigma$ и $k_{j}\sigma$ является разностью размытых по Гауссу изображений с масштабами $k_{i}\sigma$ и $k_{j}\sigma$. Для определения экстремума в пространстве масштабирования в алгоритме SIFT изображение сначала свёртывается с размыванием по Гауссу в различных масштабах. Свёрнутые изображения группируются по октаве (октава соответствует удвоению значения $\sigma$) и значение $k_{i}$ выбирается так, что мы получаем фиксированное число свёрнутых изображений на октаву. Затем вычисляется разность гауссианов от смежных размытых по Гауссу изображений в октаве.

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

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

Локализация ключевых точек

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

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

Интерполяция соседних данных для точности положения

Во-первых, для каждого кандидата ключевой точки, интерполяция ближних данных используется для точного определения положения. Начальным подходом было определение мест каждой ключевой точки по положению и масштабу кандидата в ключевые точки. Новый подход вычисляет интерполированное положение экстремума, что существенно улучшает соответствие и стабильность. Интерполяция осуществляется с помощью квадратичного разложения Тейлора функции разности гауссианов масштабного пространства (англ. Difference-of-Gaussian scale-space function) $D\left(x,y,\sigma \right)$ с кандидатом в ключевые точки, расположенном в начале координат. Это разложение Тейлора задаётся уравнением:

$D({\textbf {x}})=D+{\frac {\partial D^{T}}{\partial {\textbf {x}}}}{\textbf {x}}+{\frac {1}{2}}{\textbf {x}}^{T}{\frac {\partial ^{2}D}{\partial {\textbf {x}}^{2}}}{\textbf {x}}$,

где D и её производная вычисляются в точке-кандидате, а ${\textbf {x}}=\left(x,y,\sigma \right)^{T}$ является смещением от этой точки. Местоположение экстремума ${\hat {\textbf {x}}}$ определяется взятием производной этой функции по ${\textbf {x}}$ и приравниванием к нулю. Если смещение ${\hat {\textbf {x}}}$ больше $0,5$ в любом направлении, это свидетельствует о том, что экстремум лежит ближе к другому кандидату в ключевые точки. В этом случае кандидат в ключевые точки меняется и осуществляется интерполяция для этой точки. В противном случае смещение добавляется к кандидату в ключевые точки, чтобы получить интерполированную оценку места экстремума. Аналогичное субпиксельное определение местоположения экстремумов масштабного пространства, разработанное Линдебергом с соавторами, осуществляется в реализация реального времени на основе гибридных пирамид.

Отбрасывание ключевых точек низкого контраста

Чтобы отбросить ключевые точки с низким контрастом, вычисляется разложение Тейлора второго порядка $D({\textbf {x}})$ со смещением ${\hat {\textbf {x}}}$. Если это значение меньше $0,03$, кандидат в ключевые точки отбрасывается. В противном случае он сохраняется с местоположением в конечном масштабном пространстве ${\textbf {y}}+{\hat {\textbf {x}}}$, где ${\textbf {y}}$ является исходным местоположением ключевой точки.

Исключение вклада рёбер

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

Для плохо определённых пиков функции разности гауссианов главная кривизна поперёк ребра будет много больше главной кривизны вдоль него. Нахождение этих главных кривизн соответствует нахождению собственных значений матрицы Гессе второго порядка H:

${\textbf {H}}={\begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\end{bmatrix}}$

Собственные значения H пропорциональны главным кривизнам матрицы D. Оказывается, что отношение двух собственных значений, скажем $\alpha$ — большее из них, а $\beta$ — меньшее, с отношением $r=\alpha /\beta$, достаточно для целей SIFT. След матрицы H, то есть $D_{xx}+D_{yy}$, даёт нам сумму двух собственных значений, в то время как определитель, то есть $D_{xx}D_{yy}-D_{xy}^{2}$, даёт произведение. Отношение ${\text{R}}=\operatorname {Tr} ({\textbf {H}})^{2}/\operatorname {Det} ({\textbf {H}})$, как можно показать, равно $(r+1)^{2}/r$, что зависит только от отношения собственных значений, а не индивидуальных значений. R является минимум, если собственные значения равны. Таким образом, чем выше абсолютное значение разности между двумя собственными значениями, которое эквивалентно наибольшему абсолютному значению разности между двумя главными кривизнами D, тем выше значение R. Отсюда следует, что для некоторого порогового отношения собственных значений $r_{\text{th}}$, если R для кандидата ключевой точки больше, чем $(r_{\text{th}}+1)^{2}/r_{\text{th}}$, то ключевая точка неудачно расположена, а потому отбрасывается. Новый подход использует $r_{\text{th}}=10$.

Этот шаг подавления ответа рёбер является переносом соответствующего подхода в оператор Харриса для обнаружения углов. Разница в том, что мера для порога вычисляется из матрицы Гессе, а не из матрицы вторых моментов.

Назначение ориентации

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

В первую очередь берётся размытое по Гауссу изображение $L\left(x,y,\sigma \right)$ в ключевых точках с масштабом $\sigma$, так что все вычисления осуществляются в масштабно-инвариантной манере. Для изображения $L\left(x,y\right)$ с масштабом $\sigma$ предварительно вычисляются на основе разности пикселей величина градиента $m\left(x,y\right)$ и ориентация $\theta \left(x,y\right)$

$m\left(x,y\right)={\sqrt {\left(L\left(x+1,y\right)-L\left(x-1,y\right)\right)^{2}+\left(L\left(x,y+1\right)-L\left(x,y-1\right)\right)^{2}}}$

$\theta \left(x,y\right)=\mathrm {atan2} \left(L\left(x,y+1\right)-L\left(x,y-1\right),L\left(x+1,y\right)-L\left(x-1,y\right)\right)$

Вычисление величины и направления для градиента делается для каждого пикселя в окрестности ключевой точки в размытом по Гауссу изображении L. Формируется гистограмма направлений с 36 областями, каждая из которых покрывает 10 градусов. Каждая точка в окружающем окне добавляется в область гистограммы, взвешенная по величине градиента и по гауссово-взвешенному круговому окну с $\sigma$, которое в 1,5 раза больше масштаба ключевой точки. Пики в этой гистограмме соответствуют доминирующим направлениям. Как только гистограмма заполнена, направления, соответствующие самым высоким пикам и локальным пикам, которые в пределах 80 % от самых высоких пиков, назначаются ключевой точке. В случае назначения нескольких направлений создаётся дополнительная ключевая точка, имеющая то же местоположение и масштаб, что и оригинальная точка для каждого дополнительного направления.

Дескриптор ключевой точки

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

В первую очередь создаётся набор гистограмм направлений на 4×4 соседних пикселях с 8 областями в каждой. Эти гистограммы вычисляются из значений величины и ориентации элементов в области 16×16 вокруг ключевой точки, так что каждая гистограмма содержит элементы из 4×4 подобласти исходной области соседства. Величины далее взвешиваются функцией Гаусса с $\sigma$, равной половине ширины окна дескриптора. Дескриптор затем становится вектором всех значений этих гистограмм. Поскольку имеется 4 × 4=16 гистограмм с 8 областями в каждой, вектор имеет 128 элементов. Этот вектор нормализуется до единичной длины, чтобы обеспечить инвариантность аффинным изменениям в освещении. Чтобы сократить эффект нелинейного освещения, применяется порог величиной 0,2 и вектор снова нормализуется. Процесс применения порога может улучшить результаты сопоставления, даже если эффекты нелинейного освещения отсутствуют. Значение порога 0,2 выбрано эмпирически и замена фиксированного порога на целенаправленно вычисленный, может улучшить результаты сопоставления.

Хотя размерность дескриптора (то есть 128) кажется высокой, дескрипторы с меньшей размерностью не работают столь хорошо, а вычислительные затраты остаются низкими, поскольку для поиска ближайшего соседа применяется метод приближённого BBF (см. ниже). Более длинные дескрипторы давали бы лучшие результаты, но не на много, и есть опасность увеличения чувствительности к искажениям и наложению (преградам). Также было показано, что точность сопоставления признаков выше 50 % для изменения точки обзора до 50 градусов. Поэтому SIFT-дескрипторы инвариантны малым аффинным изменениям. Чтобы проверить различимость SIFT-дескрипторов, измеряется также точность соответствия относительно различного количества ключевых точек в тестовой базе данных и было показано, что точность соответствия уменьшается лишь слегка для больших баз данных, что свидетельствует, что SIFT-признаки высоко различимы.

Сравнение SIFT-признаков с другими локальными признаками

Проводились интенсивные исследования по оценке эффективности различных локальных дескрипторов, включая SIFT. Основные результаты приведены ниже:

• SIFT и (похожие на SIFT) GLOH признаки (англ. Gradient Location and Orientation Histogram) показывают наивысшую точность соответствия для аффинного преобразования в 50 градусов. После этого предела результаты преобразования становятся недостоверными.
• Различимость дескрипторов измеряется суммированием собственных значений дескрипторов, полученных методом главных компонент для дескрипторов, нормализованных по дисперсии. Это соответствует величине дисперсии, соответствующей разным дескрипторам, а потому их различению. Признаки PCA-SIFT (Метод главных компонент, применённый к дескрипторам SIFT), GLOH и SIFT дают наивысшие значения.
• Основанные на SIFT дескрипторы превосходят другие современные локальные дескрипторы как для текстурированных, так и структурных сценах, при этом эффективность для текстурных сцен выше.
• Для изменения масштаба в 2-2,5 раза и вращения образа в пределах от 30 до 45 градусов SIFT и основанные на SIFT дескрипторы снова превосходят другие современные локальные дескрипторы для текстурированных и структурных сцен.
• Размытие (нечёткость) воздействует на все локальные дескрипторы, особенно на те, которые основаны на границах (рёбрах), такие как алгоритм «shape context» (контекст фигуры), поскольку рёбра исчезают в случае сильного размывания границ. Но GLOH, PCA-SIFT и SIFT продолжают работать лучше, чем остальные. Это верно также для случая изменений освещения.

Проведённые испытания сильно подсказывают, что основанные на SIFT дескрипторы наиболее устойчивы и различимы, а потому наиболее рекомендуемы для сопоставления признаков. Тем не менее, недавно разработанные дескрипторы признаков, такие как SURF, в этих испытаниях не исследовались.

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

Показатель согласования изображения SIFT-дескрипторами может быть улучшен в смысле достижения более высоких показателей эффективности и более низких показателей 1-точности^{[прояснить]} (англ. 1-precision scores) путём замены масштабируемого пространственного экстремума оператора разности гауссианов в исходном SIFT на экстремум определителя гессиана в масштабируемом пространстве, или рассматривая более общее семейство обобщённых особых точек масштабируемого пространства .

В недавнем времени был предложен слегка изменённый вариант дескриптора, использующий неоднородную гистограммную решётку, который существенно улучшает качество. Вместо использования решётки 4×4 областей гистограммы все области расширяются к центру признака. Это улучшает устойчивость дескрипторов к изменению масштаба.

Дескриптор SIFT-Rank, как было показано, улучшает характеристики стандартного SIFT-дескриптора для аффинного сопоставления признаков. SIFT-Rank дескриптор образуется из стандартного SIFT-дескриптора путём присвоения каждой области гистограммы ранга в отсортированном массиве областей. Евклидово расстояние между SIFT-Rank дескрипторами инвариантно относительно произвольных монотонных изменений значений гистограммы и связано с коэффициентами корреляции рангов Спирмэна.

Приложения

Распознавание объектов с помощью SIFT-признаков

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

• Во-первых, SIFT-признаки получаются из входного изображения с помощью алгоритма, описанного выше.
• Эти признаки сопоставляются с SIFT-признаками из базы данных, полученными из тренировочных изображений. Это сопоставление признаков осуществляется с помощью подхода, основанного на евклидовом расстоянии до ближайшего соседа. Для увеличения устойчивости сопоставление отбрасывается для ключевых точек, для которых отношение расстояния до ближайшего соседа к расстоянию до второго ближайшего соседа больше 0,8. Это отбрасывает много ложных соответствий, возникающих из фоновых мешающих изображений. Наконец, во избежание затратного поиска, нужного для нахождения ближайшего соседа по евклидову расстоянию, используется приближённый алгоритм с названием «best-bin-first». Это быстрый метод, возвращающий с высокой вероятностью ближайшего соседа, и он может ускорить процесс поиска в 1000 раз, в то время как нахождение ближайшего соседа занимает 95 % времени.
• Хотя тест отношения расстояний, описанный выше, отбрасывает много ложных соответствий, возникающих из фоновых мешающих изображений, у нас остаются соответствия, принадлежащие другим объектам. Поэтому, чтобы увеличить надёжность идентификации объекта, мы хотим собрать в кластеры признаки, которые принадлежат тому же объекту, и отбросить соответствия, которые останутся после процесса кластеризации. Это делается с помощью преобразования Хафа. Это идентифицирует кластеры признаков, которые голосуют за некоторое положение объекта. Когда кластеры признаков найдены с голосами за некоторое положение объекта, вероятность правильной интерпретации будет много выше, чем для отдельного признака. Каждая ключевая точка голосует за набор положений объекта, если они согласуются с местоположением ключевой точки, масштабом и ориентацией. Области, которые аккумулируют по меньшей мере 3 голоса, считаются кандидатами для сопоставления объект/позиция.
• Для каждого кластерного кандидата получаем решение методом наименьших квадратов для лучших оценочных параметров аффинной проекции, связывающих тренировочые изображения с входным изображением. Если проекция ключевой точки через эти параметры лежит в половине интервала ошибки, который использовался для параметров в областях преобразования Хафа, соответствие ключевой точки сохраняется. Если остаётся менее 3 точек после отбрасывания выбросов для областей, соответствие для объекта отвергается. Подгонка с помощью наименьших квадратов повторяется, пока удаётся что-то отбросить. Это лучше работает для распознавания плоских объектов, но не для распознавания 3D-объектов, поскольку аффинная модель становится недостоверной для 3D-объектов.
• В статье Сирмачека и Унсалана предлагается новый подход для использования SIFT-дескрипторов для выделения нескольких объектов. Предложенный подход к обнаружению нескольких объектов проверялся на аэроснимках и спутниковых снимках.

SIFT-признаки могут, в принципе, быть применены к любой задаче, в которой требуется определение места соответствия изображений. Работа может быть осуществлена на приложениях, таких как распознавание конкретных категорий объектов в 2D-изображениях, реконструкция 3D-объектов, отслеживание движений и сегментации, местоположения робота, склейка панорамных изображений и эпиполярной калибровки. Некоторые из этих приложений обсуждаются более детально ниже.

Местоположение робота и карты

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

Сшивка панорамы

Соответствие SIFT-признаков может быть использовано для сшивки изображений для полностью автоматизированного построения панорамы из непанорамных кадров. SIFT-признаки, выделенные из входных изображений, сопоставляются друг с другом для поиска k ближайших соседей в каждом изображении. Эти соответствия затем используются для поиска m кандидатов соответствия изображений для каждого изображения. Затем вычисляются гомографии между парами изображений, используя RANSAC (англ. Random sample consensus) и используется вероятностная модель для проверки. Поскольку не существует никаких ограничений на входные изображения, применяется поиск по графу для связных компонент соответствия изображений, так что каждая связная компонента будет соответствовать панораме. Наконец, для каждой связной компоненты выполняется блочное уравнивание для решения параметров камеры, и панорама обрабатывается с помощью широкодиапазонного смешивания (англ. multi-band blending). Ввиду подхода к распознаванию объектов для сшивки панорамы, навеянного методом SIFT, результирующая система нечувствительна к порядку, ориентации, масштабу и освещённости изображений. Входные изображения могут содержать несколько панорам и шумы изображений (некоторые из которых могут даже не быть частями составного изображения).

Моделирование 3D-сцен, распознавание и трассировка

Это приложение использует SIFT-признаки для распознавания трёхмерного объекта и трёхмерного моделирования в контексте дополненной реальности, в которой создаваемые искусственные объекты в точной позе накладываются на реальные изображения. SIFT-соответствие определяется для нескольких 2D-изображений сцены или объекта, полученных с различных углов. Это используется с блочным уравниванием для построения разреженной 3D-модели рассматриваемой сцены и одновременно восстанавливаются позиции камеры и параметры калибровки. Затем определяется позиция, ориентация и размер виртуального объекта относительно координат кадра рассматриваемой модели. Для онлайнового позиционного трекинга признаки SIFT выделяются из текущего видеокадра и сопоставляются с уже вычисленными признаками, что даёт набор соответствий 2D-к-3D. Эти соответствия затем используются для вычисления текущей позиции камеры для виртуальной проекции и конечной обработки. Техника регуляризации используется для сокращения дрожания в виртуальной проекции. Были также реализованы 3D-расширения SIFT для распознавания и выделения настоящих трёхмерных объектов.

3D SIFT-подобные дескрипторы для распознавания действий человека

Изучались расширения SIFT-дескриптора до 2+1-мерных пространственно-временных данных в контексте распознавания действий человека в видео. Создание локальных зависящих от положения гистограмм в алгоритме 2D SIFT расширяется с двухмерного до трёхмерного, чтобы описать признаки SIFT пространственно-временной области. Для приложения к распознаванию действий человека в видео тренировочные видео выполняются либо с особых пространственно-временных точек, либо в случайном месте, времени и масштабе. Пространственно-временные области вокруг этих особых точек затем описываются с помощью 3D SIFT-дескриптора. Эти дескрипторы затем собираются в виде пространственно-временной модели «мешок слов». 3D SIFT-дескрипторы, извлечённые из тестовых роликов, сопоставляются этим словам для классификации действий человека.

Авторы утверждают, что их 3D SIFT-дескриптор показывает существенно более лучшие результаты, чем другие подходы, такие как простые 2D SIFT-дескрипторы и значение градиента.

Анализ человеческого мозга в трёхмерных изображениях Магнитно-резонансной томографии

Техника морфометрии, основанной на признаках, (англ. Feature-based Morphometry, FBM) использует экстремумы в разности гауссового пространства масшабирования для анализа и классификации 3D Магнитно-резонансных изображений (англ. magnetic resonance images, MRIs) человеческого мозга. FBM моделирует изображение вероятностно как коллаж независимых признаков, обусловленных геометрией изображения и группами меток, например здоровые объекты и объекты, соответствующие болезни Альцгеймера. Признаки сначала извлекаются в отдельные изображения из четырёхмерной разности гауссового пространства масшабирования, затем моделируются в понятиях их проявления, геометрии и статистики совместного выпадения событий в группе по множеству изображений. FBM была проверена в анализе болезни Альцгеймера с помощью набора ~200 объёмных снимков (MRI) человеческого мозга, автоматически определяя установленные индикаторы болезни Альцгеймера в мозге и классифицируя неострые болезни в новых изображениях с показателем 80 %.

Конкурирующие методы

Конкурирующие методы для распознавания объектов инвариантно по масштабу при помехах и частичном перекрытии следующие.

RIFT: Инвариантное относительно вращения обобщение SIFT (англ. rotation-invariant generalization of SIFT). Дескриптор RIFT строится с помощью круговых нормализованных кусочков, разделённых на концентрические кольца равной ширины, и внутри каждого кольца вычисляется гистограмма направления градиента. Чтобы получить инвариантность относительно вращения, ориентация измеряется в каждой точке относительно направления от центра.

G-RIF: Обобщённые Устойчивые Инвариантные Признаки (англ. Generalized Robust Invariant Feature) — это общий дескриптор контекста, который кодирует ориентацию рёбер, плотность рёбер и информацию о цвете в едином ключе, комбинируя информацию восприятия с пространственным кодированием. Схема распознавания объекта для оценки моделей объекта использует контекст соседства, основываясь на голосовании.

«SURF»: Устойчивые Ускоренные Признаки (англ. Speeded Up Robust Features) — это высокоэффективные детекторы / дескрипторы инвариантные по масштабу и вращению особой точки, для которых утверждается, что они приближаются или даже превосходят предварительно предложенные схемы по воспроизводимости, отчётливости и надёжности. SURF опирается на полные изображения для свёртки для сокращения времени вычисления и основан на силе лидирующих существующих детекторов и дескрипторов (используя быструю меру, основанную на матрице Гессе, для детекторов и основанных на вероятностных распределениях дескрипторах). Он описывает распределение ответов вейвлета Хаара среди соседей особой точки. Для ускорения используются полные изображения и используются только 64-мерные вектора признаков для сокращения времени вычисления и сопоставления. Шаг индексирования основан на знаке лапласиана, что увеличивает скорость сопоставления и устойчивость дескриптора.

PCA-SIFT и GLOH являются вариантами SIFT. PCA-SIFT-дескриптор — это вектор градиентов изображения в направлениях x и y, вычисленный в поддерживаемой области. Область градиента разбита на 39×39 мест, поэтому размерность вектора равна 3042. Размерность сокращается до 36 методом главных компонент. Гистограмма градиентов местоположения-ориентации (GLOH) является расширением SIFT-дескриптора, и разрабатывался для увеличения его устойчивости и различимости. SIFT-дескриптор вычисляется в логарифмических полярных координатах решётки положения с тремя областями в радиальных направлениях (радиус устанавливается в 6, 11 и 15) и 8 в угловых направлениях, что даёт 17 областей. Центральная область не разделяется на угловые направления. Направления градиента квантуются на 16 областей, что даёт гистограмму с 272 областями. Размер этого дескриптора сокращается методом главных компонент. Ковариационная матрица для метода главных компонент оценивается на кусках, собранных из разных изображений. 128 наибольших собственных векторов используются для описания.

Gauss-SIFT является чистым дескриптором изображения, определённым путём осуществления измерения всех изображений лежащего в основе дескриптора SIFT с помощью производной гауссиана, а не аппроксимации производной в пирамиде изображений, как это делается в стандартном SIFT. При таком подходе эффект дискретизации пространства и масштаба может быть сокращён до минимума, что, потенциально, даст более точные дескрипторы изображений. У Линдеберга такие Gauss-SIFT дескрипторы изображений комбинировались с набором обобщённых масштабных пространств особых точек, включая лапласиан гауссиана, определитель гессиана, четыре новых меры признаков беззнакового и знакового гессиана, а также особые точки Харриса — Лапласа и Ши — Томаса. В интенсивном экспериментальном прогоне на базе данных афиш, содержащей несколько преобразований 12 афиш по изменению масштаба до 6-кратного и направления обзора вплоть до угла в 45 градусов, было показано, что существенное увеличение эффективности обработки изображений (более высокие показатели эффективности и более низкие показателей 1-точности) может быть получено путём замены лапласиана гауссиана особых точек на определитель гессиана особых точек. Поскольку разность гауссианов особых точек предполагает численную аппроксимацию лапласиана гауссиана особых точек, это показывает, что возможно существенное увеличение производительности сопоставления путём замены разности гессианов особых точек в SIFT на определитель гессиана особых точек. Дополнительное увеличение производительности может быть далее получено при рассмотрении меры силы признака беззнакового гессиана (англ. unsigned Hessian feature strength measure) $D_{1}L=\operatorname {det} HL-k\,\operatorname {trace} ^{2}HL\,{\mbox{if}}\operatorname {det} HL-k\,\operatorname {trace} ^{2}HL>0$ или 0 в противном случае. Численное сравнение между Gauss-SIFT дескриптором и соответствующим Gauss-SURF дескриптором также показало, что Gauss-SIFT в общем случае работает существенно лучше, чем Gauss-SURF для большого числа различных детекторов масштабных пространств особых точек. Изучение, таким образом, показывает, что отбрасывание эффекта дискретизации дескриптора изображения в SIFT существенно лучше, чем дескриптор изображения в SURF, тем не менее детектор особых точек в SURF, который можно рассматривать как численное приближение к экстремуму в масштабном пространстве определителя гессиана, существенно лучше, чем детектор особых точек в SIFT.

Вагнер с сотрудниками разработал два алгоритма распознавания объектов специально приспособленных к ограничениям существующих мобильных телефонов. В отличие от классического подхода, SIFT Вагнер и др. используют алгоритм обнаружения углов FAST для обнаружения признаков. Алгоритм также отличается оффлайновой фазой подготовки, где признаки создаются на разных уровнях масштаба, и онлайновой фазой, где признаки создаются только для фиксированного уровня масштаба изображения камеры телефона. Кроме того, признаки создаются только из фиксированных областей размером 15×15 пикселей и создаётся только 36-мерный SIFT дескриптор. Подход был в дальнейшем расширен путём интеграции с масштабируемым деревом слов (англ. Scalable Vocabulary Tree). Это позволяет эффективное распознавание большого числа объектов мобильным телефоном. Подход ограничен главным образом количеством доступной оперативной памяти.

KAZE и A-KAZE (Признаки KAZE и Форсированные признаки Kaze) является новым методом 2D-обнаружения и описания признаков, который работает лучше, чем SIFT и SURF. Он получил широкую популярность вследствие того, что распространяется свободно и имеет открытые исходные коды. Алгоритм также не запатентован. KAZE создали Пабло Ф. Алькантарилья, Эдриен Бартоли и Эндрю Дж. Дэвисон.

См. также

• Свёрточная нейронная сеть
• Сшивка изображений
• Пространство масшабирования
• SLAM
• Структура по набору изображений

Ссылки

• Scale-Invariant Feature Transform (SIFT) in Scholarpedia
• реализация SIFT Роба Гесса accessed 21 Nov 2012
• The Invariant Relations of 3D to 2D Projection of Point Sets, Journal of Pattern Recognition Research(JPRR) Архивная копия от 8 сентября 2008 на Wayback Machine, Vol. 3, No 1, 2008.
• Lowe, D. G., «Distinctive Image Features from Scale-Invariant Keypoints», International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.
• Mikolajczyk, K., and Schmid, C., «A performance evaluation of local descriptors», IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 27, pp 1615—1630, 2005.
• PCA-SIFT: A More Distinctive Representation for Local Image Descriptors
• Lazebnik, S., Schmid, C., and Ponce, J., Semi-Local Affine Parts for Object Recognition, BMVC, 2004.
• ASIFT (Affine SIFT): large viewpoint matching with SIFT, with source code and online demonstration
• VLFeat, an open source computer vision library in C (with a MEX interface to MATLAB), включая реализацию SIFT
• LIP-VIREO, A toolkit для извлечения признака ключевой точки (бинарники для Windows, Linux и SunOS), включая реализацию SIFT
• (Parallel) SIFT in C#, SIFT algorithm in C# using Emgu CV and also a modified parallel version of the algorithm.
• DoH & LoG + affine, Blob detector adapted from a SIFT toolbox
• A simple step by step guide to SIFT
• SIFT for multiple object detection
• «The Anatomy of the SIFT Method» in Image Processing On Line, a detailed study of every step of the algorithm with an open source реализация and a web demo to try different parameters
• ezSIFT: an easy-to-use standalone SIFT реализация на C/C++. A self-contained open-source SIFT реализация which does not require other libraries.
• 3D SIFT реализация: detection and matching in volumetric images.