Hough transformar

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de marzo de 2021; las comprobaciones requieren 2 ediciones .

La transformada de Hough  es un  algoritmo computacional utilizado para la identificación paramétrica de los elementos geométricos de una imagen rasterizada (patente de 1962 de Paul Hough). Se utiliza en análisis de imágenes, imágenes digitales y visión por computadora . Diseñado para buscar objetos pertenecientes a una determinada clase de figuras mediante el procedimiento de votación. El procedimiento de votación se aplica al espacio de parámetros, a partir del cual se obtienen objetos de una determinada clase de cifras según el máximo local en el llamado espacio acumulador , que se construye al calcular la transformación de Hough.

El clásico algoritmo de transformada de Hough se ocupa de identificar líneas en una imagen, pero luego el algoritmo se amplió para identificar la posición de una figura arbitraria, más comúnmente elipses y círculos . La transformada de Hough, tal como se usa hoy en día, se inventó en 1981. Este algoritmo se denominó " transformación de Hough generalizada " y fue propuesto por Dana Ballard .

Teoría

En el análisis automatizado de imágenes digitales, a menudo surge el problema de identificar formas simples, como líneas, círculos o elipses. En muchos casos, se utiliza un algoritmo de búsqueda de bordes como preprocesamiento para obtener puntos que se encuentran en una curva en una imagen. Sin embargo, ya sea debido al ruido de la imagen o a un algoritmo de detección de bordes imperfecto, pueden aparecer puntos "perdidos" en la curva, así como ligeras desviaciones de la forma ideal de una línea recta, un círculo o una elipse. Por estas razones, a menudo es bastante difícil atribuir los límites encontrados a las líneas, círculos y elipses correspondientes en la imagen. El propósito de la transformada de Hough es resolver el problema de agrupar puntos límite aplicando un determinado procedimiento de votación a un conjunto de objetos de imagen parametrizados.

En el caso más simple, la transformada de Hough es una transformada lineal para la detección de líneas. La línea recta puede estar dada por la ecuación y = mx + b y puede calcularse a partir de cualquier par de puntos ( x, y ) en la imagen. La idea principal de la transformada de Hough es tener en cuenta las características de una línea recta no como una ecuación construida a partir de un par de puntos de la imagen, sino en términos de sus parámetros, es decir, m  es la pendiente y b  es la punto de intersección con el eje y. En base a esto, la recta dada por la ecuación y = mx + b se puede representar como un punto con coordenadas ( b, m ) en el espacio de parámetros.

Sin embargo, las líneas paralelas al eje y tienen infinitos valores para el parámetro m [1] [2] . Por lo tanto, es más conveniente representar la línea usando otros parámetros, conocidos como y [ rho, theta ]. El parámetro  es la longitud del radio vector del punto de la línea más cercana al origen (es decir, la normal a la línea trazada desde el origen), y  es el ángulo entre este vector y el eje x. Con tal descripción de líneas rectas, no surgen parámetros infinitos.

Por lo tanto, la ecuación de una línea recta se puede escribir como

,

o después de la conversión

.

Por tanto, es posible asociar a cada línea de la imagen original (en el plano XY) un punto de coordenadas r, θ en el plano de parámetros, que es único siempre que y , o que y .

El plano ( r,θ ) a veces se denomina Espacio de Hough para un conjunto de líneas en el caso bidimensional. La transformada de Hough está conceptualmente muy cerca de la transformada de Radon 2D y puede considerarse como su representación discreta.

Por cada punto del plano pueden pasar infinitas líneas. Si este punto tiene coordenadas , entonces todas las líneas que pasan por él corresponden a la ecuación:

.

Esto corresponde a una línea sinusoidal en el espacio de Hough ( r, θ ), que, a su vez, es única para un punto dado y lo define de manera única. Si estas líneas (curvas) correspondientes a dos puntos se superponen, entonces el punto (en el espacio de Hough ) donde se cruzan corresponde a líneas rectas (en la ubicación de la imagen original) que pasan por ambos puntos. En general, un conjunto de puntos que forman una línea recta definen sinusoides que se intersecan en el punto del parámetro para esa línea. Así, el problema de detectar puntos colineales puede reducirse al problema de detectar curvas que se intersecan.

