23-08-2012, 02:40 PM
Fast Search Strategies for Fractal Image Compression
1Fast Search Strategies.pdf (Size: 875.92 KB / Downloads: 73)
In traditional fractal image compression, the encoding procedure is time-consuming
due to the full search mechanism. In order to speedup the encoder, we adopt particle
swarm optimization method performed under classification and Dihedral transformation
to further decrease the amount of MSE computations. The classifier partitions all of the
blocks in domain pool and range pool into three classes according to the third level
wavelet coefficients. Each range block searches the most similar block only from the
blocks of the same class. Furthermore, according to the property of Dihedral transformation,
only four transformations for each domain block are considered so as to reduce the
encoding time. Experimental results show that, the encoding time of the proposed method
is faster than that of the full search method. Experimental results show that the proposed
method is about 178 times faster with only 1.46 dB decay in image quality.
INTRODUCTION
The idea of fractal image compression (FIC) was originally introduced by Barnsley
[1] and the first practical FIC scheme was realized by Jacquin in 1992 [2]. The underlying
premise is based on the partitioned iteration function system (PIFS) which utilized
the self-similarity property in the image to achieve the purpose of compression [3]. The
encoding process of the fractal image compression is time-consuming. The reason is that
most of the encoding time is spent on a large amount of computations of similarity measure.
Hence one of the main research direction for fractal image compression is focused
on how to reduce the encoding time.
In the past, FIC with some classification methods were usually adopted, in which
ranges and domains were classified in the preprocessing step. At each search entry, only
domains with a similar class were examined [4-6]. Domain pool reduction is another
technique to reduce the encoding time. A common method was to restrict the search
space to those blocks whose spatial location was near the range location [7, 8].
FRACTAL IMAGE COMPRESSION
Fractal image compression is based on the local self-similarity property in a nature
images. The fundamental idea is coming from the Partitioned Iterated Function System
(PIFS). Suppose the original gray level image f is of size m × m. Let the range pool R be
defined as the set of all non-overlapping blocks of size n × n of the image f, which makes
up (m/n)2 blocks. For obeying the Contractive Mapping Fixed-Point Theorem, the domain
block must exceed the range block in length. Let the domain pool D be defined as
the set of all possible blocks of size 2n × 2n of the image f, which makes up (m − 2n +
1)2 blocks. For m is 256 and n is 8, the range pool R is composed of (256/8) × (256/8) =
1024 blocks of size 8 × 8 and the domain pool D is composed of (256 − 16 + 1) × (256 −
16 + 1) = 58081 blocks of size 16 × 16. For each range block v from the R, the fractal
affine transformation is constructed by searching all of the domain blocks in the D to
find the most similar one and the parameters representing the fractal affine transformation
will form the fractal compression code for v.
FAST FRACTAL IMAGE ENCODING
Particle Swarm Optimization for FIC
Recently, the particle swarm optimization (PSO) has been successfully applied to
various optimization problems. This optimization algorithm combines social psychology
principles in socio-cognition human agents and evolutionary computations. The PSO algorithm
is motivated by the behavior of organisms, such as fish schooling and bird flocking.
It is characterized as a simple concept, which is both easy to implement and computationally
efficient. Unlike other heuristic techniques, PSO has a flexible and well-balanced
mechanism to enhance the global and local exploration abilities [15]. This algorithm
begins with generating an initial population of random solutions. Each individual, also
called a particle, is assigned with a randomized velocity according to its own and companions’
flying experiences. It has constructive cooperation by sharing information with
other particles [15, 16].
Proposed Algorithm
In order to improve the encoding speed, we use particle swarm optimization, given
in section 3.1, as the block searching mechanism instead of the traditional full searching
method. The DWT classification method given in section 3.2, in comparison to the full
search method, can remove about two-thirds of the MSE computations. According to the
Dihedral transformation method given in section 3.3, only four MSE computations out of
eight are computed and therefore only half of the computation time is required. In this
section, we adopt particle swarm optimization method performed under classification
and Dihedral transformation to reduce the amount of MSE computations. For each range
block v, we use particle swarm optimization as the searching strategy in the domain pool
in which the flowchart is shown in Fig. 4.
CONCLUSION
In this paper, particle swarm optimization method is adopted with classification and
Dihedral transformation in order to speedup the fractal image encoder. The PSO algorithm
is used to search the best match solution in the search space. In the search mechanism,
similarity measure are performed only when both the domain and range blocks are
of the same type. Furthermore, according to Dihedral transformation property, only four
transformations of the domain block are considered so that the encoding time can be reduced
further. Under the condition of the same PSNR, the encoding time of the proposed
method is about 1.75 of the SGA method. The proposed method speedups the encoder
effectively with only little decay in image quality.