QOI - การบีบอัดภาพแบบไม่สูญเสียข้อมูล O(n)

<p>&quot;Quite OK Image&quot; <br /> - บีบอัด RGB/RGBA ได้ขนาดใกล้เคียงกับ PNG<br /> → การบีบอัดเร็วกว่า 20x-50x และการคลายบีบอัดเร็วกว่า 3~4x <br /> → โอเพนซอร์สโค้ด C แบบ single header file ขนาด 300 บรรทัด <br /> → อิมพลีเมนเทชันแบบ single-thread ที่เรียบง่ายโดยไม่ใช้ SIMD <br /> - รายละเอียดทางเทคนิค <br /> → เข้ารหัส/ถอดรหัสภาพแบบ single-pass <br /> → แตะทุกพิกเซลเพียงครั้งเดียว และแต่ละพิกเซลจะถูกเข้ารหัสด้วยหนึ่งใน 4 วิธี <br /> ⇨ ถ้าเหมือนกับพิกเซลก่อนหน้าทันที ก็เพิ่ม run-length ของพิกเซลก่อนหน้า; ถ้าต่างกัน ก็แพ็กพิกเซลใหม่ด้วยหนึ่งในอีก 3 วิธีด้านล่าง <br /> ⇨ ถ้าเหมือนกับพิกเซลที่เคยประมวลผลไปแล้ว ก็ใช้ดัชนีของพิกเซลนั้น โดยมีอาร์เรย์เก็บพิกเซลล่าสุด 64 พิกเซลไว้เพื่อการนี้<br /> ⇨ ถ้าต่างจากพิกเซลก่อนหน้าไม่มาก ก็เก็บค่าความต่างของ RGBA <br /> ⇨ ถ้า 3 วิธีข้างต้นใช้ไม่ได้ ก็เก็บค่า RGBA ของพิกเซลนั้น แต่จะเก็บเฉพาะส่วนที่ต่างจากพิกเซลก่อนหน้า </p>

[lifthrasiir]

<p>ถ้าจะพูดแบบเวอร์ไปสักหน่อย QOI ก็คือการเอา zlib ออกจาก PNG แล้วคงไว้แค่การกรองก่อนจะปรับปรุงมันขึ้นมา<br /> <br /> แม้อัลกอริทึมบีบอัดอย่าง zlib/gzip/DEFLATE ที่ PNG ใช้อยู่จะถูกใช้งานอย่างแพร่หลาย แต่ก็เก่าเกินไปจนมีข้อจำกัดด้านประสิทธิภาพอยู่บ้าง และอัลกอริทึมตระกูล LZ77 อย่าง zlib เองก็มีสมมติฐานพื้นฐานว่า “ในบรรดาไบต์ล่าสุด มักมีหลายช่วงที่เป็นลำดับไบต์เดียวกันซ้ำกัน” (เช่น ถ้าอินพุตคือ "to be or not to be" ก็อาศัยข้อเท็จจริงที่ว่าส่วน "to be" ปรากฏสองครั้ง) แต่ภาพเป็นข้อมูลที่สมมติฐานแบบนี้ใช้ได้ไม่ค่อยดีนัก ดังนั้น PNG จึงใช้ zlib แทบจะเฉพาะสำหรับ entropy coding เท่านั้น (แนวทางการบีบอัดโดยอิงความน่าจะเป็นที่ไบต์ถัดไปจะปรากฏ โดยไม่มีบริบทเพิ่มเติมอื่น ๆ) และใช้การกรองอย่างง่ายเป็นขั้นตอนเตรียมข้อมูลเพื่อทำให้ข้อมูลที่จะส่งเข้า zlib สอดคล้องกับสมมติฐานนั้นให้มากที่สุด แต่จริง ๆ แล้วก็ไม่อาจเรียกได้ว่ามีประสิทธิภาพมากนัก<br /> <br /> ในฟอร์แมตภาพแบบไม่สูญเสียข้อมูลสมัยใหม่ โดยหลักแล้วมีแนวทางปรับปรุงเรื่องนี้อยู่สองแบบ คือแนวทางที่ปรับปรุงการทำนายพิกเซลซึ่งสอดคล้องกับการกรองของ PNG (เช่น เพิ่มชนิดของการกรองอย่างมาก หรือใช้การกรองที่ต่างกันกับแต่ละส่วนของภาพ) และแนวทางที่ปรับปรุง entropy coding ซึ่งสอดคล้องกับ zlib ของ PNG วิธีของ QOI ก็คล้ายกัน แต่มีจุดเด่นเพื่อความเรียบง่ายคือไม่ใช้พิกเซลที่อยู่เหนือขึ้นไปจากตำแหน่งปัจจุบันเลยในการทำนายพิกเซล และละทิ้ง entropy coding ไปใช้ delta coding หลายแบบที่อาศัยประสบการณ์เชิงประจักษ์แทน โดยเฉพาะคุณลักษณะแรกนี้ทำให้อัตราการบีบอัดมักด้อยกว่า PNG โดยไม่เกี่ยวกับประสิทธิภาพการบีบอัด/คลายบีบอัด แต่ก็ดูเหมือนว่าจะสามารถปรับปรุงได้หากยอมลดทอนความเรียบง่ายลงเล็กน้อย</p>

[xguru]

<p>โอ ขอบคุณสำหรับคำอธิบายเพิ่มเติมนะครับ น่าสนใจดีครับ</p>

[xguru]

<p>คงจะใช้งานเพื่อแทนที่ฟอร์แมตอื่นได้ยาก แต่โค้ดเรียบง่ายและอธิบายการทำอิมพลีเมนต์ไว้ดี เลยเป็นโค้ดที่อ่านได้เพลินดีครับ<br /> https://github.com/phoboslab/qoi/blob/master/qoi.h<br /> </p>