بخشی از مقاله
معرفی ومقایسه سخت افزارهای مختلف در پیاده سازی
تبدیل موجک گسستهشبرای فشرده سازی تصویر
چکیده:کاربرد تبدیل موجک در پردازش تصویر مانند استاندارد خنغبق,تتتلسنغبپ روز به روز گسترده تر می شود. در این مقاله ابتدا الگوریتم های مهم در تبدیل موجک معرفی می شوند و سپس سخت افزار های تبدیل موجک دو بعدی معرفی ومقایسه می شوند. ش
ش
واﮊگان کلیدی : تبدیل موجک دو بعدی و الگوریتم هرمی
۱- مقدمه ش
در ده سال اخیر پژوهشهای زیادی در تکنیکهای تبدیل موجک و بکارگیری آن در انجام تبدیل موجک دو بعدی برای تصویر صورت گرفته است. تبدیل موجک به خاطر خصوصیتهای جالبش در فشرده سازی تصویر و ویدئو بسیار مورد توجه قرار گرفته است. تبدیل موجک در واقع تجزیه یک سیگنال غیر ایستا به مجموعه ای از توابع موجک با مقیاسهای متفاوت است که این مجموعه نسبتا ایستا است وبرای کدشدن مناسب است. با مقایسه تبدیل موجک با بقیه تبدیلها، دیده می شود که تبدیل موجک انعطاف پذیرتر است وبه دلیل تحلیل مقیاس _مکان (به جای فرکانس _زمان) بهتر می تواند با طبیعت بینایی _روانی انسان تطبیق یابد. همچنین چون تبدیل موجک بطور یکجا روی کل تصویر انجام می شوددارای اثر منفی بلوک _ بلوک شدن تصویر نمی باشد.
در بخش دوم این مقاله در مورد تبدیل موجک گسسته مقدمه ای بیان می شود. در بخش سوم الگوریتمهای عمده در تبدیل موجک و در بخش چهارم سخت افزارهای تبدیل موجک دو بعدی عنوان می شوند. بخش پنجم مقایسه روشهای ارائه شده را در بر دارد و بخش آخر، بخش ششم، به نتیجه گیری می پردازد.
۲- تبدیل موجک گسسته یک بعدی و دو بعدی ش ۲-۱- تبدیل موجک یک بعدی ش
هر تابعی که بطور مربعی انتگرال پذیر است دارای تبدیل موجک گسسته است. نمایش یک تابع به صورت مجموع خانواده ای از توابع پایه به نام توابع موجک، تبدیل موجک گسسته نام داردح خانواده توابع پایه موجک می تواند از انتقال دادن یا مقیاس کردن تابع موجک مادر آن خانواده حاصل شود. ضرائب تبدیل موجک گسسته بوسیله انجام ضرب داخلی بین سیگنال ورودی وتوابع موجک بدست می آید. چون توابع پایه موجک، انتقال یافته و یا مقیاس شده یکدیگرند یک الگوریتم ساده تر به نام الگوریتم ملات یا الگوریتم هرمی ارائه شده استب۱م. در نمودار هرمی یا درختی، سیگنال اصلی با دو فیلتربالاگذر وپایین گذر به سیگنالهای فرکانس بالاو فرکانس پایین تجزیه می شوند و سپس نمونه برداری کاهنده می شوند.خروجی فیلتربالاگذر وپایین گذر به ترتیب موسوم به اطلاعات تقریب وجزئیات هستند. اطلاعات تقریبی در مرحله بعد دوباره به سیگنالهای تقریب وجزئیات تجزیه می شوند و دوباره نمونه برداری کاهنده می شود و برای مراحل بعد هم همینطور ادامه می یابدح
۲-۲- تبدیل موجک گسسته دو بعدی ش
تبدیل موجک گسسته دو بعدی با استفاده از روش جدا شدنی انجام می شودب۲م. ابتدا تبدیل موجک گسسته یک بعدی در سطرها انجام می شود و سپس نتیجه که یک ماتریس مستطیلی است(به خاطر نمونه برداری کاهنده در جهت سطر، مستطیلی است) این دفعه در جهت ستون تبدیل موجک گسسته یک بعدی به عمل می آید. شکل(١) تجزیه موجک تا سطح سوم را نشان می دهد. تجزیه در سطح اول یک زیر تصویر پایین گذر لعع وسه زیر تصویر بالاگذر (صدد,صعد,صدع) می دهد. این پردازش دوباره روی لعع تکرار می شود و خروجی (صدد,صعد,صدع) هست. این پردازش روی تصویر پایین گذر برای تجزیه تا سطوح بالاتر به همین منوال ادامه می یابد در واقع تبدیل موجک گسسته دو بعدی تصویر را به زیر تصویرهایی با ساختار هرمی تجزیه می کند که در هر سطح بالا، قدرت تفکیک در حوزه مقیاس (فرکانس) کم می شود اما قدرت تفکیک در حوزه مکان افزایش می یابد.این مسئله در شکل (٢) نمایش داده شده است.
شکل(١) : تجزیه موجک دو بعدی تا سطح سوم شکل(٢) : یک تصویر وتجزیه آن تا سه سطح
۳-
الگوریتمهای تبدیل موجک گسسته
۳-۱- الگوریتم هرمی
تبدیل موجک گسستهش نقطه ای ، P ذ N را در نظر بگیرید. می خواهیم j مرحله ،j ≤ p ، تبدیل موجک انجام دهیمب۳م. روش مستقیم مطابق شکل (۳)، الگوریتم هرمی نام دارد. در این روش یا بایدj ردیف فیلتر استفاده کرد که خروجی هر طبقه به طبقه بعد برود و یا بایدیک ردیف فیلتر با یک حافظه از درجه ش استفاده کرد که هر دو روش هزینه سخت افزار هنگفتی دارند.
شکل(٣) : نمودار هرمی برای تبدیل موجک یک بعدی تا سه سطح
۳-۲- الگوریتم هرمی بازگشتی
الگوریتم هرمی بازگشتی از بازنویسی فرمولهای الگوریتم هرمی کلاسیک بدست میآید. این الگوریتم اجازه میدهد تا بتوان بطور بلادرنگ و با جذسjضحش سلول حافظه، تبدیل موجک گسسته را محاسبه کرد. که حش طول فیلتر میباشد. یعنی در این روش برای فیلتر
کردن در سطح دوم منتظر تمام خروجی در سطح اول نمی مانیم، بلکه هر خروجی از سطح اول در اولین فرصت که بتواند برای محاسبه ضریب در سطح دوم وارد برنامه محاسباتی قرار بگیرد، در نوبت محاسبات قرار میگیردب۴م وب۵م.
شکل(٤) : زمان تبدیل موجک یک بعدی برای سطوح متفاوت
الگوریتم هرمی بازگشتی شامل مرتب سازی خروجی است، به نحوی که هر خروجی در اولین فرصت در صف محاسبات قرار بگیرد. خروجی برای سطوح مختلف برحسب زمان در شکل (٤) آمده است. زمانی که یک خروجی در یک سطح محاسبه می شود به ما برنامه خاصی را که خروجیها باید برای محاسبات در نوبت قرار گیرند، پیشنهاد میکند. خروجی تولید شده توسط الگوریتم هرمی بازگشتی برای
خذچش و خچپ در زیر آمده است. اینجا ، خروجی غ-ام فیلتر پائین گذر در سطح ط–ام میباشد.
خروجی فیلتر بالا گذر هم به همین صورت است.
۳-۳- الگوریتم هرمی بازگشتی بهبود یافته
الگوریتم هرمی بازگشتی بهبودیافته یک مدل بهبودیافته از الگوریتم هرمی بازگشتی میباشد که برای فیلترهای موازی و کاربردهایی که تأخیر بیشتر از یک واحد زمانی دارند مناسب است. تنها هنگامی که تأخیر واحدها بیشتر از یک واحد زمانی می باشد، باید دقت کرد تا اولین خروجی اکتاو (مرحله) بالا، با خروجی اکتاو قبلی ناسازگاری نداشته باشدح
اگر برای اولین خروجی هر اکتاو مسئله سازگاری رعایت شود سپس خروجیهای دیگر آن اکتاو در برنامه محاسباتی دچار مشکل نمیشوند. به عنوان مثال فرض کنید تأخیر محاسبات ٤ واحد زمانی هست سپس برنامه محاسباتی برای اکتاوهای اول، دوم و سوم مطابق الگوریتم هرمی بازگشتی بهبودیافته بصورت زیر است ب۴م :
شکل(٥) : برنامه محاسباتی برای اکتاوهای اول، دوم و سوم مطابق الگوریتم هرمی بازگشتی بهبودیافته
۴- معماری تبدیل موجک گسسته دوبعدی ش ۴-۱- معماری تبدیل موجک گسسته پریودیک دو بعدی
این معماری درنظر دارد تا تبدیل موجک دو بعدی را با بازسازی کامل پیاده سازی کند. معماریهای قدیمی دارای بازسازی غیرکامل بودند. این معماری برای رسیدن به هدف خود باید اطلاعات ابتدا و انتهای سیگنال ورودی را ذخیره کند. تأخیر مدار یک میباشد. این معماری شامل پنج نوع پردازش است که دو جزﺀ آن شامل پردازش اطلاعات سطری و ستونی هست. برای اینکه خروجی پردازش سطری برای پردازش ستونی منتقل شود یک فرآیند ترانهاده انجام میشود. این عمل با ذسع ردیف از شیفت رجیستر انجام میشود که ع طول فیلتر هست. در آخرین پردازش باید اطلاعات لازم برای پیادهسازی کامل فراهم شود. برای آنکه زمینه برای پردازش پنجم(بازسازی کامل) مهیا شود، باید از روش هرمی استفاده کرد و نباید از روشهای بهبود یافته دیگر استفاده کرد. معماری حاصل در شکل(٦) آمده استب ۶م.
۴-۲- معماری تبدیل موجک گسسته پریودیک جدانشدنی دوبعدی ش
این معماری هم جهت انجام تبدیل موجک با بازسازی کامل سیگنال ورودی را پریودیک میگیرد. با قصد تبدیل موجک با بازسازی کامل بسیاری از ضرایب باید ذخیره شوندب۷م و ب۸م. فرض کنید jحح ماتریس ورودی برای تبدیل موجک دوبعدی در اکتاو –jام باشد و ن
شکل(٦) : معماری تبدیل موجک گسسته پریودیک دو بعدی برای فیلتر با طول خچئ
و د دو ماتریس متناظر با فیلتر بالاگذر و پائین گذر باشند و jح2 ضرایب افقی باشد، 2jح ضرایب عمودی افقی باشد و 22j ضرایب قطری باشد، آنگاه
که ص نشانه ترانهاده است. فرض کنید طول فیلتر چهار هست و ش طول سیگنال ورودی هست، برای محاسبه جت,تض ذSS j ، ۶١ عنصر
jحح نیاز است:
پس بعد از محاسبه جص,صض SS j ، جت,تض ذSS J قابل محاسبه است. ولی جت,تض ذdd j به ۶١ عنصر دیگر نیاز دارد و تنها بعد از
اینکه تمام تصویر تبدیل شد قابل محاسبه هست و این زمان زیادی می طلبد. برای حل این مشکل از تبدیل همومورفیک استفاده میشود. با این تبدیل ۶١ عنصر لازم برای هر چهار موقعیت حح، 2ح،ح2، 22 یکی میشود. برای کاهش محاسبات پیچیده از شباهت فیلتر بالاگذر و پائین گذر استفاده میشود که الگوریتم همبستگی عملگر نام دارد. عیب این روش این است که الگوریتم همبستگی عملگر تنها برای موجکهای با خاصیت انعکاس آینهای جواب میدهد. همچنین معماری حاصل تعداد زیادی مالتی پلکسر نیاز دازد که سیم بندی مدار زیاد میشود.
۴-۳- معماری کسکود شونده ش
این معماری دارای ساختار ماجولار، ساده و کسکود شونده برای تبدیل موجک یک بعدی و دو بعدی و بالاتر است. در این معماری برای اختصاص دهی رجیستر دو الگوریتم متفاوت به نام الگوریتم تخصیص دهی رجیستر از جلو و الگوریتم تخصیص دهی رجیستر از جلو و عقب وجود داردب۹م. در زیر اجزای این معماری ارائه میشود:
١- آرایه سیستولیک: این آرایه شامل چهار عنصر است: تأخیر ورودی، فیلتر،بانک رجیستر و مدار کنترل.
٢- سلول فیلتر: جمع و ضرب برای عمل فیلتر در این سلول انجام می شود، در نیم سیکل عملیات فیلتر بالاگذر و در نیمی دیگر عملیات فیلتر پائین گذر انجام می شود. تعداد رجیسترهای این آرایه مطابق الگوریتم تخصیص دهی رجیستر از جلو بدست می آید. آرایه
