Báo cáo nghiên cứu khoa học đề tài MỘT SỐ PHƯƠNG PHÁP TẠO ẢNH FRACTA

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...
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học đề tài " MỘT SỐ PHƯƠNG PHÁP TẠO ẢNH FRACTA " 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 31 Đị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: x f  f(x f )  lim f on (x 0 ), x 0  X . n  Đị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ó: 1 d(x, f(x)), x  X . d(x, x f )  1 s Đị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: 32 IFS = {X; w1, w2, ..., wN}. Khi đó ánh xạ W: H(X)  H(X) được định nghĩa bởi: N W(A)   w n (A) n 1 đượ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 s  max{s n } , ánh xạ này có điểm bất động duy nhất A 1 n  N N = W(A)   w n (A) . A được gọi là điểm hút (attractor) của IFS. n 1 Đị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, N p  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 n n 1 á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ả N mãn  D n  X , Di  Dj = , với i  j, n = 1, 2, ...,N, i, j = 1, 2, ..., N. Tập các n 0 33 {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 {f on (x i, j )}0 , trong đó: n 34 i(c  a) j(d  b)   x i, j   a  ,b  i, j  0, 1, 2, ... , M M  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. Hình 1: Tập MandelBrot 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ầ ...