الگوریتم (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 از روشهای کلاسیک هستند.چندی سازی متاهیورستیک شامل الگوریتم های تکاملی و هوش جمعی مانند ژنتیک، بهینه سازی ازدحام ذرات و کرم شب تاب و غیره می باشد. 

فشرده سازی تصویر

فشرده سازی تصویر عملیاتی است که ضمن حفظ اطلاعات تصویر از حجم آن کاسته و زمان و حافظه کمتری صرف ذخیره سازی و انتقال داده ها می گردد  همچنین عملیاتی  فشرده سازی تصویر قسمتی از فشرده سازی اطلاعات می باشد و کاربرد آن در تصاویر دیجیتال می باشد که هدف آن کاهش افزونگی می باشدو به دو صورت می باشد

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

2.     بدون اتلاف(lossless) : در عملیات فشرده سازی هیچ داده ای از بین نمی رود از برای بعضی تصاویر مانند نقشه های فنی و آیکونها استفاده می شود زیرا فشرده سازی با اتلاف مخصوصا زمانی که برای نرخ بیت های پایین استفاده می شود به کیفیت تصویر لطمه وارد می کند. همچنین ممکن است برای تصاویر با ارزش مثل تصاویر پزشکی یا تصاویر اسکن شده برای بایگانی ترجیح داده شوند روشهای بدون اتلاف عبارتند از run-length encoding که یکی از امکانات BMP، TGA، TIFF می باشد