Retour à la bibliothèque
arXiv 2019CVPR 2020Suivi multi-objetsNotes de lecture

MPNTrack

Apprendre même à résoudre

Article original

Learning a Neural Solver for Multiple Object Tracking

Auteurs de l’article

Guillem Brasó · Laura Leal-Taixé

Publication
CVPR 2020Conférence
Premier dépôt sur arXiv
arXiv:1912.07515
Citer cet article · BibTeX

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

@misc{multiobjecttrackingmpntrack2019,
  title = {{Learning a Neural Solver for Multiple Object Tracking}},
  author = {Guillem Brasó and Laura Leal-Taixé},
  year = {2019},
  eprint = {1912.07515},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.07515}
}
Sur cette page

Le suivi hors ligne repose sur une vieille idée très élégante, qui consiste à représenter toutes les détections d'une vidéo sous la forme d'un graphe.

Chaque détection est un nœud, et une arête relie deux détections d'images différentes. Si deux détections appartiennent à la même trajectoire et se suivent dans le temps, l'arête est « active ». Le suivi devient alors un problème de partitionnement de graphe, qui consiste à trouver quelles arêtes activer.

L'approche standard de ce cadre se fait en deux temps. On attribue d'abord à chaque arête un coût, qui exprime la probabilité que les deux détections correspondent à la même personne ; on confie ensuite ces coûts à un solveur d'optimisation, qui trouve le meilleur partitionnement global.

En 2019, les recherches dans cette direction se partagent grosso modo en deux écoles. La première soigne la formulation du graphe, avec des optimisations de plus en plus complexes qui intègrent des relations d'ordre supérieur, mais des coûts le plus souvent conçus à la main. La seconde apprend de meilleurs coûts d'arête avec des modèles profonds, des réseaux siamois par exemple, puis les confie à un solveur simple ; mais ces coûts ne regardent que des paires, sans voir l'ensemble de la scène.

Guillem Brasó et Laura Leal-Taixé, de l'université technique de Munich, trouvent que chacune des deux voies ne fait que la moitié du chemin. Leal-Taixé compte parmi les auteurs de MOT16 et de Tracktor. Cette fois, tous deux veulent voir si le réseau peut apprendre même l'étape de « résolution ».

Définir le problème

Écrire le suivi comme un flot dans un réseau

Les auteurs partent du flot de coût minimal (min-cost flow) classique, en le simplifiant un peu.

On dispose de toutes les détections d'une vidéo, O={o1,…,on}O = \{o_1, \dots, o_n\}, où chaque détection oi=(ai,pi,ti)o_i = (a_i, p_i, t_i) contient l'image dans la boîte, les coordonnées de la boîte et l'horodatage. On construit un graphe non orienté où chaque détection est un nœud, et une arête relie toute paire de détections prises dans des images différentes. Autoriser les liaisons qui sautent des images permet de raccorder une trajectoire malgré une détection manquée au milieu.

Chaque arête (i,j)(i, j) porte une variable binaire y(i,j)y_{(i,j)}. Si les deux nœuds appartiennent à la même trajectoire et sont deux détections voisines de cette trajectoire, y(i,j)=1y_{(i,j)} = 1 ; sinon, elle vaut 0.

Les trajectoires ne peuvent pas partager de nœud ; yy doit donc satisfaire deux conditions. Chaque nœud a au plus une arête active vers le passé :

∑(j,i)∈E, tj<tiy(j,i)≤1\sum_{(j,i)\in E,\ t_j < t_i} y_{(j,i)} \le 1

Et au plus une vers le futur :

∑(i,k)∈E, ti<tky(i,k)≤1\sum_{(i,k)\in E,\ t_i < t_k} y_{(i,k)} \le 1

C'est une version simplifiée des contraintes de conservation du flot.

L'approche traditionnelle attribue à chaque arête un coût c(i,j)c_{(i,j)} et résout

min⁡y∑(i,j)∈Ec(i,j) y(i,j)\min_y \sum_{(i,j)\in E} c_{(i,j)}\, y_{(i,j)}

Sous les deux familles de contraintes ci-dessus, ce problème admet une solution optimale calculable en temps polynomial.

Prédire directement la réponse

Puisque ce qu'on veut au bout du compte, c'est yy, les auteurs renoncent à apprendre les coûts et apprennent directement yy.

