Parallel implementation of domain decomposition based image compression algorithm

Abstract

This paper presents algorithms for parallel implementation of the recently reported binary tree triangular coding (BTTC) method for lossy image compression. We present parallel BTTC algorithms for four models: (1) parallel random access machine (PRAM), (2) hypercube, (3) 2-D mesh, and (4) sparse mesh, with their respective time complexities as O((n/p) log(n/p)), O((n/p) (log(n/p) + log p)), O((n/p) (log(n/p) + log√p)), and O((n/p) (log(n/p) + log p)) for encoding and θ(n/p), θ ((n/p) (1+log p)), θ((n/p) (1+log√p)), and θ((n/p) (1 + log p)) for decoding, where n is total number of pixels in the image and p is number of processors.