›

Đồ án Tìm hiểu phương pháp sinh ảnh bằng Fractal

pdf 44 trang huongle 1660
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Tìm hiểu phương pháp sinh ảnh bằng Fractal", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_tim_hieu_phuong_phap_sinh_anh_bang_fractal.pdf

Nội dung text: Đồ án Tìm hiểu phương pháp sinh ảnh bằng Fractal

  1. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === LỜI CẢM ƠN Trước hết, em xin chân thành cảm ơn thầy giáo PGS.TS Ngơ Quốc Tạo đã tận tình hướng dẫn, chỉ dạy giúp đỡ tận tình và tạo mọi điều thuận lợi để em hồn thành báo cáo tốt nghiệp của mình. Em cũng xin chân thành cảm ơn trung tâm nghiên cứu và phát triển cơng nghệ phần mêm, nơi đã tạo điều kiện tốt trong suốt thời gian thực tập. Em cũng xin chân thành cảm ơn quý thầy cơ khoa cơng nghệ thơng tin trường đại học dân lập Hải Phịng đã tận tình giảng dạy, trang bị cho chúng em những kiến thức cần thiết trong suốt quá trình học tập. Và em cũng xin gởi lịng biết ơn đến gia đình, cha, mẹ,bạn bè đã ủng hộ, giúp đỡ và động viên em trong những lúc khĩ khăn. Dù đã hết sức cố gắng hồn thành đề tài nhưng chắc chắn sẽ khơng thể tránh khỏi những thiếu sĩt nhất định. Rất mong nhận được sự thơng cảm và đĩng gĩp những ý kiến vơ cùng quý báu của các thầy cơ, bạn bè, nhằm tạo tiền đề thuận lợi cho việc phát triển đề tài trong tương lai. Hải Phịng, tháng 07 năm 2009 Sinh viên thực hiện Vũ Thế Huy === 4 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  2. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === LỜI NĨI ĐẦU Tại sao mơn hình học được xem là "khơ cứng" và "lạnh lẽo"? Một trong lý do cơ bản nhất là vì nĩ khơng thể mơ tả được thế giới tự nhiên xung quanh chúng ta. Những đám mây trơi lơ lững khơng phải là những quả cầu, những ngọn núi nhấp nhơ khơng phải là những chĩp nĩn, những bờ biển thơ mộng khơng phải là những đường trịn. Từ cảm nhận trực quan này, nhà tốn học thiên tài Mandelbrot nảy sinh ra ý tưởng về sự tồn tại của một mơn "Hình học của tự nhiên", Fractal Geometry. Từ đây, tơi và bạn cĩ thể mơ tả một đám mây một cách chính xác như một kiến trúc sư thiết kế căn nhà của họ. Fractal Geometry . Với một người tình cờ quan sát màu sắc của cấu trúc Fractal sẽ bị lơi cuốn bởi hình thức đẹp hơn nhiều lần so với các đối tượng tốn học đã từng được biết đến === 5 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  3. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === TRANG 4 5 CHƯƠNG 1. TÌM HIỂU VỀ FRACTAL 9 hát triển của Fractal 10 1.2. Các ứng dụng tổng quát của hình học Fractal 11 1.3. Các kiến thức tốn học cơ bản 13 1.3.1. Khơng gian Metric 13 1.3.2. Khơng gian Hausdorff(H(X),h) 15 1.3.3. Ánh xạ co 17 1.3.4. Định lý cắt dán (COLLAGE) 17 1.4. Số chiều Fractal 19 1.5. Các hệ hàm lặp IFS (ITERATED FUNCTION SYSTEM) 19 1.6. Đặc trưng phổ biến của hình học Fractal 20 1.6.1. Tự đồng dạng 20 1.6.2.Thứ nguyên phân số 20 CHƯƠNG 2. MỘT SỐ ĐƯỜNG FRACTAL CƠ BẢN 21 2.1. Họ đường Vonckock 22 2.1.1. Đường hoa tuyết VoncKock – Nowflake 22 2.1.2. Đường VoncKock – Gosper 23 2.1.3. Đường VoncKock bậc hai 3-đoạn 25 2.2. Họ đường Peano 26 2.2.1. Đường Peano nguyên thủy 26 2.2.2. Đường Peano cải tiến 27 2.2.3. Tam giác Cesaro 28 2.3. Đường Sierpinski 29 2.4. Cây Fractal 30 2.4.1. Các cây thực tế 30 2.4.2. Biểu diễn tốn học của cây 30 2.5. Hệ thống hàm lặp(IFS) 32 2.5.1. Các phép biến đổi Affine trong khơng gian R2 32 2.5.2. IFS của các phép biến đổi Affine trong khơng gian R2 33 2.5.3. Giải thuật lặp ngẫu nhiên 33 2.6. Tập Mandelbrot 35 2.6.1. Đặt vấn đề 35 2.6.2. Cơng thức tốn học 36 2.6.3. Xây dựng thuật tốn 36 2.7. Tập Julia 38 2.7.1. Đặt vấn đề 38 2.7.2. Cơng thức tốn học 38 === 6 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  4. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 2.7.3. Xây dựng thuật tốn 39 2.8. Họ các đường cong Phonix 40 2.9. Kết luận 42 CHƯƠNG 3. CHƯƠNG TRÌNH CÀI ĐẶT THỬ 44 3.1. Kết quả cài đặt 45 3.1.1. Giao diện chính của chương trình 45 3.1.2. Kết quả một số đường và mặt cài đặt 45 3.2. Hạn chế 46 H 47 === 7 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  5. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Việc phát hiện ra các hiện tượng hỗn độn hay các fractal, đã tạo ra một “khoa học mới”, khoa học về các hệ thống phức tạp, và nhìn trước rằng đĩ sẽ là khoa học của thế kỷ 21. Thế giới tự nhiên và xã hội hiện ra trước mắt ta phức tạp hơn rất nhiều những gì mà “khoa học” đã hình dung trước đĩ, đầy những hỗn tạp thiên nhiên và cát bụi trần thế, và hình như chính trong những hỗn tạp và cát bụi đĩ mà con người tìm ra được vẻ đẹp chân thực của cuộc sống và lẽ sống cao quí của mình. Rồi sau những cảm nhận ban đầu như vậy, người ta đã nghiêm túc nghĩ đến việc phải xây dựng một khoa học mới, khoa học về cái phức tạp, hay về các hệ thống phức tạp, để làm cơ sở chung cho những nhận thức mới của mình. ” – trích lời của GS. Phan Đình Diệu đăng trên báo xaluan.com === 8 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  6. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Chương 1 : TÌM HIỂU VỀ FRACTAL === 9 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  7. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 1.1. VÀ PHÁT TRIỂN CỦA FRACTAL “Khoa học hiện đại” vốn được phát triển từ kỷ nguyên Khai sáng (Enlightenment) ở thế kỷ 17, khởi đầu bởi những phát minh của Kepler, Galilei và Newton về các định luật của vận động vật chất và bởi sự thúc đẩy mạnh mẽ của cuộc cách mạng cơng nghiệp. Với những phát minh đĩ, lần đầu tiên con người tìm được một cách nhận thức thế giới bằng “phương pháp khoa học” mà khơng cần dựa vào một sức mạnh thần thánh nào hay phải viện đến những liên cảm huyền bí nào giữa trí tuệ con người với một tinh thần hay linh hồn của tự nhiên. Và cũng do đĩ, “khoa học” đã được phát triển trước hết và mạnh mẽ ở các lĩnh vực nghiên cứu tự nhiên như cơ học, vật lý học, thiên văn học, v.v “tự nhiên khơng đến với ta sạch sẽ như ta nghĩ về nĩ”, và khoa học, trong tinh thần qui giản của cơ giới luận, với việc làm sạch tự nhiên đĩ đã “hất đổ cả đứa bé cùng với chậu nước tắm” . Ta trở lại đối mặt với một tự nhiên và cuộc đời như nĩ vốn cĩ, đầy cát bụi trần gian, lơ nhơ khúc khuỷu, gãy vỡ quanh co, chứ đâu cĩ thẳng băng, trịn trịa như các hình vẽ của khoa học hình thức. Ta nhận ra điều đĩ cả từ trong chính bản thân phần cốt lõi tri thức của khoa học, cả từ những lĩnh vực ứng dụng khoa học đang cĩ nhiều hứa hẹn thành cơng. Nền tảng đầu tiên của Fractal đã được nhà tốn học và vật lí học Leibniz đưa ra cùng khoảng thời gian đĩ là self-similarity (tính tự tương tự) mặc dù chưa hồn chỉnh nhưng đã mở ra bước tiến đầu tiên. Nhưng nĩ chỉ được biết đến với cái tên hình học Fractal đầu tiên vào năm 1872 khi Karl Weierstrass đưa ra một ví dụ với chức năng khơng trực quan của thuộc tính hiện thân khắp nơi liên tục mà khơng phụ thuộc vào khơng gian. Vào 1904, volt Helge Koch khơng hài lịng với kết luận của Weierstrass, đưa ra một định nghĩa hình học cao hơn về chức năng tương tự, mà bây giờ được gọi là đường cong Koch. Dựa trên thành quả đĩ , Waclaw Sierpinski đã xây dựng với tam giác vào năm 1915 mà sau nay gọi là tam giác Sierpinski. Ban đầu các Fractal hình học đã được mơ tả như là những đường cong hơn là hình 2D mà ta được biết đến như là trong các cơng trình hiện đại ngày nay. Vào 1918, Bertrand Russell đã === 10 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  8. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === đốn nhận về một " vẻ đẹp tối cao " bên trong nẩy sinh trong tốn học Fractal.Ý tưởng của các đường đồng dạng được cầm xa hơn nữa bởi Pierre Lévy Paul, người mà, trong 1938 đã đưa ra kiến giả về một đường cong fractal mới, đường cong C Lévy. Georg Cantor cũng đã cung cấp các ví dụ về các tập con cảu thuộc tính bất thường thực sự phù hợp – tập Cantor bây giờ cũng được cơng nhận là fractals. Những hàm lặp trong mặt phẳng phức được điều tra vào cuối thế kỉ 19 - đầu thế kỉ 20 bởi Henry Poincaré, Felix Klein, Pierre Fatou và Gaston Julian. Tuy nhiên, khơng cĩ sự giúp đỡ của đồ họa máy tính hiện đại, họ thiếu những phương tiện để làm cho trực quan vẻ đẹp của nhiều đối tượng mà họ khám phá. Vào những năm 1960, Benoit Mandelbrot bắt đầu điều tra self- similarity (tính tự tương tự), mà trước đĩ được xây dựng trên cơng việc của Lewis Fry Richardson. Cuối cùng, vào 1975 Mandelbrot đưa ra từ "Fractal" để biểu thị một đối tượng mà cĩ miền Hausdorff- Besicovitch là lớn hơn so với các miền trước đây. Ơng ta minh họa định nghĩa tốn học này bởi máy tính những trực quan hĩa. Những ảnh này bắt đầu trở lên nổi tiếng dựa vào phép đệ quy, dẫn tới hình thành thuật ngữ "Fractal" ngày nay. 1.2. CÁC ỨNG DỤNG TỔNG QUÁT 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 phân hình, 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. □ ỨNG DỤNG TRONG VẤN ĐỀ TẠO ẢNH TRÊN 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 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 phân hình 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ẽ. Ngồi các ứng dụng trong lĩnh vực giải trí, hình học phân hình cịn cĩ mặt trong các ứng dụng tạo ra các hệ đồ hoạ 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 hồ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 === 11 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  9. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Design. Hệ này cho phép xem các hình ảnh dưới dạng hình hoạ véctơ cũng như sử dụng các ảnh bitmap như các đối tượng. Như đã biết, các ảnh bitmap hiển thị hết sức nhanh chĩng, thích hợp cho các ứng mang tính tốc độ, các ảnh véctơ 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ệ phần mềm này trong việc tạo và hiển thị các ảnh cĩ độ phức tạp cao. □ ỨNG DỤNG TRONG CƠNG NGHỆ NÉN ẢNH: 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ượt quá khả năng lưu trữ của các thiết bị 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ư chụp địi hỏi vùng nhớ 24 bit cho 1 điểm ảnh, nên để hiện ảnh đĩ trên 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 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 tố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 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ệ nén 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ộc. 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 phân hình được áp dụng gần đây bởi Iterated System đáp ứng được yêu cầu này. === 12 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  10. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Kết quả nén cho bởi quá trình này rất cao, cĩ thể đạt 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 phân hình là bộ bách khoa tồn thư multimedia với tên gọi “Microsoft Encarta” được đưa ra vào tháng 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ố dưới dạng các dữ liệu fractal và chỉ chiếm xấp xỉ 600Mb trên một đĩa compact. □ Ứ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 phân hình 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ẽ như đã trình bày trong phần I.1, vật lý học và tố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 quá 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 tốn phi tuyến địi hỏi rất nhiều cơng sức trong việc tính tố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ợ đắt 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 phân hình trong lĩnh vực này 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 phân hình đã đượ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ố 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 quả thu được giữ vai trị rất quan trọng trong các lĩnh vực tương ứng. 1.3. CÁC KIẾN THỨC TỐN HỌC CƠ BẢN 1.3.1. Khơng gian Metric : a,Khơng gian Định nghĩa 1: Khơng gian X là một tập mà các điểm của khơng gian là các phần tử của tập đĩ. 2: (khơng gian Metric) : :XxX , y X: * d (x, y) = d (y, x) x, y X * 0 < d (x, y) < x, y X, x y === 13 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  11. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === * d (x, x) = 0 x X * d (x, y) d (x, z) + d (z, y) x, y, z X . 3: Hai metric d1 2 0 0 sao cho: d1(x, y) 0, : d(xn, xm) N 2: xn n =1 >0, : d(xn, x) < , n<N : x = limn xn : xn n =1 trong khơng gian metric (X, d xn n =1 . 3: xn n =1 X. : === 14 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  12. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === (R, d) (R2 . 4: S xn n =1 n S\ x sao cho: Limn xn=x 5: S : : S= S : S= S : S = x=1/n; n=1, 2, ( 0, 1 , d), Ơcơlit. 1: S xn n =1 . 2: S >0 sao cho: d(a, x) 0 sao cho B(x, )= y X:d(x, y) S. 1.3.2. Khơng gian Hausdorff (H(X), h): . 1: === 15 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  13. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === . 2: , x : d(x, B)=Min d(x, y):y B . 3: , B : d(A, B)=Max d(x, B):x A . 4: , B : h(A, B) = d(A, B) d(B, A) 5: S + = y X : d(x, y) S + . 1: Cho A, B , : h(A, B) A B+ A+ . ) c, An : n = 1, 2, , (H(X), h), nj j =1 0<n1<n2<n3< xnj Anj ; j=1, 2, Cauchy xn An ; n 1 sao cho ~ x nj = xnj j = 1, 2, 3, : ) An H(X) n =1 = limn An H(X). : A= x X : xn An : , xn X (limn d(x, xn : X n f(xn)=f(x). === 16 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  14. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 1.3.3. Ánh xạ co 1: :X 0 s<1 sao cho: d(f(x), f(y)) s.d(x, y) x, y X. . ) f:X on f X, x f (x) : n=0, 1, 2, xf : on limn f (x) = xf X . 1: Cho khơn w:X . 2: w:X (X). 3: w:X :H(X) H(X) như sau: w(B) = w(x): x B B H(X). . 4: h(B C, D E) h(B, D) h(C, E) B, C, D, E H(X) 5: , wn:n=1, 2, , N n n :H(X) : N W(B) = w1(B) w2 (B) wn (B) = Uwn (B) n 1 =Max sn:n=1, 2, , N . 1.3.4. Định lý cắt dán (COLLAGE) === 17 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  15. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 1: 0:H(X) 0 0 . 2: Cho X;wn, n=1, 2, , N 0 0:H(X) X;wn, n=0, 1, 2, , N . : Cho X;wn, n=0, 1, 2, , N :H(X) : N W(B) Uwn (B) B H(X) n 0 (H(X), h( : h(W(B), W(C)) s.h(B, C) B, C H(X) : N on A = W(A) =  w n (A) =limn W (B) H(X). n=0 (collage) : >0. X;wn, n=1, 2, , N 0 s<1 sao cho N h L,  w n (L) n 1(n 0) h(L, A) - A=limn wn(L) A=L w(L) w2(L) =wn(L) : N 1 h(L, A) (1 s) h L,  w n (L) L H(X). n 1(n 0) 0 , A0 0, w1, , wn 2 : h(A, w(A0) w (A0) ) - === 18 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  16. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 0 - ng . 1.4. SỐ CHIỀU FRACTAL , - : D= log N/log (1/r) . 1.5 CÁC HỆ HÀM LẶP IFS(ITERATED FUNCTION SYSTEM ) Định nghĩa 1: Một hệ hàm lặp gồm một khơng gian metric đầy đủ (X, d) và một bộ hữu hạn các ánh xạ co wn với hệ số co tương ứng sn, n = 1, 2, , N. Ta ký hiệu IFS thay cho cụm từ hàm lặp. Một IFS được ký hiệu bởi [X; wn, n = 1, 2, , N] và hệ số co s = max sn 1 n N Định lý sau tĩm tắt các kết quả chính của một IFS: Định lý IFS: Xét một IFS {X;wn,n 1,2, ,N} với hệ số co s . Khi đó phép biến đổi W: H(X) H(X) xác định bởi : N W(B) wn(B) n 1 trong đó B H(X) là một ánh xạ co trên không gian metric đầy đủ (H(X) ,h(d)) với hệ số co s , tức là : h(W(B) ,W(C)) s.h( B,C) , B,C H(X) Ánh xạ này có duy nhất một điểm bất động A H(X) với : N A W(A) wn(A) n 1 và được cho trước bởi A lim Wn(B) với bất kỳ B H(X) . n === 19 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  17. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Đị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 đĩ. 1.6 ĐẶC TRƯNG PHỔ BIẾN CỦA HÌNH HỌC FRACTAL 1.6.1. Tự đồng dạng Minkowski , Tam gi , . . 1.6.2. Thứ nguyên phân sơ , yên 3) 2 1/K , N=k =k3 . =kd =kd => d= logN/logk log8/log4=1,5 (k=2) === 20 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  18. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Chương 2 : MỘT SỐ ĐƯỜNG FRACTAL CƠ BẢN === 21 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  19. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 2.1 HỌ ĐƯỜNG VONKOCK Trong phần này chúng ta sẽ cùng nhau thảo luận các fractal được phát sinh bằng cách sử dụng đệ qui initiator / generator với kết quả là các hình tự đồng dạng hồn tồn. 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: log( N) D 1 log R Trong đĩ: N: Là số đoạn 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: 2.1.1. Đường hoa tuyết Von Kock - Nowflake Đường hoa tuyết được xây dựng bởi nhà tốn học Helge Von Kock vào năm 1904. Ở đây chúng ta bắt đầu với initiator là một đoạn thẳng. Cịn generator được phát sinh như sau: Generator của đường von kock Chúng ta chia đoạn thẳng thành ba phần bằng nhau. Sau đĩ thay thế một phần ba đoạn giữa bằng tam giác đều và bỏ đi cạnh đáy của nĩ. Sau đĩ chúng ta lặp lại quá trình này cho mỗi đoạn thẳng mới. Nghĩa là chia đoạn thẳng mới thành ba phần bằng nhau và lặp lai các bước như trên. === 22 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  20. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Ta thấy quá trình xây dựng là tự đồng dạng, nghĩa là mỗi phần trong 4 phần ở bước thứ k là phiên bản nhỏ hơn 3 lần của tồn bộ đường cong ở bước thứ (k–1). Như vậy mỗi đoạn thẳng của generator cĩ chiều dài R = 1/3 (giả sử chiều dài đoạn thẳng ban đầu là 1) và số đoạn thẳng của generator N = 4. Do vậy số chiều fractal của đường hoa tuyết là: log( N) log 4 D 1,2618 1 log 3 log R Một số hình ảnh (Bậc 2) (Bậc 3) 2.1.2. Đường Von Kock - Gosper Một dạng khác của đường Von Kock được phát hiện bởi W.Gosper. Trong đường mới này, initiator là một lục giác đều và generator chứa ba đoạn nằm trên một lưới của các tam giác đều. Hình sau cho chúng ta thấy generator bố trí trên lưới: === 23 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  21. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Ta thấy đường này cĩ chút khác biệt so với đường hoa tuyết ở chổ đoạn thẳng được thay thế khơng nằm trên bất kỳ các đường nào của lưới. Để tính số chiều fractal của đường Gosper trước hết ta tính chiều dài mỗi đoạn của generator. Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1. Đặt: AC = R => AE = 3AC = 3R AB2 = AE2 + EB2 – 2AE.EB.Cos(600) Ta cĩ: Mà AB = 1, AE = 3R, EB = AC = R 1 9R 2 R 2 2 3R R / 2 7R 2 1 R 7 EB 2 AE 2 AB 2 2AEAB cos 1 1 8 AB 2 AE 2 EB 2 1 9R 2 R 2 1 8R 2 5 7 cos 7 2AEAB 2 3R 1 6R 1 14 6 7 0 94491 0 19 1' Vì N = 3 nên số chiều fractal của đường Gosper là: log 3 D 1.1291 log 7 Một số hình ảnh của đường (Mức 1) (Mức 2) 2.1.3 Đường Von Kock bậc hai 3-đoạn === 24 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  22. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Một vài đường cong kế tiếp được gọi là bậc hai (quadric) vì initiator là một hình vuơng (Tuy nhiên điều này khơng cĩ gì bí mật về initiator là hình vuơng, nĩ cĩ thể là một đa giác). Hơn nữa chúng ta sẽ tạo ra các generator trên lưới các hình vuơng. Đối với đường cong đầu tiên này, một generator của 3-đoạn sẽ được sử dụng. Hình sau sẽ cho chúng ta một generator: Để tính số chiều fractal của đường này trước hết ta tính số chiều của mỗi đoạn của generator. Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1: Ta cĩ: Đặt AC = R AB2 = AE2 + EB2 Mà AB = 1, AE = 2AC = 2R, EB = R => 1 = 4R2 + R2 1 R 5 EB2 = EA2 + AB2 – 2EA.AB.cos 1 1 3 EA 2 AB 2 EA 2 4R 2 1 R 2 1 3R 2 2 5 cos 5 0.894427 2EAAB 2.2R.1 4R 1 5 4 5 25056' Vì N = 3 nên số chiều fractal là: log 3 D 1.3652 log 5 Một số hình ảnh của đường === 25 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  23. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === (Mức 3) (Mức 5) 2.2.HỌ ĐƯỜNG PEANO 2.2.1 Đường Peano nguyên thủy Hình sau cho chúng ta thấy generator của đường Peano nguyên thuỷ: Ở đây initiator rất đơn giản. Nĩ chỉ là một đoạn thẳng. Thật khơng may, tất cả đều tự cắt, nên hầu như khơng thể xác định cách thức mà theo đĩ đường Peano được vẽ, ngay cả các mũi tên được thêm vào trong hình vẽ. Nhìn vào hình vẽ này chúng ta thấy generator được hình thành như sau: Đầu tiên chúng ta dựng đoạn thẳng đứng về phía trên, rồi dựng đoạn thẳng ngang về bên trái, rồi dựng đoạn thẳng đứng về phía trên, rồi dựng dựng đoạn thẳng ngang về bên phải, rồi dựng đoạn thẳng đứng về phía dưới, rồi dựng đoạn thẳng ngang về bên phải, rồi dựng đoạn thẳng đứng về phía trên, rồi dựng đoạn thẳng ngang về phía trái, và cuối cùng dựng đoạn thẳng đứng về phía trên. Như vậy generator chứa 9 đoạn thẳng (nghĩa là N = 9), chiều dài mỗi đoạn của generator là R = 1/3 (Giả sử chiều dài đoạn thẳng ban đầu là 1). Do đĩ số chiều fractal là: log 9 D D 2 log 3 === 26 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  24. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Một số hình ảnh của đường (Mức 1) (Mức 3) 2.2.2. Đường Peano cải tiến Nếu khơng cĩ sự tự giao của generator đối với đường Peano thì việc đi theo vết của nĩ và quan sát cách thức vẽ sẽ dễ dàng hơn. Vì thế, đường Peano cải tiến được phát triển theo kiểu làm trịn các gĩc để tránh sự tự giao. Kết quả chúng ta được generator như hình sau: Tuy nhiên, generator cập nhật này chỉ cĩ thể sử dụng ở mức thấp nhất trước khi thực vẽ đường cong. Nếu sử dụng nĩ ở mức cao hơn, bằng kỹ thuật đệ quy chúng ta cố gắng thay thế generator đối với mỗi đường chéo được làm trịn ở một gĩc, cũng như đối với các đoạn thẳng đều. Do đĩ generator cho đường Peano nguyên thuỷ được sử dụng ở mức cao. 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 thuỷ, 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 === 27 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  25. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === (Mức 2) 2.2.3. Tam giác Cesaro Hình sau cho chúng ta xem một generator rất đơn giản (initiator là đoạn thẳng nằm ngang): Generator chứa hai cạnh của một tam giác cân. Do đĩ, số đoạn thẳng là N=2 và chiều dài của mỗi đoạn là: 1 R 2 Giả sử đoạn thẳng ban đầu cĩ chiều dài là 1. Khi đĩ số chiều fractal là: log 2 D D 2 log 2 Phụ thuộc vào các điều kiện cụ thể, generator này sẽ được đặt bên trái hoặc bên phải của mỗi đoạn thẳng mà nĩ thay thế. Nhiều đường cong khác nhau hồn tồn cĩ thể được sinh ra từ generator này. Các đường này được khám phá bởi Ernest Cesaro vào năm 1905. Các hình sau là các mức khác nhau của tam giác Cesaro: === 28 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  26. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === (Mức 1) (Mức 5) 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 hồn tồ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 1, 2 và 3 được minh hoạ như sau: Mức 1 Mức 3 Mức 4 Mức 8 === 2 9 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  27. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 2.4. CÂY FRACTAL Trong các phần trước, chúng ta đã tạo ra các đường fractal bằng cách thay thế một cách lặp lại của các đoạn thẳng với các mẫu thu nhỏ của một generator mẫu, kết quả là các đường cĩ tính tự đồng dạng. Bây giờ, chúng ta sẽ tạo ra đường cong theo một hướng khác. Chúng ta sẽ bắt đầu với một thân cây tại đầu mút của nĩ chúng ta tách thân cây thành hai hướng và vẽ hai nhánh. Chúng ta sẽ lặp lại quá trình này tại các đầu mút của mỗi nhánh. Kết quả chúng ta sẽ được một cây. Trước khi chúng ta biểu diễn các cây tự nhiên, đầu tiên chúng ta thảo luận vài điều về các cây thực tế. 2.4.1. Các cây thực tế Chúng ta phác thảo quá trình tạo cây được cho ở trên. Tại mỗi nút trong quá trình tạo cây, chúng ta tách làm hai hướng. Kết quả ta được một cây hai chiều. Chúng ta hy vọng nĩ cĩ một số quan hệ với cây thực tế 3 chiều. Trước khi đi xa hơn, chúng ta quan sát một vài cây tự nhiên. Đầu tiên, cĩ hai lớp cây là lớp cây rụng lá (deciduous) mỗi năm và lớp cây tùng bách (conifers). Hai lớp cây này hồn tồn khác nhau. Cây tùng bách cĩ khuynh hướng cĩ các vịng của các nhánh ở tại các độ cao khác nhau vịng quanh trung tâm của thân cây. Điều này dường như khơng thích hợp với tất cả các quá trình rẽ nhánh nhị phân và chúng ta sẽ thấy các cây sau đây do chúng phát sinh khơng bao giờ giống với cây tùng bách thật sự. Thứ hai, đối với cây rụng lá mặc dù sự xuất hiện của chúng rất gần với mơ hình của chúng ta, thế nhưng vẫn cịn rất nhiều phức tạp trong cấu trúc của chúng. Trong khi đĩ, việc rẽ nhánh nhị phân thường cĩ qui luật và đơn giản hơn nhiều, chỉ ngoại trừ một vài thân cây cĩ khả năng tách ra nhiều hơn hai nhánh. 2.4.2.Biểu diễn tốn học của cây Theo Leonardo da Vinci quan sát, kết quả đĩ là do tổng số các vùng cắt ngang của các nhánh cây ở một độ cao cho trước là hằng số. Điều này khơng gây ngạc nhiên vì cây địi hỏi chuyển dinh dưỡng từ gốc đến lá và cho trước một lượng dinh dưỡng, một người nghĩ rằng thiết diện cần thiết cho sự vận chuyển sẽ khơng đổi bất kể chiều cao hay số ống dẫn. Khi chúng ta chuyển sự quan sát này vào các đường kính (hay các D D D 0 1 2 chiều rộng khi chúng ta vẽ thành cây hai chiều ) thì chúng ta cĩ được biểu thức sau: === 30 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  28. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Ở đây D0, D1, D2 là đường kính của hai nhánh chia cây làm đơi, = 2 theo da Vinci. Do đĩ các dạng các dạng cấu trúc giống cây, mơ hình đơn giản được cho ở trên cĩ khả năng áp dụng cho các hệ thống sơng tốt hơn các cây, vì thường cĩ nhiều hơn hai con sơng nhánh của một hệ thống sơng sẽ nối với nhau ở cùng một nơi. Các cây khác được tìm thấy trong cơ thể con người là hệ thống động mạch và cuống phổi dùng để vận chuyển máu và oxy, trong đĩ đối với hệ thống cuống phổi là 3 và đối với động mạch là 2.7. Khi chúng ta xây dựng cây chúng ta sẽ sử dụng biểu thức: 1 (a) B 2 Bn n 1 Ở đây Bn là đường kính của nhánh ở mức thấp hơn. Bn+1 biểu diễn đường kính mỗi nhánh con khi Bn tách thành hai nhánh. Chúng ta cũng cần xem xét chiều dài mỗi nhánh. McMahon nghiên cứu các loại cây kiểu mẫu khác nhau và đưa ra cơng thức như sau cho chiều dài: 2 3 (b) L 2 Ln n 1 Với Ln là chiều dài của nhánh trước đĩ và Ln+1 chiều dài của mỗi nhánh trong hai nhánh kế sau khi nhánh trước đĩ được tách ra làm hai. Sau đây là hình minh hoạ một cây fractal với Level = 14, Height = 80, Width = 20, Left_Alpha = 2.0, Right_Alpha = 2.2, Left_Angle = 20, Right_Angle = 28. === 31 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  29. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 2.5. HỆ THỐNG HÀM LẶP (IFS) 2.5.1.Các phép biến dổi Affine trong khơng gian R2 Cho phép biến đổi w: IR2 IR2 cĩ dạng: w (x, y) = (ax + by + e, cx + dy + f) Ở đây a, b, c, d, e, f là các hệ số thực, được gọi là phép biến đổi affine (hai chiều). Phép biến đổi cĩ thể viết dưới dạng: x a b x e w AX T y c d y f Với: a b x e A , X ,T c d y f Bằng cách biểu diễn phép biến đổi trên dưới dạng tách các phép quay và vị tự ma trận A cĩ thể viết dưới dạng: r cos ssin A r sin scos === 32 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  30. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Với: r: hệ số vị tự trên trục x. s: hệ số vị tự trên trục y. : gĩc quay trên trục x. : gĩc quay trên trục y. e: hệ số tịnh tiến trên trục x. f: hệ số tịnh tiến trên trục y. 2.5.2.IFS của các phép biến đổi Affine trong khơng gian R2 Một IFS là tập hợp các phép biến đổi affine co tức là: 2 IFS { IR ; wn : n = 1, 2, , N } với wn là phép biến đổi affine. Ví dụ: 2 Một IFS của ba phép biến đổi w1, w2, w3 là IFS { IR ; w1, w2, w3 } với w1, w2, w3 xác định bởi: x 0.5 0 x 0 w 1 y 0 0.5 y 0 x 0.5 0 x 1 w 2 y 0 0.5 y 0 x 0.5 0 x 0.25 w 3 y 0 0.5 y 0.25 Trong đĩ mỗi phép biến đổi affine liên kết với một xác xuất Pn quyết định độ quan trọng của nĩ so với phép biến đổi khác. Để ý rằng: N Pn 1, Pn 0(n 1, , N) n 1 Ví dụ: Mã IFS đối với tam giác Sierpinski w a b c d e f p 1 0.5 0 0 0.5 0 0 0.33 2 0.5 0 0 0.5 1 0 0.33 3 0.5 0 0 0.5 0.5 0.5 0.34 2.5.3.Giải thuật lặp ngẫu nhiên 2 Cho IFS [IR ; wn : n = 1, 2, , N ] , mỗi wn liên kết với xác xuất Pn. === 33 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  31. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Trước khi trình bày thuật tốn, chúng ta tìm cách chọn các xác xuất Pn thích hợp. Khi chúng ta xác định các phép biến đổi, chúng ta cần chọn các xác xuất cho chúng. Việc chọn các xác xuất khác nhau sẽ khơng dẫn đến các hấp tử khác nhau, nhưng chúng ảnh hưởng đến tốc độ ở các miền khác nhau hay thuộc tính của hấp tử được làm đầy. Mỗi phép biến đổi affine wn tương ứng với hấp tử J là: x an bn x en wn ,n 1,2, ,N y cn dn y fn Số lần mà điểm nhảy một cách ngẫu nhiên dùng trong hấp tử con wn xấp xỉ với: s wn s j Với S(A): Diện tích của A Nếu detAn 0 thì việc chọn xác xuất Pn như sau: det A a d b c P n n n n n n N N det A a d b c i 1 i i 1 i i i i Nếu detAn = 0 thì Pn được gán cho một số nhỏ nhất và khá gần 0, ví dụ như 0.001. Sau đây là các bảng mã IFS: Mã IFS cho 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 Tương tự chúng ta áp dụng thuật tốn này đối với IFS của phép biến đổi affine trong khơng gian ba chiều cĩ dạng: === 34 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  32. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === x a b c x n ax by cz n w y d e f y q dx ey fz q z g h m z r gx hy mz r Mã IFS cho lá dương xỉ ba chiều: w A B c D E f G h m n q r P 1 0 0 0 0 0.1 0 0 0 0 0 0 0 0.001 8 2 0.83 0 0 0 0.8 0.1 0 -0.12 0.84 0 1.62 0 0.901 6 3 0.22 -0.23 0 0.24 0.2 0 0 0 0.32 0 0.82 0 0.049 2 4 0.22 0.23 0 0.24 0.2 0 0 0 0.32 0 0.82 0 0.049 2 Sau đây là các hình vẽ minh hoạ giải thuật lặp ngẫu nhiên tương ứng với bảng mã IFS được trình bày ở phần trước: Lá dương xỉ 2 chiều Lá dương xỉ 3 chiều 2.6. TẬP MANDELBROT 2.6.1.Đặt vấn đề Trong nhiều thập niên của thế kỷ XX, các nhà tố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: 2 zn+1 = zn + c, trong đĩ zi C, i N & c C (1) === 35 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  33. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Để đơn giản hố vấn đề, trước hết ta xét trường hợp c = 0 và z0 R. Khi đĩ cĩ 3 trường hợp sau: + z0 = 1 : khi đĩ zn = 1, n 1. + 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 lớn thì dãy (zn) càng tiến nhanh ra . Trong trường hợp tổng quát, dãy (zn) được xác định bởi cơng thức (1) ở trên rất khĩ khảo sát về mặt lý thuyết. Chỉ đến năm 1979, Mandelbrot 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ả được Mandelbrot quan sát thấy là một trong những cấu trúc fractal phức tạp và đẹp. Nĩ đã được đặt tên Mandelbrot để ghi nhớ cơng lao của tác giả, người đã khai sinh ra lý thuyết hình học phân hình. 2.6.2.Cơng thức tố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: 2 2 xn+1 = xn – yn + p yn+1 = 2xn .yn + q (2) Ngồ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 1, với 1 là hằng số hữu hạn thì cũng cĩ | zn | < 2, n k. (Ký hiệu | z | chỉ modul của số phức z). 2.6.3.Xây dựng thuật tốn === 36 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  34. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Tập Mandelbrot là hình ảnh của dãy (zn), với giá trị khởi đầu z0 = 0. Khi đĩ màn hình máy tính sẽ chuyển đổi thành một mặt phẳng phức thu hẹp với: + Trục x biểu diễn phần thực của số phức c (giá trị p được nêu ở phần 2/). + Trục y biểu diễn phần ảo của số phức c (giá trị q được nêu ở phần 2/). Từ tính chất về sự hội tụ của dãy (zn) ở phần 2 chúng ta cĩ thể chia tập các giá trị của c trên mặt phẳng phức thành 2 lớp: Lớp 1: Gồm các giá trị c làm cho dãy (zn) khơng tiến ra vơ cực mà được giới hạn trong một vịng trịn bán kính 2. Một cách cụ thể, đĩ là các giá trị c sao cho khi xuất phát từ chúng, ta luơn cĩ | zi | 2 ở một ngưỡng k hữu hạn nào đĩ. Vấn đề đặt ra ở đây là cần quan sát tính hỗn độn của dãy (zn). Do đĩ chúng ta tập trung các quan sát vào các giá trị c thuộc lớp 2. Muốn như vậy các giá trị này phải được thực hiện một cách nổi bật trên màn hình máy tính bởi các màu khác nhau. Chúng ta sẽ tơ màu mặt phẳng phức màn hình theo qui tắc sau: + Các giá trị c thuộc lớp 1 được tơ màu đen vì khơng cĩ tính chất gì đáng chú ý. + Các giá trị c thuộc lớp 2 được tơ bằng các màu khác nhau ứng với các ngưỡng tiến ra vơ hạn k khác nhau. Do số lượng màu cĩ thể hiển thị trên một màn hình đồ hoạ là hữu hạn, việc tơ màu các giá trị này sẽ được thực hiện theo kỹ thuật tơ màu xoay vịng được chỉ ra ở các phần tiếp sau đây. === 37 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  35. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Tập Mandelbrot cổ điển với các giá trị khảo sát nằm trong vùng giới hạn bởi Xmin = -2.0, Ymin = -1.2, Xmax = 1.2, Ymax = 1.2 và Max_Iterations = 512, Max_Colors = 1.6. 2.7. TẬP JULIA 2.7.1.Đặt vấn đề 2 Đối với biểu thức zn+1 = zn + c, ngồi hướng đã khảo sát như đã trình bày trong phần tập Mandelbrot, cịn cĩ hướng khảo sát khác bằng cách cho c cố định và xem xét dãy (zn) ứng với mỗi giá trị khác của z0. Theo hướng này chúng ta sẽ thu được 1 lớp các đối tượng fractal mới được gọi là tập Julia. Tập Julia và tập Mandelbrot là hai lớp các đối tượng fractal cĩ mối liên hệ rất chặt chẽ với nhau. Một tính chất đáng chú ý là tập Mandelbrot cĩ thể xem như một loại “bản đồ” Mandelbrot cĩ thể cho ra các dạng tập Julia đầy sức lơi cuốn. Các vị trí như vậy được quan sát thấy ở gần biên của tập Mandelbrot. Nhất là gần các chỏm nhọn. Ngồi ra khi phĩng to một phần của tập Mandelbrot, ta sẽ thu được một hình rất giống với tập Julia được tạo bởi giá trị của tâm phần được phĩng to. 2.7.2.Cơng thức tốn học Để thể hiện tập Julia trên màn hình máy tính, ta vẫn sử dụng các cơng thức như trong phần tập Mandelbrot, như là: 2 2 xn+1 = xn – yn + p yn+1 = 2xnyn + q Ngồi ra các tính chất đã nêu về giới hạn của dãy (z0) vẫn được sử dụng cho tập Julia. === 38 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  36. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 2.7.3.Xây dựng thuật tốn Điểm khác biệt so với tập Mandelbrot ở đây là giá trị p và q được giữ cố định, mặt phẳng màn hình biến đổi thành mặt phẳng phức thu hẹp biểu diễn các giá trị của x0 với: - Trục x biểu diễn phần thực của số phức z0. - Trục y biểu diễn phần ảo của số phức z0. Ngồi ra cịn cĩ sự phân lớp các giá trị của z0 như sau: Lớp 1: Bao gồm các giá trị (z0) cĩ | zk | 2, với n k, k Z , tức là gồm các giá trị làm cho dãy (zn) tiến ra vơ cực. Ngược lại với tập Mandelbrot, khi thể hiện tập Julia trên màn hình, chúng ta quan tâm đến các giá trị z0 làm cho dãy (zn) khơng hội tụ đến vơ cực. Do đĩ kỹ thuật tơ màu của tập Julia vẫn là kỹ thuật xoay vịng nhưng hồn tồn ngược lại với kỹ thuật tơ màu tập Mandelbrot. Trong kỹ thuật tơ màu này: - Các điểm ảnh tương ứng với các giá trị z0 thuộc lớp 1, sẽ được gán màu tùy thuộc độ lớn của | zl| với l là ngưỡng quyết định hội tụ của dãy (zn) đã nêu trong định nghĩa về lớp 1. - Các điểm ảnh tương ứng với giá trị z0 thuộc lớp 2 sẽ được gán màu trùng với màu nền của bảng màu đang sử dụng. === 39 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  37. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Hình minh hoạ tập Julia 2.8. HỌ CÁC ĐƯỜNG CONG PHOENIX Họ các đường cong Phoenix do Shigehiro Ushiki ở trường đại học Kyoto tìm ra. Phương trình của đường cong được xác định bởi: 2 Zn+1 = zn + p + q.zn-1 Trong đĩ: Zi C i, N. p = (p, 0) C. q = (q, 0) C. Phương trình được khai triển thành các phần thực và ảo của zn cĩ dạng: 2 2 xn+1 = xn – yn + p + q.xn-1 yn+1 = 2xn.yn + q.yn-1 với: xn+1 = Re(zn+1); yn+1 = Im(zn+1). Khi đĩ việc thể hiện đường cong này lên màn hình gần giống với việc thể hiện tập Julia. Tuy nhiên cĩ hai điểm thay đổi quan trọng: === 40 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  38. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Thay đổi 1: - Trục x của màn hình biểu thị phần ảo của số phức z0. - Trục y của màn hình biểu thị phần thực của số phức z0. Ở đây chúng ta đảo ngược các trục thực và ảo của mặt phẳng phức thơng thường là để thể hiện hình ảnh theo chiều đứng chứ khơng phải chiều ngang. Hình 14.1 trình bày 1 loại đường cong loại này với yêu cầu rõ ràng là phải đổi vai trị của trục x và y để hình ảnh cĩ thể được thể hiện tốt trên màn hình. Do đĩ tương ứng với một điểm ảnh (Col, Row) trên màn hình sẽ là số phức z = (x, y) cĩ dạng: x = ymax – Row * x; y = ymin – Col * y; Với: ymax y x min Max _ Row xmax x y min Thay đổi 2: Max _Col Thay đổi về thuật tốn tơ màu. Ở đây với các điểm thuộc lớp 1 (theo định nghĩa đã nêu ở phần về tập Julia) chúng ta sẽ sử dụng 3 loại màu tuỳ theo ngưỡng hội tụ: Màu 1: được sử dụng để tơ các điểm z0 cho ra giá trị | zk | < 2 với tối đa k = 32 lần lặp. Màu 2: được sử dụng để tơ các điểm z0 cho ra giá trị | zk | < 2 với số lần lặp từ 33 đến 64. Màu 3: được sử dụng để tơ các điểm z0 cho ra giá trị | zk | < 2 với số lần lặp vượt quá 64 lần. Cịn đối với các điểm thuộc lớp 2, chúng ta sẽ tơ chúng bằng một màu khác với màu nền hiện tại. === 41 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  39. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Đường cong Phoenix 2.9. KẾT LUẬN . Hiện nay trên thế giới Fractal rất phát triển. Thị trường tranh fractal và phần mềm sáng tác fractal cũng khơng hề nhỏ, nĩ cĩ giá trị gần 1 tỉ USD trong năm 2004. Tìm hiểu sâu hơn về fractal hãy truy cập những địa chỉ sau: www.les.stclair.btinternet.co.uk www.biofractalevolution.com www.fractalism.com === 42 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  40. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === . Cịn muốn tạo ra những hình họa fractal nhanh chĩng và dễ dàng nhất, hãy sử dụng các phần mềm miễn phí: - Aros Fractals: Dung lượng chỉ 165 KB, tương thích với mọi mơi trường Windows hiện hành, giải nén vào một thư mục rồi sử dụng ngay mà khơng cần cài đặt. Tải về từ địa chỉ www.arosmagic.com. - Double Fractal: Của tác giả Joao Paulo Schwarz Schuler. Dung lượng 676 KB, khơng cần cài đặt, tải về từ địa chỉ www.schulers.com/fractal. === 43 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  41. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Chương 3 : CHƯƠNG TRÌNH CÀI ĐẶT THỬ === 44 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  42. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === Để cĩ thể cài đặt một số đường và mặt fractal chúng ta cĩ thể sử dụng ngơn ngữ lập trình Visual C++. Đây là một ngơn ngữ lập trình hỗ trợ khá mạnh cho đồ hoạ. 3.1. KẾT QUẢ CÀI ĐẶT Trong phần này giới thiệu cách sử dụng các tác vụ trong việc thực hiện vẽ các đường và mặt Fractal. 3.1.1.Giao diện chính của chương trình Giao diện chính của chương trình như sau: 3.1.2.Kết quả một số dường và mặt cài đặt được  Các đường thuộc họ đường Von Kock như: . Đường hoa tuyết Von Kock. . Đường Gosper. . Đường Von Kock bậc hai 3 đoạn.  Các đường thuộc họ đường Peano như: . Đường Peano nguyên thuỷ. . Đường Peano cải tiến. . Tam giác Cesaro.  Đường Sierpinski.  Cây Fractal.  Cây dương xỉ 2 chiều và cây dương xỉ 3 chiều.  Tập Mandelbrot.  Tập Julia.  Đường cong Phoenix. === 45 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  43. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === 3.2. HẠN CHẾ Hình học Fractal bao gồm rất nhiều cấu trúc đường và mặt khác nhau. Do thời gian cĩ hạn nên chương trình vẫn cịn một số đường và mặt vẫn chưa kịp cài đặt. Bên cạnh đĩ chương trình chưa thể hiện được các hiệu ứng như lửa mây v.v Hướng phát triển đề tài: Hình học Fractal cĩ thể cài đặt thêm một số đường và mặt như sau: - Tạo đường Hilbert. - Tạo đường trịn Apolo. - Tạo đường cong Dragon - Tạo các hiệu ứng như lửa, mây - Tạo các dãy núi === 46 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal
  44. Đồ Án Tốt Nghiệp SVTH: Vũ Thế Huy === [1] Michale Barnsly. " Fractal Everywhere ", University of Wisconsin- Madison, 1998. [2] John C.Hart “Fractal Image Compression and the Inverse Problem of Recurrent Iterated Function Systems”. School of EECS, 1995 [3] , " 97-12, 1997. [4] [5] === 47 Đề Tài : Tìm Hiểu Phương Pháp Sinh Ảnh Bằng Fractal