Bloom फ़िल्टर का उपयोग करके lossless वीडियो compression

 (github.com/ross39)
4 पॉइंट द्वारा GN⁺ 2025-05-28 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Rational Bloom Filter Video Compression raw video को compress करते हुए ऐसा lossless workflow लागू करता है जिसमें restore किया गया परिणाम मूल से bit स्तर पर बिल्कुल समान होना चाहिए
  • इसका मुख्य विचार Bloom फ़िल्टर पर non-integer hash function count लागू करना है, ताकि सैद्धांतिक रूप से पारंपरिक तरीकों से बेहतर compression ratio हासिल किया जा सके
  • यह Y4M, YUV, HDR जैसे raw video content को लक्ष्य बनाता है, और सामान्य वीडियो में 40~50% storage बचत देने का दावा करता है
  • implementation Python 3.7+ आधारित है और numpy, opencv-python, xxhash, Pillow, scikit-image, HDR के लिए pyexr जैसी dependencies चाहिए
  • इसमें FFV1, HuffYUV, H.264 lossless mode के साथ तुलना करने वाले benchmarks शामिल हैं, इसलिए वास्तविक उपयोग से पहले results.md में दिए गए नतीजे और reproduction steps देखना उचित है

Rational Bloom Filter Video Compression का अवलोकन

  • यह प्रोजेक्ट rational Bloom filter आधारित lossless video compression विधि को implement करता है
  • Bloom फ़िल्टर को binary data को कुशलतापूर्वक दर्शाने वाली probabilistic data structure के रूप में उपयोग किया जाता है
  • इसकी खास बात यह है कि Bloom फ़िल्टर में integer के बजाय rational hash function का उपयोग किया जाता है
  • लक्ष्य यह है कि compression के बाद restore किया गया परिणाम मूल से bit-exact रूप से मेल खाए

समर्थित सामग्री और compression सुविधाएँ

  • compression system Y4M, YUV, HDR जैसे raw video content को लक्ष्य बनाता है
  • उपलब्ध सुविधाएँ इस प्रकार हैं
    • bit स्तर पर समान restore की गारंटी देने वाला true lossless compression
    • सामान्य वीडियो content में 40~50% storage बचत
    • multi-thread support के साथ encoding और decoding
    • RGB, BGR, YUV जैसे कई color space का समर्थन
    • HDR content processing का समर्थन
  • HDR processing के बारे में सीमा यह है कि इसे “तेज़ और व्यावहारिक” बनाने के लिए अभी और काम चाहिए

installation आवश्यकताएँ

  • execution environment Python 3.7+ है
  • आवश्यक packages इस प्रकार हैं
    • numpy
    • opencv-python
    • matplotlib
    • pandas
    • tqdm
    • requests
    • xxhash
    • Pillow
    • scikit-image
    • pyexr: HDR support के लिए
  • dependencies को नीचे दिए गए कमांड से install किया जा सकता है
pip install -r requirements.txt

बुनियादी उपयोग

  • Python code में ImprovedVideoCompressor import करके compressor को initialize किया जाता है
  • example settings में noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True, verbose=True शामिल हैं
  • compress_video() input video को .bfvc फ़ाइल में compress करता है
  • decompress_video() .bfvc फ़ाइल को restore करता है
  • verify_lossless() से original frames और restored frames के 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']}")

command line उपयोग

  • video compression को इस तरह चलाया जाता है
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
  • raw YUV फ़ाइलों को width, height, format के साथ निर्दिष्ट करके process किया जाता है
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444

benchmark और तुलना के लक्ष्य

  • प्रोजेक्ट में Rational Bloom Filter compression की अन्य lossless compression methods के साथ तुलना करने वाला benchmark system शामिल है
  • तुलना के लक्ष्य FFV1, HuffYUV, H.264 के lossless mode हैं
  • पूरा benchmark चलाने का कमांड इस प्रकार है
python benchmark_compression.py
  • केवल किसी विशेष dataset और method को चुनकर भी चलाया जा सकता है
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
  • विस्तृत benchmark results और reproduction method results.md में हैं

compression विधि का कार्यप्रवाह

  • compression scheme निम्न चरणों में काम करती है
    • Frame Extraction: input video से frames निकाले जाते हैं
    • Keyframe Selection: keyframes को सीधे zlib-compressed frames के रूप में संग्रहीत किया जाता है
    • Bloom Filter Compression: inter frames के difference map को rational Bloom filter से compress किया जाता है
    • Lossless Verification: decoding के दौरान bit-exact restore की जाँच की जाती है
  • rational Bloom filter space और accuracy के बीच संतुलन को optimize करने के लिए non-integer hash function count k* का उपयोग करता है
  • implementation ⌊k*⌋ hash functions को deterministic रूप से उपयोग करता है, और अतिरिक्त hash function को k* - ⌊k*⌋ probability के साथ लागू करता है

प्रोजेक्ट फ़ाइल संरचना

  • improved_video_compressor.py: compression algorithm का main implementation
  • verify_true_lossless.py: lossless restore को verify करने वाली script
  • benchmark_compression.py: कई compression methods की तुलना करने वाला benchmark system
  • download_*.py: test dataset download scripts
  • results.md: विस्तृत benchmark results और analysis

लाइसेंस और citation

  • लाइसेंस MIT License है, और अधिक जानकारी LICENSE फ़ाइल में मिल सकती है
  • शोध में इस code का उपयोग करने पर README में शामिल BibTeX format citation का उपयोग करने का निर्देश दिया गया है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-05-28
Hacker News राय

  • लगता है दस्तावेज़ एक बहुत सरल idea को ठीक से समझा नहीं पाया। अगर मेरी समझ सही है, तो पहले हर bit को image के pixel की तरह मानते हुए एक bitmap बनाया जाता है, और frame 0 से frame 1 पर जाते समय जो pixel बदले हों उन्हें 1, बाकी को 0 रखा जाता है
    फिर जिन positions पर 1 है, उनके offsets को hash करके Bloom filter में डाला जाता है। इससे वे indices और एक निश्चित अनुपात में false-positive indices positive निकलते हैं
    इसके बाद Bloom filter से query करके सभी positive indices ढूंढे जाते हैं, और उन pixels के लिए बदला हुआ raw pixel data store कर दें तो अगला frame आसानी से reconstruct किया जा सकता है
    इसे दो frames के बीच delta को सभी बदले हुए pixels के x,y,r,g,b के रूप में store करने जैसा देख सकते हैं, बस x,y हिस्से को काफी compress किया जाता है और जरूरत से थोड़ा ज्यादा r,g,b store किया जाता है
    frame 0→1 में बदले pixels की positions अक्सर frame 1→2 में बदलने वाली positions जैसी हो सकती हैं, इसलिए अगले frame में उपयुक्त flags set करके और पिछले से अतिरिक्त रूप से अलग हुए offsets ही जस के तस store करें तो और compression की गुंजाइश दिखती है

    • असली compression ratio कितना अच्छा है, यह जानने की इच्छा है। करीब 22 साल पहले image compression के लिए wavelets पर प्रयोग करने की याद आती है
      inverse transform एक छोटी pixel image से शुरू होकर, उसी संख्या के coefficients का उपयोग करते हुए width या height में दोगुनी image में बदलता था, और यह दोहराया जाता था
      मुख्य बात यह थी कि data का ज्यादातर हिस्सा coefficients था, और उनमें से ज्यादातर 0 के करीब होते थे, इसलिए उन्हें 0 की ओर धकेला जा सकता था। तब समस्या यह बनती थी कि non-zero positions को कैसे encode किया जाए, और structure bitmap तथा non-zero values array जैसा हो जाता था
      non-zero values encode करने वाले algorithms conservative होने की degree में अलग-अलग थे, लेकिन आम तौर पर वे इस गुण का फायदा उठाते थे कि ऐसी values काफी clustered होती हैं। यह Bloom filter में इस्तेमाल होने वाले सामान्य hash functions के बिल्कुल उलट है
      इस तरह का image compression transform खुद और coefficient compression दोनों में locality बहुत खराब होने के कारण धीमा था, इसलिए यह dead end जैसा लगा
    • अगर एक frame से अगले frame तक के delta changes store कर रहे हैं, तो जो pixels नहीं बदले वे बस 0 हैं। 0 की runs को compress करना lossless compression में सबसे मामूली काम है, और Bloom filter के विपरीत इसमें false positives भी नहीं होते
      मुझे लगता है Bloom filter किसी जटिल hybrid compression strategy का हिस्सा हो सकता है। ऐसे compressor में जितने ज्यादा tools हों उतना अच्छा, लेकिन औसतन इससे बड़ा सुधार होगा ऐसा नहीं लगता
    • जानना चाहूंगा कि Bloom filter, hash table जैसी चीज़ की तुलना में क्या मदद करता है
    • video compression का बड़ा हिस्सा motion संभालने में होता है। panning की वजह से वही pixel बाईं ओर दो pixels खिसक जाए तो इसे कैसे handle किया जाता है, यह जानना चाहूंगा

  • input video पहले से ही YouTube पर compress होकर फिर restore हुआ video है, इसलिए शायद यह बेहतर काम कर रहा है
    अगर input original video हो, तो “लगातार frames के बीच ज्यादातर pixels थोड़े ही, या बिल्कुल नहीं बदलते, इसलिए sparse difference matrix बनती है” वाली assumption टूट सकती है
    बहुत साफ signal, जैसे low-noise sensor और bright scene हो तो संभव है, लेकिन वास्तविक दुनिया के ज्यादातर signals में noise 1 LSB से ज्यादा होता है, इसलिए lower bits में से कम से कम लगभग आधे बदलने की उम्मीद है
    video को compression और restoration process से एक बार गुजारने पर ऐसा noise हटने की प्रवृत्ति होती है, जिससे इस assumption को पूरा करने वाला कृत्रिम रूप से static video बनता है

    • देखने में यह भी lossless नहीं लगता: https://github.com/ross39/new_bloom_filter_repo/blob/main/vi...
      लगता है जिन pixels के r,g,b values का average change 10 से कम है, उनका difference store नहीं किया जाता। तब अगर कोई pixel लगातार frames में pure blue(#00ff00) से pure red(#ff0000) में बदल जाए, तो दोनों frames pure blue के रूप में restore हो सकते हैं
    • जैसे photos के लिए PNG नहीं इस्तेमाल करते, वैसे ही वास्तविक शूट किए गए video के लिए lossless video codec शायद इस्तेमाल नहीं करेंगे
      lossless video screen recording जैसे digital content के लिए कहीं ज्यादा उपयुक्त है। लगातार frames के बीच बदलने वाले pixels कम होते हैं—यह assumption भी वहां ज्यादा सही बैठती है
    • आम लोग raw नहीं इस्तेमाल करते, इसलिए यह शायद बड़ी समस्या न हो। phones और cameras वैसे भी MP4 या AV1 जैसी files में save करते हैं
      जब तक आप खुद enable करके file size और processing burden स्वीकार न करें, आपको यह भी पता न हो कि original या unprocessed data जैसी कोई चीज़ अब भी मौजूद है
      मैंने पहले इस तरह सोचा नहीं था
    • मौजूदा तरीके से तो animation के लिए यह बहुत अच्छा fit लगता है
    • lazy तरीका यह है कि 8K video download करके उसे करीब 720p तक downsample कर दें
      या फिर camera खरीदकर रोजमर्रा के scenes के original 8K videos खुद shoot कर लें

  • graph [1] के मुताबिक, क्या यह नई compression method सिर्फ GZIP इस्तेमाल करने से हमेशा strict तौर पर खराब नहीं है?
    [1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...

    • graph में नहीं है, लेकिन Bloom filter method कम से कम gzip से तेज हो सकती है। हालांकि कहीं और भी performance metrics नहीं मिले

  • “मुख्य insight: अगर binary string में 1 की density कम है, खासकर p* ≈ 0.32453 से कम, तो raw string store करने की बजाय सिर्फ 1 की positions encode करना ज़्यादा efficient होता है।”
    JPEG/MPEG जो करता है उसका बड़ा हिस्सा problem को इस तरह rearrange करना है कि 0 की लंबी runs बन सकें। DCT block को AC/DC components की positions के हिसाब से scan करने का तरीका कई video और image compression techniques में सबसे innovative हिस्सों में से एक हो सकता है

    • यह तरीका असल में video compression के लिए काफी खराब है। क्योंकि यह सामान्य video में मौजूद pixel changes की locality को सक्रिय रूप से फेंक देता है
      बेहतर कहें तो, इस technique में video frames के लिए कुछ भी खास नहीं है। यही idea समान length की दो bit strings के बीच difference compress करने में भी इस्तेमाल किया जा सकता है
      फिर भी इस problem के existing compression methods, जैसे दो blocks को जोड़कर gzip करने, से बेहतर होने की संभावना कम है। Compression होने के लिए input distribution, यहां अलग-अलग bit positions का set, बहुत predictable और non-random होना चाहिए, लेकिन data को hash function से गुजारने पर वह property टूट जाती है। खासकर cryptographically strong hash का उद्देश्य output को random से अलग न पहचाना जा सकने वाला बनाना होता है
    • मुझे लगता है वह explanation सही नहीं है
      DCT और color representation conversion का काम fine details को high frequency में और core details को low frequency में बदलना है। उसके बाद image quality और compression ratio इस बात पर simplify हो जाते हैं कि high-frequency representation का कितना हिस्सा फेंका जाता है
      इसके अलावा JPEG image size को और घटाने के लिए Huffman table का इस्तेमाल करता है
      जहां तक मुझे पता है, यह 0 की लंबी runs कम करने के लिए कोई खास काम नहीं करता। इसलिए 0 को एक लाइन में align करना बहुत मददगार नहीं होता

  • यह line उलझन पैदा करती है: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
    इससे compression lossy compression बन जाएगा, और उदाहरण के लिए #ffffff से #fffffa में transition को छोड़ देगा। ठीक ऊपर वाली line में pixel data का average लेने वाला हिस्सा भी threshold से independent होकर #ff0000 से #00ff00 में transition को छोड़ देगा लगता है
    पता नहीं मैंने उस code line की भूमिका गलत समझी है या नहीं। Result mask में जो 0 हो गया है, वह Bloom filter में encode नहीं होता दिखता

  • Compression ratio calculate करने का तरीका लिखा है, लेकिन क्या worst-case, average और best-case compression ratio के examples भी हैं, यह जानना चाहूंगा
    Edit: देखा कि repository में image है। इसे README में डाल दें तो मदद मिलेगी

    • मैं author हूं। Repository पूरी तरह messy है, लेकिन अगर आप code खंगालने को तैयार हैं तो इसमें graph आदि generate करने वाला code मौजूद है
      मैं काफी proper tests करके इसे कहीं ज़्यादा concrete बनाने वाला हूं। अभी यह बहुत गंदे work-in-progress जैसा है

  • मैं author हूं। काफी अच्छा feedback मिला है, इसलिए कुछ समय के लिए original video और noisy footage पर ज्यादा rigorous testing पर focus करने का फैसला किया है। Repository को अक्सर update करता रहूंगा
    अभी बहुत शुरुआती stage है, लेकिन original video tests में कुछ caveats के साथ काफी अच्छे results मिले हैं। Compression ratio 4.8%, यानी size में 95.2% reduction, compression speed 8.29fps, decompression speed 9.16fps, keyframes केवल 4% frames के लिए जरूरी, perceptually lossless output (PSNR 31.10dB) है
    Standard codecs से तुलना करें तो Rational Bloom Filter 4.8%, JPEG2000 lossless 3.7%, FFV1 lossless 36.5%, H.265/HEVC lossy 9.2%, H.264 lossy 0.3% है
    मौजूदा limitations और future work भी हैं। Compression results promising हैं, लेकिन color channel processing में यह अभी सचमुच lossless नहीं है। Current implementation में YUV से BGR में colorspace conversion के दौरान difficulties हैं, और colorspace conversion precision की वजह से छोटे rounding errors आते हैं, जिससे pixel values में average करीब 4.7 का difference रह जाता है
    साथ ही current implementation conversion के बाद BGR format में color channels process करता है, जिससे अतिरिक्त precision loss होता है
    आगे BGR conversion के बिना सीधे YUV process करने, color data को bit-exact तरीके से handle करने, chroma subsampling patterns के हिसाब से Bloom filter parameters को tune करने, और हर color channel को independently verify करने वाला dedicated system बनाने की योजना है
    मैं mathematically lossless साबित करना चाहता हूं, लेकिन अभी लंबा रास्ता बाकी है। इस lossless compression idea को आगे explore करने की योजना है, और Rational Bloom Filter को दूसरे domains में इस्तेमाल करने के भी कुछ ideas हैं

  • H.264 जैसे codecs भी वास्तविक lossless mode में चलाए जा सकते हैं। बस लगभग कोई इसे ऐसे इस्तेमाल नहीं करता

    • मैंने इसे NVENC के साथ hardware acceleration तक चलने लायक बनाया था। हालांकि playback मुश्किल था; ffplay चला, लेकिन बाकी कुछ नहीं चला

  • Concept प्यारा है, लेकिन अगर आपके पास sparse binary string है तो traditional methods से बेहतर करने की संभावना काफी ज्यादा है

  • Repository को follow करना मुश्किल है, लेकिन compression ratio लगता है इस आधार पर calculate किया गया है कि कितने pixel differences छोड़े जा सके
    दिलचस्प है, लेकिन ज्यादा महत्वपूर्ण comparison target compressed YouTube video में हर frame का average byte size होगा। इस comparison के बिना यह तय करना मुश्किल है कि current methods से improvement है या नहीं
    अगर algorithm lossy है, यानी छोटे differences को 0 में दबा देता है, तो यह lossless नहीं है और इसकी तुलना दूसरे lossy algorithms से करनी चाहिए