В обробці зображень виявля́ння хребті́в () — це намагання за допомогою програмного забезпечення знаходити в хребти́ (), визначені як криві, чиї точки є локальними максимумами функції, схожі на географічні хребти.
Для функції N змінних її хребти — це множина кривих, чиї точки є локальними максимумами в N − 1 вимірах. У цьому відношенні поняття точок хребта розширює поняття локального максимуму. Відповідно, поняття доли́н () для функції можна визначити, замінивши умову локального максимуму умовою локального мінімуму. Об'єднання множин хребтів і множин долин, разом із пов'язаною множиною точок, званою множино́ю сполу́чників (), утворюють зв'язну множину кривих, які розбиваються, перетинаються або зустрічаються в критичних точках функції. Це спільне об'єднання множин називають відносною крити́чною множино́ю () функції. Miller, J. Relative Critical Sets in and Applications to Image Analysis. Ph.D. Dissertation. University of North Carolina. 1998.
Множини хребтів, множини долин і відносні критичні множини подають важливу геометричну інформацію, притаманну функції. Певним чином вони забезпечують компактне подання важливих ознак функції, але питання про те, наскільки їх можливо використовувати, щоби визначати глобальні ознаки функції, залишається відкритим. Основна мотивація для створення процедур виявля́ння хребті́в і виявля́ння доли́н походить з та комп'ютерного бачення, і полягає у вловлюванні внутрішностей видовжених об'єктів в області зображення. Пов'язані з хребтами подання в термінах використовували для сегментування зображень. Були також спроби вловлювати форми об'єктів за допомогою графових подань, що відображують хребти, долини та критичні точки в області зображення. Проте такі уявлення можуть бути дуже чутливими до шуму, якщо обчислюються лише в одному масштабі. Оскільки обчислення теорії простору масштабів залучають згортку гауссовим (згладжувальним) ядром, сподівалися, що використання багатомасштабових хребтів, долин та критичних точок у контексті теорії простору масштабів дозволить забезпечувати надійніше подання об'єктів (або форм) у зображенні.
У цьому відношенні хребти та долини можливо розглядати як доповнення до природних особливих точок або точок локальних екстремумів. За належно визначених понять, хребти та долини в (або в якомусь іншому поданні, отриманому з ландшафту яскравості) можуть утворювати масштабоінваріантний кістяк для утворення просторових обмежень на локальний вигляд з низкою якісних подібностей до того, як серединноосьове перетворення Блюма забезпечує для бінарних зображень. У типових застосуваннях описувачі хребтів і долин часто використовують для виявляння доріг на аерофотознімках та для виявляння кровоносних судин на чи тривимірних магнітно-резонансних зображеннях.
Диференціальногеометричне визначення хребтів і долин у фіксованому масштабі на двовимірному зображенні
Нехай позначує двовимірну функцію, і нехай буде масштабопросторовим поданням , отриманим згортанням гауссовою функцією
.
Крім того, нехай та позначують власні значення матриці Гессе
масштабопросторового подання з перетворенням координат (повертанням), застосованим до операторів локальних напрямних похідних,
де p та q — координати повернутої системи координат.
Можливо показати, що змішана похідна у перетвореній системі координат нульова, якщо ми оберемо
, .
Тоді формальне диференціальногеометричне визначення хребтів у фіксованому масштабі може бути виражено як набір точок, які задовольняють
Відповідно, долини в масштабі — множина точок
В системі координат з напрямком , паралельним градієнтові зображення,
де
можливо показати, що це визначення хребтів і долин можливо натомість еквівалентно записати як
де
а знак визначає полярність; для хребтів і для долин.
Розрахунок хребтів змінного масштабу з двовимірних зображень
Основна проблема поданого вище визначення хребта фіксованого масштабу полягає в тому, що воно може бути дуже чутливим до вибору рівня масштабу. Експерименти показують, що параметр масштабу гауссового ядра попереднього згладжування мусить бути ретельно підлаштовано до ширини хребтової структури в області зображення, щоби виявляч хребтів створював зв'язану криву, яка відображувала би структури в основі зображення. Для розв'язання цієї проблеми за відсутності попередньої інформації було введено поняття масштабопросторових хребтів (), яке розглядає параметр масштабу як невід'ємну властивість визначення хребта й дозволяє рівням масштабу змінюватися вздовж масштабопросторового хребта. Більше того, концепція масштабопросторового хребта також дозволяє підлаштовувати параметр масштабу до ширини хребтових структур в області зображення автоматично, фактично як наслідок добре сформульованого визначення. У літературі на основі цієї ідеї було запропоновано низку різних підходів.
Нехай позначує міру вираженості хребта (яку буде вказано нижче). Тоді для двовимірного зображення масштабопросторовий гребінь — це множина точок, які задовольняють
де — параметр масштабу в масштабопросторовому поданні. Аналогічно, масштабопросторова долина () — це множина точок, які задовольняють
Безпосереднім наслідком цього визначення є те, що для двовимірного зображення концепція масштабопросторових хребтів вимітає множину одновимірних кривих у тривимірному просторі масштабів, де параметрові масштабу дозволено змінюватися вздовж масштабопросторового хребта (чи масштабопросторової долини). Описувачем хребта в області зображення тоді буде проєкція цієї тривимірної кривої на двовимірну площину зображення, де інформацію про властивий масштаб у кожній точці хребта можливо використовувати як природну оцінку ширини хребтової структури в області зображення в околі цієї точки.
У літературі пропонують різні міри хребтової вираженості. Коли Ліндеберг (1996, 1998)<ref> Ранішу версію подано на конференції IEEE з розпізнавання образів та комп'ютерного бачення, CVPR'''96, Сан-Франциско, Каліфорнія, с. 465—470, червень 1996 </ref> запровадив термін «масштабопросторовий хребет», він розглядав три міри хребтової вираженості:
Основна головна кривина
виражена в термінах -нормованих похідних через .
Квадрат різниці квадратів -нормованих власних значень
Квадрат різниці -нормованих власних значень
Поняття -нормованих похідних тут важливе, оскільки дозволяє алгоритмам виявляння хребтів і долин належно калібруватися. З вимоги, щоби для одновимірного гауссового хребта, вкладеного в два (або три) виміри, масштаб виявляння дорівнював ширині хребтової структури при вимірюванні в одиницях довжини (вимога відповідності між розмірами фільтра виявляння та структурою зображення, на яку він реагує), випливає, що слід обирати . З цих трьох мір вираженості хребта перша сутність є мірою вираженості хребта загального призначення з багатьма застосуваннями, такими як виявляння кровоносних судин і виділяння доріг. Проте сутність використовували в таких застосуваннях як покращення відбитків пальців, та у реальному часі,L. Bretzner, I. Laptev and T. Lindeberg: Hand Gesture Recognition using Multi-Scale Colour Features, Hierarchical Models and Particle Filtering, Proc. IEEE Conference on Face and Gesture 2002, Washington DC, 423–428. а також для моделювання локальних статистик зображень для виявляння та відстежування людей у зображеннях та відео.
Існують також й інші тісно пов'язані визначення хребта, які використовують нормовані похідні з неявним припущенням .J. Furst and J. Miller, "The Maximal Scale Ridge: Incorporating Scale in the Ridge Definition ", Scale Space Theory in Computer Vision: Proceedings of the First International Conference on, Scale Space '97, pp. 93–104. Springer Lecture Notes in Computer Science, vol. 1682. Проробити ці підходи докладніше. Проте при виявлянні хребтів з масштаб виявляння буде вдвічі більшим, аніж для , що призводить до більших викривлень форми та нижчої здатності вловлювати хребти та долини з сусідніми завадними структурами зображення в його області.
Історія
Поняття хребтів і долин у цифрових зображеннях було запроваджено 1983 року та Кроулі стосовно пірамід різниць гауссіанів 1984 року. Застосування хребтових описувачів до аналізу медичних зображень було детально досліджено Пайзером та його співробітниками, давши їхнє поняття M-подань ().S. Pizer, S. Joshi, T. Fletcher, M. Styner, G. Tracton, J. Chen (2001) "Segmentation of Single-Figure Objects by Deformable M-reps", Proceedings of the 4th International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer Lecture Notes In Computer Science; Vol. 2208, pp. 862–871 Ліндеберг також посприяв розвитку виявляння хребтів, запровадивши -нормовані похідні та масштабопросторові хребти, визначені з локальної максимізації належним чином нормованої головної кривини матриці Гессе (або інших мір вираженості хребта) над простором та над масштабом. Ці поняття пізніше було розвинуто із застосуванням до виділяння доріг Стегером та ін. та до сегментування кровоносних судин за Франджі та ін., а також для виявлення криволінійних і трубчастих структур Сато та ін. та Крисяном та ін. Огляд кількох класичних визначень хребтів у фіксованому масштабі, включно з відношеннями між ними, було запропоновано Кендерінком та ван Дорном. Огляд методів виділяння судин було запропоновано Кірбасом та Квеком.
Визначення хребтів і долин у N вимірах
У своєму найширшому сенсі поняття хребта узагальнює уявлення про локальний максимум дійсної функції. Точка в області визначення функції є локальним максимумом цієї функції, якщо існує відстань , така, що якщо знаходиться всередині одиниць від , то . Добре відомо, що критичні точки, для яких локальні максимуми є лише одним з їхніх типів, це ізольовані точки в області визначення функції у всіх ситуаціях, окрім найнезвичніших (тобто незагальних випадків).
Розгляньмо деяке послаблення умови для у всьому околі до вимоги лише того, щоби вона дотримувалася в -вимірній підмножині. Імовірно, це послаблення дозволяє множині точок, що задовольняють цей критерій, які ми назвемо хребтом, мати один ступінь свободи, принаймні в загальному випадку. Це означає, що множина точок хребта утворюватиме одновимірне геометричне місце точок, або криву хребта (). Зверніть увагу, що вищезазначене можливо видозмінити, узагальнивши це уявлення до локальних мінімумів й отримавши те, що можна було би назвати одновимірними кривими долин.
Наступне визначення хребта відповідає книзі Еберлі, й його можливо розглядати як узагальнення деяких із вищезгаданих. Нехай — відкрита множина, а гладенька. Нехай . Нехай — градієнт в , і нехай — матриця Гессе функції в . Нехай — це впорядкованих власних значень , і нехай — одиничний власний вектор у власному просторі для . (Для цього слід виходити з відмінності всі власних значень.)
Точка є точкою на 1-вимірному хребті , якщо виконуються такі умови:
, і для .
Це уточнює поняття, що , обмежена цим конкретним -вимірним підпростором, має локальний максимум в .
Це визначення природно узагальнюється на k -вимірний хребет наступним чином: точка є точкою на k''-вимірному хребті , якщо виконуються наступні умови:
, і для .
Багато в чому ці визначення природно узагальнюють визначення локального максимуму функції. Властивості гребнів максимальної опуклості () покладено на тверду математичну основу Деймоном та Міллером. Їхні властивості в однопараметрових сімействах було визначено Келлером.Kerrel, R. Generic Transitions of Relative Critical Sets in Parameterized Families with Applications to Image Analysis. University of North Carolina. 1999.
Максимальномасштабовий хребет