Detectar patrones circulares en datos de nubes de puntos

Question

Para un algoritmo de reconstrucción de volúmenes en el que estoy trabajando, necesito detectar un número arbitrario de patrones circulares en datos de puntos 3D (procedentes de un dispositivo LIDAR). Los patrones pueden estar orientados arbitrariamente en el espacio, y se supone que se encuentran (aunque no perfectamente) en planos 2d delgados. Aquí hay un ejemplo con dos círculos en el mismo plano (aunque recuerda que este es un espacio 3d):

He probado muchos enfoques el más sencillo (pero el que mejor funciona hasta ahora) es la agrupación basada en conjuntos disjuntos del gráfico del vecino más cercano. Esto funciona razonablemente bien cuando los patrones están muy separados, pero no tanto con círculos como los del ejemplo, muy cercanos entre sí.

Probé con K-means, pero no lo hace bien: Sospecho que la disposición de puntos circulares no se adapta bien a ella. Además, tengo el problema adicional de no saber de antemano el valor de K.

Intenté enfoques más complicados, basados en la detección de ciclos en el gráfico del vecino más cercano, pero lo que obtuve era demasiado frágil o caro desde el punto de vista computacional.

También he leído sobre un montón de temas relacionados (transformada de Hough, etc) pero nada parece aplicarse perfectamente en este contexto específico. Cualquier idea o inspiración sería apreciada.

Answer 1

Una generalización de la Transformación de Hough es exactamente lo que quieres. La dificultad estriba en hacerlo de forma eficiente, porque el espacio de los círculos en 3D tiene seis dimensiones (tres para el centro, dos para orientar el plano, una para el radio). Esto parece descartar un cálculo directo.

Una posibilidad es colarse en el resultado a través de una secuencia de transformaciones de Hough más sencillas. Por ejemplo, se podría empezar con la transformada de Hough (habitual) para detectar subconjuntos planares: éstos sólo requieren una cuadrícula 3D para el cálculo. Para cada subconjunto plano detectado, corte los puntos originales a lo largo de ese plano y realice una transformada de Hough generalizada para la detección de círculos. Esto debería funcionar bien siempre que la imagen original no tenga muchos puntos coplanares (aparte de los formados por los círculos) que podrían ahogar la señal generada por los círculos.

Si los tamaños de los círculos tienen un límite superior predeterminado, se puede ahorrar mucho cálculo: en lugar de buscar todos los pares o triples de puntos en la imagen original, se puede centrar en los pares o triples dentro de una vecindad delimitada de cada punto.

Answer 2

Bueno, si el objetivo es simplemente detectar el $\textit{number}$ de patrones circulares, y tienes suficientes datos, tal vez intentes con redes neuronales convolucionales profundas. Realmente, se necesitarían todos esos datos etiquetados, pero las DCN pueden utilizarse como método complementario a los sugeridos anteriormente.