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

The graph-based block transform recently emerged as an effective tool for compressing some special signals such as depth images in 3D videos. However, in existing methods, overheads are required to describe the graph of the block, from which the decoder has to calculate the transform via time-consuming eigendecomposition. To address these problems, in this paper, we aim to develop a single graph-based transform for a class of 2D piecewise smooth signals with similar discontinuity patterns. We first consider the deterministic case with a known discontinuity location in each row. We propose a 2D first-order autoregression (2D AR1) model and a 2D graph for this type of signals. We show that the closed-form expression of the inverse of a biased Laplacian matrix of the proposed 2D graph is exactly the covariance matrix of the proposed 2D AR1 model. Therefore, the optimal transform for the signal are the eigenvectors of the proposed graph Laplacian. Next, we show that similar results hold in the random case, where the locations of the discontinuities in different rows are randomly distributed within a confined region, and we derive the closed-form expression of the corresponding optimal 2D graph Laplacian. The theory developed in this paper can be used to design both pre-computed transforms and signal-dependent transforms with low complexities. Finally, depth image coding experiments demonstrate that our methods can achieve similar performance to the state-of-the-art method, but our complexity is much lower. [ABSTRACT FROM AUTHOR]