Detección de círculos (elipses) en nube de puntos 2D

14

Dado un conjunto de puntos (2D), es decir, del punto de enturbiamiento (PC), la pregunta es sobre una robust, accuratey computing-friendlymétodo para encontrar círculos (o elipses en versión avanzada).

La idea intuitiva es utilizar Brute-Force Search en todos los puntos posibles (como centro) {infinito!} Y radios (¡nuevamente infinito!). Esto es extremadamente extremadamente lento e ineficiente.

Como se demuestra a continuación, cada círculo ajustado se clasificará en función del número de puntos ( nn) colocados en la circunferencia del círculo en una distancia menor que un umbral ( t). Entonces hay derrque presentar una distancia promedio.

En forma avanzada, las elipses son de interés para ajustarse.

¿Alguna idea, lluvia de ideas, experiencias, comentarios? ingrese la descripción de la imagen aquí

Desarrollador
fuente
Buena pregunta. ¿Qué programa usaste para generar ese diagrama?
Jason R
@JasonR Como siempre, Python + MatPlotLib .
Desarrollador

Respuestas:

14

Las mejores ideas que intentan resolver este problema exactamente son las transformaciones de Hough .

Básicamente, la señal en el espacio de espacio será r, x, ycoordinada. Aquí r representa el radio y x,yrepresenta el centro. Todos los puntos pueden pertenecer a uno o muchos círculos. Entonces, en el plano de Hough, recorra todos los círculos posibles a los que podría pertenecer este punto y simplemente haga un +1. Esto no es una búsqueda, solo una colección.

Ahora, si existe un círculo real, se sumarán tantos puntos y la puntuación de tal r, x, yserá mucho mayor que todos los demás. Seleccionar ese punto le permitirá elegir los círculos correctos.

Aquí hay un artículo clásico en 1971 (¡antes de que yo naciera!) Que inventó este concepto.

  1. USO DE LA TRASFORMACIÓN DE HOUGH PARA DETECTAR LÍNEAS Y CURVAS EN LAS IMÁGENES Por: Richard O. Duda, Peter E. Hart Informe técnico Cente de inteligencia artificial, abril de 1971.

Para el tutorial, sugeriría referencias a continuación:

  1. HIPR2 -Enlace
  2. Amos Storkey
  3. Referencia IDL

Específicamente para la detección de círculos, puede consultar esto a continuación:

  1. Cabaña AI
  2. Informe técnico de Chicago Univ.
  3. Notas de clase del Instituto Rochester

Estos métodos son muy eficientes y muy amigables con la computadora.

Dipan Mehta
fuente
1
Puedo responder por los artículos de AI Shack, realmente ayudan a asimilar las matemáticas más rigurosas que leerás en otros lugares.
Ivo Flipse
1
Buena respuesta. Ya estoy familiarizado con Hough Transform (HT). El que usé fue para la detección de líneas. Hubo un poco de dificultad para determinar los segmentos de línea. Se recomendó utilizar la Transformación probabilística de la tos (PHT). No tuve una idea clara sobre la extensión. Pensé que podría ser muy complejo para los círculos o aparecer otras dificultades. En cuanto a mis experiencias, HT es bueno pero no perfecto. También es mi preocupación cómo extender HT a 3D. Intentaré revisar sus enlaces proporcionados. Su respuesta es bastante buena para ser candidato como respuesta.
Desarrollador
AI Shack y Tech Report de los enlaces de Chicaco están muertos
Mehdi