GDR MSPC  GT Vision et Perception

Frédéric Barbaresco (Thales)
Freddy Bruckstein (Technion Intitute)
Laurent Cohen (Université Paris Dauphine)
Rachid Deriche (INRIA Sophia-Antipolis)
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
Rachid Deriche
Nicolas Rougon
Alain Trouvé
Laurent Younes

Abstracts

This talk with give an overview of the techniques, demonstrating their application to
interpretting images of faces and medical images.

The annotation of the training set is the most timeconsuming and error prone part of the
model building process.  We will describe methods
of automating this, solving the problem of finding correspondences across sets of shapes
in an optimisation framework.

Relevant Literature
T. F. Cootes and G. J. Edwards and C. J. Taylor.
Active Appearance Models,
IEEE PAMI 23,  pp. 681-685, June 2001.

R.H. Davies and C.Twining and T.F. Cootes and C.J. Taylor.
An Information Theoretic Approach to Statistical Shape Modelling,
ECCV02, May 2002.
 

Computing distance functions and geodesics in high-dimensional surfaces has applications in numerous areas in mathematical physics, image processing, medical imaging, computer vision, robotics, computer graphics, computational geometry, optimal control, knowledge discovery, and brain research. Geodesics are used for example for path planning in robotics, brain flattening and brain warping in computational neuroscience, crests, valleys, and silhouettes computations in computer graphics and brain research, mesh generation, segmentation in medical imaging, and many applications in mathematical physics. Last but not least, distances and geodesics in high dimensions are fundamental for problems in data mining, dimensionality reduction, and recognition. In addition, generalized geodesics, following the theory of harmonic maps, also found applications in numerous fields, including but not limited to brain warping, color image processing, 3D object recognition, information visualiza!
tion, inverse problems like those arising from EEG/MEG, and computer graphics.

In this talk we will discuss computational techniques for finding geodesics and generalized geodesics in any dimension. We will address the problem mainly for implicit hyper-surfaces and hyper-surfaces defined from unorganized points. We will discuss computationally optimal and efficient techniques to compute these geodesics, presenting both the underlying theory and numerous examples. We will also briefly comment how to our surprise, some of the mathematical ideas used to derive these techniques are connected with mathematical techniques to study problems in super-conductivity and nanoscales. We conclude the talk describing our current efforts in applying these computational framework.
 

Visual classification is a major open problem in cognitive neuroscience
as well as computer vision. The difficulty in performing classification
comes primarily from the large variability of images within a natural
class of objects. To cope with this variability, the recognition system
must learn to separate essential class properties from irrelevant
variations. The talk will describe an approach to classification based
on representing shapes within a class by a combination of shared
sub-structures called fragments. The fragments are extracted from
example images and used as building blocks to represent object views
within a given class of shapes. They are selected automatically from
training images by an algorithm that maximizes the information delivered
by the fragments with respect to the class they represent.
The class-fragments are used for detecting and classifying objects, but
at the same time they are also used for segmenting the objects from the
image. I will describe the combination of segmentation and
classification processes within the current approach, and compare it
with more traditional bottom-up approaches to segmentation.

-----------------------------------
Many problems in vision can be viewed as probabilistic inference
problems: the goal is to infer scene properties using image
data. Unfortunately, due to the large number of variables involved exact
inference is hopeless.

I will discuss the method of "belief propagation" for approximate
inference in such problems. This method is behind the Shannon-limit
performance of "turbo codes" and recent theoretical analysis sheds light
on its performance.

-----------------------------------
We try to give a short overview of the shape analysis technics developed
for large
evolution of domains in control of systems governed by PDE. The main
tool is the flow mapping associated with
a vector field on a manifold and the associated concepts of Shape
derivative (first and second order)
of "state equation solutions" on the moving geometry.
Several topolgies and compacity properties have been developed togeher
with several shape parametrization (including level
sets after 1980 [1], specifically for free boundary in TOKOMAK
machine).  Also intrinsic geometry and geometric measure
are deeply used, see the books [2]-[5].and also [6] for the usefull
concept of fractal perimeter.  Recent developments[7] concern weak flow
associated to non smooth field in order to handle dynamic moving shapes,
topological changes,
transverse fiels governed by Lie brackets , tube optimization.
 

