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*/ |
| Algoritmo: Encontrar siguiente Pixel de Contorno
find_next(Pc, dcp, Pn, dcn) |
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. |
Otros Artículos en esta sección
-
Acceso a OpenLDAP mediante Netscape Directory SDK para Java vía JNDI en una aplicación web con Apache Tomcat.En este artículo se plantea una introducción, totalmente funcional, a la generación de documentos XML para su posterior creación de fichero XML utilizando DOM (Document Object Model) de Java XERCES Parser v2.7.1Instalación paso a paso de Java Standar Edition Development Kit 7 en Ubuntu, Fedora, CentOS, Mint¿Alguna duda? Sientete libre de hacer tus pruntas en nuestro:
foro deProgramación »
