Kompresi Video Lossless dengan Bloom Filter
(github.com/ross39)- Proyek open source ini mewujudkan kompresi video lossless dengan memanfaatkan Bloom filter
- Dengan memperkenalkan konsep Rational Bloom Filter, proyek ini mengatasi keterbatasan Bloom filter konvensional dan mengeksplorasi kemungkinan kompresi yang efisien
- Berbeda dari codec umum, pendekatan ini menjamin kompresi lossless yang memulihkan seluruh data secara sempurna
- Dengan berfokus pada perbedaan antar-frame, bukan seluruh frame, proyek ini mencapai kompresi data sparse secara efisien
- Hasil eksperimen, prosedur verifikasi, dan penjelasan prinsipnya memberikan tingkat keandalan yang tinggi
Ikhtisar Proyek
Proyek open source ini mencoba kompresi video lossless dengan memodifikasi Bloom filter secara inovatif (struktur data yang memverifikasi dengan cepat dan efisien apakah suatu nilai termasuk dalam himpunan). Codec video tradisional seperti H.264 meningkatkan rasio kompresi dengan membuang informasi yang tidak terlihat oleh mata manusia, tetapi metode tersebut mengorbankan integritas informasi. Proyek ini mendemonstrasikan cara mengurangi ukuran berkas sambil tetap mempertahankan pemulihan data yang sempurna. Secara khusus, penggunaan jumlah fungsi hash rasional (non-bilangan bulat) pada Bloom filter dan struktur kompresi berbasis frame Δ (selisih) merupakan keunggulan teknis utamanya.
Panduan Kode Sumber Utama
- Berkas inti: youtube_bloom_compress.py
- Demo dapat dijalankan hanya dengan mengeksekusi perintah sederhana
- Untuk video berdurasi panjang masih ada keterbatasan dari sisi kecepatan, dan optimisasi berkelanjutan masih berlangsung
Dasar-Dasar Bloom Filter
Bloom filter menggunakan beberapa fungsi hash dan hanya membutuhkan memori yang sangat kecil untuk memeriksa apakah suatu nilai ada di dalam himpunan. Beberapa false positive dapat ditoleransi, tetapi tidak pernah menghasilkan false negative, sehingga unggul dalam menjamin keandalan.
Perubahan Inovatif: Rational Bloom Filter
Jumlah fungsi hash optimal (k) pada Bloom filter biasanya bukan bilangan bulat. Karena itu, Rational Bloom Filter memanfaatkan nilai k* bertipe riil:
- Selalu menerapkan ⌊k*⌋ fungsi hash
- Menerapkan fungsi hash tambahan secara probabilistik sebesar sisa nilainya (mis. jika k* = 2.7, hash ketiga digunakan dengan probabilitas 70%)
- Dirancang agar keputusan probabilistik ini dilakukan secara konsisten untuk setiap elemen
Pendekatan ini bekerja akurat baik saat kompresi maupun pemulihan, sehingga meningkatkan keandalan kompresi
Perluasan dari Bloom Filter menjadi Kompresor
Ide utamanya adalah bahwa pada binary string sparse, di mana angka 1 jarang muncul, data dapat direkam dengan ukuran lebih kecil daripada seluruh bit asli jika hanya informasi posisi angka 1 yang disimpan.
- Tahap kompresi:
- Menandai posisi angka 1 pada bitmap Bloom filter
- Selain Bloom filter, menyimpan secara terpisah nilai bit yang benar-benar diperlukan (data saksi)
- Berdasarkan analisis teoretis, keuntungan kompresi muncul ketika rasio angka 1 kurang dari 0.32453
Rumus Teknik Inti dan Optimisasi
- Menyajikan rumus k (jumlah fungsi hash) dan l (ukuran bitmap) berdasarkan tingkat sparsity
- Parameter optimal dapat dihitung secara otomatis sesuai distribusi bit pada data masukan
Cara Penerapan pada Kompresi Video
- Hanya mengekstrak perubahan antar-frame (nilai Δ), lalu mengubahnya menjadi matriks sparse yang sebagian besar tidak berubah
- Menerapkan teknik kompresi Bloom filter pada matriks selisih sparse ini
- Efisiensi penyimpanan meningkat signifikan dibandingkan menyimpan seluruh frame
Prosedur Verifikasi Kompresi dan Pemulihan
- Menghitung ukuran semua item yang diperlukan untuk pemulihan, seperti bitmap terkompresi, data saksi, metadata, dan piksel yang berubah
- Setelah dipulihkan per frame, dilakukan pemeriksaan apakah hasilnya identik hingga tingkat bit dengan data asli
- Visualisasi dan kuantifikasi perbedaan per frame, serta verifikasi menyeluruh atas seluruh pipeline telah dilakukan
- Perhitungan rasio kompresi dijelaskan dengan jelas di dalam kode sehingga siapa pun dapat mereproduksi dan memverifikasinya
Struktur Kompresi yang Sepenuhnya Mandiri
- Tidak memerlukan kamus atau lookup table terpisah untuk pemulihan
- Semua parameter Bloom filter dan informasi warna disimpan sendiri di dalam berkas kompresi
- Pemulihan sempurna dimungkinkan hanya dengan berkas kompresi
Penutup dan Panduan Open Source
Proyek ini memaksimalkan pemanfaatan sparsity data dengan menggunakan Bloom filter, sehingga sangat cocok untuk tugas yang memerlukan pemulihan sempurna, seperti data ilmiah dan citra medis. Anda dapat langsung bereksperimen dengan struktur algoritme baru dan sistem verifikasinya, serta memberikan masukan untuk perbaikan.
1 komentar
Komentar Hacker News
Menurut saya dokumen ini sebenarnya terasa seperti menjelaskan ide yang sederhana dengan cara yang rumit
Cara ini mirip dengan menyimpan perbedaan dua frame sebagai x, y, r, g, b, tetapi alih-alih menyimpan koordinat x, y secara sangat terkompresi, metode ini menyimpan r, g, b sedikit lebih banyak
Karena biasanya posisi piksel yang berubah di tiap frame mirip, tampaknya ada kemungkinan kompresi lebih lanjut dengan cukup menyetel flag posisi tersebut dengan baik pada frame berikutnya, lalu hanya menyimpan offset tambahan yang benar-benar berubah
Inilah tepatnya jenis komentar yang berwawasan tinggi yang membuat saya selalu membaca komentar dulu
Dan ternyata penulisnya juga orang yang membuat kilo, keren sekali
[edit] Entah kenapa bahkan bagian menyuntingnya juga terasa menyenangkan
Saya penasaran berapa rasio kompresi yang benar-benar dihasilkan
Dulu saya pernah bereksperimen dengan kompresi gambar berbasis wavelet
Transformasi baliknya dimulai dari gambar kecil lalu diperbesar dua kali lipat sedikit demi sedikit menggunakan koefisien
Sebagian besar datanya adalah koefisien yang hampir 0, dan itu dikompresi dengan membuang yang 0
Kuncinya adalah mengenkode posisi bagian yang tidak nol secara efisien, dan biasanya nilai-nilai ini berkelompok sehingga algoritme banyak memanfaatkan sifat itu
Itu adalah karakteristik yang sepenuhnya berlawanan dengan fungsi hash yang dipakai Bloom filter
Saya ingat pendekatan seperti ini akhirnya mentok karena baik transformasinya maupun kompresi koefisiennya kurang memiliki keterkaitan spasial dan lambat
Saya penasaran apa keunggulan Bloom filter dibanding tabel hash dalam kasus ini
Sebagian besar kompresi video berkaitan dengan ‘gerakan’
Saya penasaran bagaimana ini menangani kasus seperti panning kamera, saat piksel yang sama bergeser 2 piksel ke kiri
Jika yang disimpan hanya perubahan delta antar-frame, maka semua piksel yang tidak berubah adalah 0
Mengompresi rangkaian 0 yang berurutan adalah bagian termudah dalam kompresi lossy, tetapi pendekatan Bloom filter memiliki false positive
Bloom filter mungkin bisa dipakai sebagai salah satu strategi bawahan dalam kompresor gabungan, dan mencampur berbagai metode mungkin lebih baik, tetapi secara rata-rata saya ragu Bloom filter akan sangat meningkatkan performa dibanding pendekatan yang ada
Saya rasa ada alasan kenapa pendekatan ini bekerja baik pada video seperti video YouTube yang sudah pernah dikompresi-dekompresi sekali
Pada input raw, asumsi bahwa sebagian besar piksel hampir tidak berubah antar-frame bisa saja tidak berlaku
Pada adegan yang benar-benar bersih, minim noise, dan terang mungkin ini berlaku, tetapi sinyal pada umumnya punya banyak noise lebih dari 1 LSB sehingga bit-bit bawah akan sering berubah
Setelah melalui proses kompresi-dekompresi, noise berkurang sehingga asumsi tersebut menjadi lebih sesuai
Faktanya, pendekatan ini juga tidak lossless
Dalam kode video_delta_compress.py, perubahan tidak disimpan jika rata-rata perubahan r,g,b kurang dari 10
Misalnya saat berubah dari pure blue(#00ff00) ke pure red(#ff0000), ini juga akan diproses seperti itu, sehingga kedua frame bisa dipulihkan sebagai pure blue
Sama seperti orang tidak memakai PNG untuk memotret, codec lossless juga jarang dipakai untuk video dunia nyata
Video lossless lebih cocok untuk konten digital seperti rekaman layar
Dalam kasus seperti itu, jumlah piksel yang berubah antar-frame memang sedikit sehingga asumsi metode ini lebih cocok
Di dalam kode, jika rasionya kurang dari 32.4%, strategi yang dipakai adalah menyimpan hanya posisi bit 1
Kalau bit bawah sering berubah pun, mungkin pendekatan ini tetap bisa bekerja selama bit atas cukup jarang berubah?
Secara umum, hampir tidak ada orang yang memakai video raw
Ponsel dan kamera pun pada dasarnya menyimpan dalam format seperti MP4, AV1, dan sebagainya
Dengan mempertimbangkan ukuran file dan beban pemrosesan, banyak orang bahkan mungkin tidak sadar bahwa format raw yang belum diproses itu ada
Jadi pendekatan saat ini tampaknya cocok untuk animasi
Melihat grafik terkait compression_comparison.png, saya bertanya-tanya apakah itu berarti metode kompresi baru ini selalu kalah performa dibanding GZIP
Hanya saja saya tidak menemukan angka performanya
Disebutkan insight kunci di artikel bahwa “string biner dengan densitas 1 yang cukup rendah dapat dikompresi lebih efisien daripada data aslinya hanya dengan menyimpan posisi 1”
JPEG, MPEG, dan lain-lain pada dasarnya menata ulang masalah agar 0 menjadi berurutan panjang, dan metode pemindaian blok DCT adalah inovasi yang sangat besar dalam kompresi video seperti ini
DCT dan transformasi warna mengubah detail halus menjadi frekuensi tinggi, dan konten utama menjadi frekuensi rendah
Kompresi lalu bekerja dengan membuang komponen frekuensi tinggi
JPEG juga mengoptimalkan ukuran dengan Huffman table
Tidak banyak teknik khusus untuk mengumpulkan 0, dan hanya karena 0 terkumpul bukan berarti efisiensi kompresinya naik drastis
Setuju
Masalah terbesar dari pendekatan OP adalah ia secara aktif membuang korelasi spasial perubahan piksel yang umum ada pada video biasa
Bahkan ini bukan khusus untuk frame video, melainkan generalisasi kompresi selisih bitstring dengan panjang sama
Ini hanya efektif jika data input punya prediktabilitas, yaitu struktur dengan kerandoman rendah, tetapi bahkan data seperti itu akan tercampur setelah melewati fungsi hash
Terutama hash kriptografis membuat hasilnya berubah sepenuhnya acak, yang tidak menguntungkan untuk kompresi
Halo HN, saya penulisnya
Setelah menerima masukan, saya sedang melakukan pengujian yang lebih ketat dengan fokus pada video raw dan video yang memiliki noise
Masih tahap awal, tetapi hasil pada video raw lumayan bagus (meski ada caveat)
Dibanding codec standar
Keterbatasan saat ini dan pekerjaan selanjutnya
Pemrosesan warna belum sepenuhnya lossless pada level bit, dan proses konversi YUV-BGR menimbulkan galat pecahan (selisih rata-rata piksel ~4.7), dengan hilangnya presisi saat memproses kanal BGR setelah konversi
Rencana kerja berikutnya
Saya ingin membuktikan bahwa ini benar-benar lossless secara matematis
Saya juga sedang memikirkan ide lossless compression ini dan pemanfaatan Rational Bloom Filter di area lain selain video
Saya bingung dengan baris kode video_delta_compress.py ini
Karena bagian ini, perubahan dari #ffffff ke #fffffa, atau dari #ff0000 ke #00ff00, tampaknya semuanya dibuang tergantung ambang batas
Mungkin saya salah memahami peran baris kode ini, tetapi sepertinya perubahan piksel yang menjadi 0 memang sama sekali tidak dicatat ke Bloom filter
Metode penghitungan rasio kompresi memang dijelaskan, tetapi saya penasaran apakah ada contoh rasio kompresi terburuk/rata-rata/terbaik
(Suntingan: saya lihat ada contoh gambar di repo, jadi akan bagus kalau itu dimasukkan ke README)
Repo-nya memang cukup berantakan, tetapi di dalam kode juga ada kode untuk membuat grafik dan sebagainya
Ke depan saya berencana merapikannya banyak dengan pengujian yang benar dan perapian hasil
Sampai sekarang ini masih tahap WIP yang cukup messy
Codec seperti H.264 juga sebenarnya bisa dijalankan dalam mode lossless, meski jarang dipakai
Saya pernah menjalankan mode lossless dengan memanfaatkan akselerasi perangkat keras NVENC
Hanya saja sisi pemutaran cukup sulit; seingat saya hanya berjalan di ffplay dan hampir tidak berfungsi di tempat lain
Konsepnya bagus, tetapi saya rasa untuk string biner yang sparse, metode kompresi tradisional yang sudah ada mungkin lebih baik
Dari repo-nya, tampaknya rasio kompresi dihitung berdasarkan seberapa banyak selisih piksel yang dibuang
Ini memang menarik, tetapi yang lebih penting sebenarnya adalah perbandingan langsung dengan ukuran byte rata-rata tiap frame pada video hasil kompresi YouTube
Tanpa itu, sulit menilai apakah pendekatan saat ini benar-benar memberi peningkatan performa
Jika algoritme ini adalah metode kompresi lossy, karena perbedaan kecil semuanya didorong ke 0, maka membandingkannya dengan kompresi lossy akan lebih tepat