Project Description
The first fully automated fractal image compression algorithm was
published by Arnaud Jacquin in 1989. Given an image f, the encoder
finds a contractive affine image transformation (fractal transform) T
such that the fixed point of T is close
to f. The decoding is by iteration of the fractal transform starting
from an arbitrary image. Due to the contraction mapping principle, the
sequence of iterates converges to the fixed point of T. Jacquin's
original scheme showed promising results. Since then, several
researchers have improved the original algorithm.
Our group has the following contributions in this field:
- Reduction of the encoding complexity : In the encoding
step, the image is partitioned into disjoint blocks (range blocks).
For each range block, another block (domain block) is selected from the
same image. The goal is to approximate the pixel intensities of the
range block with
those of a domain block. Good approximations are obtained when many
domain blocks are allowed. Thus, searching for domain blocks is
time-consuming.
- Nearest neighbor search
[Saup94b,
Saup95a,
Saup95b]:
Range blocks
and domain blocks are assigned d-dimensional feature vectors such that
searching in the pool of domain blocks can be restricted to the domain
blocks whose feature vectors are the nearest neighbors of the feature
vector of the current range block. Thus, the sequential search in the
domain pool is replaced by multi-dimensional nearest neighbor searching
which can be run in logarithmic time.
- Clustering methods
[Hamz95]:
The domain blocks are classified by
clustering their feature vectors in Voronoi cells whose centers are
designed from the test image or from a
set of training images. For each range block, matches are sought in the
neighboring classes only.
- Fast search via fast convolution
[Saup96b,
SaHar95b]:
This is a
lossless method in a sense that the domain block that yields the
minimal approximation error is obtained rather than an acceptable but
suboptimal one. A calculation of the inner products between the range
blocks and codebook blocks (blocks formed from the domain blocks)
dominates the computational costs in the encoding. The codebook blocks
are typically defined by downfiltering the image
to half its resolution. The inner products are the finite
impulse response (FIR) of the downfiltered image with respect to the
range blocks. Thus, the cross-correlation of the range block with the
downfiltered image is required. This discrete two-dimensional
convolution can be carried out more efficiently in the frequency domain
when the range block is not too small.
- Domain pool reduction
[Saup96a]:
An adjustable number of domains
are excluded from the domain pool. We studied the effects on
computation time, image fidelity and
compression ratio. We showed that there is no need for keeping domains
with low intensity variance in the pool.
Use of adaptive partitions
[SaRu96a,
RuHaSa97,
HaSa98]:
We devised a fractal coder
that finds the image partition by a split and merge process, yielding
range blocks as unions of edge-connected small square blocks. This
fractal coder has a better rate-distortion
performance and subjective quality than the widely used quadtree-based
fractal coders. A source code for the algorithm can be found here.
Rate-distortion fractal coding
[SRHGM98,
HaSa00]:
Usually, the fractal
transform is found in a heuristic way. We proposed rate-distortion
based fractal coding [SRHGM98] where the fractal transform is optimal
in the sense that it guarantees the lowest approximation
error over a large set of admissible transforms that are subject to a
rate constraint. We begin with a fine scale hierarchical partition of
the image and use a pruning strategy based on the generalized BFOS
algorithm. We give
results for rectangular partitions.
Computational complexity: Standard fractal coding is a
greedy suboptimal
algorithm because a domain block is sought for a range block
independently of the other range-domain mappings. We showed that the
problem of finding the optimal fractal code is computationally
intractable
[RuHa97a].
Attractor coding: We showed how to use gradient descent
methods that search for local minima of
the reconstruction error
[VrSa99]
seen as a function of the parameters
of the fractal transform. We also proposed a local search algorithm
[HaHaSa00,
HaSaHi00,
HaSaHi01]
that starts from
an initial mapping obtained by standard coding and iteratively provides
a sequence of contractive mappings whose fixed points are monotonically
approaching the original image. Experimental
results show that the rate-distortion improvement over standard coding
is significant.
Acceleration of the decoding
[Hamz96a,
Hamz97b,
Hamz97c,
Hamz99]:
In conventional
decoding, two image arrays are needed at each iteration. We showed that
the decoding can be accelerated by keeping only one image array and
using the new pixel intensities of an image iterate as soon as they
become available. We also showed that the convergence of the proposed
decoding can be enhanced by an ordering of the pixels.
Enhancement with vector quantization
[HaMuSa96a,
HaMuSa96b,
HaSa00]:
We showed how a few fixed vectors designed from a set of training
images by a clustering algorithm accelerate the search for the domain
blocks and improve both the rate-distortion performance and the
decoding speed of a pure fractal coder, when they are used as a
supplementary vector quantization codebook. We implemented two
quadtree-based schemes: a fast top-down heuristic technique and one
optimized with a Lagrange multiplier method. A source code for the
algorithm used in [HaSa00] can be found
here.
Postprocessing of decoded images:
To reduce the blocking artifacts in the reconstructed images, we
proposed iterative postprocessing techniques that use edge detection
and adaptive smoothing filters
[GiSa00].
Quantization of luminance coefficients
[HaSaBa97]:
Most fractal coding schemes use affine transformations to map the grey
values of a domain on to a range block. The involved real parameters
have to be quantized; we have considered vector quantization for this
problem.
Analogy with vector quantization
[HaGaSa97]:
Relevant
features of fractal image compression are included in mean shape gain
vector quantization.
Progressive (embedded) fractal coding
[KoSaHa01]:
In progressive coding,
the bit-steam encoding the image consists of a series of successive segments.
Each prefix of the stream (consisting of a number of successive segments) can be decoded to obtain an approximation of the original image. By decoding additional
segments, we can gradually improve this approximation.
The problem is thus to find successive segments such that each prefix is decodable. Moreover, each segment should achieve the largest quality improvement
among all possible segments with the same size. This is called a distortion-rate optimal
progressive coding.
We designed a distortion-rate optimal progressive compression algorithm for the fractal code.
Fractal coding in noisy channels
[StaHaSa01c,
ChaEtAl02]:
Channel errors in the fractal code can lead to large degradations or even make it impossible to decode the image. The error-sensitivity of the bits of the fractal code parameters is measured. We obtain sensitivity classes, which are protected
with different number of protection bits according to their importance and
according to the given distortion-rate constraint.
A joint source-channel coding algorithm is proposed to find an optimal protection
bit allocation for these classes.
Support
-
DFG Grants Sa 449/5 and Sa449/8
|