مروری بر تولیدکدبوک به روش VQ

چکیده   

یکی از نقشهای اصلی Quantization Vector (VQ) این است که چگونه یک Codebook خوب تولید کنیم تا اعوجاج بین تصویر اصلی و تصویر بازسازی شده  به حداقل برسد .

در سال های گذشته،روش های تولید کدک VQ توسعه یافته اند.  در این مقاله تصویری از روشهای بهبود یافته ارائه شده است.

 طرح های مورد بحث شامل کدبندی مقدماتی مقیاس فاصله است

جستجو (MPS)، افزایش LBG (ELBG)، تکنیک های مبتنی بر شبکه عصبی، الگوریتم مبتنی بر ژنتیک 

روش های تجزیه و تحلیل مولفه های اصلی (PCA)، طرح جستجوی ممنوع tabu search (TS)، روشهای جابجایی کدگذاری و غیره

  

Vector Quantization (VQ)  از آنجاییکه  اجرای آن ساده  و آسان است یک روش کارامد برای  فشرده سازی داده ها محسوب می گردد. VQ  به طور گسترده در برنامه کاربردی برنامه های کاربردی مختلف مانند تشخیص الگو، فشرده سازی تصویر، تشخیص گفتار، تشخیص چهره و غیره  مورد استفاده قرار گرفته است

به منظور فشرده سازی تصویر، فرایندVQ   شامل تقسیم یک تصویر به چند بردار (یا بلوک) و همیچنین نگاشت هر بردار به یک کلمه کد (codewords) از یک  کتاب کد (codebook) جهت یافتن بردار مربوطه و بازتولید تصویر اصلی.بعبارتی دیگر  VQ نماینده ایست از بردارها.

R^K       : R  یک فضای اقلیدسیِ  k بعدی می باشد

X ⊆ R^K      :

       X مجموعه ایست از بردارها در فضای اقلیدسی

CB = {C1, C2, . . . , CN}  :

        CB همان کتاب کد است که شامل مجموعه ایست از نماینده های  کلمه کدهای تولید شده است که برای بازگردانی تصویر فشرده شده به تصویر اولیه (باید بهترین کتاب کد انتخاب شود)

: Cj = {c1, c2, . . . , ck}

       Cj   شامل  j  امین  کلمه کد.

تعداد کل کلمه کدهای موجود در CB برابر با N  و تعداد بعد (ابعاد) هر کلمه کد نیز با K مشخص شده است.

3 فاز یا روش عمده برای VQ وجود دارد:  تولید کتاب کد، روش کدگذاری و روش رمزگشایی

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

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

در شکل 1 عملیات رمز گذاری و رمزگشایی تصویر  با  VQ نمایش داده شده است. تصویر اصلی به 4  بلوک 2*2 تقسیم شده است.هر بلوک هم به یک بردار 4 بعدی تبدیل می شود.اولین وکتور-بردار در تصویر مورد نظر  X1 = (7, 10, 14, 6) که با 7امین کلمه کد در کدبوک نگاشته میشود. بعبارتی این اندیس یعنی 7 امین اندیس جایگزین وکتور نماینده از بلوک می شود. وقتی گیرنده  جدول شاخص را دریافت میکند  از 7امین کلمه کد یعنی c7 = (9, 6, 9, 9)  ،اولین بلوک را بازیابی می کند. تصویر بازیابی شده ، تصویر  بهبود یافته نامیده می شود.

یک vq خوب یک کد بوکی تولید میکند که بین تصویر اصلی و تصویر بدست آمده  کمترین اعوجاج وجود داشته باشد.

علاوه بر این، یکی دیگر از مسائل مهم در تولید کد بوک با VQ  کاهش زمان محاسبه  زمان است چون تولید کدبوک یک فرایند زمان گیر است. متداولترین الگوریتم مورد استفاده در VQ الگوریتمهای  GLA و LBG هستند.

. با این حال، LBG دارای مشکل بهینه محلی است و استفاده از هر کلمه کد در کتاب کد ،کم است. مسئله بهینه محلی  به این معناست که کتاب کد حداقل میزان تحریف – اعوجاج های محلی را تضمین می کند، اما حداقل اعوجاج عمومی  را نمی دهد. بنابراین پژوحشگران روشهای مختلفی را جهت سرعت بخشیدن به جستجوی راه حل بهینه ارائه داده اند. در این مقاله تصویری از طرح های  توسعه یافته اخیر ارائه شده است. طرح های مورد بحث شامل موارد زیر هستند:

جستجوی کد بوک  به روش میانگین فاصله( MPS ) ، الگوریتم enhance LBG (ELBG), ،  تکنیک های مبتنی بر شبکه عصبی

الگوریتم های مبتنی بر ژنتیک ، تحلیل مولفه های اصلی (PCA)، جستجوی  ، tabu  ، (TS)، روشهای جابجایی کدگذاری و غیره

الگوریتم LBG

این شیوه از تابع  نگاشت وکتورهای آموزشی به داخل N کلاستر استفاده کرد.تابع نگاشت به این صورت تعریف شده است:

R^k → CB.   .     X = (x1, x2, . . . , xk) بردارهای آموزشی هستند و d(X, Y ) فاصله اقلیدسی  مابین  دو بردارY X  ,

فرایند تولید کد بوک به روش GLA یا همان LBG:

1-     تولید کد بودک اولیه  به صورت تصادفی CB0

2-     I=0;

3-      انجام سلسله مراتب ذیل برای هر بردار آموزشی:

• a.       محاسبه فاصله اقلیدسی مابین بردار آموزشی و کلمه کدموجود در CBi .
• b.        فاصله اقلیدسی به این صورت تعریف می شود:

• c.       جستجوی نزدیکترین کلمه کد در CBi

2-     تقسیم کدبوک به N سلول

3-     محاسبه مرکز برای هر سلول برای بهینه کردن کد بوک جدید CBi+1.

4-     محاسبه میانگین فاصله  در CBi+1. .  این روند تکرار میشود تا کمترین مقدار بدست آید.کد بوک همگرا  و یا به مرحله سوم میرود. I=i+1

مثال

در این مثال،  5 وکتور آموزشی برای نشان دادن ایجاد یک کدبوک آموزشی داریم شکل 2

فرض می کنیم تعداد کل کلمه کدهای آموزشی 3 مورد است که با N نشان می دهیم.N=3

در ابتدا یک کدبوک اولیه ای  ( CB0) را به صورت تصادفی ایجاد می کنیم که در جدول شماره 1 نشان داده شده است.

در گام بعدی، فاصله مابین وکتور آموزشی و کلمه کدهای موجود در CB0 محاسبه می شود. مثلا X1  و C1  . X1  و C2  و X1  و C3

همانطور که مشخص است در i=0  ،کمترین فاصله X1   با c3 می باشد

 

وکتورهای اموزشی که دارای نزدکیترین کلمه کد یکسانی هستند در داخل یک سلول قرار می گیرند.

این طرح برای ر قسمت-سلول هسته ای را برای بهینه کردن  کدبوک جدید محاسبه میکند.

کلمه کد c3، نزدیکترین کدی است که برای دو بردار X1,x4  بدست آمدده است و داخل یک سلول  قرار گرفته اند.مرکزیت و هسته دو وکتور  (203, 150, 88, 98.5)  محاسبه میشود در واقع میانگین وکتورهای (x1,x4)هر کلمه کد باید محاسبه و ماتریس بدست امده جایگزین مقادیر متناظر در کد بوک قبلی می شود ،به اینصورت کد بوک قبلی بهینه می شود .(CB1)  و بهمین ترتیب X1+x3/2مقادیر جایگزین c3شود.

وکتورهای اموزشی که دارای نزدکیترین کلمه کد یکسانی هستند در داخل یک سلول قرار می گیرند.

این طرح برای ر قسمت-سلول هسته ای را برای بهینه کردن  کدبوک جدید محاسبه میکند.

کلمه کد c3، نزدیکترین کدی است که برای دو بردار X1,x4  بدست آمدده است و داخل یک سلول  قرار گرفته اند.مرکزیت و هسته دو وکتور  (203, 150, 88, 98.5)  محاسبه میشود در واقع میانگین وکتورهای (x1,x4)هر کلمه کد باید محاسبه و ماتریس بدست امده جایگزین مقادیر متناظر در کد بوک قبلی می شود ،به اینصورت کد بوک قبلی بهینه می شود .(CB1)

 و بهمین ترتیب X1+x3/2مقادیر جایگزین c3شود

LBG   یک الگوریتم آسان و سریع است. اما یک روش بهینه سازی محلی است. بنابراین، محققان روشهایی را برای حل این مشکل  پیشنهاد دادند : MPS ، تقسیم دودویی (DSBS) ، enhance LBG (ELBG)

تئوری تشدید انطباقی شبکه عصبی مرکزی - (CNN-ART)، الگوریتم جستجوی سریع با استفاده از طرح ریزی و عدم احتمال-نابرابری(FAUPI)، الگوریتم مبتنی بر GA ، روش جستجوی مبتنی بر جستجوی ممنوع یا (ETSA) ، PNM، الگوریتم ایجاد تولید  کدبوک با  استفاده از جابجایی کدگذاری (CGAUCD) و غیره.

Mean-distance-ordered Partial Codebook Search (MPS)

جستجوی قسمتی از  Codebook با  فاصله زمان محلی (MPS). Ra و kim یک الگوریتم جستجوی  جزئی در کدبوک با سرعت متوسط ​​را در سال 1993 پیشنهاد دادند. آنها از میانگین مربع  SMD  برای جداسازی کلمه کدهای نادرست و نامعتبر استفاده کردند.

استفاده از روش MPS  : smd  بصورت معادله 1 تعریف شده است . در این شیوه اگر  مقدار SMD بزرگتر از فاصله اقلیدسی باشد میگوییم  d(SMD) ،  فاصله اقلیدسی مابین X است و همچنین حداقل  در این مرحله  آزمایشی کلمه کدی است که  مطابقت دارد.و اگر کلمه کد در C بزرگتر از مقدار بدست آمده در معادله 2 باشد d(SMD) نزدیکترین همسایه X نیست.

در ابتدا مجموع ابعاد هر کلمه کد را بدست می آوریم و سپس مرتب سازی آنها بصورت افزایشی.. برای یک وکتور آزمایشی ، میانگین فاصله  dSMD   محاسبه می شود  و سپس پیدا کردن کلمه کد تطبیقی مورد نظر.در این نمونه،5امین کلمه کد ،همان کلمه کد مورد نظر تطبیقی است با کمترین فاصله با X .

در مرحله بعدی، فاصله اقلیدسی  مابین وکتور X و کوچکترین کلمه کد (C5) بدست آمده یعنی d(X, Cmin)  محاسبه میشود.

اگر فاصله اقلیدسی مابین وکتور X و مابقی کلمه کدها (c1, c2, c8)  از مقدار معادله  زیر بیشتر بود ،حذف میشوند.

 و سپس الگوریتم جستجوی کامل برای محاسبه فواصل c3,c4,c5,c7  و در نهایت آپدیت d(X,Cmin)

 Enhance LBG (ELBG)  : الگوریتم خوشه بندی با عنوان enhanced LBG

در این روش پاتان و روسو  از مفهوم کلمه کد برای رفع مشکل LBG  و بهبود آن استفاده نمودند.این الگوریتم از میزان اعوجاج و میانگین کلاسترها استفاده میکند. کلمه کدهای داخل کد بودک در داخل 2 خانه بنامهای HC و LC گنجانده می شوند. اگر مقدار Uj بیشتر از یک بود داخل Hc زقرار میگیرد. Uj از تقسیم مقدار اعواجاج و مقدار  میانگین تمام کلاسترها بدست می آید.در مرحله بعدی ، Cl  موجود در  CL  با کمترین اعوجاج   با نزدیکتر ین کلمه کد موجود در HC  بعنوان  Ch  جایگزین می شود. شیوه اجرایی این الگوریتم به اینصورت است که ابتدا الگوریتم LBG اجرا میشود و سپس محاسبه میزان اعوجاج  (Dj)  و Dmin و Uj .

Principal Component Analysis (PCA)

تجزیه و تحلیل مولفه اصلی (PCA) یک روش آماری است که تعدادی متغیر احتمالی را به تعدادی از متغیرهای غیر وابسته تبدیل می کند که به این ترتیب  ،مولفه های اصلی نامیده می شود. PCA  به طور گسترده و موفقیت آمیز در بسیاری از برنامه های کاربردی از قبیل تشخیص الگو، پیش بینی سری زمانی، پردازش تصویر، تجزیه و تحلیل داده های اکتشافی، فشرده سازی داده ها و غیره استفاده شده است.از آنجایی که PCA  یک روش خوب برای کاهش ابعاد و آنالیز چند متغیره است درنیز  VQ استفاده شده است. به عنوان مثال، هوانگ و هریس در سال 1993 پیشنهاد روش تقسیم دودویی (DSBS)را به کار گرفتند. در طرح خود، PCA برای انتخاب کدبوک اولیه برای کاهش ابعاد بردارهای آموزشی استفاده می شود.  پس از آن، هان و همکاران نیز از  PCA برای انتخاب بذر seed استفاده کردند.در سال 1997 چانگ، بهبود یافته الگوریتم جستجوی کد بوک را  با عنوان  دابل تست مولفه های اصلی (DTPC)با استفاده از PCA   پیشنهاد داد.  شکل 4 استفاده از الگوریتم را نشان می دهد. در ابتدا ماتریس کواریانسی از کلمه کدها ایجاد می شود.ماتریس کواریانس  در شکل 5 نشان داده شده است.  در مرحله بعد مقادیر ویژه و  بردارهای ویژه محاسبه می شود.

