Concept

# Fractal compression

Summary
Fractal compression is a lossy compression method for s, based on fractals. The method is best suited for textures and natural images, relying on the fact that parts of an image often resemble other parts of the same image. Fractal algorithms convert these parts into mathematical data called "fractal codes" which are used to recreate the encoded image. Iterated function system Fractal image representation may be described mathematically as an iterated function system (IFS). We begin with the representation of a , where the image may be thought of as a subset of . An IFS is a set of contraction mappings ƒ1,...,ƒN, According to these mapping functions, the IFS describes a two-dimensional set S as the fixed point of the Hutchinson operator That is, H is an operator mapping sets to sets, and S is the unique set satisfying H(S) = S. The idea is to construct the IFS such that this set S is the input binary image. The set S can be recovered from the IFS by fixed point iteration: for any nonempty compact initial set A0, the iteration Ak+1 = H(Ak) converges to S. The set S is self-similar because H(S) = S implies that S is a union of mapped copies of itself: So we see the IFS is a fractal representation of S. IFS representation can be extended to a grayscale image by considering the image's graph as a subset of . For a grayscale image u(x,y), consider the set S = {(x,y,u(x,y))}. Then similar to the binary case, S is described by an IFS using a set of contraction mappings ƒ1,...,ƒN, but in , A challenging problem of ongoing research in fractal image representation is how to choose the ƒ1,...,ƒN such that its fixed point approximates the input image, and how to do this efficiently. A simple approach for doing so is the following partitioned iterated function system (PIFS): Partition the image domain into range blocks Ri of size s×s. For each Ri, search the image to find a block Di of size 2s×2s that is very similar to Ri. Select the mapping functions such that H(Di) = Ri for each i.