Transformación de Hough generalizada

La transformada de Hough generalizada ( GHT ), introducida por Dana H. Ballard en 1981, es una modificación de la transformada de Hough que utiliza el principio de coincidencia de plantillas . ^{[ 1 ]} La transformada de Hough se desarrolló inicialmente para detectar formas definidas analíticamente (por ejemplo, línea , círculo , elipse , etc.). En estos casos, conocemos la forma y nuestro objetivo es determinar su ubicación y orientación en la imagen. Esta modificación permite utilizar la transformada de Hough para detectar un objeto arbitrario descrito con su modelo.

El problema de encontrar un objeto (descrito mediante un modelo) en una imagen se resuelve determinando la posición del modelo en la imagen. Mediante la transformada de Hough generalizada, este problema se transforma en el de encontrar el parámetro de la transformación que mapea el modelo en la imagen. Conociendo el valor de dicho parámetro, se puede determinar la posición del modelo en la imagen.

La implementación original de la GHT utilizaba información de borde para definir una correspondencia entre la orientación de un punto de borde y un punto de referencia de la forma. En el caso de una imagen binaria, donde los píxeles pueden ser blancos o negros, cada píxel negro de la imagen puede ser un píxel negro del patrón deseado, creando así un conjunto de puntos de referencia en el espacio de Hough. Cada píxel de la imagen vota por sus puntos de referencia correspondientes. Los puntos máximos del espacio de Hough indican posibles puntos de referencia del patrón en la imagen. Este máximo se puede encontrar explorando el espacio de Hough o resolviendo un conjunto relajado de ecuaciones , cada una de las cuales corresponde a un píxel negro. ^{[ 2 ]}

Merlin y Farber ^{[ 3 ]} mostraron cómo usar un algoritmo de Hough cuando las curvas deseadas no podían describirse analíticamente. Fue un precursor del algoritmo de Ballard, que se limitaba a la traslación y no tenía en cuenta la rotación ni los cambios de escala . ^{[ 4 ]}

El algoritmo Merlin-Farber no es práctico para datos de imágenes reales, ya que en una imagen con muchos píxeles de borde, encuentra muchos falsos positivos debido a la disposición repetitiva de los píxeles.

Para generalizar el algoritmo de Hough a curvas no analíticas, Ballard define los siguientes parámetros para una forma generalizada: a={y,s,θ} donde y es un origen de referencia para la forma, θ es su orientación y s = (s _x , s _y ) describe dos factores de escala ortogonales . Un algoritmo puede calcular el mejor conjunto de parámetros para una forma dada a partir de datos de píxeles de borde. Estos parámetros no tienen el mismo estatus. La ubicación del origen de referencia, y , se describe en términos de una tabla plantilla llamada tabla R de posibles orientaciones de píxeles de borde. El cálculo de los parámetros adicionales s y θ se realiza mediante transformaciones directas a esta tabla. La generalización clave a formas arbitrarias es el uso de información direccional. Dada cualquier forma y un punto de referencia fijo en ella, en lugar de una curva paramétrica, la información proporcionada por los píxeles de borde se almacena en forma de tabla R en la etapa de transformación. Para cada punto de borde en la imagen de prueba, se consultan las propiedades del punto en la tabla R, se recupera el punto de referencia y se incrementa la celda correspondiente en la matriz acumuladora. La celda con el mayor número de votos en la matriz acumuladora puede ser un posible punto de referencia fijo del objeto en la imagen de prueba.

Construyendo la tabla R

Elija un punto de referencia y para la forma (normalmente dentro de la forma). Para cada punto límite x , calcule ɸ(x) , la dirección del gradiente y r = y – x como se muestra en la imagen. Almacene r como una función de ɸ . Observe que cada índice de ɸ puede tener muchos valores de r . Se pueden almacenar las diferencias de coordenadas entre la referencia fija y el punto de borde ((x _c – x _ij ), (y _c – y _ij )) o como la distancia radial y el ángulo entre ellos (r _ij , α _ij ) . Habiendo hecho esto para cada punto, la tabla R representará completamente el objeto plantilla. Además, como la fase de generación es invertible, podemos usarla para localizar ocurrencias de objetos en otros lugares de la imagen.

La implementación utiliza las siguientes ecuaciones: ^{[ 6 ]}

${\displaystyle x=x_{c}+x'\ \ o\ \ x_{c}=xx'}$

${\displaystyle y=y_{c}+y'\ \ o\ \ y_{c}=yy'}$

