Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

История [ править ]

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

Основные результаты [ править ]

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

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

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

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

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

Абстрактное сотовое сложное цифровое представление изображения [ править ]

Цифровое изображение 3x4 разложено на его размерные составляющие Abstract Cell Complex.

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

Присвоение координат ACC цифрового изображения

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

См. Также [ править ]

  • Симплициальный комплекс
  • Кубический комплекс


Ссылки [ править ]

  1. ^ Райнхард Клетте: Клеточные комплексы во времени. http://spie.org/Publications/Proceedings/Paper/10.1117/12.404813
  2. ^ Листинг J .: "Der Census räumlicher Complexe". Abhandlungen der Königlichen Gesellschaft der Wissenschaften zu Göttingen , v. 10, Göttingen, 1862, 97–182.
  3. ^ Steinitz E .: "Анализ Beiträge zur". Sitzungsbericht Berliner Mathematischen Gesellschaft , Band. 7, 1908, 29–49.
  4. ↑ Tucker AW: «Абстрактный подход к многообразиям», Annals Mathematics, v. 34, 1933, 191–243.
  5. ↑ Reidemeister K .: "Topologie der Polyeder und kombinatorische Topologie der Komplexe". Akademische Verlagsgesellschaft Geest & Portig, Лейпциг, 1938 г. (второе издание 1953 г.)
  6. ^ Александров PS: комбинаторная топология, Graylock Press, Rochester, 1956,
  7. ^ Клетт Р. и Розенфельд. А .: «Цифровая геометрия», Elsevier, 2004.
  8. ↑ Ковалевский, В .: «Конечная топология в приложении к анализу изображений», Компьютерное зрение, графика и обработка изображений , т. 45, № 2, 1989, 141–161.
  9. ^ http://www.geometry.kovalevsky.de .
  10. ^ В. Ковалевский: "Геометрия локально конечных пространств". Редакция доктора Бербеля Ковалевски, Берлин, 2008. ISBN  978-3-9812252-0-4 .