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

فرایند فشرده سازی تصویر توسط VQ شامل دو تابع اصلی رمزگذار و رمزگشا می باشد. تابع رمزگذار با دریافت بردار ورودی x بردارهایی با آدرس x_i را تولید می کند و تابع رمزگشا با استفاده از همان کتاب کد رمزگذار مجددا بردارهای کد را تولید می کند. برای تصاویر رنگی VQ به 3 کتاب کد به منظور طراحی سه فضا نیاز دارد. طراحی کتاب کد یکی از مهمترین موضوعات به منظور رسیدن به یک راه حل بهینه می باشد. در فشرده سازی تصاویر رنگی با استفاده از  تکنیک VQ ابتدا باید تصویر به بلوک هایی تحت عنوان نمونه های آموزشی تقسیم گردد. به این نمونه های آموزشی، بردارهای آموزشی گفته می شود. 

  سپس عملیاتهای ترکیب و جهش جهت به دست آورده کتاب کد بهینه روی این بردارها انجام می شود. روند کار را می توان به صورت زیر بیان کرد: 

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

2. فرایند رمزگذاری(هر یک از بلوک ها به بردار تبدیل می گردند)

3. تعریف تابع ارزش گذاری

4. تولید جمعیت اولیه(جمعیت اولیه ای از کروموزوم ها تولید می شوند) توسط یک متد انتخاب تصادفی از نمونه های آموزشی

5. ارزیابی

6. متد انتخاب، توسط این متد بهترین جفت از والدین انتخاب می شوند.

7. متد ترکیب، با استفاده از این متد یک نسل جدید تولید می گردد. بعد از آن تابع ارزیابی انجام مشود تا بهترین جفت فرزندان باقی بمانند.

8. جهش، جهش همه فرزندان به منظور تنوع ژنتیکی

9. شرط خاتمه، زمانی الگوریتم خاتمه می یابد که ارزش مورد نظر به دست آید یا در دوبار تولید نسل یک مقدار برای تابع ارزش گذاری به دست آید.

به منظور ارزیابی کیفیت تصاویر فشرده شده در اکثر مقالات از فورمول زیر استفاده می کنند:

که در آن (i ,j) به ترتیب نشان دهنده مختصات پیکسلهای تصویر اصلی و فشرده شده می باشند. W و H نیز به ترتیب عرض و ارتفاع عکس را مشخص می کنند.

الگوریتم ژنتیک در موارد زیادی به منظور افزایش کارایی با الگوریتم های دیگری ترکیب می شوند. در الگوریتم ژنتیک بعد از شناسایی جمعیت اولیه، دو رشته به عنوان والدین انتخاب می شوند و به منظور انجام عمل ترکیب از الگوریتم نزدیکترین همسایه زوجی استفاده می گردد زیرا این یکی از مراحل مهم در الگوریتم ژنتیک بوده و سعی می شود از الگوریتمهایی استفاده گردد که جواب قطعی تری را بدهند. بعد از عمل ترکیب به منظور حفظ تنوع ژنتیکی عملیات جهش انجام می گیرد. در  نتیجه جمعیت جدید توکید می گردد و به منظور بهینه سازی محلی از الگوریتم GLA استفاده می کردد.  الگوریتم SGCA نیز یک الگوریتم بهبود یافته ژنتیک می باشد که در چندی سازی استفاده می گردد. که در زیر فلوچارت آن رسم گردیده است .

منابع

CODEBOOK DESIGN FOR VECTOR QUANTIZATION USING GENETIC ALGORITHM 

Wei-Hua Andrew Wang, Shih-Chun Yang and Chun-Liang Tung* Department of Industrial Engineering and Enterprise Information  Tunghai University