A basic premise in graph signal processing (GSP) is that a graph encoding pairwise (anti-)correlations of the targeted signal as edge weights is leveraged for graph filtering. Existing fast graph sampling schemes are designed and tested only for positive graphs describing positive correlations. However, there are many real-world datasets exhibiting strong anti-correlations, and thus a suitable model is a signed graph, containing both positive and negative edge weights. In this paper, we propose the first linear-time method for sampling signed graphs, centered on the concept of balanced signed graphs. Specifically, given an empirical covariance data matrix , we first learn a sparse inverse matrix , interpreted as a graph Laplacian corresponding to a signed graph . We approximate with a balanced signed graph via fast edge weight augmentation in linear time, where the eigenpairs of Laplacian for are graph frequencies. Next, we select a node subset for sampling to minimize the error of the signal interpolated from samples in two steps. We first align all Gershgorin disc left-ends of Laplacian at the smallest eigenvalue via similarity transform , leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA). We then perform sampling on using a previous fast Gershgorin disc alignment sampling (GDAS) scheme. Experiments show that our signed graph sampling method outperformed fast sampling schemes designed for positive graphs on various datasets with anti-correlations.

Viral information like rumors or fake news is spread over a communication network like a virus infection in a unidirectional manner: entity$i$conveys information to a neighbor$j$, resulting in two equally informed (infected) parties. Existing graph diffusion processes focus only on bidirectional diffusion on an undirected graph. Instead, leveraging recent research in graph signal processing (GSP), we propose a new directed acyclic graph (DAG) diffusion process to estimate the probability$x_{i}(t)$of node$i$'s infection at time$t$given an initial infected source node$s$, where$x_{i}(\infty)=1$. Specifically, given an undirected positive graph modeling node-to-node communication, we first estimate its graph embedding: a latent coordinate for each graph node in an assumed low-dimensional manifold space via extreme eigenvectors computed using LOBPCG. Next, we construct a DAG based on Euclidean distances between latent coordinates. Spectrally, we prove that the asymmetric DAG Laplacian matrix contains real non-negative eigenvalues, and that the DAG diffusion converges to the all-infection vector$\mathbf{x}(\infty)=1$as$t\rightarrow\infty$. Simulations show that our DAG diffusion process accurately estimates the probabilities of node infection over a variety of graph structures at different time instants.

Point cloud (PC)—a collection of discrete geometric samples of a 3D object’s surface—is typically large, which entails expensive subsequent operations. Thus, PC sub-sampling is of practical importance. Previous model-based sub-sampling schemes are ad-hoc in design and do not preserve the overall shape sufficiently well, while previous data-driven schemes are trained for specific pre-determined input PC sizes and sub-sampling rates and thus do not generalize well. Leveraging advances in graph sampling, we propose a fast PC sub-sampling algorithm of linear time complexity that chooses a 3D point subset while minimizing a global reconstruction error. Specifically, to articulate a sampling objective, we first assume a super-resolution (SR) method based on feature graph Laplacian regularization (FGLR) that reconstructs the original high-res PC, given points chosen by a sampling matrix${\mathbf H}$. We prove that minimizing a worst-case SR reconstruction error is equivalent to maximizing the smallest eigenvalue$\lambda _{\min }$of matrix${\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}}$, where${\boldsymbol{\mathcal{L}}}$is a symmetric, positive semi-definite matrix derived from a neighborhood graph connecting the 3D points. To arrive at a fast algorithm, instead of maximizing$\lambda _{\min }$, we maximize a lower bound$\lambda ^-_{\min }({\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}})$via selection of${\mathbf H}$—this translates to a graph sampling problem for a signed graph${\mathcal G}$with self-loops specified by graph Laplacian${\boldsymbol{\mathcal{L}}}$. We tackle this general graph sampling problem in three steps. First, we approximate${\mathcal G}$with a balanced graph${\mathcal G}_B$specified by Laplacian${\boldsymbol{\mathcal{L}}}_B$. Second, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we perform a similarity transform${\boldsymbol{\mathcal{L}}}_p~=~{\mathbf S}{\boldsymbol{\mathcal{L}}}_B {\mathbf S}^{-1}$, so that all Gershgorin disc left-ends of${\boldsymbol{\mathcal{L}}}_p$are aligned exactly at$\lambda _{\min }({\boldsymbol{\mathcal{L}}}_B)$. Finally, we choose samples on${\mathcal G}_B$using a previous graph sampling algorithm to maximize$\lambda ^-_{\min }({\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}}_p)$in linear time. Experimental results show that 3D points chosen by our algorithm outperformed competing schemes both numerically and visually in reconstruction quality.

In graph signal processing (GSP), an appropriate underlying graph encodes pairwise (anti-)correlations of targeted discrete signals as edge weights. However, existing fast graph sampling schemes are designed and tested for positive graphs describing only positive correlations. In this paper, we show that for datasets with inherent strong anti-correlations, a suitable graph structure is instead a signed graph with both positive and negative edge weights, and in response, we propose a linear-time signed graph sampling method. Specifically, given an empirical covariance data matrix ${\mathbf{\bar C}}$, we first employ graphical lasso to learn a sparse inverse matrix $\mathcal{L}$, interpreted as a generalized graph Laplacian for signed graph $\mathcal{G}$. We then propose a fast signed graph sampling scheme containing three steps: i) augment $\mathcal{G}$ to a balanced graph ${\mathcal{G}_B}$, ii) align all Gershgorin disc left-ends of corresponding Laplacian ${\mathcal{L}_B}$ at smallest eigenvalue ${\lambda _{\min }}\left( {{\mathcal{L}_B}} \right)$ via similarity transform ${\mathcal{L}_p} = {\mathbf{S}}{\mathcal{L}_B}{{\mathbf{S}}^{ - 1}}$, leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA), and iii) perform sampling on ${\mathcal{L}_p}$ using a previous fast Gershgorin disc alignment sampling scheme (GDAS). Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on two political voting datasets.

Point cloud (PC) is a collection of discrete geometric samples of a physical object in 3D space. A PC video consists of temporal frames evenly spaced in time, each containing a static PC at one time instant. PCs in adjacent frames typically do not have point-to-point (P2P) correspondence, and thus exploiting temporal redundancy for PC restoration across frames is difficult. In this paper, we focus on the super-resolution (SR) problem for PC video: increase point density of PCs in video frames while preserving salient geometric features consistently across time. We accomplish this with two ideas. First, we establish partial P2P coupling between PCs of adjacent frames by interpolating interior points in a low-resolution PC patch in frame t and translating them to a corresponding patch in frame t+1 , via a motion model computed by iterative closest point (ICP). Second, we promote piecewise smoothness in 3D geometry in each patch using feature graph Laplacian regularizer (FGLR) in an easily computable quadratic form. The two ideas translate to an unconstrained quadratic programming (QP) problem with a system of linear equations as solution-one where we ensure the numerical stability by upper-bounding the condition number of the coefficient matrix. Finally, to improve the accuracy of the ICP motion model, we re-sample points in a super-resolved patch at time t to better match a low-resolution patch at time t+1 via bipartite graph matching after each SR iteration. Experimental results show temporally consistent super-resolved PC videos generated by our scheme, outperforming SR competitors that optimized on a per-frame basis, in two established PC metrics.

3D point clouds acquired by low-cost sensors are often in lower spatial resolutions than desired for rendering images on high-resolution displays. In this paper, we propose a fast super-resolution (SR) algorithm for color 3D point clouds. We first populate a target low-res point cloud with added interior points. We refine the newly added 3D coordinates and their RGB values by minimizing a graph total variation (GTV) term of connected points' surface normals and RGB values respectively. Unlike non-local methods that require computation-intensive searches of similar patches in a large defined space, our algorithm is inherently local and performs smoothing of newly inserted points only with respect to neighboring points. Moreover, differing from our previous GTV-based SR algorithm that employs gradient descent procedures with sensitive step size parameters due to GTV's non-smooth l1-norm, we rewrite the l1objective into a linear proxy, so that together with constraints on surface normals / RGB values, it can be solved efficiently as a parameter-free linear program (LP). Experimental results show that our algorithm outperforms competing non-graph-based point cloud SR schemes, and is significantly faster than our previous graph-based SR method.

Point cloud-a collection of geometric samples of a physical object in 3D space-can be very large in size, which entails a large computation cost for many imaging applications. In this paper, we reduce the size of a point cloud towards a more compact representation via optimal sub-sampling. Specifically, we first derive a sampling objective that maximizes the stability (maximizes the smallest eigenvalue λmin(B) of a coefficient matrix B = HTH + μL) of a linear system super-resolving a sub-sampled point cloud. To circumvent eigen-decomposition, we maximize instead a lower bound λmin-(B) using a fast graph sampling scheme called Gershgorin disc alignment (GDA) based on the well-known Gershgorin circle theorem. However, GDA requires that the disc left-ends of real matrix L are initially aligned at the same value, which is not the case for point clouds. Orthogonally, we recently derived a matrix theorem proving that disc left-ends of a generalized graph Laplacian matrix for a balanced and irreducible signed graph can be perfectly aligned via a similarity transform using the matrix's first eigenvector. Leveraging this work, we first interpret L as a generalized graph Laplacian matrix and balance the underlying graph. We then align disc left-ends of the resulting generalized graph Laplacian of the balanced graph using its first eigenvector, in order to employ GDA for point cloud sampling. Experiments show that our sampling method outperforms competing methods in super-resolved point cloud quality.

Point cloud is a collection of 3D coordinates that are discrete geometric samples of an object's 2D surfaces. Imperfection in the acquisition process means that point clouds are often corrupted with noise. Building on recent advances in graph signal processing, we design local algorithms for 3D point cloud denoising. Specifically, we design a signal-dependent feature graph Laplacian regularizer (SDFGLR) that assumes surface normals computed from point coordinates are piecewise smooth with respect to a signal-dependent graph Laplacian matrix. Using SDFGLR as a signal prior, we formulate an optimization problem with a general 'p-norm fidelity term that can explicitly remove only two types of additive noise: small but non-sparse noise like Gaussian (using '2 fidelity term) and large but sparser noise like Laplacian (using '1 fidelity term). To establish a linear relationship between normals and 3D point coordinates, we first perform bipartite graph approximation to divide the point cloud into two disjoint node sets (red and blue). We then optimize the red and blue nodes' coordinates alternately. For '2-norm fidelity term, we iteratively solve an unconstrained quadratic programming (QP) problem, efficiently computed using conjugate gradient with a bounded condition number to ensure numerical stability. For '1-norm fidelity term, we iteratively minimize an '1-'2 cost function using accelerated proximal gradient (APG), where a good step size is chosen via Lipschitz continuity analysis. Finally, we propose simple mean and median filters for flat patches of a given point cloud to estimate the noise variance given the noise type, which in turn is used to compute a weight parameter trading off the fidelity term and signal prior in the problem formulation. Extensive experiments show state-of-the-art denoising performance among local methods using our proposed algorithms.

Point cloud is a collection of 3D coordinates that are discrete geometric samples of an object's 2D surfaces. Using a low-cost 3D scanner to acquire data means that point clouds are often in lower resolution than desired for rendering on high-resolution displays. Building on recent advances in graph signal processing, we design a local algorithm for 3D point cloud super-resolution (SR). First, we initialize new points at centroids of local triangles formed using the low-resolution point cloud, and connect all points using a k-nearest-neighbor graph. Then, to establish a linear relationship between surface normals and 3D point coordinates, we perform bipartite graph approximation to divide all nodes into two disjoint sets, which are optimized alternately until convergence. For each node set, to promote piecewise smooth (PWS) 2D surfaces, we design a graph total variation (GTV) objective for nearby surface normals, under the constraint that coordinates of the original points are preserved. We pursue an augmented Lagrangian approach to tackle the optimization, and solve the unconstrained equivalent using the alternating method of multipliers (ADMM). Extensive experiments show that our proposed point cloud SR algorithm outperforms competing schemes objectively and subjectively for a large variety of point clouds.

Point cloud is a collection of 3D coordinates and associated color information, which are discrete samples of an object's 2D surfaces. Imperfection in the acquisition process means that point clouds are often corrupted with noise in both geometric and color spaces. Building on recent advances in graph signal processing, we design two algorithms for 3D point cloud color denoising. Specifically, we develop a smoothness notion for 3D color point clouds using graph Laplacian regularizer (GLR) or graph total variation (GTV) priors defined on the RGB space to promote piecewise smoothness (PWS) of RGB values. Using GLR or GTV as signal prior, we formulate the point cloud color denoising problem as a maximum a posteriori (MAP) estimation problem. For the GLR prior, the MAP formulation leads to an unconstrained quadratic programming (QP) problem, which can be efficiently computed using conjugate gradient (CG). For the GTV prior, the MAP formulation results in an ℓ1-ℓ2cost function; we minimize it using alternating direction method of multipliers (ADMM) and proximal gradient descent, where a good step size is chosen via Lipschitz continuity analysis. Extensive experiments show satisfactory denoising performance using our proposed algorithms.

Acquired 3D point cloud data, whether from active sensors directly or from stereo-matching algorithms indirectly, typically contain non-negligible noise. To address the point cloud denoising problem, we propose a local graph-based algorithm. Specifically, given a $k$ -nearest-neighbor graph of the 3D points, we first approximate it with a bipartite graph (independent sets of red and blue nodes) using a KL divergence criterion. For each partite of nodes (say red), we first define surface normal of each red node using 3D coordinates of neighboring blue nodes, so that red node normals n can be written as a linear function of red node coordinates p. We then formulate a convex optimization problem, with a quadratic fidelity term $\Vert \mathbf{p}-\mathbf{q}\Vert_{2}^{2}$ given noisy observed red coordinates q and a graph total variation (GTV) regularization term for surface normals of neighboring red nodes. We minimize the resulting $l_{2}-l_{1}$-norm using alternating direction method of multipliers (ADMM) and proximal gradient descent. The two partites of nodes are alternately optimized until convergence. Experimental results show that compared to state-of-the-art schemes with similar complexity, our proposed algorithm achieves the best overall denoising performance objectively and subjectively.

In this letter, we introduce several algorithms for geometry inpainting of three-dimensional (3-D) point clouds with large holes. The algorithms are exemplar based. Hole filling is performed iteratively using templates near the hole boundary to find the best matching regions elsewhere in the cloud, from where existing points are transferred to the hole. We propose two improvements over the previous work on exemplar-based hole filling. The first one is adaptive template size selection in each iteration, which simultaneously leads to higher accuracy and lower execution time. The second improvement is a nonrigid transformation to better align the candidate set of points with the template before the point transfer, which leads to even higher accuracy. We demonstrate the algorithm's ability to fill holes that are difficult or impossible to fill by existing methods.

Holes can arise in 3D point clouds due to a number of reasons such as incomplete scans, occlusions, and packet loss. We present an exemplar-based framework for hole filling in 3D point clouds, which exploits non-local self similarity to provide plausible reconstruction even for large holes and complex surfaces. Points along the hole boundary are given priority that determines the order in which they are processed. Hole filling is performed iteratively and uses templates near the hole boundary to find the best matching regions elsewhere in the cloud, from where existing points are transferred to the hole. The proposed method has been compared with several existing methods and has shown superior results, both visually and in terms of the Hausdorff distance.