A Fast Fractal Image Compression Using The Normalized Variance

Fractal image coding suffers from the long search time of domain pool although it provides many properties including the high compression ratio. We find that the normalized variance of a block is independent of contrast, brightness. Using this observation, we introduce a self similar block searching method employing the d-dimensional nearest neighbor searching. This method takes Ο(log/N) time for searching the self similar domain blocks for each range block where N is the number of domain blocks. PSNR (Peak Signal Noise Ratio) of this method is similar to that of the full search method that requires Ο(N) time for each range block. Moreover, the image quality of this method is independent of the number of edges in the image.