Linhas de ajuste através de grandes nuvens de pontos

Eu tenho um grande conjunto de pontos (ordem de 10k pontos) formados por trilhas de partículas (movimento no plano xy no tempo filmado por uma câmera, de modo que quadros 3d - 256x256px e ca 3k no meu exemplo) e ruído. Essas partículas viajam aproximadamente em linhas retas aproximadamente (mas apenas aproximadamente) na mesma direção e, portanto, para a análise de suas trajetórias, estou tentando ajustar as linhas através dos pontos. Tentei usar o RANSAC sequencial, mas não consigo encontrar um critério para identificar falsos positivos de maneira confiável, bem como o T e J-Linkage, que eram muito lentos e também não eram confiáveis ​​o suficiente.

Aqui está uma imagem de uma parte do conjunto de dados com ajustes bons e ruins que obtive com o Ransac sequencial: estou usando os centróides dos blobs de partículas aqui, os tamanhos dos blob variam entre 1 e 20 pixels.

Descobri que as subamostras, que usam, por exemplo, apenas a cada 10 quadros, também funcionavam muito bem; portanto, o tamanho dos dados a serem processados ​​pode ser reduzido dessa maneira.

Eu li um post de blog sobre tudo o que as redes neurais podem realizar e gostaria de perguntar se esse seria um aplicativo viável para um antes de começar a ler (eu sou de um fundo que não é de matemática, então eu teria que fazer bastante um pouco de leitura)?

Ou você poderia sugerir um método diferente?

Obrigado!

Adendo: Aqui está o código para uma função Matlab para gerar uma nuvem de pontos de amostra contendo 30 linhas ruidosas paralelas, que ainda não consigo distinguir:

function coords = generateSampleData()
coords = [];
for i = 1:30
    randOffset = i*2;
    coords = vertcat(coords, makeLine([100+randOffset 100 100], [200+randOffset 200 200], 150, 0.2));
end

figure
scatter3(coords(:,1),coords(:,2),coords(:,3),'.')

function linepts = makeLine(startpt, endpt, numpts, noiseOffset)
    dirvec = endpt - startpt;
    linepts = bsxfun( @plus, startpt, rand(numpts,1)*dirvec); % random points on line
    linepts = linepts + noiseOffset*randn(numpts,3); % add random offsets to points
end

end

Com base no feedback e tentando encontrar uma abordagem mais eficaz, desenvolvi o seguinte algoritmo usando uma medida de distância dedicada.

As etapas a seguir são executadas:

1) Defina uma métrica de distância retornando:

zero - se os pontos não pertencerem a uma linha

Distância euclidiana dos pontos - se os pontos constituem uma linha de acordo com os parâmetros definidos, ou seja,

• a distância é maior ou igual ao min_line_length e

• a distância deles é menor ou igual ao max_line_length e

• a linha consiste em pelo menos min_line_points pontos com uma distância menor que line_width / 2 da linha

2) Calcule a matriz de distância usando essa medida de distância (use amostra dos dados para grandes conjuntos de dados; ajuste os parâmetros de linha de acordo)

3) Encontre os pontos A e B com distância máxima - avance para o passo 5) se a distância for zero

Observe que se a distância for maior que zero, os pontos A e B estão construindo uma linha com base em nossa definição

4) Obtenha todos os pontos pertencentes à linha AB e remova-os da matriz de distância. Repita a etapa 3) para encontrar outra linha

5) Verifique a cobertura do ponto com as linhas selecionadas, se um número substancial de pontos permanecer descoberto, repita todo o algoritmo com parâmetros de linha ajustados.

6) Caso a amostra de dados tenha sido usada - reatribua todos os pontos nas linhas e recalcule os pontos de limite.

Os seguintes parâmetros são usados:

largura da linha - line_width / 2 é a distância permitida do ponto da linha ideal = r line_width

comprimento mínimo da linha - pontos com menor distância não são considerados pertencentes à mesma linha = r min_line_length

comprimento máximo da linha - pontos com distâncias maiores não são considerados pertencentes à mesma linha = r max_line_length

pontos mínimos em uma linha - linhas com menos pontos são ignoradas =r min_line_points

Com seus dados (depois de mexer nos parâmetros), obtive um bom resultado cobrindo todas as 30 linhas.

Mais detalhes podem ser encontrados no script knitr

Resolvi tarefa semelhante, embora mais simples, com uma abordagem de força bruta. A simplificação estava no pressuposto de que a linha é uma função linear (no meu caso, até os coeficientes e a interceptação estavam em algum intervalo conhecido).

Portanto, isso não resolverá seu problema em geral, onde uma partícula pode se mover ortogonalmente com o eixo x (isto é, ela não rastreia nenhuma função), mas eu posto a solução como uma possível inspiração.

1) Tome todas as combinações de dois pontos A e B com A (x)> B (x) + constante (para evitar a simetria e um erro alto ao calcular o coeficiente)

2) Calcule o coeficiente c e intercepte i da linha AB

 A(y) = i + c * A(x)
 B(y) = i + c * B(x)
 A(y) - B(y) = c * (A(x) - B(x))
 c = (A(y) - B(y)) / (A(x) - B(x))
 i = A(y) - c * A(x)

3) Arredondar o coeficiente e interceptar (isso deve eliminar / diminuir os problemas com erros causados ​​pelos pontos em uma grade)

4) Para cada interceptação e coeficiente, calcule o número de pontos nesta linha

5) Considere apenas linhas com pontos acima de algum limite.

Exemplo simples veja aqui