Tracking par Computer Vision
Dans la Computer Vision, l’un des domaines de recherche les plus intéressants est la détection d’obstacles utilisant des réseaux de neurones. Beaucoup de documents ont été publiés, tous atteignant l’état de l’art en détectant les obstacles avec une précision très élevée. Le but de ces algorithmes est de prédire des bounding box à partir d’une image. Le Machine Learning a très bien évolué pour localiser et classifier les obstacles en temps réel dans une image. Cependant, aucun de ces algorithmes n’inclut la notion de temps et de continuité. Lors de la détection d’un obstacle, ces algorithmes supposent qu’il s’agit à chaque fois d’un nouvel obstacle.
Voici l’un des algorithmes de détection d’objets les plus populaires, appelé YOLO (You Only Look Once).
Je n’entrerai pas dans les détails de l’algorithme ici, mais vous pouvez regarder cette vidéo de Siraj Raval qui l’explique très bien.
La sortie de l’algorithme est une liste de bounding box, au format [classe, x, y, w, h, confiance]. La classe est un identifiant associé à un numéro dans un fichier txt (0 pour voiture, 1 pour piéton,…). x, y, w et h représentent les paramètres de la bounding box. x et y sont les coordonnées du centre tandis que w et h sont sa taille (largeur et hauteur). La confiance est un nombre exprimé en %.
Comment utiliser ces bounding boxes ?
Jusqu’à présent, les bounding box ont été utilisées pour compter le nombre d’obstacles de la même classe dans une foule, dans des voitures autonomes, des drones, des caméras de surveillance, des robots autonomes et toutes sortes de systèmes utilisant la Computer Vision. Cependant, ils partagent tous la même limite: les obstacles d’une classe sont de la même couleur et ne peuvent pas être séparés.
Deep SORT (Deep Simple Online Realtime Tracking)
Alors, comment pourrions-nous définir ces box comme indépendantes et comment pouvons-nous les suivre dans le temps?
Cette implémentation utilise un algorithme de détection d’objet, tel que YOLOv3 et un système de suivi des obstacles. Comme vous pouvez le voir, il fonctionne aussi avec l’occlusion. Comment ? La raison en est l’utilisation d’un filtre de Kalman et de l’algorithme hongrois.
- Un algorithme hongrois peut dire si un objet dans l’image actuelle est le même que celui de l’image précédente. Il sera utilisé pour l’attribution d’id et l’association.
- Un filtre de Kalman est un algorithme qui permet de prédire les positions futures en fonction de la position actuelle. Il peut également estimer la position actuelle mieux que ce que le capteur nous dit. Il sera utilisé pour avoir une meilleure association.
L’algorithme Hongrois (Kuhn-Munkres)
L’algorithme hongrois, également connu sous le nom d’algorithme de Kuhn-Munkres, peut associer un obstacle d’une image à l’autre, sur la base d’un score. Nous avons beaucoup de partitions auxquelles nous pouvons penser :
- IOU (Intersection Over Union); ce qui signifie que si la bounding box chevauche la précédente, c’est probablement la même.
- Forme ; si la forme ou la taille n’a pas trop varié entre deux box consécutives, le score augmente.
- Convolution ; nous pourrions exécuter un CNN (Convolutional Neural Network) sur la box et comparer ce résultat avec celui d’une image antérieure. Si les caractéristiques convolutives sont les mêmes, cela signifie que les objets ont le même aspect. S’il y a occlusion partielle, les caractéristiques convolutives resteront en partie les mêmes et l’association restera.
Comment faire l’association?
Dans cet exemple, de la trame a à la trame b, nous suivons deux obstacles (avec id 1 et 2), en ajoutant une nouvelle détection (4) et en gardant une trace (3) au cas où ce serait un faux négatif.
Le processus d’observation est le suivant.. :
- Nous avons deux listes de box de YOLO : une liste de tracking (t-1) et une liste de détection (t).
- Passez dans les deux listes, et calculez le coût IOU, la forme, le score convolutif. Pour cet exemple, considérons seulement l‘IOU, nous pourrions aussi avoir une fonction de coût donnant de l’importance à chaque score. Pour les convolutions, des mesures de distance cosinusienne seraient utilisées. Stockez les scores IOU dans une matrice…
3. Dans certains cas de chevauchement des bounding box, nous pouvons avoir deux ou plusieurs correspondances pour un même candidat. Dans ce cas, nous fixons la valeur maximale de l’IOU à 1 et toutes les autres à 0.
Nous avons une matrice qui nous indique la correspondance entre la détection et le tracking. La chose suivante est d’appeler une fonction sklearn appelée linear_assignment() qui implémente l’algorithme hongrois. Cet algorithme utilise un graphique bipartite (théorie des graphes) pour trouver, pour chaque détection, la valeur de suivi la plus basse dans la matrice. Puisque nous avons des scores et non des coûts, nous remplacerons notre 1 par -1 ; le minimum sera trouvé. Pour notre exemple, la matrice hongroise sera :
Nous pouvons alors vérifier les valeurs manquantes dans notre matrice hongroise et les considérer comme des détections non appariées, ou des suivis non appariées. Pour les détections, veuillez considérer A, B, C comme ayant id 0,1,2.
Voici le code pour interpréter cela :
NB : Dans cet exemple de code, les valeurs IOU = 0 sont présentes dans la matrice hongroise mais rejetées pendant la boucle car inférieures à un seuil.
Ce que nous obtenons de cela, c’est une matrice indiquant quel élément de la liste de détection correspond à quel élément de la liste de tracking.
À partir de là, nous pouvons avoir des détections matchées, des détections non matchées et des tracking non matchés.
Le Filtre de Kalman
Les filtres de Kalman sont très populaires pour suivre les obstacles et prédire les positions actuelles et futures. Il est utilisé dans toutes sortes de robots, drones, avions volants, voitures autonomes, fusion multi-capteurs,…
Un filtre de Kalman est utilisé sur chaque bounding box, donc il vient après qu’une box ait été associée. Lorsque l’association est faite, les fonctions de prédiction et de correction sont appelées. Ces fonctions implémentent les mathématiques des filtres de Kalman composés de formules pour déterminer la moyenne et la covariance d’état.
Moyenne et Covariance
La moyenne et la covariance sont ce que nous voulons estimer. La moyenne est les coordonnées de la box, la covariance est notre incertitude sur cette box ayant ces coordonnées.
La moyenne (x) est un vecteur d’état. Il est composé des coordonnées du centre de la box (cx,cy), de la taille de la box (largeur, hauteur) et du changement de chacun de ces paramètres, vitesses.
Lorsque nous initialisons ce paramètre, nous réglons les vitesses à 0, elles seront alors estimées par le filtre de Kalman.
La covariance (P) est notre matrice d’incertitude dans l’estimation. Nous allons le mettre à un nombre arbitraire et l’ajuster pour voir les résultats. Plus le nombre est élevé, plus l’incertitude est grande.
C’est tout ce dont nous avons besoin d’estimer : un état et une incertitude ! Il y a deux étapes pour qu’un filtre de Kalman fonctionne : la prédiction et la mise à jour. La prédiction permettra de prévoir les positions futures, la mise à jour permettra de les corriger et d’améliorer la façon dont nous prédisons en changeant l’incertitude. Avec le temps, un filtre de Kalman devient de plus en plus performant et converge.
Comment l’utiliser ?
Au temps t=0, nous avons une mesure de 3 bounding box. L’algorithme hongrois les définit comme 3 nouvelles détections. Nous n’avons donc que 3 détections dans notre système. Pour chaque box, nous initialisons des matrices de Kalman avec les coordonnées des bounding box.
Au temps t=1, nous avons 3 box, des mêmes objets. L’algorithme hongrois les associe avec les 3 précédentes et nous pouvons commencer à appeler les prédictions et les mises à jour. Nous prédisons les box réelles au temps t à partir des box au temps t-1, puis nous mettons à jour notre prédiction avec la mesure au temps t.
Prédiction
La phase de prédiction est une multiplication matricielle qui nous indiquera la position de notre box au temps t en fonction de sa position au temps t-1.
Imaginons donc que nous ayons une fonction appelée predict() dans une classe Kalman Filter qui implémente ces mathématiques. Il suffit d’avoir des matrices F, Q et u correctes. Nous n’utiliserons pas le vecteur u comme il est utilisé pour estimer les forces externes, ce que nous ne pouvons pas vraiment faire facilement ici.
Comment configurer correctement les matrices ?
State Transition : F
F est la mise en œuvre de base de ce que nous allons définir. Ce que nous mettons ici est important parce que lorsque nous multiplierons x par F, nous changerons notre x et aurons un nouveau x, appelé x’.
Comme vous pouvez le voir, la matrice F[8x8] contient une valeur temporelle : dt est la différence entre le t de l’image courante et celui de l’image précédente. Nous aurons cx’ = cx’ = cx + dt*vx pour la première ligne, cy’ = cy + dt*vy, et ainsi de suite….
Dans ce cas, cela signifie que nous considérons que la vitesse est constante. Nous avons donc mis en place F pour implémenter le modèle Constant Velocity. Il existe de nombreux modèles que nous pouvons utiliser en fonction du problème que nous voulons résoudre.
Process Covariance Matrix : Q
Q[8x8] est notre matrice de bruit. C’est la confiance que nous accordons au système. Sa définition est très importante et peut changer beaucoup de choses. Q s’ajoutera à notre covariance et définira ensuite notre incertitude globale. Nous pouvons mettre de très petites valeurs (0,01) et les changer avec le temps.
Sur la base de ces matrices et de nos mesures, nous pouvons maintenant faire une prédiction qui nous donnera x’ et P’. Ceci peut être utilisé pour prédire des positions futures ou réelles. Avoir une matrice de confiance est utile pour notre filtre qui peut modéliser l’incertitude du monde et de l’algorithme pour obtenir de meilleurs résultats.
Mise à jour
La phase de mise à jour est une étape de correction. Elle inclut la nouvelle mesure (z) et permet d’améliorer notre filtre.
Le processus de mise à jour doit commencer par la mesure d’une erreur entre la mesure (z) et la prédiction. La deuxième étape consiste à calculer un gain de Kalman (K). Le gain de Kalman est utilisé pour estimer l’importance de notre erreur. Nous l’utilisons comme facteur de multiplication dans la formule finale pour estimer un nouveau x.
Encore une fois, Comment configurer correctement les matrices ?
Vecteur de mesure : Z
z est la mesure à l’instant t. Nous n’introduisons pas ici les vitesses car elles ne sont pas mesurées, mais simplement des valeurs données par YOLO.
Matrice de mesure : H
H[4x8] est notre matrice de mesure, elle fait simplement fonctionner les maths entre toutes les matrices ou des matrices différentes. Nous les mettons en fonction de la façon dont nous avons défini notre état, et sa dimension dépend fortement de comment dont nous définissons notre état.
Bruit de mesure : R
R est notre bruit de mesure ; c’est le bruit du capteur. Pour un LiDAR ou un RADAR, il est généralement donné par le constructeur. Ici, nous devons définir un bruit pour l’algorithme YOLO, en termes de pixels. Ce sera arbitraire, on peut dire que le bruit en terme du centre est d’environ 1 ou 2 pixels alors que le bruit en largeur et en hauteur peut être plus grand, disons 10 pixels.
Des multiplications matricielles sont faites ; et nous avons une boucle de prédiction et de mise à jour qui nous donne de meilleurs résultats que l’algorithme YOLO. Le filtre peut également être utilisé pour prédire au temps t+1 (prédiction sans mise à jour) à partir du temps t. Pour cela, il doit être suffisamment bon et avoir une faible incertitude.
Conclusion
Nous savons maintenant comment suivre un obstacle dans le temps. Le processus général consiste à détecter les obstacles à l’aide d’un algorithme de détection d’objet, à faire correspondre ces box avec les anciennes box que nous avons en utilisant l’algorithme hongrois, puis à prévoir les positions futures ou réelles des box en utilisant des filtres de Kalman. A partir de là, nous pourrions utiliser l’apprentissage machine pour prédire le comportement ou les trajectoires futures, nous pourrions être en mesure d’estimer ce qu’un obstacle a fait au cours des 10 dernières secondes. Cet outil est puissant et le suivi devient non seulement possible, mais aussi très précis. Les vitesses peuvent être estimées et un large éventail de possibilités s’offre à vous.
Jeremy Cohen
→ Ajoutez moi sur LinkedIn abonnez vous !
Rejoignez Paris School of AI pour apprendre l’IA et rencontrez des personnes pertinentes dans le secteur !
