Transformada de Hough

La transformada de Hough es una técnica para la detección de figuras en imágenes digitales. Esta técnica es mayormente usada en el campo de Visión por Computadora. Con la transformada de Hough es posible encontrar todo tipo de figuras que puedan ser expresadas matemáticamente, tales como rectas, circunferencias o elipses.

Historia

La transformada de Hough fue propuesta y patentada en 1962, por Paul Hough,^[1] inicialmente esta técnica solo se aplicaba a la detección de rectas en una imagen, más tarde se extendió para identificar cualquier figura que se pudiera describir con unos cuantos parámetros;^[2] más comúnmente circunferencias y elipses. La transformada de Hough, como se usa actualmente, fue inventada por Richard Duda y Peter Hart en 1972, quienes lo llamaron "Transformada de Hough Generalizada".^[2] Dana H. Ballard popularizó este método en la comunidad de Visión por Computadora en un artículo publicado en 1981, llamado Generalizando la transformada de Hough para detectar figuras arbitrarias.

Problema

En el análisis automatizado de imágenes, es común encontrar el problema de detectar figuras simples, tales como rectas o circunferencias. Como primer paso, se puede usar un detector de bordes para obtener los puntos de la imagen que pertenecen a la frontera de la figura deseada. Debido a las imperfecciones, ya sea de la imagen captada o del detector de bordes, existen muchos puntos que pertenecen a la curva y que faltan en la imagen; también pueden existir desviaciones espaciales entre la figura ideal (por ejemplo, una recta) y los puntos ruidosos del borde detectado. Por estas razones, usualmente no es trivial agrupar los bordes detectados en un conjunto apropiado de figuras, ya sean circunferencias o cualquier otra figura. El objetivo de la transformada de Hough es resolver este problema, haciendo posible realizar agrupaciones de los puntos que pertenecen a los bordes de posibles figuras a través de un procedimiento de votación sobre un conjunto de figuras parametrizadas.

Detectando líneas rectas

El caso más simple para la transformada de Hough es la transformación lineal para detectar líneas rectas. En el espacio de la imagen, la recta se puede representar con la ecuación $y=m*x+n$ y se puede graficar para cada par $(x,y)$ de la imagen. En la transformada de Hough, la idea principal es considerar las características de una recta en término de sus parámetros $(m,n)$ , y no como puntos de la imagen $(x_{1},y_{1}),...,(x_{n},y_{n})$ . Basándose en lo anterior, la recta $y=m*x+n$ se puede representar como un punto $(m,n)$ en el espacio de parámetros. Sin embargo, cuando se tienen rectas verticales, los parámetros de la recta $(m,n)$ se indefinen. Por esta razón es mejor usar los parámetros que describen una recta en coordenada polares, denotados $(\rho ,\theta )$ .

El parámetro $\rho$ representa la distancia entre el origen de coordenadas y el punto $(x,y)$ , mientras que $\theta$ es el ángulo del vector director de la recta perpendicular a la recta original y que pasa por el origen de coordenadas.

Usando esta parametrización, la ecuación de una recta se puede escribir de la siguiente forma: $y=\left(-{\frac {\cos {\theta }}{\sin {\theta }}}\right)*x+\left({\frac {\rho }{\sin {\theta }}}\right)$ que se puede reescribir como $\rho =x*\cos {\theta }+y*\sin {\theta }$ .

Entonces, es posible asociar a cada recta un par $(\rho ,\theta )$ que es único si $\theta \in [0,\pi )$ y $\rho \in \mathbf {R}$ o $\theta \in [0,2*\pi )$ y $\rho \geq 0$ . El espacio $(\rho ,\theta )$ se denomina espacio de Hough para el conjunto de rectas en dos dimensiones.

Para un punto arbitrario en la imagen con coordenadas $(x_{0},y_{0})$ , las rectas que pasan por ese punto son los pares $(\rho ,\theta )$ con $\rho =x*\cos {\theta }+y*\sin {\theta }$ donde $\rho$ (la distancia entre la línea y el origen) está determinado por $\theta$ . Esto corresponde a una curva sinusoidal en el espacio $(\rho ,\theta )$ , que es única para ese punto. Si las curvas correspondientes a dos puntos se intersecan, el punto de intersección en el espacio de Hough corresponde a una línea en el espacio de la imagen que pasa por estos dos puntos. Generalizando, un conjunto de puntos que forman una recta, producirán sinosoides que se intersecan en los parámetros de esa línea. Por tanto, el problema de detectar puntos colineales se puede convertir en un problema de buscar curvas concurrentes.

