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

Чтобы узнать о других функциях, называемых хребтами, см. Ридж (значения) .

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

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

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

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

Дифференциальное геометрическое определение хребтов и впадин в фиксированном масштабе на двухмерном изображении

Позволять $f(x,y)$ обозначим двумерную функцию, и пусть $L$ быть масштабного пространства представлением $f(x,y)$ полученный путем свертки $f(x,y)$ с функцией Гаусса

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

Кроме того, пусть $L_{pp}$ и $L_{qq}$ обозначим собственные значения матрицы Гессе

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

в масштабном пространстве представления $L$ с преобразованием координат (поворотом), примененным к локальным операторам производной по направлению,

$\partial _{p}=\sin \beta \partial _{x}-\cos \beta \partial _{y},\partial _{q}=\cos \beta \partial _{x}+\sin \beta \partial _{y}$

где p и q — координаты повернутой системы координат.

Можно показать, что смешанная производная $L_{pq}$ в преобразованной системе координат равна нулю, если мы выберем

$\cos \beta ={\sqrt {{\frac {1}{2}}\left(1+{\frac {L_{xx}-L_{yy}}{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}}\right)}}$, $\sin \beta =\operatorname {sgn}(L_{xy}){\sqrt {{\frac {1}{2}}\left(1-{\frac {L_{xx}-L_{yy}}{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}}\right)}}$.

Тогда формальное дифференциально-геометрическое определение гребней $f(x,y)$ в фиксированном масштабе $t$ может быть выражен как набор точек, удовлетворяющих

$L_{p}=0,L_{pp}\leq 0,|L_{pp}|\geq |L_{qq}|.$

Соответственно, долины р. $f(x,y)$ в масштабе $t$ это набор точек

$L_{q}=0,L_{qq}\geq 0,|L_{qq}|\geq |L_{pp}|.$

С точки зрения $(u,v)$ система координат с $v$ направление, параллельное градиенту изображения

$\partial _{u}=\sin \alpha \partial _{x}-\cos \alpha \partial _{y},\partial _{v}=\cos \alpha \partial _{x}+\sin \alpha \partial _{y}$

где

$\cos \alpha ={\frac {L_{x}}{\sqrt {L_{x}^{2}+L_{y}^{2}}}},\sin \alpha ={\frac {L_{y}}{\sqrt {L_{x}^{2}+L_{y}^{2}}}}$

можно показать, что это определение хребта и долины вместо этого может быть эквивалентно написано как

$L_{uv}=0,L_{uu}^{2}-L_{vv}^{2}\geq 0$

где

$L_{v}^{2}L_{uu}=L_{x}^{2}L_{yy}-2L_{x}L_{y}L_{xy}+L_{y}^{2}L_{xx},$

$L_{v}^{2}L_{uv}=L_{x}L_{y}(L_{xx}-L_{yy})-(L_{x}^{2}-L_{y}^{2})L_{xy},$

$L_{v}^{2}L_{vv}=L_{x}^{2}L_{xx}+2L_{x}L_{y}L_{xy}+L_{y}^{2}L_{yy}$

и знак $L_{uu}$ определяет полярность; $L_{uu}<0$ для гребней и $L_{uu}>0$ для долин.

двумерным

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

Позволять $R(x,y,t)$ обозначают меру прочности гребня (указывается ниже). Тогда для двумерного изображения гребень масштабного пространства — это набор точек, удовлетворяющих условиям

$L_{p}=0,L_{pp}\leq 0,\partial _{t}(R)=0,\partial _{tt}(R)\leq 0,$

где $t$ — параметр масштаба в представлении в масштабном пространстве . Аналогично, долина масштабного пространства — это набор точек, которые удовлетворяют

$L_{q}=0,L_{qq}\geq 0,\partial _{t}(R)=0,\partial _{tt}(R)\leq 0.$

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

В литературе предложены различные меры прочности гребня. Когда Линдеберг (1996, 1998) введя термин «масштабно-пространственный гребень», он рассмотрел три меры прочности гребня:

• Основная главная кривизна

$L_{pp,\gamma -norm}={\frac {t^{\gamma }}{2}}\left(L_{xx}+L_{yy}-{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}\right)$

выражается в терминах $\gamma$-нормализованные производные с

$\partial _{\xi }=t^{\gamma /2}\partial _{x},\partial _{\eta }=t^{\gamma /2}\partial _{y}$.

• Площадь $\gamma$-нормализованная квадратичная разность собственных значений

