臺灣博碩士論文加值系統

費時的計算過程一直以來是碎形影像壓縮方法所要面臨的重要的問題。雖然它擁有良好的壓縮率與圖像品質，但是時間的耗時問題卻使得碎形壓縮方法很少被應用實作。在本論文中，我們使用GPU上的CUDA架構，藉由使用大量的處理器(processors)與並行計算(parallel computing)的方式來改善碎形影像壓縮方式上的時間問題。我們提出可變動的區塊(variable block)這個想法去減少計算負擔與提高運算效率。此外我們也引用平均值和變異數的分類方法來減少搜尋比對範圍。並且在多次的比對過程中，逐步縮小變動區塊的大小來更進一步的減少計算負擔。在我們的研究成果中發現，在可接受的圖片失真上，在計算時間上有顯著的變化，特別在圖片大小越大時計算結果與執行時間會有更好的效率與實現。

The problem of time-consuming is always in fractal compression method. Fractal compression method that has a good compression rate and image quality is a powerful method, but the application is still used rarely. In this thesis, we use the NVIDIA GPU video card with CUDA architecture to realize fractal image compression. In CUDA architecture, by using of a large number of powerful processors and parallel compute in order to solve time-consuming problem. Propose an idea of variable block to further reduce the burden in computing and improve computing efficiently. In repeated comparison, gradually minimize the size of block in order to reduce the computational burden. In addition, we quote the mean and variance classification method to reduce range block searches the number of domain blocks. In ours results, under the acceptable picture distortion, we can find significant changes in time. And applied fractal calculation can show good performance in a larger image size.

致謝 i
中文摘要 ii
ABSTRACT iii
List of Tables v
List of Figures vi
1. Introduction 1
1.1 Background 1
1.2 Compute Unified Device Architecture (CUDA) 2
1.3 Thesis Organization 3
2. Related work 4
2.1 The Fractal encoding 4
2.2 Classified fractal encoding 7
2.3 The Fractal Image Compression Method in CUDA 8
3. Parallel Implementation and the variable range block on GPU 9
4. Results 14
5. Conclusion 22
6. References 23

[1] Michael Batty (1967), “How Long Is the Coast of Britain? Statistical Self-Similarity and Fractional Dimension”, Science, New Series, Vol. 156, No. 3775, pp. 636-638.
[2] M. F. Barnsley (1988), Fractal everywhere, academic press.
[3] H. Yamauchi, Y. Taleuchi, M. Imai (2001), “VLSI implementation of fractal image compression processor for moving pictures”, Proceedings of IEEE Euromicro Conference, pp. 400-409.
[4] J. Valantinas, N. Morkevicius, T. Zumbakis (2002), “Acceleration Compression Times in Block-Based Fractal Image Coding Procedures”, Proceeding of EGUK ’02 Proceeding of the 20th UK conference on Eurographics, pp. 83-88.
[5] H. Jinshu (2007), “Speeding up fractal Image compression Based on Local Extreme Points”, Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD ‘07), vol. 3, pp. 732-737.
[6] NVIDIA (2007), CUDA Programming Guide Version 1.1., NVIDIA Corporation: Santa Clara, California.
[7] Wu YG, Huang MZ, Wen YL (2003), “Fractal image compression with variance and mean”, Proc. IEEE ICME, Maryland, USA, pp. 353-6.
[8] A.E. Jacquin (1992), “Image coding based on a fractal theory of iterated contractive image transformations”, IEEE Trans. On Image Processing, vol. I, pp. 18-30.
[9] Chin-Feng Lin and Jin-Yuan Kuo,'A Fast Fractal Image Compression Method on GPUs', Computer Graphics Workshop 2012, Jul. 2012, CD-ROM, Taichung.