Implementación

El algoritmo de transformada de Hough usa una matriz llamada acumulador para determinar la presencia de la línea y = mx + b . La dimensión del acumulador es igual al número de parámetros desconocidos del espacio de Hough. Por ejemplo, para una transformación lineal, debe usar una matriz bidimensional, ya que hay dos parámetros desconocidos: m y b . Las dos dimensiones del acumulador corresponden a los valores cuantificados de los parámetros m y b . Para cada punto y sus vecinos, el algoritmo determina si el peso del límite en ese punto es suficiente. En caso afirmativo, el algoritmo calcula los parámetros de la línea e incrementa el valor en la celda del acumulador correspondiente a los parámetros dados.

Luego, al encontrar las celdas del acumulador con valores máximos, generalmente buscando un máximo local en el espacio del acumulador, se pueden determinar las líneas más adecuadas. La forma más fácil es el filtrado de umbral. Sin embargo, diferentes métodos pueden dar diferentes resultados en diferentes situaciones. Dado que las líneas obtenidas no contienen información sobre la longitud, el siguiente paso es encontrar las partes de la imagen correspondientes a las líneas encontradas. Además, debido a errores en la etapa de determinación de los límites de las figuras, el espacio acumulador también contendrá errores. Esto hace que encontrar líneas adecuadas no sea trivial.

Ejemplo

Considere la imagen de prueba original de tres puntos negros. Comprueba si los puntos están en línea recta.

Las coordenadas del punto de intersección de las sinusoides determinan los parámetros de la línea recta común a los puntos que se comprueban en la imagen original.

El siguiente ejemplo muestra los resultados de la transformada de Hough para una imagen con dos líneas que se cruzan.

Los resultados de esta transformación se almacenan en la matriz. Los valores en las celdas de la matriz representan el número de curvas que pasan por el punto. Los valores máximos en las celdas corresponden a dos puntos más brillantes de la imagen y los parámetros de las líneas correspondientes. Los dos puntos brillantes son las intersecciones de dos líneas curvas. Desde estos puntos, puede determinar el ángulo y la distancia a la línea recta en la imagen original.

Restricciones

La transformada de Hough es efectiva solo si hay un número significativo de "aciertos" en el elemento correspondiente del espacio de Hough, solo entonces es posible determinar la figura con confianza, despreciando el ruido de fondo. Esto significa que el tamaño del elemento no debe ser muy pequeño, de lo contrario, algunos valores caerán en los elementos vecinos, lo que reducirá la visibilidad del elemento deseado.

Además, cuando el número de parámetros es grande (más de tres), el número medio de aciertos en un elemento es pequeño y, por lo tanto, el elemento correcto no será muy diferente de sus vecinos. Por lo tanto, el algoritmo debe usarse con mucho cuidado para no definir nada más que líneas rectas y círculos.

La eficiencia del algoritmo está determinada en gran medida por la calidad de los datos de entrada: los límites de las figuras en la etapa de preprocesamiento de imágenes deben estar claramente definidos. Usar la transformada de Hough en imágenes ruidosas es difícil. Para imágenes ruidosas, se requiere un paso de procesamiento previo para reducir el ruido. En caso de que la imagen esté corrupta, moteada , como en el caso de una imagen de indicador de radar , la transformada Radon es preferible para la detección de líneas, ya que tiene un buen efecto de reducción de ruido en el apilamiento.

Véase también

Notas

  1. ↑ PDF Doc: Uso de la transformación de Hough para detectar líneas y curvas en imágenes (enlace no disponible) . Consultado el 23 de mayo de 2008. Archivado desde el original el 13 de marzo de 2012. 
  2. ↑ Transformación de Hough . Consultado el 2 de noviembre de 2014. Archivado desde el original el 2 de noviembre de 2014.

Enlaces