$N_{\gamma -norm}=\left(L_{pp,\gamma -norm}^{2}-L_{qq,\gamma -norm}^{2}\right)^{2}=t^{4\gamma }(L_{xx}+L_{yy})^{2}\left((L_{xx}-L_{yy})^{2}+4L_{xy}^{2}\right).$

• Площадь $\gamma$-нормализованная разность собственных значений

$A_{\gamma -norm}=\left(L_{pp,\gamma -norm}-L_{qq,\gamma -norm}\right)^{2}=t^{2\gamma }\left((L_{xx}-L_{yy})^{2}+4L_{xy}^{2}\right).$

Понятие $\gamma$Здесь важна нормализованная производная, поскольку она позволяет правильно откалибровать алгоритмы детектора гребней и впадин. Требуя, чтобы для одномерного гауссовского гребня, встроенного в два (или три измерения), масштаб обнаружения был равен ширине структуры гребня при измерении в единицах длины (требование соответствия размера фильтра обнаружения и структуру образа, на которую он реагирует), следует, что следует выбрать $\gamma =3/4$. Из этих трех показателей прочности гребня первый объект $L_{pp,\gamma -norm}$ представляет собой универсальный измеритель прочности гребней, который можно использовать во многих приложениях, таких как обнаружение кровеносных сосудов и прокладка дорог. Тем не менее, сущность $A_{\gamma -norm}$ использовался в таких приложениях, как улучшение отпечатков пальцев, в реальном времени отслеживание рук и распознавание жестов а также для моделирования локальной статистики изображений для обнаружения и отслеживания людей на изображениях и видео.

Существуют также другие тесно связанные определения гребня, в которых используются нормализованные производные с неявным предположением о $\gamma =1$. Разработайте эти подходы более подробно. При обнаружении гребней с $\gamma =1$, однако масштаб обнаружения будет в два раза больше, чем для $\gamma =3/4$, что приводит к большему искажению формы и снижению способности захватывать хребты и впадины с соседними мешающими структурами изображения в области изображения.

История

Понятие хребтов и долин на цифровых изображениях было введено Хараликом в 1983 году. и Кроули о различии пирамид Гаусса в 1984 году. Применение дескрипторов гребней для анализа медицинских изображений было тщательно изучено Пайзером и его коллегами. в результате появилось понятие М-повторений. Обнаружение гребней также было усовершенствовано Линдебергом с введением $\gamma$-нормализованные производные и гребни масштабного пространства, определяемые путем локальной максимизации соответствующим образом нормализованной главной главной кривизны матрицы Гессе (или других мер прочности гребней) в пространстве и по масштабу. Эти понятия позже были развиты Стегером и др. применительно к прокладке дорог. и сегментации кровеносных сосудов Frangi et al. а также обнаружению криволинейных и трубчатых структур Сато и др. and Krissian et al. Обзор нескольких классических определений гребней в фиксированном масштабе, включая отношения между ними, был дан Кендеринком и ван Дорном. Обзор методов извлечения сосудов был представлен Кирбасом и Квеком.

хребтов и впадин в

В самом широком смысле понятие риджа обобщает идею локального максимума действительной функции. точка $\mathbf {x} _{0}$ в области определения функции $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ является локальным максимумом функции, если существует расстояние $\delta >0$ со свойством, что если $\mathbf {x}$ находится внутри $\delta$ единицы $\mathbf {x} _{0}$, затем $f(\mathbf {x} )<f(\mathbf {x} _{0})$. Хорошо известно, что критические точки, среди которых локальные максимумы являются лишь одним из типов, являются изолированными точками в области определения функции во всех ситуациях, кроме самых необычных ( т. е . нетиповых случаев).

Рассмотрите возможность смягчения состояния, которое $f(\mathbf {x} )<f(\mathbf {x} _{0})$ для $\mathbf {x}$ во всем районе г. $\mathbf {x} _{0}$ слегка требовать только, чтобы это держалось $n-1$ размерное подмножество. Предположительно, это расслабление позволяет множеству точек, удовлетворяющих критериям, которое мы назовем гребнем, иметь единственную степень свободы, по крайней мере, в общем случае. Это означает, что набор точек гребня будет образовывать одномерный локус или кривую гребня. Обратите внимание, что вышеизложенное можно изменить, чтобы обобщить идею на локальные минимумы и получить в результате то, что можно было бы назвать одномерными кривыми долины.

