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"
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
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.