Transformación de Hough
Utilizar la dirección del gradiente para reducir el número de votosEditar
Una mejora sugerida por O’Gorman y Clowes puede utilizarse para detectar líneas si se tiene en cuenta que el gradiente local de la intensidad de la imagen será necesariamente ortogonal al borde. Dado que la detección de bordes implica generalmente el cálculo de la magnitud del gradiente de intensidad, la dirección del gradiente se encuentra a menudo como un efecto secundario. Si un punto dado de coordenadas (x,y) se encuentra efectivamente en una línea, entonces la dirección local del gradiente da el parámetro θ correspondiente a dicha línea, y el parámetro r se obtiene inmediatamente. (Shapiro y Stockman, 305) La dirección del gradiente puede estimarse con una precisión de 20°, lo que acorta el trazado de la sinusoide de los 180° completos a aproximadamente 45°. Esto reduce el tiempo de cálculo y tiene el interesante efecto de reducir el número de votos inútiles, mejorando así la visibilidad de los picos correspondientes a líneas reales en la imagen.
Transformación de Hough basada en el núcleo (KHT)Editar
Fernandes y Oliveira sugirieron un esquema de votación mejorado para la transformada de Hough que permite una implementación de software para lograr un rendimiento en tiempo real incluso en imágenes relativamente grandes (por ejemplo, 1280×960). La transformada de Hough basada en Kernel utiliza el mismo ( r , θ ) {\displaystyle (r,\theta )}
parametrización propuesta por Duda y Hart pero opera sobre clusters de píxeles aproximadamente colineales. Para cada clúster, los votos se emiten utilizando un kernel elíptico-gaussiano orientado que modela la incertidumbre asociada a la línea que mejor se ajusta con respecto al clúster correspondiente. El enfoque no sólo mejora significativamente el rendimiento del esquema de votación, sino que también produce un acumulador mucho más limpio y hace que la transformación sea más robusta a la detección de líneas espurias.
Transformación de Hough basada en el núcleo para la detección de planos (3DKHT)Edit
Limberger y Oliveira sugirieron una técnica determinista para la detección de planos en nubes de puntos no organizadas cuyo coste es n log ( n ) {\displaystyle n\log(n)}
en el número de muestras, logrando un rendimiento en tiempo real para conjuntos de datos relativamente grandes (hasta 10 5 {\displaystyle 10^{5}}
puntos en una CPU de 3,4 GHz). Se basa en una estrategia de votación rápida de la transformada de Hough para regiones planas, inspirada en la transformada de Hough basada en Kernel (KHT). Esta transformada de Hough basada en el Kernel 3D (3DKHT) utiliza un algoritmo rápido y robusto para segmentar clusters de muestras aproximadamente coplanares, y emite votos para clusters individuales (en lugar de para muestras individuales) en un ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }
) acumulador esférico utilizando un kernel gaussiano trivariado. El enfoque es varios órdenes de magnitud más rápido que las técnicas existentes (no deterministas) para la detección de planos en nubes de puntos, como RHT y RANSAC, y escala mejor con el tamaño de los conjuntos de datos. Puede utilizarse en cualquier aplicación que requiera una detección rápida de características planas en grandes conjuntos de datos.
Transformación de Hough de curvas, y su generalización para formas analíticas y no analíticasEditar
Aunque la versión de la transformación descrita anteriormente sólo se aplica a la búsqueda de líneas rectas, una transformación similar se puede utilizar para encontrar cualquier forma que puede ser representada por un conjunto de parámetros. Un círculo, por ejemplo, puede transformarse en un conjunto de tres parámetros, que representan su centro y su radio, de modo que el espacio de Hough se convierte en tridimensional. También se pueden encontrar elipses y curvas arbitrarias de esta manera, así como cualquier forma fácilmente expresada como un conjunto de parámetros.
La generalización de la transformada de Hough para detectar formas analíticas en espacios que tienen cualquier dimensionalidad fue propuesta por Fernandes y Oliveira. A diferencia de otros enfoques basados en la transformada de Hough para formas analíticas, la técnica de Fernandes no depende de la forma que se quiere detectar ni del tipo de datos de entrada. La detección puede dirigirse a un tipo de forma analítica cambiando el modelo de geometría asumido en el que se han codificado los datos (por ejemplo, espacio euclidiano, espacio proyectivo, geometría conforme, etc.), mientras que la formulación propuesta permanece inalterada. Además, garantiza que las formas previstas se representan con el menor número posible de parámetros, y permite la detección concurrente de diferentes tipos de formas que se ajustan mejor a un conjunto de entradas con diferentes dimensionalidades y diferentes definiciones geométricas (por ejemplo, la detección concurrente de planos y esferas que se ajustan mejor a un conjunto de puntos, líneas rectas y círculos).
Para formas más complicadas en el plano (es decir, formas que no pueden representarse analíticamente en algún espacio 2D), se utiliza la transformada de Hough generalizada, que permite votar una característica para una posición, orientación y/o escala particular de la forma utilizando una tabla de búsqueda predefinida.La transformada de Hough acumula las contribuciones de todos los píxeles del borde detectado.
Proceso de detección de círculosEditar
Alterar el algoritmo para detectar formas circulares en lugar de líneas es relativamente sencillo.
- Primero, creamos el espacio acumulador, que está formado por una celda para cada píxel. Inicialmente cada celda se establece en 0.
- Por cada punto de borde (i, j) en la imagen, se incrementan todas las celdas que según la ecuación de un círculo ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}
podría ser el centro de un círculo. Estas celdas están representadas por la letra a {\displaystyle a}
en la ecuación.
- Por cada posible valor de a {\displaystyle a}
encontrado en el paso anterior, encuentre todos los posibles valores de b {\displaystyle b}
que satisfagan la ecuación.
- Busque los máximos locales en el espacio del acumulador. Estas celdas representan círculos que fueron detectados por el algoritmo.
Si no conocemos de antemano el radio del círculo que intentamos localizar, podemos utilizar un espacio acumulador tridimensional para buscar círculos con un radio arbitrario. Naturalmente, esto es más caro computacionalmente.
Este método también puede detectar círculos que están parcialmente fuera del espacio acumulador, siempre y cuando una parte suficiente del área del círculo siga estando presente dentro de él.
Detección de objetos 3D (Planos y cilindros)Editar
La transformada de Hough también se puede utilizar para la detección de objetos 3D en datos de rango o nubes de puntos 3D. La extensión de la transformada de Hough clásica para la detección de planos es bastante sencilla. Un plano se representa por su ecuación explícita z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}
para lo cual podemos utilizar un espacio de Hough 3D correspondiente a a x {\displaystyle a_{x}}
, a y {{displaystyle a_{y}}
y d {\displaystyle d}
. Esta extensión adolece de los mismos problemas que su homóloga en 2D, es decir, los planos cercanos a la horizontal pueden detectarse de forma fiable, mientras que el rendimiento se deteriora a medida que la dirección del plano se vuelve vertical (grandes valores de a x {displaystyle a_{x}}
y a y {\displaystyle a_{y}}
amplifican el ruido de los datos). Esta formulación del plano se ha utilizado para la detección de planos en las nubes de puntos adquiridas a partir del escaneo láser aéreo y funciona muy bien porque en ese dominio todos los planos son casi horizontales.
Para la detección generalizada de planos utilizando la transformada de Hough, el plano puede ser parametrizado por su vector normal n
(usando coordenadas esféricas) y su distancia al origen ρ {\displaystyle \rho }
dando como resultado un espacio de Hough tridimensional. Esto hace que cada punto de los datos de entrada vote por una superficie sinusoidal en el espacio de Hough. La intersección de estas superficies sinusoidales indica la presencia de un plano. Un enfoque más general para más de 3 dimensiones requiere una heurística de búsqueda para seguir siendo factible.
La transformada de Hough también se ha utilizado para encontrar objetos cilíndricos en nubes de puntos utilizando un enfoque de dos pasos. El primer paso encuentra la orientación del cilindro y el segundo paso encuentra la posición y el radio.
Usando características ponderadasEditar
Un detalle de variación común. Es decir, encontrar los bins con el mayor recuento en una etapa puede utilizarse para restringir el rango de valores buscados en la siguiente.
Espacio de parámetros cuidadosamente elegidoEditar
Un espacio de parámetros de alta dimensión para la transformada de Hough no sólo es lento, sino que si se implementa sin previsión puede sobrepasar fácilmente la memoria disponible. Incluso si el entorno de programación permite la asignación de una matriz más grande que el espacio de memoria disponible a través de la memoria virtual, el número de cambios de página necesarios para ello será muy exigente porque la matriz de acumuladores se utiliza de forma aleatoria, rara vez se detiene en la memoria contigua, ya que salta de índice a índice.
Considere la tarea de encontrar elipses en una imagen de 800×600. Asumiendo que los radios de las elipses están orientados a lo largo de los ejes principales, el espacio de parámetros es de cuatro dimensiones. (x,y) define el centro de la elipse, y a y b denotan los dos radios. Si se permite que el centro esté en cualquier lugar de la imagen, se añade la restricción 0<x<800 y 0<y<600. Si a los radios se les dan los mismos valores que a las restricciones, lo que queda es una matriz de acumuladores escasamente llena de más de 230 mil millones de valores.
Es poco probable que un programa así concebido pueda asignar suficiente memoria. Esto no significa que el problema no pueda resolverse, sino sólo que hay que encontrar nuevas formas de restringir el tamaño de la matriz de acumuladores que lo hagan factible. Por ejemplo:
- Si es razonable suponer que las elipses están cada una contenida por completo dentro de la imagen, se puede reducir el rango de los radios. Lo más grande que pueden ser los radios es si el centro de la elipse está en el centro de la imagen, permitiendo que los bordes de la elipse se extiendan hasta los bordes. En este caso extremo, los radios sólo pueden ser cada uno la mitad de la magnitud del tamaño de la imagen orientada en la misma dirección. Reducir el rango de a y b de esta manera reduce la matriz de acumuladores a 57 mil millones de valores.
- Cambiar precisión por espacio en la estimación de la transformada de Hough acumula contribuciones de todos los píxeles del borde detectado. La transformada de Hough acumula las contribuciones de todos los píxeles del borde detectado. l centro: Si se predice que el centro está desviado por 3 tanto en el eje x como en el eje y, esto reduce el tamaño de la matriz de acumuladores a unos 6.000 millones de valores.
- Precisión de cambio por espacio en la estimación de los radios: Si los radios se estiman en 5, el tamaño de la matriz de acumuladores se reduce en unos 256 millones de valores.
- Recortar la imagen en las zonas de interés. Esto depende de la imagen, y por lo tanto es impredecible, pero imagine un caso en el que todos los bordes de interés en una imagen están en el cuadrante superior izquierdo de esa imagen. La matriz de acumuladores puede reducirse aún más en este caso restringiendo los 4 parámetros por un factor de 2, para un factor de reducción total de 16.
Aplicando sólo las tres primeras de estas restricciones al ejemplo mencionado, el tamaño de la matriz de acumuladores se reduce en casi un factor de 1000, llevándolo a un tamaño que es mucho más probable que quepa en la memoria de un ordenador moderno.
Algoritmo eficiente de detección de elipsesEditar
Yonghong Xie y Qiang Ji dan una forma eficiente de implementar la transformada de Hough para la detección de elipses superando los problemas de memoria. Como se discute en el algoritmo (en la página 2 del artículo), este enfoque utiliza sólo un acumulador unidimensional (para el eje menor) con el fin de detectar elipses en la imagen. La complejidad es O(N3) en el número de puntos distintos de cero en la imagen.
Leave a Reply