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

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

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

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

У технічній літературі поняття каркаса (кістяка) і серединної осі використовуються деякими авторами як взаємозамінні, в той час як деякі інші автори розглядають їх як пов'язані, але не однакові. Аналогічно, поняття виокремлення кістяка і стоншення, вважаються одними дослідниками як ідентичні, деякими — як різні.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Використання морфологічних операторів (див. морфологічний кістяк)
• Доповнення морфологічних операторів спрощенням за формою
• Використання перетину відстаней від частин межі
• Використання еволюти кривої
• Використання множин рівня
• Пошук точок кряжів дистанційній функції
• «Відшаровування» форми без зміни топології до збігання

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

Див. також

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

Посилання

• 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)