Download Transformada de Hough

Análisis de
imágenes
digitales
EXTRACCIÓN DE PATRONES
Transformada de Hough
DETECCIÓN DE RECTAS
•
La transformada de Hough es método de extracción de características
patentado por Paul Hough en 1962*, para la detección de bordes en imágenes
parametrizadas, es decir, los objetos que se desean detectar se representan por
medio de una ecuación conocida.
•
Originalmente fue diseñada para la extracción de líneas rectas, aunque se ha
extendido para identificar otras formas como círculo o elipses.
•
La idea es transformar la imagen del espacio Cartesiano xy a un espacio de
parámetros y a través de un proceso de votos identificar los puntos que
describen una línea recta u otra formulación de bordes.
*P.V.C. Hough, "Method and means for recognizing complex patterns," U.S Patent 3 069 654, Dec. 18, 1962.
2
DETECCIÓN DE RECTAS
•
•
Considérese un punto (xi,yi) en el plano xy y
una recta que pasa a través de ese punto de la
forma yi = axi + b.
y = 2x − 1
Si se varían los valores de a y b se tendrán
infinitas líneas que satisfacen la ecuación de la
recta.
•
Si cada recta que pasa por (xi,yi) se expresa en
términos de (a,b) se tiene b = −axi + yi.
•
Entonces, considerando el plano ab (espacio de
parámetros) habrá un punto para cada posible
recta que pasa por (xi,yi), esto es, una recta en el
plano xy se transforma en punto en el plano ab.
3
(xi,yi)
y
y = −x + 2
x
yi = 2xi − 1
b
yi = −xi + 2
a
DETECCIÓN DE RECTAS
•
•
•
Ahora considérese un par de puntos (xi,yi) y
(xj,yj) en el espacio xy.
(xj,yj)
y
Entonces, cuando existe una línea recta que
simultáneamente pasa por los puntos (xi,yi) y
(xj,yj) en el espacio xy, todas las posible
soluciones en el espacio de parámetros se
intersectan en algún punto (a',b').
Por tanto, todos los puntos que estén sobre
una misma línea recta en el espacio xy
compartirán un sólo punto en el espacio ab.
4
(xi,yi)
x
b
(a',b')
a
DETECCIÓN DE RECTAS
•
Algoritmo para detección de líneas en una imagen:
1. Encontrar los puntos de los bordes de la imagen con alguna técnica de
detección de bordes (e.g., el detector de Canny).
2. Definir los intervalos para los parámetros a y b.
3. Inicializar una matriz acumuladora H en ceros en donde se contarán los
votos para los valores (a,b) que sean solución a la ecuación de la recta.
4. Evaluar cada punto de borde (x,y) en la ecuación b = −axi + yi e
incrementar en ‘1’ el valor de H(a,b) que resuelva la ecuación. El resultado
será un histograma bidimensional con los valores de ocurrencia para
ciertos valores de (a,b).
5. Umbralar la matriz H para definir los puntos (a,b) con mayor ocurrencia.
Estos puntos corresponden a los parámetros de las líneas rectas
encontradas en la imagen original.
5
DETECCIÓN DE RECTAS
Imagen de entrada
Detección de bordes con Canny
Líneas detectadas
Ocurrencias
Espacio de parámetros
b
a
b
a
6
DETECCIÓN DE RECTAS
•
Ventaja: Los píxeles que están sobre una línea no necesariamente deben ser
contínuos, de modo que se pueden detectar líneas discontinuas.
•
Deventaja: Una dificultad de esta aproximación se encuentra en la
representación de líneas verticales, ya que la pendiente a→∞.
Imagen de entrada
1
Espacio de parámetros
1
2
1
3
Líneas detectadas
b
5
2
4
3
3
2
4
5
a
7
4
5
DETECCIÓN DE RECTAS
•
•
•
Para evitar el problema de valores infinitos de a,
la ecuación de la recta se puede representar en
su forma polar como: ρ = xicos θ + yisin θ.
Los puntos en el plano xy se representan como
curvas sinusoidales en el plano ρθ, donde la
intersección de dos curvas en los puntos (ρ',θ')
corresponde a la línea que pasa por (xi,yi) y
(xj,yj).
Para calcular la transformada de Hough, el
espacio ρθ se representa como una matriz
acumuladora en el rango −90º≤θ≤90º y
− 2D ≤ρ≤ 2D , donde D es la distancia distancia
entre esquinas opuestas de la imagen.
8
y
θ
ρ
(xj,yj)
(xi,yi)
x
θ’
ρ = x j cosθ + x j sin θ
ρ’
ρ = x i cosθ + y i sin θ
ρ
θ
DETECCIÓN DE RECTAS
•
Se resuelve el problema de detección de líneas verticales:
Imagen de entrada
1
Espacio de parámetros
Líneas detectadas
1
2
2
2
3
θ
3
1
3
4
4
5
5
ρ
9
4
5
DETECCIÓN DE RECTAS
Imagen de entrada
Detección de bordes con Canny
Líneas detectadas
Ocurrencias
Espacio de parámetros
θ
ρ
θ
ρ
10
DETECCIÓN DE RECTAS
Imagen de entrada
Líneas detectadas
Detección de bordes con Canny
Espacio de parámetros
ρ
11
θ
DETECCIÓN DE RECTAS
Imagen de entrada
Líneas detectadas
Detección de bordes con Canny
Espacio de parámetros
ρ
12
θ
DETECCIÓN DE CÍRCULOS
•
•
Aunque el enfoque principal de la transformada
de Hough es la detección de líneas rectas,
también se puede aplicar a cualquier función de
la forma g(v,c) = 0, donde v es un vector de
coordenadas y c es un vector de coeficientes.
y
Un ejemplo puede ser la detección de círculos,
cuya ecuación general es:
(x − a) + (y −b) = r
2
2
r
2
donde
x = a + r cos(θ ) y x = b + r sin(θ )
donde r es el radio del círculo, 1≤ a ≤N y
1≤ b ≤M, siendo N y M el ancho y la altura de la
imagen.
13
x
θ
DETECCIÓN DE CÍRCULOS
•
•
El espacio de parámetros para el círculo
pertenece a R3 mientras que la línea recta está
definida en R2. Esto quiere decir que conforme
aumenta el número de parámetros para decribir
una forma también aumenta la dimensión del
espacio de parámetros.
r
b
Para simplificar la representación del círculo se
considera el radio constante, de modo que si
conocemos de antemano el radio del círculo
que se desea detectar el espacio de parámetros
se reduce a R2.
a
14
DETECCIÓN DE RECTAS
•
Algoritmo para detección de círculos en una imagen:
1. Encontrar los puntos de los bordes de la imagen con alguna técnica de
detección de bordes (e.g., el detector de Canny).
2. Definir los intervalos para θ∈[0º, 360º] y el establecer el valor de r.
3. Inicializar una matriz acumuladora H en ceros en donde se contarán los
votos para los valores (a,b) que sean solución a la ecuación del círculo.
4. Evaluar cada punto de borde (x,y) en la ecuación r2 = (x−a)2 + (y−b)2 e
incrementar en ‘1’ el valor de H(a,b) que resuelva la ecuación. El resultado
será un histograma bidimensional con los valores de ocurrencia para
ciertos valores de (a,b).
5. Umbralar la matriz H para definir los puntos (a,b) con mayor ocurrencia.
Estos puntos corresponden a los parámetros de los círculos encontrados
en la imagen original.
15
DETECCIÓN DE RECTAS
Imagen de entrada
Círculos detectados
Detección de bordes con Canny
Espacio de parámetros
b
16
a
DETECCIÓN DE RECTAS
Imagen de entrada
Líneas detectadas
Detección de bordes con Canny
Espacio de parámetros
b
17
a
DETECCIÓN DE RECTAS
Imagen de entrada
Líneas detectadas
Detección de bordes con Canny
Espacio de parámetros
b
18
a