Lifting transforms on graphs: theory and applications

UnrestrictedThere are many scenarios in which data can be organized onto a graph or tree. Data may also be similar across neighbors in the graph, e.g., data across neighboring sample points may be spatially correlated. It would therefore be useful to apply some form of transform across neighboring sample points in the graph to exploit this correlation in order to achieve more compact representations. To this end, we describe a general class of de-correlating lifting transforms that can be applied to any graph or tree, and propose a variety of transform optimizations. We mainly focus on the design of tree-based lifting transform designs. Extensions to graph-based lifting transforms are also discussed. As a first application, we develop distributed graph-based transforms for efficient data gathering in wireless sensor networks (WSNs), where the goal is to transmit data from every node in the network to a collection (or sink) node along a routing tree. In particular, we (i) propose a general class of unidirectional transforms that can be computed in a distributed manner as data is routed toward the sink, and (ii) provide conditions for their invertibility. Moreover, we show that any unidirectional lifting transform is invertible, and propose a variety of tree-based lifting transform designs. By using these transforms to de-correlate data in the network, the total communication cost for data gathering is significantly reduced. We also extend these tree-based lifting transforms to incorporate broadcast communication links. This leads to a set of graph-based lifting transforms for WSNs. In particular, nodes incorporate data received from their broadcast neighbors together with data received from their neighbors in the routing tree. By doing so, they are able to achieve more data de-correlation. By exploiting the additional broadcast communication links in this way, these graph-based lifting transforms reduce the total communication cost even further.; In addition to the transform designs, we also propose an algorithm that can jointly optimize the choice of routing tree with the transform. As a second application, we also develop graph-based transforms for image compression. In particular, we focus on designing graph-based transforms that avoid filtering across edges in an image. This reduces the number of large magnitude coefficients, which are expensive to code, and ultimately reduces the total bit rate while also preserving better the edge structure in the reconstructed images. To this end, we first discuss how our tree-based lifting transforms generalize existing wavelet transforms proposed for image coding, then propose algorithms to design the trees and transforms. By avoiding filtering across edges, our tree-based lifting transforms yield better coding efficiency than standard transforms (i.e., the total bit rate is reduced for a fixed reconstruction quality). We also develop an edge-adaptive intra prediction scheme that avoids computing predictions across edges in an image/video frame. Since predictions are not computed across edges, our scheme significantly reduces the number of large magnitude coefficients that must be coded. This new scheme is then incorporated with the intra prediction scheme in H.264/AVC, and is shown to increase the overall coding efficiency of H.264/AVC. Moreover, when using this new scheme to code depth map images in a multi-view video coding system (where virtual views are synthesized using video plus depth from existing views), we also see an improvement in the quality of the virtual views