Morphological filtering on graphs

Jean Cousty, Laurent Najman, Fabio Dias, Jean Serra

TL;DR

This paper introduces a novel framework for morphological filtering directly on graphs, extending traditional image processing techniques to more general graph structures. This approach allows for more nuanced analysis and filtering of data represented as graphs, outperforming existing methods in image denoising tasks.

What Problem Does This Paper Address?

Traditional mathematical morphology, a powerful tool for image analysis and processing, primarily operates on sets of points (like pixels in an image). However, many real-world datasets are more naturally represented as graphs, where relationships between data points are crucial. Applying standard morphological operators to these graph structures directly is challenging. This paper addresses this gap by developing a formal framework for morphological operations on the lattice of subgraphs, enabling the extension of morphological filtering to graph-based data. This is particularly relevant for applications where connectivity and adjacency are as important as the individual data points themselves.

Methods

The core of this paper lies in defining morphological operators that act on the lattice of subgraphs. The authors introduce dual adjunctions between vertex sets and edge sets of graphs, which form the basis for defining graph dilations and erosions. These fundamental operators are then composed to create more complex morphological filters, including openings, closings, granulometries, and alternate sequential filters, all operating directly on subgraphs. The framework is further extended to handle weighted graphs, allowing for the processing of grayscale images. The authors leverage the algebraic properties of lattices and adjunctions to rigorously define and prove the behavior of these operators.

Datasets

The paper uses synthetic binary images (e.g., a zebra, text characters) and grayscale images for illustration and evaluation. These images are degraded with various types of noise (impulse noise, random noise) to test the effectiveness of the proposed filters. No new datasets are introduced.

Key Insights and Ideas

  • Morphology on Graphs is Possible and Powerful: The paper demonstrates that traditional morphological concepts can be formally extended to operate directly on graph structures, not just pixel grids.
  • Vertex-Edge Duality is Key: The introduction of dual adjunctions between vertex and edge sets is a crucial step in defining graph-based morphological operators.
  • Graph Operators Capture More Nuance: The graph-based morphological operators can capture connectivity and adjacency properties that are lost when reducing a graph to a simple set of vertices. This leads to improved performance in tasks like image denoising.
  • Unified Framework for Spatially Variant and Invariant Filters: The proposed graph-based approach naturally accommodates both spatially invariant and spatially variant morphological filters, offering greater flexibility.
  • Extension to Weighted Graphs: The framework seamlessly extends to weighted graphs, enabling the processing of grayscale images and other weighted data.

Key Results

  • Improved Denoising Performance: The proposed graph-based Alternate Sequential Filters (ASF) consistently outperform traditional ASF filters (using structuring elements) and median filters in denoising binary and grayscale images, as evidenced by lower Mean Square Errors (MSE). For instance, in one experiment, the graph ASF achieved an MSE of approximately 4% compared to 16% for the usual ASF at the highest noise level.
  • Balanced Noise Treatment: The graph ASF treats white and black noise more symmetrically than traditional filters.
  • Spatially Variant Filters Offer Further Improvement: Using spatially variant graphs derived from image gradients further enhances denoising results compared to spatially invariant graph filters.
  • Efficiency: The proposed operators can be computed efficiently, with linear-time algorithms for basic operations.

Limitations and Future Work

  • Extension to Multi-valued Functions: The authors suggest that extending the framework to multi-valued functions would allow for the processing of color images.
  • Faster Computation for Iterated Operators: Developing algorithms based on distance maps for very fast computation of iterated operators is a promising direction.
  • Graphs Embedded in Metric Spaces: Investigating morphological operators for graphs embedded in metric spaces, where edge lengths influence operator behavior, is an area for future research.
  • Simplicial and Cubical Complexes: The framework can be extended to higher-dimensional structures like simplicial and cubical complexes.
  • Quantitative Evaluation: While promising results are shown, the authors acknowledge that a more extensive quantitative evaluation on a larger database of real images is needed for definitive conclusions.

Summary updated

Abstract

We study some basic morphological operators acting on the lattice of all subgraphs of an arbitrary (unweighted) graph G. To this end, we consider two dual adjunctions between the edge set and the vertex set of G. This allows us (i) to recover the classical notion of a dilation/erosion of a subset of the vertices of G and(ii) to extend it to subgraphs of G. Afterward, we propose several new openings, closings, granulometries and alternate filters acting (i) on the subsets of the edge and vertex set of G and (ii) on the subgraphs of G. The proposed framework is then extended to functions that weight the vertices and edges of a graph. We illustrate with applications to binary and grayscale image denoising, for which, on the provided images, the proposed approach outperforms the usual one based on structuring elements.
BibTeX
@article{cousty2013morphological,
  author = {Jean Cousty and Laurent Najman and Fabio Dias and Jean Serra},
  title = {{Morphological filtering on graphs}},
  journal = {Comput. Vis. Image Underst.},
  year = {2013},
  url = {https://openreview.net/forum?id=88xSKEYlBxH},
}
Figure