Login Form

En esta ocasión, describiremos un algoritmo muy popular dentro del procesamiento de imágenes con el cuál podemos obtener el esqueleto de la imagen en cuestión. El uso del esqueleto para la obtención de las características de un cierto patrón es muy común y es utilizado en aplicaciones tan diversas como pueden ser el reconocimiento automático de caracteres, de firmas autógrafas y de huellas dactilares, entre otros.

La idea de esto es obtener de una figura contenida en una imagen digital, una serie de trazos de un pixel de grosor que representen la forma original de la figura y que nos simplifiquen el trabajo de obtener características tales como dirección de los diferentes segmentos, intersecciones entre segmentos y demás.

A continuación se muestra un ejemplo del esqueleto de una figura de la letra B. En negro se puede ver la letra B original y en blanco, el esqueleto que representa la B con trazos de un pixel de grosor.

 

 

 

Como podrán notar, en el proceso de adelgazamiento de una figura, se producen distorciones. En el caso de la imagen, se pueden apreciar varios trazos del esqueleto que en realidad no son parte del esqueleto ideal de la figura de la letra "B". El objetivo de los algoritmos de adelgazamiento o esqueletización es el de obtener el esqueleto de una figura con la menor distorsión posible y consumiendo el menor número de recursos computacionales posibles.

El algoritmo que vamos a tratar fue propuesto por T.Y. Zhang y C.Y. Suen en 1984 en un artículo llamado "A Fast Parallel Algorithm for Thinning Digital Patterns" en la revista Communications of the ACM, Vol. 27, No. 3 y está disponible de manera gratuita en internet en caso de que les interese leer el texto original. Cabe mencionar que este artículo está basado directamente en esa publicación y que de hecho, la mayoría de las imágenes utilizadas han sido tomadas directamente del artículo.

Este algoritmo es muy popular debido a que da buenos resultados, es sencillo de implementar y es rápido. Trabaja con imagenes binarizadas y funciona por iteraciones, teniendo cada iteración, dos sub-iteraciones. Es paralelo, es decir, en cada sub-iteración, el valor de los pixeles se puede evaluar de manera independiente, eso si, obviamente, las sub-iteraciones y las iteraciones sí son secuenciales, siendo la salida de una, la entrada de la siguiente.

Pues bien, como ya se mencionó, el algoritmo trabaja por iteraciones. En cada iteración, se tienen dos sub-iteraciones en cada una de las cuales, se evalua cada pixel de la imagen en base a cuatro condiciones, que de cumplirse, permiten que el pixel en cuestión sea borrado, por no tratarse de una parte fundamental del esqueleto de la firma. El resultado de la imagen con los pixeles que hayan cumplido las condiciones borrados, será la entrada para la siguiente sub-iteración. La última iteración se da cuando se cumplen dos sub-iteraciones donde ningún pixel se borra.

Como ya se dijo, si se pudiera realizar en realidad programación en paralelo (si tuvieramos un cpu por pixel por ejemplo), cada sub-iteración podría llevarse a cabo en un sólo paso, pero como nuestras tareas en realidad son secuenciales, procederemos a describir el algoritmo para ser programado de la manera tradicional.

Para cada iteración, se deben llevar a cabo dos sub-iteraciones. Primero describiremos las condiciones de cada sub-iteracón y al final procederemos a explicar a qué se refiere cada condición.

 

Primera Sub-iteración

  • En la primera subiteración, evaluar para cada pixel, las siguientes cuatro condiciones y si las cumple, marcarlo como "para ser borrado":
  1. 2 <= B(P1) <= 6
  2. A(P1) = 1
  3. P2 * P4 * P6 = 0
  4. P4 * P8 * P6 = 0
  • Una vez evaluados todos los pixeles de la imagen, proceder a borrar aquellos marcados "para ser borrados".

 

Segunda Sub-iteración

  • En la segunda subiteración, tomar como entrada la imagen resultante de la primera sub-iteración y evaluar para cada pixel, las siguientes cuatro condiciones y si las cumple, marcarlo como "para ser borrado":
  1. 2 <= B(P1) <= 6
  2. A(P1) = 1
  3. P2 * P4 * P8 = 0
  4. P2 * P6 * P8 = 0
  • Una vez evaluados todos los pixeles de la imagen, proceder a borrar aquellos marcados "para ser borrados".

Como ya se mencionó, el algoritmo finaliza cuando en ninguna de las dos sub-iteraciones, se borra al menos un pixel.

 

Evaluación de las condiciones

Ahora procedamos a explicar cómo verificar cada una de las condiciones. Como se puede notar, las dos primeras condiciones son las mismas para las dos sub-iteraciones.

Asumo que si estás leyendo directamente esto, conoces los conceptos de correlación, convolución y kernel, máscara o filtro en el procesamiento de imágenes digitales. Si no es así, sería bueno que te familiarizaras con ello (es muy simple). Nosotros tenemos un artículo que trata acerca de estos conceptos en el siguiente enlace.

Para poder llevar a cabo las distintas condiciones, necesitamos hacer referencia a la siguiente imagen:

En esta imagen podemos ver la ubicación de cada uno de los puntos a los que se hace mención en las condiciones. P1, es el pixel que estamos evaluando. Como se puede ver, para la implementación del algoritmo,  se puede utilizar un kernel de 3x3 para la evaluación de las condiciones.

