Виявляння хребтів

В обробці зображень виявля́ння хребті́в (англ. ridge detection) — це намагання за допомогою програмного забезпечення знаходити в зображенні хребти́ (англ. ridges), визначені як криві, чиї точки є локальними максимумами функції, схожі на географічні хребти.

Для функції N змінних її хребти — це множина кривих, чиї точки є локальними максимумами в N − 1 вимірах. У цьому відношенні поняття точок хребта розширює поняття локального максимуму. Відповідно, поняття доли́н (англ. valleys) для функції можна визначити, замінивши умову локального максимуму умовою локального мінімуму. Об'єднання множин хребтів і множин долин, разом із пов'язаною множиною точок, званою множино́ю сполу́чників (англ. connector set), утворюють зв'язну множину кривих, які розбиваються, перетинаються або зустрічаються в критичних точках функції. Це спільне об'єднання множин називають відносною крити́чною множино́ю (англ. relative critical set) функції.

Множини хребтів, множини долин і відносні критичні множини подають важливу геометричну інформацію, притаманну функції. Певним чином вони забезпечують компактне подання важливих ознак функції, але питання про те, наскільки їх можливо використовувати, щоби визначати глобальні ознаки функції, залишається відкритим. Основна мотивація для створення процедур виявля́ння хребті́в і виявля́ння доли́н походить з аналізу зображень та комп'ютерного бачення, і полягає у вловлюванні внутрішностей видовжених об'єктів в області зображення. Пов'язані з хребтами подання в термінах вододілів використовували для сегментування зображень. Були також спроби вловлювати форми об'єктів за допомогою графових подань, що відображують хребти, долини та критичні точки в області зображення. Проте такі уявлення можуть бути дуже чутливими до шуму, якщо обчислюються лише в одному масштабі. Оскільки обчислення теорії простору масштабів залучають згортку гауссовим (згладжувальним) ядром, сподівалися, що використання багатомасштабових хребтів, долин та критичних точок у контексті теорії простору масштабів дозволить забезпечувати надійніше подання об'єктів (або форм) у зображенні.

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

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

Нехай $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$ для долин.

Розрахунок хребтів змінного масштабу з двовимірних зображень

Основна проблема поданого вище визначення хребта фіксованого масштабу полягає в тому, що воно може бути дуже чутливим до вибору рівня масштабу. Експерименти показують, що параметр масштабу гауссового ядра попереднього згладжування мусить бути ретельно підлаштовано до ширини хребтової структури в області зображення, щоби виявляч хребтів створював зв'язану криву, яка відображувала би структури в основі зображення. Для розв'язання цієї проблеми за відсутності попередньої інформації було введено поняття масштабопросторових хребтів (англ. scale-space ridges), яке розглядає параметр масштабу як невід'ємну властивість визначення хребта й дозволяє рівням масштабу змінюватися вздовж масштабопросторового хребта. Більше того, концепція масштабопросторового хребта також дозволяє підлаштовувати параметр масштабу до ширини хребтових структур в області зображення автоматично, фактично як наслідок добре сформульованого визначення. У літературі на основі цієї ідеї було запропоновано низку різних підходів.

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

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

де $t$ — параметр масштабу в масштабопросторовому поданні. Аналогічно, масштабопросторова долина (англ. scale-space valley) — це множина точок, які задовольняють

$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 року. Застосування хребтових описувачів до аналізу медичних зображень було детально досліджено Пайзером та його співробітниками, давши їхнє поняття M-подань (англ. M-reps). Ліндеберг також посприяв розвитку виявляння хребтів, запровадивши $\gamma$-нормовані похідні та масштабопросторові хребти, визначені з локальної максимізації належним чином нормованої головної кривини матриці Гессе (або інших мір вираженості хребта) над простором та над масштабом. Ці поняття пізніше було розвинуто із застосуванням до виділяння доріг Стегером та ін. та до сегментування кровоносних судин за Франджі та ін., а також для виявлення криволінійних і трубчастих структур Сато та ін. та Крисяном та ін. Огляд кількох класичних визначень хребтів у фіксованому масштабі, включно з відношеннями між ними, було запропоновано Кендерінком та ван Дорном. Огляд методів виділяння судин було запропоновано Кірбасом та Квеком.

Визначення хребтів і долин у N вимірах

У своєму найширшому сенсі поняття хребта узагальнює уявлення про локальний максимум дійсної функції. Точка $\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$-вимірній підмножині. Імовірно, це послаблення дозволяє множині точок, що задовольняють цей критерій, які ми назвемо хребтом, мати один ступінь свободи, принаймні в загальному випадку. Це означає, що множина точок хребта утворюватиме одновимірне геометричне місце точок, або криву хребта (англ. ridge curve). Зверніть увагу, що вищезазначене можливо видозмінити, узагальнивши це уявлення до локальних мінімумів й отримавши те, що можна було би назвати одновимірними кривими долин.

Наступне визначення хребта відповідає книзі Еберлі, й його можливо розглядати як узагальнення деяких із вищезгаданих. Нехай $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}$ є точкою на 1-вимірному хребті $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$.

Багато в чому ці визначення природно узагальнюють визначення локального максимуму функції. Властивості гребнів максимальної опуклості (англ. maximal convexity ridges) покладено на тверду математичну основу Деймоном та Міллером. Їхні властивості в однопараметрових сімействах було визначено Келлером.

Максимальномасштабовий хребет

Наступне визначення можливо простежити до Фріча, який цікавився виділянням геометричної інформації про фігури у двовимірних зображеннях у відтінках сірого. Фріч обробляв своє зображення фільтром «серединності» (англ. "medialness"), який давав йому інформацію, аналогічну даним «віддаленості від меж» (англ. "distant to the boundary") у просторі масштабів. Хребти цього зображення, проєктовані на первинне зображення, мали бути аналогічними кістякові форми (наприклад, блюмовій серединній осі) первинного зображення.

Далі наведено визначення максимальномасштабового хребта (англ. maximal scale ridge) функції трьох змінних, однією з яких є параметр «масштаб». Одне, чого ми хочемо дотриматися в цьому визначенні, це якщо $(\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$

тоді як напрямна похідна другого порядку $L_{v}$ в напрямі $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$

(додаткову інформацію див. у статті про виявляння контурів). Примітно, що отримані таким чином контури є хребтами величини градієнта.

Див. також

• Виявляння плям
• Комп'ютерне бачення
• Виявляння контурів
• Виявляння ознак (комп'ютерне бачення)
• Виявляння особливих точок
• Простір масштабів