References
[1] " The Speed Method in Shape Analysis" in Ptimization of Distributed
Parameter Structures. Natao Adv. Study. Serie E, Applied Sci., 50,
Sijthohh & Norddhoff, Rockville, USA, 1981, pp.1089-1250
[2]  Introductiojn to shape Optimization, Springer Verlag scm, 16 , 1991
[3] boundary control and boundary variation, Lecture notes in pure and
applied math. 163, Marcel Dekker, N.Y., 1994
[4] b.Kawohl, O.Pironneau, L. Tartar, J.-P. Zolesio. Optimal Shape
Design L.N.M., Springer verlag, 1740, 2000
[5],M. Delfour, J.-P. Zolesio Shape and Geometry. SIAM Advances in
Design and Control, 004, 2001.
[6]D. Bucur, J.P. Zolesio . Boundary Optimization under Pseudo Curvature
Constraint. Ann.Sc.Norm.Sup.Pisa,IV.vol.XXIII,96.
[7]J. Cagnol, M. Polis, J.-P. Zolesio. shape optimization and optimal
design,l.n.p. a. m., Marel Dekker, 216, 2001.

Pablo Arbelaez, joint work with Laurent Cohen
Minimal paths and Image Segmentation
CEREMADE, Universite  Paris IX Dauphine
Place du Marechal de Lattre de Tassigny
75775 Paris cedex 16, France

-----------------------------------
We present a two stage approach to address the problem of image
segmentation. The first part consists in a parameter free filtering
based in the formalism of minimal paths. In the second part, the
filtered image is partitioned into "segments" through a region merging
strategy. Our method is related to some morphological techniques largely
used for segmentation, in particular, the watershed transform and the
flooding hierarchies. Therefore, we will also discuss the similarities
and innovations with respect to these approaches.

-----------------------------------
We show the convergence of an algorithm for total variation minimization
based on a dual formulation. we discuss applications to image denoising,
zooming, and the computation of mean curvature motion.

A new type of diffusion process is presented that simultaneously
sharpens and denoises images.
The nonlinear diffusion coefficient switches between positive and
negative values according to a given set of criteria. This results in a
forward-and-backward (FAB) adaptive diffusion process that enhances
features while locally denoising smoother segments of the image.
The FAB method is further generalized for color processing in the
Beltrami framework, by adaptively modifying the structure tensor
that controls the process between positive and negative values.
The process is compared to previously suggested methods and
some issues of stability are addressed.

Bibliography:
G. Gilboa, N. Sochen, Y.Y. Zeevi,
"Forward-and-backward diffusion processes for adaptive image
enhancement and denoising", to appear on IEEE Trans. on Image
Processing, July 2002.

Once a quantitative description of organ shape is extracted from input
images, the problem of identifying differences between the two groups
can be reduced to one of the classical questions in machine learning,
namely constructing a classifier function for assigning new examples
to one of the two groups while making as few mistakes as possible. In
the traditional classification setting, the resulting classifier is
rarely analyzed in terms of the properties of the input data that are
captured by the discriminative model. In contrast, interpretation of
the statistical model in the original image domain is an important
component of morphological analysis. We propose a novel approach to
such interpretation that allows medical researchers to argue about the
identified shape differences in anatomically meaningful terms of organ
development and deformation. For each example in the input space, we
derive a discriminative direction that corresponds to the differences
between the classes implicitly represented by the classifier
function. For morphological studies, the discriminative direction can
be conveniently represented by a deformation of the original shape,
yielding an intuitive description of shape differences for
visualization and further analysis.

Based on this approach, we present a system for statistical shape
analysis using distance transforms for shape representation and the
Support Vector Machines learning algorithm for the optimal classifier
estimation. We demonstrate it on artificially generated data sets, as
well as real medical studies.

A common approach to image segmentation is to construct a cost function
whose minima yield the  segmented image. This is generally achieved by
competition of two terms in the cost function, one  that punishes
deviations from the original image and another that acts as a smoothing
term. We propose a variational framework for characterizing global
minimizers of a particular rough energy functional used in image
segmentation. Our motivation comes from the observation that energy
functionals are traditionally complex, for which it is usually difficult
to precise global minimizers corresponding to ``best'' segmentations.
In this paper, we prove that the set of curves that minimizes the basic
energy model is a subset of level lines or isophotes, i.e. the
boundaries of image level sets. The connections of our approach with
region-growing techniques, snakes and geodesic active contours are also
discussed. Moreover, it is absolutely necessary to regularize isophotes
delimiting object boundaries and object surfaces for vizualization and
pattern recognition purposes. It leads to a sound initialization-free
algorithm combining reaction-diffusion with isophotes selection to
extract smooth object boundaries. We illustrate the performance of our
algorithm with several examples on both 2D biomedical and aerial images,
and synthetic images.
 

