Абстрактный клеточный комплекс

В математике абстрактный клеточный комплекс — это абстрактное множество с топологией Александрова неотрицательное целое число, называемое размерностью , в котором каждой точке присвоено . Комплекс называется «абстрактным», поскольку его точки, называемые «ячейками», не являются подмножествами хаусдорфова пространства , как это имеет место в евклидовом и CW-комплексах . Абстрактные клеточные комплексы играют важную роль в анализе изображений и компьютерной графике .

История

Идея абстрактных клеточных комплексов ^[1] (также называемый абстрактными клеточными комплексами) относится к Дж. Листингу (1862). ^[2] и Э. Стейниц (1908). ^[3] Также А. В. Такер (1933), ^[4] К. Рейдемейстер (1938), ^[5] P.S. Aleksandrov (1956) ^[6] а также Р. Клетте и А. Розенфельд (2004). ^[7] описали абстрактные клеточные комплексы. Э. Стейниц определил абстрактный клеточный комплекс как $C=(E,B,dim)$ где E — абстрактное множество, B — асимметричное, иррефлексивное и транзитивное бинарное отношение, называемое ограничивающим отношением между элементами E , а dim — функция, присваивающая неотрицательное целое число каждому элементу E таким образом, что если $B(a,b)$ , затем $dim(a)<dim(b)$ . В. Ковалевский (1989) ^[8] описал абстрактные клеточные комплексы для 3D и более высоких измерений. Он также предложил множество приложений для анализа изображений. В своей книге (2008) ^[9] он предложил аксиоматическую теорию локально конечных топологических пространств , которые являются обобщением абстрактных клеточных комплексов. Книга содержит новые определения топологических шаров и сфер, независимых от метрики , новое определение комбинаторных многообразий и множество алгоритмов, полезных для анализа изображений.

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

Топология абстрактных клеточных комплексов основана на частичном порядке множества их точек или ячеек.

Понятие абстрактного клеточного комплекса, определенное Э. Стейницем, родственно понятию абстрактного симплициального комплекса и отличается от симплициального комплекса тем, что его элементы не являются симплексами : n- мерный элемент абстрактного комплекса не должен имеют n +1 нульмерных сторон, и не каждое подмножество множества нульмерных сторон ячейки является клеткой. Это важно, поскольку понятие абстрактных клеточных комплексов можно применить к двумерным и трехмерным сеткам, используемым при обработке изображений, чего нельзя сказать о симплициальных комплексах. Несимплициальный комплекс — это обобщение, которое делает возможным введение координат ячейки: существуют несимплициальные комплексы, которые являются декартовыми произведениями таких «линейных» одномерных комплексов, где каждая нульмерная ячейка, за исключением двух из них, ограничивает точно две одномерные ячейки. Только такие декартовы комплексы позволяют ввести такие координаты, что каждая ячейка имеет набор координат и любые две разные ячейки имеют разные наборы координат. Набор координат может служить именем каждой ячейки комплекса, что важно для обработки комплексов.

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

Понятие абстрактного клеточного комплекса существенно отличается от понятия CW-комплекса, поскольку абстрактный клеточный комплекс не является хаусдорфовым пространством . Это важно с точки зрения информатики, поскольку невозможно явно представить недискретное хаусдорфово пространство в компьютере. (Окрестность каждой точки такого пространства должна иметь бесконечное число точек).

Книга В. Ковалевского ^[10] содержит описание теории локально конечных пространств , являющихся обобщением абстрактных клеточных комплексов. Локально конечное пространство S подмножество S. определено в котором для каждой точки P из S — это набор точек , называется наименьшей окрестностью P. содержащее ограниченное число точек , Это подмножество , Бинарное отношение окрестности определяется в множестве точек локально конечного пространства S : Элемент (точка) b находится в отношении соседства с элементом a, если b принадлежит наименьшей окрестности элемента a . Были сформулированы новые аксиомы локально конечного пространства и доказано, что пространство S соответствует аксиомам только в том случае, если отношение окрестности антисимметрично и транзитивно. Отношение соседства представляет собой рефлексивную оболочку обратного ограничивающего отношения. Было показано, что классические аксиомы топологии можно вывести как теоремы из новых аксиом. Следовательно, локально конечное пространство, удовлетворяющее новым аксиомам, является частным случаем классического топологического пространства. Его топология представляет собой частично-положительная топология или топология Александрова .Абстрактный клеточный комплекс — это частный случай локально конечного пространства, в котором размерность определена для каждой точки. Показано, что размерность ячейки c абстрактного клеточного комплекса равна длине (количество ячеек минус 1) максимального ограничивающего пути, ведущего от любой ячейки комплекса к ячейке c . Ограничивающий путь — это последовательность ячеек, в которой каждая ячейка ограничивает следующую. Книга содержит теорию цифровых прямых отрезков в 2D-комплексах, многочисленные алгоритмы отслеживания границ в 2D и 3D, экономичного кодирования границ и точного восстановления подмножества по коду его границы. С использованием абстрактных комплексов ячеек разработаны и описаны эффективные алгоритмы трассировки, кодирования и полигонизации границ, а также обнаружения границ. ^[11]

