Printer Friendly

Geometric sampling of infinite dimensional signals.

1 Preamble

In [58], [59] we have introduced a geometric approach to sampling and reconstruction of images (and also of more general signals). Further extensions [5] and applications [60] of this paradigm and its ensuing results were considered. For the readers' convenience, we briefly present here some of the key aspects of this framework: Lately it became quite common amongst the signal processing community, to consider images as Riemannian manifolds embedded in higher dimensional spaces (see, e.g. [27], [35], [62], [64]). Usually, the preferred ambient space is [R.sup.n], however other possibilities are also considered ([7], [57]). In this approach, gray scale images are viewed as surfaces in [R.sup.3], while color images as surfaces embedded in [R.sup.5], each color channel representing a coordinate of the ambient space. In each of these cases the intensity, either gray scale or color, is considered as a function of the two spatial coordinates (x, y) and thus the surface may be equipped with a metric induced by the Euclidean metric of the ambient space. A similar approach is prevalent also in medical imaging, where it is convenient to regard CT/MRI scans as Riemannian surfaces embedded in [R.sup.3]. However, these represents the simplest cases: On the one hand, if more attributes are added, such as luminosity, texture, etc., then the objects under consideration are higher dimensional manifolds, not simply 2-dimensional ones (i.e. surfaces); on the other hand, even surfaces need not be just parametric ones, but they can be globally defined as well, e.g. by classical topological "gluing" --see [54] for a typical example and an extensive discussion. It should be noted that the question of smoothness of the manifolds in question is in general omitted, and classical numerical schemes are used for the approximations of derivatives, whenever this is deemed necessary. However, this restriction appears somewhat artificious and we have proposed a number of methods for realistically dealing with this problem in [59], [55], [60].

In view of the model discussed above, it is quite transparent by now that, by a geometric approach, we mean one that is based on sampling the graph of the signal, considered as a manifold, rather than a sampling of the domain of the signal, as is customary in both theoretical and applied signal and image processing. However, the geometric vein of our method runs much deeper that the mere interpretation of images as manifolds: The density of the sampling points is a function of the curvature of the manifold, while at the reconstruction stage classical techniques of differential topology [44] and differential geometry [45] are employed.

For practitioners of harmonic analysis, be they theoreticians (i.e. mathematicians) or applications driven (e.g. researchers in image and signal processing), this may appear, at first sight, strange, if not even incorrect. However, our approach to the sampling and reconstruction of images, stems from the classical "'grayscale" surface model permeating imaging (see, for instance, [31] or [23] for basic textbooks and [35] for a more advanced discussion).

Given this universally accepted paradigm of imaging, it will now appear quite naturally to view images as surfaces and higher dimensional manifolds, hence use tools that are basically geometric in nature, and to seek for relevant results in differential geometry and topology. In consequence, it will come as no surprise-quite the contrary-that our method is nothing but an adaptation of the triangulation method for surfaces and higher dimensional manifolds developed originally by Cairns [9], and its subsequent extensions and generalizations [48], [51]. We should emphasize that this certainly is not the only possible triangulation approach. Indeed, two more possible approaches were considered in [52] (this method being extended to more general spaces in [53]) and [61], respectively. It should be also stressed that the construction method of [51], [52] rests upon the ideas and results of Munkres [44], and that introduced in [53], on those of Colin de Verdiere [15] and Hatcher (unpublished). Needless to say, the subject of sampling and reconstruction of manifolds has generated, and still generates, a vast amount of research in graphics, imaging, etc., therefore the relevant literature is far too extensive to even contemplate here an exhaustive list. In consequence, we cite only a few representative works: [3], [13], [19], [38], [47]. (See also the reference in Remark 2.1 below.)

The main body of the paper is divided into three sections: In Section 2 we show that our geometric sampling method for images, naturally extends to a quite extensive class of infinitely dimensional manifolds (or signals) common in image processing and related fields. This represents, essentially, an exposition of an older result of McKean [40]. (Part of the material included in this section -namely Subsection 2.2-stems from the preprint [56].) In Section 3 we present the triangulation results-albeit purely topological in nature-that do exist for the essential classes of infinite dimensional manifolds and interpret them in the context of signal and image processing. We also recall classical homeomorphism results between probability spaces and the basic model infinite dimensional manifolds. As an application of these facts we introduce, in Section 3.1, a simple geometry on P(X)-the space of probability' measures on a set X- and further show that, if X is a finite set, it endows P(X) with the same type of curvature as the classical Fisher metric. Finally, in Section 4, we bring forward the existence of a natural isometric embedding of images in an infinitely dimensional function space, as well as an isometric embedding into a finitely dimensional function space, that is bi-Lipschitz relative to the infinitely dimensional one. Two other method of embedding finitely dimensional manifolds into function spaces are also briefly discussed. (Some of matter covered in this section is also presented, in a quite different context, in the preprint [54].) We conclude with a few brief summarizing remarks.

2 Extending the Geometric Method to Infinite Dimensional Signals

