Топологический каркас - Topological skeleton

Форма и ее скелет, вычисленные с помощью алгоритма прореживания с сохранением топологии.

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

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

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

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

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

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

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

Основная статья: Преобразование Grassfire

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

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

А диск (или же мяч ) B как говорят максимальный в комплекте А если

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Примечания

  1. ^ Джайн, Кастури и Шунк (1995), Раздел 2.5.10, с. 55.
  2. ^ а б Гонзалес и Вудс (2001), Раздел 11.1.5, с. 650
  3. ^ http://people.csail.mit.edu/polina/papers/skeletons_cvpr00.pdf
  4. ^ Догерти (1992).
  5. ^ Огневич (1995).
  6. ^ а б c d А. К. Джайн (1989 ), Раздел 9.9, с. 382.
  7. ^ Серра (1982).
  8. ^ а б Сетиан (1999), Раздел 17.5.2, стр. 234.
  9. ^ Abeysinghe et al. (2008)
  10. ^ Бакш (2014)
  11. ^ Гарри Блюм (1967 )
  12. ^ А. К. Джайн (1989 ), Раздел 9.9, с. 387.
  13. ^ а б Гонзалес и Вудс (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. ^ Бай, Лонгин и Вэнью (2007).
  18. ^ А. К. Джайн (1989 ), Раздел 9.9, с. 389.

Рекомендации

  • Абейсингхе, Сасакти; Бейкер, Мэтью; Чиу, Вау; Цзюй, Тао (2008 г.), «Скелетонизация без сегментации полутоновых объемов для понимания формы», IEEE Int. Конф. Моделирование форм и приложения (SMI 2008) (PDF), стр. 63–71, Дои:10.1109 / СМИ.2008.4547951, ISBN  978-1-4244-2260-9, S2CID  15148296.
  • Абейсингхе, Сасакти; Цзюй, Дао; Бейкер, Мэтью; Чиу, Вау (2008), «Моделирование формы и сопоставление в идентификации трехмерных белковых структур» (PDF), Системы автоматизированного проектирования, Эльзевьер, 40 (6): 708–720, Дои:10.1016 / j.cad.2008.01.013
  • Бай, Сян; Лонгин, Латецкий; Вэнью, Лю (2007), «Обрезка скелета путем разбиения контура с эволюцией дискретной кривой» (PDF), IEEE Transactions по анализу шаблонов и машинному анализу, 29 (3): 449–462, Дои:10.1109 / TPAMI.2007.59, PMID  17224615, S2CID  14965041.
  • Блюм, Гарри (1967), «Преобразование для извлечения новых дескрипторов формы», в Wathen-Dunn, W. (ed.), Модели восприятия речи и визуальной формы (PDF), Кембридж, Массачусетс: MIT Press, стр. 362–380..
  • Бакш, Александр (2014), «Практическое введение в скелеты для науки о растениях», Приложения в науках о растениях, 2 (8): 1400005, Дои:10.3732 / apps.1400005, ЧВК  4141713, PMID  25202647.
  • Цихос, Джозеф (1994), Самоцветы графики 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, R. L. (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.
  • Танненбаум, Аллен (1996), "Три фрагмента теории эволюции кривой в компьютерном зрении", Математическое и компьютерное моделирование, 24 (5): 103–118, Дои:10.1016/0895-7177(96)00117-3.

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

внешняя ссылка