(Vector Quantization (VQ چیست؟

هنگام ذخیره کردن تصویر به روی کامپیوتر،گاهی تعداد پیکسل ها کاهش می یابد،یا پیکسل های مشابه با هم ادغام و یا به روی سیستم ثبت نمی شوند،به این عمل فشرده سازی تصویر گفته می شود. روش های متفاوتی برای فشرده سازی تصاویر وجود دارد،یکی از پر کاربردترین روش ها 

(Vector Quantization (VQ  یا همان کمی سازی برداری می باشد. 

(VQ) نخستین بار در سال 1984 توسط گری (Gary) ارائه شد. کمی سازی برداری یکی از روش های پر اتلاف می باشد. در فشرده سازی پر اتلاف هرگاه بخواهیم تصویر فشرده شده را از حالت فشرده خارج کنیم، هرگز به کیفیت تصویر اصلی نخواهیم رسید،هر چند ممکن است این اختلاف از فاصله دور مشخص نباشد.

در VQ کوانتیزرها (عبارت کوانتیزه کردن به معنای تقسیم کردن به بخش های قابل شمارش است)، میزان اتلاف را تعیین می کنند.اگر بلوک هایی از ورودی با هم کوانتیزه شوند،به آنVQ یا کمی سازی برداری می گویند.در کمی سازی برداری تصاویر،ساده ترین راه برای پردازش قسمت های مختلف تصویر،تقسیم تصویر ورودی در رمزگذار به بلوک ها یا بردارهای مستطیلی،غیر همپوشانی،چسبیده و کوچک از پیکسل ها است که هر کدام جداگانه کوانتیزه شوند.ابعاد بردار برابر با تعداد پیکسل های هر بلوک می باشد. بعد از تقسیم تصویر به بلوک های مختلف، در هر بلوک بهترین نماینده انتخاب می شود و بعنوان نماینده در کتاب کد ذخیره می شود.این کتاب کد برای گیرنده ارسال می شود و بعد از رمزگشایی،تصویر مورد نظر به نمایش در می آید.هدف اصلی VQ تعیین بهترین دسته از الگوهای بلوک پایه است که به هر کدام یک کلمه کد گفته می شود. این کلمات کد به بهترین نحو،تمام بلوک های تصاویر را در یک تصویر نمایش می دهند. در واقع VQ یک روش فشرده سازی داده است که فرآیند بازسازی را با کمترین انحراف ممکن ارائه می دهد. کیفیت فرآیند بازسازی در VQ به مقدار داده های حذف شده و به مقصد نرسیده بستگی دارد.نمونه های بدست آمده از خروجی منبع درون بردار K بعدی دسته بندی می شوند، این بردار در حقیقت ورودی فرآیند کمی سازی برداری را تشکیل می دهد.مولفه اصلی VQ یک کتاب کد است.که شامل بردارهای نماینده با عنوان بردارهای کد می باشد.عناصر بردار کد را در حقیقت مقادیر کمی سازی شده نمونه های ورودی تشکیل می دهند.نگهداری و ذخیره کتاب کد یکسان در فرستنده و گیرنده الزامی است. برای یافتن مشابه ترین و نزدیک ترین بردار کد به بردار ورودی، کتاب کد برمبنای معیار خطای انحراف جستجو می شود.شاخص بردار کد منتخب(که در قالب باینری همان آدرسش بوده)برای گیرنده ارسال می گردد.گیرنده به یک جدول جستجو ساده نیاز دارد،شاخص دریافت شده جهت تولید دوباره یا تکثیر بردار ورودی در برگیرنده K نمونه،مورد استفاده قرار می گیرد.از الگوریتم های متفاوتی برای بدست آوردن کتاب کد بهینه استفاده شده است.تهیه کتاب کد مناسب بر کیفیت عکس فشرده شده تاثیر مستقیمی دارد در بحث فشرده سازی تصاویر از روش ها و الگوریتم های متفاوتی استفاده شده است. برای VQ باید گفت این کار شبیه زمانی است که می خواهیم یک عدد را به نزدیک ترین عدد ممکن گرد کنیم. که به آن VQیک بعدی هم گفته می شود هر عدد کمتر از 2- به سمت 3- گرد می شود.هر عدد بین 2- و 0 به 1- گرد یا نسبت داده می شود.هر عدد بین 0 و 2 به 1+ گرد می شود و هر عدد بزرگتر از 2 به عدد 3 گرد می شود. در این حالت ارزش تقریبی توسط دو بیت نشان داده می شود.

یک کمی ساز برداری،بردارهای K بعدی را در فضای برداری R^K به صورت یک مجموعه متناهی از بردارها {y_i :i=1,2,…,N} Y= نشان می دهد. هر بردار y_i یک بردار کد یا کلمه کد نامیده می شود.مجموعه ای از همه کلمات کد را کتاب کد می گویند.هر کلمه کد y_i با نزدیک ترین همسایه خود در یک ناحیه و گروه قرار می گیرند که به آن ناحیه ورونوی (Voronoi region) می گویند. در علم ریاضیات دیاگرام ورونوی روشی برای تقسیم فضا به تعدادی ناحیه می باشد.در این دیاگرام به هر مجموعه ای از نقاط، ناحیه ای اختصاص داده می شود. این نواحی سلول های ورونوی نامیده می شود. برای یک مجموعه از نقاط دیاگرام ورونوی سطح را به مناطقی تقسیم بندی می کند که برای هر نقطه از مجموعه نقاط، یک منطقه تعریف می شود. به طوری که تمام نقاط این منطقه به نقطه تولید کننده آن منطقه نزدیکتر می باشد.ناحیه ورونوی در کمی سازی برداری طبق رابطه ی زیر تعریف می شود:

{Vi={xϵR^k: ║x-y_i║ ≤║x-y_j║, for all j≠i}

R نشان دهنده نرخ می باشد در مثال بالا تقریبی(نرخ) توسط دو بیت نشان داده شده است. در VQ دو بعدی نرخ بیت 4 می باشد.K نیز نماینده بعد بردار است. به مجموعه ای از تمام نواحی ورونوی در فضای R^K، بخش گفته می شود.

U^N_i=1 V=R^k   ,   ∩^N_i=1 V_i=ᶲ   for all i≠j

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

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

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

[log₂ N]

است که N نماینده تعداد ورودی های ثبت شده درون کتاب کد است.تعداد بیت های مورد نیاز جهت نمایش یک بردار کد،برابر با KR است که K نماینده بعد بردار و R نیز نمایشگر نرخ است. با محدود کردن تعداد ورودی های ثبت شده در این کتاب کد،N کمتر از 2^KR بدست می آید.فرآیند فشرده سازی بر حسب تعداد بیت های مورد نیاز هر نمونه با :

([log₂ N]/K)

اندازه گیری می شود.فرآیند فشرده سازی بدست آمده با K بعد مربوط به بردار افزایش یافته،در صورتیکه اندازه کتاب کد به صورت نمایی گسترش می یابد. پیچیدگی رمزگذار به مواردی نظیر: اندازه کتاب کد،بعد بردار کد و تعداد محاسبات مورد نیاز جهت یافتن نزدیکترین بردار کد بستگی دارد.همانطور  که قبلا گفته شد کمی سازی برداری شامل سه عمل اصلی رمز گذاری،تولید کتاب کد و رمزگشایی می باشد. برای فشرده سازی تصاویر در ابتدا تصویر ورودی را در رمزگذار به بلوک ها یا بردارهای مستطیلی،غیر همپوشانی،چسبیده و کوچک از پیکسل ها تقسیم بندی می کنند. که معمولا به بلوک های 4×4 تقسیم می شوند.به گروهی از المان هایی مثل پیکسل ها بردار گفته می شود. هر کدام از این بلوک ها جداگانه کوانتیزه می شوند. ابعاد بردار مساوی تعداد پیکسل های هر بلوک است. همانطور که در شکل می بینید در ابتدا تصویر ورودی به بلوک های 2×2 تقسیم شده است.سپس هر بلوک به یک بردار با ابعاد 4×1 تبدیل شده است. اولین بردار X₁=(7,10,14,16) به هفتمین کلمه کد از کتاب کد نگاشت می شود. شاخص هفتمین کلمه کد،جایگزین بردار برای نمایش بلوک می شود و هنگامی که رمزگشا،جدول شاخص را دریافت می کند از هفتمین کلمه کد C₇=(9,6,9,9) برای بازسازی اولین بلوک استفاده می کند.عکس نهایی،تصویر بازسازی شده Reconstructed Image)) نامیده می شود.

یکی از نکات کلیدی VQ،طراحی یک کتاب کد خوب به طوری که حداقل انحراف،بین تصویر اصلی و تصویر بازسازی شده وجود داشته باشد.علاوه بر این،پروسه تولید کتاب کد یک پروسه زمانبر است و کیفیت تصویر بازسازی شده تا حد زیادی به کتاب کد انتخاب شده بستگی دارد. الگوریتم های متفاوتی برای انتخاب کتاب کد بهینه مورد استفاده قرار گرفته اند.در ابتدا باید گفت که دو نوع کتاب کد وجود دارد. کتاب کد محلی (Local Codebook) و کتاب کد عمومی ((Global Codebook.کتاب کد محلی،کتاب کدی است که تنها برای یک عکس ایجاد شده است یعنی این کتاب کد از بردارهای یک تصویر بدست آمده است. عملکرد(کیفیت بازسازی) خوبی دارد و به دلیل محاسبات بیشتر و انتقال کتاب کد به رمزگشا سربار(Overload) بیشتری هم دارد. اما کتاب کد عمومی برای کلاسی از تصاویر ساخته می شود در واقع کتاب کد از بردارهایی از همه تصاویر در یک کلاس ساخته می شود. عملکرد یا کیفیت بازسازی به دلیل اینکه از یک کتاب کد واحد برای بازسازی کلاسی از تصاویر استفاده می شود پایین است. اما در این حالت محاسبات کمتری انجام می شود و تعداد انتقال کتاب کد به رمزگشا کم است. بنابراین کتاب کد عمومی در مقایسه با کتاب کد محلی سربار کمتری دارد. برای ارزیابی کارایی VQ هیچ راه حل مناسبی وجود ندارد علت این امر این است که انحراف VQ توسط انسان بدست می آید و این یک اندازه گیری ذهنی است.در هر حال از میانگین خطای مربع( MSE:Mean Squared Error) و نسبت سیگنال به نویز(PSNR: Peak Signal to Noise Ratio) برای ارزیابی کارایی VQ استفاده می شود. MSE مطابق با رابطه زیر تعریف می شود:

که در آن M نشان دهنده تعداد المان های سیگنال یا تصویر می باشد. برای مثال اگر ما بخواهیم MSE را بین دو تصویر اصلی و تصویر بازسازی شده پیدا کنیم باید تفاوت بین دو عکس را پیکسل به پیکسل بررسی کنیم که فرمول بالا میانگین نتایج را نشان می دهد. PSNR هم مطابق رابطه زیر تعریف می شود:

که در آن n تعداد بیت های هر نماد است. برای مثال، اگر ما بخواهیم PSNR را بین دو تصویر خاکستری 256 پیدا کنیم،n=8 می شود.

منبع : mqasem