Suivi temporel des individus dans une vidéo grâce à l’algorithmique

Source: Deep Learning on Medium

Suivi temporel des individus dans une vidéo grâce à l’algorithmique

Introduction

Le suivi des individus dans une vidéo peut être appliqué à de nombreux domaines différents. Notamment, les systèmes de sécurité se basent sur ces algorithmes et sur des techniques d’identification pour obtenir le trajet d’un individu et analyser son mouvement. D’autre part, les magasins et centres commerciaux peuvent utiliser ce type de technologie pour collecter des données afin d’améliorer leur stratégie commerciale.

La problématique principale sera alors de suivre le mouvement de tous les clients à travers plusieurs caméras afin d’étudier leur comportement. Nous avons choisi de vous présenter une technique appelée SORT¹ (“Simple Online Realtime Tracking”) permettant de suivre plusieurs individus à partir du flux vidéo d’une seule caméra.

Etape 1 — Détection d’individus

Prenons le cas d’une caméra qui filme plusieurs individus en même temps. Pour arriver à suivre chaque personne à chaque instant, SORT¹ se base tout d’abord sur un algorithme de détection. Cet algorithme sera appliqué sur chaque image du flux vidéo afin de localiser les individus à chaque instant. L’algorithme définira alors des rectangles localisant chaque individu dans l’image appelés “bounding box”.

L’approche n’est pas limitée à l’usage d’une technique de détection spécifique. En effet, plusieurs détecteurs d’individus peuvent être utilisés, allant des détecteurs qui utilisent des approches traditionnelles (extraction des descripteurs puis classification de chaque région de l’image) aux détecteurs basée sur le deep learning comme YOLO² ou Faster RCNN³. Cependant, la précision de SORT dépend beaucoup de celle de l’algorithme de détection.

Detection des personnes avec YOLO²

A ce stade, nous arrivons donc à détecter que la vidéo présente 5 individus; vous noterez le pourcentage de précision d’être un humain au dessus de chaque rectangle.

Il sera donc important de donner un nom à chacun de ces humains pour suivre leur comportement. Exemple: Humain 1 a effectué telle action, alors que Humain 2 à fait autre chose.

Etape 2 — La mise en correspondance

Après la détection, la deuxième étape sera de suivre le trajet de chaque personne au fil du temps, d’une image à la suivante. Pour cela une correspondance doit être réalisée entre les personnes détectées dans l’image précédente et celles détectées dans l’image courante. Pour établir cette correspondance SORT¹, dans sa première version, utilise principalement l’information temporelle modélisée par un filtre de Kalman⁴. En d’autres termes, il se base sur le principe qu’une personne détectée dans une région de l’image actuelle sera présente dans une région voisine de l’image suivante.

Le suivi des personnes par SORT

Chaque personne est représentée par sa “bounding box” avec un vecteur x comme suit:

u et v sont les coordonnées du centre de la bounding box, s est l’aire du rectangle, r est le rapport entre sa longueur et largeur. Le filtre de Kalman utilise un modèle de prédiction dit “à vitesse constante” afin de prédire la position de la personne dans l’image suivante. En d’autres termes, il estime la vitesse de variation de chaque paramètre (u, v ,s) et suppose que cette vitesse est constante pour un certain temps afin de l’utiliser pour la prédiction. Par exemple, si le centre de la bounding box se trouvant au pixel (200,200) dans l’image se déplace horizontalement avec une vitesse de 5 pixels par image, le modèle prédit une position de (205,200) dans l’image suivante.

Ainsi, nous récupérons des étapes précédentes d’une part la prédiction, issue du traitement des images précédentes, et d’autre part le résultat de l’algorithme de détection de personnes dans la nouvelle image. Le problème se réduit donc à faire correspondre les nouvelles détections aux prédictions les plus “proches”. L’approche considère que deux “bounding box” sont proches si le critère IOU (“Intersection Over Union”) est grand.

Ce critère quantifie le chevauchement entre deux “bounding box” A et B. En effet, c’est le rapport de leurs surface d’ intersection A∩B sur la surface de leurs union AB. Ce rapport tend vers 1 lorsque A et B sont coïncidentes et à zéro quand les deux “bounding box” ne se chevauchent pas.

Le calcul du critère IOU. source: http://ronny.rest/tutorials/module/localization_001/iou/

Pour établir la correspondance, SORT utilise une méthode itérative appelée la méthode hongroise (“The Hungarian Method⁵”), qui consiste à faire correspondre chaque détection à une personne. Pour ce faire, l’algorithme cherche à optimiser le coût total de correspondance , afin de faire correspondre les détections aux personnes dont l’IOU est grand.

SORT version 2

La première version de SORT¹ présente des difficultés pour suivre les gens quand il y a des occlusions (personnes cachées par d’autre personnes), car elle utilise seulement l’information temporelle. Afin de remédier a ce point faible, une deuxième version⁶ est proposée qui prend en compte l’apparence de chaque personne.

La principale nouveauté de cette version consiste à calculer un vecteur qui décrit l’apparence de chaque personne détectée pour gérer les cas difficiles. Ce vecteur est obtenu en utilisant un réseau de neurones profond (“Deep Neural Network”), mais d’autres approches moins coûteuses peuvent être utilisées pour le même objectif. Les 100 derniers vecteurs de chaque personne seront sauvegardés afin de décrire son apparence d’une manière plus robuste.

La distance entre le vecteur correspondant à la nouvelle détection j et chacun des 100 vecteurs d’une personne i sera calculée et la distance minimale sera prise comme le critère de similarité entre la nouvelle détection et cette personne.

Enfin, la méthode fusionne les deux critères (l’information temporelle et la similarité des apparences) afin de donner un seul coût à minimiser par la méthode hongroise, permettant de calculer la correspondance de la façon suivante:

d¹(i,j) est lié à l’IOU (modélisant l’information temporelle) entre la “bounding box” détectée j et la “bounding box” prédite i par le filtre de Kalman d’une personne. d²(i,j) est lié au critère de similarité des apparences. λ est un paramètre de balance qui règle l’ importance de chaque critère. Plus λ s’approche de 1, plus on donne de l’importance au critère temporel sur la décision finale et inversement.

Conclusion

Nous venons de vous présenter SORT, une approche qui peut être utilisée pour suivre n’importe quel type d’entité dans un flux vidéo, à condition qu’on ait un algorithme qui permet la détection de ce type d’entité. Cependant, cette approche ne peut pas suivre les personnes à travers plusieurs flux vidéos provenant de différentes cameras car la modélisation temporelle ne sera plus exploitable.

Nous aborderons dans les prochaines semaines le suivi temporel d’individus avec plusieurs flux vidéos, en nous appuyant sur le processus mis en place précédemment.