Fractal image compression coding algorithm is a novel image compression technology; however, the long encoding time and unacceptable image reconstruction quality remain the primary obstacles in practical application. The purpose of this study is to improve the coding quality from the perspective of grey level transform and feature extraction. In this study, a novel orthogonal sparse fractal coding algorithm based on image texture feature is proposed. The authors define a normalised version as the new grey description feature of the image block so that two improved methods are scientifically combined in theory and algorithm. First, orthogonal sparse grey level transform based on sparse decomposition improves image reconstruction quality and decoding speed. Then, the similarity measure matrix, which stores the variance feature between range blocks and domain blocks, is used to reduce redundancies and encoding time. Simulation results show that the proposed algorithm in this study can obtain better image reconstruction quality and speed up encoding time significantly as compared to the conventional fractal coding schemes.