Kompresi Video Lossless dengan Bloom Filter

 (github.com/ross39)
4 poin oleh GN⁺ 2025-05-28 | 1 komentar | Bagikan ke WhatsApp
  • Rational Bloom Filter Video Compression mengimplementasikan alur kerja kompresi video mentah sambil memastikan hasil pemulihan identik dengan sumber hingga tingkat bit dalam workflow lossless
  • Intinya adalah menerapkan jumlah fungsi hash non-bilangan bulat pada Bloom filter, dengan struktur yang secara teoretis menargetkan rasio kompresi yang lebih baik dibanding pendekatan lama
  • Menargetkan raw video content seperti Y4M, YUV, dan HDR, serta dijelaskan dapat memberikan penghematan ruang 40~50% pada video umum
  • Implementasinya berbasis Python 3.7+ dan memerlukan dependensi seperti numpy, opencv-python, xxhash, Pillow, scikit-image, serta pyexr untuk HDR
  • Termasuk benchmark yang membandingkan dengan FFV1, HuffYUV, dan mode lossless H.264, sehingga sebelum penggunaan nyata alurnya adalah memeriksa hasil dan prosedur reproduksi di results.md

Gambaran Umum Rational Bloom Filter Video Compression

  • Proyek ini mengimplementasikan metode kompresi video lossless berbasis rational Bloom filter
  • Bloom filter digunakan sebagai struktur data probabilistik untuk merepresentasikan data biner secara efisien
  • Pembeda utamanya adalah penggunaan rational hash function yang bukan bilangan bulat pada Bloom filter
  • Tujuannya adalah agar hasil yang dipulihkan setelah kompresi cocok bit-exact dengan sumber aslinya

Target Dukungan dan Fitur Kompresi

  • Sistem kompresi ini menargetkan raw video content seperti Y4M, YUV, dan HDR
  • Fitur yang disediakan adalah sebagai berikut
    • true lossless compression yang menjamin pemulihan identik hingga tingkat bit
    • penghematan ruang 40~50% pada konten video umum
    • encoding·decoding dengan dukungan multithread
    • dukungan untuk berbagai color space seperti RGB, BGR, dan YUV
    • dukungan pemrosesan konten HDR
  • Untuk HDR ada keterbatasan bahwa “masih perlu pekerjaan lebih lanjut agar cepat dan praktis digunakan”

Persyaratan Instalasi

  • Lingkungan eksekusi adalah Python 3.7+
  • Paket yang dibutuhkan adalah sebagai berikut
    • numpy
    • opencv-python
    • matplotlib
    • pandas
    • tqdm
    • requests
    • xxhash
    • Pillow
    • scikit-image
    • pyexr: untuk dukungan HDR
  • Dependensi diinstal dengan perintah berikut
pip install -r requirements.txt

Cara Penggunaan Dasar

  • Dalam kode Python, impor ImprovedVideoCompressor lalu inisialisasi kompresor
  • Konfigurasi contoh mencakup noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True, verbose=True
  • compress_video() mengompresi video input menjadi file .bfvc
  • decompress_video() memulihkan file .bfvc
  • Gunakan verify_lossless() untuk memverifikasi apakah frame asli dan frame hasil pemulihan benar-benar lossless
from improved_video_compressor import ImprovedVideoCompressor

compressor = ImprovedVideoCompressor(
    noise_tolerance=10.0,
    keyframe_interval=30,
    use_direct_yuv=True,
    verbose=True
)

compressor.compress_video(
    input_file="input_video.y4m",
    output_file="compressed.bfvc"
)

compressor.decompress_video(
    input_file="compressed.bfvc",
    output_file="decompressed.mp4"
)

original_frames = compressor.extract_frames_from_video("input_video.y4m")
decompressed_frames = compressor.decompress_video("compressed.bfvc")
verification = compressor.verify_lossless(original_frames, decompressed_frames)
print(f"Lossless: {verification['lossless']}")

Penggunaan Baris Perintah

  • Kompresi video dijalankan seperti berikut
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
  • File YUV mentah diproses dengan menyertakan lebar, tinggi, dan format
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444

Benchmark dan Target Perbandingan

  • Proyek ini mencakup sistem benchmark yang membandingkan kompresi Rational Bloom Filter dengan metode kompresi lossless lain
  • Target perbandingan adalah FFV1, HuffYUV, dan mode lossless H.264
  • Perintah untuk menjalankan seluruh benchmark adalah sebagai berikut
python benchmark_compression.py
  • Bisa juga dijalankan hanya untuk dataset dan metode tertentu
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
  • Hasil benchmark terperinci dan cara reproduksinya ada di results.md

