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

Цифровая топология изучает свойства и особенности двумерных (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-смежности соответствуетоткрывать или закрывать множества в топологии ячеек трехмерной сетки . Топология ячеек сетки также применима к многоуровневым (например, цветным) 2D- или 3D-изображениям.например, на основе общего порядка возможных значений изображения и применения «правила максимальной метки» (см. книгу Клетте и Розенфельда, 2004).

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

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

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

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

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

См. также

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

Ссылки

• Герман, Габор Т. (1998). Геометрия цифровых пространств . Прикладной и численный гармонический анализ. Бостон, Массачусетс: ISBN Birkhäuser Boston, Inc.  978-0-8176-3897-9 . МР   1711168 .
• Конг, Тат Юнг; Розенфельд, Азриэль, ред. (1996). Топологические алгоритмы цифровой обработки изображений . Эльзевир. ISBN  0-444-89754-2 .
• Восс, Клаус (1993). Дискретные изображения, объекты и функции в $\mathbb {Z} ^{n}$. Алгоритмы и комбинаторика. Том. 11. Берлин: Шпрингер-Верлаг. дои : 10.1007/978-3-642-46779-0 . ISBN  0-387-55943-4 . МР   1224678 .
• Чен, Л. (2004). Дискретные поверхности и многообразия: теория цифрово-дискретной геометрии и топологии . СП Вычисления. ISBN  0-9755122-1-8 .
• Бердок, Р.; Розенфельд, Азриэль (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-Х . МР   0643798 .
• Владимир Алексеевич Ковалевский. (2008). Геометрия локально конечных пространств . Берлин: Издательство доктора Бербеля Ковалевского. 2008. ISBN  978-3-9812252-0-4 .