Abstract: Finding the optimal algorithm between an efficient encoding process and the rate distortion is the main research in fractal image compression theory. A new method has been proposed based on the optimization of the Least-Square Error and the orthogonal projection. A large number of domain blocks can be eliminated in order to speed-up fractal image compression. Moreover, since the rate-distortion performance of most fractal image coders is not satisfactory, an efficient bit allocation algorithm to improve the rate distortion is also proposed. The implementation and comparison have been done with the feature extraction method to prove the efficiency of the proposed method.