HPGNN: Using Hierarchical Graph Neural Networks for Outdoor Point Cloud Processing

A common approach to reduce the point cloud density before processing is to use a voxel grid. PointGNN [4], SSCN [10], SegCloud [11] and GridGCN [12], use cubic voxel grids. They do not exploit the irregular distribution within a point cloud. Zhu et al.[7] propose a cylindrical voxel partition with asymmetric 3D convolutions as an improvement on regular voxel-based models. These methods voxelize the clouds at a single scale. As the point cloud gets larger and irregular, voxelization schemes to prevent abstracting out fine details are not explored.

We exploit the inherent cylindrical nature of LiDAR data following [7], to parametrise the 3D space using cylindrical coordinates ($r,\theta,z$). We create a scalable voxelization scheme where linear intervals of adjustable magnitude along the radial distance, azimuth angle, and vertical height define voxel boundaries. This creates larger voxels as the radial distance increases. In a sense, the voxel size defines the “sieve” through which we filter the highly dense LiDAR points. The voxelization is parametrised such that each cylindrical block corresponds to a representative “key point”. A key point is a point with the mean position of the points inside a given voxel. The key points thus formed will create the nodes of the subsequent graph.

Consider two cylindrical grids parametrised by ($r_{L},\theta_{L},z_{L}$) and ($r_{H},\theta_{H},z_{H}$); each with a different coarseness to sample the point cloud (Figure 2 (b), (c)). They form nodes of two graphs, corresponding to two levels of coarseness (Figure 2 (d)). We maintain connections between the two graphs so that each point in a finer layer may learn from a wider scope through its connection to the coarser layer. This enables to process a wider scope of the point cloud, while preserving structural information that would otherwise be lost through down-sampling. This idea may be extended to create more than two levels in the HPGNN.

Within the HPGNN, a graph $G=(P,E)$ would be constructed with $N$ points, where $P=\{p_{1},p_{2},...,p_{N}\}$ are the set of keypoints sampled at a particular level of coarseness. Considering two adjacent levels of coarseness, we define the low-level graph $G_{L}=(P_{L},E_{L})$, and high-level graph $G_{H}=(P_{H},E_{H})$. $P_{L}$ is formed from the smaller voxel size to learn fine details related to a locality. $P_{H}$ contains keypoints from larger voxels, to learn more global and structural features from the network. Each point is characterised by $p_{u}=(s_{u},x_{u})$, with a location vector $x_{u}$ and a feature vector $s_{u}$. Hyperparameters $d_{L}$ and $d_{H}$ are radii defining the edges between points $p_{u},p_{v}$ that form the set of edges $E_{i}$ for each level $i\in(L,H)$.

$$E_{i}=\{(p_{u},p_{v})\ |\ \Delta_{x}<d_{i}\}\hskip 5.69054pt,\hskip 14.22636pt\Delta_{x}=||x_{u}-x_{v}||_{2}.\$$

(1)

The two graphs $G_{L}$ and $G_{H}$ are connected based on the voxels that define their points. Each point $q$ in $P_{L}$ will connect with a point $p$ in $P_{H}$, if the voxel of $p$ encapsulates $q$. After defining two graph levels and the spatial connection between them, we construct a formalism to represent how learning is possible through these connections, with the “neural message passing” approach by Hamilton et al.[5, 13]. A node of the network has the aim of progressively refining its feature. In each iteration $t$, it uses its current feature vector and relative coordinates to generate a message/edge feature $e$ through a learnable message generating function $f(.)$.

$$e^{t}_{uv}=f(s_{u},s_{v},\Delta_{x}).$$

(2)

The destination vector aggregates the messages that are received from its neighbours using an aggregator $\mathrm{Agg}(.)$ and updates its feature vector $s$ through a learnable function $g(.)$. A separate aggregator converts features between $G_{L}$ and $G_{H}$ (down/up sampling).

Through design decisions, we strive for better GNN learning through an architecture that supports global and local message passing. Furthermore, an appropriate choice of aggregation functions, and strategies to handle neighbourhoods of varying density and similarity are considered. The following subsections refer to Figure 3 and describe the learning process within two adjacent levels, which could be generalized for $n$ layers.
Lower Graph: The GNN of $G_{L}$ has higher density by design, and most neighbours of a point correspond to the same object in the dataset. Therefore, most edges of $G_{L}$ connect nodes of the same label, giving a high homophily as described by Zhu et al.[14]. In $G_{H}$, two neighbour nodes usually correspond to different labels, and have less homophily. We use the $\mathrm{Max}$ function as the aggregator $\mathrm{Agg}(.)$ of features from neighbouring nodes. This has the advantage of not being prone to an over-smoothing which is common in Graph Convolution Networks with mean aggregation [15]. The use of $\mathrm{Max}$ function should be complemented by a preprocessing step of removing outlier points, to reduce the possibility of outlier features being aggregated into a node feature. After a feature is aggregated, the conventional approach is to use a multi-layer perceptron (MLP) to learn the function $g(.)$ and finally add $s^{\mathrm{t}}$ in each iteration $t$.

$$s^{t+1}_{u}=g(\mathrm{Agg}\{e^{t}_{uv}|(u,v)\in E_{i}\})+s^{\mathrm{t}}_{\mathrm{u}}$$

(3)

