Offers Master

From LRDE

Propositions de stage de Master Recherche

Text extraction from natural images

Keywords:

  • image processing,
  • mathematical morphology,
  • tree-based reasoning,
  • algorithmic optimization.

Contact: thierry.geraud@lrde.epita.fr

Exploration of new self-dual filters in mathematical morphology

Keywords:

Contact: thierry.geraud@lrde.epita.fr


Étude de problématiques de performance en traitement d'images dans un contexte générique

Présentation du laboratoire

Fondé en 1998, le LRDE est un laboratoire sous tutelle de l'École Pour l'Informatique et les Techniques Avancées (EPITA). À l'instar du laboratoire, l'équipe est jeune et dynamique ; fin 2012, elle est composée d'une dizaine d'enseignant-chercheurs, d'une administratrice, de cinq doctorants et d'une douzaine d'étudiants-chercheurs de l'école. Les travaux de recherche fondamentale effectués au LRDE s'articulent autour de deux thématiques :

  • la reconnaissance des formes ;
  • les automates et la vérification formelle.

Par ailleurs, la recherche applicative s'inscrit dans un axe transverse dit de « généricité et performance ».

Description du stage

Ce stage s'inscrit dans l'axe « généricité et performance » du laboratoire.

On peut constater d'une part que de nombreux outils logiciels pour le traitement d'image sont conçus en prenant en compte des problématiques de performance relatives aux données (images ou vidéos volumineuses ou nombreuses), au contexte (contraintes de temps réel, besoins d'obtenir une réponse dans un temps « raisonnable ») ou encore liée au matériel (puissance de calcul ou capacité mémoire limitée(s)).

Par ailleurs, de plus en plus de bibliothèques logicielles pour le traitement d'images sont construites d'après une modélisation avancée mettant en œoeuvre des « abstractions » représentant les différentes notions du domaine (image, point, valeur, voisinage, etc.). Cette approche permet une écriture « haut niveau » d'algorithmes de traitement d'images, réutilisables (non limités à un unique cas d'utilisation) et souvent plus simples. Les cadres logiciels (« software frameworks ») entrant dans cette catégorie s'appuient le plus souvent sur la programmation orientée objet ou la programmation générique (templates du C++, generics de Java ou C#).

Il est cependant beaucoup plus rare d'observer des outils qui cherchent à répondre aux deux préoccupation précédentes (être performant tout en fournissant une écriture générale via des abstractions). Le projet Olena, développé depuis plus de dix ans au LRDE, propose une bibliothèque de traitement d'images générique en C++, Milena, permettant l'écriture d'algorithmes réutilisables et performants. Elle s'appuie à la fois sur la programmation générique et la programmation orientée objet. Le stage proposé a pour objet l'exploration de pistes pour étendre les capacités de Milena dans le domaine du calcul performant (notamment dans le contexte des « Big Data »), tout en préservant ses caractéristiques de généricité et d'abstraction actuelles.

Les pistes de travail proposées incluent notamment les idées suivantes :

  • la conception et l'ajout de structures de données destinées à de

gros volumes de données ;

  • l'utilisation d'instructions de vectorisation (SIMD) pour

accélérer les calculs ;

  • l'utilisation de programmation parallèle (multicœur) pour

répartir les calculs.

Dans tous les cas, les travaux de recherche devront être menés en gardant à l'esprit une intention de réutilisabilité / généricité (même partielle) des solutions proposées, en s'appuyant par exemple sur un raffinement (lifting) incrémental d'une première proposition. À terme, l'objectif est en effet de poser les premières briques d'une formalisation d'un ensemble de propriétés et de types de données permettant de généraliser les améliorations de performance mentionnées ci-avant.

Mots-clefs : calcul scientifique, Big Data, C++, programmation parallèle.

Pré-requis

Des connaissances en traitement d'images sont nécessaires à la réalisation de ce stage. Le candidat devra être familiarisé avec le langage C++ ou avoir au moins un bon niveau de connaissance du langage C. Le travail à effectuer devra s'intégrer dans la plate-forme logicielle libre de traitement d'images du LRDE, Olena, écrite en C++.

Des connaissances en modélisation objet, programmation générique, vectorisation ou en programmation parallèle / multicœcoeur seraient appréciables.

Débouchés

Si le déroulement du stage est satisfaisant, nous souhaiterions qu'il soit suivi d'une thèse de doctorat.

Informations pratiques

  • Personnes à contacter :
    • <roland.levillain-at-lrde.epita.fr>
  • Lieu du stage :

Laboratoire de Recherche et Développement de l'EPITA (LRDE)
18, rue Pasteur
94270 Le Kremlin-Bicêtre
(Porte d'Italie)

  • Rémunération : environ 800 € brut/mois

Annonce diffusée à partir du 07/12/2012.

—roland - 07 Dec 2012

Minimisation d'automates

Thématique

Automates

Laboratoire

Laboratoire de Recherche et Développement de l’EPITA (LRDE)

Équipe

Projet Vaucanson (http://vaucanson.lrde.epita.fr)

Directeur de stage

Akim Demaille <akim . demaille at lrde . epita . fr>

Présentation générale du domaine

La théorie classique des automates, des transducteurs et des expressions rationnelles, admet une extension très élégante et extrêmement utile (e.g., en traitement des langues naturelles) prenant en compte un concept de pondération. Les poids sont alors pris dans un semi-anneau, qu'il soit classique (⟨B,∨,∧⟩, ⟨Z,+,×⟩, ⟨Q,+,×⟩, etc.), tropical (⟨Z,min,+⟩, etc.), ou autre encore (par exemple des expressions rationnelles).

Vaucanson 2 est un projet ANR développé en partenariat entre Télécom ParisTech (Jacques Sakarovitch), le LaBRI (Sylvain Lombardy) et le LRDE (Alexandre Duret-Lutz et Akim Demaille). Il s'agit d'une plate-forme de manipulation des automates, transducteurs et expressions rationnelles pondérés. Elle est écrite en C++11 en évitant la programmation orientée-objet classique, au profit de la programmation générique (\texttt{template}) pour les performances.

Objectifs du stage

La minimisation d’un automate consiste à l’“optimiser” : construire le plus petit des automates équivalents. Il existe de nombreux algorithmes de minimisation d’automates, dont les domaines d’application et les performances varient. Il s’agira d’implémenter dans Vaucanson 2 certains de ces algorithmes, de les optimiser, et de mener une étude comparative de leurs performances. Ces résultats permettront de proposer une approche adaptative, qui choisisse l’algorithme à appliquer en fonction du profil de l’automate/transducteur.

Quelques références bibliographiques