Implementación

El algoritmo de la transformada de Hough usa una matriz, llamada acumulador, cuya dimensión es igual al número de parámetros desconocidos del problema. Por ejemplo, para detectar la existencia de una recta de la forma $y=m*x+n$ , la dimensión del acumulador sería dos, ya sea su representación en coordenadas cartesianas $(m,n)$ o en coordenadas polares $(\rho ,\theta )$ , son desconocidos. Las dos dimensiones del acumulador corresponden a los valores cuantificados para $(\rho ,\theta )$ .

Para construir el acumulador es necesario discretizar los parámetros que describen la figura. Cada celda del acumulador representa una figura cuyos parámetros se pueden obtener a partir de la posición de la celda.

Por cada punto en la imagen, se buscan todas las posibles figuras a las que puede pertenecer ese punto. Esto se logra buscando todas las posibles combinaciones de valores para parámetros que describen la figura (los posibles valores se obtienen a partir del acumulador). Si es así, se calculan los parámetros de esa figura, y después se busca la posición en el acumulador correspondiente a la figura definida, y se incrementa el valor que hay en esa posición.

Las figuras se pueden detectar buscando las posiciones del acumulador con mayor valor (máximos locales en el espacio del acumulador). La forma más sencilla de encontrar estos picos es aplicando alguna forma de umbral, pero distintas técnicas podrían dar mejores resultados en distintas circunstancias, determinando donde se encuentran las figuras y cuantas hay.

Por los errores que se pueden cometer detectando bordes, existirán imperfecciones en el espacio acumulador, lo que puede hacer que no sea trivial en encontrar los picos correctos y por tanto las figuras apropiadas.

Aquí se muestra un pseudocódigo de como debería funcionar el algoritmo para detectar rectas en una imagen:

1:    cargar imagen
2:    detectar los bordes en la imagen
3:    por cada punto en la imagen:
4:       si el punto  $(x,y)$  esta en un borde:
5:          por todos los posibles ángulos  $\theta$ :
6:             calcular  $\rho$  para el punto  $(x,y)$  con un ángulo  $\theta$ 
7:             incrementar la posición  $(\rho ,\theta )$  en el acumulador
8:    buscar las posiciones con los mayores valores en el acumulador
9:    devolver las rectas cuyos valores son los mayores en el acumulador.

Ejemplo

Considera tres puntos, mostrados aquí como puntos negros:

Por cada punto se dibujan un número de líneas que pasan por los mismos, con distintos ángulos. Son las líneas continuas.
Por cada línea se dibuja una recta perpendicular a esta que pasa por el origen de coordenadas. Son las líneas discontinuas.
La longitud y el ángulo de cada línea discontinua se calcula. Los resultados se muestran en las tablas.
Esto se repite por cada punto.
Se crea un grafo con las longitudes de las líneas por cada ángulo, conocido como grafo del espacio de Hough.

El punto donde las curvas se intersecan da la distancia y el ángulo. Esta distancia y este ángulo indican la recta que se interseca con los puntos anteriores. El grafo muestra el punto rosado donde se intersecan las curvas, este punto corresponde a la recta rosada de la Fig. 1, que pasa por los tres puntos negros.

El siguiente ejemplo muestra los resultados de la transformada de Hough en una imagen que contiene dos líneas bien definidas:

Los resultados de esta transformación son almacenados en una matriz. Los valores de cada celda representan la cantidad de curvas que pasan por un punto. Mientras mayor sea el valor de la celda más claro se verá. Los dos puntos más claros de la imagen representan las dos líneas.

Curvas paramétricas

La Transformada de Hough no se restringe solamente a la detección de rectas, a pesar de que se usa comúnmente con este propósito. Otras figuras geométricas que se pueden describir con unos cuantos parámetros se pueden detectar también con esta técnica.

