- Rational Bloom Filter Video Compression, ham videoyu sıkıştırırken geri yüklenen sonucun kaynakla bit düzeyinde aynı olması gereken kayıpsız bir iş akışı uygular
- Temel fikir, Bloom filtresine tam sayı olmayan sayıda hash fonksiyonu uygulayarak mevcut yöntemlere göre teorik olarak daha iyi sıkıştırma oranı hedefleyen bir yapı kurmaktır
- Y4M, YUV, HDR gibi raw video content üzerinde çalışır ve tipik videolarda %40~50 alan tasarrufu sağladığını belirtir
- Uygulama Python 3.7+ tabanlıdır ve
numpy, opencv-python, xxhash, Pillow, scikit-image, HDR için pyexr gibi bağımlılıklar gerektirir
- FFV1, HuffYUV ve H.264 kayıpsız modu ile karşılaştırmalı benchmark'lar içerir; gerçek kullanım öncesinde
results.md içindeki sonuçlar ve yeniden üretim adımlarının incelenmesi önerilir
Rational Bloom Filter Video Compression genel bakış
- Bu proje, rational Bloom filter tabanlı bir kayıpsız video sıkıştırma yaklaşımını uygular
- Bloom filtresi, ikili veriyi verimli biçimde temsil eden olasılıksal bir veri yapısı olarak kullanılır
- Fark yaratan nokta, Bloom filtresinde tam sayı olmayan rational hash function kullanılmasıdır
- Amaç, sıkıştırma sonrası geri yüklenen sonucun kaynakla bit-exact biçimde eşleşmesidir
Desteklenen içerik ve sıkıştırma özellikleri
- Sıkıştırma sistemi Y4M, YUV, HDR gibi raw video content için tasarlanmıştır
- Sunulan özellikler şunlardır
- Bit düzeyinde aynı geri yüklemeyi garanti eden true lossless compression
- Tipik video içeriklerinde %40~50 alan tasarrufu
- Çok iş parçacıklı kodlama ve kod çözme desteği
- RGB, BGR, YUV gibi birden çok color space desteği
- HDR içerik işleme desteği
- HDR işleme için, “hızlı ve kullanılabilir hale getirmek adına daha fazla çalışma gerektiği” sınırlaması belirtilir
Kurulum gereksinimleri
- Çalışma ortamı Python 3.7+ olmalıdır
- Gerekli paketler şunlardır
numpyopencv-pythonmatplotlibpandastqdmrequestsxxhashPillowscikit-imagepyexr: HDR desteği için
- Bağımlılıklar şu komutla kurulur
pip install -r requirements.txt
Temel kullanım şekli
- Python kodunda
ImprovedVideoCompressor içe aktarılır ve sıkıştırıcı başlatılır
- Örnek ayarlar arasında
noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True, verbose=True bulunur
compress_video(), giriş videosunu .bfvc dosyasına sıkıştırırdecompress_video(), .bfvc dosyasını geri açarverify_lossless() ile kaynak kareler ve geri açılan karelerin kayıpsız olup olmadığı doğrulanır
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']}")
Komut satırı kullanımı
- Video sıkıştırma şu şekilde çalıştırılır
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
- Ham YUV dosyaları genişlik, yükseklik ve format birlikte belirtilerek işlenir
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444
Benchmark ve karşılaştırma hedefleri
- Proje, Rational Bloom Filter sıkıştırmasını diğer kayıpsız sıkıştırma yöntemleri ile karşılaştıran bir benchmark sistemi içerir
- Karşılaştırma hedefleri FFV1, HuffYUV ve H.264'ün kayıpsız modudur
- Tam benchmark'ı çalıştırma komutu şöyledir
python benchmark_compression.py
- Belirli veri kümeleri ve yöntemler seçilerek de çalıştırılabilir
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
- Ayrıntılı benchmark sonuçları ve yeniden üretim yöntemi results.md içinde yer alır
Sıkıştırma yönteminin çalışma akışı
- Sıkıştırma şeması şu adımlarla çalışır
- Frame Extraction: giriş videosundan kareler çıkarılır
- Keyframe Selection: anahtar kareler doğrudan zlib ile sıkıştırılmış kareler olarak saklanır
- Bloom Filter Compression: ara kareler, fark haritası rational Bloom filter ile sıkıştırılır
- Lossless Verification: çözme sırasında bit-exact geri yükleme doğrulanır
- rational Bloom filter, alan ile doğruluk arasındaki dengeyi optimize etmek için tam sayı olmayan hash fonksiyonu sayısı
k* kullanır
- Uygulama,
⌊k*⌋ adet hash fonksiyonunu deterministik olarak kullanır ve ek hash fonksiyonu k* - ⌊k*⌋ olasılığıyla uygulanır
Proje dosya yapısı
improved_video_compressor.py: sıkıştırma algoritmasının main implementationverify_true_lossless.py: kayıpsız geri yüklemeyi doğrulayan betikbenchmark_compression.py: birden fazla sıkıştırma yöntemini karşılaştıran benchmark sistemidownload_*.py: test veri kümesi indirme betikleriresults.md: ayrıntılı benchmark sonuçları ve analiz
Lisans ve atıf
- Lisans MIT License'tır; ayrıntılar
LICENSE dosyasında bulunabilir
- Araştırmada kod kullanıldığında, README içinde yer alan BibTeX biçimindeki citation'ın kullanılması önerilir
1 yorum
Hacker News yorumları
Belgenin çok basit bir fikri iyi açıklayamadığını düşünüyorum. Doğru anladıysam, önce her biti görüntünün bir pikseli olarak gören bir bitmap oluşturuluyor; 0. kareden 1. kareye geçerken değişen piksel 1, değişmeyen 0 yapılıyor.
Ardından 1 olan konumların ofsetleri hash’lenip Bloom filter’a ekleniyor. Böylece ilgili indeksler ve belirli oranda yanlış pozitif indeksler pozitif çıkıyor.
Sonra Bloom filter sorgulanarak pozitif olan tüm indeksler bulunuyor; bu pikseller için değişmiş ham piksel verisi saklanırsa sonraki kare kolayca yeniden oluşturulabiliyor.
İki kare arasındaki deltayı değişen tüm piksellerin x,y,r,g,b değerleri olarak saklayan; ama x,y kısmını büyük ölçüde sıkıştırıp gerekenden biraz daha fazla r,g,b saklayan bir yöntem olarak görülebilir.
0→1 karelerinde değişen piksellerin konumu, çoğu zaman 1→2 karelerinde değişecek konumlara benzer olacağından, sonraki karede uygun bir bayrak ayarlayıp yalnızca öncekinden ek olarak farklılaşan ofsetleri olduğu gibi saklayarak daha da sıkıştırma olasılığı var gibi görünüyor.
Ters dönüşüm, küçük bir piksel görüntüsüyle başlayıp aynı sayıda katsayı kullanarak genişliği ya da yüksekliği iki kat olan bir görüntüye dönüştürür ve bunu tekrar eder.
Kilit nokta, verinin çoğunun katsayılardan oluşması ve bunların çoğunun 0’a yakın olduğu için 0’a itilebilmesiydi. Böyle olunca sorun, 0 olmayan konumların nasıl kodlanacağına dönüşür; bitmap ve 0 olmayan değerler dizisi gibi bir yapı ortaya çıkar.
0 olmayan değerleri kodlayan algoritmaların ihtiyatlılık derecesi farklıydı, ama genelde bu değerlerin epey kümelenmiş olma özelliğinden yararlanıyordu. Bu ise Bloom filter’da kullanılan tipik hash fonksiyonlarının tam tersidir.
Bu tür görüntü sıkıştırma, hem dönüşümün kendisinde hem de katsayı sıkıştırmada yerelliği çok kötü olduğu için yavaştı; bu yüzden bana çıkmaz yol gibi gelmişti.
Bloom filter’ın karmaşık bir hibrit sıkıştırma stratejisinin parçası olarak kullanılabileceğini düşünüyorum. Böyle sıkıştırıcılarda ne kadar çok araç varsa o kadar iyi, ama ortalamada büyük bir iyileşme sağlayacak gibi görünmüyor.
Girdi videosu zaten YouTube’da sıkıştırılıp geri açılmış bir görüntü olduğu için daha iyi çalışıyor gibi görünüyor.
Girdi özgün görüntü olsaydı, “ardışık kareler arasında piksellerin çoğu yalnızca az değişir ya da hiç değişmez; bu yüzden seyrek bir fark matrisi oluşur” varsayımı bozulurdu gibi.
Çok temiz bir sinyalde, örneğin düşük gürültülü sensör ve parlak sahnede mümkün olabilir; ama gerçek dünyadaki çoğu sinyalde gürültü 1 LSB’den büyük olduğundan alt bitlerin en az yarısının değişmesini beklerim.
Videoyu bir kez sıkıştırma ve geri açma sürecinden geçirince bu tür gürültü genelde temizlenir; böylece bu varsayımın geçerli olduğu yapay olarak statik bir görüntü oluşur.
r,g,b değerlerindeki ortalama değişimi 10’dan düşük olan pikseller için farkı saklamıyor gibi görünüyor. O zaman tek bir piksel ardışık karelerde saf maviden (#00ff00) saf kırmızıya (#ff0000) değişse bile, iki kare de saf mavi olarak geri oluşturulabilir.
Kayıpsız video, ekran kaydı gibi dijital içeriklere çok daha uygundur. Ardışık kareler arasında değişen piksel sayısının az olduğu varsayımı da orada daha makuldür.
Bunu özellikle açıp dosya boyutunu ve işlem yükünü göze almadıkları sürece, ham ya da işlenmemiş veri diye bir kavramın hâlâ var olduğunu bile bilmiyor olabilirler.
Daha önce bunu böyle düşünmemiştim.
Ya da bir kamera alıp günlük sahnelerin ham 8K görüntüsünü kendiniz çekebilirsiniz.
Grafik [1]’e göre bu yeni sıkıştırma yöntemi, sadece GZIP kullanmaktan her zaman kesin biçimde daha kötü değil mi?
[1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
“Temel içgörü: İkili bir dizgede 1 yoğunluğu düşükse, özellikle p* ≈ 0.32453’ün altındaysa, ham dizgeyi saklamaktansa yalnızca 1’lerin konumlarını kodlamak daha verimlidir.”
JPEG/MPEG’in yaptığı işin önemli bir bölümü, problemi uzun 0 dizileri oluşturabilecek şekilde yeniden düzenlemektir. DCT bloklarını AC/DC bileşenlerinin konumlarına göre tarama biçimi, birçok video ve görüntü sıkıştırma tekniğindeki en yenilikçi kısımlardan biri olabilir
Daha iyi ifade edersek, bu teknikte video karelerine özgü hiçbir şey yok. Aynı uzunluktaki iki bit dizisi arasındaki farkı sıkıştırmak için de aynı fikir kullanılabilir
Yine de bu problemin mevcut sıkıştırma yöntemlerinden, örneğin iki bloğu birleştirip gzip’lemekten daha iyi olma olasılığı düşük. Sıkıştırmanın işe yaraması için girdi dağılımının, burada farklı bit konumları kümesinin, çok öngörülebilir ve rastgele olmayan bir yapıda olması gerekir; veriyi bir hash fonksiyonundan geçirince bu özellik bozulur. Özellikle kriptografik olarak güçlü hash’lerin amacı, çıktıyı rastgeleden ayırt edilemez hâle getirmektir
DCT ve renk gösterimi dönüşümünün yaptığı şey, ince detayları yüksek frekansa, temel detayları düşük frekansa dönüştürmektir. Bundan sonra görüntü kalitesi ve sıkıştırma oranı, yüksek frekans gösteriminin ne kadarının atıldığına indirgenir
Bunun dışında JPEG, görüntü boyutunu daha da küçültmek için Huffman tabloları kullanır
Bildiğim kadarıyla uzun 0 dizilerini azaltmak için özel bir şey yapmaz. Bu yüzden 0’ları hizalamanın pek büyük faydası olmaz
Şu satır kafamı karıştırıyor: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
Bu durumda sıkıştırma kayıplı sıkıştırma hâline geliyor ve örneğin #ffffff’ten #fffffa’ya geçişi atacak gibi görünüyor. Hemen üstteki satırda piksel verisinin ortalamasını alan kısım da eşikten bağımsız olarak #ff0000’dan #00ff00’a geçişi atacak gibi duruyor
O kod satırının rolünü yanlış mı anlıyorum bilmiyorum. Sonuç maskesinde 0 olanlar Bloom filter’a kodlanmıyor gibi görünüyor
Sıkıştırma oranının nasıl hesaplandığı yazılmış, ama en kötü/ortalama/en iyi sıkıştırma oranı örnekleri de var mı merak ediyorum
Düzenleme: Depoda görsel olduğunu gördüm. README’ye koymak faydalı olabilir
Çok sayıda düzgün test yapıp bunu çok daha somut hâle getirmeyi planlıyorum. Şimdilik çok dağınık bir devam eden iş sayılır
Yazarıyım. Çok iyi geri bildirimler aldığım için bir süre orijinal video ve gürültülü görüntüler üzerinde daha sıkı testlere odaklanmaya karar verdim. Depoyu sık sık güncellemeye devam edeceğim
Henüz çok erken, ama orijinal video testlerinde bazı ipuçlarıyla birlikte oldukça iyi sonuçlar çıktı. Sıkıştırma oranı %4,8, yani boyutta %95,2 azalma; sıkıştırma hızı 8,29fps; açma hızı 9,16fps; keyframe olarak karelerin yalnızca %4’ü gerekiyor; algısal olarak kayıpsız çıktı (PSNR 31,10dB)
Standart codec’lerle karşılaştırınca Rational Bloom Filter %4,8, JPEG2000 kayıpsız %3,7, FFV1 kayıpsız %36,5, H.265/HEVC kayıplı %9,2, H.264 kayıplı %0,3
Mevcut sınırlamalar ve gelecek çalışmalar da var. Sıkıştırma sonuçları umut verici olsa da renk kanalı işlemede henüz gerçekten kayıpsız değil. Mevcut uygulama YUV’den BGR’ye renk uzayı dönüşümü sırasında zorluk yaşıyor; renk uzayı dönüşüm hassasiyeti nedeniyle küçük yuvarlama hataları oluşuyor ve piksel değerlerinde ortalama yaklaşık 4,7’lik bir fark kalıyor
Ayrıca mevcut uygulama, dönüşümden sonra renk kanallarını BGR biçiminde işleyerek ek hassasiyet kaybına yol açıyor
Bundan sonra BGR dönüşümü olmadan doğrudan YUV işlemeyi, renk verisini bit düzeyinde tam doğrulukla ele almayı, krominans alt örnekleme desenlerine göre Bloom filter parametrelerini ayarlamayı ve her renk kanalını bağımsız olarak doğrulayan özel bir sistem oluşturmayı planlıyorum
Matematiksel olarak kayıpsız olduğunu kanıtlamak istiyorum ama daha gidilecek çok yol var. Bu kayıpsız sıkıştırma fikrini kurcalamaya devam edeceğim; Rational Bloom Filter’ı başka alanlarda kullanmaya dair birkaç fikrim de var
H.264 gibi codec’ler de gerçek kayıpsız modda çalıştırılabilir. Sadece neredeyse kimse öyle kullanmıyor
Sevimli bir kavram, ama seyrek bir ikili dizgeniz varsa geleneksel yöntemlerle daha iyisini yapma olasılığınız yüksek
Depoyu takip etmek zor, ama sıkıştırma oranı ne kadar çok piksel farkının atılabildiğine bakılarak hesaplanıyor gibi görünüyor
İlginç, fakat daha önemli karşılaştırma noktası, sıkıştırılmış YouTube videosunda her karenin ortalama bayt boyutu olurdu. Bu karşılaştırma olmadan mevcut yöntemlere göre bir iyileşme olup olmadığını değerlendirmek zor
Algoritma kayıplıysa, yani küçük farkları 0’a bastırıyorsa, kayıpsız değil; diğer kayıplı algoritmalarla karşılaştırılması gerekir gibi görünüyor