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

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

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

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

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

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

предатавления в масштабном пространстве функции с преобразованием координат (вращением), применённым к операторам локальной производной по направлению,

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

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

Соответственно, долины при масштабе представляют собой множество точек

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

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

где

и знак определяет полярность — для гребней и для долин.

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

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

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

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

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

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

Главная кривизна

выраженная в терминах - нормализованной производной с .

Квадрат -нормализованной разницы квадратов собственных значений

Квадрат - нормализованной разницы собственных значений

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

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

История

Понятие гребней и долин в цифровых изображениях было предложено в 1983 году, а Кроули — в 1984 году в контексте пирамид разности гауссианов. Применение дескрипторов гребней для анализа медицинских изображений широко исследовалось Пизером и его коллегами, что привело к созданию их концепции M-репрезентаций. Развитие выделения гребней также продолжил Линдеберг, который ввёл -нормализованные производные и гребни в масштабном пространстве, определяемые локальной максимизацией соответствующим образом нормализованной главной кривизны матрицы Гессе (или других мер силы гребня) в пространстве и по масштабу. Эти концепции позднее были развиты и применены для извлечения дорог Стегером и соавторами и для сегментации кровеносных сосудов Франги и соавторами, а также для обнаружения криволинейных и трубчатых структур Сато и соавторами и Криссианом и соавторами. Обзор нескольких классических определений гребней на фиксированном масштабе, включая взаимосвязи между ними, был представлен Коэндеринком и ван Доорном. Обзор методов извлечения сосудов был представлен Кирбасом и Квеком.

Определение гребней и долин в N-мерных пространствах

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

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

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

Точка является точкой на одномерном гребне , если выполняются следующие условия:

, и for .

Это уточняет концепцию, согласно которой функция , ограниченная этим конкретным -мерным подпространством, имеет локальный максимум в точке .

Это определение естественным образом обобщается на k-мерный гребень следующим образом: точка является точкой на k-мерном гребне функции , если выполняются следующие условия:

, для .

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

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

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

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

и , и .

Связь между выделением границ и выделением гребней