Optimized directional lifting with reduced complexity

The direction-adaptive discrete wavelet transform (DADWT) proves to be a very competitive alternative in scalable wavelet-based compression of images, yielding impressive compression performance gains in comparison to the classical DWT. A major limitation of DADWT though stems from its complexity, requiring an exhaustive search for the optimum prediction direction to be employed in the directional lifting process. This paper proposes a novel algorithm to lower the complexity of the DADWT by predicting the optimal prediction direction using a gradient-based technique. The algorithm is developed based on a mathematical model of the prediction errors generated via directional lifting of an input wedge image. The proposed approach avoids a time-consuming exhaustive search and yet the prediction step remains very simple and fast. It is shown that the proposed algorithm brings a complexity-reduction factor of 11/4 for almost no penalty in the prediction accuracy.