2.1.2.1 Differential Properties of Surfaces

Similar to the curve case, one can define various types of differential properties of a given surface. For instance, the two partial derivatives

(2.7)

define two tangent vectors to the surface at a point of coordinates . The plane spanned by these two orthogonal vectors is tangent to the surface. The surface unit normal vector at , denoted by , can be computed as:

(2.8)

Here, denotes the vector cross product.

First Fundamental Form

A tangent vector to the surface at a point can be defined in terms of the partial derivatives of as:

(2.9)

The two real‐valued scalars and can be seen as the coordinates of in the local coordinate system formed by and . Let and be two tangent vectors of coordinates and , respectively. Then, the inner product , where is the angle between the two vectors, is defined as:

(2.10)

where is a 2D matrix called the first fundamental form of the surface at a point of coordinates . Let us write

The first fundamental form, also called the metric or metric tensor, defines inner products on the tangent space to the surface. It allows to measure:

• Angles. The angle between the two tangent vectors and can be computed as:
  
• Length. Consider a curve on the parametric surface. The parametric representation of the curve is . The tangent vector to the curve at any point is given as:
  

  Since the curve is on the surface defined by the parametric function , then and are two orthogonal vectors that are tangent to the surface. Using Eq. (2.3), the length of the curve is given by

  
• Area. Similarly, we can measure the surface area of a certain region :
  

  where refers to the determinant of the square matrix .

Since the first fundamental form allows measuring angles, distances, and surface areas, it is a strong geometric tool for 3D shape analysis.

Second Fundamental Form and Shape Operator

The second fundamental form of a surface, defined by its parametric function , at a point is a matrix defined in terms of the second derivatives of as follows:

(2.11)

where

(2.12)

Here, refers to the standard inner product in , i.e. the Euclidean space. Similarly, the shape operator of the surface is defined at a point using the first and second fundamental forms as follows:

(2.13)

The shape operator is a linear operator. Along with the second fundamental form, they are used for computing surface curvatures.

2.1.2.2 Curvatures

Let be the unit normal vector to the surface at a point , and a tangent vector to the surface at . The intersection of the plane spanned by the two vectors and with the surface at forms a curve called the normal curve. This is illustrated in Figure 2.5. Rotating this plane, which is also called the normal plane, around the normal vector is equivalent to rotating the tangent vector around . This will result in a different normal curve. By analyzing the curvature of such curves, we can define the curvature of the surface.

1. Normal curvature. The normal curvature to the surface at a point in the direction of a tangent vector is defined as the curvature of the normal curve created by intersecting the surface at with the plane spanned by and . Let denote the representation of in the 2D local coordinate system spanned by the two orthogonal vectors and , i.e. . Then, the normal curvature at in the direction of can be computed using the first and second fundamental forms as follows:
   (2.14)
2. Principal curvatures. By rotating the tangent vector around the normal vector , we obtain an infinite number of normal curves at . Thus, varies with . It has, however, two extremal values called principal curvatures; one is the minimum curvature, denoted by , and the other is the maximum curvature, denoted by .

   The principal directions, and , are the tangent vectors to the normal curves, which have the minimum, respectively the maximum, curvature at . These principal directions are orthogonal and thus they form a local orthonormal basis. Consequently, any vector that is tangent to the surface at can be defined with respect to this basis. For simplicity of notation, let and let be the angle between and . The Euler theorem states that the normal curvature at in the direction of is given by

   (2.15)
3. Mean and Gaussian curvatures. The mean curvature is defined as the average of the two principal curvatures:
   (2.16)

   The Gaussian curvature, on the other hand, is defined as the product of the two principal curvatures:

   (2.17)

These two curvature measures are very important and they are extensively used in 3D shape analysis. For instance, the Gaussian curvature can be used to classify surface points into three distinct categories: elliptical points , hyperbolic points , and parabolic points . Figure 2.6 illustrates the relation between different curvatures at a given surface point and the shape of the local patch around that point. For example:

• When the minimum and maximum curvatures are equal and nonzero (i.e. both are either strictly positive or strictly negative) at a given point then the patch around that point is locally spherical.
• When both minimum and maximum curvatures are zero, then the shape is planar.
• When the minimum curvature is zero and the maximum curvature is strictly positive then the shape of the local patch is parabolic. If every point on the surface of a 3D object satisfies this condition and if the maximum curvature is constant everywhere then the 3D object is a cylinder.
• If both curvatures are strictly positive then the shape is elliptical.
• If the minimum curvature is negative while the maximum curvature is positive then the shape is hyperbolic.

Finally, the curvatures can be also defined using the shape operator. For instance, the normal curvature of the surface at a point in the direction of a tangent vector is defined as

(2.18)

The eigenvalues of are the principal curvatures at . Its determinant is the Gaussian curvature and its trace is twice the mean curvature at .

2.1.2.3 Laplace and Laplace–Beltrami Operators

Let be a function in the Euclidean space. The Laplacian of is defined as the divergence of the gradient, i.e.;

(2.19)

The Laplace–Beltrami operator is the extension of the Laplace operator to functions defined on manifolds:

(2.20)

where is a function on the manifold . If is a parametric representation of a surface, as defined in Eq. (2.6), then

(2.21)

Here, and denote, respectively, the Gaussian curvature and the normal vector at a point .

2.1.4.1 Representations of Discrete Surfaces

Often, complex surfaces cannot be represented with a single parametric function. In that case, one can use a piecewise representation. For instance, one can partition a complex surface into smaller subregions, called patches, and approximate each patch with one parametric function. The main mathematical challenge here is to ensure continuity between adjacent patches. The most common piecewise representations are spline surfaces, polygonal meshes, and point sets. The spline representation is the standard representation in modern computer aided design (CAD) models. It is used to construct high‐quality surfaces and for surface deformation tasks. In this chapter, we will focus on the second and third representations since they are the most commonly used representations for 3D shape analysis. We, however, refer the reader to other textbooks, such as 1, for a detailed description of spline representations.

(1) Polygonal meshes. In a polygonal representation, a 3D model is defined as a collection, or union, of planar polygons. Each planar polygon, which approximates a surface patch, is represented with a set of vertices and a set of edges connecting these vertices. In principle, these polygons can be of arbitrary type. In fact, they are not even required to be planar. In practice, however, triangles are the most commonly used since they are guaranteed to be piecewise linear. In other words, triangles are the only polygons that are always guaranteed to be planar. A surface approximated with a set of triangles is referred to as a triangular mesh. It consists of a set of vertices

and a set of triangular faces

connecting them, see Figure 2.7a. This representation can be also interpreted as a graph whose nodes are the vertices of the mesh. Its edges are the edges of the triangular faces. In this graph representation, each triangular face defines, using the barycentric coordinates, a linear parameterization of its interior points. That is, every point in the interior of a triangle can be written as where , and and .

Obviously, the accuracy of the representation depends on the number of vertices (and subsequently the number of faces) that are used to approximate the surface. For instance, a nearly planar surface can be accurately represented using only a few vertices and faces. Surfaces with complex geometry, however, require a large number of faces especially at regions of high curvature.

A singular, or nonmanifold, vertex is a vertex that is attached to two fans of triangles as shown in Figure 2.8a,b. A singular, or nonmanifold, edge is an edge that is attached to more than two faces, see Figure 2.8c. Manifold surfaces are often referred to as watertight models.

Manifoldness is an important property of triangular meshes. In particular, a manifold surface can always be locally parameterized at each point using a function , where is a planar domain, e.g. a disk or a square. As such, differential properties (see Section 2.1.2) can efficiently be computed using some analytical approximations.

When the mesh is nonmanifold, it is often referred to as a polygon soup model. Polygon soup models are easier to create since one does not have to worry about the connectivity of the vertices and edges. They are, however, problematic for some shape analysis algorithms since the differential properties of such surfaces cannot be computed analytically. There are, however, efficient numerical methods to compute such differential properties. This will be detailed in Section 2.1.4.3.