First, to facilitate an easier reading of the sequel, we briefly present the geometric sampling method.

2.1 The geometric sampling scheme

The first stage of the sampling scheme consists in isometrically embedding, using the Nash Embedding Theorem, the image-manifold into some [R.sup.N], for N sufficiently large. For this the manifold is supposed to be sufficiently smooth, i.e. of class [C.sup.k], k [greater than or equal to] 3.

Next, a sequence A = [{[a.sub.i]}.sub.i] of points on the manifold is constructed, such that it satisfies a certain variable (local) and adaptable density condition, that is a function of the curvature of the manifold. This condition quantifies the delicate interplay between the intrinsic and extrinsic curvatures of the manifold, expressed via the so called connectivity radius and tubular radius, respectively. (For details, see [58]. For a full proof see [48], for unbounded manifolds, and [51], for manifolds with boundary.)

Remark 2.1 Recently, a combination of such intrinsic and extrinsic curvatures for triangulation of surface for graphics and related application fields, was given in [18].

The next stage of the construction is to generate the Euclidean Voronoi (Dirichlet) N-dimensional cell complex generated by the set A (of centers [a.sub.i]). It should be noted that, while we are compelled, by using Nash's Theorem, to embed [M.sup.n] in some [R.sup.N], for a usually very large N, this may, in fact, turn to our advantage, since the higher codimension allows for better and easier separation of the sampling points. Unfortunately, to ensure that the ensuing Delaunay (dual) triangulation has the thickness (or fatness) property (see, e.g. [58]), guaranteeing faithful reconstruction of the manifold from the point samples (see [58]), this direct construction does not suffice. In order that the Delaunay triangulation satisfy the thickness property, a dual cell complex must be first constructed, and the projection of its dual triangulation on the manifold will represent the triangulation of [M.sup.n] satisfying the required property. To obtain this dual cell complex, one has to "cut up" the manifold using (N-1)-dimensionai hyperplanes normal to [M.sup.n] and bisecting the segments [bar.[a.sub.i][a.sub.j]], for adjacent points [a.sub.i] and [a.sub.j]. (For the full detail of the construction, see [48] and for a comprehensive, yet less technical overview of the construction, [58].)

2.2 Geometric sampling of infinitely dimensional signals

Since in the classical context band-limited signals are viewed as elements f of [L.sup.2](R), such that supp ([??]) [subset or equal to] [-[pi],[pi]], where [??] denotes the Fourier transform of f, it is interesting to ask the following question: Can one extend the sampling theorem proven in [58] to infinite dimensional manifolds? Using an example introduced in [40], it may be concluded that this question is not only far from being naive, but rather the answer is positive: Our geometric sampling method translates directly into the context of infinite dimensional manifolds, at least for a class of functions that naturally arise in the the context of [40]. However, since the full proofs required in the example below are quite technical, we refer the reader to the original paper [40], and limit ourselves here to a brief presentation. Consider the following spaces:


where Q denotes the Hill operator: Q = -[D.sup.2] + q, q(x + 1) = q(x), and where D = [partial derivative]/[partial derivative]x, 0 [less than or equal to] x < 1. Somewhat less technically put, M denotes the set of real functions of class [C.sup.[infinity]], having period 1, and such that their corresponding Hill operator Q has ground state [[lambda].sub.0] = 0.

Since 1 and 0 are regular values for their respective funetions, M is a smooth, co-dimension one hyper-surface in [C.sup.[infinity].sub.1], that is endowed with the topology inherited from that of [C.sup.[infinity]], endowed with the "sup" norm. Further, exactly as in the finite-dimensional case (see [59]), for any 2-dimensional plane [PI] determined by unit tangent vectors to M at q, one can define and, moreovere, actually compute the maximal principal curvature of the corresponding 2-dimensional surface.

Moreover, since the co-dimension of M in [C.sup.[infinity].sup.1] is 1, it follows that, together with a tangent plane, a normal to M at q is also defined. Therefore, one can use the same method as in the finite dimensional case (see [59]) to find a sampling. of M.

In consequence, a sampling scheme identical to that developed for the finite dimensional case can be applied for the manifold M, as well. Unfortunately, no uniform sampling is possible for the entire manifold: the maximal curvature, associated with functions approximating "saw-tooth" functions can be made as large as desired (see [40]).

3 Hilbert cube manifolds

One would like to extend the considerations above, in a systematic manner, to general infinite dimensional manifolds, e.g. [l.sub.2] and Hilbert cube manifolds.

However, even if the appropriate geometric differential notions are defined and computed, the fundamental problem of constructing fat triangulations for infinite dimensional manifolds still has to be dealt with. It is therefore important to note that triangulations of such manifolds exist (see [11]). However, even finding a notion analogous to that of fatness in the [infinity]-dimensional case represents a challenge, insofar as even a proper definition of dihedral angles is problematic --see, however, Remark 3.5 below. (For a different approach to a differential geometry of some infinite dimensional spaces see for example [42].)

