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

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 16:06, 27 листопада 2021, створена Andriy.vBot (обговорення | внесок) (виправлення дат)
Перейти до навігації Перейти до пошуку
Фігура і її скелет, обчислюється за допомогою алгоритму стискання зі збереженням топології.

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

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

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

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

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

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

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

Докладніше: Grassfire transform

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

  1. ↑ Помилка скрипту: Функції «harvard_core» не існує., Section 2.5.10, p. 55.
  2. ↑ а б Помилка скрипту: Функції «harvard_core» не існує., Section 11.1.5, p. 650
  3. ↑ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
  4. ↑ Помилка скрипту: Функції «harvard_core» не існує..
  5. ↑ Помилка скрипту: Функції «harvard_core» не існує..
  6. ↑ а б в г A. K. Jain (1989), Section 9.9, p. 382.
  7. ↑ Помилка скрипту: Функції «harvard_core» не існує..
  8. ↑ а б Помилка скрипту: Функції «harvard_core» не існує., Section 17.5.2, p. 234.
  9. ↑ Помилка скрипту: Функції «harvard_core» не існує.
  10. ↑ Помилка скрипту: Функції «harvard_core» не існує.
  11. ↑ Harry Blum (1967)
  12. ↑ A. K. Jain (1989), Section 9.9, p. 387.
  13. ↑ а б Помилка скрипту: Функції «harvard_core» не існує., Section 9.5.7, p. 543.
  14. ↑ Помилка скрипту: Функції «harvard_core» не існує..
  15. ↑ R. Kimmel, D. Shaked, N. Kiryati, and A. M. Bruckstein. http://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf Comp. Vision and Image Understanding, 62(3):382-391, 1995.
  16. ↑ Помилка скрипту: Функції «harvard_core» не існує.
  17. ↑ Помилка скрипту: Функції «harvard_core» не існує..
  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.
  • 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.
  • 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.

Вільне ПЗ

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

Отримано з https://uk.wikipedia.org/w/index.php?title=Кістяк_(множина_точок)&oldid=33896046