Algoritmo de Seguimiento de Contorno (Following Contour Algorithm)

Algoritmo de Seguimiento de Contorno (Following Contour Algorithm)

Clase en java que calcula los puntos del contorno de un objeto dentro de una imagen binaria. Como se muestra en las siguientes imagenes, el contorno encontrado esta resaltado con color fosforecente, como resultado del algoritmo a describir.

 

El presente algoritmo esta basado en el libro Shape Analysis and Classification, Theory and Practice, de Luciano da Fontoura Costa y Roberto Marcondes Cesar Jr.  CRC Press 2001.(paginas 341-347)

 


 

 

 
 

Introducción

El algoritmo de seguimiento de contorno (Contour Following Algorithm) extrae el contorno paramétrico de una imagen binaria, recibe como entrada una matriz nxm de 0's y 1's, (0 = negro, 1 = blanco) y retorna una lista que contiene los puntos (x,y) que definen el contorno del objeto. Este algoritmo esta representado mediante una clase en Java que puede ser reutilizada facilmente.

El proceso de definicion del contorno de objetos es parte importante en visión artificial, especificamente en reconocimiento de formas, para luego permitir la extracción de características.

Descripción del Algoritmo

Asumiendo que los pixels del objeto son blancos y el fondo negro, el primer paso consiste en detectar el primer punto del objeto, el cual puede ser un proceso simple de recorrido línea por línea (por ejemplo de izquierda a derecha o de arriba para abajo) hasta que el primer pixel del objeto sea alcanzado. Luego el algoritmo circunavega el objeto conectado hasta que el pixel de partida sea revisitado, lo cual indicará el completamiento de la tarea. De hecho, en el afan de obtener el contorno paramétrico, es suficiente almacenar las coordenadas de los pixels del camino seguido a lo largo del contorno externo.

Se asume que  que los 8 pixels vecinos de cada pixel P estan etiquetados como 0, 1, 2, ....7, (como se indicará más adelante, estos codigos indican los códigos cadena de la direccion).


 

3 2 1
4 P 0
5 6 7

 

El contorno externo resultante consistirá en el recorrido en el sentido contrario a las agujas del reloj de los 8 pixels conectados. Una vez que el pixel de inicio fue encontrado, el algoritmo decidirá, cuál es el siguiente pixel del contorno. En cada paso, una búsqueda por el siguiente pixel vecino es realizada sobreponiendo la máscara de la tabla anterior, de tal forma que el pixel central P es sobrepuesto sobre el actual pixel de contorno a ser analizado. El siguiente pixel será uno de los vecinos etiquetados como 0, 1, 2,... 7.

 

El algoritmo de extracción de contorno puede ser simplificado de la siguiente forma:


 

Algoritmo: Seguimiento de contorno

Encontrar E[1]  linea por linea;   /* pixel de inicio*/
n = 2;
sea next_pixel el segundo pixel del contorno encontrado de acuerdo a la matriz anterior;
sea dcn la direccion de E[1] a next_pixel;
while (next_pixel <> E[1])
       E[n] = next_pixel;
       dpc = dcn;
       find_next(E[n], dpc, next_pixel, dcn);
       n = n + 1;


 

Algoritmo: Encontrar siguiente Pixel de Contorno

find_next(Pc, dcp, Pn, dcn)
dcp = invert(dpc);
For r = 0 to 6 do
       dE = mod(dcp + r, 8);
       dI = mod(dcp + r + 1, 8);
       PE = chainpoint(Pc, dE);
       PI = chainpoint(Pc, dI);
       if (isbackground(PE) and isobject(PI)) then
             Pn = PE;
             dcn = dE;

 

Luego de completar estos procedimientos, el vector E[n] almacenará el contorno externo. El algoritmo utiliza la función mod(x,y),  la cual retorna el resto de la división de x por y.  Así mismo tambien utiliza la función chainpoint(P,d), que simplemente retorna las coordenadas del pixel vecino de P en la dirección d.
 

Documentación de la clase en Java.

Miembros
public ArrayList E1x; Vector que contiene las coordenadas X
 
public ArrayList E1y; Vector que contiene las coordenadas Y
 
public int[] next_pixel; Coordenada de siguiente pixel
 
public int n =1; Contador de numero de coordenadas parametricas inicializada en 1
 
public int[][] ImageBin; Imagen auxiliar para efectos de procesamiento


 

Metodos
public follow(int [][] imagem) Constructor que recibe la imagen.
public int[][] getContour() Retorna el contorno parametrico del objeto.
protected int[] find_next(int PCX,
int PCY, int dpc, int[] w1_vect)
Retorna el siguiente pixel del contorno.
protected int[] chainpoint(int pcx,
int pcy, int d)
Retorna el siguiente punto vecino de P en la direccion d.
protected boolean isbackground(int[] PE) Retorna verdadero si el punto en analisis pertenece al fondo de la imagen.
protected boolean isobject(int[] PI) Retorna verdadero si el punto en analisis pertenece al objeto.

 

Archivos Adjuntos

  • follow.zip 1,29 KiB
    Código fuente Java del Algoritmo

Otros Artículos en esta sección

¿Alguna duda? Sientete libre de hacer tus pruntas en nuestro:
foro de Programación »