Масштабно-инвариантное преобразование признаков

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

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

Обзор [ править ]

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

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

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

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

Дескриптор SIFT основан на измерениях изображения в терминах воспринимающих полей ^{[4] [5] [6] [7],} по которым инвариантные в локальном масштабе опорные кадры ^{[8] [9]} устанавливаются путем выбора локального масштаба . ^{[10] [11] [9]} Общее теоретическое объяснение этого дается в статье Scholarpedia о SIFT. ^[12]

Основные этапы [ править ]

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

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

Сопоставление и индексирование функций [ править ]

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

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

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

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

Каждая из ключевых точек SIFT определяет 2D-местоположение, масштаб и ориентацию, и каждая сопоставленная ключевая точка в базе данных имеет запись своих параметров относительно обучающего образа, в котором она была найдена. Преобразование подобия, подразумеваемое этими 4 параметрами, является только приближением к полному пространству поз с 6 степенями свободы для трехмерного объекта, а также не учитывает какие-либо нежесткие деформации. Следовательно, Лоу ^[2]использовали широкую ячейку размером 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 A{\hat {\mathbf {x} }}\approx \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 очков , то совпадение отклоняется. Кроме того, фаза согласования сверху вниз используется для добавления любых дополнительных совпадений, которые согласуются с прогнозируемым положением модели, которое могло быть пропущено из преобразования Хафа. bin из-за приближения преобразования подобия или других ошибок.

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

Особенности [ править ]

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

Алгоритм [ править ]

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

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

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

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

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

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

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

Этот этап обнаружения Keypoint является разновидностью одного из обнаружения блобы методов , разработанных Линдебергом путем определения масштаба пространства экстремумов шкал нормализованы лапласианом; ^{[10] [11],} то есть обнаружение точек, которые являются локальными экстремумами как в пространстве, так и в масштабе, в дискретном случае путем сравнения с ближайшими 26 соседями в дискретизированном объеме пространства масштаба. Различие оператора Гаусса можно рассматривать как приближение к лапласиану, при этом неявная нормализация в пирамиде также представляет собой дискретное приближение нормированного к масштабу лапласиана. ^[12]Другая реализация в реальном времени экстремумов масштабного пространства лапласовского оператора была представлена ​​Линдебергом и Бретцнером на основе представления гибридной пирамиды ^[16], которая использовалась для взаимодействия человека с компьютером путем распознавания жестов в реальном времени в Bretzner et al. (2002). ^[17]

Локализация ключевых точек [ править ]

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

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

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

${\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 {x}}}$

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

Отказ от малоконтрастных ключевых точек [ править ]

Чтобы отбросить ключевые точки с низким контрастом, значение разложения Тейлора второго порядка вычисляется по смещению . Если это значение меньше , кандидатная ключевая точка отбрасывается. В противном случае он сохраняется с окончательным местоположением в масштабном пространстве , где находится исходное местоположение ключевой точки.${\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 минимально, когда собственные значения равны друг другу. Следовательно, чем выше абсолютная разница${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle r=\alpha /\beta }$${\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 (r+1)^{2}/r}$между двумя собственными значениями, что эквивалентно большей абсолютной разнице между двумя главными кривизнами D, тем выше значение R. Из этого следует, что для некоторого порогового отношения собственных значений , если R для ключевой точки-кандидата больше, чем , эта ключевая точка плохо локализован и, следовательно, отвергнут. Новый подход использует . ^[2]${\displaystyle r_{\text{th}}}$${\displaystyle (r_{\text{th}}+1)^{2}/r_{\text{th}}}$${\displaystyle r_{\text{th}}=10}$

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

Назначение ориентации [ править ]

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

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

${\displaystyle 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}}}}$

${\displaystyle \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 градусов. Каждая выборка в соседнем окне, добавляемая в ячейку гистограммы, взвешивается по величине градиента и с помощью взвешенного по Гауссу кругового окна с${\displaystyle \sigma }$это в 1,5 раза больше масштаба ключевой точки. Пики на этой гистограмме соответствуют доминирующим ориентациям. После заполнения гистограммы ключевой точке назначаются ориентации, соответствующие наивысшему пику и локальным пикам, которые находятся в пределах 80% от самых высоких пиков. В случае назначения нескольких ориентаций создается дополнительная характерная точка с тем же расположением и масштабом, что и исходная характерная точка для каждой дополнительной ориентации.

Дескриптор ключевой точки [ править ]

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

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

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

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

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

• 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, но в то же время намного быстрее. ^[20] Другие исследования пришли к выводу, что когда скорость не критична, SIFT превосходит SURF. ^{[21] [22] В} частности, без учета эффектов дискретизации дескриптор чистого изображения в SIFT значительно лучше, чем дескриптор чистого изображения в SURF, в то время как экстремумы в пространстве шкалы детерминанта Гессе, лежащего в основе детектора чистой точки интереса в SURF, составляют значительную часть лучшие точки интереса по сравнению с масштабными экстремумами лапласиана, к которым детектор точек интереса в SIFT представляет собой численное приближение. ^[21]

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

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

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

Приложения [ править ]

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

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

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

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

Локализация и отображение роботов [ править ]

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

Сшивание панорамы [ править ]

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

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

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

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

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

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

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

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

Конкурирующие методы [ править ]

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

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

G-RIF: ^[39] Обобщенный устойчивый инвариантный признак - это общий дескриптор контекста, который кодирует информацию об ориентации кромок, плотности кромок и оттенках в унифицированной форме, объединяя перцепционную информацию с пространственным кодированием. Схема распознавания объектов использует голосование на основе соседнего контекста для оценки моделей объектов.

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

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

Gauss-SIFT ^[21] - это чистый дескриптор изображения, определенный путем выполнения всех измерений изображения, лежащих в основе дескриптора чистого изображения в SIFT, с помощью откликов гауссовой производной, в отличие от производных приближений в пирамиде изображений, как это делается в обычном SIFT. Таким образом, эффекты дискретизации по пространству и масштабу могут быть сведены к минимуму, что позволяет создавать потенциально более точные дескрипторы изображения. В Линдеберге (2015) ^[21]такие чистые дескрипторы изображений Гаусса-SIFT были объединены с набором обобщенных точек интереса в масштабном пространстве, включающих лапласиан гауссиана, определитель гессиана, четыре новых беззнаковых или подписанных меры силы гессенских признаков, а также Харриса-Лапласа и Ши. и-Томази интересует. В обширной экспериментальной оценке набора данных плаката, включающего несколько видов 12 плакатов с преобразованием масштабирования до 6 раз и вариациями направления просмотра до угла наклона 45 градусов, было показано, что существенное повышение производительности сопоставления изображений (выше оценки эффективности и более низкие оценки с точностью до 1) могут быть получены путем замены лапласиана гауссовских точек интереса определителем точек интереса Гессе.Поскольку точки интереса с разностью гауссианов представляют собой численное приближение лапласиана точек интереса по Гауссу, это показывает, что существенное повышение эффективности сопоставления возможно путем замены точек интереса с разностью гауссианов в 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{or 0 otherwise}}}$. Количественное сравнение дескриптора Gauss-SIFT и соответствующего дескриптора Gauss-SURF также показало, что Gauss-SIFT в целом работает значительно лучше, чем Gauss-SURF, для большого количества различных детекторов точек интереса в масштабном пространстве. Таким образом, это исследование показывает, что без учета эффектов дискретизации дескриптор чистого изображения в SIFT значительно лучше, чем дескриптор чистого изображения в SURF, тогда как лежащий в основе детектор точки интереса в SURF, который можно рассматривать как численное приближение к экстремумам в масштабном пространстве детерминанта Гессен, значительно лучше, чем базовый детектор точки интереса в SIFT.

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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

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

• Инвариантные отношения трехмерной проекции к двумерной проекции наборов точек, Журнал исследований распознавания образов (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: обнаружение и сопоставление в объемных изображениях.