Цифровая топология имеет дело со свойствами и характеристиками двумерных (2D) или трехмерных (3D) цифровых изображений, которые соответствуют топологическим свойствам (например, связности ) или топологическим характеристикам (например, границам ) объектов.
Концепции и результаты цифровой топологии используются для определения и обоснования важных (низкоуровневых) алгоритмов анализа изображений , включая алгоритмы прореживания , отслеживания границ или поверхностей, подсчета компонентов или туннелей или заполнения областей.
История [ править ]
Цифровая топология впервые была исследована в конце 1960 - х лет по компьютерному анализу изображений исследователя Azriel Розенфельд (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 - замкнутое цифровое двумерное многообразие в прямой смежности (т. Е. (6,26) -поверхность в трехмерном пространстве). Формула для рода
- ,
где указывает набор точек поверхности, каждая из которых имеет i смежных точек на поверхности (Chen and Rong, ICPR 2008). Если M односвязно, т. Е. , То . (См. Также эйлерову характеристику .)
См. Также [ править ]
- Цифровая геометрия
- Комбинаторная топология
- Вычислительная геометрия
- Вычислительная топология
- Топологический анализ данных
- Топология
- Дискретная математика
Ссылки [ править ]
- Герман, Габор Т. (1998). Геометрия цифровых пространств . Прикладной и численный гармонический анализ. Бостон, Массачусетс: ISBN Birkhäuser Boston, Inc. 978-0-8176-3897-9. Руководство по ремонту 1711168 .
- Конг, Тат Юнг; Розенфельд, Азриэль, ред. (1996). Топологические алгоритмы обработки цифровых изображений . Эльзевир. ISBN 0-444-89754-2.
- Восс, Клаус (1993). Дискретные изображения, объекты и функции в Z п {\ Displaystyle \ mathbb {Z} ^ {п}} . Алгоритмы и комбинаторика. 11 . Берлин: Springer-Verlag. DOI : 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. DOI : 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.
