A Study on Fractal Image Compression BY DARSHAN ALAGUD UNDER GUIDANCE O F K R R A O FA L L 0 9 E L E C T R I C A L E N G I N E E R I N G D E PA R T M E N T U N I V E R S I T Y O F T E X A S AT A R L I N G T O N Introduction What is a Fractal A Fractal is a geometrical shape that is self similar Example The Sierpinski triangle Introduction Most physical processes in nature yield Fractal structures FIC exploit self similarity in images of natural scenes like clouds hills trees bushes and textures for compression FIC technique represents images in terms of fractal codes or iterated function systems that can be used to generate the image Mathematical representation A grayscale image S maybe thought of as a subset of R3 3D vectors of real numbers Each point represented in R3 as x y I x y An IFS is a set of contraction mappings f1 fn that when iteratively applied to any initial image S0 results in a finite fixed set image S The contractive mapping theorem guarantees the existence of such a fixed set for contractive mappings Mathematical representation Contractive mappings are transforms on points in metric spaces such that the distance between the transformed points is less than that between original points The contractive mappings used in FIC are Affine transformations such as Fi x y z ai x bi y ei ci x di y fi si z oi si controls the contrast and oi the brightness Construction of an image using IFS of 2 affine functions THE ABOVE IMAGE WAS TAKEN FROM CREATIVE COMMONS AUTHOR SCOTT DRAVES Encoding The encoding involves choosing the IFS coefficients of Affine transforms such that its fixed set approximates the input image S In real images textures vary from one part to other Eg Skin Hair Clouds Hence instead of mapping whole image to parts of images Large parts are mapped to smaller parts One way to do this is by using Fractal transform coding by Barnsley Encoding Down sample input image S1 by factor 2 and low pass filter to give image S2 Partition image S1 and S2 into range and domain blocks respectively with block size 4X4 Now each block in range image is compared with corresponding block in domain image The most closest blocks are chosen in the LMS sense and the corresponding coefficients of transforms that would transform Block Di into Block Rj is stored in the file Decoding Starting with any image S0 apply the affine transforms with coefficients as given in the encoded file for several iterations The algorithm is guaranteed to converge to an image that is similar to the original image Features Fractal encoding is highly computationally intensive but decoding is very fast and hence maybe suitable for storage in image databases and CD ROMs The images after FIC become resolution independent This means when higher magnified images are generated more details are visible as compared to ordinary zoom which blurs out gradually Illustration of Resolution Independent decoding RID Original Image Fractal decoded image and ordinary zoom using imagemagik at 2x Fractal decoded image and ordinary zoomed image using imagemagik at 4x Fractal decoded image and ordinary zoomed image using imagemagik at 8x Applications OnOnesoftware developed under license from Iterated Systems Inc which is a photoshop plugin capable of saving files in compressed FIF Fractal Image Format To date the most successful use of still fractal image compression is by Microsoft in its Encarta multimedia encyclopedia ClearVideo also known as RealVideo Fractal and SoftVideo were early fractal video compression products Also used in a opensource codec called FIASCO Fractal Image and sequencing coded Fractal Image compression is especially useful when images are compressed only once but decoded several times Ex Storage media like CD ROMs or World wide web applications and for low bit rate applications Websites and References Yuval Fisher s paper Fractal Image Compression SIGGRAPH 92 Course Notes Sloane M F and A D A Better Way to Compress Images Byte Magazine January 1988 An introduction to fractal image compression Literature Number BPRA065 TI Europe October 1997 From the following link http focus ti com cn cn general docs lit get literature tsp literatureNumber bpra065 fileTy pe pdf http compression ru arctest descript fractal htm http www cs northwestern edu agupta pro Websites and References http www fileformat info mirror egff ch09 09 htm http www femtosoft biz fractals fractal htm l http en wikipedia org wiki Fractal compre ssion http en wikipedia org wiki Fractal transfo rm http en wikipedia org wiki Iterated functi on systems http en wikipedia org wiki Sierpinski gask et http www cs northwestern edu agupta p
View Full Document
Unlocking...