Detección de líneas en una nube de puntos.

7

¿Cuáles son las mejores soluciones para detectar líneas en una nube de puntos? Comparación realizada con y entre Hough Transform , Radon Transform , RANSAC (ver wikipedia) y Brute-Force Search (ver wikipedia).
¿Cuál es el más robusto contra la dispersión de puntos en la nube de puntos?
Nota:
1- La pregunta es sobre la nube de puntos 3D, no la imagen.
2- Los puntos en la nube de puntos se dispersan al azar (ubicaciones completamente dispersas).
3- No hay información sobre el objeto (línea) que se está explorando en términos de orientación, tamaño, etc. preferidos.
4- Se debe considerar una tolerancia alrededor de la línea candidata.
Actualizaciones:
Según mis experimentos: RANSAC podría perder fácilmente algunas líneas. Es bueno para la detección rápida de bordes, sin embargo, la complejidad de la dispersión de puntos podría producir salidas no deseadas. Hough y Radon son muy similares y no tuve la oportunidad de probar la nube de puntos 3D, sin embargo, funcionan bien en casos 2D. Hay una dificultad en la extracción de segmentos de líneas encontradas. BFS simplemente no es práctico para un gran conjunto de datos.

Desarrollador
fuente
Radon y Hough operarían con datos volumétricos, no nubes de puntos, que yo sepa. Las ideas probablemente se puedan adaptar a las nubes de puntos, pero no estoy seguro de si seguirían teniendo el mismo nombre.
endolito el
¿Cuáles son tus criterios? La fuerza bruta definitivamente encontraría una línea si está allí, mientras que RANSAC solo "probablemente" encuentre la línea.
endolito el
@endolith '... volumetric ...': Un buen punto. Sin embargo, creo que es posible pixelar (mapear) los puntos 3D en volumen 3D (matriz 3D) con una tolerancia aceptable referida a la resolución de la matriz (es decir, el número de celdas). '... Brute-Force ...' es absolutamente preciso pero no computacionalmente práctico para un gran conjunto de puntos. 'RANSAC' como usted mencionó podría perder algunos candidatos. La idea es discutir y encontrar algunas sugerencias para tratar esos problemas: costo de cómputo e inexactitud.
Desarrollador
La conversión de la nube de puntos en una matriz volumétrica probablemente sería un paso en la dirección incorrecta. :) Mejor usar algoritmos que operan en la nube de puntos y la distancia euclidiana entre puntos.
endolito el
@endolith Puede que tengas razón. Solo por mencionar que mis experiencias personales con Hough Transform en casos 2D fueron muy satisfactorias y ¡fue realmente tan rápido como inmediato! Estoy pensando en beneficiarme de un método de etapas múltiples para lograr precisión y velocidad al mismo tiempo. Espero que los comentarios y respuestas en esta publicación puedan proporcionar algunas instrucciones.
Desarrollador

Respuestas:

1

Realmente depende, ¿cómo va a medir la calidad de las soluciones? ¿Cuáles son sus requisitos, tiempo real, alta precisión? ¿Qué tan grande es la nube de puntos?

Usted mencionó métodos válidos pero sofisticados basados ​​en el procesamiento de señales para abordar el problema.

Permítanme agregar tres métodos que no han mencionado que son clásicos y de naturaleza más estadística: mínimos cuadrados, regresión de crestas y lazo.

carlosdc
fuente
1
Todos estos son métodos de optimización, pero el truco es encontrar una buena función para optimizar. ¿Cuál es la función que sugiere optimizar con respecto?
Phonon
0

Si está realmente preocupado por las líneas de detección, puede hacer un enfoque simplificado.

Proyecte su nube de puntos en al menos dos superficies. Digamos proyectarlos en el plano XY y el plano YZ. Básicamente, comience con un lienzo en blanco y proyecte cada punto según algunos criterios de geometría. Así que ahora tendrá un lienzo 2D finito que está en blanco pero con puntos blancos que están presentes. Ahora puede aplicar hough transform en estos lienzos.

Basado en hough, obtendrá líneas y para dos planos respectivos. El siguiente paso es realmente asociar estas líneas para identificar una sola línea 3D de esta.(r,θ)(r,ϕ)

En cuanto a la precisión, cuando los datos son escasos, la puntuación de la altura (es decir, la fuerza) puede ser menor. Sin embargo, funcionará si, en general, todas las líneas son dispersas. Es un problema cuando se compara una línea muy larga con una línea corta.

Dipan Mehta
fuente