La transformada de Hough es una técnica de reconocimiento de patrones inventada en 1959 por Paul Hough , objeto de una patente, y utilizada en el procesamiento de imágenes digitales .
La aplicación más simple permite detectar las líneas presentes en una imagen, pero se pueden realizar modificaciones a esta técnica para detectar otras formas geométricas: esta es la transformada de Hough generalizada desarrollada por Richard Duda y Peter Hart en 1972.
El problema que se plantea es el de buscar y detectar líneas que posiblemente estarían presentes en una imagen analizada a pesar de las imperfecciones de la imagen: puntos faltantes (la línea puede quedar parcialmente enmascarada por un objeto), ruido. La transformada de Hough consiste en representar cada punto de borde detectado en un espacio de parámetros bidimensional:
la transformada de Hough de un punto de la imagen analizada es la curva del espacio de parámetros correspondiente al conjunto de líneas rectas que pasan por este punto.
Si los puntos son colineales, todas las curvas del espacio de parámetros se intersecan en el punto que representa la línea en cuestión.
Debido a las imperfecciones de la imagen, los puntos detectados no están perfectamente alineados y por tanto las curvas no son perfectamente concurrentes. Por tanto, el método consiste en discretizar el espacio de los parámetros, cortarlo en pequeños rectángulos y contar para cada rectángulo el número de curvas que lo atraviesan. Se construye así una llamada matriz de acumulación, correspondiendo los máximos locales de esta matriz a las líneas probables.
Por tanto, el algoritmo tiene tres etapas:
Inicialmente, Hough caracterizó las líneas por su pendiente y su intersección con el eje y . La desventaja de este enfoque es que la pendiente tiende al infinito cuando la línea tiende a ser vertical. En 1972, Duda y Hart propusieron una parametrización por coordenadas polares (ρ, θ) que desde entonces se ha utilizado universalmente.
Una línea (D) se puede caracterizar por parámetros polares (ρ, θ):
Las coordenadas ( x , y ) de los puntos de esta recta verifican la llamada ecuación "normal":
ρ = x ⋅ cos (θ) + y ⋅ sin (θ)En primer lugar, se supone que si hay líneas o segmentos rectos en una imagen, serán parte de los contornos presentes en la imagen. Por lo tanto, el primer paso es identificar todos los puntos de contorno de esta imagen, por ejemplo, utilizando técnicas para medir gradientes locales entre los valores de los píxeles alrededor de cada punto de la imagen, como el filtro Canny . Los puntos de la imagen que presentan los gradientes más altos en su vecindario, ya sea globalmente para la imagen (umbral fijo) o en relación con los gradientes generalmente presentes en un vecindario más amplio alrededor del punto (umbral dinámico), son los que tienen más probabilidades de pertenecer a los contornos de esta imagen.
Cada uno de los puntos de los contornos así identificados ( x , y ) permitirá entonces una proyección en un plano (el plano transformado) de las coordenadas polares de todas las líneas que pasan por este punto. Por tanto, las ecuaciones de las rectas que pasan por cada uno de estos puntos ( x , y ) están representadas por un par (ρ, θ) que satisface
ρ = x ⋅ cos (θ) + y ⋅ sin (θ)En el punto ( x , y ) del contorno, por lo tanto, hacemos corresponder una curva ρ = ƒ (θ) donde θ toma todos los valores posibles de 0 a 2 π rad (0 a 360 ° ), con
ƒ (θ) = x ⋅ cos (θ) + y ⋅ sin (θ).Esta curva es una onda sinusoidal. En la práctica, variamos θ de 0 a π rad (0 a 180 ° ) y consideramos un radio algebraico (positivo o negativo). El parámetro ρ tomará valores entre –R y + R donde R es la diagonal grande de la imagen: R = √ l 2 + h 2 , siendo l el ancho de la imagen y h su altura.
Cuando las curvas ρ (θ) correspondientes a dos puntos se encuentran, el punto de intersección caracteriza la línea que pasa por los dos puntos.
Por tanto, en el plano (θ, ρ), asociamos a cada punto una densidad correspondiente al número de curvas que lo atraviesan. Cuanto mayor sea la densidad, más puntos de contorno se ubicarán en esta línea. Por lo tanto, lo más probable es que la línea sea un segmento de la imagen.
En la práctica, el espacio de Hough transformado estará representado por una imagen cuyas abscisas son los ángulos θ, cuyas ordenadas son los valores de ρ y cuya intensidad en cualquier punto (θ, ρ) es el número de ocurrencias de (θ, ρ ) de la imagen original. Aquí no se asume la continuidad de las líneas rectas o segmentos rectos de la imagen inicial, lo que hace que la transformación sea robusta a la ausencia de puntos: enmascaramiento parcial de las líneas y al ruido en la imagen.
Los valores de θ se pueden discretizar, por ejemplo, en grados (según la precisión deseada), y los valores de ρ en píxeles que representan la distancia (siempre menor en valor absoluto que el diámetro de la imagen inicial), la frecuencia estando limitado por el número de puntos seleccionados en los contornos de la imagen inicial.
Por lo tanto, el algoritmo está en pseudocódigo:
Importe : I % image matricielle J ← contours de I % p.ex. filtre de Canny Définit : δ % pas de discrétisation 1. M ← 0 % initialisation de la matrice d'accumulation 2. pour chaque pixel (x, y) de J faire 3. pour θ allant de 0 à 180 avec le pas δ 4. ρ ← x*cos(θ) + y*sin(θ) 5. M(ρ, θ) ← M(ρ, θ) + 1 6. fin de boucle 7. fin de boucle Détection des pics de M
En la transformada de Hough, también conocida como la transformada estándar de Hough o SHT, cada línea es un vector de coordenadas paramétricas:
Transformando todas las líneas posibles que pasan por un punto, es decir, calculando el valor de ρ para cada θ, obtenemos una única sinusoide llamada "Hough space". Si las curvas asociadas a dos puntos se cruzan, el lugar donde se cruzan en el espacio de Hough corresponde a los parámetros de una línea que conecta estos dos puntos.
La detección de contornos implica determinar el gradiente de contraste de la imagen. De hecho, la dirección de este gradiente es perpendicular a la dirección del contorno. En lugar de trazar las sinusoides para θ que varían de 0 a 180 ° , podemos restringirnos a un rango alrededor de las orientaciones así encontradas. Este método fue propuesto por O'Gorman y Clowes en 1976 y se llama GHT ( transformada de Hough basada en gradientes ).
Fernandes y Oliveira han propuesto una mejora para acelerar el procesamiento hasta el punto de poder procesar imágenes hasta 1280 × 960 píxeles en tiempo real. El método es como sigue:
Este método se llama KHT ( transformación de Hough basada en kernel ).
El método se puede aplicar a cualquier curva representada por una ecuación cartesiana o paramétrica.
El método de detección de círculos también se llama HCT ( transformación de círculo de Hough ) .
En este método, un círculo se describe mediante su ecuación cartesiana :
( x - a ) 2 + ( y - b ) 2 = r 2o
En el espacio ( a , b , r ), un círculo se caracteriza por un punto. El conjunto de círculos que pasan por un punto dado M ( x , y ) forma un cono de vértice ( a = x , b = y , r = 0) y de eje r . Un "buen candidato" es la intersección de varios conos.
Si se conoce el radio del círculo buscado, entonces podemos colocarnos en el plano ( a , b ). En este plano, el conjunto de círculos que pasan por M se describe mediante el círculo con centro ( a = x , b = y ) y radio r . Por tanto, un buen candidato está en la intersección de varios círculos. Construimos una matriz de acumulación A: cada elemento A i, j de la matriz contiene el número de círculos que pasan por el punto, o bien por un cuadrado de varios píxeles, correspondiente a este elemento.
Si se desconoce el radio, el método de búsqueda consiste en construir una hipermatriz de acumulación de la cual cada celda A i, j, k corresponde a un cubo de espacio ( a , b , r ), escaneando todos los rayos posibles de 1 píxel hasta el tamaño de la imagen.
Aplicaciones
Un círculo es la proyección de un objeto esférico sobre un plano, o de una sección circular (cilindro, cono, toroide) siempre que el eje del objeto sea perpendicular al plano de proyección (de lo contrario, la proyección es una elipse). El reconocimiento de formas circulares se puede utilizar para detectar cabezas, y por lo tanto personas, en una fotografía o una imagen de videovigilancia. También se puede utilizar para detectar aneurismas en un angiograma .
Una elipse se caracteriza por cinco parámetros, normalmente:
Esto significa que la implementación directa de la transformada de Hough se realiza en un espacio de cinco dimensiones que implica un tiempo de cálculo significativo y requiere una gran capacidad de memoria. Se han propuesto varios algoritmos para reducir el número de parámetros necesarios.
En 1978, Tsuji y Matsumoto propusieron usar el gradiente de contraste para determinar la perpendicular a la tangente. Considerando los puntos que tienen tangentes paralelas, determinan la posición de los centros de las elipses. Luego, utilizan las propiedades geométricas para separar las elipses de otros objetos con la misma propiedad, finalmente, los parámetros de las elipses se determinan por el método de mínimos cuadrados
En 1994, Yin y Chen propusieron seleccionar grupos de cinco puntos, un número suficiente para determinar una elipse. Para ello, los puntos se clasifican en subimágenes. La imagen de los puntos de contorno detectados se llama F. El algoritmo escanea de arriba a abajo por una línea horizontal y toma los puntos ubicados en esta línea. Considera los puntos medios de los segmentos así definidos, estos puntos medios de los segmentos forman una imagen llamada G. Para una elipse dada, los puntos medios de los segmentos se encuentran en la misma línea recta, dependiendo la línea de la inclinación del eje mayor; esta línea se llama "eje de simetría" porque los puntos son simétricos no por reflexión sino por una similitud de razón 1. Estas líneas están determinadas por la transformada clásica de Hough de G. Luego, el algoritmo crea subimágenes de F formadas por la puntos que generan una línea dada de G; así, los puntos de F se clasifican según su posible pertenencia a una elipse que tiene un eje de simetría dado. Luego, cada subimagen se procesa por separado. En una subimagen, para cada par de puntos (A, B), el algoritmo determina cinco puntos:
Los parámetros de la elipse se determinan a partir de estos cinco puntos y la matriz de acumulación se actualiza para este conjunto de parámetros. los límites de este método son:
En 1995, Ho y Chen crearon dos subespacios de manera similar a Yin y Chen. La primera consiste en considerar los pares de puntos de contorno ubicados en una misma línea horizontal y en tomar los puntos medios de los segmentos así formados. El segundo subespacio se construye de la misma manera pero considerando los pares de puntos ubicados en la misma vertical. Luego, el algoritmo realiza una detección de las líneas formadas por estos puntos medios con la transformada de Hough clásica, la intersección de estas líneas da los centros de las elipses. Luego determinan los tres parámetros restantes (determinación del eje mayor y menor).
Un método similar consiste en considerar pares de puntos: el gradiente da acceso a la tangente, si las tangentes no son paralelas, se cruzan en un punto T. La línea que conecta este punto con la mitad del segmento pasa por el cent de la elipse. .
En 2002, Xie y Ji propusieron un método que realizaba una búsqueda en un solo parámetro, la longitud del eje semi-menor. Toman un par de puntos A 1 ( x 1 , y 1 ) y A 2 ( x 2 , y 2 ) lo suficientemente separados y asumen que están ubicados en el eje mayor de una elipse. Con esta suposición, el centro de la elipse está necesariamente en el medio O de [A 1 A 2 ], la longitud del eje mayor es 2 a = A 1 A 2 y la inclinación del eje mayor es θ = arctan (( y 2 - y 1 ) / ( x 2 - x 1 )). Luego, consideran cada punto del contorno M: si está lo suficientemente cerca de O para poder estar en una elipse con un eje mayor [A 1 A 2 ], entonces el punto M se usa para calcular el eje semi-menor b de la elipse. Es este parámetro b el que se utiliza para construir la matriz de acumulación. Si la matriz contiene un pico lo suficientemente grande como para caracterizar una elipse, entonces se retiene la elipse. Luego, el algoritmo pasa a otro par (A 1 , A 2 ). El algoritmo, por tanto, consiste en realizar una transformada de Hough para cada uno de los pares de puntos suficientemente distantes, pero esta transformada solo tiene lugar en un único parámetro. Por otro lado, la imagen debe mostrar los extremos del eje mayor para que se detecte una elipse.
Aplicaciones
Una elipse es la proyección de una sección circular sobre un plano. La detección de elipse permite, por tanto, la detección de objetos cilíndricos o tóricos como las pupilas de los ojos, las señales de tráfico y las ruedas de los vehículos.