Por ejemplo, si se quieren detectar circunferencias con la ecuación: $(x-a)^{2}+(y-b)^{2}=r^{2}$

Para describir una circunferencia son necesarios tres parámetros:

Centro de la circunferencia $(a,b)$
Radio $(r)$

Para encontrar circunferencias usando la transformada de Hough, se necesita un acumulador con tres dimensiones $(a,b,r)$ . Después cada punto en la imagen vota por las circunferencias en los que pudiera estar. Una vez terminado este procedimiento se buscan los picos en el acumulador y con esto se obtienen el radio y el centro de la circunferencia. Si se conociera el radio de antemano, solo se necesitaría un acumulador de dos dimensiones.

Generalización

La Transformada de Hough Generalizada fue presentada por Dana H. Ballard en 1981. Fue una modificación de la Transformada de Hough usando el principio de emparejamiento de plantillas.^[3] Esta modificación permite detectar un objeto arbitrario descrito por su modelo. El problema de encontrar un objeto descrito por su modelo en una imagen se puede resolver encontrando la posición del objeto en la imagen. En la transformada de Hough Generalizada, el problema de encontrar la posición del modelo, es transformado en un problema de encontrar el parámetro de transformación que hace corresponder el modelo en la imagen.

Por ejemplo, se quiere encontrar una figura por sus puntos frontera y un punto de referencia. Por cada punto frontera $p$ , se puede calcular un vector de desplazamiento: $r=a-p$ con $a$ como función de la orientación del gradiente $\theta$ . Luego, para el modelo de la figura se construye el acumulador almacenando los vectores de desplazamiento $r$ en función de la dirección del gradiente $\theta$ . Para detectar la figura en la imagen por cada punto $p$ del borde con dirección de gradiente $\theta$ :

Toma todos los $r$ indexados con $\theta$ .
Por cada $r(\theta )$ , pon un voto en el espacio de Hough en $p+r(\theta )$ .

Los picos en el acumulador representan la figura deseada, pero esta técnica es solamente invariante con la traslación en dos dimensiones. Para que sea invariante respecto al escalado y la rotación, hay que construir dos tablas adicionales para todos los posibles valores discretos de $\phi$ y $s$ : $T_{S}[R(\theta )]$ y $T_{\phi }[R[\theta ]]$ . Después se vota por $p+r(\theta ,s)$ .

Limitaciones

La transformada de Hough es eficiente si un gran número de votos cae en la celda correcta. Para que una celda sea detectada con facilidad sin importar los errores introducidos por el ruido en la imagen, debe destacarse entre sus vecinas. Esto significa que si se tienen muchos posibles valores para los parámetros, la visibilidad de la celda podría estar comprometida por sus celdas vecinas; pero si se tienen pocos valores se podrían estar dando resultados erróneos, ignorando figuras que están en la imagen.

Si se tienen muchos parámetros el promedio de los votos por cada celda es bajo y las celdas correspondientes a las verdaderas figuras en la imagen no tienen porqué parecer tener un número mayor de votos que las celdas vecinas. La complejidad del algoritmo aumenta a un ritmo de $O(A^{p-2})$ donde $A$ es la cantidad de puntos en la imagen y $p$ es la cantidad de parámetros. Por esta razón la transformada de Hough debe usarse con mucho cuidado cuando se va a detectar algo que no sean rectas o circunferencias.

Finalmente, la eficiencia de la transformada de Hough depende de la calidad de los datos de entrada del algoritmo: los bordes se deben detectar bien para que sea eficiente el procedimiento. Usar la transformada de Hough en imágenes con mucho ruido suele ser un problema y generalmente se debe aplicar algún tratamiento a la imagen para eliminarlo.

Referencias

↑ HOUGH, P. V. C. Method and means for recognizing complex patterns. U. S. Patent 3, 069 654, December 18 , 1962.
↑ ^a ^b Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972)
↑ D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981.

Datos: Q195076
Multimedia: Hough transform / Q195076

[1] HOUGH, P. V. C. Method and means for recognizing complex patterns. U. S. Patent 3, 069 654, December 18 , 1962.

[ref_duplicada_1-2] Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972)

[3] D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981.

[1]

[2]

[3]