Keywords:
--------
grouping and segmentation, energy minimization, level sets, level lines,
isophotes, connected components, anisotropic diffusion.
 

Bibliography:
----------
Optimal level curves and global minimizers of cost fucntionals in image
segmentation. C. Kervrann, A. Trubuil. 2002 (in revision).

Isophotes selection and reaction-diffusion model for object boundaries
estimation. C. Kervrann, M. Hoebeke, A. Trubuil. 2002. (in revision).

Bayesian object detection through level curves selection. C. Kervrann.
International Conference, Scale-Space and Morphology in Computer Vision
(Scale-Space'01), LNCS 2106, pp. 85-97, Vancouver, Canada, 2001.

Level lines as global minimizers of energy functionals in image
segmentation. C. Kervrann, M. Hoebeke, A. Trubuil. European Conference
on Computer Vision (ECCV'00), LNCS 1843, pp. 241-256, Dublin, Irland,
2000.

A level line selection approach for object boundary estimation. C.
Kervrann, M. Hoebeke, A. Trubuil. IEEE Int. Conf on Computer Vision
(ICCV'99), pp. 963-968, Corfu, Greece, 1999.

 The problem of filling missing gaps in image and video material (called Picture Building here) is a well known one  in digital post-production and archive restoration. In the video case, the gap may consist of the entire frame. Various schemes have been developed over the years to deal with these problems using deterministic algorithms. It would appear that this is one application domain in which work in Signal Processing overlaps with similar work in Computer Vision.

In the 2D case, various methods for continuing contours through the gap have been proposed. For the 3D case, many ad-hoc schemes have been discussed involving detection/correction using cut and paste. This talk discusses an alternate idea using Autoregressive models with motion constraints articulated under a Bayesian framework, and using a practical implementation of the Gibbs Sampler. These ideas in fact generalise all of the previous work in video reconstruction, and in the 2D case, there are interesting links with the use of PDEs.

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

While major efforts have been achieved in the design of copyright protection watermarking schemes which have not got the expected successes. A new
application domain which is emerging relates to the use of watermarking schemes as an embedded channel for added-value services accompanying the
delivery of video. One exciting area is the transmission of informations to enhance the services and to ensure its compatibility with legacy channels.

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

The use of bases for image restoration has been widely studied (see
the works on wavelet and Fourier bases). However, a single basis is
adapted to
a particular kind of feature and is therefore not sufficient to restore
an image
containing several different kind of structures (say edges and
textures).
We describe a method which use a dictionnary instead of a single basis
and show on experiments that it allows the restoration of images
containing
both edges and textures.
 

This talk begins with some theoretical connections between levelings on lattices and scale-space erosions on reference semilattices. They both represent large classes of self-dual morphological operators that exhibit both local computation and global constraints. Such operators are useful in numerous image analysis and vision tasks including edge-preserving multiscale smoothing, image simplification, feature and object detection, segmentation, shape and motion analysis. Previous definitions and constructions of levelings were either discrete or continuous using a PDE. We bridge this gap by introducing generalized levelings based on triphase operators that switch among three phases, one of which is a global constraint. The triphase operators include as special cases useful classes of semilattice erosions. Algebraically, levelings are created as limits of iterated or multiscale triphase operators. The subclass of multiscale geodesic triphase operators obeys a semigroup, which we exploit to find PDEs that can generate geodesic levelings and continuous-scale semilattice erosions. We discuss theoretical aspects of these PDEs, discrete algorithms for their numerical solution which converge as iterations of triphase operators, and provide insights for image analysis. The first part of the talk presents results from [2].
In the second part of the talk we present a multiscale connectivity framework for shape analysis based on new generalized connectivity measures, obtained using morphological scale-space operators. Levelings and global reconstruction operators are related to this connectivity framework. The concept of connectivity-tree for hierarchical image representation is introduced and used to define generalized connected morphological operators. This multiscale connectivity analysis aims at a more reliable evaluation of shape/size information within complex images, with particular applications to generalized granulometries, connected operators, and segmentation. The second part of the talk presents results from [5].
References:
[1] H.J.A.M. Heijmans and R. Keshet (Kresch), Inf-Semilattice Approach to Self-Dual Morphology, Report PNA-R0101, CWI, Amsterdam, Jan. 2001.
[2] P. Maragos, Algebraic and PDE Approaches to Lattice Scale-Spaces with Global Constraints, to appear in Int. J. Computer Vision (Special Issue on Scale-Space and Morphology), 2002.
[3] F. Meyer and P. Maragos, Nonlinear Scale-Space Representation with Morphological Levelings, J. Visual Commun. & Image Representation, 11, p.245-265, 2000.
[4] J. Serra, Connections for sets and functions, Fundamenta Informaticae, 41, p.147-186, 2000.
[5] C. Tzafestas and P.Maragos, Shape Connectivity: Multiscale Analysis and Application to Generalized Granulometries, to appear in J. Mathematical Imaging and Vision (Special Issue on Shapes and Textures), 2002.

-----------------------------------
Segmenting an image amounts to creating a partition where each tile represents a smooth zone
and its contours follow strong transition lines in the image.  The present paper aims at
enlarging the meaning of the sentence "there exists a strong (resp. smooth) transition between
two neighbouring pixels".  This will be achieved by associating to each adjunction of an
extensive dilation and of an antiextensive erosion a particular meaning to "strong transition"
and to "neighbouring pixels". We then define two types of "smooth zones" : a) in weak
smooth zones each couple of pixels is linked by a path with smooth transitions between
neighbouring pixels; b) in strong smooth zones a smooth transition exists between any couple
of neighbouring pixels.
As a next step, one defines two order relations between images expressing that image g has
less strong transitions than image f : in the weaker order relation, g is called flattening of f and
leveling of f in the stronger order relation. We then study the families of flattenings and
levelings of a function f.
We call Inter(f,h) the set of all functions g verifying :    Inf(f,h) <= g <= Sup(f,h).
Inter(f,h) is a complete lattice for the order relation defined by: "g1 smaller than g2" if and
only if g2 belongs to Inter(f,g1). Studying the extremal flattenings and levelings in Inter(f,h)
will lead to useful applications to filtering and segmentation which will be illustrated.

We consider the recovery of images x from noisy data y by
minimizing a regularized cost-function F(x,y)=G(x,y)+H(x), where
G(x,y)=sum_i g(a_i x-y_i) is a data-fidelity term with a_i linear
operators and g a function, and H is a smooth regularization term.
Usually, G is a smooth function. We focus on the effect of the
non-smoothness of G on the features of the solution x*.
We show that if g is non-smooth at
zero, typical data y lead to local minimizers x* of F(.,y) which
fit exactly part of the data entries: there is a possibly large
set composed of indexes i for which a_i x*=y_i. This effect does
not occur if g is smooth. We have a strong property which can be
used in various ways. Based on it, we built a cost-function allowing
aberrant data to be detected and selectively smoothed.
We provide an efficient numerical scheme to calculate the sought-after
minimizer.

full paper:
Mila Nikolova,
"Minimizers of cost-functions involving non-smooth data-fidelity
terms. Application to the processing of outliers"
SIAM Journ. on Numerical Analysis, vol. 40, no. 3, 2002, pp. 965-994.

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

Recently \cite{CV1,CV2,CV3}
shape optimization techniques have been used to derive
appropriate speed functions for an active contour based solution
of the minimization problem for the Mumford-Shah functional. There, the
speed function represents usually the negative gradient direction of
a variant of the Mumford-Shah functional and negative gradient flow
is realized via the level-set formulation of a propagating interface
problem. We propose to replace the gradient direction by a Newton-type
descent direction where we apply techniques from classical shape sensitivity
analysis \cite{SZ,DZ} to derive the Newton system. The numerical realization of the Newton-type
level-set flow is presented and comparisons with gradient flow are made.
 

\bibitem{CV1}
T.~F. Chan and L.~A. Vese.
\newblock Image segmentation using level sets and the piecewise constant
  {M}umford-{S}hah model.
\newblock UCLA CAM Report 00-14, University of California , Los Angeles, 2000.

\bibitem{CV2}
T.~F. Chan and L.~A. Vese.
\newblock A level set algorithm for minimizing the {M}umford-{S}hah functional
  in image processing.
\newblock UCLA CAM Report 00-13, University of California , Los Angeles, 2000.

\bibitem{CV3}
T.~F. Chan and L.~A. Vese.
\newblock Active contours without edges.
\newblock {\em IEEE Trans. Image Processing}, 10(2):266--277, 2001.

\bibitem{DZ}
M.~C. Delfour and J.-P. Zol{\'e}sio.
\newblock {\em Shapes and geometries}.
\newblock Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
  PA, 2001.
\newblock Analysis, differential calculus, and optimization.

\bibitem{SZ}
J.~Soko{\l}owski and J-P. Zol{\'e}sio.
\newblock {\em Introduction to shape optimization}.
\newblock Springer-Verlag, Berlin, 1992.
\newblock Shape sensitivity analysis.