{'fraction_non_alphanumeric': 0.025862391149979444, 'fraction_numerical': 0.014799865455768583, 'mean_word_length': 4.70046868342565, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RocNet: Recursive Octree Network for Efficient 3D Deep Representation

We introduce a deep recursive octree network for the compression of 3D voxel data. Our network compresses a voxel grid of any size down to a very small latent space in an autoencoder-like network. We show results for compressing 32, 64 and 128 grids down to just 80 floats in the latent space. We demonstrate the effectiveness and efficiency of our proposed method on several publicly available datasets with three experiments: 3D shape classification, 3D shape reconstruction, and shape generation. Experimental results show that our algorithm maintains accuracy while consuming less memory with shorter training times compared to existing methods, especially in 3D reconstruction tasks.


Introduction
While neural networks achieve excellent performance in various tasks in 2D vision, how to effectively process 3D data by neural networks has recently attracted more attention in both the computer vision and computer graphics communities. Unlike the unified representation of 2D images as pixels, there are many formats widely used for 3D data such as point clouds, volumetric voxels and surface meshes. Each of these formats has its advantages and disadvantages. Point clouds represent 3D data by unstructured points without imposing topological constraints. However, they bring difficulties in subsequent applications such as rendering and space navigation. Surface meshes are most widely used in graphics due to efficient rendering and modeling flexibility, yet their inherent graph structure makes it difficult, though not impossible, to process via neural networks. 3D volumetric voxel grids are the straightforward generalization of 2D pixels and are a natural representation of 3D space. But voxel grids are very memory intensive and memory requirements grow very fast as the size of the grid increases, making them difficult to apply to fine resolutions or large spaces.
In this paper we introduce RocNet: a recursive 3D autoencoder network that mimics the structure of an octree. As shown in Figure 1, a voxel grid is first converted to a standard octree structure until each node is homogeneous or a maximum depth is reached. RocNet recursively merges octants starting from the octree leaves, until the root is processed. In this way the whole octree can be represented by a compact 1D feature vector. Since there are a large number of empty leaves in an octree, our algorithm saves large amount of memory and computational time. Compared to traditional 3D convolutional networks, 3D convolution is only performed within octants in our recursive network arXiv:2008.03875v1 [cs.CV] 10 Aug 2020 hence is less computationally intensive. Memory savings arise from the octree structure which adapts to the geometry of the scene, allowing large empty (or otherwise homogeneous) volumes to be represented compactly.
RocNet is an end-to-end autoencoder that is a recursive, discriminative, and generative network that is primarily aimed at compressing 3D voxel structures for representation, discrimination, and generation. The main contributions of this work are: this is the first method to explore the combination of volumetric octree and recursive networks; near state-of-the-art compression ratios; near state-of-the-art recognition on ModelNet40; state-of-the-art computational and memory consumption efficiency; state-of-the-art reconstruction accuracy on ShapeNetCorev2 database.

Related work
The idea of using octrees to efficiently process sparse 3D data has been intensively explored in deep learning in recent years. These methods can be roughly classified into two groups: discriminative and generative networks.
Discriminative octree networks. Discriminative networks are designed to accomplish recognition tasks such as classification and retrieval. O-CNN [1] uses an octree-based 3D convolutional network by using fast shuffled key and hash table search. Their method significantly reduces the computational time and storage requirements for 3D convolution by restricting computations to occupied octants only. OctNet [2] uses an alternative octree-based convolutional network where a more efficient convolution is defined for octants. A major difference between RocNet and the other methods is RocNet performs convolution only within octants. Convolution is not performed across octants.
Generative octree networks. Generative octree networks are able to generate 3D data in an octree-like manner. Adaptive O-CNN [3] implements an advanced version of O-CNN which is able to generate models in adaptive patches. HSP [4] predicts high resolution voxel grids from images by using an octree up-convolutional decoder architecture. OctNetFusion [5] is the generative version of OctNet, which reconstructs dense 3D data from multiple depth images by predicting the partitioning of the 3D space. Similar to our method, OGN [6] also generates octrees, but their method is aimed at up-sampling from a coarse regular voxel grid and thus focuses on decoding only. In contrast, we seek to form an efficient latent space for storing grids of arbitrary size, where the latent space is not restricted to be grid-like.
Recursive networks. Our method is also related to recursive networks which were originally proposed as an effective tool for grammar tree parsing in natural language. In computer graphics, GRASS [7] employed recursive networks to implement a generative shape structure autoencoder. Their work focuses specifically on object structures and makes explicit use of object symmetries. RocNet focuses on volumetric representation and can also be used for generic 3D representations such as rooms or buildings. Another successful application of recursive networks is k-d networks [8] which use a k-d tree to hierarchically process 3D point clouds, whereas we focus on voxel representations.

Recursive octree networks
In this section we will describe the network architecture by which the octrees are encoded and decoded. The overall structure of the proposed network is shown in Figure 2. The network has a recursive structure that recursively merges 8 child nodes to form their parent node until the root node is encoded. The insight is that the recursive feature easily fits the hierarchical nature of octrees. Our network consists of 7 components: leaf encoder, node encoder, tree encoder, leaf decoder, node decoder, tree decoder and node classifier. The octree is encoded from the leaves up. The leaf encoder encodes the leaves and produces a multi-channel 3D code for each leaf. For each non-leaf node, the node encoder combines codes from each of its children until the root is reached, again producing a multi-channel 3D code for each node. Finally the tree encoder converts a multi-channel 3D code into a compact 1D feature vector. To produce an octree from a compact code, the corresponding decoders reverse the encoding process. The only difference is that we need to determine if a given node is an internal node or a leaf and the node classifier is used to make that determination. We describe the octree representation and each component in more detail in the following sections.

Octree representation
An octree decomposes a 3D space recursively until it contains homogeneous content (all voxels inside a leaf should be consistently occupied or empty) or a given maximum depth is reached. In the proposed algorithm, we adopt the octree representation as the input format of our neural network.
An example of an octree structure is presented in Figure 3. For simplicity, we illustrate a quad-tree on a 2D grid instead of an actual octree on a 3D grid. We define 4 types of octants: empty leaf, full leaf, mixed leaf and interior node as shown in Figure 3f. An octree can be therefore represented as two separate parts: tree topology and its mixed leaves. Empty and full leaves do not need storage and can be directly recovered from tree topology. Tree topology representations. To encode octree topology, we use a post-order Depth-First Search (DFS) ordering. As shown in Figure 3d, the octants of a 3 layer octree are serialized by the post-order DFS: it starts at the root node and goes as far as it can down its child nodes from left to right, then visit itself and backtracks.
Mixed leaf representations. We collect all mixed leaf nodes in an octree in the order defined above, forming a 4D binary matrix. In the example shown in Figure 3e, the maximum depth is 1 and two mixed leaf nodes are extracted. To clearly demonstrate the advantages of our proposed structure, we simply use binary occupancy encoding across all our experiments. However, other representations such as real-valued occupancy probability or the surface normal could also be easily integrated into our algorithm in this step.

Recursive octree encoder
Generally speaking, the encoders encode leaf nodes, interior nodes, and eventually the whole octree into features as shown in Figure 4a.
Leaf encoder. Explicit leaf nodes need to be converted into recognizable features before being fed into the recursive network. In comparison with a traditional recursive autoencoder [9] (RAE) that encodes nodes into 1D features, our method encodes a leaf node into a 4D feature with fixed dimensions using several 3D convolutional layers of kernel size 4 and stride 2. The number of channels of feature maps is set to 16, 32 and 64. We use the exponential linear unit [10] (ELU) function (f : x ∈ R → max(0, x) + min(0, e x − 1)) as the activation function and add a batch normalization (BN) layer after each 3D convolution layer. Our network is free of a pooling layer. Therefore the sequence of a leaf encoder is several layers of "3DConv + BN + ELU ". The leaf encoder therefore is a mapping: B k×k×k → R 64×4×4×4 , where B ∈ {0, 1}, k is the leaf resolution (we set k = 32 for voxels larger than 32 3 and k = 16 for 32 3 ), 64 is the number of output channels. Since there are a large number of empty and full leaf nodes, applying 3D convolution to them is unnecessary and time-consuming, hence we pass these leaves directly to the next stage without applying 3D convolutions. We call these "leaf skips" as shown in Figure 4a and 4b.
Node encoder. It first lifts the number channels of child nodes from 64 to 128 by a 1 × 1 × 1 sized kernel 3D convolutional layer denoted as φ : R 64×4×4×4 → R 128×4×4×4 and then merges the nodes into an interior parent node. The inverse of φ, denoted as ψ, is applied to the parent node which maps number of channels back to 64. We use "additive merging" for all encoders of this kind, that is, every child node is first applied with a 3D convolution followed by a batch normalization layer, and then added together to form the parent node: This encoder is applied recursively until the root node is encoded. Note that node encoders for different depth do not share weights.
Tree encoder. After obtaining the feature of the root node, the whole octree is encoded to a single feature map of 64 × 4 × 4 × 4. The tree encoder is applied to flatten the feature map into a single 1D feature vector. We achieve this by simply employing a 3D convolutional layer with kernel size 4 and stride 1. The number of channels is set to the dimensions of the feature vector. The tree encoder then is a map: R 64×4×4×4 → R dout . In our implementation d out is set to 80 across all experiments.

Recursive octree decoder
The decoders simply reverse the above process using transposed convolutions instead of convolutions.
Tree decoder. This decoder converts a 1D feature back to a 4D feature by a transposed convolutional layer and a non-linear activation layer ELU. To transform feature vectors back to the above defined dimensions, we use a kernel of size 4 and stride 1.
Node decoder. After decoding the tree we obtain the 4D feature for the root node. We then apply the node decoder to it recursively until leaf nodes are decoded. This decoder consists of a 3D convolutional layer for the node itself and a convolutional layer for each its 8 child nodes followed by a batch normalization layer as shown in Figure 4b. Note that node decoders for different depth do not share weights.
Leaf decoder. When a node is recognized as a leaf it will be decoded by a leaf decoder which recovers the features back to explicit binary occupancy voxel grids. Note that leaf skips will also be applied in the leaf decoder for efficiency, i.e. only leaves recognized as mixed need to be decoded. This decoder consists of several stacked transposed 3D convolutional layers of kernel size 4 stride 2 and padding 1. This operation will enlarge the voxel size from 4 to k which is the dimension of explicit representation we used for leaves. All layers are followed by batch normalization layers and ELU activation with the exception of the final layer which is activated by a sigmoid non-linearity without batch normalization.

Node classifier
A node classifier is a 4-category classifier trained during the decoding process in order to recover the octree topology. Note that the classifier is not involved in encoding, as at that stage the type of each node is known. This classifier labels each node one of the 4 aforementioned node types. It has the same layers as tree encoder except for an additional fully-connected layer. We use cross-entropy as the loss function. The node classifier is disabled during training and is only used for prediction in the testing stage. The predicted label is used to decide whether to stop decoding (empty/full leaf) or to decode using leaf decoder (mixed leaf) or node decoder (interior node).
Reconstruction loss. Decoded leaves are used to calculate the reconstruction loss and we use a weighted binary cross-entropy as the loss function: where t ∈ {0, 1} is the ground-truth occupancy value and o ∈ (0, 1) is the output of the leaf decoder for each individual voxel. The weight parameter α is employed because the number of empty voxels is usually much larger than occupied ones. In most cases, α should be larger than 1 for elimination of false negatives. In our implementation we use α = 5 across all experiments. The reconstruction loss of an octree is the sum of the reconstruction losses across all its mixed leaves.

Complexity analysis
In this section we analyze the model size as well as the computational time and space complexity of our proposed method both analytically and empirically.
Generally speaking, our method benefits from the recursive structure and hence can be regarded as a lightweight and scalable model. With the increase of input voxel resolution, the number of trainable parameters of our model increases linearly with respect to the logarithm of input/leaf resolutions: O(log(N/k)) where N is the input resolution and k is the leaf size (both should be a power of 2). Table 1 shows the model size of our method (right column) and other comparison methods (left column). Since all the other methods were designed specifically for classification, we show the number of trainable parameters of the encoder part of our model for a fair comparison. The total size of our model is approximately twice that shown as the encoder and decoder have roughly the same architecture. For our method we present models for 6 different resolutions. Each method is labeled as RocNet-N -k and k is set to 32. RocNet-256-32, for instance, accommodates an input voxel grid of size 256 × 256 × 256. The actual number of trainable parameters shown in Table 1 coincides with our analysis. Among the comparison methods, VoxNet [13] and LightNet [14] are also lightweight yet their models only consider a fixed voxel grid of 32 × 32 × 32 as they were designed for classification. This resolution should be adequate for a classification task. For more resolution-intensive tasks such as reconstruction and generation, it will lead to severe artifacts and imperfection.
The space and time complexity of our method are O((N/k) 3 ) and O(log(N/k)) respectively. The space complexity roughly depends on the number of mixed leaves which, in worst case, is (N/k) 3 Table 2: 3D shape classification accuracy on ModelNet40 dataset. Voxel-based methods are followed by their tested resolution. RocNet is followed by its resolution and the leaf size.
have a very small population in all leaves. Therefore our method enjoys a moderate memory consumption even for 256 × 256 × 256 volumes, which easily fits on a modern GPU. Since the nodes within the same depth can be processed in parallel, the computational time for an octree is related to its depth, which is 3 log 8 (N/k).

Experiments and comparisons 4.1 Experiments setup
We evaluate our proposed RocNet by three experiments: 3D shape classification, 3D shape reconstruction and 3D shape generation. The implementation of our algorithm is based on PyTorch [17] and TorchFold [18] for dynamic batching. All experiments were done on a server with Intel Core i7-6700K CPU (4.00GHz) and a GeForce GTX Titan X GPU (12GB memory). We set leaf size k = 16 for voxel size N = 32 and k = 32 for all the other input resolutions across all experiments. To clearly demonstrate the advantages of our proposed method, we simply use binary occupancy voxels as input in all experiments. However, the performance can be further improved by employing a more informative input format such as surface normal and truncated signed distance function. Variations of input formats can be easily integrated into our network.

3D shape classification
Dataset. We perform the classification task on the ModelNet40 dataset [12]. This dataset contains 12,311 labeled CAD mesh from 40 categories. It is split into training (9843) and testing (2468) sets and the training set is augmented by rotating each sample 12 times along its upright axis uniformly. We generate voxel representations at four different resolutions for each of the samples: 32, 64, 128, and 256 cubes.
Network architecture. We simply use the encoder architecture as feature extractor followed by an additional fullyconnected layer, a dropout layer and a softmax layer. The input of the fully-connected layer is the output of the tree encoder defined in section 3.2.
Results and discussion. The classification results are shown in Table 2. We compare our method with 4 other alternatives: 3DShapeNets [12], VoxNet [19], Geometry image [20] and O-CNN [1], all of which are voxel-based methods with the exception of Geometry image.
Similar to previous literature, our method achieves the best result when input voxel resolution has size 32 and the performance begins to drop slightly when the size increases. The reason is that categories in ModelNet40 are visually different even at a low resolution, hence less detail is required and 32 3 is adequate for distinguishing one class from another. Higher resolution probably leads to overfitting.
Our method has inferior accuracy compared to that of O-CNN [1], which is partly due to the influence of the input data. In their implementation they used more informative surface normals as input while in our experiments, we simply use the binary occupancy voxel grid. They have shown in their paper that there is approximately a 2 percent drop in accuracy by using binary input. Another reason is that instead of using max-pooling, we employ convolution of stride 2 in the leaf encoder which could lead to fewer patterns being captured. We did an additional experiment where we substituted the 2-stride convolution with 1-stride convolution followed by a max-pooling layer. The accuracy of 32 3 increases from 85.5% to 86.7%. However, this substitution increases the memory requirements of the network.
Note that focus of this paper is mainly 3D shape autoencoder, we show in this section that by simply using the encoder our method can be easily converted into a lightweight classifier with good accuracy.
Training protocol. We use batchsize=50 in training. The average total number of iterations is around 300 for each class.
Training takes approximately 20 hours for a class containing 2000 samples in 128 3 resolution. For both ShapeNet-Car and ShapeNetCorev2 we split training and testing sets by 80% and 20%, respectively, as done by [22] and [3]. Note that the ground-truth node type is used in the training stage to choose the correct decoder. In the test stage, the type of a node is predicted by the trained node classifier.
Measurements. We show the qualitative reconstruction results in Figures 5 and 6. For more visual reconstruction results please refer to the supplementary materials. For quantitative measurements, we use intersection over union (IoU) for ShapeNet-Car and Chamfer distance for ShapeNetCorev2 dataset. This is mainly for the purpose of comparison with existing methods. Using IoU is straightforward since our network produces binary voxels. Chamfer distance is usually used for evaluating the performance of surface-generating methods such as [22,3]. To compare with this group of methods, we densely sample a set of points, P, from the boundary voxels and a set of points, G, from the ground-truth mesh. The Chamfer distance is calculated as: Results and comparisons. Figure 5 shows that RocNet produces fewer missing regions (the wheels) compared to O-CNN and patch-based O-CNN, which explains why RocNet outperforms the rest in the following quantitative analysis. We also observe the reconstructed shapes are more blurred than the ground-truth voxels (see the details of wheels at 128 3 resolution in Figure 6).
IoU accuracy of the ShapeNet-Car dataset and the that of OGN [6] is shown in Table 3 and computational requirements are shown in Table 4. The Chamfer distance results of ShapeNetCorev2 are shown in Table 5. Table 3 and 4 shows that RocNet outperforms OGN at all three resolutions with lower memory consumption and faster execution time. Similar to OGN, we also test our algorithm in two modes: with and without octree structure known.
In the octree-prediction mode (named as "RocNet-p"), the type of each node is predicted by the node classifier while in octree-known mode (named as "RocNet-k"), the octree structure is given during decoding. Specifically, the node classifier is disabled in octree-known mode. Intuitively, less information is encoded in octree-known mode hence higher reconstruction accuracy should be achieved. However, as shown in the last two column of Table 3, these two modes have very close accuracy. This implies that the capacity of the hidden representation is sufficient to store both the octree  topology and the leaves. This validates our choice of a 64 × 4 × 4 × 4 voxels for the hidden representation since using a higher resolution would not lead to a significant increase in accuracy. The rest of our experiments use prediction mode only.
We also report the GPU memory usage and the computational time for one single training iteration in Table 4. It coincides with the complexity analysis in section 3.6. For all three resolutions tested, our algorithm consumes far less memory than OGN. We also observe our algorithm has a larger relative increase compared to OGN. According to the complexity analysis, the memory consumption increases cubically with N . We expect our algorithm to take more memory with larger resolutions. However, it is still tractable when processing a 512 3 voxel grid in our experiments.    [22]. Results of O-CNN and Adaptive-OCNN are provided in [3].
Adaptive O-CNN and AtlasNet. It is worth noticing that since RocNet generates voxels instead of a mesh, there is an intrinsic inaccuracy between the cube-like voxels and the smooth mesh. Mesh-based methods such as Adaptive O-CNN and AtlasNet do not suffer from this drawback. We expect our method to perform even better with a patch-based representation, which is an area for future work.

3D shape generation
In this section we present the results of model generation using RocNet. Figure 7 shows 5 generated models by RocNet autoencoder trained on ShapeNet-Car dataset.
We generate new models by randomly sampling within the convex hull of the trained samples in 80D feature space. Please note that the octree topology is generated on the fly in this experiment since it is impossible to obtain the ground-truth which exists in reconstruction task. From Figure 7 we could observe that RocNet is able to establish a semantically plausible shape manifold where each generated model can be visually identified as a car. We also present the corresponding training model closest to the sampled point in feature space. Some generated models are very similar to existing models such as the first example. There also exist some examples where there are visible differences between existing ones. This indicates that RocNet has captured some semantic information from training samples.
We also notice that the generated models are more blurred than existing ones such as the absence of the details of the wheels. This is a general problem an autoencoder suffers from without an adversarial (GAN [24]) term. Currently our RocNet has the structure of a standard autoencoder. It would be possible to combine our current loss function with an adversarial loss in the future.

Conclusion and future work
We propose a recursive octree-based network which encodes and decodes octrees by either recursively merging or producing octants. Our key insight is the recursive nature of the proposed network fits the hierarchical feature of octrees well. By using an octree representation we are able to save a large amount of storage and computational time and higher accuracy is achieved compared to existing methods for 3D shape reconstruction and generation. The architecture also provides good results for 3D shape classification. We demonstrated the advantages of our method by three experiments. The complexity of our method is analyzed both theoretically and empirically.
For future work we would like to make variants of RocNet by using more advanced network structures such as variational autoencoder (VAE) and generative adversarial networks (GAN). We believe by adding a GAN term RocNet will be able to generate more realistic models with more details. RocNet then can be applied to more realistic 3D content generation tasks.
Another promising improvement to RocNet is to use more input information. As suggested by existing work [25,1], using more informative input information such as normals or a truncated signed distance field leads to better performance.
RocNet is compatible with arbitrary input formats as long as it dose not violate the sparseness of 3D data. This sparseness arises naturally from the fact that surfaces in the world form manifolds in 3D space. We will also explore the possibility of directly generating meshes as output of the network.