Abstract: Fractal image coding is an efficient image compression technique which is based on the local self-similarities within real world images.The main drawback of this technique is that，for each range block，searching out the best-matched domain block is extremely time consuming.By an inequality linking the root-mean-square and mean deviation，the proposed algorithm sets up a kick-out condition based on the mean deviation to avoid the excessive search，in which the search process might be early terminated，and thus remaining domain blocks could be discarded，so its runtime is significantly shortened.Computer simulations on 3 test images with different complexities demonstrate that the proposed scheme could averagely achieve the speed-up of 60 times as the baseline fractal algorithm with full search，while it gives an insignificant degradation in the subjective quality of the decoded image.

摘要： 分形图像编码是一种基于自然图像局部自相似性的有效压缩技术。这项技术的主要缺点是花费在寻找range块的最佳匹配domain块上的时间太长。根据一个联系均方根和平均偏差的不等式，在编码过程中，利用平均偏差来设置剔除条件，剔除与range块不太可能匹配的domain块，以提早结束搜索过程，避免全搜索，从而减少编码过程的时间。计算机仿真显示，对3幅复杂性不同的测试图像，在影响解码图像主观质量很小的情况下，与基本分形图像编码算法相比，该文方案的编码速度平均加快60多倍。