Transformada de Hough

Universidad Nacional de Quilmes – Ing. en Automatización y Control Industrial
Cátedra: Visión Artificial
Septiembre de 2005

Procesamiento Global empleando la Transformada de Hough
En este apunte vamos a conocer a la transformada de Hough. A diferencia de los métodos de análisis local que ya se han visto, la transformada de Hough considera las relaciones globales entre píxeles de bordepermitiendo encontrar ciertos patrones en la imagen como líneas y círculos.
Supongamos que para n puntos de la imagen se desean encontrar aquellos subconjuntos de puntos que caen en líneas rectas. Una posible solución podría ser en primer lugar encontrar todas las líneas determinadas por cada par de puntos y entonces encontrar
todos los subconjuntos de puntos que están cerca de cada recta en particular.Este problema así planteado requiere encontrar n(n-1)/2~n2 rectas y realizar n(n(n-1))/2~n3 comparaciones de cada punto a línea. Este método no será viable salvo en casos triviales.

Figura 1: (a) Plano xy. (b) Espacio de parámetros.

Una alternativa al método de búsqueda exhaustiva es la transformada de Hough. Consideramos un punto (xi,yi) y la ecuación de la recta, de la forma pendiente y ordenadaal
origen,
(1)
yi = ax i + b
Por el punto (xi,yi) pasan infinitas rectas, pero todas satisfacen la ecuación anterior para diferentes valores de a y b. Sin embargo, escribiendo esta ecuación en la forma

b = − xi a + y i

(2)

y considerando el plano ab (también denominado espacio de parámetros) da lugar a una
única recta para el par (xi,yi) constante. Si ahora consideramos un segundo punto(xj,yj),
también va a tener su recta asociada en el espacio de parámetros. Estas dos rectas se
cortarán en el espacio de parámetros en un punto (a’,b’), donde a’ es la pendiente y b’ la
ordenada al origen de la recta que contiene a los puntos (xi,yi) y (xj,yj) en el plano xy, como se puede ver en la figura 1. De hecho, todos los puntos de esa recta en el plano xy
darán lugar a rectas diferentes en elespacio de parámetros que se cortan en un único
punto (a’,b’).
El atractivo de la transformada de Hough proviene de subdividir el espacio de párametros en celdas acumuladoras, como se puede ver en la figura 2, donde (amin,amax) y
(bmin,bmax) son los rangos esperados para la pendiente y la ordenada al origen. La celda
de coordenadas (i,j) con un valor de acumulador A(i,j) corresponde al cuadradoasociado
Procesamiento Global empleando la Transformada de Hough

1

Universidad Nacional de Quilmes – Ing. en Automatización y Control Industrial
Cátedra: Visión Artificial
Septiembre de 2005

con las coordenadas (ai,bj) del espacio de parámetros. Inicialmente se ponen todos los acumuladores a cero. Entonces para cada punto (xk,yk) de la imagen, permitimos que el
parámetro a pueda tomar cualquiervalor de entre los ai permitidos y calculamos b usando
la ecuación 2. Los valores resultantes para el parámetro b se redondean hasta los bj
permitidos. Si para un valor ap resultó un valor bq se tiene que

A( p , q ) = A( p , q ) + 1

(3)

Al final, un valor de M en el acumulador A(i,j) significa que M puntos del plano xy caen
sobre la recta y=aix+bj. La precisión en la colinealidad de estos puntosdepende del número de celdas del espacio de parámetros.

Figura 2: Celdas
acumuladoras en el
espacio de parámetros.

Si subdividimos el eje a en K celdas, para cada punto (xk,yk), obtenemos K valores de
b correspondientes a los K posibles valores de A. Si la imagen tiene n puntos, la carga
computacional es del orden de nK. La transformada de Hough es lineal en n, y el producto nK es mucho menor quesi hubiéramos empleado una búsqueda exhaustiva, a menos
que K sea del orden o exceda a n.
Un problema que surge al emplear la ecuación de la recta y=ax+b para representar una línea es que tanto la pendiente como la ordenada al origen pueden llegar a valer
infinito, según la línea se hace vertical. Una forma de solventar este problema consiste en
utilizar la representación normal de la recta

x...