Кістяк (множина точок)

Фігура і її скелет, обчислюється за допомогою алгоритму стискання зі збереженням топології.

В аналізі форми^[en] кістяк (або топологічний кістяк, англ. Topological skeleton) форми — це тонка версія тієї форми, яка рівновіддалена від її границь. В кістяку зазвичай підкреслюються геометричні і топологічні властивості форми, такі як зв'язність, топологія, довжина, ширина та напрямок. Разом з відстанню його точок до границі форми, кістяк може також служити представленням форми (вони містять всю інформацію, необхідну для відновлення форми).

Кістяки мають кілька різних математичних визначень в технічній літературі, і існує багато різних алгоритмів їх обчислення. Також можна знайти різні варіанти кістяка, включаючи прямий кістяк, морфологічний кістяк^[en] і т. д.

У технічній літературі поняття каркаса (кістяка) і серединної осі використовуються деякими авторами як взаємозамінні,[1][2][3][4][5] в той час як деякі інші автори[6][7][8] розглядають їх як пов'язані, але не однакові. Аналогічно, поняття виокремлення кістяка і стоншення^[en], вважаються одними дослідниками[2] як ідентичні, деякими — як різні.[6]

Скелети широко використовуються в комп'ютерному зорі, аналізі зображень^[en], розпізнаванні образів і цифровій обробці зображень для таких цілей, як оптичне розпізнавання символів, розпізнавання відбитків пальців, візуальний контроль або стиснення. В біології кістяки знайшли широке застосування для характеристики згортання білків[9] і морфології рослин на різних біологічних рівнях.[10]

Математичне визначення

Кістяки мають кілька різних математичних визначень в технічній літературі; Більшість з них призводять до аналогічних результатів в неперервних просторах^[en], але зазвичай дають різні результати в дискретних просторах.

Втамування точок моделі поширення вогню

У своїй оригінальній роботі Гаррі Блум[11] з дослідницьких лабораторій ВПС Кембриджа на ВПБ у Ганскомі^[en] в Бедфорді, штат Массачусетс, визначив серединну вісь для обчислення кістяка з використанням інтуїтивної моделі поширення вогню на трав'яному полі, де поле має вигляд заданої форми. Якщо хтось «підпалює» вогонь у всіх точках на кордоні цього поля трави в один момент, то кістяк являє собою множину точок гасіння, тобто, це ті точки, де зустрічаються два або більше фронтів розповсюдження вогню. Цей інтуїтивний опис є відправною точкою для ряду більш точних визначень.

Центри максимальних дисків (або куль)

Круг (або куля) B називається максимальною у множині A, якщо:

• ${\displaystyle B\subseteq A}$, та
• якщо інший диск D містить B, то ${\displaystyle D\not \subseteq A}$.

Один із способів визначення кістяка форми A — це множина центрів всіх максимальних дисків в A.[12]

Центри кіл з двома точками дотику

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

Кряж дистанційної функції

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

Одне з визначень кістяка, що використовує функцію відстані, — це кряжі функції відстані.[6] У літературі є поширене помилкове твердження про те, що кістяк складається з точок, «локально максимальних» в перетворенні відстаней. Це не так, що покаже навіть побіжне порівняння перетворення відстані і результуючого кістяка.

Інші визначення

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

Алгоритми скелетування

Існує безліч різних алгоритмів обчислення кістяка для фігур в цифрових зображеннях, а також у неперервних множинах^[en].

• Використання морфологічних операторів (див. морфологічний кістяк^[en][13])
• Доповнення морфологічних операторів спрощенням^[en] за формою[14]
• Використання перетину відстаней від частин межі[15]
• Використання еволюти кривої[16][17]
• Використання множин рівня[8]
• Пошук точок кряжів дистанційній функції[6]
• «Відшаровування» форми без зміни топології до збігання[18]

Алгоритми побудови кістяка іноді можуть створювати небажані гілки на вихідних скелетах. Спрощення^[en] часто використовують для видалення цих гілок.

Див. також

• Серединна вісь
• Прямий кістяк
• Бета-кістяк
• Перетворення підпаленої трави^[en]

Примітки

1. Jain, Kasturi та Schunck, (1995), Section 2.5.10, p. 55.
2. Gonzales та Woods, (2001), Section 11.1.5, p. 650
3. Архівована копія (PDF). Архів оригіналу (PDF) за 13 серпня 2017. Процитовано 18 серпня 2018.
4. Dougherty, (1992).
5. Ogniewicz, (1995).
6. A. K. Jain (1989), Section 9.9, p. 382.
7. Serra, (1982).
8. Sethian, (1999), Section 17.5.2, p. 234.
9. Abeysinghe та ін., (2008)
10. Bucksch, (2014)
11. Harry Blum (1967)
12. A. K. Jain (1989), Section 9.9, p. 387.
13. Gonzales та Woods, (2001), Section 9.5.7, p. 543.
14. Abeysinghe та ін., (2008).
15. R. Kimmel, D. Shaked, N. Kiryati, and A. M. Bruckstein. http://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf [Архівовано 11 грудня 2015 у Wayback Machine.] Comp. Vision and Image Understanding, 62(3):382-391, 1995.
16. Tannenbaum, (1996)
17. Bai, Longin та Wenyu, (2007).
18. A. K. Jain (1989), Section 9.9, p. 389.

Посилання

• Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), Segmentation-free skeletonization of grayscale volumes for shape understanding, IEEE Int. Conf. Shape Modeling and Applications (SMI 2008) (PDF), с. 63—71, doi:10.1109/SMI.2008.4547951, ISBN 978-1-4244-2260-9, архів оригіналу (PDF) за 9 травня 2009, процитовано 15 травня 2017.
• Abeysinghe, Sasakthi; Ju, Tao; Baker, Matthew; Chiu, Wah (2008), Shape modeling and matching in identifying 3D protein structures (PDF), Computer-Aided Design, Elsevier, 40 (6): 708—720, doi:10.1016/j.cad.2008.01.013, архів оригіналу (PDF) за 12 червня 2011, процитовано 15 травня 2017
• Bai, Xiang; Longin, Latecki; Wenyu, Liu (2007), Skeleton pruning by contour partitioning with discrete curve evolution (PDF), IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (3): 449—462, doi:10.1109/TPAMI.2007.59, PMID 17224615, архів оригіналу (PDF) за 5 лютого 2009, процитовано 18 серпня 2018.
• Blum, Harry (1967), A Transformation for Extracting New Descriptors of Shape, у Wathen-Dunn, W. (ред.), Models for the Perception of Speech and Visual Form (PDF), Cambridge, Massachusetts: MIT Press, с. 362—380, архів оригіналу (PDF) за 18 вересня 2013, процитовано 18 серпня 2018.
• Bucksch, Alexander (2014), A practical introduction to skeletons for the plant sciences, Applications in Plant Sciences, 2 (8), doi:10.3732/apps.1400005.
• Cychosz, Joseph (1994), Graphics gems IV, San Diego, CA, USA: Academic Press Professional, Inc., с. 465–473, ISBN 0-12-336155-9.
• Dougherty, Edward R. (1992), An Introduction to Morphological Image Processing, ISBN 0-8194-0845-X.
• Gonzales, Rafael C.; Woods, Richard E. (2001), Digital Image Processing, ISBN 0-201-18075-8.
• Jain, Anil K. (1989), Fundamentals of Digital Image Processing, ISBN 0-13-336165-9.
• Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Machine Vision, ISBN 0-07-032018-7.
• Ogniewicz, R. L. (1995), Automatic Medial Axis Pruning Based on Characteristics of the Skeleton-Space, у Dori, D.; Bruckstein, A. (ред.), Shape, Structure and Pattern Recognition, ISBN 981-02-2239-4.
• Petrou, Maria; García Sevilla, Pedro (2006), Image Processing Dealing with Texture, ISBN 978-0-470-02628-1.
• Serra, Jean (1982), Image Analysis and Mathematical Morphology, ISBN 0-12-637240-3.
• Sethian, J. A. (1999), Level Set Methods and Fast Marching Methods, ISBN 0-521-64557-3.
• Tannenbaum, Allen (1996), Three snippets of curve evolution theory in computer vision, Mathematical and Computer Modelling, 24 (5): 103—118.

Вільне ПЗ

• ITK [Архівовано 18 серпня 2018 у Wayback Machine.] (C++)
• Skeletonize3D [Архівовано 19 серпня 2018 у Wayback Machine.] (Java)
• Graphics gems IV (C)
• EVG-Thin [Архівовано 30 серпня 2017 у Wayback Machine.] (C++)

Додаткові посилання

• Skeletonization/Medial Axis Transform [Архівовано 5 серпня 2018 у Wayback Machine.]
• Skeletons of a region [Архівовано 14 серпня 2018 у Wayback Machine.]
• Skeletons in Digital image processing (pdf)
• Comparison of 15 line thinning algorithms
• Skeletonization using Level Set Methods
• Curve Skeletons
• Skeletons from laser scanned point clouds (Homepage)