Offre de thèse
Problème d'assignation euclidienne aléatoire en petite dimension, et applications
Date limite de candidature
29-05-2026
Date de début de contrat
01-10-2026
Directeur de thèse
MOYAL Pascal
Encadrement
Encadrement 50/50 entre les deux co-directeurs, à l'institut Elie Cartan de Lorraine sur le site de Nancy.
Type de contrat
école doctorale
équipe
PROBAS STATScontexte
La thèse sera co-dirigée par deux enseignants-chercheurs de l'Institut Elie Cartan de Lorraine (IECL) et une co-encadrante au CNES. Le(la) doctorant(e) sera basée sur le site de l'IECL Metz, trouvera sa place au sein de l'équipe 'Probabilités et Statistique' de l'IECL, où il/elle inter-agira avec d'autres probabilistes et statisticiens, sur un large spectre d'expertises, ainsi que plus largement, avec des mathématiciens d'autres spécialités. Il/elle pourra aussi interagir avec les réseaux de recherche de ses encadrants, participer aux réunions et aux conférences organisées par leur communauté scientifique au niveau national et international.spécialité
Mathématiqueslaboratoire
IECL - Institut Elie Cartan de Lorraine
Mots clés
ERAPs, Problème de Monge-Kantorovitch, Méthode hongroise, Analyse de Fourier discrète, Appariement optimal
Détail de l'offre
L'appariement entre deux ensembles de points est un problème récurrent, par exemple dans le traitement d'images satellites. Dans ce contexte, la mise en correspondance de points homologues dans deux images satellites différentes est nécessaire pour le géo-référencement d'une image à l'aide d'une image de référence, ou pour la reconstruction 3D par stéréophotogrammétrie. Pour cela, la plupart des approches utilisent des descripteurs locaux fondés sur la similarité des zones correspondantes d'une image à l'autre. Cependant, bien que robustes au bruit et aux perturbations, ces approches présentent des limites lorsqu'il s'agit de motifs répétitifs (par exemple des rangées de vignes ou d'arbres) ou de la mise en correspondance d'objets entre différentes modalités (par exemple une image optique et une image radar à synthèse d'ouverture — SAR). Dans ces cas, par exemple pour faire correspondre les points associés aux mêmes arbres dans deux images SAR, le problème se ramène à un problème d'assignation aléatoire.
Étant donné un système de référence de coordonnées, nous cherchons alors à apparier les observations correspondant à n objets indiscernables dans deux images satellites différentes, en considérant que la deuxième image est une version 'bruitée' de la position de chacun des n objets. Ce problème probabiliste de minimisation combinatoire est appelé Problème Euclidien d'Assignation Aléatoire (Euclidean Random Assignment Problem, ERAP).
L'objectif de cette proposition de thèse est de contribuer à l'analyse probabiliste des ERAP selon les axes suivants :
(i) Tout d'abord, étudier le problème unidimensionnel à l'aide d'une approche combinatoire. En particulier, nous souhaitons caractériser et analyser la transition de phase ainsi que la description Poissonienne à l'échelle critique, observées dans des travaux préliminaires, pour différentes distributions des points et différentes distributions des perturbations ;
(ii) Ensuite, étudier l'énergie minimale espérée de l'ERAP, avec de possibles formules exactes dans le cas unidimensionnel, des estimations asymptotiques dans un cadre plus général, ainsi qu'une possible caractérisation en deux dimensions à l'aide de l'analyse de Fourier discrète ;
(iii) Enfin, nous souhaitons appliquer ces résultats à l'acquisition de données satellitaires, et en particulier aux suspensions de particules en deux dimensions.
Keywords
ERAPs, Monge-Kantorovich problem, Hungarian method,, Discrete Fourier analysis, Optimal matching
Subject details
The assignment between two sets of points is a recurring problem, for example in satellite image processing. There, matching corresponding points in two different satellite images is needed for geo-referencing an image using a reference image or for 3D reconstruction through stereo-photogrammetry. To do this, most approaches use local descriptors that are based on the similarity of the corresponding areas from one image to another. However, while robust to noise and perturbations, these approaches encounter limitations when dealing with repetitive patterns (e.g., rows of vineyards or trees) or when matching objects between different modalities (e.g., an optical image and a Synthetic Aperture Radar image (SAR)). In these cases, for example, for matching the points corresponding to the same trees in two SAR images, the problem boils down to a random assignment problem. Given a coordinate reference system, we then wish to match the observation corresponding to of n indistinguishable objects in two different satellite images, by considering the second image as a 'perturbated' version of the positions of the n objects. This random combinatorial minimization problem is called an Euclidean Random Assignment Problem (ERAP). The aim of this PhD proposal is to contribute to the probabilistic analysis of ERAPs along the following lines: (i) First, investigating the one-dimensional problem using a combinatorial approach. In particular, we wish to characterize the phase transition and the Poisson description at the critical scale, observed in preliminary works, for various distributions of points and various distributions of perturbations; (ii) Second, investigating the minimal expected energy of the ERAP, with possible exact formulas in the one-dimensional case, asymptotic estimates in wider generality, and a possible characterization in 2D using discrete Fourier Analysis; (iii) We wish to apply these results to the satellite data acquisition, and in particular, to particle suspensions in 2D.
Profil du candidat
Nous recherchons un(e) étudiant(e) de M2 recherche très motivé, avec un baggage solide en théorie des probabilités et/ou transport optimal. Des compétences de base en programmation (spécialement en Python) sont aussi attendues.
Candidate profile
We are looking for a motivated Master 2 student in Mathematics with a solid
background in probability theory and/or optimal transport. Basic coding skills (especially in Python) are expected.
Référence biblio
[1] L. Ambrosio, F. Stra, D. Trevisan, A PDE approach to a 2-dimensional matching problem, Probab.
Theory Relat. Fields, 173(1), 2019.
[2] R. Cargnello, Hybridization of multi-sensor and multi-temporal data for monitoring water resources,
internship report, CNES, 2024.
[3] M. Chertkov, L. Kroc, F. Krzakala, M. Vergassola, and L. Zdeborová, Inference in particle tracking
experiments by passing messages between images, Proc. Natl. Acad. Sci. 107 (17) 7663-7668, 2010.
[4] S. Chibbaro, A. Decoene, S. Martin, and F. Vergnet, Irreversibility and chaos in active particle
suspensions, Phys. Rev. Fluids, Vol. 6, issue 1, (16), 2021
[5] Scharstein, D. and Szeliski, R. and Zabih, R, A taxonomy and evaluation of dense two-frame stereo
correspondence algorithms, Electron. IEEE SMBV, 2001.
[6] M. D'Achille, Statistical Properties of the Euclidean Random Assignment Problem, PhD thesis,
Paris-Saclay University, 2020. https://hal.archives-ouvertes.fr/tel-03098672
[7] M. D'Achille, An invitation to random assignment problems, AESIM-CIMPA Summer School
“Probability with / on random graphs: trees, networks, dimers, assignments”, Nesin Mathematics
Village, Sirinçe, Turkey, August 2024. https://matteodachille.github.io/teaching
[8] M. D'Achille, F. Mattesini, and D. Trevisan, Concentration for random Euclidean combinatorial
optimization, arXiv/math.PR 2602.21851, 2026. Available at https://arxiv.org/abs/2602.21851
[9] N. Gasnier, Use of multi-temporal and multi-sensor data for continental water body extrac-
tion in the context of the SWOT mission, PhD thesis, Institut Polytechnique de Paris, 2022.
https://theses.hal.science/tel-03578831
[10] S. Geman and D. Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration
of Images, IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-6, no. 6, pp. 721-741, 1984.
[11] R. M. Karp, U. V. Vazirani, and V. V. Vazirani, An optimal algorithm for on-line bipartite
matching, in Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing,
pp. 352–358, 1990.
[12] J. D. Lafferty, A.McCallum, and F. C. N. Pereira, Conditional Random Fields: Probabilistic Models
for Segmenting and Labeling Sequence Data, In: Proceedings of the Eighteenth International Con-
ference on Machine Learning. ICML '01. San Francisco, CA, USA: Morgan Kaufmann Publishers
Inc., pp. 282–289, 2001.
[13] J. Levillain, Filament models for swimming at the microscopic scale, PhD thesis, Institut Poly-
technique de Paris, 2024. https://theses.hal.science/tel-04766775
[14] J. Mairesse and P. Moyal, Stability of the stochastic matching model, Journal of Applied Proba-
bility, vol. 53, no. 4, pp. 1064–1077, 2016.
[15] M. Moharrami, C. Moore, J. Xu, The planted matching problem: Phase transitions and exact
results, Ann. Appl. Probab. 31(6), 2663-2720, 2021.
[16] M. Nazari and A. L. Stolyar, Reward maximization in general dynamic matching systems, Queueing
Systems, vol. 91, no. 1, pp. 143–170, 2019.
[17] J. Munkres, Algorithms for the Assignment and Transportation Problems. SIAM J. Appl. Math. 5,
32–38, 1957.
[18] J. Li, L. Ohm and S. E. Spagnolie, Arrested development and traveling waves of active suspensions
in nematic liquid crystals, Physical Review Fluids, 10, 083301, 2025.
[19] C. Papadimitriou, T. Pollner, A. Saberi, and D. Wajc, Online stochastic max-weight bipartite
matching: Beyond prophet inequalities, in Proceedings of the 22nd ACM Conference on Economics
and Computation, pp. 763–764, 2021.
[20] R. Thompson, Emergence of collective motion in a suspension of motile bacteria, https://youtu.
be/aoVx_YC7f94?si=GeKmejvDQYmHP9EW, 2015.
[21] T. Quarck, Random assignment problems for satellite data acquisition, M2 internship report, Sor-
bonne Université, 2025