{'fraction_non_alphanumeric': 0.030784050929803988, 'fraction_numerical': 0.007497068185625733, 'mean_word_length': 4.967758060484879, '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': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Point Cloud Segmentation based on Hypergraph Spectral Clustering

Hypergraph spectral analysis has become a significant tool in data analysis due to its power in processing complex data structure. In this work, we investigate its efficacy for 3D point cloud segmentation, where the underlying surface of point clouds and the multilateral relationship among the points can be naturally captured by the high-dimensional hyperedges. Leveraging the power of hypergraph signal processing, we estimate and order the hypergraph spectrum from observed coordinates. By trimming redundant information from the estimated hypergraph spectral space based on the strengths of spectral components, we develop a clustering-based method to achieve effective segmentation. We apply the proposed segmentation method to different point clouds, and analyze their respective spectral properties. Our experimental results clearly demonstrate the effectiveness of estimated hypergraph spectrum and efficiency of the proposed segmentation method.


Introduction
With the proliferation of low-cost sensing hardware, three-dimensional (3D) point clouds have been widely adopted as an efficient representation for 3D objects and their surroundings in many applications [1]. One of the essential processing tasks on 3D point clouds is segmentation. Similar to image segmentation, the goal of point cloud segmentation is to identify and cluster the points in a cloud with similar features into their respective regions [2]. These partitioned region should be physically meaningful. For example, the authors of [3] segmented the human posture point clouds to analyze human behaviors, where the human body is partitioned into clusters to represents different semantic body parts. The segmentation can help analyze the point clouds in various applications, such as object tracking, object classification, feature extraction, and feature detection.
To establish a general model and segment efficiently in the point clouds, we consider a new high-dimensional graph representation known as hypergraphs. A hypergraph H = (V, E) is the extension of traditional graph, consisting of nodes V and hyperedges E. Generalizing edges from traditional graphs, each hyperedge can connect more than two nodes, i.e., a subset of V. Since hypergraphs generalize graphs, a graph is only a special case of hypergraph, in which each hyperedge arXiv:2001.07797v1 [eess.SP] 21 Jan 2020 Moreover, in hypergraph signal processing (HGSP), hypergraph spectrum has shown great promise in tasks like clustering and compression [5]. The hypergraph frequency can be used to analyze the underlying structure of datasets. For example, a hypergraph Harr-like high frequency filter can extract sharp features in point clouds, as illustrated in Fig. 1(e). Major challenges of applying HGSP in point clouds are the construction of hypergraph structure and the efficient computation of the hypergraph spectral space. One traditional approach to derive the hypergraph spectrum is to first construct the hypergraph based on distances among nodes before decomposing the resulting (adjacency/Laplacian) tensor. However, such distance-based hypergraph construction is deficient in measuring efficiency. Furthermore, the decomposition of the representing tensor can also be time-consuming.
To overcome the aforementioned challenges, we propose a novel method of spectral clustering segmentation based on the hypergraph signal processing for the gray-scale point clouds. To construct the hypergraph and estimate the spectral space efficiently, we first develop a method to estimate spectral components based on hypergraph stationary process before ordering the components according to their frequency coefficients. Removing redundant information based on the spectrum order, a spectral clustering can be implemented on the key spectrum components to segment the point clouds. We test the proposed segmentation methods on multiple gray-scale point cloud datasets. The test performance of the proposed method validates its effectiveness and efficiency. Note that, the proposed hypergraph construction can be applied to applications beyond point cloud segmentation. We shall point out many future directions of HGSP on point clouds, such as compression and denoising.

Related Works
In this section, we overview the related research works on point cloud segmentation and hypergraph signal processing.
Segmentation over 3D Point Clouds: There are a plethora of methods proposed to segment point clouds efficiently. For example, edge-based methods, such as [6], detect boundaries of regions to segment point clouds and facilitate fast implementation but can be sensitive to noise. Another widely-used class of segmentation methods are region-based [7,8], and are more robust to noises but suffer from either over or under segmentation.
In addition, attribute-driven approaches based on clustering, are also used in segmentation [9,10]. These attribute-based methods would first compute attributes before clutering the derived attributes. Their performances depend highly on the quality of the derived attributes. Thus, how to accurately compute attributes poses a problem. Fortunately, graphs have been successfully applied to extract the underlying structural information of point clouds. Modeling point clouds as graphs, we can derive graph spectral space and utilize spectral clustering to achieve segmentation. Generally, graph-based methods deliver good results and have gained popularity owing to their efficiency [2]. Moreover, one can establish a natural connection between the point cloud features and the corresponding graph structure for analysis [11]. Although graph-based methods have achieved substantial success, they still suffer from low efficiency construction of graph models. How to construct a suitable graph always remains an open problem in graph application. Moreover, regular graph edges only connect two nodes and, thus, can only model pairwise relationships. However, surfaces in a point cloud usually contain more than two nodes. Point-to-point graph edges are unable to model such complex multilateral relationships. Thus, we are motivated to develop more geneal hypergraph models for point clouds.
Graph and Hypergraph Signal Processing on Point Clouds: Graph signal processing (GSP) is a recent geometric tool [12] that has shown great promises. Due to its ability in characterizing underlying structures of datasets, graph signal processing has been applied in point clouds. The authors of [11], for example, develop a fast resampling for point clouds based on graph frequency and GSP filters. Other processing tasks, such denoising [13] and compression [14], can also be implemented by GSP. To generalize GSP to capture high-dimensional multi-lateral interactions, a tensor-based framework of hypergraph signal processing (HGSP) was recently proposed in [5]. Highly suitable for characterizing the multilateral interaction among noise in a point cloud, HGSP can play a significant role in applications such as clutering, classification, compression, and denoising. The work of [4] further developed new approaches to hypergraph spectrum analysis and processing in gray-scale point clouds based on HGSP.
In this work, we extend existing studies and develop an efficient HGSP-based segmentation method for the gray-scale point clouds.

Preliminaries
In this section, we provide the background and introduce some preliminaries of tensor and hypergraph signal processing before discussing technical details.

Tensor
Tensor is a high-dimensional algebraic entity which can be viewed as a multidimensional array. The order of a tensor is the number of indices used to label its components [15]. Indeed, a scalar is a zeroth-order tensor; a vector is a first-order tensor; a 2D matrix is a second-order tensor; a 3D cubic array of entries with 3 indices is a third-order tensor, and an M -dimensional array is an M th-order tensor [16]. In this paper, we denote an M th-order tensor by A ∈ R I1×I2×···×I M , whose entry in position (i 1

Hypergraph Signal Processing
Hypergraph signal processing (HGSP) is a tensor-based framework that can describe the multi-dimensional interactions between nodes [5]. Within the HGSP framework, a hypergraph with N nodes and longest hyperedge connecting M nodes, is represented by an M -order N -dimension representing tensor which can also be decomposed via orthogonal CP decomposition, i.e., Typically, this tensor entry a i1i2···i M indicates whether nodes {v 1 , v 2 , · · · , v M } are connected in an adjacency relationship. In the orthogonal CP decomposition, f r 's are orthogonal basis called spectrum components and λ r are frequency coefficients related to hypergraph frequency. All spectrum components {f 1 , · · · , f N } form the hypergraph spectral space. We name (f r , λ r ) the spectral pair of the given hypergraph. Moreover, to capture the overall spectral information of the hypergraph, we define a supporting matrix Other details, such as hypergraph Fourier transform, HGSP filter design and hypergraph frequency analysis are introduced in [5].

Methods
In this section, we introduce the details of point cloud segmentation based on the hypergraph spectral clustering for gray-scale point clouds. There are three stages in the segmentation: 1) estimate the hypergraph spectral space, 2) order and select the key hypergraph spectrum, and 3) segment via clustering in the optimized hypergraph spectral space. In the first stage, we estimate the hypergraph spectrum directly from observed point clouds based on the hypergraph stationary process instead of decomposing the constructed hypergraph, since the representing tensor is memory-inefficient and its orthogonal-CP decomposition is time-consuming. We then estimate the distribution of hypergraph frequency coefficients according to smoothness, and order the spectrum based on the hypergraph frequency. Finally, we select the low frequency (smooth) spectral content and cluster in the optimized spectral space to segment the point clouds.

Estimation of Hypergraph Spectral Space
We first introduce to hypergraph spectrum estimation based on hypergraph stationary process. Stationarity is an important property in analyzing observation of random variables. The authors of [17] defined a graph stationary process within the graph signal processing framework [12], which describes the stationary property of the graph shifting. Moreover, [18] proposed a method to estimate the spectral components of the graph under the assumption of stationarity for the observed dataset. For point cloud datasets, the three coordinates of each point can be interpreted as three observations of a node from 3 different viewpoints, which reflects the structural information embedded in the spectrum. Thus, we can estimate the hypergraph spectrum components based on hypergraph stationary processing. Let E(·) denote expectation and (·) H denote conjugate transpose. The hypergraph stationary process is defined as follows.
hold for every integer τ ≥ 0, where P = λ max P s and P τ = P τ .
Eq. (3) requires stationary signals to have constant mean, similar to that in stochastic processes. Since the entry of P in position (i, j) is in the position (j, i) of P H , P H can be interpreted as propagation in an opposite direction of P. Then, Eq. (4) implies that the covariance of stationary process only depends on the difference between two steps, i.e., τ 1 + τ 2 [4]. With the definition of hypergraph stationary process, we have the following property. Theorem 1. A stochastic signal x is WSS if and only if it has zero-mean and its covariance matrix has the same eigenvectors as the hypergraph spectrum basis, i.e., where The proof can be found in [4]. This property indicates that, we can estimate the hypergraph spectral components from the eigenspace of the covariance matrix of observations. Thus, a hypergraph-based spectrum estimation can be developed. Given a gray-scale point cloud s = [X 1 X 2 X 3 ] ∈ R N ×3 where X i is the coordinates in ith angle, we can treat each X i as an observation of the points and normalize them to zero-mean. With the normalized observations, we can directly obtain the hypergraph spectrum based on their covariance matrix.

