QOI - การบีบอัดภาพแบบไม่สูญเสียข้อมูล O(n)
(phoboslab.org)"Quite OK Image"
- บีบอัด RGB/RGBA ได้ขนาดใกล้เคียงกับ PNG
→ การบีบอัดเร็วกว่า 20x-50x และการคลายบีบอัดเร็วกว่า 3~4x
→ โอเพนซอร์สโค้ด C แบบ single header file ขนาด 300 บรรทัด
→ อิมพลีเมนเทชันแบบ single-thread ที่เรียบง่ายโดยไม่ใช้ SIMD
- รายละเอียดทางเทคนิค
→ เข้ารหัส/ถอดรหัสภาพแบบ single-pass
→ แตะทุกพิกเซลเพียงครั้งเดียว และแต่ละพิกเซลจะถูกเข้ารหัสด้วยหนึ่งใน 4 วิธี
⇨ ถ้าเหมือนกับพิกเซลก่อนหน้าทันที ก็เพิ่ม run-length ของพิกเซลก่อนหน้า; ถ้าต่างกัน ก็แพ็กพิกเซลใหม่ด้วยหนึ่งในอีก 3 วิธีด้านล่าง
⇨ ถ้าเหมือนกับพิกเซลที่เคยประมวลผลไปแล้ว ก็ใช้ดัชนีของพิกเซลนั้น โดยมีอาร์เรย์เก็บพิกเซลล่าสุด 64 พิกเซลไว้เพื่อการนี้
⇨ ถ้าต่างจากพิกเซลก่อนหน้าไม่มาก ก็เก็บค่าความต่างของ RGBA
⇨ ถ้า 3 วิธีข้างต้นใช้ไม่ได้ ก็เก็บค่า RGBA ของพิกเซลนั้น แต่จะเก็บเฉพาะส่วนที่ต่างจากพิกเซลก่อนหน้า
3 ความคิดเห็น
ถ้าจะพูดแบบเวอร์ไปสักหน่อย QOI ก็คือการเอา zlib ออกจาก PNG แล้วคงไว้แค่การกรองก่อนจะปรับปรุงมันขึ้นมา
แม้อัลกอริทึมบีบอัดอย่าง zlib/gzip/DEFLATE ที่ PNG ใช้อยู่จะถูกใช้งานอย่างแพร่หลาย แต่ก็เก่าเกินไปจนมีข้อจำกัดด้านประสิทธิภาพอยู่บ้าง และอัลกอริทึมตระกูล LZ77 อย่าง zlib เองก็มีสมมติฐานพื้นฐานว่า “ในบรรดาไบต์ล่าสุด มักมีหลายช่วงที่เป็นลำดับไบต์เดียวกันซ้ำกัน” (เช่น ถ้าอินพุตคือ "to be or not to be" ก็อาศัยข้อเท็จจริงที่ว่าส่วน "to be" ปรากฏสองครั้ง) แต่ภาพเป็นข้อมูลที่สมมติฐานแบบนี้ใช้ได้ไม่ค่อยดีนัก ดังนั้น PNG จึงใช้ zlib แทบจะเฉพาะสำหรับ entropy coding เท่านั้น (แนวทางการบีบอัดโดยอิงความน่าจะเป็นที่ไบต์ถัดไปจะปรากฏ โดยไม่มีบริบทเพิ่มเติมอื่น ๆ) และใช้การกรองอย่างง่ายเป็นขั้นตอนเตรียมข้อมูลเพื่อทำให้ข้อมูลที่จะส่งเข้า zlib สอดคล้องกับสมมติฐานนั้นให้มากที่สุด แต่จริง ๆ แล้วก็ไม่อาจเรียกได้ว่ามีประสิทธิภาพมากนัก
ในฟอร์แมตภาพแบบไม่สูญเสียข้อมูลสมัยใหม่ โดยหลักแล้วมีแนวทางปรับปรุงเรื่องนี้อยู่สองแบบ คือแนวทางที่ปรับปรุงการทำนายพิกเซลซึ่งสอดคล้องกับการกรองของ PNG (เช่น เพิ่มชนิดของการกรองอย่างมาก หรือใช้การกรองที่ต่างกันกับแต่ละส่วนของภาพ) และแนวทางที่ปรับปรุง entropy coding ซึ่งสอดคล้องกับ zlib ของ PNG วิธีของ QOI ก็คล้ายกัน แต่มีจุดเด่นเพื่อความเรียบง่ายคือไม่ใช้พิกเซลที่อยู่เหนือขึ้นไปจากตำแหน่งปัจจุบันเลยในการทำนายพิกเซล และละทิ้ง entropy coding ไปใช้ delta coding หลายแบบที่อาศัยประสบการณ์เชิงประจักษ์แทน โดยเฉพาะคุณลักษณะแรกนี้ทำให้อัตราการบีบอัดมักด้อยกว่า PNG โดยไม่เกี่ยวกับประสิทธิภาพการบีบอัด/คลายบีบอัด แต่ก็ดูเหมือนว่าจะสามารถปรับปรุงได้หากยอมลดทอนความเรียบง่ายลงเล็กน้อย
โอ ขอบคุณสำหรับคำอธิบายเพิ่มเติมนะครับ น่าสนใจดีครับ
คงจะใช้งานเพื่อแทนที่ฟอร์แมตอื่นได้ยาก แต่โค้ดเรียบง่ายและอธิบายการทำอิมพลีเมนต์ไว้ดี เลยเป็นโค้ดที่อ่านได้เพลินดีครับ
https://github.com/phoboslab/qoi/blob/master/qoi.h