مقاله بررسی ماتريس الگوريتم

مقاله بررسي ماتريس الگوريتم در 23 صفحه ورد قابل ويرايش

-2) EZW

الگوريتم EZW در سال 1993 توسط shapiro ابداع شد نام كامل اين واژه به معناي كدينگ تدريجي با استفاده از درخت ضرايب ويولت است. اين الگوريتم ضرايب ويولت را به عنوان مجموعه اي از درختهاي جهت يابي مكاني در نظر مي گيرد هر درخت شامل ضرايبي از تمام زيرباندهاي فركانسي و مكاني است كه به يك ناحيه مشخص از تصوير اختصاص دارند. الگوريتم ابتدا ضرايب ويولت با دامنه بزرگتر را كددهي مي كند در صورتيكه دامنه يك ضريب بزرگتر يا مساوي آستانه مشخص باشد ضريب به عنوان ضريب معني دار در نظر گرفته مي شود و در غير اينصورت بي معني مي باشد يك درخت نيز در صورتي معني دار است كه بزرگترين ضريب آن از نظر دامنه بزرگتر يا مساوي با آستانه مورد نظر باشد و در غيراينصورت درخت بي معني است.

مقدار آستانه در هر مرحله از الگوريتم نصف مي شود و بدين ترتيب ضرايب بزرگتر زودتر فرستاده مي شوند در هر مرحله، ابتدا معني دار بودن ضرايب مربوط به زير باند فركانسي پايين تر ارزيابي مي شود اگر مجموعه بي معني باشد يك علامت درخت صفر استفاده مي شود تا نشان دهد كه تمامي ضرايب مجموعه صفر مي باشند در غيراينصورت مجموعه به چهارزيرمجموعه براي ارزيابي بيشتر شكسته مي شود و پس از اينكه تمامي مجموعه ها و ضرايب مورد ارزيابي قرار گرفته اند اين مرحله به پايان مي رسد كدينگ EZW براساس اين فرضيه استوار است كه چگالي طيف توان در اكثر تصاوير طبيعي به سرعت كاهش مي يابد بدين معني كه اگر يك ضريب در زير باند فركانسي پايين تر كوچك باشد به احتمال زياد ضرايب مربوط به فرزندان آن در زير باندهاي بالاتر نيز كوچك هستند به بيان ديگر اگر يك ضريب والد بي معني باشد به احتمال زياد فرزندان آن نيز بي معني هستند اگر آستانه ها توانهايي از دو باشند ميتوان كدينگ EZW را به عنوان يك كدينگ bit-plane در نظر گرفت در اين روش در يك زمان، يك رشته بيت كه از MSB شروع مي شود كددهي مي شود با كدينگ تدريجي رشته بيت ها و ارزيابي درختها از زيرباندهاي فركانسي كمتر به زيرباندهاي فركانسي بيشتر در هر رشته بيت ميتوان به كدينگ جاسازي دست يافت.

الگوريتم EZW بر پايه 4 اصل استوار است [3]

1- جدا كردن سلسله مراتبي زيرباندها با استفاده از تبديل ويولت گسسته

1-1-2) تبديل ويولت گسسته

تبديل ويولت سلسله مراتبي كه در EZW و SPIHT مورد استفاده قرار مي گيرد نظير يك سيستم تجزيه زيرباند سلسله مراتبي است كه در آن فاصله زيرباندها در مبناي فركانس بصورت لگاريتمي است.

در شكل 2-2 يك مثال از تجزيه دو سطحي ويولت روي يك تصوير دو بعدي نشان داده شده است. تصوير ابتدا با بكارگيري فيلترهاي افقي و عمودي به چهار زيرباند تجزيه مي‌شود. در تصوير (c ) 2-2 هر ضريب مربوط به ناحيه تقريبي 2×2 پيكسل در تصوير ورودي است. پس از اولين مرحله تجزيه سه زير باند LH1 , HL1 و HH1 بعنوان زيرباندهاي فركانس بالايي در نظر گرفته مي شوند كه به ترتيب داراي سه موقعيت عمودي، افقي و قطري مي باشند اگر Wv , Wh به ترتيب فركانسهاي افقي و عمودي باشند، پهناي باند فركانسي براي هر زير باند در اولين سطح تجزيه ويولت در جدول
1-2 آمده است[4]

جدول 2-1 ) پهناي باند فركانسي مربوط به هر زير باند پس از اولين مرحله تجزيه ويولت با استفاده از فيلترهاي مشابه (پايين گذر و بالاگذر) زير باند LL1 پس از اولين مرحله تجزيه ويولت، مجدداً تجزيه شده و ضرايب ويولت جديدي به دست مي آيد جدول 2-2) پهناي باند مربوط به اين ضرايب را نشان مي دهد.

2-1-2) تبديل ويولت بعنوان يك تبديل خطي

ميتوان تبديل بالا را يك تبديل خطي در نظر گرفت [5]. P يك بردار ستوني كه درايه هايش نشان دهنده يك اسكن از پيكسلهاي تصوير هستند. C يك بردار ستوني شامل ضرايب ويولت به دست آمده است از بكارگيري تبديل ويولت گسسته روي بردار p است. اگر تبديل ويولت بعنوان ماتريس W در نظر گرفته شوند كه سطرهايش توابع پايه تبديل هستند ميتوان تبديل خطي زير را در نظر گرفت.

فرمول

بردار p را ميتوان با تبديل ويولت معكوس به دست آورد.

فرمول

اگر تبديل W متعامد باشد. است و بنابراين

فرمول

در واقع تبديل ويولت W نه تنها متعامد بلكه دو متعامدي مي باشد.

3-1-2) يك مثال از تبديل ويولت سلسله مراتبي

يك مثال از تبديل ويولت سلسله مراتبي در اين بخش شرح داده شده است. تصوير اوليه 16*16 و مقادير پيكسلهاي مربوط به آن به ترتيب در شكل 3-2 و جدول 3-2 آمده است.

يك ويولت چهارلايه روي تصوير اوليه اعمال شده است. فيتلر مورد استفاده فيلتر دو متعامدي Daubechies 9/7 است [6]. جدول 4-2 ضرايب تبديل گرد شده به اعداد صحيح را نشان مي دهد. قابل توجه است كه ضرايب با دامنه بيشتر در زيرباندهاي با فركانس كمتر قرار گرفته اند و بسياري از ضرايب دامنه هاي كوچكي دارند ويژگي فشرده سازي انرژي در تبديل ويولت در اين مثال به خوبي ديده مي شود جدول 5-2 تصوير تبديل يافته و كمي شده را نشان مي دهد چنانكه كمي سازي تنها براي اولين سطح ويولت انجام گرفته است يك ضريب مقياس 25/0 در هر ضريب فيلتر ويولت ضرب شده و سپس مجموعه فيلتر پاين گذر و بالاگذر روي تصوير اوليه بكار گرفته مي شود اندازه گام كمي سازي مربوطه در اين حالت 16 است.

پس از كمي سازي بيشتر ضرايب در بالاترين زير باند فركانسي صفر مي شوند تصويربازسازي شده و تبديل ويولت معكوس در شكل (b) 7-2 و جدول 6-2 آمده است. به علت كمي سازي بازسازي با اتلاف است.





1- ضرايب با دامنه بزرگتر زدوتر ارسال مي شوند.

2- بيتهاي پرارزش تر ضريب حاوي اطلاعات كمتري هستند و زودتر ارسال ميشوند.

ميتوان نشان داد كه چگونه اينكدر SPIHT از اين اصلها براي انتقال تدريجي ضرايب ويولت به ديكدر استفاده مي كند فرض مي شود تبديل ويولت به تصوير اعمال شده و ضرايب Ci,j در حافظه ذخيره شده اند. اين ضرايب بدون در نظر گرفتن علامتشان مرتب شده و اطلاعات مرتب شده در آرايه m قرار گرفته اند و عضو m(k) از اين آرايه شامل مختصات (i,j) مربوط به آرايه Ci,j است و بنابراين براي همه مقادير k داريم

فرمول

جدول 58-5 مقادير فرضي 16 ضريب را نشان مي دهد كه هر كدام بعنوان يك عدد 16 بيتي نشان داده شده است. پرارزشترين بيت،‌بيت علامت است و 15 بيت باقيمانده مربوط به مقدار عدد هستند. اولين ضريب است كه برابر با S1aci…r است. ضريب دوم نيز برابر با است و به همين ترتيب

اطلاعات مرتب شده اي كه اينكدر بايد بفرستد دنباله m(k) است كه به ترتيب زير است:

علاوه بر آن بايد 16 علامت و 16 ضريب را به ترتيب ارزش بفرستد. يك انتقال مستقيم شامل ارسال 16 عدد است. اين روش يك روش wastfull است. در الگوريتم SPIHT ، اينكدر وارد يك حلقه مي شود كه در هر تكرار حلقه دو گام انجام مي شود: گام مرتب سازي و گام اصلاح.

در اولين تكرار اينكدر عدد 2= L يعني تعدد ضرايبي را كه در فاصله

فرمول

قرار دارند مي فرستد در ادامه دو جفت مختصات ( 3و 2 ) و (4 و 3) و علامت دو ضريب اول فرستاده مي شود. اين عمليات در نخستين مرحله مرتب سازي انجام مي شود. اين اطلاعات ديكدر را قادر به تخمين زدن ضرايب به ترتيبي كه در ادامه آمده است مي كند:

ضرايب و بعنوان يك عدد 16 بيتي بصورت و 14 ضريب باقيمانده صفر بازسازي مي شوند. اين نشان مي دهد كه چگونه پرارزش ترين بيتهاي مربوط به بزرگترين ضرايب ابتدا به ديكدر فرستاده مي شوند. گام بعدي مرحله اصلاح مي باشد كه در تكرار اول انجام نمي شود.

در تكرار دوم (حلقه دوم) اينكدر هر دو گام را انجام مي دهد. در مرحله مرتب سازي عدد 4= L بعنوان تعداد ضرايبي كه در فاصله

فرمول

قرار دارند در ادامة آن چهار مختصات ( 2و 3) ، (4 و 4) ، (2 و 1) و (1 و3) و علامت چهار ضريب فرستاده مي شود. در گام اصلاح دو بيت b , a بعنوان چهاردهمين بيت با ارزش ضرايب مربوطه به حلقه قبلي فرستاده مي شود.

اطلاعات به دست آمده ديكدر را قادر به اصلاح ضرايب تقريبي كه از مرحله قبل بدست آمده اند مي كند و شش ضريب اول به شكل زير در مي آيد:

فرمول

و ده ضريب باقيمانده تغييري نمي كند.

2-2-2) دسته بندي ضرايب در الگوريتم SPIHT

به منظور كاهش تعداد تصميم گيري ها در مقايسه ميان بيتها و نيز كاهش حجم داده هاي خروجي در الگوريتم SPIHT از ساختار سلسله مراتبي استفاده مي شود. در اينجا هدف اصلي دسته بندي ضرايب در مجموعه ها به گونه اي است كه تعداد عضوهاي يك مجموعه بي معني حداكثر باشد و هر مجموعه معني دار تنها يك عضو را شامل شود.