🚀 go-pugleaf

           I N R I A
( Institut National de Recherche en
  Informatique et en Automatique)

     Unite de recherche de
        Sophia Antipolis


                  Voici la liste des derniers rapports de recherche
                    de l'U.R. disponibles  electroniquement :

 - Soit par ftp anonyme sur l'une ou l'autre de ces machines :
           zenon.inria.fr , directory /pub/rapports
           ftp.inria.fr   , directory /INRIA/publication/RR ou RT (a venir)
           (les rapports sont en version postscript)

 - Soit par WAIS (les rapports sont indexes sur le texte integral)
   acces dans  les deux bases suivantes : 

   name            : ra-zenon-inria-fr.src        (documents en format DVI)
   serveur	   : zenon.inria.fr
   service	   : 210
   database        : ra-zenon-inria-fr
   cost	           : 0
   units	   : :free
   maintainer      : root@zenon.inria.fr

  name             : ra-mime-zenon-inria-fr.src  (Documents en format MIME
  serveur	   : zenon.inria.fr               contenant le resume et le
  service	   : 210                          fichier postscript)
  database         : ra-mime-zenon-inria-fr
  cost	           : 0
  units	           : :free
  maintainer       : doc@zenon.inria.fr

   (Pour toute information sur WAIS vous pouvez nous contacter :
       Luc Ottavj         ottavj@sophia.inria.fr
       Marie-Helene Comte comte@sophia.inria.fr )

---------------------------------------------------------------------------


RR2244 Vlad Bally, Denis Talay: 


                     The  Law  of the Euler  Scheme 
                for  Stochastic  Differential Equations:
             I. Convergence Rate of the Distribution Function

                     La    loi  du  schema  d'Euler  
            pour    les  equations differentielles stochastiques : 
           I. Vitesse de convergence de la fonction de repartition


                               Mars 1994


En anglais


We study the approximation problem  of IEf(XT) by IEf(XnT), where (Xt)
is the    solution of a stochastic    differential equation,  (Xnt) is
defined by the Euler discretization  scheme with step  T_n, and f is a
given function. For  smooth f's, Talay  and Tubaro have shown that the
error IEf(XT) - f(XnT) can be expanded in powers of 1_n, which permits
to  construct   Romberg  extrapolation procedures  to   accelerate the
convergence rate. Here, we prove that the expansion exists also when f
is   only supposed  measurable  and   bounded,   under an   additional
nondegeneracy condition  of  Hormander   type for the   infinitesimal
generator  of  (Xt): to  obtain  this result,  we use   the stochastic
variations calculus.
   In the second part of  this work, we  will consider the density  of
the law of XnTand compare it to the density of the law of XT.

On  etudie le probleme de l'approximation  de IEf(XT) par IEf(XnT), ou
(Xnt) est defini par  le  schema d'Euler de  pas   T_n, et f est   une
fonction donnee. Pour des fonctions  f regulieres, Talay et Tubaro ont
montre  que  l'erreur de  discretisation  IEf(XT)  - f(XnT)  peut etre
developpee en  puissances de 1_n,   ce qui  permet  de construire  des
algorithmes   d'extrapolation   de   Romberg     pour  accelerer    la
convergence. Dans   cet article,  on montre qu'un    tel developpement
existe aussi quand f est supposee  seulement mesurable et bornee, sous
une condition supple mentaire  de non degenerescence de type Hormander
pour le generateur infinitesimal de (Xt): pour obtenir ce resultat, on
utilise les outils du calcul des variations stochastiques.
   Dans la seconde partie de ce travail,  nous considererons la loi de
la densite de XnT et la comparerons a la densite de la loi de XT.


----------------------------------------------------------------------

RR2273 Zhengyou Zhang, Rachid Deriche, Olivier Faugeras, 
       Quang-Tuan Luong :


       A  Robust Technique for Matching  Two  Uncalibrated Images 
         Through the Recovery of the Unknown Epipolar Geometry

         Mise en correspondance robuste d'images non calibrees 
              par recouvrement de la geometrie epipolaire


                                Mai 1994

En anglais


This paper proposes a robust  approach to image matching by exploiting
the only  available   geometric  constraint,  namely, the     epipolar
constraint. The images areuncalibrated, namely the motion between them
and the  camera  parameters are  not  known.  Thus, the images  can be
taken by different  cameras or   a single  camera at different    time
instants.  If we make an exhaustive  search for the epipolar geometry,
the  complexity  is prohibitively   high.   The  idea  underlying  our
approach  is  to use  some    classical techniques  (correlation   and
relaxation methods in   our   particular implementation) to    find an
initial set  of  matches, and  then use  a robust technique_the  Least
Median of Squares (LMedS)_to  discard false matches  in this set.  The
epipolar  geometry can  then  be accurately  estimated   using a  well
adapted   criterion. More matches  are  eventually found, as in stereo
matching, by using the recovered epipolar geometry.  A large number of
experiments have beencarried out,  and  very  good results have   been
obtained.
  Regarding    the relaxation technique,  we define   a new measure of
matching support, which allows a  higher tolerance to deformation with
respect to  rigid  transformations in  the image  plane and a  smaller
contribution for distant matches than for  nearby ones. A new strategy
for  updating matches is  developed, which only  selects those matches
having both  high  matching support and  low  matching ambiguity.  The
update strategy   is different  from the classical  "winner-take-all",
which is    easily   stuck at    a  local minimum,    and   also  from
"looser-take-nothing",   which is  usually   very slow.   The proposed
algorithm has been widely tested and works  remarkably well in a scene
with many repetitive patterns.


