Форма и ее скелет, вычисленные с помощью алгоритма прореживания, сохраняющего топологию.
В анализе формы скелет ( или топологический скелет ) формы — это тонкая версия этой формы, которая равноудалена от ее границ . Скелет обычно подчеркивает геометрические и топологические свойства формы, такие как ее связность , топология , длина , направление и ширина . Вместе с расстоянием его точек до границы формы скелет также может служить представлением формы (они содержат всю информацию, необходимую для реконструкции формы).
Скелеты имеют несколько различных математических определений в технической литературе, и существует много различных алгоритмов для их вычисления. Также можно найти различные варианты скелета, включая прямые скелеты , морфологические скелеты и т. д.
В технической литературе понятия скелета и медиальной оси используются как взаимозаменяемые некоторыми авторами, [1] [2], в то время как некоторые другие авторы [3] [4] [5] считают их связанными, но не одинаковыми. Аналогично, понятия скелетизации и истончения также рассматриваются некоторыми как идентичные, [2] а другими нет. [3]
Скелеты имеют несколько различных математических определений в технической литературе; большинство из них приводят к схожим результатам в непрерывных пространствах , но обычно дают разные результаты в дискретных пространствах .
Точки гашения модели распространения пожара
В своей основополагающей статье Гарри Блюм [8] из Исследовательских лабораторий ВВС Кембриджа на базе ВВС Ханском в Бедфорде, Массачусетс , определил срединную ось для вычисления скелета формы, используя интуитивную модель распространения огня на травяном поле, где поле имеет форму заданной формы. Если кто-то «поджигает» все точки на границе этого травяного поля одновременно, то скелет представляет собой набор точек гашения, т. е. тех точек, где встречаются два или более волновых фронта. Это интуитивное описание является отправной точкой для ряда более точных определений.
Центры максимальных дисков (или шаров)
Диск (или шар ) B называется максимальным в множестве A , если
, и
Если другой диск D содержит B , то .
Один из способов определения скелета фигуры A — это набор центров всех максимальных дисков в A. [9 ]
Центры двухкасательных окружностей
Скелет формы A также можно определить как набор центров дисков, которые касаются границы A в двух или более местах. [10] Это определение гарантирует, что точки скелета равноудалены от границы формы и математически эквивалентно преобразованию срединной оси Блюма.
Гребни функции расстояния
Во многих определениях скелета используется концепция функции расстояния , которая представляет собой функцию, возвращающую для каждой точки x внутри фигуры A ее расстояние до ближайшей точки на границе A. Использование функции расстояния очень привлекательно, поскольку ее вычисление происходит относительно быстро.
Одно из определений скелета с использованием функции расстояния — это хребты функции расстояния. [3] В литературе распространено ошибочное утверждение, что скелет состоит из точек, которые являются «локально максимальными» в преобразовании расстояния. Это просто не так, как покажет даже поверхностное сравнение преобразования расстояния и полученного скелета. Хребты могут иметь различную высоту, поэтому точка на хребте может быть ниже, чем ее непосредственный сосед на хребте. Таким образом, это не локальный максимум, даже если она принадлежит хребту. Однако он находится менее далеко по вертикали, чем того требует его расстояние до земли. В противном случае он был бы частью склона.
Другие определения
Точки без сегментов вверх по течению в функции расстояния. Сегмент вверх по течению точки x — это сегмент, начинающийся в x , который следует по максимальному градиентному пути.
Точки, в которых градиент функции расстояния отличен от 1 (или, что эквивалентно, не определены достаточно хорошо)
Наименьший возможный набор линий, сохраняющих топологию и равноудалённых от границ
^ ab Gonzales & Woods (2001), Раздел 9.5.7, стр. 543.
^ Абейсингхе и др. (2008).
^ Киммел и др. (1995).
^ Танненбаум (1996)
^ Бай, Лонгин и Вэньюй (2007).
^ АК Джайн (1989), раздел 9.9, с. 389.
^ Чжан, TY; Суэн, CY (1984-03-01). "Быстрый параллельный алгоритм для прореживания цифровых шаблонов". Communications of the ACM . 27 (3): 236–239. doi :10.1145/357994.358023. ISSN 0001-0782. S2CID 39713481.
Ссылки
Абейсингхе, Сасакти; Бейкер, Мэтью; Чиу, Вах; Джу, Тао (2008), «Скелетирование объемов в оттенках серого без сегментации для понимания формы», IEEE Int. Conf. Shape Modeling and Applications (SMI 2008) (PDF) , стр. 63–71, doi :10.1109/SMI.2008.4547951, ISBN 978-1-4244-2260-9, S2CID 15148296.
Абейсингхе, Сасакти; Джу, Тао; Бейкер, Мэтью; Чиу, Вах (2008), «Моделирование и сопоставление форм при идентификации трехмерных структур белков» (PDF) , Computer-Aided Design , 40 (6), Elsevier: 708–720, doi :10.1016/j.cad.2008.01.013
Бай, Сян; Лонгин, Латеки; Вэнью, Лю (2007), «Отсечение скелета путем контурного разбиения с дискретной эволюцией кривой» (PDF) , IEEE Transactions on Pattern Analysis and Machine Intelligence , 29 (3): 449–462, doi :10.1109/TPAMI.2007.59, PMID 17224615, S2CID 14965041.
Блум, Гарри (1967), «Преобразование для извлечения новых дескрипторов формы», в Wathen-Dunn, W. (ред.), Модели восприятия речи и визуальной формы (PDF) , Кембридж, Массачусетс: 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.
Голланд, Полина ; Гримсон, В. Эрик Л. (2000), «Скелеты с фиксированной топологией» (PDF) , Конференция 2000 по компьютерному зрению и распознаванию образов (CVPR 2000), 13–15 июня 2000 г., Хилтон-Хед, Южная Каролина, США , IEEE Computer Society, стр. 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.
Sethian, JA (1999), Методы установки уровня и методы быстрого марширования , ISBN 0-521-64557-3.
Танненбаум, Аллен (1996), «Три фрагмента теории эволюции кривых в компьютерном зрении», Математическое и компьютерное моделирование , 24 (5): 103–118, doi : 10.1016/0895-7177(96)00117-3.
