الگوریتم LBG یا Linde–Buzo–Gray یک الگوریتم رقمی سازی برداری (vector quantization) است که با استفاده از آن می توان یک codebook مناسب بدست آورد. codebook در حقیقت مجموعه مراکز بازه های رقمی سازی است. این روش مشابه روش k-means در خوشه بندی (data clustering) است.
بطور کلی الگوریتم LBG، یک الگوریتم نوع پیمایشی است. در ادامه به جزئیات این الگوریتم می پردازیم:
1- ابتدا به دلخواه یک عدد کوچک مثبت ε > 0 انتخاب می کنیم.
2- N را برابر 1 قرار دهید و مقدار زیر را محاسبه کنید.
3- مرحله افراز:
ابتدا مقدار زیر را محاسبه کنید.
سپس برای i از 1 تا N مقادیر زیر را محاسبه کنید و بعد از پایان این حلقه N را دو برابر کنید.
4- مرحله پیمایش:
i را برابر صفر قرار دهید و همچنین
I) برای m از 1 تا M مینیمم مقدار زیر را بیابید که در آن n از 1 تا N می باشد.
اگر n* اندیس مینیمم باشد، قرار دهید:
II) برای n از 1 تا N، Cn ها (codevectors) را به روزرسانی کنید.
III) مقدار i را یک واحد افزایش دهید.
IV) مقدار زیر را محاسبه کنید.
V) اگر شرط زیر برقرار است، به مرحله I بازگردید.
VI) اکنون Cn ها و D مقادیر بهینه نهایی می باشند.
5- مراحل 3و 4 را آنقدر تکرار کنید تا به تعداد بازه های موردنظر برسید.
در مقالات زير هم توضيحاتي داده شده که اميدوارم مفيد باشه!
An Algorithm for Vector Quantizer Design
A fast Linde-Buzo-Gray algorithm in image vector quantization