for each level $i\in(L,H)$. This creates a skip connection to ease learning and gradient flow as the networks get deeper. Specifically for GNN, it encourages a point feature not to deviate too far from its previous feature.
After $T_{1}$ iterations of message passing, $G_{L}$ has refined its features locally. Then points in $G_{H}$ aggregate $G_{L}$ features to initialise $P_{H}$ node features through a ”downsampling” layer. Learning in $G_{H}$ continues for $T_{2}$ iterations, after which $P_{H}$ points return the features to the corresponding $P_{L}$ points through an ”upsampling” layer.
Downsample: Consider a point $p=(s_{p},x_{p})\in P_{H}$ and the corresponding set of points $\{q_{1},q_{2},..,q_{i},..,q_{k}\}\in P_{L}$ through which edges between $G_{H}$ and $G_{L}$ are formed. Each $q_{i}=(s_{q_{i}},x_{q_{i}})$ has a learnt feature $s_{q_{i}}$ from the preceding $T_{1}$ iterations. This is concatenated with $\Delta_{x}=||x_{p}-x_{q_{i}}||$, and a function $h(.)$ learns the edge feature $e_{p,q_{i}}$ between $p$ and $q_{i}$.

$$e_{p,q_{i}}=h(s_{q_{i}},\Delta_{x})$$

(4)

The downsampled feature to $G_{H}$ is the aggregate of such edge features between the point $p$ and $q_{i},\ i\in[1,k]$. For aggregation, we use attention weights for each edge feature following an Attentive Feature Merging (AFM) scheme [16]. $\alpha_{i}$ is the attention weight for $e_{p,q_{i}}$. We give more representational power for the aggregation stage in the downsampling layer, since a feature representation of a larger volume should reflect the less homophilic nature of $G_{H}$. The aggregated edge feature is then transformed through the MLP for the downsampling function $D(.)$. $s^{0}_{p}$ is the initial feature of the point $p\in P_{H}$.

$$s^{0}_{p}=D\ (\Sigma\ (\ \alpha_{i}e_{p,q_{i}}\ )\ )$$

(5)

In the classifier MLP, we predict a multi-class probability distribution for each point. Since large point cloud data sets have class distributions that are severely imbalanced, we use a weighted cross entropy loss $L_{\mathrm{wce}}$ following [24]. For each class $c$, a weight $w$ is defined inversely proportional to the relative frequency of the class. When $w_{c}$ and $\hat{y}_{i}$ are the weight and predicted probability of the labelled class, at a point $i$ in a point cloud with $N$ points, we have

$$L_{\mathrm{wce}}=-\frac{1}{N}\sum_{i=1}^{N}w_{c}\ln(\hat{y}_{i}).$$

(6)

To further improve the mean Intersection-over-Union (mIoU) of the model using the Lovasz extension of the Jaccard loss, we follow [25] by using the Lovasz-softmax loss $L_{\mathrm{ls}}$. Adding an $L_{2}$ regularisation term $L_{\mathrm{reg}}$, the total loss for semantic segmentation is

$$L_{\mathrm{total}}=\alpha L_{\mathrm{wce}}\ +\beta L_{\mathrm{ls}}\ +\gamma L_{\mathrm{reg}}\ .$$

(7)

where $\alpha,\beta,\gamma$ are weights for each loss component.

Comparisons of mIoU scores on the SemanticKITTI benchmark with point-based and second generation models are shown in Table I and Table II.

SPGraph [23] is the highest performing Graph Neural Network model that has previously attempted semantic segmentation. Although previously mentioned point based models use ideas similar to GNNs, they focus on encoding and attentive pooling modules rather than neighborhood feature aggregation mechanisms. From the experiments it can be seen that by using the hierarchical structure for learning, we can retain local information to segment and differentiate between relatively smaller objects (e.g., motor-cyclist, bicyclist, and pole) as well as larger objects (e.g., car, terrain, and trunk). This shows our design decisions of preserving fine features while graph coarsening has been effective. Therefore, using MLPs in hierarchical levels greatly improves the baseline performance for the Graph-Neural Network implementation of the point-based learning scheme. To this end, we believe we are successful in improving the baseline of point-based GNNs that can be used for large scale point cloud processing.

It is noteworthy that our model has not used any of the above enhancements specifically tailored for improving semantic segmentation. We have used hierarchical learning to improve the underlying effectiveness of message passing inside a GNN.

In 2021, nuScenes-Lidarseg was released [9], with point-wise annotations making it suitable for semantic segmentation. Therefore, to our knowledge, point-based models mentioned in Section III-A have not been evaluated in this test bench publicly. The only available comparisons are with the second generation models. They use point-based models in their feature representation step. (e.g., second generation model PolarNet [27] trains a PointNet[17] upon which “ring convolutions” are operated.) Therefore, if our HPGNN, without any additional module, is performing competitively with such second generation models, as seen from Table III, we infer it is an improvement of the underlying point-based model. This validates the generalizability of HPGNN for large scale outdoor LiDAR point clouds.

Ablation studies are done using SemanticKITTI with the standard practice [2, 36] of reserving sequence 08 of the dataset for validations.

Increasing $T_{1},T_{3}$ shows improvements of $4.1$ mIoU. This suggests that refining and learning features at $G_{L}$ significantly improves performance with moderate reception at $G_{H}$.

HPGNN is used as a framework for learning features from a point-based representation of a point cloud. For computational feasibility, we use voxelization. As presented by [37], spatially uniform re-sampling has discretization errors, and this is evident from Figure 4 where the errors of segmentation are mostly at the boundaries.

As opposed to graph-resampling methods including Octrees [38], HPGNN requires dense graphs to achieve high resolution, which leads to spatial inefficiency. This is when redundant points of a dense point cloud are stored and processed that do not contribute for evolving new features. This is a limitation in HPGNN in the graph construction step. Although our idea of connecting local points with similar semantics for efficient representation is explored in a different approach by Hypergraphs[39], it is not entirely dependent on point distance.