Quantum-Accelerated Fractal Image Compression: An Interdisciplinary Approach

Fractal image compression (FIC) is one of the most widely approved image compression approaches for its high compression ratio and quality of retrieved images. However, FIC suffers from high computational cost in searching local self-similarities in natural image. Although many papers aiming at speeding up FIC have been published, they use pre-processing tools or approximation methods. Reducing the intrinsic computational complexity of FIC is still an open problem. Since quantum mechanics based Grover´s quantum search algorithm (QSA) is able to achieve square-root speedup over classical algorithms in unsorted database searching, we propose an interdisciplinary approach by using Grover´s QSA to reduce the intrinsic computational complexity of FIC in this letter. In particular, both domain blocks and range blocks are represented as quantum states, then Grover´s QSA is employed to search the most similar domain block for each range block under the criterion of maximizing quantum fidelity between these two kinds of quantum states. Without sacrificing compression ratio, experimental results show that the execution time of the proposed method is 100 times shorter than that of the baseline FIC. Moreover, retrieved images from our proposal are also less distorted than those from other state-of-the-art FIC approaches.