4 คะแนน โดย GN⁺ 2025-05-28 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โปรเจ็กต์โอเพนซอร์สนี้ใช้ 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 ความคิดเห็น

 
GN⁺ 2025-05-28
ความคิดเห็นบน Hacker News
  • รู้สึกว่าเอกสารนี้อธิบายไอเดียง่าย ๆ ให้ดูซับซ้อนเกินจริง

    1. สร้างบิตแมปว่าพิกเซลไหนเปลี่ยนบ้าง โดยพิกเซลที่เปลี่ยนเป็น 1 และพิกเซลที่ไม่เปลี่ยนเป็น 0
    2. แฮชออฟเซ็ตของพิกเซลที่ถูกทำเครื่องหมายเป็น 1 แล้วเพิ่มเข้าไปใน Bloom filter
    3. ดึงอินเด็กซ์ทั้งหมดที่ให้ผลบวกจาก Bloom filter แล้วเก็บเฉพาะข้อมูลพิกเซลของตำแหน่งนั้น ก็จะกู้คืนเฟรมได้ค่อนข้างง่าย
      วิธีนี้คล้ายกับการเก็บส่วนต่างระหว่างสองเฟรมเป็น 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 ตลอดเลยหรือเปล่า

    • แม้กราฟจะไม่ได้แสดง แต่แนวทาง Bloom filter อย่างน้อยก็น่าจะเร็วกว่า gzip ได้
      แต่ยังหาตัวเลขด้านประสิทธิภาพไม่เจอ
  • มีการกล่าวถึง insight สำคัญในบทความว่า "สตริงไบนารีที่มีความหนาแน่นของ 1 ต่ำพอ สามารถบีบอัดได้มีประสิทธิภาพกว่าข้อมูลเดิมด้วยการเก็บแค่ตำแหน่งของ 1"
    ส่วน JPEG, MPEG และอื่น ๆ นั้นเดิมทีจัดเรียงปัญหาใหม่ให้เกิดลำดับ 0 ยาว ๆ และวิธีสแกนบล็อก DCT ก็ถือว่าเป็นนวัตกรรมสำคัญมากในงานบีบอัดวิดีโอแบบนี้

    • DCT และการแปลงสีช่วยย้ายรายละเอียดจิ๋วไปไว้ในความถี่สูง และย้ายเนื้อหาหลักไปไว้ในความถี่ต่ำ
      การบีบอัดก็แค่ทิ้งองค์ประกอบความถี่สูง
      JPEG ยังปรับขนาดด้วย Huffman table ด้วย
      เทคนิคพิเศษเพื่อรวบ 0 ไว้ด้วยกันแทบไม่ได้ใช้มากนัก และการรวม 0 เข้าด้วยกันเองก็ไม่ได้ทำให้ประสิทธิภาพการบีบอัดดีขึ้นมาก

    • เห็นด้วย
      ปัญหาใหญ่ที่สุดของแนวทาง OP คือมันจงใจทิ้งความสัมพันธ์เชิงพื้นที่ของการเปลี่ยนแปลงพิกเซล ซึ่งพบได้บ่อยในวิดีโอทั่วไป
      ที่จริงมันไม่ใช่อะไรเฉพาะกับเฟรมวิดีโอ แต่เป็นการทำให้การบีบอัดผลต่างของบิตสตริงที่มีความยาวเท่ากันกลายเป็นรูปแบบทั่วไป
      มันจะได้ผลก็ต่อเมื่อข้อมูลอินพุตมีความสามารถในการคาดเดาได้พอสมควร (มีโครงสร้างที่ไม่สุ่ม) แต่ถึงอย่างนั้นพอผ่านฟังก์ชันแฮช ข้อมูลก็ถูกผสมจนเสียรูปแบบไป
      โดยเฉพาะแฮชเชิงคริปโตกราฟีที่ทำให้ผลลัพธ์ดูสุ่มโดยสมบูรณ์ ซึ่งไม่เป็นมิตรต่อการบีบอัด

  • สวัสดี HN ผู้เขียนเอง
    หลังจากได้รับฟีดแบ็ก ตอนนี้กำลังทดสอบอย่างเข้มงวดมากขึ้นโดยเน้นวิดีโอ raw และวิดีโอที่มี noise
    ยังเป็นช่วงเริ่มต้น แต่กับวิดีโอ raw ก็ได้ผลลัพธ์ที่ค่อนข้างดีพอสมควร (แต่มี caveat)

    • อัตราการบีบอัด 4.8% (ลดขนาดลง 95.2%)
    • ความเร็วในการบีบอัด: 8.29 เฟรมต่อวินาที
    • ความเร็วในการกู้คืน: 9.16 เฟรมต่อวินาที
    • ต้องใช้ keyframe แค่ 4%
    • รู้สึกว่าแทบไม่สูญเสียข้อมูล (PSNR: 31.10 dB)
      เทียบกับโค้เดกมาตรฐาน
    • Rational Bloom Filter: 4.8%
    • JPEG2000 (ไร้การสูญเสียข้อมูล): 3.7%
    • FFV1 (ไร้การสูญเสียข้อมูล): 36.5%
    • H.265/HEVC: 9.2% (การบีบอัดแบบสูญเสียข้อมูล)
    • H.264: 0.3% (การบีบอัดแบบสูญเสียข้อมูล)

    ข้อจำกัดปัจจุบันและงานต่อไป

    ในการจัดการสี ตอนนี้ยังไม่สามารถทำแบบไร้การสูญเสียข้อมูลระดับบิตได้สมบูรณ์ และมีข้อผิดพลาดทศนิยมเกิดขึ้นในกระบวนการแปลง YUV-BGR (ความต่างเฉลี่ยของพิกเซล ~4.7) รวมถึงการสูญเสียความแม่นยำระหว่างการประมวลผลช่องสัญญาณ BGR หลังการแปลง
    แผนงานถัดไป

    • ประมวลผล YUV โดยตรงโดยไม่ต้องแปลง
    • ทำการจัดเก็บข้อมูลสีแบบไร้การสูญเสียข้อมูลระดับบิต
    • ปรับแต่ง Bloom filter ให้เข้ากับแพตเทิร์น chroma subsampling
    • สร้างระบบตรวจสอบแยกสำหรับแต่ละช่องสี
      อยากพิสูจน์ให้ได้ว่ามันไร้การสูญเสียข้อมูลอย่างสมบูรณ์ในเชิงคณิตศาสตร์
      และกำลังคิดต่อด้วยว่าไอเดีย 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 ทั้งหมด ดังนั้นการเทียบกับตัวบีบอัดแบบสูญเสียข้อมูลน่าจะเหมาะสมกว่า