بخشی از مقاله
خلاصه
در این مقاله، یک الگوریتم فشرده سازی مبتنی بر تبدیل موجک بسته ای به همراه الگوریتم تجزیه به نقاط منفرد پیشنهاد می شود. به طور دقیق تر، با تفکیک اطلاعات موجود در یک تصویر به بسته های مختلف مکان-فرکانس، می توانیم اطلاعات اضافی - بی اهیمت در بازسازی تصویر - در مکان های مختلف تصویر را از محتوای فرکانسی تصویر حذف کرده و به این ترتیب به کاهش حجم اطلاعات لازم برای نمایش و کد کردن یک تصویر کمک کنیم.
در واقع اجزای اصلی و محتوای اصلی مکان -فرکانس یک تصویر توسط بسته های موجک و الگوریتم SVD استخراج شده و توسط کدینگ هافمن کد می شوند. پس از اعمال روش و استخراج روند الگوریتم، شبیه سازی در محیط MATLAB و با نوشتن کد برنامه انجام می شود تا نتایج حاصل از فشرده سازی با روشهای دیگر متداول مانند jpeg و SVD مقایسه گردد
.1 مقدمه
هر چند ذخیره سازی دیسک سخت و درایوهای نوری و دیسک های فلش افزایش چشم گیری داشته و سرعت انتقال داده ها نیز نسبت به گذشته رشد قابل توجهی را تجربه می کند با این حال به دلایل مختلف ممکن است بخواهیم حجم فایل ها را تا حد امکان کم کنیم. فشرده سازهای گوناگون با روش هایی تقریبا یکسان و جزئیاتی متفاوت حجم فایل ها را کاهش می دهند.
مهمترین اصل در فشرده سازی وجود تکراردر محتوای فایل ها است. به این معنی که اگر در یک فایل متنی یک جمله یا کلمه چندبار تکرار شده باشد این جملات و کلمات توسط فشرده ساز شناسایی می شوند و تنها یکبار در فایل فشرده ذخیره می شوند. در نتیجه هر چه تعداد و حجم تکرار در فایل ها بیشتر باشد فشرده سازی نتیجه بهتری می دهد. مقالات زیادی در مورد فشرده سازی تصویر ارائه شده اسن. برخی بر روی فشرده سازی بدون اتلاف تمرکز داشته اند
برخی دیگر، تلاش کرده اند تا به ارائه روشهایی برای فشرده سازی تصاویر رنگی بپردازند . [5-3] برخی دیگر در مورد تصاویر پزشکی تلاش کرده اند.[6] شبکه های عصبی نیز در فرآیند فشرده سازی تصاویر بکار گرفته شده است
در این مقاله، تاثیر روش تجزیه تنک روی فشرده سازی تصاویر مورد مطالعه قرار گرفته است. شیوه های فشرده سازی متعددی در سالهای گذشته ارائه شده بود که بهترین و کاراترینشان JPEG بود و از دیکشنری DCT استفاده می نمود، در واقع با حذف مولفه های نزدیک به صفر DCT دو بعدی بلوکهای تصویر، عمل فشرده سازی را انجام می داد و حافظه ی کمتری برای داده ی کد شده آن نیاز بود. بعدها روش فشرده سازی JPEG2000 معرفی شد که به جای DCT از DWT که بر پایه ی تبدیل ویولت بود، استفاده می نمود.
این منجر به فشرده سازی بیشتری می شد. این دو روش بطور خلاصه مورد بررسی قرار می گیرد. الگوریتم K-SVD که توسط Michael Elad ارائه شده یک روش بر پایه ی نمایش تنک بوده که در فشرده سازی و حذف نویز تصویر و... نقش مفیدی داشته و نسبت به روشهای قبلی بهینه تر می باشد.
نحوه ی بکار گیری این الگوریتم در ساخت دیکشنری بصورت وفقی و حذف نویز تصویر نیز مورد بررسی قرار گرفته است. در ادامه تجزیه تصاویر به دو مولفه-ی texture و طبیعی بررسی می شود که برای هر کدام از این مولفه ها دیکشنری خاصی در نظر گرفته می شود و نقش مهمی در کاربردهایی مثل فشرده سازی و... تصاویر می تواند داشته باشد. همچنین در ادامه حالت خاص فشرده سازی تصاویر صورت که کاربردهای متعددی دارد و مورد توجه زیادی است با استفاده از الگوریتم K-SVD و کوانتیزاسیون برداری که از یک پایگاه داده ی تصاویر صورت زیادی کمک می گیرد، توضیح داده شده است.
تبدیل موجک
تبدیل موجک اطلاعات را به صورت همزمان در دو حوزه زمان و فرکانس ارائه میکند. در تبدیل موجک بر خلاف تبدیل فوریه, که سیگنال یا سری اطلاعاتی را بر روی توابع سینوسی و کسینوسی و هارمونیک های آنها تجزیه میکرد, سیگنال برروی یک دسته از توابع که موجک نامیده میشوند وبر گرفته از موج مادر میباشند تصویر میگردد . واژه مادرنیز به این منظور به کاربرده میشود که تمامی نسخه های انتقال یافته و مقیاس شده همگی از روی یک تابع اولیه به دست می آید که اصطلاحاً ویولت مادر نامیده میشود. بر خلاف توابع سینوسی و کسینوسی در تبدیل فوریه تابع موجک در فضای زمان محدود بوده و بعد از چند ارتعاش به سرعت به سمت صفر میل میکند. تئوری موجک برای غلبه بر مشکلات تبدیل فوریه ارائه گردیده است .
در این روش مسئله تقسیم سیگنال به بخشهای مختلف با استفاده از مقیاس گذاری و انتقال دادن یک تابع حل می شود. این تابع در طول سری اطلاعاتی انتقال پیدا میکند و برای هرموقعیت آن، طیف سری اطلاعاتی محاسبه میشود. این مراحل برای توابعی با مقیاسهای مختلف تکرار میشود و در نهایت نتیجه حاصل به صورت مجموعهای از اطلاعات آرگومان –فرکانس بدست میآید. ویژگی اصلی تبدیل موجک در مقابل تبدیل فوریه زمان کوتاه اینست که تمامی توابع پایه از انتقال و مقیاس یک تابع - موجک مادر - بدست می آیند. شکل کلی تبدیل پیوسته ویولت به ×صورت زیر است :
در تبدیل موجک یک شباهت سنجی بین سیگنال و توابع پایه - ویولت ها - است و منظور از شباهت سنجی در این بحث شباهت بین محتوای فرکانسی است. نتیجه تبدیل ویولت یک ماتریس است که ستونهای آن جابجایی در زمان را نشان می دهد و سطرهای آن مقیاس مورد بررسی را نشان میدهد. به بیان دیگر ضرایب تبدیل ویولت بیانگر میزان نزدیکی سیگنال به ویولت در مقیاس مورد نظر میباشد.
با توجه به اینکه تصاویر دارای دو بعد میباشند، اگر یک تصویر توسط تبدیل موجک گسسته مورد تجزیه قرار گیرد،چهار تصویر بدست می آید : یک تصویر مربوط به کلیات و سه تصویر مربوط به جزئیات - جزئیات افقی، عمودی وقطری -
شکل:1تجزیه تصویر به سطوح مختلف
تجزیه نقاط منفرد
در دسترس است. این × نحوه تجزیه یک ماتریس به مقادیر منفرد آن به صورت زیر است. فرض کنید ماتریس ×ماتریس را می توان به صورت زیر تجزیه کرد:
که U و V ماتریس هایی m*m و n*n هستند. ماتریس Σ نیز یک ماتریس قطری با درایه های بر روی قطر اصلی است. این درایه ها همان نقاط منفرد هستند.
حال می توان با استخراج مقادیر منفرد یک ماتریس و انتخاب بزرگترین مقادیر منفرد و دور ریختن کوچکترین ها بعد فضای داده ها را کاهش دهیم. فرض کنید تنها K مقدار از بزرگترین نقاط منفرد را انتخاب کنیم. آنگاه می توان ماتریس را که تقریبی از ماتریس A است با استفاده از این K مقدار به صورت زیر ساخت:
که و ستون iام از ماتریس هاس U وV هستند. به عبارت دیگر، ستونهای ماتریس U و V به ترتیب از بردارهای ویژه ماتریس های و هستند. مقدار K بر اساس میزان خطای قابل تحمل مابین ماتریس A و محاسبه می شود. دقت کنید که در این حالت یعنی هنگامی که یک ماتریس به جای A با نمایش داده شود حجم داده های لازم برای ذخیره کردن از n*m به k* - n+m+1 - کاهش می یابد. در نرم افزار MATLAB دستور svd برای تجزیه یک ماتریس به مقادیر منفرد آن است. چون یک تصویر را به صورت ماتریسی نشان می دهند لذا می توان الگوریتم تجزیه مقادیر منفرد را بر روی کدهای رنگی آن به همین صورت اعمال کرد.
کدینگ هافمن
در روش کد هافمن - Huffman coding - الگوریتم زیر بکار گرفته می شود:
1. مرتب سازی سمبول ها بر اساس فرکانس تکرار هر کدام
2. تا زمانی که تنها یک سمبول باقی بماند مراحل زیر را تکرار کن
3. دو سمبول با کمترین تکرار را انتخاب کرده و یک زیر درخت با آن تشکیل می دهیم و یک کد معادل برای والد آن ها در نظر می گیریم.
