疊代函數系統 (Iterated Function Systems) 是用來表示碎形的架構。這樣的架構可以應用在二方面：繪圖物件的表示以及影像的壓縮。疊代函數系統在這二方面的應用都有一些問題有待解決。
對用來建構2D或3D繪圖物件模型上，我們指出二個主要的障礙，這二個障礙限制了碎形物件的發展。第一個問題是碎形物件是在哪裡？在畫一個碎形前，我們要先知道碎形所在的區域以決定影像的大小。然而，在以前這件事是用猜的。先隨便給一個影像的大小，如果畫出來的碎形太小再縮小影像的範圍；否則放大影像的範圍。因此，我們發展一個精準計算碎形界限的演算法(bounding box algorithm)。另外一個問題是如何決定物件的交集。當我們使用光跡追蹤法 (ray tracing) 來描繪立體場景時必須知道光跡和物件是否有交集，以及交點在哪裡。所以計算光和碎形的交點對碎形應用在3D繪圖是很重要的課題。我們設計另一個演算法來計算碎形物件和光跡的交點。這些問題的解決讓我們可以畫出任意解析度的平面碎形圖形以及在立體場景中描繪出碎形物件。
在另一方面，我們處理碎形影像壓縮的障礙。碎形壓縮最為人垢病的問題就是壓縮的速度很慢。碎形壓縮是將影像區分為定義域區塊 (domain blocks) 及對應域區塊(range blocks)，找其中相似的區塊對應。區塊的對應關係形成分割疊代函數系統(Partitioned Iterated Function System)。 這樣的過程需要經過大量的比對才能找到相似的區塊，因此會花費很長的時間。有鑑於此，在文獻上有許多加速比對的方法被提出。這些方法不外乎二類：其一是把區塊分類，只在某一類中找區塊對應。其二是快速搜尋，在找對應區塊的時候只找附近的區塊或符合某些限制的區塊。我們提出新的解決方案：在區塊間建立索引。我們稱這個技術為定義域索引法 (Domain Indexing)。這個方法和各種傳統的區塊分類法不同的地方在於我們並沒有實際去把影像區塊分類。把眾多的區塊分類本身便是一件耗時且耗記憶體的工作，而建索引只需很短的時間以及很少的記憶體。因此我們可以進行快速的壓縮工作。同樣地，我們也考慮在解壓縮影像的效率問題。在進行解壓縮前，先算出所需的定義域範圍以降低疊代的計算量。因此，我們的解壓縮速度也可以加快許多。

Fractals with Iterated Function Systems (IFSs) can be used in two applications: object modeling and image compression. However, there are problems on both of the applications to be solved.
For modeling 2D or 3D graphic objects, we point out two significant problems that deter the ongoing development of fractals. The first problem is where fractal objects are. It is necessary to compute the bounding extent of a fractal object before the rendering procedure. Unfortunately, the current bounding extents were determined by trial and error methods. We develop an algorithm to compute tight bounding boxes of fractal objects. The second problem is how to determine the intersections of rays and fractal objects. The intersection problem is a prerequisite of rendering 3D objects with ray tracing. We develop another algorithm, called stencil tracing, to compute the intersections of rays and fractal objects. Based on the solutions, we are able to draw 2D fractal pictures at any resolution and to render fractal objects in synthetic 3D scenes.
On the other hand, we tackle the obstacles of fractal image compression. Fractal image compression is notorious for its very slow encoding procedure. Thus we suggest a new coding scheme to accelerate the encoding procedure. In fractal image compression, an image is divided into overlapped domain blocks and non-overlapped range blocks. For each range block, the mapped domain block that is affine-similar to the range block is determined. The collection of the affine mappings forms a Partitioned Iterated Function System (PIFS). The time consuming problem comes from massive computation needed for searching a best match among a multitude of range-domain block pairs. In the past, people exploited block classification algorithms or fast greedy searching algorithms to solve the problem. We give another approach. We try to build indices onto the domain image. Only those range and domain blocks with same index keys are compared. The domain indexing technology is different from variant domain classification ones because we don’t cluster all of the domain blocks really. Thus we can accelerate the encoding procedure on a large scale. We consider the efficiency of the decoding procedure in our new scheme, too. We investigate the kernel of a partitioned iterated function system that must be computed iteratively. Thus it also benefits from the speed-up of decoding images.

中文摘要 i
Abstract iii
Acknowledgement v
1. Introduction 1
1.1 Objectives 1
1.2 Major Contributions 3
1.3 Organization of the Dissertation 4
2. Fractals with Iterated Function Systems 5
2.1 The History of Fractals 5
2.1.1 Classification of Fractals 7
2.2 Iterated Function Systems 8
2.3 Contraction Mapping Theorem 9
2.4 Collage Theorem 11
2.5 Partitioned Iterated Function Systems 12
3. Fractal Generation Algorithms 13
3.1 Fractal Generation Algorithms for Non-IFS fractals 13
3.1.1 Escape Time Algorithm 13
3.1.2 L-Systems 14
3.2 Classical Generation Algorithms with IFS 15
3.2.1 Deterministic Iteration Algorithm 16
3.2.2 Random Iteration Algorithm 17
3.3 The Inaccuracy Problem 18
3.4 Deterministic Recursive Algorithm 19
4. Bounding Boxes 21
4.1 Previous work 21
4.2 Compute Bounding Boxes for IFS Attractors 25
4.3 Existence of an Initial Box 27
4.4 A Dynamic Programming Algorithm 31
4.5 Experimental Results 34
4.6 Summary 35
5. Rendering Fractal Objects 36
5.1 Free-Zooming a Fractal 37
5.2 Stencil Tracing 38
5.2.1 Determine Whether a Pixel Belongs to an IFS Attractor 39
5.2.2 Inclusion within a Tracing Window 42
5.2.3 An Example for Rendering a Picture of the Sierpinski Triangle by Stencil Tracing 43
5.3 Resolution-Free Displays of 2D Fractals 46
5.4 Rendering 3D Fractal Objects 49
5.4.1 Proposed illumination Model 49
5.4.2 Area-Sampling 50
5.4.3 Stencil-Tracing for 3D Fractals 52
5.5 An Example of 3D Fractal Object Illumination 53
5.6 Summary 55
6. Fractal Image Compression 56
6.1 A Review of the Development of Fractal Image Compression 56
6.2 Fractal Transform Process 58
6.2.1 The Encoding Procedure 58
6.2.2 The Decoding Procedure 59
6.2.3 Segmentation 60
6.2.4 Distance Measure 61
6.3 Acceleration of the Encoding Procedure 61
6.3.1 Domain Indexing 63
6.3.2 A New Algorithm 67
6.4 Acceleration of the Decoding Procedure 69
6.4.1 The Computation of a PIFS Attractor 69
6.4.2 A New Decoder 70
6.5 Experimental Results 73
6.6 Summary 76
7. Conclusions and Discussions 77
7.1 Perspectives 78
A. IFS Codes and Pictures 80
B. Sample Program of Deterministic Recursive Algorithm 85
C. Sample Program of Bounding Box Computation 87
Bibliography 92

