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

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

Обнаружение гребней - это попытка с помощью программного обеспечения найти гребни (или края) на изображении.

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \cos \beta ={\sqrt {{\frac {1}{2}}\left(1+{\frac {L_{xx}-L_{yy}}{\sqrt {(L_{xx}-L_{yy})^{2}+4L_{xy}^{2}}}}\right)}}}$, .${\displaystyle \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)}}}$

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

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

Соответственно, впадины масштаба - это набор точек${\displaystyle f(x,y)}$${\displaystyle t}$

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

В системе координат с направлением, параллельным градиенту изображения${\displaystyle (u,v)}$${\displaystyle v}$

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

куда

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

можно показать, что это определение гребня и впадины может быть эквивалентно ^[4] записано как

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

куда

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

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

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

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

Расчет гребней переменного масштаба из двухмерных изображений [ править ]

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

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

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

где - параметр масштаба в представлении масштабного пространства . Точно так же долина в масштабном пространстве - это набор точек, удовлетворяющих${\displaystyle t}$

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

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

В литературе предлагались различные меры прочности гребня. Когда Линдеберг (1996, 1998) ^[5] ввел термин гребень в масштабе пространства, он рассмотрел три меры прочности гребня:

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

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

выражается через -нормированные производные с${\displaystyle \gamma }$

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

• Квадрат -нормированной квадратной разности собственных значений${\displaystyle \gamma }$

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

• Квадрат -нормированной разности собственных значений${\displaystyle \gamma }$

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

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

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

История [ править ]

Понятие гребней и впадин на цифровых изображениях было введено Хараликом в 1983 году ^[10] и Кроули в связи с различием пирамид Гаусса в 1984 году. ^{[11] [12]} Применение дескрипторов гребней в анализе медицинских изображений широко изучалось Пайзером. и его коллеги ^{[13] [14] [15], что} привело к их понятию M-повторов. ^[16] Линдеберг также способствовал обнаружению гребней с введением${\displaystyle \gamma }$-нормализованные производные и гребни в пространстве масштаба, определенные путем локальной максимизации соответственно нормализованной главной главной кривизны матрицы Гессе (или других мер силы гребня) в пространстве и в масштабе. Эти понятия позже были развиты Steger et al., Применительно к выемке дорог. ^{[17] [18]} и сегментации кровеносных сосудов Frangi et al. ^[19], а также обнаружению криволинейных и трубчатых структур Sato et al. ^[20] и Криссиан и др. ^[21] Обзор некоторых классических определений гребня в фиксированном масштабе, включая отношения между ними, был дан Кендеринком и ван Доорном. ^[22]Обзор методов извлечения сосудов был представлен Кирбасом и Квеком. ^[23]

Определение гребней и впадин в N измерениях [ править ]

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

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

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

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

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

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

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

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

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

Максимальный масштабный хребет [ править ]

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

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

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

Связь между обнаружением кромки и обнаружением гребня [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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