Estimation of the Spectrum Distribution
One important issue in spectral clustering is the ordering of spectral components in order to identify and remove some less critical and redundant information. Within the framework of HGSP, we rank the spectral components according to their (nonnegative) frequency coefficients in decreasing order to which indicates relatively low frequency to high frequency [5]. Now the problem rests with the estimation of the spectrum distribution. In practical applications, large-scale networks are often sparse, thereby making it meaningful to infer that most entries of the hypergraph representing tensor in typical datasets are zero [19]. In addition, signal smoothness is a widely-used assumption when estimating the underlying structure of graphs and hypergraphs [20]. Thus, a general estimation of hypergraph coefficients can be formulated as Here ||A|| 2 T is the tensor norm, and set A includes prior information on the tensor types, e.g., adjacency or Laplacian. The smoothness function of signal s can be designed flexibly for specific applications.
Instead of the exact calculation of frequency coefficients in Eq. (7), our 3D point cloud segmentation only requires a general idea on the distribution of frequency coefficients. Thus, we can simplify the problem as follows. First, we limit our the tensor order to M = 3, i.e., each hyperedge has length 3, since 3 nodes are the required minimum to construct a surface. We then use the total variation based the supporting matrix, denoted by TV(s) = ||s − (1/λ max )Ps|| 2 2 , to describe the smoothness over the estimated hypergraph. In addition, the tensor norm equals ||A|| 2 T = λ T λ as proved in [4]. Let σ = 1 λmax λ. The formulation to estimate the spectrum distribution can be rewritten as Note that the we usually neglect the constraint σ max = 1 in practice to reduce computation complexity, since we only need to order the frequency coefficients for segmentation. Thus, the formulation is convex and can be readily solved by using well known numerical recipes. From the estimated σ, we order the spectral components in decreasing order of the frequency coefficients, which also indicates an increasing order of hypergraph frequency [5].

Segmentation based on Hypergraph Spectral Clustering
From the estimated spectrum components and frequency coefficients, we can directly propose a segmentation method based on spectral clustering. The detail steps are summarized as Alogrithm 1. Usually, we can define a threshold in Step 7. We will show more instructions of selecting the leading components, and discuss the efficiency of hypergraph spectral space in Section 5.2.

Experiments
In this section, we compare the performance of the proposed point cloud segmentation method with some more traditional methods to test the efficacy of hypergraph spectral clustering.

Comparison with k-means Clustering
Since the clustering parts of the hypergraph spectral clustering is based on the kmeans clustering, we first compare the performance of the proposed segmentation method with the traditional clustering of k-means. To implement the k-means, we cluster over each row of point cloud coordinates. For the hypergraph spectral 5: Estimate the normalized frequency coefficients σr's by solving Eq. (10) 6: Rank frequency components fr's based on their corresponding frequency coefficients in decreasing order, i.e., {f1, f2, · · · , fN } where σ1 ≥ σ2 ≥ · · · ≥ σN . 7: Find the first E leading spectral components fr with larger λr and construct a spectrum matrix M ∈ R N ×E with columns as the leading spectrum components. 8: Cluster the rows of M into k clusters using k-means clustering. 9: Cluster node i into partition j if the ith row of M is assigned to jth cluster. 10: Output: k partitions of the point clouds.
clustering, we select the first E key spectrum components based the frequency coefficients, for which there is a clear step difference with the next (i.e., the (E + 1)-th) frequency coefficients. Typically, the first two or three bases sufficiently satisfy this criterion. We will present more properties in Section 5.2.
We test the algorithms over a dataset of animals [21,22,23] shown as Fig.  2. In the first column of Fig. 2, we segment the a point cloud of a cat into six parts. In Fig. 2(d), the hypergraph spectral clustering can segment the limbs, the tail and the head into different colors, while the k-means clustering fails. Similar conclusions hold when segmenting the wolf and the gorilla, shown in the last two columns of Fig. 2. Especially for the gorilla data, different limbs are clustered to show four different colors in Fig. 2(c), whereas the traditional k-means is unable to distinguish its two legs in Fig. 2(f). From the test results, we can see that the hypergraph spectral clustering exhibit better performance than the k-means clustering because hypergraph can capture the underlying structure of the point cloud and effectively identify the redundant information for removal based on the frequency coefficients.

Comparison with Graph-based Methods
Next, let us show the comparison between the hypergraph-based method and graph-based clustering methods. We shall also examine the analysis of different spectrum properties.
Graph-based spectral clustering has been successful in segmentation. In graphbased methods, a graph representation, i.e., Laplacian or adjacency matrix, is constructed to generate the spectral space [24]. For example, GSP can apply a Gaussian model [11] to encode the local geometry information through an adjacency matrix W ∈ R N ×N . Let s i ∈ R 1×3 be the coordinates of the ith point.  The edge weight between points i and j is defined by where the variance δ and the threshold t are parameters to control the weights of edges. Another common model is the Laplacian matrix. Similar to that in the graph adjacency matrix, a threshold can be set to determine whether a link exist between two nodes according to their distance. The weight of the similarity matrix S is set to one or zero to indicate the link status. Next, form a diagonal degree matrix D whose entry is the degree of each node. A Laplacian matrix is defined by to facilitate the spectral clustering. However, a limitation of graph-based model is that the 2D edges can only model pairwise relationship but is unable to capture the multilateral relationship of the nodes over surfaces. On the other hand, our proposed hypergraph model of point clouds overcomes this shortcoming and can extract the multilateral information. We will compare our hypergraph-based method with the aforementioned graph models to show the power of HGSP in processing 3D point clouds.
We compare the proposed hypergraph spectral clustering with the Laplacianbased method in Eq. (16) and the adjacency-based method in Eq. (15), respectively, over the same datasets of human and animals as described in Section 5.1. We shall first show some experimental results from the different point cloud  datasets given in Fig. 3. From the test results, we can see that the GSP method and HGSP method often have similar performance by clustering limbs and torso into different parts. However, the HGSP-based method is able to further distinguish tails and different legs clearly, whereas the GSP method sometimes fails to cluster the limbs clearly. We can conclude that the hypergraph model can capture the overall structural information of 3D point cloud better than a normal graph. The Laplacian-based method emphasizes the details in some complex structures. For example, in the gorilla results shown in Fig. 3(f), the Laplacian-based method can segment the feet from the legs and hands from the arms, respectively. Generally, both HGSP-based and GSP-based methods present clearer segmentation of the main features for the point cloud datasets. Laplacian-based methods can add some specific details in complex structures if there may be more clusters.
We are interested in reasons behind the performance difference of different graphical methods. To explore the causes that lead to the differences, we ex-    amine the distribution of eigenvalues or the frequency coefficients of different methods in the specific horse point cloud shown in Fig. 4. In different rounds of the experiment, we randomly sample 400, 1400, 2400 and 3400 points from the original horse point cloud and calculate the eigenvalues from different methods. The results are shown in Fig. 5, Fig. 6 and Fig. 7. The Y-axis is the normalized values of eigenvalues or frequency coefficients. The X-axis is the position of each eigenvalues, i.e., P os i = i/N for the ith eigenvalue of N nodes. From the results, we can see that HGSP-based method and GSP-based method have quite similar distributions, which indicate that their information is more concentrated to the first few key spectral components. Moreover, with increasing number of samples, the information becomes more concentrated among the key components. Compared to GSP-based method, the key information of hypergraph spectrum are more concentrated. That explains why HGSP-based and GSP-based methods have similar performances in the segmentation results of Fig. 3. Unlike the adjacency-based methods, the distribution of eigenvalues of the Laplacian shows a quite different curve in Fig. 7. This difference accounts for the performance difference between Laplacian-based segmentation from the GSP-based and HGSP-based methods based on adjacency. We also test segmentation over point cloud with different number of samples, with results given in Fig. 8. From the test results, we can see that the performance of segmentation naturally improves with increasing number of samples. For example, in Fig. 8(b), the blue nodes appear in two legs, while the Fig, 8(c) shows a clear segmentation of the two hind legs.

Analysis of the Time Complexity
We also test the computation running time of different methods over the animal datasets. From the test results summarized in Table 1, we can see that the kmeans method is the fastest. It is because graph based methods need to estimate the spectrum before clustering. The GSP-based and Laplacian-based methods need more time, since they need to first calculate pair distances for every node to obtain the graph structure wheres we can directly estimate the HGSP spectral components. Note that, we do not need to calculate the exact values of frequency coefficients when implementing hypergraph spectral clustering. In fact, we only need an approximate distribution of the frequency coefficients to complete the segmentation task.

Conclusions
This work proposes a novel segmentation method for 3D point cloud based on hypergraph spectral clustering. We first estimate the hypergraph spectral space via hypergraph stationary processing, before ranking the spectral components according to their frequency coefficients. We further introduce a segmentation algorithm that utilizes the estimated hypergraph spectrum pairs. The test results over multiple point cloud datasets clearly demonstrate the effectiveness of hypergraph spectrum estimation and the performance advantage of the proposed hypergraph method for point cloud segmentation.
Owing to the power of HGSP in processing complex, high-dimensional structures, we anticipate many future successful applications of HGSP in 3D point clouds. Given robustly stimated spectrum components and frequency coeffi-cients, many critical data processing tasks such as resampling, reconstruction, and feature extraction can benefit from hypergraph spectral analysis.