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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки
  1. Jain, Kasturi та Schunck, (1995), Section 2.5.10, p. 55.
  2. Gonzales та Woods, (2001), Section 11.1.5, p. 650
  3. http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
  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 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.

Посилання

Вільне ПЗ

Додаткові посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.