Масштабно-инвариантное преобразование функции - Scale-invariant feature transform

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

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

Обзор

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

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

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

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

Основные этапы

Обнаружение масштабно-инвариантных функций

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

Сопоставление функций и индексация

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

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

Идентификация кластера голосованием с преобразованием Хафа

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

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

Проверка модели методом наименьших квадратов

Затем каждый идентифицированный кластер подвергается процедуре проверки, в которой выполняется линейное решение методом наименьших квадратов для параметров аффинного преобразования, связывающего модель с изображением. Аффинное преобразование точки [xy] ^T модели в точку изображения [uv] ^T можно записать следующим образом.

${\ displaystyle {\ begin {bmatrix} и \\ 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. Чтобы найти параметры преобразования, приведенное выше уравнение можно переписать, чтобы собрать неизвестные в вектор-столбец.

${\ displaystyle {\ 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 совпадения. Мы можем записать эту линейную систему в виде

${\ Displaystyle А {\ шляпа {\ mathbf {x}}} \ приблизительно \ mathbf {b},}$

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

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

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

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

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

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

Обнаружение выбросов

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

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

Функции

Обнаружение и описание локальных особенностей изображения может помочь в распознавании объектов. Функции SIFT являются локальными и основаны на внешнем виде объекта в определенных точках интереса и не зависят от масштаба и поворота изображения. Они также устойчивы к изменениям освещения, шуму и незначительным изменениям точки обзора. В дополнение к этим свойствам они очень различимы, относительно легко извлекаются и позволяют правильно идентифицировать объект с низкой вероятностью несоответствия. Их относительно легко сопоставить с (большой) базой данных локальных объектов, но, тем не менее, высокая размерность может быть проблемой, и, как правило, используются вероятностные алгоритмы, такие как деревья kd с поиском по первому интервалу. Описание объекта с помощью набора функций SIFT также устойчиво к частичному перекрытию; всего 3 функции SIFT от объекта достаточно, чтобы вычислить его местоположение и позу. Распознавание может выполняться в режиме, близком к реальному времени, по крайней мере, для небольших баз данных и на современном компьютерном оборудовании.

Алгоритм

Обнаружение экстремумов в масштабном пространстве

Мы начинаем с обнаружения точек интереса, которые в рамках SIFT называются ключевыми точками . Изображение свернуто с помощью фильтров Гаусса в разных масштабах, а затем снимается разница последовательных изображений с размытием по Гауссу. Затем ключевые точки берутся как максимумы / минимумы разности гауссианов (DoG), которые происходят в нескольких масштабах. В частности, образ DoG задается ${\ Displaystyle D \ влево (х, у, \ сигма \ вправо)}$

${\ displaystyle D \ left (x, y, \ sigma \ right) = L \ left (x, y, k_ {i} \ sigma \ right) -L \ left (x, y, k_ {j} \ sigma \ Правильно)}$,

где - свертка исходного изображения с размытием по Гауссу в масштабе , т. е.${\ Displaystyle L \ влево (х, у, к \ сигма \ вправо)}$${\ Displaystyle I \ влево (х, у \ вправо)}$ ${\ Displaystyle G \ влево (х, у, к \ сигма \ вправо)}$${\ displaystyle k \ sigma}$

${\ Displaystyle L \ влево (х, у, к \ сигма \ вправо) = г \ влево (х, у, к \ сигма \ вправо) * я \ влево (х, у \ вправо)}$

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

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

Этот этап обнаружения Keypoint является разновидностью одного из обнаружения блобы методов , разработанных Линдебергом путем определения масштаба пространства экстремумов шкал нормализованы лапласианом; то есть обнаружение точек, которые являются локальными экстремумами как в пространстве, так и в масштабе, в дискретном случае путем сравнения с ближайшими 26 соседями в дискретизированном объеме пространства масштаба. Оператор разности гауссианов можно рассматривать как приближение к лапласиану, при этом неявная нормализация в пирамиде также представляет собой дискретное приближение нормированного к масштабу лапласиана. Еще одна реализация в реальном времени экстремумов масштабно-пространственного оператора Лапласа была представлена ​​Линдебергом и Бретцнером на основе представления гибридной пирамиды, которая использовалась для взаимодействия человека с компьютером путем распознавания жестов в реальном времени в Bretzner et al. (2002).

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

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

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

Интерполяция ближайших данных для точного определения местоположения

Во-первых, для каждой ключевой точки-кандидата используется интерполяция ближайших данных для точного определения ее положения. Первоначальный подход заключался в том, чтобы просто расположить каждую ключевую точку в месте и масштабе ключевой точки-кандидата. Новый подход вычисляет интерполированное положение экстремума, что существенно улучшает согласование и стабильность. Интерполяция выполняется с использованием квадратичного разложения Тейлора функции разности гауссовского масштабного пространства с ключевой точкой-кандидатом в качестве исходной точки. Это разложение Тейлора определяется следующим образом: ${\ Displaystyle D \ влево (х, у, \ сигма \ вправо)}$

${\ Displaystyle D ({\ textbf {x}}) = D + {\ frac {\ partial D} {\ partial {\ textbf {x}}}} ^ {T} {\ textbf {x}} + {\ frac {1} {2}} {\ textbf {x}} ^ {T} {\ frac {\ partial ^ {2} D} {\ partial {\ textbf {x}} ^ {2}}} {\ textbf { Икс}}}$

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

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

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

Устранение крайних откликов

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

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

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

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

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

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

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

Сначала берется сглаженное по Гауссу изображение в масштабе ключевой точки, так что все вычисления выполняются без учета масштаба . Для образца изображения в масштабе величина градиента , и ориентация, предварительно вычисляются с использованием разностей пикселей: ${\ Displaystyle L \ влево (х, у, \ сигма \ вправо)}$${\ displaystyle \ sigma}$${\ Displaystyle L \ влево (х, у \ вправо)}$${\ displaystyle \ sigma}$${\ Displaystyle м \ влево (х, у \ вправо)}$${\ Displaystyle \ тета \ влево (х, у \ вправо)}$

${\ Displaystyle м \ влево (х, у \ вправо) = {\ sqrt {\ влево (L \ влево (х + 1, у \ вправо) -L \ влево (х-1, у \ вправо) \ вправо) ^ {2} + \ left (L \ left (x, y + 1 \ right) -L \ left (x, y-1 \ right) \ right) ^ {2}}}}$

${\ Displaystyle \ тета \ влево (х, у \ вправо) = \ mathrm {atan2} \ влево (L \ влево (х, у + 1 \ вправо) -L \ влево (х, у-1 \ вправо), L \ left (x + 1, y \ right) -L \ left (x-1, y \ right) \ right)}$

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

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

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

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

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

Сравнение функций SIFT с другими локальными функциями

Было проведено обширное исследование по оценке производительности различных локальных дескрипторов, включая SIFT, с использованием ряда детекторов. Ниже приведены основные результаты:

• SIFT и SIFT-подобные функции GLOH демонстрируют наивысшую точность согласования (скорость отзыва) для аффинного преобразования 50 градусов. После этого предела преобразования результаты становятся ненадежными.
• Отличительность дескрипторов измеряется суммированием собственных значений дескрипторов, полученных анализом главных компонентов дескрипторов, нормализованных по их дисперсии. Это соответствует размеру отклонения, улавливаемого разными дескрипторами, следовательно, их различимости. PCA-SIFT (анализ основных компонентов, применяемый к дескрипторам SIFT), функции GLOH и SIFT дают самые высокие значения.
• Дескрипторы на основе SIFT превосходят другие современные локальные дескрипторы как на текстурированных, так и на структурированных сценах, с большей разницей в производительности на текстурированной сцене.
• Для изменений масштаба в диапазоне 2–2,5 и поворота изображения в диапазоне от 30 до 45 градусов дескрипторы на основе SIFT и SIFT снова превосходят другие современные локальные дескрипторы как с текстурированным, так и со структурированным содержимым сцены.
• Введение размытия влияет на все локальные дескрипторы, особенно те, которые основаны на краях, например в контексте формы , потому что края исчезают в случае сильного размытия. Но GLOH, PCA-SIFT и SIFT по-прежнему работали лучше, чем другие. Это также верно для оценки в случае изменения освещения.

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

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

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

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

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

Приложения

Распознавание объектов с использованием функций SIFT

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

• Во-первых, признаки SIFT получаются из входного изображения с использованием описанного выше алгоритма.
• Эти функции сопоставляются с базой данных функций SIFT, полученной из обучающих изображений. Это сопоставление характеристик выполняется с помощью подхода ближайшего соседа на основе евклидова расстояния. Чтобы повысить надежность, совпадения отклоняются для тех ключевых точек, для которых отношение расстояния до ближайшего соседа к расстоянию до второго ближайшего соседа больше 0,8. Это устраняет многие ложные совпадения, возникающие из-за беспорядка на заднем фоне. Наконец, чтобы избежать дорогостоящего поиска, необходимого для нахождения ближайшего соседа на основе евклидова расстояния, используется приближенный алгоритм, называемый алгоритмом поиска наилучшего бункера. Это быстрый метод возврата ближайшего соседа с высокой вероятностью, который может дать ускорение в 1000 раз при нахождении ближайшего соседа (представляющего интерес) в 95% случаев.
• Хотя описанный выше тест отношения расстояний отбрасывает многие ложные совпадения, возникающие из-за фонового шума, у нас все еще есть совпадения, которые принадлежат разным объектам. Поэтому, чтобы повысить надежность идентификации объекта, мы хотим кластеризовать те функции, которые принадлежат одному и тому же объекту, и отклонять совпадения, которые не учитываются в процессе кластеризации. Это делается с помощью преобразования Хафа . Это позволит идентифицировать кластеры функций, которые голосуют за одну и ту же позу объекта. Когда обнаруживается, что кластеры функций голосуют за одну и ту же позу объекта, вероятность того, что интерпретация будет правильной, намного выше, чем для любой отдельной функции. Каждая ключевая точка голосует за набор поз объекта, соответствующих местоположению, масштабу и ориентации ключевой точки. Бункеры, которые набирают не менее 3 голосов, идентифицируются как подходящие объекты / позы-кандидаты.
• Для каждого кластера кандидатов получается решение методом наименьших квадратов для наилучших оцененных параметров аффинной проекции, связывающих обучающее изображение с входным изображением. Если проекция ключевой точки через эти параметры находится в пределах половины диапазона ошибок, который использовался для параметров в ячейках преобразования Хафа, совпадение ключевой точки сохраняется. Если после отбрасывания выбросов для ячейки остается менее 3 точек, то соответствие объекта отклоняется. Аппроксимация методом наименьших квадратов повторяется до тех пор, пока больше не будет отбраковок. Это работает лучше для распознавания плоских поверхностей, чем для распознавания 3D-объектов, поскольку аффинная модель больше не точна для 3D-объектов.
• В этом журнале авторы предложили новый подход к использованию дескрипторов SIFT для обнаружения множества объектов. Предлагаемый подход к обнаружению множественных объектов апробирован на аэрофотоснимках и спутниковых снимках.

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

Локализация и картография роботов

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

Панорамное сшивание

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

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

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

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

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

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

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

Метод морфометрии на основе признаков (FBM) использует экстремумы в разнице гауссовского масштабного пространства для анализа и классификации трехмерных магнитно-резонансных изображений (МРТ) человеческого мозга. FBM моделирует изображение вероятностно как коллаж из независимых элементов, зависящих от геометрии изображения и групповых меток, например здоровых субъектов и субъектов с болезнью Альцгеймера (AD). Элементы сначала извлекаются в отдельных изображениях из четырехмерной разницы гауссовского масштабного пространства, а затем моделируются с точки зрения их внешнего вида, геометрии и групповой статистики совместной встречаемости в наборе изображений. FBM был подтвержден при анализе AD с использованием набора из ~ 200 объемных МРТ головного мозга человека, автоматически определяющих установленные индикаторы AD в головном мозге и классифицирующих легкую AD на новых изображениях со скоростью 80%.

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

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

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

RootSIFT - это вариант SIFT, который изменяет нормализацию дескриптора. Поскольку дескрипторы SIFT представляют собой гистограммы (и как таковые распределения вероятностей ), использование евклидова расстояния для определения их сходства не является естественным выбором. Сравнение таких дескрипторов с использованием показателей сходства, адаптированных к распределению вероятностей, таких как коэффициент Бхаттачарьи (также известный как ядро ​​Хеллингера), оказывается более полезным. Для этого сначала нормализуется исходный нормализованный дескриптор и вычисляется квадратный корень для каждого элемента, а затем выполняется перенормировка. После этих алгебраических манипуляций дескрипторы RootSIFT можно нормально сравнивать с использованием евклидова расстояния, что эквивалентно использованию ядра Хеллингера на исходных дескрипторах SIFT. Эта схема нормализации, называемая «L1-sqrt», была ранее введена для блочной нормализации характеристик HOG, чей вариант дескриптора прямоугольной компоновки блоков (R-HOG) концептуально аналогичен дескриптору SIFT. ${\ displaystyle \ ell ^ {2}}$${\ displaystyle \ ell ^ {1}}$${\ displaystyle \ ell ^ {2}}$

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

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

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

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

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

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

Смотрите также

• Сверточная нейронная сеть
• Сшивание изображений
• Масштабировать пространство
• Реализация масштабного пространства
• Одновременная локализация и картографирование
• Структура из движения

использованная литература

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

" Связанные исследования:

• Инвариантные отношения трехмерной проекции к двумерной проекции наборов точек, Журнал исследований распознавания образов (JPRR) , Vol. 3, № 1, 2008 г.
• Лоу, Д.Г., «Отличительные особенности изображения от масштабно-инвариантных ключевых точек», Международный журнал компьютерного зрения, 60, 2, стр. 91-110, 2004.
• Миколайчик, К., и Шмид, К., «Оценка производительности локальных дескрипторов», IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 27, pp 1615-1630, 2005.
• PCA-SIFT: более четкое представление дескрипторов локальных изображений
• Лазебник С. , Шмид К. , Понсе Дж. Полулокальные аффинные части для распознавания объектов // BMVC, 2004.

Учебники:

• Масштабно-инвариантное преобразование признаков (SIFT) в Scholarpedia
• Простое пошаговое руководство по SIFT
• SIFT для обнаружения нескольких объектов
• « Анатомия метода SIFT » в разделе «Обработка изображений в режиме онлайн», подробное изучение каждого шага алгоритма с реализацией с открытым исходным кодом и веб-демонстрация для опробования различных параметров.

Реализации:

• Реализация SIFT Робом Хессом, доступ 21 ноября 2012 г.
• ASIFT (Affine SIFT) : соответствие большой точки обзора с SIFT, с исходным кодом и онлайн-демонстрацией
• VLFeat , библиотека компьютерного зрения с открытым исходным кодом на C (с интерфейсом MEX для MATLAB), включая реализацию SIFT
• LIP-VIREO , набор инструментов для извлечения ключевых точек (двоичные файлы для Windows, Linux и SunOS), включая реализацию SIFT
• (Параллельный) SIFT в C # , алгоритм SIFT в C # с использованием Emgu CV, а также модифицированная параллельная версия алгоритма.
• DoH & LoG + affine , детектор Blob, адаптированный из набора инструментов SIFT
• ezSIFT: простая в использовании автономная реализация SIFT на C / C ++ . Автономная реализация SIFT с открытым исходным кодом, не требующая других библиотек.
• Реализация 3D SIFT: обнаружение и сопоставление в объемных изображениях.