Graph based transforms for depth video coding

In this paper a graph-based transform is proposed as an alternative to the discrete cosine transform. An image or video signal is represented as a graph signal, where the graph is generated so as not to cross an image edge in a local region, i.e., square block. Then, spectral representation of graph signal is used to form transform kernels by finding eigenvectors of Laplacian matrix of the graph. This method requires to include additional information, i.e., edge map or adjacency matrix, into a bitstream so that a decoder can regenerate the exactly same graph used at an encoder. The novelty of this paper includes finding the optimal adjacency matrix and compressing it using context-based adaptive binary arithmetic coding. Coding efficiency improvement can be achieved when an image block contains arbitrarily shaped edges by applying the transform not across the edges. The proposed transform is applied to coding depth maps used for view synthesis in a multi-view video coding system, and provides 14% bit rate savings on average.