Đề tài Tìm hiểu lý thuyết hình học Fractal và ứng dụng trong việc cài đặt một số đường, mặt Fractal phổ biến

ém so với ảnh ban đầu. Đây là trường hợp của các phương pháp nén mất thông tin, ví dụ chuẩn nén JPEG. Các nghiên cứu lý thuyết cho thấy, để đạt một tỷ lệ nén hiệu quả (kích thước dữ liệu nén giảm so với ban đầu ít nhất hàng trăm lần), phương pháp nén mất thông tin là bắt buột. Tuy nhiên một vấn đề đặt ra là làm thế nào có được một phương pháp nén kết hợp cả tính hiệu quả về tỷ lệ nén lẩn chất lượng ảnh so với ảnh ban đầu? Phương pháp nén ảnh fractal được phát triển gần đây bởi Iterated System đáp ứng được yêu cầu này. Như đã biết, với một ánh xạ co trên một không gian metric đầy đủ, luôn tồn tại 1 điểm bất động xr sao cho: xr=f(xr) Micheal F.Barnsley đã mở rộng kết quả này cho 1 họ các ánh xạ co F.Barnsley đã chứng minh được với một họ ánh xạ như vậy vẫn tồn tại 1 "điểm" bất động xr. Để ý rằng với một ánh xạ co, ta luôn tìm được điểm bất động của nó bằng cách lấy một giá trị khởi đầu rồi lặp lại nhiều lần ánh xạ đó trên các kết quả thu được ở mỗi lần lặp. Số lần lặp càng nhiều thì giá trị tìm được càng xấp xỉ chính xác giá trị của điểm bất động. Dựa vào nhận xét này, người ta đề nghị xem ảnh cần nén là "điểm bất động" của một họ ánh xạ co. Khi đó đối với mỗi ảnh chỉ cần lưu thông tin về họ ánh xạ thích hợp, điều này làm giảm đi rất nhiều dung lượng cần có để lưu trữ thông tin ảnh. Việc tìm ra các ánh xạ co thích hợp đã được thực hiện tự động hóa nhờ quá trình fractal một ảnh số hóa do công ty Iterated System đưa ra với sự tối ưu về thời gian thực hiện. Kết quả nén cho bởi quá trình này rất cao, có thể đạt đến tỷ lệ 10000: 1 hoặc cao hơn. Một ứng dụng thương mại cụ thể của kỷ thuật nén fractal là bộ bách khoa toàn thư multimmedia với tên gọi"Microsoft Encarta" được đưa ra vào 12-1992. Bộ bách khoa này bao gồm hơn 7 giờ âm thanh, 100 hoạt cảnh, 800 bản đồ màu cùng với 7000 ảnh chụp cây cối, hoa quả, con người, phong cảnh, động vật,… Tất cả được mã hóa dưới dạng các dữ liệu fractal và chỉ chiếm xấp xỉ 600 Mb trên 1 đĩa compact. Ngoài phương pháp nén fractal của Barnsley, còn có một phương pháp khác cũng đang được phát triển. Phương pháp đó do F.H.Preston, A.F.Lehar, R.J.Stevens đưa ra dựa trên tính chất của đường cong Hilbert. Ý tưởng cơ sở của phương pháp là sự biến đổi thông tin n chiều về thông tin một chiều với sai số cực tiểu. Anh cần nén có thể xem là một đối tượng ba chiều, trong đó hai chiều dùng để thể hiện vị trí điểm ảnh, chiều thứ ba thể hiện màu sắc của nó. Anh sẽ được quét theo thứ tự hình thành nên đường cong Hilbert chứ không theo hàng từ trái sang phải như thường lệ để đảm bảo các dữ liệu nén kế tiếp nhau đại diện cho các khối ảnh kế cạnh nhau về vị trí trong ảnh gốc. Trong quá trình quét như vậy, thông tin về màu sắc của mỗi điểm ảnh được ghi nhận lại. Kết qủa cần nén sẽ được chuyển thành một tập tin có kích thước nhỏ hơn rất nhiều vì chỉ gồm Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 8 các thông tin màu sắc. Phương pháp này thích hợp cho các ảnh có khối cùng tông màu lớn cũng như các ảnh dithering. c) Ứng dụng trong khoa học cơ bản Có thể nói cùng với lý thuyết topo, hình học fractal đã cung cấp cho khoa học một công cụ khảo sát tự nhiên vô cùng mạnh mẽ. Vật lý học và toán học thế kỷ XX đối đầu với sự xuất hiện của tính hỗn độn trong nhiều qúa trình có tính quy luật của tự nhiên. Từ sự đối đầu đó, trong những thập niên tiếp theo đã hình thành một lý thuyết mới chuyên nghiên cứu về các hệ phi tuyến, gọi là lý thuyết hỗn độn. Sự khảo sát các bài toán phi tuyến đòi hỏi rất nhiều công sức trong việc tính toán và thể hiện các quan sát một cách trực quan, do đó sự phát triển của lý thuyết này bị hạn chế rất nhiều. Chỉ gần đây với sự ra đời của lý thuyết fractal và sự hổ trợ đắc lực của máy tính, các nghiên cứu chi tiết về sự hỗn độn mới được đẩy mạnh. Vai trò của hình học fractal trong lĩnh vực này là thể hiện một cách trực quan các cư xử kỳ dị của các tiến trình được khảo sát, qua đó tìm ra được các đặc trưng hoặc các cấu trúc tương tự nhau trong các ngành khoa học khác nhau. Hình học fractal đã được áp dụng vào nghiên cứu lý thuyết từ tính, lý thuyết các phức chất trong hóa học, lý thuyết tái định chuẩn và phương trình Yang & Lee của vật lý, các nghiệm của các hệ phương trình phi tuyến được giải dựa trên phương pháp xấp xỉ liên tiếp của Newton trong giải tích số, … các kết qủa thu được giữ một vai trò rất quan trọng trong các lĩnh vực tương ứng. 3. Các kiến thức cơ sở của lý thuyết hình học fractal a) Độ đo fractal ¥= ¥==== <¥ > = "< Î= ¥ = = ® = ïî ï í ì þ ý ü î í ì haydöông,0 thöïc soámoät laø theå coù (A)sh thì (A)HD s hôïptröôøng Trong } (A)sh : s { sup } 0 (A)sh : s { inf (A)HD : khaùccaùch Noùi . A hôïptaäp cuûa Hausdorff chieàu soá laø goïi ñöôïc (A)HD trò Giaù (A)HD s khi (A)HD s khi0 (A)s h : cho sao (A)HD soámoät cuûa taïi toàn söï ñöôïc minh chöùng ñaõ Hausdorff . i , )idiam(U vaø A cuûa môû moät phuû laø } ... , 2U , 1U { , nR gian khoâng trong Euclide metric laø d vôùi , }iU yx,:y)d(x, { sup )idiam(U : ñoù trong s)idiam(U 1 i inf (A)s h :vôùi (A)sh 0 lim (A)sh : bôûiñònh xaùc ñöôïc (A)s hthì A taäp cuûa chieàu-s Hausdorff ño ñoä laø (A)shGoïi . vaø s döông thöïc soá caùc tröôùc Cho ε Σε εε ε Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 9 Định nghĩa này giữ một vai trò quan trọng trong lý thuyết hình học fractal hiện đại nhưng không có tính thực tiễn vì việc xác định số chiều theo định nghĩa này rất phức tạp ngay cả với trường hợp tập A rất đơn giản. Do đó, xuất phát từ định nghĩa này, Mandelbrot đã đưa ra khái niệm số chiều fractal tổng quát dễ xác định hơn với ba dạng đặc biệt áp dụng cho từng loại đối tượng ( tập A ) cụ thể. Sau đây chúng tôi sẽ trình bày các định nghĩa về các dạng đặc biệt đó, đồng thời chỉ ra mối liên hệ giữa chúng với định nghĩa số chiều của Hausdorff. SỐ CHIỀU TỰ ĐỒNG DẠNG( SỐ CHIỀU HAUSDORFF-BESICOVITCH ): Định nghĩa: Ví dụ: · Xét một hình vuông được chia thành 9 hình vuông nhỏ với tỷ lệ đồng dạng là 1/3. Khi đó số chiều tự đồng dạng của hình vuông ban đầu được xác định bởi: · Xét một khối lập phương được chia thành 27 khối lập phương nhỏ hơn với tỷ lệ đồng dạng 1/3. Ta có số chiều tự đồng dạng của khối lập phương được xác định bởi: Hai ví dụ trên cho thấy định nghĩa số chiều tự đồng dạng phù hợp với định nghĩa thông thường của hình học Euclide. SỐ CHIỀU COMPA: Số chiều xác định theo định nghĩa này được áp dụng cho các đường cong không phải là các đường cong tự đồng dạng hoàn toàn ( như các đường bờ biển, các con sông,… ), nhưng có thể sử dụng nhiều đơn vị khác nhau để xác định độ dài của chúng. Định nghĩa: . ñoù truùc caáu cuûa daïng ñoàng töï chieàu soá laø goïi ñöôïc sD ñoù Khi r 1 log N log sD = D 33 log 33 log 3 1 1 log 27 log s === D 23 log 23 log 3 1 1 log 9 log s === Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 10 Xét một đường cong không tự đồng dạng . Biểu diễn số đo của đường cong trên hệ toạ độ log / log với: Ví dụ: Xét đường cong 3/2 được xây dựng theo kỹ thuật initiator/generator chỉ ra bởi hình vẽ sau: SỐ CHIỀU BOX-COUNTING: Số chiều xác định theo định nghĩa này được áp dụng cho các đường cong fractal không thể xác định số chiều theo 2 cách vừa trình bày. Cách tính số chiều này có thể áp dụng cho mọi cấu trúc trong mặt phẳng và mở rộng cho các cấu trúc trong không gian. Định nghĩa: Xét một cấu trúc fractal bất kỳ. Lần lượt đặt cấu trúc này lên một dãy các lưới có kích thước ô lưới s giảm liên tiếp theo tỉ lệ 1/2. Gọi N(s) là số các ô lưới có kích thước s có chứa một phần cấu trúc. Ta xây dựng hệ tọa độ log/log như sau: generator initiator generator d lcD : bôûiñònh xaùc ñöôïccD compa chieàu soá ñoù Khi . do töï soá heälaø b, b s 1 log . d ulog : heäquan coù Ta . tieåu cöïc phöông bình phaùp phöôngtreân döïa ñöôïc ño utrò giaù caùc xæ xaáp ñeå duøng qui hoàithaúng ñöôøng cuûa goùc soá heälaø d - += += Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 11 b) Hệ hàm lặp IFS KHÔNG GIAN ẢNH HAUSDORFF: Định nghĩa 1: Khoảng cách từ một điểm x X đến một tập B H(X) được xác định bởi: Định nghĩa 2: Khoảng cách từ một tập A H(X) đến một tập B H(X) được xác định bởi: Định nghĩa 3: Khoảng cách Hausdorff giữa hai điểm A và B H(X) được xác định bởi: Với các định nghĩa trên ta có định lý: Định lý về sự tồn tại của các IFS Fractal: . cho ñaõõ fractal truùc caáu cuûa counting- boxchieàu soá laø goïi ñöôïc vaäy nhö ñònh xaùc BD )k-N(2 )1) k(- N(2 2logk22log 1 k22log )k-N(22log-) 1)(k- N(22log BD : coù ta ñoù Khi . ñoä toïa heäcuûa N(s)) , (s ñieåm caùc haïn höõutaäp vôùi ñoái qui hoàithaúng ñöôøng cuûa goùc soá heälaø BD - . (s)) (N2log löôïng ñaïi cuûa trò giaù thò bieåutung Truïc - . ) s 1(2log löôïng ñaïi cuûa trò giaù thò bieåu hoaønhTruïc - + = -+ + = : sau nghóa ñònh caùc coù Ta . Xcuûa roãngaùccompact kh con taäp caùc gian khoânglaø H(X) hieäuKyù . Euclide metric laø d vaø 2R baèng haïngiôùi ñöôïc Xñaây ÔÛ . ñuû ñaày metric gian gmoät khoân laø d) X,( söû Giaû { }B y : y)d(x, min B)d(x, Î= { }A x : B)d(x, max B)d(x, Î= { }A x : B)d(x, max B)d(x, Î= x} veà tuï hoäi}nAn{x Cauchy daõymoät : X {x A : sau nhö taû ñaëc ñöôïc theå coù A . H(X) thuoäc cuõng nA0 limA : bôûiñònh xaùc A hôïptaäp thì Cauchy daõymoät thaønh laäp ... 1,2, n vôùi H(X) nA neáu nöõa Hôn . ñuû ñaày metric gian gmoät khoân laø h), (H(X) coù Ta Î$Î= ¥® = = Î Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 12 do nhöng , S xñieåm moät veà tuï hoäi} nN {x con daõymoät taïi toàn neân compact S Vì . S trongñieåm haïnvoâ daõymoät laø cuõng }n{x ñoù Khi . w(S) cuûañieåm haïnvoâ daõymoät laø } )nw(x ny { Xeùt .compact w(S) minh chöùng Ta . roãng khaùctaäpmoät laø } S x : w(x) { w(S) : coù ta ñoù Khi . Xcuûa roãngaùccompact kh con taäpmoät laø S söû Giaû Î Ù = Î= ÁNH XẠ CO TRÊN KHÔNG GIAN HAUSDORFF: Bổ đề 1: Giả sử w: X ' X là một ánh xạ co liên tục trên không gian metric (X,d). Khi đó w liên tục. Chứng minh: Cho s > 0. Gọi s là hệ số co của w. Khi đó: d(w(x) , w(y)) s.d(x,y) < khi và chỉ khi: d(x,y) < = / s Từ đó suy ra điều phải chứng minh Bổ đề 2: Giả sử w: X ' X là một ánh xạ liên tục trên không gian metric(X,d). Khi đó w ánh xạ không gian H(X) lên chính nó. Chứng minh: Bổ đề 3 sau đây chỉ ra cách tạo một ánh xạ co trên không gian metric (H(X),h) dựa trên một ánh xạ co trên (X,d): Bổ đề 3 : Giả sử w:X ' X là một ánh xạ có trên không gian metric (X,d) với hệ số co s. Khi đó ánh xạ w: H(X) ' H(X) được xác định bởi: w(B)={w(x): x B }, với B thuộc H(X) cũng là một ánh xạ co trên (H(X), h(d)) với hệ số co s. minh. chöùng ñöôïc ñeà Boå .compact w(S) Vaäy . w(S)y veà tuï hoäi}ny { cuûa con daõymoät laø } ) nN f(x nN y { ñöôïc rasuy w cuûa tuïc lieân tính Î Ù = Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 13 : bôûiH(X) H(X) : Wñònh Xaùc. N , ... 1,2, n,ns öùngtöông co soá heäcaùc vôùi h), (H(X) treân co xaï aùnh caùc laø } n{w hieäuKyù ®= Chứng minh: Từ bổ đề 1 suy ra w: X ' X liên tục. Do đó theo bổ đề 2, w ánh xạ H(X) lên chính nó. Bây giờ xét B, C thuộc H(X) Ta có: d(w(B), w(C)) = max { min { d(w(x) , w(y)): y C}: x B} <= max { min{ s.d(x,y): y C }: x B} = s.d(B,C) Một cách tương tự: d(w(C), w(B)) s.d(C,B) Do đó: h(w(B), w(C)) = max { d(w(B), w(C)), d(w(C), w(B))} <= s.max { d(B,C), d(C,B)} = s.h(B,C) Từ đó suy ra điều phải chứng minh. Bổ đề 4 sau đây cung cấp mộc cách thức cơ bản để nối kết các ánh xạ co trên (H(X), h) thành các ánh xạ co mới trên (H(X), h) Bổ đề 4 : Chứng minh: Kết quả trên được chứng minh bằng qui nạp. Với N = 2: Xét B, C H(X).Ta có: Vậy W là ánh xạ co với N = 2. Giả sử khẳng định đúng với N= k. Ta chứng minh khẳng định đúng với N = k + 1. Thật vậy , ta có: .ns Nn 1 max s co soá heävôùi co xaï aùnh laø Wñoù Khi . H(X) B vôùi (B)nw N 1n W(B) ££ =Î = È= C)s.h(B, C)}.h(B,2s , C).h(B,1s { max (C))}2w , (B)2 h(w, (C))1w , (B)1 h(w{ max (C)) 2w (C)1w , (B) 2w (B)1 h(w W(C)), h(W(B) £ £ £ ÈÈ= Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 14 Vậy W là ánh xạ co với N = k + 1. Do đó theo nguyên lý qui nạp bổ đề 4 được chứng minh xong. CÁC HỆ HÀM LẶP IFS ( ITERATED FUNCTION SYSTEM ): Định nghĩa 1: Định lý sau tóm tắt các kết quả chính của một IFS : Định lý IFS : Định nghĩa 2 : Điểm bất động A H(X) mô tả trong định lý IFS được gọi là hấp tử của IFS đó. ns 1kn 1 max)1ks,Tmax(ss co soá heävôùi H(X) treân co xaï aùnh laø Wcoù cuõng ta , 2 N vôùi naïp quithuyeát giaû do nhöng (B)1kwT(B) W(B) :vieát theå coù Vaäy .ns kn 1 max Ts co soá heävôùi H(X) treân co xaï aùnhmoät laø T coù ta naïp quithuyeát giaû do thì nw k 1n TÑaët (B)1kw(B)nw k 1n (B)nw 1k 1n W(B) +££ =+= = +È= ££ = = È= +È= È= + = È= ÷ ÷ ø ö ç ç è æ ns Nn 1 maxs co soá heävaø N}, ... 1,2,n,nw{X; bôûi hieäu kyùñöôïc IFSMoät . laëp haøm heätöøcuïm cho thay IFS hieäu kyùTa . N, ... 1,2,n,ns öùngtöông co soá heävôùi nw co xaï aùnh caùc haïnhöõu moät boä vaø d)(X, ñuû ñaày metric gian gmoät khoângoàm laëp haøm Moät heä ££ == = . H(X) B baát kyøvôùi (B)n W n lim A bôûitröôùc cho ñöôïc vaø (A)nw N 1n W(A)A : vôùi H(X) A ñoäng ñieåm baátmoät nhaát duy coù naøy xaï AÙnh H(X) CB, , C)B, s.h( W(C)), h(W(B) : laø töùc , s co soá heävôùi h(d)), (H(X) ñuû ñaày metric gian khoângtreân co xaï aùnhmoät laø H(X) B ñoù trong (B)nw N 1n W(B) : bôûiñònh xaùc H(X) H(X) : Wñoåi bieán pheùpñoù Khi . s co soá heävôùi N}, ... 1,2,n,nw{X; IFSmoät Xeùt Î ¥® = = È== Î Î"£ Î = È= ® = Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 15 II. MỘT SỐ HỌ ĐƯỜNG CƠ BẢN Trong phần này chúng ta sẽ tìm hiểu một số đường cơ bản được phát sinh từ các đoạn thẳng với kỹ thuật đệ quy initiator /generator. Về mặt lý thuyết thì đây chính là bước khởi đầu để tìm hiểu các lý thuyết fractal khác phức tạp hơn. 1. Họ đường Vonkock Các hình này có số chiều tự động dạng, số chiều fractal và số chiều Hausdorff-Besicovitch bằng nhau.Số chiều được tính theo công thức sau: Trong đó: N:là số đọan thẳng. R:là số chiều dài của mỗi đoạn. Chúng ta bắt đầu bằng một initiator, nó có thể là một đoạn thẳng hay một đa giác. Mỗi cạnh của initiator được thay thế bởi một generator, mà là tập liên thông của các đoạn thẳng tạo nên bằng cách đi từ điểm bắt đầu đến điểm cuối của đường thay thế (Thông thường các điểm của generator là một lưới vuông hay một lưới tạo bởi các tam giác đều). Sau đó mỗi đoạn thẳng của hình mới được thay thế bởi phiên bản nhỏ hơn của generator. Quá trình này tiếp tục không xác định được. Sau đây là một số đường Von Kock quan trọng. ĐƯỜNG HOA TUYẾT VON KOCK_SNOWFLAKE § Mỗi đoạn thẳng được thay thế bằng một generator như sau: § Số chiều fractal là : § Một số hình ảnh của đường (Bậc 2) (Bậc 3 ) ÷ ø ö ç è æ = R ND 1log )log( 2618,1 3log 4log 1log )log( »== ÷ ø ö ç è æ R ND Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 16 ĐƯỜNG VON KOCK_GOSPER § Mỗi đoạn thẳng được thay thế bằng một generator như sau: § Số chiều fractal là : § Một số hình ảnh của đường (Bậc 1) (Bậc 2) ĐƯỜNG VON KOCK BẬC HAI 3-ĐOẠN (Tương tự cho các đường có số đoạn lớn hơn) § Mỗi đoạn thẳng được thay thế bằng một generator như sau: § Số chiều fractal là : 1291.1 7log 3log »=D 3652.1 5log 3log »=D Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 17 § Một số hình ảnh của đường (Bậc 3) (Bậc 5) ĐƯỜNG VON KOCK BẬC HAI PHỨC TẠP § Mỗi đoạn thẳng được thay thế bằng một generator như sau: § Số chiều fractal là : Ta có : Do đó § Một số hình ảnh của đường (Bậc 1) (Bậc 2) 1. =å DMR 238361.1 1 9 35 3 16 »Þ =÷÷ ø ö çç è æ +÷ ø ö ç è æ D DD Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 18 2. Họ đường Peano Trong phần này, chúng ta xét các đường có số chiều fractal bằng 2. Chúng được gọi là các đường Peano vì đường đầu tiên trong họ đường này được khám phá bởi Guiseppe Peano vào năm 1900. Do số chiều fractal là 2 nên các đường này phải lấp đầy hoàn toàn mặt phẳng. Điều này dẫn đến sự tự giao nhau của chúng tại nhiều điểm trong mặt phẳng. Sau đây là một số đường đặc biệt của họ này. ĐƯỜNG PEANO ĐƠN GIẢN § Mỗi đoạn thẳng được thay thế bằng một generator như sau: § Số chiều fractal là : § Một số hình ảnh của đường (Bậc 1) (Bậc 3) ĐƯỜNG PEANO CẢI TIẾN § Mỗi đoạn thẳng được thay thế bằng một generator như sau: § Vì generator sử dụng lần đệ quy cuối cùng có độ dài ngắn hơn so với đường Peano nguyên thủy, ta có số chiều fractal D nhỏ hơn 2. Khi số lần đệ quy tăng lên, số chiều fractal sẽ thay đổi và tiến về 2. § Một số hình ảnh của đường: 2 3log 9log =Þ= DD Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 19 (Bậc 2) ĐƯỜNG CESARO TRIANGLE § Mỗi đoạn thẳng được thay thế bằng một generator như sau: § Số chiều fractal là : § Một số hình ảnh của đường (Bậc 5) ĐƯỜNG PEANO BẬC HAI 7-ĐOẠN § Mỗi đoạn thẳng được thay thế bằng một generator như sau: 2 2log 2log =Þ= DD Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 20 § Số chiều fractal là : § Một số hình ảnh của đường (Bậc 1) (Bậc 2) 3. Đường Sierpinski Đường Sierpinski được trình bày sau đây là một đường cong rất đặc biệt, bởi vì có rất nhiều cách phát sinh ra nó với các khởi động ban đầu hoàn toàn khác nhau nhưng lại kết thúc ở việc sinh ra một loại đường cong duy nhất. Chúng ta đã quen với phương pháp đầu tiên để phát sinh ra tam giác Sierpinski bằng cách sử dụng kỹ thuật initiator/generator được mô tả ở các phần trước. Đối với đường này, initiator là một đoạn thẳng. Generator đối với đường cong này và các đường được sinh ra ở mức 2 và 3 được minh họa như sau: Generator của tam giác Sierpinski Mức 2 Mức 3 21 3 3 3 16 =Þ=÷÷ ø ö çç è æ +÷ ø ö ç è æ* D DD Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 21 Và đây là đường Sierpinski ở mức 4 và 8: Mức 4 Mức 8 Như vậy là chúng ta đã khảo sát qua được gần hết các họ đường fractal đơn giản được phát sinh dựa trên kĩ thuật đệ quy initiator/generator. Trong phần kế ta sẽ khảo sát các tập phức tạp hơn mà việc phát sinh nó chủ yếu dựa trên các hệ hàm lặp IFS. Bạn sẽ được khám phá những tính chất đặc biệt, kỳ lạ cũng như vẻ đẹp diệu kỳ mà những tập này mang đến. Chắc chắn bạn sẽ gặp những bất ngờ thú vị khi khảo sát phần kế tiếp. Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 22 III. CÁC TẬP FRACTAL PHỔ BIẾN 1. Tập Maldelbrot Một trong số các tập kì ảo nhất mà tôi muốn giới thiệu đến các bạn trước tiên đó là tập Maldelbrot. Nói là kỳ ảo có lẽ do lý do chính là trước năm 1979 nó vẫn còn là ẩn số đối với các nhà khoa học máy tính. Người ta chỉ biết đến nó đơn thuần qua một hàm lặp rất đơn giản nhưng lại không thể quan sát được cụ thể hình dạng của nó. Chỉ đến năm 1979, Maldelbrot mới thành công trong việc quan sát dãy này với sự hỗ trợ của máy tính điện tử. Kết quả mà ông nhận được là một trong những cấu trúc fractal phức tạp và đẹp đẽ nhất. Để ghi nhớ công lao của tác giả, tập này đã được đặt tên Maldelbrot và cũng từ đây Maldelbrot đã khai sinh ra một lý thuyết mới đó là lý thuyết hình học fractal. a) Tìm hiểu vấn đề Trong nhiều thập niên của thế kỷ XX, các nhà toán học đã để tâm nghiên cứu đến một loại biểu thức phức tạp xác định bởi: zn+1 = zn2 +c , trong đó ziЄC, "i ЄN & cЄ C (1) Để đơn giản hóa vấn đề, trước hết ta xét trường hợp c = 0 và zo Є R. khi đó có 3 trường hợp sau: z0 =1 : khi đó zn =1, n > = 1. Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 23 z0 <1 : khi đó zn à0 khi n à∞ z0 > 1 : khi đó znà∞ khi n à∞ Ở đây tốc độ tiến đến 0 hay tiến đến ∞ của dãy (zn) được quyết định bởi giá trị ban đầu z0 của dãy. Trong trường hợp z0 < 1, giá trị z0 càng nhỏ thì dãy (zn) tiến đến 0 càng nhanh. Ngược lại khi z0>1, giá trị z0 càng lớn thì dãy (zn) càng tiến nhanh ra ∞ b) Công thức toán học Ký hiệu zn =( xn , yn), c=(p,q), trong đó: xn = Re(zn), p = Re(c), yn =Im(zn), q = Im(c), ∀n >= 0 thì hệ thức truy hồi xác định ở (1) có thể được viết lại theo dạng đơn giản hơn như sau: xn+1 = xn2 - yn2 + p yn+1 = 2xnyn + q Ngoài ra khi khảo sát dãy (zn) ta tìm được tính chất sau: Tính chất về sự hội tụ của dãy(zn): · Nếu tồn tại k Є N sao cho | zk | > 2 thì dãy (zn) hội tụ đến vô cực · Nếu tồn tại k Є N sao cho | zt | < 2, t : k <= t <= l, với l là hằng số hữu hạn thì cũng có | zn | = k. (Ký hiệu | z| chỉ modul của số phức z) c) Cài đặt Thuật toán gồm các bước sau: Bước 1: Xuất phát với một giá trị khởi đầu c = (p,q). Bước 2: Kiểm tra c thuộc lớp 1 hay lớp 2. Bước 3: Nếu c thuộc lớp 1 thì tô điểm ảnh tương ứng với c trên màn hình bằng màu đen, ngược lại tô điểm ảnh này bởi màu tương ứng xác định từ kỹ thuật tô xoay vòng. Bước 4: Chọn một giá trị c mới và trở lại bước 1 cho đến khi quét hết toàn bộ giá trị c cần khảo sát (đôi khi chúng ta không cần khảo sát toàn bộ mà chỉ khảo sát một miền con được yêu cầu của mặt phẳng phức). Khi đó thuật toán kết thúc. Bây giờ nếu ký hiệu: · Max_Iterations là số lần lặp tối đa cần có để kiểm tra một giá trị c thuộc lớp 1 hay lớp 2 (chính là giá trị l được đề cập trong định nghĩa của lớp 1). · Count là số lần lặp đã thực hiện (giá trị này tương ứng với một ngưỡng tiến ra vô hạn k được nêu ra trong định nghĩa lớp 2). Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 24 · Miền con của mặt phẳng phức cần khảo sát là một cửa sổ hình chữ nhật được đặt tả bởi tọa độ góc trái bên dưới (Xmin , Ymin) và tọa độ góc phải trên (Xmax , Ymax) (theo hệ trục tọa độ thông thường) Khi đó mối liên hệ giữa hệ trục tọa độ phức thực tế với hệ tọa độ nguyên trên màn hình máy tính được x thể hiện bởi hình dưới đây: q (0,0) Col (Xmax,Ymax) Thể hiện trên màn hình (Max_col,Max_row) (Xmin,Ymin) p Row Vùng khảo sát là 1 miền con của Hệ tọa độ nguyên trên máy mặt phẳng phức biểu diễn giá trị c tính với chiều dương ngược chiều thực tế. Theo hình này, điểm bắt đầu (0,0) trên màn hình máy tính sẽ tương ứng với giá trị c = (Xmin ,Ymax), điểm kết thúc (Max_Col,Max_Row), trong đó Max_Col x Max_Row thể hiện độ phân giải của mode đồ họa hiện thời của màn hình (ví dụ với mode VGA 16 màu ta có Max_Col=604, Max_Row = 480), sẽ tương ứng với điểm c = (Xmax , Ymin). Do đó nếu ký hiệu: · Δp làlượng gia tăng theo trục thực của giá trị p ứng với mỗi cột trên màn hình. · Δq là lượng là lượng gia tăng theo trục ảo của giá trị q ứng với mỗi hàng trên màn hình thì: Khi đó một số phức c = (p,q) ứng với một điểm ảnh có tọa độ màn hình là (Col,Row) sẽ được xác định bởi: p=Xmin + Col.Δp q = Ymax - Row.Δq Có thể kiểm tra là khi Col,Row biến thiên theo chiều tăng đến các giá trị tương ứng Max_Col , Max_Row , chúng ta cũng có p biến thiên từ Xmin đến Xmax và q biến ColMax XX p _ minmax -=D RowMax YYq _ minmax -=D Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên Phạm Trọng Tôn – Nguyễn Minh Đức 25 thiên từ Ymax xuống Ymin, đúng như yêu cầu về quan hệ giữa hệ tọa độ phức sử dụng trong toán học với hệ tọa độ hiển thị của màn hình đã được nêu ra trong hình trên. Việc kiểm tra c thuộc lớp 1 hay 2 được viết dưới dạng: if(Count > Max_Iterations)&(Modul(Zcount)<2)) c thuộc lớp 1 if(Count 2)) c thuộc lớp 2 Đồng thời màu tô cho một điểm c=(p,q) thuộc lớp 2 được tính toán theo công thức: Màu tô (p,q) = Count(p,q) mod Max_Colors Với: · Màu tô (p,q) : số hiệu màu gán cho điểm ảnh tương ứng với giá trị (p,q) · Count(p,q) : ngưỡng tiến ra vô hạn của dãy (zn) tương ứng với (p,q). · Max_Colors : số lượng màu tối đa có trong palette màu đang được sử dụng. Trong thuật toán này, để thể hiện một cách chi tiết, chúng ta quét các giá trị c trong cửa sổ giới hạn bởi (Xmin , Ymin) và (Xmax , Ymax) theo thứ tự từ trên xuống dưới và từ trái sang phải, tức là ứng với mỗi c