31

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

32

Đị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 x

trên (X,d) là tập các ánh xạ co w
n
, n = 1, 2, , N và ký hiệu:

33

IFS = {X; w
1
, w
2
, , w
N
}.
Khi đó ánh xạ W: H(X)  H(X) được định nghĩa bởi:
(A)wW(A)
n
N
1n
 
được gọi là toán tử Hutchinson.
Định lý 3. [1] Cho w
n
: X  X, n = 1, 2, , N là các ánh xạ co với hệ số co
tương ứng s
n
, n = 1, 2, , N. Khi đó toán tử Hutchinson W : H(X)  H(X) là ánh
xạ co với hệ số co }{smaxs
n
Nn1 
 , ánh xạ này có điểm bất động duy nhất A

hiệu:
FIFS = {X; w
1
, w
2
, , w
N
; p
1
, p
2
, , p
N
}.
Định nghĩa 4. Cho (X,d) là không gian mêtric đầy đủ. Các tập D
n
 X thoả
mãn XD
n
N
0n


 , D
i
 D
j
= , với i  j, n = 1, 2, ,N, i, j = 1, 2, , N. Tập các

34

2
 R
2
liên kết với hệ hàm lặp IFS {X;
w
1
,w
2
, ,w
N
} có điểm hút là A (A được xem như một tập Fractal).
Tập U  R
2
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)  R
2
, x
2
+ y
2
> r
2
}, U  V, A  U.
Ta khảo sát quỹ đạo

0nji,
on

o2
(x
i,j
), f
o3
(x
i,j
), ,
f
oN
(x
i,j
)} thuộc quỹ đạo của điểm x
i,j
 U, i, j = 0, 1,
2, , M.
Tổng số điểm trên quỹ đạo của x
i,j
được quy định tối đa là N (đây cũng
chính là số lần lặp quy định).
Nếu A
i,j
 V =  khi n = N thì ta chuyển sang tính toán điểm i,j kế tiếp.
Nếu A
i,j
 V   thì tại vị trí (i,j) được tô màu với chỉ số p
i,j
= min{n :
f
on

N
}.
Chọn tập compact A
0
bất kỳ con của X, sau đó tính các tập A
n
= W
on
(A)
theo công thức lặp sau:
3, 2, 1,n ),(AwA
nj
N
1j
1n




Bằng cách này chúng ta sẽ thu được một dãy các tập {A
n
, n = 0, 1, 2, } 
H(X). Lúc đó dãy

0nn
}{A sẽ hội tụ về một điểm hút A (tập Fractal) của IFS trong
không gian Hausdorff: )(AWlimA
0
on
n 

txA
f
e
x
x
dc
ba
x
x
w 





















A
và









i
i
i
f
e
t

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

38

4 0.85 0.04 -0.04 0.85 0 1.6 0.85

Các ánh xạ IFS là rất phong phú, các kết quả có thể xem trong [1], [5].

N
(x
n-1
)}, n = 1, 2, 3,
trong đó xác suất của biến cố x
n
= w
i
(x
n-1
) là p
i
. Ta thu được một dãy

0nn
}{x  X và dãy này hội tụ đến điểm bất động của FIFS.

H
ì
nh 2:
L
á
d
ươ
ng x
ỉ39





.
Nếu tại một giá trị i nào đó mà detA
i
= 0 (suy ra p
i
= 0) thì ta sẽ gán cho p
i

một giá trị dương rất nhỏ, chẳng hạn p
i
= 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 x
n
độc lập qua w
i
(x
n-1
).


};
(x,y) := (x
0
,y
0
);
For i:=1 To N Do
Begin
Chọn ánh xạ w
k
tương ứng với xác suất p
k
;
H
ì
nh 3:
Cây Fractal được tạo
ra bằng thuật toán lặp ngẫu
nhi
ê
n41

(x,y) := w
k
(x,y);
Draw(x,y);
End;

[ Đưa trạng thái vẽ hiện thời vào STACK
] Lấy trạng thái vẽ từ STACK ra

44

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

4

Verlag, Inc, 1986.
8. 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.
9. 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.
10. 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.

47

11. 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.