Из Википедии, свободной энциклопедии
Перейти к навигацииПерейти к поиску
Форма и ее каркас, вычисленные с помощью алгоритма прореживания с сохранением топологии.

В анализе формы , скелет (или топологический скелет ) в виде формы представляет собой тонкий вариант этой формы, которая равноудалена к его границам . Каркас обычно подчеркивает геометрические и топологические свойства формы, такие как ее связность , топология , длина , направление и ширина . Вместе с расстоянием от его точек до границы формы, скелет также может служить представлением формы (они содержат всю информацию, необходимую для восстановления формы).

В технической литературе у скелетов есть несколько различных математических определений, и существует множество различных алгоритмов их вычисления. Также можно найти различные варианты скелета, включая прямые скелеты , морфологические скелеты и т. Д.

В технической литературе понятия скелета и медиальной оси используются как взаимозаменяемые некоторыми авторами [1] [2] [3] [4] [5] », в то время как некоторые другие авторы [6] [7] [8] рассматривают их как связаны, но не то же самое. Точно так же концепции скелетонизации и прореживания также считаются идентичными одними [2], а другими нет. [6]

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

Математические определения

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

Точки гашения модели распространения огня

В своей основополагающей статье Гарри Блюм [11] из Кембриджских исследовательских лабораторий ВВС на базе ВВС Ханском в Бедфорде, штат Массачусетс , определил среднюю ось для вычисления скелета формы, используя интуитивно понятную модель распространения огня на траве. field, где поле имеет форму заданной формы. Если "поджечь" одновременно все точки на границе этого травяного поля, то каркас представляет собой набор точек гашения , то есть тех точек, где встречаются два или более фронта волн. Это интуитивно понятное описание является отправной точкой для ряда более точных определений.

Центры максимальных дисков (или шаров)

Диск (или мяч ) B называется максимальным в множестве А , если

  • , и
  • Если другой диск D содержит B , то.

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

Центры двунаправленных окружностей

Каркас формы A также можно определить как набор центров дисков, которые касаются границы A в двух или более местах. [13] Это определение гарантирует, что точки каркаса равноудалены от границы формы, и математически эквивалентно преобразованию медиальной оси Блюма.

Гребни функции расстояния

Многие определения остова использования макияжа понятия функции расстояния , которая является функцией , которая возвращает для каждой точку х внутри формы А ее расстояние до ближайшей точки на границе А . Использование функции расстояния очень привлекательно, поскольку ее вычисление выполняется относительно быстро.

Одно из определений скелета с использованием функции расстояния - это выступы функции расстояния. [6] В литературе часто встречается неверное утверждение, что каркас состоит из точек, которые являются «локально максимальными» в преобразовании расстояния. Это просто не так, поскольку даже беглое сравнение преобразования расстояния и результирующего скелета покажет. Гребни могут иметь разную высоту, поэтому точка на гребне может быть ниже, чем ее ближайший сосед на гребне. Таким образом, это не локальный максимум, даже если он относится к гребню. Однако он находится менее далеко по вертикали, чем того требует расстояние до земли. В противном случае это была бы часть склона.

Другие определения

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

Алгоритмы скелетонизации

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

  • Использование морфологических операторов (см. Морфологический скелет [13] )
  • Дополнение морфологических операторов сокращением на основе формы [14]
  • Использование пересечений расстояний от граничных участков [15]
  • Используя эволюцию кривой [16] [17]
  • Использование наборов уровней [8]
  • Нахождение точек гребня на функции расстояния [6]
  • «Отслаивание» формы без изменения топологии до схождения [18]

Алгоритмы скелетонизации иногда могут создавать нежелательные ветви на выходных скелетах. Для удаления этих ветвей часто используются алгоритмы сокращения .

См. Также

  • Средняя ось
  • Прямой скелет
  • β-скелет
  • Преобразование травяного огня
  • Шрифты на основе штрихов