Представление цифрового изображения абстрактного клеточного комплекса

Цифровое изображение может быть представлено двумерным абстрактным комплексом ячеек (ACC) путем разложения изображения на его размерные составляющие ACC: точки (0-ячейка), трещины/края (1-ячейка) и пиксели/грани (2-ячейка). .

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

См. также

Ссылки

^ Рейнхард Клетте: Клеточные комплексы во времени. http://spie.org/Publications/Proceedings/Paper/10.1117/12.404813
^ Листинг J.: «Перепись пространственных комплексов». Трактаты Королевского общества наук в Геттингене , т. 10, Геттинген, 1862, 97–182.
^ Стейниц Э.: «Вклад в анализ». Отчет заседания Берлинского математического общества , Том. 7, 1908, 29–49.
^ Такер А.В.: «Абстрактный подход к многообразиям», Annals Mathematics, т. 34, 1933, 191–243.
^ Райдемайстер К.: «Топология многогранников и комбинаторная топология комплексов». Академическое издательство Geest & Portig, Лейпциг, 1938 г. (второе издание 1953 г.)
^ Александров PS: Комбинаторная топология, Graylock Press, Рочестер, 1956,
^ Клетт Р. и Розенфельд. А.: «Цифровая геометрия», Elsevier, 2004.
^ Ковалевский, В.: «Конечная топология применительно к анализу изображений», Компьютерное зрение, графика и обработка изображений , т. 45, № 2, 1989, 141–161.
^ "Дом" . geometry.kovalevivian.de .
^ В. Ковалевский: «Геометрия локально конечных пространств». Редакция доктора Бербеля Ковалевского, Берлин, 2008 г. ISBN 978-3-9812252-0-4 .
^ Ковалевский В., Обработка изображений с помощью клеточной топологии, Springer 2021, ISBN 978-981-16-5771-9.

[1] Рейнхард Клетте: Клеточные комплексы во времени. http://spie.org/Publications/Proceedings/Paper/10.1117/12.404813

[2] Листинг J.: «Перепись пространственных комплексов». Трактаты Королевского общества наук в Геттингене , т. 10, Геттинген, 1862, 97–182.

[3] Стейниц Э.: «Вклад в анализ». Отчет заседания Берлинского математического общества , Том. 7, 1908, 29–49.

[4] Такер А.В.: «Абстрактный подход к многообразиям», Annals Mathematics, т. 34, 1933, 191–243.

[5] Райдемайстер К.: «Топология многогранников и комбинаторная топология комплексов». Академическое издательство Geest & Portig, Лейпциг, 1938 г. (второе издание 1953 г.)

[6] Александров PS: Комбинаторная топология, Graylock Press, Рочестер, 1956,

[7] Клетт Р. и Розенфельд. А.: «Цифровая геометрия», Elsevier, 2004.

[8] Ковалевский, В.: «Конечная топология применительно к анализу изображений», Компьютерное зрение, графика и обработка изображений , т. 45, № 2, 1989, 141–161.

[9] "Дом" . geometry.kovalevivian.de .

[10] В. Ковалевский: «Геометрия локально конечных пространств». Редакция доктора Бербеля Ковалевского, Берлин, 2008 г. ISBN 978-3-9812252-0-4 .

[11] Ковалевский В., Обработка изображений с помощью клеточной топологии, Springer 2021, ISBN 978-981-16-5771-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]