GDR MSPC  GT Vision et Perception GDR-PRC ISIS GT4 - Modèles Déformables Dynamiques

Yali Amit (Professor, Chicago University)
Frédéric Barbaresco (Thomson-csf)
Laurent Cohen (Université Paris Dauphine)
Donald Geman (University of Massachussets)
Nicolas Rougon (Institut National de Télécommunications)
Alain Trouvé (Université Paris 13)
Laurent Younes (CMLA, ENS de Cachan)

Frédéric Barbaresco
Laurent Cohen
Nicolas Rougon
Alain Trouvé
Laurent Younes

Abstracts

The talk will present some of the potential applications of digital image processing to medicine, and a list of associated challenging scientific problems. It will concentrate on the image registration problem, which has been extensively studied during the past 10 years. The presentation will describe geometric approaches (also named feature-based), applied both to rigid and deformable registration of monomodal images. Then, it will describe iconic approaches (also named voxel-based), where one will review several criterions useful for the rigid and deformable registration of multimodal images. If time permits, one will also describe other challenging problems, including the analysis of cardiac motion from times series of medical images, and the simulation of surgical interventions on virtual models created from medical images.Each part will be illustrated by various results obtained mainly nain our research group Epidaure at INRIA.

In his 1812 Essay on Probability, Laplace devotes a small chapter to what we call today the Bayesian decision rule. He remarks that when we see the letters "CONSTANTINOPLE," in that order, we "judge that this arrangement is not the result of chance ... because it is incomparably more probable that some person has thus arranged the aforesaid letters than that this arrangement is due to chance." This argument hinges on the fact that the number of legitimate combinations of letters, in a language, is "incomparably" smaller than the number of possible combinations. The sparseness of allowed combinations is in fact observed at all linguistic articulations, and such sparseness is also a feature of the rules that govern the hierarchical composition of simple shapes into more complex ones in natural images. Arguably, the sparseness of compositions is what allows us to perform high-level image interpretation in spite of pervasive low-level ambiguities. Compositionality thus appears to be a fundamental aspect of cognition. I shall describe a Bayesian framework, inspired from Rissanen's principle of Minimum Description Length, that Stuart Geman and I are developing in an attempt to account for compositionality in terms of elementary binding operations. The goal of this research is to make a contribution to machine vision but also to suggest the investigation of specific mechanisms that the brain may use to implement the necessary binding operations.
 
 

Ron Kimmel
Marching on Triangulated Domains
CS Dept. Technion, IIT     (Israel   Institute  of  Technology)
Haifa 32000, Israel   Email:ron@cs.technion.ac.il
Tel: +972-4-829-4616
Fax: +972-4-822-1128    (or +972-4-829-4353)
http://www.cs.technion.ac.il/~ron

