Project Final Report A Study on Fractal Image Compression By Darshan S Alagud ID 100727906 Fall 2010 Instructor Dr K R Rao List of Acronyms FIC Fractal image compression IFS Iterated function system JPEG Joint Photographic Experts Group MSE Mean square error PIFS Partitioned iterated function systems PSNR Peak signal to noise ratio QF Quality factor SSIM Structural similarity matric Proposal In this project a study on fractal based image compression using PIFS algorithm and fixed size partitioning will be made analyzed for performance and compared with a standard frequency domain based image compression standard JPEG Sample images will be used to perform compression and decompression And performance metrics such as compression ratio MSE PSNR SSIM compression time and decompression time will be measured and compared for both PIFS and JPEG cases Also the phenomenon of resolution scale independence will be studied and described with examples Introduction Fractal based image compression FIC techniques exploit redundancy due to selfsimilarity properties in images to achieve compression A fractal maybe defined as a geometrical shape that is self similar i e it has parts that are similar to the whole An example of a fractal is the below figure 8 Figure 1 The Sierpinski triangle 8 In the above figure the three triangles at each corner of a triangle are similar to the whole triangle Self similarity can be found in nature such as in clouds trees ferns mountain ranges etc and in natural images The amount of information therefore needed to describe such images is a lot lesser than it appears and hence image compression using fractalbased methods is possible Fractal based image compression such as PIFS exploits redundancy due to ordinary symmetry similarity also in addition to self similarity Mathematical Representation Mathematically in FIC an Iterated function system IFS describes an image An IFS is a set of contractive affine transforms An affine transform is a linear transform of the form 3 In the above equation wi is the transform applied on a point x y z in the ith block of input image Grayscale images can be represented by such points x y z in which case z would be the intensity or gray level at pixel co ordinates x y in an image The a i1 ai2 ai3 ai4 di1 and di2 are constants for the ith image block to which the transform is applied An affine transform is said to be contractive if the distance between transformed points is less than that between the original points in the metric space The Contractive mapping theorem guarantees that for such a set of affine transforms or IFS the repeated application of IFS to an initial random image which converges to a finite fixed point image The goal of FIC is to find such an IFS that would describe the input image For example consider the below IFS consisting of 2 affine transforms represented by their effect on a square each function transforms the outlined square into the shaded square Both functions are applied to the input image and a union U of the resulting images is formed in each iteration First three iterations are shown and then the final image fixed point image after several iterations is shown Figure 2 Illustration of construction of an image using an IFS of 2 affine functions The above image is taken from Creative Commons author Scott Draves 11 Encoding In this project the algorithm studied or used for Fractal image compression is known as Partitioned Iterative Function Systems or PIFS approach In this approach rather than forming the image from copies of its whole self the image is formed from copies of properly transformed parts of the image In other words the input image to the compressor is partitioned into a number of non overlapping range blocks Rj and nonoverlapping domain blocks Di Then a contractive mapping wi as described in Equation 1 0 and a Domain block Di is found for every Rj such that the transformed copy of the Domain block Di is very close to Ri The distance metric used here is mean square error MSE The following image shows matching domain and range blocks in images that the PIFS algorithm looks for Figure 3 Matching Range and Domain blocks in an image 7 One pair with green borders matches due to ordinary symmetry and the other with red borders matches due to self similarity In the above image the bigger red block matches the smaller one due to self similarity And the bigger green and smaller green blocks also match due to ordinary similarity between different parts of the same image This partitioning and comparison of Range and Domain block is achieved by first calculating a domain image from the range image as shown in the figure below Figure 4 Generation of domain image from range image and fixed size partitioning In this project the input image partitioning is done with non overlapping square range blocks of fixed size 16x16 pixels The domain block size before downsampling is double the range block size which is 32x32 pixels In order to create the domain image every 4 neighboring pixels of the range image is averaged and mapped to one pixel of the domain image as shown above 4 red pixels being mapped to one blue pixel in domain image This is equivalent to down sampling the range image by half and then low pass filtering Now Rj blocks in range image and Di blocks in domain image are of same size 16x16 pixels and are ready for comparison To find the best affine map we need to determine the co efficients in equation 1 0 for every domain and range block combination and choose the affine map that generates the closest match between a Rj Di pair The ai1 ai2 ai3 and ai4 are constrained to be 0 5 here since the Domain size is always twice the range size The translation constants d i1 and di2 are determined by the position of the top left corner pixel of the domain The constants c i and bi which represent the contrast scaling and brightness offset are calculated for each Rj Di pair by minimizing the sum of squared errors between a range block R j and domain block Di which is given by 3 E ci bi Nk 1 ci dk bi rk 2 2 0 In the above equation k is the index of the pixel in the domain or range block and i is the index of the domain block k varies from 1 to N the number of pixels in the domain range block The rk are the pixel values of each range block and d k are the pixel values of the domain block for which we wish to find an affine map that minimizes the above error This can be done by taking partial derivatives of the
View Full Document
Unlocking...