Suivi/tracking de particules en déplacement sur des images

Temps de lecture : 7 minutes

De la « traque de particules », c’est ce que je te propose de réaliser dans cet article… un peu comme ceci :

Pour te résumer le problème en étapes, on a :

  • Point de départ : une image représentant un milieu composé de deux populations de particules (grandes en bleu et petites en rouge)
  • Ce qu’il se passe entre temps : les particules se déplacent d’une certaine quantité : on a l’image de la nouvelle configuration
  • Notre objectif ? à partir des deux images, retrouver les déplacements de chaque particule pour établir une carte de déplacement

Let’s go !

[Code complet (Jupyter Notebook) et ressources sur Github]

Petite mise au point sur le contexte pratique général

Les images sont tirées de mes expériences de doctorat sur les mécanismes de mélange de particules solides. Pour faire simple, on a deux populations de particules de forme circulaire sur un plateau. Un intrus (en noir) vient mélanger le milieu et on regarde comment les particules interagissent les unes avec les autres. Après une expérience typique, on obtient une série temporelle d’images prises à intervalle de 0.1 s. Patience, je te dirai bientôt pourquoi une telle fréquence d’acquisition. Ensuite, sur chacune de ces images, il faut détecter les particules et leurs coordonnées dans l’espace, les classifier, générer les images en couleur comme celles que je présente en haut… Pas de magie, pour réaliser tout ça, il faut faire du traitement d’image ! J’ai déjà écrit un article complet là-dessus 🙂.

Mais là, disons qu’on a déjà fait tout ça. On a deux images : 1 (à état initial) et 2 (à l’état final après déplacement des particules). Pour chacune des images, on connait :

  • La position de toutes les particules (exprimée en coordonnées x, y dans le repère global fixe)
  • La taille t de chaque particule : pour faire simple, on fera un truc binaire : petite ou grande (on mettra 1 pour une petite particule et 2 pour une grande particule)

En récap, infos en entrée : [x_i, y_i, t_i], i \in \{1,2\}. On a 1748 particules au total donc x_i, y_i, t_i sont des vecteurs de taille 1748. Question du jour : Comment apparier les particules entre elles sur les deux images ?

Idée générale

Euh, j’avoue, j’ai fait comme si on allait faire quelque chose de très compliqué. Mais de fait, le principe de base est très simple. Pour une particule sur l’image 1, on va calculer la distance entre son centre et le centre de toutes les particules sur l’image 2. La particule sur l’image 2 qui admet la plus petite distance (la plus proche) est forcément celle qu’on recherche ! J’ai dit « forcément » mais ça n’est pas tout à fait le cas… ce principe ne marche que si les particules ne se déplacent pas de plus d’une distance équivalente à leur rayon (hypothèse de petits déplacements). Tu peux faire une pause pour y réfléchir et si tu es en plus matheux, tu peux t’amuser à démontrer ça . Mais en gros, si les particules se déplacent de 10 diamètres entre deux images par exemple, il devient virtuellement impossible de les suivre (même à l’oeil nu). C’est la raison pour laquelle on filme à relativement haute fréquence (10 Hz soit 0.1 s entre deux images) – j’avais promis de te dire pourquoi, promesse tenue ! Parce que de la sorte on s’assure que les particules se sont très peu déplacées !

Principe de l’appariement (hypothèse de petits déplacements)

Bon maintenant qu’on a le principe, et si on passait à l’implémentation ? Tu l’as vu, l’idée de base est simple. Personnellement je trouve que le plus intéressant dans ce problème, c’est la logique d’implémentation du code.

Implémentation de l’algorithme

Rappel des données du problème :

  • n = 1748 nombre total de particules (petites et grandes)
  • x_1 : vecteur de taille n représentant les abscisses des particules sur la première image
  • y_1 : vecteur de taille n représentant les ordonnées des particules sur la première image
  • t_1 : vecteur de taille n représentant le type des particules (1 pour une petite et 2 pour une grande)
  • x_2, y_2, t_2 : mêmes notations mais pour la deuxième image

Vu qu’on veut faire apparier les particules les unes aux autres, il faut commencer à bien définir la structure de la donnée finale. Je te propose ceci :

Une structure en matrice où les lignes correspondent aux images et les colonnes aux particules. De la sorte, si je prends la première colonne par exemple, je sais que j’ai les coordonnées successives de la particule 1 (part. 1) sur les images consécutives. Ici, on fait l’appariement pour 2 images; dans la vraie expérience, j’en faisais pour près de 1000 particules : la logique reste la même !

Coeur du code Python
Structure des données

Comme la matrice n’est qu’une pile de vecteurs, commençons déjà par créer des vecteurs pour stocker les informations de la première image. Et un vecteur temporaire pour stocker les paires qu’on aura trouvées pour chaque particule.

# X stocke les coordonnées x des particules, Y leurs coordonnées y et T stocke leur taille (petite = 1 ou grande = 2)
X = []; Y = []; T = [] # Listes vides

# Ajout des informations de la première image
X.append(x1); Y.append(y1); T.append(t1)

# Listes tampons pour contenir les résultats des appariements
xt = [-1]* len(x1); yt = [-1]*len(y1) ; 
Séparation grandes/petites particules

Rappelle-toi, on a de petites et de grandes particules. Donc si on a affaire à une petite particule sur la première image, ça ne sert à rien de chercher sa paire dans toutes les particules de la deuxième image. On parcourra uniquement les petites particules sur la deuxième image. Donc faisons tout de suite deux tas, petites particules et grandes particules :

