Para algunos algoritmos de reconstrucción de volumen en los que estoy trabajando, necesito detectar un número arbitrario de patrones circulares en datos de puntos 3D (provenientes de un dispositivo LIDAR). Los patrones se pueden orientar 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 recuerde que este es un espacio 3d):
Intenté muchos enfoques ... el más simple (pero el que mejor ha funcionado hasta ahora) es la agrupación basada en conjuntos disjuntos del gráfico 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 cerca uno del otro.
Intenté con K-means, pero no funciona bien: sospecho que la disposición de los puntos circulares podría no ser adecuada para ello. 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 vecino más cercano, pero lo que obtuve fue demasiado frágil o computacionalmente costoso.
También leí sobre muchos temas relacionados (transformación de Hough, etc.) pero nada parece aplicarse perfectamente en este contexto específico. Cualquier idea o inspiración sería apreciada.
fuente
Respuestas:
Una transformación Hough generalizada es exactamente lo que quieres. La dificultad es hacerlo de manera 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 acercarse sigilosamente al resultado a través de una secuencia de transformaciones de Hough más simples. Por ejemplo, podría comenzar con la transformación de Hough (habitual) para detectar subconjuntos planos: estos requieren solo 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 transformación 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, potencialmente puede guardar una gran cantidad de cálculos: en lugar de mirar todos los pares o triples de puntos en la imagen original, puede enfocarse en pares o triples dentro de un vecindario acotado de cada punto.
fuente
fuente