En matemáticas, un complejo de celdas abstracto es un conjunto abstracto con topología de Alexandrov en el que se asigna a cada punto un número entero no negativo llamado dimensión . El complejo se denomina "abstracto" ya que sus puntos, que se denominan "células", no son subconjuntos de un espacio de Hausdorff como es el caso del complejo Euclidiano y CW . Los complejos de células abstractas juegan un papel importante en el análisis de imágenes y los gráficos por computadora .
Historia
La idea de complejos celulares abstractos [1] (también denominados complejos celulares abstractos) se relaciona con J. Listing (1862) [2] y E. Steinitz (1908). [3] También AW Tucker (1933), [4] K. Reidemeister (1938), [5] PS Aleksandrov (1956) [6] así como R. Klette y A. Rosenfeld (2004) [7] han descrito resúmenes complejos celulares. E. Steinitz ha definido un complejo celular abstracto comodonde E es un conjunto abstracto , B es una relación binaria asimétrica, irreflexiva y transitiva llamada relación de límite entre los elementos de E y dim es una función que asigna un número entero no negativo a cada elemento de E de tal manera que si, luego . V. Kovalevsky (1989) [8] describió complejos celulares abstractos para 3D y dimensiones superiores. También sugirió numerosas aplicaciones al análisis de imágenes. En su libro (2008) [9] ha sugerido una teoría axiomática de espacios topológicos localmente finitos que son generalizaciones de complejos celulares abstractos. El libro contiene, entre otras, nuevas definiciones de bolas y esferas topológicas independientes de la métrica , una nueva definición de variedades combinatorias y muchos algoritmos útiles para el análisis de imágenes.
Resultados basicos
La topología de los complejos de celdas abstractas se basa en un orden parcial en el conjunto de sus puntos o celdas.
La noción de complejo celular abstracto definida por E. Steinitz está relacionada con la noción de complejo simplicial abstracto y se diferencia de un complejo simplicial por la propiedad de que sus elementos no son simples : un elemento n- dimensional de un complejo abstracto no debe tienen n +1 lados de dimensión cero, y no cada subconjunto del conjunto de lados de dimensión cero de una celda es una celda. Esto es importante ya que la noción de un complejo celular abstracto se puede aplicar a las cuadrículas bidimensionales y tridimensionales utilizadas en el procesamiento de imágenes, lo que no es cierto para los complejos simpliciales. Un complejo no simplicial es una generalización que hace posible la introducción de coordenadas de celda: hay complejos no simpliciales que son productos cartesianos de tales complejos unidimensionales "lineales" donde cada celda de dimensión cero, además de dos de ellos, limita exactamente dos celdas unidimensionales. Solo tales complejos cartesianos hacen posible introducir coordenadas tales que cada celda tenga un conjunto de coordenadas y dos celdas diferentes tengan diferentes conjuntos de coordenadas. El conjunto de coordenadas puede servir como nombre de cada celda del complejo, lo cual es importante para procesar complejos.
Los complejos abstractos permiten la introducción de la topología clásica (topología de Alexandrov) en las cuadrículas que son la base del procesamiento de imágenes digitales. Esta posibilidad define la gran ventaja de los complejos celulares abstractos: es posible definir exactamente las nociones de conectividad y del límite de subconjuntos. La definición de dimensión de células y de complejos es, en general, diferente de la de los complejos simpliciales (ver más abajo).
La noción de un complejo celular abstracto difiere esencialmente de la de un complejo CW porque un complejo celular abstracto no es un espacio de Hausdorff . Esto es importante desde el punto de vista de la informática, ya que es imposible representar explícitamente un espacio de Hausdorff no discreto en una computadora. (La vecindad de cada punto en tal espacio debe tener infinitos puntos).
El libro de V. Kovalevsky [10] contiene la descripción de la teoría de espacios localmente finitos que son una generalización de complejos celulares abstractos. Un espacio localmente finito S es un conjunto de puntos en los que un subconjunto de S se define para cada punto P de S . Este subconjunto que contiene un número limitado de puntos se llama el barrio más pequeño de P . Una relación de vecindad binaria se define en el conjunto de puntos del espacio localmente finito S : El elemento (punto) b está en la relación de vecindad con el elemento a si b pertenece a la vecindad más pequeña del elemento a . Se han formulado nuevos axiomas de un espacio localmente finito y se ha demostrado que el espacio S está de acuerdo con los axiomas solo si la relación de vecindad es antisimétrica y transitiva. La relación de vecindad es el casco reflexivo de la relación de límite inversa. Se demostró que los axiomas clásicos de la topología pueden deducirse como teoremas de los nuevos axiomas. Por lo tanto, un espacio localmente finito que satisface los nuevos axiomas es un caso particular de un espacio topológico clásico. Su topología es una topología poset o topología Alexandrov . Un complejo celular abstracto es un caso particular de un espacio localmente finito en el que la dimensión se define para cada punto. Se demostró que la dimensión de una celda c de un complejo celular abstracto es igual a la longitud (número de celdas menos 1) de la ruta delimitadora máxima que va desde cualquier celda del complejo a la celda c . La ruta delimitadora es una secuencia de celdas en la que cada celda limita con la siguiente. El libro contiene la teoría de los segmentos rectos digitales en complejos 2D, numerosos algoritmos para trazar límites en 2D y 3D, para codificar económicamente los límites y para reconstruir exactamente un subconjunto del código de su límite.
Representación de imágenes digitales complejas de células abstractas
Una imagen digital se puede representar mediante un complejo de celdas abstractas 2D (ACC) descomponiendo la imagen en sus componentes dimensionales de ACC: puntos (celda 0), grietas / bordes (1 celda) y píxeles / caras (2 celdas) .
Esta descomposición, junto con una regla de asignación de coordenadas para asignar de manera inequívoca las coordenadas de los píxeles de la imagen a los constituyentes dimensionales, permite realizar ciertas operaciones de análisis de imagen en la imagen con elegantes algoritmos como el trazado de límites de grietas , subdivisión digital de segmentos rectos , etc. regla asigna los puntos, las grietas y las caras a la coordenada superior izquierda del píxel. Estos constituyentes dimensionales no requieren una traducción explícita en sus propias estructuras de datos, pero pueden entenderse implícitamente y relacionarse con la matriz 2D, que es la representación de la estructura de datos habitual de una imagen digital. Esta regla de asignación de coordenadas y las representaciones de cada celda que incide en esta imagen se muestran en la imagen de la derecha.
Ver también
Referencias
- ^ Reinhard Klette: complejos celulares a través del tiempo. http://spie.org/Publications/Proceedings/Paper/10.1117/12.404813
- ^ Listado J .: "Der Census räumlicher Complexe". Abhandlungen der Königlichen Gesellschaft der Wissenschaften zu Göttingen , v. 10, Göttingen, 1862, 97–182.
- ^ Steinitz E .: "Análisis de Beiträge zur". Sitzungsbericht Berliner Mathematischen Gesellschaft , Band. 7, 1908, 29–49.
- ^ Tucker AW: "Un enfoque abstracto de las variedades", Annals Mathematics, v. 34, 1933, 191-243.
- ^ Reidemeister K .: "Topologie der Polyeder und kombinatorische Topologie der Komplexe". Akademische Verlagsgesellschaft Geest & Portig, Leipzig, 1938 (segunda edición 1953)
- ^ Aleksandrov PD: topología combinatoria, Graylock Press, Rochester, 1956,
- ^ Klette R. y Rosenfeld. A .: "Geometría digital", Elsevier, 2004.
- ^ Kovalevsky, V .: "Topología finita aplicada al análisis de imágenes", procesamiento de imágenes, gráficos y visión por computadora , v. 45, n. ° 2, 1989, 141-161.
- ^ http://www.geometry.kovalevsky.de .
- ^ V. Kovalevsky: "Geometría de espacios localmente finitos". Editora Dr. Bärbel Kovalevski, Berlín 2008. ISBN 978-3-9812252-0-4 .