Rate-distortion optimized tree based coding algorithms

This paper addresses the problem of efficient coding of an important class of signals, namely piecewise polynomials. For this signal class, we develop a coding algorithm, which achieves oracle like rate-distortion (R-D) behavior in the high bit rate regime and with a reasonable computational complexity. For the 1-D case, our scheme is based on the binary tree segmentation of the signal and an optimal bit allocation strategy among the different signal segments. The scheme further encodes the similar neighbors jointly to achieve the right exponentially decaying R-D behavior (D(R) ~ CO^2-C1R ). We have also shown that the computational cost of the scheme is of the order O(N log N). We then show that the scheme can be easily extended to the 2-D case, as the quadtree based coding scheme, with the similar R-D behavior and computational cost. Finally, we conclude with some numerical results.