Цифровая топология - Digital topology

Цифровая топология занимается свойствами и особенностями двумерный (2D) или трехмерный (3D) цифровые изображения которые соответствуют топологический свойства (например, связность ) или топологические особенности (например, границы ) объектов.

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

История

Впервые цифровая топология была изучена в конце 1960-х гг. компьютерный анализ изображений Исследователь Азриэль Розенфельд (1931–2004), чьи публикации по этой теме сыграли важную роль в становлении и развитии этой области. Сам термин «цифровая топология» был изобретен Розенфельдом, который впервые использовал его в публикации 1973 года.

Связанная работа под названием топология ячейки сетки, что можно рассматривать как ссылку на классический комбинаторная топология, появился в книге Павел Александров и Хайнц Хопф, Топология I (1935). Розенфельд и другие. предлагаемые цифровые возможности подключения, такие как 4-связность и 8-связность в двух измерениях, а также 6-связность и 26-связность в трех измерениях. Метод маркировки для вывода связного компонента был изучен в 1970-х годах. Теодосиос Павлидис (1982) предложил использовать алгоритмы теории графов, такие как поиск в глубину метод поиска связанных компонентов. Владимир Ковалевский (1989) расширил топологию ячеек двумерной сетки Александрова – Хопфа до трех и более измерений. Он также предложил (2008) более общую аксиоматическую теорию локально конечные топологические пространства и абстрактные клеточные комплексы ранее предложенный Эрнст Стейниц (1908). Это Топология Александрова. Книга 2008 года содержит новые определения топологических шаров и сфер, не зависящих от метрики, и многочисленные приложения к анализу цифровых изображений.

В начале 1980-х гг. цифровые поверхности были изучены. Дэвид Моргенталер и Розенфельд (1981) дали математическое определение поверхностей в трехмерном цифровом пространстве. Это определение содержит в общей сложности девять типов цифровых поверхностей. В цифровой коллектор изучалась в 1990-е гг. Рекурсивное определение цифрового k-многообразия было интуитивно предложено Ченом и Чжаном в 1993 году. Многие приложения были найдены в обработке изображений и компьютерном зрении.

Основные результаты

Базовый (ранний) результат в цифровой топологии говорит о том, что двоичные 2D-изображения требуют альтернативного использования 4- или 8-смежности или "подключение пикселей "(для" объекта "или" не объекта "пиксели ) для обеспечения базовой топологической двойственности разделения и связности. Это альтернативное использование соответствует открытым или закрытым наборам в 2D. топология ячейки сетки, и результат обобщается на 3D: альтернативное использование 6- или 26-смежности соответствует открытым или закрытым множествам в 3D. топология ячейки сетки. Топология ячеек сетки также применима к многоуровневым (например, цветным) 2D или 3D изображениям, например, на основе общего порядка возможных значений изображения и применения «правила максимальной метки» (см. Книгу Klette and Rosenfeld, 2004).

Цифровая топология тесно связана с комбинаторная топология. Основные различия между ними: (1) цифровая топология в основном изучает цифровые объекты, образованные ячейками сетки,^{[требуется разъяснение ]} и (2) цифровая топология также имеет дело с нежордановыми многообразиями.

Комбинаторное многообразие - это разновидность многообразия, которое является дискретизацией многообразия. Обычно это означает кусочно-линейное многообразие сделан симплициальные комплексы. А цифровой коллектор представляет собой особый вид комбинаторного многообразия, которое определяется в цифровом пространстве, то есть в пространстве ячеек сетки.

Цифровая форма Теорема Гаусса – Бонне это: Пусть M быть закрытым цифровым 2D многообразие в непосредственной близости (т.е. (6,26) -поверхность в 3D). Формула для рода

${ displaystyle g = 1 + (M_ {5} + 2M_ {6} -M_ {3}) / 8}$,

куда ${ displaystyle M_ {i}}$ указывает набор точек поверхности, каждая из которых имеет я соседние точки на поверхности (Chen and Rong, ICPR 2008). M односвязно, т. е. ${ displaystyle g = 0}$, тогда ${ displaystyle M_ {3} = 8 + M_ {5} + 2M_ {6}}$. (Смотрите также Эйлерова характеристика.)

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

• Цифровая геометрия
• Комбинаторная топология
• Вычислительная геометрия
• Вычислительная топология
• Топологический анализ данных
• Топология
• Дискретная математика

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

• Герман, Габор Т. (1998). Геометрия цифровых пространств. Прикладной и численный гармонический анализ. Бостон, Массачусетс: Birkhäuser Boston, Inc. ISBN  978-0-8176-3897-9. МИСТЕР  1711168.
• Конг, Тат Юнг; Розенфельд, Азриэль, ред. (1996). Топологические алгоритмы обработки цифровых изображений. Эльзевир. ISBN  0-444-89754-2.
• Восс, Клаус (1993). Дискретные изображения, объекты и функции в ${ Displaystyle mathbb {Z} ^ {п}}$. Алгоритмы и комбинаторика. 11. Берлин: Springer-Verlag. Дои:10.1007/978-3-642-46779-0. ISBN  0-387-55943-4. МИСТЕР  1224678.
• Чен, Л. (2004). Дискретные поверхности и многообразия: теория цифрово-дискретной геометрии и топологии. SP Computing. ISBN  0-9755122-1-8.
• Klette, R .; Розенфельд, Азриэль (2004). Цифровая геометрия. Морган Кауфманн. ISBN  1-55860-861-3.
• Моргенталер, Дэвид Дж .; Розенфельд, Азриэль (1981). «Поверхности в трехмерных цифровых изображениях». Информация и контроль. 51 (3): 227–247. Дои:10.1016 / S0019-9958 (81) 90290-4. МИСТЕР  0686842.
• Павлидис, Тео (1982). Алгоритмы обработки графики и изображений. Конспект лекций по математике. 877. Роквилл, Мэриленд: Computer Science Press. ISBN  0-914894-65-X. МИСТЕР  0643798.
• Ковалевский, Владимир (2008). Геометрия локально конечных пространств. Берлин: Издательство доктора Бербеля Ковалевски. ISBN  978-3-9812252-0-4.