Max Hernandez: Laboratorio 9: Usando detección de esquinas para encontrar poligonos

Para esta semana en la clase de visón computacional se nos dio a la tarea de utilizar las técnicas aprendidas en el salón para encontrar esquinas para encontrar polígonos en una imagen, esta publicación servirá a manera de reporte para dicha tarea.

Paso 1 - detectando esquinas
Para detectar las esquinas en una imagen se utilizo una técnica muy simple primero se aplica a una copia de la imagen con la que se va a tratar un filtro de media, después se resta este mismo filtro a la imagen original y se le aplica un filtro umbral.

Debido a que el filtro de la media disminuye la intensidad los píxeles que se diferencian mucho de sus vecinos, esto provoca que al restas estas dos imágenes las esquinas y el ruido de la imagen se pinten con mas intensidad. Para obtener la imagen de arriba se aplico además BFS para promediar los píxeles de las esquinas y que fuese mas fácil de tratar.

Paso 2 - Detectando bordes
En el siguiente paso se detectan los bordes de las figuras utilizando gradientes calculados con la mascara de Sobel, no voy a meterme a detalle con esto por que esté método ya ha sido implementado en la siguiente publicación:
http://maxkalavera.blogspot.mx/2013/02/tarea-1-deteccion-de-bordes.html

Paso 3 - Recorriendo las esquinas

Ahora para poder saber a que polígono pertenece cada esquina se utilizo de nueva cuenta BFS para recorrer todos los bordes guardando en un arreglo las esquinas que pertenecen a cada polígono.

Otro punto importante de este pasó es que el recorrido del BFS debe darse en una dirección puesto que necesitamos saber que esquinas tiene conexión con otras para poder comprobar que es una figura, esto debido a que en el siguiente paso analizaremos si estos bordes que juntan las esquinas son lineas rectas o no.

Para poder lograr esto simplemente se modifico la implementación de BFS para que los nuevos vecinos a visitar se agreguen al final de la lista, esto para que los píxeles recorridos se expandan como si ese borde fuera un canal de agua y se llenara con agua, después se hace que empiece a correr en una de las esquinas, cuando llegue a la siguiente esquina se borran todos los píxeles a visitar en la lista, esto provoca que se cierre el punte entre la primer esquina y las demás pero como la primer esquina ya fue visitada, no nos interesa volver a visitar sus píxeles vecinos.

Paso 4 - Comprobando los bordes

Una vez que el programa conoce las esquinas y cuales se comunican con otras se hace un recorrido de esquina a su vecina con un algoritmo para dibujar lineas, comprobando que haya píxeles de borde en cada píxel que se visita.

Como punto final para encontrar el centro de la figura solamente se promedian los puntos de las esquinas.

Código

Resultados

Imagen uno

Esquinas	Bordes	Recorrido	Salida

Salida terminal

max@max-laptop:~/Dropbox/vision_computacional/lb9$ python polygons.py lb9-1.png 
Poligono1 encontrado, tiene 6 lados.
Poligono2 encontrado, tiene 4 lados.
Poligono3 encontrado, tiene 5 lados.
Tiempo de corrida: 0.922751903534

Imagen dos

Salida terminal

max@max-laptop:~/Dropbox/vision_computacional/lb9$ python polygons.py lb9-2.png 
Poligono1 encontrado, tiene 3 lados.
Tiempo de corrida: 0.841367959976

Imagen tres

Salida terminal

max@max-laptop:~/Dropbox/vision_computacional/lb9$ python polygons.py lb9-3.png 
Poligono1 encontrado, tiene 10 lados.
Tiempo de corrida: 0.845256090164

Conclusiones
Como se puede ver la implementación funciona bien con figuras bien definidas con pocos lados ya que como pudimos ver en el hexágono dado que los ángulos son mas amplios no fue posible para el programa detectar de forma correcta las esquinas.
Otra cosa que serviría recalcar es que en el mundo real no todos los objetos de forma poligonal tienen esquinas definidas así que esta implementación podría no ser muy útil para el uso de robots o cosas parecidas.

Referencias: