بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
استفاده از تبدیل هادامارد جهت فشرده سازی تصاویر
چکیده
استفاده از تبدیلات مختلف تصویر جهت کدینگ و فشرده سازی از روشهای متداول می باشد. روش zonal compression از روشهای مؤثر فشرده سازی توسط تبدیل کسینوسی گسسته((DCT می باشد که از ایدۀ تمرکز انرژی در نواحی خاصی از تبدیل استفاده می کند. از معایب قابل توجه در روش فوق، ضرائب بکار رفته در DCT می باشد که اعشاری می باشند. روش ارائه گشته توسط این مقاله، از تبدیل هادامارد که دارای ضرائب +1 و -1 می باشد، استفاده می نماید. مهمترین نکته در تبدیل هادامارد، یافتن مناطقی از تبدیل می باشد که بیشترین انرژی تصویر در آن مناطق نهفته می باشد. تحقیقات نشان می دهد ک فقط با استفاده از ./15. کل مقادیر ماتریس تبدیل می توان 0/94 کل توان تصویر را در اختیار گرفت.
کلمات کلیدی: پردازش تصویر- تبدیل هادامارد- فشردگی تصاویر.
-1 مقدمه
مفهوم تبدیل1 به مفهوم نمایش تصویر در حوزه ای غیر از حوزۀ زمان بر اساس توابع پایه مختلف می باشد به نحویکه بتوان هر تصویر را به صورت ترکیب خطی از یک سری تصاویر پایه نوشت. در اثر تبدیل،معمولاً میتوان روابط مشکل کانولشن در حوزۀ زمان را با روابط سادۀ ضرب در حوزۀ تبدیل معادل ساخت. همچنین می توان همبستگی مقادیر پیکسل ها را توسط توابع پایه تعریف شده، از بین برد و جهت کدینگ یا ذخیره سازى فقط به ضرائب توابع پایه بسنده کرد. در حالت یک بعدی ، تبدیل یافته سیگناله N نمون x(n) به صورت رابطه جمع و ماتریسی به صورت رابطه 1 نوشته می شود:
در حالت تبدیل unitary خواص ویژه ای نیز مطرح می گردد که:
و در نتیجه رابطه تبدیل و عکس آن را می توان به صورت خلاصه همانگونه که رابطه 3 نشان میدهد، نوشت:
مهمترین خاصیت تبدیل unitaryآن است که انرژی سیگنال اصلی و تبدیل یافته آن یکسان می باشد.
درواقع، در حالی که مقادیر اصلی دارای همبستگی بالائی می باشند، مقادیر تبدیل یافته، ناهمبسته خواهند بود.
یکی از تبدیلات مهم در این زمینه، تبدیل هادامارد می باشد. این تبدیل بدلیل اینکه دارای خواص فرکانسی مشخص مانند تبدیل فوریه نمی باشد، تاکنون کاربرد قابل توجهی نیافته است. در این مقاله ضمن اشاره به خواص ویژۀ این تبدیل سعی گردیده است امکان کاربرد آن نیز مورد بحث و ارزیابی قرار گیرد.
-2 تبدیل هادامارد
فرض می گردد که سیگنال اصلی x(n) برای تعریف شده است، و میباشد . در نتیجه به منظور نمایش شمارۀ هر نمونه به صورت باینری از L بیت استفاده می شود که به صورت: نمایش داده می شود که b=1 یا b=0 می باشد. در این صورت تبدیل هادامارد به صورت رابطه 5 تعریف میشود
می باشد. در
bL−1bL−2 Lb1b0
می گردد :[1]
بطور مشخص ضرائب تبدیل با صرفنظر از مقدار ثابت برابر می باشند. اگر روابط به صورت ماتریسی بیان گردند، در حالتی که می باشد است که هر ردیف آن یک بردار ویژه در فضای 2×1 می باشد. اگر N مقادیر بزرگتری را در بر گیرد، ماتریسهای بزرگتری با ید برای آن تعریف نمود. این ماتریسها توسط یک آلگوریتم برگشتی به صورت رابطه 6 قابل محاسبه خواهند بود :[2]
محاسبه ماتریس انتقال به صورت برگشتی مستلزم صرف زمان زیادی می باشد. بدین دلیل محققین در صدد یافتن روشی برای محاسبه مستقیم ماتریس انتقال برآمده اند کهذیلاً بطور خلاصه توضیح داده شده است :[5-3]
در ماتریس B اعداد 0 تا N-1 را به صورت باینری با L بیت زیر هم نوشته می شوند تا ماتریس BN به ابعاد N×L ساخته شود. در این صورت:
لازم به ذکر است که ضرب و جمع در دستگاه باینری انجام می گردد، یعنی برای اعداد زوج، صفر و برای اعداد فرد، یک منظور می گردد.به طور مثال برای N=4، ماتریس انتقال را می توان به شکل زیر محاسبه نمود:
بررسی بیشتر بر روی ماتریس انتقال نشان می دهد که ماتریسهای انتقال متقارن بوده و تمام سطرها و همچنین ستونها نسبت به هم متعامد می باشند به نحویکه حاصل جمع مجذور مقادیر هر ردیف یا هرستون برابر N می گردد.
مقایسه هر دو ردیف (یا هر دو ستون) متمایز نشان می دهد که N/2 از عناصر یکسان هستند که نیمی از آنان دارای مقدار +1 و نیمی دیگر دارای مقدار -1 می باشند. N/2 بقیه عناصر در دو ردیف متمایز، متفاوت خواهند بود که N/4ز ا آنان به صورت (+1,-1) و N/4 دیگر به صورت (-1,+1) می باشند. ترتیب تغییرات اعداد در هر سطر یا ستون از +1به -1 که در واقع تعداد نقاط عبور از صفر را نشان می دهد، دارای ترتیب خاصی می باشد که در مرجع [4] به آن اشاره گردیده است. با توجه به رابطه تبدیل (1) و ماتریس انتقال بطور مثال برای N=4 می توان یک سری از خواص ویژه را در مؤلفه های مختلف یافت. به طور مثال، مؤلفه y(0) نمادی از مقدار متوسط یا DC سیگنال خواهد بود. همچنین مؤلفه y(1) نشانگر کیفیت وجود بالاترین فرکانس در سیگنال اصلی خواهد بود. مؤلفه های دیگر فرکانسهای کوچکتری از تصویر اصلی را نشان می دهند.
تبدیل هادامارد برای سیگنال دو بعدی با اندازۀ N×N به صورت رابطه 8 نشان داده می شود:
با توجه به خاصیت جدائی پذیری در توابع انتقال (8) می توان رابطه را به صورت ماتریس نشان داده شده در رابطه 9 نمایش داد که:
که در اینجا،
رابطه (8) را با استفاده از تصویر پایه نیز می توان تعریف کرد. بدین ترتیب که هر مؤلفه تبدیل هادامارد را حاصل ضرب داخلی تصویر اصلی در یک تصویر پایه مربوط به مؤلفه (k1,k2) در نظر گرفت. تصویر پایه مربوطه را به صورت رابطه 11 با توجه به رابطه (8) می توان محاسبه کرد:
در رابطه (11)، برای هر مؤلفه (k1,k2)، یک ماتریس تصویر پایه N×N به ازای مقادیر مختلف (m,n) محاسبه می گردد و سپس:
در نتیجه می توان انتظار داشت که چگونگی مقادیر داخل هر تصویر پایه(در مجموع N2 تصویر پایه)، خواص مؤلفه مربوط به آن را نشان دهد. این مسئله، سبب بررسی بیشتر اشکال تصاویر پایه هادامارد که همگی از +1 و -1 تشکیل گردیده اند و هر دو تصویر پایه مختلف، بر هم orthogonal می باشند، می گردد. از دیگر خواص مهم تصاویر پایه هادامارد آن است که:
بررسی تصاویر پایه، نشانگر خواص نهفته شده در هر مؤلفه ای از تبدیل، y(k1,k2) می باشد. بطور مثال، تصویر پایه مربوط به تبدیل DFT که از رابطه (14) بدست می آید [2] ، در شکل (1) برای N=8 محاسبه و نمایش داده شده است. این تصاویر از گوشه بالا سمت چپ، تصویر پایه مربوط به مؤلفه (0,0) شروع گردیده و در گوشه پائین سمت راست به تصویر پایه مربوط به مؤلفه (7,7) ختم می شود. در نتیجه مؤلفه (0.0) از تبدیل نشانگر مقدار متوسط تصویر
می باشد و مقدار مؤلفه (k1,k2)ام نیز نشانگر مؤلفه در حوزۀ فرکانسی می باشد. باتوجه به خواص تقارنی در DFT، بیشترین فرکانس در مؤلفه مرکزی (4,4) و مجاورت آن می باشد که حول (π, π) هستند و تصایر پایه مربوط به مؤلفه های فرکانس پائین در کنار لبه ها قرار گرفته اند. نکات فوق در تصاویر پایه مربوط به هر یک از مؤلفه ها نیز مشهود می باشد.
شکل -1 تصاویر پایه DFT برای .N=8تصاویر پایه مربوط به تبدیل هادامارد نیز از طریق رابطه 15 قابل محاسبه خواهد بود:
شکل 2 تصاویر پایه تبدیل هادامارد را برای مقادیر N=8 و N=16 نشان می دهد:
شکل -2 راست- 64 تصاویر پایه هادامارددر اندازۀ 8×8 برای N=8،
چپ- 256 تصاویر پایه هادامارددر اندازۀ 16×16 برای .N=16
برخلاف تبدیل DFT در تبدیل هادامارد تقارن بین تصاویر پایه مختلف برقرار نبوده و همچنین برخلاف DFT و DCT و Walsh توزیع فرکانسهای مختلف نیز مرتب نمی باشد. بطور مثال، تصویر پایه (0,0) محاسبه کنندۀ مقدار متوسط یا فرکانس صفر می باشد، در حالی که مؤلفه (1,1) محاسبه کنندۀ بیشترین فرکانس تصویر می باشد. با کمی دقت مشاهده می شود که از نظر افزایش فرکانسی پس از مؤلفه های ستون و سطر اول که مؤلفه های (0,:) و (:,0) را در بر می گیرند و نشانگر چگونگی وجود فرکانسهائی فقط در جهتسطرافقی و یا عمودی می باشند، N/2 و همچنین ستون N/2 قرار دارند. سپس سطر های(یا ستونهای) N/4 و 3N/4 قرار می گیرند. دلیل وقوع چنین ترتیبی را در نمایش باینری این مقادیر می توان یافت. با توجه به آنکه، N=2L در نظر گرفته شده است، در نمایش باینری عدد N/2 یا N/4 همگی به جز یکی صفر خواهند بود و به همین دلیل در محاسبه مقدار تبدیل فقط اثر پیکسلهائی که در
