Ajustement des lignes à travers de gros nuages ​​de points

8

J'ai un grand ensemble de points (ordre de 10k points) formés par des pistes de particules (mouvement dans le plan xy dans le temps filmé par une caméra, donc 3d - 256x256px et environ 3k images dans mon jeu d'exemples) et le bruit. Ces particules se déplacent sur des lignes approximativement droites à peu près (mais seulement à peu près) dans la même direction, et donc pour l'analyse de leurs trajectoires, j'essaie d'ajuster les lignes à travers les points. J'ai essayé d'utiliser Sequential RANSAC, mais je ne trouve pas de critère pour distinguer de manière fiable les faux positifs, ainsi que les liaisons T et J, qui étaient trop lentes et pas assez fiables.

Voici une image d'une partie de l'ensemble de données avec de bons et de mauvais ajustements que j'ai obtenus avec Ransac séquentiel: entrez la description de l'image ici j'utilise ici les centroïdes des blobs de particules, les tailles de blob varient entre 1 et environ 20 pixels.

J'ai trouvé que les sous-échantillons n'utilisant par exemple que toutes les 10 images fonctionnaient également très bien, de sorte que la taille des données à traiter peut être réduite de cette façon.

J'ai lu un article de blog sur tout ce que les réseaux de neurones peuvent accomplir, et je voudrais vous demander si ce serait une application réalisable avant de commencer à lire (je viens d'un milieu non mathématique, donc je devrais faire tout à fait un peu de lecture)?

Ou pourriez-vous suggérer une méthode différente?

Merci!

Addendum: Voici le code d'une fonction Matlab pour générer un échantillon de nuage de points contenant 30 lignes bruyantes parallèles, que je ne peux pas encore distinguer:

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
Lukas K.
la source
si vous nous donnez un exemple de jeu de données, ou un faux jeu de données suffisamment semblable à votre vrai jeu de données, ou une image d'un vrai ou faux jeu de données, vous obtiendrez peut-être une meilleure réponse. Vous ne dites pas si c'est 2d ou 3d - ou 4d ...
Spacedman
Je ne pensais pas que cela devrait être aussi précis. Mis à jour quand même
Lukas K.
Ooh c'est beaucoup plus intéressant que je ne le pensais. Vous avez tout un nuage de points qui appartiennent à un grand nombre de lignes différentes et certains points bruyants qui ne le font pas, et idéalement, vous voulez trouver toutes les lignes, même les plus petites comme les 3 ou 4 en bas à droite ...
Spacedman
Je suis content que le problème soit intéressant, maintenant j'espère que quelqu'un pourra m'aider :)
Lukas K.
ah, mais ce ne sont pas des coordonnées de points x, y, T continus mais un tas de rasters binaires (0/1)? Et si deux pistes se croisent, vous pourriez obtenir un pixel qui appartient à plusieurs pistes ...
Spacedman

Réponses:

3

Sur la base des commentaires et en essayant de trouver une approche plus efficace, j'ai développé l'algorithme suivant en utilisant une mesure de distance dédiée.

Les étapes suivantes sont effectuées:

1) Définissez une métrique de distance renvoyant:

zéro - si les points n'appartiennent pas à une ligne

Distance euclidienne des points - si les points constituent une ligne selon les paramètres définis, c'est-à-dire

  • leur distance est supérieure ou égale à la longueur_min_line et

  • leur distance est inférieure ou égale à max_line_length et

  • la ligne se compose d'au moins min_line_points points avec une distance inférieure à line_width / 2 de la ligne

2) Calculez la matrice de distance à l' aide de cette mesure de distance (utilisez un échantillon des données pour les grands ensembles de données; ajustez les paramètres de ligne en conséquence)

3) Trouvez les points A et B avec la distance maximale - passez à l'étape 5) si la distance est nulle

Notez que si la distance est supérieure à zéro, les points A et B construisent une ligne basée sur notre définition

4) Obtenez tous les points appartenant à la ligne AB et supprimez-les de la matrice de distance. Répétez l'étape 3) pour trouver une autre ligne

5) Vérifiez la couverture du point avec les lignes sélectionnées, si un nombre substantiel de points reste découvert, répétez tout l'algorithme avec les paramètres de ligne ajustés.

6) Si cet échantillon de données a été utilisé - réaffectez tous les points aux lignes et recalculez les points limites.

Les paramètres suivants sont utilisés:

largeur de ligne - largeur_ligne / 2 est la distance autorisée entre le point et la ligne idéale = r line_width

longueur de ligne minimale - les points avec une distance plus courte ne sont pas considérés comme appartenant à la même ligne = r min_line_length

longueur maximale de ligne - les points avec une distance plus longue ne sont pas considérés comme appartenant à la même ligne = r max_line_length

minimum de points sur une ligne - les lignes avec moins de points sont ignorées =r min_line_points

Avec vos données (après quelques manipulations de paramètres), j'ai obtenu un bon résultat couvrant les 30 lignes.

entrez la description de l'image ici

Plus de détails peuvent être trouvés dans le script knitr

Marmite Bomber
la source
2

J'ai résolu une tâche similaire, bien que plus simple, avec une approche par force brute. La simplification reposait sur l'hypothèse que la ligne est une fonction linéaire (dans mon cas, même les coefficients et l'ordonnée à l'origine étaient dans une plage connue).

Cela ne résoudra donc pas votre problème en général, où une particule peut se déplacer orthogonalement à l'axe x (c'est-à-dire qu'elle ne trace aucune fonction), mais je poste la solution comme une inspiration possible.

1) Prendre toutes les combinaisons de deux points A et B avec A (x)> B (x) + constante (pour éviter la symétrie et une erreur élevée lors du calcul du coefficient)

2) Calculez le coefficient c et l' ordonnée à l'origine i de la droite 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) Arrondissez le coefficient et l'interception (cela devrait éliminer / réduire les problèmes d'erreurs causées par les points dans une grille)

4) Pour chaque interception et coefficient, calculez le nombre de points sur cette ligne

5) Ne considérez que les lignes dont les points dépassent un certain seuil.

Exemple simple voir ici

Marmite Bomber
la source
C'est essentiellement ce que je fais avec RANSAC (sauf que j'utilise l'échantillonnage aléatoire au lieu d'essayer toutes les combinaisons). Le problème pour moi ne correspond pas à certaines lignes, le problème est que j'adapte trop de lignes, car avec autant de points proches, même une ligne asymétrique trouvera suffisamment d'inliers dans un seuil raisonnable. Je cherche donc un critère pour distinguer les lignes qui correspondent aux lignes "réelles" des autres.
Lukas K.
1
Je ne sais pas si c'est vraiment la même approche. Je ne fais pas de distinction entre le point sur une ligne et la valeur aberrante . J'examine si deux vecteurs peuvent ou non appartenir à une même ligne. Je pense que cela pourrait être beaucoup plus exact. Additioanly J'utilise les paramètres largeur de ligne , la longueur minimale de ligne et des points de ligne minimale pour commander la sélection.
Marmite Bomber
OK je vois. Bien qu'avec 10k points et (10E + 5 choisissez 2) = 5E + 11 paires possibles, je devrai faire un échantillonnage aléatoire. De plus, cela est probablement assez sensible aux écarts par rapport à une ligne droite, ce qui pourrait changer l'interception. Mais je vais essayer! Pense comme longueur minimum et pas minimum. de points en ligne que j'ai déjà utilisé dans mes tentatives pour nettoyer les résultats.
Lukas K.