Dans cet article,  nous proposons une approche  robuste au probleme de
la  mise  en correspondance de  primitives  dans le  cas  d'images non
calibrees i.e on  ne dispose ni du mouvement  entre les cameras ni des
parametres intrinseques  associes  a chacune  des cameras.  Les images
peuvent ainsi  etre  considerees comme prises par   une meme camera  a
differents instants ou par un  systeme stereoscopique de 2 cameras. Du
a la complexite de la tache,  une recherche exhaustive de la geometrie
epipolaire ne peut  evidemment etre entreprise.  L'idee principale  de
l'approche que   nous  developpons est d'utiliser,  dans  une premiere
phase, des methodes classiques de type  correlation et relaxation afin
de trouver  un premier ensemble   d'appariements entre points a  forte
courbure des  2  images.  Une seconde  phase fait  alors  appel a  des
methodes robustes de type  - Moindres  medianes  des erreurs au  carre
(Least Median of Squares  ou  LMedS) -  afin d'eliminer les  eventuels
faux appariements. La geometrie epipolaire est  alors estimee a l'aide
de cet ensemble  d'appariements et  de  l'utilisation de  criteres  de
minimisation adequats et bien adaptes au probleme de sa determination.
Une  ultime  phase  de   recherche  des  appariements   respectant  la
contrainte de  la  ligne  epipolaire peut  alors  etre effectuee  afin
d'ameliorer encore  les resultats.  Un  grand nombre d'experiences ont
ete menees  et d'excellents  resultats ont  ete  obtenus.  
  Concernant la technique de relaxation utilisee, nous definissons une
nouvelle   mesure d'appariement qui   associe une grande tolerance aux
deformations  rigides dans le plan   image, et qui  associe une faible
(resp.  grande)  contribution   aux appariements    lointains   (resp.
proches). Une nouvelle strategie pour  la mise a jour des appariements
est  developpee.  Elle permet  de ne selectionner que les appariements
qui  ont  un   large support  de   correspondance et  un faible  score
d'ambiguite.  Cette mise a jour est differente de l'approche classique
dite  "le vainqueur prend  tout" (winner-take-all) sujette au probleme
des minima locaux, et aussi  differente de  l'approche "le perdant  ne
gagne rien" (looser  take nothing) qui  est  tres lente.  L'algorithme
propose a ete  largement teste et  fonctionne remarquablement bien sur
des scenes a motifs periodiques.

----------------------------------------------------------------------

RR2274 Xavier Pennec, Nicholas Ayache:


        An O(n2) Algorithm for 3D Substructure Matching of Proteins

        Un Algorithme  en O(n2) pour  le recalage de  sous-structures 
                            dans les proteines


                                 Mai 1994

En anglais


Most biological  actions of proteins  depend on some  typical parts of
their three-dimensional  structure, called 3D motifs. To automatically
discover corresponding 3D motifs between proteins, we propose a new 3D
substructure   matching      algorithm  based  on    geometric hashing
techniques. The key feature of the method is  the introduction of a 3D
reference frame  attached to each amino acid.   This allows to compute
for  every couple    of   amino acids  6 invariants,     and therefore
drastically  reduce  the  complexity  of  both  the  preprocessing and
recognition stages of  geometric  hashing,   typically to  O(n2).  
  A    thorough  analysis  of  the  propagation     of the  errors  in
preprocessing and the introduction of extended Kalman filtering insure
efficiency and robustness during the recognition stage.
  Our  experimental results confirm  the validity of the approach, and
the remarkable stability of the 6 rigid  invariants used for matching.
We believe that this  new algorithm, because  of the reduction  of the
algorithmic complexity   it   implies,   will allow  the    systematic
comparison of very large structures in the near future.


La plupart des actions biologiques des  proteines dependent de parties
precises de  leur structure 3D  que l'on nomme motifs.  Pour decouvrir
automatiquement  les motifs 3D se  correspondant entre proteines, nous
proposons un  nouvel algorithme    de reconnaissance et    recalage de
sous-structures 3D base sur des  techniques  de geometric hashing.  Le
point cle  de la methode est  l'introduction d'une base Euclidienne 3D
attachee a chaque acide amine, ce  qui permet de calculer 6 invariants
par couple d'acides amines, et par la meme de reduire drastiquement la
complexite, typiquement en O(n2).
  Une  analyse precise de la  propagation des  erreurs dans l'etape de
pretraitement et l'introduction   du filtre de Kalman etendu  assurent
l'efficacite et la robustesse   lors    de la reconnaissance.      
  Nos resultats experimentaux confirment  la validite de l'approche et
la stabilite remarquable     des  6  invariants  utilises   pour    le
matching. Nous  croyons  que ce  nouvel  algorithme permettra dans  un
futur  proche la comparaison systematique   de tres grandes structures
grace a la reduction de la complexite qu'il autorise.

----------------------------------------------------------------------

Anita Guiteau                       
 INRIA Sophia Antipolis                
 Centre de Documentation                      |  Tel : (33) 93 65 77 57/77 55
 BP 93                                                     |  Fax : (33) 93 65
79 33
 06902 Sophia Antipolis Cedex (France) |  Email:Anita.Guiteau@sophia.inria.fr