The speaker will review a computationally optimal numerical answer to the question of how to compute the shortest path between two points on a surface, also known as the `minimal geodesic problem'. We (Kimmel-Sethian) have extended a numerical technique for solving Eikonal equations on flat domains to triangulated curved domains. It provides a scheme for computing geodesic distances and thereby solving the minimal geodesic problem. Next, we show who to use the method to compute Voronoi diagrams and offset curves on surfaces.  We also present applications of the technique to areas like 3D shape reconstruction in computer vision, path planning in robotic navigation, and texture mapping in computer graphics.

Constructing sparse representations, where signals are characterized by few parameters, is at the root of most image processing problems. Applications to compression, estimation and inverse problems will illustrate this general statement, showing that nearly optimal algorithms are then implemented with diagonal operators. This explains the profound impact of new harmonic analysis tools such as wavelets. Optimizing representations relies on image models. The minimax approach will be presented and contrasted with Bayesian modeling. To improve the current state of image processing, one must take into account the geometrical regularity of structures in images (edges). Bandelets define new orthogonal bases which are adapted to the geometry of edges, and build a bridge with snake optimization methods. This opens the door to the dream of "2nd generation image coding," where the representation is not only adapted to efficient compression but also to search and pattern recognition in large data-bases of images.

 Nonlinear diffusion filtering allows flexible processing of degraded and noisy images. It is based on the idea to filter an image by regarding it as the initial state of a diffusion process which adapts itself to the local image structure. After explaining the basic concepts behind diffusion filtering, we focus on its relations to regularization methods for image restoration, and variational techniques for recovering the optic flow in an image sequence. For a class of linear and nonlinear regularization methods we derive a well-posedness and scale-space theory that is in analogy with results for diffusion filtering. In the second part of the presentation we discuss relations between diffusion filtering of multichannel images and variational methods for optic flow estimation. This framework also leads to novel optic flow regularizers.

Three types of data are now available to test for changes in brain shape: 3D binary data for the indicator function or mask of the structure; 2D displacement data from the surface of the 3D structure; and trivariate 3D vector displacement data from the non-linear deformations required to align the structure with an atlas standard. We use the Euler characteristic of the excursion set of a random field as a tool to test for localised structural changes using local maxima and size of clusters in the excursion set. The data is highly non-isotropic, that is, the effective smoothness is not constant across the image, so the usual random field theory does not apply. We propose a solution that warps the data to isotropy using local multidimensional scaling. We then show that the subsequent corrections to the random field theory can be done without actually doing the warping - it is only sufficient to know that such a warp exists - a fact that is guaranteed in part by Nash's Embedding Theorem. We shall apply thee methods to a set of 151 brain images from the Human Brain Mapping data base.
 

Object detection is a fundamental problem in computer vision. The problem will be formulated as one of detecting a global event (conjunction) in a point process - generated by applying a number of local and binary feature detectors on the image. The appropriate feature detectors are determined through a simple training procedure, using sample images of the object. The statistical properties of these features on object and on background will be discussed in detail.

We study some qualitative aspects of crystalline motion by mean curvature in three dimensions. This is an evolution law obtained as the gradient flow of a functional defined on boundaries, having an integrand which weights the normal vector to the interface, and is a norm having a polytope as unit ball. This evolution law provides a natural way to flow polyhedral interfaces by relative (crystalline) mean curvature, and more generally suitable Lipschitz surfaces. Remarkably, starting from an initial polyhedral surface which is close the the reference crystal (usually called Wulff shape) it may happen that a facet instantly subdivides into two or more regions. It may also happen that a facet bends, so that the initial surface does not remain polyhedral. We will analyze in some details the above phenomena, and we will give necessary and sufficient conditions on a facet of the initial surface for not subdivide or bend.

references :
[1] G. Bellettini & M. Paolini, "Anisotropic Motion by Mean Curvature In the
Context of Finsler Geometry", MURST program report, Hokkaido Math J., vol.25,
pp.537-566, 1996
[2] M.Amar & G. Bellettini, "A Notion of Total Variation depending on a Metric with
Discontinuous Coefficients", Ann. Inst. H. Poincaré, Anal. Non Linéaire, vol.11,
pp.91-133, 1993
[3] G. Bellettini, M. Paolini & S. Venturini, "Some Results on Surface Measures in
Calculus of Variations", Ann. Mat. Pura. Appl., vol. 170, pp.329-359, 1996
[4] G. Bellettini & M. Novaga, & M. Paolini, "Facet-breaking for three-dimensional
crystals evolving by Mean Curvature", Preprint, univ. Di Pisa n° 2.322.1143,
October 1998

will be based on a joint paper with Ronny Kimmel and Nir Sochen.

ABSTRACT: This paper will survey a series of methods for discontinuity-preserving smoothing processes for signals, grey-scale images, color images or vector fields. All the methods will be shown to be based on a data-induced metric for defining the neighborhoods over which averaging should be done, and also the weights of the various contributions for computing the output at each location.

In this paper we present a mixture density based approach to invariant image object recognition. We start our experiments using Gaussian mixture densities within a Bayesian classifier. To allow for reliable parameter estimation, the dimensionality of the extracted feature vectors is reduced by applying a robust variant of a linear discriminant analysis. In another experiment, invariance to affine transformations is achieved by replacing Euclidean distance with Simard's tangent distance. We propose an approach to estimating covariance matrices with respect to image invariances as well as a new classifier combination scheme, called the virtual test sample method.  On the US Postal Service handwritten digits recognition task, we obtain an excellent classification error rate of 2.2%, using the original USPS training and test sets.

work with Laurent Cohen, CEREMADE

This work presents a new method to find minimal paths in 3D images, giving as initial data one or two endpoints. This is based on previous work by Cohen-Kimmel for extracting paths in 2D images using Fast Marching (Sethian99). Our original contribution is to extend this technique to 3D, and give new improvements of the approach that are relevant in 2D as well as in 3D.  We also introduce several methods to reduce the computation cost and the user interaction.

This work finds its motivation in the particular case of 3D medical images.  We show that this technique can be efficiently applied to the problem of finding a centered path in tubular anatomical structures with minimum interactivity, and we apply it to path construction for virtual endoscopy.  Synthetic and real medical images are used to illustrate each contribution.

References
T. Deschamps and L.D. Cohen, Minimal paths in {3D} images and application
to virtual endoscopy, Proc. sixth  European Conference on Computer Vision (ECCV'00), Dublin, Ireland, June 2000.

Demo: Some videos

Common work with Patrick Bouthemy

 We present an original approach for motion-based retrieval involving partial query. More precisely, we propose a unified statistical  framework both to extract entities of interest in video shots and to obtain their content-based characterization to be exploited for satisfying retrieval requests.

  The proposed method relies on a  non-parametric probabilistic modeling of motion information expressed as temporal Gibbs distributions. Observations are given by sequences of local motion-related measurements, which are directly computed from the spatio-temporal derivatives of the intensity function. The main interest of this framework lies in the possibility to perform an exact computation of the conditional likelihood of a sequence of motion quantities w.r.t. a given model by means of a simple dot product between model potentials and temporal cooccurrence measurements. This property allows us to design a simple maximum likelihood estimation scheme and to define an appropriate motion-based similarity measure based on the Kullback-Leibler divergence.

We exploit this motion modeling framework both to extract and to characterize entities of interest in video shots. The extraction relies on a region-level ascendant hierarchical classification applied to the adjacency graph of an initial block-based partition of the image. Entities of interest are given by the extracted regions that do not conform to the model associated to the dominant motions. As a consequence, given a video base, we are able to construct a base of samples of entities of interest associated to statistical motion model. The retrieval operations is then formulated as a Bayesian inference issue using the MAP criterion. Given a video query and an area selected by the user as the partial query, we aim at retrieving videos from the base which best fit to query content in terms of scene activity.

We report several results of extraction of entities of interest in video sequences and examples of retrieval operations performed on a base including one hundred of various video samples.

Common work with Don Geman

Our goal is to detect all instances of frontal faces in greyscale scenes. Performance is measured by the number of false alarms and the amount of computation necessary for no missed detections. Starting from training examples, we build a hierarchy of detectors, corresponding to a recursive partitionning of the face pose space. Each of those detectors is based on arrangements of edge fragments (``coarse-to-fine templates''). The arrangements are "decomposable'': each can be split into two correlated subarrangements, each of which can be further divided, etc. The final search is coarse-to-fine in both the exploration of poses and the representation of faces.
 

 references
F. Fleuret, Détection hiérarchique de visages par apprentissage
statistique (Thèse de doctorat de l'Université Paris VI, 2000)

F. Fleuret et D. Geman, Coarse-to-fine visual selection (International
Journal of Computer Vision, accepté, à paraître)

F. Fleuret et D. Geman, Graded learning for object detection (Actes du
Workshop CVPR IEEE on Statistical and Computational Theories of Vision,
1999)

Yann Gousseau
Morphological statistics of natural images
CMLA, ENS-Cachan,
61 av du President Wilson
94235 Cachan Cedex
tel : 01 47 40 59 49 fax : 01 47 40 59 01
gousseau@cmla.ens-cachan.fr
www.cmla.ens-cachan.fr/~gousseau

The statistical study of natural images has recently been a subject of increasing interest, and has mainly focussed on low order statistics or on additive decompositions. Having in mind a better understanding of the geometrical structure of images, we have a different approach and investigate statistics on their level sets or some of their combinations. We will present results mainly focusing on the size distributions of such quantities, enabling the investigation of both the mathematical irregularity and the scale invariance of natural images. We will also relate these results to a generative model of images taking occlusion into account, in which a power law distribution of objects' sizes is shown to yield the statistics we observe.

We explore the microworld of natural scenes as represented by large samples of two- and four-pixel patches extracted from a diverse collection of coarsely quantized images. Based on prior results of statistical stability of the underlying empirical distributions, we proceed by quantifying various types of geometric and photometric symmetries of the microimage space. The most intuitive among those are the left-right and up-down reflections.  Several statistical tests are employed to guide us in building a hierarchy of models based on respective types of symmetry.  A possible application of the results is in the context of tree-based microimage classification as used to define elementary features for various imaging tasks.

 This talk is about the problems of restoration and segmentation of noisy image sequences with a static background. Usually, motion segmentation and image restoration are  considered separately. Moreover, motion segmentation is often noise sensitive.  The key idea is that the motion segmentation and the image restoration parts should be performed in  coupled way, allowing the motion segmentation part to positively influence the restoration part and vice-versa. A theoretically justified optimization problem that permits to take into  ccount both requirements is proposed.   Experimental results obtained on noisy synthetic data and real images will illustrate the capabilities of this approach.

Reference :
Image Sequence Analysis via Partial Differential Equations
  Kornprobst (P.), Deriche (R.), Aubert (G.)
  Journal of Mathematical Imaging and Vision,
  Vol 11, no 1, pp. 5-26, Septembre 1999
 available at :
ftp://ftp-robotvis.inria.fr/pub/html/Papers/kornprobst-deriche-etal:99.ps.gz

We address the problems of perceptual grouping and contour completion using a minimal path approach. We present a new method in order to find complete curves from a set of contours or edge points. This is based on previous work on finding minimal paths between two end points using fast marching (Cohen_Kimmel-97). However, in our approach, we do not need to give end points as initialization. A set of representative points is automatically generated from a larger set of admissible points. At the same time this set of points is obtained, saddle points between pairs of points are selected. Once this set is obtained, paths are drawn on the image from the saddle points to both points of each pair. This gives the minimal paths between selected pairs of points. The complete set of minimal paths completes the initial set of contours and allows to close these contours.  We illustrate the capacity of our approach to close contours with examples on various images of sets of edge points representing simple shapes with missing contours.

Center for Imaging Science
Whiting School of Engineering
The Johns Hopkins University
221 Barton Hall/3400 N. Charles Street
Baltimore, MD 21218-2686
http://cis.jhu.edu/wu_personnel/mim.html
mim@cis.jhu.edu

We examine image understanding from the classical source-channel point of view of statistical communications. The space of images corresponding to the source $I \in {\mathcal I}$ is a Grenander deformable template, an orbit under the group action of diffeomorphisms of a prototype. The prior distribution on the source $p(I), I \in {\mathcal I}$ is induced through a distribution on the group $g \in {\mathcal G}$. The channel corresponding to the remote sensor generates the observable images $I^{\cal D}\in {\cal I}^{\cal D}$ reflecting projection and noise and modeled via the conditional density $\pi(I^D |I)$. Minimum-risk estimation, rate-distortion, and compression are examined by introducing
a distance $d(I,I^\prime)$ on the orbit through a distance on the group $d(g,g^\prime)$. Three examples are examined, both for finite and infinite dimensional
groups associated with geometric and signature variation in image understanding and anatomical shape representation.
This work was supported by Grant ARO DAAH-04-95-1-0494, ONR-MURI N00014-98-1-0606.

(joint work with A.Desolneux and J.-M.Morel)
We present a recently introduced method for computing geometric structures in a digital image, without any a priori information. According to a basic principle of perception due to Helmholtz, an observed geometric structure is perceptually ``meaningful'' if its number of occurences would be very small in a random situation : in this context, structures are characterized as large deviations from randomness. We explain how non-intersecting maximal structures can be defined to meet the perception law stating that parts of a whole are not perceived, and illustrate these principles with experiments on images and histograms.

Together with texture and colour,  contour-shape plays a prominent role in characterizing  the visual content of images. Since the construction of precise and robust shape-descriptors is extremely difficult,  it is convenient that, for the purpose of content-based image retrieval (CBIR),  it often suffices to measure the relative similarity between two contours.

There is no shortage of methods that try to handle shape-description and/or -comparison. We propose to use a combination of curve-evolution and transformation mapping. More precisely, the distance between two contours is  defined as the minimal cost to transform a simplified version of one contour into a simplified version of the other. The cost-function takes into account the contributions from both the simplification and the transformation.

We will discuss different algorithms that can be used to implement contour-simplification and -transformation and their associated costs. We conclude by giving some examples of shape-matching in CBIR.

Traditionally, symmetry set representation has been defined for segmented shape. However, the difficulties in obtaining shape from gray-level images have led us to consider the symmetry maps of gray-level images as well as shape. In this talk, we propose that the symmetry map of an edge map is an appropriate intermediate level representation between low-level edge maps  and high-level object models and transformations of it are canonical building blocks for perceptual grouping and object recognition. First, we review an approach for computing the symmetries (skeletons) of an edge map (and shape) consisting of a collection of curve segments. This approach is a combination of analytic computations in the style of computational geometry and discrete propagations on a grid in the style of the numerical solutions of PDE's as in curve evolution. This framework results in (i) analytically exact solutions, (ii) near optimal computational complexity, (iii) local computations, and (iv) a graph representation which can be used in applications, e.g., for object recognition. Second, we present symmetry transformations on the symmetry map  as a language for perceptual organization. Specifically, it is proposed that (i) a symmetry map can fully represent the initial edge map so that both boundary and regional continuities can be represented via skeletal/shock continuity; (ii) a re-organization of the edge map in the form of completing gaps, discarding spurious elements, smoothing, and partitioning a contour (grouped set of edge elements) can be represented by transformations on the symmetry map; (iii) the optimal grouping corresponds to the least action path consisting of a sequence of symmetry transforms.
 

Antonio Turiel
Analysis of natural images with multifractal measures: fractal
decomposition, reconstruction and coding.
Laboratoire de Physique Statistique Ecole Normale Superieure
24 rue Lhomond, 75231 Paris Cedex 05  France
Telephone: (+33) (0)1 44 32 34 75
e-mail: Antonio.Turiel@lps.ens.fr

Real world images form a class of objects with self-similar character: they are not characterized by any intrinsic scale, its statistics remaining the same under changes in scale. Among the models used to describe such a property, we will make use of the multifractal representation. This scheme is strongly linked both to statistics (multiscaling) and to functional description of images in terms of multifractal measures. In this talk, we will show how images are decomposed in fractal components of different information content. We will show and justify an ansatz for reconstructing images out of the most relevant component. We will analyse further the structure of this component and discuss it from the perspective of coding.

Common work with Fernand Meyer
CMM Ecole des Mines de Paris 77000 Fontainebleau, meyer@cmm.ensmp.fr
 

This paper presents a morphological scale-space approach to the problem of image segmentation. The method relies on two steps : a feature extraction step based on pyramids of flattening filters and a multilevel segmentation step based on the watershed transform. Flattening operators are ideally suited for this purpose. Indeed, in the feature extraction step, the feature should be ranked in a monotonic way; the flattening filters only suppress regional extrema ; they never introduce new extremum. Furthermore, they do not corrupt the contours, allowing an accurate segmentation of the image content, even at the coarse scales. As the criteria on which they are build vary, a variety of different pyramids may be constructed: contrast, size or combination of both. Applying the watershed transform on a neighbouring graph speeds up the overall construction of the segmentation pyramid, and also allows interaction. Several image segmentation applications are presented which illustrate the robustness of our method and that it can deal with very different type of images.
 

References:
C. Vachier and F. Meyer Extinction value : a new measurement of persistence. IEEE workshop on Nonlinear Signal and Image Processing, 1995.
C. Vachier and L. Vincent Valuation of image extrema using alterning filters by reconstruction. Image Algebra and Morphological Processing, 1995.
F. Meyer, A. Oliveras, P. Salembier and C. Vachier Morphological tools for segmentation: connected filters and watershed. Annales des télécommunications, 1997.
C. Vachier, F. Meyer A Morphological Scale-space Approach to Image Segmentation
based on Connected operators. Soumission à Pattern Analysis and Machine Intelligence.