Still, for example, the triangulation of Hilbert cube manifolds--that represent the "archetypal" infinitely dimensional manifolds--is possible and, moreover, we have a by now classical Triangulation Theorem for Hilbert cube manifolds. However, we have first to recall that the Hilbert cube Q is defined as the countable infinite product of the segment [-1, +1] with itself, i.e. Q = [I.sup.w] = [[PI].sup.[infinity].sub.n=1] [I.sub.n], where [I.sub.n] = [-1, +1], n [greater than or equal to] 1. Moreover, Q is a (compact) metric space, with the [l.sub.2] metric


We also need to remind the following definition:

Definition 3.1 A polyhedron is a locally compact (or locally finite) space, triangulated by a simplicial complex K, i.e. P = [absolute value of K].

(For the necessary background in PL topology see, e.g. [30].)

We can now state the Triangulation Theorem for Hilbert cube manifolds:

Theorem 3.2 ([11], Theorem 37.2; [63], [section] 6,7) Let [M.sub.Q] be a Hilbert cube manifold. Then, [M.sub.Q] [??] P x Q, where Q denotes the Hilbert cube and where K represents a polyhedron. (Here [??] denotes homeomorphism.)

Remark 3.3 The theorem above shows, that, perhaps against "common sense", infinitely dimensional manifolds are much easier to triangulate than their finitely dimensional non-smooth counterparts, due to the lack of the intricate obstructions that appear in the finitely dimensional case.

Remark 3.4 The proof of the triangulation theorem resembles the one for the finitely dimensional case (see also [52], [61]), in so far as it produces an exhaustion of the manifold by nested relatively compact set, that intersect in "good" bicollared neighbourhoods. However, while in the Riemannian case the "chopping of compact pieces" criterion is based on curvature--obviously not feasible for Hilbert cube manifolds--in the case of Q-manifolds this is done via homotopy type.

Remark 3.5 While, a noted above, a general notion of fat triangulation eludes at for the moment, Theorem 3.2 allows us to formulate a practical--at least from the implementational viewpoint--definition: A triangulation of a Hilbert cube manifold MQ will be called fat if its restriction to P is fat, where P is as in Theorem 3.2 above.

The main reason for considering Q-manifolds and the search for a fitting sampling theory derives from the natural occurrence of this class of geometrical objects, for instance, in the context of continuous variations and deformations of signals, e.g video, perceived as an infinite sequence, or even a continuum, of images, each being viewed as a "classical" signal, hence given via the Stone-Weierstarss Theorem as an arbitrarily good approximation by a series of trigonometric functions or, via Shannon's Theorem, by a series of "sine" functions. In this context we may interpret the Triangulation Theorem above as indicating that the decomposition of [M.sub.Q] into the product of a polyhedron and a segment is somewhat akin to the Taylor polynomial and reminder, in the case, say, of real functions. In our case, the polyhedron represents the (bits of) essential information, reproducible, at least theoretically, from its point samples (i.e. vertices) while the segment [0, 1) stands for the perhaps less important deformation of the said information, e.g. in time, or by other perturbation (such as continuous noise). Another possible interpretation--suggested to us by K. Polthier--is to consider the space of spline functions applicable for the possible reconstruction of an image. In this instance, the polyhedron in the Triangulation Theorem represents the set of minimal (or, rather, essential in a natural sense) set of such functions necessary for a faithful reconstruction of the given image.

That Hilbert cube manifolds do not represent a whimsical choice, but rather a natural one, is further augmented by the fact that such manifolds represent a kind of "universal space" for a large class of metric spaces:

Theorem 3.6 Any separable metric space admits an isometric embedding into Q. (Recall that a topological space X is called separable iff there exists [X.sub.0] [subset] X such that [absolute value of [X.sub.0] is countable and its closure [[bar.X].sub.0]] = X.)

(For a proof see, e.g., [43].)

A no less important motive to study Hilbert cube manifolds is supplied by the fact that they represent "good" representations of probability spaces, more exactly we have the following results:

Theorem 3.7 ([20], [16]) Given a space X, the following statements are equivalent:

1. X is compact and uncountable;

2. P(X) [??] Q;

3. [M.sup.+(X)] [??] Q x [0,1).

The probability space of a noncompact manifold similarly coincides with [R.sup.w] denotes the countable infinite product of the real line with itself, [R.sup.w] = [I.sup.w] = [[PI].sup.[infinity].sub.n=1] R, endowed with the [l.sub.2] metric.

Theorem 3.8 ([16]) Given a space X, the following statements are equivalent:

1. X is a noncompact Polish space;

2. P(X) [??] [R.sup.w]

3. [M.sup.+] (X) [??] [R.sup.w]

(Recall that a topological space is called Polish iff it is separable and completely metrizable, i.e. homeomorphic to a complete metric space.)

In both theorems above, P(X) denotes the space of probability measures on X, and [M.sup.+](X) denotes the set of nonnegative Borel measures on X.

Remark 3.9 Note that by [11], Theorem 23.1, Q x [0, 1) is (trivially) triangulable.

