{'fraction_non_alphanumeric': 0.03389218467887542, 'fraction_numerical': 0.011245808614908434, 'mean_word_length': 4.430252100840336, 'pattern_counts': {'":': 0, '<': 1, '<?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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
3D Dynamic Point Cloud Inpainting via Temporal Consistency on Graphs

With the development of 3D laser scanning techniques and depth sensors, 3D dynamic point clouds have attracted increasing attention as a representation of 3D objects in motion, enabling various applications such as 3D immersive tele-presence, gaming and navigation. However, dynamic point clouds usually exhibit holes of missing data, mainly due to the fast motion, the limitation of acquisition and complicated structure. Leveraging on graph signal processing tools, we represent irregular point clouds on graphs and propose a novel inpainting method exploiting both intra-frame self-similarity and inter-frame consistency in 3D dynamic point clouds. Specifically, for each missing region in every frame of the point cloud sequence, we search for its self-similar regions in the current frame and corresponding ones in adjacent frames as references. Then we formulate dynamic point cloud inpainting as an optimization problem based on the two types of references, which is regularized by a graph-signal smoothness prior. Experimental results show the proposed approach outperforms three competing methods significantly, both in objective and subjective quality.


INTRODUCTION
3D dynamic point cloud is a natural representation of arbitrarily-shaped 3D objects in motion. It consists of a sequence of point clouds, each of which is a set of points. Each point corresponds to a measurement point, which contains 3D geometric coordinates and possibly attributes such as color and normal. The acquisition of dynamic point clouds becomes convenient with the development of depth sensing and 3D laser scanning techniques 1 , thus enabling a variety of applications such as navigation in autonomous driving, animation, gaming and virtual reality [2].
Nevertheless, 3D dynamic point clouds often exhibit holes of missing data inevitably, as shown in Fig. 1. This is mainly due to complicated object structure, fast object motion, inherent limitations of the acquisition equipments and incomplete scanning views. Besides, the object itself may have some missing regions (e.g., dilapidated heritage). Therefore, it is necessary to inpaint incomplete point clouds prior to the subsequent applications. Nevertheless, 3D dynamic point cloud inpainting is challenging to address, because each frame is irregularly sampled with possibly different numbers of points. Further, there is no explicit temporal correspondence between points over time.
However, the direct inpainting of 3D dynamic point cloud has been largely overlooked so far in the literature, while several approaches have been proposed for static point clouds. These methods mainly include two categories according to the cause of holes: 1) restore holes in the object itself such as heritage and sculptures [3][4][5][6][7][8][9], and 2) inpaint holes caused by the limitation of scanning devices [10][11][12][13][14][15][16][17]. For the first class, the main hole-filling data source is online database, as the holes are often large. Sahay et al. [5] project the point cloud to a depth map, search a similar one from an online depth database via dictionary learning for inpainting, while the projection process inevitably introduces geometric loss. Instead, Dinesh et al. [8,9] search best matching regions in the object itself based on the smallest rotation difference to fill the missing area. The results still suffer from geometric distortion due to the simple data source.
The other class of methods focus on holes generated due to the limitations of scanning devices, which is smaller and more fragmentary than the aforementioned ones in general. Wang et al. [10] and Quinsat et al. [11] create a triangle mesh from the input point cloud and fill holes in the mesh for final interpolation. These methods rely on the quality of mesh construction though. Lozes et al. [12,13] deploy partial difference operaters to solve an optimization problem on the point cloud. Muraki et al. [15] generate a surface to fit the vicinity of the hole and interpolate the surface for inpainting. Due to the reference from local neighborhood only, their results tend to be more planar than the ground truth, and artifacts are likely to occur around the boundary in complicated structure. Fu et al. [16,17] exploit the non-local similarity in the point cloud, which inpaints holes from their most similar regions based on normals of points.
Nevertheless, all above methods are not tailored for dynamic point clouds. If we apply them to a point cloud sequence frame by frame, the inpainting process of each frame is independent to each other, which neglects the inter-frame correlation and is thus sub-optimal. To this end, as an extension to the inpainting method in [17], we exploit both intraframe self-similarity and inter-frame consistency in the geometry for dynamic point cloud inpainting. For each target region which contains a hole in the target frame, our key idea is to search its most similar region in the target frame as well as its corresponding regions in the adjacent frames as source regions, and then inpaint the hole from these source regions.
Due to the irregularity of point clouds, it is difficult to search similar regions and fill holes according to the source regions. Hence, we resort to Graph Signal Processing [18], and represent point clouds on graphs naturally. In particular, for each target frame in the input point cloud sequence with holes, we first segment it into cubes of the same size and choose the target cube with missing area. Secondly, we search the most similar cube to the target cube in the target frame as the intra-source cube as in [17]. Thirdly, we search the corresponding cubes of the target cube in the previous and subsequent frames as the inter-source cubes. The correspondence is set based on searching for a cube that contains the most nearest neighbors of the points in the target cube in the relative location. Next, we formulate the hole-filling step as an optimization problem, which is based on both intra-and inter-source cubes and regularized by a graph-signal smooth-ness prior [22][23][24] for the target cube. Finally, we acquire the closed-form solution of the optimization problem, leading to the inpainted result. Experimental results show that we outperform separate inpainting from state-of-the-art methods.

SPECTRAL GRAPH THEORY
We consider an undirected graph G = {V, E, W} composed of a vertex set V of cardinality |V| = N , an edge set E connecting vertices, and a weighted adjacency matrix W. W is a real symmetric N × N matrix, where w i,j is the weight assigned to the edge (i, j) connecting vertices i and j. For example, K-Nearest Neighbor (K-NN) graph is a commonly used undirected graph, which is constructed by connecting each point with its nearest K neighbors.
The Laplacian matrix is defined from the adjacency matrix [28]. Among different variants of Laplacian matrices, the combinatorial graph Laplacian used in [30][31][32] is defined as Graph signal refers to data residing on the vertices of a graph. For example, if we construct a K-NN graph on the point cloud, then the normal or the coordinate of each point can be treated as graph signal defined on the K-NN graph. This will be discussed further in the proposed spatio-temporal graph construction in Section 3.3. A graph signal z defined on a graph G is smooth with respect to the topology of G if where is a small positive scalar, and i ∼ j denotes two vertices i and j are one-hop neighbors in the graph. In order to satisfy (1), z i and z j have to be similar for a large edge weight w i,j , and could be quite different for a small w i,j . Hence, (1) enforces z to adapt to the topology of G, which is thus coined graph-signal smoothness prior.   (1) is concisely written as z T Lz < in the sequel. This prior will be deployed in our problem formulation of point cloud inpainting as a regularization term, as discussed in Section 3.4.

THE PROPOSED INPAINTING METHOD
Leveraging on spectral graph theory, we introduce the proposed point cloud inpainting method from both intra-frame self-similarity and inter-frame consistency. The input is a point cloud sequence of q frames denoted by S = {P 1 , P 2 , ..., P q }, where P f , f = 1, ..., q denotes each frame of point cloud in the sequence. As shown in Fig. 2, we inpaint each target frame P f with holes in order. Firstly, we split P f into fixed-sized cubes as processing units in the subsequent steps and choose the target cube with missing area. Secondly, we search for the most similar cube to the target cube in P f as the intra-source cube. Thirdly, we search for the corresponding cubes to the target cube in P f −1 and P f +1 , which are referred to as the inter-source cubes. Fourthly, we formulate dynamic point cloud inpainting as an optimization problem, which poses the graph-signal smoothness prior via the intra-source cube and enforces consistency with the intersource cubes. We derive the closed-form solution of the optimization problem, leading to the resulting cube. Finally, we replace the target cube with the resulting cube as the output.

Preprocessing
For each target frame of point cloud P f = {p 1 , p 2 , ...} with p i ∈ R 3 meaning the coordinates of the i-th point in the point cloud, we first split P f into overlapping cubes {c 1 , c 2 , ... } with c i ∈ R M 3 ×3 (M is the size of the cube), as the processing unit of the proposed inpainting algorithm. Then we choose the cube with missing data as the target cube c t . Next, we obtained the intra-source cube c s as in [17] based on the direct component (DC) and the anistropic graph total variation (AGTV) of the normals of points in the cube. Further, we also perform structure matching (i.e., coarse registration) for c s and c t so as to match the relative locations as in [17], which includes both translation and rotation as a simplified Iterative Closest Points (ICP) operation [40,41]. This leads to the final intra-source cube, denoted asĉ s , which will be adopted in the final inpainting step. Considering that the inpainted results of dynamic point clouds should be coherent among consecutive frames, it is necessary to explore the temporal correspondence between neighboring frames in a point cloud sequence. Unlike videos, dynamic point clouds are irregular, thus the temporal correspondence is challenging to define.

Inter-frame Cube Matching
In order to efficiently explore the temporal correspondence in dynamic point clouds for coherent inpainting, we propose to find corresponding cubes for c t both in P f −1 and P f +1 , which are denoted by c f −1 t and c f +1 t respectively as the inter-source cubes. Note that, the inter-frame consistency can be generalized to several previous and subsequent frames, instead of one forward and one backward as in our method.
Specifically, inspired by the observation that a set of points representing the same region have little variation in consecutive frames, we find the temporal correspondence via searching the nearest neighbor of each point in the target cube. As shown in Fig. 3, we first find a co-located cube where V (c w ) is the number of the nearest neighbors of c t in c w in terms of the relative location. That is, c f −1 t contains the most nearest neighbors of points in c t .
We further perform the same structure matching on c f −1 t as the way we deal with c s in Section 3.1, which leads to the final inter-source cube in P f −1 , denoted asĉ f −1 t . The final inter-source cube in P f +1 , denoted byĉ f +1 t , is searched in the same way as in P f −1 . Thus we obtain two source cubes as the temporal reference, which will be adopted in the final inpainting step.

Spatio-Temporal Graph Construction
To take advantage of both intra-frame self-similarity and inter-frame consistency, we construct a spatial-temporal graph on the target cube c t as the following.
We first build spatial connectivities within c t . As there exists a hole in c t , we approximate the connectivities via the similarities in its intra-source cubeĉ s . We choose to build a K-NN graph mentioned in Section 2, based on the affinity of geometric distance among points inĉ s . Specifically, the edge weight w k,l between nodes k and l inĉ s is assigned as where k ∼ l means nodes k and l are K nearest neighbors and thus connected. σ is a weighting parameter (empirically σ = 1 in our experiments). This is based on the assumption that geometrically closer points are more similar in general. We then construct temporal connectivities between c t and its previous frameĉ f −1 t , as well as temporal connectivities between c t and its subsequent frameĉ f +1 t . Due to the hole in c t , the connectivities for known points and unknown points in c t are linked in different manners. Specifically, we link each known point in c t with its corresponding point inĉ f −1 t .
To circumvent the unavailability of unknown points in c t , we approximate the temporal connectivities by the similarities between their corresponding points in the intra-source cubê c s and their corresponding points in the inter-source cubê c f −1 t . The temporal correspondence is based on the the nearest neighbor in the relative location in the cube.
Further, we define a weight matrix W f −1 ∈ M 3 × M 3 to encode the temporal connectivities between c t andĉ f −1 t . The rows of W f −1 correspond to points in c t and columns correspond to points inĉ f −1 t . Specifically, the weight in W f −1 between nodes k and l is assigned as where k ∼ l means nodes k and l are temporally corresponding points and thus connected. We set weight 1 to each pair of temporally connected points as the temporal correlation is strong for corresponding points. It is the same for the construction of temporal connectivities between c t andĉ f +1 t . Similarly, we define a weight matrix W f +1 to describe the temporal connections.

Problem Formulation
Finally, we cast dynamic point cloud inpainting as an optimization problem, which is regularized by the graph-signal smoothness prior as mentioned in Section 2 and temporal consistency. It is formulated as min cr Ωc r − Ωc t 2 2 + α Ωc r − Ωĉ s where c r ∈ R M 3 ×3 is the desired resulting cube. Ω is a M 3 × M 3 diagonal matrix with Ω i,i ∈ {0, 1}, where 0 indicates known points and 1 indicates missing points. Thus Ωc r and Ωĉ s represent the missing region in c r andĉ s respectively. Ω is complementary to Ω, which extracts the known region. L is the Laplacian matrix of the spatial graph constructed over c t as described in Section 3.3. α, β and γ are three weighting parameters (we empirically set α = 1, β = 0.5 and γ = 0.5 in the experiments). The first term in (5) is a data fidelity term, which ensures the desired cube to be close to c t in the known region. The second term constraints the missing region of c r to be similar to that ofĉ s . The last two terms aim to make the structure of c r mimic that ofĉ f −1 t andĉ f +1 t , which enforces the temporal consistency. Further, the third term is the graph-signal smoothness prior, which enforces the internal structure of c r to be smooth with respect to the constructed spatial graph when merging information from three source cubes.
(5) is a quadratic programming problem. Taking derivative of (5) with respect to c r and setting the derivative to 0, we have the closed-form solution: (5) is thus solved optimally and efficiently. We replace the target cube with the resulting cube in the target frame P f , which serves as the output.

EXPERIMENTS 4.1. Experimental Setup
We evaluate the proposed method by testing on several 3D dynamic point cloud datasets from MPEG [45] and JPEG Pleno [46], including Longdress, Loot, Redandblack, Soldier, and UlliWegner. We test on two types of holes: 1) real holes generated during the capturing process, which have no ground   Further, we compare our method with three competing algorithms for static 3D geometry inpainting, including Meshlab [47], Lozes et al. [13] and Hu et al. [17]. We test the static methods by performing them on each frame separately. Besides, as Meshlab is based on meshes, we convert point clouds to meshes via the Meshlab software [47] prior to testing the method, and then convert the inpainted meshes back to point clouds as the final output.

Results on Point Cloud Inpainting
Objective results. It is nontrivial to measure the geometry difference of point clouds objectively. We apply the geometric distortion metrics in [48] and [8], referred to as GPSNR and NSHD, respectively, as the metric for evaluation. The higher GPSNR is and the lower NSHD is, the smaller the difference between two point clouds is. Table 1 and Table 2 show the average objective results of the frames for each sequence with synthetic holes in GP-SNR and NSHD, respectively. We see that our scheme outperforms all the competing methods in GPSNR and NSHD significantly. Specifically, in Table 1 we achieve 26.80 dB gain in GPSNR on average over Meshlab, 16.18 dB over [13] and 5.26 dB over [17]. In Table 2, we produce much lower NSHD than the other methods, at least three times lower compared to the next best method [17].
Subjective results. Further, Fig. 4 and Fig. 5 demonstrate the subjective inpainting results for real and synthetic holes, respectively. Due to the page limit, we show several repre- sentative frames compared with one competitive method [13]. For the real holes in Fig. 4 (a), which are fragmentary, the results of [13] exhibit artificial contours, since it attempts to connect the boundary of the hole region with planar structures without smoothing. However, the inpainted results are not smooth in the local region, which indicates the temporal inconsistency to some extent. In comparison, our results shown in row 3 of Fig. 4 demonstrate that our method is able to inpaint holes with appropriate geometry structure and smoothness over the hole region. Besides, since we leverage the inter-frame correlation, our inpainted regions show good consistency across neighboring frames. In Fig. 5, we synthesize holes in the point cloud sequence Soldier, with more complex and bigger holes than the real holes in Fig. 4. We observe that [13] covers the missing area with stripy geometry, which introduces wrong geometry around the holes compared to the ground truth. Also, the contents look incoherent among the consecutive frames. In comparison, our results shown in row 3 of Fig. 5 are almost the same as the ground truth, and exhibit consistency between neighboring frames. This gives credits to the intraframe self-similarity, the inter-frame consistency and graphsignal smoothness prior.

CONCLUSION
We propose a novel 3D dynamic point cloud inpainting method. The key idea is to enforce both intra-frame selfsimilarity and inter-frame consistency in point cloud sequences. Given a target cube with holes inside, we propose to efficiently search for its intra-frame self-similar cube and inter-frame corresponding cubes. We then cast dynamic point cloud inpainting as a quadratic programming problem, based on the searched source cubes and regularized by the graphsignal smoothness prior. Experimental results show that our algorithm significantly outperforms three competing methods. Future works include the extension to inpainting the attributes of dynamic point clouds.