We propose an algorithm for image recovery where completely lost blocks in an image/video-frame are recovered using spatial information surrounding these blocks. Our primary application is on lost regions of pixels containing textures, edges and other image features that are not readily handled by prevalent recovery and error concealment algorithms. The proposed algorithm is based on the iterative application of a generic denoising algorithm and it does not necessitate any complex preconditioning, segmentation, or edge detection steps. Utilizing locally sparse linear transforms and overcomplete denoising, we obtain good PSNR performance in the recovery of such regions. In addition to results on image recovery, the paper provides further insights into the usefulness of popular transforms like wavelets, wavelet packets, discrete cosine transform (DCT) and complex wavelets in providing sparse image representations.