Information Theory : Channel and Source Coding : Project 1

Subject Project 1: Fractal Image Coding

กำหนดส่ง 11 กุมภาพันธ์ 2009

ได้รับมอบหมายให้ทำรายงานกลุ่ม เรื่อง Fractal Image Coding ซึ่งจะต้องเขียนโปรแกรมจาก Matlab และจัดทำเอกสารเพื่อ Present เรื่องนี้ให้เพื่อนฟังในชั้นเรียน ซึ่ง Fractal Image Coding เป็นหลักการเข้ารหัสรูปภาพโดยใช้หลักการแบ่งเป็นบล็อก และเทียบค่ากับ Domain Box ซึ่งจะมีทั้งหมด 8 รูป สาเหตุที่ได้ 8 รูปเพราะบล็อคแบ่งเป็น 4*4 ซึ่งเมื่อกลับค่าแล้วจะได้ 8 รูป ตัวเองรับหน้าที่เป็นกราฟิกดีไซต์ พวกสร้างภาพค่ะ กว่าจะได้แต่ละภาพเสียเหงื่อไปหลายลิตรเหมือนกัน และก็รับหน้าที่ Endcode เพื่อที่จะนำรูปมาทำ ProwerPoint เครื่องแทบพัง เพราะว่า ใช้ภาพขนาด 256*256 จะใช้เวลานานมาก ซึ่งอาจารย์ประจำวิชาบอกว่า 27 ชม. ถ้าเครื่องดีหน่อยก็ไว้หน่อย ตัวเองได้ทดลองทำแล้ว Run โปรแกรมตั้งแต่ 2 ทุ่มวันที่ 10 กุมภาพันธ์ ถึง บ่ายโมง ของวันที่ 11 กุมภาพันธ์ 2552 เกื่อบไม่ทัน พอรันออกแล้วดีใจมาก ยอมรับแล้วว่าการเข้ารหัสแบบนี้ จะเสียเวลามาก แต่ถ้า Decode จะไว

คำจำกัดความของแฟลคทอล
แฟลคทอลเป็นคณิตศาสตร์ที่เกิดขึ้นใน ค.ศ. 1977 โดยนักวิทยาศาสตร์ชาวเยอรมันชื่อB. Mandelbrot ซึ่งแฟลกทอลที่ใช้จะเป็นเซตของฟังก์ชันที่ปฏิบัติการซ้ำกันหลายๆ ครั้ง บนพื้นที่ที่แตกต่างกันในระนาบเชิงซ้อน (complex Plane) เพราะมีค่าเริ่มต้นแตกต่างกัน จนกระทั่งกลายเป็นฟังก์ชันที่ลู่เข้าสู่ Single value โดยทั่วไปจะรู้จักกันในกลุ่มของเซต Mandelbrot กับ เซต Julia
อีกคำจำกัดความหนึ่ง หมายถึง วัตถุที่มีลักษณะพิเศษคือไม่ว่าจะนำจุดใดของวัตถุ มาขยายด้วยอัตราขยายเท่าใดก็ตาม ภาพที่ปรากฏจะมีรายละเอียดอยู่ภายในเสมอ

ประวัติ
สิ่งที่เรารู้จักกันในนามของแฟรคทอลนั้น ได้ถูกค้นพบมานานก่อนที่คำว่า "แฟรคทอล" จะถูกบัญญัติขึ้นมาใช้เรียกสิ่งเหล่านี้ ในปี ค.ศ. 1872 คาร์ล ไวแยร์สตราสส์ (Karl Weierstrass) ได้ยกตัวอย่างของฟังก์ชัน ที่มีคุณสมบัติ "everywhere continuous but nowhere differentiable" คือ มีความต่อเนื่องที่ทุกจุด แต่ไม่สามารถหาค่าอนุพันธ์ได้ ต่อมาในปี ค.ศ. 1904 เฮลเก ฟอน ค็อค (Helge von Koch) ได้ยกตัวอย่างทางเรขาคณิต ซึ่งได้รับการเรียกขานในปัจจุบันนี้ว่า "เกล็ดหิมะค็อค" (Koch snowflake) ต่อมาในปี ค.ศ. 1938 พอล ปีแอร์ ลาวี (Paul Pierre Lévy) ได้ทำการศึกษา รูปร่างของ กราฟ (curve และ surface) ซึ่งมีคุณสมบัติที่ส่วนประกอบย่อย มีความเสมือนกับโครงสร้างโดยรวมของมัน คือ "Lévy C curve" และ "Lévy dragon curve"

การบีบอัดภาพแบบ Fractal
การบีบอัดรูปภาพแบบแฟรกทัลเป็นวิธีการบีบอัดขนาดของรูปภาพแบบยอมให้มีการสูญเสียข้อมูลได้ (Lossy Image Compression) ที่สามารถบีบอัดข้อมูลรูปภาพให้มีอัตราการบีบอัด ข้อมูล (Compression Ratio) สูงมากได้ โดยที่มีการสูญเสียของข้อมูลจากกระบวนการบีบอัดอยู่ในระดับที่ไม่สูงมากนัก และสามารถถอดรหัสสร้างคืนรูปภาพได้อย่างรวดเร็วด้วยกระบวนการถอดรหัสแบบวนซ้ำ (Iteration Function) แต้มีข้อด้อยคือ กระบวนการเข้ารหัสบีบอัดรูปภาพแบบแฟรกทัลมีความซับซ้อน และใช้เวลาของกระบวนการเข้ารหัสสูงมาก การเข้ารหัสข้อมูลภาพแบบแฟรคทอล ที่นำเสนอโดย Yuval Fisher เป็นการนำทฤษฏี Fractal มาใช้ในการบีบอัดข้อมูลภาพ ซึ่งผลที่ได้เป็นการบีบอัดแบบสูญเสียข้อมูลบางส่วน (Lossy Compression) โดยวิธีการเข้ารหัสข้อมูลภาพแบบแฟรคทอลนี้มีข้อดีคือ มีอัตราการบีบอัดข้อมูล (Compression Ratio) สูง มีคุณภาพของภาพ (Quality of Image) สูง อีกทั้งมีความเร็วในการคืนภาพ (Reconstructed Image) ที่เร็ว และมีความสามารถในการคืนภาพผลลัพธ์ที่ไม่ขึ้นอยู่กับความละเอียด (Resolution Independence) ของภาพ เพราะวิธีการเข้ารหัสข้อมูลภาพแบบแฟรคทอล นั้น ไม่ได้เก็บข้อมูลบางส่วนของภาพแบบวิธีการอื่นๆ แต่จะเป็นการเก็บข้อมูลในรูปแบบของรหัสแฟรคทอล (Fractal Code) ประกอบไปด้วยค่าคงที่ที่ใช้ในการปรับค่าความสว่าง ค่าความคมชัด และรูปแบบที่ใช้ในการเข้ารหัสข้อมูลภาพ จึงทำให้ข้อมูลที่ถูกเก็บมีค่าน้อยเมื่อเปรียบเทียบกับวิธีการอื่นๆ และจะใช้ข้อมูลจากรหัสแฟรคทอลนำมาสร้างภาพขึ้นใหม่ด้วยกระบวนการทำซ้ำ แต่วิธีการเข้ารหัสข้อมูลภาพแบบแฟรคทอลนี้ จะมีข้อเสีย คือใช้เวลาในการเข้ารหัสข้อมูลภาพหรือการบีบอัดข้อมูลภาพที่นานเมื่อเปรียบเทียบกับวิธีการอื่น เพราะต้องใช้เวลาในการหาค่าคงที่ ที่ใช้ในการปรับค่าความสว่าง ความคมชัด และรูปแบบที่ใช้ในการเข้ารหัสภาพของแต่ละส่วนในภาพต้นฉบับ ซึ่ง Yuval Fisher ได้ใช้วิธีการหาค่าคงที่ต่างๆ 2 วิธีด้วยกัน คือการแบ่ง Range Block แบบคงที่ และการ แบ่ง Range Block แบบ Quadtree