We also briefly mention here another infinite dimensional model space, that is relevant for signal processing:


For results similar to Theorems 3.7 and 3.8 above, regarding [SIGMA], see [20], [11].

Of course, abstract infinite dimensional manifolds appear intimidating and it is only natural to seek a "reassuring" result, namely an infinite dimensional counterpart, if not of Nash's Isometric Embedding Theorem, then at least of Whitney's Topological Theorem (see, e.g. [43]). It turns out that, in fact, infinite dimensional manifolds are, essentially, the open subsets of the model space:

Theorem 3.10 (Open Embedding Theorem; [28], [29], [10], [11]) The following open embedding results hold:

1. [R.sup.w] (E) manifolds coincide with the open sets of [R.sup.w] ([SIGMA]).

2. Let [M.sub.Q] be a Q-manifold. Then [M.sub.Q] x [0, 1) admits an embedding as an * open subset of Q.

Remark 3.11 It is important to stress that the discussion regarding the space of probability measures P(X), both above and in the following subsection, is not whimsical, but that this mathematical object arises naturally and plays an important role in imaging. Indeed, this role is manifold and appears at various levels of image processing and analysis. Probability and related distributions appear, of course, at the very roots of elementary image processing, both "classical" and digital image processing, as histograms and masks. Probabilities may also arise--after a possible suitable normalization--as uncertainties intrinsic to the acquiring of the image (for instance in ultrasonography), in modeling textures and, in a variety of instances, as ad hoc tools employed at various stages of the implementation of a variety of tasks, such as smoothing, (elastic) registration, warping, segmentation, etc. (see, e.g. [4]). However, in the context of Medical Imaging, densities (thus probabilities) appear at even a more basic, intrinsic level. A typical example is that of MRI Imaging; indeed, the density of many types of MRI images is equal to the very proton density. It also appears, via optimal transportation (see e.g. [66] for a comprehensive reference) in such imaging tasks as aligning, shape comparison, recognition and retrieval, as well as texture mapping--see, amongst others, [21], [1], [50], [41], [17].

3.1 A simple geometry on P(X)

Using Theorem 3.7(2) one can endow P(X), X compact and uncountable, with a metric [[rho].sub.[phi]] defined to be the pull-back, via a homeomorphism [phi] : P(X) [??] Q, of the [l.sub.2] metric on Q, i.e. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Of course, this homeomorphism may well not be unique. However, by its very definition, [[rho].sub.[phi]] reproduces the intrinsic properties of the standard geometry of Q. In particular, we conclude that if X is a compact, uncountable space, then P(X) has non-negative curvature. Indeed, Q has this property, as a convex subset of the Hilbert space [R.sup.[omega]] that is fiat (and separable)--see, e.g. [49].

In the same manner, using Theorem 3.8, we obtain that P(X) is flat if X is a noncompact Polish space.

Moreover, if X is a finite set with n+ 1 points, then P(X) is homeomorphic to an n-dimensional cube (see [20]), hence it has positive curvature or, perhaps more correctly: non-negative curvature, since the cube is flat except at the vertices. Compare this last result with the fact (well known in Information Geometry) that the probability simplex [[sigma].sub.0] = {p(x) | x [member of] A, p(x) > O, [[SIGMA].sub.A] p(x) z 1}, endowed with the Fisher metric, maps isometrically onto the first orthant of the sphere S = [[SIGMA].sub.A] u[(x).sup.2] = 4 (see [2]), therefore implying a spherical geometry - hence a positive curvature - on P(X).

In this context it is relevant to note that we obtain a simple proof of the fact that P(X) (X compact and uncountable) has positive Alexandrov (comparison) curvature [46]. Furthermore, it explains why in this case P(X) is compact yet infinitely dimensional. These observations illustrate that one can, indeed, use this simple [l.sub.2] metric to determine the basic geometric properties of on P(X), and use the more expressive and perhaps more intuitive--but far more intricate and difficult to analyze--metrics, such as the Wasserstein metric [W.sub.2] (or the Prokhorov metric d p)--see, e.g. [66], to obtain the fine properties of P(X), such that, for instance, (P([R.sup.n]), [W.sub.2]) has non-negative sectional curvature. This agrees, incidentally, to our assessment of [R.sup.w] as being flat.

Remark 3.12 Of course, the metrization proposed here--and the comparison geometry it produces--is far more "rough" than the one given by the Wasserstein metric. This is illustrated, for instance, by the fact ([39], [65]) that, given a (compact) Riemannian manifold M, (P(M), [W.sub.2]) has non-negative Alexandrov curvature iff M has non-negative sectional curvature (see also the discussion above).

4 From Images to Function Spaces

The approach presented in this section stems from the observation that one can embed [M.sup.n] not in some [R.sup.N], but in an infinitely dimensional space, more precisely in [L.sup.[infinity]] ([M.sup.n])--the (Banach) space of bounded Borel functions on [M.sup.n], endowed with the "sup" metric, i.e. d(f,g) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for any f, g [member of] [L.sup.[infinity]] ([M.sup.n])--via the Kuratowski Embedding [37]:

Definition 4.1 (Kuratowski embedding) Let [M.sup.n] be a closed Riemannian manifold. Then

K: [M.sup.n] [right arrow] [L.sup.[infinity]] ([M.sup.n]), K(x) = [dist.sub.x],


[dist.sub.x] = dist(x,*), (1)

and where "dist" denotes the (intrinsic, Riemannian) distance on [M.sup.n], is called the Kuratowski embedding (of [M.sup.n]).

Remark 4.2 For topological manifolds the Kuratowski embedding can be obtained by using the length of curves as given, for instance, by the realization of [M.sup.n] as a submanifold of [M.sup.2n], via the standard Whitney embedding (see, e.g.,

This method is much more powerful than it would appear at first sight. Indeed, the Kuratowski embedding is an isometry, more precisely we have the following Lemma (see, e.g. [26]):

Lemma 4.3 With the notation above, we have

d([dist.sub.x], [dist.sub.y]) = dist(x, y).

Remark 4.4 This approach is widely divergent from the Riemennian embedding one adopted in Nash's Theorem. Indeed, the Riemannian and Kuratowski embeddings coincide iff K([M.sup.n]) [subset] [L.sup.[infinity]] ([M.sup.n]) is a convex, open subset of an affine linear subspace of dimension n.

On behalf of the Kuratowski embedding, one can remark that, albeit being infinite dimensional, it may be quite advantageous when a functional approach is needed or sought for (e.g. when considering spline functions, wavelets, etc.). Note that a closely related approach is well known to the imaging and vision community: Embedding by using the eigenvalues of the Laplacian or of the Green kernel. (For applications of these methods in the context of Riemannian geometry, see, e.g. [6], [32].) However, usually--and more realistically-the spaces that appear in computer science, and even more so in graphics, are finitely dimensional. Moreover, most people in the said communities find infinitely dimensional spaces as somewhat of an artifice, highly nonintuitive, and of theoretical value at best.

Fortunately, there exists a finitely dimensional version of the Kuratowski embedding. However, we first need to recall the following definition:

Definition 4.5 Let (X,d) be a metric space, and let A [subset] X. A is called an [epsilon]-net iff d(x, A) [less than or equal to] [epsilon], for all x [member of] X.

We can now introduce the finite dimensional version of the Kuratwoski embedding: Let X be an [epsilon]-net in [M.sup.n], [absolute value of X] = m. Then, for small enough [epsilon], [K.sub.X] : X [right arrow] [l.sup.m.sub.[infinity]] is an embedding, where [K.sub.X] = [K|.sub.x] - the restriction of K to X, and [l.sup.m.sub.[infinity]] denotes the m-dimensional Banach space endowed, again, with the "sup" metric: if x = ([x.sub.1],... ,[x.sub.m]), then [parallel]x[parallel] = [sup.sub.i] [absolute value of [x.sub.i]].

Moreover, we can assure that this "discrete" version of the Kuratowski embedding is bi-Lipschitz, more precisely we have the following result ([26], [34]):

Theorem 4.6 Let [M.sup.n] be a compact Riemannian manifold without boundary.

Then, for any C > O, there exists a [epsilon]-net X, where [epsilon] = [epsilon] (C), such that

(1- C)dist(x, y) [less than or equal to] [absolute value of [K.sub.X] (x) - [K.sub.X] (y)] [less than or equal to] dist(x, y). (2)

Using the finite dimensional version of the Kuratowski embedding, Gromov [24] (see also Katsuda [33]), proved a rigidity theorem, that, informally stated, asserts that if two n-dimensional (compact) Riemannian manifolds, having the same lower bound for their volumes, and upper bounds on diameters and sectional curvatures, are sufficiently close one to each other in the Gromov-Hausdorff (metric) topology, then they are diffeomorphic. (See, e.g. [22], [55] for a short overview of the Gromov-Hausdorff metric and its numerous geometric applications.) Since the types of manifolds that are usually encountered in Imaging, Vision, etc., naturally satisfy such bounds, it follows that the result above, as well as the finitely-dimensional Kuratowski embedding in general, are quite relevant for applications in the mentioned fields, in particular for recognition type problems.

Needless to say, in practice only finitely dimensional spaces are encountered, therefore the obvious question arises, whether it is actually possible to implement this approach. The answer appears to be positive, since, for the triangular (or, slightly more general, tetrahedral) meshes usually employed in graphics, etc., the number of distance functions is, essentially, finite: given a base point (usually a vertex of the mesh), the intrinsic distance from it to any other point on the mesh is a finite sum of PL affine combinations of the distances to a subset of the finite set of vertices. It follows, therefore, that this approach is, indeed, feasible in an actual computational setting. Moreover, the distances above can be, if needed, approximated by more commonly encountered types of functions, such as splines, wavelets, etc.

Remark 4.7 There are at least two other ways of embedding finitely dimensional manifolds into infinitely dimensional spaces, albeit perhaps less geometrical in spirit.

The first one is not usually connected in anybody's mind with embeddings, and certainly not into infinitely dimensional manifolds: It is nothing but the (atlas) of coordinate charts (for, say, a [C.sup.[infinity]] manifold). (Unfortunately, the author cannot recall a precise source for this approach.) Moreover, by standard arguments (see, e.g. [44]), to each x [member of] [M.sup.n] corresponds only a finite number of such functions. In this approach, the connection between the triangulation of [M.sup.n] and its embedding into the (infinitely dimensional) function space is quite transparent: To each point x [member of] [M.sup.n] corresponds one of the functions [phi],1,...,[phi]x,p, to each edge [??] = {[x.sub.t] | 0 [less than or equal to] t [less than or equal to] 1 ,x = [x.sub.0], y = [x.sub.1]} of a triangulation T of [M.sup.n] corresponds a path (edge)[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] etc. Obviously, this correspondence is far from being 1-to-1 and, while it would appear that in general many paths [??] correspond to a path [??], therefore triangulations of the finitely dimensional manifold are easily obtained from the one of its infinitely dimensional embedding, the sobering truth, is however, that, certain obstructions for the triangulation of topological manifolds exist in low dimension--see, for instance, [36], [8] (and Remark 3.2 above).

Remark 4.8 Note that, if [M.sup.n] is of class [C.sup.[infinity]], then the embedding above represents--in a natural manner, via the identification [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a submanifold of [R.sup.w] and, that, if in addition, the derivatives [[phi].sup.(k).sub.x] of the coordinate charts satisfy the relatively mild condition of being uniformly bounded, then, after a standard normalization of the said bound, of the Hilbert cube Q.

The second one, on the other hand, represents quite the opposite, as far as its familiarity to the Image and Signal Processing communities (and much wider ones): We refer to the embedding in standard Hilbert space [l.sub.2] via the (normalized) eigenfunctions of the Laplacian. Evidently, the relevant bibliography is truly far too vast to even contemplate a beginning of an exhaustion here; we therefore refer the reader solely to the brief comments in [6] and the references therein, as a starting point.

5 Concluding Remarks

In this paper we have showed that, indeed, the geometric sampling approach extends from the classical case of surfaces and higher dimensional Riemannian manifolds, almost without modifications, to a substantial class of infinite dimensional manifolds. Moreover, we have shown that the finitely dimensional sampling and triangulation results also extend, albeit only in a topological sense, to more general infinite dimensional manifolds, most notably to Hilbert cube manifolds. We went, however, beyond this technical fact and found a natural--in the context, say, of video processing--of the Triangulation Theorem for Hilbert cube manifolds, and also proposed a practical notion of fat triangulation for this type of manifolds. In addition, we introduced a simple, course type of geometry on P(X). Since the context of infinite dimensional manifolds less familiar, perhaps, to the imaging community, and since it is, regrettably, quite counterintuitive, we have shown how to properly emulate it by a finite dimensional approximation, via the "discrete" Kuratowski embedding. We believe that this represents the most promising direction of further study, both from the the theoretical as well as the practical viewpoints. It is, however, the most challenging, as well. For instance, it would be important to adapt the Kuratowski embedding so that the resulting triangulation would be inherently fat.


Research supported by the Israel Science Foundation Grant 666/06 and by European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement n[degrees] [203134]. The author wishes to thank Yehoshua Y. Zeevi for the introducing him to Sampling Theory and for his stimulating questions, and also to Eli Appleboim for many discussion on geometric sampling and related subjects. Thanks are also due to Mikhail Katz for reminding the author of the Kuratowski embedding. Moreover, the author would like to express special thanks for the anonymous reviewer, for his attentive remarks, suggestions and corrections.


[1] N. Ahmad, The Geometry of Shape Recognition Via the Monge-Kantorovich Optimal Transport Problem, PhD Thesis, Toronto University, 2004.

[2] S. Amari and H. Nagaoka, Methods of Information Geometry, Translations of Mathematical Monographs, AMS, Oxford University Press, Providence, R.I., 2000.

[3] N. Amenta and M. Bern, Surface reconstruction by Voronoi filtering, Discrete and Computational Geometry, 22, 481-504, 1999.

[4] S. Angenent, E. Pichon, and A. Tannenbaum, Mathematical methods in medical image processing, Bull. Amer. Math. Soc., 43(3), 365-396, 2006.

[5] E. Appleboim, E. Saucan, and Y.Y. Zeevi, Geometric sampling for signals with applications to images, Proceedings of Samp TA 07--Sampling Theory and Applications, 1-6, 2008.

[6] P. Berard, G. Besson and S. Gallot, Embedding manifolds by their heat kernel, Geom. Funet. Anal., 4(4), 373-398, 1994.

[7] A.M. Bronstein, M.M. Bronstein and R. Kimmel, On isometric embedding of facial surfaces into $3, Proc. Intl. Conf. on Scale Space and PDE Methods in Computer Vision, 622-631, 2005.

[8] J.L. Bryant, Piecewise Linear Topology, In: R. Daverman and R. Sher, editors, Handbook of Geometric Topology, North Holland, Amsterdam, 219-259, 2001.

[9] S.S. Cairns, A simple triangulation method for smooth manifolds, Bull. Amer. Math. Soc., 67, 380-390, 1961.

[10] T.A. Chapman, Dense sigma-compact subsets of infinite-dimensional manifolds, Trans. Amer. Math. Soc., 154, 399-426, 1971.

[11] T.A. Chapman, Lectures on Hilbert cube manifolds, AMS, Providence, Rhode Island, 1976.

[12] J. Cheeger, W. Muller and R. Schrader, On the curvature of piecewise flat spaces, Comm. Math. Phys., 92, 405-454, 1984.

[13] S.W. Cheng, T.K. Dey, T. and E.A. Ramos, Manifold reconstruction from point samples, Proc. A CM-SIAM Sympos. Discrete Algorithms, 1018-1027, 2005.

[14] A. Chigogidze, Infinite Dimensional Topology and Shape Theory, In: R. Daverman and R. Sher, editors, Handbook of Geometric Topology, North Holland, Amsterdam, 219-259, 2001.

[15] Y. Colin de Verdi6re and A. Marin, Triangulations presque 6quilat6rales des surfaces, Y. Differential Geometry, 32, 199-207, 1990.

[16] T. Dobrowski and K. Sakai, Spaces of measures on metrizable spaces, Toppology AppIic., 72, 215-258, 1996.

[17] A. Dominitz and A. Tannenbaum, Texture mapping via optimal mass transport, IEEE Transactions on Visualization and Computer Graphics, 16,419433, 2010.

[18] R. Dyer, H. Zhang and T. Moller, Surface sampling and the intrinsic Voronoi diagram, Computer Graphics Forum, 27(4), (Special issue on Eurographics Symposium on Geometry Processing 2008), 1393-1402, 2008.

[19] H. Edelsbrunner, Geometry and Topology for Mesh Generation, Cambridge University Press, Cambridge, 2001.

[20] V.V. Fedorchuk, Covariant functors in the category of compacta, absolute retracts, and @manifolds, Russian Math. Surveys, 36(3), 211-233, 1981.

[21] D.S. Fry, Shape recognition using metrics on the space of shapes, PhD thesis, Harvard University, 1993.

[22] K. Fukaya, Metric Riemannian Geometry, In: F.J.E. Dillen and L.C.A. Verstraelen, editors, Handbook of differential geometry, Vol. II, 189-313, Elsevier/North-Holland, Amsterdam, 2006.

[23] R.C. Gonzale and, R.E. Woods, Digital Image Processing (3d ed.), Prentice Hall, Upper Saddle River, N J, 2008.

[24] M. Gromov, Structures metriques pour les varietes riemanniennes, J. Lafontaine and P. Pansu, editors, Textes Math@matiques 1, CEDIC, Paris, 1981.

[25] M. Gromov, Metric Structures for Riemannian and Non-Riemannian Spaces, Birkhauser, Second printing, 2001.

[26] L. Guth, Notes on Gromov?s systolic estimate, Geom. Dedicata, 123, 113-129, 2006.

[27] P. Hallinan, A low-dimensional representation of human faces for arbitrary lighting conditions, Proc. CVPR, 995-999, 1994.

[28] D.W. Henderson, Infinite-dimensional manifolds are open subsets of Hilbert space, Bull. Amer. Math. Soc., 75, 759-762, 1969.

[29] D.W. Henderson and R.M. Schori, Topological classification of infinite-dimensional manifolds by homotopy type, Bull. Amer. Math. Soc., 76, 121-124, 1970.

[30] J.F. Hudson, Piecewise Linear Topology, Math. Lect. Notes Series, Benjamin, N.Y., 1969.

[31] A.K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, Englewood Clifs, N J, 1989.

[32] A. Kasue and H. Kumura, Spectral convergence of Riemannian manifolds, T6hoku Math. J., 46, 147-179, 1994.

[33] A. Katsuda, Gromov's convergence of theorem and its applications, Nagoya Math. Y., 100, 11-48, 1985.

[34] K.U. Katz and M.G. Katz, Bi-Lipschitz approximation by finite-dimensional imbeddings, Geom. Dedicata, Online First (DOI 10.1007/s10711-010-9497-4), 2010.

[35] R. Kimmel, R. Malladi and N. Sochen, Images as embedded maps and minimal surfaces: Movies, color, texture, and volumetric medical images, International Journal of Computer Vision, 39(2), 111-129, 2000.

[36] R. Kirby and L. Siebenmann, On the triangulation of manifolds and the Hauptvermutung, Bull. Amer. Math. Soc., 75, 742-749, 1969.

[37] C. Kuratowski, Quelques problemes concernant les espaces metriques nonseparables, Fund. Math., 25, 534-545, 1935.

[38] G. Leibon and D. Letscher, Delaunay triangulations and Voronoi diagrams for Riemannian manifolds, Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 341-349, 2000.

[39] J. Lott and C. Villani, Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math., 169(3), 903-991, 2009.

[40] H.P. McKean, Curvature of an m-dimensional manifold related to Hill's equation, J. Diff. Geom., 17, 523-529, 1982.

[41] F. Memoli and G. Sapiro, A theoretical and computational framework for isometry invariant recognition of point cloud data, Found. Comput. Math., 5(2), 313-347, 2005.

[42] P.W. Michor, and D. Mumford, Riemannian geometries on spaces of plane curves, J. Eur. Math. Soc. (JEMS), 8, 1-48, 2006.

[43] J.R. Munkres, Elementary Differential Topology, (rev. ed.), Princeton University Press, Princeton, N J, 1966.

[44] J.R. Munkres, Topology: A First Course, Prentice Hall Inc., Englewood Cliffs, N J, 1980.

[45] J. Nash, The embedding problem for Riemannian manifolds, Ann. of Math. (2), 63, 20-63, 1956.

[46] F. Otto, The geometry of dissipative evolution equations: the porous medium equation, Comm. Partial Differential Equations, 26,101-174, 2001.

[47] J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley-Interscience, New York, NY, 1995.

[48] K. Peltonen, On the existence of quasiregular mappings, Ann. Acad. Sci. Fenn., Series I Math., Dissertationes, 1992.

[49] C. Plaut, Spaces of Wald-Berestowsku curvature bounded below, The Journal of Geometric Analysis, 6(1), 113-134, 1996.

[50] Y. Rubner, C. Tomasi, and L.J. Guibas, The earth mover's distance as a metric for image retrieval, International Journal of Computer Vision, 40(2), 99-121, 2000.

[51] E. Saucan, Note on a theorem of Munkres, Mediterr. j. math., 2(2), 215-229, 2005.

[52] E. Saucan, Intrinsic differential geometry and the existence of quasimeromorphic mappings, Revue Roumaine de Math. Pures et Appl., 54(5-6), 565-574, 2009.

[53] E. Saucan, Curvature based triangulation of metric measure spaces, to appear in AMS Contemporary Mathematics, arXiv:1002.0007vl [math.DG], 2010.

[54] E. Saucan, Isometric Embeddings in Imaging and Vision: Facts and Fiction, to appear in J. Math. Imaging Vis., ("Online First", DOI 10.1007/s10851011-0296-9).

[55] E. Saucan and E. Appleboim, Metric Methods in Surface Triangulation, Lecture Notes in Computer Science, 5654, 335-355, 2009.

[56] E. Saucan, E. Appleboim, D.A. Lorenz and Y.Y. Zeevi, On the classical--and not so classical--Shannon Sampling Theorem, Technion CCIT Report #680, 2008.

[57] E. Saucan, E. Appleboim and Y.Y. Zeevi, Image Projection and Representation on Sn, Y Fourier Anal Appl 13(6), 711-727, 2007.

[58] E. Saucan, E. Appleboim and Y.Y. Zeevi, Geometric Sampling of Manifolds for Image Representation and Processing, Lecture Notes in Computer Science, 4485, 907-918, 2007.

[59] E. Saucan, E. Appleboim and Y.Y. Zeevi, Sampling and Reconstruction of Surfaces and Higher Dimensional Manifolds, Journal of Mathematical Imaging and Vision, 30(1), 105-123, 2008.

[60] E. Saucan, E. Appleboim and Y.Y. Zeevi, Geometric Approach to Sampling and Communication, preprint, arXiv:1002.2959vl, 2010.

[61] E. Saucan and M. Katchalski, The existence of thick triangulations--an "elementary" proof, The Open Mathematics Journal, 2, 8-11, 2009.

[62] H.S. Seung and D.D. Lee, The manifold ways of perception, Science, 290, 2323-2326, 2000.

[63] L. Siebenmann, L'invariance topologique du type simple d'homotopie, Seminaire Bourbaki, 25e anee, 1972/73, n[degrees] 428, 186-209, 1973.

[64] N. Sochen and Y.Y. Zeevi, Representation of colored images by manifolds embedded in higher dimensional non-Euclidean space, ICIP98, 166-170, 1998.

[65] K.-T. Sturm, On the geometry of metric measure spaces I, Acta Math., 196, 65-131, 2006.

[66] C. Villani, Optimal Transport, Old and News Grundlehren der mathematischen Wissenschaften, 338, Springer, Berlin-Heidelberg, 2009.

Emil Saucan

Department of Mathematics, Technion, Technion City

Haifa, 32000, Israel
COPYRIGHT 2011 Sampling Publishing
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Saucan, Emil
Publication:Sampling Theory in Signal and Image Processing
Article Type:Report
Geographic Code:7ISRA
Date:Jan 1, 2011
Previous Article:Multichannel sampling of multidimensional parametric signals.
Next Article:A linear singularity analysis by the continuous shearlet transform.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters