Обнаружение угла

Выходные данные типичного алгоритма обнаружения углов

Оценка эгодвижения с использованием обнаружения углов

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

Формализация

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

Точка интереса — это точка на изображении, которая имеет четко определенное положение и может быть надежно обнаружена. Это означает, что точка интереса может быть углом, но также может быть, например, изолированной точкой локального максимума или минимума интенсивности, окончаниями линий или точкой на кривой, где кривизна локально максимальна.

На практике большинство так называемых методов обнаружения углов обнаруживают точки интереса в целом, и фактически термины «угол» и «точка интереса» используются в литературе более или менее взаимозаменяемо. Как следствие, если необходимо обнаружить только углы, необходимо провести локальный анализ обнаруженных точек интереса, чтобы определить, какие из них являются настоящими углами. Примерами обнаружения краев, которые можно использовать с постобработкой для обнаружения углов, являются оператор Кирша и набор маскирования Фрея-Чена.

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

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

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

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

Алгоритм обнаружения углов Моравца

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

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

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

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

Как отметил Моравец, одна из основных проблем этого оператора заключается в том, что он не изотропен : если присутствует ребро, не направленное в сторону соседей (горизонтальное, вертикальное или диагональное), то наименьший SSD будет большой, и край будет неправильно выбран в качестве точки интереса.

Алгоритмы обнаружения углов Харриса и Стивенса/Ши-Томази

Дополнительная информация: Угловой детектор Харриса.

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

Без ограничения общности будем считать, что используется двухмерное изображение в оттенках серого. Пусть это изображение задано $I$. Рассмотрите возможность использования патча изображения над областью. $(u,v)$ и смещая его на $(x,y)$. Взвешенная сумма квадратов разностей (SSD) между этими двумя патчами, обозначаемая $S$, определяется:

$S(x,y)=\sum _{u}\sum _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$

$I(u+x,v+y)$ может быть аппроксимировано разложением Тейлора . Позволять $I_{x}$ и $I_{y}$ быть частными производными от $I$, такой, что

$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$

Это дает приближение

$S(x,y)\approx \sum _{u}\sum _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2},$

что можно записать в матричной форме:

$S(x,y)\approx {\begin{bmatrix}x&y\end{bmatrix}}A{\begin{bmatrix}x\\y\end{bmatrix}},$

где A — структурный тензор ,

$A=\sum _{u}\sum _{v}w(u,v){\begin{bmatrix}I_{x}(u,v)^{2}&I_{x}(u,v)I_{y}(u,v)\\I_{x}(u,v)I_{y}(u,v)&I_{y}(u,v)^{2}\end{bmatrix}}={\begin{bmatrix}\langle I_{x}^{2}\rangle &\langle I_{x}I_{y}\rangle \\\langle I_{x}I_{y}\rangle &\langle I_{y}^{2}\rangle \end{bmatrix}}$

Говоря словами, находим ковариацию частной производной интенсивности изображения $I$ в отношении $x$ и $y$ топоры.

Угловые скобки обозначают усреднение (т.е. суммирование по $(u,v)$). $w(u,v)$ обозначает тип окна, которое скользит по изображению. Если используется фильтр Box , отклик будет анизотропным , но если используется фильтр Gaussian , отклик будет изотропным .

Угол (или вообще точка интереса) характеризуется большим изменением $S$ во всех направлениях вектора ${\begin{bmatrix}x&y\end{bmatrix}}$. Анализируя собственные значения $A$, эта характеристика может быть выражена следующим образом: $A$ должно иметь два «больших» собственных значения для точки интереса. Основываясь на величинах собственных значений, на основе этого аргумента можно сделать следующие выводы:

1. Если $\lambda _{1}\approx 0$ и $\lambda _{2}\approx 0$ тогда этот пиксель $(x,y)$ не имеет особенностей, представляющих интерес.
2. Если $\lambda _{1}\approx 0$ и $\lambda _{2}$ имеет некоторое большое положительное значение, то находится ребро.
3. Если $\lambda _{1}$ и $\lambda _{2}$ имеют большие положительные значения, то находится угол.

Харрис и Стивенс отмечают, что точное вычисление собственных значений требует больших вычислительных затрат, поскольку требует вычисления квадратного корня , и вместо этого предлагают следующая функция $M_{c}$, где $\kappa$ — настраиваемый параметр чувствительности:

$M_{c}=\lambda _{1}\lambda _{2}-\kappa \left(\lambda _{1}+\lambda _{2}\right)^{2}=\det(A)-\kappa \operatorname {trace} ^{2}(A)$

Следовательно, алгоритм не нужно фактически вычислять разложение матрицы по собственным значениям $A$ и вместо этого достаточно определитель и след оценить $A$ найти углы, а точнее точки интереса в целом.

Ши-Томази детектор углов напрямую вычисляет $\min(\lambda _{1},\lambda _{2})$ потому что при определенных предположениях углы более стабильны для отслеживания. Обратите внимание, что этот метод также иногда называют угловым детектором Канаде – Томаси.

Стоимость $\kappa$ должен определяться эмпирически, и в литературе сообщалось, что значения в диапазоне 0,04–0,15 являются возможными.

Можно избежать установки параметра $\kappa$ с помощью Нобла угловая мера $M_{c}'$ что составляет среднее гармоническое собственных значений:

$M_{c}'=2{\frac {\det(A)}{\operatorname {trace} (A)+\epsilon }},$

$\epsilon$ является небольшой положительной константой.

Если $A$ можно интерпретировать как матрицу точности углового положения, ковариационная матрица углового положения равна $A^{-1}$, то есть

${\frac {1}{\langle I_{x}^{2}\rangle \langle I_{y}^{2}\rangle -\langle I_{x}I_{y}\rangle ^{2}}}{\begin{bmatrix}\langle I_{y}^{2}\rangle &-\langle I_{x}I_{y}\rangle \\-\langle I_{x}I_{y}\rangle &\langle I_{x}^{2}\rangle \end{bmatrix}}.$

Сумма собственных значений $A^{-1}$, которую в этом случае можно интерпретировать как обобщенную дисперсию (или «полную неопределенность») углового положения, связана с угловой мерой Нобла. $M_{c}'$ по следующему уравнению:

$\lambda _{1}(A^{-1})+\lambda _{2}(A^{-1})={\frac {\operatorname {trace} (A)}{\det(A)}}\approx {\frac {2}{M_{c}'}}.$

Угловой детектор Фёрстнера

Обнаружение углов с использованием алгоритма Фёрстнера

В некоторых случаях может потребоваться вычислить местоположение угла с точностью до субпикселя. Чтобы получить приближенное решение, Фёрстнер Алгоритм находит точку, ближайшую ко всем касательным линиям угла в данном окне, и представляет собой решение методом наименьших квадратов. Алгоритм основан на том факте, что в идеальном углу касательные пересекаются в одной точке.

Уравнение касательной $T_{\mathbf {x} '}(\mathbf {x} )$ в пикселе $\mathbf {x} '$ дается:

$T_{\mathbf {x'} }(\mathbf {x} )=\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} )=0$

где $\nabla I(\mathbf {x'} )={\begin{bmatrix}I_{\mathbf {x} }&I_{\mathbf {y} }\end{bmatrix}}^{\top }$ вектор градиента изображения $I$ в $\mathbf {x'}$.

Суть $\mathbf {x} _{0}$ ближайший ко всем касательным линиям в окне $N$ является:

$\mathbf {x} _{0}={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}T_{\mathbf {x'} }(\mathbf {x} )^{2}d\mathbf {x'}$

Расстояние от $\mathbf {x} _{0}$ к касательным линиям $T_{\mathbf {x'} }$ взвешивается по величине градиента, что придает большее значение касательным, проходящим через пиксели с сильными градиентами.

Решение для $\mathbf {x} _{0}$:

${\begin{aligned}\mathbf {x} _{0}&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}\left(\nabla I\left(\mathbf {x'} \right)^{\top }\left(\mathbf {x} -\mathbf {x'} \right)\right)^{2}d\mathbf {x'} \\&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}(\mathbf {x} -\mathbf {x'} )^{\top }\nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} )d\mathbf {x'} \\&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\left(\mathbf {x} ^{\top }A\mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} +c\right)\end{aligned}}$

$A\in \mathbb {R} ^{2\times 2},{\textbf {b}}\in \mathbb {R} ^{2\times 1},c\in \mathbb {R}$ определяются как:

${\begin{aligned}A&=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }d\mathbf {x'} \\\mathbf {b} &=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\mathbf {x'} d\mathbf {x'} \\c&=\int \mathbf {x'} ^{\top }\nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\mathbf {x'} d\mathbf {x'} \\\end{aligned}}$

Минимизацию этого уравнения можно выполнить, дифференцируя по $x$ и установим его равным 0:

$2A\mathbf {x} -2\mathbf {b} =0\Rightarrow A\mathbf {x} =\mathbf {b}$

Обратите внимание, что $A\in \mathbb {R} ^{2\times 2}$ – структурный тензор . Чтобы уравнение имело решение, $A$ должно быть обратимым, а это означает, что $A$ должен быть полного ранга (ранг 2). Таким образом, решение

$x_{0}=A^{-1}\mathbf {b}$

существует только там, где в окне существует реальный угол $N$.

Методология автоматического выбора масштаба для этого метода угловой локализации была представлена ​​Линдебергом. минимизируя нормализованную невязку

${\tilde {d}}_{\min }={\frac {c-b^{T}A^{-1}b}{\operatorname {trace} A}}$

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

Примечания:

• $c$ можно рассматривать как остаток при вычислении решения методом наименьших квадратов: если $c=0$, то ошибки не было.
• этот алгоритм можно модифицировать для вычисления центров круговых объектов, заменив касательные линии нормальными линиями.

Многомасштабный оператор Харриса

Вычисление матрицы второго момента (иногда также называемой структурным тензором ) $A$ в операторе Харриса требуется вычисление производных изображений $I_{x},I_{y}$ в области изображений, а также суммирование нелинейных комбинаций этих производных по локальным окрестностям. Поскольку вычисление производных обычно включает этап сглаживания в масштабном пространстве, рабочее определение оператора Харриса требует двух параметров масштаба: (i) локального масштаба для сглаживания перед вычислением производных изображения и (ii) масштаба интегрирования . для накопления нелинейных операций над производными операторами в интегрированный дескриптор изображения.

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

$g(x,y,t)={\frac {1}{2{\pi }t}}e^{-\left(x^{2}+y^{2}\right)/2t}$

с параметром локального масштаба $t$:

$L(x,y,t)\ =g(x,y,t)*I(x,y)$

и пусть $L_{x}=\partial _{x}L$ и $L_{y}=\partial _{y}L$ обозначаем частные производные $L$. Кроме того, введем оконную функцию Гаусса $g(x,y,s)$ с параметром масштаба интегрирования $s$. Тогда многомасштабная матрица второго момента может быть определен как

$\mu (x,y;t,s)=\int _{\xi =-\infty }^{\infty }\int _{\eta =-\infty }^{\infty }{\begin{bmatrix}L_{x}^{2}(x-\xi ,y-\eta ;t)&L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x-\xi ,y-\eta ;t)\\L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x-\xi ,y-\eta ;t)&L_{y}^{2}(x-\xi ,y-\eta ;t)\end{bmatrix}}g(\xi ,\eta ;s)\,d\xi \,d\eta .$

Затем мы можем вычислить собственные значения $\mu$ аналогично собственным значениям $A$ и определим многомасштабную угловую меру Харриса как

$M_{c}(x,y;t,s)=\det(\mu (x,y;t,s))-\kappa \,\operatorname {trace} ^{2}(\mu (x,y;t,s)).$

К вопросу о выборе параметра локального масштаба $t$ и параметр масштаба интегрирования $s$, эти параметры масштаба обычно связаны параметром относительного масштаба интегрирования $\gamma$ такой, что $s=\gamma ^{2}t$, где $\gamma$ обычно выбирается в интервале $[1,2]$. Таким образом, мы можем вычислить многомасштабную угловую меру Харриса. $M_{c}(x,y;t,\gamma ^{2}t)$ в любом масштабе $t$ в масштабном пространстве, чтобы получить многомасштабный угловой детектор, который реагирует на угловые структуры разных размеров в области изображения.

На практике этот многомасштабный угловой детектор часто дополняется шагом выбора масштаба , где нормированный по масштабу оператор Лапласа

$\nabla _{\mathrm {norm} }^{2}L(x,y;t)\ =t\nabla ^{2}L(x,y,t)=t(L_{xx}(x,y,t)+L_{yy}(x,y,t))$

вычисляется в каждом масштабе в масштабном пространстве, а угловые точки, адаптированные к масштабу, с автоматическим выбором масштаба («оператор Харриса-Лапласа») вычисляются из точек, которые одновременно:

• пространственные максимумы многомасштабной угловой меры $M_{c}(x,y;t,\gamma ^{2}t)$

  $({\hat {x}},{\hat {y}};t)=\operatorname {argmaxlocal} _{(x,y)}M_{c}\left(x,y;t,\gamma ^{2}t\right)$

• локальные максимумы или минимумы в масштабах нормированного по масштабу оператора Лапласа $\nabla _{\mathrm {norm} }^{2}(x,y,t)$:

  ${\hat {t}}=\operatorname {argmaxminlocal} _{t}\nabla _{\mathrm {norm} }^{2}L({\hat {x}},{\hat {y}};t)$

Подход с использованием кривизны кривой уровня

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

${\tilde {\kappa }}(x,y;t)=L_{x}^{2}L_{yy}+L_{y}^{2}L_{xx}-2L_{x}L_{y}L_{xy}$

и обнаружить положительные максимумы и отрицательные минимумы этого дифференциального выражения в некотором масштабе $t$ в масштабном представлении пространства $L$ исходного изображения. Однако основная проблема при вычислении объекта кривизны перемасштабированной кривой уровня в одном масштабе заключается в том, что он может быть чувствителен к шуму и выбору уровня масштаба. Лучшим методом является вычисление $\gamma$-нормализованная измененная кривизна кривой уровня

${\tilde {\kappa }}_{\mathrm {norm} }(x,y;t)=t^{2\gamma }(L_{x}^{2}L_{yy}+L_{y}^{2}L_{xx}-2L_{x}L_{y}L_{xy})$

с $\gamma =7/8$ и обнаружить масштабном пространстве знаковые экстремумы этого выражения в , которые представляют собой точки и масштабы, которые являются положительными максимумами и отрицательными минимумами как по отношению к пространству, так и по масштабу.

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argminmaxlocal} _{(x,y;t)}{\tilde {\kappa }}_{\mathrm {norm} }(x,y;t)$

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

Лапласиан от гауссиана, различия гауссианов и определитель точек интереса гессенского масштабного пространства

Бревно это аббревиатура, обозначающая лапласиан или гауссиан , DoG. — это аббревиатура, обозначающая разность гауссианов (DoG — это аппроксимация LoG), а DoH — это аббревиатура, обозначающая определитель гессиана . Все эти инвариантные к масштабу точки интереса извлекаются путем обнаружения экстремумов в масштабном пространстве нормализованных к масштабу дифференциальных выражений, т. е. точек в масштабном пространстве, где соответствующие нормированные к масштабу дифференциальные выражения принимают локальные экстремумы как по отношению к пространству, так и к масштабу.

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argminmaxlocal} _{(x,y;t)}(D_{\mathrm {norm} }L)(x,y;t)$

где $D_{norm}L$ обозначает соответствующий дифференциальный объект, нормализованный по масштабу (определенный ниже).

Эти детекторы более полно описаны в разделе «Обнаружение BLOB-объектов» . Нормированный по масштабу лапласиан гауссовых и разностных гауссовских характеристик (Линдеберг 1994, 1998; Лоу 2004)

${\begin{aligned}\nabla _{\mathrm {norm} }^{2}L(x,y;t)&=t\,(L_{xx}+L_{yy})\\&\approx {\frac {t\left(L(x,y;t+\Delta t)-L(x,y;t)\right)}{\Delta t}}\end{aligned}}$

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

Нормированный по масштабу определитель оператора Гессе (Линдеберг 1994, 1998).

$\det H_{\mathrm {norm} }L=t^{2}(L_{xx}L_{yy}-L_{xy}^{2})$

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

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

Точки интереса в масштабном пространстве, основанные на мерах силы признаков Линдеберга-Гессе

Вдохновлен структурно схожими свойствами матрицы Гессе. $Hf$ функции $f$ и матрица второго момента (структурный тензор) $\mu$, что может проявляться, например, в их схожих трансформационных свойствах при аффинных деформациях изображений

$(Hf')=A^{-T}\,(Hf)\,A^{-1}$,

$\mu '=A^{-T}\,\mu \,A^{-1}$,

Линдеберг (2013, 2015) предложено определять четыре меры силы признаков из матрицы Гессе аналогичным образом, поскольку операторы Харриса и Ши-и-Томази определяются из структурного тензора (матрицы второго момента). В частности, он определил следующие беззнаковые и подписанные меры силы гессенских признаков:

• беззнаковая мера силы гессенского признака I:

  $D_{1,\mathrm {norm} }L={\begin{cases}t^{2}\,(\det HL-k\,\operatorname {trace} ^{2}HL)&{\mbox{if}}\,\det HL-k\,\operatorname {trace} ^{2}HL>0\\0&{\mbox{otherwise}}\end{cases}}$

• подписанная мера силы гессенского признака I:

  ${\tilde {D}}_{1,\mathrm {norm} }L={\begin{cases}t^{2}\,(\det HL-k\,\operatorname {trace} ^{2}HL)&{\mbox{if}}\,\det HL-k\,\operatorname {trace} ^{2}HL>0\\t^{2}\,(\det HL+k\,\operatorname {trace} ^{2}HL)&{\mbox{if}}\,\det HL+k\,\operatorname {trace} ^{2}HL<0\\0&{\mbox{otherwise}}\end{cases}}$

• беззнаковая мера силы гессиана II:

  $D_{2,\mathrm {norm} }L=t\,\min(|\lambda _{1}(HL)|,|\lambda _{2}(HL)|)$

• подписанная мера силы гессенского признака II:

  ${\tilde {D}}_{2,\mathrm {norm} }L={\begin{cases}t\,\lambda _{1}(HL)&{\mbox{if}}\,|\lambda _{1}(HL)|<|\lambda _{2}(HL)|\\t\,\lambda _{2}(HL)&{\mbox{if}}\,|\lambda _{2}(HL)|<|\lambda _{1}(HL)|\\t\,(\lambda _{1}(HL)+\lambda _{2}(HL))/2&{\mbox{otherwise}}\end{cases}}$

где $\operatorname {trace} HL=L_{xx}+L_{yy}$ и $\det HL=L_{xx}L_{yy}-L_{xy}^{2}$ обозначаем след и определитель матрицы Гессе $HL$ представления в масштабном пространстве $L$ в любом масштабе $t$, тогда как

$\lambda _{1}(HL)=L_{pp}={\frac {1}{2}}\left(L_{xx}+L_{yy}-{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}\right)$

$\lambda _{2}(HL)=L_{qq}={\frac {1}{2}}\left(L_{xx}+L_{yy}+{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}\right)$

обозначают собственные значения матрицы Гессе.

Беззнаковая мера силы гессиана $D_{1,\mathrm {norm} }L$ реагирует на локальные экстремумы положительными значениями и не чувствителен к седловым точкам, тогда как знаковая мера силы признака Гессе ${\tilde {D}}_{1,\mathrm {norm} }L$ дополнительно реагирует на седловые точки отрицательными значениями. Беззнаковая мера силы гессиана $D_{2,\mathrm {norm} }L$ нечувствителен к локальной полярности сигнала, тогда как знаковая мера силы гессиана ${\tilde {D}}_{2,\mathrm {norm} }L$ реагирует на локальную полярность сигнала по знаку его выхода.

В Линдеберге (2015) эти четыре дифференциальных объекта были объединены с выбором локального масштаба на основе обнаружения экстремумов в масштабном пространстве.

$({\hat {x}},{\hat {y}};{\hat {t}})=\operatorname {argminmaxlocal} _{(x,y;t)}(D_{\mathrm {norm} }L)(x,y;t)$

или масштабировать связь. Кроме того, знаковый и беззнаковый гессиан характеризуются мерами силы. $D_{2,\mathrm {norm} }L$ и ${\tilde {D}}_{2,\mathrm {norm} }L$ были объединены с дополнительной пороговой оценкой $D_{1,\mathrm {norm} }L>0$.

Путем экспериментов по сопоставлению изображений при масштабных преобразованиях на наборе данных плакатов с 12 плакатами с сопоставлением нескольких изображений по масштабным преобразованиям до масштабного коэффициента 6 и изменениям направления просмотра до угла наклона 45 градусов с локальными дескрипторами изображений, определенными из переформулировок было показано, что дескрипторы чистого изображения в операторах SIFT и SURF для измерения изображений в терминах операторов производной Гаусса (Gauss-SIFT и Gauss-SURF) вместо исходного SIFT, определенного на основе пирамиды изображений, или исходного SURF, определенного на основе вейвлетов Хаара, было показано это обнаружение точки интереса в масштабном пространстве на основе беззнаковой меры силы признака Гессе $D_{1,\mathrm {norm} }L$ допускал лучшую производительность и лучшую производительность, чем точки интереса в масштабном пространстве, полученные из определителя гессиана $\det H_{\mathrm {norm} }L=t^{2}\left(L_{xx}L_{yy}-L_{xy}^{2}\right)$. Обе беззнаковые гессианские функции являются мерой силы. $D_{1,\mathrm {norm} }L$, знаковая мера силы гессиана ${\tilde {D}}_{1,norm}L$ и определитель гессиана $\det H_{norm}L$ допускал лучшую производительность, чем лапласиан гауссовой $\nabla _{\mathrm {norm} }^{2}L=t\,(L_{xx}+L_{yy})$. В сочетании с привязкой масштабов и дополнительным пороговым значением $D_{1,\mathrm {norm} }L>0$, знаковая мера силы гессиана ${\tilde {D}}_{2,\mathrm {norm} }L$ дополнительно обеспечил лучшую производительность, чем лапласиан гауссовой $\nabla _{\mathrm {norm} }^{2}L$.

Кроме того, было показано, что все эти детекторы точек интереса в дифференциальном масштабе, определенные на основе матрицы Гессе, позволяют обнаруживать большее количество точек интереса и улучшать производительность сопоставления по сравнению с операторами Харриса и Ши-и-Томази, определенными из структуры тензор (матрица второго момента).

Теоретический анализ свойств выбора масштаба этих четырех мер силы гессиана и других дифференциальных объектов для обнаружения точек интереса в масштабном пространстве, включая лапласиан гауссиана и определитель гессиана, приведен в Линдеберге (2013). и анализ их свойств аффинного преобразования, а также экспериментальных свойств в Линдеберге (2015).

Аффинно-адаптированные операторы точек интереса

Точки интереса, полученные с помощью многомасштабного оператора Харриса с автоматическим выбором масштаба, инвариантны к перемещениям, вращениям и равномерным изменениям масштаба в пространственной области. Однако изображения, которые представляют собой входные данные для системы компьютерного зрения, также подвержены перспективным искажениям. Чтобы получить оператор точки интереса, более устойчивый к перспективным преобразованиям, естественным подходом является разработка детектора признаков, инвариантного к аффинным преобразованиям . На практике аффинные инвариантные точки интереса могут быть получены путем применения аффинной адаптации формы , при которой форма сглаживающего ядра итеративно деформируется, чтобы соответствовать локальной структуре изображения вокруг точки интереса, или, что эквивалентно, локальный фрагмент изображения итеративно деформируется, в то время как форма сглаживания ядро остается вращательно-симметричным (Линдеберг, 1993, 2008; Линдеберг и Гардинг, 1997; Миколайзчик и Шмид, 2004). Следовательно, помимо широко используемого многомасштабного оператора Харриса, аффинная адаптация формы может применяться к другим угловым детекторам, перечисленным в этой статье, а также к дифференциальным детекторам BLOB-объектов, таким как оператор Лапласа/разности гауссовских операторов, определитель гессиана. и оператор Гессиана–Лапласа.

Алгоритм обнаружения углов Ванга и Брейди

Ван и Брейди детектор считает изображение поверхностью и ищет места с большой кривизной по краю изображения. Другими словами, алгоритм ищет места, где край быстро меняет направление. Угловой счет, $C$, определяется:

$C=\left({\frac {\delta ^{2}I}{\delta \mathbf {t} ^{2}}}\right)^{2}-c|\nabla I|^{2},$

где ${\bf {t}}$ - единичный вектор, перпендикулярный градиенту, и $c$ определяет, насколько фобичен детектор. Авторы также отмечают, что для уменьшения шума необходимо сглаживание (предлагается гауссово).

Сглаживание также вызывает смещение углов, поэтому авторы выводят выражение для смещения угла на 90 градусов и применяют его в качестве поправочного коэффициента к обнаруженным углам.

Угловой детектор SUSAN

СЬЮЗЕН — аббревиатура, обозначающая наименьший однозначный сегмент ассимилирующего ядра . Этот метод является предметом патента Великобритании 1994 года, который больше не действует.

Для обнаружения признаков СЬЮЗАН помещает круглую маску на тестируемый пиксель (ядро). Область маски $M$, а пиксель в этой маске представлен как ${\vec {m}}\in M$. Ядро находится в ${\vec {m}}_{0}$. Каждый пиксель сравнивается с ядром с помощью функции сравнения:

$c({\vec {m}})=e^{-\left({\frac {I({\vec {m}})-I({\vec {m}}_{0})}{t}}\right)^{6}}$

где $t$ – порог разницы яркостей, $I$ - яркость пикселя, а степень показателя степени определена эмпирически. Эта функция имеет вид сглаженного цилиндра или прямоугольной функции . Площадь Сьюзен определяется как:

$n(M)=\sum _{{\vec {m}}\in M}c({\vec {m}})$

Если $c$ – прямоугольная функция, то $n$ количество пикселей в маске, находящихся в пределах $t$ ядра. Ответ оператора SUSAN имеет вид:

$R(M)={\begin{cases}g-n(M)&{\mbox{if}}\ n(M)<g\\0&{\mbox{otherwise,}}\end{cases}}$

где $g$ называется «геометрическим порогом». Другими словами, оператор SUSAN имеет положительную оценку только в том случае, если площадь достаточно мала. Наименьший SUSAN локально можно найти с помощью немаксимального подавления, и это полный оператор SUSAN.

Значение $t$ определяет, насколько похожими должны быть точки на ядро, прежде чем они будут считаться частью однозначного сегмента. Стоимость $g$ определяет минимальный размер однозначного сегмента. Если $g$ достаточно велик, то это становится детектором границ .

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

Угловой детектор Трайковича и Хедли

Подобно СЬЮЗАН, этот детектор напрямую проверяет, является ли участок под пикселем самоподобным, исследуя близлежащие пиксели. ${\vec {c}}$ - это пиксель, который следует учитывать, и ${\vec {p}}\in P$ это точка на окружности $P$ сосредоточен вокруг ${\vec {c}}$. Суть ${\vec {p}}'$ это точка, противоположная ${\vec {p}}$ по диаметру.

Функция ответа определяется как:

$r({\vec {c}})=\min _{{\vec {p}}\in P}\left(\left(I({\vec {p}})-I({\vec {c}})\right)^{2}+\left(I({\vec {p}}')-I({\vec {c}})\right)^{2}\right)$

Оно будет большим, если не существует направления, в котором центральный пиксель похож на два соседних пикселя по диаметру. $P$ представляет собой дискретизированный круг ( круг Брезенхема ), поэтому интерполяция для промежуточных диаметров используется , чтобы дать более изотропный отклик. Поскольку любое вычисление дает верхнюю границу $\min$, сначала проверяются горизонтальное и вертикальное направления, чтобы понять, стоит ли приступать к полному вычислению $c$.

Детекторы признаков на основе AST

AST — это аббревиатура, обозначающая ускоренное тестирование сегмента . Этот тест представляет собой упрощенную версию углового критерия СЬЮЗАН. Вместо оценки круглого диска только пиксели в круге Брезенхэма радиуса $r$ вокруг точки-кандидата рассматриваются. Если $n$ все смежные пиксели ярче ядра как минимум на $t$ или все темнее ядра на $t$, то пиксель под ядром считается признаком. Сообщается, что этот тест дает очень стабильные функции. Выбор порядка проверки пикселей — это так называемая задача двадцати вопросов . Построение коротких деревьев решений для этой проблемы приводит к созданию наиболее эффективных в вычислительном отношении доступных детекторов признаков.

Первый алгоритм обнаружения углов, основанный на AST, — это FAST ( функции ускоренного теста сегмента ). Хотя $r$ в принципе может принимать любое значение, FAST использует только значение 3 (что соответствует окружности с окружностью 16 пикселей), а тесты показывают, что наилучшие результаты достигаются при $n$ равно 9. Это значение $n$ является самым низким, при котором края не обнаруживаются. Порядок проверки пикселей определяется алгоритмом ID3 из обучающего набора изображений. Как ни странно, название детектора чем-то похоже на название статьи, описывающей детектор Трайковича и Хедли.

Автоматический синтез детекторов

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

Детекторы пространственно-временных точек интереса

Оператор Харриса был распространен на пространство-время Лаптевым и Линдебергом. Позволять $\mu$ обозначают пространственно-временную матрицу второго момента, определяемую формулой

$A=\sum _{u}\sum _{v}\sum _{w}h(u,v,w){\begin{bmatrix}L_{x}(u,v,w)^{2}&L_{x}(u,v,w)L_{y}(u,v,w)&L_{x}(u,v,w)L_{t}(u,v,w)\\L_{x}(u,v,w)L_{y}(u,v,w)&L_{y}(u,v,w)^{2}&L_{y}(u,v,w)L_{t}(u,v,w)\\L_{x}(u,v,w)L_{t}(u,v,w)&L_{y}(u,v,w)L_{t}(u,v,w)&L_{t}(u,v,w)^{2}\\\end{bmatrix}}={\begin{bmatrix}\langle L_{x}^{2}\rangle &\langle L_{x}L_{y}\rangle &\langle L_{x}L_{t}\rangle \\\langle L_{x}L_{y}\rangle &\langle L_{y}^{2}\rangle &\langle L_{y}L_{t}\rangle \\\langle L_{x}L_{t}\rangle &\langle L_{y}L_{t}\rangle &\langle L_{t}^{2}\rangle \\\end{bmatrix}}$

Тогда для подходящего выбора $k<1/27$, пространственно-временные точки интереса обнаруживаются по пространственно-временным экстремумам следующей пространственно-временной меры Харриса:

$H=\det(\mu )-\kappa \,\operatorname {trace} ^{2}(\mu ).$

Определитель оператора Гессе был расширен на совместное пространство-время Виллемсом и др. и Линдеберг, что приводит к следующему дифференциальному выражению, нормализованному по масштабу:

$\det(H_{(x,y,t),\mathrm {norm} }L)=\,s^{2\gamma _{s}}\tau ^{\gamma _{\tau }}\left(L_{xx}L_{yy}L_{tt}+2L_{xy}L_{xt}L_{yt}-L_{xx}L_{yt}^{2}-L_{yy}L_{xt}^{2}-L_{tt}L_{xy}^{2}\right).$

В работе Виллемса и др. более простое выражение, соответствующее $\gamma _{s}=1$ и $\gamma _{\tau }=1$ был использован. В Линдеберге, было показано, что $\gamma _{s}=5/4$ и $\gamma _{\tau }=5/4$ подразумевает лучшие свойства выбора масштаба в том смысле, что выбранные уровни масштаба получены из пространственно-временного гауссова пятна с пространственной протяженностью. $s=s_{0}$ и временная протяженность $\tau =\tau _{0}$ будет идеально соответствовать пространственной протяженности и временной продолжительности BLOB-объекта, при этом выбор масштаба выполняется путем обнаружения экстремумов пространственно-временного масштаба-пространства дифференциального выражения.

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

$\partial _{t,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }/2}(L_{xxt}+L_{yyt}),$

$\partial _{tt,\mathrm {norm} }(\nabla _{(x,y),\mathrm {norm} }^{2}L)=s^{\gamma _{s}}\tau ^{\gamma _{\tau }}(L_{xxtt}+L_{yytt}).$

Для первого оператора свойства выбора масштаба требуют использования $\gamma _{s}=1$ и $\gamma _{\tau }=1/2$, если мы хотим, чтобы этот оператор принял свое максимальное значение в пространственно-временных масштабах на уровне пространственно-временного масштаба, отражающем пространственную протяженность и временную продолжительность возникшего гауссова пятна. Для второго оператора свойства выбора масштаба требуют использования $\gamma _{s}=1$ и $\gamma _{\tau }=3/4$, если мы хотим, чтобы этот оператор принял максимальное значение в пространственно-временных масштабах на уровне пространственно-временного масштаба, отражающем пространственную протяженность и временную продолжительность мигающего гауссова пятна.

Цветовые расширения пространственно-временных детекторов точек интереса были исследованы Everts et al.

Эталонные реализации

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

• Обнаружение DoG (в рамках системы SIFT ), Windows и x86 Linux исполняемые файлы
• Харрис-Лаплас , статические исполняемые файлы Linux . Также содержит детекторы DoG и LoG и аффинную адаптацию для всех включенных детекторов.
• Детектор FAST , исходный код C, C++, MATLAB и исполняемые файлы для различных операционных систем и архитектур.
• Lip-vireo. Архивировано 11 мая 2017 г. в Wayback Machine , [LoG, DoG, Харрис-Лапласиан, Гессиан и Гессиан-Лаплас], [SIFT, флип-инвариант SIFT, PCA-SIFT, PSIFT, управляемые фильтры, SPIN] [Linux] , Windows и SunOS] исполняемые файлы.
• СЬЮЗАН Низкоуровневая обработка изображений , исходный код C.
• Онлайн-реализация углового детектора Харриса - IPOL

См. также

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

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

• Линдеберг, Тони (2001) [1994], «Обнаружение углов» , Энциклопедия математики , EMS Press
• Бростоу, «Обнаружение углов — UCL Computer Science»