lunes, 25 de febrero de 2013

Tarea 4: Detección de Líneas

Link al repositorio: https://github.com/synnick/viscomp

La Tarea 4 consiste en la detección de líneas en una imagen para lo cual se hace uso de la transformada de Hough. Las imagenes de prueba usadas fueron:





Pre procesamiento

Previo a la detección de líneas, es necesario que las imagenes de entrada se encuentren binarizadas. Para comprender más sobre como binarizar una imagen, véase éste post.

Detección de Líneas

El método de detección consiste en calcular las gradientes vertical y horizontal de una cierta imagen, para calcular en base a ellos el ángulo de un cierto pixel en la imagen. Los gradientes se calculan utilizando máscaras de convolución, como la máscara de Sobel para bordes horizontales y la máscara para bordes verticales (para comprender más acerca de las máscaras de convolución y como aplicarlas, véase éste post).

Los gradientes anteriores serán dos "imagenes nuevas" (solo representamos las matrices con los valores de los pixeles, no se guardan como salida '.png'), en las cuales de igual manera que la imagen de entrada, solo contarán con valores binarios (0 o 255, negro o blanco). 

En base a los gradientes, se calcula el ángulo para cada pixel, dependiendo de los valores del gradiente horizontal y el gradiente vertical en dicho pixel. En una imagen binarizada, podemos tomar en cuenta lo siguiente:

Sí $g_{x} = 0$ y $g_{y} = 0$ , $ \theta = Nulo (no hay ángulo)$
Sí $g_{x} = 255$ y $g_{y} = 0$ , $ \theta = 0°$
Sí $g_{x} = 0$ y $g_{y} = 255$ , $ \theta = 90°$

También se toma en cuenta la fórmula:

$\theta = \arctan ( g_y / g_x)$

Donde $\theta$ es el ángulo, $\arctan$ es la función matemática arco tangente, $g_{y}$ el gradiente vertical y $g_{x}$ el gradiente horizontal.

Con cada ángulo además calculamos una variable rho con la siguiente fórmula:

$ \rho = x \cos ( \theta ) + y \sin ( \theta) $

que servirá para generar una matriz, donde cada índice $(x, y)$ tendrá su par $(\rho, \theta)$.

Para poder detectar líneas con está matriz, debemos de ahora crear otra lista (o diccionario en mi caso), donde para cada par diferente $(\rho, \theta)$ sumaremos un contador por cada vez que se encuentre en un pixel. Este diccionario nos ayudará a determinar cuales pixeles son líneas y cuales no, ya que entre más repeticiones tenga un par $(\rho, \theta)$ es más probable que todos los pixeles que tengan ese par sean una misma línea.

Al final, pintamos los pixeles que seleccionemos como líneas en base al diccionario anterior. Para efecto demostrativo, el programa pinta las líneas verticales de color azul, y las líneas horizontales de color rojo.

Los resultados, junto a la cantidad de pixeles horizontales y verticales, son los siguientes:



Los valores son similares lo cual es bueno debido a que el Sudoku es básicamente una tabla simétrica con cuadros. La diferencia entre las cantidades de pixeles es debido a los números dentro de ciertas celdas de la tabla, que funcionan como ruido al detectar pequeñas líneas en ellos.



Aquí los valores en la cantidad de pixeles son idénticos, por tratarse de una imagen simétrica con la misma cantidad de líneas horizontales y verticales.



En esta imagen observamos que existen mayor cantidad de líneas horizontales que verticales. Esto lo podemos comprobar al observar las cantidades de pixeles detectadas, siendo un mayor número los pixeles horizontales que los verticales.

Por alguna razón cerca de los finales de las líneas se localiza una linea contraria (al final de las líneas verticales aparecen pequeñas lineas horizontales y viceversa).

Código:


1 comentario:

  1. Decidiste ni usar el atan, pero pues, funciona para las imágenes de prueba. Para los círculos, confía en las fórmulas ;) 4 pts.

    ResponderEliminar