छवियाँ: प्रारूप और संपीड़न (2/3)

फिर से नमस्कार! एक महीने के विराम के बाद, हम छवि प्रारूपों और संपीड़न एल्गोरिदम के दौरे को जारी रखते हैं । हम कहां ठहरे हैं? अरे हां, अस्सी का दशक।

झगड़ा: अपने आप को बनाएँ

1986 के आंगन में। पीसीएक्स और टीजीए प्रारूप साधारण डेस्कटॉप के भाग्यशाली मालिकों के लिए चश्मा प्रदान करना शुरू कर रहे हैं। लेकिन व्यवसाय केवल घरेलू कंप्यूटर तक सीमित नहीं है, इसमें उद्यम और विश्वविद्यालय भी हैं। और उनके पास पहले से ही शक्तिशाली मशीनें और स्कैनर हैं, और स्कैनर के बीच ... एक गड़बड़ और अपमान। स्कैनर का कार्य छवि को कागज पर डिजिटल प्रारूप में बदलना है, और प्रत्येक निर्माता के पास यह प्रारूप था।

एक पल के लिए कल्पना कीजिए, आप कुछ महत्वपूर्ण ड्राइंग का एक स्कैन बना रहे हैं, इसे प्रिंटिंग हाउस में ला रहे हैं, और वे कहते हैं कि वे इसे नहीं पढ़ सकते हैं। हमें इसे एक अलग प्रारूप से आगे निकलना होगा, लेकिन विश्वसनीयता के लिए केवल एक फोटोकॉपी लाना बेहतर है। यह शर्म की बात है।

एल्डस ने इस समस्या का हल निकाला, अंततः TIFF प्रारूप को पेश किया। सभी स्कैन अब एक प्रारूप में थे, और यहां तक ​​कि "बॉक्स से बाहर" एक फ़ाइल में दस्तावेज़ के कई पृष्ठ हो सकते हैं। इसके अलावा, रेखापुंज डेटा के साथ, मेटा-जानकारी को स्टोर करना संभव हो गया: दस्तावेज़ का नाम, लेखक, स्कैनिंग की तारीख, स्कैनर मॉडल - हां लगभग कुछ भी।

प्रारूप इतना विस्तार योग्य हो गया है कि यह आज तक जीवित है और रहता है। और यह सब इस तथ्य के कारण है कि एल्डस ने ग्राफिक प्रारूप की बहुत अवधारणा पर पुनर्विचार किया। जानकारी की एक निश्चित परत के बजाय, अपेक्षाकृत छोटी संरचनाओं का उपयोग किया जाता है जिससे एक फ़ाइल को इकट्ठा किया जा सकता है। लेखक को ज्ञात है - हम संरचना को सम्मिलित करते हैं, अज्ञात - बस हटाएं। इस तरह के "टैग" का उपयोग, वास्तव में, प्रारूप के नाम पर ही किया गया था: "टैग की गई छवि फ़ाइल स्वरूप"।

हालाँकि, इस विस्तार की फ्लिप पक्ष, विनिर्देशन का अत्यधिक प्रवाह था। एल्डस (और फिर इसे खरीदने के लिए एडोब) के प्रयासों ने अन्य लोगों के उत्साह को प्रभावित करने के लिए बेहतर नहीं करने के लिए प्रभावित किया।

चित्र साझा करने का प्रारूप

नया झगड़ा प्रारूप, जिसमें ठाठ के फायदे थे, केवल मुद्रण के लिए उपयुक्त था: पहले संशोधन में बिना हाफ़टोन के केवल काले और सफेद चित्र प्रदान किए गए थे। और 1987 में, वीजीए वीडियो कार्ड के साथ पैलेट तक लुभावनी 256 रंग पहले से ही दिखाई दिए। टीजीए और पीसीएक्स (परिष्करण के साथ) ने कुख्यात 256 रंगों को संग्रहीत करने की अनुमति दी, लेकिन फ़ाइल का आकार दोगुना, या इससे भी अधिक - एक बड़े पैलेट पर एक साधारण आरएलई ने बहुत खराब काम किया।

पैमाने का अनुमान लगाने के लिए, हम पीसीएक्स प्रारूप में एक पूर्ण स्क्रीन वीजीए तस्वीर (320 × 200 @ 256) - लगभग 50 KiB , प्लस या माइनस लेते हैं। अब एक तेज, 9600 बॉड, डायल-अप मॉडेम का उपयोग करके इसे स्थानांतरित करने का प्रयास करें, और डाउनलोड का समय एक मिनट के आसपास कहीं भी प्राप्त करें। शांत नहीं। CompuServe उसी तरह के बारे में लग रहा था जैसे उसने ओहियो के सनी कोलंबस में अपने BBS तक पहुंच प्रदान करके पैसा कमाया था।

लेकिन कोई इस स्थिति से कैसे बाहर निकल सकता है? आप तकनीकी रूप से अतिरिक्त क्षेत्रों को काट सकते हैं, अनावश्यक नहीं डाल सकते हैं, और एक शक्तिशाली संपीड़न एल्गोरिदम का उपयोग कर सकते हैं। आप मानवीय सरलता का उपयोग कर सकते हैं, और पूर्ण लोड से पहले चित्र के समान कुछ दिखा सकते हैं, और फिर उपयोगकर्ता को व्यावहारिक रूप से महसूस होगा कि सब कुछ तेजी से लोड होता है।

इन दोनों दृष्टिकोणों को जीआईएफ प्रारूप ("ग्राफिक्स इंटरचेंज फॉर्मेट") में जोड़ा गया था। और अब और अधिक विस्तार से।

GIF: संरचना

यह जानने के लिए कि जीआईएफ क्या कर सकता है और यह कैसे काम करता है, हम प्रलेखन में शामिल होंगे। प्रारूप पहले पेटेंट किया गया था, लेकिन इन पेटेंटों ने एक दर्जन साल पहले समाप्त कर दिया था, और सब कुछ सार्वजनिक डोमेन में रखा गया है।

हैडर

फ़ाइल के पहले छह बाइट्स हेडर हैं। इसमें हस्ताक्षर " GIF " और संस्करण शामिल हैं: "87 89a " या "89 89a ", जहां 87 और 89 ऐसे वर्ष हैं जिनमें उन्हें विकसित किया गया था। संस्करण 89a 87a का विस्तार करता है और इसके साथ पूरी तरह से पिछड़ा हुआ है। विनिर्देशन जब भी संभव हो 87a के उपयोग को निर्धारित करता है, लेकिन मैं व्यक्तिगत रूप से अनुशंसा नहीं करूंगा कि ब्राउज़र 87a के साथ कुटिलता से काम करते हैं। एक प्रदर्शन के रूप में, मैं थोड़ा आगे बढ़ूंगा और ध्यान केंद्रित करूंगा:



चित्र में क्या दिखाया गया है? यदि एक वर्ग, तो आपके पास फ़ायरफ़ॉक्स या क्रोम है। यदि दो, तो आईई। यदि तीन, तो ओपेरा (जो अभी भी प्रेस्टो पर है)।

लॉजिकल स्क्रीन विवरण ब्लॉक

एक तार्किक स्क्रीन ग्राफिक्स प्रदर्शित करने के लिए आवंटित एक आयताकार क्षेत्र है, जिसका अर्थ है देखने के बंदरगाह जैसा कुछ। जीआईएफ में कई चित्र हो सकते हैं, और वे तार्किक स्क्रीन से छोटे हो सकते हैं। इसके अलावा, GIF87a में, ये चित्र एनीमेशन के फ्रेम नहीं हैं, बल्कि परतें हैं।

दूसरे शब्दों में, यदि आपको पूरी स्क्रीन पर बिल्ली के बच्चे के बीच में 800 × 600 खींचने की जरूरत है, और कोने में एक फूल है, तो एक विशाल "मिश्रित" छवि के बजाय, आप बिल्ली के बच्चे और फूलों को तार्किक स्क्रीन के सापेक्ष उनके विस्थापन के साथ स्टोर कर सकते हैं।

एक छोटा सा अस्वीकरण। इस तथ्य के बावजूद कि सहज ज्ञान युक्त स्तर पर ही GIF (argh ... ठीक है, "GIF") एक तस्वीर है जो स्क्रीन पर दिखाई देती है, हम विनिर्देश में निर्दिष्ट शब्दावली का पालन करेंगे: "तार्किक स्क्रीन" पूरे GIF का आकार है। और "छवि" एक परत / फ्रेम है।

तो, तार्किक स्क्रीन विवरण ब्लॉक हमेशा 7 बाइट्स लेता है। पहला आकार है - चौड़ाई में दो बाइट्स और ऊंचाई में दो बाइट्स (UInt16LE)। यह पता चला है कि अधिकतम आकार 65535 × 65535 पिक्सेल है। विनिर्देश यह नहीं दर्शाता है कि चौड़ाई या ऊंचाई शून्य से अधिक होनी चाहिए, लेकिन इसके बारे में जागरूकता हमें जिज्ञासा के अलावा कुछ नहीं देती है।

यहां एक महत्वपूर्ण टिप्पणी की जानी चाहिए: यदि GIF फ़ाइल संस्करण 87a, फ़ायरफ़ॉक्स और क्रोम हमेशा इस फ़ील्ड को अनदेखा करते हैं, और तार्किक स्क्रीन के आकार के रूप में पहली छवि के आकार का उपयोग करते हैं। ओपेरा और IE केवल तभी करते हैं जब पहली छवि के निर्देशांक शून्य होते हैं।

इसके बाद एक बाइट होती है जिसमें कई फील्ड होते हैं। सातवां बिट (उच्च) इंगित करता है कि क्या कोई वैश्विक पैलेट है, और बिट्स 2 के माध्यम से इसका आकार निर्धारित किया जाता है (2 ¹ से 2 ^{8 तक} )। पिछले 4 वर्षों में शेष 4 बिट्स ने अपना अर्थ खो दिया है।

अगला क्षेत्र एक बाइट है, जो वैश्विक पैलेट (यदि उपयोग किया जाता है) में पृष्ठभूमि का रंग दर्शाता है। इस क्षेत्र को तार्किक स्क्रीन के सभी क्षेत्रों में भरा जाना चाहिए, किसी भी छवि पर कब्जा नहीं किया जाना चाहिए। सिद्धांत रूप में। व्यवहार में, केवल फ़ोटोशॉप और इरफानव्यू इस आवश्यकता को पूरा करते हैं। आम ब्राउजर बिना स्पेस वाली जगह को पारदर्शी छोड़ देता है। और ओपेरा 12 में एक दिलचस्प बाज़ोक है: अगर जीआईएफ संस्करण 87 ए, और इसमें एक से अधिक छवि हैं, तो यह खाली स्थान काले रंग से भर गया है।

तार्किक स्क्रीन के विवरण के अंतिम बाइट में पिक्सेल के अनुपात की जानकारी होती है। ब्राउज़र इस विकल्प को अनदेखा करते हैं, और सभी पिक्सेल को वर्ग माना जाता है।

वैश्विक पैलेट

यदि वैश्विक पैलेट का ध्वज 0 पर सेट किया गया है, तो यह बस मौजूद नहीं है। और अगर वहाँ है, तो बाइट्स में पूरे ब्लॉक का आकार पैलेट समय तीन में रंगों की संख्या के बराबर है। भरने सिद्धांत: RGB RGB RGB ..., बिल्कुल PCX की तरह।

एक वैश्विक पैलेट को एक फ़ाइल में प्रत्येक छवि पर लागू किया जाता है यदि इसमें एक स्थानीय पैलेट नहीं है। और अगर न तो कोई है और न ही है? इस अवसर पर स्पेक का कहना है कि "उम ... ठीक है, मुझे नहीं पता, इसे किसी तरह सुलझाओ", और मानक डिवाइस पैलेट का उपयोग करने का सुझाव देता है, लेकिन यह वांछनीय है कि पहला रंग काला है और दूसरा सफेद। 2013 में, हर कोई पहले ही भूल गया है कि डिवाइस का मानक पैलेट क्या है, और यह ध्यान अक्सर काम नहीं करता है।

इस बिंदु पर, अनिवार्य, निश्चित प्रारूप फ़ील्ड समाप्त होते हैं, और वैकल्पिक शुरू होते हैं।

छवि

यहाँ रेखापुंज डेटा और तार्किक स्क्रीन के सापेक्ष उनका स्थान संग्रहीत होता है। एक फ़ाइल में किसी भी संख्या में चित्र हो सकते हैं - शून्य से अनंत तक।

यह खरोंच से है! स्पेक पूरी तरह से मानता है कि फ़ाइल में कोई भी चित्र नहीं हैं। उदाहरण के लिए, यदि आपको डिवाइस पर वैश्विक पैलेट को प्रारंभ करने की आवश्यकता है। लेकिन वर्तमान ब्राउज़र इन सूक्ष्मताओं को नहीं समझते हैं, और ऐसे मामलों में विचार करते हैं कि फ़ाइल "टूटी हुई" है।

छवि एक मार्कर, ASCII चरित्र " , " (अल्पविराम) से शुरू होती है। इस मार्कर को यह समझने के लिए आवश्यक है कि किस संरचना की अभी शुरुआत हुई है: एक छवि (" , "), एक एक्सटेंशन ब्लॉक (" ! "), या एक एंड-ऑफ़-फ़ाइल ब्लॉक (" ; ")।

चार चार-बाइट पूर्णांकों का अनुसरण करते हैं: तार्किक स्क्रीन के सापेक्ष छवि के ऊपरी बाएं किनारे की स्थिति के दो निर्देशांक और स्वयं छवि की चौड़ाई / ऊंचाई। विनिर्देश के अनुसार, छवि के निचले दाएं किनारे को तार्किक स्क्रीन से परे नहीं जाना चाहिए।

पैक्ड खेतों के साथ आगे बाइट। उच्च बिट: क्या छवि में एक स्थानीय पैलेट है, तीन निचले वाले: क्या आकार, तार्किक स्क्रीन के विवरण में उसी के बारे में। 6 बिट बिट स्कैनिंग ऑर्डर के लिए जिम्मेदार है: लाइन-बाय-लाइन (प्रगतिशील) या इंटरलेस्ड (इंटरलेसिंग)। मुझे नहीं लगता कि यह वर्णन करना आवश्यक है कि एक इंटरलेस्ड छवि कैसे लोड हो रही है, सभी ने इसे एक हजार बार देखा, लेकिन सिर्फ मामले में, यहां चित्रों के साथ एक भव्य लेख है

इसके बाद, जैसा कि तार्किक स्क्रीन के विवरण में है, स्थानीय पैलेट तुरंत अनुसरण करता है, यदि कोई हो।

वैसे, जब से मैं बात कर रहा था, क्या आपने पहले से ही अनुमान लगाया था कि एक तार्किक जीआईएफ स्क्रीन पर 256 से अधिक रंगों को कैसे प्रदर्शित किया जा सकता है?

अगला बाइट LZW कोड का आकार है। प्रारंभिक शब्दकोष की लंबाई LZW संपीड़ित डेटा स्ट्रीम में इंगित नहीं की गई है, और इसे अलग से निर्दिष्ट किया जाना चाहिए। लेकिन हम इस पर वापस आएंगे।

मनमाना लंबाई का डाटा पैक करना

फिर छवि में सीधे LZW डेटा संपीड़ित होते हैं। लेकिन वे एक निर्दिष्ट लंबाई के साथ एक साधारण डेटा फ़ीड द्वारा संग्रहीत नहीं किए जाते हैं, लेकिन ब्लॉक में पैक किए जाते हैं। (जाहिरा तौर पर, जब मनमाना IO और एन्कोडिंग के दौरान अत्यधिक मेमोरी खपत से बचने के लिए।) पैकिंग सिद्धांत: ब्लॉक बाइट की एक बाइट, डेटा की एक बाइट, ब्लॉक की बाइट की एक बाइट, डेटा की बाइट्स और इसी तरह, जब तक कि डेटा बाहर नहीं निकलता। और डेटा के अंत में लंबाई 0 का एक ब्लॉक इंगित करता है।

उदाहरण के लिए, एक तेज़ लोमड़ी के बारे में प्रसिद्ध पैंग्राम को इस तरह पैक किया जा सकता है:

\x2B The quick brown fox jumps over the lazy dog \x00

और यह दूसरे तरीके से संभव है, हम एक और बाइट खर्च करेंगे, लेकिन इसे एक त्रुटि नहीं माना जाएगा:

\x20 The quick brown fox jumps over t \x0B The quick brown fox jumps over t he lazy dog \x00

सामान्य तौर पर, आप आमतौर पर प्रति ब्लॉक कम से कम एक बाइट का उपयोग कर सकते हैं, फिर पैक्ड डेटा मूल से दोगुना होगा। और सफेद (या काली) रोटी की एक पाव रोटी से आप एक ट्रॉली बस बना सकते हैं।

विस्तार

चौकस पाठक ने शायद पहले ही ध्यान दिया कि न तो छवि के वर्णन में, न ही तार्किक स्क्रीन के वर्णन में, जबकि वास्तव में जीआईएफ "बन्स" थे: पारदर्शिता और एनीमेशन। ऐसा इसलिए है क्योंकि उन्हें विस्तार इकाई के रूप में संस्करण 89a में पेश किया गया था।

चार प्रकार के एक्सटेंशन ब्लॉक हैं: ग्राफिक्स मैनेजमेंट एक्सटेंशन, टेक्स्ट एक्सटेंशन, कमेंट और एप्लिकेशन एक्सटेंशन। सभी ब्लॉक वैकल्पिक हैं, जो GIF89a प्रारूप को 87a के साथ संगत बनाता है।

ग्राफिक्स प्रबंधन विस्तार

यह एक्सटेंशन मूल रूप से उस छवि के लिए अतिरिक्त फ़ील्ड का एक सेट है जो इसके तुरंत बाद आता है। वास्तव में, यह वह है जो "छवि" की अस्पष्ट वर्णित अवधारणा को बहुत ही ठोस "फ्रेम" में बदल देता है। निश्चित क्षेत्रों में से, केवल दो मार्कर बाइट्स हैं: 0xF9 , "यह एक एक्सटेंशन है" और 0xF9 , "यह ग्राफिक्स प्रबंधन का एक विस्तार है।"

आगे के क्षेत्रों को कच्ची छवि डेटा के रूप में उसी तरह से पैक किया जाता है - ब्लॉक लंबाई, एन बाइट्स, ब्लॉक लंबाई, एन बाइट्स। एक और बात यह है कि विनिर्देश के अनुसार यह हमेशा एक ब्लॉक 4 बाइट्स लंबा होता है। आपको इसे ब्लॉक में क्यों तोड़ना पड़ा? मैं भी नहीं समझना चाहता, जाहिर है, यह आसान था।

एक रास्ता या दूसरा, इन चार बाइट्स में से पहला बिट फ़ील्ड का एक सेट है। तीन सबसे महत्वपूर्ण बिट्स आरक्षित हैं। अगला, तीन बिट्स, 0 से 7 तक पूर्णांक बनाते हुए, इंगित करते हैं कि अगले को दिखाने से पहले फ्रेम के साथ क्या किया जाना चाहिए। 0: कुछ भी नहीं (परिभाषित नहीं); 1: कुछ भी नहीं (जैसा सब कुछ छोड़ दें); 2: स्क्रीन को साफ़ करें; 3: इस फ्रेम से पहले क्या था; मान 4-7 आरक्षित हैं।

ऐतिहासिक दृष्टि से बिट 1 सबसे दिलचस्प है। इसके बाद के फ्रेम को दिखाने के लिए "किसी भी कुंजी" के लिए उपयोगकर्ता से इंतजार करना है या नहीं। हां, जीआईएफ के आधार पर न केवल एक स्लाइड शो बनाना संभव था, बल्कि खुद के लिए एक प्रस्तुति भी थी। अब यह सुविधा वास्तव में समर्थित नहीं है।

कम बिट इंगित करता है कि पैलेट में कोई भी रंग पारदर्शी माना जाता है या नहीं।

अगले दो बाइट्स UInt16 का निर्माण करते हैं, यह दर्शाता है कि दूसरे के कितने सौवें हिस्से को आपको अगले फ्रेम दिखाने से पहले इंतजार करना होगा। इस प्रकार, देरी 0 से 655.35 सेकंड की सीमा में हो सकती है।

अंत में, अंतिम बाइट पैलेट में "पारदर्शी" रंग का सूचकांक है (यदि यह ऊपर इंगित किया गया था कि यह है)।

ऐप एक्सटेंशन

यह एक्सटेंशन जीआईएफ को अपने मालिकाना मेटाडेटा लिखने के लिए एप्लिकेशन को अनुमति देने के लिए बनाया गया है। प्रारूप पहले से ही परिचित है: हस्ताक्षर मार्कर के दो बाइट्स, 0x21 0xFF , बाकी उनके सामने की लंबाई के साथ ब्लॉक हैं। और फिर से, पहले ब्लॉक की लंबाई सख्ती से तय की गई है: 11 बाइट्स जो एप्लिकेशन की पहचान करते हैं। इसके बाद के ब्लॉक किसी भी लम्बाई के हो सकते हैं और उनमें कुछ भी हो सकता है।

ऐसा ही एक एक्सटेंशन नेटस्केप नेविगेटर ब्राउज़र द्वारा आविष्कार किया गया था। तथ्य यह है कि जीआईएफ प्रारूप स्वयं चक्रीय एनीमेशन के लिए प्रदान नहीं करता है, और मालिकाना एक्सटेंशन " NETSCAPE2.0 " के साथ आप निर्दिष्ट कर सकते हैं कि एनीमेशन को कितनी बार स्क्रॉल किया गया है: 1 से 65535 बार तक, या अंतहीन।

अब सभी ब्राउज़र इस डिज़ाइन को समझते हैं, और यदि ऐसा नहीं है, तो यह माना जाता है कि एनीमेशन लूप नहीं किया गया है।

फ़ाइल आकार को कम करने के लिए शेष एप्लिकेशन एक्सटेंशन को सुरक्षित रूप से मग किया जा सकता है।

पाठ का विस्तार

तार्किक स्क्रीन पर मनमाना पाठ आकर्षित करने के लिए यह विस्तार आवश्यक है। पिक्सेल में ग्लिफ़ के आकार को निर्दिष्ट करें, टेक्स्ट फ़ील्ड का आकार, तार्किक स्क्रीन के सापेक्ष स्थिति, और वॉइला! आप केवल एक स्लाइड शो या प्रस्तुति नहीं कर सकते हैं, लेकिन सामान्य तौर पर एक दृश्य उपन्यास बनाते हैं।

लेकिन अफसोस, इस विस्तार के लिए कोई वास्तविक समर्थन नहीं है। प्रकृति में, यह प्रजाति नहीं होती है, लाल किताब से हटा दी जाती है। और हम आगे बढ़ते हैं।

टिप्पणी

अंतिम विस्तार सबसे आसान है। दो बाइट मार्कर 0x21 0xFE , और फिर मनमानी सामग्री, ब्लॉक में पैक किए गए।

समापन ब्लॉक

अनुगामी ब्लॉक ("ट्रेलर") में एक एकल बाइट 0x3B (" ; ") होता है। यह फ़ाइल के अंत में स्थित है और इसका मतलब है कि इस जगह में, वास्तव में, फ़ाइल का अंत। इसके बाद का सब कुछ कचरा माना जाता है और इसे नजरअंदाज कर दिया जाता है।

यह डिज़ाइन विनिर्देश द्वारा अनिवार्य है, इसके बारे में मत भूलना।

ओह! सब कुछ संरचना में लगता है। ईमानदारी से, मुझे खुद उम्मीद थी कि यह आसान होगा। अगर अचानक कोई गलतफहमी होती है, तो प्रस्तुति की शैली या शर्तों के अनुवाद के कारण, आप खुद को GIF89a के आधिकारिक विनिर्देश के साथ परिचित कर सकते हैं। मैं GIF सलामी बल्लेबाज कार्यक्रम की अत्यधिक अनुशंसा करता हूं, वह दोपहर के भोजन में सौ साल पुराना है, लेकिन मैंने निम्न-स्तरीय gif संपादन के लिए कुछ भी बेहतर नहीं देखा।

लेम्पेल-ज़िव-वेल्च एल्गोरिथम

अब जब हमने आस-पास की जांच की है, तो हम GIF के बहुत दिल में उतरेंगे - लेम्पेल-ज़िव-वेल्च एल्गोरिथ्म, उर्फ ​​एलजेडडब्ल्यू। सबसे पहले, यह ध्यान देने योग्य है कि यह एल्गोरिथ्म शब्दावली है । आइए देखें इसका क्या मतलब है।

शब्दकोश संपीड़न, एक सरल उदाहरण है

शब्दावली संपीड़न RLE विचार का प्रत्यक्ष विकास है। सामान्य तौर पर, सिद्धांत यह है: हम डुप्लिकेट मानों की तलाश करते हैं और उन्हें शब्दकोश में दर्ज करते हैं, और फिर सही जगह पर हम शब्दकोश के तत्व का संकेत देते हैं। इस प्रकार, न केवल एक पंक्ति में समान मान संपीड़ित होते हैं, बल्कि विभिन्न मूल्यों के समूह भी होते हैं, जिनके बीच एक निश्चित दूरी हो सकती है।

उदाहरण के लिए, इस लाइन को लें:



यह देखा जा सकता है कि वह को दोहराते हुए सही ढंग से भर गई थी। हम कुछ अप्रयुक्त चरित्र का चयन करते हैं, उदाहरण के लिए, " 1 " और कहते हैं कि इस तरह के किसी भी चरित्र को " " द्वारा प्रतिस्थापित किया जाना चाहिए। नतीजतन, हमें " 11 11 " लाइन 11 11 , जो कि आधी है। और इसलिए कि हमारे अलावा कोई यह समझ सकता है कि इस एन्क्रिप्शन को पढ़ा जाएगा, किसी को खुद ही शब्दकोश लिखना नहीं भूलना चाहिए, अर्थात " 1 " के साथ इसे बदलने की क्या आवश्यकता है। परिणाम कुछ इस प्रकार होगा:

1=; 11 11

आप थोड़ा आगे जा सकते हैं, और " 1 " को " 2 " से भी बदल सकते हैं:

1=,2=1; 11 22

हम्म ... ऐसा लगता है कि हमने अधिक डुप्लिकेट मानों को बदल दिया है, और स्ट्रिंग अधिक लंबा है। काश, शब्दकोश को भी संग्रहीत करने की आवश्यकता होती है, और यह जितना बड़ा होता है, उतना ही अधिक उपरि।

बेशक, वे किसी भी तरह इस से लड़ने की कोशिश कर रहे हैं। उदाहरण के लिए, LZ77 एल्गोरिथ्म को औपचारिक रूप से एक शब्दकोश माना जाता है, लेकिन डिकोड किया गया डेटा स्वयं एक शब्दकोश के रूप में कार्य करता है - डिकोडर को एन बाइट्स वापस जाने और वहां से मी बाइट्स कॉपी करने की आज्ञा दी जाती है। आप इस लेख में LZ77 के बारे में और अधिक पढ़ सकते हैं सम्मानित डरावनी_x द्वारा।

LZW में, LZ77 के "वंशज", शब्दकोश प्रविष्टियां भी दिखाई देती हैं क्योंकि वे डिकोड किए गए हैं, लेकिन यह सिर्फ एक ऑफसेट के साथ नकल नहीं है, बल्कि एक पूर्ण शब्दकोश है।

LZW: सामान्य कोडिंग सिद्धांत

उदाहरण के लिए, एक ही लाइन को लें, " ।"

अब आपको इस स्ट्रिंग के एन्कोडिंग का चयन करने की आवश्यकता है। मल्टीबाइट एन्कोडिंग का उपयोग उदाहरण को बहुत जटिल करेगा, इसलिए कौन यूटीएफ -8 को पूरी तरह से स्थगित कर देगा। सात-बिट एन्कोडिंग्स की राख, जैसे कि KOI-7 H1 (GOST 13052-74), हम परेशान नहीं करेंगे। चलो कुछ आठ-बिट एक का चयन करें, उदाहरण के लिए, प्रिय CP866।

इस प्रकार, मूल शब्द CP866 के समान होगा:

  00000000 <NUL>
 00000001 <SOH>
 ...
 10,000,000 ए
 10000001 बी
 ...
 10011111 आई
 ...
 11111111 <एनबीएसपी> 

इस शब्दकोश को पहले ही भर दिया गया है और इसमें कुछ भी नहीं जोड़ा जाएगा। लेकिन एलजेडडब्ल्यू में, शब्दकोश को हमेशा एक नई प्रविष्टि जोड़ने में सक्षम होना चाहिए। जैसे ही इसके लिए पिछली कोड लंबाई गायब है, इसे बढ़ाना होगा:

  000000000 <NUL>
 ...
 011111111 <NBSP> 

अब, शब्दकोश के सूचकांक को इंगित करने के लिए सात बिट्स का उपयोग किया जाता है (यह "कोड लंबाई" है)। वैसे, जब वे "8 की कोड लंबाई के साथ LZW" जैसा कुछ कहते हैं, तो हमारा मतलब मूल शब्दकोश के कोड की लंबाई से है, हम कोड की लंबाई के साथ कोडिंग शुरू करते हैं। थोड़ा भ्रमित, लेकिन यह वास्तव में है।

लाइन एक राजधानी "ए" से शुरू होती है। द्विआधारी मूल्य 010000000 शब्दकोष में इसके अनुरूप है। हम बिट्स को इस तरह सीधे लिखते हैं, LZW सीधे बिट्स के साथ काम करता है, और तथ्य यह है कि इस एल्गोरिथ्म के लिए एक बाइट आमतौर पर 8 बिट्स से कोई फर्क नहीं पड़ता है।

  और 010000000 (हम शब्दकोश में कुछ भी नहीं जोड़ते हैं) 

अगला पत्र "बी" है। हम इसे उसी तरीके से दर्ज करते हैं, लेकिन अब इसके साथ हम शब्दकोश में एक नया रिकॉर्ड जोड़ते हैं: पिछली एन्कोडेड लाइन और इसके पहले वर्ण। अंतिम पंक्ति "ए" थी, यह एक "बी" थी, और इसका पहला चरित्र, क्रमशः "बी"।

  B 010000001 |  शब्दकोश में जोड़ें = 100000000 

चलो आगे जारी रखें:

  पी 010010000 |  BR = 100000001
 और 1 बिलियन |  आरए = 100000010
 से 010001010 |  AK = 100000011
 और 1 बिलियन |  केए = 100000100
 डी 010000100 |  हेल ​​= १०००००१०१ 

इसके अलावा, कोई "ए" उसी तरह लिख सकता है, लेकिन हमारे पास पहले से ही शब्दकोश में "एबी" है! हम इसका उपयोग करते हैं। और यह मत भूलो कि केवल पहला अक्षर नए शब्दकोश प्रविष्टि में जाता है।

  एबी 100000000 |  YES = 100000111
 आरए 100000010 |  ADB = 100001000
 <सपा> 000100000 |  आरए <एसपी> = 100001001
 से 010010001 |  <SP> C = 100001010
 <सपा> 000100000 |  <SP> = 100001010 के साथ
 एक्स 010010101 |  <SP> X = 100001011 

अब कटहल! हमारे पास पहले से ही शब्दकोश में "एडीबी" है, और हम तीन में एक बार में सिर्फ एक अक्षर डाल सकते हैं। शब्दकोश से सबसे लंबे समय तक मिलान स्ट्रिंग चुनना एक अच्छा विचार है।

  Adb 100001000 |  XA = 100001100
 और 1 बिलियन |  एबीआरए = 100001101
 हा 100001100 |  एएच = 100001110
 बीआर 100000001 |  HUB = 100001111
 और 1 बिलियन |  एआरबी = 100010000 

अब हम सभी प्राप्त बिट्स (दूसरे कॉलम से) को एक पंक्ति में, 8 बाइट्स द्वारा समूह में लिखते हैं और आपका काम हो गया। 24 × 8 = 192 बिट्स के बजाय, 18 × 9 = 162 बिट्स प्राप्त हुए थे। 15% बचत, इस तथ्य के बावजूद कि आरएलई ने एक बिट को बिल्कुल भी नहीं हटाया होगा।

लालच बुरी बला है

एल्गोरिथ्म के विवरण में, यह संकेत दिया गया है कि एन्कोडिंग के दौरान शब्दकोश से सबसे लंबी स्ट्रिंग का चयन करना आवश्यक है। लेकिन जैसा कि ट्रेजर आइलैंड के लड़के बिली के बारे में गीत सिखाता है, लालच सबसे अच्छा विकल्प नहीं है। पिछला उदाहरण लें और थोड़ा पीछे हटें:

  एक 010000000
 B 010000001 |  एबी = 100000000
 पी 010010000 |  BR = 100000001
 और 1 बिलियन |  आरए = 100000010
 से 010001010 |  AK = 100000011
 और 1 बिलियन |  केए = 100000100
 डी 010000100 |  हेल ​​= १०००००१०१
 एबी 100000000 |  YES = 100000111
 आरए 100000010 |  ADB = 100001000
 <सपा> 000100000 |  आरए <एसपी> = 100001001
 से 010010001 |  <SP> C = 100001010
 <सपा> 000100000 |  <SP> = 100001010 के साथ
 एक्स 010010101 |  <SP> X = 100001011
 Adb 100001000 |  XA = 100001100
 और 1 बिलियन |  एबीआरए = 100001101 

इस बिंदु पर हम लालच के खिलाफ जाएंगे और " " शब्दकोष से एक छोटी लाइन, " " चुनेंगे:

  एक्स 010010101 |  एएच = 100001110
 ABRA 100001101 |  XA = 100001111 

अब एन्कोड किए गए संदेश की लंबाई 17 × 9 = 153 बिट्स है, अंतर लगभग 5% है। लेकिन हमने मैन्युअल रूप से फ़ाइल एकत्र की, लेकिन एल्गोरिदम को कैसे निर्धारित किया जाए, लालच के बारे में नहीं? यह माथे में काम नहीं करेगा: प्रत्यक्ष गणना की जटिलता घातीय है। इसलिए, जैसा कि वे सभी प्रकार की स्मार्ट पुस्तकों में कहते हैं, मैं इसे पाठक पर छोड़ दूंगा। हो सकता है कि आपको ट्यूरिंग अवार्ड मिले।

समान मूल्यों का संपीड़न

अब आइए केवल "A" अक्षरों से मिलकर एक आदिम स्ट्रिंग को संपीड़ित करने का प्रयास करें।

  ए |
 ए |  ए.ए.
 एए |  ए.ए.
 एए |  एएए
 एएए |  एएए
 ... 

किसी तरह बहुत प्रभावी नहीं, शब्दकोश डुप्लिकेट के साथ भरा हुआ है। लेकिन इस मामले के लिए, LZW एक मुश्किल चाल प्रदान करता है। दूसरी पंक्ति में, हम शब्दकोश में " " जोड़ते हैं, हालांकि यह प्रविष्टि मौके पर हमारे लिए उपयोगी होगी। वास्तव में, यह वही है जो हम कर सकते हैं:

  ए |
 एए |  ए.ए.
 एएए |  एएए
 ... 

एक नया रिकॉर्ड निर्धारित करने के लिए, केवल पहला कोडित चरित्र प्रासंगिक है। हम उसे निश्चित रूप से जानते हैं, यह " " है। इसलिए, हम पहले शब्दकोश में एक नई प्रविष्टि जोड़ते हैं, और फिर सबसे लंबी लंबाई के साथ स्ट्रिंग के लिए उसमें देखते हैं।

यह दृष्टिकोण न केवल समान अक्षरों के साथ काम करता है, बल्कि लंबे अनुक्रमों के साथ भी काम करता है:

  ए |
 B |  एबी
 एबी |  बीए
 ABA |  ए.बी.ए.
 ... 

आप सोच रहे होंगे कि डिकोडर उनके साथ कैसा व्यवहार करेगा, जब वे उससे कहेंगे: "अब सातवाँ रिकॉर्ड डालें", और शब्दकोश में उनमें से केवल छह हैं। यह ठीक है, वह ऐसी चीजों में प्रशिक्षित है और समस्याओं के बिना समझ जाएगा।

LZW को GIF

खैर, हमने बिल्लियों पर प्रशिक्षण दिया, अब हम वास्तविक कार्यों की ओर मुड़ते हैं। आइए ऐसी सरल छवि के साथ एक GIF बनाएं।



सुविधा के लिए, 8 गुना बढ़ा, वास्तविक आकार: 11 × 6 पिक्सेल, प्रत्येक पट्टी की ऊँचाई 2 पिक्सेल है।

यह किसका झंडा है? कोई नहीं। सिर्फ तीन क्षैतिज पट्टियाँ। लेकिन अगर यह अधिक सुविधाजनक है, तो आप इसे सॉवरेन कलर मॉडल आरजीबी का झंडा मान सकते हैं।

पैलेट का आकार पीसीएक्स में बिल्कुल वैसा ही चुना जाता है - जितना संभव हो उतना छोटा। छवि में केवल तीन रंग हैं, इसलिए हम 4 रंगों के पैलेट का उपयोग करेंगे। आपको याद दिला दूं कि LZW के लिए पैलेट में रंगों का क्रम मायने नहीं रखता है, केवल कोड की लंबाई। फ़ाइल में छवि एक होगी, इसलिए इससे हमें कोई फर्क नहीं पड़ता कि यह स्थानीय होगा या वैश्विक। इसे वैश्विक होने दो।



हम इंटरलेसिंग का उपयोग नहीं करेंगे, हम बस ऊपर से नीचे तक, बाएं से दाएं पिक्सेल का चयन करेंगे। तार्किक स्क्रीन का आकार 11 × 6 है, छवि का आकार समान है, कोड का आकार 2 बिट है, चलो चलते हैं!

हम एक शब्दकोष बनाते हैं:

 00 आर (पैलेट इंडेक्स 0)
01 G (पैलेट इंडेक्स 1)
10 बी (पैलेट इंडेक्स 2)
11 (पैलेट इंडेक्स 3) 

वास्तव में, निश्चित रूप से, एलजेडडब्ल्यू को किसी विशेष रंग के बारे में कोई पता नहीं है, और पैलेट में केवल इसकी संख्या को एन्कोड करता है। लेकिन लिस्टिंग में इतनी संख्या होगी कि हम उनमें उलझने का जोखिम उठाते हैं, इसलिए मैं उन्हें "आर", "जी" और "बी" के रूप में चिह्नित करता हूं।

वह सब नहीं है। शब्दकोश में हम विशेष अर्थ "क्लियर कोड" जोड़ते हैं। यह कुछ भी सांकेतिक शब्दों में बदलना नहीं करता है, यह केवल डिकोडर को निर्देश देता है कि वह अपनी प्रारंभिक अवस्था में शब्दकोश को रीसेट कर दे।

इसके अलावा शब्दकोश में "सूचना का अंत" का एक और विशेष अर्थ है, यह इंगित करता है कि संकुचित धारा समाप्त हो गई है। इसकी आवश्यकता क्यों है?मान लीजिए कि प्रति डिक्शनरी में 4 बिट्स बचे हैं और " 00010010 00110000" का एन्कोडेड वैल्यू है । यह स्पष्ट नहीं है कि इसे 1 2 3किस प्रकार या किस तरह से डिकोड किया जाना है , 1 2 3 0और ईओआई कोड बिट्स के लिए धारा के अंत को इंगित करता है, और समस्या गायब हो जाती है।

कुल मिलाकर, हमारा आरंभिक शब्दकोश इस तरह दिखता है:

 000 आर (पैलेट इंडेक्स 0)
001 G (पैलेट इंडेक्स 1)
010 बी (पैलेट इंडेक्स 2)
011 (पैलेट इंडेक्स 3)
100 <सीसी>
101 <ईओआई>

हम कोड के साथ कोडिंग शुरू करते हैं CC। यह वही है जो विनिर्देश निर्धारित करता है। यह कोड डिक्शनरी में कुछ जोड़ता है या नहीं यह अज्ञात है, क्योंकि यह तुरंत मूल एक पर रीसेट हो जाता है।

 100 <CC> | 

धारा की शुरुआत में इस कोड की आवश्यकता क्यों है अज्ञात है। या यह चौकीदार के पहले कार्यान्वयन में किसी प्रकार की बग के लिए एक समाधान है, जो पहले से ही ग्राहकों को वितरित किया गया है। क्या विनिर्देश के प्रोटोटाइप में, कोड की प्रारंभिक लंबाई इस तरह से निर्धारित की गई थी (शून्य बिट की संख्या इसके बराबर है)। या सिर्फ व्यामोह।

अगला पहला पिक्सेल के लिए कोड है। यदि PCX में हमने 4 बाइट्स को 0 से 3 तक एक बाइट में संभावित मान से चिपकाया है, तो यह GIF में आवश्यक नहीं है।

 000 आर | 

इसके अलावा, ऊपर वर्णित विधि: हम इसके प्रवेश के साथ-साथ शब्दकोश प्रविष्टि का उपयोग करते हैं।

110 आरआर | आरआर = 110
111 आरआरआर | आरआरआर = 111

शब्दकोश भरा हुआ है और इसे एक बिट से बढ़ाने की आवश्यकता है। अगले रिकॉर्ड में पहले से ही 4 बिट्स होंगे।

1000 आरआरआरआर | आरआरआरआर = 1000

10 पिक्सल एन्कोडेड हैं, और एक स्कैनलाइन 11. लेकिन जीआईएफ में स्कैनलाइन के साथ जुड़े प्रतिबंध नहीं हैं - सभी पिक्सल को "एक लाइन में खींचा जाता है" और एक बड़े अनुक्रम के रूप में एन्कोड किया गया है। यदि हम इंटरलेसिंग का उपयोग करते हैं, तो हम आगे ब्लू बैंड लेंगे, जो निश्चित रूप से, संपीड़न पर सकारात्मक प्रभाव नहीं होगा।

1001 आरआरआरआरआर | आरआरआरआरआर = 1001
1010 RRRRRR | आरआरआरआरआरआर = 1010

21 लाल पिक्सेल एनकोडेड, अकेले रह गए। इस बार पिक्सेल चार बिट्स में एन्कोडेड है। इस तथ्य के बावजूद कि RRशब्दकोश में प्रविष्टि " " पहले से मौजूद है, इसे फिर से जोड़ें।

0000 आर | आरआरआरआरआरआर = 1011

ग्रीन पिक्सल के साथ इसी तरह से जारी है।

0001 जी | आरजी = 1100
1101 जीजी | जीजी = 1101
1110 जीजीजी | जीजीजी = 1110
1111 जीजीजीजी | जीजीजी = 1111

फिर से, कोड की लंबाई बढ़ाएं।

10000 GGGGG | GGGGG = 10000
10001 जीजीजीजीजीजी | जीजीजीजीजी = 10001
00001 जी | GGGGGGG = 10010
00010 बी | जीबी = 10011
10100 बीबी | बीबी = 10100
10101 बीबीबी | बीबीबी = 10101
10110 बीबीबीबी | बीबीबीबी = 10110
10111 बीबीबीबीबी | बीबीबीबी = 10111
11000 BBBBBBB | BBBBBBB = 11000
00010 बी | BBBBBBBB = 11001

अंत में, डेटा मार्कर के अंत का संकेत दें।

 00101 <ईओआई> | 

अब प्राप्त बिट्स को प्रति बाइट में आठ टुकड़ों में पैक किया जाता है, सबसे कम उम्र से लेकर सबसे पुराना तक। अनुक्रम से (100) (000) (110) (111) (1000) …हम प्राप्त करते हैं:

 10) (000) (100) = 0x84
(1000) (111) (1 = 0x8F)
 ... 

और ब्लॉक की लंबाई ( 0x0D= 13) की शुरुआत में प्राप्त 13 बाइट्स में जोड़ना न भूलें और 0x00छवि को समाप्त करने के लिए अंत में दिखाएं।

और आखिरकार, क्या हुआ: । काम करने लगता है।

शब्दकोश रीसेट करें

यदि आप बारीकी से देखते हैं, तो यह पता चलता है कि तीन समान आकार की धारियों में, 25 बिट्स लाल पर, 31 बिट्स हरे पर, और 35 नीले पर पहले से ही गिर गए। लेकिन क्या हुआ, मुझे बढ़ते शब्दकोश के साथ काम करने के लिए कोडों का आकार बढ़ाना पड़ा।

लेकिन जब तक हम नीली पट्टी को घेरना शुरू करते हैं, तब तक "लाल" मूल्यों के साथ रिकॉर्ड बेकार हो जाते हैं - वे अब नहीं मिलेंगे। इस मामले में, बहुत ही शब्द सफाई कोड जो अब अपने इच्छित उद्देश्य के लिए इस्तेमाल किया जाएगा, न कि केवल अनुष्ठान के लिए, हमारी मदद करेगा।

चलो लाल पट्टी के अंत में वापस जाते हैं:

 100 <CC> |
000 आर |
110 आरआर | आरआर = 110
111 आरआरआर | आरआरआर = 111
1000 आरआरआरआर | आरआरआरआर = 1000
1001 आरआरआरआरआर | आरआरआरआरआर = 1001
1010 RRRRRR | आरआरआरआरआरआर = 1010
0000 आर | आरआरआरआरआरआर = 1011

आइए शब्दकोश को रीसेट करें, और कोडिंग जारी रखें।

0100 <CC> | (शब्दकोश रीसेट)
001 जी |
110 ग्राम | जीजी = 110
111 जीजीजी | जीजीजी = 111
1000 GGGG | GGGG = 1000
1001 GGGGG | GGGGG = 1001
1010 GGGGGG | GGGGGG = 1010
0001 जी | GGGGGGG = 1011

और एक बार और।

0100 <CC> | (शब्दकोश रीसेट)
010 बी |
110 बीबी | बीबी = ११०
111 बीबीबी | बीबीबी = 111
1000 बीबीबीबी | BBBB = 1000
1001 बीबीबीबी | BBBBB = 1001
1010 BBBBBB | BBBBBBB = 1010
0010 बी | BBBBBBBB = 1011
0101 <ईओआई> | 

यह 90 बिट्स निकला, और कुल फ़ाइल का आकार 52 से 51 बाइट्स तक कम हो गया, जबकि शेष पठनीय: ।और यहाँ, GIF संपीड़न के लिए gifsicle, टूल नंबर एक, जैसे अब संपीड़ित नहीं हो सकता।

वैसे, आप देख सकते हैं कि सभी तीन बैंड लगभग समान थे। LZW के लिए " 0x0022 बार" और " 0x0222 बार" के बीच कोई अंतर नहीं है , और आप पैलेट में किसी भी रंग की व्यवस्था चुन सकते हैं।

गैरमानक

उन्माद का एक सा। स्ट्रीम के बहुत शुरुआत में डिक्शनरी कोड ("CC") कुछ भी प्रभावित नहीं करता है। और अंत में धारा का कोड ("ईओआई"), सामान्य रूप से आवश्यक नहीं है - यदि कोई डेटा बाइट की पूंछ में रहता है, तो यह पहले से ही छवि के बाहर होगा। उन्हें काटने के बाद, हम 50 बाइट तक तस्वीर को और भी अधिक सिकोड़ सकते हैं, और यह सामान्य रूप से ब्राउज़रों में प्रदर्शित होगा: ।

यदि आप एक ऐसे ब्राउज़र के खुश मालिक हैं जिसमें यह दिखाई नहीं देता है, तो कृपया टिप्पणियों में सदस्यता समाप्त करें।

लेकिन एक है लेकिन, और यह एक "लेकिन" मौलिक है: यह विनिर्देश का उल्लंघन है। क्या यह एक बाइट को बचाने के लायक है - अपने लिए तय करें।

GIF एनिमेटेड

आज, शायद, यह जीआईएफ का एकमात्र उपयोग है। गैर-एनिमेटेड आइकन और चित्रों के लिए, पीएनजी बहुत ठंडा है। लेकिन, दुर्भाग्य से, PNG- आधारित एनिमेटेड छवि प्रारूप ने "बंद नहीं किया है": APNG एक W3C मानक नहीं है, और केवल आधे ब्राउज़रों द्वारा समर्थित है; और मानक W3C की आह एमएनजी आमतौर पर स्थिर होती है। यह पुराने जीआईएफ के लिए थोड़ी अधिक देर तक जीना संभव बनाता है।

विनिर्देश याद करें। छवि विस्तार सेंटीसेकंड में देरी , पारदर्शी रंग और तार्किक स्क्रीन के साथ आगे क्या करने के लिए इंगित करता है । फिर छवि ही। फिर फिर से छवि और छवि का विस्तार, और इसी तरह अंत तक।

रचना

यहां हमें मुख्य बात से शुरू करना चाहिए: यदि केवल 2 × 2 वर्ग एक नए फ्रेम के साथ 800 × 600 की तार्किक स्क्रीन पर बदल गया है, तो यह 2 × 2 का फ्रेम बनाने के लिए समझ में आता है, न कि 800 × 600। मुझे लगता है कि यह तर्कसंगत है। लेकिन, अफसोस, इस तरह के विश्लेषण से सभी छवि प्रसंस्करण कार्यक्रम परेशान नहीं होते हैं, और जीआईएफ अनुकूलन के शेर की हिस्सेदारी इस तुच्छ त्रुटि का सुधार है।

और अब विवरण के लिए, छवि विस्तार के निपटान विधि क्षेत्र के लिए, जो इंगित करता है कि एक नया दिखाने से पहले फ्रेम के साथ क्या करना है। मैं थोड़ा दोहराता हूं:

विभिन्न योगों में मान 0 और 1 यह दर्शाता है कि रेंडरर कुछ भी नहीं करता है। यही है, अगले फ्रेम के पिक्सल को सीधे शीर्ष पर खींचा जाना चाहिए (पारदर्शी लोगों को छोड़कर, निश्चित रूप से)।

मान 2 - एक नया फ्रेम दिखाने से पहले, तार्किक स्क्रीन से सब कुछ हटा दें। विनिर्देश के अनुसार, तार्किक स्क्रीन को पृष्ठभूमि के रंग से भरा होना चाहिए, व्यवहार में, यह पूरी तरह से पारदर्शी हो जाता है।

मान 3 सबसे दिलचस्प है - अगला फ्रेम दिखाने से पहले, वर्तमान फ्रेम दिखाए जाने से पहले सब कुछ वापस कर दें। तो, जब एन्कोडिंग, कहते हैं, पांचवें फ्रेम, यह न केवल चौथे के साथ अंतर को निर्धारित करने के लिए सार्थक है, बल्कि तीसरे के साथ - अचानक यह बेहतर संपीड़ित करेगा।

पारदर्शी रंग

कृपया ध्यान दें कि एक पारदर्शी रंग प्रत्येक छवि के लिए निर्दिष्ट है, भले ही एक वैश्विक पैलेट का उपयोग किया जाए। यह हमें क्या दे सकता है? आइए तस्वीर को देखें:

कितने फूल हैं? लाल, हरा, नीला, पीला और पारदर्शी पांच हैं। ठीक ऐसा ही GIMP और Photoshop भी सोचते हैं। लेकिन वे गलत हैं - केवल चार रंग हैं। सभी चार चित्र फ़्रेम बिल्कुल समान हैं, और एक वैश्विक पैलेट का उपयोग करते हैं। अंतर केवल छवि एक्सटेंशन में है जो उनके सामने खड़ा है, प्रत्येक रंग को वैकल्पिक रूप से पारदर्शी घोषित किया गया है।

कोड पैलेट और आकार

यद्यपि LZW कोड का आकार आमतौर पर पैलेट के आकार (बिट्स की संख्या) के बराबर होता है, चश्मा में ऐसी कोई आवश्यकता नहीं होती है। यह केवल आवश्यक है कि एन्कोड किए गए मान खुद को मौजूदा पैलेट सूचकांकों के लिए संदर्भित करते हैं, और यदि आप अंतरिक्ष को ध्यान में नहीं रखते हैं तो आप कम से कम 24-बिट कोड का उपयोग कर सकते हैं।

तदनुसार, छोटे कोड आकारों का उपयोग करना संभव है, इसलिए सभी पैलेट इंडेक्स उपलब्ध नहीं होंगे। पहली नज़र में, यह किसी भी तरह से व्यर्थ है, हालांकि, यह रिसीवर काम में आ सकता है।

उदाहरण के लिए चित्र होगा ... हम्म ... चलो फिर से एक यूएफओ प्राप्त करें! एनीमेशन को सरल होने दें, बस दो फ्रेम।



8 रंगों का एक वैश्विक पैलेट:



पहले फ्रेम में हम सभी आठ का उपयोग करते हैं, जबकि यह दर्शाता है कि ऑफसेट 0 (हल्का नीला) पर रंग पारदर्शी माना जाता है।



दूसरे फ्रेम में, हमें वैश्विक पैलेट के केवल पहले दो रंगों की आवश्यकता है: हल्का नीला और ग्रे। और इस बार यह पारदर्शी ग्रे (ऑफसेट 1 पर) होगा। और यहां हम LZW कोड के आकार को दो बिट्स तक कम कर सकते हैं। यह पता चलता है कि आठ रंगों में से, हम केवल 0 से 3 तक ही रंगों को एनकोड कर सकते हैं, लेकिन हमें इससे अधिक की आवश्यकता नहीं है। यह एक तक हो सकता था, लेकिन विनिर्देश के अनुसार कोड का न्यूनतम आकार 2 है। हम

जांचते हैं कि क्या यह काम करता है?



यह काम करता है। ठीक है, तो हम GIFs को एक और वॉइला में गोंद कर देते हैं!

तस्वीर "वजन" 437 बाइट्स। यदि हम एक स्थानीय पैलेट का उपयोग करते हैं, तो फ़ाइल 6 बाइट्स अधिक, 443 बाइट्स लेगी। और अगर हमने वैश्विक पैलेट बढ़ा दिया, जैसा कि फ़ोटोशॉप का सुझाव है, तो यह पहले से ही 469 बाइट्स है, और यह पहले से ही लगभग 7% अंतर है।

कुल मिलाकर

हम संक्षेप में बताते हैं। GIF अनुकूलन तकनीक:

• छवि एक्सटेंशन सहित अनावश्यक ब्लॉकों को हटाना;
• न्यूनतम संभव रंग गहराई (पैलेट आकार) का चयन;
• छवि फ़्रेम का आकार कम से कम करना;
• एक स्थानीय पैलेट का उपयोग करना;
• लालच LZW से प्रस्थान;
• शब्दकोश रीसेट LZW;
• प्रगतिशील या इंटरलेस्ड स्कैनिंग (यदि लागू हो) के बीच का विकल्प;
• फ्रेम की सफाई के तरीकों का उपयोग करना: "छोड़ना", "स्पष्ट", "रद्द करना" (केवल एनीमेशन के लिए);
• पारदर्शी रंगों का "पुन: उपयोग" (केवल एनीमेशन के लिए);
• कोड के आकार को कम करने के लिए पैलेट का अनुकूलन (केवल एनीमेशन के लिए)।

यह काम करता है, लेकिन प्रोत्साहित नहीं किया जाता है:

• शुरुआत में LZW स्ट्रीम एंड मार्कर और डिक्शनरी रीसेट कोड हटाता है।

जारी रखा जाए

आज के लिए बस इतना ही। और अगला, अंतिम भाग पीएनजी ग्राफिक प्रारूप और इसका डेरिवेटिव है।