GHT

Transformada de Hough tradicional

La transformada de Hough es una técnica de detección de figuras en imágenes. Dicha técnica comenzó aplicándose a la detección de rectas pero luego se extendió para cualquier tipo de figura con representación analítica, es decir que se pueda expresar mediante una ecuación matemática dependiente de parámetros.

La implementación de esta técnica se realiza sobre una imagen binaria. El objetivo de la transformada es encontrar la mayor cantidad de puntos distintos de cero que cumplan con la ecuación de la figura que se busca identificar. La forma en que esto se implementa es, para cada punto distinto de cero de la imagen se le asigna un voto a cada conjunto de parámetros de la representación analítica de la figura, tales que el punto en cuestión pertenezca a la figura. Los conjuntos más votados son aquellos que representan las figuras por las cuales pasan más puntos de la imagen.

Transformada de hough para figuras circulares aplicada a una imagen con tres puntos.

En la figura anterior se muestra un ejemplo para una imagen con tres puntos. Se aplica transformada de Hough para una figura circular, donde los parámetros son: x_c, y_c (cooerdenadas de los centros) y R (radio). En el ejemplo de la izquierda se muestra el resultado para dos votos con un cierto radio que cumple que la figura pasa por dos puntos y el ejemplo de la derecha para tres votos para un radio que cumple que el circulo correspondiente pase por los tres puntos de la imagen.

Transformada de Hough generalizada

Aprovechando las propiedades de la transformada de Fourier, la transformada de Hough se puede extender para figuras que no sean representables a través de una expresión analítica. En el caso que se quieran encontrar círculos en una imagen, la detección se puede realizar como se explicó anteriormente, pero otra forma es dada una imagen de un círculo, calcular la correlación entre esta y la imagen donde se quiere hacer la búsqueda. Luego los puntos de mayor valor del resultado indicaran la posición donde se dio la mayor coincidencia. De esta manera, la transformada de Hough tradicional, probando con todos los conjuntos de parámetros y viendo cuales son los más votados, es análogo a realizar una correlación entre la imagen y la figura, y luego encontrar los máximos relativos en el resultado. Pero con dos grandes diferencias, si se pasan las imágenes al espacio de las frecuencias a través de la transformada de Fourier, la correlación se puede hacer con una simple multiplicación entre matrices elemento a elemento. Y además no se necesita una representación analítica, solo una imagen de la figura que se quiere encontrar. A esta forma de encontrar coincidencias en una imagen se le llama Transformada de Hough Generalizada o Template Matching.

La implementación de la GHT es hacer la correlación entre una imagen de entrada y el template que contiene la figura que se quiere detectar. Para esto se debe transformar ambas figuras mediante una transformada de Fourier, luego conjugar una de las dos y multiplicar ambas elemento a elemento, obteniendo la transformada de la correlación. Por ende solo resta antitransformar.

Dado que realizar la correlación es análogo al método de la transformada tradicional de Hough, la imagen obtenida por el proceso explicado de correlación es similar a la matriz de votos de Hough, que llamamos espacio de Hough. Sobre este espacio se debe realizar la búsqueda de máximos locales, ya que la posición de estos puntos coincide con los lugares en la imagen donde se da la mayor coincidencia con la figura que se quiere detectar.

Este método se centra en la detección de figuras por su forma sin tener en cuenta la intensidad. Para esto se trabaja con imágenes de bordes binarias. Es decir, la imagen en la que queremos encontrar las figuras así como el template deben valer 1 en los bordes y 0 en el fondo. Normalizando el template por el área en pixeles que ocupa, hace que dada una máxima coincidencia se obtenga el valor igual a 1.

En resumen, se buscan figuras en la imagen mediante la correlacion de ambas. Se utiliza la herramienta de Fourier para acelerar el proceso y se obtiene el espacio de Hough como resultado. Luego, sabiendo que los máximos del espacio de Hough representan las máximas coincidencias entre la imagen y el template, en ese lugar de la imagen es altamente probable que se encuentre el centro de la figura que se busca. Por lo tanto, al encontrar los máximos del espacio de Hough se encuentran las figuras en la imagen.

Pruebas: implementación de la transformada de hough

Para comenzar a evaluar la herramienta de la trasformada de Hough generalizada se realizaron varias pruebas con imágenes sencillas con el fin de estudiar el funcionamiento, los resultados, las variantes y la robustez de este método.

Se crearon imágenes de figuras geométricas sencillas y se les aplicó la GHT. Al buscar un figura en la imagen con un template con la misma figura, lo que se obtiene en el espacio de Hough es una delta de valor 1. A este resultado le llamaremos correlación máxima, que es cuando se da la mayor coincidencia.

Luego se probaron distintas variantes sobre las figuras de las imágenes: cambio de grosor, cambio de orientación, agregar ruido gaussiano y sal y pimienta, cambio de intensidad. Al estar presentes esta variaciones se observa que la detección no tiene como resultado la correlación máxima.

Pruebas realizadas:

Cambio de grosor: en el espacio de Hough se observa una región con valor 1, no solo una delta. Esto es porque las coincidencias entre el template y la figura buscada se dan en una región, ya que al ser mas gruesa la figura en la imagen, el template entra varias veces dentro de esta. Esto puede ser una ventaja ya que se tiene una zona de máxima correlación en el espacio de Hough lo que podría facilitar la detección de máximos. Pero también puede ser una desventaja, encontrando falsos positivos.
Cambio de la orientación: el resultado muestra que al no coincidir las orientaciones entre la figura y el template no se percibe una delta y la intensidad de la imagen es atenuada.
Cambio de la intensidad: sí se percibe una delta, pero con una intensidad menor a 1.
Agregado de ruido sal y pimienta y gaussiano: se observa que la GHT es muy robusta al ruido, ya que a pesar de tener gran cantidad de ruido es posible detectar una delta, pero sin embargo con un valor menor que 1.
Oclusión: se observa que la GHT logra detectar la figura, sin embargo la delta en el espacio de Hough aparece atenuada.

A continuación se observa el espacio de Hough luego de realizar la búsqueda de la figura de un triángulo. Se observa una delta de valor 1 dado que la imagen contenía solamente el mismo triangulo que el template.
En la figura de la izquierda tenemos la imagen de entrada y en la figura de la derecha visualizamos el espacio de Hough.

A la izquierda imagen de entrada, a la derecha espacio de hough

Template

Al realizar distintas pruebas de la GHT con variantes en las figuras buscadas se observan cambios en el espacio de Hough. Partiendo de distintas imágenes de entrada, en las cuales tenemos distintas situaciones como cambio de grosor, rotación, etc. realizamos la búsqueda con el template. Por ejemplo, se quiere detectar triángulos ¿que sucede si busco en una imagen de entrada con la figura de un triángulo muy grueso utilizando un template de un triángulo fino?
En las siguientes imágenes se observa la imagen de entrada a la izquierda y correspondiente espacio de Hough que se obtiene como resultado a la derecha. El template utilizado es el que se encuentra más arriba.
A continuación observamos variaciones en el grosor, angulo e intensidad.

Cambio de grosor 1

Cambio de grosor 2

Cambio de grosor 3

Rotación 1

Rotación 2

Rotación 3

Oclusión 1

Oclusión 2

Oclusión 3

Padding

Al probar el funcionamiento de la GHT en los casos donde las figuras se encuentran ocluidas por los bordes de la imagen, se observó un comportamiento particular. En el caso donde el centro de la figura queda fuera de la imagen, en el espacio de Hough se observa que la detección de la figura no se da en el lugar correcto. Como se muestra mas abajo, se puede ver que al estar la figura en la parte superior de la imagen y su centro quedar fuera, luego en el espacio de Hough la detección muestra como si la figura en verdad se encontrara en la parte inferior. Esto es debido a que se utiliza la herramienta de Fourier para realizar el template-matching. Para solucionar este problema es necesario extender el espacio de Hough, de manera que todos los centros de las figuras se encuentren dentro de la imagen. Para lograr esto, se extienden la imagen de entrada y el template. Esta extención se conoce como padding. De esta manera, para asegurarnos que el centro de la figura que estamos buscando quede dentro de la imagen se hace una extensión de esta con un tamaño de por lo menos el tamaño del radio de la figura buscada. Es decir, se debe agregar un marco de pixeles negros alrededor de la imagen y del template con el tamaño apropiado. Más abajo vemos un ejemplo de esto. A la izquierda tenemos una imagen donde el centro del triángulo se encuentra fuera de ella y en el medio tenemos el resultado del espacio de Hough. A la derecha tenemos el espacio de Hough luego de hacer un padding y el marco blanco representa el tamaño de la imagen original. Podemos comprobar que el centro del triángulo se encentra fuera de la imagen original.