# Affine-invariant geodesic geometry of deformable 3D shapes

Af?ne-invariant geodesic geometry of deformable 3D shapes

Dan Raviv1 , Alexander M. Bronstein2 , Michael M. Bronstein3 , Ron Kimmel1 and Nir Sochen4

1 2 3 4

Dept. of Computer Science, Technion, Israel, {darav,ron}@cs.technion.ac.il Dept. of Electrical Engineering, Tel Aviv University, Israel, bron@eng.tau.ac.il Institute of Computational Science, Faculty of Informatics, Universit` a della Svizzera Italiana, Lugano, michael.bronstein@usi.ch Dept. of Applied Mathematics, Tel Aviv University, Israel, sochen@math.tau.ac.il

Abstract Natural objects can be subject to various transformations yet still preserve properties that we refer to as invariants. Here, we use de?nitions of af?ne invariant arclength for surfaces in R3 in order to extend the set of existing non-rigid shape analysis tools. We show that by re-de?ning the surface metric as its equi-af?ne version, the surface with its modi?ed metric tensor can be treated as a canonical Euclidean object on which most classical Euclidean processing and analysis tools can be applied. The new de?nition of a metric is used to extend the fast marching method technique for computing geodesic distances on surfaces, where now, the distances are de?ned with respect to an af?ne invariant arclength. Applications of the proposed framework demonstrate its invariance, ef?ciency, and accuracy in shape analysis.

1. Introduction Modeling 3D shapes as Riemannian manifold is a ubiquitous approach in many shape analysis applications. In particular, in the recent decade, shape descriptors based on geodesic distances induced by a Riemannian metric have become popular. Notable examples of such methods are the canonical forms [7] and the Gromov-Hausdorff [9, 14, 2] and the GromovWasserstein [13, 6] frameworks, used in shape comparison and correspondence problems. Such methods consider shapes as metric spaces endowed with a geodesic distance metric, and pose the problem of shape similarity as ?nding the minimum-distortion correspondence between the metrics. The advantage of the geodesic distances is their invariance to inelastic deformations (bendings) that preserve the Riemannian metric, which makes them especially appealing for non-rigid shape analysis. A particular setting of ?nding shape selfsimilarity can be used for intrinsic symmetry detection in non-rigid shapes [17, 25, 12, 24]. The ?exibility in the de?nition of the Riemannian

Preprint submitted to SMI 2011

metric allows extending the invariance of the aforementioned shape analysis algorithms by constructing a geodesic metric that is also invariant to global transformations of the embedding space. A particularly general and important class of such transformations are the af?ne transformations. Such transformations are a common local model for perspective distortions in images [15], and af?ne invariance is a necessary property of image descriptors. In 3D shape analysis, global af?ne transformations play an important role in paleontological research studying bones of prehistoric creatures that may be squeezed by earth pressure [8]. Furthermore, photometric properties of 3D shapes and images can be treated as embedding coordinates in high-dimensional spaces that include both geometric and color coordinates [20, 11]. Photometric transformations can be thus represented as geometric transformations of the respective coordinates ,for example, af?ne transformations in the Lab color space correspond to brightness, contrast, hue, and saturation transformations. Af?ne-invariant metrics are thus useful for a description of the object that is invariant to color transformations.

March 13, 2011

Many frameworks have been suggested to cope with the action of the af?ne group in a global manner, trying to undo the af?ne transformation in large parts of a shape or a picture. While the theory of af?ne invariance is known for many years [4] and used for curves [18] and ?ows [19], no numerical constructions applicable to general two-dimensional manifolds have been proposed. In this paper, we construct an (equi-)af?ne-invariant Riemannian geometry for 3D shapes. So far, such metrics have been de?ned for convex surfaces; we extend the construction to surfaces with non-vanishing Gaussian curvature. By de?ning an af?ne-invariant Riemannian metric, we can in turn de?ne af?ne-invariant geodesics, which result in a metric space with a stronger class of invariance. This new metric allows us to develop ef?cient computational tools that handle non-rigid deformations as well as equi-af?ne transformations. We demonstrate the usefulness of our construction in a range of shape analysis applications, such as shape processing, construction of shape descriptors, correspondence, and symmetry detection.

2.1. Geodesics Minimal geodesics are the minimizers of (C ), giving rise to the geodesic distances dX ( x, x ) = min

C ∈Γ( x, x )

(C )

(4)

where Γ( x, x ) is the set of all admissible paths between the points x and x on the surface X , where due to completeness assumption, the minimizer always exists. Structures expressible solely in terms of the metric tensor g are called intrinsic. For example, the geodesic can be expressed in this way. The importance of intrinsic structures stems from the fact that they are invariant under isometric transformations (bendings) of the shape. In an isometrically bent shape, the geodesic distances are preserved – a property allowing to use such structures as invariant shape descriptors [7]. 2.2. Fast marching The geodesic distance dX ( x0 , x) can be obtained as the viscosity solution to the eikonal equation ?d 2 = 1 (i.e., the largest d satisfying ?d 2 ≤ 1) with boundary condition at the source point d( x0 ) = 0. In the discrete setting, a family of algorithms for ?nding the viscosity solution of the discretized eikonal equation by simulated wavefront propagation is called fast marching methods [10]. On a discrete shape represented as a triangular mesh with N vertices, the general structure of fast marching closely resembles that of the classical Dijkstra’s algorithm for shortest path computation in graphs, with the main difference in the update step. Unlike the graph case where shortest paths are restricted to pass through the graph edges, the continuous approximation allows paths passing anywhere in the mesh triangles. For that reason, the value of d( x0 , x) has to be computed from the values of the distance map at two other vertices forming a triangle with x. Computation of the distance map from a single source point has the complexity of O(N log N ) [23]. On parametric surfaces, the fast marching can be carried out by means of a raster scan and ef?ciently parallelized, which makes it especially attractive for GPU-based computation [21, 3]. 3. Af?ne-invariant geometry An af?ne transformation x → Ax + b of the threedimensional Euclidean space can be parametrized using twelve parameters: nine for the linear transformation A, and additional three, b, for a translation, which we will omit in the following discussion (here, we assume vectors to be column). Volume-preserving transformations, known as special or equi-af?ne are restricted by 2

2. Background We model a shape (X, g) as a compact complete twodimensional Riemannian manifold (surface) X with a metric tensor g. The metric g can be identi?ed with an inner product ·, · x : T x X × T x X → R on the tangent plane T x X at point x. We further assume that X is embedded into R3 by means of a regular map x : U ? R2 → R3 , so that the metric tensor can be expressed in coordinates as gi j = ?xT ?x , ?ui ?u j (1)

where ui are the coordinates of U . The metric tensor relates in?nitesimal displacements in the parametrization domain U to displacement on the manifold d p2 = g11 du1 2 + 2g12 du1 du2 + g22 du2 2 . (2)

This, in turn, provides a way to measure length structures on the manifold. Given a curve C : [0, T ] → X , its length can be expressed as (C ) =

0 T

˙ (t), C ˙ (t ) C

1/ 2 C (t) dt,

(3)

˙ denotes the velocity vector. where C

det A = 1. Such transformations involve only eleven parameters. In the following, when referring to af?ne transformations and af?ne invariance, we will imply volume-preserving (equi-)af?ne transformations. An equi-af?ne metric can be de?ned through the parametrization of a curve on the surface. Let C be the coordinates of a curve on the surface X parametrized by p. By the chain rule, Cp C pp = = du2 du1 + x2 x1 dp dp x1 d u1 d u2 du1 + x2 2 + x11 dp d p2 dp

2 2 2 2

that g ? 11 du ?2 g12 du ? 1 du ?2 + g ? 22 du ?2 1 + 2? 2 = and

4 g ? 11 g ? 22 ? g ?2 ? 11 g ? 22 ? g ?2 12 = g 12 det ( J ),

g ? 11 du2 + 2? g12 dudv + g ? 22 dv2 det( J ),

(11)

(12)

? 2, x ? i j ). From (11) and (12) we conwhere g ? i j = det(? x1 , x clude that g ? 11 du ?2 g12 du ? 1 du ?2 + g ? 22 du ?2 1 + 2? 2

1 4

+ (5)

?2 x ?ui ?u j ,

g ? 11 g ? 22 ? g ?2 12 =

du2 du1 du2 + x22 2x12 dp dp dp where, for brevity, we denote xi =

dC dp ,

2

,

g ? 11 du2 + 2? g12 dudv + g ? 22 dv2 g ? 11 g ? 22 ? g ?2 12

1 4

,

(13)

?x ?ui ,

xi j =

Cp =

and derive the af?ne invariant parameter normalization f ( X ) = |g ? |?1/4 , g ? i j |g ? |?1/4 . (14)

C and C pp = d . As volumes are preserved under d p2 the equi-af?ne group of transformations, we de?ne the invariant arclength p through

which de?nes the equi-af?ne pre-metric tensor [4, 19] g ?i j = (15)

f (X ) det(x1 , x2 , C pp ) =

1,

(6)

where f (X ) is a normalization factor for parameterization invariance (i.e., invariance with respect to the choice of p), and the determinant is applied on a matrix formed by the column vectors x1 , x2 , and C pp . Since xi i is parallel to xi du d p it follows that det(x1 , x2 , αx1 + βx2 ) = 0 ?α , β, (7)

and plugging (5) into (6) using (7) yields the equi-af?ne arclength d p2 = = f (X ) det(x1 , x2 , x11 du2 1+ 2x12 du1 du2 + x22 du2 2) f (X ) g ? 11 du2 g12 du1 u2 + g ? 22 du2 1 + 2? 2 , (8) where g ? i j = det(x1 , x2 , xi j ). In order to evaluate f (X ) such that the quadratic form (8) will also be parameterization invariant, we introduce ?i = an arbitrary parameterization u ? 1 and u ? 2 , for which x ?2 x ?x ? ?u ? i and xi j = ?u ? i ?u ? j . The relation between the two sets of parameterizations can be expressed using the chain rule ?1 x ?2 x = = xu ? 1 = xu1 u1 u ? 1 + xu2 u2 u ?1 xu ? 2 = x u1 u 1 u ? 2 + xu2 u2 u ?2 . (9)

The pre-metric tensor (15) applies only for strictly convex surfaces [4]; a similar dif?culty appeared in equi-af?ne curve evolution. There the arc-length was determined by the absolute value of the geometric structure [18]. In two dimensions the problem is more acute as we can encounter non-positive de?nite metrics in concave, and hyperbolic regions. We propose ?xing the metric by ?ipping the main axes of the operator, if needed. In practice, we restrict the eigenvalues of the tensor to be positive. From the ? = UΓUT of eigendecomposition in matrix notation, G g ? where U is orthogonal and Γ = diag{γ1 , γ2 }, we compose a new metric G, such that G = U|Γ|UT (16)

is positive de?nite and equi-af?ne invariant, for surfaces with non-vanishing Gaussian curvature. 4. Discretization We model the surface X as a triangular mesh, and construct three coordinate functions x(u, v), y(u, v), and z(u, v) for each triangle. While this can be done practically in any representation, we use the fact that a triangle and its three adjacent neighbors, can be unfolded to the plane, and produce a parameter domain. The coordinates of this planar representation are used as the parametrization with respect to which the ?rst fundamental form coef?cients are computed at the barycenter 3

It can be shown [1, 4] using the Jacobian J= u1 u ?1 u1 u ?2 u2 u ?1 , u2 u ?2 (10)

Standard

Equi-af?ne

Standard

Equi-af?ne

Figure 3: Distance maps from different source points calculated using the standard (second to fourth columns) and the proposed equi-af?ne geodesic metric (?fth to seventh columns) on a reference surface (?rst and third rows) and its af?ne (second row) and isometric deformation+af?ne transformation (fourth row). Thirds and sixth rows show the global histogram of geodesic distances before and after the transformation (green and blue curves). The overlap between the histograms is an evidence of invariance.

of the simplex (Figure 1). Using the six base functions 1, u, v, uv, u2 , and v2 we can construct a second-order polynomial for each coordinate function. This step is performed for every triangle of the mesh (Algorithm 1). Once the coef?cients D are known, evaluating the equi-af?ne metric, as seen in Figure 1, becomes straight forward using: ? ? D21 + D41 v + 2D51 u ? ? ? ? ? D + D42 v + 2D52 u ? ? ? 22 D23 + D43 v + 2D53 u ? ? ? ? ? ? ? ; ? ? ? 4

xv xuu xuu xuv

= = = =

? ? D31 + D41 v + 2D61 u ? ? ? ? ? D + D42 v + 2D62 u ? ? ? 32 D33 + D43 v + 2D63 u 2D51 2D5,2 2D53

T T

? ? ? ? ? ? ? ; ? ? ?

;

2D61 2D6,2 2D63 ; xvu = [D41 D42 D43 ]T .

xu

=

Calculating geodesic distances was well studied in past decades. Several fast and accurate numerical

Figure 1: The three neighboring triangles together with the central one are unfolded ?at to the plane. The central triangle is canonized into a right isosceles triangle while the rest of its three neighboring triangles follow the same planar af?ne transformation. Finally, the six surface coordinate values at the vertices are used to interpolate a quadratic surface patch from which the metric tensor is computed.

The (af?ne invariant) length of each edge is de?ned by L2 (dx, dy) = g11 dx2 +2g12 dxdy+g22 dy2 . Speci?cally, for our canonical triangle with vertices at (0, 0), (1, 0) 2 2 2 and (0, 1) we have L1 = g11 , L2 = g22 and L3 = g11 ? 2g12 + g22 . Each edge may appear in more than one triangle. In our experiments we use the average length as an approximation, while verifying that the triangle inequality holds. In Figures 2 and 3 we compare between geodesic distances induced by the standard and our af?ne-invariant metric. 5. Results The equi-af?ne metric can be used in many existing methods that process geodesic distances. In what follows, we show several examples for embedding the new metric in known applications such as voronoi tessellation, canonical forms, non-rigid matching and symmetry detection. 5.1. Voronoi tessellation

Figure 2: Geodesic level sets of the distance function computed from the tip of the tail, using the standard (left) and the proposed equi-af?ne (right) geodesic metrics.

Algorithm 1: Equi-af?ne-invariant metric discretization. Input: 3 × 6 matrix P of triangle vertex coordinates in R3 (each column Pi represents the coordinates of a vertex, the ?rst three columns belonging to the central triangle). Output: 6 × 3 matrix of coef?cients D 1 Flatten the triangles to a plane, such that each vertex Pi becomes Qi ∈ R2 , and (i) the ?rst vertex becomes the origin, C1 = [0 0]T ; (ii) edge lengths are preserved, d(Ci , C j ) = d(Pi , P j ) for all i and j; and (iii) the orientation is unchanged, T sign CT i C j = sign Pi P j . ? i = MCi , where 2 Construct a new parameterization C

3

Voronoi tessellation is a partitioning of (X, g) into disjoint open sets called Voronoi cells. A set of k points ( xi ∈ X )k i=1 on the surface de?nes the Voronoi such that the i-th cell contains all points on cells (Vi )k i=1 X closer to xi than to any other x j in the sense of the metric g. Voronoi tessellations created with the equiaf?ne metric commute with equi-af?ne transformations as visualized in Figure 4 5.2. Canonical forms Methods considering shapes as metric spaces with some intrinsic (e.g. geodesic) distance metric is an important class of approaches in shape analysis. Geodesic distances are particularly appealing due to their invariance to inelastic deformations that preserve the Riemannian metric. Elad and Kimmel [7] proposed a shape recognition algorithm based on embedding the metric structure of a shape (X, dX ) into a low-dimensional Euclidean spaces. Such a representation, referred to as canonical form, allows undoing the degrees of freedom due to all possible isometric non-rigid shape deformations and translating them into a much simple Euclidean isometry group. For example, the Hausdorff distance can be used to compare two canonical forms. Given a shape sampled at N points and an N × N matrix of pairwise geodesic distances, the computation of the canonical form consists of ?nding a con?guration of N points z1 , . . . , zN in Rm such that zi ? z j 2 ≈ dX ( xi , x j ). This problem is known as multidimensional 5

M = [C2 C3 ]?1 . Calculate the coef?cients D = N?1 PT of each ? i1 , v = C ? i2 , and coordinate polynomial, where u = C N is a 6 × 6 matrix with each row de?ned as Ni = [1 u v uv u2 v2 ].

schemes [10, 22, 26] can be used off-the-shelf for this purpose. We use FMM technique, after locally rescaling each edge according to the equi-af?ne metric.

Figure 4: Voronoi cells generated by a ?xed set of 20 points on a shape undergoing an equi-af?ne transformation. The standard geodesic metric (left) and its equi-af?ne counterpart (right) were used. Note that in the latter case the tessellation commutes with the transformation.

scaling (MDS) and can be posed as a non-convex leastsquares optimization problem of the form {z1 , . . . , zN } = argmin

z1 ,...,zN i> j

The smallest achievable value of the distortion is called the Gromov-Hausdorff distance [5] between the metric spaces (X, dX ) and (Y, dY ), dGH (X, Y ) = 1 inf dis(C), 2 C (19)

| zi ? z j

2

? dX ( xi , x j )|2 .

(17)

The invariance of the canonical form to shape transformations depends on the choice of the distance metric dX . Figure 5 shows an example of a canonical form of the human shape undergoing different bendings and af?ne transformations of varying strength. The canonical form was computed using the geodesic and the proposed equi-af?ne distance metric. One can clearly see the nearly perfect invariance of the latter. Such a strong invariance allows to compute correspondence of full shapes under a combination of inelastic bendings and af?ne transformations. 5.3. Non rigid matching Two non-rigid shapes X, Y can be considered similar if there exists an isometric correspondence C ? X × Y between them, such that ? x ∈ X there exists y ∈ Y with ( x, y) ∈ C and vice-versa, and dX ( x, x ) = dY (y, y ) for all ( x, y), ( x , y ) ∈ C, where dX , dY are geodesic distance metrics on X, Y . In practice, no shapes are truly isometric, and such a correspondence rarely exists; however, one can attempt ?nding a correspondence minimizing the metric distortion, dis(C) = max |dX ( x, x ) ? dY (y, y )|.

( x,y)∈C ( x ,y )∈C

and can be used as a criterion of shape similarity. The choice of the distance metrics dX , dY de?nes the invariance class of this similarity criterion. Using geodesic distances, the similarity is invariant to inelastic deformations. Here, we use geodesic distances induced by our equi-af?ne Riemannian metric tensor, which gives additional invariance to af?ne transformations of the shape. Bronstein et al. [2] showed how (19) can be ef?ciently approximated using a convex optimization algorithm in the spirit of multidimensional scaling (MDS), referred to as generalized MDS (GMDS). Since the input of this numeric framework are geodesic distances between mesh points, all that is needed to obtain an equi-af?ne GMDS is one additional step where we substitute the geodesic distances with their equi-af?ne equivalents. Figure 6 shows the correspondences obtained between an equi-af?ne transformation of a shape using the standard and the equi-af?ne-invariant versions of the geodesic metric. 5.4. Intrinsic symmetry Raviv et al. [17] introduced the notion of intrinsic symmetries for non-rigid shapes as self-isometries 6

(18)

Figure 5: Embedding into R3 of a human shape and its equi-af?ne transformations of varying strength. Classical scaling was used with a matrix of geodesic (left) and equi-af?ne geodesic (right) distances. In the latter case, canonical forms remain approximately invariant up to a rigid transformation.

of a shape with respect to a deformation-invariant (e.g. geodesic) distance metric. These self-isometries can be detected by trying to identify local minimizers of the metric distortion or other methods proposed in followup publications [16, 25, 12, 24]. Here, we adopt the framework of [17] for equi-af?ne intrinsic symmetry detection. Such symmetries play an important role in paleontological applications [8]. Equiaf?ne intrinsic symmetries are detected as local minima of the distortion, where the equi-af?ne geodesic distance metric is used. Figure 7 shows that using the traditional metric we face a decrease in accuracy of symmetry detection as the af?ne transformation becomes stronger (the accuracy is de?ned as the average geodesic distance between the detected and the groundtruth symmetry). Such a decrease does not occur using the equi-af?ne metric. 6. Conclusions

Figure 6: The GMDS framework is used to calculate correspondences between a shape and its isometry (left) and isometry followed by an equi-af?ne transformation (right). Matches between shapes are depicted as identically colored Voronoi cells. Standard distance (?rst row) and its equi-af?ne-invariant counterpart (second row) are used as the metric structure in the GMDS algorithm. Inaccuracies obtained in the ?rst case are especially visible in the legs and arms.

We introduced a framework for the construction of (equi-) af?ne-invariant Riemannin metric and the associated geodesic geometric, and showed that it can be utilized to construct af?ne-invariant shape descriptors, ?nd non-rigid correspondence between shapes, and detect intrinsic symmetry. Handling af?ne transformations of the ambient space is important in some applications where the data acquisition process introduces 7

Figure 7: As the af?ne transformation becomes stronger, the quality of the symmetry detection decreases when the standard geodesic metric is used. On the other hand, detection quality is nearly unaffected by the transformations when using the equi-af?ne geodesic metric.

af?ne transformations (e.g. ultrasonic medical imaging) or where the object has undergone skew (e.g. dinosaur fossils). An important class of applications where af?ne invariance is of high importance is the geometric representation of photometric information in images and 3D shapes by means of high-dimensional embeddings. We plan to explore these applications in future works. Additional point to address is scale invariance which will make our construction fully af?ne-invariant. It is important to note that our construction addresses af?ne invariance locally though the construction of a Riemannian metric, which in theory would allow invariance to a more generic class of spatially-varying af?ne transformations. Such a situation is typical in image analysis, where af?ne transformations are a local model for more general view point transformations. 7. Acknowledgement This research was supported by European Community’s FP7- ERC program, grant agreement no. 267414. References

[1] Blaschke, W., 1923. Vorlesungen uber Differentialgeometric und geometrische Grundlagen von Einsteins Relativitatstheorie. Springer. [2] Bronstein, A., Bronstein, M., Kimmel, R., 2006. Ef?cient computation of isometry-invarient distances between surfaces. SIAM journal Scienti?c Computing 28/5, 1812–1836. [3] Bronstein, A. M., Bronstein, M. M., Devir, Y. S., Kimmel, R., Weber, O., 2008. Parallel algorithms for approximation of distance maps on parametric surfaces. TOG 27 (4). [4] Buchin, S., 1983. Af?ne differential geometry. Beijing, China: Science Press.

[5] Burago, D., Burago, Y., Ivanov, S., 2001. A course in metric geometry. Vol. 33 of Graduate studies in mathematics. American Mathematical Society. [6] Chazal, F., Cohen-Steiner, D., Guibas, L., M? emoli, F., Oudot, S., 2009. Gromov-hausdorff stable signatures for shapes using persistence. In: Proc. Symposium on Geometry Processing (SGP). pp. 1393–1403. [7] Elad, A., Kimmel, R., 2003. On bending invariant signatures for surfaces. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI) 25 (10), 1285–1295. [8] Ghosh, D., Amenta, N., Kazhdan, M., 2010. Closed-form blending of local symmetries. In: Proc. SGP. [9] Gromov, M., 1981. Structures M? etriques Pour les Vari? et? es Riemanniennes. No. 1 in Textes Math? ematiques. [10] Kimmel, R., Sethian, J. A., 1998. Computing geodesic paths on manifolds. Proc. National Academy of Sciences (PNAS) 95 (15), 8431–8435. [11] Kovnatsky, A., Bronstein, M. M., Bronstein, A. M., Kimmel, R., 2011. Diffusion framework for geometric and photometric data fusion in non-rigid shape analysis. Tech. Rep. arXiv:1101. [12] Lasowski, R., Tevs, A., Seidel, H., Wand, M., 2009. A Probabilistic Framework for Partial Intrinsic Symmetries in Geometric Data. In: Proc. International Conference on Computer Vision (ICCV). [13] M? emoli, F., 2009. Spectral gromov-wasserstein distances for shape matching. In: Proc. NORDIA. [14] M? emoli, F., Sapiro, G., 2005. A theoretical and computational framework for isometry invariant recognition of point cloud data. Foundations of Computational Mathematics 5, 313–346. [15] Mikolajczyk, K., Tuytelaars, T., Schmid, C., Zisserman, A., Matas, J., Schaffalitzky, F., Kadir, T., Gool, L. V., 2005. A comparison of af?ne region detectors. IJCV 65 (1–2), 43–72. [16] Ovsjanikov, M., Sun, J., Guibas, L., 2008. Global intrinsic symmetries of shapes. In: Proc. Eurographics Symposium on Geometry Processing (SGP). Vol. 27. [17] Raviv, D., Bronstein, A. M., Bronstein, M. M., Kimmel, R., Oct. 2007. Symmetries of non-rigid shapes. In: Proc. Non-rigid Registration and Tracking (NRTL) workshop. See Proc. of International Conference on Computer Vision (ICCV). [18] Sapiro, G., Tannenbaum, A., January 1994. On af?ne plane curve evolution. Journal of Functional Analysis (1), 79–120. [19] Sochen, N., 2004. Af?ne-invariant ?ows in the Beltrami framework. Journal of Mathematical Imaging and Vision 20 (1), 133– 146. [20] Sochen, N., Kimmel, R., Malladi, R., 1998. A general framework for low level vision. IEEE Trans. Image Processing 7 (3), 310–318. [21] Spira, A., Kimmel, R., 2004. An ef?cient solution to the eikonal equation on parametric manifolds. Interfaces and Free Boundaries 6 (3), 315–327. [22] Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S., Hoppe, H., 2005. Fast exact and approximate geodesics on meshes. In: Proc. SIGGRAPH. pp. 553–560. [23] Tsitsiklis, J. N., 1995. Ef?cient algorithms for globally optimal trajectories. IEEE Trans. Automatic Control 40 (9), 1528–1538. [24] Xu, K., Zhang, H., Tagliasacchi, A., Liu, L., Li, G., Meng, M., Xiong, Y., 2009. Partial intrinsic re?ectional symmetry of 3d shapes. In: Proc. SIGGRAPH Asia. [25] Yang, X., Adluru, N., Latecki, L., Bai, X., Pizlo, Z., 2008. Symmetry of Shapes Via Self-similarity. In: Proc. International Symposium on Advances in Visual Computing. pp. 561–570. [26] Yatziv, L., Bartesaghi, A., Sapiro, G., 2006. O(N) implementation of the fast marching algorithm. J. Computational Physics 212 (2), 393–399.

8