La proposition en bref

---

Rapport scientifique de l'année 2008

1) Analyse et détection de formes :

    Un de nos objectifs est d'étendre la prise en compte de l'information géométrique dans nos modèles. En effet, jusqu'à présent, nos ne traitons que d'objets paramétriques de faible dimension (disques, ellipses,  segments, rectangles). Dans ce cadre de la modélisation des formes, nous avons abordé trois points :

    1.a) Echantillonnage dans un espace de formes :

    Nous avons implanté un algorithme d'échantillonnage de formes, à partir des travaux du département statistique de l'université d'état de Floride (dans le cadre de l'équipe associée SHAPES). Ces travaux préliminaires vont permettre de définir un processus ponctuels marqué, pour lequel la marque d'un point correspond à un point dans l'espace des formes considéré. Nous pourrons alors appliquer l'algorithme de naissances et morts multiples que nous avons proposé pour optimiser le modèle ; l'échantillonnage des formes étant un prérequis pour la phase des naissances.
 
    1.b) Algorithmes de diffusion pour des espaces de formes :

    Lorsque nous utilisons des objets paramétriques de faible dimension, l'algorithme de naissances et morts multiples s'avère suffisant pour échantillonner et optimiser le modèle. En effet, notre expérience nous a montré que l'ajout d'un terme de diffusion dans la dynamique d'optimisation n'apporte pas de gain notable en terme de temps de calcul.  En considérant un nombre suffisant de naissances, la probabilité d'ajouter un "bon" objet est suffisamment élevée.   En revanche, dans le cadre de formes génériques, l'extrème variabilité de l'objet d'intérêt remet en cause cette conclusion. Nous avons donc entamé une reflexion sur la façon de définir une dynamique de diffusion sur l'espace des formes. La première piste envisagée consiste à utiliser la description de Fourier pour les formes, et de définir la diffusion sur les coefficients de Fourier. Le problème consiste alors à  lier l'énergie du modèle et son gradient, définis dans le plan image, avec la description par les coefficients de Fourier.

    1.c) Descripteurs de formes en vue de leur classification :
   
    Si l'on considère, non plus le problème de la détection d'un ensemble de formes à partir d'une image mais celui de la classification, un modèle générique de formes n'est plus nécessaire. Il est, dans ce cas, plus utile de rechercher des caractéristiques particulières qui soient discriminantes.  Dans cette optique, nous avons initié une approche de caractérisation des formes par leur entropie. Concrètement, cela revient à caractériser une forme en fonction de l'accroissement relatif de sa surface lorsqu'elle subit une dilatation élémentaire. Du point de vue théorique, la limite de ce rapport de surfaces, lorsque que le voisinage utilisé pour la dilatation tend vers zéro, est égale à l'entropie de la forme. Nous avons utilisé cette caractéristique pour aider à la discrimination des vaisseaux sanguins dans des coupes 2D obtenues sur des volumes tomographiques du système vasculaire cérébral. 

2) Processus ponctuels marqués 3D pour l'extraction du bâti :

    Un des grands enjeux applicatifs de l'équipe ODESSA est de définir un algorithme de reconstruction 3D du bâti s'affranchissant du problème de la mise en correspondance induite par la stéréovision. l'idée est de définir un modèle de scènes 3D composées de bâtiments. Un modèle a priori sur la structure de la scène sera défini. L'attache aux données, permettant de mettre en correspondance la scène avec les données, sera construit à partir de la projection de cette scène sur le(s) plan(s) image. L'enjeu principal de cette approche novatrice réside dans le temps de calcul nécessaire à l'obtention de la solution. Pour ce faire, nous définirons une dynamique d'optimisation fondée sur notre approche de naissances et morts multiples couplée avec différentes dynamique de diffusion. Dans ce cadre, nous avons réalisé un programme de génération d'images tests à partir de bâtiments simplifiés. Un moteur, développé sous OpenGl, permet également la visualisation 3D de la scène. Un premier terme du modèle, fondé sur l'ombre d'un bâtiment, a été défini à partir de la différence symétrique entre l'ombre présente dans les données et celle produite par la solution courante. Ce premier modèle très simple a été testé dans le cas d'une scène synthétique contenant un seul bâtiment.

