High-Speed Implementations Of Fractal Image Compression For Low And High Resolution Images - Saad, Abdul Malik Haider Yusef (2018)
Fractal Image Compression (FIC) is a very popular coding technique that is used in image/video applications due to its simplicity and superior performance. The major drawback of FIC is that it is a time consuming algorithm, especially when a full search is attempted. Hence, it is very challenging to achieve a real-time operation especially when this algorithm is run on a general or graphic processor unit. Therefore, in this research new hardware implementations of FIC are proposed for accelerating the encoding process by means of parallelism and pipelining. Various approaches have been investigated for achieving high speed performance. The computational complexity of fractal operations are first investigated in order to select the minimum and efficient bit sizes that can provide similar or nearly similar encoding quality. This has resulted in a relatively new FIC hardware which is referred in this thesis as Design I. In this design, a full-search approach was adopted in order to enable reconstruction at highest possible quality. However, full-search scheme is not suitable for encoding larger images since the encoding time is increased dramatically when processing high-resolution images. This problem is solved in Design II which used a partial-search based scheme in order to achieve high-speed operation. This method exploits the inherently high degree of correlation between pixels in the neighbourhood areas in digital image to restrict the search space to those areas. By fixing these areas for each group of range blocks and partitioning an image in which each domain block contains four range blocks, enabled two matching operations be performed simultaneously. This reduced the memory access by half, thereby, doubling the speed by a factor of 2. This design was extended to encode RGB image, resulting in another new design referred to as Design III. In this design, the strong cross-correlation between the image components was exploited so that only the G component was encoded using the same approach as in Design II, while the R and B components were encoded by searchless-based scheme with direct mapping between overlapped blocks. All three designs were examined in terms of runtime, peak-signal-to-noise-ratio (PSNR), and compression rate. The experimental results of Design I when implemented in Altera Cyclone II FPGA, showed speedup of 3 times, on average, while the PSNR was not significantly affected. Empirical results demonstrated that this firmware is competitive when compared to other existing full-search hardware with PSNR averaging at 30 dB, 5.82 % compression rate and a runtime of 9.8 ms. On the other hand, Design II was synthesised on Altera Stratix IV FPGA and showed an ability to encode a 1024×1024 image at 395 MHz in 10.8 ms with PSNR averaging at 27 dB and compression rate of 34. These results suggest that the proposed approach enables colour images be encoded at approximately same speed as grayscale images. Also the proposed architectures have achieved better performance compared to the state-of-the-art designs, with speed averaging at 100, 92 and 83 fps for Design I, II and III respectively.