2.3 Curvas
Esta sección discute métodos de “adelgazar” una S dada en un grupo de arcos y curvas. Asumiremos que S consta enteramente de partes alargadas, así que los arcos y curvas resultantes constituyen una aproximación razonable a S (Sección 1.5c). Para otro tipo de S’s el resultado de adelgazamiento no debería ser particularmente significativo. (Para una definición de alargamiento ver Sección 3.4b). El resultado de adelgazar S se llamará el esqueleto de S.
El MA de una S adelgazada en cualquier parte puede ser considerado como un esqueleto, pero tiene dos defectos. En los lugares donde S ha sido ensanchada, su MA tiene dos puntos de grosor, ya que el MA es el conjunto de máximos de las distancias a Š, como se muestra en la sección 2.1a. Además, como se señala allí, el MA tiende a ser disconexo, y a nosotros nos gustarían trozos conexos de S para ser adelgazados en arcos o curvas conexas. En esta sección describiremos un esquema de adelgazamiento que produce esqueletos conexos y delgados.
a. Thinning
Nuestro algoritmo de adelgazamiento es un proceso especializado de encogimiento que suprime de S, en cada iteración, los puntos de borde cuya eliminación no desconecta localmente sus vecindades; puede demostrarse [54] que esto garantiza que las propiedades de conexión de S no cambian, ni siquiera si tales puntos se eliminan todos simultáneamente. Para evitar que un arco ya adelgazado se encoja en su final, además estipulamos que los puntos que tengan tan sólo un vecino en S que no sean borrados.
Desafortunadamente, si eliminamos todos esos puntos de los bordes de S, y S tiene un grosor de sólo dos puntos, e.g.,
1 1 1 1 1
1 1 1 1 1
entonces S se desvanecerá completamente. Podríamos evitar esto usando un algoritmo que examine más que tan sólo el vecino inmediato de un punto, pero tal algoritmo sería demasiado complicado. En cambio, eliminaremos sólo los puntos de l borde que están en un lado dado de S, i.e. que tienen un vecino específico (norte, este, oeste, o sur) en Š, en una iteración dada. Para asegurarnos de que el esqueleto está tan cerca del “medio” de S como sea posible, usamos lados opuestos alternativamente, ej., norte, sur, este, oeste... (Es posible idear algoritmos que eliminen puntos de borde de dos lados adyacentes a la vez, e.g.,. norte y este, y luego oeste y sur, pero esta aproximación es un poco más complicada y aquí no se describirá detalladamente. Otra posibilidad es comprobar los vecinos de un punto en dos lados para determinar si ellos también se eliminarán, y si es así, no borrar el punto dado).
Para presentar el algoritmo de una forma más precisa, debemos dar las condiciones exactas bajo las cuales un punto de borde pueda ser eliminado. Al punto de borde P de S se le llama simple si el conjunto de 8-vecinos de P que están en S tiene exactamente una componente que es adyacente a P. Esta última cláusula significa que si estamos utilizando 4-conectividad de S, sólo nos preocupamos de las componentes que son 4-adyacentes a P. Si estamos utilizando 8-conectividad, la última cláusula se puede omitir. Por ejemplo, P es 4-simple si su vecindad es
0 1 1
0 P 0
1 0 0
ya que en este caso sólo una 4-componente de 1’s es 4-adyacente a P; pero P no es 4-simple si su vecindad es
0 1 1 0 1 0
0 P 0 ó 0 P 1
0 1 0 0 0 0
Por otra parte, P es 8-simple en el tercer caso, pero no en los dos primeros casos.
Es fácil ver que borrando un punto simple de S no cambian las propiedades de conexión ni de S ni de Š; S - {P} tiene las mismas componentes que S, excepto que una de ellas ahora carece del punto P, y Š È {P} tiene los mismos componentes que Š, excepto que ahora P está uno de ellos. Nótese que un punto aislado (que no tenga un vecino en S) no es simple, y que un punto final (que tenga exactamente un vecino en S) es automáticamente simple.
Nuestro algoritmo de adelgazamiento puede ahora estar establecido como sigue: Borramos todos los puntos de borde de un lado dado de S, siempre que sean simples y no sean puntos finales. Haremos esto sucesivamente desde los lados norte, sur, este, oeste, norte,... de S hasta que no haya más cambios. Un ejemplo simple de la operación de este algoritmo se muestra en la Fig. 14.
La eliminación de los puntos de los bordes de un lado dado de S debería hacerse “en paralelo”, i.e. las condiciones para la eliminación de un punto deberían ser comprobadas antes de que cualquier otro punto sea borrado. (Supongamos que no lo hacemos, y simplemente realicemos la eliminación fila a fila. Cuando borrásemos los puntos del borde norte, quitaríamos capa a capa desde la parte superior de S, y el esqueleto resultante no sería simétrico; e.g., si S fuera un rectángulo, no quedaría nada excepto su fila inferior después de la primera operación). De este modo cada iteración del algoritmo puede ser realizada como una simple operación paralela de un ordenador multiprocesador.
El algoritmo puede implementarse en un ordenador convencional, utilizando un rastreo de la imagen para cada iteración. En cada fila, los puntos se marcan para borrarse, pero no se borran hasta que los puntos de la fila siguiente hayan sido marcados. Podemos evitar rastreos repetidos de la imagen entera operando en las filas en secuencia 1; 2, 1; 3, 2, 1; ... como en la Sección 2.1c. Después de k pasos, donde 2k + 1 es la anchura máxima de S, no se necesita más adelgazamiento sobre la primera fila, así que podrá ser abandonada; de este modo sólo k filas necesitarán estar disponibles al tiempo.
b. Esquemas de adelgazamiento
alternativos
A veces se pueden usar aproximaciones simplificadas al adelgazamiento. Por ejemplo, si S tiene en todas partes un grosor esencialmente constante (ver Sección 3.2d), digamos 2k + 1, puede adelgazarse (al menos de una forma vasta) encogiendolo k veces. Nósese, sin embargo, que el resultado del esqueleto puede ser ocasionalmente grueso o roto. El proceso de adelgazamiento descrito en (tratará S’s de un grosor variable. Otro método [32] que puede usarse si S es un arco de grosor constante es iniciar dos procesos de seguimiento de borde en un final de S que atraviese los lados opuestos de S. (De forma análoga, si S es una curva cerrada de grosor constante, iniciamos dos procesos de seguimiento del borde en puntos que tengan justo el grosor de S desde cada uno, que atraviesa los dos bordes de S). Si la distancia entre los seguidores de borde se hace mayor que el grosor, detenemos uno de ellos hasta que el otro lo alcanza; de este modo siempre permanecen aproximadamente uno al lado del otro. El punto medio del segmento de la línea que une a los seguidores de borde traza un esqueleto de S.
Fig. 14
Adelgazamiento. (a) S original; (b)-(e) resultados de adelgazamientos
sucesivos desde el norte, sur, este, y oeste, tratando S como 8-conexo. En el
siguiente paso norte, el punto más
arriba de (e) será borrado; en el siguiente paso sur, el punto de más a la
izquierda de los de más abajo; y en el siguiente paso oeste, los puntos más a la
izquierda de los de más arriba. No habrá otros cambios. Nótese como el ángulo en
el punto superior izquierdo se encoge hacia abajo a la misma altura que la línea
diagonal en el superior derecha. (b’)-(e’) Resultados análogos tratando S como
4-conexo, y definiendo los puntos finales que tengan sólo un 4-vecino en S. Un
punto más será eliminado en el siguiente paso norte; no habrá más
cambios.
Se pueden definir algoritmos de adelgazamiento para imágenes multivaluadas de varias formas. Una aproximación [15] es generalizar la definición de un punto simple como sigue: definimos la fuerza de un camino P1,..., Pn como el valor mínimo de cualquier punto del camino, y el grado de conexión de P y Q como la fuerza máxima de cualquier camino de P a Q, Decimos que P es “simple” si reemplazándolo por el mínimo de sus vecinos no decrementa el grado de conexión de cualquier par de puntos dentro de su 8-vecindad. Puede verificarse que esto generaliza las definiciones bi-valoradas dadas en (a). El adelgazamiento se define entonces como una operación de mínimo local especializada: repetidamente reemplazamos puntos por el mínimo de sus vecinos, siempre que sean simples y tengan más de un vecino con un valor más alto (esto generaliza la condición de que puntos aislados y finales no se eliminan). En cada iteración realizamos esto desde sólo un lado, i.e, sólo lo hacemos a los puntos que tienen un vecino con valor menor en un lado específico (norte, sur,...). Los resultados de aplicar este proceso a un conjunto de imágenes se muestran en la Fig. 15.
La salida de los operadores de detección de límites es normalmente gruesa. Puede ser adelgazada suprimiendo los no-máximos en la dirección del gradiente en cada punto; esto descarta todo menos el valor del límite más escarpado en cada sección trasversal del límite, pero no permite que los puntos a lo largo del límite compitan entre ellos. Otra posibilidad es la de aumentar o disminuir el valor de cada punto en proporción según lo mayor o menor que es con respecto a su vecino en la dirección del gradiente. Esto provoca que el valor máximo en cada sección trasversal del límite crezca a costa de los valores más bajos, así que eventualmente absorbe a todas las respuestas de esta sección trasversal [17].
Fig. 15
Ejemplo de un adelgazamiento en escala de grises.
c. El resultado del
adelgazamiento
Idealmente, decimos que un subconjunto de A del conjunto de T es un arco digital simple si es un componente conexo de T cada punto de la cual tiene exactamente dos vecinos en T, excepto los dos puntos finales, que tienen un vecino cada uno. Nótese que esto son dos definiciones en una, dependiendo de si nos referimos a 4- u 8-vecinos. Nótese además que un arco no puede ramificarse, cruzarse a sí mismo o incluso tocarse a sí mismo, ya que si no podría contener puntos que tuvieran más de dos vecinos en S. Una curva digital cerrada simple es una componente conexa C de T cada punto de la cual tiene exactamente dos vecinos en T; aquí también tenemos dos definiciones. Nótese que un borde no es siempre una curva cerrada simple, ya que puede que pase a través de algunos puntos dos veces.
El objetivo de adelgazar S es el de producir un T que sea una unión de tales arcos y curvas, quizás después de unos pocos puntos atravesados o ramificados - i.e., puntos que tienen más de dos vecinos - hayan sido eliminados. Nótese que tales puntos aparecerán a menudo en clusters; e.g., consideremos
1 1 1
J J J
1 J J J 1 y J J
J 1 1
1
donde hemos indicado los puntos de unión por J’s. Si muchas ramificaciones de curvas e intersecciones pasan juntas muy cercanas, será difícil identificar y clasificar las uniones individuales. Una S adelgazada puede que tenga además puntos internos; un ejemplo 8-conexo es
1 1 1
1 1 1
1 1 1 1 1
1 1 1
1 1 1
en el que cada punto de borde es o punto final o no simple, así que ese adelgazamiento no tiene efecto sobre él. Los resultados del adelgazamiento dependen de la orientación; por ejemplo, cuando 8-adelgazamos
1 1 1 1 1 1 1 1 1
1 obtenemos 1
pero cuando 8-adelagazamos
1 obtenemos
1 1 1 1 1 1 1 1 1 1
(Bajo 4-adelagazamiento, ninguno de estos patrones cambia)
Una vez que los puntos que tengan más de dos vecinos han sido eliminados, es sencillo construir el código de cadenas de un arco moviéndonos de vecino a vecino, empezando desde uno de los puntos finales y terminando en el otro; o de una curva cerrada empezando en un punto de comienzo arbitrario y moviéndonos en una dirección hasta que el punto de partida se alcanza de nuevo.
El adelgazamiento a veces produce esqueletos “de punta”, especialmente cuando S tiene bordes “velludos” que contienen muchos puntos finales, o cuando los puntos finales salen prematuramente en el curso del proceso de adelgazamiento; esto se aprecia especialmente en la versión para 4-conectividad del algoritmo. Una manera [56] de detectar una ramificación de esqueleto inapropiada es la de considerar las distancias de los puntos de la ramificación desde Š, o, equivalentemente, las iteraciones en las cuales llegan a ser puntos del borde. En una ramificación del esqueleto real estas distancias deberían ser aproximadamente constantes, pero en una ramificación de punta debería aumentar de una forma firme conforme nos movemos desde el extremo de la punta.