Chaque arête devient un problème de classification binaire, dont l'étiquette est y(i,j)y_{(i,j)}. Tout le problème de suivi devient ainsi une tâche entraînable de bout en bout, où les caractéristiques et la « résolution » s'apprennent dans le même réseau.

Reste un problème. Un classifieur qui ne regarde que deux nœuds ne peut pas apprendre une information globale comme « cette personne a déjà été reliée à quelqu'un d'autre ». Pour que la décision sur chaque arête tienne compte de tout le graphe, les auteurs utilisent un réseau de passage de messages (Message Passing Network, MPN).

Résoudre le problème

Figure 1 de l'article : vue d'ensemble de la méthode. (a) En entrée, quelques images et leurs boîtes de détection. (b) Construction du graphe et encodage des caractéristiques : chaque détection est un nœud dont les caractéristiques d'apparence sont extraites par un CNN, et les nœuds d'images différentes sont tous reliés par des arêtes. (c) Passage de messages neuronal : les embeddings des nœuds et des arêtes sont propagés sur le graphe un nombre fixe de fois. (d) Classification des arêtes : chaque arête est classée active (en vert) ou inactive (pointillés rouges). (e) Sortie : les boîtes de détection d'une même trajectoire sont de la même couleur.
Figure 1 de l'article de Brasó et Leal-Taixé, extraite de la page 3 du PDF, licence arXiv, citation académique.

Le processus se divise en quatre étapes : construction du graphe, encodage des caractéristiques, passage de messages et classification des arêtes.

Caractéristiques initiales

L'embedding initial des nœuds vient de l'apparence. Les auteurs entraînent un ResNet-50 préentraîné sur ImageNet sur trois jeux de ré-identification de piétons, Market-1501, CUHK03 et DukeMTMC, ce qui donne des caractéristiques de re-ID de 256 dimensions ; trois couches entièrement connectées ajoutées ensuite compriment l'embedding des nœuds à 32 dimensions.

L'embedding initial des arêtes vient des relations géométriques. Pour deux boîtes de détection d'images différentes, (xi,yi,hi,wi)(x_i, y_i, h_i, w_i) et (xj,yj,hj,wj)(x_j, y_j, h_j, w_j), on calcule d'abord la position et la taille relatives :

2(xj−xi)hi+hj,2(yj−yi)hi+hj,log⁡hihj,log⁡wiwj\begin{aligned} &\frac{2(x_j - x_i)}{h_i + h_j},\quad \frac{2(y_j - y_i)}{h_i + h_j},\\ &\log\frac{h_i}{h_j},\quad \log\frac{w_i}{w_j} \end{aligned}

Le déplacement est divisé par la hauteur moyenne des deux boîtes, si bien que des personnes plus ou moins éloignées se comparent à la même échelle. On y ajoute l'écart temporel tj−tit_j - t_i et la distance euclidienne entre les deux caractéristiques de re-ID, et le tout passe dans un MLP qui donne l'embedding initial de l'arête.

Passage de messages

Dans un réseau de passage de messages ordinaire, chaque étape comprend deux mises à jour. On met d'abord à jour chaque arête avec ses deux nœuds :

h(i,j)(l)=Ne([hi(l−1), hj(l−1), h(i,j)(l−1)])h_{(i,j)}^{(l)} = \mathcal{N}_e\left(\left[h_i^{(l-1)},\ h_j^{(l-1)},\ h_{(i,j)}^{(l-1)}\right]\right)

On met ensuite à jour chaque nœud avec les arêtes qui le touchent. Chaque arête produit un message, et la somme de tous les messages (ou leur moyenne, ou leur maximum) donne le nouvel embedding du nœud.

Après LL répétitions, chaque nœud et chaque arête portent l'information située à une distance d'au plus LL, un peu comme le champ récepteur d'un CNN. La classification d'une arête, qui ne regardait que deux boîtes, peut désormais voir « quelles autres candidates entourent ces deux nœuds ».

Une mise à jour des nœuds sensible au temps

Figure 2 de l'article : schéma de la mise à jour des nœuds. (a) État initial : le nœud central 3 est à l'image t, avec les nœuds 1 et 2 dans les images passées et les nœuds 4 et 5 dans les images futures ; chaque arête a calculé le message qu'elle doit transmettre au nœud 3. (b) Mise à jour classique : les quatre messages sont tous additionnés. (c) Mise à jour sensible au temps : les deux messages du passé et les deux messages du futur sont additionnés séparément, puis concaténés et envoyés dans un MLP.
Figure 2 de l'article de Brasó et Leal-Taixé, extraite de la page 5 du PDF, licence arXiv, citation académique.

