Laboratorio 9: Detección de Esquinas

Para esta semana, lo encargado fue detectar esquinas en imágenes utilizando el método de diferencia de filtro mediano para la parte básica, y en base a esas esquinas y utilizando bordes, realizar un seguimiento en cierto orden de las esquinas, trazando líneas para corroborar que en verdad se tratan de esquinas de algún objeto.

El procedimiento es bastante simple, y se explicará usando la siguiente imagen:

Primero, se aplica el filtro mediano a la imagen. El filtro mediano es parecido al de promedios, se procesan pixeles alrededor de uno determinado y se hacen cálculos con todos, en este caso se busca encontrar el mediano o la mediana de ellos. Como seguramente recordemos, la mediana es el valor que se encuentre exactamente en la mitad de una lista o secuencia de números. Igual que el filtro promedio, requerimos una especie de "ventana" o caja de cierto tamaño, que centrándola en el pixel actual dictará cuales a su alrededor se incluirán en el cálculo de la mediana. Entonces si se tuviera una imagen de 3x3 pixeles, y calculamos la mediana usando una ventana de 3x3 cuando el pixel actual es el del centro:

Pixel actual = Pixel[1, 1] = 40

90    150    20 

255    40    150

210    125    9

Los valores que tomaríamos en cuenta serían:

[90 150 20 255 40 150 210 125 9]

Ordenados:

[9 20 40 90 125 150 15 210 255]

Donde el valor de la mediana es entonces 125, que sustituirá el valor actual del pixel en una copia de la imagen o una nueva (no se reemplaza la misma, todos estos cálculos se hacen con los valores originales). Asumiendo que no existiera un valor exactamente a la mitad, se tomarían los 2 a la mitad y se calcula su promedio.

Esto nos arroja una imagen ligeramente diferente, que a simple vista no se podría observar, pero las puntas o esquinas de las figuras están cortadas. En imágenes más comunes y coloridas el efecto sería similar al de un smooth o suavizado.

Ahora, para obtener las esquinas, se obtiene la diferencia entre la imagen original y la obtenida con el filtro mediano. Esto corresponde a una simple resta entre los pixeles de la original menos los pixeles en la filtrada (posición - posición). Después se normalizan los valores a un rango entre el mayor y menor de los pixeles y se binariza (el proceso es similar al descrito en este post). El resultado de hacer lo anterior con este ejemplo:

Siendo la imagen anterior efectivamente las esquinas de las figuras. 

Lo siguiente después de haber obtenido las esquinas es realizar un recorrido a través de ellas (wire-frame). Esto es mucho más sencillo si sabemos que estas esquinas están dentro de los bordes de la figura, y ya que existen métodos para obtener los bordes (como este), podemos obtener las coordenadas de ellos fácilmente.

Los bordes de la figura original obtenidos serían:

Obtiene tanto bordes internos como externos, pero no es problema debido a que alguno de ambos esta incluido en las esquinas. Ahora, lo que se hace es distinguir los bordes por separado, es decir buscar un pixel blanco en esta imagen anterior, y almacenar todos sus pixeles vecinos blancos en una lista (algo como recorrido BFS sirve perfectamente). De esta forma discriminamos todos los bordes uno de otro.

Ya separados, buscamos pixel por pixel en cada borde por separado, y los comparamos con las esquinas. Si encontramos equivalencias, todas las equivalencias encontradas dentro de un mismo borde corresponden a esquinas de la misma figura, y las almacenamos igualmente en listas por separado. 

Con lo anterior debería ser posible trazar líneas de esquina a esquina que cubran la figura, pero existe un problema. En el caso del recorrido BFS, este se hace de una forma expansiva, no sigue un orden, por lo cual al comparar puntos del borde con puntos de esquinas, al agregarlos a una lista no estarán ordenados y podría pasar algo como:

Debido al ordenamiento de las esquinas, el cuadrado-rectángulo no fue enmarcado correctamente.

Para arreglar esto, antes de dibujar las líneas se ordenan los puntos de cierta forma, ya sea siguiendo las manecillas del reloj o en contra. Esto se hace calculando un punto central entre ellos, y calculando para cada uno su ángulo con respecto a el centro. De esta manera ordenamos los puntos en base a estos ángulos, y trazamos líneas en orden. El resultado es:

Los colores dictan el orden. Rojo fue la primera línea trazada, verde la segunda, azul la tercera, y celeste la cuarta. El encuadramiento es correcto ahora, y podemos determinar el orden de las esquinas (y por consiguiente las líneas trazadas entre ellas).

Otro ejemplo:

Por alguna razón los cruces con diagonales no son detectados correctamente, por lo que las esquinas no aparecen y solo se traza una línea diagonal en dichas figuras. Pero en los cruces entre líneas verticales y horizontales las esquinas se detectan correctamente.

Código: