Tree triangular coding image compression algorithms

Abstract

This paper presents new algorithms for image compression that are an improvement on the recently published Binary Tree Triangular Coding (BTTC). These algorithms are based on recursive decomposition of the image domain into triangles where the new triangle vertex is located at the point of maximum prediction error and does not require the constraints of right-angled isosceles triangle and square image as in previous algorithm. These algorithms execute in O(n log n) for encoding and θ(n) for decoding, where n is the number of image pixels. Simulation results show that the new algorithms have a significant execution time advantage over conventional BTTC while providing a quality of the reconstructed image as good as BTTC. This improvement is obtained by eliminating a major weakness of the standard BTTC, wherein the algorithm does not utilize the point of maximum error for domain decomposition despite performing an exhaustive search (in the worst case) over the triangular domain. © 2001 World Scientific Publishing Company.