การเข้ารหัสข้อมูลภาพแบบ Fractal
การเข้ารหัสข้อมูลภาพแบบแฟรคทอล ที่นำเสนอโดย Fisher เป็นการนำทฤษฎีแฟรคทอลมาใช้ในการบีบอัดข้อมูลภาพ โดยวิธีการเปรียบเทียบข้อมูลระหว่าง Range Block กับกลุ่มของ Domain Block เพื่อเลือก Domain block ที่มีลักษณะ หรือ คุณสมบัติคล้ายและดีที่สุดของแต่ละ Range Block แล้วเก็บค่าคงที่ที่ใช้ในการบรับค่าความสว่าง ความคมชัด และรูปแบบที่ใช้ในการเข้ารหัสภาพ เพื่อจะนำค่าคงที่ที่ได้จากการเข้ารหัสข้อมูลภาพนำมาสร้างภาพขึ้นใหม่ด้วยกระบวนการทำซ้ำ เพื่อความสะดวกในการอธิบายจะใช้วิธีการเข้ารหัสภาพด้วยวิธีการแบ่งแบบ Range Block คงที่ ซึ่งผลที่ได้เป็นการบีบอัดแบบสูญเสียข้อมูลบางส่วนโดยวิธีการเข้ารหัสข้อมูลภาพแบบแฟรคทอลนี้มีข้อดี คือ มีอัตราการบีบอัดข้อมูลสูง คุณภาพของภาพ (Quality of Image) ใกล้เคียงกับภาพต้นฉบับ ความเร็วในการคืนสภาพ (Reconstructed Image) ที่เร็ว ความสามารถในการคืนสภาพผลลัพธ์ที่ไม่ขึ้นอยู่กับความละเอียด (Resolution Independent) ของภาพ เพราะวิธีการเข้ารหัสข้อมูลภาพแบบแฟรคทอลนั้น ไม่ได้เก็บข้อมูลบางส่วนของภาพเหมือนวิธีการอื่นๆ และการเก็บข้อมูลในรูปแบบของรหัสแฟรคทอลประกอบไปด้วยค่าคงที่ที่ใช้ในการปรับค่าความสว่าง ค่าความคมชัดและรูปแบบที่ใช้ในการเข้ารหัสข้อมูลภาพ จึงทำให้ข้อมูลที่ถูกเก็บมีค่าน้อยเมื่อเปรียบเทียบกับวิธีการอื่นๆ แต่วิธีการเข้ารหัสข้อมูลภาพแบบแฟรคทอลใช้เวลาในการเข้ารหัสข้อมูลภาพที่นาน เมื่อเปรียบเทียบกับวิธีการอื่น เพราะต้องใช้เวลาในการหาค่าคงที่ที่ใช้ในการปรับค่าความสว่าง ความคมชัด และรูปแบบที่ใช้ในการเข้ารหัสภาพของแต่ละส่วนในภาพต้นฉบับ

ศึกษาเพิ่มเติมได้ในเว็บนี้นะคะ แต่จะต้องลงโปรแกรม Java ก่อนถึงจะใช้งานได้นะคะ

http://www.eurecom.fr/~image/DEMOS/FRACTAL/english/index.html

ตัวอย่างภาพ Fractal ที่เกิดจากสมการคณิตศาสตร์

สุดท้ายขอขอบคุณเพื่อนๆ ทุกคนที่ร่วมแรงรวมใจที่ทำให้งานครั้งนี้สำเร็จได้ด้วยดี และขอบคุณปอนมากเลยที่เอื้ออำนวยข้อมูลสำหรับทำบล็อกหัวข้อนี้

ธัญนิจ วุฒินาม (เจ้าของบล็อกค่ะ)