Image registration is an essential step in many computer vision applications which demands high accuracy for significantly random and complex deformations. In medical image processing applications image registration is a basic preprocessing step to non-rigidly align images from different acquisition environments to an atlas image. We propose a novel non-rigid image registration method to get more reliable registration even under noisy conditions with manageable time complexity. The proposed method explores the the inherent multi-resolution capability of wavelets to perform nonrigid registration in a graph environment. The inherent time complexity of wavelet feature map calculation is avoided using Chebyshev Polynomial approximations for the wavelet operators. © 2018 ACM.