(2) Depth maps. Depth maps, or depth images, record the distance of the surface of objects in a 3D scene to a viewpoint. They are often the product of some 3D acquisition systems such as stereo cameras or Kinect sensors. They are also used in computer graphics for rendering where the term Z‐buffer is used to refer to depth. Mathematically, a depth map is a function where is the depth at pixel . In other words, if one projects a ray from the viewpoint through the image pixel , it will intersect the 3D scene at the 3D point of coordinates . Depth maps are compact representations. They, however, represent the 3D world from only one viewpoint, see Figure 2.7b. Thus, they only contain partial information and are often referred to as 2.5D representations. To obtain a complete representation of a 3D scene, one requires multiple depth maps captured from different viewpoints around the 3D scene.

As we will see in the subsequent chapters of this book, depth maps are often used to reduce the 3D shape analysis problem into a 2D problem in order to benefit from the rich image analysis literature.

(3) Point‐based representations. 3D acquisition systems, such as range scanners, produce unstructured point clouds , which can be seen as a dense sampling of the 3D world. In many shape analysis tasks, this point cloud is not used as it is, but converted into a 3D mesh model using some tessellation techniques such as ball pivoting 2 and alpha shapes 3. Point clouds can be a suitable representation for some types of 3D objects such as hair, fur, or vegetation, which contain dense tiny structures.

(4) Implicit and volumetric representations. An implicit surface is defined to be the zero‐set of a scalar‐valued function . In other words, the surface is defined as the set of all points such that .

The implicit or volumetric representation of a solid object is, in general, a function , which classifies each point in the 3D space to lie either inside, outside, or exactly on the surface of the object. The most natural choice of the function is the signed distance function, which maps each 3D point to its signed distance from the surface . By definition, negative values of the function designate points inside the object, positive values designate points outside the object, and the surface points correspond to points where the function is zero. The surface is referred to as the level set or the zero‐level isosurface. It separates the inside from the outside of the object.

Implicit representations are well suited for constructive solid geometry where complex objects can be constructed using Boolean operations of simpler objects called primitives. They are also suitable for representing the interior of objects. As such, they are extensively used in the field of medical imaging since the data produced with medical imaging devices, such as CT scans, are volumetric.

There are different representations for implicit surfaces. The most commonly used ones are discrete voxelization and the radial basis functions (RBFs). The former is just a uniform discretization of the 3D volume around the shape. In other words, it can be seen as a 3D image where each cell is referred to as a voxel (voxel element), in analogy to pixels (picture elements) in images.

The latter approximates the implicit function using a weighted‐sum of kernel functions centered around some control points. That is:

(2.26)

where is a polynomial of low degree and the basis function is a real valued function on , usually unbounded and has a noncompact support 4. The points are referred to as the centers of the radial basis functions.

With this representation, the function can be seen as a continuous scalar field. In order to efficiently process implicit representations, the continuous scalar field needs to be discretized using a sufficiently dense 3D grid around the solid object. The values within voxels are derived using interpolation. The discretization can be uniform or adaptive. The memory consumption in the former grows cubically if the precision is increased by reducing the size of the voxels. In the adaptive discretization, the sampling density is adapted to the local geometry since the signed distance values are more important in the vicinity of the surface. Thus, in order to achieve better memory efficiency, a higher sampling rate can be used in these regions only, instead of a uniform 3D grid.

2.1.4.2 Mesh Data Structures

Let us assume from now on, unless explicitly stated otherwise, that the boundary of a 3D object is represented as a piecewise linear surface in the form of a triangulated mesh , i.e. a set of vertices and triangles . The choice of the data structure for storing such 3D objects should be guided by the requirements of the algorithms that will be operating on the data structure. In particular, one should consider whether we only need to render the 3D models, or do we need to have constant‐time access to the local neighborhood of the vertices, faces, and edges.

