HEXAGONAL PARTITIONING AND ITS PARALLEL PROCESSING FOR FRACTAL IMAGE COMPRESSION

Abstract

In this thesis, three aspects of the fractal image compression are explored: (I) A new hexagonal partitioning scheme, (2) A two-level fast domain block search scheme, (3) The parallelization of the above algorithms on a Distributed Memory Parallel Machine - the Fujitsu AP3000 machine. In the context of Partitioned Iterated Function System (PIFS), the encoding process comprises two steps: (i) the partitioning of original image into a collection of non-overlapping range blocks, (ii) the searching of best matched domain blocks to resemble the range blocks evaluated by particular similarity measure. The partitioning scheme is therefore an important issue. There exist a number of different partitioning schemes based on various block shapes including square, rectangle and triangle. The proposed hexagonal partitioning scheme is based on hexagonal clusters, which are of the following properties. First, each hexagonal cluster can be partitioned into seven identical smaller clusters. Second, the hexagonal clusters have jagged and slanting block edges. One main advantage of using such a hexagonal cluster based partitioning scheme lies in the fact that the reconstruction quality for detail-dominant or detail-dominant images is better than those of other partitioning schemes, such as. QuadTree partitioning. The efficient domain search scheme is another key issue worth careful consideration. To speedup the searching process while retaining the reconstruction quality, a two-level fast search is proposed. In the method, the first level briefly 'scan' an area of image, which contains a number of domain blocks, and the second level closely examines all domain blocks in the area provided the first level gives positive results, otherwise, all domain blocks in the area are ignored. The method is proven to be efficient. A speedup of about 13 can be obtained while the reconstruction quality is slightly affected by -0.35 dB. To further speedup the encoding process, both full search and fast search schemes are parallelized on a distributed memory parallel machine, namely, the Fujitsu AP3000 machine. During parallelization of sequential algorithms, the appropriate scheduling scheme is essential in order to achieve high speedup. For the full search scheme, since is computational load is fixed and known beforehand, two static scheduling schemes, namely Static Domain Distribution and Static Range Distribution, are employed. For the fast search scheme, since its computational load is unpredictable and undetermined beforehand, a dynamic scheduling scheme based on Dynamic Range Distribution, is employed, so that the working load is evenly distributed among processors. With appropriate scheduling schemes, a speedup of about 10 of encoding algorithm can be obtained for both the full search and fast search methods.