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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Фігура і її скелет, обчислюється за допомогою алгоритму стискання зі збереженням топології.

В аналізі форми[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. 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.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання)
  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.

Посилання

[ред. | ред. код]

Вільне ПЗ

[ред. | ред. код]

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

[ред. | ред. код]