Alur Kerja Metode Kompresi

  • Skema kompresi bekerja melalui tahapan berikut
    • Frame Extraction: mengekstrak frame dari video input
    • Keyframe Selection: keyframe disimpan sebagai frame yang dikompresi langsung dengan zlib
    • Bloom Filter Compression: inter-frame mengompresi peta perbedaan dengan rational Bloom filter
    • Lossless Verification: memverifikasi pemulihan bit-exact saat decoding
  • Rational Bloom filter menggunakan jumlah fungsi hash non-bilangan bulat k* untuk mengoptimalkan keseimbangan antara ruang dan akurasi
  • Implementasinya menggunakan ⌊k*⌋ fungsi hash secara deterministik, lalu menerapkan satu fungsi hash tambahan dengan probabilitas k* - ⌊k*⌋

Struktur File Proyek

  • improved_video_compressor.py: main implementation dari algoritme kompresi
  • verify_true_lossless.py: skrip untuk memverifikasi pemulihan lossless
  • benchmark_compression.py: sistem benchmark untuk membandingkan beberapa metode kompresi
  • download_*.py: skrip unduhan dataset uji
  • results.md: hasil benchmark terperinci dan analisis

Lisensi dan Sitasi

  • Lisensinya adalah MIT License, dan detailnya dapat dilihat di file LICENSE
  • Jika kode digunakan dalam penelitian, README mengarahkan untuk memakai citation format BibTeX yang disertakan

Bacaan terkait

1 komentar

 
GN⁺ 2025-05-28
Opini Hacker News

  • Sepertinya dokumennya kurang berhasil menjelaskan ide yang sebenarnya sangat sederhana. Kalau pemahaman saya benar, pertama buat bitmap yang melihat setiap bit sebagai piksel pada gambar, lalu saat bergerak dari frame 0 ke frame 1, piksel yang berubah diberi 1, kalau tidak 0.
    Setelah itu, offset dari posisi bernilai 1 di-hash dan dimasukkan ke Bloom filter. Dengan begitu indeks-indeks tersebut dan sejumlah indeks positif palsu dalam proporsi tertentu akan keluar sebagai positif.
    Kemudian kueri Bloom filter untuk menemukan semua indeks yang positif, lalu simpan data piksel mentah yang berubah untuk piksel-piksel itu, sehingga frame berikutnya bisa direkonstruksi dengan mudah.
    Ini bisa dilihat sebagai cara menyimpan delta antara dua frame dalam bentuk x,y,r,g,b untuk semua piksel yang berubah, tetapi bagian x,y dikompresi besar-besaran dan r,g,b disimpan sedikit lebih banyak dari yang diperlukan.
    Karena posisi piksel yang berubah dari frame 0→1 sering kali mirip dengan posisi yang akan berubah dari frame 1→2, tampaknya masih ada ruang untuk kompresi lebih lanjut dengan memasang flag yang sesuai pada frame berikutnya dan hanya menyimpan offset tambahan yang berbeda dari sebelumnya apa adanya.

    • Saya penasaran seberapa bagus rasio kompresi sebenarnya. Ini mengingatkan saya pada eksperimen wavelet untuk kompresi gambar sekitar 22 tahun lalu.
      Transformasi balik dimulai dari gambar piksel kecil, lalu mengubahnya menjadi gambar dengan lebar atau tinggi dua kali lipat menggunakan jumlah koefisien yang sama, dan mengulanginya.
      Intinya adalah sebagian besar data berupa koefisien, dan sebagian besar koefisien itu mendekati 0 sehingga bisa didorong menjadi 0. Maka masalahnya menjadi bagaimana mengodekan posisi yang tidak bernilai 0, dan strukturnya menjadi semacam bitmap plus array nilai non-nol.
      Algoritma untuk mengodekan nilai non-nol berbeda-beda dalam tingkat konservatifnya, tetapi umumnya memanfaatkan sifat bahwa nilai-nilai tersebut cukup bergerombol. Ini justru kebalikan dari fungsi hash umum yang dipakai pada Bloom filter.
      Kompresi gambar seperti ini lambat karena lokalitasnya sangat buruk, baik pada transformasinya sendiri maupun pada kompresi koefisien, sehingga terasa seperti jalan buntu.
    • Kalau menyimpan perubahan delta dari satu frame ke frame berikutnya, piksel yang tidak berubah tinggal 0. Mengompresi deretan 0 adalah salah satu pekerjaan paling sepele dalam kompresi lossless, dan tidak ada positif palsu seperti pada Bloom filter.
      Saya bisa melihat Bloom filter dipakai sebagai bagian dari strategi kompresi hibrida yang kompleks. Untuk kompresor seperti itu, semakin banyak alat semakin baik, tetapi rata-rata saya tidak merasa ini akan memberi peningkatan besar.
    • Saya penasaran apa manfaat Bloom filter dibandingkan sesuatu seperti hash table.
    • Sebagian besar kompresi video berkaitan dengan menangani gerakan. Saya penasaran bagaimana kasus saat piksel yang sama bergeser dua piksel ke kiri karena panning ditangani.

  • Sepertinya ini bekerja lebih baik karena video inputnya sudah berupa video yang dikompresi lalu dipulihkan dari YouTube.
    Kalau inputnya video asli, asumsi bahwa “di antara frame berurutan sebagian besar piksel hanya berubah sedikit, atau tidak berubah sama sekali, sehingga menghasilkan matriks selisih yang sparse” tampaknya akan runtuh.
    Untuk sinyal yang sangat bersih, misalnya sensor rendah noise dan adegan terang, ini mungkin mungkin saja, tetapi pada kebanyakan sinyal dunia nyata, noise lebih besar dari 1 LSB, jadi saya memperkirakan setidaknya sekitar separuh bit bawah akan berubah.
    Jika video sekali melewati proses kompresi dan pemulihan, noise seperti itu cenderung terhapus, sehingga tercipta video yang secara artifisial statis dan asumsi ini menjadi berlaku.

    • Dari kelihatannya, ini juga tampaknya bukan lossless: https://github.com/ross39/new_bloom_filter_repo/blob/main/vi...
      Sepertinya piksel yang perubahan rata-rata nilai r,g,b-nya kurang dari 10 tidak disimpan selisihnya. Kalau begitu, bahkan jika satu piksel berubah dari biru murni (#00ff00) menjadi merah murni (#ff0000) pada frame berurutan, kedua frame bisa direkonstruksi sebagai biru murni.
    • Seperti halnya kita tidak memakai PNG untuk foto, saya rasa orang tidak akan memakai codec video lossless untuk video rekaman dunia nyata.
      Video lossless jauh lebih cocok untuk konten digital seperti rekaman layar. Asumsi bahwa hanya sedikit piksel yang berubah di antara frame berurutan juga lebih masuk akal di sana.
    • Mungkin ini bukan masalah besar karena orang biasa tidak memakai raw. Ponsel dan kamera bagaimanapun menyimpan dalam file seperti MP4 atau AV1.
      Kecuali seseorang sengaja mengaktifkannya dan menanggung ukuran file serta beban pemrosesannya, mereka bahkan mungkin tidak tahu bahwa konsep data asli atau mentah masih ada.
      Saya belum pernah memikirkannya seperti ini sebelumnya.
    • Dengan metode yang sekarang, sepertinya ini akan sangat cocok untuk animasi.
    • Cara malasnya adalah mengunduh video 8K lalu melakukan downsampling ke sekitar 720p.
      Atau beli kamera dan rekam sendiri video 8K mentah dari adegan sehari-hari.

  • Menurut grafik [1], bukankah metode kompresi baru ini selalu secara ketat lebih buruk daripada sekadar memakai GZIP?
    [1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...

    • Meski tidak ada di grafik, metode Bloom filter setidaknya mungkin lebih cepat daripada gzip. Namun saya juga tidak bisa menemukan metrik kinerja di tempat lain.

  • “Wawasan utama: jika kepadatan angka 1 dalam string biner rendah, terutama di bawah p* ≈ 0,32453, lebih efisien mengodekan hanya posisi angka 1 daripada menyimpan string mentah.”
    Sebagian besar hal yang dilakukan JPEG/MPEG adalah menata ulang masalah agar bisa membuat deretan 0 yang panjang. Cara memindai blok DCT sesuai posisi komponen AC/DC mungkin merupakan salah satu bagian paling inovatif dalam berbagai teknik kompresi video dan gambar

    • Cara ini sebenarnya cukup buruk untuk kompresi video. Sebab ia secara aktif membuang lokalitas perubahan piksel yang ada pada video umum
      Dengan kata lain, teknik ini tidak punya sesuatu yang khusus untuk frame video. Ide yang sama juga bisa dipakai untuk mengompresi selisih antara dua bitstream dengan panjang yang sama
      Namun kecil kemungkinan masalah ini lebih baik daripada metode kompresi yang sudah ada, misalnya menggabungkan dua blok lalu menjalankan gzip. Agar bisa dikompresi, distribusi input—dalam hal ini himpunan posisi bit yang berbeda—harus sangat dapat diprediksi dan tidak acak, tetapi ketika data dilewatkan ke fungsi hash, sifat itu rusak. Terutama hash yang kuat secara kriptografis memang bertujuan membuat output tidak dapat dibedakan dari acak
    • Menurut saya penjelasan itu tidak tepat
      Yang dilakukan DCT dan transformasi representasi warna adalah mengubah detail halus menjadi frekuensi tinggi, dan detail inti menjadi frekuensi rendah. Setelah itu kualitas gambar dan rasio kompresi menjadi sederhana: seberapa banyak representasi frekuensi tinggi yang dibuang
      Selain itu, JPEG memakai tabel Huffman untuk lebih mengurangi ukuran gambar
      Sejauh yang saya tahu, tidak ada hal khusus yang dilakukan untuk mengurangi deretan 0 yang panjang. Jadi menyelaraskan 0 dalam satu baris tidak banyak membantu

  • Baris ini membingungkan: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
    Dengan begitu, kompresinya menjadi kompresi lossy, dan misalnya sepertinya akan membuang transisi dari #ffffff ke #fffffa. Bagian yang mengambil rata-rata data piksel di baris tepat di atasnya juga tampaknya akan membuang transisi dari #ff0000 ke #00ff00 terlepas dari ambang batasnya
    Entah saya salah memahami peran baris kode itu. Yang menjadi 0 pada mask hasil tampaknya tidak dienkode ke Bloom filter

  • Cara menghitung rasio kompresi sudah tertulis, tetapi saya penasaran apakah ada contoh rasio kompresi terburuk, rata-rata, dan terbaik
    Edit: saya melihat ada gambar di repositori. Mungkin akan membantu kalau dimasukkan ke README

    • Saya penulisnya. Repositori ini memang benar-benar berantakan, tetapi kalau Anda bersedia mengorek kodenya, ada kode untuk membuat grafik dan semacamnya
      Saya berencana melakukan banyak pengujian yang layak agar hasilnya jauh lebih konkret. Saat ini masih sangat berantakan dan lebih mirip pekerjaan yang sedang berjalan

  • Saya penulisnya. Setelah mendapat banyak masukan bagus, untuk sementara saya memutuskan fokus pada pengujian yang lebih ketat terhadap video asli dan video yang mengandung noise. Repositori akan terus sering diperbarui
    Masih sangat awal, tetapi dalam pengujian video asli hasilnya cukup bagus, dengan beberapa catatan. Rasio kompresi 4,8%, yaitu pengurangan ukuran 95,2%, kecepatan kompresi 8,29fps, kecepatan dekompresi 9,16fps, keyframe hanya perlu 4% dari frame, dan output yang secara perseptual lossless (PSNR 31,10dB)
    Dibandingkan codec standar: Rational Bloom Filter 4,8%, JPEG2000 lossless 3,7%, FFV1 lossless 36,5%, H.265/HEVC lossy 9,2%, H.264 lossy 0,3%
    Ada juga batasan saat ini dan pekerjaan mendatang. Hasil kompresinya menjanjikan, tetapi dalam pemrosesan kanal warna masih belum benar-benar lossless. Implementasi saat ini mengalami kesulitan dalam proses konversi ruang warna dari YUV ke BGR, dan karena presisi konversi ruang warna, muncul kesalahan pembulatan kecil sehingga masih tersisa selisih nilai piksel rata-rata sekitar 4,7
    Selain itu, implementasi saat ini memproses kanal warna dalam format BGR setelah konversi, yang menyebabkan kehilangan presisi tambahan
    Ke depannya saya berencana memproses YUV secara langsung tanpa konversi BGR, menangani data warna secara akurat pada tingkat bit, menyetel parameter Bloom filter sesuai pola subsampling kroma, dan membuat sistem khusus untuk memverifikasi tiap kanal warna secara independen
    Saya ingin membuktikannya lossless secara matematis, tetapi jalan masih panjang. Saya berencana terus menggali ide kompresi lossless ini, dan juga punya beberapa ide untuk menerapkan Rational Bloom Filter di bidang lain

  • Codec seperti H.264 juga bisa dijalankan dalam mode benar-benar lossless. Hanya saja hampir tidak ada yang menggunakannya seperti itu

    • Saya pernah membuatnya sampai memakai akselerasi hardware dengan NVENC. Namun pemutarannya sulit; ffplay bisa, tetapi yang lain tidak

  • Konsepnya memang menarik, tetapi kalau ada string biner sparse, kemungkinan besar metode tradisional bisa melakukannya lebih baik

  • Repositorinya sulit diikuti, tetapi rasio kompresi tampaknya dihitung dengan melihat seberapa banyak selisih piksel yang bisa dibuang
    Ini menarik, tetapi pembanding yang lebih penting adalah ukuran byte rata-rata tiap frame pada video YouTube yang sudah dikompresi. Tanpa perbandingan ini, sulit menilai apakah ini perbaikan dibanding metode yang ada
    Jika algoritmanya bersifat lossy, yaitu menekan selisih kecil menjadi 0, maka sepertinya ini bukan lossless dan harus dibandingkan dengan algoritma lossy lain