# Sur la deuxième image, sélection des coordonnées des petites particules uniquement 
x2_p = x2[t2 == 1]
y2_p = y2[t2 == 1]

# Sur la deuxième image, sélection des coordonnées des grandes particules uniquement
x2_g = x2[t2 == 2] 
y2_g = y2[t2 == 2]

Désormais, on peut parcourir la liste des petites particules et calculer pour chacune les distances avec les petites particules de la seconde image. Comme on a dit, la particule qu’on recherche est celle qui admet la distance minimale. Et bien sûr après les petites, il faudra faire de même avec les grandes.

N.B. : j’ai aussi précisé plus haut que ceci ne marche que si les particules ne se sont pas déplacées de plus d’une distance équivalente au rayon d’une particule. Je mets donc un if de sécurité pour m’assurer que cette condition est vérifiée. Dans notre cas, le rayon est d’à peu près 9 pixels. Pour nos deux images ici, ça marche tout le temps pour toutes les particules. Mais le piège dans un algorithme, c’est toujours les exceptions et il ne faut jamais les oublier 🤨!

#Balayage des particules
for k in range(len(x1)):
    
    x = x1[k]; y = y1[k];

    # CAS D'UNE PETITE PARTICULE
    if (t1[k] == 1):

        # Distance entre la particule k de l'image 1 et toutes les petites particules de l'image 2
        dist = np.sqrt((x - x2_p)**2 + (y - y2_p)**2)

        # La particule qui admet le min de dist est forcément celle qu'on cherche
        imin = np.argmin(dist)

        # Remplissage de la case concernée dans les listes tampons
        if (dist[imin] <= 9): #Particule retrouvée
            xt[k] = x2_p[imin];
            yt[k] = y2_p[imin];
             
        else : # paire non retrouvée
            pass
            # Je ne gère pas ce cas dans ce code, il fera peut être l'objet d'un autre article

    # CAS D'UNE GRANDE PARTICULE
    else : 
        if(t1[k]==2):

            # Distance entre la particule k de l'image 0 et toutes les images de l'image 1
            dist = np.sqrt((x - x2_g)**2 + (y - y2_g)**2)

            # La particule qui admet le min de dist est forcément celle qu'on cherche
            imin = np.argmin(dist)

            # Remplissage de la case concernée dans les listes tampons
            if (dist[imin] <= 9): #Particule retrouvée
                xt[k] = x2_g[imin];
                yt[k] = y2_g[imin];

  
            else :
                pass
                # particule non retrouvée, non gérée comme plus haut

Maintenant nous avons trouvé les paires de chaque particule et constitué la deuxième ligne de notre matrice. On peut rajouter x_t à X et y_t à Y.

# Rajout des listes tampons avec les paires retrouvées aux listes globale
X.append(np.asarray(xt)); 
Y.append(np.asarray(yt));

Techniquement X et Y ne sont pas des matrices mais des listes de vecteurs. X[0] représente l’image 1 avec les n = 1748 éléments et X[1] représente l’image 2 avec les n = 1748 éléments. Et chaque position dans ces vecteurs correspond à une particule précise. Si on veut avoir rigoureusement une matrice, il faut rajouter quelques lignes de code mais je te laisse t’amuser avec ça 😉!

Gestion des exceptions/erreurs

Les plus attentifs ont dû constater que je n’ai pas géré les exceptions, j’ai fait des « pass ». Dans le cas de mes 1000 images à traiter, je peux t’assurer qu’il y avait des exceptions… C’est véritablement là où le code peut devenir complexe : si on ne trouve pas la paire d’une particule, qu’est-ce qu’on fait ? Quelle nouvelle structure des données choisit-on ? Ici aussi, je te laisse réfléchir là-dessus, dis-moi si tu veux que je réécrive un article dessus !

Carte de déplacement : quiver plot

Mais retour au cas parfait, toutes les particules ont trouvé leur paire, il ne reste qu’à représenter les déplacements avec des flèches « quiver plot » en anglais. Python propose une fonction pour faire ça, devine son nom : quiver de la librairie matplotlib.pyplot. Oui, il y a beaucoup de créativité sur les noms 😀; (ok, je suis mauvaise langue, c’est mieux comme ça, on se retrouve plus facilement).

Il faut préciser les abcisses x_1 de départ, les ordonnées y1 de départ, les déplacements absolus x_2 – x_1, et y_2 – y_1 (là il faut faire attention à l’orientation des axes pour avoir les flèches dans le bon sens), et il y a d’autres paramètres pour spécifier la normalisation du code couleur, la longueur, la largeur des flèches…etc. Bref, amuse-toi à les changer pour comprendre. Et tada, on obtient notre carte avec de jolies couleurs :

Plutôt cool non ? tu peux voir que loin de la tige par exemple, les particules ne se déplacent pas et on a un mouvement de recirculation autour de la tige au cours de son déplacement… Euh, pardon, je me suis mis à réécrire mon manuscrit de thèse là ! Mauvaises habitudes, on fera de la physique de l’écoulement dans un autre article 😅.

Voilà, amuse-toi avec le code complet et fais-toi plaisir ! Là, nous avons tracké les particules et tu sais quoi ? On peut aussi s’amuser à suivre la trajectoire de l’intrus dans son déplacement. Si ça t’intéresse, c’est par ici !

Partager

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *