Volver a apuntes de Topología Digital
1.4 Representaciones
de los conjuntos derivados
Con frecuencia necesitamos definir nuevos subconjuntos o particiones de una imagen en función de unas dadas, e.g., desarrollando operaciones teóricas de conjuntos en las dadas, o re-segmentándolas. Si estamos utilizando un tipo particular de representaciones, nos gustaría ser capaces de obtener las representaciones de los nuevos conjuntos directamente de las representaciones de los conjuntos originales. Los métodos para hacer esto en situaciones concretas serán descritos a lo largo de este capítulo; e.g., véanse las secciones 3.1a y 3.1b sobre el etiquetado de componentes conexas utilizando varias representaciones. En esta sección discutiremos brevemente el problema de desarrollar operaciones teóricas de conjuntos sobre las representaciones de un tipo dado. En aras de la simplicidad, trataremos particiones en un conjunto S y su complementario.
Si S y T se representan como matrices binarias cS y cT’ es trivial obtener Š, S È T, S Ç T, etc., mediante operaciones booleanas puntuales sobre estas matrices. Dichas operaciones pueden realizarse en un único paso paralelo en un ordenador multiprocesador o pueden realizarse en un único rastreo de cS y cT en un ordenador convencional.
Dada la representación de la longitud de la secuencia de S (y de T), obtenemos eso mismo de Š simplemente invirtiendo la designación del primer valor de cada fila. En el resto de este párrafo describiremos un algoritmo que crea la lista de secuencia L para S Ç T en una fila dada a partir de las listas L1 y L2 de S y T. Se pueden dar algoritmos análogos para otras funciones booleanas. Si tanto L1 como L2 comienzan con secuencias de 1’s, también lo hace L; en otro caso, L comienza con 0. Describiremos ahora cómo añadir con éxito secuencias a L examinando las partes iniciales de L1 y L2; cada vez que hacemos esto, borramos o truncamos la(s) secuencia(s) inicial(es) en L1 y L2. Los procesos se repiten entonces utilizando los recortados L1 y L2. Cuando están vacíos, tenemos el L deseado. Un contador está también asociado con L, y es establecido inicialmente en 0; su papel será explicado en el paso (b) del algoritmo.
(a) Supongamos que ambos L1 y L2 (actualmente) comienzan con secuencias de 1’s, r1 y r2, de longitudes | r1 | £ | r2 | . En este caso añadimos una secuencia de 1’s de longitud | r1 | a b; borramos la secuencia inicial de L1; y cortamos la secuencia inicial de L2 a una longitud | r1 | - | r2 | (o borrarla, si | r1 | = | r2 | ). Nótese que al menos uno de L1 o L2 comienzan ahora con una secuencia de 0’s.
(b) Supongamos que L1 comienza con una secuencia r1 de 0’s, y L2 con una secuencia de 1’s o con una secuencia más corta de 0’s. Sumamos longitudes de secuencia en L2 hasta que alcancemos | r1 | , i.e.,
| r21 | + | r22 | + . . . + | r2, k-1 | £ | r1 | < | r21 | + | r22 | + . . . + | r2k |
(b1) Si r2k es una secuencia de 1’s, truncamos a la longitud
| r2k | - (| r1 | - | r21 | - | r22 | - . . . - | r2, k-1 | );
borramos r1 de L1; añadimos una secuencia de 0’s de longitud | r1 | + C a L, donde C es el valor del contador; y reseteamos el contador a 0.
(b2) Si r2k es una secuencia de 0’s, truncamos como antes; borramos r1 de L1; y sumamos | r1 | al contador. En este caso L2 todavía comienza con una secuencia de 0’s, por lo que todavía estamos en el caso (b), posiblemente con los papeles de L1 y L2 cambiados.
Dados los MATs de S y T, conseguimos un MAT redundante para S È T tomando simplemente su unión. Un procedimiento para construir un MAT para S Ç T encontrando las intersecciones maximales de los bloques en los MATs de S y T se describe en [49]; los detalles no se darán aquí.
El árbol de cuadrados de Š es el mismo que el de S con los nodos hojas “negros” (= nodos correspondientes a bloques de 1’s) cambiados a “blanco” (círculos huecos frente a los rellenos – negros - ) y viceversa. Para conseguir el árbol de cuadrados de S È T a partir de los de S y T, recorremos los dos árboles simultáneamente. Donde coincidan, el nuevo árbol es igual. Si S tiene un nodo gris (= nodo no hoja) donde T tiene un nodo negro, el nuevo árbol logra un nodo negro; si T tiene un nodo blanco ahí, copiamos el subárbol de S de ese nodo gris en el nuevo árbol; si S tiene un nodo blanco y T uno negro, el nuevo árbol consigue un nodo negro. El algoritmo para S Ç T es exactamente análogo, con los papeles de blancos y negros cambiados. El tiempo necesario para estos algoritmos es proporcional al número de nodos en el más pequeño de los dos árboles [27, 72]
Los códigos de fisura de los bordes de Š son los mismos que los de S (pero en orden inverso, si queremos mantener un criterio lo haremos como el orden del seguimiento de bordes). Construir códigos de cadena de los bordes de Š a partir de los de S es algo más complejo; los detalles se omitirán aquí. Tanto para los códigos de fisura como para los de cadena, es bastante complicado construir estos códigos de S È T o S Ç T a partir de los de S y T; en concreto, esto implica encontrar qué pares de bordes rodean a otro, y también encontrar todas las intersecciones de cada par de bordes. Las representaciones de los bordes no son adecuadas para llevar a cabo operaciones teóricas de conjuntos.