چندی سازی برداری با الگوریتم LBG

الگوریتم LBG یا GLA یکی از الگوریتم­های معروف خوشه بندی کردن داده­ها  است. در بحث چندی سازی بردارینیز می­توان از این الگوریتم استفاده نمود. چندی سازی برداری شامل 3 مرحله مهم تولید کدبوک، رمزگذاری و رمزگشایی است که می­توان برای مرحله اول از الگوریتم LBG استفاده کرد.

    

 به عبارتی دیگر کدبوک بهینه همان راه حل بهینه ای است، شامل نماینده بردارهای تصاویر، که به دنبال آن تصویر فشرده شده و بازیابی شده نیز دارای کیفیت بهتری است. این الگوریتم تصویری را به ­عنوان ورودی دریافت می­کند. تصویر دریافت شده به تعدادی بلوک تقسیم می­شود و سپس بلوک­های ایجاد شده به بردار تبدیل می­شوند. به بردارهای ایجاد شده کدبردار[1] یا کلمه کد[2]گفته می­شود. تصویر دریافت شده معمولا در اندازه های 512x512 ، 256x256 است و تعداد بلوک­ها عموما" مضربی از 2 هستند مانند 2x2،4x4 ، 8x8 است. در این پیاده­ سازی می­توان اندازه بلاک­ها و تعداد کدبوک را مشخص نمود. کدبوک­ها همان مراکز خوشه­ ها محسوب می­شوند و باید بردارهای آموزشی در نزدیک ترین خوشه قرار بگیرند. لذا باید فاصله اقلیدسی این بردارها با کدبوک ها که همان مراکز هستند محاسبه شود و به این ترتیب هر بردار در نزدیکترین کدبوک قرار می­گیرد.برای یافتن بهترین کدبوک می­توان با استفاده از تابع برازش، میزان برازش هر کدبوک را محاسبه کرده و به صورت صعودی آنها را مرتب نمود.کدبوکی، جواب مسأله است که بالاترین مقدار را داشته باشد. این کدبوک همان کدبوکی است که برای بازیابی تصویر فشرده شده مورد استفاده قرار می­گیرد. بنابراین اندیس بهترین کلمه ­کد تطبیق داده شده به جای بردار متناظر  در تصویر ، در جدول ایندکس ذخیره می­شود و در مرحله پایانی کدبوک به رمزگشا  جهت بازسازی تصویر ارسال می­گردد. برای ارزیابی تصویر اصلی و تصویر رمز شده  بطور معمول از معیارهای MSE و PSNR کمک گرفته می­شود.

مراحل انجام  چندی سازی برداری با الگوریتم LBG :

1-     دریافت تصویر

2-     تقسیم کردن تصویر و تبدیل هر بلاک از تصویر به یک بردار (بردارهای آموزشی )

3-     مشخص کردن پارامترهای اولیه : اندازه هر بلاک از تصویر ورودی و تعداد کد بوک مورد نیاز(شرط توقف)

4-     ایجاد کدبوک بر حسب بردارهای آزمایشی :

·         در نظر گرفتن بردارهای آموزشی در قالب یک کدبوک اولیه (CBi , i=0) و انتخاب یک بردارمیانگین (D)، بعنوان مرکز برای مجموعه بردارهای آموزشی.

·         محاسبه فاصله اقلیدسی مابین مجموعه بردارهای آموزشی و مرکز (D)

·     با در نظر گرفتن ضریب خطای ثابت(E=0.01)، کدوکتوری که به ­عنوان مرکز در نظر گرفته شده، به دو بردار تقسیم می­گردد (D' و D).

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

·         مراحل تقسیم مرکز خوشه تکرار می­گردد تا زمانیکه شرط  توقف حاصل شود. بطور مثال شرط زیر میتواند به عنوان شرط توقف در نظرگرفته شود.  

((D'-D)/D)<E

5-     محاسبه برازش کدبوک­ها

6-     مرتب سازی کدبوک­های ایجاد شده بر اساس بیشترین مقدار برازش و ذخیره آن.

7-     مرحله رمزگذاری و رمزگشایی: رمزگذار بردار ورودی X را دریافت می کند و بردارهایی با آدرس Xi   تولید می­کند و تابع رمزگشا همان کتاب کد رمزگذار را دارد که با شاخص، دوباره بردارهای کد را تولید می کند و تصویر بازیابی شده ایجاد می­گردد.

ساختار الگوریتم LBG

چندی  سازی برداری با الگوریتم LBG

---

[1] CodeVector

[2] CodeWord