Перегляд вихідного коду сторінки Виявляння хребтів

{{Виявляння ознак (комп'ютерний зір)}}
{{For|інші поняття, що називають хребтами,|Хребет (значення)}}
{{Technical|дата=травень 2022}}

В [[Обробка зображень|обробці зображень]] '''виявля́ння хребті́в''' ({{lang-en|ridge detection}})&nbsp;— це намагання за допомогою програмного забезпечення знаходити в [[Зображення|зображенні]] '''хребти́''' ({{lang-en|ridges}}), визначені як криві, чиї точки є [[Локальний максимум|локальними максимумами]] функції, схожі на географічні [[Хребет (географія)|хребти]].

Для функції ''N'' змінних її хребти&nbsp;— це множина кривих, чиї точки є локальними максимумами в ''N'' − 1 вимірах. У цьому відношенні поняття точок хребта розширює поняття [[Локальний максимум|локального максимуму]]. Відповідно, поняття '''доли́н''' ({{lang-en|valleys}}) для функції можна визначити, замінивши умову локального максимуму умовою [[Локальний мінімум|локального мінімуму]]. Об'єднання множин хребтів і множин долин, разом із пов'язаною множиною точок, званою '''множино́ю сполу́чників''' ({{lang-en|connector set}}), утворюють зв'язну множину кривих, які розбиваються, перетинаються або зустрічаються в критичних точках функції. Це спільне об'єднання множин називають '''відносною крити́чною множино́ю''' ({{lang-en|relative critical set}}) функції.<ref name="Damon99">{{cite journal |author=Damon, J. |title=Properties of Ridges and Cores in Two-Dimensional Images |journal=J Math Imaging Vis |volume=10 |issue=2 |doi=10.1023/A:1008379107611 |pages=163–174 |date=March 1999 }} {{ref-en}}</ref><ref name="Miller98">Miller, J. ''Relative Critical Sets in <math>\mathbb{R}^n</math> and Applications to Image Analysis.'' Ph.D. Dissertation.  University of North Carolina. 1998. {{ref-en}}</ref>

Множини хребтів, множини долин і відносні критичні множини подають важливу геометричну інформацію, притаманну функції. Певним чином вони забезпечують компактне подання важливих ознак функції, але питання про те, наскільки їх можливо використовувати, щоби визначати глобальні ознаки функції, залишається відкритим. Основна мотивація для створення процедур '''виявля́ння хребті́в''' і '''виявля́ння доли́н''' походить з {{нп|Аналіз зображень|аналізу зображень||Image analysis}} та [[Комп'ютерне бачення|комп'ютерного бачення]], і полягає у вловлюванні внутрішностей видовжених об'єктів в області зображення. Пов'язані з хребтами подання в термінах {{нп|Вододіл (алгоритм)|вододілів||Watershed (algorithm)}} використовували для [[сегментування зображень]]. Були також спроби вловлювати форми об'єктів за допомогою графових подань, що відображують хребти, долини та критичні точки в області зображення. Проте такі уявлення можуть бути дуже чутливими до шуму, якщо обчислюються лише в одному масштабі. Оскільки обчислення теорії простору масштабів залучають згортку гауссовим (згладжувальним) ядром, сподівалися, що використання багатомасштабових хребтів, долин та критичних точок у контексті теорії [[Простір масштабів|простору масштабів]] дозволить забезпечувати надійніше подання об'єктів (або форм) у зображенні.

У цьому відношенні хребти та долини можливо розглядати як доповнення до природних [[Виявляння особливих точок|особливих точок]] або точок локальних екстремумів. За належно визначених понять, хребти та долини в {{нпні|Ландшафт яскравості|ландшафті яскравості||Intensity landscape}} (або в якомусь іншому поданні, отриманому з ландшафту яскравості) можуть утворювати [[Інваріантність щодо масштабу|масштабоінваріантний]] [[Кістяк (множина точок)|кістяк]] для утворення просторових обмежень на локальний вигляд з низкою якісних подібностей до того, як [[Серединна вісь|серединноосьове перетворення]] Блюма забезпечує {{нпні|кістяк форми|||Shape skeleton}} для [[Бінарне зображення|бінарних зображень]]. У типових застосуваннях описувачі хребтів і долин часто використовують для виявляння доріг на [[Аерофотознімок|аерофотознімках]] та для виявляння [[Кровоносні судини|кровоносних судин]] на {{нп|Фотографування очного дна|зображеннях очного дна||Fundus photography}} чи тривимірних [[Магнітно-резонансна томографія|магнітно-резонансних зображеннях]].

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

Нехай <math>f(x, y)</math> позначує двовимірну функцію, і нехай <math>L</math> буде [[Простір масштабів|масштабопросторовим поданням]] <math>f(x, y)</math>, отриманим згортанням <math>f(x, y)</math> гауссовою функцією

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

Крім того, нехай <math>L_{pp}</math> та <math>L_{qq}</math> позначують [[власні значення]] [[Матриця Гесе|матриці Гессе]]

: <math>H = \begin{bmatrix}
L_{xx} & L_{xy} \\ 
L_{xy} & L_{yy}
\end{bmatrix}</math>

[[Простір масштабів|масштабопросторового подання]] <math>L</math> з перетворенням координат (повертанням), застосованим до операторів локальних напрямних похідних,

: <math>\partial_p = \sin \beta \partial_x - \cos \beta \partial_y, \partial_q = \cos \beta \partial_x + \sin \beta \partial_y </math>

де ''p'' та ''q''&nbsp;— координати повернутої системи координат.

Можливо показати, що змішана похідна <math>L_{pq}</math> у перетвореній системі координат нульова, якщо ми оберемо

: <math>\cos \beta = \sqrt{\frac{1}{2} \left( 1 + \frac{L_{xx}-L_{yy}}{\sqrt{(L_{xx}-L_{yy})^2 + 4 L_{xy}^2}} \right)}</math>, <math> \sin \beta = \sgn(L_{xy}) \sqrt{\frac{1}{2} \left( 1 - \frac{L_{xx}-L_{yy}}{\sqrt{(L_{xx}-L_{yy})^2 + 4 L_{xy}^2}} \right)} </math>.

Тоді формальне диференціальногеометричне визначення хребтів <math>f(x, y)</math> у фіксованому масштабі <math>t</math> може бути виражено як набір точок, які задовольняють<ref>{{cite encyclopedia
| author=T. Lindeberg
| title=Scale-space
| encyclopedia=Encyclopedia of Computer Science and Engineering
| editor=Benjamin Wah
| publisher=John Wiley and Sons
| volume=IV
| pages=2495–2504
| year=2009
| doi=10.1002/9780470050118.ecse609
| url=http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A441147&dswid=1804
| isbn=978-0470050118
| accessdate=15 травня 2022
| archivedate=15 травня 2022
| archiveurl=https://web.archive.org/web/20220515191835/http://kth.diva-portal.org/smash/record.jsf?pid=diva2:441147&dswid=1804
}} {{ref-en}}</ref>

: <math>L_{p} = 0, L_{pp} \leq 0, |L_{pp}| \geq |L_{qq}|.</math>

Відповідно, долини <math>f(x, y)</math> в масштабі <math>t</math>&nbsp;— множина точок

: <math>L_{q} = 0, L_{qq} \geq 0, |L_{qq}| \geq |L_{pp}|.</math>

В системі координат <math>(u, v)</math> з напрямком <math>v</math>, паралельним градієнтові зображення,

: <math>\partial_u = \sin \alpha \partial_x - \cos \alpha \partial_y, \partial_v = \cos \alpha \partial_x + \sin \alpha \partial_y </math>

де

: <math>\cos \alpha = \frac{L_x}{\sqrt{L_x^2 + L_y^2}}, \sin \alpha = \frac{L_y}{\sqrt{L_x^2 + L_y^2}} </math>

можливо показати, що це визначення хребтів і долин можливо натомість еквівалентно<ref>{{cite journal |author=Lindeberg, T |title=Scale-space theory: A basic tool for analysing structures at different scales |journal=Journal of Applied Statistics |volume=21 |issue=2 |pages=224–270 |year=1994 |url=http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A457189&dswid=7617 |doi=10.1080/757582976 |accessdate=15 травня 2022 |archive-date=15 травня 2022 |archive-url=https://web.archive.org/web/20220515181807/http://kth.diva-portal.org/smash/record.jsf?pid=diva2:457189&dswid=7617 }} {{ref-en}}</ref> записати як

: <math> L_{uv} = 0, L_{uu}^2 - L_{vv}^2 \geq 0 </math>

де

: <math>L_v^2 L_{uu} = L_x^2 L_{yy} - 2 L_x L_y L_{xy} + L_y^2 L_{xx},</math>
: <math>L_v^2 L_{uv} = L_x L_y (L_{xx} - L_{yy}) - (L_x^2 - L_y^2) L_{xy}, </math>
: <math>L_v^2 L_{vv} = L_x^2 L_{xx} + 2 L_x L_y L_{xy} + L_y^2 L_{yy} </math>

а знак <math>L_{uu}</math> визначає полярність; <math>L_{uu}<0</math> для хребтів і <math>L_{uu}>0</math> для долин.

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

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

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

: <math>L_{p} = 0, L_{pp} \leq 0, \partial_t(R) = 0, \partial_{tt}(R) \leq 0,</math>

де <math>t</math>&nbsp;— параметр масштабу в [[Простір масштабів|масштабопросторовому поданні]]. Аналогічно, ''масштабопросторова'' ''долина'' ({{lang-en|scale-space valley}})&nbsp;— це множина точок, які задовольняють

: <math>L_{q} = 0, L_{qq} \geq 0, \partial_t(R) = 0, \partial_{tt}(R) \leq 0.</math>

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

У літературі пропонують різні міри хребтової вираженості. Коли Ліндеберг (1996, 1998)<ref>{{cite journal |doi=10.1023/A:1008097225773 |author=Lindeberg, T. |title=Edge detection and ridge detection with automatic scale selection |journal=International Journal of Computer Vision |volume=30 |issue=2 |pages=117–154 |year=1998 |url=http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A452310&dswid=-5900}} Ранішу версію подано на конференції ''IEEE'' з розпізнавання образів та комп'ютерного бачення, ''CVPR'''96, Сан-Франциско, Каліфорнія, с. 465—470, червень 1996 {{ref-en}}</ref> запровадив термін «масштабопросторовий хребет», він розглядав три міри хребтової вираженості:

* Основна головна кривина

:: <math>L_{pp, \gamma-norm} = \frac{t^{\gamma}}{2} \left( L_{xx}+L_{yy} - \sqrt{(L_{xx}-L_{yy})^2 + 4 L_{xy}^2} \right)</math>
: виражена в термінах ''<math>\gamma</math>-нормованих похідних'' через
:: <math>\partial_{\xi} = t^{\gamma/2} \partial_x, \partial_{\eta} = t^{\gamma/2} \partial_y</math>.

* Квадрат різниці квадратів <math>\gamma</math>-нормованих власних значень

:: <math>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 + 4 L_{xy}^2 \right).</math>

* Квадрат різниці <math>\gamma</math>-нормованих власних значень

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

Поняття <math>\gamma</math>-нормованих похідних тут важливе, оскільки дозволяє алгоритмам виявляння хребтів і долин належно калібруватися. З вимоги, щоби для одновимірного гауссового хребта, вкладеного в два (або три) виміри, масштаб виявляння дорівнював ширині хребтової структури при вимірюванні в одиницях довжини (вимога відповідності між розмірами фільтра виявляння та структурою зображення, на яку він реагує), випливає, що слід обирати <math>\gamma = 3/4</math>. З цих трьох мір вираженості хребта перша сутність <math>L_{pp, \gamma-norm}</math> є мірою вираженості хребта загального призначення з багатьма застосуваннями, такими як виявляння кровоносних судин і виділяння доріг. Проте сутність <math>A_{\gamma-norm}</math> використовували в таких застосуваннях як покращення відбитків пальців,<ref>{{cite journal |author=Almansa, A., Lindeberg, T. |title=Fingerprint Enhancement by Shape Adaptation of Scale-Space Operators with Automatic Scale-Selection |journal=IEEE Transactions on Image Processing |volume=9 |issue=12 |pages=2027–42 |year=2000 |url=http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A338874&dswid=9389 |pmid=18262941 |doi=10.1109/83.887971 |bibcode=2000ITIP....9.2027L |accessdate=15 травня 2022 |archive-date=15 травня 2022 |archive-url=https://web.archive.org/web/20220515181716/http://kth.diva-portal.org/smash/record.jsf?pid=diva2:338874&dswid=9389 }} {{ref-en}}</ref> {{нп|відстежування рук|||Hand tracking}} та {{нп|розпізнавання жестів|||Gesture recognition}} у реальному часі,<ref>[http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A462620&dswid=3479 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.] {{Webarchive|url=https://web.archive.org/web/20220515191841/http://kth.diva-portal.org/smash/record.jsf?pid=diva2:462620&dswid=3479 |date=15 травня 2022 }} {{ref-en}}</ref> а також для моделювання локальних статистик зображень для виявляння та відстежування людей у зображеннях та відео.<ref>{{cite journal |author=Sidenbladh, H., Black, M. |title=Learning the statistics of people in images and video |journal=International Journal of Computer Vision |volume=54 |issue=1–2 |pages=183–209 |year=2003 |doi=10.1023/a:1023765619733 |url=http://www.csc.kth.se/~hedvig/publications/ijcv_03.pdf |accessdate=15 травня 2022 |archive-date=5 липня 2017 |archive-url=https://web.archive.org/web/20170705113229/http://www.csc.kth.se/~hedvig/publications/ijcv_03.pdf }} {{ref-en}}</ref>

Існують також й інші тісно пов'язані визначення хребта, які використовують нормовані похідні з неявним припущенням <math>\gamma = 1</math>.<ref>J. Furst and  J. Miller, "[https://books.google.com/books?hl=en&lr=&id=Zm4Vs0HiaskC&oi=fnd&pg=PA93&ots=G-gYPyZj2N&sig=IlsrBAcoiil7wjlnYG9lVyaqn4M#v=onepage&q&f=false The Maximal Scale Ridge:  Incorporating Scale in the Ridge Definition] {{Webarchive|url=https://web.archive.org/web/20220515191753/https://books.google.com/books?hl=en&lr=&id=Zm4Vs0HiaskC&oi=fnd&pg=PA93&ots=G-gYPyZj2N&sig=IlsrBAcoiil7wjlnYG9lVyaqn4M#v=onepage&q&f=false |date=15 травня 2022 }}", ''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. {{ref-en}}</ref> ''Проробити ці підходи докладніше.'' Проте при виявлянні хребтів з <math>\gamma = 1</math> масштаб виявляння буде вдвічі більшим, аніж для <math>\gamma = 3/4</math>, що призводить до більших викривлень форми та нижчої здатності вловлювати хребти та долини з сусідніми завадними структурами зображення в його області.

== Історія ==

Поняття хребтів і долин у цифрових зображеннях було запроваджено {{нп|Роберт Гаралік|Гараліком||Robert Haralick}} 1983 року<ref>{{cite journal |doi=10.1016/0734-189X(83)90094-4 |author=Haralick, R. |title=Ridges and Valleys on Digital Images |journal=Computer Vision, Graphics, and Image Processing  |volume=22 |issue=10 |pages=28–38 |date=April 1983 }} {{ref-en}}</ref> та Кроулі стосовно [[Піраміда (обробка зображень)|пірамід]] [[Різниця гауссіанів|різниць гауссіанів]] 1984 року.<ref>{{cite journal |doi=10.1109/TPAMI.1984.4767500 |author=Crowley, J.L., {{нп|Еліс К. Паркер|Parker, A.C.||Alice C. Parker}} |title=A Representation for Shape Based on Peaks and Ridges in the Difference of Low Pass Transform |journal=IEEE Trans Pattern Anal Mach Intell |volume=6 |issue=2 |pages=156–170 |date=March 1984 |url=http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Parker84.pdf |pmid=21869180 |citeseerx=10.1.1.161.3102 |accessdate=15 травня 2022 |archive-date=3 березня 2016 |archive-url=https://web.archive.org/web/20160303195549/http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Parker84.pdf }} {{ref-en}}</ref><ref>{{cite journal |doi=10.1109/TPAMI.1987.4767876 |pmid=21869381 |author=Crowley, J.L., Sanderson, A. |title=Multiple Resolution Representation and Probabilistic Matching of 2-D Gray-Scale Shape |journal=IEEE Trans Pattern Anal Mach Intell |volume=9 |issue=1 |pages=113–121 |date=January 1987 |url=http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Sanderson-PAMI87.pdf |citeseerx=10.1.1.1015.9294 |accessdate=15 травня 2022 |archive-date=30 серпня 2017 |archive-url=https://web.archive.org/web/20170830032237/http://www-prima.inrialpes.fr/Prima/Homepages/jlc/papers/Crowley-Sanderson-PAMI87.pdf }} {{ref-en}}</ref> Застосування хребтових описувачів до аналізу медичних зображень було детально досліджено Пайзером та його співробітниками,<ref>{{cite journal |doi=10.1109/34.216734 |author=Gauch, J.M., Pizer, S.M. |title=Multiresolution Analysis of Ridges and Valleys in Grey-Scale Images |journal=IEEE Trans Pattern Anal Mach Intell |volume=15 |issue=6 |pages=635–646 |date=June 1993 }} {{ref-en}}</ref><ref>{{cite journal |doi=10.1007/BF01262402 |author1=Eberly D. |author2=Gardner R. |author3=Morse B. |author4=Pizer S. |author5=Scharlach C. |title=Ridges for image analysis |journal=Journal of Mathematical Imaging and Vision |volume=4 |issue=4 |pages=353–373 |date=December 1994 }} {{ref-en}}</ref><ref>{{cite journal |doi=10.1006/cviu.1997.0563 |author=Pizer, Stephen M., Eberly, David, Fritsch, Daniel S. |title=Zoom-invariant vision of figural shape: the mathematics of cores |journal=Computer Vision and Image Understanding |volume=69 |issue=1 |pages=55–71 |date=January 1998 |citeseerx=10.1.1.38.3116 }} {{ref-en}}</ref> давши їхнє поняття ''M''-подань ({{lang-en|M-reps}}).<ref>[http://citeseer.ist.psu.edu/pizer01segmentation.html 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] {{Webarchive|url=https://web.archive.org/web/20070310222641/http://citeseer.ist.psu.edu/pizer01segmentation.html |date=10 березня 2007 }} {{ref-en}}</ref> Ліндеберг також посприяв розвитку виявляння хребтів, запровадивши <math>\gamma</math>-нормовані похідні та масштабопросторові хребти, визначені з локальної максимізації належним чином нормованої головної кривини матриці Гессе (або інших мір вираженості хребта) над простором та над масштабом. Ці поняття пізніше було розвинуто із застосуванням до виділяння доріг Стегером та ін.<ref>{{cite journal |author=Steger C. |title=An unbiased detector of curvilinear structures |journal=IEEE Trans Pattern Anal Mach Intell |volume=20 |issue=2 |pages=113–125 |year=1998 |doi=10.1109/34.659930 |citeseerx=10.1.1.42.2266 }} {{ref-en}}</ref><ref>{{cite journal |doi=10.1007/s001380050121 |author1=Laptev I. |author2=Mayer H. |author3=Lindeberg T. |author4=Eckstein W. |author5=Steger C. |author6=Baumgartner A. |title=Automatic extraction of roads from aerial images based on scale-space and snakes |journal=Machine Vision and Applications |volume=12 |issue=1 |pages=23–31 |year=2000 |url=http://www.irisa.fr/vista/Papers/2000_mva_laptev.pdf |accessdate=15 травня 2022 |archive-date=15 квітня 2021 |archive-url=https://web.archive.org/web/20210415044227/http://www.irisa.fr/vista/Papers/2000_mva_laptev.pdf }} {{ref-en}}</ref> та до сегментування кровоносних судин за Франджі та ін.,<ref>{{cite journal |vauthors=Frangi AF, Niessen WJ, Hoogeveen RM, van Walsum T, Viergever MA |title=Model-based quantitation of 3-D magnetic resonance angiographic images |journal=IEEE Trans Med Imaging |volume=18 |issue=10 |pages=946–56 |date=October 1999 |pmid=10628954 |doi=10.1109/42.811279 |citeseerx=10.1.1.502.5994 }} {{ref-en}}</ref> а також для виявлення криволінійних і трубчастих структур Сато та ін.<ref>{{cite journal |vauthors=Sato Y, Nakajima S, Shiraga N, Atsumi H, Yoshida S, etal |title=Three-dimensional multi-scale line filter for segmentation and visualization of curvilinear structures in medical images |journal=Medical Image Analysis |volume=2 |issue=2 |pages=143–168 |year=1998 |url=http://www.image.med.osaka-u.ac.jp/member/yoshi/paper/linefilter.pdf |doi=10.1016/s1361-8415(98)80009-1 |pmid=10646760 |accessdate=15 травня 2022 |archive-date=24 березня 2018 |archive-url=https://web.archive.org/web/20180324191705/http://www.image.med.osaka-u.ac.jp/member/yoshi/paper/linefilter.pdf }} {{ref-en}}</ref> та Крисяном та ін.<ref>{{cite journal |doi=10.1006/cviu.2000.0866 |author1=Krissian K. |author2=Malandain G. |author3=Ayache N. |author4=Vaillan R. |author5=Trousset Y. |title=Model-based detection of tubular structures in 3D images |journal=Computer Vision and Image Understanding |volume=80 |issue=2 |pages=130–171 |year=2000 |url=http://portal.acm.org/citation.cfm?id=363419.363423}} {{ref-en}}</ref> Огляд кількох класичних визначень хребтів у фіксованому масштабі, включно з відношеннями між ними, було запропоновано Кендерінком та ван Дорном.<ref>{{cite journal |doi=10.1016/0167-8655(94)90134-1 |author=Koenderink, Jan J., van Doorn, Andrea J. |title=2+1-D differential geometry |url=https://archive.org/details/sim_pattern-recognition-letters_1994-05_15_5/page/439 |journal=Pattern Recognition Letters |volume=15 |issue=5 |pages=439–443 |date=May 1994 }} {{ref-en}}</ref> Огляд методів виділяння судин було запропоновано Кірбасом та Квеком.<ref>{{cite journal |doi=10.1145/1031120.1031121 |vauthors=Kirbas C, Quek F |title=A review of vessel extraction techniques and algorithms |journal=ACM Computing Surveys |volume=36 |issue=2 |pages=81–121 |year=2004 |url=ftp://cmp.felk.cvut.cz/pub/cmp/articles/matas/ps/Curvilinear/blood-vessel_review.pdf |citeseerx=10.1.1.460.8544 |url-status=dead }} {{ref-en}}</ref>

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

У своєму найширшому сенсі поняття хребта узагальнює уявлення про локальний максимум дійсної функції. Точка <math>\mathbf{x}_0</math> в області визначення функції <math>f:\mathbb{R}^n \rightarrow \mathbb{R}</math> є локальним максимумом цієї функції, якщо існує відстань <math>\delta>0</math>, така, що якщо <math>\mathbf{x}</math> знаходиться всередині <math>\delta</math> одиниць від <math>\mathbf{x}_0</math>, то <math>f(\mathbf{x}) < f(\mathbf{x}_0)</math>. Добре відомо, що критичні точки, для яких локальні максимуми є лише одним з їхніх типів, це ізольовані точки в області визначення функції у всіх ситуаціях, окрім найнезвичніших (тобто незагальних випадків).

Розгляньмо деяке послаблення умови <math>f(\mathbf{x}) < f(\mathbf{x}_0)</math> для <math>\mathbf{x}</math> у всьому околі <math>\mathbf{x}_0</math> до вимоги лише того, щоби вона дотримувалася в <math>n-1</math>-вимірній підмножині. Імовірно, це послаблення дозволяє множині точок, що задовольняють цей критерій, які ми назвемо хребтом, мати один ступінь свободи, принаймні в загальному випадку. Це означає, що множина точок хребта утворюватиме одновимірне геометричне місце точок, або криву хребта ({{lang-en|ridge curve}}). Зверніть увагу, що вищезазначене можливо видозмінити, узагальнивши це уявлення до локальних мінімумів й отримавши те, що можна було би назвати одновимірними кривими долин.

Наступне визначення хребта відповідає книзі Еберлі,<ref>{{cite book |author=Eberly, D. |title=Ridges in Image and Data Analysis |url=https://archive.org/details/ridgesinimagedat0007eber |publisher=Kluwer |year=1996 |isbn=978-0-7923-4268-7 }} {{ref-en}}</ref> й його можливо розглядати як узагальнення деяких із вищезгаданих. Нехай <math>U \subset \mathbb{R}^n</math>&nbsp;— відкрита множина, а <math>f:U \rightarrow \mathbb{R}</math> гладенька. Нехай <math>\mathbf{x}_0 \in U</math>. Нехай <math>\nabla_{\mathbf{x}_0}f</math>&nbsp;— градієнт <math>f</math> в <math>\mathbf{x}_0</math>, і нехай <math>H_{\mathbf{x}_0}(f)</math>&nbsp;— матриця Гессе <math>n \times n</math> функції <math>f</math> в <math>\mathbf{x}_0</math>. Нехай <math>\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n</math>&nbsp;— це <math>n</math> впорядкованих власних значень <math>H_{\mathbf{x}_0}(f)</math>, і нехай <math>\mathbf{e}_i</math>&nbsp;— одиничний власний вектор у власному просторі для <math>\lambda_i</math>. (Для цього слід виходити з відмінності всі власних значень.)

Точка <math>\mathbf{x}_0</math> є точкою на 1-вимірному хребті <math>f</math>, якщо виконуються такі умови:

# <math>\lambda_{n-1}<0</math>, і
# <math>\nabla_{\mathbf{x}_0} f \cdot \mathbf{e}_i=0</math> для <math>i=1, 2, \ldots, n-1</math>.

Це уточнює поняття, що <math>f</math>, обмежена ''цим конкретним'' <math>n-1</math>-вимірним підпростором, має локальний максимум в <math>\mathbf{x}_0</math>.

Це визначення природно узагальнюється на ''k'' -вимірний хребет наступним чином: точка <math>\mathbf{x}_0</math> є точкою на ''k''-вимірному хребті <math>f</math>, якщо виконуються наступні умови:

# <math>\lambda_{n-k}<0</math>, і
# <math>\nabla_{\mathbf{x}_0} f \cdot \mathbf{e}_i=0</math> для <math>i=1, 2, \ldots, n-k</math>.

Багато в чому ці визначення природно узагальнюють визначення локального максимуму функції. Властивості гребнів максимальної опуклості ({{lang-en|maximal convexity ridges}}) покладено на тверду математичну основу Деймоном<ref name="Damon99" /> та Міллером.<ref name="Miller98" /> Їхні властивості в однопараметрових сімействах було визначено Келлером.<ref>Kerrel, R. ''[https://dl.acm.org/citation.cfm?id=930172 Generic Transitions of Relative Critical Sets in Parameterized Families with Applications to Image Analysis].'' University of North Carolina. 1999. {{ref-en}}</ref>

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

Наступне визначення можливо простежити до Фріча,<ref>Fritsch, DS, Eberly,D., Pizer, SM, and McAuliffe, MJ. "Stimulated cores and their applications in medical imaging." Information Processing in Medical Imaging, Y. Bizais, C Barillot, R DiPaola, eds., Kluwer Series in Computational Imaging and Vision, pp. 365–368. {{ref-en}}</ref> який цікавився виділянням геометричної інформації про фігури у двовимірних зображеннях у відтінках сірого. Фріч обробляв своє зображення фільтром «серединності» ({{lang-en|"medialness"}}), який давав йому інформацію, аналогічну даним «віддаленості від меж» ({{lang-en|"distant to the boundary"}}) у просторі масштабів. Хребти цього зображення, проєктовані на первинне зображення, мали бути аналогічними кістякові форми (наприклад, [[Серединна вісь|блюмовій серединній осі]]) первинного зображення.

Далі наведено визначення максимальномасштабового хребта ({{lang-en|maximal scale ridge}}) функції трьох змінних, однією з яких є параметр «масштаб». Одне, чого ми хочемо дотриматися в цьому визначенні, це якщо <math>(\mathbf{x},\sigma)</math>&nbsp;— точка на цьому хребті, то значення цієї функції в ній максимальне за виміром масштабу. Нехай <math>f(\mathbf{x},\sigma)</math>&nbsp;— гладенька диференційована функція <math>U \subset \mathbb{R}^2 \times \mathbb{R}_{+}</math>. <math>(\mathbf{x},\sigma)</math>&nbsp;— точка на максимальномасштабовому хребті тоді й лише тоді, коли

# <math>\frac{\partial f}{\partial \sigma}=0</math> і <math>\frac{\partial^2 f}{\partial \sigma^2}<0</math>, і
# <math>\nabla f \cdot \mathbf{e}_1=0</math> і <math>\mathbf{e}_1^t H(f) \mathbf{e}_1 <0</math>.

== Взаємозв'язок між виявлянням контурів та виявлянням хребтів ==

Метою виявляння хребтів зазвичай є вловлювання головної осі симетрії видовженого об'єкта,{{Джерело|дата=травень 2022}} тоді як мета [[виявляння контурів]] зазвичай полягає у вловлюванні межі об'єкта. Проте деяка література з виявляння контурів помилково{{Джерело|дата=травень 2022}} відносить поняття хребтів до поняття контурів, що заплутує ситуацію.

З точки зору визначень, між виявлячами контурів та виявлячами хребтів існує тісний зв'язок. З формулюванням не-максимуму, наведеним Кенні,<ref>{{cite journal |doi=10.1109/TPAMI.1986.4767851 |author=Canny J. |title=A computational approach to edge detection |journal=IEEE Trans Pattern Anal Mach Intell |volume=8 |issue=6 |pages=679–698 |year=1986 |pmid=21869365 |url=http://portal.acm.org/citation.cfm?id=11275}} {{ref-en}}</ref> стверджується, що контури визначаються як точки, де величина градієнта набуває локального максимуму в напрямі градієнта. Дотримуючись диференціальногеометричного способу вираження цього визначення,<ref>{{cite journal |doi=10.1007/BF01664794 |author=Lindeberg T. |title=Discrete Derivative Approximations with Scale-Space Properties: A Basis for Low-Level Feature Extraction |journal=Journal of Mathematical Imaging and Vision |volume=3 |issue=4 |pages=349–376 |year=1993 |url=http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A473368&dswid=294 |accessdate=15 травня 2022 |archive-date=15 травня 2022 |archive-url=https://web.archive.org/web/20220515192136/http://kth.diva-portal.org/smash/record.jsf?pid=diva2:473368&dswid=294 }} {{ref-en}}</ref> ми можемо у вищезгаданій системі координат <math>(u, v)</math> стверджувати, що величина градієнта масштабопросторового подання, яка дорівнює похідній за напрямом першого порядку в напрямі <math>v</math>, <math>L_v</math>, повинна мати свою напрямну похідну першого порядку в напрямі <math>v</math> рівною нулеві

: <math>\partial_v(L_v) = 0</math>

тоді як напрямна похідна другого порядку <math>L_v</math> в напрямі <math>v</math> має бути від'ємною, тобто

: <math>\partial_{vv}(L_v) \leq 0</math>.

Записане як явний вираз у термінах локальних частинних похідних <math>L_x</math>, <math>L_y</math> … <math>L_{yyy}</math>, це визначення контуру можливо виразити у вигляді кривих, які перетинають нуль, диференціального інваріанта

: <math>L_v^2 L_{vv} = L_x^2 \, L_{xx} + 2 \, L_x \, L_y \, L_{xy} + L_y^2 \, L_{yy} = 0,</math>

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

: <math>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</math>

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

== Див. також ==

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

== Примітки ==
{{Примітки}}

[[Категорія:Виділення ознак (комп'ютерний зір)|Хребтів]]
[[Категорія:Числення багатьох змінних]]
[[Категорія:Теорія сингулярностей]]