Retour à la bibliothèque
CVPR 2025Suivi multi-objetsNotes de lecture

TrackTrack

C'est réciproque

Article original

Focusing on Tracks for Online Multi-Object Tracking

Auteurs de l’article

Kyujin Shim · Kangwook Ko · Yujin Yang · Changick Kim

Publication
CVPR 2025Conférence
Citer cet article · BibTeX

La référence correspond à la version liée et cite les auteurs de l’article original.

@inproceedings{multiobjecttrackingtracktrack2025,
  title = {{Focusing on Tracks for Online Multi-Object Tracking}},
  author = {Kyujin Shim and Kangwook Ko and Yujin Yang and Changick Kim},
  year = {2025},
  booktitle = {CVPR},
  url = {https://doi.org/10.1109/CVPR52734.2025.01091},
  doi = {10.1109/CVPR52734.2025.01091}
}
Sur cette page

L'algorithme hongrois est le composant le plus courant des traqueurs. On lui donne une matrice de coûts entre trajectoires et détections, et il trouve l'appariement un à un de coût total minimal ; depuis SORT, presque tous les traqueurs « détecter puis associer » l'utilisent.

Cet algorithme a été conçu à l'origine pour le problème d'affectation, par exemple répartir des ouvriers entre des tâches au moindre coût total. Peu importe quelle tâche revient à quel ouvrier ; ce qui compte, c'est que l'ensemble soit le plus avantageux possible.

Kyujin Shim, Changick Kim et leurs collègues du KAIST estiment que le suivi n'est pas ce genre de problème. Les trajectoires et les boîtes de détection représentent les mêmes personnes, et chaque trajectoire a, dans l'image courante, une boîte de détection correcte. À chercher le coût total minimal, on finit parfois par échanger l'identité de deux personnes pour gagner un tout petit peu sur l'ensemble.

Définir le problème

0.01 d'écart, et les identités s'échangent

Figure 2 de l'article : un exemple d'occultation sur DanceTrack. Les trajectoires T2 et T3 se chevauchent ; à côté, la matrice de coûts entre quatre trajectoires et quatre boîtes de détection. (a) L'algorithme hongrois choisit T2–D4 et T3–D3 (cases jaunes encadrées de rouge) ; à l'image suivante, les identités de T2 et T3 sont échangées et un changement d'identité se produit. (b) TPA choisit T2–D3 et T3–D4 (cases jaunes encadrées de bleu), et les deux personnes sont suivies correctement. D4 est une boîte à score élevé supprimée par la NMS (en jaune).
Figure 2 de l'article de Shim et al., extraite de la page 2 du PDF, citation académique.

T1 avec D2 (0.16) et T4 avec D1 (0.18) ne font pas débat ; le problème se joue dans les quatre cases de T2, T3 et D3, D4 :

AppariementT2T3Coût total
Algorithme hongroisD4 : 0.48D3 : 0.331.15
TPAD3 : 0.10D4 : 0.721.16

Chiffres tirés de la Figure 2 de l'article ; coût total des quatre paires calculé pour cette note.

Les deux appariements ne diffèrent que de 0.01 en coût total. L'algorithme hongrois prend celui dont la somme est la plus petite ; or, dans cet appariement, T2, qui n'est qu'à 0.10 de D3, la plus petite case de tout le tableau, se voit attribuer D4, à 0.48.

D3 ressemble le plus à T2, et T2 ressemble le plus à D3 ; l'attirance est réciproque, et cette paire a très peu de chances d'être fausse. À la séparer de force pour gagner 0.01 sur l'ensemble, on aboutit à l'échange des identités.

Les boîtes à faible score passent après

L'autre problème vient de l'appariement en plusieurs étapes qui s'est imposé depuis ByteTrack. Les boîtes à score élevé sont d'abord appariées aux trajectoires, et les boîtes à faible score n'ont leur tour qu'avec les trajectoires restées sans partenaire.

Or une personne occultée a souvent un score de détection plutôt bas. Pour une trajectoire donnée, la boîte la plus appropriée peut justement être une boîte à faible score, mais elle s'est fait souffler la place dès le premier tour par une boîte à score élevé moins appropriée.

Plus extrême encore, il y a les boîtes supprimées par la NMS. Quand deux personnes se chevauchent fortement, la NMS supprime la boîte de l'une d'elles comme doublon. D4, dans la figure, est une boîte de ce genre ; son score est élevé, elle chevauche simplement trop une autre boîte. La plupart des traqueurs ne lui accordent plus un regard.

Résoudre le problème

TrackTrack repose sur deux stratégies : TPA (track-perspective-based association) pour l'appariement, et TAI (track-aware initialization) pour la création de nouvelles trajectoires. La méthode ne demande aucun entraînement supplémentaire.

TPA : toutes les boîtes ensemble, et seulement les paires réciproques

Figure 3 de l'article : le déroulement de TPA. À gauche, la matrice de coûts entre cinq trajectoires et six boîtes de détection ; en vert les boîtes à score élevé, en bleu les boîtes à faible score, en jaune les boîtes à score élevé supprimées par la NMS. Le premier tour trouve les cases qui sont à la fois le minimum de leur ligne et de leur colonne (encadrées de rouge) : T1–D6, T2–D2 et T4–D3. Une fois ces lignes et colonnes retirées, il reste la petite matrice de droite, où le second tour trouve T3–D1.
Figure 3 de l'article de Shim et al., extraite de la page 4 du PDF, citation académique.

TPA commence par mettre trois sortes de boîtes dans une même matrice de coûts : les boîtes à score élevé après NMS, les boîtes à faible score après NMS, et les boîtes à score élevé supprimées par la NMS. Les coûts des deux dernières reçoivent chacun une pénalité, qui les fait passer après les boîtes à score élevé à conditions égales, sans pour autant leur ôter toute chance.

Le coût lui-même reprend la combinaison de Hybrid-SORT : le recouvrement des boîtes, la distance cosinus entre caractéristiques d'apparence, la confiance de détection et l'écart d'angle entre directions de mouvement.

Ensuite, on cherche à plusieurs reprises toutes les paires « mutuellement minimales », c'est-à-dire les cases qui sont à la fois le minimum de leur ligne et le minimum de leur colonne, et sous le seuil. Toutes les paires trouvées sont validées, leurs lignes et colonnes retirées, et l'on cherche de nouveau dans la matrice restante. À chaque tour supplémentaire, le seuil se resserre un peu.

Déroulons la matrice de la figure :

  1. Premier tour. Le minimum de la ligne de T1 est D6 (0.1), et le minimum de la colonne de D6 est aussi T1 ; la paire est formée. Même chose pour T2–D2 et T4–D3. Le minimum de la ligne de T3 est D2 (0.2), mais le minimum de la colonne de D2 est T2 (0.1) ; T3 reste sans partenaire à ce tour.
  2. Second tour. Il reste T3, T5 et D1, D4, D5. Le minimum de la ligne de T3 est D1 (0.3), et dans la colonne de D1, la valeur de T3 est aussi inférieure au 0.9 de T5 ; la paire est formée.

Ce processus ressemble un peu à un speed dating. Quand deux personnes se trouvent chacune le meilleur choix de la salle, elles forment d'abord un couple ; les cas moins clairs attendent que les paires évidentes soient formées, puis choisissent parmi ceux qui restent.

En traitant d'abord les paires les plus sûres, on évite ce que fait l'algorithme hongrois, qui sépare la paire la plus évidente pour ménager l'ensemble.

TAI : qu'une nouvelle trajectoire ne percute pas une ancienne

Une fois l'appariement fait, les boîtes à score élevé restantes sont en général traitées comme de nouvelles personnes, et ouvrent de nouvelles trajectoires. Le problème, c'est que certaines de ces boîtes sont en réalité des détections en double de trajectoires existantes, ou des boîtes surnuméraires sur une personne occultée. Si on en fait de nouvelles trajectoires, on obtient une ribambelle de fausses trajectoires éphémères.

Figure 4 de l'article : schéma de TAI. À gauche, les boîtes bleue, verte et violette sont les trajectoires déjà appariées T1, T2 et T3 ; les boîtes en pointillés rouges sont les détections à score élevé restées sans partenaire, D1 à D4. Les trajectoires appariées servent d'ancres de confiance 1 et passent à la NMS avec ces détections ; D4 chevauche trop T1 et est supprimée, et des deux boîtes D1 et D3, qui se chevauchent, une seule est gardée. À droite, le résultat ; seules deux boîtes deviennent de nouvelles trajectoires, T4 et T5.
Figure 4 de l'article de Shim et al., extraite de la page 5 du PDF, citation académique.

TAI prend la position des trajectoires déjà appariées comme des boîtes de confiance 1, impossibles à supprimer, et refait une NMS avec les boîtes à score élevé restantes. Les boîtes qui chevauchent trop une trajectoire existante, ou une boîte de score plus élevé, sont supprimées. Seules les boîtes qui restent ouvrent de nouvelles trajectoires.

Le seuil de cette NMS peut s'ajuster selon la scène : plus bas, seuls les nouveaux objets très sûrs sont créés ; plus haut, on rate moins de vrais nouveaux venus dans les scènes encombrées.

Le processus complet

À chaque image, YOLOX-X détecte, un filtre de Kalman NSA prédit la position des trajectoires, puis TPA fait l'appariement. Les boîtes à score élevé restantes sont appariées une fois de plus avec les nouvelles trajectoires « nées depuis moins de trois images » ; ces nouvelles trajectoires sont souvent du bruit, des reflets par exemple, et les auteurs ne les laissent pas disputer les boîtes aux trajectoires confirmées. Enfin, TAI décide quelles boîtes peuvent ouvrir une nouvelle trajectoire.

Discussion

Ensembles de test

BenchmarkHOTA TrackTrack2e en ligne1er hors ligne
MOT1767.166.4 (ImprAsso)67.1 (CoNo-Link)
MOT2065.765.0 (AdapTrack)65.9 (CoNo-Link)
DanceTrack66.565.7 (Hybrid-SORT-ReID)63.8 (CoNo-Link)

MOT17 d'après la Table 1 de l'article, MOT20 d'après la Table 2, DanceTrack d'après la Table 3, tous sur les ensembles de test.

Sur les trois jeux de données, TrackTrack est premier parmi les méthodes en ligne, et fait jeu égal avec les méthodes hors ligne, qui ont besoin de voir toute la vidéo. SUSHI, hors ligne, obtient 66.5 sur MOT17 et 63.3 sur DanceTrack, en dessous de TrackTrack dans les deux cas. Sur MOT17, l'IDF1 est de 83.1 et l'AssA de 68.2 ; ce sont les métriques liées à l'association qui progressent le plus nettement.

Les auteurs insistent sur le fait d'« être bon sur tous les jeux de données ». Beaucoup de méthodes très fortes sur MOT17 décrochent sur DanceTrack, et inversement ; TrackTrack est aux avant-postes sur les trois.

Il faut toutefois noter que le détecteur est entraîné avec deux jeux de données de piétons supplémentaires, CrowdHuman et WiderPerson. SambaMOTR, de la même époque et sans données supplémentaires, obtient un HOTA de 67.2 sur DanceTrack, et ne figure pas dans les tableaux de comparaison de cet article.

Ablations

ConfigurationMOT17 HOTAMOT17 AssADanceTrack HOTADanceTrack AssA
Référence67.369.661.947.7
+ TPA68.572.062.949.1
+ TAI67.469.662.648.7
Les deux69.172.763.349.7

D'après la Table 4 de l'article, ensembles de validation.

La référence est l'approche courante : algorithme hongrois, appariement en plusieurs étapes, et nouvelle trajectoire dès qu'un score dépasse le seuil. TPA apporte davantage que TAI, avec 2.4 points d'AssA en plus sur MOT17.

TPA réunit en fait trois changements, que les auteurs examinent aussi séparément :

  1. Minimum mutuel ou algorithme hongrois. Toutes choses égales par ailleurs, en ne changeant que la méthode d'affectation, le HOTA passe de 68.1 à 69.1 sur MOT17 et de 61.6 à 63.3 sur DanceTrack.
  2. Appariement en une fois ou par étapes. Sur MOT17, le HOTA passe de 68.3 à 69.1 ; sur DanceTrack, il ne gagne que 0.1, et l'AssA perd même 0.1. Les étapes comptent peu sur DanceTrack.
  3. Utiliser ou non les boîtes supprimées par la NMS. Avec elles, le HOTA passe de 68.6 à 69.1 sur MOT17 et de 62.1 à 63.3 sur DanceTrack.

Les auteurs analysent aussi l'effet de l'occultation. En définissant la sévérité de l'occultation comme le nombre de chevauchements dont l'IoU dépasse 0.6, divisé par le nombre de chevauchements dont l'IoU dépasse 0.1, ils observent sur cinq vidéos de MOT17 et MOT20 que plus l'occultation est sévère, plus TrackTrack progresse par rapport à la référence. En cas d'occultation, la boîte la plus appropriée a toutes les chances d'être une boîte à faible score ou une boîte supprimée, et d'être séparée de sa trajectoire par l'algorithme hongrois ; TPA a précisément été conçu pour ce cas.

Vitesse

TPA doit parcourir toute la matrice à chaque tour, ce qui semble devoir le rendre plus lent que l'algorithme hongrois. À la mesure, il est au contraire un peu plus rapide. Hors post-traitement, on passe de 155.4 à 161.5 FPS sur MOT17, et de 394.8 à 408.4 sur DanceTrack. Les auteurs précisent que TPA est écrit en Python pur, alors que l'algorithme hongrois utilise une bibliothèque très optimisée ; il reste donc de la marge pour accélérer. L'article indique que le post-traitement est exclu de la mesure ; YOLOX-X n'atteint pas à lui seul cette vitesse, et ces chiffres reflètent l'étape d'association elle-même.

Conclusion

TrackTrack modifie la façon d'apparier trajectoires et boîtes de détection, le maillon le plus discret d'un traqueur.

L'algorithme hongrois cherche le coût total minimal ; TPA cherche à donner à chaque trajectoire la boîte qui lui convient le mieux. La plupart du temps, les deux donnent le même résultat ; la différence apparaît lors des occultations, où, de deux appariements qui ne diffèrent que de 0.01 en coût total, l'un échange l'identité de deux personnes et l'autre non. Comme on met en plus dans la comparaison les boîtes à faible score et celles supprimées par la NMS, une personne cachée a de meilleures chances d'être retrouvée.

Les deux stratégies ne demandent aucun entraînement et peuvent remplacer directement l'étape d'association d'un traqueur existant. Grâce à elles, TrackTrack permet à un traqueur en ligne, qui traite les images une à une, de faire jeu égal sur trois jeux de données avec des méthodes hors ligne qui voient toute la vidéo.