दर-विरूपण सिद्धांत

दर-विरूपण सिद्धांत सूचना सिद्धांत की एक प्रमुख शाखा है जो लोसी डेटा कम्प्रेशन के लिए सैद्धांतिक आधार प्रदान करती है, यह दर R द्वारा मापी गई प्रति प्रतीक बिट्स की न्यूनतम संख्या निर्धारित करने की समस्या को संबोधित करती है जिसे एक चैनल पर संचारित किया जाना चाहिए जिससे स्रोत (इनपुट संकेत) को अपेक्षित विरूपण से अधिक हुए बिना रिसीवर (आउटपुट संकेत) पर प्रायः पुनर्निर्मित किया जा सकता है

परिचय

दर विरूपण एनकोडर और डिकोडर। एनकोडर $f_{n}$ अनुक्रम को एन्कोड करता है $X^{n}$. एन्कोडेड अनुक्रम $Y^{n}$ फिर डिकोडर को फीड किया जाता है $g_{n}$ जो अनुक्रम आउटपुट करता है ${\hat {X}}^{n}$. हम मूल अनुक्रम के मध्य विकृति को कम करने का प्रयास करते हैं $X^{n}$ और पुनर्निर्मित अनुक्रम ${\hat {X}}^{n}$.

इस प्रकार दर-विरूपण सिद्धांत विश्लेषणात्मक अभिव्यक्ति देता है कि लोसी कम्प्रेशन विधियों का उपयोग करके कितना कम्प्रेशन प्राप्त किया जा सकता है। वर्तमान ऑडियो, भाषण, इमेज और वीडियो कम्प्रेशन तकनीकों में से विभिन्न परिवर्तन, परिमाणीकरण और बिट-दर आवंटन प्रक्रियाएं हैं जो दर-विरूपण फलन के सामान्य आकार का लाभ उठाती हैं।

इस प्रकार दर-विरूपण सिद्धांत क्लाउड शैनन द्वारा सूचना सिद्धांत पर अपने मूलभूत फलन में बनाया गया था।

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

विरूपण फलन

इस प्रकार विरूपण फलन किसी प्रतीक $x$ को अनुमानित प्रतीक ${\hat {x}}$ द्वारा दर्शाने की निवेश को मापते हैं। विशिष्ट विरूपण फलन हैमिंग विरूपण और स्क्वेर्ड-त्रुटि विरूपण हैं।

हैमिंग विरूपण

$d(x,{\hat {x}})={\begin{cases}0&{\text{if }}x={\hat {x}}\\1&{\text{if }}x\neq {\hat {x}}\end{cases}}$

वर्ग-त्रुटि विरूपण

$d(x,{\hat {x}})=\left(x-{\hat {x}}\right)^{2}$

दर-विरूपण फलन

इस प्रकार दर और विरूपण से संबंधित फलन निम्नलिखित न्यूनतमकरण समस्या के समाधान के रूप में पाए जाते हैं:

$\inf _{Q_{Y\mid X}(y\mid x)}I_{Q}(Y;X){\text{ subject to }}D_{Q}\leq D^{*}.$

यहाँ $Q_{Y\mid X}(y\mid x)$ को कभी-कभी परीक्षण चैनल भी कहा जाता है जो किसी दिए गए इनपुट (मूल संकेत) $X$ के लिए संचार चैनल आउटपुट (संपीड़ित संकेत) $Y$ का नियमबद्ध संभाव्यता घनत्व फलन (पीडीएफ) है, इस प्रकार $I_{Q}(Y;X)$ $Y$ और $X$ के मध्य पारस्परिक जानकारी को इस प्रकार परिभाषित किया गया है

$I(Y;X)=H(Y)-H(Y\mid X)\,$

जहाँ $H(Y)$ और $H(Y\mid X)$ क्रमशः आउटपुट संकेत Y की एन्ट्रापी और इनपुट संकेत दिए गए आउटपुट संकेत की नियमबद्ध एन्ट्रापी हैं:

$H(Y)=-\int _{-\infty }^{\infty }P_{Y}(y)\log _{2}(P_{Y}(y))\,dy$

$H(Y\mid X)=-\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)\log _{2}(Q_{Y\mid X}(y\mid x))\,dx\,dy.$

इस प्रकार समस्या को विरूपण-दर फलन के रूप में भी तैयार किया जा सकता है, जहां हम दी गई दर अवरोध के लिए प्राप्त करने योग्य विकृतियों पर न्यूनतम और सर्वोच्च पाते हैं। प्रासंगिक अभिव्यक्ति है:

$\inf _{Q_{Y\mid X}(y\mid x)}E[D_{Q}[X,Y]]{\text{ subject to }}I_{Q}(Y;X)\leq R.$

दोनों सूत्रीकरण ऐसे फलन को उत्पत्ति देते हैं जो दूसरे के व्युत्क्रम हैं।

इस प्रकार पारस्परिक जानकारी को प्रेषक के संकेत (H(Y)) के बारे में प्राप्तकर्ता की 'पूर्व' अनिश्चितता के उपाय के रूप में समझा जा सकता है, जो प्रेषक के संकेत $H(Y\mid X)$ के बारे में जानकारी प्राप्त करने के पश्चात् छोड़ी गई अनिश्चितता से कम हो जाती है। निश्चित रूप से अनिश्चितता में कमी है संप्रेषित सूचना की मात्रा के कारण जो $I\left(Y;X\right)$ है

उदाहरण के तौर पर, यदि कोई संचार नहीं है, तो $H(Y\mid X)=H(Y)$ और $I(Y;X)=0$ वैकल्पिक रूप से, यदि संचार चैनल सही है और प्राप्त संकेत $Y$ प्रेषक के संकेत $X$ के समान है तो $H(Y\mid X)=0$ और $I(Y;X)=H(X)=H(Y)$

दर-विरूपण फलन की परिभाषा में $D_{Q}$ और $D^{*}$ क्रमशः दिए गए $Q_{Y\mid X}(y\mid x)$ और निर्धारित अधिकतम विरूपण के लिए $X$ और $Y$ के मध्य विरूपण हैं। जब हम माध्य वर्ग त्रुटि को विरूपण माप के रूप में उपयोग करते हैं, तो हमारे निकट (आयाम-निरंतर संकेतों के लिए) होता है:

$D_{Q}=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }P_{X,Y}(x,y)(x-y)^{2}\,dx\,dy=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)(x-y)^{2}\,dx\,dy.$

जैसा कि उपरोक्त समीकरण दिखाते हैं, दर-विरूपण फलन की गणना के लिए पीडीएफ $P_{X}(x)$ के संदर्भ में इनपुट $X$ के स्टोकेस्टिक विवरण की आवश्यकता होती है और फिर नियमबद्ध पीडीएफ $Q_{Y\mid X}(y\mid x)$ खोजना होता है जो किसी दिए गए विरूपण $D^{*}$ के लिए दर को न्यूनतम करता है। इस प्रकार इन परिभाषाओं को असतत और मिश्रित यादृच्छिक वैरिएबल को ध्यान में रखते हुए माप-सैद्धांतिक रूप से तैयार किया जा सकता है।

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

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

$R(D)\geq h(X)-h(D)\,$

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

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

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

$R(D)=\lim _{n\rightarrow \infty }R_{n}(D)$

जहाँ

$R_{n}(D)={\frac {1}{n}}\inf _{Q_{Y^{n}\mid X^{n}}\in {\mathcal {Q}}}I(Y^{n},X^{n})$

और

${\mathcal {Q}}=\{Q_{Y^{n}\mid X^{n}}(Y^{n}\mid X^{n},X_{0}):E[d(X^{n},Y^{n})]\leq D\}$

जहां सुपरस्क्रिप्ट उस समय तक के पूर्ण अनुक्रम को दर्शाता है और सबस्क्रिप्ट 0 प्रारंभिक स्थिति को संकेत करता है।

वर्ग-त्रुटि विरूपण के साथ स्मृतिहीन (स्वतंत्र) गाऊसी स्रोत

यदि हम मानते हैं कि $X$ विचरण के साथ सामान्य वितरण यादृच्छिक वैरिएबल $\sigma ^{2}$ है , और यदि हम मानते हैं कि संकेत $X$ के क्रमिक फॉर्मेट स्टोकेस्टिक रूप से स्वतंत्र हैं (या समकक्ष, स्रोत स्मृतिहीन है, या संकेत असंबद्ध है), हम दर-विरूपण फलन के लिए निम्नलिखित विश्लेषणात्मक अभिव्यक्ति पाते हैं:

$R(D)={\begin{cases}{\frac {1}{2}}\log _{2}(\sigma _{x}^{2}/D),&{\text{if }}0\leq D\leq \sigma _{x}^{2}\\0,&{\text{if }}D>\sigma _{x}^{2}.\end{cases}}$   

निम्नलिखित चित्र दिखाता है कि यह फलन कैसा दिखता है:

इस प्रकार दर-विरूपण सिद्धांत हमें बताता है कि 'कोई कम्प्रेशन प्रणाली उपस्थित नहीं है जो ग्रे क्षेत्र के बाहर फलन करती हो।' व्यावहारिक कम्प्रेशन प्रणाली लाल (निचली) सीमा के निकट होती है, उत्तम प्रदर्शन करती है। सामान्य नियम के रूप में, यह सीमा केवल कोडिंग ब्लॉक लंबाई मापदंड को बढ़ाकर ही प्राप्त की जा सकती है। फिर भी, यूनिट ब्लॉकलेंथ पर भी कोई अधिकांशतः अच्छा (स्केलर) क्वांटाइजेशन (सिग्नल प्रोसेसिंग) पा सकता है जो दर-विरूपण फलन से दूरी पर फलन करता है जो व्यावहारिक रूप से प्रासंगिक है।

इस प्रकार यह दर-विरूपण फलन केवल गाऊसी स्मृतिहीन स्रोतों के लिए प्रयुक्त होता है। यह ज्ञात है कि गॉसियन स्रोत एन्कोड करने के लिए सबसे कठिन स्रोत है: किसी दिए गए माध्य वर्ग त्रुटि के लिए, इसे सबसे बड़ी संख्या में बिट्स की आवश्यकता होती है। छवियों पर फलन करने वाली व्यावहारिक कम्प्रेशन प्रणाली का प्रदर्शन दिखाए गए $R\left(D\right)$ निचली सीमा से अधिक नीचे हो सकता है।

हैमिंग विरूपण के साथ स्मृतिहीन (स्वतंत्र) बर्नौली स्रोत

हैमिंग विरूपण के साथ बर्नौली यादृच्छिक वैरिएबल का दर-विरूपण फलन इस प्रकार दिया गया है:

$R(D)=\left\{{\begin{matrix}H_{b}(p)-H_{b}(D),&0\leq D\leq \min {(p,1-p)}\\0,&D>\min {(p,1-p)}\end{matrix}}\right.$

जहाँ $H_{b}$ बाइनरी एन्ट्रॉपी फलन को दर्शाता है।

$p=0.5$ के लिए दर-विरूपण फलन का प्लॉट :

दर-विरूपण सिद्धांत को चैनल क्षमता से जोड़ना

मान लीजिए कि हम किसी स्रोत के बारे में उपयोगकर्ता को D से अधिक विरूपण के साथ जानकारी प्रसारित करना चाहते हैं। दर-विरूपण सिद्धांत हमें बताता है कि स्रोत से जानकारी के कम से कम $R(D)$ बिट्स/प्रतीक उपयोगकर्ता तक पहुंचने चाहिए। हम शैनन के चैनल कोडिंग प्रमेय से यह भी जानते हैं कि यदि स्रोत एन्ट्रॉपी H बिट्स/प्रतीक है, और चैनल क्षमता C (जहां $C<H$) है, तो दिए गए चैनल पर इस जानकारी को प्रसारित करते समय $H-C$ बिट्स/प्रतीक विलुप्त हो जाता है। इस प्रकार उपयोगकर्ता को अधिकतम विरूपण D के साथ पुनर्निर्माण की कोई उम्मीद रखने के लिए, हमें यह आवश्यकता लगानी होगी कि रूपांतरण में विलुप्त जानकारी $H-R(D)$ बिट्स/प्रतीक की अधिकतम सहनीय हानि से अधिक न हो। इसका कारण यह है कि चैनल की क्षमता कम से कम $R(D)$ के अनुसार बड़ी होनी चाहिए

यह भी देखें

• ब्लाहुत-अरिमोटो एल्गोरिदम
• डेटा कम्प्रेशन
• डेकोरिलेशन
• दर-विरूपण अनुकूलन
• स्फीयर पैकिंग
• वाइट नॉइज़

बाहरी संबंध

• Marzen, Sarah; DeDeo, Simon. "PyRated: a python package for rate distortion theory". PyRated is a very simple Python package to do the most basic calculation in rate-distortion theory: the determination of the "codebook" and the transmission rate R, given a utility function (distortion matrix) and a Lagrange multiplier beta.
• VcDemo Image and Video Compression Learning Tool