3) Processus ponctuels spatio-temporels :

    Très en amont, nous avons défini de nouveaux modèles spatio-temporel de particules en interaction dans le domaine spatial. Cette première étude s'appuie sur des travaux mathématiques récents ("Self-organizing birth-and-death stochastic systems in continuum", Minlos R., Kondratiev Y., Zhizhina E., Reviews in Math. Pysics, 2008).
De premiers algorithmes ont été proposés. Il reste à les implanter pour étudier leur vitesse de convergence en pratique. Par ce biais, nous pouvons espérer simuler certains des processus ponctuels marqués que nous avons définis pour nos applications.  

4) Détection d'un réseau routier par processus ponctuel (non marqué) :

Nous avons considéré le problème de l'extraction automatique du réseau routier à partir d'une image satellite par processus ponctuel.
L'originalité de cette approche par rapports à nos travaux antérieurs est la définition d'un modèle fondé sur des configurations de points et non plus de segments. Le but recherché étant d'obtenir des temps de calcul plus en accord avec un cadre opérationnel. Nous avons donc classiquement défini une énergie contenant un a priori et un terme d'attache aux données. L' a priori permet de modéliser les partie occultées du réseau ainsi que les jonctions. Nous avons également proposé certains pré-traitements, notamment par l'estimation d'un flot de gradient, permettant de diriger le processus d'optimisation, et par conséquent de réduire le temps de calcul. De tout premiers résultats ont été obtenus. L'approche reste cependant à approfondir.

Rapport scientifique de l'année 2009

1) Processus ponctuels marqués pour l'extraction 3D du bâti :

Nous avons avancé sur l'extraction du bâti. De premiers résultats, avec un algorithme glouton, supposant le nombre de bâtiments connu ont été présentés à la conférence GRETSI  2009 (Dijon, France). Du point de vue programmation, un algorithme de naissances et morts multiples a été implanté par la suite. Il permet de gérer un nombre indéterminé de bâtiments.  Nous avons notamment montré la supériorité d'un critère d'attache aux données fondé sur l'ombre sur un critère  global défini par une distance entre l'image reconstruite et les données. Il va de soi que des informations supplémentaires seront nécessaires. De premiers pré-traitements, fondés sur des gradients locaux ont été définis et sont en cours de test. Un des enjeux de ce projet est de montrer la faisabilité d'une approche directe pour la reconstruction 3D du bâti. Cette approche est séduisante car elle s'affranchit des problèmes liés à l'approche inverse. En revanche, elle engendre un surcoût calculatoire qui peut s'avérer rédibitoire. Nous pensons que les nouvelles dynamiques d'optimisation et la performance des processeurs et des cartes graphiques actuels rendent l'approche réalisable. A chaque étape, un effort particulier est donc fait pour distribuer le calcul sur le processeur et la carte graphique, en minimisant les transferts de données sur le bus.

2) Détection de manchots royaux en vue du décompte de la population :

Nous avons développé un premier modèle contenant un a priori pénalisant les intersections entre objets et un terme modélisant la colorimétrie des manchots. Ce modèle considère des ellipsoïdes comme objets. Une dynamique de naissances et morts multiples effectue l'optimisation. Ce premier travail est en cours de validation sur des données synthétiques.
Nous avons par ailleurs reçu les premiers clichés de colonies de manchots pris par les scientifiques basés en Terre Adélie, suivant le protocole que nous avions établi. Ces clichés devraient permettre de calibrer les paramètres de la prise de vue. Pour les clichés ne respectant pas le protocole établi, nous avons étudié en parallèle une méthode d'estimation de ces paramètres. Pour ce faire, nous supposons que la répartition des manchots sur le sol suit une loi Poissonienne. La répartition des surfaces des cellules du diagramme de Voronoi  associé à la localisation des manchots dans le plan image dépend alors de la perspective et donc des paramètres de la prise de vue. Cette approche, et notamment la précision de l'estimation, sont en cours d'évaluation.

3) Diffusion sur un espace de formes :

