Laboratoire d'Algorithmique et Image de Clermont-FerrandL.A.I.C. - EA 2146
Laboratoire d'Algorithmique et Image de Clermont-Ferrand
| |
||||
|
jeudi 25 Juin 2009
10h15, Salle du conseil. |
Marcel Guillaume
(LAIC)
Principes des projets de démonstration d'indépendance de Hilbert |
Algo | ||
|
jeudi 11 Juin 2009
10h15, Salle du conseil. |
Maciek Mostowski
(LAIC)
Fast animation in dynamic scenes for voxel-based global illumination |
Image | ||
|
jeudi 4 Juin 2009
10h15, Salle du conseil. |
Michal Krynicki
(Université de Varsovie)
Dependence Logic |
Algo | ||
|
jeudi 28 Mai 2009
10h15, Salle de visio. |
Alexandre Faure
(Laic)
Analyse multi-primitives de courbes digitales |
Groupe de Travail Image | ||
|
jeudi 14 Mai 2009
14h00, Isima, salle A104. |
Konrad Zdanovski
(Université Paris VI, LIAFA)
A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata |
Groupe de Travail B.D. Laic-Limos | ||
|
jeudi 14 Mai 2009
10h15, Salle de visio. |
Konrad Zdanovski
(Université Paris VI, LIAFA)
Glivenko theorem for the second order intuitionistic propositional logic without universal quantifiers (suite et fin) |
Algo | ||
|
jeudi 7 Mai 2009
14h00, Salle B21. |
Chafik Samir
(INMA, Université catholique de Louvain)
Modélisation, Analyse, déformation optimale, morphing des formes 2D et 3D |
Image | ||
|
jeudi 7 Mai 2009
10h15, Salle du Conseil. |
Luc Gillibert
(LORIA, PostDoc Météo France)
Traitement géométrique d'images tomographiques de neige |
Image | ||
|
jeudi 30 Avril 2009
15h30, Salle du Conseil. |
Nicolas Andreff
(LASMEA, Université Clermont II)
Estimation de pose et de vitesse Cartésienne par vision rapide |
Image | ||
|
jeudi 30 Avril 2009
10h15, Salle du Conseil. |
Christophe Fiorio
(Ecole Polytechnique Universitaire de Montpellier, LIRMM)
Modélisation, Analyse, Représentation des Images Numériques Approche Combinatoire de l'Imagerie |
Image | ||
|
jeudi 23 Avril 2009
15h30, Salle du Conseil. |
Céline Roudet
(Université Claude Bernard Lyon 1, LIRIS)
Compression adaptative de surfaces par ondelettes géométriques |
ppt | Image | |
|
jeudi 23 Avril 2009
14h00, Salle du Conseil. |
Vincent Charvillat
(Université de Toulouse, ENSEEIHT, IRIT)
Analyse et Composition d'Objets Visuels - Applications en Réalité Augmentée |
Image | ||
|
jeudi 23 Avril 2009
10h15, Salle du Conseil. |
Julien Mille
(Université de Paris-Dauphine, Ceremade)
Modèles déformables pour l'extraction de structures tubulaires et arborescentes |
Image | ||
| |
||||
| Semaine du 30 mars au 3 avril 2009 |
| |||
|
jeudi 26 Mars 2009
10h15, Salle du conseil. |
Emmanuelle Darles
(Université de Limoges, XLIM)
Simulation dynamique et rendu de scènes océaniques en synthèse d'images réalistes |
Image | ||
|
jeudi 26 Mars 2009
14h00, salle C6 au laic |
Florian Richoux
(Ecole Polytechnique, LIX)
Complexité algorithmique des problèmes de satisfaction de contraintes. |
Algo | ||
|
jeudi 19 Mars 2009
10h15, B21. |
Konrad Zdanovski
(Université Paris VI, LIFA)
Glivenko theorem for the second order intuitionistic propositional logic without universal quantifiers |
Algo | ||
|
jeudi 26 Février 2009
10h15, Salle de visio. |
Emilie Koenig
(Université Blaise Pascal, LIMOS)
Synthèse de textures aléatoires : algorithme et applications |
Image | ||
| |
||||
|
jeudi 12 Février 2009
16h15, Salle de visio. |
Christophe Rey
(Université Blaise Pascal, Limos)
La discussion portera sur l'article de Jan Van den Bussche Constraint databases: A tutorial introduction |
ps.gz | Groupe de Travail B.D. Laic-Limos | |
|
jeudi 12 Février 2009
10h15, Salle de visio. |
En grève partielle
|
occupé | ||
|
jeudi 5 Février 2009
10h15, Salle de visio. |
En grève partielle
|
occupé | ||
|
jeudi 29 Janvier 2009
10h15, Salle de visio. |
Antoine Vacavant
(Université Louis Lumière Lyon II, LIRIS)
Géométrie discrète sur grilles irrégulières isothétiques |
Image | ||
|
jeudi 8 Janvier 2009
16h30, Salle à préciser. |
Christophe Rey
(Université Blaise Pascal, Limos)
élimination des quantificateurs dans l'algèbre des termes |
Groupe de Travail B.D. Laic-Limos | ||
| |
||||
|
jeudi 18 Décembre 2008
10h15, Salle de visio. |
Smaïl Kaouache
(Université de Jijel, Algérie)
Sur une démonstration du théorème Skolem-Mahler-Lech |
Groupe de Travail Algo | ||
|
jeudi 11 Décembre 2008
14h00, Amphi B |
Olivier Teytaud
(LRI, Inria projet TAO)
Algorithmiques pour les jeux, le cas du Go et le reste |
affiche | Vulgarisation | |
|
jeudi 11 Décembre 2008
10h15, Salle du conseil. |
Olivier Teytaud
(LRI, Inria projet TAO)
Fouille d'arbres par Monte-Carlo: les progrès en planification |
planning | Tout public | |
|
jeudi 4 Décembre 2008
14h30, Amphi B |
Thibault Marzais
(LAIC)
Soutenance de thèse intitulée Reconstruction de surfaces paramétrées par LP-Fitting. |
Tout Public | ||
|
jeudi 4 Décembre 2008
10h15, Salle de visio. |
Rémi Brochenin
(Laboratoire Spécification et Vérification, CNRS, ENS Cachan)
Des pouvoirs de la baguette magique. |
Algo | ||
|
jeudi 27 Novembre 2008
10h15, Salle de visio. |
Arnaud Carayol et Didier Caucal
(CNRS, Institut Gaspard Monge, Université Paris-Est Marne-la-Vallée)
Algorithmique et langages sur les graphes réguliers. |
pdf pdf | Algo | |
|
jeudi 20 Novembre 2008
10h15, Salle de visio. |
Stefan Dantchev
(University of Durham, ACiD)
Complexity Gaps in Propositional Proof Complexity |
Algo | ||
|
jeudi 13 Novembre 2008
10h15, Salle de visio. |
Stefan Szeider
(University of Duham, ACiD)
Tricky Problems for Graphs of Bounded Treewidth |
Algo | ||
| |
||||
|
jeudi 23 Octobre 2008
10h15, Salle de visio. |
Marc Chevaldonné
(Laic)
Système de gestion de versions : concepts et utilisations |
Tout public | ||
|
jeudi 16 Octobre 2008
10h15, Salle de visio. |
Alexandre Guitton
(Limos, Université Blaise Pascal)
Étude de complexité des problèmes d'arbres optiques |
Tout public | ||
|
jeudi 9 Octobre 2008
10h15, Salle de visio. |
Yan Gérard
(Laic, Université d'Auvergne)
Reconstruction d'une matrice en tomographie discrète |
Tout public | ||
|
jeudi 2 Octobre 2008
10h05, Salle A5. |
Mirek Kutylowski
(école Polytechnique de Wroclaw, Pologne)
Secure data transmission in the world of tiny artefacts |
Tout public | ||
|
jeudi 25 Septembre 2008
10h15, Salle B21. |
Julien Tierny
(LIFL - Telecom Lille 1)
Modélisation de forme 3D par graphe de Reeb et applications |
thèse (pdf) | Image | |
|
jeudi 18 Septembre 2008
10h15, Salle B21. |
Christophe Rey
(Université Blaise Pascal, Limos)
Constraint Database |
Groupe de Travail Algo | ||
jeudi 11 Juin 2009, 10h15, Salle de Visio.
Maciek Mostowski
(Laic)
Fast animation in dynamic scenes for voxel-based
global illumination
Résumé
We will present an approach for adding animation to Global Illumination
algorithm developed in LAIC
jeudi 4 Juin 2009, 10h15, Salle de Visio.
Michal Krynicki
(Université de Varsovie)
Dependence Logic
Résumé
We give a general presentation of the so called Dependence Logic (DO).
This logic is in some aspects dual to first-order logic with Henkin quantifiers.
We sketch in particular how the dependency notion may be expressed inside of DO.
Pointing out some of the main characteristics of DO we compare its expressive power
to those of First and Second Order Logics.
jeudi 28 Mai 2009, 10h15, Salle de Visio.
Alex Faure
(Laic)
Analyse multi-primitives de courbes digitales
Résumé
L'expose durera 20 minutes environ.
jeudi 14 Mai 2009, 14h00, Isima Salle A104.
Konrad Zdanovski
(Université Paris VI, LIAFA)
A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata
Résumé
This is joint work with Thomas Colcombet.
We establish a lower bound Ω((1.64n)n) for the problem of
translating a Büchi word automaton of size n into a deterministic
Rabin word automaton when both the Büchi and the Rabin conditions
label transitions rather than states. This lower bound exactly matches
the known upper bound to this problem, namely o((1.65n)n).
Our result entails a lower bound when the input Büchi automaton has
(as it is usual) its Büchi acceptance condition labeling states.
Those lower bounds remain when the output deterministic Rabin automaton
has its Rabin acceptance condition labeling states.
Hence, in the standard setting, our result establishes a lower bound of
Ω((1.64n)n), while the best known lower bound
was Ω((0.76n)n).
A known upper bound for the standard case is o((2.66n)n).
jeudi 14 Mai 2009, 10h15, Salle de Visio.
Konrad Zdanovski
(Université Paris VI, LIAFA)
Glivenko theorem for the second order intuitionistic propositional logic without universal quantifiers
Résumé
Note that this is the second part of the talk started on the 19th of March.
The famous Glivenko theorem for the intuitionistic propositional logic,
IPC, states that a formula $\psi$ is a classical tautology if and only
if $\neg\neg\psi$ is an IPC tautology. We examine the second order
propositional intuitionistic logic, IPC2, and we extend Glivenko theorem
for formulas of IPC2 without universal quantifiers. As a corollary we obtain
a semantic argument that the universal quantifier is not definable in IPC2
from other logical operators. We will present also two semantics for IPC2,
the equivalence of which reminds an open problem.
jeudi 7 Mai 2009, 14h00, Salle de Visio.
Chafik Samir
(INMA - Université de Louvain)
Modélisation, Analyse, déformation optimale, morphing des formes 2D et 3D
Résumé
La modélisation et l'analyse de la forme est un problème fondamentale
en vision par ordinateur et trouve ses applications dans de nombreux domaines
tels que l'animation, la biométrie, et l'imagerie médicale. Dans ce cadre, nous
explorons une nouvelle méthode qui analyse la forme comme un élément de
l'espace des formes, i. e. une variété riemannienne. Ce choix nous permettra
d'analyser les déformations optimales entre les formes telles que la
symétrisation des formes, de définir quelques notions de statistiques sur
l'espace des formes, et de construire une animation d'une forme en passant
par plusieurs états clés. Des exemples applicatifs concrets viennent illustrer
l'utilité de notre approche pour chacun de ces problèmes de recherche.
jeudi 7 Mai 2009, 10h15, Salle de Visio.
Luc Gillibert
(LORIA - Postdoc Météo France)
Traitement géométrique d'images tomographiques de neige
Résumé
La neige déposée au sol est constituée de grains de glace soudés entre eux
par des sollicitations thermodynamiques et mécaniques. Pour analyser la
microstructure de la neige et en comprendre sa formation et son évolution,
il est souvent nécessaire de séparer numériquement ces grains de glace de
leurs voisins. Les méthodes d'imagerie tridimensionnelles communément
utilisées ne fournissent aucune information directe sur les frontières entre
les grains. Afin d'obtenir une segmentation pertinente, nous avons mis au
point une méthode géométrique basée sur la détection de concavités sur la
surface de glace.
Sur l'image tridimensionnelle de neige, il est possible de calculer, en
chaque point de la surface, les courbures gaussienne et moyenne. Combinées,
ces courbures fournissent le signe de la courbure principale la plus petite.
Il est alors possible de séparer la surface en deux zones : l'une positive,
l'autre négative. En utilisant un diagramme de Voronoï, ces zones sont
étendues à l'objet entier. Les voxels de la zone négative sont retirés de
l'image, fournissant ainsi une segmentation en objets déconnectés. Ces
objets sont alors utilisés comme germes pour un second diagramme de Voronoï,
permettant d'obtenir la segmentation désirée.
jeudi 30 Avril 2009, 15h30, Salle de Visio.
Nicolas Andreff
(LASMEA - Université Clermont II)
Estimation de pose et de vitesse Cartésienne par vision rapide
Résumé
Cet exposé traitera de l'exploitation d'une acquisition non simultanée
des pixels d'une image, associée aux caméras CMOS. Dans un premier temps, nous
partirons d'une acquisition ligne après ligne (l'effet "rolling shutter") afin
d'établir un modèle de projection d'un objet rigide connu sous un tel effet,
qui se traduit par une déformation des images d'objets en mouvement.
Dans un deuxième temps, nous approfondirons l'étude du cas où l'on observe
partiellement et successivement les points d'intérêt de l'objet. En effet,
cette acquisition permet d'augmenter la fréquence d'acquisition en réduisant la
quantité de données inutiles transmise de la caméra vers le PC.
Des résultats expérimentaux issus du domaine de la robotique seront présentés
pour valider la méthode proposée.
jeudi 30 Avril 2009, 10h15, Salle de Visio.
Christophe Fiorio
(Ecole Polytechnique Universitaire de Montpellier, LIRMM)
Modélisation, Analyse, Représentation des Images Numériques
Approche Combinatoire de l'Imagerie
Résumé
Dans cet exposé, je vous présenterai un panorama de mes différents
travaux concernant une approche combinatoire de l'imagerie. Le point
de départ de ces travaux a été la volonté d'aborder la
problématique de l'analyse d'image, et en particulier de la
segmentation, par une approche algorithmique combinatoire plutôt que
par une approche traitement du signal. En particulier, nous
souhaitions nous appuyer sur une représentation à base de graphes
afin de pouvoir utiliser toute l'algorithmique sous-jacente. Trés
vite, des problèmes théoriques de modélisation sont apparus. Je vous
présenterai donc mes travaux concernant la topologie des espaces
discrets et j'évoquerai ceux relatifs à la modélisation
géométrique à base topologique. Je m'attarderai également sur les
résultats de segmentation d'images et notamment sur des critères
statistiques d'homogénéité des régions. Enfin je présenterai les
quelques résultats obtenus en géométrie discrète sur les notions de
plans, surfaces et courbes discrètes.
jeudi 23 Avril 2009, 15h30, Salle du Conseil.
Céline Roudet
(Université Claude Bernard Lyon 1, LIRIS)
Compression adaptative de surfaces par ondelettes géométriques
Résumé
L'évolution de l'infographie et des techniques de numérisation a récemment
ouvert la voie à une modélisation tridimensionnelle du monde qui nous entoure.
Afin de s'adapter à l'hétérogénéité des ressources et médias manipulant ces
objets 3D, des techniques basées sur l'analyse multirésolution sont
généralement utilisées car elles fournissent une représentation "scalable"
de ces modèles géométriques. C'est dans ce cadre de compression et de
transmission progressive d'objets 3D (modélisées sous forme de maillages surfaciques)
que se situe mon travail de thèse, réalisé dans le cadre du projet "CoSurf"
(collaboration entre le laboratoire LIRIS de Lyon et Orange Labs - Rennes).
A lissue de cette collaboration, nous avons proposé une nouvelle méthode
de compression hiérarchique s'appuyant sur une décomposition en ondelettes,
outil d'analyse performant et robuste qui a fait ses preuves en termes de
compression d'images et de vidéos. Notre méthode se démarque des techniques de
létat de lart, puisqu'elle s'appuie sur une segmentation préalable de la
surface en régions d'amplitudes fréquentielles variables. Pour cela, une
étude de la distribution des coefficients dondelettes sur les différents
niveaux de résolution a été considérée. Les partitions résultantes peuvent
ainsi être traitées indépendamment durant les phases d'analyse multirésolution,
de quantification et d'allocation binaire, de façon à s'adapter aux caractéristiques
surfaciques locales des maillages et ainsi réduire les informations à coder.
La contribution visuelle de chacune des partitions à l'ensemble de la surface
est également un point important à considérer dans la phase d'optimisation des bits
alloués à celles-ci, notamment pour des applications comme la transmission et
la visualisation sélectives.
D'autres applications telles que le tatouage, le filtrage, le débruitage,
l'indexation ou enfin la correction d'erreurs après transmission sur un canal
bruité, pourraient bénéficier de notre concept générique d'analyse multirésolution
adaptative.
jeudi 23 Avril 2009, 14h00, Salle du Conseil.
Vincent Charvillat
(Université de Toulouse, ENSEEIHT, IRIT)
Analyse et Composition d'Objets Visuels - Applications en Réalité Augmentée
Résumé
L'exposé situera d'abord globalement mes activités de recherche récentes
menées à l'IRIT (Institut de Recherche en Informatique de Toulouse) au
sein de l'équipe VORTEX ("Visual Objects : from Reality To EXpression").
Ensuite, je présenterai quelques contributions en suivi visuel 2D et 3D.
Je mettrai l'accent sur l'utilité d'une coopération entre analyse et
synthèse d'image. A titre d'exemple, je montrerai que les approches "par
points" pour la modélisation géométrique d'objets 3D et les algorithmes
de rendu associés peuvent être utilisés avec succès pour le suivi
d'objets 3D et la Réalité Augmentée.
Enfin, de manière plus succincte, j'illustrerai une facette
complémentaire de mon travail qui concerne l'accès contextuel et
interactif à des contenus visuels mêlant des objets visuels 2D ou 3D,
naturels ou synthétiques, temporisés ou non. De nombreuses
applications dans le domaine du multimédia sont envisageables à partir
de ces travaux.
jeudi 23 Avril 2009, 10h15, Salle du Conseil.
Julien Mille
(Université de Paris-Dauphine, Ceremade)
Modèles déformables pour l'extraction de structures tubulaires et arborescentes
Résumé
Les contours et les surfaces actives sont des modèles déformables employés en segmentation d'images 2D et 3D.
Généralement, leur évolution est gouvernée par la minimisation d'une fonctionnelle d'énergie, composée principalement
d'un terme de lissage et d'un terme image. Ainsi, la segmentation par modèle déformable réalise un compromis entre
la régularité du modèle et l'adéquation aux données.
De nombreux travaux, dans la continuité des modèles actifs de forme (Active Shape Models, ASM)
abordent la spécialisation du modèle déformable en vue d'une application précise, en ajoutant
à la fonctionnelle d'énergie un terme d'a priori sur la forme. Cette énergie va contraindre la
géométrie de la courbe/surface durant son évolution, afin d'obliger celle-ci à conserver une certaine
similarité avec une courbe/surface de référence.
Dans l'optique de reconstruire des structures tubulaires (ex: vaisseaux sanguins) à l'aide de modèles déformables,
formuler mathématiquement un a priori de « tubularité » s'avère difficile. Nous introduisons donc un modèle déformable
basé sur un cylindre généralisé, défini par une courbe centrale et une fonction rayon. Selon la dimension considérée,
il peut être vu comme une bande ou un tube d'épaisseur variable. Les extrémités étant fournies, la technique des
chemins minimaux est employée pour fournir une courbe initiale fiable. Tout comme un contour actif basé région,
le cylindre évolue par minimisation d'un critère d'homogénéité, formulé ici en fonction de la courbe et du rayon.
Nous nous intéressons également à la reconstruction de structures arborescentes en imagerie médicale. Dans ce cadre,
nous construisons un arbre dans lequel chaque branche est un cylindre déformable. L'arbre évolue ensuite dans son
ensemble, à l'aide d'une méthode prenant en compte les connexions et les relations (liens de parenté) entre les
branches.
jeudi 26 Mars 2009, 10h15 ou 14h00, Salle de Visio.
Emmanuelle Darles
(Université de Limoges, XLIM)
Simulation dynamique et rendu de scènes
océaniques en synthèse d'images réalistes
Résumé
Actuellement, les images de synthèse sont omniprésentes dans notre
quotidien. Le réalisme de ces images est grandissant, surprenant, et il
n'est souvent pas aisé de distinguer la réalité de la virtualité, cette
réalité faite et enrichie par toute la complexité des phénomènes naturels
qui nous entourent. L'eau est un de ces phénomènes dont la variété et la
richesse dynamique rend la représentation complexe. Nous nous
intéresserons dans cet exposé à sa forme la plus étendue, celle des
océans, qui font partie intégrante de nos paysages.
Dans un premier temps, nous décrirons brièvement quelles sont les méthodes
existantes permettant la simulation et le rendu de l'océan à la fois dans
le domaine physique mais aussi dans le domaine de la synthèse d'images
réalistes.
Puis nous montrerons une nouvelle méthode de rendu unifiée que nous avons
proposé, permettant une visualisation plus rapide de l'océan au large et
capable d'approximer les échanges lumineux surfaciques et
sous-surfaciques, l'écume et les phénomènes d'éblouissement.
Enfin, nous nous intéresserons à la représentation de vagues déferlantes
en proposant une nouvelle approche adaptative basée physique permettant de
reproduire ce phénomène et de réduire les temps de calculs imposés par la
résolution des équations de la mécanique des fluides en 3D.
jeudi 26 Mars 2009, 14h00, salle C6 au laic.
Florian Richoux
(Ecole Polytechnique, LAIC)
Complexité algorithmique des problèmes de satisfaction de contraintes.
Résumé
Les problèmes de satisfaction de contraintes (CSP) constituent un formalisme homogène pour modéliser de très nombreux problèmes algorithmiques et combinatoires.
Une instance de CSP est une conjonction de contraintes, ou prédicats, où les variables prennent leur valeur sur un domaine D.
On les retrouve dans l'étude de problèmes liés aux bases de données, à l'intelligence artificielle, au encore au raisonnement dans l'espace.
Le problème de décision d'une instance de CSP, à savoir
"existe t-il une solution pour une instance donnée satisfaisant toutes les contraintes ?",
est connu pour être NP-complet. Il existe pourtant des sous-classes de ce problème que l'on peut décider en temps polynomial.
En fait, on observe un phénomène de dichotomie: une restriction du problème est soit difficile (NP-complet) soit facile (polynomiale).
Ceci fait l'objet d'une conjecture dite de la dichotomie qui reste ouverte.
La séparation des cas polynomiaux et NP-complet se fait à travers l'étude d'une version paramétrique du problème de décision.
Dans cet exposé, le paramètre est l'ensemble des contraintes que l'on s'autorise à utiliser pour construire une instance de CSP.
Nous allons aborder dans cet exposé les dichotomies connues et introduire les récents résultats obtenus dans ce domaine.
jeudi 19 Mars 2009, 10h15, Salle de Visio.
Konrad Zdanovski
(Université Paris VI, LIAFA)
Glivenko theorem for the second order intuitionistic propositional logic without universal quantifiers
Résumé
The famous Glivenko theorem for the intuitionistic propositional logic,
IPC, states that a formula $\psi$ is a classical tautology if and only
if $\neg\neg\psi$ is an IPC tautology. We examine the second order
propositional intuitionistic logic, IPC2, and we extend Glivenko theorem
for formulas of IPC2 without universal quantifiers. As a corollary we obtain
a semantic argument that the universal quantifier is not definable in IPC2
from other logical operators. We will present also two semantics for IPC2,
the equivalence of which reminds an open problem.
jeudi 26 Février 2009, 10h15, Salle de Visio.
Emilie Koenig
(Université Blaise Pascal, LIMOS)
Synthèse de textures aléatoires : algorithme et applications
Résumé
Les études des images naturelles, ainsi que des textures aléatoires,
ont révélées deux propriétés: ces images sont invariantes en échelle
et ont des statistiques non-Gaussiennes. De nombreux modèles ont tenté
de modéliser les statistiques de ce type d'images. Nous nous intéresserons
ici au modèle des cascades infiniment divisibles et plus particulièrement
à la sous-famille des cascades de poisson composées (CPC) plus faciles à
manipuler numériquement. Ce modèle permet de synthétiser des champs
aléatoires en N dimensions invariants en échelle et aux statistiques
non-Gaussiennes. Deux domaines d'applications seront abordés. En physique
solaire, les images du soleil calme présentent les mêmes propriétés que
les images naturelles et peuvent être modélisées par CPC. Une extension
des CPC aux surfaces a permis de synthétiser des textures ayant les mêmes
caractéristiques que le soleil calme directement sur la sphère. Les
textures générées sont utilisées pour la validation d'un algorithme de
traitement d'images stéréographiques. De plus, une question essentielle
en physique solaire porte sur les caractéristiques d'images qui seraient
issues d'un télescope avec une résolution de 50km au lieu de 3800km. Une
méthode d'augmentation d'information basée sur les CPC a été développée
pour étudier quantitativement les propriétés d'images mieux résolues.
La seconde application des CPC se trouve en infographie : les nombreux
degrés de libertés permettent de générer une grande variété de textures
en 2D, 2D+t, 3D et sur des surfaces quelconques.
jeudi 29 Janvier 2009, 10h15, Salle de Visio.
Antoine Vacavant
(Université Louis Lumière Lyon II, LIRIS)
Géométrie discrète sur grilles irrégulières isothétiques
Résumé
Nous nous intéresserons à l'adaptation d'algorithmes
de géométrie discrète aux grilles irrégulières isothétiques. Ce
modèle de grille permet de représenter de manière générique les
structurations d'images en pixels ou voxels de taille et de position
variable (ou cellules) : les grilles anisotropes, très répandues en
imagerie médicale, les décompositions hiérarchiques telles que
quadtree/octree, les techniques de compression comme le run length
encoding, etc. Nous proposons d'étendre deux méthodologies largement
étudiées pour analyser les formes discrètes à cette représentation :
la reconstruction d'objets binaires complexes et la transformée en
distance.
jeudi 18 Décembre 2008, 10h15, Salle de Visio.
Smaïl Kaouache
(Université de Jijel, Algérie)
Sur une démonstration du théorème Skolem-Mahler-Lech
Résumé
Le théorème de Skolem-Mahler-Lech énonce que si une suite est
définie par une récurrence linéaire (comme la suite bien connue de
Fibonacci par exemple) alors l'ensemble des indices pour lesquelles
cette suite s'annule est une réunion finie d'ensembles finis ou
périodiques.
Des questions actuelles sont la décidabilité de propriétés de cet
ensemble (est-il fini? est-il vide? ...) ou la calculabilité d'une
borne lorsque cet ensemble est fini.
La preuve classique du théorème de Skolem-Mahler-Lech se développe
en analyse p-adique. Cet exposé présente une formulation destinée à
en évaluer l'effectivité.
jeudi 11 Décembre 2008, 14h00, Amphi B.
Olivier Teytaud
(LRI, Inria projet TAO)
Algorithmiques pour les jeux, le cas du Go et le reste
Résumé
Ancien étudiant de l'université d'Auvergne et
maintenant chercheur à l'Inria (Institut National de Recherche
en Informatique et Automatique) Olivier Teytaud, va présenter
la conception d'Intelligence Artificielle pour jouer à des jeux (dames,
échecs, backgammon, etc.
En particulier, il présentera les travaux
récents de son équipe sur MoGo, le
champion du monde actuel des programmes de Go qui rivalise même avec
les meilleurs joueurs humains.
Vous avez aimé le duel titanesque entre Kasparov et Deep Blue?
Venez découvrir MoGo, premier programme de niveau Dan.
jeudi 11 Décembre 2008, 10h15, Salle du Conseil.
Olivier Teytaud
(LRI, Inria projet TAO)
Fouille d'arbres par Monte-Carlo: les progrès en planification
Résumé
On présentera l'algorithme dit du Monte-Carlo Tree Search,
axé sur le parcours aléatoire d'arbres en "meilleure branche
d'abord", et son application (notamment parallèle) au jeu de Go.
Cet algorithme, utilisant peu d'expertise humaine est à la base d'un changement radical
de performance au multimillénaire jeu de Go.
jeudi 4 Décembre 2008, 14h30, Amphi B.
Thibault Marzais
(LAIC)
Reconstruction de surfaces paramétrées par LP-Fitting.
Résumé
La modélisation est un domaine qui est devenu primordial dans
l'informatique graphique de nos jours. On peut modéliser des objets
par des nuages de points, des maillages ou des surfaces de type
surfaces paramétrées.
Nous présentons la chaine complète de
reconstruction allant du maillage à un ensemble de surfaces
paramétrées. Ce processus fait intervenir plusieurs techniques comme
la segmentation de maillages, la paramétrisation et le fitting.
Nous présentons un nouvel algorithme de fitting, qui prend en
compte une norme uniforme en lieu et place de la norme euclidienne
dominante, permettant ainsi sa résolution par un programme linéaire.
jeudi 4 Décembre 2008, 10h15, Salle de Visio.
Rémi Brochenin
(Laboratoire Spécification et Vérification, CNRS, ENS Cachan)
Des pouvoirs de la baguette magique.
Résumé
Nous nous plaçons dans le cadre des méthodes formelles qui permettent de
vérifier des programmes. Des formalismes logiques sont utilisés pour la
spécification. Plus particulièrement, nous nous intéressons aux programmes
à pointeurs manipulant directement la mémoire. La logique de séparation
est un langage de spécification introduit pour de tels programmes. Elle
permet de raisonner localement par l'usage de deux opérateurs idoines,
l'un séparant la mémoire, et l'autre l'étendant par un contexte. Le
premier est appelé "étoile", et l'autre "baguette magique". Après une
introduction aux méthodes de vérification avec cette logique, nous
définirons et expliquerons la logique de séparation. Je pourrai enfin
présenter nos résultats comparant la logique de séparation à la logique du
second ordre.
jeudi 27 Novembre 2008, 10h15, Salle de visio.
Arnaud Carayol et Didier Caucal
(CNRS, Institut Gaspard Monge, Université Paris-Est Marne-la-Vallée)
Algorithmique et langages sur les graphes réguliers.
Résumé
Les graphes réguliers sont des graphes orientés ayant un
nombre possiblement infinis de sommets de décomposition finie par distance.
Plus précisément, la suppression par distance croissante à partir
d'un sommet fixé,
ne fait apparaître qu'un nombre fini de composantes connexes
(à renommage des sommets près).
Du point de vue de l'algorithmique, ces graphes sont engendrés (à la
limite) par un système fini
de réécriture de graphes appelé grammaire déterministes de graphes .
Ce mécanisme élémentaire
est parfaitement adapté pour étendre la théorie de graphes finis ou
graphes réguliers.
Du point de vue de la théorie des langages formels, ces graphes
peuvent être considérés comme des
automates infinis reconnaissant les langages algébriques. Ils
fournissent ainsi une vision structurelle
des langages algébriques.
Dans cet exposé, nous présenterons deux résultats récents sur
l'algorithmique des graphes réguliers: accessibilité,
extraction d'un arbre couvrant, ... et en théorie des langages:
définition des sous-familles des langages algébriques
ayant des propriétés de clôtures analogues langages rationnels.
jeudi 20 Novembre 2008, 10h15, Salle de visio.
Stefan Dantchev
(University of Duham, ACiD)
Complexity Gaps in Propositional Proof Complexity
Résumé
We will start by briefly introducing the area of Propositional Proof
Complexity. We will then make a case for studying the proofs of certain
uniformly generated families of propositional tautologies and
relate this to the existence of a model at infinity. We will finally
illustrate this approach with so-called Complexity Gap theorems
for two propositional proof systems: Tree-like Resolution and
Lovasz-Schrijver lift-and-project method.
jeudi 13 Novembre 2008, 10h15, Salle de visio.
Stefan Szeider
(University of Duham, ACiD)
Tricky Problems for Graphs of Bounded Treewidth
Résumé
In this talk I will consider computational problems that
jeudi 23 Octobre 2008, 10h15, .
Marc Chevaldonné
(Laic)
Système de gestion de versions : concepts et utilisations
Résumé
Aujourd'hui, le développement d'applications logicielles par un ou
plusieurs utilisateurs distincts et souvent distants peut rapidement
devenir complexe : le développement de différents modules et
bibliothèques sous différentes versions, la fusion de code source
provenant de différents développeurs, le retour à une version
antérieure sont autant de problématiques qu'un système de gestion de
versions permet de résoudre simplement et efficacement.
Le but de cet exposé est de présenter le système Subversion à
travers l'exemple, afin de convaincre l'auditoire de l'utiliser pour
ses projets, aussi bien ceux qui développent en solo que ceux qui
travaillent en équipe.
J'utiliserai pour cela une version graphique de Subversion intitulée
Tortoise pour réaliser des démonstrations mono et multi utilisateurs
et présenter les avantages de l'utilisation de tels outils.
Cet exposé ne présentera donc qu'un faible intérêt scientifique mais
proposera des méthodes de travail pour une équipe de développement,
quelles que soient leurs thématiques, qui si elles sont suivies,
réduira significativement le temps de développement d'applications
ou de simples tests et améliorera la qualité des développements.
jeudi 16 Octobre 2008, 10h15, Salle de visio.
Alexandre Guitton
(Limos, Université Blaise Pascal)
Étude de complexité des problèmes d'arbres optiques
Résumé
Dans cet exposé, nous présentons deux problèmes de construction
d'arbres de communication multicast dans un réseau tout optique. Après
avoir rappelé ce qu'est un réseau tout optique et la contrainte de
duplication des noeuds dans un tel réseau, nous montrons qu'une telle
contrainte peut être problématique lors de la réalisation d'arbres
multicast. Lors de la construction d'arbres de coût minimum, la
contrainte de duplication ne change pas la nature de la complexité du
problème. En revanche, lorsque l'on s'intéresse à la construction
d'arbres des plus courts chemins, la contrainte de duplication rend le
problème beaucoup plus difficile à résoudre. Nous donnons rapidement
les idées de la preuve de la NP-complétude de ce dernier problème,
ainsi que de la preuve de sa non (2-epsilon)-approximabilité, pour
epsilon positif. L'exposé se termine sur quelques questions ouvertes
concernant la contrainte de duplication et les arbres optiques.
jeudi 9 Octobre 2008, 10h15, Salle de visio au bloc central.
Yan Gérard
(Laic)
Reconstruction d'une matrice en tomographie discrète
Résumé
D. Gale et H.J. Ryser ont montré indépendamment en 1957 que la reconstruction
d'une matrice binaire -avec uniquement des 0 et des 1- dont les sommes des
lignes et des colonnes sont fixées au préalable peut être résolue en temps
polynomial.
Ce problème initial a conduit à de nombreuses généralisations du côté des
problèmes de flux -puisque le problème de Gale et Ryser peut naturellement se
traduire en un problème de mariage dans un graphe biparti complet- du côté des
problèmes d'emploi du temps, de la tomographie discrète...
Nous considérerons dans cet exposé les variantes qui consistent à introduire
différentes contraintes -locales ou globales- sur les coefficients que nous ne
restreignons plus nécessairement à 0 ou 1 et parmi les principales classes que
nous imaginerons, nous essaieront de donner leur complexité. Nous montrerons
ainsi en particulier que la généralisation du problème de Gale-Ryser avec une
liste de mn coefficients donnée est un problème NP-difficile.
jeudi 2 Octobre 2008, 10h05, Salle A5.
Mirek Kutylowski
(école Polytechnique de Wroclaw, Pologne)
Secure data transmission in the world of tiny artefacts
Résumé
Emerging pervasive systems incorporate growing number of cheap tiny devices
of low computational power and limited communication capabilities.
Typically, they are unresistant to any serious reverse-engineering attack.
Also, they are too weak to implement any even moderately sophisticated
cryptographic solution. Among others, the asymmetric methods are
typically too ``heavy'' for them.
Despite extreme demands on simplicity, it turns out that
certain security functionalities can be achieved. For this purpose
we abandon algebraic cryptographic methods and relay
on combinatorial difficulty of certain problems.
We present some recent work concerning:
jeudi 25 Septembre 2008, 10h15, Salle B21.
Julien Tierny
(LIFL - Telecom Lille 1)
Modélisation de forme 3D par graphe de Reeb et applications
Résumé
Avec le développement récent des technologies 3D, les formes 3D sont devenues
un type de données multimedia interactives de première importance. Leur
représentation la plus courante, le maillage de polygones, souffre cependant
de grande variabilité face à des transformations canoniques préservant la
forme. Il est donc nécessaire de concevoir des techniques de modélisation
intrinsèque de forme. Dans cette thèse, nous explorons la modélisation
topologique par l'étude de structures basées sur les graphes de Reeb. En
particulier, nous introduisons une nouvelle abstraction de forme, appelée
squelette topologique avancé, qui permet non seulement l'étude de l'évolution
topologique des lignes de niveau de fonctions de Morse mais aussi l'étude de
leur évolution géométrique. Nous démontrons l'utilité de cette représentation
intrinsèque de forme dans trois problèmes de recherche liés à l'Informatique
Graphique et à la Vision par Ordinateur. Tout d'abord, nous introduisons la
notion de calcul géométrique sur les graphes de Reeb pour le calcul
automatique et stable de squelettes de contrôle pour la manipulation
interactive de forme. Ensuite, en introduisant les notions de cartes de Reeb
et de motifs de Reeb, nous proposons une nouvelle méthode pour l'estimation
de similarité partielle entre formes 3D. Nous montrons que cette approche
dépasse les méthodes participant au concours international de reconnaissance
de forme 2007 (SHREC 2007) par un gain de 14%. Enfin, nous présentons deux
techniques permettant de fournir une décomposition fonctionnelle d'une forme
3D, à la fois en considérant des heuristiques issues de la théorie de la
perception humaine et des données 3D variant dans le temps. Des exemples
applicatifs concrets viennent illustrer l'utilité de notre approche pour
chacun de ces problèmes de recherche..