Fractal image encoding is one of the famous lossy encoding techniques ascertain high compression ratio, higher PSNR and good quality of encoded image. It is the approach that uses self similarity property in natural image.The main drawback of fractal image encoding is time consumption in search of appropriate domain for each range of image blocks.There have been various researches carried out to overcome the limitation of fractal encoding and to speed up the encoder.The neighborhood search strategy used in spatial domain reduces the encoding time from linear time to logarithmic time.The proposed algorithm used k-nearest neighbor search to find the similar edge shaped range and domain blocks to be mapped on the basis of DCT lowest coefficients in horizontal and vertical directions and then using similarity measure; the virtual codebook was prepared to encode the image and then decoded the image using averaging of pixels of selected domains. The proposed approach explained in this book is compared with the existing method and this work gave high PSNR value, high compression ratio and reduced MSE computations with little decay in image quality which is acceptable.