Encontrar rápidamente líneas aproximadas en conjuntos de puntos

12

En una clase particular de detectores, nuestros datos salen como pares de puntos en dos dimensiones, y queremos unir estos puntos en líneas.

Los datos son ruidosos y están agrupados en una dirección pero no en la otra. No podemos garantizar un golpe en cada contenedor, incluso cuando cada elemento del detector está funcionando, por lo que puede haber saltos.

Nuestra cadena de análisis actual se parece a

  1. Ajuste los golpes para la calibración de elementos detectores individuales
  2. Encuentra grupos
  3. Líneas de ajuste áspero a los grupos
  4. Conecte grupos en estructuras más largas como líneas
  5. ...

Esta pregunta se refiere al paso (3).

Hemos estado usando una transformación Hough para ese paso y funciona bien, pero a medida que intentamos escalar desde el banco de pruebas hasta la simulación de un proyecto a gran escala, se vuelve inaceptablemente lento.

Estoy buscando una manera más rápida.

Para aquellos a quienes les pueda interesar, el caso de uso real aquí es una cámara de proyección de tiempo de argón líquido

regression computer-vision pattern-recognition dmckee --- gatito ex moderador
fuente
1
También hicimos un método de transformación Hough recursivo para el seguimiento de rutas a través de cámaras proporcionales de cables múltiples en FermiLab. La tesis de Erik Kangas tiene todos los detalles. Creo que esta sigue siendo la mejor manera de hacerlo.
Matt Knepley
1
¿Querías decir "... pares en el punto ..." o "... pares de puntos ..." en la primera oración?
Bill Barth

Respuestas:

2

Hay una versión probabilística de la transformación de Hough (PHT) que es más rápida. Según lo descrito por Bradski y Kaehler en su libro OpenCV:

La idea es que el pico será lo suficientemente alto de todos modos, luego alcanzarlo solo una fracción de tiempo será suficiente para encontrarlo.

La biblioteca OpenCV presenta una implementación para el PHT.

Hay otras alternativas No es difícil crear una versión distribuida de la transformación Hough. Simplemente divida su conjunto de puntos en trozos más pequeños y use el marco MapReduce para resumir todos los acumuladores. Otra idea es realizar una gruesa versión de transformada de Hough utilizando un espacio de parámetros con baja resolución. Elija a sus mejores candidatos y ejecute una iteración más fina utilizando un espacio de parámetros que presente una resolución más alta. Tal vez esta es la idea detrás del FHT de Gandalf.

TH.
fuente
1
El PHT fue propuesto en: Matas, J. y Galambos, C. y Kittler, JV, Robust Detection of Lines Using the Progressive Probabilistic Hough Transform. CVIU 78 1, pp 119-137 (2000).
TH.
El curso entonces el procedimiento fino se puede generalizar a múltiples pasos, que es lo que hace Gandalf.
dmckee --- gatito ex moderador
Por cierto, en el tiempo transcurrido desde que hice esta pregunta, un colega ha agregado un módulo que utiliza la versión probabilística progresiva de la transformación a nuestro código. Esto vino con varios cambios asociados, por lo que es difícil caracterizar exactamente qué diferencia hizo, pero es parte de un paquete que aceleró considerablemente un par de pasos del análisis. Entonces, voy a aceptar esto como el consejo "ganador".
dmckee --- ex-gatito moderador
5

Yo colega ha encontrado el Transformación Fast Hough en la biblioteca de Gandalf , que parece muy prometedora pero que puede ser mucho trabajo integrar, así que estoy buscando otros enfoques.

La implementación de Gandalf es interesante: evalúan el espacio del acumulador de forma recursiva como si atravesara un árbol cuádruple o octogonal. Las regiones sin mucha densidad se desechan a medida que avanzan.

dmckee --- gatito ex moderador
fuente