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

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

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

Формализация [ править ]

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

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

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

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

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

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

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

Алгоритм определения углов Moravec [ править ]

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

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

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

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

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

Алгоритмы определения углов Харриса и Стивенса / Ши – Томази [ править ]

См. Угловой детектор Харриса .

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

Не умаляя общности, мы будем предполагать, что используется двухмерное изображение в градациях серого. Пусть это изображение будет дано . Подумайте о том, чтобы нанести пятно изображения на область и сместить его . Взвешенная сумма квадратов разностей (SSD) между этими двумя патчами, обозначенная как:${\ displaystyle I}$${\ Displaystyle (и, v)}$${\ Displaystyle (х, у)}$${\ displaystyle S}$

${\ Displaystyle S (х, y) = \ сумма _ {и} \ сумма _ {v} вес (и, v) \, \ влево (я (и + х, v + y) -I (и, v) \ right) ^ {2}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, алгоритм ^[6] не имеет на самом деле вычислить собственное значение разложения матрицы , а вместо этого достаточно , чтобы оценить определитель и след от найти углы, или скорее процентные пункты в целом.${\displaystyle A}$${\displaystyle A}$

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

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

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

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

${\displaystyle \epsilon }$ будучи небольшой положительной константой.

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

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

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

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

Угловой детектор Förstner [ править ]

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

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

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

где - вектор градиента изображения в точке .${\displaystyle \nabla I(\mathbf {x'} )=[I_{\mathbf {x} },I_{\mathbf {y} }]^{\top }}$${\displaystyle I}$${\displaystyle \mathbf {x'} }$

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

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

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

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

${\displaystyle {\begin{aligned}\mathbf {x} _{0}&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}(\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} ))^{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} }}\,(\mathbf {x} ^{\top }A\mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} +c)\end{aligned}}}$

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

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

Минимизировать это уравнение можно, дифференцировав по и установив его равным 0:${\displaystyle x}$

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

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

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

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

Методология выполнения автоматического выбора масштаба для этого метода локализации угла была представлена ​​Линдебергом ^{[10] [11]} путем минимизации нормализованной невязки.

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

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

Примечания:

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

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

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

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

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

с параметром местного масштаба :${\displaystyle t}$

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

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

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

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

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

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

На практике этот многомасштабный угловой детектор часто дополняется этапом выбора масштаба , на котором применяется нормированный по масштабу лапласовский оператор ^{[11] [12]}

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

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

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

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

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

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

Подход кривизны кривой уровня [ править ]

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

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

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

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

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

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

в сочетании с дополнительным этапом локализации, чтобы справиться с увеличением ошибки локализации в более грубых масштабах. ^{[10] [11] [12]} Таким образом, большие значения масштаба будут связаны с закругленными углами большой пространственной протяженности, тогда как меньшие значения масштаба будут связаны с острыми углами с малой пространственной протяженностью. Этот подход является первым детектором углов с автоматическим выбором масштаба (до «оператора Харриса-Лапласа» выше) и использовался для отслеживания углов при крупномасштабных вариациях в области изображения ^[18] и для сопоставления угловых откликов с краями для вычисления особенности структурного изображения для распознавания объектов на основе geon . ^[19]

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

LoG ^{[11] [12] [15]} - это аббревиатура от Laplacian of Gaussian , DoG ^[20] - это аббревиатура, обозначающая разность гауссианов (DoG - это приближение к LoG), а DoH - это аббревиатура, обозначающая определитель Гессен. ^[11] Все эти масштабно-инвариантные точки интереса извлекаются путем обнаружения экстремумов в масштабном пространстве нормализованных по масштабу дифференциальных выражений, т. Е. Точек в масштабном пространстве, где соответствующие нормализованные по масштабу дифференциальные выражения предполагают локальные экстремумы как по пространству, так и по масштабу. ^[11]

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

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

Эти детекторы более полно описаны в разделе «Обнаружение блобов» . Нормированный по масштабу лапласиан гауссовских и разностных гауссовых функций (Lindeberg 1994, 1998; Lowe 2004) ^{[11] [12] [20]}

