Топологический скелет

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

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

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

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

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

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

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

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

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

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

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

$B\subseteq A$ , и
Если другой диск D содержит B , то $D\not \subseteq A$ .

Один из способов определения скелета формы A — это набор центров всех максимальных дисков A. в ^[9]

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

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

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

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

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

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

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

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

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

Использование морфологических операторов (см. Морфологический скелет ^[10])
на основе формы Дополнение морфологических операторов обрезкой ^[11]
Использование пересечений расстояний от граничных участков ^[12]
Использование эволюции кривой ^[13]^[14]
Использование наборов уровней ^[5]
Нахождение точек гребня по функции расстояния ^[3]
«Пилинг» формы, без изменения топологии, до сходимости ^[15]
Алгоритм прореживания Чжан-Суэна ^[16]

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

См. также

Примечания

^ Джайн, Кастури и Шунк (1995) , раздел 2.5.10, с. 55; Голландия и Гримсон (2000) ; Догерти (1992) ; Огневич (1995) .
^ Перейти обратно: ^а ^б Гонсалес и Вудс (2001) , раздел 11.1.5, с. 650
^ Перейти обратно: ^а ^б ^с ^д А. К. Джайн ( 1989 ), раздел 9.9, с. 382.
^ Серра (1982) .
^ Перейти обратно: ^а ^б Сетиан (1999) , раздел 17.5.2, с. 234.
^ Абейсингхе и др. (2008)
^ Бакш (2014)
^ Гарри Блюм ( 1967 )
^ АК Джайн ( 1989 ), раздел 9.9, с. 387.
^ Перейти обратно: ^а ^б Гонсалес и Вудс (2001) , раздел 9.5.7, с. 543.
^ Абейсингхе и др. (2008) .
^ Киммел и др. (1995) .
^ Танненбаум (1996)
^ Бай, Лонгин и Веньюй (2007) .
^ АК Джайн ( 1989 ), раздел 9.9, с. 389.
^ Чжан, Тайвань; Суен, Калифорния (1 марта 1984 г.). «Быстрый параллельный алгоритм прореживания цифровых шаблонов» . Коммуникации АКМ . 27 (3): 236–239. дои : 10.1145/357994.358023 . ISSN 0001-0782 . S2CID 39713481 .

Ссылки

Абейсингхе, Сасакти; Бейкер, Мэтью; Чиу, Вау; Джу, Тао (2008), «Скелетирование объемов в оттенках серого без сегментации для понимания формы», IEEE Int. Конф. Моделирование формы и приложения (SMI 2008) (PDF) , стр. 63–71, doi : 10.1109/SMI.2008.4547951 , ISBN 978-1-4244-2260-9 , S2CID 15148296 .
Абейсингхе, Сасакти; Джу, Тао; Бейкер, Мэтью; Чиу, Ва (2008), «Моделирование формы и сопоставление при идентификации трехмерных белковых структур» (PDF) , Компьютерное проектирование , 40 (6), Elsevier: 708–720, doi : 10.1016/j.cad.2008.01.013
Бай, Сян; Лонгин, Латецкий; Вэнью, Лю (2007), «Скелетная обрезка путем разделения контуров с дискретной эволюцией кривой» (PDF) , Транзакции IEEE по анализу шаблонов и машинному интеллекту , 29 (3): 449–462, doi : 10.1109/TPAMI.2007.59 , PMID 17224615 , S2CID 14965041 .
Блюм, Гарри (1967), «Преобразование для извлечения новых дескрипторов формы», в Уотен-Данн, В. (редактор), Модели восприятия речи и визуальной формы (PDF) , Кембридж, Массачусетс: MIT Press, стр. 362–380 .
Бакш, Александр (2014), «Практическое введение в скелеты для науки о растениях», Applications in Plant Sciences , 2 (8): 1400005, doi : 10.3732/apps.1400005 , PMC 4141713 , PMID 25202647 .
Цихош, Джозеф (1994), Graphics Gems IV , Сан-Диего, Калифорния, США: Academic Press Professional, Inc., стр. 465–473 , ISBN 0-12-336155-9 .
Догерти, Эдвард Р. (1992), Введение в морфологическую обработку изображений , ISBN 0-8194-0845-Х .
Голландия, Полина ; Гримсон, В. Эрик Л. (2000), «Скелеты с фиксированной топологией» (PDF) , Конференция 2000 г. по компьютерному зрению и распознаванию образов (CVPR 2000), 13–15 июня 2000 г., Хилтон-Хед, Южная Каролина, США , Компьютерное общество IEEE, стр. 1010–1017, doi : 10.1109/CVPR.2000.855792 , S2CID 9916140.
Гонсалес, Рафаэль К.; Вудс, Ричард Э. (2001), Цифровая обработка изображений , ISBN 0-201-18075-8 .
Джайн, Анил К. (1989), Основы цифровой обработки изображений , Bibcode : 1989fdip.book.....J , ISBN 0-13-336165-9 .
Джайн, Рамеш; Кастури, Рангачар; Шунк, Брайан Г. (1995), Машинное зрение , ISBN 0-07-032018-7 .
Киммел, Рон; Шакед, Дорон; Кирьяти, Наум; Брукштейн, Альфред М. (1995), «Скелетизация с помощью карт расстояний и наборов уровней» (PDF) , Компьютерное зрение и понимание изображений , 62 (3): 382–391, doi : 10.1006/cviu.1995.1062
Огневич, Р.Л. (1995), «Автоматическая обрезка медиальной оси на основе характеристик скелетного пространства», Дори, Д.; Брукштейн А. (ред.), Распознавание формы, структуры и образов , 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), «Три фрагмента теории эволюции кривых в компьютерном зрении», Mathematical and Computer Modeling , 24 (5): 103–118, doi : 10.1016/0895-7177(96)00117-3 .

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

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

[1] Джайн, Кастури и Шунк (1995) , раздел 2.5.10, с. 55; Голландия и Гримсон (2000) ; Догерти (1992) ; Огневич (1995) .

[gonzales-2] Перейти обратно: ^а ^б Гонсалес и Вудс (2001) , раздел 11.1.5, с. 650

[jain-3] Перейти обратно: ^а ^б ^с ^д А. К. Джайн ( 1989 ), раздел 9.9, с. 382.

[4] Серра (1982) .

[sethian-5] Перейти обратно: ^а ^б Сетиан (1999) , раздел 17.5.2, с. 234.

[6] Абейсингхе и др. (2008)

[7] Бакш (2014)

[8] Гарри Блюм ( 1967 )

[9] АК Джайн ( 1989 ), раздел 9.9, с. 387.

[gonzales543-10] Перейти обратно: ^а ^б Гонсалес и Вудс (2001) , раздел 9.5.7, с. 543.

[11] Абейсингхе и др. (2008) .

[FOOTNOTEKimmelShakedKiryatiBruckstein1995-12] Киммел и др. (1995) .

[13] Танненбаум (1996)

[14] Бай, Лонгин и Веньюй (2007) .

[15] АК Джайн ( 1989 ), раздел 9.9, с. 389.

[16] Чжан, Тайвань; Суен, Калифорния (1 марта 1984 г.). «Быстрый параллельный алгоритм прореживания цифровых шаблонов» . Коммуникации АКМ . 27 (3): 236–239. дои : 10.1145/357994.358023 . ISSN 0001-0782 . S2CID 39713481 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]