Graph-Based Transform for 2D Piecewise Smooth Signals With Random Discontinuity Locations.

Area of Science:

• Signal Processing
• Image Compression
• Graph Theory

Background:

• Graph-based block transforms are effective for compressing specific signals, like depth images.
• Existing methods require significant overhead for graph description and involve computationally expensive eigendecomposition for transform calculation.

Purpose of the Study:

• To develop a single, efficient graph-based transform for 2D piecewise smooth signals with similar discontinuity patterns.
• To reduce the computational complexity associated with current graph-based transform methods.

Main Methods:

• Proposed a 2D first-order autoregression (2D AR1) model and a corresponding 2D graph for deterministic signals with known discontinuity locations.
• Derived the closed-form expression for the inverse of the biased Laplacian matrix of the proposed 2D graph, showing its equivalence to the 2D AR1 model's covariance matrix.
• Extended the methodology to random cases with confined, randomly distributed discontinuities, deriving the optimal 2D graph Laplacian.

Main Results:

• The eigenvectors of the proposed 2D graph Laplacian represent the optimal transform for the signals.
• The derived graph Laplacian provides a closed-form solution, eliminating the need for eigendecomposition.
• Experimental results on depth image coding show comparable performance to state-of-the-art methods with significantly lower computational complexity.

Conclusions:

• The developed theory enables the design of both pre-computed and signal-dependent transforms with reduced complexity.
• The proposed method offers an efficient alternative for compressing 2D piecewise smooth signals, particularly depth images.
• This approach significantly lowers the computational burden in graph-based signal compression.