Следующее определение гребня следует книге Эберли. и его можно рассматривать как обобщение некоторых из вышеупомянутых определений гребней. Позволять $U\subset \mathbb {R} ^{n}$ быть открытым множеством, и $f:U\rightarrow \mathbb {R}$ быть гладким. Позволять $\mathbf {x} _{0}\in U$. Позволять $\nabla _{\mathbf {x} _{0}}f$ быть градиентом $f$ в $\mathbf {x} _{0}$, и пусть $H_{\mathbf {x} _{0}}(f)$ быть $n\times n$ Матрица Гессе $f$ в $\mathbf {x} _{0}$. Позволять $\lambda _{1}\leq \lambda _{2}\leq \cdots \leq \lambda _{n}$ быть $n$ упорядоченные собственные значения $H_{\mathbf {x} _{0}}(f)$ и пусть $\mathbf {e} _{i}$ быть единичным собственным вектором в собственном пространстве для $\lambda _{i}$. (Для этого следует предположить, что все собственные значения различны.)

Суть $\mathbf {x} _{0}$ является точкой на одномерном гребне $f$ если выполняются следующие условия:

1. $\lambda _{n-1}<0$, и
2. $\nabla _{\mathbf {x} _{0}}f\cdot \mathbf {e} _{i}=0$ для $i=1,2,\ldots ,n-1$.

Это уточняет концепцию, согласно которой $f$ ограничено этим конкретным $n-1$-мерное подпространство имеет локальный максимум в точке $\mathbf {x} _{0}$.

Это определение естественным образом обобщается на k -мерный гребень следующим образом: точка $\mathbf {x} _{0}$ является точкой на k -мерном гребне $f$ если выполняются следующие условия:

1. $\lambda _{n-k}<0$, и
2. $\nabla _{\mathbf {x} _{0}}f\cdot \mathbf {e} _{i}=0$ для $i=1,2,\ldots ,n-k$.

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

Гребень максимального масштаба

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

Далее следует определение максимального гребня масштаба функции трех переменных, одна из которых является параметром «масштаба». Мы хотим, чтобы это определение было верным, если $(\mathbf {x} ,\sigma )$ является точкой на этом гребне, то значение функции в этой точке максимально в размерности масштаба. Позволять $f(\mathbf {x} ,\sigma )$ быть гладкой дифференцируемой функцией на $U\subset \mathbb {R} ^{2}\times \mathbb {R} _{+}$. $(\mathbf {x} ,\sigma )$ является точкой на ребре максимального масштаба тогда и только тогда, когда

1. ${\frac {\partial f}{\partial \sigma }}=0$ и ${\frac {\partial ^{2}f}{\partial \sigma ^{2}}}<0$, и
2. $\nabla f\cdot \mathbf {e} _{1}=0$ и $\mathbf {e} _{1}^{t}H(f)\mathbf {e} _{1}<0$.

Взаимосвязь между обнаружением краев и обнаружением гребней

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

С точки зрения определений, существует тесная связь между детекторами краев и детекторами гребней. С формулировкой немаксимального значения, данной Кэнни, считается, что края определяются как точки, в которых величина градиента принимает локальный максимум в направлении градиента. Следуя дифференциально-геометрическому способу выражения этого определения, мы можем в вышеупомянутом $(u,v)$-система координат утверждает, что величина градиента представления в масштабном пространстве, равная производной по направлению первого порядка в $v$-направление $L_{v}$, должна иметь производную первого порядка по направлению $v$-направление равно нулю

$\partial _{v}(L_{v})=0$

а производная второго порядка по направлению $v$-направление $L_{v}$ должно быть отрицательным, т.е.

$\partial _{vv}(L_{v})\leq 0$.

Записано в виде явного выражения через локальные частные производные. $L_{x}$, $L_{y}$ ... $L_{yyy}$, это определение края может быть выражено как кривые перехода через нуль дифференциального инварианта

$L_{v}^{2}L_{vv}=L_{x}^{2}\,L_{xx}+2\,L_{x}\,L_{y}\,L_{xy}+L_{y}^{2}\,L_{yy}=0,$

которые удовлетворяют знаковому условию следующего дифференциального инварианта

$L_{v}^{3}L_{vvv}=L_{x}^{3}\,L_{xxx}+3\,L_{x}^{2}\,L_{y}\,L_{xxy}+3\,L_{x}\,L_{y}^{2}\,L_{xyy}+L_{y}^{3}\,L_{yyy}\leq 0$

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

См. также

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