[Lab VC] Actividad 2: Convex Hull

Para la tercer actividad de laboratorio se tuvo que programar las rutinas necesarias para hallar el convex hull en una imágen dada.
Convex Hull o envolvente convexa es un algoritmo que, dados los puntos de un objeto en una imágen, permite crear un polígono que encierra todos los puntos de dicho objeto, como si un cinturón los envolviera.

Para lograr ésto es necesario identificar los pixeles del borde del objeto que queremos encerrar, para lograr ésto utilicé la técnica de detección de formas aplicada en la tarea 2:

http://juankenny.blogspot.com/2013/02/vc-tarea-2-deteccion-de-formas.html

En la entrada se explica la aplicación del algoritmo BFS para la detección de formas y el fondo de la imágen, también se explica como lograr unos buenos bordes gruesos y continuos para obtener buenos resultados.

Para aplicar el convex hull utilicé las siguientes imágenes:

Ahora, la instrucción para detectar un objeto dada una imágen binarizada es tomar aquellos pixeles de color negro, ya que los de color blanco se consideran del borde. Bien, para el convex hull se supone lo contrarío, detectar los pixeles blancos como objeto porque ahora queremos los pixeles que conforman el borde. Aquí identificamos los pixeles del borde, los pintamos de un color diferente.


Ahora, la rutina programada para BFS nos regresa los pixeles del borde, lo que haremos con esos pixeles será dárselos como entrada al algoritmo de convex hull. El algoritmo elegido para dicha tarea fue Graham Scan

...

Graham Scan

Se usará una variación del algoritmo Graham Scan que divide el convex hull en 2 partes: superior e inferior. Los pasos que realiza este algoritmo para hallar el convex hull son:

• Ordenar los puntos de mayor a menor de acuerdo al eje y, si dos puntos comparten la misma coordenada entonces se ordenan de acuerdo al eje x.
• El primer punto es el que se encuentre más a la parte inferior izquierda, se recorre la lista tomando 3 puntos en todo momento, uno inicial, uno medio y uno final.
• Se comprueba si el cambio de dirección dados los 3 puntos es positivo o negativo.
• Si es negativo entonces puede ser candidato del hull inferior, si es positivo entonces puede formar parte del hull superior.

Así se van eliminando candidatos hasta que quedan aquellos que son los vértices de la figura. Como tenemos 2 hull diferentes tenemos que unirlos, sabemos que ambos comparten los vértices que se encuentren más a la izquierda y a la derecha. Simplemente tomamos una de las 2 listas, eliminamos los puntos extremos que corresponderían a estos puntos, giramos la lista para ponerla en orden y finalmente sumamos ambas listas superior e inferior.

Para una explicación más completa recomiendo el siguiente documento: http://intinno.iitkgp.ernet.in/courses/91/wfiles/29755

...

El algoritmo nos regresa los puntos correspondientes a los vértices mas extremos dado el borde de un objeto en la imagen, pintamos los vértices para identificarlos.


Por ultimo, concateno los puntos en una lista continua de tuplas y se la paso a Tkinter para que dibuje un polígono con ellos que envuelva a los pixeles del objeto dado.

0.604544878006 s (400x300)	0.413755893707 s (350x263)
0.922349214554 s (450x291)	2.62748289108 s (1004x465)

Enla parte superior se pueden ver los tiempos de ejecución para cada imágen, sirven para comparar el rendimiento del algoritmo. Los tiempos se tomaron desde el punto donde BFS toma el borde como objeto hasta el dibujo del convex hull.

Así concluye la actividad.

Código

Código Graham Scan
Código para dibujar el convex hull en el canvas
Referencias:
http://personal.us.es/almar/docencia/practicas/envolvente/tema5.html
http://tomswitzer.net/2010/03/graham-scan/