Hausdorff Point Convolution with Geometric Priors

Given an input feature vector $F=f(v)$ and a kernel vector $G=g(v)$, the discrete convolution writes as:

$$F*G=\sum_{u\in{U}}f(u)g(v-u)=\langle f(u),g(v-u)\rangle,$$

(1)

where $*$ denotes convolution operation, and $\langle\cdot,\cdot\rangle$ is vector inner product. Convolution is essentially a “sliding inner product” between the input feature $f(u)$ and the flipped kernel $g(v-u)$. Inner product measures the similarity between two vectors. The convolution response thus reflects a “sliding similarity” between the “shape” of $F$ and $G$.

In 2D convolutional layers of a CNN, the similarity is measured between a 2D feature map and a 2D filter for feature extraction. We hope to extend this concept of convolution to deep feature learning of 3D point clouds. We give a generalized definition of point convolution. Given a point $p_{o}\in P$ and its neighboring point set $Q$, and a given kernel point set $G$, we use a function $T$ to calculate the similarity response $\hbar$ between each other:

$$\hbar=T(Q,G),Q=\{p_{i}\mid\|p_{o}-p_{i}\|\leq r\},$$

(2)

where $r$ is the query radius. Hausdorff distance can be used for computing shape similarity. Given the neighboring point set $Q$ and a kernel point set $G$, the Hausdorff distance $H(Q,G)$ is adopted as the convolution function $T$:

$$H(Q,G)=\max(h(Q,G),h(G,Q)),$$

(3)

where $h(G,Q)$ and $h(Q,G)$ are called the narrow Hausdorff distance. Their formula is defined as follows:

$$\begin{split}h(G,Q)&=\max_{g\in{G}}\min_{q\in{Q}}\|g-q\|,\\ h(Q,G)&=\max_{q\in{Q}}\min_{g\in{G}}\|g-q\|,\end{split}$$

(4)

where $\|g-q\|$ is the Euclidean distance between point $g$ and $q$. Obviously, $H(G,Q)=H(Q,G)\leq r$, but $h(G,Q)\neq h(Q,G)$ in general.

If the kernel point set $G$ is defined in a spherical space, $G=\{g_{i}\mid\|g_{i}\|\leq r\}$, the neighborhood point set $Q$ and the kernel point set $G$ do not necessarily need a rigid registration, which means that Hausdorff distance measurement can be performed directly on the two point sets.

In fact, the Eq. (3) satisfies the important properties of point cloud convolutions described in [19]. For $Q=\left[q_{1},\ldots,q_{n}\right]$ and its permuted counterpart $Q^{\prime}=\left[q^{\prime}_{\pi_{1}},\ldots,q^{\prime}_{\pi_{n}}\right]$, it has point permutation invariance: $H(Q,G)=H(Q^{\prime},G)$. Besides, it is scale invariance after normalization as $H(Q,G)=H(rQ,rG)/r$ with the query radius $r$ being a given constant. Since $H(G,Q)\leq r$, $1/r$ is then the normalization factor. This means that a kernel shape can calculate neighboring shape responses at any scale or query radius. Figure 3 shows the result of calculation using the Eq. (3) on a 3D indoor scene. It can be seen that the vertical line kernel causes a notable response on the pole-like structures, while the plane kernel has a notable response on the ground. This result is very similar to the neuron activation of feature maps in 2D convolutional neural networks.

As a network layer, Hausdorff convolution layer should contain learnable weights which can be optimized via back propagation. Instead of computing the Hausdorff response directly, we opt to assign a weight corresponding to each shortest distance, and automatically adjust the length according to the attitude and distribution of neighboring points with input features. We split the Hausdorff distance operator into two parts: the shortest distance set and the distributive function (see definition below). The distance between a neighboring point $q_{i}$ and a kernel point set $G$ is defined as $d(q_{i},G)=\min_{g\in{G}}\|g-q_{i}\|$, and similarly the distance between a kernel point $g_{i}$ and a neighboring point set $Q$ is $d(g_{i},Q)=\min_{q\in{Q}}\|g_{i}-q\|$. Let set $D_{g}$ represent the set of distances from each point in $G$ to the set $Q$ as $D_{g}=\left[d(g_{1},Q),\ldots,d(g_{n},Q)\right]$, and $D_{q}$ be $D_{q}=\left[d(q_{1},G),\ldots,d(q_{m},G)\right]$, where $n=|G|$ and $m=|Q|$. Therefore, the Hausdorff convolution between $Q$ and $G$ can be written as:

$$\begin{split}H(Q,G)&=\max(\max(D_{g}),\max(D_{q}))\\ &=\max([D_{g},D_{q}]).\end{split}$$

(5)

Let us name a function $f$ satisfying $f(\{f(D_{g})\}\cup\{f(D_{q})\})=f(D_{g}\cup D_{q})$ a distributive function. $\left[D_{g},D_{q}\right]=D_{g}\cup D_{q}$ is the shortest distance set. It can be seen that the $\max$ function is a distributive function. However, the $\max$ operator is sensitive to outliers. To overcome this issue, many improved variants of Hausdorff distance has been proposed [5]. Among the variants, we found the Hausdorff distance in the cumulative form [13] is more appropriate for pattern matching. This modified Hausdorff distance is:

$$h(Q,G)=\sum_{q\in{Q}}\min_{g\in{G}}d(g,q).\\$$

(6)

In this case, Eq. (3) and Eq. (4) would also adopt accumulation operation instead of max operation. Let $\mathrm{sum}$ indicate the accumulation of elements in a set, it can be:

$$\begin{split}H(Q,G)&=\mathrm{sum}(\mathrm{sum}(D_{g}),\mathrm{sum}(D_{q}))\\ &=\mathrm{sum}([D_{g},D_{q}]).\end{split}$$

(7)

Obviously, the accumulation function is also a distributive function. We construct a shortest distance matrix $D_{\text{min}}$ to store the shortest distance set $D_{g}\cup D_{q}$:

$$D_{\text{min}}(i,j)=\left\{\begin{aligned} \|q_{i}-g_{j}\|,&&\|q_{i}-g_{j}\|\in D_{g}\cup D_{q}\\ 0,&&\text{otherwise}\end{aligned}\right.$$

(8)

where $1\leq i\leq m$ and $1\leq j\leq n$. The size of $D_{\text{min}}$ is $n\times m$.

The point convolutional network layer is to weight the elements in $D_{\text{min}}$, and the input feature of each point can also be considered as a distance weighting constant. Inspired by KPConv [33], we formulate the computation of Hausdorff convolution based on the shortest distance matrix $D_{\text{min}}$. For a input features $F_{\text{in}}\in{\mathbb{R}^{m\times c_{\text{in}}}}$, and an output features $F_{\text{out}}\in{\mathbb{R}^{c_{\text{out}}}}$, the convolution formula of the point convolutional layer is:

$$F_{\text{out}}=f(D_{\text{min}}F_{\text{in}}W),\\$$

(9)

where $W$ is the weight matrix with a size of $n\times c_{\text{in}}\times c_{\text{out}}$. It maps the features from input channel number $c_{in}$ to the output channel number $c_{out}$. The shortest distance matrix is a sparse matrix: $\|D_{min}\|_{0}\leq n+m$. Therefore, multiplying $D_{\text{min}}$ by the weight matrix $W$ approximates weighting each shortest distance as $w_{ji}D_{\text{min}}(i,j)$. Since distributive functions including $\max$, $\mathrm{sum}$, $\min$ are all differentiable, the Hausdorff convolutional layer is also differentiable. Figure 4 shows the architecture of a HPC layer. As can be seen, the shortest distance matrix is normalized before weighting. Normalization is to remove the scale factor: $\bar{D}_{\text{min}}(i,j)=D_{\text{min}}(i,j)/r$. In addition, since the Hausdorff distance measures the maximum dissimilarity between two shapes, for similarity response, the nonzero value should take $1-\bar{D}_{\text{min}}(i,j)$.

Hausdorff convolution is a general form of point cloud convolution operation. From the view of Hausdorff convolution, KPConv [33] is equivalent to computing a one-way similarity by using a self-defined measurement function (kernel function). PointConv [36] and RSCNN [20] are equivalent to matching with a kernel containing only one point at the center. PointConv uses density information to weight distance, while RSCNN adopts maximum distance.

Similar to common CNNs, we require multiple kernels (the point cloud $G$) to facilitate a powerful feature learning. This involves the design of kernel point generation and multi-kernel network structure.

For indoor scene segmentation, we use the public indoor point cloud dataset S3DIS [1] to compare our proposed HPC-DNN with KPConv [33], JSENet [11] and other state-of-the-art point convolution methods. S3DIS contains $271$ indoor rooms encompassing offices, corridors, etc. The 3D data were acquired with RGBD scanner, and the dense point cloud data is associated with RGB color information. Following the convention, we use the set of Area-1 to Area-4 and Area-6 for training, and the set of Area-5 for testing. Segmentation accuracy is measured by mean of intersection over union (mIoU).

Table 1 shows that our HPC-DNN exhibits a significant performance improvement for scene segmentation compared to other baselines. We achieve a $66.7\%$ for single kernel HPC and $68.2\%$ for multi-kernel HPC, which are both higher than KPConv [33] under the same configuration. In particular, the results of multi-kernel HPC-DNN achieves the state-of-the-art performance among all methods. Due to the high scanning quality of S3DIS scenes, the geometry of the objects is relatively complete. The multi-kernel HPC-DNN can effectively capture and enhance the geometric features of semantic targets.

SemanticKITTI [3] is a dataset of large-scale outdoor point clouds built based on the KITTI vision benchmark [6]. The data sequences in SemanticKITTI are composed of continuous frames of point cloud captured by LiDAR scanners without color information. Although a single frame of point cloud contains about $100$K points, they are usually scattered in a space of $160\times 160$ meters. Therefore, the point clouds are very sparse. Besides, due to the round scanning nature of LiDAR, the density of the point clouds is heavily anisotropic, which further increase the difficulty of processing and understanding. We use sequences 0–7 and 9–10 for training, and sequence 8 for testing. We again use mIoU to evaluate the prediction accuracy over the 19 categories in the dataset. Our method is compared to KPConv [33], PolarNet [40] and other baselines. The hyper-parameters, e.g., the query radius of each layer and the number of sampled points, are kept consistent across different deep networks.

Table 2 shows the scene segmentation result of our networks and other baselines. HPC-DNN and Multi-kernel HPC-DNN get an mIoU of $59.6\%$ and $60.3\%$, respectively, outperforming the state of the art KPConv. Although the point clouds of this dataset contain much missing data, HPC is still able to capture as much geometric information as possible, leading to improved understanding results.

We visualize the feature map of our HPC-DNN network after convolution, particularly the extracted features from different kernel shapes. Besides, we visualize the segmentation results of HPC-DNN on S3DIS and SemanticKITTI.

Figure 6 shows the feature maps of the same layer with different kernels on a S3DIS point cloud scene. In some feature channels, the features extracted from each kernel has obvious characteristics. In two different feature channels, the spherical kernel produces similar convolution response on the wall in the same direction(left sub-figure) and in arbitrary directions(right sub-figure), respectively. It shows that the network has learned directional information by spherical kernel. Meanwhile, the planar kernel strengthens edge structures. The vertical linear kernel is robust to the vertical walls with the same feature distribution. The center point kernel has a local strengthening effect on the point cloud associated with input features.

Figure 7 shows some results of scene segmentation on S3DIS. It can be seen that our method attains accurate segmentation results; it is especially good at distinguishing objects with geometry discrepancy. The segmentation error mainly comes from the semantic objects on the facade with similar planar shape. Figure 8 demonstrates the predicted labels by our proposed network on SemanticKITTI. As can be seen, small objects, e.g., vehicle, on road scene are well distinguished by our method.