Estoy buscando un algoritmo que sea capaz de resolver este problema.

El problema:

Tengo los siguientes puntos de ajuste:

Quiero agrupar los puntos que representan una línea (con algo de épsilon) en un grupo. Entonces, la salida óptima será algo como:

Algunas notas:

El punto pertenece a una sola línea.Si el punto puede pertenecer a dos líneas, debería pertenecer al más fuerte.Una línea se considera más fuerte que otra cuando tiene más puntos de pertenencia.El algoritmo no debe cubrir todos los puntos porque pueden ser atípicos.El espacio contiene muchos valores atípicos, puede alcanzar el 50% del espacio total.El rendimiento es crítico, en tiempo real es imprescindible.

Las soluciones que encontré hasta ahora:

1) Tratarlo como un problema de agrupamiento:

El principal inconveniente de este método es que hayNo distancia directa métrica entre puntos. La métrica de distancia está en el clúster (cuánto es lineal). Por lo tanto, no puedo usar los métodos de agrupación tradicionales y tengo que (por lo que pensaba) usar algún tipo de, por ejemplo, agruparnos el algoritmo genético donde la evaluación ocurre en el grupo de tiempo no entre dos puntos. Tampoco quiero usar algo como Algoritmo Genético Mientras busco una solución en tiempo real.

2) pares acumulativos y luego agrupamiento:

Si bien es difícil agrupar los puntos directamente, pensé en extraer pares de puntos y luego tratar de agruparlos con otros. Entonces, tengo una distancia entre dos pares que puede representar la linealidad (dos pares están en 4 puntos reales). El inconveniente de este método es cómo elegir estos pares? Si dependo de la distancia eclediana entre ellos, puede que no sea exacto porque dos puntos pueden estar tan cerca el uno del otro pero están muy lejos de hacer una línea con los demás.

Agradezco cualquier solución, sugerencia, pista o nota. Por favor, puede preguntar sobre cualquier aclaración.

PD Puede usar cualquier función OpenCV preparada para pensar en cualquier solución.