La primera condición para ambas sub-iteraciones es: 2 <= B(P1) <= 6 donde B(P1) es el número de pixeles vecinos a P1 que son parte de la figura, es decir, que tienen valor de 1 ya que la imagen se encuentra binarizada. Esta condición nos permite asegurar que no se borren pixeles que sean puntos finales o que se encuentren en el centro de la figura ya que el algoritmo lo que va haciendo en realidad, es eliminar los pixeles de los bordes, como si fuera quitando capas hasta dejar simplemente los pixeles centrales. Para implementarla se puede realizar una correlación al pixel a evaluar con el siguiente kernel:

 

 

La segunda condición es A(P1) = 1 donde A(P1) es el número de patrones "01" en el conjunto ordenado P2, P3P4, P5, P6P7 y P8. ¿Qué quiere decir esto?..., pues que hay que checar, para cada par de pixeles adyacentes de izquierda a derecha, si se presenta un cambio de un pixel con valor 0 a uno con valor de 1 y contabilizarlos. En la siguiente imagen se muestra un ejemplo en el cual esta suma da un 2 ya que dos veces se presenta el caso de que, para un pixel con valor 0, su vecino tiene un 1:

 

 

Como se puede ver, el patrón "01" se presenta dos veces siendo en este caso A(P1) igual a 2 por lo que la condición no se cumple. Esta condición lo que nos permite es evitar que se borren pixeles que se encuentran en el medio de dos puntos finales.

En la siguiente imagen se ilustran dos casos en los que la condición 1 nos impide borrar un pixel final y la condición 2 nos impide borrar un pixel que se encuentre en medio de dos finales :

 

En la parte señalada con la letra A se evalua un pixel final (el cuál no debe ser borrado). El resultado de la condición 1 nos daría 1 por lo que el pixel no sería marcado para borrarse. En la parte central (la B), se muestra un ejemplo donde se evalua un pixel que en realidad, se encuentra en medio de dos pixeles finales (el A y el C) con lo que la condición 2 nos daría un 2 manteniendo el pixel sin ser borrado.

Ahora bien, pasemos a examinar las condiciones 3 y 4 de las dos sub-iteraciones. Comencemos primero con las de la primera sub-iteración.

  1. P2 * P4 * P6 = 0
  2. P4 * P8 * P6 = 0

Estas condiciones evaluan el resultado de multiplicar el valor de los pixeles indicados en cada condición y lo que hacen es verificar que el pixel a borrar, sea un pixel perteneciente a un borde en la parte este, sur o bien, que el pixel sea parte de la esquina noroeste.

A continuación se muestra una imagen donde se muestran los pixeles que intervienen en estas condiciones:

En realidad, cada par de condiciones se puede ver como un sistema de ecuaciones cuya solución se da , en el caso de las condiciones que estamos tratando de la primera sub-iteración, cuando Pó Pson cero o bien, cuando P2 y P8 son cero. Si sólo P6 es 0, estamos hablando que P1 se trata de un pixel perteneciente a un borde en la parte sur. Si  sólo Pes 0, estamos hablando de que Ppertenece a un borde en la parte este. Por último, si la solución del sistema de ecuaciones es que P2 y P8 son cero, entonces P1 pertenece a una esquina en la parte noroeste.

Lo mismo para las condiciones de la sub-iteración 2:

  1. P2 * P4 * P8 = 0
  2. P2 * P6 * P8 = 0

La diferencia aquí es que se evalua que el pixel pertenezca a un borde en la parte norte u oeste, o bien, sea una esquina en la parte sureste.

Por último, a manera de ejemplo, evaluamos la primera sub-iteración de la siguiente matriz:

 

 

El pixel azul con valor 1 es el pixel a evaluar en base a su relación con sus pixeles vecinos en rojo y verde.

Para la primera condición 2 <= B(P1) <= 6 tenemos que B(P1es igual a  5. Es decirel número de pixeles vecinos con valor de 1 es 5 por lo que la primera condición se cumple.

Para la segunda condición  A(P1) = 1 vemos que también se cumple, ya que el único patrón de cambio de 0 a 1 se da del pixel de la esquina inferior izquierda hacia el pixel izquierdo de la fila central (indicado con el color verde).

Por último, Pes igual a 0 por lo que se cumplen las condiciones 3 y 4: P2 * P4 * P6 = 0 y  P4 * P8 * P6 = 0 ya que para ambas: 1 * 1 * 0 = 0. Con ésto sabemos que el pixel pertenece a un borde este, sur o bien a una esquina noroeste, en nuestro caso pertenece a un borde sur.

El pixel debe ser marcado para ser borrado una vez finalizada la evaluación de todos los pixeles en la sub-iteración y la matriz resultante una vez borrado el pixel sería la siguiente:

 

 

A continuación dejo una imagen (también tomada de la publicación original) donde se muestran ejemplos de aplicaciones de este algoritmo a diferentes figuras:

 

 

 

Por último, para aquellos que estén interesados, dejo un enlace a un sitio donde explican de manera detallada el algoritmo de Pavlidis, también usado para obtener el esqueleto de una imagen.

Add comment


Security code
Refresh

contacts Contactanos

 

bugs Reportar bugs

about Acerca de www.tecnohobby.net

Go to top