Surface Networks via General Covers
Niv Haim Nimrod Segol Heli Ben-Hamu Haggai Maron Yaron Lipman

	
	
	
	
	
	
	
	Surface Networks via General Covers
    Niv Haim Equal contribution

		
		Nimrod Segol 

		
		Heli Ben-Hamu 

		
		Haggai Maron 

		
		Yaron Lipman 

		

		
		Weizmann Institute of Science

		Rehovot, Israel

		
		
		
		
		
		
		
		
		
		
	
    
============================================================================================================================================================================================================


		Developing deep learning techniques for geometric data is an active and fruitful research area. This paper tackles the problem of sphere-type surface learning by developing a novel surface-to-image representation. Using this representation we are able to quickly adapt successful CNN models to the surface setting. 
		
		The surface-image representation is based on a covering map from the image domain to the surface. Namely, the map wraps around the surface several times, making sure that every part of the surface is well represented in the image. Differently from previous surface-to-image representations, we provide a low distortion coverage of all surface parts in a single image. Specifically, for the use case of learning spherical signals, our representation provides a low distortion alternative to several popular spherical parameterizations used in deep learning.
		
		We have used the surface-to-image representation to apply standard CNN architectures to 3D models including  spherical signals. We show that our method achieves state of the art or comparable results on the tasks of shape retrieval, shape classification and semantic shape segmentation.
		
	
	
	
	
	
	
	

	

§ INTRODUCTION

	Adapting deep learning methods to geometric data (, shapes) is a vibrant research area that has already produced state of the art algorithms for several geometric learning tasks (,  <cit.>). 
	
	Two prominent approaches are: (i) mapping the geometric data to tensors (, images) and using off-the-shelf convolutional neural network (CNN) architectures and optimization techniques <cit.>; and (ii) developing novel architectures and optimization techniques that are tailored to the geometric data <cit.>. 
	
	An important benefit of (i) is in reducing the geometric learning task to an image learning one, allowing to harness the huge algorithmic progress of neural networks for images directly to geometric data. 
	
	Some previous attempts, following (i), to perform learning tasks on geometric data use projections to 2D planes, , by rendering the shapes <cit.>. Such projections are not injective and suffer from occlusions, thus often require a collection of projections for a single shape. Other methods embed the shape in an encapsulating 3D grid <cit.>; these methods require dealing with higher dimensional tensors and are usually less robust to deformations. Other methods <cit.> try to find low distortion 2D mappings to an image domain. In this case the intrinsic dimensionality of the data is preserved, however, these maps suffer from high distortion and/or ignore the difference in the topologies of the surface (no boundary) and the image (with boundary).
	
	In this paper, we advocate a novel 2D mapping method for representing sphere-type (genus zero, , the human model in Figure <ref>a, left) surfaces as images. The challenge in using an image to represent a surface has two aspects: geometrical and topological. Geometrically, a general curved surface cannot be mapped to a flat domain (, the image) without introducing a significant distortion. Topologically, an image has a boundary while sphere-type surfaces do not; hence, any mapping between the two will introduce cuts and discontinuities. Furthermore, a naive application of 2D convolution to the image would be ambiguous on the surface (see Figure <ref> and Subsection <ref>). 
	
	To address these challenges we think of the image as a periodic domain (, a torus) and relax the notion of a one-to-one mapping to that of a covering map from the image domain onto the surface. That is, we construct a mapping from the image domain to the surface that covers the surface several times. For example, Figure <ref>a visualizes a degree-5 covering map. Meaning, the surface appears 5 times in the image; note how each part of the surface appears with low distortion at-least once in the image. The image generated by our covering map is periodic, namely its left and right boundaries as well as its bottom and top boundaries correspond, making the image boundaryless. Importantly, since image convolution is well defined on a torus, it will translate to a continuous convolution-like operator on the surface <cit.>.
	
	
    Applying our method to surface learning is easy: use a covering map to transfer functions of interest over the input surfaces (, the coordinate functions) to images and apply one's favorite CNN with periodic padding. 
		
	We tested our method in two scenarios: spherical signal learning <cit.>, and surface collection learning. For spherical signal learning, our approach provided state of the art results among all spherical methods on a shape retrieval dataset (SHREC17 <cit.>) and a shape classification dataset (ModelNet40 <cit.>). For surface collection learning, our method produced state of the art results on a surface segmentation dataset (Humans <cit.>). 
	Our contributions are:
	

		
  * We introduce a broad family of low distortion surface-to-toric image representations. The toric image representation allows applying off-the-shelf CNNs to general genus-zero surfaces. 

		
		
  * In particular, we provide a framework for learning spherical signals using CNNs. 

		
		
  * We introduce a practical algorithm for computing toric covers of genus zero surfaces. 

	

	Our code is available at <https://github.com/nivha/surface_networks_covers>
	
	
	
	

§ PREVIOUS WORK
	

		
	
	
		
	
	Applying deep learning techniques to geometric data has proved to be a huge success in the last few years.  A wide variety of methods were suggested, where the most popular approaches are: volumetric based methods (, <cit.>), rendering based methods (, <cit.>), spectral based methods (, <cit.>) and methods that operate directly on the surface itself (, <cit.>). A popular related problem is the problem of learning on point clouds which received a lot of attention lately (see , <cit.>).
	
	Here, we restrict our attention to intrinsic or parameterization-based surface methods and refer the reader to the above mentioned works and a recent survey <cit.> for further information. 
	
	Local parameterization. Such methods (,  <cit.>) extract local surface patches and use them in order to learn point representations. In <cit.> the authors use local polar coordinates as the patch operator. In a follow-up work,  <cit.> use projections on oriented anisotropic diffusion kernels, where <cit.> learn the patch operator using a Gaussian mixture model. In contrast to these works, we employ a global parameterization which represents the shape using a single image.
	
	Global parameterization. Other methods use global parametrization of the surface to a canonical domain. <cit.> use an area-preserving parameterization and map surfaces to a planar domain (going through a sphere); the global area-preserving parameterization cannot cover the surface with low distortion everywhere and depends on the specific cut made on the surface. 
	
	The most similar method to ours is <cit.> that proposes gluing four copies of the surface into a torus and map it conformally (, preserving angles) to a flat torus, where the convolution is well defined. Their map is defined by a choice of three points on the surface, and suffers from significant angle and scale distortion, see Figure <ref>b (, the head, right arm and torso). In order to cover each point on the surface reasonably well, the authors sample multiple triplets of points from each surface where each triplet focuses on a different part of the surface. In a follow up work, <cit.> use the same parameterization as a surface representation for Generative Adversarial Networks (GANs) <cit.>. In order to deal with the high distortion of each single parameterization, the authors devise a multi-chart structure and rely on given sparse correspondences between the surfaces.
	
	
	Convolutions on tangent planes. <cit.> define convolutions on surfaces by working on the tangent planes. <cit.> also define the convolutions on tangent planes and relate convolutions on nearby points using parallel transport. <cit.> define convolutions on surfaces by extending the notion of a signal on a surface into a directional signal and build layers that are equivariant to the choice of reference directions. <cit.> utilizes 4-rotational symmetric field to define a domain for convolution on a surface.
	
	Convolutions of spherical signals. Our work targets learning of general genus zero surfaces. In particular, it can facilitate learning of spherical signals, a task that has received growing interest in the last few years. <cit.> note that an equirectangular projection of a spherical signal suffers from large distortions and suggest network architectures that try to compensate for these distortions. <cit.> perform 2D convolution on spherical strips extracted from the spherical signal. 
	<cit.> suggest to define the convolution of a spherical signal as a linear combination of differential operators with learned weights.   
	In a different line of work, <cit.> propose networks that are invariant to the natural action of SO(3) on spherical signals. <cit.> advocate the notion of gauge equivariance as the correct equivariance notion on manifolds, and construct gauge equivariant networks on spheres. 
	
	Other methods.	<cit.> tackle the shape segmentation problem by a novel architecture that operates on local features (such as normals) and global features (such as distances) and then fuses them together. <cit.> propose an improved graph neural network model based on the Dirac operator.



	

	
	

§ PRELIMINARIES
 

	In this section we discuss our choice of periodic images (images with toric topology) and introduce branched covering maps, the main mathematical tool used in our approach. 
	
	
	
	

 §.§ Convolutions on flattened spheres


	
	A standard way to apply CNNs to a signal on a sphere-type surface is to represent it as an image and apply standard 2D convolution. Since representing a sphere as an image requires cutting and duplicating the cuts, different boundary segments in the image represent the same segment on the sphere. 
	
	In the case where the transformation in the image domain between the two duplicated boundary segments is a pure translation then the result of applying 2D convolution at any two matching points on these segments will result in exactly the same value. In other cases, such as equirectangular spherical projection <cit.> or octahedron spherical projection <cit.>, 2D convolution on two matching points result in two different values. Figure <ref> shows an example where duplicated image boundary segments are marked with the same color arrows; a pair of matching points (marked P) are shown in each example along with an illustration of a convolution kernel. Note that only in the toric topology the kernel is consistent at the duplicated points. A similar point of view for toric images was suggested in <cit.>. We extend it to a more general family for toric images of sphere-type surfaces. 
	
	
	

	

 §.§ Branched covering maps

	This section provides a brief introduction to branched covering maps (for more details see <cit.>). We start with a formal definition:
	
	
	Let X and Y be topological spaces. A map E : X → Y is a branched covering map if every point y ∈ Y except for a finite set of points {b_1, … ,b_k} has a neighborhood U ⊆ Y, such that E^-1(U) is a disjoint union of homeomorphic [A homeomorphism is continuous map with a continuous inverse.] copies of U.
		
	The set of points {b_1, … ,b_k} are called branch points.
	
	
	A simple example for a branched covering map is E(z) = z^d, for X=Y=ℂ, and for some integer d. The function E has one branch point at b_1=0. Every point y∈ Y ∖{0}, has d distinct pre-images E^-1(y) = {x_1, …, x_d}⊂ X. However, the point y=0 has a single pre-image E^-1(y) ={0}. We say that the point y=0 has d pre-images located at 0, or that 0 is a pre-image with multiplicity d. The ramification index of x over E(x) is the multiplicity at x, namely 1 for all x∈ E^-1 ( Y ∖0) and d for x=E^-1(b_1)=0. We denote it as r(x|E(x)). Figure <ref>b shows this example for d=4. In fact, this example captures all the local behaviors of covering maps: around a point x ∈ X with r(x|E(x)) = r the map E looks like the map z ↦ z^r.
	
	
	
	Let us give another example: Consider the function E(z) = z^2(z-7). It has a branch point at y=0 with two distinct pre-images. Namely, E^-1(0) = {0, 7}. Here, the ramification index of 0 over E(0) is 2 and the ramification index of 7 over E(7) is 1. We say that the ramification structure of 0 is [2,1], formally:
	
	
		Let E:X→ Y be a branched covering map, b_i a branch point and l_i=|E^-1(b_i)|, the number of pre-images of b_i. The ramification structure of b_i is the multi-set of ramification indices of its pre-images, denoted by ρ_i = [r_i,1, … r_i,l_i]. The ramification type of E is the collection of its ramification structures, ρ = [ρ_1, … , ρ_k].
	
	
	Figure <ref>a depicts a branch point b_1 with three distinct pre-images, l_1=3, and ramification structure ρ_1 = [2, 1, 3]. Note that the ramification structure of a non-branch point is a trivial multi-set of ones: [1… 1], see , the red dot in Figure <ref>a. 
	
	The sum of the ramification indices of any point in X is independent of the choice of the point (see <cit.>, page 44 Proposition 7), namely 
	
    ∑_j=1^l_ir_i,j=d.

	Lastly, d is called the degree of the covering. Intuitively, the degree of the covering counts how many times X covers Y, or alternatively how many copies of Y can be found in X.
	
	 
 

	

 §.§ Riemann-Hurwitz formula

	
	A key fact about ramification types of branched covering maps between (boundaryless) surfaces is the Riemann-Hurwitz formula (RH), which connects the genus (, number of handles) of the surfaces with the ramification type. In our case, we map a torus to a sphere-type surface and get the corresponding RH formula:
	
    ∑_i=1^k∑_j=1^l_i(r_i,j - 1) = 2d

	A quick derivation of this formula is given in Section <ref>.
	
	
	Therefore, the RH formula sets a necessary condition on the possible ramification types ρ of such branched covering maps. For example, the ramification type [2],[2],[2],[2] satisfies the RH equations but the ramification type [2],[2] does not (in this case d=2, k=2, l_i=1), implying that there is no covering map with this ramification type. We note that Equations (<ref>) and (<ref>) are necessary but not sufficient conditions. 
	
	
	

§ APPROACH

	Our goal is transferring signals (, functions) from a sphere-type  surface M to the image domain I (, the flat torus: unit square [0,1]^2 with opposite ends identified). This is done by constructing a branched covering map 	
    E: I→ M
 
	and pulling back the signals to the image using E. That is, given a signal f:M^n that we want to transfer, the value of a pixel p∈ I is set to f(E(p)). We represent the surface M using a triangular mesh. 
	
	
	
	We build the covering map E:I M in two steps, as a composition of two functions:
	
    E    =   Ψ∘Φ
    Φ   : I → T  
    Ψ   : T → M.

    where T is a torus-type surface built out of d copies of M, Ψ is a branched covering map, and Φ is a homeomorphism between the two tori I and T (see Figure <ref> for illustration).
    

	

 §.§ Computing the branched covering map Ψ

	
	In this section we describe how we construct the mesh T out of the mesh M and the branched covering map Ψ:T → M. The idea is to cut and glue together several copies of the input surface M in a way that generates a toric covering space corresponding to a specific choice of ρ.
	
	First, we choose k branch points b_1, … , b_k from the set of vertices of M (using farthest point sampling), a degree d and a valid ramification type ρ satisfying Equations (<ref>)-(<ref>). Our algorithm then consists of the following steps:
	
	Step (i): We cut the mesh along k disjoint paths, all emanating from the same (arbitrary) vertex v_0 in M and ending at the branch points b_i for i∈ [k]. Figure <ref> shows this for k=d=5. Topologically, M_disk is a disk, with all branch points at its boundary. 
	
	Step (ii):
	M_disk is then duplicated d times, to form copies M_disk^ (1),…, M_disk^ (d). Figure <ref> shows the 5 copies with v_0 as a white dot and the branch points as colored dots.
 
	
	
	
	
	Step (iii): 
	We glue the d copies of M_disk to create the surface T as follows. Consider a branch point b_i; it has d copies located in each of the copies of M_disk, see , the blue dots in Figure <ref>. Denote by B_j and A_j the two boundary edges emanating from the j-th copy of b_i. Note that on the original surface A_j is glued to B_j; since every B_j' is a duplicate of B_j, A_j can be glued to any B_j', j'∈[d]. Therefore, to describe the gluing of the edges emanating from b_i we use a  permutation σ_i ∈ S_d (a permutation is a bijection [d] [d]): A_j is glued to B_σ_i(j). The collection of all permutations (one permutation per branch point)
	
    Σ=σ_1,…,σ_k

	is called the gluing instructions.  Given gluing instructions Σ we use it to stitch the boundary of the d copies of M_disk to construct the toric surface T (, genus one). The mapping Ψ:T→ M is then defined by: map v∈ T to its original version in M, and extend linearly in each triangle (, face) of T.  Ψ is a well defined branched covering map. The gluing procedure is summarized in Algorithm <ref>. In Subsection <ref> we describe the algorithm for computing the gluing instructions given the desired ramification type ρ. 
	
	
	
	
	
	
	
	
	

  §.§.§ Computing the gluing instructions

  In this paper we limit our attention to ramification types of the form 
	
    ρ =  [1^d-r, r ]^k ,

	where d is the cover degree, k is the number of branch points, and r is the maximal multiplicity of the branch points' pre-images. The motivation in choosing these ramification types is two-fold: First, we want all branch points to be treated equally by the cover. Second, applying higher ramification order improves area distortion of protruding parts (see , <cit.>); See Figure <ref> and Subsection <ref> for an example.
	
	First, let us compute necessary conditions for ρ defined in  (<ref>) to be a feasible ramification type. Equation (<ref>) is automatically satisfied since d-r+r=d. Plugging ρ in (<ref>) we get 
	
    k (r-1) = 2d.

	
	This sets a trade-off between r and d: higher values of r, while reducing distortion of protruding parts would force higher degree d of the cover, which will produce more copies of M in the image. Practically, we found that k=5,r=5,d=10 and k=6,r=2,d=3 are both good options that strike a good balance between r and d. 
	
    To compute gluing instructions Σ we start with k,r,d satisfying (<ref>). The next theorem (proved in Section <ref>)
     provides a necessary and sufficient condition for the gluing instructions Σ to furnish a cover with ramification type ρ:
	
		
		A set of gluing instructions Σ=σ_1,…,σ_k yields a branched covering map with ramification type ρ if and only if the following conditions hold:
		
			
  * The cycle structure of σ_i equals the ramification structure of b_i, , ρ_i=[r_i,1,…, r_i,l_i].
			
  * Σ is a product one tuple. That is, σ_1·σ_2⋯σ_k = I_d.
			
  * The group G generated by Σ is a transitive subgroup of S_d. Namely, for each i,j∈ [d] there exists σ∈ G so that j=σ(i).  
		
	
	
	Theorem <ref> indicates that we should search for permutations σ_i with prescribed cycle structures. That is, the permutations σ_i, if exist, are in some prescribed conjugacy classes of the permutation group. Algorithm <ref> performs such a search, more or less exhaustively, using conditions (ii) and (iii) to prune options that cannot lead to a solution Σ. 
	
	Since theoretically not all k,r,d satisfying Equation (<ref>) have a corresponding covering map, Algorithm <ref> can terminate without finding gluing instructions. In this case, according to Theorem <ref> we know that there is no covering map with ramification type ρ. Nevertheless, it is rare to find such examples in practice and indeed we did not encounter such a case in our experiments. Table <ref> contains the results of Algorithm <ref> for any permissible k,r,d with k≤ 6, d≤ 10 so that they can be used as input to Algorithm <ref>.
	

	

	
	
	

 §.§ Flattening the toric surface 

	
	
	
	The last part of our covering map computation is the computation of the map Φ:I T. Equivalently, we compute Φ^-1.  To that end we use a version of the Orbifold-Tutte embedding <cit.>. We first cut T along the two generating loops of the torus (using <cit.>, Algorithm 5) to get a disk-type surface T_disk. Second, we compute a bijective piecewise affine map Φ^-1:T I by solving a sparse linear system of equations Ax=b, where A∈^m × m and x, b∈ ^m× 2, and m is the number of vertices in the disk-like mesh T_disk. This system is a discrete version of the Poisson equation <cit.>, see Section <ref> 
	for details on how to construct A,b. We use x to map the vertices of T to I and extend linearly to get the piecewise affine map Φ^-1.
	
		The resulting map is discrete harmonic <cit.>, approximately conformal up to a linear transformation, and as proven in <cit.>, a bijection.
	
	
	
	
	
	

 §.§ Example

	
	Figure <ref>a depicts the case k=5, r=3, d=5. Thus ρ =  [1,1,3]^5; every branch point b_i has three distinct pre-images, where two have ramification one, and one with order-3 ramification. The gluing instructions in this case, computed using Algorithm <ref>, are:
	
    Σ = {   (1)(2)(345), (1)(4)(235),  (3)(4)(152), 
       (3)(4)(125), (1)(5)(243) } .

	Note that each of these permutations has a cycle structure [1,1,3] as required in Theorem <ref> (i); conditions (ii)-(iii) can be checked as well. These gluing instructions were used to glue the 5 copies of M_disk (as shown in Figure <ref> and described in alg:glue) to generate the representation E: I → M shown in Figure <ref>a.
	
	
	

		
	
	
	


	

§ EXPERIMENTS

	To evaluate the efficacy of our method we tested it in two main scenarios: learning signals on the sphere, and learning sphere-type surface data. 
	
	

	

 §.§ Evaluation

    In this section we compare the geometric properties of our representation to standard or existing techniques. Figure <ref> shows the area and scale distortion of our method (right, in blue) and two other popular methods for sphere flattening:  Equirectangular projection (see , <cit.>) and octahedron unfolding projection, see <cit.>.
    
    Area distortion is computed as the determinant of the differential of the cover map E (treated as affine over each triangle of M), and angle distortion is the condition number of the differential. Since our image representation contains several copies of each triangle of M we use the least distorted one for the histogram, as we want each part of the surface to appear in the image at-least once with low distortion. As can be seen in Figure <ref>, our projection has better angle preservation with only a mild sacrifice to area distortion. 
    
    
	In Figure <ref> we repeat this experiment with a sphere-type model of a human and compare the area and angle distortion of five different types of image representations. While the method of <cit.> (leftmost, in red) preserves area better, it suffers from significant angle distortion. The orbifold covering of <cit.> (second to the left, in red) is angle-preserving, but suffers from notable area shrinking. Our covering maps (green and blue) strike a balance between angle and area preservation. The covering of type [[1^5, 5]^5] (middle, in blue) has the least area distortion and we chose it for the segmentation task (below).
	
	The top row of Figure <ref> compares the different image representations by reconstructing the original model. Specifically, for each vertex of the mesh we sampled its x,y,z coordinates directly from the image at the vertex location (we used 512× 512 images here).  In our representation, we take the coordinates from the vertex copy with the least area distortion. Note that the image representations of <cit.> and <cit.> do not represent well significant parts of the surface (, the right leg and the head). 
	
	
		
	
	 


	
	


	

 §.§ 3D shape retrieval
	

	The first application of our method is 3D shape retrieval. We use the SHREC2017 benchmark <cit.> that contains 51162 3D models from 55 different categories. 
		
		There are two separate challenges: (i) the shapes are consistently aligned (ii) the shapes are randomly rotated. We tackle the (harder) second challenge.
	
	Since the shapes are not of genus zero we follow the protocol of <cit.> that project the meshes on a bounding sphere using ray casting, and record six functions on this sphere: distance to the model, cos/sin of the model angles (this is done for both the model and its convex-hull). We then use our method to transfer these six spherical signals to periodic images (flat torus). See Figure <ref> for an example of such shape representation.    
	
	We compare our method to the top methods in each category, the Spherical CNN method <cit.>, and the recent SO-3 equivariant networks suggested in <cit.>. The results are summarized in Table <ref>; note that in the F1 measure we score first among all methods.   
	
	For this application we use a slight modification of the inception v3 architecture <cit.>. We train the network with ADAM optimizer <cit.> for 100 epochs with learning rate 0.05, batch size of 32, and learning rate decay of 0.995. Training took 15 minutes per epoch on a Tesla V100 Nvidia GPU. In evaluation time we average the output of the network on 5 randomly rotated copies of the query model.  
		

	

 §.§ Surface classification
	

		
	We apply our method to the ModelNet40 surface classification benchmark  <cit.> that contains 12311 3D models from 40 different categories.
		
		As in the shape retrieval task, we follow the protocol of <cit.> to generate input signals on a sphere. We then use our method to represent the spherical signals as periodic images and apply the same inception v3 model as in the shape retrieval task.  We present peak performance results (following <cit.>) for two scenarios that are popular in the literature: (i) the shapes are rotated randomly about the z axis; and (ii) the shapes are learned in their original orientation. We train the network with ADAM optimizer <cit.> for 100 epochs for scenario (1) and 300 for scenario (ii) with learning rate 0.0005, batch size 16, and learning rate decay 0.995. Training took 19 minutes per epoch for the first scenario (that contains 10 rotation augmentations) and 3 minutes per epoch for the second scenario on a Tesla V100 Nvidia GPU.
		
	Table <ref> compares our results with several recent methods including the baselines of equirectangular projection (, <cit.>) and octahedron unfolding projection <cit.>. Our results are the best among all spherical learning methods.
	
	
	
	

	

 §.§ Surface segmentation
 	
 While our first two application targeted spherical signals, our last applications learns signals defined on general sphere-type human models. In particular, we perform human model semantic segmentation. We use the benchmark from <cit.> that consists of 373 train models from multiple sources and 18 test models. 5% randomly sampled train models were used as a validation set (18 models). All models are given as triangular meshes. For each model, each face is labeled according to a predefined partition of the human body (, head, torso, hands, total of 8 labels). The task is to label the triangles of a new unseen human model with these labels. For each model we generate an augmented set of 120 images per mesh, by permuting the order of the branch points, multiplying the vertices by a random orthogonal matrix and a uniform scale sampled from [0.85,1.15] as suggested in <cit.>, and small periodic image translations of ± 15 pixels. In evaluation, as the toric image contains d values for each triangle on the original mesh, we use the label of the triangle with the largest area. Furthermore, we use 10 random augmentations of test images and label each mesh face using a majority vote. 
	
	Table <ref> summarizes the results of this experiment, where our method outperformed previous methods; Figure <ref> shows typical segmentation results.
	
	For this application we used the U-net architecture <cit.> with 16 layers (see Table <ref> for details).  We used a weighted loss with equal probability labels, and trained the network using stochastic gradient descent with momentum <cit.> for 50 epochs with learning rate 0.2, batch size 2, and learning rate decay of 0.995. Training takes ∼ 3 hours per epoch on a Tesla V100 Nvidia GPU.
	
	
	
	
	
	
	

	

§ CONCLUSIONS


	In this paper, we introduce a new method for representing sphere-type surfaces as toric images that can be used in standard Convolutional Neural Network frameworks for shape learning tasks. The method allows faithful representation of all parts of the surface in a single image, thus alleviating the need to generate multiple maps to cover each surface. Our method is general and can target both spherical signal learning tasks as well as more general learning tasks that involve signals on different genus zero surfaces.  Practically, we showed that off-the-shelf CNN models applied to images generated with our method lead to state of the art performance in the tasks of shape retrieval, shape classification and surface segmentation. 
	
	The main limitation of this work is its restriction to genus-zero surfaces. This kind of models are abundant, but certainly do not exhaust all 3D models. We would like to seek a generalization of this method to point clouds, depth images and more general topological types. 
	
	
	
	

	

§ ACKNOWLEDGEMENTS
 

	This research was supported in part by the European Research Council (ERC Consolidator Grant, ”LiftMatch” 771136) and the Israel Science Foundation (Grant No. 1830/17).
	
	ieee_fullname
		
	












§ CONVOLUTION ON A SPHERICAL MESH

In Figure <ref> we depict a cover map from the torus (texture square image on the left) to a human surface (middle); this map covers the human 5 times. We further show how standard convolution stencil (in yellow) translates to a seamless convolution on the surface. Note that the texture seams on the human models are pretty arbitrary and just indicate when moving to a different copy of the surface. 




§ GUIDELINES ON CHOOSING PARAMETERS

Adding branch points helps reducing the local distortion in protruding parts, therefore we recommend to choose as many branch points as there are protruding parts common in the dataset (5 for humans, 8 for octopuses etc.).
As we mentioned in section <ref> we choose a ramification type of the form [ [r , 1^d-r ] ] for each branch point.

As noted in Section <ref>, higher ramification (r) also improves area distortion of protruding parts. However, in that case, we are limited by the RH formula (eq:rhkind). So we would recommend choosing the highest r possible (as appears in Table <ref>) and taking d (number of copies) to satisfy eq:rhkind. Also note that higher r implies higher d (number of copies). Therefore, for a fixed image resolution we would like the highest number of branch points for which all relevant parts are still visible in the image.





§ GLUING INSTRUCTIONS

As mentioned in Section <ref>, for each choice of number of branch points k , degree d  and ramification type ρ satisfying Equations (<ref>) and  (<ref>) We need to compute a product one tuple of permutations satisfying the conditions of theorem <ref>. We note that this computation can be done in an offline step, before using Algorithm <ref> to compute the toric parameterization. 
In Table <ref> We provide gluing instructions corresponding to each valid choice of k≤ 6, d≤ 10 and ρ that complies with Equations  (<ref>) and  (<ref>). Each of the gluing instructions in Table <ref>
can be used as input to Algorithm (<ref>).
 





§ IMPLEMENTATION DETAILS





  
Learning. We use Pytorch <cit.> for learning. All the experiments are done with toric images generated by our algorithm and off-the-shelf CNN architectures with a single change: we replace the standard zero padding with periodic padding.  



  
Data generation. For the surface segmentation task we use a cover of the type ρ =[1^5,5]^5, that is, ρ_i=[1^5,5], i∈ [5]. For the spherical learning tasks (shape retrieval and classification) we use a cover of type ρ_i=[1,2], i∈ [6]. The locations of the branch points are chosen using farthest points sampling. We use the shortest paths from an arbitrary base point to all branch points in order to cut the mesh. When the mesh does not allow such a path we subdivide it locally (without changing its geometry). This pre-processing step is implemented in Matlab. It takes ∼22 seconds in average (relatively long running time due to a non-optimized mesh cutting code in Matlab) to generate a periodic (toric) image for a mesh with 6890 vertices on a single CPU core in an Intel(R) Xeon(R) CPU E5-2670 v3 @ 2.30GHz machine.



 §.§ Segmentation Task




  
Prediction. The network outputs per-pixel labels. In order to obtain a label for each face in the original mesh M, we first transfer the per-pixel logits to the faces F_T of the toric mesh using bilinear interpolation sampled at the faces' centers. Since each face f in M has d duplicated faces in the toric mesh T (|Ψ^-1(f) | = d), each face f in M has d sets of logits. We use a weighted average of the d sets of logits, where the weights are the area scales of the faces Ψ^-1(f). The label of f is the argmax of this weighted-average of logits. This means that better scaled faces (in the toric mesh) receive more weight when deciding how to label a face in the original mesh M.



  
Architecture. We use a version of a U-Net <cit.>. The feature-channels sizes are given in Table <ref>. After each convolution we use ReLU with a Batch-Normalization layer <cit.>. Each UpSample layer is a nearest-neighbour interpolation with scale-factor 2.




















§ PROOFS



 §.§ Riemann-Hurwitz formula


Consider a branched covering map E : T  → M of degree d and k branch points, from a toric mesh T= (V_T, E_T, F_T) to a spherical mesh M = (V_M, E_M, F_M). We prove that the ramification type of E must satisfy the Riemann-Hurwitz formula (<ref>).


	First, we note that the set of branch points B = {b_1, … b_k} can always be chosen from V_M.
	
	Every node v∈ V_M∖ B has d pre-images in V_T. However, a branch point b_i has l_i < d pre-images in V_T. Every edge e ∈ E_M has exactly d pre-images in E_T, that is |E_T|=d|E_M|. Similarly, |F_T|=d|F_M|.
	
	By computing the Euler characteristic for a toric surface:
	
    0    = χ(T) = |V_T| - |E_T| + |F_T|  
        = d (|V_M| - |E_M| + |F_M|)_χ(M) - ∑_i=1^k(d-l_i) 
        = 2d - ∑_i=1^k(d-l_i)
   
	
	Using 
    ∑_j=1^l_ir_i,j=d

	
	and rewriting we obtain the Riemann-Hurwitz formula (RH), in its version for a map from a toric surface to a spherical surface:
	
    ∑_i=1^k∑_j=1^l_i(r_i,j - 1) = 2d





 §.§ Proof of Theorem <ref>



We recall the following topological facts. A degree d branched covering map E:T → M from a torus to a genus 0 surface induces a group homomorphism, called the monodromy representation, from π_1 , the fundamental group of 
M∖{ b_1,…,b_k} to S_d.

The homomorphism is given as follows: We take each loop l ∈π_1, based at a point p, and lift it to T starting from a preimage of p. This lift has to end at another preimage of p. Due to properties of the lifting, this induces a permutation on the preimages of p in T, referred to as the fiber of p. 

The group π_1 has k generators and a single relation. The generators, l_1…,l_k, are the k loops around each of the branch points. The relation is l_1*…* l_k = 1.

Our gluing instructions, σ_1,…,σ_k, will be the images of l_1,…,l_k under the monodromy representation.
We shall now give a proof of Theorem <ref> . Namely, that our algorithm produces a cover T → M with ramification ρ if and only if the gluing instructions are a tuple of permutations satisfying the conditions of Theorem <ref>.

	First we prove that the conditions in the theorem are necessary.
	
	For (i), we note that a lift of a loop around a branch point l_i with a particular ramification structure induces a permutation with the same cycle structure.

	For (ii), the fact that l_1*… *l_k = 1, implies (using group homomorphism)  that σ_1·…·σ_k = I_d. 

	For (iii), fix p_1 ,p_2 in the fiber of p. Since T is connected, there exists a path γ connecting p_1 and p_2. The loop E∘γ is a loop starting and ending at p whose lift takes p_1 to p_2. Thus, the action of group generated by Σ = σ_1,…,σ_n is transitive.
	
	Conversely, suppose we have a product one tuple σ_1, … , σ_k satisfying the conditions of the theorem and k branch points b_1, …, b_k. Then condition (i) allows us to define an action of the group H:= ⟨σ_1,σ_2,…,σ_k⟩ on [d]. Following the construction in <cit.> pg 68-70 the space U × [d]/π_1× H is a covering space of M, where U is the universal cover of M. The transitivity of H implies that this covering space C is connected. Condition (iii) implies by the Riemann-Hurwitz formula that C is topologically a torus.
	
	Let D be the space produced from Algorithm <ref>. Note that the construction in Algorithm <ref> implies that lifting a loop circling each branch point b_i induces the permutation σ_i on the fiber of a generic point. Thus, the action of π_1 on D coincides with the action of π_1 on C. Since every action of π_1 on [d] (up to conjugation) produces a unique (up to homeomorphism) covering space, we deduce that D is homeomorphic to C.
	
	





  
Comment: The equivalence between branched covering maps and tuples of permutations satisfying the conditions of Theorem <ref> is well known. This equivalence is commonly referred to as Riemann's existence theorem (RET). However, to the best of our knowledge, it was previously not known how to practically construct any given branched covering map (our Algorithm <ref>). 



§ GLUING INSTRUCTIONS

We now turn to describing an algorithm that finds tuples of permutations
σ_1,…,σ_k∈ S_d, corresponding to a prescribed
ramification structure ρ, up to simultaneous conjugation (relabeling of the branch points). We call such a tuple a product one tuple. We implement our algorithm using Magma computational algebra system <cit.>.

We denote the conjugacy class in S_d associated with the cycle structure of ρ_i by C_i. In the algorithm construction we use the following:

	
		
  * ⟨σ_1,σ_2,…,σ_k-1⟩
		is a transitive permutation group and Π_i=1^k-1σ_i∈ C_n , if and only if σ_1,σ_2,…, σ_k, where σ_k =  (σ_1σ_2⋯σ_k-1)^-1 is a transitive product one tuple with σ_k∈ C_k.
		
  * The set σ_1,…,σ_i can be completed to a transitive product one tuple compatible with a ramification structure ρ if and only if σ_1,…, σ_i-1, g σ_i g^-1, for any g∈ Z(σ_1,…, σ_i-1) (Z denotes the centralizer), can be completed to a transitive product one tuple compatible with ρ. 
	


	(1) follows from the observations that adding elements to a transitive generator set keeps the set transitive, and that for g ∈ S_d the cycle structure of g and g^-1 are the same. For (2), note that for any g∈ Z(σ_1,…,σ_i-1) and j∈[i-1] it holds that gσ_jg^-1=σ_j. Thus,  for any g∈ Z(σ_1,…,σ_i-1), we have that any tuple with σ_1, …, σ_i is the same as a tuple with gσ_1g^-1,… ,gσ_ig^-1,  up to simultaneous conjugation.


The main idea in the algorithm for finding all gluing instructions corresponding to a ramification type ρ is to exhaustively go over all tuples σ_i∈ C_i and check whether they form a product one tuple. We use the claim above to prune this exhaustive search, as described in Algorithm <ref>. Note that this computation is done once for a given cover ramification type and is reused for all models using this type of cover. 


















§ ORBIFOLD-TUTTE EMBEDDING OF T


We compute x by solving a sparse linear system following <cit.>:

    Ax= b
 Here A∈^m × m and x, b∈ ^m× 2, where m is the number of vertices in the disk-like mesh T_disk. The linear system (<ref>) is constructed by putting together four sets of linear equations as follows:

First, for all interior vertices we set the discrete harmonic equation: 
    ∑_u∈ N_v w_vu( x_v - x_u)=0

where N_v is the set of vertices in V_T_disk adjacent to v and w_uv are the cotangent weights <cit.>.

Let L_1 and L_2 be the generators of the homotopy group of T. Denote by v_0∈ V_T the intersection of the two loops L_1 and L_2 . In T_disk, the vertex v_0 has four copies v_1', v_2', v_3', v_4'. next, we ensure that these four copies are mapped to the four corners of the unit square [0, 1]^2. Explicitly,  
    v_1' = [0, 0]^T, v_2' = [1, 0]^T, v_3' = [1, 1]^T, v_4' = [1, 0]^T

Each vertex v ∈∂ V_T_disk∖{v_1', v_2', v_3', v_4'} has a twin vertex ṽ such that v and ṽ  correspond to the same vertex in the uncut mesh T. Moreover, each such vertex v has its origin in V_T either in L_1 or in L_2. 

We set the vertices whose origin is in L_1 to be different by a constant translation in [0, 1]^T and the vertices whose origin is in L_2 to be different by a constant translation in [1, 0]^T. Namely:

    ṽ - v = a
 where v and ṽ are twins, and a is either [0, 1]^T  or [1, 0]^T, depending on whether the origin of v belongs to L_1 or L_2.

Finally we set each vertex v∈∂ V_T_disk∖{v_1', v_2', v_3', v_4'} to be the weighted average of both its neighbors and the translated neighbors of its twin. 
    ∑_u ∈ N(v) w_uv(x_v-x_u) + ∑_u ∈ N(ṽ) w_uṽ(x_ṽ -x_u + a) = 0
 with a as before.












	
