{'fraction_non_alphanumeric': 0.027703374913905256, 'fraction_numerical': 0.012703757557205174, 'mean_word_length': 5.049768518518518, '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}}
EllipsoidNet: Ellipsoid Representation for Point Cloud Classification and Segmentation

Point cloud patterns are hard to learn because of the implicit local geometry features among the orderless points. In recent years, point cloud representation in 2D space has attracted increasing research interest since it exposes the local geometry features in a 2D space. By projecting those points to a 2D feature map, the relationship between points is inherited in the context between pixels, which are further extracted by a 2D convolutional neural network. However, existing 2D representing methods are either accuracy limited or time-consuming. In this paper, we propose a novel 2D representation method that projects a point cloud onto an ellipsoid surface space, where local patterns are well exposed in ellipsoid-level and point-level. Additionally, a novel convolutional neural network named EllipsoidNet is proposed to utilize those features for point cloud classification and segmentation applications. The proposed methods are evaluated in ModelNet40 and ShapeNet benchmarks, where the advantages are clearly shown over existing 2D representation methods.


Introduction
Point cloud is a widely used data structure that represents the 3D objects using an orderless list of scanned points. In recent years, tremendous research efforts have been conducted on point cloud pattern recognition in the field of automated driving [3,32,51,19,53,37,21] and indoor/outdoor scene recognition [40,41,46]. As concluded in Guo et al. [10], 2D representation learning is one of the promising approaches to extract local and global features from point clouds. 2D representations, including multi-view representation [44], spherical representation [37,3,58,32,51], and bird-eyeview representation [53,19], are applied to point cloud learning tasks because they benefit from 2D convolutional neural networks (CNNs), which are well studied in image learning tasks [11,42,14,26]. However, existing 2D representations methods either require point clouds from specific sensors (e.g., LiDARs [32,37,51] ) or have huge point loss rate without a sufficient study of impact to related applications [44,36]. Recent methods try to overcome those drawbacks by mapping the points near-losslessly [33] or mapping only local regions around target point in each time [27], which however are time inefficient. Thus, it is still an unsolved problem to apply an effective and efficient representation to a point cloud.
Motivation. Our work is motivated by the spherical representation, a popular representation method for LiDAR point cloud processing [32,31,37,58,51,3]. In LiDAR point cloud frames, points are near-uniformly distributed on a spherical space so that a LiDAR point cloud is projected to a 2D feature map with minimal point overlaps and void pixels in the feature map. Lyu et al. [31] compares several representation method on KITTI road benchmark [7] and finds that the spherical representation of a LiDAR frame is a well balanced solution between point usage and latent space usage. In general point cloud processing, however, a spherical representation may not work well since the points are usually not uniformly distributed in the spherical space. In our work, we extend the use of spherical representation in general point cloud feature extraction. The proposed representation method effectively organizes the points in a 2D latent space with minor point overlaps and minor limitations to the network processing. Additionally, the proposed representation method is time efficient comparing to existing methods [44,50,24,29].
Approach. To address the spherical representation of general point cloud issue, we extend the spherical representation to hierarchical ellipsoid representation by introducing the following schemes: (1) point cloud decomposition, (2) spatial transform, and (3) feature map completion.
Point cloud decomposition aims to split a big point cloud to several point partitions, in which local patterns can be better recognized and time efficiency can be improved. Spatial transform aims to generate a ellipsoid latent space that better fits the point partitions. Feature map completion is used to fill each pixel in the latent space with reasonable values to generate a dense feature map for further processing.
The ellipsoid representation of a point cloud outputs two items: a combination of 2D feature maps for point-wise features and a combination of feature vectors for ellipsoid-wise features. Targeting the classification and semantic segmentation applications, we further propose EllipsoidNet, a neural network based solution to process the ellipsoid representation of a point cloud. The network utilizes both the pointwise features and ellipsoid-wise features for point cloud classification and segmentation.
Performance preview. To demonstrate the effectiveness of our ellipsoid representation, we evaluate the proposed method in two point cloud datasets: ModelNet40 for classification, and ShapNet for segmentation. In the experiment, the proposed method achieves near state-of-the-art performance in both datasets, with the help of the proposed neural networks.
Contributions. In summary, our key contributions of this paper are as follows: • A novel representation method is proposed that represent point cloud in ellipsoid latent space. This method project a point cloud in dense 2D feature maps and works hierarchically for large-scale point cloud. Additionally, we explicitly present its impact to point cloud classification and segmentation application. • Accordingly, a novel neural network named EllipsoidNet is proposed to take advantage of the ellipsoid representation for point cloud classification and segmentation applications. • We evaluate the proposed representation method and networks in a point cloud classification dataset and a point cloud segmentation datasets, and present its effectiveness and efficiency.

Related work
Point cloud decomposition. Point cloud decomposition is widely used to separate the points to small partitions, reduce the computational complexity of point cloud learning, and enhance local pattern recognition. Lyu et al. [33] utilizes a modified Kmeans clustering to create balanced point cloud partitions, which significantly decrease the computational complexity of point cloud representation. ACD [25] proposed an approximate convex decomposition method that divides an 3D object into near-convex parts, which however requires object surface meshes and unable to apply directly to point clouds. Cvxnet [5] introduces a network architecture to represent a low dimensional family of convexes. Yu et al. [55] performs recursive binary decomposition to a point cloud and concatenate the features from all tree levels. Ψ-CNN [21], Kd-net [15], and TreeRNN [34] perform similar decomposition schemes for point cloud and graph learning tasks. In this paper, we take the Kmeans for point cloud decomposition since it is fast and generates a fixed number of point partitions.
Spatial transform. Spatial transform is used to normalize a point cloud and learn a robust feature extractor. Spatial transform is usually achieved by applying a 3D transform to each point, which results in 3D rotation, translation, or scaling to the target point cloud. PointNet [40] and Point-Net++ [41] apply two spatial transforms to the point cloud: a non-learnable transform that scale and transit the point cloud within a uniball, and a learnable transformer named T-net for better feature extraction. In the experiment, they show that T-net has a significant improvement to point cloud classification. Wang et al. [48] proposes a novel approach to learn different non-rigid transformations of a input point cloud for different local neighborhoods at each layer. They claim that spatial transformers can learn the features more efficiently by altering local neighborhoods according to the semantic information of 3D shapes regardless of variations in a category.
Feature map completion. Feature map completion is used to generate a dense feature map with no void pixels, which helps CNNs better extract local features. This method is frequently used for depth completion in LiDAR point cloud processing. FuseNet [4] learns to extract joint 2D and 3D features for depth completion, which results in a dense depth map from camera and LiDAR inputs. LodoNet [58] completes the depth map using its nearest valid depth values. Different from the nearest neighbourhood filling, InterpCNN [35] and TangentConv [45] perform the completion using Gaussian mixture. In other point cloud learning applications, FoldingNet [54] and AtlasNet [9] try to learn a latent vector space that cover the point cloud with 2D surfaces. In this paper, we propose to fill a dense feature map by projecting the nearest point in the point cloud to anchors in the ellipsoid latent space. Point cloud 2D representation learning. Point cloud 2D representation learning tries to project a point set onto a 2D latent space, from which 2D CNNs are adopted for feature extraction. Besides the methods that focus on LiDAR point cloud only [32,37,51], several universal methods are proposed to represent a point cloud in 2D space. There are two major approaches: projection based and learning based. Projection based approaches try to define a 2D surface in the 3D space and then projects the points to the surface. MVCNN [44] projects the points into multiple 2D plane space and concatenates the features from all 2D plane representations for point cloud classification. Similarly, in DeePr3SS [20], SnapNet [2] and TangentConv [45], the input point cloud is projected into multiple virtual camera views. Lyu et al. explores the use of graph drawing to project the point cloud into a single 2D space for segmentation purposes. To better represent the local geometry pattern in 2D space, FPConv [27] proposes a learnable method that projects the local region of each point onto a 2D image space in each layer.
Other point cloud learning methods. Besides the 2D representation learning, volumetric, graph, and structure are also widely used methods for point cloud representation learning. Volumetric-based methods [36,59,49,8] discretize the 3D space to voxels, to which 3D convolution based methods can be applied. Graph-based methods [50,43,18] connect the points to graphs and apply graph convolutions and poolings to them. Structure-based methods [55,16,23] decomposite a point cloud layer by layer into a tree, and apply point-wise convolutions and recurrent neural networks to it.

Method overview
Given a point cloud P ∈ R N ×3 and a 2D feature map I ∈ R M ×M ×C where N , M , C denote the point size, the feature map resolution and feature size, the ellipsoid representation of point cloud is to perform a projection f : P → I that maps the point cloud to a 2D latent space. Figure 2 illustrates the steps of this representation. For a large-scale point cloud with a complex shape, we further propose a hierarchical pipeline that performs the representation in multiple scales.
In this section, we firstly introduce the method in detail; secondly, we present the hierarchical scheme of this method for a large-scale point cloud with a complex shape; at last, we analysis the impact of this representation to point cloud classification and segmentation applications and illustrate its effectiveness and efficiency.

Approach
Given a point cloud P, the spherical representation is equivalent to constructing its circumsphere, mapping each point to it's nearest point on the sphere, and generating a feature map I by sampling on the circumsphere. However, this method has two disadvantages: (1) unbalanced projection, and (2) sparse feature map. Some point clouds are much longer radii along their major axis than that along the minor axis, which results in heavily overlapped projection onto the poles of the circumsphere and many void pixels in the other parts; the pixels in feature map are not always filled with 3D points, which results in void pixels that confuse the CNNs .
Tackling this two issues, we proposed a novel representation method that generates a dense feature map and reduce the overlaps. As illustrated in Figure 2, the method has two upgrades: (1) use ellipsoid surface instead of circumsphere, and (2) feature-map-orientated projection. The first upgrade is achieved by measuring the ellipsoid radius of the point cloud using the principal component analysis (PCA), and then scaling the circumsphere by the inverse of the radius. In this way, an ellipsoid surface of the point cloud is constructed that better fits the 3D shape. The second upgrade is achieved by tracing the nearest point of each pixel in the latent feature map and fill them into the pixel. By switching from point-cloud-orientated projection scheme to feature-map-orientated scheme, each point can be projected to multiple feature map pixels and all pixels can be filled with points. The algorithm is described in Algorithm 1.
By applying the ellipsoid representation, we successfully build the correspondence between the points in 3D space and the pixels in the latent space. Point-wise features and ellipsoid-wise features. The key novelty of the ellipsoid representation is that it outputs not only point-wise features but also ellipsoid-wise features. The point-wise features are organized as a feature map where extensive local features are included. The ellipsoid-wise features are organized as a feature vector containing the global features of the target point cloud.
Point-wise feature includes the point's x, y, z position in the 3D space, its relative position in the ellipsoid coordinate frame, and the pixel's position in the 3D space and its relative position in the ellipsoid coordinate frame. Since we have the correspondence between the points and the pixels, we manage to organize a 2D feature map I ∈ R M ×M ×C , where each pixel is a feature vector of point-wise features.

Algorithm 1 Ellipsoid representation
Ellipsoid-wise feature contains the position, orientation and radius of the ellipsoid that covers the point cloud.

Hierarchical representation
Ellipsoid representation is an effective way to extract local and global features from a point cloud. However, it is still difficult to represent a point cloud with a complex shape. To this end, we further proposed a hierarchical pipeline to generate the ellipsoid representation in multiple scales. Figure 1 illustrates the steps of a 2-level hierarchical representation. Given a point cloud P, we decomposite it into N c partitions denoted as P 1 , P 2 , ..., P Nc . After decomposition, we generate the ellipsoid representation of each partition. In multi-scale representation, we further decomposite each partition to even smaller partitions and generate ellipsoid representation (i.e., decomposite P 1 to P 11 , P 12 , ..., P 1Nc ).
In that way, we can extract point-wise features and ellipsoidwise features in multi-scales and feed them all into the neural network.
In this paper, we utilize the Kmeans solver for point cloud decomposition because it generates compact partitions and is time efficient.

Analysis
To analysis the performance of our ellipsoid representation, we manage to evaluate its impact to classification and segmentation on ShapeNet dataset. For qualitative evaluation, we test on an airplane point cloud and visualize results of spherical, single-scale ellipsoid and multi-scale ellipsoid representation. In Figure 3 our multi-scale ellipsoid representation better fits the point cloud, and has much more points mapped to the latent space.
Impact to classification and segmentation. To quantitatively evaluate the impact of ellipsoid representation to point cloud classification and segmentation, we generate the representations for all the 14007 point cloud objects in the ShapeNet training set and compare the point usage rate and maximum segmentation intersect over union (IoU). The point usage rate measures the percentage of points in the point cloud that are mapped to the feature maps. A representation with high point usage ratio is expected to keep more local pattern, which may further leads to better performance in classification and segmentation. The maximum segmentation IoU measures the instance mean IoU of the dataset if we have correct segment on feature maps. This metric values the upper bound of the segmentation performance.
In Table 1, we compare the between different representations with the same feature map size. We observe that our multi-scale ellipsoid representation has a significant improvement towards single-scale ellipsoid representation and spherical representation, which indicates that our proposed  In Table 2 we compare between multi-scale representation with different partition sizes, and in Table 3 we compare between representation with different feature map sizes. Clearly we see that more partitions and larger those metrics.   We further fuse the encoder outputs in each level by adding them together, and then send them to the next level after a max-pooling. In classification tasks, we add a classification head at the end of the encoder, and in segmentation tasks, we add both classification head and segmentation head. The input of the EllipsoidNet are point-wise features and ellipsoid features in all hierarchical levels. For classification tasks, the network outputs the object class estimation; for segmentation tasks, the network outputs object class estimation as auxiliary loss, and point-wise segmentation estimates in all levels.

Modules
Point-wise feature encoder. This encoder extracts the local features from point-wise feature maps. As presented in Figure 5 (a), we employ ResBlock inspired from ResNet [11] to Ellipsoid-wise feature encoder. This encoder fuses the ellipsoid-wise features in each point partition. As shown in Figure 5(b), we employ 1 × 1 convolution layers similar to PointNet [40]. The encoder outputs are directly added to the output of the point-wise feature encoder and the outputs of lower levels. Similar to the point-wise feature encoder, the feature vectors from each partition is processed in parallel.
Classification head. The classification head estimates the category of an point cloud object based on the extracted features. In point classification tasks, its output is the final result; in point segmenting tasks, its output serves as an intermediate result that helps the network training. This head is constructed by several fully-connected layers.
Segmentation head. The segmentation head estimates the category of each point in a point cloud. This head is not implemented for point cloud classification tasks. As seen in Figure 4, this head returns a segmentation map in each level, where we further estimate the point category. The segmentation head contains several multi-layer perceptrons (MLPs).
From network output to point cloud segmentation. The segmentation head outputs a segmentation map for each level. In order to get the point cloud segment from the map segment, we trace back the projected points from map segment according to the ellipsoid representation. For the points that is projected to multiple pixels in the segment map, we use the mean value of all the estimation. For minor points that are not projected to the segment map, we assign them according to their nearest neighbour in the point cloud with known segment labels. In this way the semantic labels of all points are estimated.

Datasets
The proposed ellipsoid representation and EllipsoidNet are evaluated in two dataset: ModelNet40 for classification, and ShapeNet for segmentation.
ModelNet40 dataset contains a 9840-object training set and a 2468-object testing set. Each object belongs to one of 40 classes and is sampled to 2048 points. Similarly, ShapeNet dataset contains a 14007-object training set and a 2874-object testing set, where each object belongs to one of 16 object classes and is sampled to 2048 points. In addition, each point in the dataset belongs to one of the 50 semantic class.
The metrics for ModelNet40 classification benchmark are overall accuracy (OA) and mean class accuracy (mAcc), and the metric for ShapeNet segmentation benchmark are the mean intersection over union (mIoU) in class level (class mIoU) and object level (instance mIoU).

Ellipsoid representation implementation
In our experiment, we use a 2-level ellipsoid representation, which means that we construct the ellipsoid for the entire point cloud (Level 0) and each of its partition (Level 1). By default, we set N c = 36, namely we decomposite the point cloud into 36 partitions. For each ellipsoid latent space, we project the points into a 32 × 32 feature map (M = 32). For point-wise features, we use the points 3D position in the ellipsoid coordinate frame; for ellipsoid-wise features, we use the orientation, the radii along each ellipsoid axle, and the position of ellipsoid center in the patent coordinate frame.
Taking advantage of the point cloud augmentation, we employ an end-to-end training scheme that rotates a point cloud, jitters, and generates an ellipsoid representation in each training step. For testing, we generate 1 representation for each object in all test sets.

Network implementation
In the experiment, the default implementation of the EllipsoidNet modules is as follows: (1) [47] and Scikit-learn 0.23 [39].
The statistics of the implementation for ModelNet40 and ShapeNet are listed in Table 4.

Training scheme
To train the network, we use the categorical cross entropy loss for both classification and segmentation tasks, and all auxiliary losses are equally weighted. In addition, we employ the Adam [13] optimizer with a 1 × 10 −4 learning rate. We trained the network for 2000 epochs with a 32-sample batch for classification task and a 4-sample batch for segmentation task due to GPU memory limitation.

Ablation study
Impact of features. To study the impact of point-wise feature and ellipsoid-wise feature to the point cloud learning, we manage to train and evaluate the network using point-wise feature only, ellipsoid-wise feature only and a combination of both features. All three input options are evaluated in ModelNet40 and ShapeNet datasets. From Table 5 we observe that EllipsoidNet with either point-wise features or ellipsoid-wise features achieves better results than PointNet, a baseline method that parses the point cloud without any representation. In addition, EllipsoidNet with both feature inputs results in near state-of-the-art performance in both classification and segmentation tasks, which indicates that the method provides a robust point cloud representation for general point cloud learning. Impact of decomposition. To study the impact of decom-   position to the point cloud learning, we apply the ellipsoid representation with different number of partitions. In Table  2 we compare some metrics in the representation level, here we implement the neural network and explicitly compare the performance in classification and segmentation tasks. Table  6 shows that more point partitions result in better performance in both applications. The impact of decomposition to the point cloud applications shares the same trend as the impact to point cloud representation.
Impact of latent space resolution. To study the impact of decomposition to the point cloud learning, we apply the ellipsoid representation with different feature map sizes. In Table  3 we compare some metrics in the representation level, here we implement the neural network and explicitly compare the performance in classification and segmentation tasks. As shown in the table, 32 × 32 feature map leads to the best result in both applications; a smaller feature map result in a significant drop in performance, perhaps it lost too much points during point cloud representation; a bigger feature map does not gain a significant improvement in point cloud learning, which shares the same trend of performance in point cloud representation in Table 7.

State-of-the-art performance comparison
Quantitative comparison in ModelNet40. In Table 8   existing works. Our work achieves near state-of-the-art accuracy in overall accuracy and the best in the mean accuracy for all shape classes. In addition, our work has much fewer floating point operations (FLOPs) than existing methods.
Quantitative comparison in ShapeNet. In Table 9, we compare the class mean intersection over union (class mIoU) and the instance mean intersection over union (instance mIoU) between ours and several existing 2D representationbased works. Our works achieves near state-of-the-art in both class mIoU and Instance mIoU. Again, our work takes much fewer floating point operations during network inference.
Qualitative comparison. For qualitative comparison, we visualize several segmentation results in ShapeNet dataset together with the ground truth and results from PointNet, and ours in Figure 6. It is clearly seen that our method has better segmentation on small parts.

Conclusion
In this paper we address the problem of point cloud classification and segmentation via 2D representation learning. To this end, a novel point cloud representation method is proposed that hierarchically projects the point cloud to a ellipsoid space. The method effectively and efficiently projects the point cloud into 2D latent space for local feature extrac-  Table 9: Result comparison (%) with recent works on ShapeNet. Numbers in red are the best in the column, and numbers in blue are the second best. class mIoU represents class mean intersection over union and instance mIoU represents instance mean intersection over union. The symbol '-' means not given. tion. In addition, a novel neural network architecture named EllipsoidNet is proposed to perform point cloud classification and segmentation from the proposed representations. We evaluate our method on ModelNet40 and ShapeNet, achieving near state-of-the-art performance on both data sets. In future works ellipsoid representation for point clouds scanned from the real scenes will be explored.