Point Cloud Resampling via Hypergraph Signal Processing

The widespread deployment of networked sensors and cameras is a critical element of IoT. In visualization applications, 3D point clouds provide efficient data representation of external surfaces for objects and their surroundings. Point clouds have found wide applications in recent years, including surface reconstruction [1], rendering [2] and feature extraction [3]. High data volume of point cloud representation poses challenges to data transport and storage. One important point cloud processing task involves resampling for reducing the data size in a point cloud while preserving vital 3D structural features. Point cloud resampling serves important practical applications such as segmentation, object classification, and data compression.

The literature contains a variety of works on point cloud resampling. A centroidal Voronoi tessellation based method in [4] can progressively generate high-quality resampling results with isotropic or anisotropic distributions from a given point cloud. The 3D downsampling technique based on a growing neural gas network developed in [5] deals with data outliers and can represent 3D spaces by an induced Delaunay triangulation of the input space. Importantly, graph-based resampling has exhibited attractive capability to capture some underlying structures of point clouds [6, 7]. For example, the work [8] focused on computationally efficient resampling and proposed several graph-based filters to capture the distribution of point data. Another graph-based example is a graph-based contour-enhanced resampling method presented in [9]. We also note a different, feature-based, approach to point cloud resampling based on edge detection and feature extraction. In [10], the authors presented a sharp feature detector using Gaussian map clustering on local neighborhoods. Bazazian and co-authors [11] extended this principle by leveraging principal component analysis (PCA) to develop a new agglomerative clustering method. This work establishes speed and accuracy improvement by analyzing the eigenvalues of covariance matrix defined by $k-$nearest neighbors.

Despite these and other successes, graph-based and feature-based resampling methods still need to overcome some limitations. For graph-based methods, each graph edge can only model pairwise relationships even though multilateral interactions of point data represent highly informative characteristics of 3D objects. For example, bilateral connections only partially represent multilateral relationship among multiple points on the same surface. Another open issue relates to the efficient construction of a graph for an arbitrary point cloud. Among feature-based methods, how to select adequate features and filter parameters remains a practical design challenge. The development of a general model with robust parameter selection remains an open problem.

There have been some reported successes at applying hypergraphs to model and characterize the multilateral interactions among multimedia data points [12]. Hypergraph consists of nodes and hyperedges. Since each hyperedge can include more than two nodes, hypergraph provides a more general tool in point cloud processing to model multilateral point relationships on object surfaces. Furthermore, as a generalization of graph signal processing (GSP) [13], hypergraph signal processing (HGSP) [14, 15] has enjoyed additional notable successes in processing point clouds for segmentation, sampling, and denoising [16, 17].

In this paper, we propose a novel 3D point cloud resampling method using kernel filtering based on hypergraph signal processing. Leveraging hypergraph stationary process, we first estimate hypergraph kernel basis for a point cloud. We further define a local smoothness with respect to high-pass filtering in spectrum domain for resampling. In order to test the model preserving property on complex models, we develop a simple method for point cloud recovery based on alpha complex and Poisson sampling. Our experimental results demonstrate the compression efficiency and robustness of our proposed point-cloud resampling method.

In this section, we introduce our kernel-based resampling method. Generally, our proposed method consists of three main steps: i) hypergraph spectrum construction, ii) Fourier transform, iii) high-pass filtering and resampling.

We first estimate hypergraph spectrum based on hypergraph stationary process. Shown in [17], a stochastic signal $\mathbf{x}$ is weak-sense stationary iff it has zero-mean and its covariance matrix has the same eigenvectors as the hypergraph spectrum basis, i.e., $\mathbb{E}[\mathbf{x}]=\mathbf{0}$ and $\mathbb{E}[\mathbf{x}\mathbf{x}^{H}]=\mathbf{V}\Sigma_{\mathbf{x}}\mathbf{V}^{H},$ where $\mathbf{V}$ is the hypergraph spectrum. We can estimate the hypergraph spectrum from the covariance matrix of three coordinates by assuming the signals to be stationary. Here, we use the same spectrum estimation strategy as [17], and consider the adjacency tensor as a third-order tensor which is the minimal number of nodes to form a surface.

We define a $k\times k\times k$ 3D cube as the kernel to define a local signal $\mathbf{s}_{i}$. For simplicity, we use a $3\times 3\times 3$ cube as the kernel in this paper, although larger kernel can facilitate flexibility in filter design at the cost of complexity. Let $d$ be the center distance between two nearby voxels in the kernel. A proper selection of $d$ should allow $\mathbf{s}_{i}$ to capture local geometric information. If $d$ is too small, only a few neighbors of the $i$-th point are included in the $\mathbf{s}_{i}$, leading to noise-sensitivity. If $d$ is too large, many neighbors are included in each voxel, which may lead to blurred local geometric information. A typical choice of $d$ is the intrinsic resolution $d^{(i)}$ of a point cloud. We place the kernel towards the bounding box of the point cloud in our experiment.

Let $\mathbf{s}=[\mathbf{X_{1}}\ \mathbf{X_{2}}\ \mathbf{X_{3}}]\in\mathbb{R}^{N_{k}\times 3}$ be the coordinates of the total $N_{k}$ voxel centers in the kernel. For our selected $3\times 3\times 3$ kernel, $N_{k}=27$. We then normalize the coordinates $\mathbf{s}$ to define a zero mean signal $\mathbf{s^{\prime}}$. By calculating eigenvectors $\mathbf{f}_{1},\cdots,\mathbf{f}_{N_{k}}$ for $R_{\mathbf{s^{\prime}}}=\mathbf{s^{\prime}}\mathbf{s^{\prime}}^{T}$, we can estimate hypergraph spectrum $\mathbf{V}=[\mathbf{f}_{1},\cdots,\mathbf{f}_{N_{k}}]$.

Next, for $i$-th point in the point cloud, its corresponding local signal $\mathbf{s}_{i}\in\mathbb{R}^{N_{k}}$ is defined according to the number of points in the voxel of kernel centered at point $i$. By focusing on 3rd-order tensors and signal energies in spectrum domain, we can utilize hypergraph spectrum to calculate a simplified-form of hypergraph Fourier transform $\hat{\mathbf{s}}_{i}$ as

For edge-preserving purpose, we would like to separate high frequency coefficients from low frequency coefficients in spectrum domain. Since the spectrum bases corresponding to smaller $\lambda$ represent higher frequency components[14], we can sort eigenvalues of $R_{\mathbf{s^{\prime}}}$ as $0\leq\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{N_{k}}$ with corresponding eigenvectors {$\mathbf{f}_{1},\cdots,\mathbf{f}_{N_{k}}$}. We can then devise a threshold $\theta$ for dividing high frequency components and low frequency components based on a sharp change between two adjacent eigenvalues.

Given a threshold selection of $\theta$, we could further define a local smoothness $\sigma(\mathbf{p}_{i})$ to select resampled points:

which is the fraction of high frequency energy.

Finally, we resample the point cloud by selecting points with smaller $\sigma(\mathbf{p}_{i})$, which corresponds to points containing larger amount of high frequency in the hypergraph. We summarize our algorithm as Algorithm 1. Since the resampled point clouds tend to favor high-frequency points, they often contain sharper features and are less smooth. Although the higher frequency basis vectors do not necessarily display a clear regular pattern, as shown in Fig. 2, they have larger total variation over the (hyper)graph, which are corresponding to sharper features. Interested readers could refer to [14, 13, 17] for a comprehensive discussion on the high frequency features in hypergraphs.

For an unorganized point cloud, the computational complexity of our method amounts to $O(N^{2}+N\log{N}+N_{k}(N_{k}+1)N+N_{k}^{3})$, whereas for an organized point cloud, the complexity order is $O(N\log{N}+(N_{k}^{2}+N_{k}+1)N+N_{k}^{3})$.

We now describe our experiment setup and present test results of the proposed resampling algorithm.

In this work, we developed a 3D point cloud resampling method using kernel filtering based on hypergraph signal processing (HGSP). Our proposed HGSP resampling is simple and effective. Experimental results demonstrated that our HGSP method outperforms traditional graph-based methods or feature-based methods such as edge detection in terms of robustness to the noise and model preservation. This work establishes HGSP as an efficient tool to model multilateral relationship and to extract features in point cloud applications.