2.2 Bordes
Recordemos que el borde S’ de un conjunto S es el conjunto de puntos de S que son 4-adyacentes a Š. Para encontrar todos los puntos del borde de S, podemos rastrear cS y comprobar los cuatro vecinos de cada 1 para ver si alguno de ellos es 0 (o viceversa). En un ordenador multiprocesador, podemos encontrar el borde realizando una operación Booleana en cada punto P de cS. Sean Pn, Ps, Pe, Pw los cuatro vecinos de P; entonces calculamos
donde las barras sobre las letras indican la negación lógica . Evidentemente, esto produce 1’s en los puntos de borde de S y 0’s en cualquier otro lugar.
En esta sección describimos algoritmos para encontrar, seguir, y codificar las bordes individuales entre componentes de S y Š, y para reconstruir S desde esos códigos de borde. Estos algoritmos proporcionan los medios para la conversión entre el bit plano y la representación del código de borde. La conversión entre árbol de cuadrados y los códigos de borde será también discutida brevemente .
Continuaremos asumiendo aquí que S no toca los límites de la imagen. Esto hará innecesario para nuestros algoritmos manejar los casos especiales que involucren vecinos que se encuentran fuera de la imagen.
a. Seguimiento de fisuras (crack
following)
Sean C, D componentes de S y Š, respectivamente, y sean P, Q puntos 4-adyacentes a C y D, de tal forma que (P,Q) define una de las fisuras en el (C, D)-borde. Sean U, V el par de puntos que encaramos cuando permanecemos en la fisura entre P y Q con P a nuestra izquierda, con U, V 4-adyacentes a P, Q respectivamente, i.e.,
(Definir U, V en términos de P a la izquierda implica que los bordes externos serán seguidos en el sentido contrario de las agujas del reloj y los agujeros de bordes en el sentido de las agujas del reloj; el inverso sería cierto si tuviéramos P a la derecha). Entonces las siguientes reglas definen la próxima fisura (P’, Q’) a lo largo del (C, D)-borde:
(1) Si usamos 8-conectividad para C
(2) Si usamos 4-conectividad para C
El algoritmo se para cuando llegamos al par inicial otra vez.
Para generar el código de fisura correspondiente a este recorrido del borde, nótese que las cuatro configuraciones iniciales de P, Q, U y V dadas más arriba se corresponden con los códigos de fisura de 0, 1, 2 y 3, respectivamente. Para determinar el código de (P’, Q’) a partir de eso para (P, Q), simplemente añadimos un 1 (módulo 4) si giramos a la izquierda, restamos 1 (módulo 4) si giramos a la derecha, y usamos el mismo código si no hacemos ningún giro. (De forma alternativa, las reglas de giro nos dan el código de fisura de diferencia directamente).
b. Seguimiento de
borde
Los algoritmos para el seguimiento del D-borde de C son algo más complicados. Sean P, Q como antes, y sean los ocho vecinos de P, en el sentido contrario de las agujas del reloj orden empezando desde Q, Q = R1, R2, ..., R8. (Usar este orden implica que los bordes externos van a ser seguidas en el sentido contrario de las agujas del reloj y los agujeros de borde en sentido de las agujas del reloj.) Asumimos que C no consta solamente de un punto aislado {P}. Las siguientes reglas definen un nuevo par P’, Q’:
(1) Si usamos 8-conectividad para C:
Sea Ri el primero de los R’s que es 1 (tal R existe ya que P no está aislado). Entonces P’ = Ri, Q’= Ri-1.
(2) Si usamos 4-conectividad para C:
Sea Ri el primer 4-vecino que es 1 (i.e., el primero de R3, R5, R7). Si Ri-1= 0, tomamos P’ = Ri, Q’ = Ri-1; si Ri-1 = 1, tomamos P’ = Ri-1, Q’ = Ri-2.
El algoritmo se para cuando llegamos al P inicial otra vez, con tal que encontremos el Q inicial (como uno de los R’s) antes de encontrar el siguiente P’. Esta última condición es necesaria porque un borde puede pasar a través de un punto dos veces, como veremos en el ejemplo que sigue a continuación.
Como ejemplo, sean C, P y Q como en Fig. 9a. Los R’s y los nuevos P, Q en los dos primeros pasos del algoritmo se muestran en las Figs. 9b y 9c. Si usamos 8-conectividad para C, los siguientes tres pasos se muestran en Figs. 9d-9f; si usamos 4-conectividad, el segundo paso (Fig. 9c) es seguido directamente por la Fig. 9f’. Nótese que P es el mismo en las Figs. 9e y 9c, pero el algoritmo no se detendría incluso si éste hubiera sido el P inicial, ya que el Q de la Fig. 9c no es uno de los R’s encontrados en el siguiente paso antes de encontrar un 1. Observaciones análogas se aplican a las Figs. 9b y 9f’. En ambos casos, 4- y 8-, los dos últimos pasos son como se muestran en las Figs. 9g-9h. Tras el paso 9h el algoritmo se para, puesto que P es el mismo q el P inicial, y el Q inicial es uno de los R’s encontrados en el siguiente paso antes de encontrar un 1. Un criterio de detención equivalente sería como sigue: El algoritmo se para cuando encuentre dos P’s sucesivos que hayan sido encontrados previamente en el mismo orden consecutivo.
Fig. 9
Seguimiento de bordes, mostrando los P y Q iniciales en (a), y los R’s y los nuevos P y Q en los sucesivos pasos (b)-(h). Para
una explicación detallada ver texto.
Cualesquiera dos P’s sucesivos encontrados por el algoritmo son siempre 8-vecinos, y en el caso en el que C sea 4-conexo, son también 4-conexos a través de 1’s; así, todos los P’s pertenecen a C. Cualesquiera dos Q’s sucesivos están siempre 8-conectados a través de 0’s (cuando C es 4-conexo, pueden no estar 4-conectados, ya que uno de los R’s intermedios puede ser un 1 adyacente diagonalmente a P), y cuando C es 8-conexo, están también 4-conectados a través de 0’s; así todos los Q’s pertenecen a D, de forma que los P’s están todos en el D-borde de C. Es mucho más difícil demostrar que constituyen el D-borde completo; ver [55] para un tratamiento detallado de esto. Puesto que los sucesivos P’s son 8-vecinos, la secuencia de P’s define el código de cadena del borde.
Un método alternativo de obtener los puntos sucesivos del D-borde de C es como sigue: Usar el algoritmo de seguimiento de fisura para generar las sucesivas fisuras (Pi, Qi) del (C, D)-borde. Si un punto dado P aparece dos o más veces en sucesión en el primer término de una fisura se eliminan las repeticiones. [Esta situación surge cuando un punto del borde de C tiene varios 4-vecinos consecutivos en D, que se corresponden con varias fisuras sucesivas en el (C, D)-borde.} La secuencia de los primeros términos que permanecen después de estas eliminaciones es justamente la secuencia de puntos de CD. De hecho, podemos generar el código de cadena de CD directamente a partir del algoritmo de seguimiento de fisura. Por ejemplo, si las parejas de puntos actuales son
P U
Q V
y a continuación giramos a la derecha, añadimos un 7 a la cadena; si no hacemos ningún giro, añadimos un 0;mientras que si giramos a la izquierda, no añadimos nada a la cadena, ya que el nuevo primer término es aún P. Puesto que el algoritmo para el seguimiento de borde es más complicado que el de seguimiento de fisura, puede ser más económico usar el seguimiento para generar la secuencia de puntos de borde y el código de cadena, como se ha descrito, más que usar el seguimiento de borde.
c. Border
finding
Supongamos que queremos seguir todas las bordes de S, una cada vez, para obtener todos sus códigos de cadena. (La discusión para los códigos de fisura es análoga). Para consumar esto, podemos rastrear la imagen sistemáticamente, esto es, fila a fila; cuando tocamos un borde (e.g., cuando encontramos un 1 inmediatamente a continuación de un 0), lo seguimos; cuando ha sido completamente seguido reanudamos el rastreo. Este proceso encontrará todos los bordes, ya que en cualquier borde debe haber un 1 con un 0 justo a su izquierda (e.g., el punto más a la izquierda de un borde externo o el de más a la derecha de un borde de agujero). Sin embargo, encontrará el mismo borde repetidamente (en cada fila que contenga puntos de la componente o del agujero), de forma que cada borde será seguido muchas veces, cosa que es completamente indeseable. Podemos eliminar este problema marcando cada borde mientras lo seguimos, e iniciando el seguimiento de borde sólo cuando toquemos un borde no marcado; esto nos asegura que ningún borde será seguido dos veces. Sin embargo, ahora algunos bordes pueden perderse; de hecho, un borde de agujero puede ser un subconjunto de un borde externo. Los ejemplos más simples son
o al menos todos sus puntos con 0’s a la izquierda pueden estar en un borde externo, de forma que esos puntos se marcan cuando el borde externo es seguido, y el borde de agujero, a su vez, no. Para evitar este problema, debemos marcar solo esos puntos de borde (e.g., en el D-borde de C) que tienen puntos de D como vecinos a su izquierda; esto garantiza que nunca tocaremos el mismo borde en una transición de un 0 a un 1 no marcado, pero no interfiere con la detección de otros bordes que compartan puntos con el ya dado.
Si queremos distinguir entre bordes externos y de agujero, podemos etiquetar las componentes conexas de Š (véase Sección 3.1) antes de buscar los bordes; esto da al fondo una etiqueta distintiva, de forma que los bordes exteriores son identificables a través de sus adyacencias a puntos que tengan esa etiqueta. De manera alternativa, usamos el modelo modificado siguiente de rastreo, seguimiento de borde, y marcado. Usamos dos marcas, l y r, para puntos del D-borde que tengan D a su izquierda y derecha, respectivamente; e iniciamos el seguimiento de borde en cada transición de 0 a un 1 no marcado l, o de un 1 no marcado r a un 0. Ahora un borde externo siempre se encuentra primero como una transición de 0 a 1(en el punto de más a la izquierda de los superiores de C), y similarmente un borde de agujero siempre se encuentra primero como una transición de 1 a 0; por tanto este esquema nos permite identificarlos tan pronto como se encuentren.
d. Border
tracking
El seguimiento de fisuras y bordes tiene la desventaja de que requiere acceso a los puntos de la imagen en un orden aleatorio, ya que un borde puede tener cualquier forma y tamaño. En los párrafos siguientes describimos un método de construcción de códigos de fisuras o de cadenas de todos los bordes de S en un sólo rastreo fila a fila de la imagen. Esto nos permite convertir una representación por filas de S (e.g., secuencias)directamente a una representación de bordes. También se discutirá la conversión de bordes a secuencias.
Ahora mostraremos cómo convertir secuencias a códigos de fisuras; la conversión a código de cadenas es bastante parecida y se ha dejado como ejercicio para el lector.
(1) Para cada secuencia r de la primera fila, o cada secuencia r no adyacente a una secuencia de la fila precedente, inicializamos una cadena de código de la forma 1 2 · · · 2 3, donde el número de 2’s es la longitud de r; esto representa la parte superior y los lados de r, que sabemos que debe estar sobre un borde. El final de la cadena está asociado con el final izquierdo de r, y su principio con el final derecho.
(2) En general, una secuencia r en una fila ya facilitada tiene un final de una cadena de código asociada a cada uno de sus finales (veremos brevemente como las cadenas en los dos finales pueden ser diferentes). Supongamos que las cadenas sean ap y bp, donde el final de ap está asociado con el final izquierdo de r, y el inicio de bp está asociado con su final derecho. Nótese como ap siempre termina con 3 y bp siempre empieza con 1. Si ninguna secuencia de la siguiente fila es adyacente a r, enlazamos el final de ap al inicio de bp mediante una cadena de la manera 0 · · · 0, donde el número de 0’s es la longitud de r. Esta cadena representa la parte inferior de r, el cual debe estar sobre un borde.
(3) Si tan sólo una secuencia r’ de la siguiente fila es adyacente a r, añadimos al final de ap una cadena de la manera 2 · · · 2 3, si r’ se extiende hacia la izquierda de r; un único 3, si r’ y r están alineados con sus finales izquierdos; y una cadena de la manera 0 · · · 0 3, si r se extiende hacia la izquierda de r’. El final de la extensión de ap está ahora asociado con el final izquierdo de r’. Similarmente, añadimos al inicio de bp una cadena de la manera 1 2 · · 2, si r’ se extiende hacia la derecha de r; un único 1, si r’ y r están alineados con sus finales derechos, y una cadena de la manera 1 0 · · · 0, si r se extiende hacia la derecha de r’. El inicio de la extensión de bp está asociado con el final derecho de r’.
(4) Si varias secuencias, digamos r’1, ..., r’k, en la siguiente fila son adyacentes a r, añadimos cadenas al final de ap y al inicio de bp tal y como en (3), dependiendo de las posiciones de r’1 relativas al final izquierdo de r y de r’k relativa a su final derecho. El final y el inicio de estas cadenas están asociados con el final izquierdo de r’1 y con el final derecho de r’k, respectivamente. Adicionalmente, para cada pareja consecutiva de secuencias r’i-1, r’i (1 < i £ k), creamos una nueva cadena de la manera 1 0 · · · 0 3, representando el lado derecho de r’i-1, la porción inferior de r entre r’i-1 y r’i, y el lado izquierdo de r’i . El inicio de esta nueva cadena está asociado con el final derecho r’i-1, y su final con el final izquierdo de r’i.
(5) Supongamos finalmente que la secuencia r‘ es adyacente a varias secuencias, digamos r1,..., rk , en la fila precedente. En este caso, añadimos cadenas al final de ap1 y al inicio de bpk tal y como en (3); las formas de estas cadenas dependen de las posiciones de r’ relativas al final izquierdo de r1 y al final derecho de rk. El final e inicio de estas cadenas extendidas están asociadas con los finales izquierdo y derecho de r‘, respectivamente. Adicionalmente, para cada pareja consecutiva de secuencias ri-1, ri (1 < i £ k), enlazamos el final de ai al inicio de bi-1 mediante una cadena de la manera 2 · · · 2, representando la porción superior de r‘ entre ri-1 y ri.
Cuando todas las filas han sido elaboradas, nos quedamos con un conjunto de códigos de fisuras cerrados representando todos los bordes de S, con los bordes externos representados en el sentido contrario de las manecillas del reloj y bordes internos siguiendo las manecillas del reloj. Un ejemplo simple de la operación del algoritmo se muestra en la Fig. 10.
Si queremos convertir códigos de fisuras o cadenas a secuencias, debemos almacenarlos de tal manera que sea fácil acceder todas las cadenas de códigos relacionadas a una fila ya dada. Por ejemplo, podemos romper cada código en un conjunto de subcadenas cada una de las cuales representa una secuencia monótona no creciente o no decreciente de coordenadas-y, y registrar las coordenadas de los puntos finales de esos segmentos. Entonces podemos generar una representación de secuencias fila a fila rastreando las subcadenas apropiadas (hacia adelante, si y no aumenta; en sentido contrario, si no decrece) para determinar las secuencias finales. Aquí no se facilitarán más detalles; ver (8).
Fig. 10 Border tracking. (a) Entrada, con las filas numeradas. (b) Códigos de
fisura de las filas sucesivas; los nuevos segmentos en cada fila están
subrayados.
e. Reconstrucción a partir de los
bordes
Supongamos que se nos han facilitado todos los bordes de S, e.g., se nos da cS’, el cual tiene 1’s en los puntos de los bordes de S y 0’s en el resto. Asumimos que estamos utilizando 8-conectividad para S y 4-conectividad para Š §. Entonces intentaremos reconstruir S siguiendo las siguientes líneas: (1) Etiquetamos todos los 4-componentes de 0’s(véase Sección 3.1 sobre etiquetado de componentes conexas); sea b la etiqueta de la componente de fondo. (2) Marcamos los 1’s adyacentes a los b’s, por ejemplo con comilla simple. (3) Si l ¹ b es cualquier etiqueta que aparece adyacente a un 1 con comilla, se cambian todos los puntos etiquetados con l a 1’s con comilla. (4) Marcamos los 1’s adyacentes a los 1’s con comilla con asteriscos. (5) Si l es cualquier etiqueta que aparece adyacente a un 1 con asterisco, se cambian todos los puntos etiquetados con l a b’s. (“Adyacente” en todos estos pasos significa “4-adyacente”). Los pasos (2)-(5) se repiten hasta que todas las etiquetas de 0’s han sido cambiadas a b’s o a 1’s con comilla. Desafortunadamente, este proceso se interrumpe si algún borde interno y borde externo de S tienen un punto en común; ese punto será adyacente a los b’s en alguna etapa, y se le asignará una comilla, lo que provocará que los 0’s del interior se conviertan en 1’s con comilla. Para evitar este problema, se nos debe facilitar más que sólo cS’. (De hecho, cS’ solo no determina S; por ejemplo si S’ es
1
1 1
1
S es
1
1 1 1
1
o si S es igual que S’?). En particular, supongamos que los 1’s que están sobre más de un borde están marcados de una forma especial. Cuando tales 1’s son adyacentes a los b’s, les asignamos asteriscos en vez de comillas; las etiquetas que aparecen adyacentes a ellos son entonces transformadas a b’s, no a 1’s con comilla. Los pasos sucesivos en este algoritmo están ilustrados esquemáticamente en la Fig. 11.
Si S sólo tiene unos pocos bordes, un método de seguimiento de borde de reconstruccióna partir de sus bordes puede ser más apropiado que el modo anteriormente descrito. Supongamos que se nos facilita el código de fisuras del (C, D)-borde de S, y las coordenadas del par inicial (P, Q); basándonos en la convención de que P siempre está a la izquierda, esto nos permite encontrar las sucesivas parejas. Conforme las encontramos, marcamos los P’s como 1’s y los Q’s como 0’s (en una matriz inicialmente en blanco). Cuando este proceso está completado, el D-borde de C ha sido completamente marcado con 1’s, y el C-borde de D con 0’s. Después de que todos los bordes de S hayan sido marcados de esta manera, es fácil “rellenar” el resto de S (y Š) expandiendo los 1’s y los 0’s a los espacios en blanco 4-vecinos (pero no entre ellos); en un ordenador multiprocesador, el número de pasos de expansión requeridos es menor que el diámetro de la imagen. En un ordenador convencional, podemos “rellenar” S y Š realizando un rastreo fila a fila de la imagen, transformando los blancos consecutivos en 0’s empezando en cualquier 0 o en el borde de la imagen, y transformando los blancos consecutivos en 1’s empezando por cualquier 1.
Fig.11
Reconstrucción a partir de bordes. (a) S (rodeado de 0’s). (b) S’ (rodeado de 0’s); el 1 que se
encuentra en dos bordes está subrayado. (c) Todas las 4-componentes de Š’(rodeadas de b’s) están etiquetadas. (d) Los 1’s
adyacentes los b’s están con
comillas; el 1 previamente subrayado está con asterisco. (e) Las etiquetas x y z aparecen adyacentes a los 1’s con
comillas; todos los x’s y z’s se convierten en 1’s con comillas.
(f) Los 1’s adyacentes a 1’s con comillas reciben asteriscos. (g) La etiqueta y
aparece adyacente a los 1’s con asterisco; todos los y’s se convierten en b’s. El paso (d) se repite ahora, y al 1
central se le pone una comilla; si estuviera en el borde externo de una
componente de 1’s que tenga agujeros, la repetición de los pasos (e)-(g)
transformaría el interior de esa componente en 1’s con comilla, su borde interno
en 1’s con asterisco y sus agujeros en b’s.
El proceso de reconstrucción es algo más complicado si se nos facilitan los códigos de cadenas en vez de códigos de fisuras. Supongamos que conocemos el código de cadenas del D-borde de C y las coordenadas del punto inicial P; entonces el código de cadenas nos da el siguiente punto P’. Consideremos primero el caso donde utilizamos 8-conectividad para C. Sabemos que el 8-vecino de P precediendo a P’(en un sentido contrario al de las agujas del reloj) es Q’, y que (al menos) el 4-vecino de P precediendo a P’ está en D (o es Q, o es uno de los R’s visitados antes de encontrar un 1; nótese que si P’ es un 8-vecino de P, este 4-vecino es igual que Q’). Marcamos P y P’ como 1, y este 4-vecino -llamémosle Q- y Q’ como 0 (en la matriz inicialmente en blanco). Ahora el código de cadenas nos da el siguiente punto P’’, y sabemos que el 8-vecino de P’ precediendo a P’’ es Q’’, y que todos los 8-vecinos de P’ entre Q’ y Q’’ están también en D. Marcamos P’’ como 1 y todos estos 8-vecinos (incluyendo Q’’) como 0’s. Este proceso se repite hasta que alcanzamos el final de la cadena; esto debería llevarnos a P de nuevo, digamos desde P*. En este paso, los 8-vecinos de P entre Q* y Q deben ser todos 0’s. Nótese que puede que visitemos un punto más de una vez, pero diferentes vecinos serán 0’s en cada visita. El D-borde de C y el C-borde de D han sido ahora marcados con 1’s y 0’s, respectivamente. El procedimiento es análogo cuando C es 4-conexo, excepto que ahora sólo los 4-vecinos de Pi entre Qi y Qi+1 se convierten en 0’s, ya que los 8-vecinos intermedios pueden ser ahora 1’s. Además, si Pi+1 es un 8-vecino de Pi, sabemos que el 4-vecino siguiente debe estar además en C, y convertimos ambos vecinos en 1’s. Un ejemplo simple de reconstrucción desde un código de cadenas borde se da en la Fig. 12.
La expansión de los 1’s y 0’s de los bordes a los blancos puede utilizarse para “rellenar” regiones incluso cuando los bordes no forman curvas perfectamente cerradas [75]. Por ejemplo, supongamos que hemos detectado un conjunto de límites que están colocados en una región de borde; marcamos los puntos en los lados oscuros de los límites como 1’s, y los puntos en los lados claros como 0’s, como se ilustra en la Fig. 13a. Entonces expandimos los 0’s y 1’s a los blancos; cuando un blanco tiene 0’s y 1’s como vecinos, lo marcamos con un 0. La Fig. 13b muestra el resultado del primer paso de la expansión; es evidente que en algunos pasos mas, la región será rellenada con 1’s y el fondo con 0’s. Esta técnica puede utilizarse sólo si los límites “rodean” al borde adecuadamente, y no hay límites de ruido en el interior o en el fondo. Si el borde no está bien rodeado, los 1’s se “escaparán” hacia el fondo. Si hay límites de ruido, la expansión creará regiones de 0’s en el interior o de 1’s en el fondo.
Fig. 12
Reconstrucción a partir de códigos de cadena de borde. (a) Código de
cadena; el borde en sí se muestra en (b), con el punto inicial subrayado. (c)
Paso inicial; (d)-(j) pasos sucesivos. En el último paso, con P* = 1 y Q* = 0,
es sencillo rellenar el interior expandiendo los 1’s a los huecos. El proceso
mostrado aquí trata los 1’s como 8-conectados.
Fig. 13
Reconstrucción a partir de bordes incompletos. (a) Los 0’s y 1’s
iniciales que representan los puntos en los lados iluminado y oscuro de un
borde. (b) Resultado de la expansión de los 4-vecinos de los 0’s y los 1’s a los huecos (un
paso); los huecos adyacentes a un 0 y a un 1 se convierten en 0. Evidentemente,
en los pasos sucesivos el agujero se rellenará con 1’s y el fondo con
0’s.
f. Árboles de cuadrados y
bordes
En esta subsección describiremos brevemente métodos de conversión entre representaciones de árboles de cuadrados y de borde. Se pueden encontrar detalles en dos artículos de Samet et al. [16, 64]. No se tratará aquí la conversión entre el MAT y las representaciones de bordes; sobre la construcción de un MAT continuo a partir de un borde poligonal ver Montanari [38].
Para determinar, para un nodo hoja dado M de un árbol de cuadrados, si el correspondiente bloque está en un borde, debemos visitar los nodos hoja que corresponden a los bloques 4-adyacentes y comprobar si son negros o blancos. Para encontrar los nodos correspondientes, e.g., los bloques vecinos a mano derecha, nos movemos hacia arriba desde M en el árbol hasta que alcancemos algún nodo antepasado a partir de su hijo noroeste o sudoeste. (Si alcanzamos el nodo raíz antes de que esto ocurra, M está en el límite este de la imagen y no tiene bloques vecinos a la derecha). Tan pronto como esto ocurre, volvemos hacia abajo por el árbol realizando las imágenes reflejadas de los movimientos que hicimos en el camino hacia arriba, i.e., el primer movimiento hacia abajo será hacia su hijo noreste o sudeste, y los próximos movimientos serán hacia sus hijos noroeste o sudoeste. Si se alcanza un nodo hoja al tiempo en que llegamos al final de esta secuencia de movimientos, su bloque es al menos tan grande como el bloque de M, y así es el único vecino a mano derecha de M. Por otra parte, el nodo no hoja alcanzado al final de la secuencia es la raíz de un subárbol cuyos nodos hoja más a la izquierda corresponden a los vecinos a la derecha de M, y podemos encontrar estos nodos atravesando ese subárbol.
Sean M, N nodos hoja negros y blancos cuyos bloques sean 4-adyacentes. De este modo la pareja M, N define un segmento de borde común de longitud 2k (la más pequeña de las longitudes de los lados de M y N) que termina en la esquina de M o de N (o de ambos). Para determinar el próximo segmento a lo largo de este borde, debemos encontrar la otra hoja P cuyo bloque toca el final de este segmento:
Si el segmento termina
en una esquina de M y de N (de ambos), debemos encontrar las
otras dos hojas P, Q cuyos bloques se encuentran en la
esquina
Esto puede realizarse
mediante un procedimiento ascendente y descendente similar al que se describió
en el párrafo precedente; ver [16] para detalles. El próximo segmento de borde
es entonces el borde común definido por M y P si P es blanco, o por N y P si P es negro. [En el caso de la esquina
común, la pareja de bloques que definen el próximo segmento del borde se
determina exactamente como en el siguiente algoritmo de seguimiento de fisuras
de la Subsección (a) más arriba, con M, N, P, Q con los roles de P, Q, U, V, respectivamente]. Este proceso se
repite hasta que llegamos a M, N otra vez, en cuya etapa el borde
completo ha sido recorrido. Los sucesivos segmentos de borde constituyen un
código de fisuras, repartido en trozos cuyas longitudes son potencias de 2. El
tiempo requerido para este proceso es del orden del
número de nodos del borde
veces la altura del árbol.
Utilizando los métodos descritos en los últimos dos párrafos, podemos recorrer el árbol de cuadrados, encontrar todos los bordes, y generar sus códigos de fisuras. Como en la subsección (c) más arriba, deberíamos marcar cada borde conforme lo seguimos, así ya no lo seguiremos otra vez desde otro punto de inicio; nótese que el proceso de marcado es complicado por el hecho de que el bloque de un nodo puede estar en muchos bordes diferentes.
Para generar un árbol de cuadrados a partir de un conjunto de códigos de fisuras, primero recorremos cada código y creamos parejas de nodos hoja teniendo los segmentos de borde dados, junto con los nodos no hoja necesarios. Entonces generamos nodos de hoja (o no hoja) correspondientes a los bloques interiores. En cualquier etapa, si cuatro hojas con un padre común todas tienen el mismo color, se fusionan. Los detalles de este algoritmo no se darán aquí; ver [64]. El tiempo requerido es del orden del perímetro (= longitud total de la cadena de fisuras) veces la altura de árbol.