การบีบอัดวิดีโอแบบไม่สูญเสียด้วย Bloom Filter
(github.com/ross39)- โปรเจ็กต์โอเพนซอร์สนี้ใช้ Bloom Filter เพื่อทำการบีบอัดวิดีโอแบบไม่สูญเสีย
- นำแนวคิด Rational Bloom Filter มาใช้เพื่อก้าวข้ามข้อจำกัดของ Bloom Filter แบบเดิม และสำรวจความเป็นไปได้ของการบีบอัดอย่างมีประสิทธิภาพ
- แตกต่างจาก codec ทั่วไป ตรงที่รับประกันการกู้คืนข้อมูลทั้งหมดได้อย่างสมบูรณ์ในแบบไม่สูญเสีย
- มุ่งเน้นที่ ความแตกต่างระหว่างเฟรม แทนทั้งเฟรม เพื่อให้บีบอัดข้อมูลแบบเบาบางได้อย่างมีประสิทธิภาพ
- ผลการทดลอง ขั้นตอนการตรวจสอบ และคำอธิบายหลักการ ช่วยยืนยันความน่าเชื่อถือในระดับสูง
ภาพรวมโปรเจ็กต์
โปรเจ็กต์โอเพนซอร์สนี้ทดลองบีบอัดวิดีโอแบบไม่สูญเสียด้วยการดัดแปลง Bloom Filter (โครงสร้างข้อมูลที่ใช้ตรวจสอบได้อย่างรวดเร็วและมีประสิทธิภาพว่าค่าหนึ่งอยู่ในเซตหรือไม่) ในเชิงนวัตกรรม โดย codec วิดีโอแบบดั้งเดิมอย่าง H.264 จะเพิ่มอัตราการบีบอัดด้วยการตัดข้อมูลที่ตามนุษย์มองไม่เห็นออกไป แต่วิธีนั้นทำให้สูญเสียความสมบูรณ์ของข้อมูล โปรเจ็กต์นี้สาธิตวิธีลดขนาดไฟล์โดยยังคง การกู้คืนข้อมูลได้อย่างสมบูรณ์แบบ เอาไว้ โดยจุดเด่นทางเทคนิคคือวิธีใช้จำนวนฟังก์ชันแฮชแบบมีเหตุผล (ไม่เป็นจำนวนเต็ม) ของ Bloom Filter และโครงสร้างการบีบอัดแบบอิง เฟรม Δ (ความต่าง)
แนะนำซอร์สโค้ดหลัก
- ไฟล์หลัก: youtube_bloom_compress.py
- สามารถรันเดโมได้ด้วยคำสั่งง่าย ๆ เพียงไม่กี่คำสั่ง
- สำหรับวิดีโอระยะยาวยังมีข้อจำกัดด้านความเร็ว และกำลังปรับแต่งอย่างต่อเนื่อง
พื้นฐานของ Bloom Filter
Bloom Filter ใช้ฟังก์ชันแฮชหลายตัว และต้องการหน่วยความจำน้อยมากในการตรวจสอบว่าค่าหนึ่งอยู่ในเซตหรือไม่ แม้จะยอมให้เกิด false positive ได้บ้าง แต่จะไม่มี false negative เด็ดขาด จึงมีจุดแข็งด้านความน่าเชื่อถือ
นวัตกรรมสำคัญ: Rational Bloom Filter
จำนวนฟังก์ชันแฮชที่เหมาะสมที่สุด (k) ของ Bloom Filter มักไม่ใช่จำนวนเต็ม ดังนั้น Rational Bloom Filter จึงใช้ค่า k* แบบจำนวนจริง:
- ใช้ฟังก์ชันแฮชจำนวน ⌊k*⌋ ตัวเสมอ
- ส่วนที่เหลือจะใช้ฟังก์ชันแฮชเพิ่มแบบความน่าจะเป็น (เช่น ถ้า k* = 2.7 จะใช้แฮชตัวที่สามด้วยความน่าจะเป็น 70%)
- ออกแบบให้การตัดสินใจเชิงความน่าจะเป็นนี้เกิดขึ้นอย่างสอดคล้องกันในแต่ละองค์ประกอบ
วิธีนี้ทำงานได้ถูกต้องทั้งตอนบีบอัดและกู้คืน จึง เพิ่มความน่าเชื่อถือของการบีบอัด
การขยายจาก Bloom Filter ไปเป็นตัวบีบอัด
แนวคิดหลัก คือในสตริงไบนารีที่มีค่า 1 เกิดขึ้นน้อย (ข้อมูลเบาบาง) หากเก็บเฉพาะตำแหน่งของค่า 1 ก็สามารถบันทึกข้อมูลด้วยขนาดที่เล็กกว่าการเก็บทั้งบิตเดิมได้
- ขั้นตอนการบีบอัด:
- ระบุตำแหน่งของค่า 1 ในบิตแมปของ Bloom Filter
- นอกเหนือจาก Bloom Filter จะเก็บบิตค่าที่จำเป็นจริง ๆ (ข้อมูลพยาน) แยกไว้ต่างหาก
- จากการวิเคราะห์เชิงทฤษฎี พบว่าจะเกิดประโยชน์ด้านการบีบอัดเมื่อสัดส่วนของค่า 1 ต่ำกว่า 0.32453
สูตรเทคนิคหลักและการปรับให้เหมาะสม
- นำเสนอสูตรของ k (จำนวนฟังก์ชันแฮช) และ l (ขนาดบิตแมป) ตามระดับความเบาบาง
- สามารถคำนวณพารามิเตอร์ที่เหมาะสมโดยอัตโนมัติตามการกระจายบิตของข้อมูลนำเข้า
วิธีประยุกต์ใช้กับการบีบอัดวิดีโอ
- ดึงเฉพาะการเปลี่ยนแปลง ระหว่างเฟรม (ค่า Δ) แล้วแปลงเป็นเมทริกซ์เบาบางที่ส่วนใหญ่ไม่มีการเปลี่ยนแปลง
- นำเทคนิคการบีบอัดด้วย Bloom Filter ไปใช้กับเมทริกซ์ความต่างแบบเบาบางนี้
- ช่วยเพิ่มประสิทธิภาพการจัดเก็บได้อย่างมากเมื่อเทียบกับการเก็บทั้งเฟรม
ขั้นตอนการตรวจสอบการบีบอัดและการกู้คืน
- คำนวณขนาดของทุกองค์ประกอบที่จำเป็นต่อการกู้คืน เช่น บิตแมปที่บีบอัดแล้ว ข้อมูลพยาน เมทาดาทา และพิกเซลที่เปลี่ยนแปลง
- หลังการกู้คืนในระดับเฟรม จะตรวจสอบว่า ตรงกับต้นฉบับในระดับบิต หรือไม่
- มีทั้งการแสดงภาพและการวัดเชิงปริมาณของความแตกต่างในแต่ละเฟรม พร้อมการตรวจสอบครบทั้งไปป์ไลน์
- การคำนวณอัตราการบีบอัดถูกเขียนไว้อย่างชัดเจนในโค้ด ทำให้ทุกคนสามารถทำซ้ำและตรวจสอบได้
โครงสร้างการบีบอัดแบบพึ่งพาตนเองอย่างสมบูรณ์
- ไม่ต้องใช้พจนานุกรมหรือ lookup table แยกต่างหากในการกู้คืน
- เก็บพารามิเตอร์ของ Bloom Filter และข้อมูลสีทั้งหมดไว้ในไฟล์บีบอัดเอง
- สามารถกู้คืนได้อย่างสมบูรณ์ด้วยไฟล์บีบอัดเพียงอย่างเดียว
บทสรุปและข้อมูลโอเพนซอร์ส
โปรเจ็กต์นี้ใช้ Bloom Filter เพื่อดึงประโยชน์จากความเบาบางของข้อมูลให้ได้มากที่สุด และเหมาะอย่างยิ่งกับงานที่ต้องการการกู้คืนอย่างสมบูรณ์แบบ (เช่น ข้อมูลวิทยาศาสตร์ ภาพทางการแพทย์ เป็นต้น) คุณสามารถทดลองโครงสร้างอัลกอริทึมใหม่และระบบตรวจสอบนี้ได้โดยตรง พร้อมฝากข้อเสนอแนะเพื่อการปรับปรุงต่อไป
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
รู้สึกว่าเอกสารนี้อธิบายไอเดียง่าย ๆ ให้ดูซับซ้อนเกินจริง
วิธีนี้คล้ายกับการเก็บส่วนต่างระหว่างสองเฟรมเป็น x, y, r, g, b แต่แทนที่จะเก็บพิกัด x, y แบบตรง ๆ ก็อัดมันให้แน่นมากขึ้น แล้วไปเก็บ r, g, b มากขึ้นเล็กน้อยแทน
ปกติตำแหน่งพิกเซลที่เปลี่ยนในแต่ละเฟรมมักคล้ายกัน ดังนั้นในเฟรมถัดไป ถ้าตั้งแฟล็กตำแหน่งเดิมให้ดีแล้วค่อยเก็บออฟเซ็ตที่เปลี่ยนเพิ่มเข้าไปอีก ก็น่าจะบีบอัดได้มากขึ้นอีก
นี่แหละคือคอมเมนต์ที่เข้าใจประเด็นจริง ๆ จนผมอ่านคอมเมนต์ก่อนทุกครั้ง
แล้วเพิ่งเห็นว่าคนเขียนคือคนที่ทำ kilo ด้วย เจ๋งมาก
[edit] แม้แต่การแก้ไขเพิ่มเติมก็ยังรู้สึกสนุกดี
อยากรู้ว่าอัตราการบีบอัดจริงออกมาได้เท่าไร
เมื่อก่อนเคยทดลองการบีบอัดภาพแบบ wavelet
หลักการของการแปลงกลับคือเริ่มจากภาพเล็ก ๆ แล้วใช้ค่าสัมประสิทธิ์ขยายขึ้นทีละ 2 เท่า
ข้อมูลส่วนใหญ่คือค่าสัมประสิทธิ์ที่เกือบเป็น 0 และบีบอัดโดยตัดพวกนี้ให้เป็น 0 ไปเลย
แก่นสำคัญคือการเข้ารหัสตำแหน่งที่ไม่เป็น 0 ให้มีประสิทธิภาพ ซึ่งโดยมากค่าพวกนี้จะเกาะกลุ่มกัน และอัลกอริทึมต่าง ๆ ก็อาศัยคุณสมบัตินี้มาก
มันให้คุณสมบัติตรงข้ามกับฟังก์ชันแฮชที่ใช้ใน Bloom filter อย่างสิ้นเชิง
จำได้ว่าวิธีแบบนี้ทั้งตัวทรานส์ฟอร์มเองและการบีบอัดค่าสัมประสิทธิ์ก็ขาดความสัมพันธ์เชิงพื้นที่และช้า สุดท้ายเลยติดเพดานข้อจำกัด
สงสัยว่า Bloom filter มีข้อได้เปรียบอะไรเมื่อเทียบกับ hash table
การบีบอัดวิดีโอส่วนใหญ่เกี่ยวข้องกับ "การเคลื่อนไหว"
ถ้าเป็นกรณีกล้องแพนที่พิกเซลเดิมทั้งชุดเลื่อนไปทางซ้าย 2 พิกเซล แบบนี้จัดการอย่างไร
ถ้าเก็บแค่ delta ระหว่างเฟรม พิกเซลที่ไม่เปลี่ยนทั้งหมดก็จะเป็น 0
การบีบอัดลำดับ 0 ต่อเนื่องเป็นเรื่องที่ง่ายที่สุดอย่างหนึ่งในงานบีบอัดแบบสูญเสียข้อมูล แต่แนวทาง Bloom filter มี false positive อยู่
Bloom filter อาจใช้เป็นกลยุทธ์ย่อยในตัวบีบอัดแบบผสมได้ และการผสมหลายวิธีก็น่าจะดีกว่า แต่โดยเฉลี่ยแล้วไม่คิดว่า Bloom filter จะเพิ่มประสิทธิภาพเหนือวิธีเดิมได้มากนัก
คิดว่าวิธีนี้น่าจะทำงานได้ดีกับวิดีโอที่ผ่านการบีบอัด-คลายบีบอัดมาแล้วอย่างวิดีโอ YouTube
สำหรับอินพุตแบบ raw สมมติฐานที่ว่าพิกเซลส่วนใหญ่แทบไม่เปลี่ยนระหว่างเฟรมต่อเนื่องอาจใช้ไม่ได้
ถ้าเป็นฉากที่สะอาดมาก มี noise ต่ำ และสว่าง ก็อาจใช้ได้ แต่สัญญาณทั่วไปมักมี noise มากกว่า 1 LSB ทำให้บิตล่าง ๆ เปลี่ยนบ่อย
พอผ่านกระบวนการบีบอัด-คลายบีบอัด noise จะลดลง จึงทำให้สมมติฐานนี้กลับมาใช้ได้
จริง ๆ แล้ววิธีนี้ก็ไม่ใช่แบบไร้การสูญเสียข้อมูล
ในโค้ด video_delta_compress.py ถ้าค่าเฉลี่ยการเปลี่ยนแปลงของ r,g,b น้อยกว่า 10 จะไม่เก็บการเปลี่ยนแปลงนั้น
ตัวอย่างเช่น ต่อให้เปลี่ยนจาก pure blue(#00ff00) เป็น pure red(#ff0000) ก็ยังถูกจัดการแบบนี้ ทำให้ทั้งสองเฟรมถูกกู้คืนเป็น pure blue
เหมือนที่การถ่ายภาพไม่ใช้ PNG กัน วิดีโอที่ถ่ายจากหน้างานก็มักไม่ใช้โค้เดกแบบไร้การสูญเสียข้อมูล
วิดีโอแบบไร้การสูญเสียข้อมูลเหมาะกับคอนเทนต์ดิจิทัลอย่างการอัดหน้าจอมากกว่า
ในกรณีแบบนั้นพิกเซลที่เปลี่ยนระหว่างเฟรมมีน้อย สมมติฐานของวิธีนี้จึงค่อนข้างตรง
ในโค้ดใช้กลยุทธ์เก็บเฉพาะตำแหน่งบิต 1 เมื่อสัดส่วนน้อยกว่า 32.4%
ถ้าบิตล่าง ๆ เปลี่ยนบ่อย แต่บิตบนยังเปลี่ยนน้อยพอ วิธีนี้อาจยังใช้ได้อยู่หรือเปล่า ก็เป็นความคิดหนึ่ง
โดยทั่วไปแทบไม่มีใครใช้วิดีโอ raw
โทรศัพท์มือถือและกล้องก็เก็บเป็น MP4, AV1 ฯลฯ โดยปริยาย
เมื่อดูทั้งขนาดไฟล์และภาระในการประมวลผล ก็มีคนจำนวนมากที่ไม่รู้ด้วยซ้ำว่ามีฟอร์แมต raw แบบไม่ผ่านการปรุงแต่งอยู่
เพราะงั้นแนวทางปัจจุบันจึงเหมาะกับงานแอนิเมชัน
จากกราฟ compression_comparison.png ที่เกี่ยวข้อง เลยสงสัยว่าวิธีบีบอัดใหม่นี้แปลว่าประสิทธิภาพด้อยกว่า GZIP ตลอดเลยหรือเปล่า
แต่ยังหาตัวเลขด้านประสิทธิภาพไม่เจอ
มีการกล่าวถึง insight สำคัญในบทความว่า "สตริงไบนารีที่มีความหนาแน่นของ 1 ต่ำพอ สามารถบีบอัดได้มีประสิทธิภาพกว่าข้อมูลเดิมด้วยการเก็บแค่ตำแหน่งของ 1"
ส่วน JPEG, MPEG และอื่น ๆ นั้นเดิมทีจัดเรียงปัญหาใหม่ให้เกิดลำดับ 0 ยาว ๆ และวิธีสแกนบล็อก DCT ก็ถือว่าเป็นนวัตกรรมสำคัญมากในงานบีบอัดวิดีโอแบบนี้
DCT และการแปลงสีช่วยย้ายรายละเอียดจิ๋วไปไว้ในความถี่สูง และย้ายเนื้อหาหลักไปไว้ในความถี่ต่ำ
การบีบอัดก็แค่ทิ้งองค์ประกอบความถี่สูง
JPEG ยังปรับขนาดด้วย Huffman table ด้วย
เทคนิคพิเศษเพื่อรวบ 0 ไว้ด้วยกันแทบไม่ได้ใช้มากนัก และการรวม 0 เข้าด้วยกันเองก็ไม่ได้ทำให้ประสิทธิภาพการบีบอัดดีขึ้นมาก
เห็นด้วย
ปัญหาใหญ่ที่สุดของแนวทาง OP คือมันจงใจทิ้งความสัมพันธ์เชิงพื้นที่ของการเปลี่ยนแปลงพิกเซล ซึ่งพบได้บ่อยในวิดีโอทั่วไป
ที่จริงมันไม่ใช่อะไรเฉพาะกับเฟรมวิดีโอ แต่เป็นการทำให้การบีบอัดผลต่างของบิตสตริงที่มีความยาวเท่ากันกลายเป็นรูปแบบทั่วไป
มันจะได้ผลก็ต่อเมื่อข้อมูลอินพุตมีความสามารถในการคาดเดาได้พอสมควร (มีโครงสร้างที่ไม่สุ่ม) แต่ถึงอย่างนั้นพอผ่านฟังก์ชันแฮช ข้อมูลก็ถูกผสมจนเสียรูปแบบไป
โดยเฉพาะแฮชเชิงคริปโตกราฟีที่ทำให้ผลลัพธ์ดูสุ่มโดยสมบูรณ์ ซึ่งไม่เป็นมิตรต่อการบีบอัด
สวัสดี HN ผู้เขียนเอง
หลังจากได้รับฟีดแบ็ก ตอนนี้กำลังทดสอบอย่างเข้มงวดมากขึ้นโดยเน้นวิดีโอ raw และวิดีโอที่มี noise
ยังเป็นช่วงเริ่มต้น แต่กับวิดีโอ raw ก็ได้ผลลัพธ์ที่ค่อนข้างดีพอสมควร (แต่มี caveat)
เทียบกับโค้เดกมาตรฐาน
ข้อจำกัดปัจจุบันและงานต่อไป
ในการจัดการสี ตอนนี้ยังไม่สามารถทำแบบไร้การสูญเสียข้อมูลระดับบิตได้สมบูรณ์ และมีข้อผิดพลาดทศนิยมเกิดขึ้นในกระบวนการแปลง YUV-BGR (ความต่างเฉลี่ยของพิกเซล ~4.7) รวมถึงการสูญเสียความแม่นยำระหว่างการประมวลผลช่องสัญญาณ BGR หลังการแปลง
แผนงานถัดไป
อยากพิสูจน์ให้ได้ว่ามันไร้การสูญเสียข้อมูลอย่างสมบูรณ์ในเชิงคณิตศาสตร์
และกำลังคิดต่อด้วยว่าไอเดีย lossless compression นี้กับการใช้ Rational Bloom Filter จะนำไปใช้กับงานนอกเหนือจากวิดีโอได้อย่างไร
รู้สึกสับสนกับบรรทัดโค้ดใน video_delta_compress.py
เพราะบรรทัดนี้ ดูเหมือนว่าไม่ว่าจะเป็นการเปลี่ยนจาก #ffffff เป็น #fffffa หรือจาก #ff0000 เป็น #00ff00 การเปลี่ยนแปลงก็อาจถูกทิ้งทั้งหมดตามค่า threshold
หรือว่าผมเข้าใจหน้าที่ของบรรทัดนี้ผิดไปเอง เพราะดูเหมือนโครงสร้างจะไม่บันทึกการเปลี่ยนแปลงของพิกเซลที่เป็น 0 ลงใน Bloom filter เลย
มีการอธิบายวิธีคำนวณอัตราการบีบอัดไว้แล้ว แต่ก็สงสัยว่ามีตัวอย่างอัตราการบีบอัดแบบแย่สุด/เฉลี่ย/ดีที่สุดหรือไม่
(แก้ไข: เห็นแล้วว่ามีตัวอย่างภาพอยู่ในรีโป จึงอยากเสนอว่าใส่ไว้ใน README ก็น่าจะดี)
รีโปยังค่อนข้างรกมาก แต่ในโค้ดก็มีส่วนสร้างกราฟและผลลัพธ์ต่าง ๆ อยู่ด้วย
ต่อไปตั้งใจจะทำการทดสอบและจัดระเบียบผลลัพธ์ให้ดีขึ้นเพื่อขัดเกลาอีกมาก
ตอนนี้ยังเป็น WIP ที่ค่อนข้าง messy อยู่มาก
โค้เดกอย่าง H.264 ก็มีโหมดไร้การสูญเสียข้อมูลได้เหมือนกัน แม้จะไม่ค่อยมีคนใช้แต่ก็ทำได้
เคยใช้งานโหมดไร้การสูญเสียข้อมูลโดยอาศัยฮาร์ดแวร์เร่งความเร็ว NVENC มาก่อน
แต่ฝั่งเล่นกลับค่อนข้างลำบาก จำได้ว่าเล่นได้ด้วย ffplay เท่านั้น ที่เหลือแทบไม่รองรับ
เป็นคอนเซปต์ที่ดี แต่รู้สึกว่าสำหรับสตริงไบนารีแบบ sparse วิธีบีบอัดดั้งเดิมที่มีอยู่แล้วอาจดีกว่า
ดูจากรีโปเหมือนว่าเขาคำนวณอัตราการบีบอัดจากจำนวนส่วนต่างของพิกเซลที่ถูกทิ้งไปมากน้อยแค่ไหน
ตรงนี้น่าสนใจ แต่สิ่งที่สำคัญกว่าจริง ๆ คือการเทียบโดยตรงกับขนาดไบต์เฉลี่ยของแต่ละเฟรมในวิดีโอที่ถูกบีบอัดแบบ YouTube
ถ้าไม่มีข้อมูลนี้ ก็ยากจะรู้ว่าวิธีปัจจุบันมีพัฒนาการด้านประสิทธิภาพจริงหรือไม่
ถ้าอัลกอริทึมนี้เป็นการบีบอัดแบบสูญเสียข้อมูล การเปลี่ยนแปลงเล็กน้อยจะถูกปัดเป็น 0 ทั้งหมด ดังนั้นการเทียบกับตัวบีบอัดแบบสูญเสียข้อมูลน่าจะเหมาะสมกว่า