Tracking prédictif

Un moyen simple d'effectuer du tracking est de le faire par prédiction. En regardant la position des détections entre les frames et en les comparant, on peut déterminer si la même personne est vue sur les différentes images, et ainsi suivre ses déplacements.

Il y a plusieurs moyens de faire cela, chaque méthode ayant une complexité et des capacités différentes.

Algorithme naïf

Une idée d'algorithme assez naïf pour un tracking visuel simple serait de simplement calculer la distance des détections entre elles entre deux images consécutives, et si elles sont suffisamment proches on peut considérer qu'elles correspondent à la même personne.
Un tel algorithme est assez simple à écrire, mais il ne serait pas très bon dans la pratique, car deux détections trop proches de deux personnes différentes pourraient fusionner si une seule personne est détecter sur l'image suivante (par exemple dans le cas où une personne passe devant l'autre). Il est donc plus intéressant d'utiliser d'autres techniques de tracking, plus complexes mais plus performantes.

Algorithme hongrois

L'algorithme hongrois est "un algorithme d'optimisation combinatoire, qui résout le problème d'affectation en temps polynomial". C'est un algorithme qui permet de trouver un couplage parfait de poids optimum dans un graphe biparti dont les arêtes sont valuées (plus d'informations ici).

Pour le problème du tracking, on peut appliquer cet algorithme en modélisant les deux sous ensemble du graphe biparti comme étant les détections de la frame précédente et actuelle, puis en reliant chaque détection de la frame précédente à toutes celles de la frame suivante avec des arrêtes dont le poids est la distance sur l'image entre les centres des deux détections. L'algorithme nous donne donc une correspondance optimale entre les détections. En filtrant les résultats de l'algorithme, on a un algorithme plus précis que l'algorithme naïf pour faire du tracking.

Cette solution fonctionne mieux que la précédente, mais peut toujours souffrir des mêmes problèmes.

C'est cette algorithme qui est utilisé pour le tracking de détections sur les caméras OAK-D, en le combinant avec différentes amélioration comme un filtre de Kalman ou l'utilisation rudimentaire du visuel, ainsi qu'en offrant la possibilité d'y ajouter du tracking temporel.

Tracking temporel

Les algorithmes précédents sont fonctionnels, mais n'effectuent leurs calculs que sur la position des détections précédentes et actuelles. Un moyen d'améliorer les résultats est de se baser sur les dernières positions connues d'une détection pour prédire sa position actuelle, et ainsi comparer les nouvelles détections avec la prédiction plutôt qu'avec les précédentes. Cette méthode apporte deux grands avantages :

• Si l'on a peu d'images par secondes, les algorithmes précédents auraient du mal à associer les détections car elles seront trop éloignées; si le déplacement sur l'image de la détection est à peu près régulier, cette méthode fonctionnera bien mieux
• Si une personne passe derrière un obstacle, et que sa détection est perdue, au lieu de simplement indiquer que la détection à disparue, l'algorithme peut extrapoler le déplacement et retrouver la personne lorsqu'elle réapparaît

Cet algorithme est donc potentiellement bien plus performant que les deux précédents, mais peu ajouter une complexité plus ou moins grande selon la façon dont on prédit les trajectoires des détections.

Dans le projet

Dans ce projet, la méthode de tracking visuel utilisée est celle fournie par la caméra, donc se basant sur un filtre de Kalman et l'algorithme hongrois, sans paramètres supplémentaires pour améliorer la prédiction car d'après nos essais, le filtre de Kalman fournissant déjà une prédiction de la position de la détection, il ne nous a pas semblé nécessaire de complexifier le tracking pour un gain non significatif de précision.