الگوریتم (LBG Linda-Buzo-Gray)

الگوریتم LBG در واقع یک الگوریتم رقمی سازی برداری(vector quantization) می باشد که  به کمک آن می توان یک codebook مناسب تهیه کرد. Codebook به دست آمده در حقیقت مجموعه مراکز بازه های رقمی سازی می باشد. این روش شبیه روش k-means در خوشه بندی (data clustering) می باشد.

الگوریتم LBG در حقیقت یک الگوریتم پیمایشی می باشد  و به منظور رفع مشکل خوشه بندی پیشنهاد گردید که به آن الگوریتم لوید تعمیم یافته نیز گفته می شود. این الگوریتم توسط لیند و همکارانش در سال 1982 مطرح گردید که قادر است به طور قابل قبولی بر مشکل k-mean غلبه کند. مراحل این الگوریتم به صورت زیر می باشد.

1.     تعداد خوشه ها مشخص می گردد و در ابتدا M= 1 قرار می دهیم

2.     برای تمام داده ها بردار مرکز محاسبه می گردد.

3.     تا زمانی که تعداد خوشه ها برابر تعداد تعین شده نشده باشد هر یک از M بردار مرکز به 2 بردار جدید شکسته می شود تا 2M بردار مرکز تولید گردد. هر بردار جدید بایستی درون همان خوشه قرار داشته باشد و به اندازه کافی از هم دور باشند.

4.     شرط خاتمه : زمانی که M برابر تعداد خوشه مورد نظر الگوریتم LBG باشد الگوریتم خاتمه می یابد  و در غیر این صورت به مرحله 2 می رود و الگوریتم را تکرار می کند.  

چندی سازی بردراری(Vector Quantization)

VQ یکی از پرکاربردترین روشها برای فشرده سازی تصاویر می باشد. مکانیزم VQ، کاربردهای زیادی دارد که یکی از آنها فشرده سازی داده ها (متن،صوت،عدد) می باشد. درواقع VQ به سه فاز کد، رمزگذاری بردار و رمزگشایی بردار تقسیم می گردد. در فشرده سازی تصویر، رمزگذار(encoder)، یک آدرس از کلمه کدها ایجاد کرده که به بردار تصویر ورودی نزدیک می باشد. و رمزگشا(decoder) برای بازیابی تصویر از این بردار تصویر استفاده می کند. کتاب کد ، یک عامل کلیدی تاثیرگذار به روی کارایی فرآیند فشرده سازی تصویر می باشد. تولید کتاب کد یکی از فرآیندهای مهم به منظور تشخیص کارایی چندی سازی برداری می باشد. هدف از این کار یافتن بردار کدهایی برای بردارهای آموزشی داده شده می باشد. این کار توسط مینیمم کردن فاصله بین بردارهای آموزشی و بردارکدهای مرتبط به هر کدام انجام می گیرد. در عملیات کدگذاری ابتدا تصویر به بردارهای ورودی (بلاک ها) تقسیم می گردد سپس با کلمه های کد کتاب مقایسه مقایسه می گردد تا نزدیک ترین کلمه کد برای هربردار ورودی پیدا گردد. در واقع اندیس نزدیکترین کلمه کد به بردار تعیین می گردد.البته باید این نکته را در نظر داشت که اندازه کلمه کد از تصویر اصلی خیلی کوچک تر می باشد، که هدف فشرده سازی تصویر می باشد. در فرآیند کدگشایی نیز تصویر توسط کتاب کد مربوطه اش بازیابی می شود.کدگشایی زمانی تکمیل می گردد که تصویر به طور کامل بازیابی گردد. روشهای چندی سازی بردار یبه دو دسته کلاسیک و ممتاهیورستیک تقسیم بندی می گردد. چندی سازی با ساختار درختی، چندی سازی برداری حاصل ضربی و lbg از روشهای کلاسیک هستند.چندی سازی متاهیورستیک شامل الگوریتم های تکاملی و هوش جمعی مانند ژنتیک، بهینه سازی ازدحام ذرات و کرم شب تاب و غیره می باشد.