Fei Yang

Franck Davoine
email: franck.davoine@hds.utc.fr

Huan Wang
email: wanghuanphd@njust.edu.cn

Zhong Jin
email: zhongjin@njust.edu.cn

Continuous Conditional Random Field Convolution for Point Cloud Segmentation

Keywords: point cloud segmentation, conditional random fields, message passing, graph convolution, mean-field approximation

Point cloud segmentation is the foundation of 3D environmental perception for modern intelligent systems. To solve this problem and image segmentation, conditional random fields (CRFs) are usually formulated as discrete models in label space to encourage label consistency, which is actually a kind of postprocessing. In this paper, we reconsider the CRF in feature space for point cloud segmentation because it can capture the structure of features well to improve the representation ability of features rather than simply smoothing. Therefore, we first model the point cloud features with a continuous quadratic energy model and formulate its solution process as a message-passing graph convolution, by which it can be easily integrated into a deep network. We theoretically demonstrate that the message passing in the graph convolution is equivalent to the mean-field approximation of a continuous CRF model. Furthermore, we build an encoder-decoder network based on the proposed continuous CRF graph convolution (CRFConv), in which the CRFConv embedded in the decoding layers can restore the details of high-level features that were lost in the encoding stage to enhance the location ability of the network, thereby benefiting segmentation. Analogous to the CRFConv, we show that the classical discrete CRF can also work collaboratively with the proposed network via another graph convolution to further improve the segmentation results. Experiments on various point cloud benchmarks demonstrate the effectiveness and robustness of the proposed method. Compared with the state-of-the-art methods, the proposed method can also achieve competitive segmentation performance.

Introduction

A conditional random field (CRF) is a kind of probabilistic graphical model (PGM) that is widely employed for structure prediction problems in computer vision. In image segmentation, most previous studies have attempted to model the data affinity in label space with CRFs, where the CRF is formulated as a discrete model. Such a discrete model is usually NP-hard to solve. Nevertheless, some approximate methods have been proposed to solve discrete CRF models efficiently. The most widely used approximate methods in computer vision are α-expansion/αβ-swap [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] and mean-field approximation [2]. The former is a graph-cut-based method, and the latter belongs to the variational inference-based method. With the rapid development of deep learning techniques, mean-field approximation methods have attracted more attention in the community because the mean-field approximation can be easily embedded in a deep network to build an end-to-end architecture [3]. Despite these, discrete CRFs that encourage label consistency in the results can only smooth the object boundaries and remove some small noises. The misclassified object regions in the prediction stage are hard to correct by these kinds of postprocessing CRFs.

Convolutional neural networks (CNNs) have achieved significant success in image, speech, and natural language processing (NLP). However, with the explosion in 3D data such as point clouds, traditional CNNs that are designed for grid-like data can no longer meet all the needs. On the one hand, the point cloud data acquired by 3D sensors are usually large-scale, sparse, and unordered, which is difficult to process with traditional CNNs directly. On the other hand, point cloud segmentation is the foundation of 3D environmental perception in modern intelligent systems, such as intelligent robotics and autonomous driving cars. Therefore, segmenting point clouds with deep learning techniques is an urgent challenge in modern computer vision. Although many deep learning-based methods[4, [START_REF] Li | Pointcnn: convolution on χ-transformed points[END_REF][START_REF] Thomas | Kpconv: flexible and deformable convolution for point clouds[END_REF] have been proposed to segment point clouds, they focus on the design of the feature extractor to improve the representation ability of the point features. Segmentation consists of two parts: classifying (what it is) and locating (where it is). For classification tasks, we only need to encode the high-level features, and focus less on where the extracted features should be. The classification result can be inferred from only a single global vector. However, segmentation is a dense prediction task. We need to not only extract the high-level features (what it is) but also restore the correspondence between the encoded high-level features and each input point exactly (where it is). The restoration process can be understood as solving the problem of where it is. In other words, previous studies attempted to make the network understand what it is but failed to investigate the problem of where it is. Currently, the research on feature decoding is scarce in the literature. To fill this gap, we focus our study on feature decoding rather than feature encoding, considering that the feature encoding methods targeting a classification task are competent for a segmentation task.

To address the problems mentioned above, we reconsider the CRF in feature space to enhance the location ability of the network during feature decoding. Segmentation is a typical structure prediction problem. To address this problem, the CRF is usually formulated as a discrete model to encourage label consistency in the results, which can only smooth the object boundaries and remove some small noises. Inspired by the continuous CRF used for depth completion, we reconsider the CRF as a continuous model in feature space to restore the encoding features for point cloud segmentation. The CRF is enforced to participate in the feature extraction process of the point cloud and thus can fundamentally improve the representation ability of the features rather than just smoothing the labels by postprocessing. Specifically, previous methods usually adopt the kNN (k-nearest neighbors)-based interpolation method to decode high-level features. They roughly place the high-level features at their closest positions during upsampling but ignore the consistency of features in feature space. The details of the high-level features will be lost in such an upsampling process. There is an intuitive assumption that similar points in low-level feature space should also have similar high-level features. Therefore, we employ the CRF model to guide the feature upsampling procedure to restore the details of high-level input point features gradually. In our continuous CRF model, the low-level features in the encoding layers are used as guidance information to guide the high-level feature upsampling. This process has a similar effect to guided filtering, such as joint bilateral filters.

In this paper, we propose a continuous CRF graph convolution (CRFConv) to capture the feature structures during the feature extraction stage. More precisely, we propose using a continuous quadratic energy model to describe the point cloud in feature space, in that a continuous CRF model is mathematically equivalent to a quadric energy model that has a similar form to the diffusion model. Inspired by some diffusion-based graph convolution methods in the community, we formulate the solution process of this model as a message-passing graph convolution, by which the continuous CRF can be embedded in the network for feature extraction. From a CRF perspective, we also prove that the message passing of this graph convolution is equivalent to the mean-field approximation algorithm of a continuous Gaussian CRF model, which indicates that the proposed graph convolution is actually equivalent to a continuous CRF model. After that, we build an encoder-decoder network for point cloud segmentation, in which the decoding modules are carefully designed based on the proposed CRFConv. We use the proposed CRFConv to enhance the location ability (where it is) of the network as described above. To enlarge the receptive field, the extracted high-level features in the encoder lose details by successive pooling/downsampling operations. Previous methods only upsample the high-level features with simple linear interpolation in the decoding layers, while our method models the upsampling process with a structure model (i.e., the CRFConv), by which the details of the high-level point cloud features can be restored gradually. Furthermore, we show that our continuous CRF can also work collaboratively with the classical discrete CRF to further improve the segmentation results. The discrete CRF is formulated as another message-passing graph convolution by analogy to the CRFConv, by which the discrete CRF can be embedded in our segmentation network to implement an end-to-end dual CRF network. To the best of our knowledge, we are the first to consider CRF models both in feature and label space simultaneously in point cloud segmentation.

Experiments on various datasets, including object-level and scene-level segmentation tasks, demonstrate the ef-fectiveness of the proposed method. The contributions of this paper can be summarized as follows: 11. We propose a continuous CRF graph convolution (CRFConv) to model the data affinity in feature space instead of label space, which enforces the CRFConv to participate in the point cloud feature extraction process. The CRFConv can thus fundamentally improve the representation ability of the features rather than just smoothing the labels by postprocessing. 2. We design a point cloud segmentation network based on the proposed CRF convolution to enhance the location ability of the network. The CRFConv is embedded in the network decoder to model the upsampling process with a continuous CRF model, by which the details of the high-level point cloud features can be restored gradually during upsampling. 3. We further implement a dual CRF network by reformulating the classical discrete CRF as another graph convolution. The dual CRF network models the data affinity both in feature space and label space simultaneously to further improve the segmentation results. 4. We conduct experiments on various challenging point cloud segmentation benchmarks, including synthetic object data and large-scale indoor and outdoor scenes. The experimental results demonstrate the effectiveness and robustness of the proposed method.

The rest of this paper is organized as follows. In section 2, we review the literature and introduce some related basic knowledge about CRF. The continuous CRF graph convolution and theoretical analyses are presented in section 3. In section 4, we present the architecture of the segmentation network in detail and show how to combine the continuous CRF with the classical discrete CRF in our segmentation network. The experimental results, comparisons, and ablation analysis can be found in section 5. Section 6 concludes the work in this paper, in which the limitations and future works are also discussed.

Related Work

Point cloud segmentation

With the popularity of 3D sensors, 3D data are exploding in human daily life owing to their easy acquisition.

One key application of 3D data is point cloud segmentation, which is the foundation of 3D environmental perception. Considering the success of CNNs in image processing, many researchers have attempted to employ deep learning techniques to segment point clouds [START_REF] Guo | Deep learning for 3d point clouds: a survey[END_REF]. In this section, we only review the point cloud segmentation methods based on deep learning. These methods can be divided into four categories: image-based, voxel-based, point-based, and graph-based methods.

Image-based methods convert the point cloud as an image-like representation and employ some image-based networks to process the point cloud. For example, Yang et al. [START_REF] Yang | A fusion network for road detection via spatial propagation and spatial transformation[END_REF] projected LiDAR (light detection and ranging) points to the image plane by the cross-calibration parameters. Instead of converting the LiDAR point cloud to the image plane, Wu et al. [START_REF] Wu | Squeezeseg: convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud[END_REF] projected the LiDAR point cloud to a sphere plane to form a dense and grid-based representation. An alternative solution for 3D point cloud representation is the multiview-based method [START_REF] Kalogerakis | 3d shape segmentation with projective convolutional networks[END_REF]. In other words, the image-based methods convert the 3D point cloud to a 2D grid-like representation to cater to image-based networks. The structural information of the point cloud will inevitably be lost during such conversions.

Voxel-based methods borrow ideas from image-based CNNs. In these methods, the point cloud is first split into uniform voxels and then processed by deep 3D networks. Maturana et al. proposed VoxNet [START_REF] Maturana | Voxnet: a 3d convolutional neural network for real-time object recognition[END_REF], an architecture to segment point clouds by integrating a volumetric occupancy grid representation with a supervised 3D CNN. However, the voxel-based presentation for a point cloud is usually time consuming and space wasting. To address this problem, Octree [12] and Kd-Tree [13]-based approaches have been proposed to save computations by skipping convolution in empty space. Nevertheless, voxel-based representation methods still cause information loss. In addition, it is difficult to balance computations and accuracy. How to determine the voxel resolution for the point cloud, which varies in density, remains a problem.

Point-based methods overcome the shortcomings of image-based and voxel-based methods. The unordered and sparse points can be directly processed by point-based methods without transformations. PointNet[4] was the first work to directly process the points in point clouds with deep learning techniques. Since Qi et al. pioneered this field, many point-based methods have emerged in the community. For example, Qi et al. further extended their PointNet to PointNet++ [14], which is a hierarchical version of PointNet. Li et al. [START_REF] Li | Pointcnn: convolution on χ-transformed points[END_REF] learned a χ-transformation to transform the point cloud to a latent and potential canonical order, by which the typical convolution operator can be applied on the χ-transformed features. [START_REF] Hermosilla | Monte carlo convolution for learning on non-uniformly sampled point clouds[END_REF][START_REF] Wu | Pointconv: deep convolutional networks on 3d point clouds[END_REF] defined the convolution on point cloud domains using Monte Carlo. Thomas et al. [START_REF] Thomas | Kpconv: flexible and deformable convolution for point clouds[END_REF] proposed the kernel point convolution (KPConv) inspired by the convolution operator on regular domains. Recently, the attention mechanism was also explored to extract the point features for point cloud segmentation in [START_REF] Feng | Point attention network for semantic segmentation of 3d point clouds[END_REF] and [START_REF] Zhou | Feature fusion network based on attention mechanism for 3d semantic segmentation of point clouds[END_REF].

Graph-based methods have also been extended to process point clouds with the advent of graph neural networks (GNNs) in recent years. In these methods, they assume that a latent graph exists in the point cloud (e.g., kNN or radius graph). Landrieu et al. [START_REF] Landrieu | Large-scale point cloud semantic segmentation with superpoint graphs[END_REF] first presegmented the point cloud to superpoints using an unsupervised cluster algorithm. Then they built a superpoint graph based on the superpoint features extracted by PointNet to segment the point cloud. Wang et al. [START_REF] Wang | Dynamic graph cnn for learning on point clouds[END_REF] proposed EdgeConv, which is dynamically computed in each layer of the network, for high-level tasks on point clouds. DeepGCNs [START_REF] Li | Deepgcns: can gcns go as deep as cnns?[END_REF] extended graph convolutional networks (GCNs) to deep models by borrowing concepts from CNNs, specifically residual/dense connections and dilated convolutions. DeepGCNs have also shown their ability on large-scale 3D point cloud segmentation tasks.

Point-based and graph-based methods can both be categorized as geometric deep learning (GDL) [START_REF] Bronstein | Geometric deep learning: going beyond euclidean data[END_REF] methods. GDL has shown its advances in processing point clouds. In this paper, the proposed method is also a kind of GDL method. However, previous methods focus on improving the classification ability of the network but ignore its location ability, which is crucial for segmentation. Our work focuses on the decoding rather than the encoding of the point features to enhance the location ability of the network, which is the most different point from existing methods.

Conditional random field

In this section, we first review some basic knowledge about CRF for the convenience of readers who are not familiar with this field. Then, we review the applications of CRFs in computer vision, including but not limited to point cloud processing. Basic knowledge. Let G(V, E) be an undirected graph, where V and E represent the node and edge sets of the graph, respectively. Denote x i as a random variable defined on node i ∈ V. e(i, j) ∈ E can be understood as the relationship between the random variables x i and x j . Thus, X = {x i |i ∈ V} can be viewed as a random field on G. If the random variables of X in G satisfy the Markov property, then we call X a Markov random field (MRF) on G. According to the Hammersley-Clifford theorem, the joint probability distribution of the MRF can be presented with a Gibbs distribution parameterized by the clique potentials defined on G, that is:

P(X) = 1 Z c∈C G φ c (X c ), (1)
where c and X c denote a maximum clique (complete subgraph) of G and its associated random variable, respectively. C G is the set of all cliques. φ c is the clique potential defined on c. Z is a partition function to ensure a distribution. Note that φ c is constrained to be nonnegative in the Gibbs distribution. In general, we can transform φ c (X c ) to its log space. Specifically, we let φ c (X c ) = exp(-ψ c (X c )), where ψ c (X c ) = -log φ c (X c ) denotes the energy function defined on c. Hence the Gibbs distribution can be simply rewritten as:

P(X) = 1 Z exp -E(X) , (2)
where E(X) = c∈C G ψ c (X c ) is the Gibbs energy function defined by all cliques of G. Eq. ( 2) is a log linear model, which ensures a positive distribution.

The MRF can also be used to describe a conditional distribution. Given another random variable Y, if the random variable X on G is conditional on Y, we say the MRF determined by X is a CRF determined by X and Y. The conditional distribution P(X|Y) of the CRF can also be represented with a Gibbs distribution, which has the same form as Eq. (2). Y and X can be viewed as the observed and latent variables in the CRF, respectively. In other words, the CRF of X and Y can be understood as the MRF of X with an additional input Y. For notational convenience, we omit the condition Y in the rest of the paper when we refer to CRF. Applications. CRFs/MRFs are widely applied to image segmentation for structure prediction as a kind of postprocessing. Krähenbühl et al. [START_REF] Krähenbühl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF] proposed the fully connected CRF for image segmentation for the first time. The fully connected CRF also acts as a postprocessing step of a CNN in [START_REF] Chen | Deeplab: semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] to improve the localization accuracy. In addition, Zheng et al. [START_REF] Zheng | Conditional random fields as recurrent neural networks[END_REF] extended the fully connected CRF as a recurrent neural network (RNN) for object segmentation. Qiu et al [START_REF] Qiu | Saliency detection using a deep conditional random field network[END_REF] also integrated the CRF into a CNN to segment saliency objects. Although these methods allow us to jointly train the CNN and the CRF model end-to-end, the CRF still acts as postprocessing in the pipeline. In contrast to the existing approaches that use discrete CRF models, Vemulapalli et al. [START_REF] Vemulapalli | Gaussian conditional random field network for semantic segmentation[END_REF] proposed using a Gaussian CRF model for semantic segmentation instead, in which the CRF is still built in the label space to refine the labels. In addition to image segmentation, the application of CRFs/MRFs for point cloud segmentation is also explored. Wu et al. adopt a CRF model as in [START_REF] Chen | Deeplab: semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF] to refine the output of their SqueezeNet [START_REF] Wu | Squeezeseg: convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud[END_REF].

