En esta semana trabajamos con lo que es obtener el Convex Hull de una imagen, que es básicamente un polígono que recubre todo el contorno de la imagen. Para poder realizarlo es necesario contar con otras funcones programadas previamente en los posts de la materia y laboratorio.
Obtención de contornos (Opcional, puede usarse una imagen dibujada en cualquier herramienta)
En el post de Laboratorio 2 y la Tarea 1 de la materia, trabajamos dos formas distintas de obtener los contornos (para más explicación de como se obtienen ver los respectivos posts). Es necesario utilizar alguno para obtener una imagen binaria con el fondo siendo negro y los bordes blancos. Esto debido a que el convex hull se dibujará alrededor de los contornos y es necesario saber identificarlos del resto de la imagen.
En este caso, como el punto de interés es el convex hull, dibuje directamente imagenes de prueba en KolourPaint para Linux y las utilicé con el programa.
Como se puede ver es una imagen con fondo totalmente negro, con solo una figura aleatoria.
Localización de Contornos
Esta parte es obligatoria, y para hacerlo se hace uso del algoritmo BFS programado en la Tarea 2 de la materia (de nuevo, ver el post para más información). En dicho post se utilizaba el algoritmo para localizar figuras y el fondo, por lo cual buscabamos un punto negro y pintabamos todos sus vecinos que fueran de su mismo color de algún color aleatorio.
Ahora, haremos algo parecido pero con los contornos (buscando pixeles blancos), con el objetivo de usar BFS para obtener todos sus puntos y después poder aplicar un algoritmo para calcular el convex hull.
Para poder hacer esto forzosamente tenemos que marcar los puntos recorridos para evitar loops infinitos al buscar el contorno, por lo cual pintamos los contornos de rojo.
Pintando todos los contornos rojos sabemos que recorrimos todos los puntos del contorno. Todos estos puntos se guardan en una lista, que utilizará el algoritmo de convex hull para encontrar los vértices del polígono envolvente.
Gift Wrapping
Uno de los múltiples algoritmos para obtener el convex hull de un set de puntos es Gift Wrapping, también conocido como Jarvis's march. El funcionamiento se basa en dos principios:
- Se inicia a un punto extremo dentro de los puntos del contorno, normalmente el que se encuentre más a la izquierda.
- En cada paso, se prueba cada punto de los puntos y se encuentra cual hace la vuelta más larga hacia la derecha. Este punto debe estar en el contorno.
La siguiente imagen explica bien estos conceptos:
Aplicando este algoritmo, localizamos los puntos del convex hull y los pintamos de color verde para demostración:
Lo siguiente es dibujar líneas entre ellos, la forma en la que lo hice fue utilizando Tkinter, colocando la imagen original (binarizada) como fondo, y dibujando líneas azules entre los puntos del convex hull sobre el Canvas. El resultado es así:
Las líneas azules envuelven correctamente el contorno blanco (como un regalo, por eso Gift Wrapping).
Ejemplos de funcionamiento con tiempo de operaciones (medido desde la recolección de puntos del contorno, hasta la localización de los puntos del convex hull):
Imagen Original
|
Convex Hull
|
Tiempo (s)
|
 |  | 0.54566693306 |
 |  | 2.74937391281 |
 |  | 2.74453306198 |
 |  | 3.45063400269 |
Código
Dilatación
Otra cosa que implementé fue dilatación, que como el nombre podría indicar (por su contraparte física) consiste en ampliar o engordar algunas partes de una imagen. Típicamente, lo que se utiliza como entrada es una imágen binarizada, a la cual se le engordaran los pixeles blancos, pero en mi caso lo utilicé en los puntos negros. La imagen de ejemplo es la siguiente:
Código:
Referencias:
Muy bien; 10 pts.
ResponderEliminar