L'algorithme de naissances et morts multiples a été adapté pour traiter de formes plus générales. Le modèle a priori contient un terme portant sur les coefficients de Fourier des formes, permettant ainsi de différencier les classes de formes, en favorisant, ou pénalisant, certaines fréquences. Pour éviter l'explosion combinatoire due à un espace de formes de dimension trop élevé, nous avons  intercalé, entre les étapes de naissance et de mort, une optimisation locale sur chacun des objets, en minimisant une énergie de type contour actif. L'algorithme résultant a été testé sur des images de synthèse ainsi que sur des images d'arbres à très haute résolution (quelques centimètres). Ce travail sera présenté à la conférence "SPIE, Computational Imaging" en janvier 2010. Ce travail donne lieu à une thèse (M. Kulikova) qui sera soutenue en décembre 2009.
Les aspects théoriques de l'algorithme de naissances et morts multiples ont été soumis dans une revue : D. Finkelshtein, Yu. Kondratiev, O.
Kutoviy, E. Zhizhina.  "An approximative approach to construction of the Glauber dynamics in continuum", soumis à SIAM Journal of Math. Anal.

4) Descripteurs de formes en vue de leur classification :

Différents descripteurs ont été définis. Ils consistent à appliquer une transformation affine à la forme étudiée qui étire la forme suivant une direction et la contracte suivant la direction perpendiculaire. Cette étude directionnelle de la forme permet une classification robuste. Les fondations théoriques de ce travail ont été présentées dans le "16th International Congress of Mathematical Physics, Prague, August 3-8, 2009"  (S.Komech, "Entropy and the boundary distortion rate for smooth dynamical systems" ) et l'atelier franco-russe "Stochastic Processes in Physics and Biology", 17-19 Août 2009, (B.Gurevich, S.Komech , "On one geometric meaning of dynamical entropy").
L'idée générale est d'accentuer les détails caractéristiques d'une classe de formes. La classification actuelle se fait par une distance euclidienne dans l'espace généré par les directions étudiées. La continuité de la fonction qui associe les descripteurs à une forme a été démontrée. L'approche a été validée sur une base de données publique contenant plus de mille formes (http://www.lems.brown.edu/vision/software/index.html). Les résultats obtenus se révèlent tout à fait pertinents, malgré la taille de la base de données.

5) Nous avons investigué l'apport en termes d'efficacité des approches de programmation modernes (MMX, SEE2). Cette étude a été réalisée pour la minimisation d'une fonction d'énergie issue d'un modèle markovien de mise en correspondance. L'application concerne le calcul d'un Modèle Numérique d'Elévation à partir d'un couple stéréoscopique d'images aériennes. Comparativement à la programmation traditionnelle, un gain en temps de calcul d'un facteur autour de 100 a été obtenu. Ce travail a été présenté à la conférence PRIP à Minsk en mai 2009.

PUBLICATIONS

Revues :

"The Gibbs fields approach and related dynamics in image processing"
X. Descombes, E. Zhizhina
Condensed Matter Physics, 11(2(54)): pages 293-312, 2008.

"Object Extraction Using a Stochastic Birth-and-Death Dynamics in Continuum"
X. Descombes, R. Minlos, E. Zhizhina
Journal of Mathematical Imaging and Vision (JMIV), 33: pages 347-359, 2009.

Conférences :

"Reconstruction 3D du bâti par la technique des ombres chinoises."
P. Lukashevish,  A. Kraushonak, X. Descombes, J.D. Durou, B. Zalessky,  E. Zhizhina.
In GRETSI Dijon, Dijon, France, November 2009.

"Fast Realization of Digital Elevation Model ."
X. Descombes, A. Kraushonak, P. Lukashevish, B. Zalessky.
 In PRIP , pages 156-160, Minsk, Belarus, May 2009.

"Gibbs point field models for extraction problems in image analysis,"
E. Zhizhina, X. Descombes.
Proceedings of Dobrushin International Conference, Moscow, Russia, July 15-20 2009, ISBN 978-5-901158-10-4.

"Extraction of arbitrarily shaped objects using stochastic multiple birth-and-death dynamics and active contours."
M. S. Kulikova, I. H. Jermyn, X. Descombes, E. Zhizhina, J. Zerubia.
In IS&T/SPIE Electronic Imaging, San Jose, USA, January 2010.