Bloom फ़िल्टर का उपयोग करके lossless वीडियो compression
(github.com/ross39)- यह open source प्रोजेक्ट Bloom फ़िल्टर का उपयोग करके lossless वीडियो compression को संभव बनाता है
- Rational Bloom Filter की अवधारणा पेश कर पारंपरिक Bloom फ़िल्टर की सीमाओं को पार किया गया है और अधिक कुशल compression की संभावना तलाश की गई है
- सामान्य codecs से अलग, यह सभी डेटा को पूरी तरह restore करने वाली lossless compression की गारंटी देता है
- पूरे frame के बजाय frames के बीच के अंतर पर ध्यान देकर sparse data की कुशल compression हासिल की गई है
- प्रयोगों के नतीजों, verification प्रक्रिया और सिद्धांत की व्याख्या के माध्यम से उच्च विश्वसनीयता सुनिश्चित की गई है
प्रोजेक्ट अवलोकन
यह open source प्रोजेक्ट Bloom फ़िल्टर (एक data structure जो किसी मान के किसी set में शामिल होने की तेज़ और कुशल जाँच करता है) को नए तरीके से रूपांतरित कर lossless वीडियो compression का प्रयास करता है। H.264 जैसे पारंपरिक वीडियो codecs compression ratio बढ़ाने के लिए ऐसी जानकारी हटा देते हैं जो मानव आँख को दिखाई नहीं देती, लेकिन इस तरीके में सूचना की पूर्णता खो जाती है। यह प्रोजेक्ट डेटा की पूर्ण बहाली बनाए रखते हुए भी file size घटाने का तरीका प्रदर्शित करता है। खास तौर पर, Bloom फ़िल्टर में rational (गैर-पूर्णांक) hash function count के उपयोग की विधि और frame Δ (difference) आधारित compression संरचना इसकी तकनीकी विशेषताएँ हैं।
मुख्य source code मार्गदर्शिका
- मुख्य फ़ाइल: youtube_bloom_compress.py
- केवल साधारण command चलाकर demo को चलाया जा सकता है
- लंबे वीडियो के लिए अभी speed की सीमाएँ हैं, और लगातार optimization जारी है
Bloom फ़िल्टर की बुनियाद
Bloom फ़िल्टर कई hash functions का उपयोग करता है और किसी set में कोई मान मौजूद है या नहीं, इसकी जाँच के लिए बहुत कम memory की आवश्यकता होती है। कुछ false positives की अनुमति होती है, लेकिन false negatives कभी नहीं होते, इसलिए विश्वसनीयता के मामले में इसकी बड़ी ताकत है।
नवाचारी बदलाव: Rational Bloom Filter
Bloom फ़िल्टर में hash functions की optimal संख्या (k) आम तौर पर पूर्णांक नहीं होती। इसलिए Rational Bloom Filter वास्तविक मान k* का उपयोग करता है:
- हमेशा ⌊k*⌋ hash functions लागू किए जाते हैं
- शेष हिस्से के अनुपात में एक अतिरिक्त hash function को probabilistic तरीके से लागू किया जाता है (उदा. यदि k* = 2.7 हो, तो 70% संभावना से तीसरा hash उपयोग किया जाता है)
- इसे इस तरह डिज़ाइन किया गया है कि प्रत्येक element के लिए यह probabilistic निर्णय लगातार एकसमान रहे
यह तरीका compression और restoration दोनों में सटीक रूप से काम करता है और compression की विश्वसनीयता बढ़ाता है
Bloom फ़िल्टर से compressor तक विस्तार
मुख्य विचार यह है कि ऐसे sparse binary string में, जहाँ 1 बहुत कम होते हैं, केवल 1 की positions को संग्रहीत करके पूरे मूल bits की तुलना में कम आकार में डेटा रिकॉर्ड किया जा सकता है।
- compression चरण:
- Bloom फ़िल्टर bitmap में 1 की positions को स्पष्ट किया जाता है
- Bloom फ़िल्टर के अलावा वास्तव में आवश्यक bit values (witness data) को अलग से संग्रहीत किया जाता है
- सैद्धांतिक विश्लेषण के अनुसार, जब 1 का अनुपात 0.32453 से कम हो तब compression का लाभ मिलता है
मुख्य तकनीक के सूत्र और optimization
- sparsity के अनुसार k (hash functions की संख्या) और l (bitmap का आकार) के लिए सूत्र दिए गए हैं
- input data के bit distribution के आधार पर optimal parameters अपने-आप निकाले जा सकते हैं
वीडियो compression में लागू करने का तरीका
- केवल frames के बीच के परिवर्तन (Δ values) निकाले जाते हैं और उन्हें ऐसे sparse matrix में बदला जाता है जहाँ अधिकतर भाग में कोई बदलाव नहीं होता
- इस sparse difference matrix पर Bloom फ़िल्टर compression तकनीक लागू की जाती है
- पूरे frame की तुलना में storage efficiency में बड़ा सुधार होता है
compression और restoration verification प्रक्रिया
- compressed bitmap, witness data, metadata, बदले गए pixels आदि सहित restoration के लिए आवश्यक सभी हिस्सों के आकार की गणना की जाती है
- frame स्तर पर restore करने के बाद मूल डेटा से bit स्तर की समानता की जाँच की जाती है
- frame-वार differences का visualization और quantification किया जाता है, और पूरी pipeline का पूर्ण verification किया जाता है
- compression ratio की गणना code में स्पष्ट रूप से दी गई है, इसलिए कोई भी इसे दोहरा और verify कर सकता है
पूरी तरह self-contained compression संरचना
- restoration के लिए किसी अलग dictionary या lookup table की आवश्यकता नहीं होती
- सभी Bloom फ़िल्टर parameters और color information compression file के भीतर ही संग्रहीत रहती है
- केवल compression file से पूर्ण restoration संभव है
निष्कर्ष और open source जानकारी
यह प्रोजेक्ट Bloom फ़िल्टर का उपयोग करके data sparsity का अधिकतम लाभ उठाता है और उन कार्यों के लिए उपयुक्त है जहाँ पूर्ण restoration आवश्यक है (जैसे वैज्ञानिक डेटा, medical imaging)। नए algorithm structure और verification system को सीधे प्रयोग करके देखा जा सकता है और सुधार के सुझाव छोड़े जा सकते हैं।
1 टिप्पणियां
Hacker News की राय
मुझे लगता है कि यह दस्तावेज़ असल में एक सरल आइडिया को बहुत जटिल तरीके से समझा रहा है
यह तरीका दो frames के delta को x, y, r, g, b के रूप में स्टोर करने जैसा है, लेकिन x, y coordinates को बहुत compress करने के बदले r, g, b को थोड़ा ज़्यादा स्टोर करता है
आम तौर पर हर frame में बदलने वाले pixels की positions मिलती-जुलती होती हैं, इसलिए अगले frame में उन position flags को ठीक से सेट करके और सिर्फ अतिरिक्त बदले हुए offsets को जोड़कर शायद और compression किया जा सकता है
मैं हमेशा पहले comments इसी तरह की समझदार टिप्पणियाँ पढ़ने के लिए ही पढ़ता हूँ
और देखा तो पता चला कि लेखक वही व्यक्ति है जिसने kilo बनाया था, वाकई कमाल
[edit] इसे edit करना भी किसी वजह से मज़ेदार लग रहा है
असली compression ratio कितना निकलता है, यह जानने की उत्सुकता है
मैंने बहुत पहले wavelet-आधारित image compression के साथ प्रयोग किया था
inverse transform छोटे image से शुरू होता है और coefficients का उपयोग करके उसे धीरे-धीरे 2x बड़ा करता जाता है
ज़्यादातर data लगभग 0 वाले coefficients होते हैं, और इन्हें 0 करके compress किया जाता है
असली मुद्दा non-zero हिस्सों की positions को efficiently encode करना है, और आम तौर पर ये values cluster होती हैं, इसलिए algorithms इस गुण का खूब उपयोग करते हैं
Bloom filter में इस्तेमाल होने वाले hash functions में इसका बिल्कुल उल्टा गुण दिखता है
ऐसे तरीके में transform खुद भी और coefficient compression भी, दोनों में spatial locality कम होती है और यह धीमा पड़ता है, इसलिए आख़िरकार इसकी सीमा आ जाती है
जिज्ञासा है कि Bloom filter, hash table की तुलना में किस तरह बेहतर है
video compression का बड़ा हिस्सा ‘motion’ के बारे में होता है
जैसे camera panning में वही pixel 2 pixels बाएँ खिसक जाए, तब इसे कैसे handle किया जाता है, यह जानना चाहता हूँ
अगर frames के बीच सिर्फ delta changes ही स्टोर किए जाएँ, तो जो pixels नहीं बदलते वे सब 0 होंगे
लगातार 0 की sequences को compress करना lossy compression में सबसे आसान चीज़ों में से एक है, लेकिन Bloom filter तरीके में false positives होते हैं
Bloom filter को composite compressor की एक sub-strategy की तरह इस्तेमाल किया जा सकता है, और कई तरीकों का मिश्रण बेहतर हो सकता है, लेकिन औसतन Bloom filter मौजूदा तरीकों की तुलना में performance को बहुत नहीं बढ़ाएगा, ऐसा लगता है
मुझे लगता है कि यह तरीका YouTube video जैसी पहले से एक बार compress-decompress हो चुकी video पर अच्छा चलने का एक कारण है
Raw input में यह मान्यता कि ज़्यादातर pixels लगातार frames में लगभग नहीं बदलते, टूट सकती है
पूरी तरह साफ, low-noise, bright scene हो तो यह लागू हो सकता है, लेकिन सामान्य signal में 1 LSB से ज़्यादा noise होता है, इसलिए lower bits अक्सर बदलते रहेंगे
compress-decompress प्रक्रिया के बाद noise कम हो जाता है और यह मान्यता सच होने लगती है
असल में यह तरीका lossless भी नहीं है
video_delta_compress.py कोड में, अगर r,g,b की औसत बदलाव मात्रा 10 से कम हो तो बदलाव स्टोर ही नहीं किया जाता
उदाहरण के लिए pure blue(#00ff00) से pure red(#ff0000) में बदलने पर भी ऐसा ही हो सकता है, और दोनों frames pure blue के रूप में reconstruct हो सकते हैं
जैसे photography में PNG नहीं इस्तेमाल होता, वैसे ही real-world video में lossless codec कम ही इस्तेमाल होते हैं
lossless video ज़्यादा digital content जैसे screen recording के लिए उपयुक्त है
ऐसे मामलों में frames के बीच बदलने वाले pixels कम होते हैं, इसलिए इस तरीके की assumptions ठीक बैठती हैं
कोड में ratio 32.4% से कम होने पर सिर्फ bit 1 की positions स्टोर करने की strategy इस्तेमाल की जाती है
तो क्या यह संभव नहीं कि lower bits अक्सर बदलें, फिर भी अगर higher bits काफ़ी नहीं बदलते, तो यह तरीका अब भी काम कर जाए? ऐसा विचार है
आम तौर पर Raw video इस्तेमाल करने वाले लोग बहुत कम होते हैं
phone और camera भी default रूप से MP4, AV1 आदि में save करते हैं
file size और processing overhead को देखते हुए, कई लोग raw unprocessed format के अस्तित्व से भी अनजान होते हैं
इसलिए मौजूदा तरीका animation के लिए उपयुक्त लगता है
संबंधित compression_comparison.png graph के अनुसार, क्या नया compression तरीका हमेशा GZIP से खराब performance देता है?
हालाँकि performance metrics मुझे नहीं मिले
मुख्य लेख में कही गई इस key insight का ज़िक्र: “जिन binary strings में 1 की density काफ़ी कम हो, उनमें सिर्फ 1 की positions स्टोर करके मूल data से भी अधिक efficient compression संभव है”
JPEG, MPEG आदि मूल समस्या को इस तरह rearrange करते हैं कि 0 लंबी runs में आ जाएँ, और DCT block scan तरीका ऐसे video compression में बहुत क्रांतिकारी है
DCT और color transform सूक्ष्म details को high frequency में और मुख्य content को low frequency में बदल देते हैं
compression में high frequency components को फेंक दिया जाता है
JPEG Huffman table से size भी optimize करता है
0 को इकट्ठा करने की कोई बहुत खास तकनीक ज़्यादा इस्तेमाल नहीं होती, और सिर्फ 0 इकट्ठे होने से compression efficiency बहुत नहीं बढ़ती
सहमत
OP के approach की सबसे बड़ी समस्या यह है कि यह सामान्य video में अक्सर मौजूद pixel changes की spatial locality को सक्रिय रूप से छोड़ देता है
यह वास्तव में video frame-विशेष तकनीक कम, और समान लंबाई की bitstrings के delta compression का एक generalization ज़्यादा है
यह तभी असरदार होगा जब input data में predictability हो, यानी randomness कम हो, लेकिन ऐसे data को भी hash function से गुज़ारते ही information बिखर जाती है
खासकर cryptographic hash का output पूरी तरह random जैसा हो जाता है, जो compression के लिए प्रतिकूल है
नमस्ते HN, मैं लेखक हूँ
feedback मिलने के बाद मैं raw video और noisy video पर ज़्यादा सख़्त tests कर रहा हूँ
अभी शुरुआती चरण है, लेकिन raw video में काफ़ी ठीक results मिल रहे हैं (हालाँकि caveat है)
standard codecs से तुलना
मौजूदा सीमाएँ और आगे का काम
color handling में यह bit-level पूरी तरह lossless नहीं है, और YUV-BGR conversion में floating-point errors आते हैं (औसत pixel difference ~4.7), साथ ही conversion के बाद BGR channel processing में precision loss होता है
आगे की योजना
मैं इसे गणितीय रूप से पूरी तरह lossless साबित करना चाहता हूँ
इस lossless compression आइडिया और Rational Bloom Filter के उपयोग को video के अलावा दूसरे क्षेत्रों में भी सोच रहा हूँ
video_delta_compress.py की code line को लेकर उलझन है
इस हिस्से की वजह से #ffffff से #fffffa तक का बदलाव, या #ff0000 से #00ff00 जैसे बदलाव भी threshold के आधार पर पूरी तरह फेंक दिए जाते दिखते हैं
क्या मैं इस code line की भूमिका गलत समझ रहा हूँ, या 0 वाले pixel changes वास्तव में Bloom filter में दर्ज ही नहीं किए जाते?
compression ratio निकालने का तरीका बताया गया है, लेकिन worst/average/best compression ratio के उदाहरण हैं क्या?
(संपादन: repo में image examples देख लिए, इसलिए राय है कि उन्हें README में डालना अच्छा रहेगा)
repo अभी बहुत बिखरा हुआ है, लेकिन code के अंदर graphs वगैरह generate करने वाला code भी है
आगे proper testing और result organization करके इसे काफ़ी polish करने का इरादा है
अभी यह काफ़ी messy WIP चरण में है
H.264 जैसे codecs वास्तव में lossless mode में भी चल सकते हैं, भले ही उनका कम उपयोग होता हो
मैंने NVENC hardware acceleration के साथ lossless mode चलाया हुआ है
लेकिन playback मुश्किल था; याद है कि यह सिर्फ ffplay में चलता था, और बाकी लगभग कहीं नहीं
concept अच्छा है, लेकिन sparse binary strings के लिए शायद पारंपरिक मौजूदा compression तरीके ही बेहतर हों
repo को देखकर लगता है कि compression ratio इस आधार पर निकाला गया है कि pixel differences में से कितने differences फेंक दिए गए
यह दिलचस्प है, लेकिन वास्तव में ज़्यादा महत्वपूर्ण बात यह है कि YouTube-compressed video में हर frame का औसत byte size सीधे compare किया जाए
इसके बिना यह जानना मुश्किल है कि मौजूदा तरीका सच में performance improvement देता भी है या नहीं
अगर यह algorithm lossy compression है, तो छोटे differences को 0 में मिला देता है, इसलिए lossy compression से तुलना करना ज़्यादा उचित होगा