Đề 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

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN …:: dc ::… BÁO CÁO ĐỀ 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 Giảng viên hướng dẫn: Th.s Bùi Tiến Lên Sinh viên thực hiện: Phạm Trọng Tôn (0012181) Nguyễn Minh Đức (0012147) - TP HCM 4/2003 - “Chúng em xin chân thành cảm ơn Thạc sĩ Bùi Tiến Lên đã tin tưởng và giao chúng em thực hiện đề tài này. Cảm ơn tới những người thân trong gia đình, những người bạn đã là chỗ dựa tinh thần trong suốt thời gian thực hiện đề tài.” Tìm hiều lý thuyết hình học Fractal – GVHD Thạc sĩ Bùi Tiến Lên MỤC LỤC I. TỔNG QUAN VỀ HÌNH HỌC FRACTAL.................................................................................... 4 1. Sự ra đời và phát triển lý thuyết về hình học fractal................................................................ 5 2. Ứng dụng của hình học fractal................................................................................................. 6 a) Ứng dụng trong vấn đề tạo ảnh bằng máy tính ................................................................... 6 b) Công nghệ nén ảnh fractal................................................................................................... 6 c) Ứng dụng trong khoa học cơ bản ........................................................................................ 8 3. Các kiến thức cơ sở của lý thuyết hình học fractal .................................................................. 8 a) Độ đo fractal ........................................................................................................................ 8 b) Hệ hàm lặp IFS .................................................................................................................. 11 II. MỘT SỐ HỌ ĐƯỜNG CƠ BẢN .................................................................................................. 15 1. Họ đường Vonkock................................................................................................................ 15 2. Họ đường Peano..................................................................................................................... 18 3. Đường Sierpinski ................................................................................................................... 20 III. CÁC TẬP FRACTAL PHỔ BIẾN ............................................................................................ 22 1. Tập Maldelbrot....................................................................................................................... 22 a) Tìm hiểu vấn đề.................................................................................................................. 22 b) Công thức toán học ............................................................................................................ 23 c) Cài đặt................................................................................................................................ 23 2. Tập Julia................................................................................................................................. 27 a) Tìm hiểu vấn đề.................................................................................................................. 27 b) Công thức toán học ............................................................................................................ 28 c) Cài đặt................................................................................................................................ 28 3. Tập Phoenix ........................................................................................................................... 29 a) Tìm hiểu vấn đề.................................................................................................................. 30 b) Công thức toán học ............................................................................................................ 30 c) Cài đặt................................................................................................................................ 31 IV. KẾT LUẬN & TÀI LIỆU THAM KHẢO ................................................................................ 32 1. Kết luận.................................................................................................................................. 32 2. Tài liệu tham khảo ................................................................................................................. 32 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 4 I. TỔNG QUAN VỀ HÌNH HỌC FRACTAL Có bao giờ bạn tự hỏi những hình ảnh như thế này được tạo ra bằng cách nào chưa ? Những hình ành này là do bàn tay của các hoạ sĩ vẽ ? do các phần mềm 3D vẽ? Câu trả lời chính xác là nhờ các công thức toán học fractal, các hệ hàm lặp (IFS) đặc biệt vẽ nên đấy. Thật kì diệu phải không, nhưng chính bản thân fractal còn chứa đựng nhiều điều kì diệu và bí ẩn hơn mà con người còn chưa khám phá hết. Và trong khuôn khổ của đề tài này tôi và các bạn sẽ khám phá một phần của điều kì diệu ấy. 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 5 1. Sự ra đời và phát triển lý thuyết về hình học fractal Sự ra đời của lý thuyết hình học fractal là kết quả của nhiều thập kỷ nỗ lực giải quyết các vấn đề nan giải trong nhiều ngành khoa học chính xác, đặc biệt là vật lý và toán học. Một cách cụ thể, lý thuyết hình học fractal được xây dựng dựa trên 2 vấn đề lớn được quan tâm ở những thập niên đầu thế kỷ 20. Các vấn đề đó bao gồm: · Tính hỗn độn của các quá trình phát triển có quy luật trong tự nhiên. · Sự mở rộng khái niệm số chiều và độ đo trong lý thuyết hình học Euclide cổ điển. Năm 1979, nhà toán học Benoit Mandelbrot áp dụng tập Mandelbrot đầy kì ảo lên máy tính. Ông đã khám phá ra một lãnh vực hình học mới đầy thú vị cho phép phản ánh thế giới thực một cách tự nhiên hơn so với hình học Euclid. Tất cả những hình ảnh mà ta thường gặp trong tự nhiên như : núi, mây, sông, nước… nay máy tính đã có khả năng mô tả được bằng phương pháp fractal. Để thấy rõ hơn sức mạnh của fractal trong mô tả tự nhiên bạn có thể xem thêm bộ sưu tập ảnh fractal kèm theo. Trong giai đoạn này B. Mandelbrot và các nhà toán hoc khác như A.Douady và J.Hubbard đã đặt nền móng và phát triển lí thuyết cho hình học Fractal. Các kết quả đạt được chủ yếu tập trung ở các tính chất của các cấu trúc fractal cơ sở như tập Maldenbrot và tập Julia. Ngoài ra các ngiên cứu khác cũng cố gắng tìm kiếm mối quan hệ giữa các cấu trúc này, ví dụ như mối quan hệ giữa Maldenbrot và Julia. Dựa trên các công trình của Maldenbrot (trong những năm 1976, 1979, 1982) và Hutchinson(1981), vào các năm 1986,1988 Michael F.Barnsley và M.Begger đã phát triển lý thuyết biểu diễn các đối tượng tự nhiên dựa trên cơ sở lý thuyết về các hệ hàm lặp IFS. Các hệ hàm lặp này bao gồm một bộ hữu hạn các phép biến đổi affine cho phép với sự giúp đỡ của máy tính tạo nên hình ảnh của các đối tượng trong tự nhiên. Theo lý thuyết này hình học Euclide cổ điển rất có hiệu lực trong việc biểu diển các đối tượng nhân tạo như một tòa nhà, một cổ máy nhưng lại hoàn toàn không thích hợp cho việc biểu diễn các đối tượng của thế giới thực vì đòi hỏi một lượng quá lớn các đặc tả cần có. Nếu như trong hình học Euclide các yếu tố cơ sở là đường thẳng, đường tròn, hình vuông,… thì lý thuyết IFS mở rộng hình học cổ điển với các yếu tố cơ sở mới là vô số thuật toán để vẽ nên các fractal của tự nhiên. Ngoài các công trình có tính chất lý thuyết, hình học fractal còn được bổ sung bởi nhiều nghiên cứu ứng dụng lý thuyết vào khoa học máy tính và các khoa học chính xác khác, ví dụ như dựa trên lý thuyết IFS, Barnsley đã phát triển lý thuyết biến đổi fractal áp dụng vào công nghệ nén ảnh tự động trên máy tính, là một lĩnh vực đòi hỏi những kỹ thuật tiên tiến nhất của tin học hiện đại. Hiện nay nhiều vấn đề, về lý thuyết fractal vẫn đang được tiếp tục nghiên cứu. Một trong những vấn đề lớn đang được quan tâm là bài toán về các độ đo đa fractal(multifractal measurement) có liên quan đến sự mở rộng các khái niệm số chiều fractal với đối tượng fractal trong tự nhiên, đồng thời cũng liên quan đến việc áp dụng các độ đo fractal trong các ngành khoa học tự nhiên. 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 6 2. Ứng dụng của hình học fractal Hiện nay có 3 hướng ứng dụng lớn của lý thuyết hình học fractal, bao gồm: · Ứng dụng trong vấn đề tạo ảnh trên máy tính. · Ứng dụng trong công nghệ nén ảnh. · Ứng dụng trong nghiên cứu khoa học cơ bản a) Ứng dụng trong vấn đề tạo ảnh bằng máy tính Cùng với sự phát triển vượt bậc của máy tính cá nhân trong những năm gần đây, công nghệ giải trí trên máy tính bao gồm các lĩnh vực như trò chơi, anmation video… nhanh chóng đạt đỉnh cao của nó. Công nghệ này đòi hỏi sự mô tả các hình ảnh của thế giới thực trên máy PC với sự phong phú về chi tiết và màu sắc với sự tốn kém rất lớn về thời gian và công sức. Gánh nặng đó hiện nay đã được giảm nhẹ đáng kể nhờ các mô tả đơn giản nhưng đầy đủ của lý thuyết fractal về các đối tượng tự nhiên. Với hình học fractal khoa học máy tính có trong tay một công cụ mô tả tự nhiên vô cùng mạnh mẽ. Ngoài các ứng dụng trong lĩnh vực giải trí, hình học fractal còn có mặt trong các ứng dụng tạo ra các hệ đồ họa trên máy tính. Các hệ này cho phép người sử dụng tạo lập và chỉnh sửa hình ảnh, đồng thời cho phép tạo các hiệu ứng vẽ rất tự nhiên, hết sức hoàn hảo và phong phú, ví dụ hệ phần mềm thương mại Fractal Design Painter của công ty Fractal Design. Hệ này cho phép xem các hình ảnh dưới dạng hình họa vectơ cũng như sử dụng các ảnh bitmap như các đối tượng. Như đã biết, các ảnh bitmap được hiển thị hết sức nhanh chóng, thích hợp cho các ứng dụng mang tính tốc độ, các ảnh vector mất nhiều thời gian hơn để trình bày trên màn hình(vì phải được tạo ra bằng cách vẽ lại) nhưng đòi hỏi rất ít vùng nhớ làm việc. Do đó ý tưởng kết hợp ưu điểm của hai loại đối tượng này sẽ giúp tiết kiệm nhiều thời gian cho người sữ dụng các hệ mềm này trong việc tạo và hiển thị các ảnh có độ phức tạp cao. b) Công nghệ nén ảnh fractal Một trong những mục tiêu quan trọng hàng đầu của công nghệ xử lý hình ảnh hiện nay là sự thể hiện hình ảnh thế giới thực với đầy đủ tính phong phú và sống động trên máy tính. Vấn đề nan giải trong lĩnh vực này chủ yếu do yêu cầu về không gian lưu trữ thông tin vược quá khả năng của các thiết bị lưu trữ thông thường. Có thể đơn cử một ví dụ đơn giản: 1 ảnh có chất lượng gần như ảnh chụp đòi hỏi 1 vùng nhớ 24 bit cho 1 điểm ảnh, nên để hiện ảnh đó trên một màn hình máy tính có độ phân giải tương đối cao như 1024x768 cần xấp xỉ 2.25Mb. với các ảnh "thực" 24 bit này, để thể hiện được một hoạt cảnh trong thời gian 10 giây đòi hỏi xấp xỉ 700Mb dữ liệu, tức là bằng sức chứa của một đĩa CD-ROM. Như vậy khó có thể đưa công nghệ multimedia lên máy PC vì nó đòi hỏi một cơ sở dữ liệu ảnh và âm thanh khổng lồ. Đứng trước bài toán này, khoa học máy tính đã giải quyết bằng những cải tiến vượt bậc cả về phần cứng lẩn phần mềm. Tất cả các cải tiến đó dựa trên ý tưởng nén thông 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 7 tin hình ảnh trùng lặp. Tuy nhiên cho đến gần đây, các phương pháp nén thông tin hình ảnh đều có 1 trong 2 yếu điểm sau: · Cho tỉ lệ nén không cao. Đây là trường hợp của các phương pháp nén không mất thông tin · Cho tỉ lệ tương đối cao nhưng chất lượng ảnh nén quá ké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