چندی سازی برداری با الگوریتم K-means

این الگوریتم نیز به­مانند الگوریتم LBG تصویری را به­عنوان ورودی دریافت نموده و به تعدادی بلاک تقسیم کرده و سپس هر بلاک به بردار تبدیل می­شود. در الگوریتم  K-meansباید از ابتدا تعداد خوشه ها مشخص شود. که تمام بردارها نیز باید در داخلK خوشه قرار بگیرند.برای هر K نیز باید مرکزی در نظر گرفت. در چندی سازی برداری، کدبوک­ها همان خوشه ها (K) هستند که ایجاد اولین کدبوک با انتخاب K بردار تصادفی از مجموعه بردارهای آموزشی که کدوکتور یا همان کلمه­ کد نامیده می شود انجام می­گیرد. کدبوک­ها همان خوشه هستند و کلمه­ کدها، همان مراکز خوشه.

 

محاسبه فاصله اقلیدسی مابین تمام بردارهای آموزشی و k بردار انتخابی که به تبع آن K خوشه ایجاد می­شود. هر بردار آموزشی به خوشه ای تعلق می­گیرد که با کدوکتور (مرکز خوشه) حداقل فاصله را داشته باشد. در صورتیکه فاصله بیش از یک بردار آموزشی با کدوکتوری همانند باشد یکی از آن وکتورها در خوشه قرار داده می­شود.

بعد از مشخص شدن اعضای هر کدبوک، باید مراکز یا کلمه کدهای جدید ایجاد شوند که برای اینکار، باید میانگین بردارهای موجود در هر خوشه محاسبه و جایگزین کلمه­کدهای قبلی شوند. این روند ادامه می­یابد تا مراکز خوشه ثابت بمانند. به این ترتیب کدبوک­ها ایجاد می­شوند و باید بهترین کدبوک جهت بازیابی تصویر انتخاب شود که می­توان از تابع fitness برای یافتن بهترین جواب استفاده کرد. این تابع برازش فقط جهت ارزش گذاری مورد استفاده قرار می­گیرد و با تابع برازش در الگوریتم ژنتیک متفاوت است.

 بعد از انتخاب کدبوک نهایی، باید ایندکس بهترین کلمه­ کد هر بردار آموزشی در جدول ایندکس ذخیره می­شود که برای بازیابی تصویر فشرده شده،ایندکس به کلمه کد اشاره کرده و کلمه کد جایگزین محتویات بردار آموزشی شده و به این ترتیب، تصویر بازیابی شده به صورت فشرده شده بازیابی می­شود. و در این الگوریتم نیز مانند الگوریتم های دیگر، جهت مقایسه میزان اعوجاج تصویر اصلی و تصویر بازیابی شده از معیارهای  MSE و PSNR استفاده می­کند. لازم به ذکر است که می­توان مقدار MSE را برای هر خوشه و همچنین MSE خالص را بدست آورد، حتی تکرار الگوریتم می­تواند تا زمانیکه  MSE خالص به همگرایی برسد تکرار شود.