نظریه نرخ-اعوجاج

نظریه نرخ-اِعوِجاج (به انگلیسی: Rate-distortion theory)، یک شاخه اصلی از نظریه اطلاعات است که اصول نظری فشرده‌سازیِ خطادارِ داده‌ها را بیان می‌کند. این نظریه به مسئله کمترین تعداد بیت لازم برای هر سمبل منبع که باید از کانال مخابراتی منتقل شود تا بتوان داده‌ها را طوری در مقصد بازیافت که اعوجاج از حد معینی بیشتر نشود، می‌پردازد.

نظریه نرخ-اعوجاج یک فرمول‌بندی ریاضی است که بیان می‌کند چه مقدار فشرده‌سازیِ خطادار امکان‌پذیر است. بسیاری از روش‌های فشرده‌سازی صدا، گفتار، تصویر ثابت یا متحرک، دارای تبدیلات، کوانتیزاسیون و روندهایی برای تعیین نرخ بیت هستند که در قالب کلی توابع نرخ-اعوجاج قرار می گیرند.

نظریه نرخ-اعوجاج را کلود شانون در کار اساسی‌اش در نظریه اطلاعات، پایه ریخت.

در نظریه نرخ-اعوجاج، معمولاً نرخ به عنوان تعداد بیت لازم برای هر سمبل، هنگام انتقال یا فشرده‌سازی داده‌ها شناخته می‌شود. در موارد ساده، اعوجاج به صورت متوسطِ (امیدِ ریاضی) مربع اختلاف سیگنال ورودی و خروجی تعریف می‌شود. اما، از آنجاکه تکنیک‌های فشرده‌سازی خطادار روی داده‌های قابل درک برای انسان اعمال می‌شوند (مانند صدا، تصاویر ثابت یا متحرک)، اعوجاج باید به گونه‌ای مدل شود که متناسب با درک انسان باشد. مشابه استفاده از احتمالات در فشرده‌سازی خطادار، معیارهای اعوجاج با توابع هزینه (همان‌گونه که در تخمین بِیزی و تئوری تصمیم استفاده می‌شود) بیان می‌شوند.

در فشرده‌سازی صدا، مانند تکنیک MP3 یا Vorbis، مدل‌های ادراکی (و در نتیجه اعوجاج ادراکی) استفاده می‌شوند، گرچه اغلب نمی‌توان آنها را به سادگی در غالب تئوری نرخ- اعوجاج بیان کرد. در فشرده‌سازی تصویر ثابت یا متحرک، مدل‌های مبتنی بر ادراک انسان کمتر توسعه یافته‌اند و به صورت محدود در ماتریس وزن‌های JPEG و MPEG استفاده می‌شود.

توابعی که نرخ و اعوجاج را پیوند می‌دهند، پاسخ‌های مسئلهٔ کمینه‌سازی زیر هستند:

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

که در آن، (Q_{Y | X}(y | x، تابع چگالی احتمال شرطی خروجی کانال مخابراتی (Y) برای یک ورودی مفروض (X) است و گاهی تست کانال نامیده می‌شود. (I_Q(Y ; X اطلاعات متقابل بین Y و X است و چنین تعریف می‌شود:

${\displaystyle I(Y;X)=H(Y)-H(Y|X)\,}$

که (H(Y و (H(Y | X آنتروپی سیگنال خروجی (y) و آنتروپی شرطی سیگنال خروجی به شرط سیگنال ورودی است:

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

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

همچنین مسئله را می‌توان به صورت یک تابع نرخ-اعوجاج بیان کرد که باید روی اعوجاج‌های ممکن به ازای یک نرخ معین، کمینه شود:

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

این دو فرمول‌بندی به توابعی می‌انجامند که معکوس هم هستند.

اطلاعات متقابل، معیاری برای تفاوت عدم قطعیت از Y و عدم قطعیت از Y به شرط دانستن X است. این کاهش عدم قطعیت به‌سبب اطلاعاتی است که میان فرستنده و گیرنده مخابره می‌شود، (I(Y; X.

برای نمونه، اگر هیچ داده‌ای منتقل نشود، آنگاه (H(Y |X) = H(Y و I(Y; X) = ۰. از سوی دیگر، اگر کانال مخابراتی بی‌خطا باشد و سیگنال دریافتی Y، همان سیگنال ارسالی X باشد، آنگاه H(Y | X) = ۰ و (I(Y; X) = H(Y.

در تعریف نرخ-اعوجاج، اعوجاج بین X و Y، به ازای یک (Q_{Y | X}(y | x و یک حداکثر اعوجاج مجاز تعریف می‌شود. اگر از میانگین مربع خطا به عنوان معیار اعوجاج استفاده کنیم (برای سیگنال‌های با دامنه پیوسته)، آنگاه

${\displaystyle 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|X}(y|x)P_{X}(x)(x-y)^{2}\,dx\,dy.}$

همان‌طور که معادله بالا نشان می‌دهد، محاسبهٔ یک تابع نرخ-اعوجاج نیاز به تابع چگالی احتمال ورودی X دارد و به دنبال آن، یک تابع چگالی احتمال شرطی (Q_{Y | X}(y | x که نرخ را برای یک اعوجاج D^* کمینه کند، به دست می‌آید. البته این مسئله، جز در موارد ساده، یک پاسخ تحلیلی بسته (به انگلیسی: closed form) ندارد.

تابع نرخ-اعوجاج هر منبع، چند ویژگی اساسی دارد. مهم‌ترینشان این است که یک تابع پیوستهٔ اکیداً نزولی مقعر است.

اگرچه جواب تحلیلی برای این مسئله، نادر است، حد بالا و پایین، مانند حد پایین شانون برای این توابع وجود دارد، که به ازای خطای مربعی و منبع بی‌حافظه دلخواه با آنتروپی دیفرانسیلی محدود چنین است

${\displaystyle R(D)\geq h(X)-h(D)\,}$

که (h(D آنتروپی دیفرانسیلی متغیر تصادفی گاوسی با واریانس D است. این حد پایین، قابل تعمیم به منابع حافظه‌دار و سایر معیارهای اعوجاج است. یک ویژگی مهم حد پایین شانون این است که برای اعوجاج‌های اندک، حد خوبی برای طیف وسیعی از منابع به دست می‌دهد.

الگوریتم Blahut–Arimoto یک روش مبتنی بر تکرار برای حل عددی تابع نرخ-اعوجاج برای الفبای محدود ورودی-خروجی منبع است و کارهای زیادی برای گسترش این راه حل به مسائل عمومی‌تر انجام شده‌است.

در منابع حافظه‌دار، تعریف تابع نرخ-اعوجاج نیازمند بازنگری است و به صورت یک حد روی دنباله‌هایی که طول افزایشی دارد بیان می‌شود.

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

که

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

و

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

که بالانویس‌ها یک دنباله کامل تا آن زمان و زیرنویس 0، حالت اولیه را نشان می‌دهند.

اگر (P_X(x یک توزیع گاوسی با واریانس σ^2، و نمونه‌های آتی سیگنال X مستقل باشند (منبع بی‌حافظه است یا سیگنال‌ها ناهمبسته‌اند)، فرم بستهٔ زیر برای تابع نرخ-اعوجاج به دست می‌آید

${\displaystyle R(D)=\left\{{\begin{matrix}{\frac {1}{2}}\log _{2}(\sigma _{x}^{2}/D),&{\mbox{if }}0\leq D\leq \sigma _{x}^{2}\\\\0,&{\mbox{if }}D>\sigma _{x}^{2}.\end{matrix}}\right.}$

شکل زیر این تابع را نشان می‌دهد.

بر پایه نظریه نرخ-اعوجاج، هیچ روش فشرده‌سازی نمی‌تواند بیرون از ناحیهٔ خاکستری عمل کند. خط قرمز، یک باند برای فشرده‌سازهای عملی است. به عنوان یک قانون کلی این حد تنها با افزایش طول بلوک‌های کد امکان‌پذیر است. با این حال، حتی در طول بلوک واحد، ممکن است بتوان یک کوانتیزاسیون خوب به گونه‌ای که با فاصله خوبی از تابع نرخ-اعوجاج کار کند، یافت.

این تابع نرخ-اعوجاج تنها برای منابع گاوسی بی‌حافظه برقرار است. منبع گاوسی سخت‌ترین منبع برای کدگشایی کردن است. برای یک خطای میانگین مربعات معین، این منبع به بیشترین تعداد بیت نیاز دارد. عملکرد یک فشرده‌ساز عملی تصویر، ممکن است به خوبی زیر باند پایین (R(D نشان‌داده‌شده باشد.

اگر بخواهیم اطلاعات منبعی را منتقل کنیم طوری‌که اعوجاج از حد D تجاوز نکند، بر پایه نظریه نرخ-اعوجاج، باید کمترین نرخ بیت (R(D برای هر سمبل اطلاعات از منبع به مقصد برسد. همچنین بر پایه نظریهٔ کدگذاری کانال شانون، اگر آنتروپی منبع، H بیت برای هر سمبل و ظرفیت کانال (C (C<H باشد، آنگاه H-C بیت برای هر سمبل هنگام ارسال اطلاعات روی کانال از دست می‌رود. برای اینکه گیرنده بتواند اطلاعات را با حداکثر اعوجاج D باز یابد، از دست دادن اطلاعات هنگام انتقال نباید از بیشینه خطای قابل تحمل (H − R(D بیت برای هر سمبل بیشتر باشد؛ یعنی ظرفیت کانال باید دست کم از (R(D بیشتر باشد.

• Decorrelation
• بهینه‌سازی نرخ-اعوجاج
• کدگذاری منبع
• بسته‌بندی - کروی
• سفید کردن (نویز)
• Blahut-Arimoto الگوریتم

• PyRated: کد پایتون برای محاسبات ابتدایی در نظریه نرخ-اعوجاج است.
• VcDemo تصویر و ویدئو فشرده سازی ابزار یادگیری

<link rel="mw:PageProp/Category" href=". /رده:نظریه_اطلاعات"/>