I am pleased to announce that the following paper has been accepted
to the Mirage 2007 (http://acivs.org/mirage2007/) an international
conference on Computer Vision / Computer Graphics Collaboration
Techniques and Applications.
J. Darbon. A Note on the Dicerete Binary Mumford-Shah Model.
This paper is concerned itself with the analysis of the twophase
Mumford-Shah model also known as the active contour without
edges model introduced by Chan and Vese. It consists of approximating
an observed image by a piecewise constant image which can take only
two values. First we show that this model with the L1-norm as data
fidelity yields a contrast invariant filter which is a well known property
of morphological filters. Then we consider a discrete version of the original
problem. We show that an inclusion property holds for the minimizers.
The latter is used to design an efficient graph-cut based algorithm which
computes an exact minimizer. Some preliminary results are presented
***************************************************************************
I am also pleased to announce that the following twin papers have
been published in the Journal of Mathmematical Imaging and Vision
(http://www.springerlink.com/content/u8388810354q/?p=e3972a8e80d5433daf4bc20…)
J. Darbon and M. Sigelle
Image Restoration with Discrete Constrained Total Variation Part I: Fast and
Exact Optimization
Journal of Mathematical Imaging and Vision. Journal of Mathematical Imaging and
Vision. Vol 26 n.3, pp. 277-291, December 2006.
This paper deals with the total variation minimization problem in image
restoration for convex data fidelity functionals. We propose a new and fast
algorithm which computes an exact solution in the discrete framework. Our
method relies on the decomposition of an image into its level sets. It maps the
original problems into independent binary Markov Random Field optimization
problems at each level. Exact solutions of these binary problems are found
thanks to minimum cost cut techniques in graphs. These binary solutions are
proved to be monotone increasing with levels and yield thus an exact solution
of the discrete original problem. Furthermore we show that minimization of
total variation under L1 data fidelity term yields a self-dual contrast
invariant filter. Finally we present some results.
J. Darbon and M. Sigelle
Image Restoration with Discrete Constrained Total Variation Part II: Levelable
Functions, Convex and Non-Convex Cases
In Part II of this paper we extend the results obtained in Part I for total
variation minimization in image restoration towards the following directions:
first we investigate the decomposability property of energies on levels, which
leads us to introduce the concept of levelable regularization functions (which
TV is the paradigm of). We show that convex levelable posterior energies can be
minimized exactly using the level-independant cut optimization scheme seen in
Part I. Next we extend this graph cut scheme to the case of non-convex
levelable energies.We present convincing restoration results for images
corrupted with impulsive noise. We also provide a minimum-cost based algorithm
which computes a global minimizer for Markov Random Field with convex priors.
Last we show that non-levelable models with convex local conditional posterior
energies such as the class of generalized Gaussian models can be exactly
minimized with a generalized coupled Simulated Annealing.
----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
I am pleased to announce that I have been invited to speak at the next IMECS
conference, Hong Kong, March 2007. The chosen topic is given below. A
corresponding paper will be available soon.
CLOS solutions to binary methods
Impementing binary methods in traditional object oriented languages is
difficult: numerous problems arise, such as typing (covariance vs.
contravariance of the arguments), polymorphism on multiple arguments (lack of
multi-methods) etc. The purpose of this paper is to demonstrate how those
problems are either solved, or inexistent in the Common Lisp Object System
(CLOS). Several solutions for implementing binary methods in CLOS are
proposed. They mainly consist in re-programming a binary-method specific
object system through the CLOS meta-object protocol.
--
Didier Verna, didier(a)lrde.epita.fr, http://www.lrde.epita.fr/~didier
EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (1) 44 08 01 85
94276 Le Kremlin-Bicêtre, France Fax.+33 (1) 53 14 59 22 didier(a)xemacs.org
We are pleased to announce that the following paper has been accepted
to the Fifth IEEE International Conference on Computer Sciences,
Research, Innovation and Vision for the Future (RIVF'07 --- www.rivf.org).
Stochastic routing in large grid-shaped quantum networks
https://publis.lrde.epita.fr/200703-RIVF
Cuong Le Quoc Patrick Bellot Akim Demaille
ENST ENST EPITA Research and
qle(a)enst.fr bellot(a)enst.fr Development Laboratory (LRDE)
Akim.Demaille(a)lrde.epita.fr
This paper investigates the problem of secret key transmissions for
an arbitrary Alice-Bob pair in Quantum Key Distribution (QKD)-based
networks. We develop a realistic QKD-based network framework and we
show that the key transmission problem on such a framework can be
considered as a variant of the classical percolation problem. We also
present an adaptive stochastic routing algorithm protect from
inevitable eavesdroppers. Simulations were carried out not only to
validate our approach, but also to compute critical parameters
ensuring security. These results show that large quantum networks with
eavesdroppers do provide security.
Bonjour,
Vous êtes tous cordialement invités à assister au séminaire qui aura
lieu les jeudi 7 décembre et vendredi 8 décembre 2006 à 14 heures en
salle amphi Masters (KB).
-----------------------------------------------------------------------
Le programme du 7 décembre:
*VAUCANSON, THÉORIE DES JEUX & OLENA*
http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2006-12-07
VAUCANSON
14h00 : Présentation du TAF-Kit -- Robert Bigaignon
14h45 : État des lieux des propositions XML pour les automates --
Florent Terrones
THÉORIE DES JEUX
15h45 : Recherche d'un epsilon-Nash de support de taille 2 -- Michaël
Cadilhac
OLENA
16h30 : Extractions d'objets : l'algorithme Fast Level Lines Transform
(FLLT) -- Christophe Berger
-----------------------------------------------------------------------
Le programme du 8 décembre:
*OLENA, THÉORIE DES JEUX, BDD & PARALLÉLISATION DE CALCULS*
http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2006-12-08
OLENA
14h00 : Extraction automatique d'artères à partir d'images médicales 3D
-- Nicolas Widynski
THÉORIE DES JEUX
14h45 : Poker AI -- Johan Oudinet
BDD
15h45 : BDD distribués, Java, Threads, et optimisations -- Guillaume Guirado
PARALLÉLISATION DE CALCULS
16h45 : Parallélisme appliqué au traitement d'image -- Alexandre Borghi
THÉORIE DES JEUX
17h30 : Les systèmes de recommandations -- Thomas Largillier
-----------------------------------------------------------------------
Les Résumés des exposés du 7 décembre :
***************************************
VAUCANSON
* Présentation du TAF-Kit -- Robert Bigaignon
La plate-forme de manipulation d'automates finis Vaucanson propose
depuis peu un ensemble d'outils permettant la manipulation d'automates
au travers de simples programmes Unix, à la façon de FSM
(http://www.research.att.com/~fsmtools/fsm/). Ces programmes sont réunis
dans le Typed Automata Functions Kit (TAF-Kit) et s'appuient directement
sur la bibliothèque C++, cœur du projet Vaucanson. Ils fournissent ainsi
à l'utilisateur un sous-ensemble des services déjà présents dans
Vaucanson (algorithmes et entrées-sorties) tout en lui épargnant
l'écriture de programmes C++.
Nous présenterons les fonctionnalités du TAF-Kit ainsi que les outils
dont il dispose pour mesurer ses performances.
* État des lieux des propositions XML pour les automates -- Florent Terrones
Les utilisateurs de logiciels de manipulation d'automates ont exprimé
depuis quelques années le besoin de disposer d'un format de fichier
universel de description d'automates.
L'équipe Vaucanson a présenté dès 2004 pour la conférence CIAA'04 une
proposition de format XML pour la description d'automates à états finis.
Cette dernière a subi de nombreuses modifications et suivi différentes
lignes directrices pour en arriver à la version actuelle.
Le but de ce séminaire est de faire un état des lieux de cette
proposition et des avantages qu'elle apporte. Une description des autres
propositions ainsi que leurs différentes caractéristiques seront
également présentées.
THÉORIE DES JEUX
* Recherche d'un epsilon-Nash de support de taille 2 -- Michaël Cadilhac
Dans le cadre de la théorie des jeux, la recherche d'un équilibre tel
qu'aucun joueur ne puisse augmenter ses gains en changeant de stratégie
est primordiale. De récents résultats montrent que l'obtention
algorithmique de cet équilibre, dit de Nash, n'est pas abordable en
temps raisonnable.
Depuis 2003 et les résultats de Lipton, on s'est rendu compte que
chercher un équilibre approximatif, à un epsilon près, amenait à des
algorithmes de plus faible complexité et un contexte plus humainement
parlant.
Nous étudierons des algorithmes permettant la recherche d'un équilibre
de Nash approximé dans un cadre où les joueurs choisissent de manière
probabiliste entre deux stratégies parmi une multitude.
OLENA
* Extractions d'objets : l'algorithme Fast Level Lines Transform (FLLT)
-- Christophe Berger
Il existe de nombreux algorithmes de segmentation. Nous présenterons ici
le FLLT qui se base sur le principe de composantes connexes séparées par
les lignes de niveaux. En effet, il existe sur une image, comme sur une
carte géographique, des lignes formées par les différences entre les
zones. Dans une image ces différences sont matérialisées par la teinte
ou le contraste.
Nous verrons tout d'abord les spécificités de cet algorithme et des
différentes structures utilisées afin de détecter les lignes de niveaux,
nous proposerons également une comparaison avec le max-tree et
présenterons les différences de ces deux méthodes. Finalement nous
verrons en quoi FLLT est intéressant dans la pratique grâce a son
implémentation dans Olena.
-----------------------------------------------------------------------
Les Résumés des exposés du 8 décembre :
***************************************
OLENA
* Extraction automatique d'artères à partir d'images médicales 3D --
Nicolas Widynski
Depuis le début du 20ème siècle, les techniques d'acquisition employées
en imagerie médicale sont en constante évolution. Rayons X, IRM,
ultra-sons et imagerie nucléaire sont des outils physiques permettant
l'acquisition de différentes données telles que le scanner,
l'echographie, la radiographie... Face à l'amélioration de ces
techniques d'acquisition et au nombre croissant des données à traiter,
le rôle du traiteur d'images médicales est d'extraire le maximum de
caractéristiques et d'agencer au mieux les données, dans le but d'aider
le spécialiste médical à effectuer son diagnostique.
Plus spécialement, le scanner peut nous permettre d'acquérir des données
3D. Notre rôle consiste ici à en extraire les artères coronaires. Pour
ce faire, nous emploierons la méthode décrite par Thierry Géraud et
Jean-Baptiste Mouret dans Fast Road Network Extraction in Satellite
Images Using Mathematical Morphology and Markov Random Field (EURASIP
2004), en divisant notre chaîne de traitement en deux étapes :
l'extraction d'une surface à partir de données 3D, puis l'extraction
d'une ligne, représentant notre artère, à partir de cette surface. Nous
développerons également les outils nécessaires à cette segmentation, à
savoir la convolution gaussienne, la ligne de partage des eaux, le
graphe d'adjacence de régions et les champs Markoviens.
THÉORIE DES JEUX
* Poker AI -- Johan Oudinet
Une des stratégies les plus utilisées pour créer une intelligence
artificielle (IA) dans un jeu où les joueurs jouent à tour de rôle,
consiste à construire l'arbre associé : chaque branche d'un nœud
correspond à une stratégie possible du joueur qui doit jouer à ce nœud.
Le problème avec le poker, ou tout autre jeu à information imparfaite,
c'est qu'on ne connaît pas les stratégies accessibles à l'adversaire
(elles dépendent des cartes qu'il a reçues). Ainsi, à chaque décision
prise par l'adversaire, on doit se référer à son modèle pour améliorer
la qualité des décisions. Un excellent joueur de poker arrive à deviner
avec précision la main de son adversaire, c'est l'objectif que doit
atteindre le modèle.
Au cours de cette présentation, nous nous intéresserons au Texas Hold'em
qui est une des variantes les plus complexes du poker et la plus
populaire actuellement. Nous présenterons une IA utilisant un modèle
d'adversaire pertinent.
BDD
* BDD distribués, Java, Threads, et optimisations -- Guillaume Guirado
Lors d'une précédente présentation, les BDD (diagrammes de décision
binaires) distribués ont été étudiés. Leur implantation, en Java, a
montré ses limites lors des tests de performances.
Une des idées proposées afin d'accélérer les calculs était de mieux
gérer les processus, ou threads. Premièrement, limiter le nombre de
processus simultanés permet d'éviter de nombreuses restaurations des
registres du processeur. Second point, une file d'attente des processus
avec un contrôle intelligent des processus prioritaires ou non pourrait
augmenter la parallélisation de l'application. Nous verrons ce qu'il en
est dans les faits.
Enfin, le monde Java dispose de nombreux compilateurs ou optimiseurs
susceptibles d'améliorer les performances. Nous testerons un certain
nombre de ces outils et verrons si oui ou non, les résultats en sont
améliorés.
PARALLÉLISATION DE CALCULS
* Parallélisme appliqué au traitement d'image -- Alexandre Borghi
Le parallélisme permet d'effectuer plusieurs opérations simultanément
tout en tirant parti d'une mémoire partagée. Aujourd'hui, l'informatique
grand public permet d'utiliser cette capacité autrefois réservée aux
professionnels du fait de leurs grands besoins en puissance de calcul.
Ce séminaire vise à explorer certaines techniques permettant la
conception de bibliothèques parallélisées. L'objectif est de faciliter
l'écriture d'algorithmes parallèles tout en cachant un maximum de
détails implémentatoires superflus sans perdre en fonctionnalité.
Le traitement d'image a été choisi comme cadre de travail et plusieurs
algorithmes ont été sélectionnés pour illustrer les concepts rencontrés.
THÉORIE DES JEUX
* Les systèmes de recommandations -- Thomas Largillier
La multiplication des sites de ventes sur le Net a poussé à une plus
grande fidélisation des clients. Ceci passe par une offre plus ciblée
correspondant mieux à chaque utilisateur. On assiste donc à une
émergence des systèmes de recommandations. Ces systèmes se basent sur
les achats déjà effectués et la ressemblance de comportements entre les
utilisateurs pour proposer des produits toujours plus attractifs. Nous
ferons ici une présentation de plusieurs d'entre eux ainsi qu'une
comparaison.
--
Daniela Becker
Bonjour,
Nous avons le plaisir de vous présenter le n°7 du bulletin du LRDE.
Vous y trouverez des informations sur le travail de deux des doctorants
du labo. Et les résumés des exposés des CSI 2007: au cours de leurs deux
derniers séminaires programmés les 7 et 8 décembre 2006, ils
présenteront la conclusion de leur passage au LRDE.
Vous pouvez télécharger le bulletin en couleur à la page suivante:
http://publis.lrde.epita.fr/200611-l-air-de-rien-7
--
Daniela Becker
Le LRDE est heureux d'accueillir un nouveau doctorant : Alexandre
Hamez.
Il commence une thèse intitulée « Model checking réparti » sous la
direction de Fabrice Kordon (LIP6/MoVe) et des co-encadrants Akim
Demaille (EPITA/LRDE) et Yann Thierry Mieg (LIP6/MoVe), après avoir
obtenu un master Systèmes et Applications Distribués à l'université
Pierre et Marie Curie (Paris VI).
Le model checking est une technique de vérification formelle
permettant de prouver que le comportement d'un système est correct.
Cependant, elle est très souvent sujette à une utilisation prohibitive
du temps de calcul, ceci à cause du problème dit de l'explosion de
l'espace d'états.
La répartition du model checking est apparue récemment comme solution
possible à ce problème en utilisant les avantages d'un réseau de
machines, augmentant de ce fait la taille mémoire et la puissance de
calcul disponible. Le but de son travail est de répartir le processus
de model checking, en se focalisant sur le cas particulier des
clusters, lesquels offrent un environnement dédié au calcul réparti.
Il a aussi comme objectif de fournir un framework facilitant la
répartition de model checkers existants. De plus il souhaite y
intégrer des techniques de réduction d'espace d'états, tels que les
diagrammes de décision.
Alexandre Hamez suit ainsi d'une année Alban Linard, avec un parcours
tout à fait similaire, et montre les bonnes relations qui lient le
LRDE et l'équipe MoVe du LIP6.
--
LIP6 Laboratoire d'Informatique de Paris 6
http://www.lip6.fr/fr/index.html
LRDE Laboratoire de Recherche et Développement de l'EPITA
http://www.lrde.epita.fr
MoVe Modélisation et Vérification
http://www.lip6.fr/en/recherche/team.php?id=720
UPMC Université Pierre et Marie Curie (Paris VI)
http://www.upmc.fr/FR/info/00
[Désolé pour l'éventuel doublon, nous avions des problèmes avec notre
gestion des news.]
« Modeling of Sensor Networks Using XRM »
Akim Demaille, Sylvain Peyronnet, Benoît Sigoure
http://publis.lrde.epita.fr/200609-ISOLA
Accepted to 2nd International Symposium on Leveraging Applications of
Formal Methods, Verification and Validation (ISOLA 2006)
Sensor networks are composed of small electronic devices that embed
processors, sensors, batteries, memory and communication
capabilities. One of the main goals in the design of such systems is
the handling of the inherent complexity of the nodes, exarcerbated by
the huge number of nodes in the network. For these reasons, it becomes
very difficult to model and verify such systems. In this paper, we
investigate the main characteristics of sensor nodes, discuss the use
of a language derived from Reactive Modules for their modeling, and
propose a language (and a tool set) that ease the modeling of this
kind of systems.
J'avais oublié d'en parler à la réunion précédente: j'ai également écrit un article sur CurVe pour le PracTeX Journal paru le 15 Août.
http://www.tug.org/pracjourn/
--
El Didou
