Retour à la bibliothèque
arXiv 2020IJCV 2021Suivi multi-objetsNotes de lecture

HOTA

Renvoyer dos à dos

Article original

HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking

Auteurs de l’article

Jonathon Luiten · Aljosa Osep · Patrick Dendorfer …

Afficher les 7 auteurs

Jonathon Luiten · Aljosa Osep · Patrick Dendorfer · Philip Torr · Andreas Geiger · Laura Leal-Taixe · Bastian Leibe

Premier dépôt sur arXiv
arXiv:2009.07736
Citer cet article · BibTeX

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

@misc{multiobjecttrackinghota2020,
  title = {{HOTA: A Higher Order Metric for Evaluating Multi-Object Tracking}},
  author = {Jonathon Luiten and Aljosa Osep and Patrick Dendorfer and Philip Torr and Andreas Geiger and Laura Leal-Taixe and Bastian Leibe},
  year = {2020},
  eprint = {2009.07736},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.07736}
}
Sur cette page

Après quelques articles sur le suivi, vous connaissez sans doute bien le chiffre MOTA. SORT l'utilise, DeepSORT aussi, et c'est encore lui qui occupe la première colonne du tableau principal de Tracktor et de FairMOT.

Pourtant, nous l'avons vu avec DeepSORT, 45 % de changements d'identité (ID switches) en moins ne rapportent que 1.6 point de MOTA. FairMOT a aussi montré, par une expérience, qu'un modèle entraîné uniquement à la détection, avec des caractéristiques re-ID presque aléatoires, obtient un MOTA plus élevé qu'un modèle entraîné sur les deux tâches à la fois.

Une métrique censée mesurer le « suivi » semble peu sensible à la question de savoir si l'on suit la bonne personne.

Cet article vient de la RWTH Aachen, de l'Université technique de Munich, d'Oxford et de Tübingen ; parmi les auteurs figurent des mainteneurs de MOTChallenge, ainsi qu'Andreas Geiger, le créateur de KITTI. Ils démontent un à un MOTA, IDF1 et Track-mAP, puis proposent une nouvelle métrique, HOTA (Higher Order Tracking Accuracy). L'influence de l'article se lit dans les tableaux principaux des notes qui suivent, où HOTA est devenu la métrique principale de la génération ByteTrack et OC-SORT.

Définir le problème

Le suivi multi-objets doit réussir trois choses :

  1. Détection : trouver dans chaque image les objets à trouver, ni plus ni moins.
  2. Localisation : des boîtes précises.
  3. Association : un même objet doit recevoir le même identifiant à des instants différents, et deux objets différents ne doivent pas partager un identifiant.

Une bonne métrique doit refléter ces trois aspects à la fois, avec des poids raisonnables. Les auteurs examinent d'abord les deux métriques les plus utilisées à l'époque.

MOTA