[1] K. T. Alligood, D. S. Sauer, and J. A. Yorke, Chaos : an introduction to dynamical systems, Springer-Verlag, New York, 1993.
[2] E. Angel, Interactive Computer Graphics: A top-down approach with OpenGL, Addison-Wesley, 1997.
[3] D. Ashlock and J. B. Golden, “Iterated function system fractals for the detection and display of dna reading frame”, in the Proceedings of the 2000 Congress on Evolutionary Computation, 2000.
[4] M. F. Barnsley and A. D. Sloan, “A Better Way to Compress Images,” Byte, pp.215-223, Jan. 1988.
[5] M. F. Barnsley and A. D. Sloan, “Methods and apparatus for image compression by Iterated Function System,” U.S. Patent No. 4,9411,193, 1990.
[6] M. F. Barnsley and A. D. Sloan, “Methods and apparatus for processing digital data,” U.S. Patent No. 5,065,447, 1990.
[7] M. F. Barnsley, Fractals Everywhere, 2nd ed., Academic, New York, 1993.
[8] M. F. Barnsley, L. P. Hurd, Fractal Image Compression, Wellesley, AK Peters, 1993.
[9] S. Bell, “Fractals, a fast, accurate and illuminating algorithm,” Image and Vision Computing, Vol. 13, No. 4, pp. 253-257, 1995.
[10] D. Canright, “Estimating the spatial extent of attractors of iterated function systems,” Computers and Graphics, Vol. 18, No. 2, pp. 231-238, 1994.
[11] G. Cherbit (Ed.), Fractals : non-integral dimensions and applications, John Wiley & Sons, England, 1991.
[12] A. Edalat, D. W.N. Sharp, and R. L.While, “An Upper Bound on the Area Occupied by a Fractal,” Proc. of the Conference on Acoustics, Speech, and Signal Processing ICASSP '95, Vol. 4, pp. 2443-2446, 1995.
[13] K. Falconer, Fractal geometry : mathematical foundations and applications, John Wiley & Sons, England, 1990.
[14] Y. Fisher (ed.), Fractal Image Compression Theory and Application to Digital Images, San Diego, Springer-Verlag, 1995.
[15] J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, Computer Graphics Principles and Practice, 2nd ed., Addison-Wesley, 1996.
[16] R. C. Gonzalez, and R. E. Woods, Digital Image Processing, Addison Wesley, New York, 1992.
[17] J. C. Hart, T. A., “DeFanti Efficient anti-aliased rendering of 3D linear fractals,” Computer Graphics, Vol. 25, No. 4, pp. 91-100, 1991.
[18] J. C. Hart , “The Object Instancing Paradigm for Linear Fractal Modeling,” Proc. of the Conference of Graphics Interface GI-92 , pp. 224-231, 1992.
[19] D. D. Hearn and M. P. Baker, Computer Graphics, 2nd ed., Prentice Hall, New Jersey, 1994.
[20] E. Jacquin, “A Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding,” Ph.D. thesis, Georgia Tech., Atlanta, GA, 1989.
[21] E. Jacquin, “Fractal Image Coding Based on a Theory of Iterated Contractive Image Transformations,” SPIE, Vol. 1360, Visual Communication and Image Processing, pp. 227-239, 1990.
[22] E. Jacquin, “A Novel Fractal Block-coding Technique for Digital Images,” Proc. ICASSP, Vol. 1, pp. 18-30, 1992.
[23] E. Jacquin, “Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations,” IEEE Trans. On Image Processing, Vol. 1, No.1, pp. 18-30, 1992.
[24] E. Jacquin, “Fractal Image Coding: A Review,” Proc. of the IEEE, No. 81, pp. 1451-1465, 1993.
[25] E. Jacquin, “An Introduction to Fractals and their Applications in Electrical Engineering,” Journal of the Franklin Institute, Vol. 331 B, No. 6, pp. 659-680, 1994.
[26] A. Kelley, “Layering Techniques in Fractal Art,” Computers and Graphics, Vol. 24, No.4, pp. 611-616, 2000.
[27] C. Kim, R. Kim and S. Lee, “Novel Fractal image Compression Method with Non-iterative Decoder,” Proc. of ICIP '95, Washington, D.C., 1995.
[28] K. Lee and W. K. Lee, “Fast Fractal Image Block Coding Based on Local Variance,” IEEE Trans. On Image Processing, vol. 7, no. 6, pp. 888-891, 1998.
[29] S. Lepsøy, G. E. Øien and T. A. Ramstad, “Attractor Image Compression with a fast non-iterative Decoding Algorithm,” Proc. of ICASSP '93, Vol. 5, pages 337-340, Jan. 1993.
[30] A. Lindenmayer, “Mathematical Models for Cellular Interactions in Development, Parts I and II,” J. Theor. Biol., No. 18, , pp. 280-315,1968.
[31] M. Majewski, “A Tutorial on The Realistic Visualization of 3D Sierpinski Fractals,” Computers and Graphics, 1998;22(1): 129-142.
[32] B. Mandelbrot, Fractals: Form, Chance, and Dimension, Freeman, San Francisco, CA, 1977.
[33] B. Mandelbrot, The Fractal Geometry of Nature, Freeman, San Francisco, CA, 1982.
[34] D. M. Monro, F. Dudbridge, “Rendering algorithms for deterministic fractals,” IEEE Computer Graphics and Applications, Vol. 15, No. 1, pp. 32-41, 1995.
[35] D. Oliver, FractalVision: Put Fractals to Work for You, Sams Publishing, Carmel, IN, 1992.
[36] E. Reusens, “Partitioning the Time Complexity Issue for Iterated Functions Systems Based Image Coding,” Proc. of VII EUSIPCO, Edinburgh, Sep. 1994.
[37] J. Rice , “Spatial bounding of self-affine iterated function system attractor sets,” Proc. of the Conference of Graphics Interface GI-96 , pp.107-115, 1996.
[38] P. Rojas, “A tutorial on efficient computer graphic representation of the mandelbrot set,” Computers and Graphics, Vo. 15, No. 1, pp. 91-100, 1991.
[39] D. Saupe, “Breaking in Time Complexity of Fractal Image Compression,” Technical Report 53, Institut f"ur Informatik, 1994.
[40] D. Saupe and R. Hamzaoui, “A Guided Tour of the Fractal Image Compression Literature,” Technical Report 53, Institut f"ur Informatik, 1994.
[41] D. Saupe, “Accelerating Fractal Image Compression by Multi-dimensional Nearest Neighbor Search,” Proc. Data Compression Conference Dcc’95, IEEE Computer Society Press, 1995.
[42] D. Saupe and R. Hamzaoui, “Complexity Reduction Methods for Fractal Image Compression,” I.M.A. Conf. Proc. On Image Processing; Mathematical Methods and Applications, J.M. Blackledge, Oxford University Press, 1996.
[43] D. Saupe and M. Ruhl, “Evolutionary Fractal Image Compression, “ in Proc. of IEEE Int. Conf. On Image Processing ICIP’96, IEEE Computer Society Press, 1996.
[44] R. Sedgewick, Algorithms, Addison-Wesley, 1988.
[45] R. Smith, “Plants, Fractals, and Formal Languages,” SIGGRAPH 84, pp. 1-10, 1984.
[46] J. C. Sprott, and C. A. Pickover, “Automatic generation of general quadratic map basins,” Computers and Graphics, Vol. 19, No. 2, pp. 309-313, 1995.
[47] R. T. Stevens, Advanced fractal programming in C, M&T Books, 1990.
[48] G. Vines, “Signal Modeling with Iterated Function Systems,” Ph.D. thesis, Georgia Tech., Atlanta, GA, 1989.
[49] T. Whitted, “An Improved Illumination Model for Shaded Displays,” CACM, vol. 23, no. 6, June, pp. 343-349, 1980.