🚀 go-pugleaf

           I N R I A
( National Institute for Research in
  Computer Science and Automation)

     Unite de recherche de
        Sophia Antipolis


                      INRIA-SOPHIA ANTIPOLIS
                          Technical report
                            OCTOBER 1992


The  following technical reports  are available.  If  you want a paper
copy send a email to : doc@sophia.inria.fr
You can  also obtain by the net the corresponding files:

 - In DVI format using the wais base: ra-zenon-inria-fr  on
      zenon.inria.fr port 210
 - In Postscript format using one of the following:

    * wais base : ra-mime-zenon-inria-fr on zenon.inria.fr port 210
     ( this source is an index of MIME documents containning
       pointers and requires metamail on the client size)
    * anonymous FTP on:
        zenon.inria.fr , directory /pub/rapports
        and soon on :
        ftp.inria.fr   , directory /INRIA/publication

------------------------------------------------------------------------------
RR1768  Veronique CLEMENT, Gerard GIRAUDON, Stephane HOUZELLE 
        et Fadi SANDAKLY :


          Interpretation of Remotely Sensed Image in a Context of
          Multisensor Fusion Using a Multi-Specialist Architecture.

          Interpretation d'images de teledetection dans un contexte
              de fusion multi-capteurs  avec utilisation d'une
	            architecture  multi-specialistes.


                             OCTOBER 1992

In english language


This  report presents a scene  interpretation  system in  a context of
multisensor  fusion; it has  been  applied   to the interpretation  of
remotely sensed images. First we present a typology of the multisensor
fusion concepts involved, and we  derive the consequences  of modeling
problems   for   objects,   scene      and  strategy.     The proposed
multi-specialist  architecture generalizes the  ideas  of our previous
work [GG90a] by taking  into account the  knowledge about sensors, the
multiple viewing notion (shot), and the uncertainty and impresision of
models  and data  modeled with the  Possibility Theory. In particular,
generic models  of objects are represented by  concepts independent of
sensors (geometry, materials,  and  spatial context).  Three  kinds of
specialists are  present  in  the  architecture:  generic  specialists
(scene and conflict),  semantic   object specialists,   and  low level
specialists.  A blackboard  structure  with a centralized   control is
used.  The  interpreted scene is implemented as  a  matrix of pointers
enabling conflicts to be  detected  very  easily. Under the control of
the scene specialist, the conflict specialist resolves conflicts using
the spatial context knowledge of  objects.  Finally, an interpretation
system with SAR/SPOT sensors is described, and an example of a session
concerned with bridge, urban area and road detection is shown.

Ce  rapport  presente un  systeme d'interpretation de  scenes  dans un
contexte  de     fusion   multi-capteurs   ; il  a   ete   applique  a
l'interpretation   d'images  de  teledetection.    Tout  d'abord, nous
presentons  une typologie  des  concepts mis en   jeu  pour  la fusion
multi-capteurs, puis les problemes de modelisation pour les objets, la
scene  etles strategies.   L'architecture  multi-specialistes proposee
generalise les  idees de nos  travaux precedents [GG90a] en prenant en
compte la connaissance  sur  les capteurs, la notion de  points de vue
multiples (shot), ainsi que l'incertitude et l'imprecision des modeles
et  des  donnees modelisees     par  la  theorie  des  possibilites.En
particulier, des modeles generiques d'objets sont representes  par des
concepts independants des capteurs (geometrie, materiaux,  et contexte
spatial).   Trois  types     de  specialistes  sont    presents   dans
l'architecture : les specialistes generiques  (scene et conflits), les
specialistes d'objets  sem antiques,  et les specialistes  bas niveau.
Une structure de tableau noir avec un controle centralise est utilise.
La scene interpretee est implementee par une matrice de  pointeurs, ce
qui permet de detecter les conflits tres facilement.  Sous le controle
du specialiste scene, le  specialiste conflits resoud  les conflits en
utilisant   la  connaissance sur    le contexte   spatial  des objets.
Finalement,    un systeme   d'interpretation  utilisant  des   donnees
provenant de capteurs SAR et SPOT est decrit  ;  un exemple de session
montrant la detection de ponts, zones urbaines et routes est commente.

------------------------------------------------------------------------------
RR 1752  Frank Dehne,  Andreas Fabri,  Mostafa Nassar,  Andrew
         Rau-Chaplin et Rada Valiveti :

                  
                    Construction of d-Dimensional Hyperoctrees on a
                             Hypercube Multiprocessor

                    La Construction d'un Hyperoctree de Dimension d
                             sur un Hypercube
                               

                            SEPTEMBER 1992
In english language



We  present  a   parallel algorithm  for   the  construction  of   the
hyperoctree representing a  d-dimensional object  from a  set of n  (d
-1)dimensional    hyperoctrees, representing  adjacent crossections of
this object.  On  a p-processor SIMD  hypercube the time complexity of
our algorithm is $O(\frac m p \log p\log n)$ , where m is  the maximum
of input and output size.


Nous  presentons ici un  algorithme parallele  pour la construction de
l'hyperoctree   representant un objet   de   dimension d  a partir  de
l'ensemble d'hyperoctrees de dimension d -1 representant des coupes de
cet objet. Sur un hypercube avec p  processeurs le temps de calcul est
$O(\frac  m p \log p\log  n)$ ,  ou m  est le maximum de  la taille de
l'entree et de la sortie.


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


RR1740   P. Aubert, M.C. Ciccoli et J.A. Desideri :

                       Une methode de partition de domaine

                   appliquee a une equation d'advection-diffusion


                                   JUNE 1992

In french language


 Les methodes de decomposition de domaine pour resoudre les equations
aux  derivees  partielles sont   particulierement adaptees  au  calcul
parallele. Elles sont basees sur le  decoupage du domaine de calcul en
sous-domaines plus petits,  sur lesquels on resout des  sous-problemes
independants de taille reduite.
  Ce   rapport    presente       l'etude    d'un   modele     lineaire
d'advection-diffusion en  une   puis  deux  dimensions  d'espace.   Il
comporte  une  etude theorique du   probleme  modele  et des resultats
numeriques.

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

RR1727   M. Teillaud :

                    Towards Dynamic Randomized Algorithms
                       in Computational Geometry

                    Vers des algorithmes dynamiques randomises
                       en geometrie algorithmique

                                PHD thesis

                               JULY 1992 

In english language

Computational geometry aims  to design  and  analyze algorithms  for
solving  geometric problems.  It is   a  recent  field of  theoretical
computer  science, that rapidly developed since   it  appeared in M.I.
Shamos' thesis in 1978.
  Randomization  allows    to  avoid  the   use  of   complicated data
structures, and has been proved to be very efficient, from both points
of view of theoretical compexity and practical results.
  We take particular  interest  in designing dynamic algorithms  :  in
practice, the  data of a problem  are often acquired progressively. It
is  obviously not reasonable to compute  the  whole result again  each
time  a  new  data  is inserted,  (semi-)dynamic    schemes  are  thus
necessary.
  We introduce a  very  general data  structure,  the Influence Graph,
that allows us  to construct various   geometric structures :  Voronoi
diagrams, arrangements of line segments: : :
  We study both theoretical complexity and practical efficiency of the
algorithms.


  La Geometrie algorithmique a pour but de concevoir et d'analyser des
algorithmes  pour  resoudre des  problemes  geometriques.    C'est  un
domaine recent de l'Informatique theorique, qui s'est  tres rapidement
developpe depuis son apparition dans la these de M.I. Shamos en 1978.
  La randomisation   permet  d'eviter  le  recours a   des  structures
compliquees, et s'avere  tres efficace, tant  du  point de  vue de  la
complexite theorique,  que des resultats pratiques.
  Nous nous sommes interesses plus  particulierement a  la  conception
d'algorithmes dynamiques  :    en  pratique,  il   est   frequent  que
l'acquisition des donnees  d'un  probleme soit progressive.  Il  n'est
evidemment pas question  de recalculer le  resultat a chaque  nouvelle
donnee, d'ou la necessite  d'utiliser  des schema  (semi-)dynamiques.
  Nous introduisons une structure de donnees tres generale,  le Graphe
d'Influence,  qui  permet  de  construire de   nombreuses   structures
geometriques :  diagrammes de  Voronoi, arrangements  de segments: : :
Nous etudions  les  algorithmes,  a  la  fois  du point de  vue de  la
complexite   theorique,  de  leur  mise  en oeuvre   pratique   et  de
l'efficacite des programmes.

----------------------------------------------------------------------
RR1721      Remi Abgrall, Jean-Antoine Desideri, Michel Mallet,   
             Jacques Periaux, Pierre Perrier et Bruno Stoufflet

                   Synthesis of the Workshop on
                   Hypersonic Flows for Reentry
                   Problems, parts I & II
                                             
                              JUNE 1992

In english language


Synthesis  of the Workshop  on HYPERSONIC FLOWS   FOR REENTRY PROBLEMS
held in Antibes, France, in January 1990 and April 1991

One of the most  challenging problems of  modern aerospace engineering
is   undoubtedly the prediction of   hypersonic   flows around reentry
vehicles.   Indeed this  challenge  has many   aspects : defining  the
appropriate  physical model for  these  flows is  the first difficulty
since very complex physical and chemical  phenomena  take place during
the reentry phase;  moreover,  temperature, velocity and  enthalpy are
very high,   density  very low, making  the  reentry   conditions very
difficult to reproduce in ground-based experiments.  Thus, in the past
two  decades, important efforts  in Computational  Fluid Dynamics have
been made employing  supercomputers  to simulate these complex  flows.
However, most simulation tools were originally designed for transonic
or supersonic flow  applications  and  later  extended; these  usually
contain imperfect models, and also still have to be improved to permit
the accurate  prediction  of  hypersonic  flows.   This situation  has
motivated  strong  international cooperative  efforts  including three
Europe  / US Short Courses on  Hypersonics   [1] [2]  and two sessions
(Parts I and II)  of the scientific  workshop  organized  by INRIA and
GAMNI [3] which   took  place  in  Antibes, France.

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

RR1597  Eitan Altman :

                  Flow control using the theory of
                         zero sum Markov games

                  Controle de flux utilisant la theorie
                  des jeux stochastiques a somme nulle

                          JANUARY 1992



In english language

We consider the problem of dynamic flow control of  arriving packets
into an infinite buffer. The service rate  may depend on the  state of
the system, may change in time  and is unknown to the  controller. The
goal of the    controller is  to   design an  efficient   policy which
guarantees  the   best  performance under   the  worst   case  service
conditions.    The cost is  composed of  a  holding cost,  a cost  for
rejecting customers (packets) and a  cost that  depends on the quality
of the service.  The problem is studied in  the  framework of zero-sum
Markov games, and a value iteration algorithm is used to solve  it. We
show that there  exists an optimal  stationary  policy (such that  the
decisions depend only on the actual number of customers in the queue);
it is of  a  threshold type, and it  uses randomization in at most one
state.

  Nous  considerons  le  probleme  du  controle  dynamique  de flux de
paquets arrivant a une file d'attente  de capacite infinie. Le taux de
service peut dependre de l'etat du systeme, peut varier dans  le temps
et n'est pas  connu  du  controleur. L'objectif  est  de concevoir une
strategie qui  garantit  la meilleure   performance   sous  les  pires
conditions de service. Le  probleme est etudie dans le  cadre d'un jeu
stochastique a somme nulle et la methode  dite  de value iteration est
utilisee pour le resoudre.  Nous  montrons l'existence d'une politique
optimale  stationnaire (ou  les  actions ne  dependent  que du  nombre
actuel de paquets  dans la  file  d'attente), qui est a  seuil, et qui
utilise un mecanisme aleatoire dans un etat au plus.
===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu