MAT-Net: Medial Axis Transform Network for 3D Object Recognition

1 Introduction

Shape representation and neural network architecture are the research hotspots of 3D deep learning. Although deep learning has achieved remarkable results in the field of 2D images, it is difficult to be applied directly to 3D shapes, due to the complexity of the spatial and topological relationship between surface samples. Voxel representation [Wu et al., 2015] is a regular 3D binary grid, which can be input to a standard convolution operation. But the memory and computation costs grow cubically as the resolution increases. Multiview-based methods [Su et al., 2015] express 3D objects as multi-view 2D images, by taking the advantage of pre-trained 2D CNN architectures. However, all views need to be pregenerated, and it is unclear how to determine the number and distribution of views to cover the 3D shape while avoiding self-occlusions. Point cloud is a typical 3D object representation that can be easily obtained from scanning devices, which has been exploited in point-based deep learning methods [Qi et al., 2017a]. But they also ignore the information of topology structure in geometric presentation, leading to relatively low accuracy results in classification tasks.

This situation motivates us to find a 3D shape representation that has the following properties while avoiding the above mentioned problems: adapting to typical CNNs, expressing local and multi-scale information of shape, utilizing topological structure, and having low computational complexity. A representation is called a complete shape descriptor if it can be used to reconstruct the original shape. Medial Axis Transform (MAT) [Blum, 1967] is exactly a complete shape descriptor, and it contains information that jointly describes geometry, topology, symmetry, and thickness properties of a shape in a very compact fashion.

∗Corresponding Author

Medial axis of a shape is the set of all points having at least two closest points on the shape boundary. Medial axis transform (MAT) is a shape descriptor including the medial axis together with the associated radius function of the maximallyinscribed spheres, which can be used to reconstruct the original shape. There has been strong evidences on the importance of medial axis on human's perception of shapes. For example, physiologists have found that neurons in the primary visual cortex (V1) show strong response to the 2D medial axis of a textured figure [Kimia, 2003], and neurons in the inferior temporal cortex (IT) encode 3D medial axis information [Hung et al., 2012]. Despite the important links between MAT and human cognitive system, there is still no study of 3D deep learning methods from the perspective of MAT, to the best of our knowledge. In this paper, we integrate the MAT of 3D shapes into the design of deep neural network, called MAT-Net, for 3D shape recognition.

In Q-MAT [Li et al., 2015], the MAT is approximated by a medial mesh, which is a 2D simplicial complex consisting of spheres, edges, and triangle faces. A sphere is expressed as a four-dimensional vector: position coordinates (x, y, z) and radius (r). The medial mesh gives a linear approximation to the true MAT through linear interpolation of the spheres along its edges and faces. Q-MAT [Li et al., 2015] proposes a method for simplifying an initial medial mesh to obtain a geometrically accurate and structurally simple MAT representation. Figure 1 shows an example of simplified medial mesh.

There are several difficulties that we need to address when designing and exploiting MAT-Net for 3D deep learning.

1. Deep learning needs large data set for training, but there is no MAT data set with a large number of samples. ModelNet40 [Wu et al., 2015] is one of the most popular data set on 3D object classification. Converting it to MAT representation is a non-trivial task. This is because MAT computation often needs closed manifold mesh surface. In ModelNet40, a lot of shapes are not watertight or are non-manifold. We repaired the meshes of majority objects in ModelNet40, and used Q-MAT to construct an open MAT data set called ModelNet40MAT for research community.
2. Similar to point clouds, the medial spheres (x, y, z, r) are unordered and cannot be directly input to typical CNNs. PointNet [Qi et al., 2017a] provides a solution for feature extraction of point clouds or other coordinatebased representation. Except for position coordinates (x, y, z), other local features (e.g. radius r of sphere as in our case) may be added as additional dimensions.
3. Another difficulty is local feature extraction from its topological structure. Although the medial sphere already expresses the local volumetric feature by its radius, it is better to extract different resolutions of local features from these spheres. A convenient method is to use the strategy in PointNet++ [Qi et al., 2017b] to sample and group neighboring spheres around a given center sphere. However, this method still cannot utilize the topological structure of MAT.

In this paper, we propose two facilitating modules: GroupMAT and Edge-Net. The Group-MAT groups the unordered spheres into a regular local data structure by referring to their edge information. Then Edge-Net is designed to extract features of local shape. The idea is to use max-pooling function to select the max response sphere features from the neighbor spheres. The detailed description is given in Section 3.3.

The contributions of this paper are as follows:

• We present the first deep neural network architecture that can learn the features of MAT, for 3D object recognition.
• By utilizing MAT's edge information, we design GroupMAT and Edge-Net modules to capture local features from its topological structure, which achieves remark-
• able performance on 3D shape classification task, even for MATs with very few number of spheres only.
• We construct an open MAT dataset: ModelNet40-MAT, by repairing the majority of 3D models in ModelNet40.

2 RelatedWork

2.1 Shape Representation for 3DAnalysis

Hand-Crafted Features. 3D shapes can be represented using either histograms or bag of features models, such as point feature histograms and normal histograms. Other representations include Light Fight Descriptor [Chen et al., 2010], Heat Kernel Signatures [Bronstein et al., 2011], and Spherical Harmonics [Kazhdan et al., 2003], to name a few.

Voxel Grids. 3D ShapeNets [Wu et al., 2015] uses convolutional deep belief network to learn probability distribution of binary information on 3D voxel grids. Similar to regular data in 2D images, voxel grids are proposed to represent 3D shapes because they are compatible with 3D convolutional neural networks. A similar approach was proposed in VoxNet [Maturana and Scherer, 2015]. VolumetricMVCNN [Qi et al., 2016] and FusionNet [Hegde and Zadeh, 2016] also combine the voxels and images. Using voxel grid representation achieves good results on a variety of recognition tasks. However, it is constrained by the grid resolution and computational cost.

• 2D Images. By taking advantages of pre-trained 2D convolutional neural networks [Krizhevsky et al., 2012], multiview methods [Su et al., 2015; Qi et al., 2016; Li et al., 2018] have achieved excellent performance on shape classification tasks. PANORAMA-based methods [Shi et al., 2015; Sfikas et al., 2017] extract the panoramic representation that preserves feature continuity of the 3D models and achieves a performance above or comparable to the state-of-the-art.

Kd-tree and Octree. Kd-Net [Klokov and Lempitsky, 2017] uses a kd-tree structure to form a computational graph, and computes a sequence of hierarchical representation. OCNN [Wang et al., 2017] presents an octree-based convolutional neural network, which represents the 3D shapes with octrees and performs 3D CNN operations on the sparse octants occupied by the surfaces of 3D shapes. The octree structure stores the octants information computed from surfaces. Then it can be input into the common deep network to realize shape analysis tasks including object classification, shape retrieval, and shape segmentation.

2.2 Feature Capturing on Point Clouds

PointNet [Qi et al., 2017a] and PointNet++ [Qi et al., 2017b] are the pioneering methods to directly process point cloud by utilizing symmetric function for disordered input. Although PointNet has excellent result on point cloud learning, it ignores the features extraction of local structures. PointNet++ proposes a set abstraction level to extract multiple scales of local patterns and combine them intelligently according to local point densities. It constructs local region sets by finding "neighboring" points around the center points. Inspired by this idea, PointCNN [Li et al., 2018] proposed

X-Conv operator that weights and permutes input points and features before they are processed by a typical convolution. GraphCNN [Wang et al., 2018] also recomputes a graph by using nearest neighbors in the feature space produced by each

neural network layer.

3 The Method

3.1 SimplifiedMedial Mesh

Q-MAT [Li et al., 2015] uses quadratic error minimization to compute a structurally simple, geometrically accurate, and compact simplicial complex representation of the MAT. A triangle mesh Ms, called medial mesh is used to approximate the MAT of a 3D shape S. Each vertex si of Ms represents a medial sphere and is denoted as a 4D point s = (x, y, z, r)⊤ which contains the center (x, y, z)⊤ and radius r of the sphere. eij is the edge of Ms between two medial spheres si and sj, in which case si and sj are called neighboring spheres.

Each edge of the medial mesh defines an enveloping volume primitive. The primitive given by the edge eij= {si, sj} is swept by the family of spheres defined by the linear interpolation of si and sj, that is, (1-t)si+tsj, t ∈ [0, 1]. It comprises two spherical caps joined by a truncated cone, called a medial cone. A medial cone can be seen as a part of a 3D shape, such as the human arm. Meanwhile a medial sphere may have several edges connecting with other medial spheres. All composed medial cones can express various shapes. We call si and all of its neighbor spheres as the neighbor data. Experiments show that using neighbor data of MAT can improve classification accuracy remarkably.

As shown in Figure 1, the MAT sampled and interpolated with a few medial spheres can still represent a 3D object very well. The question is how to use these data for designing an appropriate architecture of neural networks.

3.2 MAT-Net Architecture

Our full network architecture is visualized in Figure 2. The inputs of MAT-Net include medial axis sphere information and edge information. The sphere information is represented

by an N × 4 matrix:

where N is the total number of spheres, i is sphere's index, and si = (xi, yi, zi, ri)⊤. The edge information is represented by two N × K matrices. One is called Edge Index Matrix:

where dik is the index of the k-th neighbor sphere of si. We set the number of neighbors to be a constant K. If a medial sphere's number of neighbors is less than K, we set the redundant dik = -1. Another one is called Edge Mask Matrix:

If dik ≥ 0, then mik = 1; otherwise mik = 0. Figure 3 shows the illustration of these two matrices.

As shown in Figure 2, the medial spheres are processed into two branches. The top branch is similar with the original PointNet. The Spatial Transformation module can predict an affine transformation matrix by neural networks and directly apply this transformation to input data. It aligns all input set to a canonical space before feature extraction, which improves the classification performance. Feature Transformation extends this idea to the alignment in the feature space. To be exact, Transformation module learns a K × K feature map from N ×K input features. Then multiplies the N ×K input features and K×K feature map, and get a transformed N ×K features. This performs better than using N ×K input features directly. Feature Transformation just has lager K value than Spatial Transformation. After transformation, we use multiple layer perceptrons and max-pooling to obtain a feature vector fsphere.

In the bottom branch, we utilize topology structure that groups the neighbor data according to Edge Index Matrix and Edge Mask Matrix. Group-MAT constructs a N × K × 4 sphere tensor T by filling medial spheres to their corresponding positions. This operation is shown in Figure 3. The K×4 matrix Ti, i = 0, · · · ,N - 1 can be seen as a local shape patch centered around sphere si. Let us use δ = si - sj to denote the offset between the spheres i and j. We define Edge Label Vector (ELV) to be: lij = (δx, δy, δz, δr, ri, rj, ‖δ‖)⊤. Here the dimension of ELV is E = 7. We construct an ELV tensor that is of dimension N × K × E to represent local neighbor information of all spheres [Simonovsky and Komodakis, 2017]. Then we use two sub-branches with EdgeNet to learn local shape's features. After Feature Capture Module, we obtain two feature vectors: fgroup sphere and fgroup elv. Then the three features fsphere, fgroup sphere, and fgroup elv are concatenated into global features. Finally MAT-Net uses fully connected networks and soft-max layers to classify these features.

3.3 Group-MAT and Edge-Net

Suppose the sphere si has Ki neighbor spheres. In order to extract features from a local shape centered around si, a simple and convenient way is to group the neighbor spheres into a Ki × 4 matrix. We can extract a feature map by using a Ki ×4 kernel. But in the medial mesh, spheres have different number of neighbors Ki, thus a fixed-size kernel cannot be applied directly. We choose a large enough number K for all spheres (i.e. Ki ≤ K), and then fill the redundant value of the kernel with 0 if Ki < K. In this method, a K × 4 kernel can be used to represent the neighbor data of each sphere. Obviously, the neighbor data of different spheres have different numbers of filling elements. In addition, the spheres in the neighbor data do not have a reasonable order.

We treat a local shape as a K × 4 matrix with some filling value of (0, 0, 0, 0). As shown in Figure 3, Group-MAT

groups the spheres by referring to Edge Index Matrix and reshapes si's local shape data into a K × 4 matrix Ti. Then Edge-Net uses a kernel w of size 4 × 1 and bias vector b of size K × 1 to compute a feature map:

We use rectified linear unit as activation function to insure that Fi ≥ 0. In Figure 3, F0 = (f0, · · · , f4). Directly using max-pooling operation will fail to extract maximum responsive feature Fi,max because of those Fi,r where r corresponds to the filling entries, i.e., di,r = -1. For example, f4 of Figure 3. In order to solve this problem, we make an element-wise product between Fi and Edge Mask Matrix Mi, to let Fi,r = 0 for all filling entries r. Finally, by using max-pooling we get Fi,max from the neighbor data of si:

Since multiple convolution kernels are used, different kernels make different maximum responsive sphere features. This means that the local features of neighbor spheres can be represented as a set of maximum responsive sphere features from all feature maps. Our following experiments show that using Group-MAT and Edge-Net greatly improves the classification performance.

4 Experiments

4.1 Datasets

We evaluate MAT-Net on ModelNet40-MAT (rigid object) and SHREC15 [Lian et al., 2015] (non rigid object).

• ModelNet40-MAT: ModelNet40 is a popular 3D data set to verify the classification capability of 3D deep learning methods. To prepare the input MAT data for our MAT-Net, we need to compute MAT for the 3D data in ModelNet40. The MAT computation typically needs the 3D surface to be uniformly sampled, and be

a closed manifold. But the majority of 3D models in ModelNet40 do not satisfy these requirements. Consequently, Q-MAT [Li et al., 2015] can not be applied directly to compute MAT. We successfully repaired 83.2% of all 3D models in ModelNet40 and constructed a MAT data set, named ModelNet40-MAT, which has multiresolution MAT data for each 3D model.

• SHREC15: The database has 1200 watertight meshes which are equally classified into 50 categories. Each category contains 24 shapes which generated from an original 3D shape by implementing various pose transformations. Because all shapes are watertight and manifold, we can directly generate simplified medial meshes by Q-MAT. We use five fold cross validation to acquire classification accuracy.

4.2 Mesh Repair

The repairing method is inspired by the virtual camera algorithm [Wang et al., 2017]. We first place several cameras on the external ball, and sample the first intersected point between the ray emitted by the camera the faces of the 3D model. The parallel rays are uniformly cast toward the object. In this way, we can delete the point whose normal is different from the ray direction to fix the normals of the faces. This method can fix most of faces. However, there could be some occluded surfaces inside the 3D model, no matter how many cameras are placed around it. So we use a dynamic cameraplacing strategy. If two intersected points of neighboring rays from the same virtual camera are far away from each other, there may be a gap on the faces of the model, so we can place the new camera in the further point position. This method generates surface samples that are more uniform and complete. Finally we use Poisson surface reconstruction to obtain a closed manifold surface from these samples.

Our ModelNet40-MAT has 10, 243 MAT objects in 40 categories, about 83.2% of the original ModelNet40. We use 8, 208 objects for training and 2, 035 objects for testing. For each 3D object, we use Q-MAT to compute the MAT data of different numbers of spheres: 128, 256, 512, and 1024. All medial sphere centers and radii are normalized into a unit ball. To ensure a fair comparison, all compared methods are run on the same 83.2% objects of ModelNet40.

4.3 Implementation Details

Our network is implemented with TensorFlow on an NVIDIA TITAN Xp. All experiments are trained with a large-enough number of neighbors K = 16. We jitter the initial medial spheres (with random translation of Gaussian distribution N(0, 0.008) and clipped to 0.01 to generate the augmented spheres. Edge-Net has only 1 convolution layer with output channel of 32. In group sphere and group elv subbranches, Edge-Net is also used after the Spatial Transformation module. Batch-normalization and relu activation are applied to other layers.

The first CONV module of Feature Capture Module has two convolution layers and the second has three convolution layers. Their filters size are {64,64,128,256,1024}. The convolution kernel size of the first layer is 1×4, and the rest are 1 × 1. FC module has two fully connected layers and filters size are {512,256}. The three branch features are 1 × 256 vectors. The concatenated feature is a 1 × 768 vector. The loss function includes cross entropy loss for classification and L2 loss of feature transformation matrix. The batch size of ModelNet40-MAT classification is 32, and 16 for SHREC15.

For fair comparison, we reproduced the representative 3D CNN methods on the same 83.2% objects of ModelNet40. The grouping method of PointNet++ is multi-scale grouping (MSG). The PointCNN is trained on modelnet x3 l4, which includes the configured network structure and hyper parameters. We generated the octree data, and rotated them to 12

orientations. The resolution of leaf octants is 643 . MVCNN is pre-trained on the ImageNet1K data set. We fine-tuned this model on multi-view data (views=12). The object classification results of all methods are computed without voting.

4.4 3DObject Classification

Table 1 compares the classification performance of different methods. We can see that even using only 256 medial spheres MAT-Net (fsphere) can get an accuracy better than PointNet's 90.2% and PointNet++'s 90.5% (without normals). By using three features simultaneously, MAT-Net (fsphere + fgroup sphere + fgroup elv) gets an overall classification accuracy of 93.2%. Compared with using only the sphere feature fsphere, adding the local shape feature fgroup sphere and fgroup elv produces improvements for accuracy, respectively. Note that the classification accuracy does not necessarily improve with the increase of MAT resolution. The low resolution MAT contains simple but concise topology, while in high resolution MAT the topology has redundant information. Thus, it will slightly affects the classification accuracy as shown in Table 1. It can be seen that the MAT resolution of 256 spheres produces the best results.

Sphere radius is an important characteristic of MAT, which encodes the volume of local shape. In order to explore the effect of radius for classification, we compare the performances of different resolutions of MAT without and with radius used. As shown in Table 2, by using only fsphere, the accuracy is improved by around 0.8%- 1.4% after using radius. As shown in Table 3, we compare the average class accuracies of three methods, and list the object classes with significant differences in classification accuracy. MAT-Net (3 features) greatly improves overall accuracy and average class accuracy. Only in very few object classes, as shown in the last two columns of Table 3, MAT-Net has slightly-worse accuracy than PointNet++. Here we use 1024 points and normals for PointNet++, and 256 spheres for MAT-Net. For the ambiguous category in ModelNet40, such as plant (confused with flower pot and vase), the result of MAT-Net is not very satisfactory.

4.5 Classification on 3DNon-Rigid Object

We test our method on randomly divided SHREC15 benchmark. As shown in Table 4, PointNet++ achieves excellent classification performance when using non-Euclidean metric space and intrinsic features (including wave kernel signature, heat kernel signature and multi-scale Gaussian curvature). However, with the spatial coordinates as input features, PointNet++ achieves a classification accuracy of 60.18%. MATNet gets a much higher classification accuracy even using the fsphere merely. The best classification accuracy of MAT-Net is 96.42% when concatenating the fsphere and fgroup sphere.

4.7 Running Time

We record the forward time with a batch size 5 and using TensorFlow 1.4 with a single NVIDIA TITAN Xp. The first batch is neglected since there is some preparation for GPU. As shown in Table 5, MAT-Net gets faster and without large accuracy reduction when using fspheres merely. Concatenating three branch features leads to best classification result but increases the running time a bit, since the forward propagation will be executed three times.

5 Conclusion and FutureWork

In this paper, we propose the MAT-Net architecture that extracts features of spheres and their topological structures from MAT of 3D shapes, which shows better performance on 3D classification task than state-of-the-art methods.

We would like to extend MAT-Net to explore other 3D representations with topology information. It is interesting to note that in our MAT-Net architecture, Group-MAT is used only once, and the neighbor index matrix is static. We would like to explore the dynamic updates of neighbor index matrix and the use of Edge-Net to learn hierarchical features.

Acknowledgements

This work was supported by the NSFC under Grant 61772301.

4.6 Feature Visualization

In order to explore the features that MAT-Net learned, we visualize the information that has been learned from maxpooling layer of Feature Capture Module. Max-pooling layer outputs a 1024-dimensional feature vector from 1024 feature maps of size N ×1. A feature map includes the features of N spheres. The max-pooling layer will find out the maximum features of all feature maps. These sphere features are input to fully-connected layers, finally affecting the soft-max layer. We call these spheres responsive spheres, which have contribution to classification. As shown in Figure 4, we count the indexes of responsive spheres from max-pooling layer, and color these spheres by their frequency. Large frequency spheres have more contribution to classification. In order to eliminate the occlusion between the spheres and make it easy to be visualized, in each row we only show the spheres whose frequencies are larger than a certain threshold. We can observe that each class object learns its unique features that are important for the classification.

In Figure 5, we show the responsive spheres from three types of features proposed in our MAT-Net. The second and third rows show that adding edge information highlights local structures, especially for frame structures of 3D objects. It partially explains why concatenating all three types of features gets the best classification results.