Một số phương pháp tạo ảnh fractal

TẠP CHÍ KHOA HỌC, Đại học Huế, Số 12, 2002
MỘT SỐ PHƯƠNG PHÁP TẠO ẢNH FRACTAL
Phạm Anh Phương, Trần Thanh Lương
Trường Đại học Khoa học, Đại học Huế
1. GIỚI THIỆU
	Hình học Fractal được chính thức biết đến vào năm 1975 qua bài báo nổi tiếng “Lý thuyết về các tập Fractal”, tiếp đó là cuốn chuyên khảo “Hình học Fractal của tự nhiên” của nhà toán học người Pháp Benoit B. Mandelbrot làm việc tại trung tâm nghiên cứu Thomas B. Waston của công ty IBM. Tuy chỉ mới ra đời nhưng hình học Fractal được ứng dụng trong rất nhiều lĩnh vực: tạo ảnh, nén ảnh... Ngoài ra nó còn được ứng dụng trong các ngành khoa học khác như: y học, sinh học, hoá học, vật lý, dự báo thời tiết, thiên văn học, kinh tế,... Trong bài báo này chúng tôi sẽ trình bày một số nội dung chính như sau: Cơ sở toán học cho việc tạo ảnh Fractal; giới thiệu 4 thuật toán tạo ảnh Fractal: thuật toán thời gian thoát, thuật toán tất định, thuật toán lặp ngẫu nhiên và thuật toán L-System; cuối cùng là một số kết quả được cài đặt và hướng nghiên cứu tiếp theo trong tương lai.
2. CƠ SỞ TOÁN HỌC CỦA HÌNH HỌC FRACTAL
Định nghĩa 1. Ánh xạ f : X ® X trên không gian mêtric (X,d) được gọi là ánh xạ co nếu tồn tại hằng số s, 0 £ s < 1 sao cho với mọi x, y Î X thì:
d(f(x),f(y)) £ s.d(x,y)
lúc đó s được gọi là hệ số co của f (hay độ co của f).
Định lý 1. [1] (Nguyên lý ánh xạ co hay nguyên lý điểm bất động)
Cho f : X ® X là ánh xạ co trên không gian mêtric đầy đủ (X,d), khi đó tồn tại duy nhất điểm xf Î X (gọi là điểm bất động) sao cho:
.
Định lý 2. [1] (Định lý cắt dán - Collage).
Giả sử f là ánh xạ co trên không gian mêtric đầy đủ (X,d) với hệ số co s và xf là điểm bất động của f, lúc đó ta có:
.
Định nghĩa 2. Cho wn : X ® X, n = 1, 2, ..., N là các ánh xạ co trên không gian mêtric đầy đủ (X,d) với các hệ số co tương ứng sn, n = 1, 2, ..., N. Một IFS trên (X,d) là tập các ánh xạ co wn, n = 1, 2, ..., N và ký hiệu:
	IFS = {X; w1, w2, ..., wN}.
Khi đó ánh xạ W: H(X) ® H(X) được định nghĩa bởi:
được gọi là toán tử Hutchinson.
Định lý 3. [1] Cho wn : X ® X, n = 1, 2, ..., N là các ánh xạ co với hệ số co tương ứng sn, n = 1, 2, ..., N. Khi đó toán tử Hutchinson W : H(X) ® H(X) là ánh xạ co với hệ số co , ánh xạ này có điểm bất động duy nhất A =. A được gọi là điểm hút (attractor) của IFS.
Định nghĩa 3. Cho không gian compact (X,d), wn, n = 1, 2, ..., N là các các ánh xạ co trên (X,d) với hệ số co tương ứng sn, n = 1, 2, ..., N. pn, 0 < pn < 1, , là xác suất gắn với wn, n = 1, 2, ...N. Một FIFS trên (X,d) là tập các ánh xạ co wn, n = 1, 2, ..., N liên kết với các xác suất pn, n = 1, 2, ..., N và ký hiệu:
	FIFS = {X; w1, w2, ..., wN; p1, p2, ..., pN}.
Định nghĩa 4. Cho (X,d) là không gian mêtric đầy đủ. Các tập Dn Ì X thoả mãn , Di Ç Dj = Æ, với i ¹ j, n = 1, 2, ...,N, i, j = 1, 2, ..., N. Tập các {Dn : n = 1, 2, ...,N} được gọi là một phân hoạch của X. Một PIFS là tập các ánh xạ co wn : Dn ® X, n = 1, 2, ..., N với hệ số co tương ứng là sn, n = 1, 2, ...,N và ký hiệu:
	PIFS = {X; D1, D2, ..., DN; w1, w2, ..., wn}
3. CÁC THUẬT TOÁN TẠO ẢNH FRACTAL
3.1 Thuật toán thời gian thoát (Escape Time Algorithm)
	Giả sử hệ động lực {R2, f}, f : R2 ® R2 liên kết với hệ hàm lặp IFS {X; w1,w2, ...,wN} có điểm hút là A (A được xem như một tập Fractal).
	Tập U Ì R2 là hình chữ nhật đóng chứa A. (a,b), (c,d) tương ứng là các đỉnh dưới-trái và đỉnh trên-phải của hình chữ nhật U.
	Gọi M là số điểm chia trong hình chữ nhật, số dương r được gọi là bán kính thoát của hình cầu có tâm là gốc toạ độ.
V = {(x,y) Î R2, x2 + y2 > r2}, U Ì V, A Ì U.
	Ta khảo sát quỹ đạo , trong đó:
Hình 1: Tập MandelBrot
	Tập điểm Ai,j = {fo1(xi,j), fo2(xi,j), fo3(xi,j), ..., foN(xi,j)} thuộc quỹ đạo của điểm xi,j Î U, i, j = 0, 1, 2, ..., M.
	Tổng số điểm trên quỹ đạo của xi,j được quy định tối đa là N (đây cũng chính là số lần lặp quy định).
	Nếu Ai,j Ç V = Æ khi n = N thì ta chuyển sang tính toán điểm i,j kế tiếp.
	Nếu Ai,j Ç V ¹ Æ thì tại vị trí (i,j) được tô màu với chỉ số pi,j = min{n : fon(xi,j) Î V}
Sau đó chuyển sang tính toán điểm (i,j) tiếp theo.
	Thuật toán thời gian thoát tìm các Fractal dựa trên sự rời rạc hoá điểm hút. Trong miền này ta chỉ vẽ những điểm có quỹ đạo không dần ra vô cùng bằng cách chọn một miền rộng hơn chứa miền ảnh Fractal. Thuật toán này có thể được áp dụng cho các hệ động lực dạng {R2;f}, {C;f} và {;f}. (Các kết quả xem thêm trong [1], [5], [7], [10]).
Ví dụ: tập Mandelbrot bao gồm những số phức c sao cho z2 + c hữu hạn với mọi lần lặp.
3.2. Thuật toán tất định (Deterministic Algorithm)
	Giả sử trong không gian Hausdorff (H(X),d) ta có hệ hàm lặp IFS = {X; w1, w2, ..., wN}.
	Chọn tập compact A0 bất kỳ con của X, sau đó tính các tập An = Won(A) theo công thức lặp sau:
	Bằng cách này chúng ta sẽ thu được một dãy các tập {An, n = 0, 1, 2, ...} Ì H(X). Lúc đó dãy sẽ hội tụ về một điểm hút A (tập Fractal) của IFS trong không gian Hausdorff: là ảnh Fractal cần tìm do hệ hàm lặp IFS sinh ra.
	Gọi MxN là kích thước hình chữ nhật khởi tạo ban đầu (tập A0).
	Khởi gán các giá trị của mảng t[i,j] chứa ảnh là biên của một hình chữ nhật MxN mà ảnh Fractal của nó sẽ nằm trong hình chữ nhật này. Mảng s[i,j] làm nhiệm vụ lưu trữ tạm thời các kết quả trung gian, sau đó nó sẽ chuyển các kết quả này cho mảng t[i,j].
	Gán các giá trị dữ liệu của hệ hàm lặp tương ứng vào các tham số a, b, c, d, e, f, ....
	Thực hiện lặp với các ánh xạ co của IFS. Sau mỗi lần lặp ta thu được một tập Ai mới, quá trình này tiếp tục cho đến khi thu được một hình Fractal đủ mịn đáp ứng được yêu cầu bài toán.
	Các ánh xạ IFS có thể được viết một cách đơn giản như sau:
trong đó: và 
	Ví dụ: Lá dương xỉ được sinh bởi 4 ánh xạ co.
Bảng 1: Bốn ánh xạ co sinh ra lá dương xỉ
w
a
b
c
d
e
F
p
1
0
0
0
0.16
0
0
0.01
2
0.2
-0.26
0.23
0.22
0
1.6
0.07
3
-0.15
0.28
0.26
0.24
0
0.44
0.07
4
0.85
0.04
-0.04
0.85
0
1.6
0.85
Hình 2: Lá dương xỉ
Các ánh xạ IFS là rất phong phú, các kết quả có thể xem trong [1], [5].
3.3. Thuật toán lặp ngẫu nhiên (Random Iterated Algorithm)
	Giả sử trong không gian Hausdorff (H(X),d) ta có hệ hàm lặp có gắn xác suất FIFS = {X; w1, w2, ..., wN; p1, p2, ...,pN}, x0 Î X và lấy xn một cách độc lập:
xn Î {w1(xn-1), w2(xn-1), ..., wN(xn-1)}, n = 1, 2, 3, ...
trong đó xác suất của biến cố xn = wi(xn-1) là pi. Ta thu được một dãy Ì X và dãy này hội tụ đến điểm bất động của FIFS.
 Ta thấy rằng với thuật toán tiền định thì không cần phải xét đến các xác suất pi gắn với wi, nhưng ở thuật toán lặp ngẫu nhiên này thì ta phải cần đến các xác suất pi đó. Các xác suất này đóng vai trò quan trọng trong việc tính ảnh trong điểm hút của FIFS. Chúng ta có thể lấy các giá trị pi xấp xỉ theo công thức sau:
.
	Nếu tại một giá trị i nào đó mà detAi = 0 (suy ra pi = 0) thì ta sẽ gán cho pi một giá trị dương rất nhỏ, chẳng hạn pi = 0.00001.
	Gọi MxN là hình chữ nhật mà trong đó nó chứa ảnh Fractal được sinh ra.
	Khởi gán các giá trị dữ liệu của hệ hàm lặp FIFS và các mảng tương ứng a, b, c, d, e, f, p, ....
	Khởi tạo số lần lặp cần thiết để tạo sinh ảnh.
	Trong thuật toán này có một điều lưu ý là cách tạo ra xác suất và lấy xác suất. Có nhiều cách tạo và lấy xác suất, chẳng hạn như dùng hàm random, dùng xác suất Gauss,....
	Thực hiện lặp với các ánh xạ co của FIFS theo xác suất được chọn bằng cách lấy xn độc lập qua wi(xn-1).
Sau đây là giải thuật cài đặt thuật toán IFS:
* Input:	Tập ánh xạ co và xác suất {w1,w2,...,wn , p1, p2,...,pn}, 
	 	Số lần lặp: N,
	Điểm xuất phát (x0,y0).
Hình 3: Cây Fractal được tạo ra bằng thuật toán lặp ngẫu nhiên
* Output: Ảnh Fractal.
* Method:
Procedure IFS(N);
Begin
	Khởi tạo {wi, pi};
	(x,y) := (x0,y0);
	For i:=1 To N Do
 Begin
	 	Chọn ánh xạ wk tương ứng với xác suất pk;
	 	(x,y) := wk(x,y);
	Draw(x,y);
 End;
End;
3.4. Thuật toán tạo ảnh bằng L-System
	Cho xâu ban đầu: Axiom , tập luật: Rule và góc quay: Angle.
	Sau n lần lặp thì ta có xâu kết quả: Result.
	Ví dụ:
	Axiom: F+F+F+F
	Rule: F --> F+F-F-FF+F+F-F
Axiom
Sau 1 lần lặp
	sau một lần lặp ta có:
	Result: F+F-F-FF+F+F-F + F+F-F-FF+F+F-F + F+F-F-FF+F+F-F + F+F-F-FF+F+F-F .
	Từ xâu kết quả Result, ta xây dựng qui tắc vẽ dựa trên tập các ký tự sau:
Ký tự
ý nghĩa 
F
Vẽ một đoạn thẳng
+
Quay trái một góc angle
-
Quay phải một góc angle
|
Đổi hướng (quay 1800)
[
Đưa trạng thái vẽ hiện thời vào STACK
]
Lấy trạng thái vẽ từ STACK ra
Hình 4: Một số ảnh được tạo ra bằng phương pháp L-System
4. KẾT LUẬN
	Qua bài báo này, chúng tôi đã trình bày cơ sở toán học cũng như giới thiệu một số thuật toán tạo ảnh Fractal thông qua lý thuyết hệ hàm lặp. Bên cạnh đó chúng tôi cũng đã cài đặt chương trình tạo ảnh Fractal bằng ngôn ngữ Delphi 5.0 chạy trên môi trường Windows. Chương trình tạo ra các hình ảnh tự nhiên khá đẹp (Xem hình 1, 2, 3, 4).
Trong thời gian tới, chúng tôi sẽ chú trọng đến việc cải tiến tốc độ tính toán, ước lượng các công thức để nâng cao tốc độ của các thuật toán. Đồng thời, chúng tôi cũng phát triển một chương trình hệ sinh ảnh Fractal trực quan ([3], [5]) phục vụ cho việc tạo sinh các ảnh Fractal được dễ dàng hơn. Tiếp tục nghiên cứu, tìm hiểu về lý thuyết cũng như các kỹ thuật tạo ảnh Fractal trong không gian ba chiều.
TÀI LIỆU THAM KHẢO
Barnsley M. F., Fractals Everywhere, Academic Press, Inc, 1988.
Falconer K. J., Fractal Geometry: Mathematical Foundations and Applications, John Wiley & Sons, Inc, 1990.
Nguyễn Xuân Huy, Nguyễn Xuân Hoài, Xây dựng chương trình thiết kế ảnh Fractal trực quan, Tạp chí tin học và điều khiển học, T.15, S.3, 1999, Tr 66-72.
Nguyễn Xuân Liêm, Giải tích hàm, Nhà xuất bản Giáo dục, Hà Nội 1994.
Trần Thanh Lương, Tìm hiểu một số phương pháp sinh ảnh Fractal, Luận văn Tốt nghiệp Đại học, chuyên ngành Công Nghệ Thông Tin, Trường Đại học Khoa học Huế, Hà Nội, 2001.
Massopust P. R., Fractal Functions, Fractal Surfaces, and Wavelets, Academic Press, Orlando, 1994.
Peitgen H. O., and Richter P. H., The Beauty of Fractals, Springer-Verlag, Inc, 1986.
Peitgen H. O., Jỹrgens H., Saupe D., Maletsky E., Perciante T., Fractals for Classroom: Strategic Activities Volume Three, Springer-Verlag, New York, Inc, 1999.
Rériaux J., Miettlinen K., Mäkëlä M. M., Taannaki P. N., Evolutionary Algorithms in Engineering and Computer Science, John Wiley & Sons, Ltd, 1999, Chaper 15.
Ngô Quốc Tạo, Cơ sở hình học Fractal và chương trình thử nghiệm Fractal, Viện Công Nghệ Thông Tin, Mã số: CS97-12, Hà Nội, 1997.
Z. Baharav, D. Malah, E. Karnin, Hierachical Interpretation of Fractal Image Coding and Its Application to Fast Decoding, In Intl, Conf, on Digital Signal Processing, Cyprus, July 1993.
TÓM TẮT
Hình học Fractal là một môn hình học được ứng dụng trong rất nhiều lĩnh vực, đặc biệt là ứng dụng trong việc tạo ảnh trên máy tính. Trong bài báo này, chúng tôi sẽ giới thiệu một số phương pháp tạo ảnh Fractal. Các kết quả đạt được cho những hình ảnh khá đẹp.
SOME METHODS CREATE FRATAL IMAGES
Phan Anh Phuong, Tran Thanh Luong
College of Sciences, Hue University
SUMMARY
 Fractal geometry is applied in many domains of science, especially in creating images on computer. In this paper, we introduce some methods that create Fractal images. The practical results gave us rather beautiful images.