${\displaystyle \cos(\pi -\alpha )=x'/r\ \ {\text{o}}\ \ x'=r\cos(\pi -\alpha )=-r\cos(\alpha )}$

${\displaystyle \sin(\pi -\alpha )=y'/r\ \ {\text{o}}\ \ y'=r\sin(\pi -\alpha )=r\sin(\alpha )}$

Combinando las ecuaciones anteriores tenemos:

${\displaystyle x_{c}=x+r\cos(\alpha )}$

${\displaystyle y_{c}=y+r\sin(\alpha)}$

Construcción de la tabla R

(0) Convierta la imagen de la forma de muestra en una imagen de bordes utilizando cualquier algoritmo de detección de bordes como el detector de bordes de Canny.

(1) Elija un punto de referencia (por ejemplo, (x _c , y _c ) )

(2) Dibuje una línea desde el punto de referencia hasta el límite.

(3) Calcular ɸ

(4) Almacene el punto de referencia (x _c , y _c ) como una función de ɸ en la tabla R(ɸ) .

Detección:

(0) Convierta la imagen de la forma de muestra en una imagen de borde utilizando cualquier algoritmo de detección de bordes como el detector de bordes de Canny .

(1) Inicializar la tabla del acumulador: A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ]

(2) Para cada punto de borde (x, y)

(2.1) Utilizando el ángulo de gradiente ɸ , recupere de la tabla R todos los valores (α, r) indexados bajo ɸ .

(2.2) Para cada (α,r) , calcule los puntos de referencia candidatos:

x _c = x + r  cos(α)

y _c = y + r  sin(α)

(2.3) Aumentar los contadores (votación):

++A([[x _c ]][y _c ])

(3) Las posibles ubicaciones del contorno del objeto vienen dadas por los máximos locales en A[x _c ][y _c ] .

Si A[x _c ][y _c ] > T , entonces el contorno del objeto está ubicado en (x _c , y _c ).

Caso general:

Supongamos que el objeto ha sufrido una rotación Θ y un escalado uniforme s :

(x ′ , y ′ ) → (x″, y″)

x″ = (x ′ cos(Θ) – y ′ sin(Θ))s

y″ = (x ′ sin(Θ) + y ′ cos(Θ))s

Sustituyendo x ′ por x″ e y ′ por y″:

x _c = x – x″ o x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y – y″ o y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

(1) Inicializar la tabla del acumulador: A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ][q _min . . . q _max ][s _min . . . s _max ]

(2) Para cada punto de borde (x, y)

(2.1) Utilizando su ángulo de gradiente ɸ , recupere todos los valores (α, r) de la tabla R.

(2.2) Para cada (α, r) , calcule los puntos de referencia candidatos:

x ′ = r  cos(α)

y ′ = r  sin(α)

para( Θ = Θ _mín ; Θ ≤ Θ _máx ; Θ++ )

para( s = s _min ; s ≤ s _max ; s++ )

x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

++(A[x _c ][y _c ][Θ][s])

(3) Las posibles ubicaciones del contorno del objeto vienen dadas por los máximos locales en A[x _c ][y _c ][Θ][s]

Si A[x _c ][y _c ][Θ][s] > T , entonces el contorno del objeto está ubicado en (x _c , y _c ) , ha sufrido una rotación Θ , y ha sido escalado por s .

Ballard sugirió utilizar información de orientación del borde para disminuir el costo computacional. Se han propuesto muchas técnicas GHT eficientes, como la SC-GHT (que utiliza la pendiente y la curvatura como propiedades locales). ^{[ 7 ]} Davis y Yam ^{[ 8 ]} también propusieron una extensión del trabajo de Merlin para la coincidencia invariante de orientación y escala, que complementa el trabajo de Ballard, pero no incluye la utilización por parte de Ballard de información de pendiente del borde y estructuras compuestas.

• Hough transforma
• Transformación de Hough aleatoria
• El radón transforma
• Coincidencia de plantillas
• Esquema del reconocimiento de objetos

• Implementación de la transformada de Hough generalizada en OpenCV : http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html
• Tutorial e implementación de transformadas de Hough generalizadas http://www.itriacasa.it/generalized-hough-transform/default.html Archivado el 30/01/2016 en Wayback Machine
• Implementación práctica de la transformada de Hough generalizada http://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html
• Implementación en FPGA de transformadas de Hough generalizadas, Biblioteca Digital IEEE https://ieeexplore.ieee.org/document/5382047/
• Implementación en MATLAB de la transformada de Hough generalizada http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform