# Graph Fourier Transform with Negative Edges for Depth Image Coding

arXiv: https://arxiv.org/abs/1702.03105 · HTML: https://mlsanity.com/paper/1702.03105/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2017.

## Built on by (most cited first, 4 of 4)

- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming](https://mlsanity.com/paper/2409.07794/) (2024)
- [Hybrid Model-based / Data-driven Graph Transform for Image Coding](https://mlsanity.com/paper/2203.01186/) (2022)
- [Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming](https://mlsanity.com/paper/2506.01826/) (2025)

## Abstract (arXiv)

Recent advent in graph signal processing (GSP) has led to the development of new graph-based transforms and wavelets for image / video coding, where the underlying graph describes inter-pixel correlations. In this paper, we develop a new transform called signed graph Fourier transform (SGFT), where the underlying graph G contains negative edges that describe anti-correlations between pixel pairs. Specifically, we first construct a one-state Markov process that models both inter-pixel correlations and anti-correlations. We then derive the corresponding precision matrix, and show that the loopy graph Laplacian matrix Q of a graph G with a negative edge and two self-loops at its end nodes is approximately equivalent. This proves that the eigenvectors of Q - called SGFT - approximates the optimal Karhunen-Lo`eve Transform (KLT). We show the importance of the self-loops in G to ensure Q is positive semi-definite. We prove that the first eigenvector of Q is piecewise constant (PWC), and thus can well approximate a piecewise smooth (PWS) signal like a depth image. Experimental results show that a block-based coding scheme based on SGFT outperforms a previous scheme using graph transforms with only positive edges for several depth images.