Séminaire Sébastien Bougleux

Séminaire Sébastien Bougleux (GREYC UMR 6072)

Calculer des correspondances entre des données structurées ou non-structurées constitue un problème majeur dans de nombreuses applications de traitement et d’analyse d’images, de reconnaissance de formes ou encore d’apprentissage machine. Nous nous intéressons aux problèmes d’appariement d’ensembles et d’appariement de graphes avec correction d’erreurs, et au problème du calcul de la distance d’édition entre graphes. Dans cette présentation, nous exposerons dans un premier temps nos travaux sur le calcul d’une ou plusieurs solutions au problème linéaire d’appariement d’ensembles avec correction d’erreurs. En particulier, nous montrerons que ce problème est équivalent à un problème linéaire d’appariement (sans correction d’erreur) par transformation de la matrice de coûts. Puis, dans un deuxième temps, nous exposerons nos travaux sur le calcul d’appariements de graphes avec correction d’erreurs pour obtenir une distance d’édition sous-optimale. Notre approche est basée sur une formulation quadratique du problème et sur l’algorithme de Frank-Wolfe pour rechercher des minima locaux. Dans notre cas, l’algorithme de Frank-Wolfe itère la résolution d’un problème linéaire d’appariement avec correction des erreurs. Les expérimentations que nous avons réalisées montrent que notre approche fournit un bon compromis entre temps de calcul et qualité de l’estimation.

Computing correspondences between structured or unstructured data is a major problem in image processing and analysis, pattern recognition, and machine learning. We are interested in the problems of pairing sets and matching graphs with error correction, and in the problem of computing the edit distance between graphs. In this presentation, we will first expose our work on the computation of one or more solutions to the linear sum assignment problem with error correction. In particular, we will show that this problem is equivalent to a linear sum assignment problem (without error correction) by transformation of the cost matrix. Then, in a second step, we will expose our work on the error-correcting graph matching problem to obtain a suboptimal graph edit distance. Our approach is based on a quadratic formulation of the problem and on Frank-Wolfe’s algorithm to search for local minima. In our case, Frank-Wolfe’s algorithm iterates the resolution of a linear assignment problem with error correction. The experiments we have carried out show that our approach provides a good compromise between calculation time and quality.