Estou procurando um algoritmo capaz de resolver esse problema.

O problema:

Eu tenho os seguintes pontos de ajuste:

Quero agrupar os pontos que representam uma linha (com algum épsilon) em um grupo. Portanto, a saída ideal será algo como:

Algumas notas:

O ponto pertence a uma e única linha.Se o ponto puder pertencer a duas linhas, ele deve pertencer ao mais forte.Uma linha é considerada mais forte que outra quando possui mais pontos de pertença.O algoritmo não deve abranger todos os pontos, pois podem ser discrepantes.O espaço contém muitos outliers, podendo atingir 50% do espaço total.O desempenho é crítico, é necessário em tempo real.

As soluções que encontrei até agora:

1) Lidando com isso como um problema de agrupamento:

A principal desvantagem deste método é que existenão métrica de distância direta entre pontos. A métrica de distância está no próprio cluster (quanto é linear). Portanto, não posso usar métodos tradicionais de agrupamento e tenho que (até onde eu pensava) usar algum tipo, por exemplo, de agrupar algoritmos genéticos nos quais a avaliação ocorre no agrupamento enquanto não está entre dois pontos. Eu também não quero usar algo como Algoritmo Genético Enquanto estou buscando uma solução em tempo real.

2) pares acumulativos e faça cluster:

Embora seja difícil agrupar pontos diretamente, pensei em extrair pares de pontos e depois tentar agrupá-los com outras pessoas. Então, eu tenho uma distância entre dois pares que podem representar a linearidade (dois pares são reais em 4 pontos). A desvantagem deste método é como escolher esses pares? Se eu dependo da distância éclediana entre eles, pode não ser preciso, porque dois pontos podem estar tão próximos um do outro, mas estão longe de fazer uma linha com os outros.

Agradeço qualquer solução, sugestão, pista ou observação. Por favor, você pode perguntar sobre qualquer esclarecimento.

P.S. Você pode usar qualquer função OpenCV pronta para pensar em qualquer solução.