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

1-2) EZW
الگوریتم EZW در سال 1993 توسط shapiro ابداع شد نام کامل این واژه 1 به معنای کدینگ تدریجی با استفاده از درخت ضرایب ویولت است. این الگوریتم ضرایب ویولت را به عنوان مجموعه ای از درختهای جهت یابی مکانی در نظر می گیرد هر درخت شامل ضرایبی از تمام زیرباندهای فرکانسی و مکانی است که به یک ناحیه مشخص از تصویر اختصاص دارند. الگوریتم ابتدا ضرایب ویولت با دامنه بزرگتر را کددهی می کند در صورتیکه دامنه یک ضریب بزرگتر یا مساوی آستانه مشخص باشد ضریب به عنوان ضریب معنی دار 2 در نظر گرفته می شود و در غیر اینصورت بی معنی3 می باشد یک درخت نیز در صورتی معنی دار است که بزرگترین ضریب آن از نظر دامنه بزرگتر یا مساوی با آستانه مورد نظر باشد و در غیراینصورت درخت بی معنی است.
مقدار آستانه در هر مرحله از الگوریتم نصف می شود و بدین ترتیب ضرایب بزرگتر زودتر فرستاده می شوند در هر مرحله، ابتدا معنی دار بودن ضرایب مربوط به زیر باند فرکانسی پایین تر ارزیابی می شود اگر مجموعه بی معنی باشد یک علامت درخت صفر استفاده می شود تا نشان دهد که تمامی ضرایب مجموعه صفر می باشند در غیراینصورت مجموعه به چهارزیرمجموعه برای ارزیابی بیشتر شکسته می شود و پس از اینکه تمامی مجموعه ها و ضرایب مورد ارزیابی قرار گرفته اند این مرحله به پایان می رسد کدینگ EZW براساس این فرضیه استوار است که چگالی طیف توان در اکثر تصاویر طبیعی به سرعت کاهش می یابد بدین معنی که اگر یک ضریب در زیر باند فرکانسی پایین تر کوچک باشد به احتمال زیاد ضرایب مربوط به فرزندان آن در زیر باندهای بالاتر نیز کوچک هستند به بیان دیگر اگر یک ضریب والد بی معنی باشد به احتمال زیاد فرزندان آن نیز بی معنی هستند اگر آستانه ها توانهایی از دو باشند میتوان کدینگ EZW را به عنوان یک کدینگ bit-plane در نظر گرفت در این روش در یک زمان، یک رشته بیت که از MSB شروع می شود کددهی می شود با کدینگ تدریجی رشته بیت ها و ارزیابی درختها از زیرباندهای فرکانسی کمتر به زیرباندهای فرکانسی بیشتر در هر رشته بیت میتوان به کدینگ جاسازی 4 دست یافت.
الگوریتم 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 متعامد 5 باشد. است و بنابراین
فرمول
در واقع تبدیل ویولت W نه تنها متعامد بلکه دو متعامدی 6 می باشد.
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 آمده است. به علت کمی سازی بازسازی با اتلاف است.
4-1-2) انتقال تدریجی تصویر [1]
اگر یک تبدیل متعامد و سلسله مراتبی زیر باند، p یک ماتریس از اسکن پیکسلهای pi,j که (i, j) مختصات پیسک است و c ماتریس مربوط به ضرایب تبدیل یافته باشد، آنگاه:
فرمول
c ماتریسی است که باید کد شود.
در یک کدینگ کامل EZW ، ؟؟ ماتریس بازسازی C اولیه را برابر صفر قرار می دهد و با دریافت هر بیت آنرا تغییر می دهد.
فرمول
هدف اصلی در انتقال تدریجی این است که ابتدا، اطلاعات مهمتر تصویر فرستاده شود. ارسال درست این اطلاعات خطا را تا میزان زیادی کاهش می دهد. بنابراین نکته مهم، انتخاب اطلاعات مهمتر در C است. معیار متوسط مربعات خطا بعنوان یک معیار سنجش خطا مورد استفاده قرار می گیرد.
فرمول
که N تعداد پیکسلهای تصویر اولیه است. با توجه به اینکه Euclidean norm در تبدیل متعامد حفظ می شود میتوان گفت
فرمول
معادله نشان می دهد که با دریافت ضریب انتقال Ci,j در دیکدر ، DMSE به اندازه
فرمول
کاهش می یابد. واضح است با ارسال ضرایب بزرگتر در ابتدا، خطای تصویربازسازی شود. کاهش بیشتر خواهد داشت.
علاوه بر آن اگر Ci,j بصورت باینری باشد اطلاعات را میتوان بصورت تدریجی ارسال نمود. به بیان دیگر MSB که مهمترین بیت است در ابتدا و LSB که کم اهمیت ترین بیت است در آخر فرستاده می شود.
5-1-2) درخت جهت یابی مکانی
ایجاد و تقسیم بندی مجموعه ها با استفاده از ساختار ویژه ای به نام درخت جهت یابی مکانی انجام می شود این ساختار بگونه ای است که از ارتباط مکانی میان ضرایب ویولت در سطوح مختلف هرم زیرباندها 7 استفاده می کند.
درختهای جهت یابی مکانی در شکل 59-5 برای یک تصویر 16*16 نشان داده شده است. زیرباند LL2 مجدداً به چهار گروه که هر یک شامل 2×2 ضریب است تقسیم می شود در هر گروه هر یک از چهار ضریب (شکل دو سطح پایین گذر و بالاگذر دارد و هر سطح به چهار زیر باند تقسیم می شود).
به غیر از ضریبی که در سمت چپ و بالا قرار گرفته و با رنگ خاکستری مشخص شده است ریشه یک درخت جهت یابی مکانی است پیکانها نشان می دهند که چگونه سطوح مختلف این درختها به هم مربوطند به طور کلی یک ضریب در موقعیت (i,j) در تصویر والد چهار ضریب در موقعیتهای (2i,2y) ، (2i+1,2y) ، (2i,2y+1) و (2i+1 , 2y+1) است ریشه های درختهای جهت یابی مکانی مربوط به این مثال در زیر باند LL2 قرار گرفته اند هر ضریب ویولت به غیر از آنهایی که با رنگ خاکستری مشخص شده اند و برگها میتواند ریشه برخی زیر درختهای جهت یابی مکانی باشند.
در این مثال اندازه زیر باند LL2 برابر 4×4 است و بنابراین به چهار گروه 2×2 تقسیم شده است. تعداد درختها در این مثال 12 تا است که برابر 4 /3 اندازه بالاترین زیر باند LL است.
هر کدام از 12 ریشه در زیر باند LL2 والد چهار فرزند استا که در سطح مشابهی قرار گرفته اند. فرزندان این فرزندان در سطح یک قرار می گیرند. عموماً ریشه های درختها در بالاترین سطوح، فرزندان آنها در سطحی مشابه از آن پس فرزندان ضرایبی که در سطح k قرار دارند در سطح k-1 قرار می گیرند.
بطور کلی میتوان گفت پس از تبدیل ویولت یک تصویر را میتوان با ساختار درختی آن نشان داد که در آن یک ضریب در زیر باند پایین میتواند چهار فرزند در زیر باند بالاتر داشته باشد و هر یک از این چهار فرزند میتوانند چهار فرزند دیگر در زیرباندهای بالاتر داشته باشند. به ساختاری که در این حالت پدید می آید.
درخت چهارتایی8 گفته می شود که هر ریشه 9 چهارگره10 دارد. نکته بسیار مهم نوع شماره گذاری موقعیت مکانی خانه ها (ضرایب) است. ضریبی که در پایین ترین سطح و در گوشه بالا در سمت چپ قرار داد دارای موقعیت مکانی (0 و 0 ) خواهد بود و به همین ترتیب ضرایب بعدی اضافه می شوند. اگر این موقعیت گذاری رعایت نشود جواب درستی به دست نمی آید [7].
6-1-2) درخت صفر
همانگونه که قبلاً اشاره شد میان زیرباندهای مجاوری که در موقعیت مکانی مشابه قرار گرفته اند نوعی وابستگی داخلی وجود دارد این بدان معناست که اگر ضریب مربوط به یک والد در تک آستانه مشخص بی معنی باشد به احتمال زیاد ضرایب مربوط به فرزندان نیز در مقایسه با استانه جاری بی معنی خواهد بود و این امر تایید کننده نزولی بودن چگالی طیف توان در تصاویر طبیعی می باشد در الگوریتم EZW و الگوریتمهای مشابه این رابطه والد و فرزندی برای bitplane مربوط به باارزشترین بیت bit plante (MSB) مربوط به کم ارزشترین بیت (LSB) بکار برده می شود.
معنی دار بودن ضرایب با توجه به آستانه داده شده تعیین می گردد و آستانه در هر مرحله نصف می شود. ضرایب در هر مرحله با آستانه مقایسه می شود و با توجه به این مقایسه در bitplane مربوطه مقدار o یا 1 به آنها اختصاص داده می شود.
یک درخت صفر درختی است متشکل از ضرایبی که همگی در مقایسه با آستانه جاری بی معنی هستند در اکثر موارد درختهای صفر زیادی در یک bit plane وجود دارد. استفاده از نمایش درخت صفر برای یک ریشه به معنای بی معنی بودن تمام فرزندان آن در مقایسه با آستانه فعلی می باشد و این امر به فشرده سازی کمک شایانی می کند.
7-1-2) کدگذاری در الگوریتم EZW
در این الگوریتم دو لیست با نامهای DL 11 و SL مورد استفاده قرار می گیرند. لیست DL شامل مختصات ضرایبی است که معنی دار نیستند. لیست SL شامل بزرگی (نه مختصات) ضرایبی است که معنی دار می باشند هر دوره انجام الگوریتم شامل یک گذار اصلی12 می باشد که در ادامه آن یک گذار فرعی 13 می آید. گامهای اصلی الگوریتم به ترتیب زیر است:
1- مقداردهی اولیه
الف) مختصات تمامی ضرایب ویولت در لیست DL قرار می گیرد.
ب ) تنظیم آستانه اولیه :
فرمول
که Ci,y ضریب ویولت می باشند.
2- گذار اصلی
تمامی ضرایب در یک مسیر از پیش تعیین شده اسکن می شوند این مسیر طبق چند الگو تعریف می شود. انتخاب مناسب هر یک از این الگوها می تواند نقش مهمی در افزایش کارایی الگوریتم داشته باشد. شکل با مقایسه هر یک از ضرایب لیست DL با آستانه جاری T یکی از چهار علامت زیر بعنوان علامت مشخصه ضریب در نظر گرفته می شود.
الف) در صورتیکه ضریب در مقایسه با آستانه جاری T معنی دار مثبت باشد علامت PS 14 بعنوان خروجی در نظر گرفته می شود. هنگامیکه این علامت ورودی دیکدر قرار گیرد ضریب را برابر T5/1 قرار می دهد.
ب) در صورتیکه ضریب در مقایسه با آستانه جاری T معنی دار و منفی باشد علامت NS 15 بعنوان خروجی در نظر گرفته می شود. هنگامیکه این علامت ورودی دیکدر قرار گیرد ضریب را برابر T5/1- قرار می دهد.
ج) در صورتیکه یک ضریب در مقایسه با آستانه جاری معنی دار نباشد ولی بعضی از فرزندان آن معنی دار باشند علامت IZ 16 (صفر منفرد) بعنوان خروجی در نظر گرفته می شود.
د) در صورتیکه یک ضریب و تمام فرزندان آن در مقایسه با آستانه جاری بی معنی باشند علامت ZTR 17 (درخت صفر) بعنوان خروجی در نظر گرفته می شود. نکته مهم این است که لازم نیست نسلهای این درخت صفر در تکرار جاری کدگذاری شوند. هنگامیکه این علامت ورودی دیکدر قرار می گیرد، به ضریب و تمامی ضرایب مربوطه به نسلهای آن مقدار صرف نسبت می دهد. مقدار این ضرایب در تکرارهای متوالی اصلاح میشود.
ضرایبی که با علامت PS و NS مشخص شده اند در لیست SL قرار گرفته و مقادیر آنها bitplane مربوطه صفر می شود فلوچارت مربوطه به دسته بندی ضرایب در شکل
آمده است.
3- گذار فرعی
این مرحله یک مرحله اصلاح می باشد. در این مرحله هر ضریب معنی دار، با ارسال یک بیت بیشتر از نمایش باینری اش اصلاح می شود. هنگامیکه دیکدر این بیت را دریافت می کند با توجه به صفر یا یک بودن بیت مقدار T25/0 را به مقدار معنی ضریب اضافه می کند.
4- کوانینزاسیون
مقدار آستانه نصف شده (T=T/2) و اگر تکرار بیشتری مورد نیاز باشد به گام 2 بر می گردد.
8-1-2) تحلیل و بررسی الگوریتم EZW
همانگونه که قبلا اشاره شد در مرحله گذار اصلی هنگامیکه یک ضریب با توجه به آستانه جاری بعنوان یک ضریب معنی دار شناخته می شود ضریب به لیست SL اضافه شده و دیگر در مرحله گذار اصلی بعدی مورد ارزیابی قرار نمی گیرد. در صورتیکه باشد، ضریب ویولت بعنوان ضریب بی معنی در نظر گرفته می شود. ساختار داده درخت صفر براساس نتایج عملی شناخته شده ای است که در ادامه است: اگر ضریب ویولت قرار گرفته در یک مقیاس کلی 18 بالای هرم مربوط به تصویر با توجه به آستانه T بی معنی باشد، آنگاه به احتمال زیاد تمام ضرایبی که در مقیاسهای جزئی تر 19 در همان جهت و در موقعیت مکانی مشابه قرار گرفته اند. با توجه به آستانه ‏T بی معنی خواهند بود. در هر تکرار، تمامی ضرایب به ترتیبی که در شکل نشان داده شده است. اسکن می شوند. بدین ترتیب هنگامیکه یک گره مورد بررسی قرار می گیرد، تمامی والدین آن مورد بررسی و اسکن قرار گرفته اند. اسکن از پایین ترین زیر باند فرکانسی LLn آغاز می شود و در زیرباندهای HHn , LHn , HLn ادامه می یابد و سپس به سطح n-1 تنزل کرده و زیرباندهای و و را اسکن می کند. قبل از آنکه الگوریتم به زیرباند بعدی برود هر زیر باند بطور کامل اسکن می شود. ضرایب موجود در پایین ترین سطح هرم هیچ فرزندی ندارند و بنابراین نمی توانند ریشه های درخت باشند[1].
جدول 8-2 توزیع ضرایب ویولت آستانه گذاری شده مربوط به تصویر Lena با پنج سطح تجزیه را نشان می دهد. در این جدول دو نکته قابل توجه مشاهده می شود.
1- اکثر ضرایبی که در زیرباندهای فرکانسی پایین تر هستند. دامنه بزرگتری دارند و ضرایبی که در زیرباندهای فرکانسی بالاتر هستند، دامنه کوچکتری دارند. تعداد زیادی از ضرایب با دامنه صفر در بالاترین زیرباندهای فرکانسی قرار گرفته اند. از نقطه نظر bitplane ها وقتی آستانه ها بصورت توالی از دو هستند. بیتهایی که در bitplane های بالاتر هستند اکثراً در زیرباندهای فرکانسی پایین کد می شوند و بیتهایی که در bitplane های پایین تر هستند اکثراً در زیرباندهای فرکانسی پایین تر کد می شوند.
2- تعداد ضرایبی که در مقایسه با آستانه های بیشتر معنی دار هستند کمتر از ضرایبی است که در مقایسه با آستانه های کمتر معنی دار هستند با توجه به جدول 8-2 دیده می شود که تعداد ضرایب معنی دار در مقایسه با آستانه 11 2 ، دوتاست. درصورتیکه در مقایسه با آستانه تعداد ضرایب معنی دار 12791 تاست[2].
9-1-2- مثال [1] و [3]
در این بخش با یک مثال ساده عملکرد الگوریتم EZW به خوبی نشان داده شده است. شکل 5-65a سه سطح تبدیل ویولت مربوط به یک تصویر 8×8 را نشان می دهد. بزرگترین ضریب 63 است. بنابراین آستانه اولیه در محدوده [ 64 و 31 ) قرار می گیرد. آستانه اولیه در نظر گرفته می شود. جدول 5-65b نتایج مربوط به اولین مرحله اصلی را نشان می دهد.
نکات زیر در این جدول قابل توجه است.
1- ضریب 63 دامنه ای بزرگتر از آستانه دارد و مثبت است، بنابراین علامت PS توسط اینکدر برای آن در نظر گرفته می شود. سپس این ضریب به صفر تبدیل می گردد. پس از دریافت این علامت در دیکدر مقدار 48 که نقطه میانی بازه (64 و 32] است به این ضریب تخصیص داده می شود.
2- ضریب 31 با در نظرگرفتن آستانه 32 بی معنی می باشد ولی مقدار یکی از فرزندان آن در دو نسل پایین تر در زیر باند LH1 47 است که از آستانه جاری بزرگتر است. از این رو ضریب 31 بعنوان یک صفر منحصر به فرد (IZ) در نظر گرفته می شود.
3- ضریب 23 از آستانه جاری کوچکتر بوده و تمامی فرزندان آن ( 3، 12- ، 14- و 8) در زیر باند HH2 و نیز در زیر باند HH1 بی معنی هستند. بنابراین ضریب 23 ریشه یک درخت صفر (ZTR) می باشد. با توجه به این موضوع هیچ علامتی برای فرزندان آن در مرحله اصلی در نظر گرفته نمی شود و هیچکدام از این ضرایب در جدول 5-65b دیده نمیشود.
4- ضریب 10 و تمامی فرزندان آن (12- ، 7 ، 6 و 1- ) در زیر باند HL1 از آستانه جاری کوچکترند و بنابراین 10 بعنوان یک ریشه درخت صفر (ZTR) در نظر گرفته می شود. ضریب 12- از نظر قدرمطلق از 10 بزرگتر ولی از آستانه جاری کوچکتر است.
5- ضریب 14 با توجه به آستانه جاری بی معنی است. فرزندان این ضریب 1- و 47 و 3- و 2 می باشند و بنابراین یکی از فرزندان آن (47) در مقایسه با آستانه جاری معنی دار است. در نتیجه این ضریب بعنوان یک صفر منفرد (IZ) در نظر گرفته می شود.
6- ضریب 47 در زیر باند LH1 با توجه به آستانه جاری معنی دار و مثبت است. بنابراین علامت PS برای آن در نظر گرفته می شود و مقدار صفر به جای این ضریب منظور می گردد. در گذار اصلی بعدی که آستانه نصف (16) می شود والدین ضریب یعنی ضریب 14 بعنوان یک درخت صفر در نظر گرفته می شود.
در طول اولین گذار اصلی با توجه به آستانه 32 ، چهار ضریب بعنوان ضرایب معنی دار مشخص شدند. دیکدر با دریافت علائم مربوط به این چهار ضریب می داند که این ضرایب در فاصله ( 64 و 32] قرار گرفته اند. در اولین گذار فرعی این ضرایب اصلاح می شوند در این گذار اگر دیکدر به ازای هر یک از ضرایب صفر دریافت کند آن ضریب را در فاصله (48 و 32 ] و اگر یک دریافت کند آن ضریب را در فاصله (64 و 48 ] قرار می دهد. اینکدر در مرحله اصلاح به ترتیب بیتهای "1010 " را برای ضرایب 63 ، 34 ، 49 و 47 ارسال می کند و بنابراین دیکدر این ضرایب را به ترتیب با مقادیر 56 ، 40 ، 56 و 40 جایگزین می کند.
در مرحله اصلی دوم فقط ضرایبی که در مرحله قبلی بعنوان ضرایب معنی دار در نظر گرفته نشده بودند اسکن و تست می شوند. ضرایبی که در مرحله قبل بعنوان ضرایب معنی دار شناخته شده اند با صفر جایگزین گشته و برای تعیین درخت صفر مورد استفاده قرار می گیرند. در گذار اصلی دوم ضریب 31- در زیر باند LH3 بعنوان ضریب معنی دار منفی، ضریب 23 در زیرباند کددهی می شوند. در این قسمت گذار اصلی دوم به پایان می رسد.
در این مرحله نوبت به گذار فرعی دوم می رسد. لیست SL اکنون S به ترتیب شامل ضرایب 63، 49 ، 34 ، 47 ، 31 و 23 است که در این مرحله در دیکدر با مقادیر 60 ، 52 ، 44 ، 36 ، 28 و 20 بازسازی می شوند.
-A فرض کنید آستانه اولیه باشد. هنگامیکه ضریب در تکرار اول وارد شود معنی دار در نظر گرفته شده و از آنجا که مثبت است بعنوان PS کدگذاری می شود. وقتی دیکدر این علامت را بعنوان ورودی دریافت کند می فهمد که ضریب در مقایسه با استانه جاری معنی دار مثبت است و بنابراین و از طرفی . بنابراین بهترین مقداری که میتواند برای ضریب در نظر بگیرد است. از آن پس ضریب صفر میشود و بنابراین در تکرار بعدی بعنوان ضریب معنی دارتعریف نمی شود. میتوان آستانه T را بعنوان یک اشاره گر 20 در نظر گرفت که موقعیت یک بیت را مشخص می کند. در هر تکرار این آستانه بر 2 تقسیم شده و به موقعیت بیت بعدی با ارزش کمتر اشاره می کند و بدین ترتیب بیتهای با ارزش کمتر شناخته می شوند. در طول گذار فرعی لیست فرعی SL اسکن شده و اینکدر خروجی صفر یا یک را برای هر ضریب در نظر می گیرد. اگر باشد در این مرحله اینکدر عدد یک را می فرستد که به دیکدر نشان می دهد که مقدار واقعی ضریب از 48 بیشتر است. با دریافت عدد یک ارسال شده دیکدر مقدار ضریب را از 48 به تغییر می دهد. اگر مقدار صفر توسط اینکدر ارسال شود. دیکدر مقدار ضریب را به تغییر می دهد.
رشته بیتی که توسط اینکدر در یک گذار فرعی تولید می شود با استفاده از کدگذاری ریاضی تطبیقی بصورت منظم کدگذاری می شوند اینکدر حلقه را هنگامیکه به موقعیت خاصی رسید متوقف می کند چرا که کاربرد ممکن است خواستار نرخ بیت مشخصی باشد. در اینصورت کار اینکدر در زمان رسیدن به این نرخ بیت مشخص پایان می یابد. کاربر می تواند با تعیین حداکثر خطای قابل قبول (اختلاف بین تصویر اصلی و تصویربازسازی شده) نیز خواستاراتمام کار توسط اینکدر و دیکدر باشد[1].
SPIHT
در سال 1966 pearlman و Said الگوریتم جدیدی را در زمینه فشرده سازی سیگنال و تصویر ارائه دادند [4].
این الگوریتم که SPIHT 21 نام گرفت در واقع حالت پیشرفته و توسعه یافته الگوریتم EZW است از میان الگوریتمهای فشرده سازی مبتنی بر ویولت، از جایگاه خوبی برخوردار است.
الگوریتم SPIHT برای انتقال پیوسته و بهینه مطلوب طراحی شده است. یکی از بهترین مشخصه های این الگوریتم و شاید مشخصه منحر به فرد آن این است که کیفیت تصویری که نمایش داده می شود بهترین کیفیتی است که می تواند با استفاده از بیتهای کدگذاری شده تا آن لحظه به دست آید. مشخصه اصلی دیگر این الگوریتم استفاده از کدینگ گسترده22 است این مشخصه بصورت زیر بیان می شود:
اگر اینکدر دو فایل یکی به بزرگی M و دیگری به بزرگی m تولید کند که m از M کوچکتر باشد فایل کوچکتر با m بیت اول فایل بزرگتر برابراست. این موضوع با یک مثال به خوبی قابل بیان است. اگر فرض شود سه کاربر منتظر فرستاده شدن یک تصویر فشرده شده مشخص یا کیفیتهای مختلف هستند که اولی به کیفیتی در یک فایل 10 کیلوبایتی ، دومی 20 کیلوبایتی و سومی 50 کیلوبایتی نیاز دارد اکثر روشهای با اتلاف فشرده سازی برای چنین هدفی تصویر را با کیفیتهای مختلف و سه بار فشرده می کنند اما در روش SPIHT یک فایل تولید شده و سه بخش با طولهای 10 کیلوبایت ، 20 کیلوبایت و 50 کیلوبایت به کاربر فرستاده می شود.
الگوریتم SPIHT از روش انتقال تدریجی تصویر استفاده می کند که در بخش 4-1-2 مورد بررسی قرار گرفت. هدف اصلی در انتقال تدریجی این است که ابتدا اطلاعات خیلی مهم تصویر فرستاده می شود. این اطلاعات از کاهش زیاد خطا 23 تفاوت بین تصویر اصلی و تصویربازسازی شده به دست می آید. SPIHT از معیار متوسط مربعات خطا استفاده می کند همانگونه که در بخش اشاره شد هر چه ضریب Ci,j بزرگتر باشد شامل اطلاعاتی است که خطا را کاهش می دهد. بنابراین یک اینکدر پیشرفته بهتر است ابتدا ضرایب بزرگتر را بفرستد. میتوان گفت در الگوریتم SPIHT دو اصل مهم وجود دارد:
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 ، اینکدر وارد یک حلقه می شود که در هر تکرار حلقه دو گام انجام می شود: گام مرتب سازی24 و گام اصلاح.
در اولین تکرار اینکدر عدد 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 از ساختار سلسله مراتبی استفاده می شود. در اینجا هدف اصلی دسته بندی ضرایب در مجموعه ها به گونه ای است که تعداد عضوهای یک مجموعه بی معنی حداکثر باشد و هر مجموعه معنی دار تنها یک عضو را شامل شود.
رابطه والد – فرزندی در درختهای جهت یابی مکانی در شکل 5-2 آمده است. یکی از تفاوتهای این الگوریتم با الگوریتم EZW در این است که چهار ضریب کنار هم بصورت همزمان پردازش می شوند. تفاوت دیگر در این است که در SPIHT هر ضریب به جز ضریبی که با علامت * مشخص شده و در زیر باند LL قرار گرفته و ضرایبی که در بالاترین زیرباندها قرار گرفته اند دارای چهار فرزند است.
مجموعه مختصاتهایی که در ادامه آمده اند برای نشان دادن نحوه عملکرد الگوریتم SPIHT مورد استفاده قرار می گیرند. موقعیت یک ضریب با (i,j) نشان داده می شود که i نشان دهنده شماره صطور j نشان دهنده شماره ستون است.
H(i,j) : مجموعه مختصات ریشه های تمام درختهای جهت یابی مکانی (4/ 3 از ضرایب ویولت در بالاترین زیرباند LL )
O(i,j) : مجموعه ای از مختصات چهارفرزند مستقیم گره (i,j) اگر (i,j) مختصات مربوط به برگ یک درخت جهت یابی مکانی باشد، O(i,j) تهی است.
D(i,j) : مجموعه مختصات نسلهای گره (I,j) یعنی مجموعه مختصات فرزندان مستقیم و غیر مستقیم آن.
L(i,j) : شامل مجموعه مختصات فرزندان غیرمستقیم گره (i,j) یعنی D(i,j) – O(i,j)
فرزندان مستقیم به چهار فرزند یک گره و فرزندان غیر مستقیم به فرزندان یک گره و نسلهای آن گره اطلاق می شود شکل 6-2 نشان دهنده مجموعه های حاصل از تقسیم بندی درخت جهت یابی مکانی در الگوریتم SPIHT را نشان می دهد.
تابعی که تعیین کننده معنی دار بودن یا بی معنی بودن مجموعه هاست. است که از رابطه زیر به دست می آید:
فرمول
یک بیت منفرد است که به دیکدر فرستاده می شود و از آنجا که نتیجه هر تست یک بیت منفرد است که در یک رشته فشرده نوشته می شود، بهتر است تعداد تستها کم شود. برای رسیدن به چنین هدفی مجموعه ها باید بگونه ای ایجاد شوند که مجموعه های بی معنی شامل چندین عضو و مجموعه های معنی دار تنها شامل یک عضو باشند.
فرمول
3-2-2) کدگذاری در الگوریتم SPIHT
مهمترین نکته در اجرای الگوریتم SPIHT در این است که تستهایی که برای معنی دار بودن مجموعه ها انجام می شود در اینکدر و دیکدر مشابه باشد. در الگوریتم SPIHT از سه لیست منظم شده استفاده می شود.
LSP : لیست پیکسلهای معنی دار (ضرایب منفردی با دامنه بزرگتر از آستانه)
LIP : لیست پیکسلهای بی معنی (ضرایب منفردی با دامنه کوچکتر از آستانه)
LIS : لیست مجموعه هایی که تمامی اعضای آنها بی معنی هستند.
هر عضو این مجموعه ها با مختصات (i,j) تعریف می شود که نشان دهنده یک ضریب منفرد در LIP و LSP و یک مجموعه ضرایب در LIS است. مجموعه ضرایب در LIS یا D(i,j) است یا L (i,j) که به ترتیب با نوع A و نوع B مشخص می شود. الگوریتم از چهار گام تشکیل شده است:
گام اول : پیدا کردن آستانه حداکثر در مقیاس Log2 و مقدار دهی اولیه LIP و LIS با مختصات ضرایبی است که در مجموعه H قرار گرفته اند. قابل توجه است که هر عضو LIP به یک ضریب منفرد اشاره دارد. در حالیکه هر عضو LIS شامل یک مجموعه D(i,j) (نوع A ) می باشد.
در گام دوم، در مرحله مرتب سازی ضرایب موجود در LIP که قبلاً جزء اعضای بی معنی طبقه بندی شده بودند دوباره ارزیابی می شوند و آنهایی که معنی دار هستند به LSP منتقل میشوند مجموعه های موجود در LIS نیز به همین ترتیب مورد ارزیابی قرار می گیرند. اگر مجموعه ای معنی دار باشد به زیر مجموعه هایی تفکیک می شود این زیر مجموعه ها اگر بیش از یک عضو داشته باشند به انتهای LIS منتقل می شود و در صورتیکه تنها یک عضو داشته باشد و آن عضو معنی دار باشد به انتهای LSP و در صورتیکه عضو بی عنی باشد به انتهای LIP منتقل می شود.
در گام سوم یعنی مرحله اصلاح ضرایب که مختصات آنها در LSP است با آستانه جاری ارزیابی می شوند.
در گام چهارم آستانه بصورت توالی از دو کاهش می باد و گامهای دوم و سوم تکرار می شود.
جزئیات الگوریتم SPIHT در ادامه آمده است.
1- مقدار دهی اولیه
الف ) مقدار اولیه n برابر با
فرمول
قرار داده می شود.
ب ) مجموعه LSP تهی در نظر گرفته می شود مجموعه قرار می گیرد و مجموعه LIS مقدار که اعضای LIS در گروه A طبقه بندی می شوند.
2) مرحله مرتب سازی
الف) برای ارزیابی هر یک از عضای LIP یعنی خروجی طبق رابطه
ایجاد می شود. اگر یک باشد (I,j) به مجموعه LSP منتقل شده و خروجی بعدی علامت خواهد بود.
ب) برای هر یک از اعضای LIS یعنی
اگر (i,j) از گروه A و باشد برای هر
فرمول
هستند خروجی محاسبه شده و در صورتیکه این خروجی 1 باشد (k,l) به مجموعه LSP انتقال می یابد و علامت ضریب خروجی بعدی را تشکیل می دهد و سپس
فرمول
قرار می گیرد و در غیراینصورت Ck,l به LIP منتقل می شود. سپس (i,j) به انتهای مجموعه LIS به عنوان گروه B اضافه می شد.
اگر (i,j) از گروه B و باشد آنگاه
فرمول
هستند به انتهای مجموعه LIS بعنوان گروه A اضافه می شوند و (i,j) از مجموعه LSP پاک می شود.
3) مرحله اصلاح
در این مرحله برای هر (i,j) که تا قبل از مرحله مرتب سازی جاری در LSP قرار گرفته اند. n امین بیت پر ارزش خروجی است.
4- کوانتیزاسیون
در این مرحله یک واحد از مقدار n کم شده و حلقه به گام 2 می رود.
4-2-2) تجزیه و تحلیل الگوریتم SPIHT
الگوریتم SPIHT یک روش ساده در میان روشهای فشرده سازی است چرا که در آن ضرایب پیش از آنکه حلقه شروع شود، مرتب شده اند ممکن است یک میلیون ضریب برای کدگذاری وجود داشته باشد که دسته بندی همه آنها بسیار آهسته صورت می گیرد. الگوریتم SPIHT به جای دسته بندی ضرایب از مقایسه دو عضو استفاده می کند و هر مقایسه یک نتیجه ساده بله یا نه دارد. بنابراین اگر اینکدر و دیکدر از الگوریتم مرتب سازی مشابهی استفاده کنند، اینکدر می تواند به سادگی به عمل اصلی الگوریتم SPIHT انتخاب ضرایب در مرحله مرتب سازی به گونه ای است که در هر تکرار ضریب در محدوده
فرمول
قرار گیرد. بدین ترتیب برای مقدار داده شده n ، اگر ضریب بصورت باشد یا ضریب بصورت ضریب معنی دار و در غیر اینصورت بصورت ضریب بی معنی تعریف میشود. در حلقه اول تعداد ضرایب معنی دار نسبتاً کم است ولی این تعداد از یک حلقه به حلقه بعدی و با کم شدن مقدار n زیاد میشود. معنی دار بودن یک مجموعه در ارزیابی مجموعه ها بدین معناست که حداقل یکی از اعضای آن مجموعه در مقایسه با آستانه جاری معنی دار است و بی معنی بودن یک مجموعه بدین معناست که تمامی اعضای آن مجموعه در مقایسه با آستانه جاری بی معنی هستند.
اینکدر با ضرایب ویولت شروع به کار می کند و تصویر واقعی را نمی بیند ولی دیکدر باید تصویر را نمایش دهد و تصویر نمایش داده شده را در هر تکرار تغییر دهد. در هر تکرار هنگامیکه مختصات (i,j) مربوط به ضریب به LSP فرستاده می شود. در اینکدر و دیکدر
فرمول
در نظر گرفته می شود. بهترین مقداری که دیکدر میتواند به ضریب در هگام بازسازی آن نسبت دهد بین دو مقدار و است و بنابراین مقدار
فرمول
را در نظر می گیرد. (علامت ضریب پس از درج مقدار آن با اضافه کردن مقدار (اگر یک ارسال شود) و یا کم کردن مقدار (اگر صفر ارسال شود) به مقدار
فرمول
اجرای الگوریتم SPIHT را می توان با کدینگ انرژی خروجی اینکدر بهبود بخشید ولی تجربه نشان داده است که افزایش نسبت فشرده سازی در این روش بسیار کم است و نمی تواند اتلاف زمانی را که این کدینگ دارد جبران کند. این موضوع نشان دهنده این است که علامتها و بیتهای منفرد ضرایب خروجی در هر تکرار بصورت یکنواخت توزیع شده اند و بنابراین کدینگ آنها بصورت آنتروپی نسبت فشرده سازی را بالا نمی برد. از طرف دیگر بیتهای توزیع یکنواخت ندارند و ممکن است از طریق چنین کدینگی به دست آیند.
در الگوریتم EZW همانگونه که قبلا اشاره شد، اگر ضریبی معنی دار باشد چهار فرزند آن مورد ارزیابی قرار گرفته و هر یک بصورت جداگانه کد می شوند. این امر حتی هنگامیکه هر چهار فرزند بی معنی باشند اتفاق می افتد ولی در الگوریتم SPIHT تنها یک بیت برای نشان دادن بی معنی بودن فرزندان یک ضریب بکار می رود. در این الگوریتم برای نشان دادن بی معنی بودن تمامی فرزندان غیرمستقیم یک ضریب نیز تنها یک بیت بکار می رود و این نکات برتری الگوریتم SPIHT بر EZW را نشان می دهد.
مثال
ضرایب ویولت مربوط به یک تصویر در یک ماتریس 4×4 نشان داده شده است. (شکل 62+5) این 16 ضریب هر کدام در حافظه بصورت شش بیتی نشان داده شده است که پنج بیت نشان دهنده بزرگی ضریب و یک بیت نشان دهنده علامت ضریب است. در شکل 62-5 تمامی ضرایب همراه با درخت جهت یابی مکانی مربوط به آنها نشان داده شده است. در الگوریتم کدینگ مقدار اولیه LIP برابر با { ( 1و 1) } مقدار اولیه LIS برابر با و LSP تهی در نظر گرفته می شود. بزرگترین ضریب از میان ضرایب 18 است و مقدار n برابر با در نظر گرفته می شود دو تکرار اول الگوریتم در ادامه آمده است:
مرحله مرتب سازی 1 :

– آیا ضریب ( 1 و 1 ) معنی دار است ؟ بله – خروجی 1 است.
– { ( 1و 1) } = LSP و بیت علامت صفر است.
– آیا (1 و 1) D معنی دار است ؟ خیر – خروجی صفر است.
– {(1و1) } = LSP { } = LSP و {(1و1) D } LIS=
– خروجی این مرحله سه بیت است.
مرحله اصلاح 1
– چون این مرحله روی ضرایب مجموعه LSP که حاصل از مرحله n-1 است انجام میشود، این مرحله بیت خروجی ندارد.
کم کردن یک واحد از مقدار n
مرحله مرتب سازی 2

– آیا (1 و 1) D معنی دار است؟ بله – خروجی یک است.
– آیا ضریب (2 و 1) معنی دار است؟ خیر – خروجی صفر است.
– آیا ضریب (1 و2) معنی دار است؟ خیر – خروجی صفر است.
– آیا ضریب (2و2) معنی دار است؟ خیر – خروجی صفر است.
– {(1و1) L } = LIS و { (2و2) و (1و2) و (2و1) } = LIP
– آیا (1 و 1) L معنی دار است؟ بله – خروجی یک است.
{ (2 و 2 ) D و (1و2) D و (2و1) D } LIS=

1 – Embedded zerotree wavelet
2 – Significant
3 – insignificant
4 – embedded coding
5 – orthogonal
6 – biorthogonal
7 – subband pyramid
8 – qual tree
9 – root
10 – node
11 – Dominant List
12 – Dominant pass
13 – subordinate pass
14 – positive significant
15 – negative significant
16 – Isolaled zero
17 – Zero-tree root
18 – coarse scale
19 – finer scale
20 – indicator
21 – Set partitioning in hierar chical trees
22 – embedded codnig
23 – distortion
24 – Sorling step
—————

————————————————————

—————

————————————————————

2

23