Efficient Graph Construction For Image Representation

Sarath Shekkizhar, Antonio OrtegaICIP 2020 · OpenReview

TL;DR

This paper introduces a novel, efficient method for constructing sparse graphs from images, adapting the Non-negative Kernel Regression (NNK) approach. By exploiting image-specific properties, their method significantly speeds up graph construction and leads to better image representation and denoising performance compared to traditional graph constructions derived from filters like the bilateral filter.

What Problem Does This Paper Address?

Many modern image processing techniques, such as bilateral filtering, can be interpreted through the lens of graph signal processing. In this framework, pixels are nodes, and edges with associated weights represent relationships between them. However, constructing these graphs often relies on simple, fixed-size windows, leading to dense graphs that are computationally expensive and may not optimally capture the intrinsic structure of the image data. This limits the interpretability and efficiency of these methods, especially for large images. The paper aims to address this by developing a more efficient and data-driven graph construction method that produces sparse graphs, thereby improving computational performance and representation quality.

Methods

The core contribution is the adaptation of the Non-negative Kernel Regression (NNK) graph construction method for image data. NNK graphs are designed to be sparse and adapt to the intrinsic data properties, unlike fixed-window approaches. The authors leverage the regularity of pixel positions in images and specific characteristics of image kernels (like the bilateral filter) to develop image-specific simplifications.

Key techniques include:

  • Kernel Ratio Interval (KRI) Conditions: The paper adapts the KRI conditions from NNK to image graphs. These conditions provide a principled way to determine edge connectivity based on pixel similarity and spatial relationships.
  • Image-Specific Simplifications: By exploiting the regular grid structure of images and the known spatial relationships, the authors derive simplified KRI conditions. This allows for efficient pruning of edges, leading to sparse graphs. They introduce a thresholding rule based on the relative differences in intensity and spatial distances between pixels.
  • Spectral Graph Wavelets (SGW): The proposed sparse NNK graphs are then used in conjunction with SGW for image representation and denoising. SGW provides a way to analyze signals on graphs in a spectral domain, analogous to Fourier transforms but adapted for graph structures.

Datasets

The paper evaluates its method on standard image datasets, using a collection of 12 typical images (256x256) for denoising experiments. These images are corrupted with Gaussian noise at various variance levels (σ = 10, 15, 20, 25, 30). The paper does not introduce new datasets but uses these standard benchmarks to demonstrate the effectiveness of their approach.

Key Insights and Ideas

  • Sparsity is Key for Efficiency: The primary insight is that constructing sparse graphs, rather than dense ones derived from fixed windows, dramatically improves computational efficiency for graph-based image processing tasks.
  • Image Structure Enables Faster NNK: The regular grid structure of images is not a limitation but an opportunity. By exploiting this regularity, the authors can significantly speed up the NNK graph construction process, making it scalable to large images.
  • NNK Graphs Offer Better Representation: The sparse NNK graphs capture image energy more compactly in the wavelet domain compared to traditional bilateral filter graphs. This suggests a more efficient and accurate representation of image content.
  • Denoising Benefits from Sparse Graphs: Using SGW with the proposed sparse NNK graphs leads to improved denoising performance, outperforming SGW with dense bilateral filter graphs. This highlights how the quality of the graph construction directly impacts downstream applications.

Key Results

  • Speedup: The proposed NNK graph construction achieves average speedups of at least a factor of 10 for a 11x11 window compared to the original NNK algorithm. For graph wavelet operations, the speedup can be up to 15x compared to using BF graphs.
  • Sparsity: The NNK graphs have 90% fewer edges than bilateral filter graphs constructed with an 11x11 window.
  • Energy Compaction: NNK graphs demonstrate better energy compaction in the wavelet domain, capturing more image energy in lower frequency bands.
  • Denoising Performance: When used with Spectral Graph Wavelets, the proposed NNK graphs achieve improved SSIM and comparable PSNR for image denoising compared to traditional BF graphs. The performance is also competitive with BM3D.

Limitations and Future Work

  • Limitations: The paper acknowledges that the proposed method is an approximation of the original NNK weights, using the bilateral kernel weights after pruning. While justified by experimental results, it's an approximation. The current work focuses on the bilateral filter graph as a starting point, and its direct applicability to other complex filters might require further adaptation.
  • Future Work: The authors suggest exploring the performance of their graph construction with more complex filtering kernels, such as those used in non-local means, BM3D, and kernel regression methods. They also highlight the potential for parallelization, further enhancing computational efficiency.

Summary updated

Abstract

Graphs are useful to interpret widely used image processing methods, e.g., bilateral filtering, or to develop new ones, e.g., kernel based techniques. However, simple graph constructions are often used, where edge weight and connectivity depend on a few parameters. In particular, the sparsity of the graph is determined by the choice of a window size. As an alternative, we extend and adapt to images recently introduced non negative kernel regression (NNK) graph construction. In NNK graphs sparsity adapts to intrinsic data properties. Moreover, while previous work considered NNK graphs in generic settings, here we develop novel algorithms that take advantage of image properties, so that the NNK approach can scale to large images. Our experiments show that sparse NNK graphs achieve improved energy compaction and denoising performance when compared to using graphs directly derived from the bilateral filter.
BibTeX
@inproceedings{shekkizhar2020efficient,
  author = {Sarath Shekkizhar and Antonio Ortega},
  title = {{Efficient Graph Construction For Image Representation}},
  booktitle = {ICIP},
  year = {2020},
  url = {https://openreview.net/forum?id=01DVjZKY7C},
}
Figure