PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Spectral Image Processing

Gene Cheung, Enrico Magli, Yuichi Tanaka, Michael Ng

arXiv:1801.04749v2eess.IVeess.SP

TL;DR

Graph spectral image processing addresses how to represent regularly sampled images with graphs that capture their structure. The paper surveys graph-spectral methods for compression, restoration, filtering, and segmentation, highlighting graph design and signaling overhead as practical considerations.

  • Problem

    Image pixels lie on a regular grid, but graph-based processing requires selecting an underlying graph whose edges and weights describe image structure appropriately.

  • Method

    The paper overviews graph-spectral techniques that construct or use image graphs for compression, restoration, filtering, and segmentation.

  • Results

    The survey covers graph-based methods across image compression, restoration, filtering, and segmentation, including adaptive transforms, priors, diffusion, and normalized cuts.

  • Takeaways & Limitations

    Graph construction is central: it conveys local similarity for restoration, filtering, and segmentation, while its description creates coding overhead for compression.

Abstract

from arXiv · show

Recent advent of graph signal processing (GSP) has spurred intensive studies of signals that live naturally on irregular data kernels described by graphs (e.g., social networks, wireless sensor networks). Though a digital image contains pixels that reside on a regularly sampled 2D grid, if one can design an appropriate underlying graph connecting pixels with weights that reflect the image structure, then one can interpret the image (or image patch) as a signal on a graph, and apply GSP tools for processing and analysis of the signal in graph spectral domain. In this article, we overview recent graph spectral techniques in GSP specifically for image / video processing. The topics covered include image compression, image restoration, image filtering and image segmentation.

I. INTRODUCTION

Graph signal processing represents image pixels as signals on graphs whose weighted edges encode local similarity and structure. The overview surveys graph-spectral tools for image compression, restoration, filtering, and segmentation, while emphasizing graph selection and representation challenges.

  • Graph-based image representation: GSP models image pixels as graph nodes connected by weighted edges that encode expected similarity or correlation.A large edge weight indicates that neighboring signal samples are expected to be similar.
  • Graph spectral representation: Eigen-decomposition of the graph Laplacian defines graph frequencies and transforms that generalize frequency analysis such as the DCT.The GFT decomposes a graph signal into components using the Laplacian eigenvectors.
  • Graph design: Graph construction can use pixel neighborhoods, Gaussian-kernel weights, local patches, features, or learned structures, depending on the application.Graph learning can identify structures that fit observed data under specified models or criteria.
  • Image restoration: Graph-spectral image restoration extends sparsity, smoothness, and stationarity-based priors to denoising and deblurring.These priors regularize otherwise ill-posed restoration problems.
  • Filtering and applications: Graph spectral filtering includes graph interpretations of bilateral filtering, diffusion, edge-preserving smoothing, retargeting, rendering, and fast polynomial implementations.The overview specifically discusses Chebyshev polynomial approximation for fast graph-filter computation.
  • Image segmentation: The survey also covers graph-based segmentation, including normalized cuts, Mumford-Shah models, and graph biLaplacians.Normalized cuts address the tendency of minimum cuts to favor regions with few vertices.

C. Variation Operators

Graph variation operators quantify image-signal behavior on weighted graphs, while graph-spectral methods use these structures for priors, compression, and adaptive transforms. Their benefits depend on graph design and can be limited by transform-description overhead and computational cost.

  • Variation Operators: Graph smoothness is measured by the Laplacian regularizer xT Lx, which penalizes differences between signals on connected nodes.The regularizer is also expressed spectrally as a weighted sum of squared graph-Fourier coefficients.
  • Variation Operators: For positive edge weights, the smoothest signal is constant, achieving the lower bound xT Lx = 0.This corresponds to the first Laplacian eigenvector with eigenvalue λ1 = 0.
  • Variation Operators: Graph priors for restoration include smoothness, total variation, GFT sparsity, and sparsity in graph dictionaries.Graph-dictionary atoms can be constructed as polynomials of the graph Laplacian.
  • Adaptive transforms for compression: Transform coding applies a transform, quantization, and entropy coding, with adaptive graph information transmitted as ancillary side information.The total rate combines coded transform coefficients and graph-related ancillary information.
  • Adaptive transforms for compression: KLT is optimal for Gaussian sources under mean square error and fixed-rate coding, but image nonstationarity motivates more flexible graph-based transform design.Unlike fixed transforms, KLT adaptivity requires communicating an unstructured transform matrix to the decoder.
  • Adaptive transforms for compression: Graph description overhead must be optimized jointly with transform effectiveness in a rate-distortion design.The graph should be informative enough to produce effective transforms without requiring excessive ancillary coding.

B. Graph Fourier Transform and graph design

Graph design determines the GFT used for image compression: topology and weights should reflect pixel relationships while balancing rate-distortion performance, signaling overhead, and computational cost. The reviewed methods include binary or quantized weights, graph learning, complexity reductions, and steerable transforms.

  • B. Graph Fourier Transform and graph design: A square-grid graph typically connects each pixel to its four horizontal and vertical neighbors, with edge weights based on the photometric distance between connected pixels.The graph topology and weights determine the graph Laplacian and its GFT.
  • 1) Choosing edge weights: Binary or quantized edge weights reduce graph-description overhead, but weight binarization can be suboptimal for compression efficiency.Two-level weights can preserve a connected graph, while suitably designed quantization can make the performance loss very small.
  • 2) Graph learning: Graph learning methods estimate graph structures from data, while rate-distortion graph learning explicitly accounts for the cost of transmitting graph weights by coding them on a dual graph.The latter poses graph selection as a rate-distortion optimization problem.
  • 3) Reducing GFT complexity: GFT complexity can outweigh coding gains, motivating lookup tables, low-resolution graph transforms with edge-adaptive filtering, separable transforms, and symmetry-based implementations.Lookup tables transmit only the index of a commonly used transform and work well for relatively small block sizes.
  • 4) Compression performance: MR-GFT outperforms the other transforms on Teddy depth-image compression, obtaining gains of 5 to 10 dB over the corresponding DCT-based coder.At the same bit-rate, MR-GFT reconstruction has less evident artifacts.
  • C. Steerable transforms from GFT: Steerable 2D-DCTs rotate eigenvector pairs associated with repeated eigenvalues, with angles selected to match image directionality while limiting signaling overhead.Individual angle selection can almost halve the number of DCT coefficients transmitted.

D. Applications

Graph-based image restoration treats recovery from noisy or degraded observations as an ill-posed inverse problem requiring signal priors. The reviewed approaches use graph transforms, adaptive edge weights, sparsity, filtering, and iterative optimization for denoising and related restoration tasks.

  • IV. GRAPH-BASED IMAGE RESTORATION: Image restoration recovers an original signal from noisy or degraded observations, including denoising, interpolation, super-resolution, and deblurring.A generic formation model uses y = Hx + z, where H models degradation and z is additive noise.
  • IV. GRAPH-BASED IMAGE RESTORATION: Because restoration is ill-posed, graph-signal priors regularize the problem by distinguishing the target signal from alternative candidates.The regularization term R(x) is weighted by a parameter µ in the MAP formulation.
  • 1) Sparsity of GFT Coefficients: Graph transforms and wavelets replace predetermined bases for coefficient thresholding, extending sparse-representation denoising to graph-signal domains.The graph Laplacian can be roughly interpreted as an inverse covariance matrix of a Gaussian model.
  • 1) Sparsity of GFT Coefficients: NLGBT denoises similar depth-image patches jointly using a four-connected graph whose photometric edge weights are computed adaptively.Similar patches are first searched to form an average patch, and the graph is computed from local pixel relationships.
  • 1) Sparsity of GFT Coefficients: Computed graph weights can be sensitive to observation noise, so pre-filtering, dual-graph smoothing, or patch averaging is used to improve robustness.For NLGBT, averaging over similar patches effectively provides low-pass pre-filtering.
  • 1) Sparsity of GFT Coefficients: For piecewise smooth images, the iterative graph-based denoising method can outperform state-of-the-art algorithms such as BM3D.Edge weights are updated between iterations using the computed solution.

2) Graph Laplacian regularizer:

The graph Laplacian regularizer promotes smooth graph signals by encouraging strongly connected pixels to have similar values, yielding low-pass behavior and useful restoration properties. Its continuous-manifold interpretation connects iterative regularization to anisotropic diffusion that preserves piecewise-smooth structure.

  • Graph Laplacian regularizer: The regularizer R(x) = xT Lx penalizes differences between strongly connected pixels, concentrating signal energy in low graph frequencies.Large edge weights indicate expected similarity between connected samples.
  • Graph Laplacian regularizer: Using R(x) = xT Lx produces a low-pass GFT filter whose coefficients decrease as graph eigenvalues increase.The filter coefficient is (1+µλi)^−1 and can be approximated efficiently with Chebyshev polynomials.
  • Continuous interpretation: The graph Laplacian regularizer converges to a continuous-manifold functional as sample density increases and neighbor distances shrink.Signal-adaptive edge weights motivate writing the prior as xT L(x)x.
  • Continuous interpretation: For γ < 1, anisotropic diffusion smooths along image edges and sharpens perpendicular to them; γ = 1 yields behavior analogous to total variation.This diffusion interpretation explains strong denoising performance on piecewise-smooth images such as depth images.
  • Graph-based restoration: The low-dimensional manifold restoration formulation can be replaced by a weighted graph Laplacian method because the original point-integral solution is computationally complex.The resulting Euler–Lagrange equation is a symmetric positive-definite linear system that is easier to solve.

3) Graph Total Variation:

Graph total variation provides a nonsmooth alternative to Laplacian smoothness for restoration, with specialized optimization methods handling its convex fidelity-regularization formulation. Primal-dual approaches can also support distributed processing on large graphs.

  • Graph Total Variation: Graph total variation is defined from local graph gradients and provides a traditional total-variation prior for graph signals.The reviewed works distinguish this formulation from an earlier graph total variation definition.
  • Optimization: Because the TV norm is convex but nonsmooth, proximal-gradient algorithms can minimize it together with a fidelity term.The optimization is designed for restoration problems involving noisy observations.
  • Optimization: Dual constrained total variation generalizes graph TV and includes it as a special case, with a parallel proximal algorithm proposed for optimization.This extends the available optimization framework beyond the basic TV formulation.
  • Optimization: A primal-dual method solves the saddle-point formulation after converting the L1 norm to its convex-conjugate L∞ norm ball.A distributed version is provided for large graphs.

4) Wiener Filter:

The reviewed restoration approaches extend beyond MAP sparsity and smoothness priors to statistical graph Wiener filtering and graph-based deblurring. In JPEG soft decoding, complementary graph and sparse priors recover piecewise-smooth structure and improve reconstruction quality over competing schemes.

  • Wiener Filter: Graph Wiener filtering designs a statistical denoiser by generalizing wide-sense stationarity, estimating graph power spectral density, and minimizing mean square error.Fast Chebyshev or Lanczos implementations can execute the filter locally in the vertex domain.
  • Wiener Filter: Graph-based deblurring can iteratively update a similarity matrix after solving a linear inverse problem with conjugate gradient.Diagonal scaling makes the intermediate matrix row- and column-stochastic, while the normalized Laplacian is symmetric positive semidefinite.
  • Wiener Filter: JPEG soft decoding combines Laplacian DCT statistics, sparse dictionary representation, and the LERaG graph-smoothness prior to reconstruct quantized coefficients.The decoder chooses coefficient values within quantization bins before inverse DCT.
  • Wiener Filter: LERaG complements sparse coding by promoting piecewise-smooth behavior and recovering lost high DCT frequencies in pixel patches.The complementarity is especially relevant when using a small over-complete dictionary.
  • Wiener Filter: LERaG outperforms a normalized graph Laplacian based on a doubly stochastic similarity matrix while requiring lower computation cost.The prior also preserves constant signals in natural images.
  • Wiener Filter: Iterative edge-weight updates make filtered patches increasingly piecewise smooth, while the normalized Laplacian’s second eigenvalue decreases with iterations.The reported soft-decoded Butterfly image has higher quality than competing schemes.

D. Other Graph-based Image Restorations

Graph-based restoration methods extend image priors such as smoothness and sparsity to graph signals, supporting denoising, deblurring, demosaicking, and related inverse-imaging tasks. Graph spectral smoothing includes heat-kernel diffusion and polynomial or Krylov approximations, with approximation accuracy depending on the graph spectrum.

  • Applications include Bayer-pattern demosaicking and graph-based bilateral filtering for suppressing noise in a lower-quality stereo view.
  • Heat-kernel filtering assigns larger edge weights to pixels with similar values and models diffusion through the graph heat equation.The diffusion parameter t controls the spreading speed.
  • Taylor expansion and finite-order polynomial truncation provide graph-filter approximations, with Krylov subspace methods used for implementation.
  • Approximation accuracy significantly worsens for large λ, motivating alternative methods whose suitability depends on the graph's maximum eigenvalue.

B. Edge-Preserving Smoothing

Graph spectral filtering separates image-dependent structure from the desired filtering response by encoding relationships such as geometry, photometry, edges, textures, and saliency in a graph. The bilateral filter admits a graph low-pass interpretation, while related graph filters support smoothing, sharpening, and non-local processing.

  • Graph construction can use geometric distance, photometric distance, their combination, and image saliency to represent pixel- or patch-wise relationships.
  • The bilateral filter is represented using a graph adjacency matrix and normalized Laplacian, making its pixel-dependent operation a graph spectral filter.
  • The bilateral filter has spectral response ehBF(λn) = 1 −λn, which acts as a graph low-pass filter because λn ∈[0, 2].
  • Related approaches interpret non-local filters as graph spectral filters, while some variational operators allow negative-weighted edges.
  • Graph spectral filtering can encode image priors separately from the user-desired response, supporting edge-preserving smoothing and other image-filtering effects.

C. Relationship between Edge-Preserving Smoothing and Retargeting

Domain-transform processing first constructs a nonuniform pixel coordinate system from geometric and photometric relationships, filters the resulting signal, and maps it back or interpolates it. This shared pipeline connects edge-preserving smoothing with content-aware image retargeting.

  • The domain transform computes warped pixel positions from geometric and photometric distances before filtering the nonuniformly sampled signal.
  • Its processing sequence places pixel values on warped coordinates, applies a continuous-domain low-pass filter, and replaces the filtered values at original coordinates.
  • The deformed pixel positions can be formulated through linear systems related to graph Laplacians and mesh-deformation optimization.
  • Mapping the filtered nonuniform signal back to uniform positions yields edge-preserving smoothing, whereas interpolation to uniform positions produces image retargeting.
  • Graph-based methods remain fully discretized, avoiding the continuous-domain estimation and computational cost required by conventional approaches.

D. Non-Photorealistic Rendering of Images

Non-photorealistic rendering combines edge-preserving smoothing with thresholding, segmentation, and frequency-domain processing to create stylized effects such as pencil drawings and abstraction. Practical graph filtering therefore requires efficient approximations instead of direct eigendecomposition for large images.

  • Non-photorealistic rendering uses smoothing together with thresholding and segmentation to produce stylization, pencil drawing, and abstraction.
  • In the illustrated examples, stylization combines an edge image with a smoothed image, while pencil drawing combines detected edges with high-frequency information.
  • A 4K image has WH > 8 × 10^6 pixels, making construction and eigendecomposition of a WH × WH graph Laplacian computationally burdensome.
  • Polynomial graph filters approximate spectral responses through matrix-vector multiplications and correspond to localized K-hop transforms in the vertex domain.
  • Chebyshev approximation uses recurrence with low memory, low passband error, and an error bound; unlike Taylor approximation, its error is bounded across λ.
  • Graph-based segmentation constructs an energy function on pixel graphs and focuses on graph-cut methods applied to the Mumford-Shah model.

A. Graph Cut

Graph cuts model image segmentation by partitioning pixel graphs into regions while assigning costs to terminal and neighborhood edges. Minimum-cut, normalized-cut, random-walk, and variational formulations provide related optimization frameworks.

  • Graph construction: The graph contains image-pixel vertices plus source and sink terminals, with pixel, source-to-pixel, and pixel-to-sink edges.Nonnegative weights are assigned to graph edges.
  • Cost design: Graph-cut costs combine region terms for pixel assignments with boundary terms for neighboring pixels assigned to different regions.Shape information can be incorporated by revising these terms.
  • Minimum cut: A minimum cut partitions foreground and background by minimizing the cost of edges crossing between source- and sink-side sets.The max-flow problem is equivalent to min-cut, enabling globally optimal solutions through max-flow algorithms.
  • Normalized cut: Normalized cut addresses minimum-cut bias toward regions with few vertices by normalizing cut cost by total edge connections.Its optimization can be relaxed to an eigenvalue problem using the normalized Laplacian.
  • Related formulations: Other graph-cut approaches include mean cut, ratio cut, ratio regions, random walks, and graph-cut formulations of Mumford–Shah segmentation.Finding cuts in arbitrary graphs is NP-hard, while related iterative methods can converge to global optima in specified formulations.

1) Discrete Models:

Discrete Mumford–Shah segmentation constructs graph-cut energies on image grids, using neighborhood weights tied to total-variation discretization. Layered graphs extend the approach to multiple regions, and reported results show improved efficiency over PDE-based methods.

  • Discrete models: The variational Mumford–Shah problem is discretized on a grid and represented by a discrete energy function solvable through graph cuts.For fixed region values, the minimizer is obtained as a minimum cut without explicitly imposing integer constraints on the level-set variables.
  • Discrete models: Neighborhood weights are defined as wi,j = 1/(k×distance(i,j)), where k reflects the neighborhood number used for the total-variation discretization.The weights encode the spatial regularization associated with grid-point neighborhoods.
  • Discrete models: Multiple-region segmentation uses multiple graph layers, with one layer per region and grid-point edges representing neighborhood interactions.A five-point, three-region example illustrates the layered construction.
  • Discrete models: Numerical results report that graph-cut solutions for Mumford–Shah segmentation are more efficient than partial-differential-equation-based approaches.Convex active-contour approaches provide an alternative segmentation strategy.

C. Graph BiLaplacian

Graph biLaplacians extend graph-Laplacian methods to second-order image-processing models. Their formulations connect discrete graph operators with harmonic and biharmonic PDEs under Neumann boundary conditions.

  • Graph biLaplacian: The graph biLaplacian is introduced as a second-order generalization of the graph Laplacian for graph-based image optimization methods.The normalized graph biLaplacian is defined analogously, with spectral properties studied separately.
  • Graph biLaplacian: The graph biLaplacian component at a vertex is defined using that vertex’s neighborhood, and its matrix rows provide the corresponding discrete operator.The neighborhood consists of all vertices connected to the vertex.
  • PDE connection: Graph Laplacian and graph biLaplacian formulations are equivalent to discretizations of harmonic and biharmonic PDEs with Neumann boundary conditions.The harmonic equation uses Δu = 0, while the biharmonic equation uses Δ²u = 0.
  • PDE connection: The biharmonic equation arises from minimizing total squared curvature.This connects the second-order graph operator to curvature-based regularization.
  • Scope and outlook: The article surveys graph spectral techniques for image compression, restoration, filtering, and segmentation, emphasizing graph selection as a central challenge.Future work targets application-specific graphs while trading performance against computational complexity.
Loading 1801.04749v2…