La principale modification d'architecture de l'article porte sur la mise à jour des nœuds.

Revenons aux contraintes du flot, selon lesquelles chaque nœud a au plus une liaison vers le passé et au plus une vers le futur. Mais la mise à jour ordinaire mélange et additionne les messages de tous les voisins ; une fois la somme faite, le nœud ne peut plus distinguer les messages venus du passé de ceux venus du futur, et il lui devient difficile de savoir si les contraintes sont violées.

Les auteurs inscrivent directement la structure temporelle du graphe de MOT dans la règle de mise à jour. Pour le nœud ii, les messages des voisins passés et futurs sont calculés par deux MLP différents. Les voisins passés j∈Nipastj \in N_i^{past} utilisent

m(i,j)(l)=Nvpast([hi(l−1), h(i,j)(l), hi(0)])m_{(i,j)}^{(l)} = \mathcal{N}_v^{past}\left(\left[h_i^{(l-1)},\ h_{(i,j)}^{(l)},\ h_i^{(0)}\right]\right)

Les voisins futurs utilisent Nvfut\mathcal{N}_v^{fut}. Les deux côtés sont additionnés séparément pour donner hi,past(l)h_{i,past}^{(l)} et hi,fut(l)h_{i,fut}^{(l)}, qui sont concaténés puis envoyés dans un dernier MLP :

hi(l)=Nv([hi,past(l), hi,fut(l)])h_i^{(l)} = \mathcal{N}_v\left(\left[h_{i,past}^{(l)},\ h_{i,fut}^{(l)}\right]\right)

Dans la formule, hi(0)h_i^{(0)} est l'embedding initial, transmis à chaque étape pour que le réseau n'oublie pas les caractéristiques d'origine, même après de nombreuses propagations. La mise à jour des arêtes reçoit de même les caractéristiques initiales des arêtes.

Entraînement et inférence

Le classifieur d'arêtes est un MLP qui produit une seule valeur sigmoïde. De l'étape l0l_0 à la dernière étape LL, les embeddings d'arêtes de chaque étape servent à prédire, et l'on calcule sur l'ensemble une entropie croisée binaire pondérée :

L=−1∣E∣∑l=l0L∑(i,j)∈Eℓ(i,j)(l)\mathcal{L} = -\frac{1}{|E|}\sum_{l=l_0}^{L}\sum_{(i,j)\in E} \ell_{(i,j)}^{(l)}

La perte de chaque arête à l'étape ll s'écrit

ℓ(i,j)(l)=w y(i,j)log⁡y^(i,j)(l)+(1−y(i,j))log⁡(1−y^(i,j)(l))\begin{aligned} \ell_{(i,j)}^{(l)} = {} & w\, y_{(i,j)} \log \hat{y}_{(i,j)}^{(l)} \\ & + (1 - y_{(i,j)}) \log\big(1 - \hat{y}_{(i,j)}^{(l)}\big) \end{aligned}

Les arêtes actives sont bien moins nombreuses que les inactives ; les exemples positifs sont donc multipliés par un poids ww.

À l'inférence, les prédictions de la dernière étape servent directement de réponse pour yy, binarisées avec un seuil de 0.5. Rien n'oblige le réseau à respecter les contraintes du flot ; après seuillage, un nœud peut donc se retrouver avec deux arêtes sortantes. Les auteurs prévoient deux corrections : soit garder de façon gloutonne l'arête au score le plus élevé, soit calculer l'arrondi optimal exact par programmation linéaire. En pratique, les arêtes qui violent les contraintes sont rares, les deux méthodes donnent presque le même résultat, et la méthode gloutonne ne perd que 0.2 point d'IDF1.

Détails d'implémentation

