छवि संपीड़न एल्गोरिदम

यह गणना करना आसान है कि 2000 * 1000 पिक्सेल के आकार के साथ एक असम्पीडित पूर्ण-रंग की छवि का आकार लगभग 6 मेगाबाइट होगा। यदि हम पेशेवर कैमरों या उच्च-रिज़ॉल्यूशन स्कैनर से प्राप्त छवियों के बारे में बात करते हैं, तो उनका आकार और भी बड़ा हो सकता है। भंडारण उपकरणों की क्षमता में तेजी से वृद्धि के बावजूद, विभिन्न छवि संपीड़न एल्गोरिदम अभी भी बहुत प्रासंगिक हैं।
सभी मौजूदा एल्गोरिदम को दो बड़े वर्गों में विभाजित किया जा सकता है:

• दोषरहित संपीड़न एल्गोरिदम;
• हानिपूर्ण संपीड़न एल्गोरिदम।

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

दोषरहित संपीड़न एल्गोरिदम

RLE एल्गोरिथम

आरएलई श्रृंखला के सभी एल्गोरिदम एक बहुत ही सरल विचार पर आधारित हैं: तत्वों के दोहराए जाने वाले समूहों को एक युगल (दोहराए जाने वाले तत्व, दोहराए जाने वाले तत्व) द्वारा प्रतिस्थापित किया जाता है। बिट्स के अनुक्रम के उदाहरण के रूप में इस एल्गोरिथ्म पर विचार करें। शून्य और लोगों के समूह इस क्रम में वैकल्पिक होंगे। इसके अलावा, समूहों में अक्सर एक से अधिक तत्व होंगे। फिर अनुक्रम 11111 000000 11111111 00 संख्या 5 6 8 के निम्नलिखित सेट के अनुरूप होगा। ये संख्या दोहराव की संख्या (इकाइयों के साथ गिनती शुरू होती है) को इंगित करती है, लेकिन इन नंबरों को भी एन्कोड किया जाना चाहिए। हम मानते हैं कि पुनरावृत्ति की संख्या 0 से 7 तक होती है (यानी, 3 बिट्स हमारे लिए दोहराव की संख्या को एनकोड करने के लिए पर्याप्त हैं)। फिर ऊपर माना गया क्रम संख्या 5 6 7 0 1 के निम्नलिखित अनुक्रम द्वारा एन्कोडेड है। यह गणना करना आसान है कि मूल अनुक्रम को एन्कोड करने के लिए 21 बिट्स की आवश्यकता होती है, और RLE- संपीड़ित रूप में यह अनुक्रम 18 बिट्स लेता है।
यद्यपि यह एल्गोरिथ्म बहुत सरल है, इसकी प्रभावशीलता अपेक्षाकृत कम है। इसके अलावा, कुछ मामलों में, इस एल्गोरिथ्म के अनुप्रयोग में कमी नहीं होती है, लेकिन अनुक्रम की लंबाई में वृद्धि के लिए। उदाहरण के लिए, निम्नलिखित अनुक्रम पर विचार करें 111 0000 11111111 00. इसी RL अनुक्रम इस तरह दिखता है: 3 4 7 0 1 2. मूल अनुक्रम की लंबाई 17 बिट्स है, संपीड़ित अनुक्रम की लंबाई 18 बिट्स है।
यह एल्गोरिदम काले और सफेद चित्रों के लिए सबसे प्रभावी है। इसे अक्सर अधिक जटिल एल्गोरिदम को संपीड़ित करने के मध्यवर्ती चरणों में से एक के रूप में भी उपयोग किया जाता है।

शब्द एल्गोरिदम

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

यह तालिका सूचना को संपीड़ित करने वाले के पक्ष में है, और जो अनपैक करता है, उसकी ओर है। अब हम संपीड़न प्रक्रिया पर विचार करेंगे।


तालिका शब्दकोश को भरने की प्रक्रिया को दर्शाती है। यह गणना करना आसान है कि परिणामी संपीड़ित कोड 105 बिट्स लेता है, और स्रोत पाठ (बशर्ते कि हम एक चरित्र एन्कोडिंग पर 4 बिट्स खर्च करते हैं) 116 बिट्स।
वास्तव में, डिकोडिंग प्रक्रिया कोड के प्रत्यक्ष डिक्रिप्शन के लिए कम हो जाती है, और यह महत्वपूर्ण है कि एन्कोडिंग के दौरान तालिका को भी प्रारंभ किया जाता है। अब डिकोडिंग एल्गोरिथ्म पर विचार करें।

I-th स्टेप में डिक्शनरी में जोड़ी गई लाइन केवल i + 1 पर पूरी तरह से निर्धारित की जा सकती है। जाहिर है, i-th लाइन i + 1 लाइनों के पहले चरित्र के साथ समाप्त होनी चाहिए। इस प्रकार हमने केवल यह पता लगाया कि शब्दकोश को कैसे पुनर्स्थापित किया जाए। कुछ रुचियों में से वह स्थिति है जब प्रपत्र cScSc का एक क्रम एन्कोडेड होता है, जहाँ c एक वर्ण होता है और S एक स्ट्रिंग होता है, और cS शब्द पहले से ही शब्दकोश में है। पहली नज़र में, ऐसा लग सकता है कि डिकोडर इस स्थिति को हल करने में सक्षम नहीं होगा, लेकिन वास्तव में इस प्रकार की सभी लाइनें हमेशा उसी चरित्र के साथ समाप्त होनी चाहिए, जिसके साथ वे शुरू होते हैं।

सांख्यिकीय एन्कोडिंग एल्गोरिदम

इस श्रृंखला के एल्गोरिदम सबसे लगातार अनुक्रम तत्वों को सबसे छोटा संपीड़ित कोड देते हैं। यानी एक ही लंबाई के अनुक्रम विभिन्न लंबाई के संकुचित कोड द्वारा एन्कोड किए गए हैं। इसके अलावा, अधिक बार अनुक्रम होता है, इसी संकुचित कोड छोटा है।

हफ़मैन एल्गोरिदम

हफ़मैन एल्गोरिथ्म आपको उपसर्ग कोड बनाने की अनुमति देता है। आप एक बाइनरी ट्री पर पथ के रूप में उपसर्ग कोड पर विचार कर सकते हैं: एक नोड से उसके बाएं बेटे को पास करना कोड में 0 से मेल खाता है, और दाहिने बेटे के लिए - 1. यदि हम एन्कोड किए गए वर्णों के साथ पेड़ की पत्तियों को चिह्नित करते हैं, तो हमें बाइनरी ट्री के रूप में उपसर्ग कोड का प्रतिनिधित्व मिलता है।
हम एक हफ़मैन पेड़ के निर्माण और हफ़मैन कोड प्राप्त करने के लिए एक एल्गोरिथ्म का वर्णन करते हैं।

1. इनपुट वर्णमाला के वर्ण मुक्त नोड्स की एक सूची बनाते हैं। प्रत्येक शीट में एक वजन होता है जो प्रतीक की घटना की आवृत्ति के बराबर होता है
2. सबसे छोटे वज़न वाले दो फ्री ट्री नोड चुने गए हैं
3. उनके माता-पिता को उनके कुल वजन के बराबर वजन के साथ बनाया गया है
4. एक माता-पिता को मुफ्त नोड्स की सूची में जोड़ा जाता है, और उनके दो बच्चों को इस सूची से हटा दिया जाता है।
5. एक चाप जो माता-पिता को छोड़ देता है उसे बिट 1 में मैप किया जाता है, दूसरे को बिट 0 में
6. दूसरे से शुरू होने वाले चरणों को तब तक दोहराया जाता है जब तक कि केवल एक मुक्त नोड मुक्त नोड्स की सूची में न रह जाए। इसे पेड़ की जड़ माना जाएगा।

इस एल्गोरिथ्म का उपयोग करके, हम किसी वर्णमाला के लिए हफ़मैन कोड प्राप्त कर सकते हैं, पात्रों की घटना की आवृत्ति को ध्यान में रखते हुए।

अंकगणित कोडिंग

अंकगणित कोडिंग एल्गोरिदम एक अंश में तत्वों की जंजीरों को कूटबद्ध करता है। इस मामले में, तत्वों के आवृत्ति वितरण को ध्यान में रखा जाता है। फिलहाल, अंकगणित कोडिंग एल्गोरिदम पेटेंट द्वारा संरक्षित हैं, इसलिए हम केवल मुख्य विचार पर विचार करेंगे।
हमारी वर्णमाला में N अक्षर a1, ..., A, और उनकी आवृत्ति p1, ..., pN, क्रमशः शामिल हैं। हम आधे अंतराल को [0; 1) में विभाजित करते हैं, जो कि आधे-अंतराल को नापसंद करते हैं। प्रत्येक आधा-अंतराल तत्वों एआई से मेल खाता है, जबकि आधे-अंतराल की लंबाई आवृत्ति पी के लिए आनुपातिक है।
कोडिंग अंश का निर्माण निम्नानुसार किया जाता है: नेस्टेड अंतराल की एक प्रणाली का निर्माण किया जाता है ताकि मूल विभाजन में तत्व की स्थिति के अनुरूप प्रत्येक बाद का आधा अंतराल पिछली जगह पर ले जाए। सभी अंतराल एक-दूसरे के भीतर होने के बाद, आप परिणामी आधे-अंतराल में से कोई भी संख्या ले सकते हैं। इस संख्या को बाइनरी कोड में लिखना एक संपीड़ित कोड होगा।
डिकोडिंग - ज्ञात संभावना वितरण के अनुसार अंशों को डिकोड करना। जाहिर है, डिकोडिंग के लिए, आवृत्ति तालिका को संग्रहीत करना आवश्यक है।
अंकगणित कोडिंग बेहद कुशल है। इसकी मदद से प्राप्त कोड सैद्धांतिक सीमा के करीब पहुंच रहे हैं। इससे पता चलता है कि पेटेंट की अवधि समाप्त होने के साथ, अंकगणित कोडिंग अधिक से अधिक लोकप्रिय हो जाएगी।

हानिपूर्ण संपीड़न एल्गोरिदम

कई अत्यधिक कुशल दोषरहित संपीड़न एल्गोरिदम के बावजूद, यह स्पष्ट हो जाता है कि ये एल्गोरिदम संपीड़न की पर्याप्त डिग्री प्रदान नहीं कर सकते (और नहीं कर सकते हैं)।
हानिपूर्ण संपीड़न (जैसा कि छवियों पर लागू होता है) मानव दृष्टि की विशेषताओं पर आधारित है। हम जेपीईजी छवि संपीड़न एल्गोरिदम के पीछे मूल विचारों को कवर करेंगे।

JPEG संपीड़न एल्गोरिथम

JPEG वर्तमान में सबसे आम हानिपूर्ण छवि संपीड़न विधियों में से एक है। हम इस एल्गोरिथ्म में अंतर्निहित बुनियादी चरणों का वर्णन करते हैं। हम मानते हैं कि पिक्सेल प्रति 24 बिट्स की रंग गहराई वाली छवि संपीड़न एल्गोरिदम के लिए इनपुट है (छवि को RGB रंग मॉडल में प्रस्तुत किया गया है)।

YCbCr रंग स्थान में कनवर्ट करें

YCbCr रंग मॉडल में, हम छवि को ल्यूमिनेंस घटक (Y) और दो रंग-अंतर घटकों (Cb, Cr) के रूप में प्रस्तुत करते हैं। रंग के बजाय चमक के लिए मानव आंख अधिक संवेदनशील होती है, इसलिए जेपीईजी एल्गोरिथ्म ल्यूमिनेंस घटक (वाई) में न्यूनतम संभव परिवर्तन करता है, और रंग अंतर घटकों में महत्वपूर्ण बदलाव किए जा सकते हैं। स्थानांतरण निम्नलिखित सूत्र के अनुसार किया जाता है:

Kr और Kb का चुनाव उपकरण पर निर्भर करता है। आमतौर पर Kb = 0.114; Kr = 0.299। हाल ही में, Kb = 0.0722; Kr = 0.2126 का भी उपयोग किया गया है, जो आधुनिक प्रदर्शन उपकरणों की विशेषताओं को बेहतर ढंग से दर्शाता है।

रंग घटकों के उप-नमूने

YCbCr रंग अंतरिक्ष में अनुवाद के बाद, विवेक का प्रदर्शन किया जाता है। तीन नमूनों में से एक विधि संभव है:
4

• : 4: 4 - कोई डाउनसमलिंग नहीं;
• 4: 2: 2 - रंग घटक क्षैतिज रूप से एक के माध्यम से बदलते हैं;
• 4: 2: 0 - रंग घटक एक पंक्ति के माध्यम से क्षैतिज रूप से बदलते हैं, जबकि लंबवत रूप से वे एक रेखा के माध्यम से बदलते हैं।

दूसरी या तीसरी विधि का उपयोग करते समय, हमें क्रमशः 1/3 या 1/2 जानकारी से छुटकारा मिल जाता है। जाहिर है, हम जितनी अधिक जानकारी खोते हैं, अंतिम छवि में विकृतियां उतनी ही मजबूत होती हैं।

असतत कोसाइन रूपांतरण

छवि को घटकों में विभाजित किया जाता है 8 * 8 पिक्सल, डीसीटी प्रत्येक घटक पर लागू होता है। इससे कोड में ऊर्जा संघनन होता है। ट्रांसफार्मर स्वतंत्र रूप से घटकों पर लागू होते हैं।

परिमाणीकरण

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

ज़िगज़ैग मैट्रिक्स बायपास

Zigzag मैट्रिक्स बाईपास आकृति में दिखाए गए बाईपास की एक विशेष दिशा है:

इसके अलावा, अधिकांश वास्तविक छवियों के लिए, गैर-शून्य गुणांक शुरुआत में जाएंगे, और शून्य अंत तक करीब जाएंगे।

RLE एन्कोडिंग

RLE कोडिंग का एक विशेष प्रकार का उपयोग किया जाता है: संख्याओं के जोड़े आउटपुट होते हैं, जोड़ी में पहला नंबर शून्य की संख्या को एन्कोड करता है, और दूसरा - शून्य के अनुक्रम के बाद मान। यानी अनुक्रम के लिए कोड 0 0 15 42 0 0 0 44 निम्नलिखित होंगे (2; 15) (0; 42) (3; 44)।

हफमैन कोडिंग

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

भग्न संपीड़न

भग्न संपीड़न एक अपेक्षाकृत नया क्षेत्र है। भग्न एक जटिल ज्यामितीय आकृति है जिसमें आत्म-समानता की संपत्ति होती है। भग्न संपीड़न एल्गोरिदम को अब सक्रिय रूप से विकसित किया जा रहा है, लेकिन उन्हें अंतर्निहित विचारों को कार्यों के निम्नलिखित अनुक्रम द्वारा वर्णित किया जा सकता है।
संपीड़न प्रक्रिया:

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

छवि पुनर्प्राप्ति चरण:

1. एक ही आकार ए और बी की दो छवियां बनाना क्षेत्रों के आकार और सामग्री से कोई फर्क नहीं पड़ता।
2. छवि बी को उसी तरह से डोमेन में विभाजित किया जाता है जैसे कि संपीड़न प्रक्रिया के पहले चरण में। क्षेत्र बी के प्रत्येक डोमेन के लिए, छवि ए के रैंक क्षेत्रों के संबंधित affine परिवर्तन किया जाता है, जिसे संपीड़ित फ़ाइल से गुणांक द्वारा वर्णित किया जाता है। परिणाम को क्षेत्र बी में रखा गया है। रूपांतरण के बाद, एक पूरी तरह से नई छवि प्राप्त की जाती है।
3. डेटा को क्षेत्र B से क्षेत्र A में परिवर्तित करना। यह चरण 3 चरण को दोहराता है, केवल छवियाँ A और B उलट हैं।
4. चरण 3 और 4 तब तक दोहराए जाते हैं जब तक कि चित्र A और B अप्रभेद्य न हो जाएं।

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