भग्न छवि संपीड़न की मूल बातें

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

शुरू करने के लिए, आपको अभी भी गणित में थोड़ा गहरा जाना होगा और कई परिभाषाओं को पेश करना होगा।
निम्नलिखित काम आएगा:

• एक मीट्रिक एक अंतरिक्ष पर परिभाषित एक फ़ंक्शन है जो इस स्थान के दो बिंदुओं के बीच की दूरी को वापस करता है। उदाहरण के लिए, सामान्य यूक्लिडियन मीट्रिक। यदि कोई स्थान मीट्रिक दिया जाता है, तो उसे मीट्रिक कहा जाता है। मीट्रिक को कुछ शर्तों को पूरा करना चाहिए, लेकिन हम गहराई तक नहीं जाएंगे।
• एक संकुचन मानचित्रण (परिवर्तन) मीट्रिक अंतरिक्ष पर एक फ़ंक्शन है जो अंतरिक्ष में दो बिंदुओं के बीच की दूरी को समान रूप से कम करता है। उदाहरण के लिए, y = 0.5x।

संपीड़न मैपिंग में एक महत्वपूर्ण संपत्ति है। यदि हम कोई बिंदु लेते हैं और पुनरावृत्ति को उसी संकुचन मानचित्र पर लागू करना शुरू करते हैं: f (f (f (f ... f (x))), तो परिणाम हमेशा एक ही बिंदु होगा। जितनी बार हम आवेदन करते हैं, उतने ही सटीक रूप से हम इस बिंदु को पाते हैं। इसे एक निश्चित बिंदु कहा जाता है , और प्रत्येक कंप्रेसिव मैपिंग के लिए यह मौजूद है, और केवल एक।

कई चक्करदार संकुचन मैपिंग, संचालित कार्यों (सीआईएफ) की एक प्रणाली बनाते हैं। वास्तव में, सीआईएफ एक गुणक मशीन है। यह मूल छवि लेता है, इसे विकृत करता है, इसे स्थानांतरित करता है, और इसी तरह कई बार।
उदाहरण के लिए, CIF की सहायता से, Sierpinski त्रिभुज तीन कार्यों से बना है:



मूल त्रिकोण तीन बार गुणा करता है, घटता है और स्थानांतरित होता है। और इसी तरह। यदि हम अनंत तक इस तरह जारी रखते हैं, तो हमें 0 के क्षेत्र और 1.585 के आयाम के साथ एक प्रसिद्ध फ्रैक्टल मिलता है।

यदि CIF में शामिल फ़ंक्शन कंप्रेसिव हैं, तो CIF का भी एक निश्चित बिंदु है। लेकिन यह "बिंदु" अब एन-आयामी अंतरिक्ष में एक परिचित बिंदु नहीं होगा, लेकिन ऐसे बिंदुओं का एक सेट है, जो एक छवि है। इसे CIF अट्रैक्टर कहा जाता है। CIF के लिए, ऊपर, Sierpinski त्रिभुज एक आकर्षण होगा।

यहां हम अगले स्तर पर जाते हैं - छवि स्थान। इस अंतरिक्ष में:

• अंतरिक्ष का एक बिंदु एक छवि है।
• बिंदुओं के बीच की दूरी से पता चलता है कि चित्र एक-दूसरे के समान हैं, कैसे "करीब" (स्वाभाविक रूप से, यदि आप इसे तदनुसार सेट करते हैं)।
• संपीड़न मानचित्रण किसी भी दो छवियों को अधिक समान बनाता है (किसी दिए गए मीट्रिक के अर्थ में)।

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



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

यहां, वास्तव में, समस्याएं शुरू होती हैं। फ्रैक्चर्स के विपरीत मनमानी छवियां आत्म-समान नहीं हैं, इसलिए यह कार्य इतनी आसानी से हल नहीं होता है। यह कैसे करना है इसका आविष्कार 1992 में अर्नोल्ड जैक्विन ने किया था, जबकि वह माइकल बार्न्सले के स्नातक छात्र थे, जिन्हें भग्न संपीड़न का जनक माना जाता है।

हमें आत्म-समानता की आवश्यकता है - अन्यथा परिवर्तन को सीमित करें, उनकी क्षमताओं में सीमित, छवियों को वास्तविकता के करीब लाने में सक्षम नहीं होंगे। और अगर यह भाग और पूरे के बीच नहीं है, तो आप भाग और भाग के बीच खोज कर सकते हैं। जाहिरा तौर पर, जैक्विन ने लगभग उसी तरह तर्क दिया।

एक सरलीकृत कोडिंग योजना इस प्रकार है:

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

तस्वीर में, रैंकिंग ब्लॉक पीले रंग में चिह्नित किया गया है, जो लाल रंग में एक ही डोमेन है। रूपांतरण और परिणाम के चरणों को भी दिखाया गया है।



आप इसे स्वयं खेल सकते हैं: कोडर डेमो ।

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

डिकोडिंग सरल और काफी त्वरित है। हम किसी भी छवि को लेते हैं, इसे रैंकिंग क्षेत्रों में विभाजित करते हैं, क्रमिक रूप से सम्मान को लागू करने के परिणामस्वरूप उन्हें प्रतिस्थापित करते हैं। एसीसी में रूपांतरण। डोमेन क्षेत्र (जो कुछ भी इस समय है)। कई पुनरावृत्तियों के बाद, मूल छवि स्वयं की तरह दिखाई देगी:



शायद जानकारी शुरू करने के लिए पर्याप्त है। जो लोग रुचि रखते हैं वे विकिपीडिया या संबंधित समुदाय पर प्रासंगिक लेख पढ़ सकते हैं।

इस लेख में एक विस्तृत विवरण पाया जा सकता है, जिसके साथ यह सब 1992 में शुरू हुआ। अधिकांश सामग्री, निश्चित रूप से, अंग्रेजी में हैं।