Direction des Relations Internationales (DRI)
BILAN TRIENNAL / THREE-YEAR REVIEW |
ATTENTION
: ce dossier doit obligatoirement être rédigé en
anglais
Please fill in this review in ENGLISH
EQUIPE ASSOCIEE |
SHAPES |
sélection / selected in year |
2007 |
Equipe-Projet INRIA / Research
team : |
Organisme étranger partenaire / Foreign Partner Institution: Florida State University |
Centre de recherche INRIA / Research
Center : Sophia Antipolis Mediterrannée |
Pays/Country : |
|
Coordinateur français/French coordinator |
Coordinateur étranger/Partner coordinator |
Nom, prénom / |
Zerubia, Josiane |
Srivastava, Anuj |
Organisme d'appartenance/ Home Institution,
Department, Lab |
INRIA, Ariana |
Florida State University, Department of Statistics |
URL |
||
|
La
collaboration en bref / The Collaboration in brief
Titre de la thématique de collaboration / Title of the collaboration theme : Statistical theory of configurations of shapes for analyzing aerial and satellite images |
Descriptif (environ 10 lignes) / Summary (approximately 10 lines) : The aim of this Associated Team is to combine the competences of EPI Ariana (INRIA/I3S), directed by Josiane Zerubia, in image processing, stochastic geometry, and MCMC techniques, with those of the team led by Anuj Srivastava in the Department of Statistics at Florida State University, in shape analysis and shape statistics applied to images. The synergy between the two groups via the Associated Team will allow advances in the problem of the detection of objects in high resolution satellite and aerial imagery, on the application side, as well as in the theory of shape modeling and statistics. |
|
INRIA |
Partenaire(s)/
Partner |
|
Chercheurs seniors impliqués |
Senior researchers involved |
3 |
4 |
Post-doctorants |
Post-doctoral graduates |
1 |
0 |
Doctorants |
PhD students |
2 |
3 |
Stagiaires |
Interns |
0 |
1 |
Thèses en co-tutelle soutenues |
Co-supervised defended PhD |
0 |
0 |
Thèses en co-tutelle en cours |
Current co-supervised PhD |
0 |
0 |
Total des thèses soutenues |
Global defended PhD |
1 |
1 |
Total des thèses en cours |
Global current PhD |
1 |
2 |
Visites de l'équipe partenaire (hors colloques) |
Travels to the partners (conferences not included) |
11 |
9 |
Nombre de Publications/Number of publications |
9 |
Quels sont, selon
vous, les points forts de cette collaboration et la valeur ajoutée
de l'Equipe Associée ? The main results are: the development of the SRV representation for curves in Rn, and the associated metrics and algorithms; the combination of shape tools and differential geometry leading to successful object recognition in cluttered point clouds; the development of computationally feasible marked point processes for general object shapes. None of these results could have been achieved without the collaboration enabled by the Associated Team funding. We note that the French Space Agency CNES is interested in marked point processes for general object shapes for the analysis of satellite images. |
Comment
envisagez-vous l'avenir de cette collaboration ?
(renouvellement de l'Equipe Associée, poursuite sur fonds
propres, projet européen ou autre, arrêt de la
coopération...) During the last year, the PhD work of Maria Kulikova has moved towards a fusion of the approaches to shape modeling and object extraction under investigation in Associated Team Shapes and the other Associated Team involving EPI Ariana, Odessa. When Odessa comes to an end next year, we envisage submitting a proposal for a single, new Associated Team involving all the partner teams of both Shapes and Odessa, and combining their research themes into a unified whole, stressing the commonalities and complementarities of the various approaches. |
Description de l'activité
scientifique de l'équipe associée et des résultats
obtenus au cours des 3 dernières années : publications,
communications, organisation de colloques, formation, soutenances de
thèse, valorisation économique, sociale, industrielle,
dépôt de brevets ... (maximum 5 pages)
Please
detail the Associate Team scientific activity as well as the results
obtained in the last 3 years : publications, communications,
organization of conferences, training, defended PhD, valorization,
patents filing.
This work introduces a square-root velocity (SRV) representation for analyzing shapes of curves in Euclidean spaces using an elastic metric. The SRV representation has several advantages: the well-known elastic metric simplifies to the L2 metric, the reparameterization group acts by isometries, and the space of unit length curves becomes the familiar unit sphere. The shape space of closed curves is a submanifold of the unit sphere, modulo rotation and reparameterization groups, and one finds geodesics in that space using a path-straightening approach.
The choice of a shape representation and a Riemannian metric are critically important for shape analysis and description – for improved understanding, physical interpretation, and efficient computing. This work introduces a particularly convenient representation for curves in Rn that enables a simple physical interpretation of the 'energy' of shape deformations. This representation is motivated by the well-known Fisher-Rao metric, used previously for imposing a Riemannian structure on the space of probability densities; taking the positive square-root of densities results in a simple Euclidean structure where geodesics, distances, and statistics are straightforward to compute. A similar idea was introduced by Younes [1] and later used in Younes et al. [2] for studying shapes of planar curves under an elastic metric. The representation used in our work is similar to these earlier ideas, but is sufficiently different to be applicable to curves in arbitrary Rn.
The main contributions of this research are as follows:
Introduction of the square-root velocity (SRV) representation for closed curves in Rn. This has the following advantages:
Under this representation, the previously-used elastic metric becomes a simple L2 metric for any n.
The action of the reparameterization group on the pre-shape space of parametrized curves is by isometries.
The space of fixed length curves is a Hilbert sphere with well-known geometry.
The use of a numerical approach, termed path-straightening, for finding geodesics between shapes of closed elastic curves. It uses a gradient-based iteration to find a geodesic where, using the Palais metric on the space of paths, the gradient is available in a convenient analytical form.
The use of a gradient-based solution for finding the optimal reparameterization of curves when finding geodesics between their shapes. We studied the relevant strengths and weaknesses of this gradient solution versus the commonly used Dynamic Programming (DP) algorithm.
The application and demonstration of this framework to: (i) shape analysis of cylindrical helices in R3 for use in studies of protein backbone structures, (ii) shape analysis of 3D facial curves, (iii) development of a wrapped normal distribution to capture shapes in a shape class, and (iv) parallel transport of deformations from one shape to another. The last item is motivated by the need to predict individual shapes or shape models for novel objects, or novel views of the objects, using past data.
Publications
Conference Paper: S. H. Joshi, A. Srivastava, E. Klassen and I. H. Jermyn, An Efficient Representation for Computing Geodesics Between n-Dimensional Elastic Curves, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Minneapolis, MN, June 2007.
Conference Paper: A. Srivastava, I. H. Jermyn and S. Joshi. Riemannian Analysis of Probability Density Functions with Applications in Vision, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Minneapolis, MN, June 2007.
Conference Paper: S.H. Joshi, A. Srivastava, E. Klassen, and I. H. Jermyn, Removing Shape-Preserving Transformations in Square-Root Elastic (SRE) Framework for Shape Analysis of Curves, Proceedings of Sixth International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR), pages 387-398, Hubei, China, August 2007.
Journal Paper: A. Srivastava, E. Klassen, S. H. Joshi, and I. H. Jermyn, Shape Analysis of Elastic Curves in Euclidean Spaces, Under review at Transactions of Pattern Analysis and Machine Intelligence, revised, May 2009.
We study the problem of classifying shapes in point clouds that are made of sampled contours corrupted by clutter and observation noise. Taking an analysis-by-synthesis approach, we simulate high-probability configurations of sampled contours using models learned from the training data to evaluate the given test data. To facilitate simulations, we develop statistical models for sources of (nuisance) variability: (i) shape variations within classes, (ii) variability in sampling continuous curves, (iii) pose and scale variability, (iv) observation noise, and (v) points introduced by clutter. The variability in sampling closed curves into finite points is represented by positive diffeomorphisms of a unit circle and we derive probability models on these functions using their square-root forms and the Fisher-Rao metric. Using a Monte Carlo approach, we simulate configurations using a joint prior on the shape-sample space and compare them to the data using a likelihood function. Average likelihoods of simulated configurations lead to estimates of posterior probabilities of different classes and, hence, Bayesian classification.
The process of estimating boundaries in images or videos uses low-level techniques that extract a set of primitives - points, edges, arcs, etc. - in the image plane, resulting in a cloud of primitives. Therefore, an important problem in object recognition is to (probabilistically) relate a given set of primitives to the predetermined (continuous) shape classes and to classify the shape of this set using a fully statistical framework.
|
|
|
|
---|---|---|---|
(a) Data |
(b) Clutter removal |
(c) Ordering |
(d) Classification |
Figure 1: Problem Challenges: for the point set shown in left, the points belonging to clutter are removed. The remaining points are ordered and classified into a shape class. |
Problem challenges
The biggest challenge in this problem is to select and organize a large subset of given primitives into shapes that resemble shapes of interest. The number of permutations for organizing primitives into possible shapes is huge. For example, the number of possible polygons using 40 distinct points in a plane is of the order 1047. Even if we take only 20 points, out of the given 40, to form a polygonal shape, the number of possibilities is still high ≈ 1029. To form and evaluate all shape permutations is impossible. Our solution is to analyze these configurations through synthesis, i.e. synthesize high-probability configurations from known shape classes and measure their similarities with the data. Although this approach has much less complexity compared to the bottom-up combinatoric approach, the joint variability of all the unknowns is still enormous. One has to put an additional structure into the problem by breaking down the variability into components, and probabilistically modeling the components individually. Through the examples presented in Figure 1 we will explain these components.
Background Rejection: Perhaps the most difficult issue is to determine which belong to the object contour and which belong to the background (clutter). Discarding clutter points takes us to go from (a) to (b) in Figure 1.
Ordering: Secondly, the ordering of primitives (along a curve) is most probably unknown. If n primitives are used in forming a polygonal shape, there are n! possibilities. Having a specific ordering will simplify our problem from (b) to (c) in Figure 1.
Classification: Finally, given an ordered set of primitives, all of them belonging to the curve, the task of shape (class) determination, that is going from (c) to (d), is still challenging, although not as difficult as going from (a) to (d). This part can become especially difficult when the shapes are heavily under sampled and the observation noise is high. To reach a statistical framework for this classification, we have to develop models for variabilities associated with shapes, the sampling process, and the observation noise.
Bayesian Solution
We have proposed and implemented a fully Bayesian approach that follows the paradigm of analysis by synthesis. The idea is to understand a given point cloud by by synthesizing high-probability configurations of points x generated by the object from prior models on shape given class, P(q|C), and on sets of sample points on the shape given class, P(s|C). These synthesized configurations are compared with the data y using a likelihood function based on the product of a Gaussian distribution for the distances between points in x and associated points in y, and a Poisson distribution for the points in y not associated to points in x, i.e. supposed generated by the background. The likelihood is obtained by optimizing over rotations, translations, and scaling of x, and over associations between the points of x and those of y. We use the standard Euclidean registration techniques for the former and the Hungarian algorithm for the latter. We can then estimate the posterior probability for class C, P(C|y), as follows. We: (i) randomly generate a Poisson random variable n (number of sample points on the curve), (ii) generate a shape q ∼ P(q|C) from the shape model for class C, (iii) generate a sampling function (diffeomorphism of the circle creating n points on the curve starting from uniformly spaced points Un) s ∼ P(s |C), and (iv) evaluate the likelihood of the resulting point set x = q(s(Un)) by solving the association and the registration problems mentioned earlier. Averaging of the likelihood over multiple realizations of n, q and s leads to a Monte Carlo estimate of the posterior. The method works well: the posterior probabilities are typically highest for the class to which the object in the image belongs, even though the training shapes used to develop the shape models P(q|C) were distinct and sometimes quite different from the shapes present in the test images.
Publications
Conference Paper: A. Srivastava and I. H. Jermyn, Bayesian Classification of Shapes Hidden in Point Clouds, Proceedings of 13th Digital Signal Processing Workshop, Marco Island, FL, January 2009.
Journal Paper: A. Srivastava and I. H. Jermyn, Looking for Shapes in Two-Dimensional, Cluttered Point Cloud, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 9, pages 1616-1629, September 2009.
We have studied the improvement in object
classification due to shape descriptors. The application addressed is
tree species classification based on tree crown contours extracted
from high resolution images. We consider a forest in Sweden where
only four species occur (birch, aspen, spruce and pine). A first
classification is performed using radiometric and textural features.
The textural features are derived from the co-occurrence matrices.
Therefore, we use first and second order statistics to describes tree
crowns. We then consider the shape description proposed by Srivastava
et al. [3] and the associated metric. We define some features from
this shape representation by considering the geodesic distance
between the considered shape and a disk. We add also some parameters
characterizing the angle function of the curve describing the shape
contour. We show that these shape descriptors improve tree crown
classification performance.
Publications
Conference
paper: M. S. Kulikova, M. Mani, A. Srivastava, X. Descombes and
J. Zerubia,
Tree Species Classification Using Radiometry, Texture
and Shape Based Features, Proc. European Signal Processing
Conference (EUSIPCO), 2007.
Over the past ten years, EPI Ariana has developed a methodology based on marked point processes for the detection of a collection of objects in an image. It consist in modeling the output as a configuration of objects, each described by a small number of parameters. Numerous applications have been addressed within this framework. However, one limit of this approach lies in the simplicity of the geometric description of the objects. Disks or ellipses have been used for tree detection, rectangles for building footprint extraction or segments for road network delineation. Recently, a new optimization algorithm has been proposed that outperforms the classical RJMCMC algorithm [4]. We therefore can expect to embed more complex descriptions of objects into the marked point process. In this context, we have proposed a marked point process modeling collections of potentially arbitrary shapes. To construct the set of objects for a given image, we evolve an active contour under gradient descent starting from a disk, the radius being the mark of the point in the configuration. The energy of the active contour contains two data terms: a Gaussian term inside and outside the shape and a contrast term along the contour; and two prior terms: contour length and another based on Fourier descriptors of the shape. In this way, by varying the position and the radius of the initial circle, we generate a set of objects adapted both to the data and to the prior information contained in the energy. We then invoke the marked point process framework to address the detection of multiple objects. The associated energy includes the active contour energy and a repulsive term encouraging objects not to overlap. The final configuration is obtained by simulated annealing based on multiple birth and death dynamics. We have applied this model to tree crown extraction. In terms of object detection, the results obtained provide performance similar to marked point processes based on simple parametric objects (ellipses in this case), but with a more detailed description of individual object geometry. Therefore, simple shapes like ellipses appear to be better adapted to counting objects, whereas, for example, for classifying trees into species or to evaluate the crown size, the approach described here is more accurate.
Publications
Conference paper: M. S. Kulikova, I. H. Jermyn, X. Descombes, E. Zhizhina and J. Zerubia, Extraction of arbitrarily shaped objects using stochastic multiple birth-and-death dynamics and active contours, IS&T/SPIE Electronic Imaging, San Jose, USA, January 2010.
Conference paper: M. S. Kulikova, I. H. Jermyn, X. Descombes, E. Zhizhina and J. Zerubia, A marked point process model with strong prior shape information for extraction of multiple, arbitrarily-shaped objects., Proc. IEEE SITIS, Marrakesh, Morocco, December 2009.
[1] L. Younes, Computable elastic distance between shapes, SIAM Journal of Applied Mathematics, 58(2):565–586, 1998.
[2] L. Younes, P. W. Michor, J. Shah, D. Mumford, and R. Lincei, A metric on shape space with explicit geodesics, Matematica E Applicazioni, 19(1):25–57, 2008.
[3] A. Srivastava, S. Joshi, W. Mio and B .Liu, Statistical Shape Anlaysis: Clustering, Learning and Testing, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(4), pages 590-602, April 2005.
[4] X. Descombes, R. Minlos and E. Zhizhina, Object Extraction Using a Stochastic Birth-and-Death Dynamics in Continuum, Journal of Mathematical Imaging and Vision, 33, pages 347-359, 2009.
April 2-13, 2007 - Visit to FSU, Tallahassee, Florida - Participants: X. Descombes, I. H. Jermyn,and M.S. Kulikova.
April 6, 2007 – 'Shape Day' Workshop at FSU. Participants: X. Descombes, I. H. Jermyn, S. Joshi, M.S. Kulikova, and A. Srivastava.
June 1-15, 2007 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participant: S. Joshi.
September 4-8, 2007 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participant: V. Patrangenaru.
September 20-26, 2007 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participant: A. Srivastava.
April 5-12, 2008 - Visit to the FSU - Participant: I. H. Jermyn.
April 7-11, 2008 - Visit to the FSU - Participant: X. Descombes.
June 3-8, 2008 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participant: A. Srivastava.
July 2-6, 2008 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participant: E. Klassen.
July 2, 2008 - Seminar at INRIA, Sophia-Antipolis, France - Speaker: E. Klassen.
July 7-11, 2008 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participant: A. Barbu.
Decembre 14-22, 2008 - Visit to the FSU - Participants: A. El Ghoul, C. Benedek.
Decembre 21, 2008 - Seminar at the FSU - Speakers: A. El Ghoul, C. Benedek.
Decembre 13-24, 2008 - Visit to the Ariana, INRIA, Sophia-Antipolis, France - Participant: J. Su.
February 23-28, 2009 - Visit to the FSU - Participant: M. S. Kulikova.
February 27, 2009 - Seminar at FSU - Speaker: M. S. Kulikova.
March 30 - April 5, 2009 - Visit to the FSU - Participant: I. H. Jermyn.
June 7-12, 2009 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participant: A. Srivastava.
June 8, 2009 - Seminar at INRIA, Sophia-Antipolis, France - Speaker: A. Srivastava.
June 2-14, 2009 - Visit to Ariana, INRIA, Sophia-Antipolis, France - Participants: S. Kurtek, W. Liu.
December 13-18, 2009 - Visit to Ariana, INRIA, Sophia-Antipolis, France – Participant: A. Srivastava.
The following junior scientists visited the corresponding partner team during the lifetime of the project:
INRIA: A. El Ghoul (PhD), M. S. Kulikova (PhD), and C. Benedek (Post-doc). All of these scientists gave seminars during one or more of their visits.
FSU: S. Joshi (PhD), W. Liu (PhD), S. Kurtek (PhD), and J. Su (Master).
Shantanu Joshi: July, 2007. Title: Inference in Shape Spaces with Applications to Computer Vision.
Maria Kulikova: December, 2009. Title: Shape Recognition for Image Scene Analysis.
© INRIA - mise à jour le 08/07/2009