Примечания

  1. ^ Jain, Кастури & Шунка (1995) , раздел 2.5.10, стр. 55.
  2. ^ a b Gonzales & Woods (2001) , раздел 11.1.5, стр. 650
  3. ^ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
  4. ^ Догерти (1992) .
  5. ^ Ogniewicz (1995) .
  6. ^ a b c d А. К. Джайн ( 1989 ), раздел 9.9, стр. 382.
  7. ^ Серра (1982) .
  8. ^ a b Sethian (1999) , раздел 17.5.2, стр. 234.
  9. ^ Abeysinghe et al. (2008)
  10. ^ Бакш (2014)
  11. ↑ Гарри Блюм ( 1967 )
  12. ↑ AK Jain ( 1989 ), раздел 9.9, стр. 387.
  13. ^ a b Gonzales & Woods (2001) , раздел 9.5.7, стр. 543.
  14. ^ Abeysinghe et al. (2008) .
  15. ^ Р. Киммел, Д. Шакед, Н. Кирьяти и А. М. Брукштейн. https://www.cs.technion.ac.il/~ron/PAPERS/skeletonization_CVIU_1995.pdf Ср. Видение и понимание образа, 62 (3): 382-391, 1995.
  16. ^ Танненбаум (1996)
  17. ^ Bai, Лонгин и Wenyu (2007) .
  18. ↑ AK Jain ( 1989 ), раздел 9.9, стр. 389.

Ссылки

  • Абейсингхе, Сасакти; Бейкер, Мэтью; Чиу, Вау; Цзюй, Тао (2008), «Скелетонизация без сегментации полутоновых объемов для понимания формы», IEEE Int. Конф. Shape Моделирование и приложений (SMI 2008) (PDF) . С. 63-71, DOI : 10.1109 / SMI.2008.4547951 , ISBN 978-1-4244-2260-9, S2CID  15148296.
  • Абейсингхе, Сасакти; Цзюй, Дао; Бейкер, Мэтью; Чиу, Ва (2008), «Моделирование формы и сопоставление в идентификации трехмерных белковых структур» (PDF) , Computer-Aided Design , Elsevier, 40 (6): 708–720, doi : 10.1016 / j.cad.2008.01.013
  • Бай, Сян; Лонгин, Латецкий; Вэньюй, Лю (2007), "Скелет обрезки по контуру перегородки с эволюцией дискретной кривой" (PDF) , IEEE Transactions на шаблон анализа и Machine Intelligence , 29 (3): 449-462, DOI : 10,1109 / TPAMI.2007.59 , PMID  17224615 , S2CID  14965041.
  • Блюм, Гарри (1967), «Преобразование для извлечения новых дескрипторов формы», в Wathen-Dunn, W. (ed.), Models for the Perception of Speech and Visual Form (PDF) , Cambridge, Massachusetts: MIT Press, стр. 362–380.
  • Бакш, Александр (2014), «Практическое введение в скелеты для наук о растениях», Applications in Plant Sciences , 2 (8): 1400005, doi : 10.3732 / apps.1400005 , PMC  4141713 , PMID  25202647.
  • Cychosz, Joseph (1994), Graphics gems IV , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр.  465–473 , ISBN 0-12-336155-9.
  • Догерти, Эдвард Р. (1992), Введение в морфологическую обработку изображений , ISBN 0-8194-0845-X.
  • Gonzales, Rafael C .; Вудс, Ричард Э. (2001), Цифровая обработка изображений , ISBN 0-201-18075-8.
  • Джейн, Анил К. (1989), Основы обработки цифровых изображений , Bibcode : 1989fdip.book ..... J , ISBN 0-13-336165-9.
  • Джайн, Рамеш; Кастури, Рангачар; Шунк, Брайан Г. (1995), Машинное зрение , ISBN 0-07-032018-7.
  • Ogniewicz, RL (1995), «Автоматическая обрезка медиальной оси на основе характеристик скелетного пространства», в Dori, D .; Брукштейн, А. (ред.), Форма, структура и распознавание образов , ISBN 981-02-2239-4.
  • Петру, Мария; Гарсия Севилья, Педро (2006), Обработка изображений с текстурой , ISBN 978-0-470-02628-1.
  • Серра, Жан (1982), Анализ изображений и математическая морфология , ISBN 0-12-637240-3.
  • Сетиан, Дж. А. (1999), Методы установки уровня и методы быстрого перехода , ISBN 0-521-64557-3.
  • Танненбаум, Allen (1996), "Три обрывки теории эволюции кривой в области компьютерного зрения", Математическое и компьютерное моделирование , 24 (5): 103-118, DOI : 10,1016 / 0895-7177 (96) 00117-3.

Программное обеспечение с открытым исходным кодом

  • ИТК (C ++)
  • Skeletonize3D (Java)
  • Самоцветы графики IV (C)
  • EVG-тонкий (C ++)
  • NeuronStudio

Внешние ссылки

  • Скелетонизация / трансформация медиальной оси
  • Скелеты региона
  • Скелеты в цифровой обработке изображений (pdf)
  • Сравнение 15 алгоритмов прореживания линий
  • Скелетонизация с использованием методов набора уровней
  • Кривые скелеты
  • Скелеты из облаков точек, сканированных лазером (Домашняя страница)