علامت لاندا معرف مقادیر ویژه هستند و EV معرف بردارهای ویژه.

مقادیر وبژه  و بردارهای ویژه متناظر با شکل 4 در شکل 6 نمایش داده شده است. اولین بردار ویژه (EV1)  بیشترین اطلاعات ذخیره  شده را نشان میدهد.

 

Genetic-based Approach

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

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

 در این طرح ارزش تناسب برای کروموزومها  محاسبه می شود و کروموزومها  بر حسب ارزش تناسبشان مرتب می شوند. بهترین N کروموزوم ها به عنوان نسل جدید در نسل بعدی انتخاب می شوند.

در سال2007  پان و چنگ برای ایجاد یک کدبوک مبتنی بر تکامل، از جستجوی   tabu   مبتنی بر تکامل  استفاده کردند که رویکرد جستجوی مبتنی بر تکامل (ETSA) نامیده می شود. طرح آنها مشابه الگوریتم مبتنی بر GA است. دراین روش ، در ابتدا  یک جمعیت والدین P باN کلمه کد  به صورت تصادفی تولید می شود. سپس، آنها از اپراتورهای تکثیر جنسی و دوگانه- غیرجنسی استفاده می کنند تا نسل بعدی فرزندان جنسی ( Ps ) و فرزندان غیرمعمول-غیرجنسی (  Pa  ) را تولید کنند.
 

Codeword Displacement

جابه جایی کلمه کد

لای و لیا با استفاده از پیش بینی -تجسم و نابرابری-اختلاف   الگوریتم جستجوی سریع (FAUPI ) را در سال 2004 پیشنهاد دادند. آنها از دو  نابرابری  جهت   کاهش محاسبات اعوجاج و کاهش کلمه کدهای نامناسب استفاده کردند. اولین معادله برای پایان دادن به فرایند جستجو و معادله دوم ،کلمه کدهای غیر ممکن را حذف میکند.پس از آن،  لیا ، الگوریتم ایجاد کدبوک  را بااستفاده ازجابه جایی کلمه کد  یعنی CGAUCD ارائه داد.  در این طرح ، کلمه کدها به در قالب دو خوشه دسته بندی می شوند : خوشه ایستا و خوشه فعال. کلمه کدهای موجود در خوشه ایستا به این معنی است که مقدار کلمه کد همانند کلمه کد در آخرین تکرار است. در غیر این صورت، کلمه کد  در خوشه فعال طبقه بندی شده است.

اگر یک بردار آموزش در یک خوشه استاتیک باشد، فقط باید فاصله بین بردار و کلمه کدهای موجود در خوشه فعال را برای یافتن نزدیکترین کلمه کد محاسبه کرد. علاوه بر این، آنها از الگوریتم های جستجو سریع مانند  MPS، FAUPI  و غیره برای کاهش  پیچدگی زمان استفاده کردند. در CGAUCD، کدبوک اولیه به طور تصادفی تولید می شود. به منظور سرعت بخشیدن به فرآیند خوشه بندی، از kd-tree برای تولید مرکز خوشه   کدبوک اولیه  استفاده شده است.علاوه بر این، آنها همچنین از kd-tree برای تعیین نزدیکترین همسایگان استفاده کردند.

MPS، DSBS، DTPC،FAUPI و CGAUCD برای کاهش پیچدگی LBG  طراحی شده اند. اکثرآنها  می توانند روند آموزش را تسریع بخشند.  با این حال  کیفیت تصاویر بازسازی شده از این طرح ها  ضعیفتر از LBG است.  علاوه بر این، برخی از آنها حتی دارای اثرات بلوکی هستند.



برگرفته از مقاله :

A Survey of VQ Codebook Generation