41
La Transformada de Hough. Detección de Líneas y Círculos Presentado por: Tania Martínez

Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

  • Upload
    lamhanh

  • View
    222

  • Download
    1

Embed Size (px)

Citation preview

Page 1: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

La Transformada de Hough. Detección deLíneas y Círculos

Presentado por: Tania Martínez

Page 2: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

Herramienta utilizada para detectar figuras enuna imagen digital que pueden ser expresadasmatemáticamente, tales como rectas, círculos oelipses.

La Transformada de Hough

Page 3: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

inicialmente esta técnica solo se aplicaba a ladetección de rectas en una imagen, más tarde seextendió para identificar cualquier figura que sepudiera describir con unos cuantos parámetros.

La Transformada de Hough

Page 4: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

Como primer paso, se puede usar un detectorde bordes para obtener los puntos de la imagenque pertenecen a la frontera de la figuradeseada.

La Transformada de Hough

Page 5: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

Debido a las imperfecciones, ya sea de la imagencaptada o del detector de bordes, existenmuchos puntos que pertenecen a la línea y quefaltan en la imagen; también pueden existirseparaciones espaciales entre la figura ideal (porejemplo, una recta) y los puntos ruidosos delborde detectado.

La Transformada de Hough

Page 6: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

El objetivo de la transformada de Hough esresolver este problema, haciendo posiblerealizar agrupaciones de los puntos quepertenecen a los bordes de posibles figuras através de un procedimiento de votación sobreun conjunto de figuras parametrizadas.

La Transformada de Hough

Page 7: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

Será responsabilidad nuestra establecer elumbral de votos para considerar que una líneaexiste en la imagen

La Transformada de Hough

Page 8: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:Para poder representar todas las posibles rectasque puedan aparecer en la imagen, podemosutilizar la ecuación de la recta en coordenadaspolares:

xcos θ+ysin θ=ρ

La Transformada de Hough

Page 9: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

Se tendrá el rango natural de θ ∈ [0, 2π]. Luego,se transforma cada punto (x, y) de la imagen deorigen, en los puntos (ρi, θi ), el espacio definidopor (ρ, θ) se denomina espacio de Hough para elconjunto de rectas en dos dimensiones.

La Transformada de Hough

Page 10: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:Para un punto arbitrario en la imagen con

coordenadas (x0,y0), las rectas que pasan por

ese punto son los pares (ρ,θ) con r = x*cos θ +y*sin θ donde ρ (la distancia entre la línea y elorigen) está determinado por θ. Estocorresponde a una curva sinusoidal en elespacio (ρ,θ) que es única para ese punto.

La Transformada de Hough

Page 11: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

Si las curvas correspondientes a dos puntos seinterceptan, el punto de intersección en elespacio de Hough corresponde a una línea en elespacio de la imagen que pasa por estos dospuntos.

La Transformada de Hough

Page 12: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

Generalizando, un conjunto de puntos queforman una recta, producirán sinusoides que seinterceptan en los parámetros de esa línea.

La Transformada de Hough

Page 13: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

El algoritmo de la transformada de Hough usauna matriz, llamada acumulador, cuyadimensión es igual al número de parámetrosdesconocidos del problema, en el caso de unarecta la dimensión del acumulador será dos,correspondientes a los valores cuantificadospara (ρ,θ)

La Transformada de Hough

Page 14: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

Para construir el acumulador es necesariodiscretizar los parámetros que describen lafigura. Cada celda del acumulador representauna figura cuyos parámetros se pueden obtenera partir de la posición de la celda.

La Transformada de Hough

Page 15: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

Cada punto en la imagen vota por las posiblesrectas a las que puede pertenecer ese punto.Esto se logra buscando todas las posiblescombinaciones de valores para parámetros quedescriben la figura (los posibles valores seobtienen a partir del acumulador).

La Transformada de Hough

Page 16: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

Si es así, se calculan los parámetros de esafigura, y después se busca la posición en elacumulador correspondiente a la figura definida,y se incrementa el valor que hay en esa posición.

La Transformada de Hough

Page 17: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:

Las figuras se pueden detectar buscando lasposiciones del acumulador con mayor valor(máximos locales en el espacio del acumulador).La forma más sencilla de encontrar estos picoses aplicando alguna forma de umbral

La Transformada de Hough

