Перегляд вихідного коду сторінки Кістяк (множина точок)

[[Файл:Skel.png|міні|Фігура і її скелет, обчислюється за допомогою алгоритму стискання зі збереженням топології.]]
В {{Не перекладено|Аналіз форми|аналізі форми|en|Shape analysis (digital geometry)}} '''кістяк''' (або '''топологічний кістяк''', {{lang-en|Topological skeleton}}) [[Форма|форми]]&nbsp;— це тонка версія тієї форми, яка [[Рівновіддаленість|рівновіддалена]] від її [[Границя|границь]]. В кістяку зазвичай підкреслюються [[Геометрія|геометричні]] і [[Топологія|топологічні]] властивості форми, такі як [[зв'язність]], [[топологія]], [[довжина]], [[ширина]] та [[напрямок]]. Разом з відстанню його точок до границі форми, кістяк може також служити представленням форми (вони містять всю інформацію, необхідну для відновлення форми).

Кістяки мають кілька різних математичних визначень в технічній літературі, і існує багато різних алгоритмів їх обчислення. Також можна знайти різні варіанти кістяка, включаючи [[прямий кістяк]], {{Нп|морфологічний кістяк|||Morphological skeleton}} і&nbsp;т.&nbsp;д.

У технічній літературі поняття каркаса (кістяка) і [[Серединна вісь|серединної осі]] використовуються деякими авторами як взаємозамінні,<ref>{{harvtxt|Jain|Kasturi|Schunck|1995}}, Section 2.5.10, p.&nbsp;55.</ref><ref name="gonzales">{{harvtxt|Gonzales|Woods|2001}}, Section 11.1.5, p.&nbsp;650</ref><ref>{{Cite web |url=http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf |title=Архівована копія |accessdate=18 серпня 2018 |archive-date=13 серпня 2017 |archive-url=https://web.archive.org/web/20170813084127/http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf }}</ref><ref>{{harvtxt|Dougherty|1992}}.</ref><ref>{{harvtxt|Ogniewicz|1995}}.</ref> в той час як деякі інші автори<ref name="jain">{{harvs|first=A. K.|last=Jain|year=1989|txt}}, Section 9.9, p.&nbsp;382.</ref><ref>{{harvtxt|Serra|1982}}.</ref><ref name="sethian">{{harvtxt|Sethian|1999}}, Section 17.5.2, p.&nbsp;234.</ref> розглядають їх як пов'язані, але не однакові. Аналогічно, поняття виокремлення кістяка і {{Нп|стоншення (морфологія)|стоншення||Thinning (morphology)}}, вважаються одними дослідниками<ref name="gonzales"/> як ідентичні, деякими&nbsp;— як різні.<ref name="jain"/>

Скелети широко використовуються в [[Комп'ютерний зір|комп'ютерному зорі]], {{Не перекладено|аналіз зображень|аналізі зображень|en|Image analysis}}, [[Теорія розпізнавання образів|розпізнаванні образів]] і [[Цифрова обробка зображень|цифровій обробці зображень]] для таких цілей, як [[оптичне розпізнавання символів]], розпізнавання [[відбитки пальців|відбитків пальців]], [[візуальний контроль]] або [[Стиснення зображень|стиснення]]. В біології кістяки знайшли широке застосування для характеристики [[згортання білків]]<ref>{{harvtxt|Abeysinghe|Ju|Baker|Chiu|2008}}</ref> і [[Морфологія рослин|морфології рослин]] на різних біологічних рівнях.<ref>{{harvtxt|Bucksch|2014}}</ref>

== Математичне визначення ==
Кістяки мають кілька різних математичних визначень в технічній літературі; Більшість з них призводять до аналогічних результатів в {{Не перекладено|Неперервність (топологія)|неперервних просторах|en|Continuum_(topology)}}, але зазвичай дають різні результати в [[Дискретний простір|дискретних просторах]].

=== Втамування точок моделі поширення вогню ===
{{main|Grassfire transform}}
У своїй оригінальній роботі Гаррі Блум<ref>{{harvs|first=Harry|last=Blum|year=1967|txt}}</ref> з дослідницьких лабораторій ВПС Кембриджа на {{Не перекладено|ВПБ у Ганскомі||en|Hanscom_Air_Force_Base}} в [[Бедфорд (округ, Вірджинія)|Бедфорді]], штат [[Массачусетс]], визначив [[Серединна вісь|серединну вісь]] для обчислення кістяка з використанням інтуїтивної моделі поширення вогню на трав'яному полі, де поле має вигляд заданої форми. Якщо хтось «підпалює» вогонь у всіх точках на кордоні цього поля трави в один момент, то кістяк являє собою множину точок гасіння, тобто, це ті точки, де зустрічаються два або більше фронтів розповсюдження вогню. Цей інтуїтивний опис є відправною точкою для ряду більш точних визначень.

=== Центри максимальних дисків (або куль) ===
[[Круг]] (або [[куля]]) ''B'' називається ''максимальною'' у множині ''A'', якщо:
* <math>B\subseteq A</math>, та
* якщо інший диск ''D'' містить ''B'', то <math>D\not\subseteq A</math>.
Один із способів визначення кістяка форми A&nbsp;— це множина центрів всіх максимальних дисків в ''A''.<ref>{{harvs|first=A. K.|last=Jain|year=1989|txt}}, Section 9.9, p.&nbsp;387.</ref>

=== Центри кіл з двома точками дотику ===
кістяк форми A також може бути визначений як множина центрів кіл, які є дотичними до межі ''A'' в двох або більше точках.<ref name="gonzales543"/> Це визначення гарантує, що точки кістяка рівновіддалені від межі форми і математично еквівалентні перетворенню серединної осі Блума.

=== Кряж дистанційної функції ===
У багатьох визначеннях кістяка використовується концепція [[Метрика (математика)|функції відстані]], яка є функцією, що повертає для кожної точки ''x'' всередині форми ''A'' відстань від неї до найближчої точки на межі A. Використання функції відстані дуже привабливо, оскільки її обчислення є швидким.

Одне з визначень кістяка, що використовує функцію відстані,&nbsp;— це [[кряж]]і функції відстані.<ref name="jain"/> У літературі є поширене помилкове твердження про те, що кістяк складається з точок, «локально максимальних» в перетворенні відстаней. Це не так, що покаже навіть побіжне порівняння перетворення відстані і результуючого кістяка.

=== Інші визначення ===
* Точки без висхідних відрізків у функції відстані. Висхідний відрізок у точці ''x''&nbsp;— це відрізок, що починається в ''x'', який йде у напрямку шляха максимального градієнта.
* Точки, в яких градієнт функції відстані відрізняється від 1 (або, що еквівалентно, не визначений).
* Мінімально можливий набір ліній, які зберігають топологію і рівновіддалені від межі форми.

== Алгоритми скелетування ==
Існує безліч різних алгоритмів обчислення кістяка для фігур в [[Цифрове зображення|цифрових зображеннях]], а також у {{Нп|Неперервна функція (теорія множин)|неперервних множинах||continuous function (set theory)}}.
* Використання [[Математична_морфологія#Основні_операції|морфологічних операторів]] (див. {{Нп|морфологічний кістяк|||Morphological skeleton}}<ref name="gonzales543">{{harvtxt|Gonzales|Woods|2001}}, Section 9.5.7, p.&nbsp;543.</ref>)
* Доповнення морфологічних операторів {{Не перекладено|Спрощення (морфологія)|спрощенням|en|Pruning_(morphology)}} за формою<ref>{{harvtxt|Abeysinghe|Baker|Chiu|Ju|2008}}.</ref>
* Використання перетину відстаней від частин межі<ref>[[R. Kimmel, D. Shaked, N. Kiryati, and A. M. Bruckstein.]] http://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf {{Webarchive|url=https://web.archive.org/web/20151211080027/http://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf |date=11 грудня 2015 }} Comp. Vision and Image Understanding, 62(3):382-391, 1995.</ref>
* Використання [[Еволюта|еволюти]] кривої<ref>{{harvtxt|Tannenbaum|1996}}</ref><ref>{{harvtxt|Bai|Longin|Wenyu|2007}}.</ref>
* Використання множин рівня<ref name="sethian"/>
* Пошук точок кряжів дистанційній функції<ref name="jain"/>
* «Відшаровування» форми без зміни топології до збігання<ref>{{harvs|first=A. K.|last=Jain|year=1989|txt}}, Section 9.9, p.&nbsp;389.</ref>

Алгоритми побудови кістяка іноді можуть створювати небажані гілки на вихідних скелетах. {{Не перекладено|Спрощення (морфологія)|Спрощення|en|Pruning_(morphology)}} часто використовують для видалення цих гілок.

== Див. також ==
* [[Серединна вісь]]
* [[Прямий кістяк]]
* [[Бета-кістяк]]
* {{Нп|Перетворення підпаленої трави|||Grassfire Transform}}

== Примітки ==
{{reflist|2}}

== Посилання ==
* {{citation|last1=Abeysinghe|first1=Sasakthi|last2=Baker|first2=Matthew|last3=Chiu|first3=Wah|last4=Ju|first4=Tao|contribution=Segmentation-free skeletonization of grayscale volumes for shape understanding|title=IEEE Int. Conf. Shape Modeling and Applications (SMI 2008)|pages=63–71|year=2008|url=http://www.cs.wustl.edu/~ssa1/resources/grayskeleton_smi2008_paper.pdf|doi=10.1109/SMI.2008.4547951|isbn=978-1-4244-2260-9|accessdate=15 травня 2017|archiveurl=https://web.archive.org/web/20090509090817/http://www.cs.wustl.edu/~ssa1/resources/grayskeleton_smi2008_paper.pdf|archivedate=9 травня 2009|deadurl=yes}}.
* {{citation|last1=Abeysinghe|first1=Sasakthi|last2=Ju|first2=Tao|last3=Baker|first3=Matthew|last4=Chiu|first4=Wah|title=Shape modeling and matching in identifying 3D protein structures|journal=Computer-Aided Design|volume=40|issue=6|pages=708–720|publisher=Elsevier|year=2008|url=http://www.cs.wustl.edu/~ssa1/resources/graphmatch_cad2008_journal.pdf|doi=10.1016/j.cad.2008.01.013|accessdate=15 травня 2017|archiveurl=https://web.archive.org/web/20110612052510/http://www.cs.wustl.edu/~ssa1/resources/graphmatch_cad2008_journal.pdf|archivedate=12 червня 2011|deadurl=yes}}
* {{citation | last1 = Bai | first1 = Xiang | last2 = Longin | first2 = Latecki | last3 = Wenyu | first3 = Liu | title = Skeleton pruning by contour partitioning with discrete curve evolution | journal = IEEE Transactions on Pattern Analysis and Machine Intelligence | volume = 29 | issue = 3 | pages = 449–462 | year = 2007 | url = http://xiang.bai.googlepages.com/TPAMI-0573-1005-2.pdf | doi = 10.1109/TPAMI.2007.59 | pmid = 17224615 | accessdate = 18 серпня 2018 | archive-date = 5 лютого 2009 | archive-url = https://web.archive.org/web/20090205094237/http://xiang.bai.googlepages.com/TPAMI-0573-1005-2.pdf }}.
* {{citation|last=Blum|first=Harry|contribution=A Transformation for Extracting New Descriptors of Shape|title=Models for the Perception of Speech and Visual Form|editor-first=W.|editor-last=Wathen-Dunn|publisher=MIT Press|location=Cambridge, Massachusetts|pages=362–380|year=1967|url=http://pageperso.lif.univ-mrs.fr/~edouard.thiel/rech/1967-blum.pdf|accessdate=18 серпня 2018|archive-date=18 вересня 2013|archive-url=https://web.archive.org/web/20130918144056/http://pageperso.lif.univ-mrs.fr/~edouard.thiel/rech/1967-blum.pdf}}.
* {{citation|last1=Bucksch|first1 = Alexander | title = A practical introduction to skeletons for the plant sciences | journal = Applications in Plant Sciences | volume = 2 | issue = 8 | year = 2014 | url = http://www.bioone.org/doi/full/10.3732/apps.1400005 | doi = 10.3732/apps.1400005 }}.
* {{citation | last = Cychosz | first = Joseph | title = Graphics gems IV | publisher = Academic Press Professional, Inc. | location = San Diego, CA, USA | year = 1994 | pages = [https://archive.org/details/isbn_9780123361554/page/465 465–473] | isbn = 0-12-336155-9 | url = https://archive.org/details/isbn_9780123361554/page/465 }}.
* {{citation|last=Dougherty|first=Edward R.|title=An Introduction to Morphological Image Processing|isbn=0-8194-0845-X|year=1992}}.
* {{citation|last1=Gonzales|first1=Rafael C.|last2=Woods|first2=Richard E.|title=Digital Image Processing|isbn=0-201-18075-8|year=2001}}.
* {{citation|last=Jain|first=Anil K.|title=Fundamentals of Digital Image Processing|isbn=0-13-336165-9|year=1989|url-access=registration|url=https://archive.org/details/fundamentalsofdi0000jain}}.
* {{citation|last1=Jain|first1=Ramesh|last2=Kasturi|first2=Rangachar|last3=Schunck|first3=Brian G.|title=Machine Vision|isbn=0-07-032018-7|year=1995|url-access=registration|url=https://archive.org/details/machinevision0000jain}}.
* {{citation|last=Ogniewicz|first=R. L.|contribution=Automatic Medial Axis Pruning Based on Characteristics of the Skeleton-Space|title=Shape, Structure and Pattern Recognition|editor1-first=D.|editor1-last=Dori|editor2-first=A.|editor2-last=Bruckstein|isbn=981-02-2239-4|year=1995}}.
* {{citation|last1=Petrou|first1=Maria|last2=García Sevilla|first2=Pedro|title=Image Processing Dealing with Texture|isbn=978-0-470-02628-1|year=2006}}.
* {{citation|last=Serra|first=Jean|title=Image Analysis and Mathematical Morphology|isbn=0-12-637240-3|year=1982}}.
* {{citation|last=Sethian|first=J. A.|title=Level Set Methods and Fast Marching Methods|isbn=0-521-64557-3|year=1999}}.
* {{citation|last=Tannenbaum|first = Allen|authorlink=Allen Tannenbaum | title = Three snippets of curve evolution theory in computer vision | journal = Mathematical and Computer Modelling | volume = 24 | issue = 5 | pages = 103–118 | year = 1996}}.

== Вільне ПЗ ==
* [http://www.insight-journal.org/browse/publication/181 ITK] {{Webarchive|url=https://web.archive.org/web/20180818210032/http://www.insight-journal.org/browse/publication/181 |date=18 серпня 2018 }} (C++)
* [http://imagejdocu.tudor.lu/doku.php?id=plugin:morphology:skeletonize3d:start Skeletonize3D] {{Webarchive|url=https://web.archive.org/web/20180819011005/http://imagejdocu.tudor.lu/doku.php?id=plugin:morphology:skeletonize3d:start |date=19 серпня 2018 }} (Java)
* [https://github.com/erich666/GraphicsGems/blob/master/gemsiv/thin_image.c Graphics gems IV] (C)
* [http://personal.traclabs.com/~pbeeson/software.html#EVG EVG-Thin] {{Webarchive|url=https://web.archive.org/web/20170830084927/http://personal.traclabs.com/~pbeeson/software.html#EVG |date=30 серпня 2017 }} (C++)

== Додаткові посилання ==
* [http://homepages.inf.ed.ac.uk/rbf/HIPR2/skeleton.htm Skeletonization/Medial Axis Transform] {{Webarchive|url=https://web.archive.org/web/20180805162625/http://homepages.inf.ed.ac.uk/rbf/HIPR2/skeleton.htm |date=5 серпня 2018 }}
* [http://www.cs.ru.nl/~ths/rt2/col/h9/9gebiedENG.html#9.2.4 Skeletons of a region] {{Webarchive|url=https://web.archive.org/web/20180814001501/http://www.cs.ru.nl/~ths/rt2/col/h9/9gebiedENG.html#9.2.4 |date=14 серпня 2018 }}
* [https://web.archive.org/web/20180516114724/http://www.citr.auckland.ac.nz/techreports/2002/CITR-TR-112.pdf Skeletons in Digital image processing (pdf)]
* [https://web.archive.org/web/20061130075721/http://www-igm.univ-mlv.fr/LabInfo/rapportsInternes/2006/01.pdf Comparison of 15 line thinning algorithms]
* [https://web.archive.org/web/20110719231706/http://mecca.louisville.edu/~msabry/projects/cskel.htm Skeletonization using Level Set Methods]
* [https://web.archive.org/web/20110720095326/http://www.cvip.uofl.edu/~msabry/home/Publications/Hassouna_Farag_ICCV_2007.pdf Curve Skeletons]
* [https://web.archive.org/web/20180805064502/http://www.bucksch.nl/ Skeletons from laser scanned point clouds (Homepage)]

[[Категорія:Обробка зображень]]
[[Категорія:Цифрова геометрія]]
[[Категорія:Комп'ютерний зір]]