In this paper we proposed a new computationally efficient interpolation algorithm for natural images in which unknown pixels are divided into few bins. The categorization of these unknown pixels into bins is based upon the characteristics of the neighboring pixels. These characteristics are obtained by taking difference of two slopes which are in orthogonal direction and these slopes are calculated from a set of neighboring pixels. We used the Least-Squares (LS) based approach to find optimal predictors for pixels belonging to various slope bins. We also presented a simplified proposed algorithm in which we used bilinear interpolation algorithm instead of estimating LS based predictor for some bins and it results into further reduction in computational complexity without sacrificing the much performance. Our proposed algorithm gives better interpolation quality with significantly lower computational complexity as compared to recently reported interpolation algorithms. © 2011 IEEE.