Page 18: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA: Algoritmo1: cargar imagen2: detectar los bordes en la imagen3: por cada punto en la imagen:4: si el punto (x,y) esta en un borde:5: por todos los posibles ángulos θ :6: calcular ρ para el punto (x,y) con un ángulo θ7: incrementar la posición (ρ, θ) en el acumulador8: buscar las posiciones con los mayores valores en el

acumulador9: devolver las rectas cuyos valores son los mayores en el

acumulador.

La Transformada de Hough

Page 19: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:Considera tres puntos, mostrados aquí comopuntos negros:

La Transformada de Hough

Page 20: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:Por cada punto se dibujan un número de líneasque pasan por los mismos, con distintosángulos. Son las líneas continuas.

La Transformada de Hough

Page 21: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:Por cada línea se dibuja una recta perpendiculara esta que pasa por el origen de coordenadas.Son las líneas discontinuas.

La Transformada de Hough

Page 22: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:La longitud y el ángulo de cada línea discontinuase calcula. Los resultados se muestran en lastablas.

La Transformada de Hough

Page 23: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:Se crea un grafo con las longitudes de las líneaspor cada ángulo, conocido como grafo delespacio de Hough.

La Transformada de Hough

Page 24: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

RECTA:El punto donde las curvas se interceptan da ladistancia y el ángulo. Esta distancia y esteángulo indican la recta que se intercepta con lospuntos anteriores. El grafo muestra el puntorosado donde se interceptan las curvas, estepunto corresponde a la recta rosada de laFigura, que pasa por los tres puntos negros.

La Transformada de Hough

Page 25: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

CIRCULO:

Para definir la transformada de Hough para elcírculo, lo primero que debemos hacer esexpresar el círculo mediante la siguienteecuación:

(x-a)^2+(y-b) ^2=r^2

La Transformada de Hough

Page 26: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

CIRCULO:

Donde (a,b) es el centro del círculo y r su radio.Para encontrar circunferencias usando latransformada de Hough, se necesita unacumulador con tres dimensiones .

La Transformada de Hough

Page 27: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

CIRCULO:Después cada punto en la imagen vota por lascircunferencias en los que pudiera estar. Una vezterminado este procedimiento se buscan lospicos en el acumulador y con esto se obtienen elradio y el centro de la circunferencia. Si seconociera el radio de antemano, solo senecesitaría un acumulador de dos dimensiones

La Transformada de Hough

Page 28: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

CIRCULO:

La Transformada de Hough

Page 29: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

En MATLAB

HOUGH implementa la transformada Houghestandar.

HOUGHPEAKS Identifica los picos en latransformada de Hough.

HOUGHLINES Extrae los segmentos de lineabasados en la transformada de Hough.

La Transformada de Hough

Page 30: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

En MATLABBusque los segmentos delinea correspondiente a 5picos de la transformada deHough de la imagencircuit.tif rotada,adicionalmente indique elsegmento mas largo.

La Transformada de Hough

Page 31: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

En MATLAB

La Transformada de Hough

Page 32: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

La Transformada de Hough

Page 33: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

En MATLAB

La Transformada de Hough

Page 34: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

La Transformada de Hough

Page 35: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

En MATLAB

La Transformada de Hough

Page 36: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

La Transformada de Hough

Page 37: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

La Transformada de Hough

Page 38: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

En MATLAB

La Transformada de Hough

Page 39: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

La Transformada de Hough

Page 40: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

En MATLAB

La Transformada de Hough

Page 41: Presentado por: Tania Martínez · 2015-09-25 · Herramienta utilizada para detectar figuras en una imagen digital que pueden ser expresadas matemáticamente, tales como rectas,

• Rojas, T., Sanz, W., y Arteaga F.(2008). Sistema de visión porcomputadora para la detección de objetos esféricos a través dela transformada de Hough. Revista Ingeniería UC, 15 (1), 77-87.

• Technology Robotix Society. Tutorial: Shape Detection.Disponible en:

http://www.robotix.in/tutorials/categ/opencv/shape_detection

• Escolano, F., Cazorla, M., Galipienso, M., Pardo, O., y Lozano,M.,(2003) . Inteligencia Artificial. Modelos, Técnicas y Áreas deAplicación. Madrid, España: Paraninfo.

Bibliografía