Quelques réglages comptent beaucoup quand on fait réellement tourner la méthode :

  • CNN gelé. Les auteurs constatent qu'entraîner aussi le ResNet n'améliore pas nettement les résultats, mais alourdit beaucoup le calcul ; toutes les couches de convolution sont donc gelées, et seuls les MLP en aval sont entraînés.
  • Fenêtre glissante. La vidéo est découpée en graphes de 15 images, deux graphes consécutifs se chevauchant sur 14 images ; pour les arêtes du chevauchement, on fait la moyenne des prédictions des différents graphes. Les séquences à caméra fixe sont échantillonnées à 6 images par seconde, celles à caméra mobile à 9 ; chaque graphe ne couvre donc qu'environ une seconde et demie à un peu plus de deux secondes de vidéo.
  • Élagage. Relier tous les nœuds d'images différentes ferait exploser le nombre d'arêtes ; deux nœuds ne sont donc reliés que si chacun figure parmi les 50 plus proches voisins de l'autre selon les caractéristiques de re-ID.
  • Prétraitement par Tracktor. Les détections publiques passent d'abord par Tracktor ; on jette les ID qu'il attribue pour ne garder que les boîtes corrigées comme entrée. Les boîtes de Tracktor sont plus précises, et il rajoute aussi dans les images voisines quelques détections manquées. Pour les images manquantes au milieu des trajectoires de sortie, on comble d'abord avec les trajectoires de Tracktor, puis par interpolation pour le reste.

Ce dernier point mérite l'attention. Le réseau de MPNTrack tourne seul à 35 images par seconde, mais Tracktor, en amont, n'en traite que 8 ; le système complet tourne en moyenne à 6.5 images par seconde.

Discussion

Les ablations sont toutes faites sur le jeu d'entraînement de MOT17, en validation croisée à trois plis.

La mise à jour sensible au temps

Mise à jourMOTA ↑IDF1 ↑Chang. d'ID ↓Contraintes ↑
Classique63.067.31 02282.1 %
Sensible au temps64.070.060298.8 %

D'après la Table 1 de l'article. La colonne Contraintes donne la proportion moyenne de contraintes de conservation du flot satisfaites avec un seuil de 0.5.

Séparer passé et futur fait gagner près de 3 points d'IDF1, et les changements d'identité passent de 1 022 à 602.

La dernière colonne est plus intéressante encore. Avec un MPN classique binarisé directement, seules 82.1 % des contraintes sont satisfaites ; avec la version sensible au temps, 98.8 %. Le réseau a presque appris de lui-même la règle selon laquelle « chacun ne peut se relier qu'à une personne en avant et une en arrière », sans qu'un solveur externe ait à l'imposer.

Combien d'étapes de propagation

Figure 3 de l'article : MOTA (en bleu, axe de gauche) et IDF1 (en rouge, axe de droite) pour un nombre d'étapes de passage de messages allant de 0 à 18. À 0 étape, le MOTA est d'environ 61.9 et l'IDF1 d'environ 65.4 ; à 2 étapes, ils bondissent à environ 64.0 et 69.3 ; à partir de 4 étapes, l'IDF1 tourne autour de 70 et le MOTA autour de 64, puis les deux restent presque stables.
Figure 3 de l'article de Brasó et Leal-Taixé, extraite de la page 8 du PDF, licence arXiv, citation académique.

Zéro étape signifie aucun passage de messages ; on fait une classification binaire sur les seuls embeddings initiaux des arêtes, ce qui revient à l'approche traditionnelle qui « apprend des coûts par paires ».

De 0 à 2 étapes, le MOTA et l'IDF1 font un bond, celui du passage des relations par paires aux relations d'ordre supérieur. La tendance à la hausse s'arrête ensuite vers 6 étapes, et il n'y a plus d'amélioration au-delà de 12. La configuration finale utilise L=12L = 12.

L'origine des caractéristiques

Caract. d'arêteMOTA ↑IDF1 ↑FP ↓Chang. d'ID ↓
Temps seul58.852.613 1272 962
Temps + position63.668.76 308895
Temps + position + apparence64.070.06 169602

D'après la Table 2 de l'article.

Ce tableau a de quoi surprendre. L'ajout de la position relative fait passer l'IDF1 de 52.6 à 68.7, le plus grand saut ; ajouter ensuite les caractéristiques d'apparence ne rapporte que 1.3 point d'IDF1. Mais l'apparence fait encore tomber les changements d'identité de 895 à 602, et mérite d'être gardée.

Dans ce cadre, la position compte bien plus que l'apparence. L'article n'analyse pas la raison plus avant ; une explication possible est que les nœuds portent déjà l'embedding d'apparence, auquel les arêtes ont aussi accès pendant le passage de messages, si bien qu'une distance d'apparence placée sur les arêtes fait en partie double emploi.

