پاورپوینت الگوریتم های فشرده سازی اتلاف دار

1

الگوریتم های فشرده سازی اتلاف دار

درس سیستم های چندرسانه ای

دانشگاه اصفهان – درس سیستم های چندرسانه ای
الگوریتم های فشرده سازی اتلاف دار
مقدمه روش های اندازه گیری اعوجاج کوانتیزاسیون تبدیلات

دانشگاه اصفهان – درس سیستم های چندرسانه ای
مقدمه
الگوریتمهای فشرده سازی بدون اتلاف، غالباً نرخ فشرده سازی مناسبی ندارند به همین دلیل در فشرده سازی صوت و تصویر از این روشها استفاده نمی شود

فشرده سازی با اتلاف چیست ؟
– بعد از دیکد کردن داده فشرده شده همان داده اصلی به دست نمی آید ولی تقریباً نزدیک به آن است .
– از نرخ فشرده سازی بسیار بیشتری نسبت به فشرده سازی بدون از دست رفتن اطلاعات برخوردار است .

دانشگاه اصفهان – درس سیستم های چندرسانه ای
نحوه محاسبه میزان خطا
از دو دیدگاه می توان میزان خطا را بررسی کرد:
دیدگاه اول: دیدگاه ادراکی: نظر افراد مختلف
دیدگاه دوم: دیدگاه ریاضی: با استفاده از تفاضل
تفاوت دو دیدگاه را می توان در یک تصویر که به اندازه یک سطر به بالا شیفت داده شده است، تصور کرد
اولین روش ریاضی: خطای میانگین مربعی ( MSE ) σ2 ،

در این فرمول xn ، yn و N، به ترتیب داده های ورودی، داده های بازسازی شده و تعداد داده ها می باشند .

دانشگاه اصفهان – درس سیستم های چندرسانه ای
نحوه محاسبه میزان خطا
روش دوم ریاضی: نسبت سیگنال به نویز ( SNR ) در مقیاس دسی بل

در این فرمول مقدار میانگین مربعی داده های اصلی و ، MSE است.
روش سوم ریاضی: حداکثر نسبت سیگنال به نویز ( PSNR ) :

5

دانشگاه اصفهان – درس سیستم های چندرسانه ای
نظریه نرخ انحراف
D: میزان انحراف
R(D): تعداد بیت مورد نیاز برای نمایش هرسمبل
H: آنتروپی

هر چه بخواهیم میزان تفاوت بعد از دیکد
اطلاعات فشرده شده،از منبع اولیه کمتر
باشد، باید بیت بیشتری استفاده کنیم

دانشگاه اصفهان – درس سیستم های چندرسانه ای
کوانتیزاسیون
تعداد مقادیر خروجی متفاوت (متمایز) را به مجموعه بسیار کوچکتری کاهش می دهد.
منبع اصلی Loss در فشرده سازی، از دست رفتن اطلاعات
سه شکل متفاوت کوانتیزاسیون:
یکنواخت
غیر یکنواخت
برداری

دانشگاه اصفهان – درس سیستم های چندرسانه ای
کوانتیزاسیون اسکالر یکنواخت
یک کوانتیزاسیون یکنواخت دامنه مقادیر ورودی را به فواصل مکانی یکسان تقسیم می کند.
خروجی یا مقدار بازسازی مربوط به هر بازه به عنوان نقطه میانی آن بازه در نظر گرفته می شود .
طول هر بازه اندازه قدم ( گام ) نامیده شده و با علامت Δ نشان داده می شود .

دانشگاه اصفهان – درس سیستم های چندرسانه ای
کوانتیزاسیون اسکالر یکنواخت
دو نوع کوانتیزاسیون اسکالر یکنواخت :
– کوانتایزر Mid-rise دارای سطوح خروجی به تعداد زوج می باشند .
– کوانتایزر Mid-tread دارای سطوح خروجی به تعداد فرد می باشند و صفر نیز یکی از آنهاست ( شامل صفر هم هستند )
9

دانشگاه اصفهان – درس سیستم های چندرسانه ای

a: کوانتایزر های اسکالر یکنواخت از نوع Midrise
b: کوانتایزر های اسکالر یکنواخت از نوع Midtread

کوانتیزاسیون اسکالر یکنواخت

دانشگاه اصفهان – درس سیستم های چندرسانه ای
برای مورد خاصی که 1 Δ = است می توانیم مقادیر خروجی را برای این کوانتایزرها سادگی محاسبه کنیم

کوانتیزاسیون اسکالر یکنواخت

دانشگاه اصفهان – درس سیستم های چندرسانه ای
12
محاسبه کارایی یک کوانتایزرM سطحی
مجموعه B = {b0, b1, . . . , bM} ، مجموعه مرزهای تصمیم گیری
Y = {y1, y2, . . . , yM} مجموعه مقادیر خروجی یا بازسازی باشد
فرض کنید که ورودی به صورت یکنواخت در بازه [−Xmax,Xmax] توزیع شده باشد
===تعداد بیتهای مورد نیاز:

محاسبه خطا در کوانتایزر یکنواخت

دانشگاه اصفهان – درس سیستم های چندرسانه ای
برای یک کوانتایزر از نوع Midrise و پارامترهای مشخص شده در اسلاید قبل

از آنجایی که مقادیر بازسازی yi، نقاط میانی هر بازه هستند، خطای کوانتیزه باید در بازه [− , ] قرار گیرد. در شکل نمودار خطای کاهش توزیع شده یکنواخت یک منبع نشان داده شده است .

محاسبه خطا در کوانتایزر یکنواخت

دانشگاه اصفهان – درس سیستم های چندرسانه ای
خطای کوانتایزر یکنواخت
محاسبه خطا در کوانتایزر یکنواخت

دانشگاه اصفهان – درس سیستم های چندرسانه ای

کوانتایزر غیر یکنواخت

دانشگاه اصفهان – درس سیستم های چندرسانه ای
کوانتایزر بُرداری
بر اساس مطالعات شانون در نظریه اطلاعات ، هر سیستم فشرده سازی اگر بر روی بردارها و یا گروه نمونه ها عمل کند ، از کار کردن بر روی علائم یا نمونه های انفرادی بهتر کار می کند .
نمونه های ورودی را به سادگی با الحاق تعدادی نمونه های متوالی، میتوان به یک بردار تبدیل کرد.
به جای استفاده از یک مقدار اسکالر، از یک بردار n تایی در کوانتایزر برداری استفاده می شود.

دانشگاه اصفهان – درس سیستم های چندرسانه ای

مراحل کوانتایزر بُرداری

دانشگاه اصفهان – درس سیستم های چندرسانه ای
کدینگ با استفاده از تبدیل
گاهی اوقات استفاده از یک تبدیل برای نمایش داده ها به صورت دیگر، به ما کمک می کند که داده ها را به صورت موثرتر کد کنیم

مثال: به جای استفاده از مدل RGB از مدل YUV برای تصویر استفاده کنیم، اگر U و V را کوانتیزه کنیم از کیفیت تصویر خیلی کم نمی شود ولی اگر مستقیما G,B یا R را کوانتیزه می کردیم کیفیت خیلی خراب می شد.

دانشگاه اصفهان – درس سیستم های چندرسانه ای
کدینگ با استفاده از تبدیل
اگر y نتیجه یک تغییر خطیِ ( T ) بردار X ورودی ، به گونه ای باشد که عناصر y بسیار کمتر وابسته باشند ، y می تواند بسیار موثرتر از X کد گذاری شود .
خود تبدیل T باعث فشرده سازی نمی شود ولی با پردازش و کوانتیزه کردن y می توان به فشرده سازی خوبی رسید
نیاز به تبدیلی داریم که همبستگی بین داده ها را حذف کند و فقط داده های مستقل و مورد نیاز را داشته باشیم
راه حل تبدیل کسینوسی (DCT)
دانشگاه صنعتی اصفهان-درس سیستم های چندرسانه ای
19

دانشگاه اصفهان – درس سیستم های چندرسانه ای
تبدیل کسینوسی گسسته یک بعدی (1D DCT) :

19-8

در جایی که i = 0, 1, . . . , 7, u = 0, 1, . . . , 7

تبدیل کسینوسی گسسته معکوس یک بعدی (1D IDCT) :

20-8

در جایی که i = 0, 1, . . . , 7, u = 0, 1, . . . , 7

تعریف DCT یک بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای
21
DCT یک تبدیل خطی است.
به طور کلی یک تبدیل ( یا تابع ) T ، خطی است اگر:

در این فرمول α و β ثابت و p و q هر تابع ، متغیر و یا ثابت می توانند باشند.
با استفاده از تعریف چنین برداشت می شود که این خصوصیت می تواند برای DCT به اثبات برسد زیرا تــنها از اعمال ساده ریاضی استفاده می کند .

تعریف DCT یک بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای

توابع پایه DCT یک بعدی

DCT یک بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای

ادامه توابع پایه DCT یک بعدی

DCT یک بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای

شکل 7-8 مثالهای تبدیل کسینوسی گسسته یک بعدی
الف: سیگنال DC و f1(i) ، ب: سیکنال AC و f2(i)

(a)
(b)
DCT یک بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای

ادامه شکل 7-8 مثالهای تبدیل کسینوسی گسسته یک بعدی
(c) f3(i) = f1(i)+f2(i) ، (d) یک سیگنال اختیاری

(c)
(d)
DCT یک بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای
توابع پایه کسینوسی
توابع Bp(i) و Bq(i) متعامد هستند اگر

22-8

توابع Bp(i) و Bq(i) متعامد هستند اگر آنها متعامد هستند و

می توان نشان داد که

دانشگاه اصفهان – درس سیستم های چندرسانه ای
تعریف DCT دو بعدی

با گرفتن تابع ورودی f(i, j) و دو متغیر i و j ( یک قطعه تصویر ) ، DCT دوبعدی آن را به یک تابع جدید F(u, v) با متغیرهای صحیح u و v در همان بازهi و j تبدیل می کند . تعریف عمومی و کلی تبدیل چنین است .

15-8

در این فرمول i , u = 0, 1, . . . ,M − 1 و j , v = 0, 1, . . . ,N – 1و ثابتهای C(u) و C(v) به وسیله فرمول زیر تعریف می شوند .

16-8

دانشگاه اصفهان – درس سیستم های چندرسانه ای
تبدیل کسینوسی گسسته دو بعدی (2D DCT) : (برای یک ماتریس 8*8)
17-8

در این فرمول i, j, u, v = 0, 1, . . . , 7 و ثابتهای C(u) و C(v) توسط معادله 8.5.16 تعیین می شوند .
 
تبدیل کسینوسی گسسته معکوس دو بعدی (2D IDCT) :
تــــــابع معکوس تقریباً یکسان است . ( با f(i, j) و F(u, v) ، معکوس شده ) به جز اینکه اکنون C(u) ، C(v) باید داخل حاصل جمع ها قرار گیرند .

18-8
در جایی که i, j, u, v = 0, 1, . . . , 7

تعریف DCT دو بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای

شکل 9-8 نمایش گرافیکی یک DCT دو بعدی 8×8

تعریف DCT دو بعدی

دانشگاه اصفهان – درس سیستم های چندرسانه ای
کاهش محاسبات در تبدیل DCT
DCT دو بعدی می تواند به یک توالی دو مرحله ای DCT یک بعدی تفکیک شود .

واضح است که این تغییر ساده چقدر باعث تسهیل عملیات ریاضی می شود .
تعداد تکرارهای مورد نیاز از 8×8 به 8+8 کاهش می یابد .