Zhi-Yong Chen, January 2002--April 2003, "New Improvements on Time Complexity and Compression Ratio for Lossless Binary Tree Predictive Coding", degree conferred on Spring 2003 convocation, Computer Science Department, University of Western Ontario, Canada.

M.Sc. Thesis Abstract

Data structures and prediction strategies are very important factors in most image compression algorithms. In this thesis, the binary tree data structure and shape adaptive predictors of Binary Tree Predictive Coding (BTPC) have been analyzed, and two modifications are provided to further improve the performance of the algorithm. These modifications are: * Optimize the tree structure by adjusting the level of the binary tree and the threshold which is used to separate tree and data portions. * Modify the "Line/Valley/Ridge" predictors.

The modified schemes have been tested on 40 different images. The results show that when optimizing the tree structure, the decoding time complexity of the BTPC scheme is reduced by 10.25% (on average) without degrading the compression ratio. In fact, the compression performance is slightly improved by 1.03%, on average. When tree structure optimization and predictor modification are combined, the decoding time complexity of the BTPC scheme is reduced by 7.94%, with a 1.33% improvement of the compression ratio. After applying the proposed improvements, the average decoding time of the BTPC scheme outperforms the average decoding time of state-of-the-art lossless image compression scheme JPEG-LS.

Keywords: binary tree predictive coding, BTPC, data compression, image encoding, prediction, time complexity, computational complexity, compression ratio, noncausal shape-adaptive predictor, Huffman codes, tree codes.