La transformada de Hough es una técnica de extracción de características utilizada en análisis de imágenes, visión por computadora, reconocimiento de patrones y procesamiento digital de imágenes. Su propósito es encontrar instancias imperfectas de objetos dentro de una cierta clase de formas mediante un procedimiento de votación. Este procedimiento de votación se lleva a cabo en un espacio de parámetros, del cual se obtienen candidatos a objetos como máximos locales en un espacio acumulador construido explícitamente por el algoritmo. Matemáticamente, es la transformada de Radon en el plano, conocida desde al menos 1917, pero la transformada de Hough se refiere específicamente a su uso en análisis de imágenes.
La transformada de Hough clásica se ocupaba de identificar líneas en una imagen, pero desde entonces se ha extendido a identificar posiciones de formas arbitrarias, más comúnmente círculos o elipses. La transformada tal como se usa universalmente hoy en día fue inventada por Richard Duda y Peter Hart en 1972, quienes la llamaron "transformada de Hough generalizada" en referencia a la patente relacionada de Paul Hough de 1962. Fue popularizada en la comunidad de visión por computadora por Dana H. Ballard a través de un artículo de revista de 1981 titulado "Generalizing the Hough transform to detect arbitrary shapes."
Historia
La transformada de Hough fue inventada inicialmente para el análisis automático de fotografías de cámaras de burbujas por Paul Hough en 1959. Fue patentada como patente estadounidense 3,069,654 en 1962 y asignada a la Comisión de Energía Atómica de los Estados Unidos bajo el nombre "Method and Means for Recognizing Complex Patterns." Esta patente utilizaba una parametrización pendiente-intersección para líneas rectas, lo que conducía de manera incómoda a un espacio de transformación no acotado, ya que la pendiente puede llegar a infinito.
La parametrización rho-theta utilizada universalmente hoy en día fue descrita por primera vez en un artículo de 1972 de Richard Duda y Peter Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," publicado en Communications of the ACM. Esta parametrización ya era estándar para la transformada de Radon desde al menos la década de 1930. Frank O'Gorman y M.B. Clowes publicaron una variación en 1976 en IEEE Transactions on Computers, titulada "Finding Picture Edges Through Collinearity of Feature Points." La historia de cómo se inventó la forma moderna se detalla en el artículo de Peter Hart de 2009 "How the Hough Transform was Invented" en IEEE Signal Processing Magazine.
Teoría
En el análisis automatizado de imágenes digitales, a menudo surge un subproblema de detectar formas simples, como líneas rectas, círculos o elipses. Un detector de bordes puede usarse como etapa de preprocesamiento para obtener puntos de imagen en la curva deseada. Sin embargo, debido a imperfecciones en los datos de imagen o en el detector de bordes, puede haber puntos faltantes o desviaciones espaciales entre la forma ideal y los puntos de borde ruidosos. La transformada de Hough aborda esto realizando un procedimiento de votación explícito sobre un conjunto de objetos de imagen parametrizados, lo que hace posible agrupar puntos de borde en candidatos a objetos.
Detección de líneas
El caso más simple es la detección de líneas rectas. En general, una línea y = mx + b puede representarse como un punto (b, m) en el espacio de parámetros, pero las líneas verticales plantean un problema debido a valores de pendiente no acotados. Duda y Hart propusieron usar la forma normal de Hesse: r = x cos(theta) + y sin(theta), donde r es la distancia desde el origen al punto más cercano en la línea, y theta es el ángulo entre el eje x y la línea que conecta el origen con ese punto más cercano. Cada vector en la línea es perpendicular al segmento de línea de longitud r desde el origen. El punto de intersección está en P0 = (r cos(theta), r sin(theta)). Para cualquier punto P en la línea, el vector P - P0 debe ser ortogonal a P0, lo que impone (P - P0) punto P0 = 0, que se simplifica a r(x cos(theta) + y sin(theta)) = r^2(cos^2(theta) + sin^2(theta)).
Algoritmo y procedimiento de votación
En la práctica, la transformada de Hough discretiza el espacio de parámetros en un arreglo acumulador. Para cada punto de borde en la imagen, el algoritmo calcula todos los valores posibles de parámetros (por ejemplo, r y theta para líneas) que podrían corresponder a una forma que pase por ese punto, e incrementa las celdas acumuladoras correspondientes. Después de procesar todos los puntos, los máximos locales en el acumulador indican candidatos probables a formas. Este procedimiento de votación es robusto al ruido y a datos faltantes, ya que no requiere que todos los puntos en una forma estén perfectamente alineados.
Extensiones y aplicaciones
La transformada de Hough generalizada, introducida por Dana Ballard en 1981, extiende la técnica a formas arbitrarias mediante el uso de un punto de referencia y una tabla de orientaciones de bordes. Esto permite la detección de formas complejas más allá de líneas, círculos y elipses. La transformada se ha aplicado ampliamente en campos como la conducción autónoma, la imagen médica y la inspección industrial. En sistemas de Computer vision, a menudo se combina con algoritmos de detección de bordes para identificar objetos en tuberías de procesamiento de imágenes digitales. Su fundamento matemático en la transformada de Radon la conecta con técnicas más amplias de análisis de imágenes utilizadas en aplicaciones de Machine learning y Artificial intelligence.
Limitaciones y variantes
Una limitación de la transformada de Hough clásica es su costo computacional, especialmente para espacios de parámetros de alta dimensión. Se han desarrollado variantes como la transformada de Hough probabilística y la transformada de Hough circular para mejorar la eficiencia. La versión probabilística muestrea un subconjunto de puntos de borde para reducir el cálculo, mientras que la transformada circular utiliza un espacio de parámetros tridimensional (centro x, centro y, radio). Estas variantes se implementan comúnmente en bibliotecas como opencv y se utilizan en sistemas en tiempo real, incluidos aquellos en vehículos autónomos y Robotics.
Véase también
- radon-transform
- edge-detection
- Computer vision
- image-processing