تحلیل VQ با k-means

تحلیل  VQ  با k-means    

1. دریافت تصویر به عنوان  داده  ورودی
2. تبدیل به تصویر سیاه سفید
3. بدست آوردن اندازه تصویر
4. مشخص کردن اندازه  بلاک یا همان بردارهای آموزشی (bs : block size)، جهت تبدیل ماتریس (تصویر) به بلاکهای مشخص  

برای تنظیم استفاده می کنیم.این تابع ،عناصر ماتریس ک همان مقدار پیکسلهای تصویر هستند را در قالب ستون ،مرتب میکند.

5-ایجاد کد بوک :  cb = codebook(pool,cbs)

کتاب کد ، یک ماتریسی است با ابعاد  pool , cbs

Cbs   (code book size): تعداد کد بوک های  مورد نظر

در الگوریتم k-means   در ابتدا یک کدبوک تصادفی ایجاد می شود.

6- انتخاب بهترین راه حل

 در این مرحله بعد از ایجاد کدبو کها باید بهترین  کدبوک  انتخاب شود.   BestSol=Fitness(pool,cb)

ایجاد کدبوک:

گفته شد که در این الگوریتم یکی از الگوریتمهای خوشه بندیست و روش آن به گونه ایست که در ابتدای کار ،تعداد خوشه ها و مراکز آن مشخص شوند. بهمین منظور از دستور randperm استفاده میکنیم تا به تعداد cbs،  و  در بازه n ،اندیس عناصری در خروجی نمایش داده شود و سپس مقدار آن اندیس از ماتریس pool مشخص و در متغیر cb  که همان کد بوک است درج شود و سپس محاسبه میزان انحراف –اعوجاج مابین ماتریس اصلی و کدبوک بدست آمده (cb)باید فاصله اقلیدسی هریک از عناصر ماتریس pool با محتویات cb محاسبه شود. در واقع عناصر cb همان مراکز اولیه خوشه هستند که بصورت تصادفی انتخاب شده اند.

[m,n]=size(pool)

order=randperm(n,cbs);

cb=pool(:,order);

r1=distortion(pool,cb);

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

همانطور که قبلا گفته شده است باید فاصله هر کدارم از وکتورها ی آموزشی با هریک از سطرهای cb  محاسبه شود. و سپس کمترین فاصله هر بردار با cb را بدس آورد.

به این ترتیب مشخص می کنیم که هر بردار به کدام مرکز تعلق میگیرد.

بعد از مشخص شدن اعضای هر مرکز یا همان خوشه ها، باید مراکز ،آپدیت شوند، که میانگین اعضا محاسبه میگردد و بردار جدید به عنوان مرکز جدید معرفی میگردد ،این روال تکرار میشود تا مراکز و اعضا تغییری پیدا نکنند.  که به دنبال آن،کد بوک نهایی ایجاد میشود.

تابع fitness

VQ Encoding

برای رمزگذاری وکتورهای آموزشی ، باید یک جدول شاخص یاایندکس ایجاد شود بعبارتی دیگر در این مرحله باید برای هر بردار(سگمنتهای تصویر)یک نماینده انتخاب شود.

جهت اینکار، فاصله مابین هر پیکسل از بردارهای آموزشی با جدول cb  بدست می آید. سپس مقدار متناظر با ایندکس کمترین مقدار بدست آمده در جدول ایندکس درج می گردد.ابعاد جدول ایندکس ،به اندازه ابعاد ماتریس pool است.

VQ Decoding

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

محاسبه MSE و PSNR برای ارزیابی کیفیت

MSE : میانگین توان دوم خطا - میانگین مربع خطا

PSNR :

میزان درصد نویز بر سیگنال

PSNR می توان متداولترین روش برای اندازه گیری کیفیت تصویر است. که در آن MAXبیشترین مقدار پیکسل موجود در تصویر است. هر چه میزان PSNRبیشتر باشد نشان دهنده این است که بازسازی تصویر بهتر صورت گرفته است

در معادله های زیر،  i ,jسطر و ستون تصویر را نشان می دهد   Iو K   به ترتیب رزولوشن بالای تصویر  اصلی و تصویر بازسازی شده است.ساده ترین معیار ارزیابی که به طور گسترده نیز مورد استفاده قرار میگیرد، میانگین مربع خطا( MSE  )است. این معیار به این دلیل که از نظر محاسباتی ساده بوده، دارای معنای فیزیکی واضح هستند و از نظر ریاضی در زمینه بهینه سازی مناسبند، دارای جذابیت هستند. اما این معیارها با کیفیت درک شده توسط چشم انسان هماهنگ نیستند.

منابع :

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

 مسأله خوشه بندی k-Means با استفاده از الگوریتم PSO در متلب

 داده کاوی-خوشه بندی (الگوریتم k-means و k-medoid)