${\displaystyle {\begin{aligned}\nabla _{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 ^[20] Поэтому система использует дополнительный пост-обработку сцену, где собственные значения по гессиану изображения в масштабе обнаружения уже рассмотрены в аналогично оператору Харриса. Если соотношение собственных значений слишком велико, тогда локальное изображение рассматривается как слишком похожее на кромку, поэтому признак отклоняется. Также можно определить лапласиан Линдеберга гауссовского детектора признаков, чтобы он содержал дополнительную пороговую обработку для дополнительного дифференциального инварианта для подавления откликов вблизи краев. ^[21]

Масштабно-нормированный определитель оператора Гессе (Lindeberg 1994, 1998) ^{[11] [12]}

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

с другой стороны, очень селективен к хорошо локализованным характеристикам изображения и реагирует только при значительных вариациях уровня серого в двух направлениях изображения ^{[11] [14]} и в этом и других отношениях является лучшим детектором точки интереса, чем лапласиан гауссовский. Определитель гессиана является аффинно-ковариантным дифференциальным выражением и имеет лучшие свойства масштабного выбора при преобразованиях аффинных изображений, чем оператор Лапласа (Lindeberg 2013, 2015). ^{[21] [22]}Экспериментально это означает, что определитель точек интереса Гессе имеет лучшие свойства повторяемости при локальной деформации изображения, чем точки интереса Лапласа, что, в свою очередь, приводит к лучшей производительности сопоставления на основе изображений с точки зрения более высоких оценок эффективности и более низких оценок точности 1. ^[21]

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

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

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

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

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

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

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

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

• подписанная мера силы гессенских элементов I:

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

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

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

• подписанная мера силы гессенских элементов II:

${\displaystyle {\tilde {D}}_{2,norm}L={\begin{Bmatrix}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{Bmatrix}}}$

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

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

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

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

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

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

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

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

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

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

Теоретический анализ свойств выбора шкалы этих четырех мер силы признаков Гессе и других дифференциальных сущностей для обнаружения точек интереса в масштабном пространстве, включая лапласиан гауссиана и определитель гессиана, приведен в Lindeberg (2013) ^[22]. и анализ их свойств аффинного преобразования, а также экспериментальных свойств в Lindeberg (2015). ^[21]

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

Точки интереса, полученные с помощью многомасштабного оператора Харриса с автоматическим выбором масштаба, инвариантны к сдвигам, поворотам и равномерному изменению масштаба в пространственной области. Однако изображения, входящие в систему компьютерного зрения, также подвержены перспективным искажениям. Чтобы получить оператор точки интереса, который более устойчив к перспективным преобразованиям, естественным подходом является разработка детектора признаков, который инвариантен к аффинным преобразованиям . На практике аффинно-инвариантные точки интереса можно получить, применяя адаптацию аффинной формы.где форма сглаживающего ядра итеративно деформируется, чтобы соответствовать локальной структуре изображения вокруг интересующей точки, или, что эквивалентно, локальный участок изображения итеративно деформируется, в то время как форма сглаживающего ядра остается вращательно-симметричной (Lindeberg 1993, 2008; Lindeberg and Garding 1997; Миколайзцик и Шмид 2004). ^{[12] [13] [14] [15]} Следовательно, помимо широко используемого многомасштабного оператора Харриса, адаптация аффинной формы может применяться к другим детекторам углов, перечисленным в этой статье, а также к дифференциальным детекторам капель, таким как лапласиан. / разность гауссовского оператора, определитель гессиана ^[14] и оператора Гессе – Лапласа.

Алгоритм обнаружения углов Ванга и Брэди [ править ]

Детектор Ванга и Брэди ^[24] рассматривает изображение как поверхность и ищет места с большой кривизной по краю изображения. Другими словами, алгоритм ищет места, где край быстро меняет направление. Угловой счет определяется по формуле:${\displaystyle C}$

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

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

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

Угловой детектор SUSAN [ править ]

SUSAN ^[25] - это аббревиатура, обозначающая ассимилирующее ядро ​​наименьшего однозначного сегмента. Этот метод является предметом патента Великобритании 1994 года, который больше не действует. ^[26]

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

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

где - порог разности яркости, ^[27] - яркость пикселя, а степень экспоненты была определена эмпирически. Эта функция имеет вид сглаженного цилиндра или прямоугольной функции . Площадь СУЗАНА определяется по:${\displaystyle t}$ ${\displaystyle I}$

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

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

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

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

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

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

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

Подобно SUSAN, этот детектор ^[28] непосредственно проверяет, является ли участок под пикселем самоподобным, исследуя соседние пиксели. - это пиксель, который необходимо учитывать, и представляет собой точку на круге с центром вокруг . Точка - это точка, противоположная диаметру.${\displaystyle {\vec {c}}}$${\displaystyle {\vec {p}}\in P}$${\displaystyle P}$${\displaystyle {\vec {c}}}$${\displaystyle {\vec {p'}}}$${\displaystyle {\vec {p}}}$

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

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

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

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

AST - это аббревиатура, обозначающая ускоренный сегментный тест. Этот тест является упрощенной версией критерия угла SUSAN. Вместо оценки круглого диска учитываются только пиксели в круге Брезенхема с радиусом вокруг точки-кандидата. Если смежные пиксели все ярче ядра по крайней мере или все темнее ядра на , то пиксель под ядром считается признаком. Сообщается, что этот тест дает очень стабильные функции. ^[29] Выбор порядка, в котором проверяются пиксели, представляет собой так называемую задачу «Двадцать вопросов».${\displaystyle r}$${\displaystyle n}$${\displaystyle t}$${\displaystyle t}$. Построение коротких деревьев решений для этой проблемы приводит к наиболее эффективным с вычислительной точки зрения доступным детекторам.

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

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

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

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

Оператор Харриса был расширен на пространство-время Лаптевым и Линдебергом. ^[31] Позвольте обозначить пространственно-временную матрицу второго момента, определенную как${\displaystyle \mu }$

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

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

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

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

${\displaystyle \operatorname {det} (H_{(x,y,t),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).}$

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

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

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

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

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

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

Библиография [ править ]

Эталонные реализации [ править ]

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

• Обнаружение DoG (как часть системы SIFT ), исполняемые файлы Windows и x86 Linux
• Харрис-Лаплас , статические исполняемые файлы Linux . Также содержит детекторы DoG и LoG и аффинную адаптацию для всех включенных детекторов.
• Детектор FAST , исходный код C, C ++, MATLAB и исполняемые файлы для различных операционных систем и архитектур.
• lip-vireo , [LoG, DoG, Harris-Laplacian, Hessian и Hessian-Laplacian], [SIFT, инвариантный SIFT, PCA-SIFT, PSIFT, управляемые фильтры, SPIN] [Linux, Windows и SunOS] исполняемые файлы.
• SUSAN Низкоуровневая обработка изображений , исходный код C.
• Онлайн-реализация детектора угла Харриса - IPOL

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

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

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

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