Bloom filtresi kullanılarak kayıpsız video sıkıştırma
(github.com/ross39)- Bu açık kaynak proje, Bloom filtresi kullanarak kayıpsız video sıkıştırmayı gerçekleştiriyor
- Rational Bloom Filter kavramını tanıtarak mevcut Bloom filtrelerinin sınırlarını aşıyor ve verimli sıkıştırma olasılığını araştırıyor
- Genel amaçlı kodeklerden farklı olarak, tüm veriyi eksiksiz geri yükleyen kayıpsız sıkıştırmayı garanti ediyor
- Tüm kare yerine kareler arası farklara odaklanarak seyrek verinin verimli biçimde sıkıştırılmasını sağlıyor
- Deney sonuçları, doğrulama süreci ve ilke açıklamaları sayesinde yüksek güvenilirlik sunuyor
Proje özeti
Bu açık kaynak proje, Bloom filtresini (belirli bir değerin bir kümede bulunup bulunmadığını hızlı ve verimli biçimde doğrulayan bir veri yapısı) yenilikçi biçimde dönüştürerek kayıpsız video sıkıştırmayı deniyor. H.264 gibi geleneksel video kodekleri, insan gözünün fark etmediği bilgileri kaldırarak sıkıştırma oranını yükseltir, ancak bu yöntem bilgi bütünlüğünü kaybettirir. Bu proje ise verinin eksiksiz geri yüklenmesini korurken dosya boyutunu küçültmenin bir yolunu gösteriyor. Özellikle Bloom filtresinde rasyonel (tam sayı olmayan) hash fonksiyonu sayısı kullanımı ve kare Δ (fark) tabanlı sıkıştırma yapısı teknik olarak öne çıkan özellikler.
Başlıca kaynak kod dosyaları
- Çekirdek dosya: youtube_bloom_compress.py
- Basit komut çalıştırmalarıyla demoyu görmek mümkün
- Uzun videolarda hâlâ hız sınırları bulunuyor ve optimizasyon çalışmaları sürüyor
Bloom filtresinin temelleri
Bloom filtresi, bir kümede değer bulunup bulunmadığını sınamak için birden çok hash fonksiyonu kullanır ve çok az bellek gerektirir. Bazı false positive durumlarına izin verir, ancak false negative asla üretmediği için güvenilirlik açısından güçlüdür.
Yenilikçi değişim: Rational Bloom Filter
Bloom filtresinde en uygun hash fonksiyonu sayısı (k) genelde tam sayı değildir. Bu nedenle Rational Bloom Filter, gerçek sayı biçimindeki k* değerini kullanır:
- Her zaman ⌊k*⌋ adet hash fonksiyonu uygulanır
- Kalan kısım kadar ek hash fonksiyonu olasılıksal olarak uygulanır (ör. k* = 2.7 ise üçüncü hash %70 olasılıkla kullanılır)
- Bu olasılıksal kararın her öğe için tutarlı biçimde verilmesi sağlanır
Bu yöntem hem sıkıştırma hem de geri yükleme sırasında doğru şekilde çalışarak sıkıştırma güvenilirliğini artırır
Bloom filtresinden sıkıştırıcıya genişleme
Temel fikir, 1 değerinin seyrek olduğu ikili dizelerde yalnızca 1'lerin konum bilgisini saklayarak veriyi, toplam bitlerin tamamını saklamaktan daha küçük boyutta kaydetmenin mümkün olmasıdır.
- Sıkıştırma aşaması:
- Bloom filtresi bitmap'inde 1'lerin konumları belirtilir
- Bloom filtresine ek olarak gerçekten gerekli bit değerleri (witness verisi) ayrı olarak saklanır
- Kuramsal analiz, 1 oranı 0.32453'ten düşük olduğunda sıkıştırma kazancı oluştuğunu gösterir
Temel teknik formüller ve optimizasyon
- Seyreklik düzeyine göre k (hash fonksiyonu sayısı) ve l (bitmap boyutu) için formüller sunulur
- Girdi verisinin bit dağılımına göre en uygun parametreler otomatik olarak hesaplanabilir
Video sıkıştırmaya uygulama yöntemi
- Kareler arası değişim (Δ değeri) çıkarılarak, çoğunlukla değişim içermeyen seyrek bir matrise dönüştürülür
- Bu seyrek fark matrisi üzerinde Bloom filtresi sıkıştırma tekniği uygulanır
- Tüm kareyi saklamaya kıyasla depolama verimliliği büyük ölçüde artar
Sıkıştırma ve geri yükleme doğrulama süreci
- Sıkıştırılmış bitmap/witness verisi/meta veri/değişen pikseller dâhil, geri yükleme için gereken tüm öğelerin boyutu hesaplanır
- Kare bazında geri yükleme yapıldıktan sonra özgün veriyle bit düzeyinde eşleşme kontrol edilir
- Kare bazında farkların görselleştirilmesi ve nicel analizi ile tüm boru hattı eksiksiz biçimde doğrulanır
- Sıkıştırma oranı hesaplaması kodda açık şekilde tanımlandığı için herkes tarafından yeniden üretilebilir ve doğrulanabilir
Tam anlamıyla kendi kendine yeterli sıkıştırma yapısı
- Geri yükleme için ayrı bir sözlük ya da lookup table gerekmez
- Tüm Bloom filtresi parametreleri ve renk bilgileri sıkıştırılmış dosyanın içinde bulunur
- Yalnızca sıkıştırılmış dosyayla eksiksiz geri yükleme mümkündür
Sonuç ve açık kaynak notu
Bu proje, Bloom filtresiyle veri seyreklik özelliğinden azami düzeyde yararlanıyor ve eksiksiz geri yüklemenin gerekli olduğu işler için (bilimsel veriler, tıbbi görüntüler vb.) uygundur. Yeni algoritma yapısını ve doğrulama sistemini doğrudan deneyebilir, geliştirme önerileri bırakabilirsiniz.
1 yorum
Hacker News yorumları
Bu belgenin aslında basit bir fikri karmaşık şekilde anlattığı hissine kapıldım
Bu yöntem, iki kare arasındaki farkı x, y, r, g, b olarak saklamaya benziyor; ancak x, y koordinatlarını çok daha sıkıştırılmış şekilde saklarken r, g, b için biraz daha fazla veri saklıyor
Genelde kareden kareye değişen piksel konumları benzer olduğu için, sonraki karede bu konum bayraklarını iyi ayarlayıp sadece ek olarak değişen ofsetleri saklayarak daha da fazla sıkıştırma yapılabilir gibi görünüyor
Tam da bu seviyede anlayışlı yorumlar için her zaman önce yorumları okuyorum
Bir de bakıyorum ki yazıyı yazan kişi aynı zamanda kilo’yu yapan kişiymiş, gerçekten harika
[edit] Düzeltme yapma biçimi bile nedense eğlenceli geliyor
Gerçek sıkıştırma oranının ne kadar çıktığını merak ediyorum
Eskiden wavelet tabanlı görüntü sıkıştırmayı denemiştim
Ters dönüşüm, küçük bir görüntüden başlayıp katsayıları kullanarak onu giderek 2 kat büyütme mantığıyla çalışıyordu
Verinin büyük kısmı neredeyse 0 olan katsayılardan oluşuyor ve bunlar 0’a atılarak sıkıştırılıyor
Asıl mesele, 0 olmayan kısımların konumunu verimli biçimde kodlamak; normalde bu değerler kümelenmiş oluyor ve algoritmalar da bu özelliği yoğun şekilde kullanıyor
Bloom filter’daki hash fonksiyonlarında ise bunun tam tersi bir özellik ortaya çıkıyor
Bu yaklaşımda hem dönüşümün kendisi hem de katsayı sıkıştırma uzamsal ilişkiyi kaybedip yavaşladığı için sonunda bir sınıra takılmıştım diye hatırlıyorum
Bloom filter’ın hash table’a kıyasla hangi açıdan daha avantajlı olduğunu merak ediyorum
Video sıkıştırmanın büyük kısmı “hareket” ile ilgilidir
Örneğin kamera pan yaparken aynı piksel 2 piksel sola kayıyorsa bunun nasıl ele alındığını merak ediyorum
Kareler arası sadece delta değişimini saklıyorsan, değişmeyen tüm pikseller 0’dır
Uzun 0 dizilerini sıkıştırmak kayıplı sıkıştırmada en kolay kısımlardan biridir, ama Bloom filter yaklaşımında false positive vardır
Bloom filter da birleşik bir sıkıştırıcının alt stratejilerinden biri olarak kullanılabilir; farklı yöntemleri karıştırmak daha iyi olabilir ama ortalamada Bloom filter’ın mevcut yöntemlere göre performansı büyük ölçüde artıracağını sanmıyorum
Bence bu yöntemin YouTube videosu gibi zaten bir kez sıkıştırılıp açılmış videolarda iyi çalışmasının bir nedeni var
Raw girdide, çoğu pikselin ardışık karelerde neredeyse hiç değişmediği varsayımı bozulabilir
Tamamen temiz, düşük gürültülü, parlak sahnelerde uygulanabilir olabilir ama tipik sinyallerde 1 LSB’den fazla gürültü olduğu için alt bitler sık sık değişir
Sıkıştırma-açma sürecinden geçince gürültü azalır ve bu varsayım daha geçerli hale gelir
Aslında bu yöntem zaten kayıpsız değil
video_delta_compress.py kodunda, r,g,b ortalama değişimi 10’dan küçükse değişim saklanmıyor
Örneğin pure blue(#00ff00)’dan pure red(#ff0000)’a geçişte bile bu şekilde işleniyor ve sonuçta iki kare de pure blue olarak geri oluşturuluyor
Fotoğraf çekerken PNG kullanılmaması gibi, sahadan gelen videolarda da kayıpsız codec pek kullanılmaz
Kayıpsız video daha çok ekran kaydı gibi dijital içeriklere uygundur
Böyle durumlarda kareler arasında değişen piksel sayısı az olduğundan bu yöntemin varsayımı daha iyi tutar
Kodda oran %32.4’ün altındaysa yalnızca bit 1 konumlarını saklama stratejisi kullanılıyor
Alt bitler sık değişse bile üst bitler yeterince az değişiyorsa bu yöntem yine de çalışabilir mi diye düşünüyorum
Genel olarak Raw video kullanan kişi sayısı çok az
Telefonlar ve kameralar da varsayılan olarak MP4, AV1 vb. biçimlerde kaydediyor
Dosya boyutu ve işleme yükü nedeniyle raw, işlenmemiş formatların varlığından bile haberdar olmayan çok insan olduğu yönünde bir algım var
O yüzden mevcut yaklaşım animasyon için uygun gibi duruyor
İlgili compression_comparison.png grafiğine göre, yeni sıkıştırma yöntemi her zaman GZIP’ten daha mı kötü performans veriyor sorusu akla geliyor
Yine de performansla ilgili sayı bulamadım
Metindeki “1 yoğunluğu yeterince düşük olan ikili bir dize, sadece 1’lerin konumunu saklayarak özgün veriden daha verimli biçimde sıkıştırılabilir” ana içgörüsünden söz ediliyor
JPEG, MPEG vb. zaten asıl problemi uzun 0 dizileri oluşturacak şekilde yeniden düzenler; DCT blok tarama yöntemi bu tür video sıkıştırmada çok yenilikçi olmuştur
DCT ve renk dönüşümü, ince ayrıntıları yüksek frekansa, asıl içeriği ise düşük frekansa taşır
Sıkıştırma da yüksek frekans bileşenlerini atma şeklinde olur
JPEG ayrıca Huffman table ile boyutu optimize eder
0’ları bir araya toplamak için özel bir teknik pek kullanılmaz; 0’ların kümelenmesi tek başına sıkıştırma verimini çok artırmaz
Katılıyorum
OP’nin yaklaşımındaki en büyük sorun, normal videoda yaygın olan piksel değişimlerinin uzamsal korelasyonunu aktif biçimde çöpe atması
Hatta bu, video karelerine özel bir yöntemden çok, aynı uzunluktaki bit dizileri arasındaki farkın genel bir sıkıştırması gibi
Girdi verisi öngörülebilirlik taşıdığında, yani rastgeleliği düşük bir yapıya sahip olduğunda etkili olabilir; ama böyle veriler bile hash fonksiyonundan geçince bilgi karışır
Özellikle kriptografik hash’lerde çıktı tamamen rastgeleleştiğinden sıkıştırma için elverişsizdir
Merhaba HN, yazının sahibiyim
Geri bildirimleri aldıktan sonra raw video ve gürültülü videolar üzerinde daha sıkı testler yapıyorum
Hâlâ erken aşamada ama raw videoda fena olmayan sonuçlar çıkıyor (ama caveat var)
Standart codec’lerle karşılaştırma
Mevcut sınırlamalar ve sonraki çalışmalar
Renk işlemede bit düzeyinde tam kayıpsız değil ve YUV-BGR dönüşüm sürecinde kayan nokta hatası oluşuyor (ortalama piksel farkı ~4.7); dönüşüm sonrası BGR kanal işlemede hassasiyet kaybı var
Sonraki çalışma planı
Bunun matematiksel olarak tamamen kayıpsız olduğunu kanıtlamak istiyorum
Bu lossless compression fikrini ve Rational Bloom Filter kullanımını video dışındaki başka alanlarda da düşünüyorum
video_delta_compress.py kod satırı kafamı karıştırıyor
Bu bölüm nedeniyle #ffffff’ten #fffffa’ya geçiş ya da #ff0000’dan #00ff00’a geçiş gibi değişimlerin eşik değerine göre tamamen atıldığı bir yapı var gibi görünüyor
Bu satırın işlevini yanlış mı anlıyorum, yoksa değeri 0 olan piksel değişimleri Bloom filter’a hiç kaydedilmeyen bir yapıda mı
Sıkıştırma oranının nasıl hesaplandığı anlatılmış ama en kötü/ortalama/en iyi sıkıştırma oranı örnekleri var mı merak ediyorum
(Düzeltme: repoda görsel örnekler olduğunu fark ettim, bunları README’ye koyarsan iyi olur)
Repo oldukça dağınık ama kodun içinde grafik vb. üreten kısımlar da var
İleride düzgün testler ve sonuç düzenlemeleri yapıp epey toparlamayı planlıyorum
Şimdilik oldukça dağınık bir WIP aşamasında
H.264 gibi codec’ler de aslında kayıpsız modu destekleyebilir; çok yaygın kullanılmasa da mümkün
NVENC donanım hızlandırmasını kullanarak kayıpsız modu çalıştırmışlığım var
Ama oynatma tarafı zordu; yanlış hatırlamıyorsam sadece ffplay ile çalışıyordu, diğerlerinde neredeyse hiç olmuyordu
Güzel bir konsept ama sparse ikili dizelerde klasik geleneksel sıkıştırma yöntemleri muhtemelen daha iyi olabilir diye düşünüyorum
Repoya bakınca, sıkıştırma oranı sanki piksel farkları içinde ne kadar farkın atıldığına göre hesaplanıyor gibi görünüyor
Bu ilginç, ama pratikte daha önemli olan şey bunu YouTube sıkıştırmalı videolarda her karenin ortalama bayt boyutuyla doğrudan karşılaştırmak
Bu olmadan mevcut yaklaşımın performansta gerçekten iyileşme sağlayıp sağlamadığını anlamak zor
Eğer bu algoritma kayıplı sıkıştırmaysa, küçük farkları topluca 0’a ittiği için kayıplı sıkıştırma yöntemleriyle karşılaştırmak daha uygun olur diye düşünüyorum