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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

Шаблон:Reflist

Посилання

Вільне ПЗ

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

  1. ↑ Шаблон:Harvtxt, Section 2.5.10, p. 55.
  2. ↑ 2,0 2,1 Шаблон:Harvtxt, Section 11.1.5, p. 650
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Harvtxt.
  5. ↑ Шаблон:Harvtxt.
  6. ↑ 6,0 6,1 6,2 6,3 Шаблон:Harvs, Section 9.9, p. 382.
  7. ↑ Шаблон:Harvtxt.
  8. ↑ 8,0 8,1 Шаблон:Harvtxt, Section 17.5.2, p. 234.
  9. ↑ Шаблон:Harvtxt
  10. ↑ Шаблон:Harvtxt
  11. ↑ Шаблон:Harvs
  12. ↑ Шаблон:Harvs, Section 9.9, p. 387.
  13. ↑ 13,0 13,1 Шаблон:Harvtxt, Section 9.5.7, p. 543.
  14. ↑ Шаблон:Harvtxt.
  15. ↑ R. Kimmel, D. Shaked, N. Kiryati, and A. M. Bruckstein. http://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf Шаблон:Webarchive Comp. Vision and Image Understanding, 62(3):382-391, 1995.
  16. ↑ Шаблон:Harvtxt
  17. ↑ Шаблон:Harvtxt.
  18. ↑ Шаблон:Harvs, Section 9.9, p. 389.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Кістяк_(множина_точок)&oldid=7028