Project topics and materials
Get Complete Project Material File(s) Now! »
Shape Sets and Basic Distances
Abstract
This chapter is dedicated to the definition of relevant sets of shapes and that of defining a metric on them. Following a recent research monograph by Delfour and Zolesio [33], we consider the characteristic functions of the subsets of R2 and their distance functions. The L2 norm of the difference of characteristic functions, the L∞ and the W 1 ,2 norms of the difference of distance functions define interesting topologies, in particular the well-known Hausdorff distance. Because of practical considerations arising from the fact that we deal with image shapes defined on finite grids of pixels we restrict our attention to subsets of R2 of positive reach in the sense of Federer [45], with smooth boundaries of bounded curvature. For this particular set of shapes we show that the three previous topologies are equivalent.
Introduction
Learning shape models from examples, using them to recognize new instances of the same class of shapes are fascinating problems that have attracted the attention of many scientists for many years. Central to this problem is the notion of a random shape which in itself has occupied people for decades. Frechet [48] is probably one of the first mathematicians to develop some interest for the analysis of random shapes, i.e. curves. He was followed by Matheron [76] who founded with Serra the french school of mathematical morphology and by David Kendall [57, 65, 66] and his colleagues, e.g. Small [104]. In addition, and independently, a rich body of theory and practice for the statistical analysis of shapes has been developed by Bookstein [10], Dryden and Mardia [39], Carne [13], Cootes, Taylor and colleagues [26]. Except for the mostly theoretical work of Frechet and Matheron, the tools developed by these authors are very much tied to the point-wise representation of the shapes they study: objects are represented by a finite number of salient points or landmarks. This is an important difference with our work which deals explicitly with curves as such, independently of their sampling or even parametrization.
In effect, our work bears more resemblance with that of several other authors. Like in Grenander’s theory of patterns [53, 54], we consider shapes as points of an infinite dimen-sional manifold but we do not model the variations of the shapes by the action of Lie groups on this manifold, except in the case of such finite-dimensional Lie groups as rigid displace-ments (translation and rotation) or affine transformations (including scaling). For infinite dimensional groups such as diffeomorphisms [41, 112] which smoothly change the objects’ shapes previous authors have been dependent upon the choice of parameterizations and origins of coordinates [118, 119, 114, 113, 81, 55]. For them, warping a shape onto another requires the construction of families of diffeomorphisms that use these parameterizations. Our approach, based upon the use of the distance functions, does not require the arbitrary choice of parameterizations and origins. From our viewpoint this is already very nice in two dimensions but becomes even nicer in three dimensions and higher where finding parame-terizations and tracking origins of coordinates can be a real problem: this is not required in our case. Another piece of related work is that of Soatto and Yezzi [105] who tackle the problem of jointly extracting and characterizing the motion of a shape and its deformation. In order to do this they find inspiration in the above work on the use of diffeomorphisms and propose the use of a distance between shapes (based on the set-symmetric difference described in section 1.2.2). This distance poses a number of problems that we address in the same section where we propose two other distances which we believe to be more suitable. They also use a signed distance score but it is non-symmetric with respect to the two regions and is not an approximation to a distance.
Some of these authors have also tried to build a Riemannian structure on the set of shapes, i.e. to go from an infinitesimal metric structure to a global one. The infinitesimal structure is defined by an inner product in the tangent space (the set of normal deformation fields) and has to vary continuously from point to point, i.e. from shape to shape. The Riemannian metric is then used to compute geodesic curves between two shapes: these geodesics define a way of warping either shape onto the other. The distance between the shapes is then given by the length of the geodesic path. This is dealt with in the work of Trouvé and Younes [118, 119, 112, 114, 113, 120] and, more recently, in the work of Klassen and Srivastava [68], again at the cost of working with parameterizations. The problem with these approaches, beside that of having to deal with parameterizations of the shapes, is that there exist global metric structures on the set of shapes (see section 1.2.2) which are useful and relevant to the problem of the comparison of shapes but that do not derive from an infinitesimal structure. Our approach can be seen as taking the problem from exactly the opposite viewpoint from the previous one: we start with a global metric on the set of shapes and build smooth functions (in effect smooth approximations of these metrics) that are dissimilarity measures, or energy functions; we then minimize these functions using techniques of the calculus of variation by computing their gradient and performing infinitesimal gradient descent (see part II): this minimization defines another way of warping either shape onto the other. In this endeavor we build on the seminal work of Delfour and Zolesio who have introduced new families of sets, complete metric topologies, and compactness theorems. This work is now available in book form [33]. The book provides a fairly broad coverage and a synthetic treatment of the field along with many new important results, examples, and constructions which have not been published elsewhere. Its full impact on image processing and robotics has yet to be fully assessed.
Section 1.2 sets the stage and introduces some notations and tools. In particular in section 1.2.2 we discuss three of the main topologies that can be defined on sets of shapes and motivate the choice of two of them. In section 1.3 we introduce the particular set of shapes we work with in this chapter, show that it has nice compactness properties and that the three topologies defined in the previous section are in fact equivalent on this set of shapes.
Shapes and shape topologies
To define fully the notion of a shape is beyond the scope of this chapter in which we use a limited, i.e purely geometric, definition. It could be argued that the perceptual shape of an object also depends upon the distribution of illumination, the reflectance and texture of its surface; these aspects are not discussed here. In our context we define a shape to be a measurable subset of R2. Since we are driven by image applications we also assume that all our shapes are contained in a hold-all open bounded subset of R2 which we denote by D. The reader can think of D as the « image ».
In the next section we will restrict our interest to a more limited set of shapes but presently this is sufficient to allow us to introduce some methods for representing shapes.
Definitions
Since, as mentioned in the introduction, we want to be independent of any particular parametrization of the shape, we use two main ingredients, the characteristic function of a shape Ω
χΩ(x) = 1 if x ∈ Ω and 0 if x ∈/ Ω, and the distance function to a shape Ω
dΩ(x) = inf y x = inf d(x, y) if Ω = + ∞ if Ω = ∅ .
y Ω | − | y Ω 6 ∅ and
Note the important property [33, chapter 4, theorem 2.1]: (1.1) dΩ1 = dΩ2 ⇐⇒ Ω1 = Ω2
Also of interest is the distance function to the complement of the shape, d{Ω and the distance function to its boundary, d∂Ω. In the case where Ω = ∂Ω and Ω is closed, we have dΩ = d∂Ω d{Ω = 0
We note Cd(D) the set of distance functions of nonempty sets of D. Similarly, we note Cdc(D) the set of distance functions to the complements of open subsets of D (for technical reasons which are irrelevant here, it is sufficient to consider open sets).
Another function of great interest is the oriented distance function bΩ defined as bΩ = dΩ − d{Ω
Note that for closed sets such that Ω = ∂Ω, one has bΩ = dΩ.
We briefly recall some well known results about these two functions. The integral of the characteristic function is equal to the measure (area) m(Ω) of Ω
Note that this integral does not change if we add to or subtract from Ω a measurable set of Lebesgue measure 0 (also called a negligible set).
Concerning the distance functions, they are continuous, in effect Lipschitz continuous with a Lipschitz constant equal to 1 [31, 33]: |dΩ(x) − dΩ(y)| ≤ |x − y| ∀x, y, ∈ D.
Thanks to the Rademacher theorem [42], this implies that dΩ is differentiable almost every-where in D, i.e. outside of a negligible set, and that the magnitude of its gradient, when it exists, is less than or equal to 1 |rdΩ(x)| ≤ 1 a.e..
The same is true of d{Ω and bΩ (if ∂Ω 6= ∅ for the second), [33, Chapter 5, theorem 2.1]. Closely related to the various distance functions (more precisely to their gradients) are the projections associated with Ω and {Ω. These are also related to the notion of skeleton.
We recall some definitions. The first one is adapted from [33, Chapter 4 definition 3.1]:
Definition 1 (Projections and skeletons).
• Given Ω ⊂ D, Ω 6= ∅ (resp. {Ω 6= ∅), the set of projections of x ∈ D on Ω (resp. on {Ω) is given by
def ΠΩ(x) = {p ∈ Ω : |p − x| = dΩ(x)}
def (resp. Π{Ω(x) = {p ∈ {Ω : |p − x| = d{Ω(x)})
The elements of ΠΩ(x) (resp. Π{Ω(x)) are called projections onto Ω (resp. {Ω).
• Given Ω ⊂ D, Ω 6= ∅ (resp. {Ω 6= ∅), the set of points where the projection on Ω (resp. {Ω) is not unique is called the exterior (resp. interior) skeleton Skext(Ω) (resp. Skint(Ω)). We define Sk(Ω) = Skext(Ω) ∪ Skint(Ω).
The following properties of the skeletons can be found e.g. in [33, Chapter 4, theorems 3.1 and 3.2]
Proposition 2. The exterior (resp. interior) skeleton is exactly the subset of {Ω (resp. of int(Ω)) where the function dΩ (resp. d{Ω) is not differentiable. Moreover the exterior and interior skeletons and the boundary ∂Ω is exactly the subset of D where d∂Ω is not differentiable.
At each x of {Ω\Skext(Ω), the gradient of the distance function d∂Ω is well-defined, of unit norm, and points away from the projection y = ΠΩ(x) of x onto Ω, see figure 1.1. Similar considerations apply to the case where x ∈ Ω.
We introduce an additional definition that will be useful in the sequel.
Definition 3. Given Ω ⊂ D, Ω 6= ∅, and a real number h > 0, the h-tubular neighborhood of Ω is defined as def Uh(Ω) = {y ∈ D : dΩ(y) < h}
Table of contents :
Introduction
Résumé en français
I Shapes and Distances
1 Shape Sets and Basic Distances
1.1 Introduction
1.2 Shapes and shape topologies
1.2.1 Definitions
1.2.2 Some shape topologies
1.3 The set S of all shapes and its properties
1.3.1 The set of all shapes
1.3.2 Compactness properties
1.3.3 Comparison between the three topologies on S
1.3.4 Minima of a continuous function defined on S
2 Shape Distance Approximations
2.1 How to approximate shape distances
2.1.1 Averages
2.1.2 Approximations of the Hausdorff distance
2.1.3 Continuity
2.1.4 A possible extension of the approximation by changing the measure
2.1.5 Other alternatives related to the Hausdorff distance
2.1.6 Approximations to the W1,2 norm
2.2 Quality of the approximation
2.2.1 Quality of the approximation ˜H of H
2.2.2 Some basic invariance properties of the approximation
3 Different Notions of Shape and Associated Distances
3.1 Full shapes vs boundaries
3.1.1 Definitions
3.1.2 Hausdorff distance between boundaries of shapes
3.2 Incorporating shape descriptors
3.2.1 Motivation
3.2.2 A first extension of the Hausdorff distance to boundary orientation
3.2.3 Extension of the Hausdorff distance to shape local descriptors
3.2.4 A distance in the set of local descriptions: the local cross-correlation
3.3 Shapes as images, images as shapes
3.3.1 Full shapes and images
3.3.2 Local cross-correlation
3.3.3 Distance related to the local cross-correlation
3.3.4 Distances and deformation
3.3.5 Multiscale
4 Shape Statistics Based on the only knowledge of Distances
4.1 Exact representation of a set of shapes in a finite dimensioned vector space
4.2 Graph Laplacian and best approximative map
4.3 Examples of maps
II Shape Warping
5 Shape Gradient and Shape Warping
5.1 Deforming shapes
5.1.1 Derivatives of an energy and gradient
5.1.2 Derivatives in the metric space S
5.1.3 A word on transports
5.1.4 A word on geodesics
5.1.5 From the theoretical framework to the practice
5.1.6 Computing the gradient of the approximation to the Hausdorff distance
5.1.7 Computation of the gradient of the approximation to the W1,2 norm
5.1.8 Direct minimization of the W1,2 norm
5.2 Application to curve evolutions: Hausdorff warping
5.2.1 Applying the theory
5.2.2 Some remarks about our implementation
5.2.3 Comparison with other approaches
5.3 Computations
5.3.1 Computation of r ˜H(, 0)
5.3.2 Computation of r˜D(, 0)
6 Intrinsic Differentiation
6.1 Differentiation with respect to parameters
6.2 Intrinsic differentiation
7 Generalized Gradients: Priors on Minimization Flows
7.1. Introduction
7.2. Minimization and inner product
7.3. New Inner Products and New Flows
7.3.1 . Designing new inner products
7.3.2 . Designing new minimizing flows
7.3.3 . Adding an orthogonal term
7.4. Some Spatially Coherent Minimizing Flows
7.4.1 . Motion decomposition
7.4.2 . The Sobolev H1 gradient flow
7.4.3 . Intrinsic Gaussian smoothing
7.5. Numerical Experiments With The New Inner Products
7.5.1 . Shape warping
7.5.2 . Tracking
7.5.3 . Landmarks-guided shape warping
7.6 Combination of the effects of two different inner products
7.6.1 Nothing but a symmetric way to preserve the symmetry
7.6.2 Better weights in the symmetry for parameterized groups
7.6.3 Extension towards homogeneity
7.6.4 The smoothed rigidification case
8 Extended Gradient: more General Priors
8.1. The meaning of the gradient
8.2. Generalization of the regularizing term
8.3. Remarks
8.3.1 Addition of an orthogonal term
8.3.2 Directional formulation
8.3.3 Temporal coherence
8.4. Computing the extended gradient
8.5. Application: the semi-local rigidification
8.6. Numerical Example
8.7. Conclusion
III Shape Statistics and Priors
9 Shape Statistics: Empirical Mean and Modes of Variation
9.1 Empirical mean
9.2 Empirical covariance
9.3 Examples of modes of variation
9.4 Comparison with other approaches
10 Image Statistics and Object Classification
10.1. Introduction
10.2. Image matching
10.3. The mean of a set of images
10.3.1. An intuitive algorithm: find the mean
10.3.2. Another intuitive algorithm
10.3.3. The final word: eliminating the mean
10.3.4. Example
10.4. Second order statistics of a set of images
10.4.1. Definition and computation
10.4.2. Example
10.4.3. Intensity variations
10.5. Classification: Expression Recognition
10.5.1. From the mean image
10.5.2. With knowledge of the face without expression
10.6. Summary and Conclusions
11 Image Segmentation with Shape Priors
11.1 Image Segmentation
11.2 Shape Priors
11.2.1 Context
11.2.2 Shape Probability
11.2.3 Invariance with respect to Rigid Motion
11.2.4 Pre-Computing
11.2.5 Influence of the inner product
11.3 Hausdorff second order derivative
11.3.1 Notations
11.3.2 First order derivative
11.3.3 Second order derivative
11.3.4 Calculi
11.4 Examples of Segmentation with Shape Priors
11.4.1 Rigid registration of a fixed shape
11.4.2 Parzen method with the Hausdorff distance
11.4.3 Gaussian Eigenmodes
Discussion
Bibliographie
