Lieu : LAAS-CNRS - Toulouse

Durée : 5 à 6 mois
Début au plus tôt : février 2026 – Fin au plus tard : 30 août 2026
Gratification : Oui
Contacts : Cyrille BRIAND (briand@laas.fr) et Cyrille Equoy (cequoy@laas.fr)

Niveau : Master 1 ou 2 ou PFE d’écoles d’ingénieurs

Titre : Branch-and-Price pour la ré-identification de personnes dans un réseau de caméras disjoints

La réidentification des personnes, appelée « re-ID », est utilisée dans de nombreuses applications de surveillance impliquant un suivi de personnes, ou de sécurité. Elle consiste à réidentifier un ensemble personnes qui se déplacent dans un environnement très vaste équipé de caméras en réseau à champs non superposées. Après détection et apprentissage des signatures des personnes sur le flux vidéo de chaque caméra, la re-ID tente d’apparier les individus entre chaque paire de caméras pour en déduire leur chemin dans le réseau (cf. figure).

De par la nature du problème, la plupart des approches de re-ID sont basées sur la re-ID par paires de caméras et recherchent le meilleur descripteur pour les détections, les meilleures mesures de correspondance, ou les deux. Ainsi, les réidentifications de personnes déduites indépendamment par chaque paire de caméras, même si elles sont supposées exactes, peuvent être incohérentes les unes par rapport aux autres à travers le réseau de caméras.

Pour pallier ce problème, plusieurs approches ont vu le jour qui reformulent le problème de re-ID sous la forme d'une « réidentification cohérente avec le réseau » en tant que problème d’optimisation global (e.g. [1]). L'optimisation vise à maximiser le profit global de l'association de paires de détections sur l'ensemble du réseau de caméras. Cela garantit la cohérence entre les trajets des personnes cibles et améliore les performances de réidentification.

Les équipes ROC et RAP du LAAS-CNRS ont proposé une approche de cette nature qui intègre de surcroit des contraintes intrinsèques au réseau : un horodatage des détections, une topologie du réseau et les temps de transit minimum entre deux caméras. Une méthode d’optimisation exacte a été proposée qui repose sur une décomposition en cluster à profit maximum d’un graphe dirigé et valué, les sommets du graphe représentant les détections. Des méthodes de programmation mathématique ont été exploitées pour résoudre ce problème [2]. Ces méthodes utilisent une estimation à priori du nombre de clusters. La figure 2 représente la chaine complète de re-ID où sont représentés en rouge l’heuristique d’estimation de chemins et la méthode exacte de clusterisation.

Les méthodes de programmation mathématiques passant difficilement à l’échelle, l’objectif de ce stage est d'adapter, développer et tester une méthode de Branch-and-Price de la littérature pour la résolution du problème de re-ID. La problématique de recherche de clusters est en effet semblable à celle de recherche de chemins dans un graphe permettant de couvrir tous les sommets à coût minimum (ou profit maximum). Il semble donc prometteur d’adapter les méthodes de Branch-and-Price existantes utilisées pour résoudre le problème de tournées de véhicule (Vehicle Routing Problem), réputées performantes.

Ce sujet s’adresse aux étudiant(e)s de niveau Master 1 ou 2 à dominante Recherche-Opérationnelle. Des compétences en langages de programmation (python / C++) sont souhaitées ainsi qu’en Recherche Opérationnelle. Une connaissance des méthodes de décomposition en programmation mathématiques sera appréciée (sans que cela soit nécessaire).

Merci de soumettre votre candidature en joignant un CV, une lettre de motivation et vos derniers relevés de notes.

1. A. Das, A. Chakraborty, and A. K. Roy-Chowdhury. Consistent re-identification in a camera network. In D. Fleet,T. Pajdla, B. Schiele, and T. Tuytelaars, editors, Computer Vision – ECCV 2014, pages 330–345, Cham, 2014. Springer International Publishing.
2. Cyrille Equoy, Alessandro Goldwurm, Cyrille Briand, Frédéric Lerasle. A New Path-Oriented Optimization Procedure for Consistent Person Reidentification in a Camera Network. 2025 IEEE International Conference on Advanced Visual and Signal-Based Systems (AVSS), Aug 2025, Tainan, Taiwan. pp.1-6, ⟨10.1109/AVSS65446.2025.11149973⟩. ⟨hal-05288927⟩