Our continuous CRF model is different from discrete CRFs that usually act as postprocessing to refine the labels. We model the data affinity in feature space with a continuous CRF that essentially participates in the feature extraction process of the point cloud. Hence, our CRF can fundamentally improve the representation ability of the features rather than only smoothing the labels in postprocessing.

The continuous CRF graph convolution

In this section, we present the CRF graph convolution from a continuous quadratic energy model in the feature space of a point cloud. First, we present how to formulate its solution process as a message-passing algorithm in a graph defined on the point cloud. Then we define the continuous graph convolution based on this message-passing algorithm. Finally, we conduct a theoretical analysis of the proposed graph convolution from a CRF perspective.

The continuous quadratic energy model

Denote P = {(p i , z i , x i )|i < N} as a point cloud with N points. p i ∈ R 3 is the position vector of point i in the 3D Euclidean space. z i ∈ R d and x i ∈ R d represent the observed and latent features of point i, respectively. Assume that the observed feature z i is independent of each other. We infer the latent feature x i from the observed feature z i by considering the affinity in the feature space. Thus, we consider the following quadratic energy function:

E(X) = i (x i -z i ) (x i -z i ) fidelity term + i j (x i -x j ) w i j (x i -x j ) smoothness term , (3)
where X = {x i |i < N} denotes the feature set of the latent features. w i j ∈ R d×d is the weight matrix between features x i and x j , which encodes the relationship between two points. It can be computed as:

w i j = s i j C, (4)
where s i j ≥ 0 is the scalar similarity between points i and j, which can be estimated from the observed feature z.2 C ∈ R d×d 0 is a compatibility matrix to model the intrarelationship between feature channels and is assumed to be independent of the feature value. There is a similar concept of the compatibility matrix in the classic discrete CRF model. In that case, C describes the co-occurrence (or compatibility) of different object classes or labels. Since our model is built in feature space, C actually describes the channel/dimension compatibility of feature space here. In general, we can assume that the channels are independent of each other, and the messages pass in each channel individually in this case. Therefore, it is possible to directly define C as the identity matrix. Alternatively, it is also possible to automatically learn it from the data to further enhance the expression ability of the model. We cannot parameterize C directly because of its positive-define constraint. In this paper, we let C = c c + I to ensure positive definition, where c is a learnable parameter initialized as c = I. is a tiny positive value.

Eq. (3) consists of two terms: a fidelity term and a smoothness term. It can be understood that we want the new representation x i to be smoother but as close as possible to its original representation z i . Eq. (3) and its variants have been widely applied in the problems of denoising, recovery, and superresolution in computer vision. The latent feature X can be obtained by minimizing Eq. (3):

X * = argmin X E(X). (5)
Eq. ( 5) is a quadratic convex optimization problem with a closed-form solution. Denote Z = [z 1 , z 2 , ..., z N ] and X = [x 1 , x 2 , ..., x N ] as the concatenated feature vector of the point cloud, where Z, X ∈ R (N×d) . The compact form of Eq. (3) can be rewritten as:

E(X) = (X -Z) (X -Z) + X (D -W)X, (6)
where W is a N × N block matrix consisting of w i j , which can be computed as W(i, j) = w i j . D is a N × N block diagonal matrix that can be computed as D(i, i) = j w i j . The derivative of E(X) is calculated with respect to X and ∂E(X)/∂X = 0. We can obtain the closed-form solution of E(X):

X * = (I + D -W) -1 Z, (7)
where

I + D -W is a (N × d) × (N × d) matrix.
To solve the linear system, we need to calculate the inverse of such a large matrix, which is computationally expensive, especially when N and d are both large. Alternatively, we adopt an iterative strategy instead of using the closed-form solution. Recalling Eq. (3), we calculate the partial derivation of E(X) with respect to x i and let ∂E(X)/∂x i = 0. Then, we can obtain an iterative solution for x i under the coordinate descent framework:

x * i = (I + j w i j ) -1 (z i + j w i j x j ). (8)
Since Eq. ( 3) is convex, the coordinate descent algorithm can guarantee the global minimum, which is validated in the experimental section. If we further assume that point i is only related to its neighbor points N(i) = j p i -p j 2 2 ≤ r in the point cloud and normalize the similarity to ŝi j = s i j / j∈N(i) s i j , Eq. ( 8) can be further simplified to:

x * i = (I + C) -1 (z i + C j∈N(i) ŝi j x j ). (9)
It is easy to find that Eq. (3) actually contains a graph structure implicitly. We denote the graph defined on a point cloud as G P (V P , E P ), where V P is the node set that contains all points (|V P | = N). E P represents the edge set that indicates whether two points are related to each other. Therefore, the update equation Eq. ( 9) can be described as a message-passing process in G P , as shown in Algorithm 1.

Algorithm 1

The message-passing process of Eq. (3) Input: Point cloud graph G P (V P , E P ), observed feature Z = {z i |i ∈ V P }, maximum iteration steps T . 1: Initialize:

x i ← z i for i ∈ V P 2:
Compute the normalized similarity: ŝi j for e(i, j) ∈ E P 3: for t = 1 : T do 4:

for i ∈ V P do 5:

Message passing: msg j→i = e(i, j)∈E P ŝi j x j 6:

Compatibility transformation: msg j→i = Cmsg j→i 7:

Add unary:

x i = z i + msg j→i 8:
Normalize:

x i = (I + C) -1 x i 9:
end for 10: end for Output: Latent feature X = {x i |i ∈ V P }.

The message-passing graph convolution

Gilmer et al. proposed a universal GNN paradigm named message-passing neural networks (MPNNs) in [START_REF] Gilmer | Neural message passing for quantum chemistry[END_REF]. The forward pass of MPNN has two phases: message passing and readout. In fact, most graph convolutional networks previously proposed [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF][START_REF] Veličković | Graph attention networks[END_REF][START_REF] Monti | Geometric deep learning on graphs and manifolds using mixture model cnns[END_REF] follow such a message-passing paradigm. Accordingly, we can also reformulate Algorithm 1 as a message-passing graph convolution.

Denote x l i as the feature vector of node i in the l th layer of the network. Our message-passing graph convolution can be defined as:

Initial step: h (l,0) i = z (l) i = MLP(x (l-1) i ), (10)
Message-passing step:

Message: m (l,t) i = C j∈N(i) ŝi j h (l,t-1) j , (11)
Update:

h (l,t) i = (I + C) -1 (h (l,0) i + m (l,t) i ), ( 12
)
Readout step:

x l i = σ(h (l,T ) i ), ( 13
)
where MLP(•) denotes the multilayer perceptron which is used for the pointwise feature transformation. m (l,t) i and h (l,t) i denote the message and the hidden state of node i in the l th layer after t message-passing steps, respectively. σ(•) acts as a nonlinear activation function in the read out step. The data flow of the message-passing step is illustrated in Figure 1. Unlike most one-step graph convolution methods, the message-passing phase of our graph convolution, which consists of a message function Eq. ( 11) and an update function Eq. ( 12), runs T times.

The CRF Perspective

Consider a Gibbs distribution in Eq. (2) with the energy function given in Eq. (3). According to the Hammersley-Clifford theorem, in this case, Eq. (2) actually determines a continuous Gaussian CRF model defined on G P (V P , E P ). Considering CRF, the maximization of P(X) is also equivalent to the minimization of the energy function E(X).

Theorem 1. The coordinate decent of Eq. ( 3) is equivalent to the mean-field approximation of Eq. (2) when the approximate distribution

Q i ∼ N(µ i , Σ i ).
Proof. The goal of the mean-field approximation algorithm is to find a distribution Q(X) that can be factorized as Q(X) = i Q i (x i ) to approximate the original distribution P(X), where we have

Q i (x i ) ∼ N(x i ; µ i , Σ i ).
Then, we can obtain Q(X) by minimizing the Kullback-Leibler divergence KL(Q||P) between Q(X) and P(X). We obtain {(µ * i , Σ * i )|i ∈ V P } by solving the following problem:

{(µ * i , Σ * i )|i ∈ V P } = argmin {(µ i ,Σ i )|i∈V P } KL(Q||P) = argmin {(µ i ,Σ i )|i∈V P } F[Q(X; {(µ i , Σ i )|i ∈ V P }), E(X)], (14)
where F[•] is an energy functional about the energy function E(X) and the approximation distribution Q(X). Since the forms of E(X) and Q(X) are determined in our case, F can be viewed as a function of {(µ i , Σ i )|i ∈ V P } directly.

Q i is supposed to be independent and identically distributed. Without losing generality, we consider each µ i and Σ i individually. By setting ∂F/∂µ i = 0 and ∂F/∂Σ i = 0, we can obtain the update equations of µ i and Σ i , respectively:

µ * i = (I + j∈N(i) w i j ) -1 (z i + j∈N(i) w i j µ j ). ( 15
)
Σ * i = 1 2 (I + j∈N(i) w i j ) -1 . (16)
Actually, we are only interested in the mean vector

µ i of Q i in that max Q i (x i ) = Q i (µ i ).
We find that the update equation of µ i in the mean-field algorithm is equivalent to the update equation of x i in the coordinate descent algorithm. In other words, the coordinate descent of Eq. ( 3) is equivalent to the mean-field approximation of a continuous CRF (Eq. ( 2)), by which Theorem 1 can be proved. Hence, we name the proposed message-passing graph convolution continuous CRF graph convolution (CRFConv). For clarity reasons, we only provide a brief proof here. The detailed proof of Theorem 1 can be found in the supplemental material.

The point cloud segmentation network

In this section, we show how to utilize the proposed CRFConv for point cloud segmentation. We design a point cloud segmentation network that includes two parts: an encoder and a decoder. An overview of the network architecture is shown in Figure 2. The CRFConv is embedded in the decoder to decode the high-level features. Specifically, we model the upsampling process with the CRF model rather than linear interpolation, by which the lost details of high-level features caused by the encoder can be restored gradually during feature decoding.

The encoder

Because point clouds are unordered, sparse, and continuous in 3D Euclidean space, the convolution on a point cloud is different from that on an image. Analogous to image convolution, we adopt the convolution defined on irregular domains to extract the point features in the encoder. The standard convolution operation is defined as:

f * g(x) = +∞ -∞ f (y)g(x -y)dy = y∈N(x) f (y)g(x -y), ( 17
)
where f is the signal to be convolved, and g is the convolution kernel. In a regular domain (e.g., image), the offset (xy) is fixed with respect to different kernel centers, which allows us to directly parameterize g with shared parameters. However, for an irregular domain (e.g. ,point cloud), the offset (xy) and the neighborhood size |N(x)| may vary at different positions, which leads to the fact that we cannot parameterize g directly. In the literature, researchers have attempted different methods to define the convolution on irregular domains [START_REF] Li | Pointcnn: convolution on χ-transformed points[END_REF][START_REF] Thomas | Kpconv: flexible and deformable convolution for point clouds[END_REF][START_REF] Wang | Deep parametric continuous convolutional neural networks[END_REF][START_REF] Hermosilla | Monte carlo convolution for learning on non-uniformly sampled point clouds[END_REF][START_REF] Wu | Pointconv: deep convolutional networks on 3d point clouds[END_REF]. In this paper, we follow [START_REF] Wang | Deep parametric continuous convolutional neural networks[END_REF][START_REF] Hermosilla | Monte carlo convolution for learning on non-uniformly sampled point clouds[END_REF][START_REF] Wu | Pointconv: deep convolutional networks on 3d point clouds[END_REF] and parameterize the convolution kernel g as:

g(x -y) = MLP(x -y; Θ), ( 18
)
where Θ is the learnable weights of the MLP. Therefore, the point convolution (PointConv) used in this paper can be written as:

f * g(x) = 1 |N(x)| y∈N(x) f (y)MLP(x -y; Θ), (19)
in which normalization is necessary to make it robust to various neighbor sizes. d in and d out are denoted as the input and output feature dimensions, respectively. For each PointConv, the kernel g(•) is evaluated N × |N| × d in × d out times. This is computationally expensive in practice, especially when both the number of points and the feature dimension are large. Inspired by the depthwise separable convolution of image networks, we separate canonical PointConv into a depthwise point convolution and several 1 × 1 convolutions. Figure 3 illustrates our PointConv layer in detail. Specifically, we first use a 1 × 1 convolution to reduce the dimension of the input feature from d in to d in /r with a proportion of r. Then, we evaluate N × |N| × (d in /r) kernels for depthwise point convolution. Finally, another 1 × 1 convolution with (d in /r) × d out parameters is adopted to produce the output features. Moreover, batch normalization (BN) and residual connections are also adopted for PointConv. Dilated kNN neighbors are constructed for dilated PointConv to increase the receptive field of the encoder, which is proven to be helpful in image segmentation [START_REF] Chen | Deeplab: semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs[END_REF].

The decoder

In the literature, successive pooling operations or strided convolutions are adopted to increase the receptive field of the encoder. In the decoding stage, they simply adopt linear interpolation to upsample the high-level features, by which the details of these features are lost. Such linear interpolation only considers the positions of the features but ignores their continuity in feature space. The high-level features become increasingly coarser during decoding. Previous methods skip connections to relieve this situation. However, no previous study has fundamentally attempted to solve this problem. To address this problem, we propose using the CRFConv to restore the details of the high-level features during decoding. In our method, not only the point positions but also the distribution of the low-level features are considered for feature decoding. CRFConv is utilized to model the data affinity in feature space to generate high-resolution and detailed high-level features.

Denote x (l-1) and x l as the high-level feature to be upsampled (the input feature in the decoder) and the upsampled high-level feature (the output feature in the decoder), respectively. Let x (l) be the corresponding lower-level feature in the encoder that has the same resolution as x (l) . Figure 4(a) gives the architecture of our decoding layer. The high-level feature is initially upsampled by kNN interpolation. Then, a unary net is immediately adopted to extract the unary feature, which produces z (l) as described in Eq. [START_REF] Kalogerakis | 3d shape segmentation with projective convolutional networks[END_REF]. Then, we dynamically compute the similarity s i j . We adopt a pairwise net that takes the corresponding feature x (l) in the encoding layer to compute s i j . The CRFConv takes these two inputs to generate the restored feature via the message-passing module, as shown in Figure 1. Once the message-passing completes, the restored feature is further concatenated with the corresponding lower-level feature x (l) in the encoding layer to feed the next decoding layer after activation.

Unary Net. We simply take an MLP as the unary net, which conducts a pointwise feature transformation for the point features. The unary net plays the roles of dimension reduction and feature fusion in the decoding layers.

Pairwise Net. The pairwise net is used to compute the similarity s i j of each point pair (i, j). For each high-level point feature pair (x i , x j ), we compute its similarity with the corresponding point feature pair (x i , x j ) in a lower-level feature space. We adopt the Mahalanobis distance in the low-level feature space to compute the similarity s i j . The vanilla Mahalanobis distance is computed as:

d 2 (x i , x j ) = (x i -x j ) M(x i -x j ) = (x i -x j ) PP (x i -x j ) = P x i -P x j 2 2 , ( 20
)
where

x i , x j ∈ R d , M ∈ R d×d 0, P ∈ R d×d .
The Mahalanobis distance is actually the Euclidean distance on a projected space determined by the linear projection matrix P, which may fail to model nonlinear data effectively. In this paper, we reformulate P as a nonlinear projection to better model nonlinear data. We let the network learn a measure function automatically with an MLP. Thus, the improved Mahlanobis distance used in this paper can be computed as:

d 2 (x i , x j ) = MLP(x i ) -MLP(x j ) 2 2 . ( 21
)
Accordingly, the normalized similarity ŝi j is given as:

ŝi j = exp(-d 2 (x i , x j )) j∈N(i) exp(-d 2 (x i , x j )) , (22)
which can be easily implemented with a softmax layer in the network.

Classical discrete CRF as graph convolution

Most previous studies utilize the discrete CRF model to refine the labels in segmentation tasks, while our CRF is a continuous model defined in feature space. Hence our continuous CRF can work collaboratively with the classical discrete CRF to further improve the segmentation performance. In image segmentation, the energy function of the discrete CRF is usually defined as a pairwise model [START_REF] Krähenbühl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF]:

E(X) = i ψ u (x i ) + i j∈N(i) ψ p (x i , x j ), (23)
where x i ∈ L presents the label of pixel (node) i. Here L is a discrete label set. ψ u (x i ) ≥ 0 is the unary potential, which gives a penalty when each pixel is assigned a label. In the postprocessing CRFs, the unary potential can be simply computed as ψ u (x i ) = -log p(x i ), where p(x i ) is the probability predicted by a discriminative classifier. ψ p (x i , x j ) = µ(x i , x j )K(f i , f j ) is the pairwise potential, which penalizes two connected pixels with different labels.

Here, µ(•, •) measures the compatibility between different classes. K(•, •) : R d × R d → R + is a positive function defined on a feature space of the pixels. The update equation of the approximate distribution Q i in the mean-field approximation of Eq. ( 23) is given in [START_REF] Krähenbühl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF]:

Q * i (x i ) = 1 Z i exp -ψ u (x i ) - l∈L µ(x i , l) j∈N(i) K(f i , f j )Q j (l) . (24)
We show that Eq. ( 23) can also be used for point cloud segmentation. For each point i, let p i be the output probability vector of the segmentation network and q i be the vector version of Q i . Eq. ( 24) can be compactly rewritten as:

q * i = Softmax log(p i ) -C j∈N(i) w i j q j , (25)
where we denote w i j = K(f i , f j ). C ∈ R |L|×|L| is a matrix that encodes the compatibility of labels. Here, we have no constraint on C and learn it from the data. If we set C = I, it will degenerate to the Potts model, that is, µ(x i , x j ) = 0 if x i = x j otherwise 1, which is widely adopted in most previous image segmentation CRFs.

Algorithm 2 Message passing of the discrete CRF Input: Point cloud graph G P = (V P , E P ), initial distribution P = {p i |i ∈ V P }, maximum iteration step T . 1: Initialize: q i ← p i for i ∈ V P 2: Compute weights: w i j = K(f i , f j ) for e(i, j) ∈ E P 3: for t = 1 : T do 4:

for i ∈ V P do 5:

Message-passing: msg j→i = e(i, j)∈E P w i j q j 6:

Compatibility transformation: msg j→i = Cmsg j→i 7:

Add unary: q i = log(p i ) -msg j→i 8:

Normalize:

q i = Softmax( q i ) 9:
end for 10: end for Output: Approximate distribution Q = {q i |i ∈ V P }.

Eq. ( 25) can be formulated as another message-passing algorithm on the point cloud graph G P (V P , E P ), as shown in Algorithm 2. Analogous to CRFConv, we can further reformulate Algorithm 2 as another message-passing graph convolution for point cloud segmentation: Initial step:

h (0) i = p i , (26)
Message-passing step: Message:

m t i = j∈N(i) w i j h (t-1) j , (27)
Update:

h t i = Softmax log(p i ) -Cm t i , (28)
Readout step:

q i = h T i . (29)
Following [START_REF] Krähenbühl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF], we set w i j = M m=1 ω m k m (f i , f j ) as the linear combination of multiple Gaussian, where k m (f i ,

f j ) = exp -(f i -f j ) Σ -1 m (f i -f j ) .
Instead of adopting artificially designed parameters such as [START_REF] Krähenbühl | Efficient inference in fully connected crfs with gaussian edge potentials[END_REF], we learn ω m and Σ m of each Gaussian component from the data automatically. To ensure positive definition and avoid the inverse operation, we let Σ -1 m = PP , where P ∈ R d×d , which can be implemented with a linear layer having d outputs. Similarly, the weight sum operation can also be implemented with another linear layer having only one output. The data flow of the discrete CRF convolution layer is shown in Figure 4(b). It can be added at the end of our segmentation network as an additional graph convolution layer to form a dual CRF network. In addition, the whole network can be trained end-to-end.

Experiments

The experimental platform is a PC equipped with an Intel Core i7 9700K CPU, 16 GB RAM, and an Nvidia TITAN RTX GPU (24 GB). The algorithm is implemented with PyTorch [START_REF] Paszke | Pytorch: an imperative style, high-performance deep learning library[END_REF] and PyTorch Geometric[34] on Ubuntu 16.04.

Datasets

The experiments are conducted on various 3D point cloud segmentation datasets, including ShapeNet [START_REF] Yi | A scalable active framework for region annotation in 3d shape collections[END_REF] for object-level evaluation and S3DIS [START_REF] Armeni | 3d semantic parsing of large-scale indoor spaces[END_REF] and Semantic3D [START_REF] Hackel | Semantic3d.net: a new large-scale point cloud classification benchmark[END_REF] for indoor and outdoor scene-level evaluation.

ShapeNet. ShapeNet is a 3D object model dataset that contains 16,880 object models from 16 categories. Each 3D object consists of approximately 2k points. ShapeNet Parts is the part segmentation benchmark for the ShapeNet models, in which each model annotates 2 to 6 parts with a part label (50 parts in total). S3DIS. S3DIS is a large-scale indoor 3D scene segmentation dataset that was collected on six large-scale indoor areas from 3 different buildings. The scene is annotated with 13 categories (including clutter). Following [4], we organize the dataset by rooms (271 rooms in total). In our experiments, we split the training and test sets according to area.

Semantic3D. Semantic3D is a large-scale outdoor point cloud segmentation online benchmark. This benchmark provides a large labeled 3D point cloud dataset of natural scenes with over 4 billion points in total, which covers a range of diverse urban scenes. We conduct our experiments on the reduced-8 benchmark, which contains 15 scenes for training and 4 reduced scenes for testing with 8 semantic categories.

Experimental Settings

The encoder of our segmentation network contains five convolution blocks, each of which consists of two successive PointConv layers. The cloud resolution is reduced by the farthest point sampling (fps) with a ratio of r after each convolution block; additionally, the feature dimension d is doubled. In our experiment, we set r = [1.0, 0.25, 0.375, 0.375, 0.375] and d = [64, 128, 256, 512, 1024]. The decoder consists of four corresponding CRFConv layers to restore the cloud resolution to the original input size gradually. We use kNN to search the neighbors for each point. The kernel (neighbor) size k is set to 32 in the first layer and 16 in the remaining layers. The dilated kNN is only available in the encoder. We set the dilation rate dil = [1, 2, 4, 4, 2] in the five PointConv blocks. Two fully connected layers follow the last decoding layer to obtain per-point labels. The discrete CRF is added after the last fully connected layer if necessary. To make fair comparisons with the previous methods, the discrete CRF convolution is not adopted in the comparison experiments. The performance of the discrete CRF convolution is evaluated in the ablation study. The detailed network architecture and more experimental details can be found in the supplementary material.

Object-Level Evaluation

We conduct a shape part segmentation experiment on the ShapeNet Parts benchmark. Instead of training each category individually, we train a model with all part labels (50 in total). The normalized x, y, z position and the normal vector n x , n y , n z of each point are taken as the input features. Because our network supports various input point cloud sizes, we do not sample the points as in previous methods[4, 14,[START_REF] Li | Pointcnn: convolution on χ-transformed points[END_REF]. The intersection over union (IoU) of the object parts is used as the metric to evaluate the performance. The instance part IoU (pIoU) and mean class pIoU (mpIoU) are given in Table 1. Compared with nearly twenty current popular methods, the performance of the proposed method exceeds most previous methods. From Table 1, we can find that KPConv [START_REF] Thomas | Kpconv: flexible and deformable convolution for point clouds[END_REF] performs best overall, which may be due to the better feature encoding ability. Even compared with state-of-the-art methods, the proposed method can achieve competitive performance. Please see the supplementary material for some visualization results. Advanced Implementation. In conventional implementations, the network will require considerable computation to organized the structure of the point cloud (i.e., neighbor searching and cloud sampling). Therefore, some methods [START_REF] Thomas | Kpconv: flexible and deformable convolution for point clouds[END_REF][START_REF] Hu | Randla-net: efficient semantic segmentation of large-scale point clouds[END_REF] adopt a more computationally efficient method to organize the input point cloud blocks. In this strategy, the multiscale point cloud and the point neighbors at each scale are efficiently precomputed on the CPU. This strategy allows them to handle ten times the input size than the conventional implementation under the same time complexity, which is helpful for training the network on large-scale point clouds. To compare with them, we also employ this strategy as an advanced implementation for the proposed method and conduct experiments on scene-level benchmarks.

The advanced implementation is denoted as CRFConv+ to be distinct from the conventional implementation, which is denoted as CRFConv.

Indoor Scene Segmentation

The proposed method is evaluated on the S3DIS dataset for scene-level segmentation tasks. We adopt the normalized coordinates in the block and the corresponding RGB color as the input feature. We set the input point size to 8,192 for the conventional implementation (CRFConv) and 40,960 for the advanced implementation (CRFConv+). We take the overall accuracy (OA), mean accuracy (mACC), mean IoU (mIoU), and per class IoU as metrics to evaluate the performance. Since previous methods usually give the results on Area 5, we also report the results on this area in Table 2. From the experimental results, our method can achieve state-of-the-art performance with the precomputed multiscale strategy. For conventional implementation, the proposed method can also outperform some previous methods that prepare data in a conventional style, such as PointNet and PointCNN.

Outdoor Scene Segmentation

We further evaluate the proposed method on the large-scale outdoor 3D point cloud segmentation benchmark Semantic3D. We first uniformly downsample the training set before sampling blocks to maintain a voxel resolution of 0.01m3 , which is the as the reduced test set. The normalized position in the block and the corresponding RGB color are taken as the input features for the network. The input point cloud sizes are set to 8,192 and 65,536 for the conventional and advanced implementations, respectively. Because Semantic3D is an online benchmark, we submit the experimental results on the reduced-8 test set to the benchmark website. 3 The experimental results are also shown in Table 3. Note that only the published methods are listed in the table. From the table, the performance of RandLA-Net and SCF-Net is state-of-the-art overall. Next, the proposed method performs comparably with KPConv and BCM AFM, and outperforms the other methods.

Discussion

According to the experimental results for scene-level evaluation, the proposed method can perform well in both indoor and outdoor scenes, which demonstrates the robustness of our method. Overall, the proposed method performs better in indoor scenes because the outdoor scenes are usually more complex and biased than indoor scenes. In Table 3, we find that our method performs better on large or regular objects such as terrain and cars but worse on small or irregular objects such as vegetation and landscape. The reason can be explained by the fact that the former will benefit from the proposed CRF model, but the latter may be erroneously viewed as noise and smoothed by the CRF model in feature extraction, especially when the training samples involving the case are very limited. Actually, this phenomenon occurs not only in this dataset but will be magnified in a biased situation. We will try to address this problem in future works. In addition, we find that the advanced implementations with a precomputed multiscale strategy can largely improve the performance on both indoor and outdoor scenes compared with the conventional implementations. This is because the block sampling strategy damages the completeness of the continuous point cloud, especially when the block size is small, which may harm the overall performance in some way. In contrast, the precomputed multiscale strategy allow us to handle a larger input block size, which is helpful for network learning on scene-level point clouds. More visualization results on the scene-level datasets can be found in the supplementary material.

Ablation Study

To further evaluate the performance of the continuous/discrete CRF convolution, we conduct an ablation study on the S3DIS dataset for the proposed method. First, we compare the performance of the proposed method with/without the continuous/discrete CRF convolution. Table 4 shows the experimental results on Area 5. Note that the results in this section are conventionally implemented without merging labels. We adopt the same encoder for all models. In the baseline model, we remove the continuous CRF convolution in the decoder and only perform linear interpolation for point cloud upsampling. Baseline+discrete CRF denotes that we add the discrete CRF at the end of the baseline model. Baseline+continuous CRF employs continuous CRF convolution in the decoder, which is the general version of the proposed method. For baseline+dual CRF, we add the discrete CRF convolution at the end of the general version to form the dual CRF version of the proposed method. In Table 4, even the baseline model achieves promising performance, which can also prove the effectiveness of the encoder we designed. Compared with the baseline model, the model with continuous CRF has achieves a significant improvement. Although the discrete CRF also improves the performance in some way, the improvement effect is marginal. In traditional discrete CRF, the performance of the model depends largely on the unary term. In other words, the misclassified regions caused by the classifier are hard to correct by the discrete CRF. However, our continuous CRF model can fundamentally improve the presentation (location) ability of the point features, therefore avoiding such discrete CRF model limitations. Additionally, some visualization comparisons with/without the CRFConv are illustrated in Figure 5. We can see that the segmentation results of the CRFConv model look smoother and more complete than those of the baseline model in most cases, especially on some boundary areas (see office 2 and office 40). Some misclassified regions produced by the baseline model can also be corrected by the proposed CRFConv (see hallway 1).

The proposed CRFConv layer is flexible and scalable and can be used as a plug-and-play module for integrating into existing encoder-decoder networks to further improve their performance. In this section, we integrate CRFConv with RandLA-Net [START_REF] Hu | Randla-net: efficient semantic segmentation of large-scale point clouds[END_REF], which is one of the representative methods in the community, and conduct experiments on the S3DIS dataset. Specifically, we package the CRFConv as an upsampling layer and insert it into the decoding layers of the original RandLA-Net. All other settings follow the same schemes as the original paper. We report the results on Area5 in Table 5. In the table, our CRFConv can further improve its performance, which also proves the effectiveness of the proposed CRFConv. Through this experiment, we demonstrate that the proposed method has a certain generality that can improve the performance of the network independent of specific encoders.

Parameter Analysis

The mean-field step T of our CRFConv is a flexible parameter, which allows us to adopt different mean-field steps for the training and test phases. In training, we set the mean-field step as 1 for efficiency and to avoid vanishing/exploding gradients. Therefore, we evaluate the performance of various mean-field steps in the test phase. The performance of different mean-field steps on the validation set is illustrated in Figure 6. According to this figure, the continuous CRF performs best when the mean-field step is approximately 10. With the increase in the mean-field steps, the performance tends gradually become saturated. Owing to the fidelity ability of CRFConv, we do not observe obvious performance degradation caused by oversmoothness, which may occur in most current popular graph convolutions. However, we find that the model performs best when it is about to converge rather than converge. When the model converges, the feature may become smoother, which may be harmful to some small or irregular objects. This can explain why the performance decreases slightly when the CRF reaches convergence. This experimental result is also coincident with our analysis of the outdoor scenes.

Time complexity

In this section, we conduct a runtime analysis of the proposed method. First, the runtime of the proposed method with/without the precomputed multiscale strategy is given. Then, we additionally make a runtime comparison with some previous methods. Specifically, we choose the S3DIS benchmark for this experiment and run the previous methods on our experimental platform. The experimental setting follows the original paper. We give both the training and test runtime of each iteration including data preparation. To make a fair comparison, we make the input point cloud size of our method the same as previous methods. Note that, because KPConv adopts various input sizes, we report an approximate value here. The experimental results are shown in Table 6. From the table, we find that PointNet is the most efficient method because of its simple architecture. Although the overall runtime of the proposed method is higher than that of previous methods, the proposed CRFConv module only adds a small runtime cost to the backbone network in both training and testing. Moreover, due to the precomputed multiscale strategy, the efficiency of the network greatly improved. This strategy allows us to handle a larger batch size but with lower time complexity.

Conclusion

In this paper, we addressed the problem of point cloud segmentation. First, we proposed a continuous CRF graph convolution to capture the structure of the point features, by which the representation ability of the features improved.

Then, we designed an encoder-decoder point cloud segmentation network based on the proposed continuous CRF convolution. The continuous CRF convolution embedded in the decoder can restore the details of the high-level features produced by the encoder to enhance the localization ability of the network. Furthermore, we also showed how to formulate the discrete CRF as another message-passing graph convolution and combined it with the continuous CRF convolution, by which we modeled the data affinity not only in feature space but also in label space to further improve the segmentation results. Experiments on various datasets demonstrated the effectiveness of the proposed method.

However, compared with indoor scenes, we find that the proposed method performs worse in outdoor scenes that are usually more complex and biased than the former. In this case, the CRF model erroneously viewed some small or irregular objects as noise in feature extraction, especially when the number of training samples involving the case was very limited. This situation may be relieved by increasing the input point cloud size with the precomputed multiscale strategy. In the future, we will attempt to address this problem. In this work, we focused the decoding of the point cloud features and achieve promising results. However, the overall performance of the network depends on more than one aspect. For example, the feature encoder may play a decisive role. In future work, we will also attempt to investigate more feature encoding methods, such as convolution in the point cloud domain. Moreover, we will continue exploring the feasibility of integrating graph neural networks with probabilistic graphical models.

The proof of Theorem 1

Problem statement:

Given a continuous CRF defined on graph G(V, E), its corresponding Gibbs distribution can be written as:

P(X) = 1 Z exp(-E(X)), (1)
where the X = {x i ∈ R d |i ∈ V} denotes the set of all latent features, Z is a partition function to ensure a distribution. The energy function E(X) is defined as a continuous quadratic energy model:

E(X) = i∈V (x i -z i ) (x i -z i ) + i∈V j∈N(i) (x i -x j ) w i j (x i -x j ), (2)
where z i denotes the observed feature of node i. N(i) denotes the neighbor nodes set of node i in G. w i j ∈ R d×d 0 is the weight matrix of two connected nodes in G.

Let Q(X) = i Q i (x i ) be the approximate distribution of P(x), where Q i ∼ N(µ i , Σ i ). Our object is to obtain {(µ * i , Σ * i )|i ∈ V} by solving the following problem:

{(µ * i , Σ * i )|i ∈ V} = argmin {(µ i ,Σ i )|i∈V} KL(Q||P), (3)
where

KL(Q||P) = Q(X) log Q(X) P(X) dX (4)
is the KL-divergence between Q(X) and P(X).

Solution:

{(µ * i , Σ * i )|i ∈ V} = argmin {(µ i ,Σ i )|i∈V} KL(Q||P) = argmin {(µ i ,Σ i )|i∈V} Q(X) log Q(X)dX - Q(X) log P(X)dX = argmin {(µ i ,Σ i )|i∈V} i∈V Q i (x i ) log Q i (x i )dx i + Q(X)E(X)dX + log Z constant = argmin {(µ i ,Σ i )|i∈V} - i∈V H Q i [x i ] + E X∼Q [E(X)] = argmin {(µ i ,Σ i )|i∈V} - 1 2 i∈V log |Σ i | + d(log 2π + 1) constant + E X∼Q [E(X)] = argmin {(µ i ,Σ i )|i∈V} - 1 2 i∈V log |Σ i | + i∈V E x∼Q [x i x i ] -2 i∈V E x∼Q [z i x i ] + i∈V E x∼Q [z i z i ] constant + i∈V j∈N(i) E x∼Q [x i w i j x i ] -2 i∈V j∈N(i) E x∼Q [x i w i j x j ] + i∈V j∈N(i) E x∼Q [x j w i j x j ] = argmin {(µ i ,Σ i )|i∈V} - 1 2 i∈V log |Σ i | + i∈V E x∼Q [tr(x i x i )] -2 i∈V E x∼Q [z i x i ] + i∈V j∈N(i) E x∼Q [tr(x i w i j x i )] -2 i∈V j∈N(i) E x∼Q [tr(x i w i j x j )] + i∈V j∈N(i) E x∼Q [tr(x j w i j x j )] = argmin {(µ i ,Σ i )|i∈V} - 1 2 i∈V log |Σ i | + i E x∼Q [tr(x i x i )] -2 i∈V E x∼Q [z i x i ] + i∈V j∈N(i) E x∼Q [tr(x i x i w i j )] -2 i∈V j∈N(i) E x∼Q [tr(x j x i w i j )] + i∈V j∈N(i) E x∼Q [tr(x j x j w i j )] = argmin {(µ i ,Σ i )|i∈V} - 1 2 i∈V log |Σ i | + i∈V tr(E x∼Q [x i x i ]) -2 i∈V E x∼Q [z i x i ] + i∈V j∈N(i) tr(E x∼Q [x i x i ]w i j ) -2 i∈V j∈N(i) tr(E x∼Q [x j x i ]w i j ) + i∈V j∈N(i) tr(E x∼Q [x j x j ]w i j ) = argmin {(µ i ,Σ i )|i∈V} - 1 2 i∈V log |Σ i | + i∈V tr(Σ i + µ i µ i ) -2 i∈V z i µ i + i∈V j∈N(i) tr((Σ i + µ i µ i )w i j ) -2 i∈V j∈N(i) tr((µ j µ i )w i j ) + i∈V j∈N(i) tr((Σ j + µ j µ j )w i j ) = argmin {(µ i ,Σ i )|i∈V} i∈V µ i µ i -2 i∈V z i µ i + i∈V j∈N(i) µ i w i j µ i -2 i∈V j∈N(i) µ i w i j µ j + i∈V j∈N(i) µ j w i j µ j temrs consist of {µ i |i ∈ V} + - 1 2 i∈V log |Σ i | + i∈V tr(Σ i ) + i∈V j∈N(i) tr(Σ i w i j ) + i∈V j∈N(i) tr(Σ j w i j ) temrs consist of {Σ i |i ∈ V} . (5)
2

To minimize µ i and Σ i , we only need to concern about the terms which contains µ i and Σ i in Eq. ( 5), respectively. For µ i , we have

µ * i = argmin µ i µ i µ i -2z i µ i + j∈N(i) µ i w i j µ i -2 j∈N(i) µ i w i j µ j = argmin µ i µ i I + j∈N(i) w i j µ i -2z i µ i -2µ i j∈N(i) w i j µ j . (6)
For Σ i , we have

Σ * i = argmin Σ i - 1 2 log |Σ i | + tr(Σ i ) + j∈N(i) tr(Σ i w i j ) = argmin Σ i tr Σ i I + j∈N(i) w i j - 1 2 log |Σ i | (7)
Compute the gradients of Eq. ( 6) and Eq. ( 7) with respect to µ i and Σ i respectively and let the gradients to be zero, we can get the update equations of µ * i and Σ * i :

µ * i = I + j∈N(i) w i j -1 z i + j∈N(i)
w i j µ j (8)

Σ * i = 1 2 I + j∈N(i) w i j -1 (9)
To maximize Q(X), we only need to compute µ i for all Q i (x i ). It can be found that the update equation of µ i in the mean-field approximation is the same as that of x i in the coordinate descent algorithm, by which Theorem 1 can be proven.

The relationship with diffusion

Consider an anisotropic diffusion process on a heat field H defined on graph G H . Denote h t as the heat vector of H at time t on G H . And let L H = I -D -1 H W H be the normalized Laplacian matrix of G H , where D H and W H are the degree and adjacent matrix, respectively. The diffusion process on G H can be described as the following PDE with a discrete form:

h t+1 -h t = -cL H h t , (10)
where c is a diffusion coefficient to control the diffusion speed.

In the diffusion process, the heat field is a scalar field. By unfolding Eq. ( 10), we can obtain the temperature h t i in the heat field H for any position i and time t:

h t+1 i = h t i -c j∈N(i) w i j (h t i -h t j ) = 1 2 (h t i + j∈N(i) w i j h t j ) (by setting c = 1 2 ), (11)
where w i j is the weight of two adjacent nodes. If we set the compatibility transform matrix C = I in our model, that is, each channel is independent of others, we can find that our CRFConv is equivalent to a diffusion model built on each channel individually at time t = 0. However, when t > 0, the difference between the diffusion process and our CRFConv is that the diffusion process adds the previous state at each iteration while our CRFConv always adds the initial state at each iteration. Furthermore, when the diffusion process reaches the stable state, we have L H h = 0, which is the solution of

h * = argmin h h L H h, (12)
where h T L H h is the Dirichlet energy. It can be found that the Dirichlet energy only acts as the smoothness term of our CRF model. That is to say, the diffusion-based methods only ensure the smoothness but ignore the uniqueness of features, which could cause over smoothness, while the proposed method does. In other words, our CRFConv can overcome the over smoothness phenomenon usually occurred in current popular graph convolution methods. Moreover, the diffusion-based methods suppose that each channel is independent of the others, while our CRFConv models the relations between each channel by a compatibility transformation matrix C which can be learned from the data automatically to improve the representation ability of the model.

More experimental details and results

Implementation details

The details of the point cloud segmentation network can be found in Table 1. Note that the Batch Normalization with the momentum of 0.98 and the LeakyReLU with the negative slope of 0.1 are added after each convolution layer. For brevity, we did not show them in Table 1. We construct the point cloud graph based on kNN in both the encoder and the decoder. The dilated kNN is only available for the PointConv in the encoder. The momentum stochastic gradient descent (SGD) algorithm is used to minimize the cross entropy-loss, with a momentum of 0.95. We take an exponential decay strategy for the learning rate with initial rate of 0.01. The decay rate is set to ensure the learning rate is divided by 10 every 50 epochs. The network will reach convergence within 100 epochs. The batch sizes are set to 16 and 8 for the conventional and advanced (with precomputed multiscale strategy) implementations, respectively.

Figure 1 :

 1 Figure 1: The data flow of the message-passing module of the proposed graph convolution.

Figure 2 :

 2 Figure 2: Overview of the proposed point cloud segmentation network. The red dotted circles indicate where the CRFConv was embedded.

Figure 3 :

 3 Figure 3: The PointConv used in the encoding layers. Note that in the residual path, pooling and 1 × 1 convolution are adopted to align the point cloud size or feature dimension if necessary.

  (a) The continuous CRF convolution layer. (b) The discrete CRF convolution layer.

Figure 4 :

 4 Figure 4: The continuous and discrete CRF convolution layer used in the point cloud segmentation network. The data flow of the message-passing modules here can be represented with Figure 1.

Figure 5 :Table 5 :

 55 Figure 5: Visualization comparisons of the baseline model and the CRFConv model. We show three rooms in area 5 of the S3DIS dataset, that is, hallway 1 on the top left, office 2 on the right, and office 40 on the bottom left. The results are visualized in the bird view from the upper axis.Note that the "ceilings" category is removed manually for better visualization. The regions marked by green circles show some significant local differences.

Figure 6 :

 6 Figure 6: The test performance of the CRFConv on various mean-field steps.

Figure 1 : 6 Figure 2 :

 162 Figure 1: Visualization results compared with the groundtruth on the ShapeNet Part dataset. Three samples are shown for each object category, in which each part is visualized in a unique color.

Figure 3 :

 3 Figure 3: Visualization results compared with the groundtruth on the validation set of the Semantic3D dataset. Each class is visualized in a unique color. Note that the "unlabeled" category is removed manually for better visualization.

Table 1 :

 1 Performance of the proposed method on the ShapeNet Part segmentation benchmark.MethodspIoU mpIoU air bag cap car chair ear guitar knife lamp laptap motor mug pistol rocket bord tabel

5.4. Scene-Level Evaluation 5.4.1. Data Preparation Conventional Implementation. Scene-level point cloud data are more complex than object-level data. The former is spatially continuous and usually nonuniform in density and cannot be processed by the network directly. Following [4, 14, 5], we sample blocks from a scene point cloud in training and testing. For indoor scenes, the point cloud is first collected by rooms. Then, each block is randomly sampled from each room. For outdoor scenes, we directly sample blocks from each scene. To control the block size, we then uniformly sample N points in each block to feed the network. In training, the blocks are randomly sampled from the training set in each epoch. In the test, we sample multiple blocks in the test set until each point is evaluated at least once. After that, the final per-point labels can be obtained by voting. In this strategy, neighbor searching and cloud sampling are computed directly in the network. We adopt this strategy as a conventional implementation in scene-level evaluation experiments.

Table 2 :

 2 Performance of the proposed method on the Stanford S3DIS dataset (Area 5).MethodsOA mACC mIoU ceil. floor wall beam col. wind. door table chair sofa book. board clut. ] 88.9 73.1 65.4 92.9 97.9 82.3 0.0 23.1 65.5 64.9 78.5 87.[START_REF] Li | Pointcnn: convolution on χ-transformed points[END_REF] 61.4 70.7 68.7 57.2 CRFConv (ours) 88.4 68.6 62.0 94.0 97.5 81.8 0.0 21.7 62.2 45.4 78.1 85.2 51.1 71.8 61.7 55.7 CRFConv+ (ours) 89.2 73.7 66.2 93.3 96.3 82.2 0.0 23.7 60.3 68.2 82.4 86.0 63.4 73.8 72.4 58.9

	2017	PointNet[4] SegCloud[49]	--	49.0 41.1 88.8 97.3 69.8 0.1 3.9 46.3 10.8 58.9 52.6 5.9 40.3 26.4 32.2 57.4 48.9 90.1 96.1 69.9 0.0 18.4 38.4 23.1 70.4 75.9 40.9 58.4 13.0 41.6
	2018 2019 2020 2021	Eff 3D Conv[50] TangentConv[51] --RNN Fusion[52] -PointCNN[5] 85.9 63.9 57.3 92.3 98.2 79.4 0.0 17.6 22.8 62.1 74.4 80.6 31.7 66.7 62.1 56.7 68.3 51.8 79.8 93.9 69.0 0.2 28.3 38.5 48.3 73.6 71.1 59.2 48.7 29.3 33.1 62.2 52.6 90.5 97.7 74.0 0.0 20.7 39.0 31.3 77.5 69.4 57.3 38.5 48.8 39.8 63.9 57.3 92.3 98.2 79.4 0.0 17.6 22.8 62.1 80.6 74.4 66.7 31.7 62.1 56.7 SPGGraph[44] 86.4 66.5 58.0 89.4 96.9 78.1 0.0 42.8 48.9 61.6 84.7 75.4 69.8 52.6 2.1 52.2 PCNN[42] -67.0 58.3 92.3 96.2 75.9 0.3 6.0 69.5 63.5 66.9 65.6 47.3 68.9 59.1 46.2 GACNet[32] 87.8 -62.9 92.3 98.3 81.9 0.0 20.4 59.1 40.9 78.5 85.8 61.7 70.8 74.7 52.8 PointWeb[53] 87.0 66.6 60.3 92.0 98.5 79.4 0.0 21.1 59.7 34.8 76.3 88.3 46.9 69.3 64.9 52.5 KPConv rigid[6] -70.9 65.4 92.6 97.3 81.4 0.0 16.5 54.5 69.5 80.2 90.1 66.4 74.6 63.7 58.1 KPConv deform[6] -72.8 67.1 92.8 97.3 82.4 0.0 23.9 58.0 69.0 81.5 91.0 75.4 75.3 66.7 58.9 FPConv[54] --62.8 94.6 98.5 80.9 0.0 19.1 60.1 48.9 80.6 88.0 53.2 68.4 68.2 54.9 SegGCN 88.2 70.4 63.6 93.7 98.6 80.6 0.0 28.5 42.6 74.5 80.9 88.7 69.0 71.3 44.4 54.3 PointASNL[55] 87.7 68.5 62.6 94.3 98.4 79.1 0.0 26.7 55.2 66.2 83.3 86.8 47.6 68.3 56.4 52.1 PAConv[47] -72.3 65.6 93.1 98.4 82.6 0.0 22.6 61.3 63.3 78.5 88.0 64.5 73.5 70.1 57.3 BCM+AFM[56

Table 3 :

 3 Performance of the proposed method on the Semantic3D dataset (reduced-8).

		Methods	OA mACC mIoU	man-made terrain	natural terrain	high vegetation	low vegetation	buildings	hard scape	scanning artefacts	cars
	2017	SnapNet[57] 88.6 70.8 59.1 SEGCloud[49] 88.1 73.1 61.3	82.0 83.9	77.3 66.0	79.7 86.0	22.9 40.5	91.1 91.1	18.4 37.3 64.4 30.9 27.5 64.3
	2018	RF MSSF[58] 90.3 71.6 62.7 MSDVN[59] 88.4 77.2 65.3 SPGraph[44] 94.0 79.6 73.2	87.6 83.0 97.4	80.3 67.2 92.6	81.8 83.8 87.9	36.4 36.7 44.0	92.2 92.4 93.2	24.1 42.6 56.6 31.3 50.0 78.2 31.0 63.5 76.2
	2019 2020 2021	ShellNet[60] 93.2 79.7 69.3 GACNet[61] 91.9 79.5 70.8 KPConv[6] 92.9 81.4 74.6 RandLA-Net[48] 94.8 84.1 77.4 FGCN[62] -89.3 62.4 BCM+AFM[56] 94.3 -75.3 SCF-Net[63] 94.7 85.2 77.6 CRFConv (ours) 93.5 78.4 72.5 CRFConv+ (ours) 94.2 84.1 74.9	96.3 86.4 90.9 95.6 90.3 96.3 97.1 95.0 98.1	90.4 77.7 82.2 91.4 65.2 93.7 91.8 93.1 91.1	83.9 88.5 84.2 86.6 86.2 87.7 86.3 86.4 81.8	41.0 60.6 47.9 51.5 38.7 48.1 51.2 40.8 44.8	94.2 94.2 94.9 95.7 90.1 94.6 95.3 93.3 95.2	34.7 43.9 70.2 37.3 43.5 77.8 40.0 77.3 79.7 51.5 69.8 76.8 31.6 28.8 68.2 43.8 58.2 79.5 50.5 67.9 80.7 33.7 60.5 76.8 40.8 59.4 88.0

Table 4 :

 4 Performance of the proposed method under different module configurations.

	Models	OA	mACC	mIoU
	Baseline Baseline+Discrete CRF Baseline+Continuous CRF (general version) Baseline+Dual CRF (dual CRF version)	89.78 90.01 90.13 90.31	66.25 66.51 67.91 68.12	59.36 59.88 61.22 61.54

Table 6 :

 6 Runtime analysis of the proposed method.

	Methods	Batch Size	Precomputed Multiscale	Training Time (ms/iter)	Test Time (ms/iter)
	PointNet[4] PointNet++(SSG)[14] PointNet++(MSG)[14] KPConv[6] RandLA-Net[48] Baseline (ours) Baseline+CRFConv (ours) RandLA-Net+CRFConv (ours)	16 × 4096 16 × 4096 16 × 4096 ≈ 8 × 15000 8 × 40960 8 × 8192 8 × 40960 8 × 8192 8 × 40960 8 × 40960	No No No Yes Yes No Yes No Yes Yes	138 532 694 552 760 935 909 1141 990 815	98 495 633 271 448 475 625 653 667 485

Table 1 :

 1 Detailed architecture of the proposed point cloud segmentation network.

	Modules	Layers
		conv 1	PointConv(in dims=F, out dims=64,kernel size=32, dil=1, ratio=1.0) PointConv(in dims=64, out dims=64, kernel size=32, dil=1, ratio=1.0)
		conv 2	PointConv(in dims=64, out dims=128, kernel size=16, dil=2, ratio=0.25) PointConv(in dims=128, out dims=128, kernel size=16, dil=2, ratio=1.0)
	Encoder	conv 3	PointConv(in dims=128, out dims=256, kernel size=16, dil=4, ratio=0.375) PointConv(in dims=256, out dims=256, kernel size=16, dil=4, ratio=1.0)
		conv 4	PointConv(in dims=256, out dims=512, kernel size=16, dil=4, ratio=0.375) PointConv(in dims=512, out dims=512, kernel size=16, dil=4, ratio=1.0)
		conv 5	PointConv(in dims=512, out dims=1024, kernel size=16, dil=2, ratio=0.375) PointConv(in dims=1024, out dims=1024, kernel size=16, dil=2, ratio=1.0)
		deconv 4	CRFConv(unary dims=1024, pairwise dims=512, out=512, kernel size=16)
		deconv 3	Linear(in dims=512+512, out dims=512) CRFConv(unary dims=512, pairwise dims=256, out dims=256, kernel size=16)
	Decoder	deconv 2	Linear(in dims=256+256, out dims=256) CRFConv(unary dims=256, pairwise dims=128, out dims=128, kernel size=16)
		deconv 1	Linear(in dims=128+128, out dims=128) CRFConv(unary dims=128, pairwise dims=64, out dims=64, kernel size=16)
	Classifier	fc 1 fc 2	Linear(in dims=64+64, out dims=256) LeakyReLU(negative slope=0.1) Linear(in dims=256, out dims=L) Softmax(dim=-1)
	Discrete CRF (optional)	DiscreteCRFConv(in dims=L, out dims=L, kernel size=32)

Code is available at https://github.com/yangfei1223/CRFConv.

s i j is task-relevant and can be learned from data. We specify its form in the next section.

http://semantic3d.net/view_results.php?chl=2

Acknowledgment

This work is partially supported by National Natural Science Foundation of China under Grant Nos 61872188, 61703209, U1713208, 61972204, 61672287, 61861136011, 61773215, and by the French Labex MS2T ANR-11-IDEX-0004-02 through the program Investments for the future.

Supplementary Material of Continuous Conditional Random Field Convolution for Point Cloud Segmentation

Fei Yang a,b , Franck Davoine c , Huan Wang b , Zhong Jin a,b, *


David Sohr
email: david.sohr@schott.com

Jens Ulrich Thomas

Bernd Hoppe

Stefan Skupin

Combining glass cutting and edge shaping by using optical Airy beams

Using an optical Airy beam we created curved permanent modifications in borosilicate glass and achieved separation of a 525 µm thick glass sheet with a convex edge with a radius of curvature of 774 µm after etching.

For reasons reaching from practical purposes, such as improved handling and durability, to decorative considerations, processed glass is often required to have a seamed or round edge. Currently this requires an extra grinding step to obtain for example the most common curved shape, the so called "c-cut". For the preceding processing step of cutting the glass to shape, ultra short pulse lasers with their beams shaped to an elongated focal volume (line focus) are increasingly replacing conventional cutting tools [START_REF] Mishchik | Improved laser glass cutting by spatio-temporal control of energy deposition using bursts of femtosecond pulses[END_REF][START_REF] Jenne | Facilitated glass separation by asymmetric bessel-like beams[END_REF]. These straight line foci can be used to modify the workpiece throughout its entire depth with one single laser shot, effectively perforating it instantaneously, instead of having to dig into the material, as for example by ablation [START_REF] Mathis | Micromachining along a curve: Femtosecond laser micromachining of curved profiles in diamond and silicon using accelerating beams[END_REF]. This way single pass laser glass cutting up to a thickness of 12 mm has been demonstrated with a Bessel-like beam [START_REF] Jenne | Facilitated glass separation by asymmetric bessel-like beams[END_REF]. Here, we report on combining cutting and edge shaping of glass in one laser process. To this end, we replace the Bessel-like beam in the aforementioned micromachining setup with an Airy-Gauss beam to directly achieve a curved edge as the result of the cutting process. We used a 2f setup as shown in Fig. 1 a), imaging the cubic phase produced by a diffractive optical element (DOE) with a microscope objective (MO) to create an Airy-Gauss beam. The main lobe of this beam appears to be accelerated in the transverse plane during propagation, yielding a curved line focus with a parabolic trajectory in the longitudinal plane, see Fig. 1 b). While the cubic phase mask was fixed in our experiments, we used the focal length f of the microscope objective for scaling the line focus [START_REF] Polynkin | Curved plasma channel generation using ultraintense airy beams[END_REF][START_REF] Sohr | Shaping convex edges in borosilicate glass by single pass perforation with an airy beam[END_REF]. We found that the volume modifications resulting from placing the focus deep within a glass sheet show the expected curvature for a wide range of experimental parameters (see Fig. 2 a)). With increasing pulse energy the trajectory remains unchanged while the length and lateral extent of the modifications increase, for f = 20 mm reaching lengths of up to 2 mm and a maximum angle a max = 11 • . More confined and stronger modifications are observed for longer pulse durations. Simulations of the energy deposition employing an unidirectional pulse propagation model accounting for all relevant nonlinear propagation effects, in particular the laser-generated conduction electrons [START_REF] Caulier | Femtosecond laser pulse train interaction with dielectric materials[END_REF], corroborate this observation: For the short pulses the laser affected zone is much broader due to intensity clamping, resulting in high absorption, but a low energy confinement. The broadening of the modification is reinforced due to the low focal contrast between the main lobe and the side lobes of the Airy beam. This low contrast is particularly important near the glass surface when perforating glass sheets, as the threshold for laser induced damage is higher in volume than at the surface. We found that an intermediate pulse duration of 5 ps in combination with a burst mode operation emitting 2 pulses with a delay of 25 ns per burst results in low surface damage while still creating a sufficiently strong volume damage throughout the glass sheet. With these laser parameters we achieved single pass perforation of a 525 µm thick glass sheet for f = 10 mm. Using a well established etching process with potassium hydroxide [START_REF] Gottmann | Microcutting and hollow 3d microstructures in glasses by in-volume selective laser-induced etching (isle)[END_REF] allowed us to separate the glass along a perforation line, thus obtaining a well defined convex edge down to a radius of curvature of 774 µm as shown in Fig. 2 b). For this first demonstration of using the Airy beam for glass cutting we placed the vertex of the parabolic trajectory below the center of the glass sheet to compensate the preferential energy deposition in front of the linear focus (Fig. 2 a)/b)). In a future experiment we plan to shift the intensity distribution with respect to the vertex of the parabola [START_REF] Hu | Self-accelerating airy beams: Generation, control, and applications[END_REF] to achieve a more symmetric edge.

Fig. 1 .

 1 Fig. 1. Experimental 2f-setup (a) used for creating an Airy-Gauss beam and resulting theoretical intensity profiles (b) for focal length f = 10 mm.

Fig. 2 .

 2 Fig. 2. Light microscopy cross sections of permanent in-volume modifications in glass (a) follow the expected curved trajectory. Corresponding deposited energy densities in the focal plane (insets) obtained from numerical simulations confirm a higher confinement of deposited energy for long pulses. Result of cutting a a 525 µm thick glass sheet by perforation with an Airy beam and subsequent etching is shown in (b). The cross section view parallel to the line of laser modifications shows the curved profile of the cut.


domain: chim.anal chim sde

text:
Nina Huynh

Emilie Caupos

Caroline Soares Peirera

Julien Le Roux

Adèle Bressy

Régis Moilleron

How important is the sample preparation step for non-target screening of micropollutants in urban waters?

Introduction Methods

Results

Conclusions

Objectives

Acknowledgment:

Distribution of HRMS features retained on X-AW

The Multilayer cartridge (HLB, ENV+, X-AW, X-CW):

• is the most effective at retaining a large range of HRMS features • is less affected by the adsorption of dissolved organic matter • takes advantage of the four phases in terms of diversity of compounds Ongoing investigation: better characterize the chemical space (log Kow, pKa, chemical functions…) covered by each cartridge. This could help determining the relevance of each type of cartridge towards specific purposes (e.g., focus on more polar compounds).

• Based on EEM spectra, regions II and IV were well retained by X-AW and Multilayer (≥ 80%). Those regions can be associated with simpler, more polar and nitrogenous compounds (Zhang et al., 2008).

These cartridges seem to be the most efficient to retain hydrophobic materials as well as smaller and more polar compounds for a global screening of the molecules present in the sample.

Multilayer is the cartridge with the highest number of specific features (323 features only found in this cartridge), but also the one with the highest number of intersected features (20 intersections with features find on other tested cartridges for a total of 212 features intersected), making it the most interesting cartridge for non-target studies by retaining the most extensive set of features (i.e., with diverse properties).

Distribution of HRMS features retained on HLB Distribution of HRMS features retained on Multilayer

UV 254 retention = 32%

Panel of 9 commercially-available (HLB, C18, X-AW, X-CW, SDBL, ENV+, C18/ENV+, X-A, X-C) stationary phases + 1 home-made multilayer cartridge X-AW exhibits high retention of fluorescent materials but few features in HRMS which is the total opposite of HLB. This can be associated with a higher retention of dissolved organic matter which could contribute to a competition with the retention of organic compounds.

However, Multilayer does not seem to suffer such matrix effects, retaining both high content of fluorophores and organic compounds. Moreover, Multilayer retains molecules with a wider range of molecular weight, making it interesting for the screening of a large range of micropollutants.

Characteristics of the features retained on Multilayer:

• 594 retained features = 47 % more than HLB which is often considered as an universal cartridge • Average m/z = 470.6467 (on a range from 100 to 1000) which shows its ability to retain molecules with low and high molecular weight together • Average retention time = 47% of the chromatographic gradient, which shows that the compounds retained have a large range of polarity

  Testing different natures of phases for solid phases extraction (SPE) to retain a large range of micropollutants on real samples • Developing a strategy based on different types of relevant indicators to compare the results in NTS • Applying the developed strategy on urban water samples Non-target screening (NTS) has gained interest in recent years for environmental monitoring purposes because it enables the analysis of a large number of pollutants without predefined lists of molecules. However, sample preparation methods are diverse, and few have been systematically compared in terms of amount and relevance of the information obtained by subsequent NTS analysis. after SPE on X-AW EEM after SPE on HLB EEM after SPE on Multilayer (HLB, ENV+, X-AW, X-CW, based on Kern et al., 2009) Evaluation of the retention ability Discrimination based on HRMS features

  600 nm] matrix (EEM)