Face aux autres méthodes

Table 3 de l'article : comparaison sur les trois benchmarks 2D MOT 2015, MOT16 et MOT17, avec les détections publiques ; les colonnes sont MOTA, IDF1, MT, ML, FP, FN, changements d'identité et vitesse (Hz), et (G) signale les méthodes de partitionnement de graphe. MOT15 : la méthode obtient un MOTA de 51.5, un IDF1 de 58.6, 375 changements d'identité et 6.5 Hz ; Tracktor 46.6, 47.6, 1 290 et 1.8 Hz ; JointMC 35.6, 45.1, 457 et 0.6 Hz. MOT16 : la méthode 58.6, 61.7 et 354 ; Tracktor 56.2, 54.9 et 617 ; NOTA 49.8, 55.3 et 614. MOT17 : la méthode 58.8, 61.7 et 1 185 ; Tracktor 56.3, 55.1 et 1 987 ; eHAF 51.8, 54.7 et 1 834 ; jCC 51.2, 54.5 et 1 802.
Table 3 de l'article de Brasó et Leal-Taixé, extraite de la page 8 du PDF, licence arXiv, citation académique.

Les trois benchmarks utilisent les détections publiques. MPNTrack arrive premier sur les trois jeux de données, et dépasse le meilleur IDF1 antérieur de respectivement 11, 6.4 et 6.6 points. Face aux autres méthodes de partitionnement de graphe, il est non seulement bien plus précis, mais aussi plus rapide d'un ordre de grandeur que certaines d'entre elles ; JointMC, par exemple, ne tourne qu'à 0.6 Hz.

Le prétraitement par Tracktor aide toutefois beaucoup ici. En annexe, les auteurs rapportent aussi une version sans Tracktor, qui corrige les détections publiques avec la tête de régression d'un Faster R-CNN :

JeuMOTA (avec Tracktor)MOTA (sans)IDF1 (avec Tracktor)IDF1 (sans)
MOT1551.546.658.653.8
MOT1658.654.361.756.8
MOT1758.856.061.758.4

D'après la Table 7 de l'annexe de l'article.

Sans Tracktor, le MOTA perd de 2.8 à 4.9 points, et l'IDF1 de 3.3 à 4.9 points. Même ainsi, la méthode bat encore les autres méthodes à base de graphe du tableau, dont plusieurs utilisent des détections brutes sans suppression des non-maxima, des caractéristiques d'image de bas niveau ou une conception hiérarchique, et disposent donc de plus d'informations qu'elle.

Limites

MPNTrack est une méthode hors ligne ; chaque graphe doit voir les images futures pour décider, et la méthode ne se transpose pas directement à un système temps réel.

La fenêtre temporelle est aussi très courte. Un graphe ne couvre qu'environ deux secondes ; une personne masquée longtemps, même si elle revient dans l'image, n'est plus dans le même graphe et ne peut pas être raccordée. Le nombre d'arêtes croît comme le carré du nombre de nœuds ; pour allonger la fenêtre, il faudrait élaguer encore plus sévèrement.

Le même laboratoire a ensuite empilé les graphes en plusieurs niveaux dans SUSHI, en 2023 ; les niveaux inférieurs traitent les liaisons à court terme, les niveaux supérieurs raccordent les courtes trajectoires en longues trajectoires, ce qui répond justement à ce problème de fenêtre trop courte.

Conclusion

Avant cet article, l'apprentissage servait surtout, en suivi multi-objets, à apprendre des caractéristiques et des coûts ; c'était encore un solveur d'optimisation traditionnel qui décidait vraiment des trajectoires. MPNTrack prend directement les variables binaires du flot comme étiquettes de classification, utilise le passage de messages pour que chaque arête voie tout le graphe, et laisse le réseau apprendre lui-même des solutions presque admissibles.

La mise à jour sensible au temps est une petite modification discrète, qui se contente d'additionner séparément passé et futur ; elle suffit pourtant à ce que le réseau apprenne presque seul les contraintes de conservation.

Le titre de l'article promettait d'apprendre un solveur, et le réseau a bel et bien appris 98.8 % du travail. Les 1.2 % restants, il faut finalement les confier à une règle d'arrondi ; une boucle gloutonne suffit.