الگوریتم 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) درخت جهت یابی مکانی ایجاد و تقسیم بندی مجموعه ها با استفاده از ساختار ویژه ای به نام درخت جهت یابی مکانی انجام می شود این ساختار بگونه ای است که از ارتباط مکانی میان ضرایب ویولت در سطوح مختلف هرم زیرباندها استفاده می کند.
درختهای جهت یابی مکانی در شکل 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 قرار می گیرند.
بطور کلی میتوان گفت پس از تبدیل ویولت یک تصویر را میتوان با ساختار درختی آن نشان داد که در آن یک ضریب در زیر باند پایین میتواند چهار فرزند در زیر باند بالاتر داشته باشد و هر یک از این چهار فرزند میتوانند چهار فرزند دیگر در زیرباندهای بالاتر داشته باشند.
به ساختاری که در این حالت پدید می آید.
درخت چهارتایی گفته می شود که هر ریشه چهارگره دارد.
نکته بسیار مهم نوع شماره گذاری موقعیت مکانی خانه ها (ضرایب) است.
ضریبی که در پایین ترین سطح و در گوشه بالا در سمت چپ قرار داد دارای موقعیت مکانی (0 و 0 ) خواهد بود و به همین ترتیب ضرایب بعدی اضافه می شوند.
اگر این موقعیت گذاری رعایت نشود جواب درستی به دست نمی آید [7].
6-1-2) درخت صفر همانگونه که قبلاً‌اشاره شد میان زیرباندهای مجاوری که در موقعیت مکانی مشابه قرار گرفته‌اند نوعی وابستگی داخلی وجود دارد این بدان معناست که اگر ضریب مربوط به یک والد در تک آستانه مشخص بی معنی باشد به احتمال زیاد ضرایب مربوط به فرزندان نیز در مقایسه با استانه جاری بی معنی خواهد بود و این امر تأیید کننده نزولی بودن چگالی طیف توان در تصاویر طبیعی می باشد در الگوریتم EZW و الگوریتمهای مشابه این رابطه والد و فرزندی برای bitplane مربوط به باارزشترین بیت bit plante (MSB) مربوط به کم ارزشترین بیت (LSB) بکار برده می شود.
معنی دار بودن ضرایب با توجه به آستانه داده شده تعیین می گردد و آستانه در هر مرحله نصف می شود.
ضرایب در هر مرحله با آستانه مقایسه می شود و با توجه به این مقایسه در bitplane مربوطه مقدار o یا 1 به آنها اختصاص داده می شود.
یک درخت صفر درختی است متشکل از ضرایبی که همگی در مقایسه با آستانه جاری بی معنی هستند در اکثر موارد درختهای صفر زیادی در یک bit plane وجود دارد.
استفاده از نمایش درخت صفر برای یک ریشه به معنای بی معنی بودن تمام فرزندان آن در مقایسه با آستانه فعلی می باشد و این امر به فشرده سازی کمک شایانی می کند.
7-1-2) کدگذاری در الگوریتم EZW در این الگوریتم دو لیست با نامهای DL و SL مورد استفاده قرار می گیرند.
لیست DL شامل مختصات ضرایبی است که معنی دار نیستند.
لیست SL شامل بزرگی (نه مختصات) ضرایبی است که معنی دار می باشند هر دوره انجام الگوریتم شامل یک گذار اصلی می باشد که در ادامه آن یک گذار فرعی می آید.
گامهای اصلی الگوریتم به ترتیب زیر است: 1- مقداردهی اولیه الف) مختصات تمامی ضرایب ویولت در لیست DL قرار می گیرد.
ب ) تنظیم آستانه اولیه : فرمول که Ci,y ضریب ویولت می باشند.
2- گذار اصلی تمامی ضرایب در یک مسیر از پیش تعیین شده اسکن می شوند این مسیر طبق چند الگو تعریف می شود.
انتخاب مناسب هر یک از این الگوها می تواند نقش مهمی در افزایش کارایی الگوریتم داشته باشد.
شکل با مقایسه هر یک از ضرایب لیست DL با آستانه جاری T یکی از چهار علامت زیر بعنوان علامت مشخصه ضریب در نظر گرفته می شود.
الف) در صورتیکه ضریب در مقایسه با آستانه جاری T معنی دار مثبت باشد علامت PS بعنوان خروجی در نظر گرفته می شود.
هنگامیکه این علامت ورودی دیکدر قرار گیرد ضریب را برابر T5/1 قرار می دهد.
ب) در صورتیکه ضریب در مقایسه با آستانه جاری T معنی دار و منفی باشد علامت NS بعنوان خروجی در نظر گرفته می شود.
هنگامیکه این علامت ورودی دیکدر قرار گیرد ضریب را برابر T5/1- قرار می دهد.
ج) در صورتیکه یک ضریب در مقایسه با آستانه جاری معنی دار نباشد ولی بعضی از فرزندان آن معنی دار باشند علامت IZ (صفر منفرد) بعنوان خروجی در نظر گرفته می شود.
د) در صورتیکه یک ضریب و تمام فرزندان آن در مقایسه با آستانه جاری بی معنی باشند علامت ZTR (درخت صفر) بعنوان خروجی در نظر گرفته می شود.
نکته مهم این است که لازم نیست نسلهای این درخت صفر در تکرار جاری کدگذاری شوند.
هنگامیکه این علامت ورودی دیکدر قرار می گیرد، به ضریب و تمامی ضرایب مربوطه به نسلهای آن مقدار صرف نسبت می دهد.
مقدار این ضرایب در تکرارهای متوالی اصلاح میشود.
ضرایبی که با علامت PS و NS مشخص شده اند در لیست SL قرار گرفته و مقادیر آنها bitplane مربوطه صفر می شود فلوچارت مربوطه به دسته بندی ضرایب در شکل آمده است.
3- گذار فرعی این مرحله یک مرحله اصلاح می باشد.
در این مرحله هر ضریب معنی دار، با ارسال یک بیت بیشتر از نمایش باینری اش اصلاح می شود.
هنگامیکه دیکدر این بیت را دریافت می‌کند با توجه به صفر یا یک بودن بیت مقدار T25/0 را به مقدار معنی ضریب اضافه می‌کند.
4- کوانینزاسیون مقدار آستانه نصف شده (T=T/2) و اگر تکرار بیشتری مورد نیاز باشد به گام 2 بر می گردد.
8-1-2) تحلیل و بررسی الگوریتم EZW همانگونه که قبلا اشاره شد در مرحله گذار اصلی هنگامیکه یک ضریب با توجه به آستانه جاری بعنوان یک ضریب معنی دار شناخته می شود ضریب به لیست SL اضافه شده و دیگر در مرحله گذار اصلی بعدی مورد ارزیابی قرار نمی گیرد.
در صورتیکه باشد، ضریب ویولت بعنوان ضریب بی معنی در نظر گرفته می شود.
ساختار داده درخت صفر براساس نتایج عملی شناخته شده ای است که در ادامه است: اگر ضریب ویولت قرار گرفته در یک مقیاس کلی بالای هرم مربوط به تصویر با توجه به آستانه T بی معنی باشد، آنگاه به احتمال زیاد تمام ضرایبی که در مقیاسهای جزئی تر در همان جهت و در موقعیت مکانی مشابه قرار گرفته اند.
با توجه به آستانه 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 را بعنوان یک اشاره گر در نظر گرفت که موقعیت یک بیت را مشخص می‌کند.
در هر تکرار این آستانه بر 2 تقسیم شده و به موقعیت بیت بعدی با ارزش کمتر اشاره می کند و بدین ترتیب بیتهای با ارزش کمتر شناخته می شوند.
در طول گذار فرعی لیست فرعی SL اسکن شده و اینکدر خروجی صفر یا یک را برای هر ضریب در نظر می گیرد.
اگر باشد در این مرحله اینکدر عدد یک را می فرستد که به دیکدر نشان می دهد که مقدار واقعی ضریب از 48 بیشتر است.
با دریافت عدد یک ارسال شده دیکدر مقدار ضریب را از 48 به تغییر می دهد.
اگر مقدار صفر توسط اینکدر ارسال شود.
دیکدر مقدار ضریب را به تغییر می دهد.
رشته بیتی که توسط اینکدر در یک گذار فرعی تولید می شود با استفاده از کدگذاری ریاضی تطبیقی بصورت منظم کدگذاری می شوند اینکدر حلقه را هنگامیکه به موقعیت خاصی رسید متوقف می کند چرا که کاربرد ممکن است خواستار نرخ بیت مشخصی باشد.
در اینصورت کار اینکدر در زمان رسیدن به این نرخ بیت مشخص پایان می یابد.
کاربر می تواند با تعیین حداکثر خطای قابل قبول (اختلاف بین تصویر اصلی و تصویربازسازی شده) نیز خواستاراتمام کار توسط اینکدر و دیکدر باشد[1].
SPIHT در سال 1966 pearlman و Said الگوریتم جدیدی را در زمینه فشرده سازی سیگنال و تصویر ارائه دادند [4].
این الگوریتم که SPIHT نام گرفت در واقع حالت پیشرفته و توسعه یافته الگوریتم EZW است از میان الگوریتمهای فشرده سازی مبتنی بر ویولت، از جایگاه خوبی برخوردار است.
الگوریتم SPIHT برای انتقال پیوسته و بهینه مطلوب طراحی شده است.
یکی از بهترین مشخصه های این الگوریتم و شاید مشخصه منحر به فرد آن این است که کیفیت تصویری که نمایش داده می شود بهترین کیفیتی است که می تواند با استفاده از بیتهای کدگذاری شده تا آن لحظه به دست آید.
مشخصه اصلی دیگر این الگوریتم استفاده از کدینگ گسترده است این مشخصه بصورت زیر بیان می شود: اگر اینکدر دو فایل یکی به بزرگی M و دیگری به بزرگی m تولید کند که m از M کوچکتر باشد فایل کوچکتر با m بیت اول فایل بزرگتر برابراست.
این موضوع با یک مثال به خوبی قابل بیان است.
اگر فرض شود سه کاربر منتظر فرستاده شدن یک تصویر فشرده شده مشخص یا کیفیتهای مختلف هستند که اولی به کیفیتی در یک فایل 10 کیلوبایتی ، دومی 20 کیلوبایتی و سومی 50 کیلوبایتی نیاز دارد اکثر روشهای با اتلاف فشرده سازی برای چنین هدفی تصویر را با کیفیتهای مختلف و سه بار فشرده می کنند اما در روش SPIHT یک فایل تولید شده و سه بخش با طولهای 10 کیلوبایت ، 20 کیلوبایت و 50 کیلوبایت به کاربر فرستاده می شود.
الگوریتم SPIHT از روش انتقال تدریجی تصویر استفاده می کند که در بخش 4-1-2 مورد بررسی قرار گرفت.
هدف اصلی در انتقال تدریجی این است که ابتدا اطلاعات خیلی مهم تصویر فرستاده می شود.
این اطلاعات از کاهش زیاد خطا تفاوت بین تصویر اصلی و تصویربازسازی شده به دست می آید.
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 ، اینکدر وارد یک حلقه می شود که در هر تکرار حلقه دو گام انجام می شود: گام مرتب سازی و گام اصلاح.
در اولین تکرار اینکدر عدد 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 منتقل می شود.