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.
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.
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.
En el espacio de la imagen, la recta se puede representar con la ecuación
Por esta razón es mejor usar los parámetros que describen una recta en coordenada polares, denotados
, la dimensión del acumulador sería dos, ya sea su representación en coordenadas cartesianas
Las dos dimensiones del acumulador corresponden a los valores cuantificados para
Para construir el acumulador es necesario discretizar los parámetros que describen la figura.
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).
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.
Aquí se muestra un pseudocódigo de como debería funcionar el algoritmo para detectar rectas en una imagen: Considera tres puntos, mostrados aquí como puntos negros:
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.
Mientras mayor sea el valor de la celda más claro se verá.
Para describir una circunferencia son necesarios tres parámetros: Para encontrar circunferencias usando la transformada de Hough, se necesita un acumulador con tres dimensiones
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.
La Transformada de Hough Generalizada fue presentada por Dana H. Ballard en 1981.
[3] Esta modificación permite detectar un objeto arbitrario descrito por su modelo.
: 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
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.
La complejidad del algoritmo aumenta a un ritmo de
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.
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.