The simplest data structure is the one that stores the mesh as a table of vertices and encodes triangles as a table of triplets of indices into the vertex table. This representation is simple and efficient in terms of storage. While it is very suitable for rendering, it is not suitable for many of the shape analysis algorithms. In particular, most of the 3D shape analysis tasks require access to:

• Individual vertices, edges, and faces.
• The faces attached to a vertex.
• The faces attached to an edge.
• The faces adjacent to a given face.
• The one‐ring vertex neighborhood of a given vertex.

Mesh data structures should be designed in such a way that these queries can run in a constant time. The most commonly used data structure is the halfedge data structure 5 where each edge is split into two opposing halfedges. All halfedges are oriented consistently in counter‐clockwise order around each face and along the boundary, see Figure 2.9. Each halfedge stores a reference to:

• The head, i.e. the vertex it points to.
• The adjacent face, i.e. a reference to the face which is at the left of the edge (recall that half edges are oriented counter‐clockwise). This field stores a zero pointer if this half edge is at the boundary of the surface.
• The next halfedge in the face (in the counter‐clockwise direction).
• The pair, called also the opposite, half‐edge.
• The previous half‐edge in the face. This pointer is optional, but it is used for a better performance.

Additionally, this data structure stores at each face, references to one of its adjacent half‐edges. Each vertex also stores a reference to one of its outgoing half‐edges. This simple data structure enables to enumerate, for each element (i.e. vertex, edge, half‐edge, or face), its adjacent elements in a constant time independently of the size of the mesh.

Other efficient representations include the directed edges 6, which is a memory efficient variant of the half‐edge data structure. These data structures are implemented in libraries such as the Computational Geometry Algorithms Library (CGAL)¹ and OpenMesh.²

2.1.4.3 Discretization of the Differential Properties of Surfaces

Since, in general, surfaces are represented in a discrete fashion using vertices and faces , their differential properties need to be discretized.

First, the discrete Laplace–Beltrami operator at a vertex can be computed using the following general formula:

(2.27)

where denotes the set of all vertices that are adjacent to , are some weight factors, and is a normalization factor. Discretization methods differ in the choice of these weights. The simplest approach is to choose and . This approach, however, is not efficient. In fact, all edges are considered equally, independently of their length. This may lead to poor results (e.g. when smoothing meshes) if the vertices are not uniformly distributed on the surface of the object.

A more accurate way of discretizing the Laplace–Beltrami operator is to account for how the vertices are distributed on the surface. This is done by setting:

and is equal to twice the Voronoi area of the vertex , which is defined as one‐third of the total area of all the triangles attached to the vertex . The angles and are the angles opposite to the edge that connects to , see Figure 2.10.

The discrete curvatures can be computed using the discrete Laplace–Beltrami operator as follows:

• The mean curvature:
  (2.28)
• The Gaussian curvature at a vertex is given as
  (2.29)
  where is the Voronoi area, and is the angle between two adjacent edges incident to , see Figure 2.10.
• The principal curvatures:
  (2.30)
  (2.31)

2.2.1.1 Normalization for Translation

One can discard translation by translating so that its center of mass is located at the origin:

(2.34)

where is the center of mass of . It is computed as follows:

(2.35)

Here is the local surface area at . It is defined as the norm of the normal vector to the surface at . In the case of objects represented as a set of vertices and faces , then the center of mass is given by:

(2.36)

Here, 's are weights associated to each vertex . One can assume that all vertices have the same weight and set . This is a simple solution that works fine when the surfaces are densely sampled. A more efficient choice is to set to be the Voronoi area around the vertex .

2.2.1.2 Normalization for Scale

The scale component can be discarded in several ways. One approach is to scale each 3D object being analyzed in such a way that its overall surface area is equal to one:

(2.37)

where is a scaling factor chosen to be the entire surface area: . When dealing with triangulated surfaces, is chosen to be the sum of the areas of the triangles which form the mesh.

Another approach is to scale the 3D object in such a way that the radius of its bounding sphere is equal to one. This is usually done in two steps. First, the 3D object is normalized for translation. Then, it is scaled by a factor where is the distance between the origin and the farthest point on the surface from the origin.