MOTA apparie une à une, dans chaque image, les boîtes prédites et les boîtes de vérité terrain (IoU d'au moins 0.5). Les paires formées sont des vrais positifs (TP), les prédictions en trop des faux positifs (FP), et les boîtes de vérité terrain restées sans partenaire des détections manquées (FN). Les erreurs d'association sont comptées comme des changements d'identité (IDSW) ; chaque fois que l'identifiant prédit apparié à un objet réel diffère de celui de son appariement précédent, on en compte un.

MOTA=1−∣FN∣+∣FP∣+∣IDSW∣∣gtDet∣\text{MOTA} = 1 - \frac{|\text{FN}| + |\text{FP}| + |\text{IDSW}|}{|\text{gtDet}|}

Le dénominateur est le nombre total de boîtes de vérité terrain.

IDF1

IDF1 n'apparie pas image par image ; il apparie une à une des trajectoires prédites entières avec des trajectoires réelles entières, en choisissant la combinaison qui maximise le recouvrement. Sur les portions où les trajectoires appariées se recouvrent, on compte des IDTP ; toutes les autres boîtes de vérité terrain sont des IDFN, et toutes les autres boîtes prédites des IDFP :

IDF1=∣IDTP∣∣IDTP∣+0.5 ∣IDFN∣+0.5 ∣IDFP∣\text{IDF1} = \frac{|\text{IDTP}|}{|\text{IDTP}| + 0.5\,|\text{IDFN}| + 0.5\,|\text{IDFP}|}

Une même personne, deux façons de la suivre

Faisons le calcul sur l'exemple de la première figure de l'article.

Fig. 1 de l'article : une trajectoire réelle de 100 images (trait noir épais) et les sorties de trois traqueurs. A ne suit que les 50 premières images, avec un seul identifiant ; B a deux trajectoires de 35 images chacune ; C couvre les 100 images, mais en quatre segments de 25 images, avec quatre identifiants différents. Scores à droite : DetA, MOTA, HOTA, IDF1 et AssA valent 50 %, 50 %, 50 %, 67 % et 50 % pour A ; 70 %, 69 %, 50 %, 52 % et 35 % pour B ; 100 %, 97 %, 50 %, 25 % et 25 % pour C. En bas, des flèches indiquent que MOTA penche de plus en plus vers la mesure de la détection, et IDF1 vers celle de l'association.
Fig. 1 de l'article de Luiten et al., extraite de la page 1 du PDF, licence arXiv, citation académique.

La scène ne contient qu'une personne, présente sur 100 images. Prenons les traqueurs A et C :

  • A suit les 50 premières images avec le même identifiant du début à la fin, puis rate complètement les 50 suivantes.
  • C suit la personne sur chaque image, mais change d'identifiant toutes les 25 images, soit quatre identifiants au total.

Lequel est le meilleur ?

Commençons par MOTA. A a 50 détections manquées, aucun faux positif et aucun changement d'identité, soit 1−50/100=50%1 - 50/100 = 50\%. C n'a ni détection manquée ni faux positif, mais 3 changements d'identité, soit 1−3/100=97%1 - 3/100 = 97\%.

Pour MOTA, C est bien meilleur. Changer trois fois d'identifiant ne coûte que 3 points.

Passons à IDF1. L'unique trajectoire de A est appariée à la trajectoire réelle ; IDTP = 50, IDFN = 50, IDFP = 0, et IDF1 = 50/(50+25)=67%50 / (50 + 25) = 67\%. C ne peut apparier qu'un seul segment de 25 images ; IDTP = 25, les 75 autres boîtes de vérité terrain sont des IDFN, et les 75 boîtes prédites des trois autres segments des IDFP, d'où IDF1 = 25/(25+37.5+37.5)=25%25 / (25 + 37.5 + 37.5) = 25\%.

Pour IDF1, c'est A qui est bien meilleur. Que C ait suivi la personne sur chaque image n'est presque pas pris en compte.

Chaque métrique choisit son camp, et toutes deux de façon extrême.

Résoudre le problème

HOTA vise à mesurer équitablement, en un seul score, la détection, l'association et la localisation, tout en restant décomposable pour voir d'où viennent les erreurs.

D'abord, apparier image par image, comme MOTA

Comme MOTA, HOTA apparie une à une, dans chaque image, les boîtes prédites et les boîtes de vérité terrain, à condition que la similarité de localisation SS (l'IoU, par exemple) atteigne au moins un seuil α\alpha. Les paires formées sont des TP, le reste des FP et des FN.

Le score de détection est l'indice de Jaccard classique :

DetAα=∣TP∣∣TP∣+∣FN∣+∣FP∣\text{DetA}_\alpha = \frac{|\text{TP}|}{|\text{TP}| + |\text{FN}| + |\text{FP}|}

Puis demander à chaque TP à quel point sa trajectoire est juste

La partie association est l'apport nouveau de l'article. Pour chaque TP apparié, noté cc, les auteurs définissent trois ensembles :

Fig. 2 de l'article : TPA, FPA et FNA illustrés autour d'un TP (l'appariement c, entouré en rouge). Les grands cercles bleu foncé forment la trajectoire réelle à laquelle appartient c, les petits points noirs la trajectoire prédite à laquelle appartient c. Les cadres en pointillés verts sont les TPA, c'est-à-dire les appariements dont l'identifiant réel et l'identifiant prédit sont tous deux ceux de c, au nombre de cinq ; les cadres en pointillés jaunes sont les FPA, les prédictions qui ont le même identifiant prédit que c, mais un identifiant réel différent ou aucun objet correspondant, au nombre de quatre ; les cadres en pointillés rouge orangé sont les FNA, les boîtes de vérité terrain qui ont le même identifiant réel que c, mais ont reçu un autre identifiant prédit ou n'ont pas été détectées, au nombre de trois.
Fig. 2 de l'article de Luiten et al., extraite de la page 7 du PDF, licence arXiv, citation académique.
  • TPA (True Positive Associations) : les TP qui ont le même identifiant réel et le même identifiant prédit que cc. Ce sont les instants où « la même personne est traitée par le traqueur comme la même personne ».
  • FNA (False Negative Associations) : les boîtes de vérité terrain qui ont le même identifiant réel que cc, mais qui ont reçu un autre identifiant prédit ou n'ont pas été détectées du tout. C'est la même personne, et pourtant le traqueur ne l'a pas reconnue.
  • FPA (False Positive Associations) : les boîtes prédites qui ont le même identifiant prédit que cc, mais qui appartiennent en réalité à quelqu'un d'autre, ou ne correspondent à aucun objet. Le traqueur croit avoir affaire à la même personne, alors que ce n'est pas elle.

Dans la figure, cc a cinq TPA, quatre FPA et trois FNA. Son score d'association est, lui aussi, un indice de Jaccard :

A(c)=∣TPA(c)∣∣TPA(c)∣+∣FNA(c)∣+∣FPA(c)∣\mathcal{A}(c) = \frac{|\text{TPA}(c)|}{|\text{TPA}(c)| + |\text{FNA}(c)| + |\text{FPA}(c)|}

Avec les chiffres de la figure :

A(c)=55+3+4≈0.42\mathcal{A}(c) = \frac{5}{5 + 3 + 4} \approx 0.42

La moyenne des scores d'association de tous les TP donne l'exactitude d'association :

AssAα=1∣TP∣∑c∈TPA(c)\text{AssA}_\alpha = \frac{1}{|\text{TP}|}\sum_{c \in \text{TP}} \mathcal{A}(c)

Deux scores, une moyenne géométrique

HOTAα=∑c∈TPA(c)∣TP∣+∣FN∣+∣FP∣=DetAα⋅AssAα\begin{aligned} \text{HOTA}_\alpha &= \sqrt{\frac{\sum_{c \in \text{TP}} \mathcal{A}(c)}{|\text{TP}| + |\text{FN}| + |\text{FP}|}} \\ &= \sqrt{\text{DetA}_\alpha \cdot \text{AssA}_\alpha} \end{aligned}

Les auteurs parlent de « double Jaccard ». La couche extérieure est le Jaccard de la détection, mais au numérateur, chaque TP ne compte pas pour 1 ; il est multiplié par son propre score d'association.

Revenons à l'exemple de tout à l'heure.

Pour A, DetA vaut 50/(50+50+0)=50%50 / (50 + 50 + 0) = 50\%. Chaque TP a 50 TPA ; les FNA sont les 50 boîtes de vérité terrain de la fin, jamais suivies, et il n'y a aucun FPA. Chaque score d'association vaut donc 50/10050/100, et AssA vaut aussi 50 %. HOTA =0.5×0.5=50%= \sqrt{0.5 \times 0.5} = 50\%.

Pour C, DetA vaut 100 %. Le segment auquel appartient chaque TP ne dure que 25 images, d'où 25 TPA ; les 75 autres images de la même personne ont reçu d'autres identifiants et sont toutes des FNA. Chaque score d'association vaut 25 %, et AssA aussi. HOTA =1×0.25=50%= \sqrt{1 \times 0.25} = 50\%.

Les deux traqueurs sont à égalité. A n'a suivi que la moitié du parcours, mais sans jamais se tromper de personne ; C a tout suivi, mais en changeant sans cesse d'identifiant. HOTA ne favorise aucun des deux et les renvoie dos à dos.

Enfin, intégrer la localisation

Tous les calculs ci-dessus se font à un seuil de localisation α\alpha fixé. Pour tenir compte aussi de la précision des boîtes, HOTA est calculé à chacun des 19 seuils α=0.05,0.10,…,0.95\alpha = 0.05, 0.10, \ldots, 0.95, puis moyenné :

HOTA=∫01HOTAα dα≈119∑α∈{0.05,…,0.95}HOTAα\begin{aligned} \text{HOTA} &= \int_0^1 \text{HOTA}_\alpha \, d\alpha \\ &\approx \frac{1}{19}\sum_{\alpha \in \{0.05, \ldots, 0.95\}} \text{HOTA}_\alpha \end{aligned}

L'appariement est refait à chaque seuil. Plus les boîtes sont précises, plus il reste de TP appariés aux seuils élevés, et plus le score final est haut.

Les auteurs précisent que DetA et AssA doivent d'abord être combinés en HOTAα\text{HOTA}_\alpha à chaque α\alpha, avant la moyenne sur α\alpha ; l'ordre ne peut pas être inversé. C'est pourquoi le HOTA des tableaux de l'article n'est en général pas exactement la moyenne géométrique des DetA et AssA de ces mêmes tableaux.

Décomposer

HOTA se décompose jusqu'à cinq sous-métriques, chacune associée à un type d'erreur :

  • DetRe =∣TP∣/(∣TP∣+∣FN∣)= |\text{TP}| / (|\text{TP}| + |\text{FN}|) : les détections manquées.
  • DetPr =∣TP∣/(∣TP∣+∣FP∣)= |\text{TP}| / (|\text{TP}| + |\text{FP}|) : les faux positifs.
  • AssRe : la moyenne de A(c)\mathcal{A}(c) sans les FPA. Si une personne est découpée en plusieurs trajectoires, AssRe est bas.
  • AssPr : la moyenne de A(c)\mathcal{A}(c) sans les FNA. Si une trajectoire s'étend sur plusieurs personnes, AssPr est bas.
  • LocA : la similarité de localisation moyenne de tous les TP, elle aussi moyennée sur les différents α\alpha.

Cette décomposition permet à chacun de choisir ce qui compte pour son application. Les auteurs donnent des exemples. L'analyse du mouvement humain, l'analyse de foule ou l'analyse de compétitions sportives tiennent à ce que les identités soient suivies correctement du début à la fin ; AssRe et AssPr y comptent davantage. Un système d'aide à la conduite doit trouver chaque piéton, sans pour autant faire d'écart d'urgence pour une personne qui n'existe pas ; DetRe et DetPr y comptent davantage. En vidéosurveillance, on préfère en général trop signaler plutôt que rater quelqu'un.

Fig. 16 de l'article : MOTA, IDF1 et HOTA tracés en fonction de DetA (rangée du haut) et d'AssA (rangée du bas) pour tous les traqueurs publiés sur MOT17, avec le coefficient de détermination R² en haut à gauche de chaque case. MOTA : 0.96 avec DetA, 0.46 avec AssA ; IDF1 : 0.58 avec DetA, 0.97 avec AssA ; HOTA : 0.67 avec DetA, 0.94 avec AssA.
Fig. 16 de l'article de Luiten et al., extraite de la page 23 du PDF, licence arXiv, citation académique.

Cette figure confronte les trois métriques à DetA et à AssA sur MOT17. MOTA suit presque uniquement la détection (R2=0.96R^2 = 0.96) et n'a qu'un lien faible avec l'association (0.46) ; IDF1 fait exactement l'inverse (0.58 et 0.97) ; HOTA est nettement lié aux deux (0.67 et 0.94).

Si HOTA est plus fortement lié à AssA, ce n'est pas parce que l'association pèse plus lourd ; les deux ont le même poids. La raison est que ces traqueurs utilisent tous le même jeu de détections publiques ; leurs scores de détection sont proches, et leurs écarts viennent surtout de l'association.

Discussion

Les neuf problèmes de MOTA

Les auteurs relèvent neuf problèmes de MOTA. Voici les plus convaincants :

  1. La détection pèse bien plus lourd que l'association. Parmi les dix premiers du classement MOT17 au 1er avril 2020, le rapport entre le nombre de FN + FP et celui d'IDSW va de 42.3 à 186.4, avec une moyenne de 98.6. Les auteurs font aussi une régression linéaire sur 175 traqueurs ; MODA, qui ne regarde que la détection (MOTA sans le terme IDSW), explique 99.4 % de la variance de MOTA, contre 23.7 % seulement pour IDSW.
  2. La précision pèse bien plus lourd que le rappel. Sans IDSW, MOTA peut se réécrire DetRe⋅(2−1/DetPr)\text{DetRe} \cdot (2 - 1/\text{DetPr}) ; il est linéaire en rappel, mais hyperbolique en précision. Une précision un peu plus faible fait chuter le score bien plus qu'un rappel un peu plus faible. Cela pousse tout le monde à relever le seuil de détection, en préférant rater des objets plutôt que produire des faux positifs.
  3. IDSW ne regarde que l'étape précédente. Un changement d'identité vérifie seulement si l'identifiant actuel est le même que le précédent ; il ne voit pas dans quelle mesure toute la trajectoire est alignée. Quand un traqueur se trompe puis se corrige de lui-même, MOTA compte aussi la correction comme un IDSW, ce qui revient à le pénaliser deux fois.
  4. Le transfert d'identité n'est pas pénalisé. Si une trajectoire prédite saute de A à B, ce n'est pas un IDSW tant que ni A ni B ne changent d'identifiant. L'exemple de l'article est une vidéo de deux images seulement ; une personne découpée en deux trajectoires donne un MOTA de 0.5, tandis que deux personnes différentes fusionnées en une seule trajectoire donnent un MOTA parfait de 1.0.
  5. Il dépend de la fréquence d'images. Prenons une même trajectoire de 2.5 secondes, avec un changement d'identité au milieu. Évaluée à 40 FPS, le dénominateur compte 100 boîtes et MOTA vaut 0.99 ; évaluée à 4 FPS, il n'y a plus que 10 boîtes et MOTA vaut 0.90. HOTA vaut 1×0.5≈0.707\sqrt{1 \times 0.5} \approx 0.707 dans les deux cas.
  6. Il n'a pas de borne inférieure. Les faux positifs peuvent augmenter sans limite, et MOTA peut descendre jusqu'à moins l'infini. Face à un MOTA négatif, difficile de dire ce qu'il représente.

Les problèmes d'IDF1

IDF1 a été conçu à l'origine pour le suivi multi-caméras. Son problème central est qu'il n'autorise qu'un seul ensemble optimal d'appariements de trajectoires. Pour une trajectoire non retenue, aussi bien suivie soit-elle, chaque détection correcte compte comme un IDFP et fait baisser le score. IDF1 n'est donc pas monotone vis-à-vis de la détection ; une meilleure détection peut dégrader le score.

Cela explique aussi pourquoi beaucoup de nouveaux benchmarks gardent MOTA. La détection est une part essentielle du suivi, et IDF1 la mesure mal.

Pourquoi Jaccard, pourquoi la racine carrée

La section 7 de l'article examine plusieurs choix de conception.

  • Jaccard plutôt que F1 ou MODA. Les auteurs montrent par un exemple que seule la forme de Jaccard garantit la monotonie ; une détection correcte de plus fait toujours monter le score, et intervertir prédictions et vérité terrain donne le même résultat. Pour certains rapports de longueur, F1 classe plus haut un résultat moins bon, et MODA n'est pas symétrique.
  • Les trois rôles de la racine carrée. D'abord, elle ramène les valeurs de HOTA dans une plage proche de celles, familières, de MOTA et d'IDF1. Ensuite, elle fait de HOTA la moyenne géométrique de la détection et de l'association ; si l'une des deux tend vers zéro, le score total aussi. Enfin, elle compense un double comptage. Le score d'association contient déjà les FN et les FP des trajectoires appariées ; sans la racine, ces erreurs seraient pénalisées deux fois. En suivi mono-objet, avec un seul objet, DetA et AssA sont identiques, et après la racine carrée, HOTA vaut exactement un indice de Jaccard.
  • On ne peut pas se passer de DetA. Les FN et les FP qui n'appartiennent à aucune trajectoire appariée n'apparaissent pas dans AssA ; il faut DetA pour les pénaliser. De plus, AssA seul n'est pas monotone ; ajouter un TP mal associé fait baisser la moyenne.

Et les humains, qu'en pensent-ils ?

Enfin, les auteurs ont mené une étude utilisateur. Ils ont découpé les sept vidéos de test de MOT17 en 36 extraits de 6 secondes, sélectionné des paires de traqueurs sur lesquelles deux métriques étaient en désaccord, puis montré aux participants les deux résultats de suivi en leur demandant de choisir le meilleur.

L'étude a réuni 230 personnes, dont 62 spécialistes du suivi multi-objets et 122 spécialistes de la vision par ordinateur, pour un total de 2075 comparaisons, avec en moyenne 2 minutes 13 secondes par comparaison.

Sans compter les votes d'égalité, face à MOTA, 61.6 % des participants donnent raison à HOTA ; face à IDF1, la proportion est de 72.0 % ; entre MOTA et IDF1, c'est à peu près moitié-moitié. Chez les seuls spécialistes du suivi multi-objets, HOTA l'emporte sur MOTA dans 79.3 % des cas, et sur IDF1 dans 85.9 % des cas.

La suite

HOTA a été adopté rapidement. En février 2021, le classement de suivi de KITTI passe au classement par HOTA, avec un code d'évaluation tiré de TrackEval, que maintiennent les auteurs ; de nouveaux benchmarks comme DanceTrack prennent aussi HOTA comme métrique principale. ByteTrack, OC-SORT, StrongSORT et BoT-SORT, que nous lirons plus loin, placent tous HOTA, MOTA et IDF1 côte à côte dans leur tableau principal.

D'autres estiment que HOTA n'est pas le dernier mot. En 2021, Jack Valmadre, Alex Bewley (oui, l'auteur de SORT) et leurs collègues de Google Research proposent ALTA, une métrique de suivi locale dans le temps. Pour eux, beaucoup d'applications tolèrent un certain niveau d'erreurs d'association, et l'importance relative de la détection et de l'association devrait pouvoir se régler ; ils prennent la longueur de la fenêtre temporelle comme bouton de réglage. HOTA fixe le partage à moitié-moitié ; c'est un choix, mais pas le seul possible.

Conclusion

On apparie d'abord image par image ; pour chaque boîte appariée, on mesure ensuite la justesse de l'association sur toute la trajectoire ; enfin, on prend la moyenne géométrique de la détection et de l'association, puis la moyenne sur 19 seuils de localisation. Voilà HOTA. Il se décompose en cinq sous-métriques : rappel de détection, précision de détection, rappel d'association, précision d'association et localisation.

Désormais, quand vous lirez les tableaux des articles de suivi, ne regardez pas seulement la colonne HOTA ; jetez aussi un œil à DetA et AssA. Quand le HOTA d'une méthode progresse, ces deux colonnes disent au premier coup d'œil si c'est le détecteur qui a été remplacé par un meilleur, ou si l'association s'est vraiment améliorée.

MOTA dit que changer trois fois d'identifiant ne coûte que trois points ; IDF1 dit que suivre la personne de bout en bout ne compte pas pour grand-chose.

HOTA leur répond qu'ils ont raison tous les deux, et tort tous les deux.