2.2.1.3 Normalization for Rotation

Normalization for rotation is the process of aligning all the 3D models being analyzed in a consistent way. This step is often used after normalizing the shapes for translation and scale. Thus, in what follows, we assume that the 3D models are centered at the origin. There are several ways for rotation normalization. The first approach is to compute the principal directions of the object and then rotate it in such a way that these directions coincide with the three axes of the coordinate system. The second one is more elaborate and uses reflection symmetry planes.

Rotation Normalization Using Principal Component Analysis (PCA)

The first step is to compute the covariance matrix :

(2.38)

where is the number of points sampled on the surface of the 3D object, is its center of mass, and refers to the transpose of the matrix . For 3D shapes that are normalized for translation, is the origin. When dealing with surfaces represented as polygonal meshes, Eq. (2.38) is reduced to

(2.39)

Here, is the number of vertices in . Let be the eigenvalues of , ordered from the largest to the smallest, and their associated eigenvectors (of unit length). Rotation normalization is the process of rotating the 3D object such that the first principal axis, , coincides with the axis, the second one, , coincides with the axis, and the third one, , coincides with the axis. Note, however, that both and are correct principal directions. To select the appropriate one, one can set the positive direction to be the one that has maximum volume of the shape. Once this is done, then the 3D object can be normalized for rotation by rotating it with the rotation matrix that has the unit‐length eigenvectors as rows, i.e.:

(2.40)

This simple and fast procedure has been extensively used in the literature. Figure 2.12 shows a few examples of 3D shapes normalized using this approach. This figure also shows some of the limitations. For instance, in the case of 3D human body shapes, Principal Component Analysis (PCA) produces plausible results when the body is in a neutral pose. The quality of the alignment, however, degradates with the increase in complexity of the nonrigid deformation that the 3D shape undergoes. The cat example of Figure 2.12 also illustrates another limitation of the approach. In fact, PCA‐based normalization is very sensitive to outliers in the 3D object and to nonrigid deformations of the object's extruded parts such as the tail and legs of the cat. As shown in Figure 2.13, PCA‐based alignment is also very sensitive to geometric and topological noise and often fails to produce plausible alignments when dealing with partial and incomplete data.

In summary, while PCA‐based alignment is simple and fast, which justifies the popularity of the method, it can produce implausible results when dealing with complex 3D shapes (e.g. shapes which undergo complex nonrigid deformations, partial scans with geometrical and topological noise). Thus, objects with a similar shape can easily be misaligned using PCA. This misalignment can result in an exaggeration of the difference between the objects, which in turn will affect the subsequent analysis tasks such as similarity estimation and registration.

Rotation Normalization Using Planar Reflection Symmetry Analysis

PCA does not always produce compatible alignments for objects of the same class. It certainly does not produce alignments similar to what a human would select 9. Podolak et al. 9 used the planar‐reflection symmetry transform (PRST) to produce better alignments. Specifically, they introduced two new concepts, the principal symmetry axes (PSA) and the Center of Symmetry (COS), as robust global alignment features of a 3D model. Intuitively, the PSA are the normals of the orthogonal set of planes with maximal symmetry. In 3D, there are three of such planes. The Center of Symmetry is the intersection of those three planes. The first principal symmetry axis is defined as the plane with maximal symmetry. The second axis can be found by searching for the plane with maximal symmetry among those that are perpendicular to the first one. Finally, the third axis is found in the same way by searching only the planes that are perpendicular to both the first and the second planes of symmetry.

We refer the reader to 9 for a detailed description of how the planar‐reflection symmetry is computed. Readers interested in the general topic of symmetry analysis of 3D models are referred to the survey of Mitra et al. 10 and the related papers. Figure 2.14 compares alignments produced using (a) PCA and (b) planar reflection symmetry analysis. As one can see, the latter produces results that are more intuitive. More importantly, the latter method is less sensitive to noise, missing parts, and extruded parts.