تحقیق رمزنگاری توسط سیستم های فرکتال و کیاس

دانشگاه آزاد

موضوع : رمزنگاری توسط سیستم های فرکتال و کیاس

استاد راهنما :

گردآورندگان :

تقدیم ساحت مقدس یوسف زهرا(عج)

مقدمه گردآورندگان:

حمد و سپاس ایزد منان را که با الطاف بیکران خود این توفیق را به ما ارزانی داشت تا بتوانیم قدم در این راه بگذاریم.

فهرست مطالب
عنوان
صفحه
چکیده
14
رمزنگاری با سیستمهای آشوب
15
تحلیل سیستم لورنز
16
سایفرهای رمزنگاری تصویر
16
الگوریتم رمزنگاری آشوبگون تصویر
16
فصل اول : 1-1 ) مقدمهای بر فشردهسازی اطلاعات
17
1-2 ) دستهبندی روشهای فشرده سازی اطلاعات
17
1-2-1 ) فشردهسازی اطلاعات متنی
18
1-2-2 ) فشردهسازی تصاویر دو سطحی
19
1-2-3 ) فشردهسازی تصاویر چند سطحی سیاه و سفید و رنگی
19
1-3) فشردهسازی اطلاعات تصویری
20
1-4 ) کدینگ تصاویر
21
1-4-1 ) نگاشت
21
1-4-2 ) کوانتیزاسیون
23
1-4-3 ) اختصاص کد
23
1-5 ) معیارهای سنجش خطا
25
1-6) فشردهسازی با استفاده از تخمین
26
1-6-1) روشDPCM
27
1-6-2) روش Delta Modulation

1-6-3) تکنیکهای وفقی
29
1-7) فشردهسازی با استفاده از تبدیلات متعامد
30

فصل دوم : مقدمهای بر فرکتالها و هندسه فرکتالی
41
2-1) مقدمه
47
2-2) نظریه آشوب (Chaos)

2-3) بررسی خصوصیات فرکتالها
51
2-4)روش تعیین بُعد ساختارهای فرکتالی
52

فصل سوم : : فشردهسازی تصاویر بر اساس تئوری فرکتالی توابع تکراری
54
3-1 ) مقدمه
58
3-2) تولید فرکتالهای خطی با استفاده از ایده ماشین MRCM
60
3-3 ) تبدیلات آفینی انقباضی وکدهای IFS
61
3-4 ) کدهای IFS و تولید تصاویر خود متشابه
62
3-5 ) کد کردن تصاویر معمولی با استفاده از تئوری فراکتالها
64
3- 5-1) خود تشابهی در تصاویر معمولی
67
3-5-2) مدل کردن خود تشابهی در تصاویر بوسیله ماشین Partitiond-MRCM
69
3-5-3) قضیه کالج و تبدیلات آفینی سه بعدی
71
3-6 ) چرا فشردهسازی با فرکتال؟
75
3-7 ) ارائه یک روش عملی برای فشردهسازی فرکتالی
76
3-7-1) تقسیم بندی تصاویر(Image Segmentation)
77
3-7-2) تکنیکهای کلاسبندی
80
3-7-3 ) انتخاب دامنههای مناسب
80
3-7-4)تبدیلات بلوکی فرکتالی

3-8) فشردهسازی تصویر و نوشتن فایل فرمت فرکتالی تصویر
83
3-9) بازسازی تصویر با استفاده از فایل فرمت فراکتالی تصویر
84
نتایج شبیه سازی
85
نتیجه
87

فهرست اشکال و نمودارها
عنوان
صفحه
شکل(1-1) بلوک دیاگرام یک سیستم کدینگ تصویر
19
شکل(1-2) بلوک دیاگرام سیستم DPCM
24
شکل(1-3) نحوه تخمین دو بعدی
25
شکل(1-4) بلوک دیاگرام یک سیستم DM
25
شکل(2-1) بنویت مندلبروت
31
شکل(2-2) نمونهای از اشکال طبیعی تولید شده بوسیله فرکتال
32
شکل(2-3) سه مرحله از تولید مثلث سیرپینسکی
33
شکل(2-4) ساختار فرکتالی مثلث سرپینسکی
34
شکل(2-5) دو نمونه از اشکال تولید شده توسط فرکتالهای غیرخطی
34
شکل(2-6) شکل کوه تولید شده توسط فرکتالهای تصادفی
35
شکل(2-7) فرضیه آشوب
37
شکل(2-8) فرضیه آشوب
38
شکل(2-9) خودتشابهی در ذوزنقه
42
شکل(2-10) خود متشابهی در فرکتال کخ
42
شکل(2-11) نحوه تشکیل فرکتال کخ از طریق تکرار
44
شکل(2-12) ساختار فرکتالی دانه برف کخ
44
شکل(2-13) مجموعه مندلبرت
45
شکل(2-14) روش تعیین بعد فرکتالی
50
شکل(3-1 ) طرح سیستم MRCM
53
شکل(3-2) مستقل بودن MRCM از تصویر اولیه
53
شکل(3-3) تبدیل آفینی انقباضی
55
شکل(3-4) برگ درخت بارنسلی
58
شکل(3-5) نحوه انتخاب دامنه و برد در سیستم PMRCM
64
شکل(3-6) مقایسه کیفیت لبهها
68
شکل(3-7) بلوک دیاگرام کلی فشردهسازی
71
شکل(3-8) نمودار روش Quadtree
74
شکل(3-9) بلوک دیاگرام تبدیلات بلوکی فرکتالی
77
شکل(3-10) فلوچارت روش دکدکردن فرکتالی
81

فهرست جداول
عنوان
صفحه
جدول(2-1)
46
جدول(2-2)
46
جدول(3-1) کد های IFS چند شکل معروف.
60
جدول(4-1) مقایسه الگوریتم ژنتیک با الگوریتم استاندارد.
95

چکیده :
با توجه به کاربرد روزافزون کامپیوتر حفظ امنیت و تایید صحت تصاویر نیز روز به روز اهمیت بیشتری می یابد . تصاویر مخابره شده ممکن است کاربردهایی چون کاربرد تجاری ، نظامی و یا حتی کاربردهای پزشکی داشته باشند که در هر صورت حفظ امنیت آنها و جلوگیری از دسترسی های غیر مجاز به این تصاویر رمزنگاری آنها را قبل از ارسال روی شبکه ضروری می کند ولی به دلیل ویژگیهای تصاویر خصوصاً حجم زیاد داده های تصویری و ویدئویی استفاده از الگوریتمهای کلاسیک رمز نگاری متن مانند RSA و DES و… در این موارد ناکارآمد ، چون اولاً رمزکردن حجم زیاد داده های تصویری به این طریق بسیار وقتگیر خواهد بود و خصوصاً در کاربردهای بلادرنگ عملی ن یست و دومین مشکلی که این الگوریتمها دارند طول کلید آنهاست که با توجه به حجم داده های رمزشده استفاده از کلیدهای با طول محدود باعث ضربه پذیری روش در برابر حملات متن رمزشده می گردد .برای غلبه بر این مشکلات افراد بسیاری به ارائه روشهای نوینی در رمزنگاری تصویر پرداخته اند.
در این مقاله سعی بر این بوده که با استفاده از ویژگیهای توابع آشوب و امکان تولید کلیدهایی با طول بینهایت الگوریتمی ساده ، سریع و ایمن برای رمزنگاری داده های تصویری ایجاد شود .همچنین با توجه به فضای بزرگ کلید در توابع آشوب این روش در برابر حملاتی چون حمله Brute force نیز بسیار مقاوم است. در انتها باید گفت که علاوه بر حملات عمدی این الگوریتم نسبت به تغییراتی بسیار کوچک در کلید بسیار حساس بوده حتی با در دست داشتن مقادیر تقریبی کلید امکان شکستن رمز برای حمله گران وجود ندارد. بخش دوم این مقاله به بیان ویژگیهای سیستمهای آشوب و سیستم آشوب لورنز اختصاص یافته است . در بخش سوم روشهای رمزنگاری تصویر و ویژگی های خاص تصویر از نظر رمزنگاری را مورد بررسی قرار داده است . در بخش چهارم روش رمزنگاری پیشنهادی بیان شده است.در بخش پنجم نتایج شبیه سازی ارائه شده و بخش ششم به جمع بندی کار اختصاص یافته است.

رمزنگاری با سیستمهای آشوب :

آشوب پدید ه ای است که در سیستمهای غیر خطی تعریف پذیر رخ می دهد که حساسیت زیاد به شرایط اولیه و رفتار شبه تصادفی از خود نشان می دهند . چنین سیستمهایی در حالتی که شرایط معادلات نمایی لیاپانوف را برآورده سازند در مد آشوب به حال پایدار باقی خواهند ماند. ویژگی مهمی که باعث شده این پدیده برای رمزنگاری بسیار مورد توجه قرار بگیرد تعریف پذیری سیستم در عین رفتار شبه تصادفی آن است که باعث می گردد خروجی سیستم از دید حمله گران تصادفی به نظر برسد در حالی که از دید گشاینده رمز سیستمی تعریف پذیر بوده و لذا قابل رمزگشایی است.
الگوریتمهای رمزنگاری بسیاری بر اساس تئوری آشوب طرح شده اند . و برخی از آنها به گونه ای گسترش یافته اند که علاوه بر داده های متنی قادر به رمزنگاری تصاویر هم هستند ولی چون رمزنگاری تصویر باید قابلیت های خاصی همچون سرعت مناسب برای رمزکردن داده های تصویری با حجم زیاد را داشته باشند اغلب ، روشهای رمزکردن متن برای پیاده سازی روی تصویر مناسب نیستند .
دو روش عمده در رمز نگاری آشوبگون تصویر وجود دارد ، رمزنگاری بلوکی و رمزنگاری پی در پی که رمزنگاری بلوکی بیشتر مورد توجه بوده ولی هر دو شیوه مزایا و شایستگی های خاصی را دارا می باشد و در کاربردهای مختلفی تحت شرایط مختلف می توانند به کار گرفته شوند .

تحلیل سیستم لورنز :

سیستم لو رنز از اولین سیستمهای شناخته شده آشوبگون است که در ابتدا برای تحلیل جریانات هوایی و پیش بینی وضع هوا ابداع شد ولی بسیاری از سیستمهای هیدرو دینامی کی ، مکانیکی ، دینامیکی و مسائل لیزری و نوری نیز می توان به وسیله آن مدل و تحلیل کرد .معادلات حاکم بر سیستم به این شرح است :

این سیستم شامل سه پارامتر کنترلی σ ، r ، b است که هر سه مقادیر مثبتی اختیار می کنند .
پارامتر r برای عدد رایلی ، σ به عنوان عدد پرانتل 1 و نسبت هندسی یا b این سیستم با تغییر هر یک از پارامترها رفتارهای گوناگونی از خود بروز می دهد . سیستم لورنز یک سیستم دینامیکی غیرخطی زمان پیوسته است که با مقادیر خاصی برای پارامترهایش رفتار آشوبگون از خود بروز می دهد . در حالتی که پارامتر r به بازه [ 0,1 ] محدود شده باشد منبع ( 0,0,0 ) در حالت عمومی پایدار خواهد بود . در r=1 سیستم بین دو نقطه ایستای متقارن C1 وC2 با مختصات

دو شاخه می گردد البته در صورتی که C2 در ناحیه X>0 قرارگرفته باشد . این نقاط

ایستا تا مقدار پایدار می مانند .

سایفرهای رمزنگاری تصویر :
برخلاف پیامهای متنی داد ه های تصویری ویژگی های خاص خود را همانند حجیم بودن ، اضافات زیاد 2 و همبستگی زیاد بین نقاط تصویر دارند که باعث می شود که اجرای روشهای رمزنگاری سنتی روی تصاویر بسیار سخت و کند باشد گاهی اوقات کاربردهای تصویر نیازهای ، خاصی دارند همانند بلادرنگ بودن ، نگهداری همسان، 3 یکنواختی شکل تصویر 4 ، فشردگی داده ها برای انتقال و نظایر آن . گاهی اوقات برآوردن این نیاز ها به همراه نیاز به امنیت زیاد و کیفیت بالا مشکلاتی را برای بلادرنگ بودن ارسال تصاویر ایجاد می کند برای مثال اگر نیاز باشد تصویری را رمز کرده و فشرده نیز بکنیم برای روشهای سنتی رمزنگاری تصویر قابلیت فشرده سازی بسیار کمی وجود دارد به عبارت دیگر فشرده سازی باعث عدم صحت رمزگشایی و اتلاف در شیوه رمزگشایی می شود خصوصاً اگر از یک روش رمزنگاری با امنیت بالا استفاده شده باشد حل مشکل ناسازگاری بین قابلیت فشرده سازی و ام نیت اگر ممکن نباشد بسیار سخت است . ویژگی های رمزنگاری تصویر را می توان به صورت زیر خلاصه نمود :
اضافات زیاد وظرفیت حجیم عموماً داده های تصاویر رمزشده را در مقابل تحلیل گران و حملات آسیب پذیر می کند . به دلیل ظرفیت حجیم رقبا می توانند نمونه هایی کافی از مت ن رمز شده را برای تحلیلات آماری حتی از یک تصویر بدست آورند در حالی که داده های تصویری اضافات بسیار زیادی دارند نقاط مجاور هم تصویر احتمالاً مقادیر خاکستری شبیه به همی را دارا هستند ، یا بلوکهای تصویر الگوهای مشابه ای را دارند ، که اغلب تصاویری با الگوهای خ اص در خود جای می دهد که منجر به نشت اسناد می شود .
در بین نقاط مجاور هم داده های تصویری همبستگی های بسیار خوبی وجود دارد که باعث می شود در هم ریزی داده های تصویری بسیار کند باشد . تحلیل آماری روی تعداد زیادی از تصاویر نشان داده است که نقاط مجاور هشت تا ش انزده تایی به شکل افقی ، عمودی و حتی قطری ، هم در تصاویر طبیعی در گرافیکهای کامپیوتری به شدت با هم بستگی دارند . مطابق تئوری اطلاعات شانون سیستم رمزنگاری ایمن باید شرایطی را روی انتروپی اطلاعات اجرا کند .

P متن ساده و C متن رمز شده است ، که طبق آن تصویر رمز شده نباید هیچ اطلاعاتی در مورد تصویر رمز نشده بدهد . برای برآورده شدن این نیاز تصویر رمز شده باید تا حد امکان تصادفی باشد از آنجا که یک پیام که توزیع غیر یکنواختی دارد یک پیشینه عدم قطعیت دارد ، یک تصویر رمزشده ایده آل باید یک هیستوگرام متعادلی داشته باشد و هر دو نقطه مجاور باید از نظر آماری کاملاً غیر همبسته باشند این هدف ، تحت تعداد محدودی دورهای جابجایی و پخشی به سادگی قابل دستیابی نیست .
ظرفیت حجیم داده های تصویری رمزنگاری بلادرنگ تصاویر را بسیار سخت می کند . در مقایسه با متن ، داده های تصویری بصورت غیر قابل باوری بزرگ هستند برای مثال یک تصویر رنگی بیست وچهار بیتی با انداره نقاط 512*512 به فضایی برابر با 768=8/24 *512*512 کیلو بایت نیاز دارد و لذا یک ثانیه تصویر متحرک نوزده مگا بایت حافظه نیاز خواهد داش ت و این در حالی است که پردازشهای بلادرنگ برای اغلب کاربردهای تصاویر مانند ویدئو کنفرانس ، مر ا قبتهای تصویری و… مورد نیاز است . مقادیر زیاد داده های تصویری پردازشهای بسیار زیادی را برای رمزنگاری و رمزگشایی تصاویر ایجاب می کند رمزنگاری در طی کدینگ فاز و بعد از آن و رمزگشایی در طی دیکد کردن فاز یا بعد از آن مشکل را پیچیده تر می کند . اگر یک الگوریتم رمزگشایی با وجود امنیت زیادش بسیار کند اجرا شود برای کاربردهای بلادرنگ تصویری ارزش عملی کمی خواهد داشت به همین علت است که الگوریتمهایی همچون RSA ، IDEA ، DES برای این منظور انتخاب مناسبی به شمار نمی آیند .
رمزنگاری تصویر اغلب به همراه فشرده سازی داده ها انجام می شود . تقریباً در همه موارد داده ها قبل از آنکه ذخیره شوند یا انتقال داده شوند فشرده می گردند این بدلیل حجم داده های تصویری و اضافات بسیار زیاد آنهاست بنابراین آمیختن نیازهای امنینی با سیستمهای فشرده سازی داده اهمیت بسیار دارد . مشکل اساسی این است که چگونه در حالی که هزینه محاسبات را بدون کاهش کیفیت عملکرد فشرده سازی کاهش می دهیم از امنیت مناسب نیز اطمینان حاصل کنیم .
در کاربرد تصویر تبدیل شکل فایل یک عمل همیشگی است . رمزنگاری تصویر نیز باید بشکلی طرح شود که چنین اعمالی بر روی آن اثر نداشته باشد . به همین علت محتویات داده ها ی تصویر رمزشده و سرآیند 5 و داده های کنترلی رمز نشده باقی می مانند . بینایی انسان نسبت به نویز و تخریب جزئی تصویر مقاومت زیادی د ارد و برای محافظت از تصویر باید بیت هایی که با هم همبستگی زیادی دارند بخوبی رمز گردند . در صورتی که در روشهای سنتی رمزنگاری به همه بیتهای داده به شکل یکسانی نگریسته می شود و بنابراین لازم است که توان محاسباتی زیادی برای رمزنگاری همه بیتهای تصویر صرف شود که اغلب اوقات این حجم محاسبات غیر ضروری است .
در رابطه با امنی ت ، داده های تصویری به اندازه داده متنی حساس نیستند . امنیت تصویر کاملاً با موقعیت واقعی آن در کاربرد تصویر تعریف می شود . در اکثر موارد به غیر از کاربرد های جاسوسی ، نظامی ، ویدئو کنفرانسها و کاربردهای تجاری خاص داده های تصویری ارزش خیلی زیادی ندارند و لذا حملاتی با هزینه زیاد به داده های تصویری اغ لب ارزشمند نیستند غالباً محافظت هماندهی و کیفیت تصاویر از محافظت از امنیت اطلاعاتشان مهمتر است . در برخی شرایط حتی امکان دارد بخشهایی از داده نیز نشت کند ولی این امر در داده های متنی کاملاً غیر مجاز است چون پس از نشت بخشی از داده حمله به کل داده ها و شکستن رمز آنها کاری کاملاً ساده خواهد بود . در حال حاضر الگوریتمهای رمزنگاری تصویری که قادر باشد همه موارد فوق الذکر را اجرا کند ولی روشهای رمزنگاری آشو ب گون ، بسیاری از این نیازها را تا حد خوبی برآورده می کند خصوصاً این روش رمزنگاری موازنه خوبی بین امنیت ، سرعت وانعطاف پذیری را ایجاد می کند .

الگوریتم رمزنگاری آشوبگون تصویر
الگوریتمهای رمزنگاری آشوبگون به دو صورت بلوکی و پی در پی وجود دارند که هر دو عم لکرد خوبی در این زمینه از خود نشان می دهند . در این مقاله یک روش پی در پی ارائه شده است که در ادامه به شرح نحوه رمزنگاری و رمزگشایی می پردازیم.

1- الگوریتم رمزنگاری

در روش پیشنهادی ابتدا با استفاده از سیستم آشوب لورنز یک کلید رمزنگاری با ابعاد ی برابر ابعاد تصویر مورد نظر تولید کرده به گونه ای که هر یک از حروف این کلیدعددی در بازه [1,256] هستند سپس با استفاده از سایفر بلوکی ضربی و عملگر هنگ که در اینجا برای جلوگیری از واگرا شدن حاصل رمزنگاری ضروری است ، طبق رابطه C=P (P,K) تصویر اولیه رمز می گردد البته در اینجا فقط یک بلوک داریم .این شیوه را می توان با تولید کلیدهایی با اندازه های کوچکتر در تعداد بلوکهای بیشتری هم اعمال نمود همچنین می توان با استفاده از این الگوریتم تصاویر رنگی را هم رمز نمود.
برای مدولاسیون از هنگ 257 که عددی اول است استفاده شده و برای معکو س پذیر بودن کامل کلید بجای تمامی صفرها از 256 استفاده شده ( البته می توان برای جلوگیری از بالا رفتن فرکانس تکرار این عدد از یک الگوی معین برای پخش صفرها بین تمامی 256 عدد دیگر استفاده کرد که با اینکار می توان کلیدی با توزیع یکنواخت تولید کرد که مناسبتر است ولی در مقابل هزینه های محاسباتی بیشتری را در رمزنگاری و رمزگشایی ایجاد می کند.

2- الگوریتم رمزگشایی

برای رمزگشایی تصویر رمزشده با استنفاده از یک سیستم آشوب مشابه در گیرنده و با بکارگیری مقدار اولیه یکسان و با توجه به روشهای معکوس کردن در حوزه هنگ اعداد اول ، کلید رمزگشایی تولید می گردد .یکی از مزایای مهم استفاده از سیستم آشوب ، تسهیلات شیوه مدیریت کلید است زیرا در این روش تنها نیاز به محافظت و انتقال ایمن کلیدهای سری (پارامترها و مقادیر اولیه سیستم آشوب ) است که حجم کمی دارد و بنابراین نه تنها برای نگهداری از آن حافظه کمی نیاز است بلکه در هنگام انتقال آن هم اطمینان بیشتری وجود دارد چون امکان دسترسی غیر مجاز به کلیدهای کوتاه نسبت به کلیدهایی با طول بزرگ در هنگام ارسال و دریافت روی کانال کاهش چشمگیری دارد در واقع حروف کلید رمزگشایی معکوس شده حروف کلید رمزنگاری در هنگ اعداد اول هستند و عمل رمزگشایی ب ا بکار گیری کلید مناسب و تکرار مجدد الگوریتم رمزنگاری بر روی تصویر رمزشده اجرا می شود یعنی P=D(C,K)=E(C,K')

1-1) مقدمهای بر فشردهسازی اطلاعات
پیشرفت در زمینه کامپیوتر و سیستمهای دیجیتال در دهههای اخیر چشمگیر بوده است. سیستمهای دیجیتال مزایای عمدهای نسبت به سیستمهای آنالوگ دارند. اما مشکل عمده سیستمهای دیجیتال، چه در ارسال و چه در ذخیرهسازی، حجم بالای اطلاعات میباشد. در ارسال اطلاعات بصورت دیجیتالی، پهنای باند مورد نیاز به صورتی است که ممکن است ظرفیت فیزیکی کانال، جوابگو نباشد. در ذخیرهسازی اطلاعات نیز هر چند در سالهای اخیر بدنبال پیشرفتهای عمده در تولید حافظههای نیمه هادی و حافظههای جنبی، حجم حافظهها افزایش و قیمت نیز کاهش یافته است اما باز در کل نمیتوانند جوابگوی نیازهای روزافزون برای ذخیره اطلاعات باشند. به همین دلیل همیشه این نیاز احساس میشده که بتوان بصورتی دادهها را فشردهسازی نمود که بدون از دست رفتن اطلاعات و در بعضی موارد با خطای قابل چشم پوشی آنها را در حجم کمتری از حافظه ذخیره و یا با استفاده از پهنای باند کمتری ارسال نمود. علاوه بر موارد فوق فشردهسازی اطلاعات در سیستمهای دیجیتال مزایای دیگری نیز میتواند در بر داشته باشد. به عنوان نمونه فشردهسازی تصاویر یک نوع کد کردن است که دادهها را از دسترسی غیرمجاز مصون میکند.

1-2) دسته بندی روشهای فشردهسازی اطلاعات
فشردهسازی اطلاعات را میتوان بسته به نوع دادههایی که فشرده میشوند به سه دسته کلی: فشردهسازی اطلاعات متنی، فشردهسازی تصاویر دو سطحی و فشردهسازی تصاویر چند سطحی سیاه و سفید و رنگی تقسیم کرد،که در بخشهای بعدی به توضیح هر کدام میپردازیم.

1-2-1 ) فشردهسازی اطلاعات متنی
این روشها، مبتنی بر استفاده از خواص آماری اطلاعات میباشند. برای روشن شدن موضوع به ذکر یک مثال میپردازیم. میدانیم که در سیستمهای کد گذاری اسکی برای همه کاراکترها یک طول ثابت، برابر یک بایت در نظر میگیرند. با تحلیل متون مختلف انگلیسی مشخص میشود که احتمال تکرار بعضی از حروف به مراتب بیشتر از بعضی دیگر میباشد. حال اگر بتوانیم احتمال تکرار یک کاراکتر را در طول کد اختصاص یافته به آن به نحوی دخالت دهیم که برای حروف با احتمال تکرار بیشتر کدهای کوتاهتر و برای حروف کم کاربردتر کدهای طولانیتر اختصاص یابد میتوان یک متن را در حافظه کمتری ذخیره نمود. به این روش، کدگذاری با طول متغییر1 میگویند. در این روش عمل فشردهسازی به صورتی است که بازسازی بدون خطای اطلاعات میسر میباشد. بعنوان یک مثال از این دسته میتوان به روش کد گذاری هافمن اشاره نمود[10].
1-2-2 ) فشردهسازی تصاویر دو سطحی
دومین دسته از روشهای فشردهسازی برای فشرده کردن تصاویر دو سطحی مانند متون ارسالی توسط دستگاه فاکس و نقشههای مهندسی بکار میروند. این روشها نیز بر پارهای از خواص آماری و ریاضی اطلاعت تکیه دارند. بعنوان نمونه در دستگاه فاکس ابتدا سطح سند مورد نظر جاروب یا اسکن میشود و در طول یک خط جاروب شده نقاط سفید با یک بیت صفر و نقاط سیاه با یک بیت یک نمایش داده میشوند. سپس برای کد کردن متن جاروب شده طول رشتههای صفر و یک را بعنوان پدیدههای احتمالی که هر کدام احتمال تکرار خاصی دارند در نظر میگیرند و بر اساس احتمال تکرار هر رشته به آن کد خاصی اختصاص میدهند. در این مورد نیز برای رشتهای با احتمال تکرار بالا کدهای کوتاه و برای رشتههایی که کمتر ظاهر میشوند کدهای بلندتر اختصاص میدهند. روشهای متعددی در این زمینه ارائه شده است که هدف همگی آنها حذف زواید غیر ضروری میباشد که برای حذف این زواید همبستگی بین اطلاعات در طول یک خط(کدینگ یک بعدی) یا در بین خطوط متوالی(کدینگ دو بعدی) در نظر گرفته شده است. در این دسته روشهایی وجود دارند که بازسازی بدون خطای اطلاعات را تضمین می کنند و روشهای دیگری نیز وجود دارند که بازسازی همراه با خطا است.
1-2-3 ) فشردهسازی تصاویر چند سطحی سیاه و سفید و رنگی
سومین دسته از روشهای فشردهسازی جهت کدکردن تصاویر چند سطحی بکار میروند. اساس این روشها بر پایه حذف زواید چشمی و آماری استوار است. بنابراین فشردهسازی همراه با حذف مقداری از اطلاعات کم ارزشتر میباشد که باعث میشود بازسازی همراه با خطا باشد. در این روشها تلاش بر این است که بازسازی با خطای قابل قبول بسته به مورد کاربرد، تضمین شود. معیار سنجش در این مورد میتواند کمی یا کیفی باشد. معیارهای کمی میانگین مربعات خطا2، نسبت سیگنال به نویز3، و حداکثر سیگنال به نویز4 میباشند. معیارهای کیفی معمولا مبتنی بر قضاوت افراد درباره تصاویر میباشد که بستگی زیادی به خواص بینایی چشم انسان دارد.
تصاویر چند سطحی میتوانند بصورت سطوح خاکستری5، رنگی، متحرک یا ثابت و پردازشها نیز بصورت بلادرنگ درسیستمهای ارسال و یا معمولی درهنگام ذخیره باشند، که نحوه پیادهسازی و پارامترهای تعیین کننده در هر مورد متفاوت است. به عنوان مثال در هنگام ارسال تصاویر سرعت الگوریتم، یک پارامتر اساسی است اما به هنگام ذخیره اطلاعات نسبت فشردهسازی بالاتر و خطای بازسازی کمتر، از اهمیت بیشتری برخوردار است و سرعت در درجه دوم اهمیت قرار دارد[17]. علیرغم موارد فوق میتوان گفت که در طراحی یک الگوریتم بهینه به طور کلی سه مورد زیر مد نظر است:
1- بدست آوردن نسبت فشردهسازی هرچه بیشتر.
2- حداقل کردن خطای بازسازی.
3- طراحی الگوریتمهای هر چه سریعتر که بتواند زمان فشردهسازی و بازسازی اطلاعات را به حداقل ممکن برساند.

1-3) فشردهسازی اطلاعات تصویری
هدف از فشردهسازی تصاویر دیجیتال حداقل کردن تعداد بیت مورد نیاز برای ارائه اطلاعات تصویر میباشد. کاربردهای فشردهسازی تصاویر به طور عمده در دو زمینه ارسال و ذخیرهسازی میباشد. ارسال تصاویر مانند پخش تلویزیونی، سنجش از راه دور با استفاده از ماهوارهها، مخابرات نظامی، رادار و سونار، کنفرانس از راه دور، مخابره اطلاعات در شبکههای کامپیوتری، ارسال فکس و غیره میباشد. ذخیرهسازی تصاویر مانند مستندات آموزشی و تجاری، تصاویر پزشکی از جمله توموگرافی کامپیوتر، رادیوگرافی دیجیتالی و نقشههای هوایی میباشد. علاوه بر ذخیرهسازی و ارسال تصاویر کاربرد فشردهسازی جهت الگوریتمهای سریع پردازش تصاویر که میتوانند بر روی دادههای فشرده عمل کنند نیز مدنظر میباشد.
تحقیقات در زمینه فشردهسازی تصاویر به سالهای 1920 میلادی که تلاش برای ارسال تصاویر بین لندن و نیویورک شروع شد برمیگردد. در آن زمان با استفاده از تکنیکهای ابتدایی موفق شدند که زمان ارسال تصاویر را از یک هفته به سه روز کاهش دهند. در دهه 60 پیشرفت در زمینه کامپیوترهای دیجیتال باعث توسعه روشهای فشردهسازی تصاویر شد. این تلاشها در دهه 70 نیز ادامه یافت. در این زمان تحقیقات برروی مسائل اساسی از جمله معیارهای برآورد خطا، مدلهای آماری برای تصاویر، کدینگ بر اساس تخمین6 و فشردهسازی با استفاده از تبدیلات، متمرکز بود. از دهه 1970 تاکنون فشردهسازی اطلاعات به عنوان یک زمینه پرجاذبه در پردازش تصاویر مطرح و تلاش برای ابداع روشهای بهتر ادامه داشته است. در این راستا روشهای جدید فشردهسازی از جمله کوانتیزاسیون برداری7، کدینگ زیر باند8 و فشردهسازی تصاویر با استفاده از فرکتال ابداع شدهاند. تفاوت روشهای مختلف را با توجه به ساختار کلی سیستمهای فشردهسازی تصویر میتوان توضیح داد که در ادامه به این موضوع خواهیم پرداخت.
1-4 ) کدینگ تصاویر
فشردهسازی تصاویری که به صورت چند سطحی هستند با تصاویر دو سطحی سیاه و سفید کاملا متفاوت است. معمولا تصاویر را به صورت یک تابع دو بعدی مانند
F(i ,j) i , j=1, …, N-1
(1-1)
نشان میدهیم. که بین نقاط مختلف آن تکرار9 و همبستگی10 زیادی وجود دارد. موارد فوق به دو دسته زواید آماری و چشمی دسته بندی میشوند. زواید چشمی ناشی از خواص بینایی انسان است. در کدینگ تصاویر، هدف حذف این زواید میباشد. کد کردن شامل سه مرحله می باشد که این سه مرحله در شکل(1-1) نشان داده شدهاند.
1-4-1 ) نگاشت11
در این مرحله هدف نگاشت مقادیر پیکسلها، به ضرایبی ناهمبسته و کاستن از زواید موجود میباشند. در این بخش از تبدیلاتی استفاده میشود که ممکن است معکوس پذیر یا معکوس ناپذیر باشند. هر چند ابعاد برابر ابعاد میباشد اما تبدیلات بکار رفته بصورتی عمل میکنند که یا از محدوده تغییرات دینامیکی دادهها میکاهند و یا درصد بالایی از اطلاعات تصویر را در تعداد محدودی از ضرایب تبدیل متمرکز میکنند. بصورتی که مقادیر بقیه ضرایب در مقابل آنها ناچیز محسوب میشوند و حذف آنها تاثیر ناچیزی در کیفیت تصاویر بازسازی شده دارد.
1-4-2 ) کوانتیزاسیون 12
دادههایی که حاصل عمل نگاشت هستند ممکن است مقادیر متفاوت بسیار زیادی را بتوانند اختیار کنند. عمل کوانتایزر محدود کردن تعداد مقادیری است که خروجی اختیار میکند. بعنوان مثال ممکن است که اعداد حاصل از نگاشت، اعداد حقیقی با محدوده تغییرات وسیعی باشند و کونتایزر این مقادیر را به نزدیکترین اعداد صحیح تقریب بزند. هدف از این کار فراهم آوردن امکان استفاده از بیتهای کمتر برای کد کردن تصاویر میباشد. یک روش ممکن برای کوانتیزاسیون این است که بازه کلی تغییرات ضرایب را به زیر بازههای مساوی تقسیم کرده و یکی از اعداد وسط، ابتدا و یا انتهای هر بازه را برای کوانتیزه کردن مقادیری که در آن بازه قرار میگیرند استفاده نماییم. به این روش، کوانتیزاسیون یکنواخت میگویند. یکی دیگر از انواع کوانتایزرها، کوانتایزرهای غیر خطی است. در این کوانتایزرها بازههای مختلف طولهای متفاوت دارند.
عمل کوانتیزاسیون یک عمل غیر قابل برگشت است. چون با در دست داشتن مقادیر خروجی نمیتوان مقادیر ورودی اولیه را تعیین نمود. بنابراین در خلال عمل کوانتیزاسیون متحمل یک خطای ثابت میشویم. هدف روشهای مختلف کوانتیزاسیون حداقل کردن این خطا میباشد و کوانتیزاسیون غیرخطی تلاشی در راستای این هدف است.
از آنجایی که ضرایب با واریانس بیشتر مشارکت بیشتری به نسبت ضرایب با واریانس کمتر در بازسازی اطلاعات نهایی دارند استفاده از کوانتیزاسیون خطی خطای بیشتری را به سیستم تحمیل میکند. یک راه چاره آن است که ابتدا ضرایب هر بازه را به نسبت واریانس مقادیر آن بازه نرمال کرده سپس از کوانتایزر خطی استفاده کنیم. یک دیدگاه دیگر با توجه به تحلیلهای به انجام رسیده(که نشان میدهد تابع توزیع ضرایب به توزیع نرمال نزدیک است) استفاده از یک کوانتایزر با بازههای نامساوی است. درجاهایی که احتمال وقوع ضرایب زیادتر است عرض بازهها را کمتر و در جاهایی که این احتمال کمتر است عرض بازهها را بیشتر اختیار کنیم. بدین ترتیب 20 تا30 درصد از خطای کوانتیزاسیون کاسته میشود[22].

1-4-3 ) اختصاص کد
بعد از کوانتیزاسیون ضرایب، مرحله اختصاص کد به ضرایب کوانتیزه شده قرار دارد. در این بخش برخلاف کوانتایزر چون به ازای هر ورودی خاص، یک خروجی معین داریم متحمل هیچ خطایی نمیشویم. سادهترین روش برای اختصاص کد استفاده از کد باینری معمولی میباشد. در ارسال اطلاعات برای حداقل کردن اثر خطای خطوط مخابره میتوان از کدهای گری، به جای کد باینری معمولی استفاده نمود. ویژگی این کد در آن است که کدهای هر دو عدد متوالی تنها در یک بیت تفاوت دارند. با توجه به آنکه احتمال تکرار ضرایب مختلف یکسان نیست میتوان برای دستیابی به فشردهسازی بالاتر از کدهای با طول متغیر مانند کد هافمن استفاده نمود. روشهای به کار رفته در این بخش همان طوریکه در بالا به آن اشاره شد بدون خطا هستند و مشابه روشهای کدینگ فایلهای داده میباشند. در اینجا به دو دلیل از شرح جزئیات این بخش صرفنظر میکنیم. یکی به دلیل آنکه استفاده از روشهای کدینگ با طول متغیر در اکثرسیستمها بدلیل افزودن بر بار محاسبات و پیچیدگی سیستم استفاده نمیشود. علاوه بر آن خواننده علاقمند میتواند این بحث را در تئوری اطلاعات و کدینگ آنتروپی پیگیری نماید. از دیدگاه فشردهسازی اطلاعات تصویری، روشهای مختلف بر اساس تکنیکهای به کار رفته در دو بخش نگاشت و کوانتیزاسیون از همدیگر جدا میشوند که در بخشهای آینده مهمترین آنها را مورد بررسی قرار میدهیم[22].
1-5 ) معیارهای سنجش خطا
همانطوریکه قبلا اشاره شد روشهای فشردهسازی اطلاعات تصویری، همراه با تحمل خطا13 هستند. در این سیستمها وفاداری تصویر14 بازسازی شده به تصویر اولیه یک معیار مهم برای ارزیابی راندمان فشردهسازی میباشد. این معیارها به دو دسته کیفی و کمی تقسیم میشوند. بدلیل آنکه معیارهای کیفی یک روش دقیق ریاضی بدست نمیدهند و بر قضاوت افراد استوار هستند، معمولا برای ارزیابی کارآیی روشهای مختلف از معیارهای کمی استفاده میشود. به همین دلیل در این بخش ما به معرفی دقیقتر معیارهای کمی معمول در سیستمهای فشردهسازی میپردازیم. فرض کنیم تصویر ورودی یک بردار N*N از پیکسلهایی به صورت
,i ,j= 0,1,…,N-1 باشد و تصویر نهایی بعد از عمل بازسازی را با تابع دو بعدی
,i ,j= 0,1,…,N-1 نشان دهیم. متداولترین معیار سنجش خطا، میانگین مربعات خطا15 میباشد که به صورت اختصاری آنرا با MSE نمایش میدهند و از رابطه زیر محاسبه می شود:
(1-2)
MSE =

دومین معیار، میانگین مربعات سیگنال به نویز یا به صورت ساده شده نسبت سیگنال به نویز16 است، که به صورت زیر محاسبه میشود :
(1-3)
SNR =

(1-4)
PSNR =

بعنوان یک معیار جایگزین برای رابطه فوق میتوان از نسبت حداکثر سیگنال به نویز17 استفاده نمود، که رابطه آن در زیر آمده است .

معیارهای فوق عملکرد مشابهی دارند و به دلیل سادگی محاسبات آنها بصورت گستردهای برای ارزیابی روشهای مختلف فشردهسازی استفاده میشوند. اما تذکر این نکته ضروری است که معیارهای فوق مستقل از تصاویرهستند. بنابراین در حالت کلی نمیتوانند منعکس کننده کیفیت واقعی تصویر از نظر بینایی انسان باشند. ممکن است در اغلب موارد دو تصویر متفاوت که دارای خطای MSE یکسان هستند از نظر بینایی انسان کاملا متفاوت باشند. بنابراین بعنوان یک راه حل نهایی معیارهای کیفی که مبتنی بر قضاوت افراد هستند نقش مهمی را بازی میکنند.

1-6) فشردهسازی با استفاده از تخمین 18
در تصاویر معمولی مقادیر پیکسلهای مجاور اغلب به یکدیگر خیلی نزدیک هستند و تغییرات در آنها به آرامی صورت میگیرد. تکنیکهای تخمین تصاویر بر این اساس استوار هستند که با مشاهده مقادیر یک یا چند پیکسل قبل، مقدار پیکسل جاری را برآورد نمود. بدین وسیله میتوان زواید را کم کرد و تنها اطلاعات جدید را ارسال یا ذخیره نمود. تکنیکهای تخمین ممکن است یک بعدی یا دو بعدی باشند. در ادامه این بخش به مرور معروفترین این روشها میپردازیم.

1-6-1) روشDPCM 19
همانطوریکه قبلا اشاره شد پیکسلهای مجاور در اغلب تصاویر شدیدا همبستگی دارند و این بدین معنی است که اگر تفاضل پیکسلهای مجاور را بدست آوریم این تفاضل غالبا مقدار خیلی کمتری از مقادیر خود پیکسلها خواهد داشت. روش DPCM از این خاصیت برای کاستن از زواید چشمی و آماری و کدکردن تصاویر با تعداد بیت کمتر استفاده میکند. زیرا بدلیل کوچک بودن تفاضل بین مقادیر پیکسلهای متوالی برای کد کردن آنها مقدار بیت بمراتب کمتری نیاز خواهد بود. بلوک دیاگرام این روش در شکل(1-2) مشاهده میشود.

در روش DPCM ابتدا بر اساس مقادیر پیکسهای قبلی تخمینی از مقدار پیکسل جاری بدست میآید. سپس تفاضل این مقدار تخمینی از مقدار واقعی پیکسل محاسبه میشود و نهایتا بجای کد کردن مقدار واقعی، خطای تخمین کد میشود. در هنگام بازسازی تصویر نیز دوباره بر اساس همان رابطه مورد استفاده هنگام کد کردن تخمینی از مقدار مورد نظر محاسبه و سپس مقدار بدست آمده با خطای دکد شده جمع میشود.
بخش تخمین و مقایسه کننده در شکل(1-2) جمعا با هم عمل نگاشت را انجام میدهند. روشهای DPCM بصورت یک بعدی یا دو بعدی موجود میباشند. در DPCM یک بعدی برای تخمین مقدار پیکسل جاری تنها از پیکسلهای قبل از آن در خط جاری استفاده میشود. در DPCM دو بعدی برای تخمین مقدار پیکسل با شماره صفر مطابق شکل(1-3) از مقادیر پیکسلهای یک تا چهار در خط قبل و خط جاری استفاده میشود.

2 3 4
خط قبلی
خط فعلی
1 0

شکل1-3: نحوه تخمین دو بعدی.

DPCM دو بعدی به بهبود کیفیت تصاویر بازسازی شده کمک میکند و خطای بازسازی را به مقدار قابل توجهی کاهش میدهد. بررسیهای انجام شده نشان میدهد که دخالت دادن پیکسلهای بیشتر از آنچه در شکل(1-3) نمایش داده شدهاند تاثیر چندانی در بهبود کیفیت تخمین ندارد.

1-6-2) روش Delta Modulation
روش DM در واقع یک مدل ساده شده از DPCM میباشد. که کوانتایزر آن دو سطحی میباشد. حسن این روش سادگی آن میباشد. بخش پیشگویی یا تخمین این سیستم از یک تاخیر دهنده استفاده میکند که عمل آن انتگرالگیری گسسته از سیگنال خطا است. بلوک دیاگرام آن در شکل(1-4) دیده میشود.

دراین سیستم خطای خروجی کوانتایز در یک ضریب همبستگی ضرب میشود و سپس به انتگرالگیر وارد میشود که با این روش مرتبا تخمین سیستم از مقدار خطا تصحیح میشود. در خروجی تنها یک بیت با علامت مثبت یا منفی داریم. برای کاربرد در کدینگ تصاویر سیستم فوق براحتی وفقی میگردد و علت مورد توجه قرار گرفتن این سیستم همین مسئله میباشد. در یک سیستم DM وفقی پلاریته20 خروجیهای متوالی مبنای کار است وقتی خروجیهای متوالی، سیستم پلاریته یکسان داشته باشند میتوان استنباط نمود که در محل یک لبه با کنتراست زیاد قرار گرفتهایم و افزایش ارتفاع سطوح کوانتیزاسیون باعث کاهش خطا خواهد شد بر عکس در هنگامی که خروجیهای متوالی بطور متناوب تغییر پلاریته میدهند میتوان نتیجه گرفت که در ناحیه زمینه ثابت تصویر قرار داریم و در این حالت کاهش ارتفاع سطوح کوانتایزر مفید خواهد بود.
1-6-3) تکنیکهای وفقی 21
ایده وفقی کردن روشهای تخمین برای بدست آوردن راندمان بیشتر با توجه به متفاوت بودن طبیعت تصاویر مختلف میباشد. با توجه به آنکه دو جزء اصلی در این سیستمها بخش کوانتیزاسیون و پیشگویی میباشند وفقی کردن میتواند متضمن وفقی کردن هر کدامیک از این دو باشد. طراحی کوانتایزرهای وفقی خود شامل دو مسئله اساسی میشود. یکی اینکه بتوانیم ساختارهای متفاوت در تصاویر را آشکار کرده و آنها را کلاسبندی نماییم و دوم آنکه بتوانیم مجموعهای از کوانتایزرها را به صورتی طراحی کنیم که با ساختارهای مربوط بخوبی تطبیق پیدا کنند.
پیشگوهای وفقی بدین منظور طراحی میشوند که کیفیت تصویر را بخصوص در لبهها بهبود بخشند. یک روش ممکن آن است که از چندین بلوک پیشگو استفاده شود که هر کدام همبستگی در یک جهت خاص حساس باشد. برای فعال کردن هر کدامیک از این پیشگوها میتوان از یک سیستم تشخیص جهت، استفاده نمود. بدلیل سادگی و سرعت روشهای تخمین، در ارسال بلادرنگ تصاویر از این روشها خیلی استفاده شده است. وفقی کردن الگوریتمها بهبود نسبی در کیفیت تصاویر بازسازی شده ایجاد میکند. با دو بیت به ازای هر پیکسل نتایج خوبی گزارش شده است. بصورت کلی روشهای تخمین در محدوده یک تا سه بیت بر پیکسل میتوانند اطلاعات را فشرده کنند. خطای این روشها به نسبت روشهای دیگر بیشتر است. در بخش آینده خواهیم دید که روشهای فشردهسازی با استفاده از تبدیلات بمراتب کاراتر هستند.
1-7) فشردهسازی با استفاده از تبدیلات متعامد
یکی از مهمترین روشهای فشردهسازی تصاویر، کدینگ تبدیل22 میباشد. روشهای کدینگ از تبدیلات متعامد بعنوان ابزاری جهت نگاشت اطلاعات تصویری اولیه به ضرایب تبدیل استفاده میکنند. این ضرایب خواص آماری متفاوت با دادههای مربوطه در حوزه زمان دارند. عمدهترین مشخصه مورد نظر عدم وابستگی آنها میباشد.
تبدیلات کاربردهای وسیعی دارند و مدتها قبل از پردازش تصاویر در شاخههای دیگر علوم و مهندسی از آنها استفاده میشده است. برخلاف روش DPCM که پیکسلهای تک به تک مورد پردازش قرار میگیرند، روشهای کدینگ تبدیل بر روی بلوکهایی از دادههای تصویری عمل میکنند. در فشردهسازی تصاویر معمولا از تبدیلات دو بعدی استفاده میشود. بعد از اعمال تبدیل به دادههای اولیه تعداد بیت متفاوتی بر اساس مقدار ضرایب جهت کوانتیزه کردن به آنها اختصاص داده میشود. بدلیل آنکه ضرایب تبدیل تقریبا ناهمبسته هستند خطای کوانتیزاسیون و خطای کانال در خلال تبدیل معکوس بر روی تمامی پیکسلها پخش شده و بصورت یک نویز تصادفی جمع شونده ظاهر میشود. تبدیلاتی که در این زمینه بکار میروند قادرند که انرژی بلوکهای تصویر را در تعداد معدودی از ضرایب خلاصه کنند بصورتی که نصف بیشتر ضرایب مقدار نزدیک به صفر دارند و میتوان قبل از کوانتیزاسیون آنها را حذف نمود. که این عمل منجر به افزایش نسبت فشردهسازی میشود. در روشهای کدینگ تبدیل، چندین پارامتر اساسی وجود دارد که باید آنها را تعیین نمود. این پارامترها عبارتند از :
1- انتخاب نوع تبدیل.
2- انتخاب ابعاد زیر تصویرها یا بلوکهای تصویر.
3- معیار انتخاب ضرایب جهت کدکردن و ارسال .
انتخاب نوع تبدیل بر اساس معیارهایی چون توانایی متمرکز کردن انرژی در تعداد محدودی از ضرایب، ناهمبسته بودن ضرایب تبدیل، عدم وابستگی به دادههای ورودی، سادگی و سرعت اجرای تبدیل میباشد. تبدیلات متعامد انواع مختلفی دارند. این تبدیلات به دو گروه تبدیلات بهینه23 و زیر بهینه24 تقسیم میشوند. یک تعریف ارائه شده برای تبدیل بهینه این است که بتواند ضرایب کاملا ناهمبسته تولید کند و ضمنا انرژی تصویر را در حداقل ضرایب ممکن ذخیره نماید. بر اساس این تعریف تبدیل کارهننلاو25 یک تبدیل بهینه است. اما بدلیل آنکه شدیدا به محتوای تصاویر وابسته است و هیچ الگوریتم سریعی برای تخمین ضرایب آن وجود ندارد از این روش تنها بعنوان معیاری جهت سنجش میزان بهینه بودن تبدیلات دیگر استفاده میشود.

تبدیلات زیر بهینه متعددی موجود است که از جمله آنها میتوان به تبدیل فوریه، تبدیل کسینوسی، تبدیل سینوسی، تبدیل هار26، تبدیل اسلانت27 و تبدیل هادامارد28 اشاره نمود. از میان این تبدیلات، تبدیل کسینوسی بدلیل آنکه با فاصله بسیار کمی تبدیل KLT را دنبال میکند کاربرد فراوانی دارد. در ضمن ساختار سخت افزاری آن بسیار ساده است.
دومین پارامتر مهم در کدکنندههای تبدیل، اندازه زیر تصویرها است. با افزایش ابعاد بلوکها تعداد عملیات مورد نیاز به صورت توانی افزایش مییابد و باعث افت شدید سرعت فشردهسازی و بازسازی تصاویر میشود. همچنین بررسیهای مختلف نشان داده است که با افزایش ابعاد بلوکها از یک حد معین به بعد بدلیل کاهش همبستگی نقاط تصویر راندمان فشردهسازی تقریبا ثابت میماند. البته عملکرد تبدیلهای مختلف نیز تا اندازهای متفاوت است. اما معمولا از بلوکهای 8*8 یا 16*16 برای کدرهای تبدیل استفاده می شود.
پارامتر سوم نحوه انتخاب ضرایبی است که برای عمل کوانتیزاسیون استفاده میشوند. در این رابطه دو نوع استراتژی تحت عنوان کدینگ ناحیهای29 و آستانهای30 وجود دارد. در روش اول معمولا تعداد n عدد از ضرایب تبدیل که بیشترین مقدار واریانس را دارند کد میشوند. برای اجرای این روش فرض میشود که ضرایب با بیشترین واریانس در یک ناحیه خاص قرار میگیرند و مطابق آن یک ماسک مناسب در نظر میگیرند. در روش دوم یک سطح آستانه مناسب در نظر میگیرند و ضرایب بزرگتر از آن را کد کرده و مقادیر کوچکتر از آن را مساوی صفر فرض میکنند. در مقایسه این دو روش، روش آستانهای کیفیت بهتری از نظر تصاویر بازسازی شده ارائه میدهد. ولی پیادهکردن آن پیچیدهتر است و بدلیل نیاز به مشخص بودن محل ضرایب نسبت فشردهسازی را کاهش میدهد.

فصل دوم

مقدمهای بر فرکتالها
و
هندسه فرکتالی

2-1 ) مقدمه
هندسه اشیای طبیعی از مقیاس اتمی تا کیهانی نقش اساسی در مدل کردن و فهم طبیعت دارد. هندسه مسیر ذرات، خطوط جریان سیال، امواج کوهها، جزایر، سواحل، رودخانهها، هندسه ذرات دانهای31 در صخرهها، فلزات و مواد کامپوزیتی، هندسه گیاهان، حشرات، رودخانهها، شبکه رگها و اعصاب و هندسه کریستال و مواد شیمیایی چون پروتئینها ، نمونههایی از هندسه طبیعت هستند.
به طور سنتی، ابزار هندسه اقلیدسی یعنی خط، دایره، کره و … ابزار اساسی مدل کردن بودهاند اما این ابزار تناسبی با اشکال طبیعی ندارد. به بیان بهتر با یک ترکیب از تعداد متناهی خط، دایره، کره و … نمیتوان به مدلی هم بعد با اشیائ طبیعی دست یافت. همه شما حتی اگر از هندسه نیز چیزی ندانید بارها نام آن را شنیدهاید و حتماً میدانید که "جبر، حساب و هندسه" سه شاخه مهم از ریاضیات است، همین سه عنوان در ریاضیات پایه گذار پیشرفت در تمام علوم محسوب میشوند.
شاید همین حس مسئولیتی که ریاضیات به تمام بخشهای علوم دارد آن را بسیار جدی و در نظر بسیاری، علمی خشک و در عین حال سخت جلوه داده است. در این میان هندسه نقش بسیار مهمی را حتی در شاخههای ریاضی برعهده دارد. هندسه که میتوان به آن علم بازی با اشکال لقب داد، خود پایه گذار دیگر شاخههای ریاضی است. زیرا تمام قسمتهای دیگر در ریاضیات و علوم دیگر تا به صورت مشهودی قابل بررسی دقیق و اصولی نباشد جای پیشرفت چشمگیری برای آنها نمیتوان درنظر گرفت. با این اوصاف، شایسته است به هندسه لقب
"مادر بزرگ علوم" دهیم. شاید اگر زمانی که حوزه اطلاعاتمان از اعداد تنها به مجموعه اعداد طبیعی منتهی میشد و معلم درس ریاضیات از ما میخواست تا ضلع سوم مثلث قائم الزاویهای را که طول هر ضلعش یک سانتی متر است اندازه بگیریم نمیتوانستیم عددی را با چنین ویژگی بیابیم. سالها پیش اقلیدس با حل مسئلهای نظیر این(محاسبه قطر مربعی که هر ضلعش 1 واحد بود)، سلسله اعداد جدیدی را به مجموعههای شناخته شده اضافه کرد که یکی از شاهکارهای بینظیر در پیشرفت ریاضیات و البته علوم بود. بله این عدد عجیب و غریب
" رادیکال 2 " بود.
عموم تحصیلکردگان با هندسه اقلیدسی آشنا هستند. زیرا دست کم در طول دوران تحصیل خود به اجبار هم که بوده در کتابهای درسی با این هندسه که اصول آن بر مبنای اندازهگیری است آشنا شدهاند. اما هندسه اقلیدسی تنها به بررسی اشکال کلاسیک موجود در طبیعت
میپردازد. در این هندسه اشکال و توابع ناهموار، آشفته و غیر کلاسیک به بهانه اینکه مهارناپذیرند، جایی نداشتند. این ناکارایی، ریاضیدانان را بر آن داشت تا به ابداع هندسههای پیشرفتهتر از هندسه اقلیدسی بپردازند. بالاخره در سال 1980، طلسم یکی از تئوریهای ریاضی که از سال1897، عنوان شده بود، شکست و "بنویت مندلبرت" ریاضیدان لهستانی، پایه گذار هندسه جدیدی شد که به آن هندسه بدون اندازه یا هندسه فرکتالی گویند. هندسه بدون اندازه یکی از شاخههای جدید ریاضیات است که در برابر تفسیر و شبیهسازی اشکال مختلف طبیعت از خود انعطاف و قابلیت بینظیر نشان داده است. با به کارگیری هندسه فرکتالی، افق روشنی پیش روی ریاضیدانان و محققان در زمینه بازگو کردن رفتار توابع و مجموعههای به ظاهر ناهموار و پر آشوب قرار گرفت.

شکل2-1: بنویت مندلبروت
واژه فرکتال به معنای سنگی است که به شکل نامنظم شکسته شده باشد. فرهنگستان زبان فارسی، واژه برخال را برای آن جایگزین نموده است. واژه برخال از دو پاره برخ و ال ساخته شده است، برخ واژه فارسی برای کسر32 است و پسوند ال پسوندی به معنای" مرتبط با " است. در این هندسه اشکالی مورد بررسی قرار میگیرند که بسیار نامنظم به نظر میرسند. اما اگر با دقت به شکل نگاه کنیم متوجه میشویم که تکههای کوچک آن کم و بیش شبیه به کل شکل هستند به عبارتی جزء در این اشکال، نمایندهای از کل است، به چنین اشکالی نام "خود متشابه" نیز میدهند.
اشکال فرکتالی چنان با زندگی روزمره ما گره خورده که تعجب آور است. با کمی دقت به اطراف خودتان، میتواند بسیاری از این اشکال را بیابید. از گل فرش زیر پای شما و گل کلم درون مغازههای میوه فروشی گرفته تا شکل کوهها، ابرها، دانه برف و باران، شکل ریشه، تنه و برگ درختان و بالاخره شکل سرخسها، سیاهرگ و شش و… همه اینها نمونههایی از اشکال فرکتالیاند. این موجودات به عنوان اصلیترین بازیگران هندسه منتج از نظریه آشوب شناخته میشوند.
این هندسه ویژگیهای منحصر به فردی دارد، که میتواند توجیهگر بسیاری از رویدادهای جهان اطراف ما باشد، اما ویژگی اصلی که در تعریف آشوب و بالطبع هندسه آن وجود دارد، باعث میشود ما استفاده ویژهای از این سیستم ببریم. این روزها از فرکتالها به عنوان یکی از ابزارهای مهم در گرافیک رایانهای نام میبرند، اما هنگام پیدایش این مفهوم جدید بیشترین نقش را در فشردهسازی فایلهای تصویری بازی کردند[48].
یک مجموعه فرکتالی، وجوهی متمایز نسبت به اشکال هندسی نسبتی دارد. فرکتالها در هر مقیاس، کمابیش یکسان دیده میشوند. این خود همانندی، یکی از دلایل اصلی تناسب هندسه فرکتالی برای توصیف برخی خصوصیات سیستمهای دینامیکی غیرخطی است. دیگر مشخصه معمول فرکتالها، بعد غیرصحیح آن است، برای آن که درک بهتری نسبت به فرکتالها داشته باشیم، در ادامه نگاه مختصری به نظریه آشوب خواهیم داشت. هندسه فرکتالی کتابخانهای بسیار غنی از اشکال پیچیدهای ارائه میدهد و بنظر میرسد که در توصیف اشکال طبیعی بمراتب کاراتر از هندسه معمولی باشد. اشکال بسیار زیبای فرکتالی زیر میتواند دلیلی بر این مدعا باشد.

شکل2-2: نمونه ای از اشکال طبیعی تولید شده بوسیله فرکتال.

از یک جنبه میتوان فرکتالها را به دو دسته زیر تقسیم کرد:
1- فرکتالهای طبیعی
2- فرکتالهای مصنوعی
از جنبهای دیگر میتوان فرکتالها را به سه دسته تقسیم کرد که عبارتند از :
1- فرکتالهای خطی 33
2- فرکتالهای غیرخطی34
3- فرکتالهای تصادفی 35

فرکتالهای خطی را میتوان به سیستمهای درجه اول تشبیه نمود. در این سیستمها در صورتی که ورودی، یک خط مستقیم باشد خروجی نیز یک خط مستقیم خواهد بود. بنابراین تبدیلات بکار رفته بصورتی عمل میکنند که زوایای بین اجزای مختلف را تغییر نمیدهند و تنها ممکن است عملیاتی مانند مقیاس بندی اجزا، دوران و یا انتقال آنها را انجام دهند. یک مثال بارز و شناخته شده از این نوع فرکتالها مثلث سیرپینسکی36 میباشد که در شکل زیر نشان داده شده است. این مثلث به این صورت شکل میگیرد که در یک مثلث اولیه ابتدا وسط سه ضلع مثلث را به هم متصل کرده تا سه مثلث دیگر ایجاد شود و حال این عمل برای مثلثهای ایجاد شده به همین ترتیب ادامه مییابند تا بینهایت جزئیات تولید شود. مجموعه زیبایی از مثلثهای پر و خالی به وجود میآید که فرکتال سر پینسکی به دست خواهد آمد[49].

شکل2-3: سه مرحله از تولید مثلث سیرپینسکی.

شکل2-4: ساختار فرکتالی مثلث سرپینسکی.

برای ایجاد این مثلث میتوان از یک روش توصیف دیگر نیز استفاده نمود که در بخشهای بعد به آن اشاره خواهیم کرد. همان طوریکه مشاهده میشود مثلثهای کوچکتر که در هر مرحله تولید میشوند مشابه مثلثهای بزرگتر در مرحله قبل هستند و تنها اضلاع آنها به یک نسبت کوچکتر شدهاند.
دومین دسته از فرکتالها را فرکتالهای غیرخطی مینامند. برای تولید این فرکتالها از تبدیلاتی غیرخطی مانند جذرگرفتن و غیره استفاده میشود که علاوه بر ابعاد، زوایای موجود در تصویر را نیز در هر مرحله از الگوریتم تکرار به نسبتهای متفاوتی مقیاسبندی میکنند. اشکال تولید شده توسط این دسته از فرکتالها بسیار غنی و از نظر ظاهر پیچیده هستند. از معروفترین آنها میتوان به مجموعه ژولیا37 اشاره نمود. دو نمونه از آن در شکل زیر آمده است.

شکل2-5: دو نمونه از اشکال تولید شده توسط فرکتالهای غیر خطی.
دو دسته فوق را فرکتالهای معین 38میگویند، بدلیل آنکه در تبدیلات بکار رفته هیچ گونه حالت تصادفی وجود ندارد. یک روش دیگر برای تولید فرکتالها این است که در هر مرحله از الگوریتم تکرار تولید شکل فرکتالی، مقادیر پارامترهای تبدیل بصورت تصادفی از بین مجموعه مقادیر مجاز انتخاب شوند، بدین ترتیب، دستهای از فرکتالها حاصل میشوند که به آنها فرکتالهای تصافی میگویند. این فرکتالها توانایی خود را در بازسازی بعضی از تصاویر طبیعی مانند کوهها و درهها بخوبی نشان دادهاند و مندلبرات برای اولین بار موفق شد که با استفاده از این نوع فرکتالها اشکال بسیار جذابی تولید نماید.

شکل2-6: شکل کوه تولید شده توسط فرکتالهای تصادفی.

در ادامه این فصل هر جا بحثی از فرکتال باشد تنها دسته اول یعنی فرکتالهای خطی مورد نظر خواهد بود مگر آنکه صریحا تاکید کنیم که نوع دیگری مورد نظر است.

2-2 ) نظریه آشوب(Chaos)
آشوب، در مبحث واژگان این کلمه انسان را به یاد بینظمی میاندازد. به یاد حالتی که هیچ چیز بر سر جای خود نباشد. اما آیا واقعا چنین است؟
مطالعه در مورد این مبحث در حقیقت از مطالعات هواشناسی شروع شد. چندی از دانشمندان هواشناسی مشغول مطالعه در مورد شرایط جوی و تاثیر موارد مختلف بر هوای جهان و منطقه داشتند. آنان به مدت دو سال مشغول مطالعه هوای یک منطقه خاص دارای آب و هوای نسبتا بیتغییر و کاملا معتدل بودند و تمامی تغییرات را ثبت میکردند. یک دستگاه ثبت نمودار تغییرات جوی هر روز راس ساعت شش صبح روشن میشد و نمودار تغییرات را تا شش بعد از ظهر ثبت میکرد. اما در پاییز سال دوم ناگهان نمودار این تغییرات به طرز عجیبی عوض شد. یعنی نموداری مغشوش به ثبت رسید که نشانه بروز تغییرات شدید جوی بود در صورتی که آن منطقه هیچ تغییری مشاهده نشده بود. دانشمندان شروع به مطالعه در این مورد کردند تا دلیل این تغییر را دریابند اما متوجه هیچ چیز نشدند. پس از پاییز همه چیز دوباره عادی شد. این امر آنان را بر آن داشت تا یک سال دیگر مطالعات خود را در آن محل ادامه دهند. در پاییز سال بعد آنها همه چیز را تحت نظر داشتند. در این سال نتیجه مشاهدات خود را پیدا کردند. در نزدیکی آن محل دریاچهای بود که گروهی از پرندگان مهاجر در پاییز به آنجا میرفتند. آن چه باعث تغییر شدید در نمودار میشد همین پرندگان بودند. پرواز دسته جمعی این پرندگان باعث میشد تا حرکت بالهای آنان فشاری بر جو بیاورد و این فشار به مولکولهای کناری هوا منتقل میشد و نهایتا به سنسور ثبت نمودار دستگاه میرسید. یکی از دانشمندان کنجکاو در پی آن شد که متوجه شود اگر این پرندگان آنجا نبودند چه میشد. وی با استفاده از یک برنامه کامپیوتری موقعیت منطقه را شبیهسازی کرد و برنامه را یکبار با حضور پرندگان و یکبار بدون حضور آنان اجرا کرد. هنگامی که پرندگان وجود داشتند کامپیوتر شرایط را دقیقا همان طور که در واقعیت بود نشان داد. اما بدون حضور پرندگان طوفانی بزرگ در منطقه شکل میگرفت که باعث تخریب تقریبا 12 هکتار از آن منطقه میشد. در حقیقت پر زدن آن پرندگان باعث میشد که شرایط شکلگیری این طوفان پیش نیایند…
پس از مطالعات جدیتر و عمیقتر و شبیهسازی جو جهان آنان به نتیجهای رسیدند که مهمترین شعار نظریه آشوب نام گرفت. پروانهای در آفریقا بال میزند و گردبادی در آمریکای جنوبی شکل میگیرد. فشاری که بال زدن آن پروانه بر اتمسفر میآورد شاید بسیار ناچیز باشد، اما فرآیند تشدید باعث میشود که این فشار ناچیز و اندک به مرور و پس از طی مسافتی تبدیل به یک طوفان عظیم شود.
در جای دیگری، گروهی از دانشمندان علم ژنتیک مشغول مطالعه بر نقشه ژنتیکی قورباغهها بودند. آنان سعی داشتند تا نقشه ژنتیکی این موجودات را تهیه کنند و از آن در راه پیشرفت دانش ژنتیک استفاده کنند. برای جلوگیری از زاد و ولد قورباغهها و کنترل وضعیت آزمایشگاهی آنان تصمیم گرفتند که تنها از قورباغههای نر استفاده کنند. پس از حدود یک سال مطالعه ناگهان چیزی غریب اتفاق افتاد. روزی آنان متوجه شدند که پنج قورباغه به تعداد قورباغهها افزوده شده است!!!
پس از مطالعه آنان متوجه شدند که برای جلوگیری از انقراض نسل، در قورباغهها جهشی ژنتیکی اتفاق افتاده است و این گروه از قورباغه ها شش ماه از سال را نر و شش ماه را مادهاند. در فاصله تغییر جنسیت آنان در بدنشان تولید مثل میکنند و این امر باعث ایجاد شعار مهم دوم نظریه آشوب گشت؛ "زندگی برای بقا راه خود را خواهد یافت".
این نظریه در ابتدا تنها یک نظریه بود. اما مطالعات بعدی آنرا به یک تئوری تبدیل کرد. مطالعات بیشتر آن را به حد علم نیز رساندند. به طوری که امروزه از علم آشوب حتی در معماری و عمران نیز استفاده میشود. چرا که یکی از اصولی که این علم بیان میکند این است که هیچ چیز قابل پیش بینی نیست به دلیل این که حیات راه خود را خواهد یافت حتی اگر با دقت بسیار زیاد شرایط را کنترل کنیم، به این دلیل که خود ما نیز جزئی از مساله هستیم، دچار اشتباه خواهیم شد. مثال زیر را در نظر بگیرید:

شکل2-7: فرضیه آشوب.

اگر ما به دنبال این باشیم که در این شکل یک نظم و یک معادله پیدا کنیم شاید هیچگاه نتوان به فرمولی رسید. اما از آنجا که باید برای توضیح انحرافات خطی در این شکل الگویی قابل توضیح وجود داشته باشد با استفاده از هندسه غیر اقلیدسی به چندین فرمول میرسیم که بخش اعظمی از این شکل را توضیح میدهد، اما برای بقیه این شکل توضیحی نداریم. بنابراین دست به ایجاد شاخهای جدید در ریاضیات و هندسه میزنیم تا بتوانیم آن را توضیح دهیم. همین مساله به عدم قطعیت ختم میشود. یعنی ایجاد شرایط جدید باعث ایجاد علوم جدید میشود که گاهی تمام علوم قدیمی را زیر و رو میکند. حالا بیایید تا همان شکل را بطور کامل ببینیم:

شکل 2-8: فرضیه آشوب.

مشاهده میکنیم که تمامی بینظمی موجود در آن شکل منجر به نظمی بزرگ شد. یعنی ایجاد یک خط راست. اما به دلیل این که ما درون شکل قرار داشتیم نتوانستیم به نظم کلی آن پی ببریم و به اشتباه کشیده شدیم. عین همین مساله را میتوان در جهان جستجو کرد. دنیای اطراف ما پر از روابطی است که ما قادر به فهم آنان نیستیم و برای توضیح و توجیه آنان دست به ایجاد علوم مختلف میکنیم. علومی که هیچ کدام قطعیت ندارند و به گفته علم آشوب قابل پیش بینی نیستند…
بدین ترتیب طی 20 سال گذشته، در حوزه ریاضیات و فیزیک مدرن، روش علمی و تئوری جدید و بسیار جالبی به نام "آشوب" پا به عرصه ظهور گذاشته است. تئوری آشوب، سیستمهای دینامیکی بسیار پیچیدهای مانند اتمسفر زمین، جمعیت حیوانات، جریان مایعات، تپش قلب انسان، فرآیندهای زمین شناسی و … را مورد بررسی قرار میدهد. نگاره اصلی و کلیدی تئوری آشوب این است که در هر بینظمی، نظمی نهفته است. به این معنا که نباید نظم را تنها در یک مقیاس جستجو کرد؛ پدیدهای که در مقیاس محلی، کاملا تصادفی و غیرقابل پیش بینی به نظر میرسد چه بسا در مقیاس بزرگتر، کاملا پایا و قابل پیشبینی باشد[9].
نقاط تشابهی بین تئوری آشوب و علم آمار و احتمالات وجود دارد. آمار نیز به دنبال کشف نظم در بینظمی است. نتیجه پرتاب یک سکه در هر بار، تصادفی و نامعلوم است، زیرا دامنه محلی دارد. اما پیامدهای مورد انتظار این پدیده، هنگامی که به تعداد زیادی تکرار شود، پایا و قابل پیش بینی است. وجود چنین نظمی است که باعث زنده ماندن صنعت قمار است، وگرنه هیچ سرمایهگذاری حاضر نبود که در چنین صنعتی سرمایه گذاری کند. در واقع، قمار برای کسی که قمار میکند پدیدهای تصادفی و شانسی است(چون در مقیاس محلی قرار دارد) و برای صاحب قمارخانه، پدیدهای قابل پیشبینی و پایا است(چون در مقیاس بزرگتر این پدیده دارای نظم است) همینجا میتوان به مصادیقی از این تئوری در حوزه علوم انسانی اشاره کرد.
بسیاری از وقایع تاریخی که در مقیاس 20 ساله ممکن است کاملا تصادفی و بینظم به نظر برسند، ممکن است که در مقیاس 200 ساله، 2000 ساله یا 20000 ساله دارای دوره تناوب مشخص و یا نوعی نظم در علتها باشند( و البته نه لزوما به گونهای که مارکس معتقد است!!! ). در نگرش رفتارگرایی در حوزه روانشناسی، در واقع با نوعی تغییر مقیاس، به نظم رفتاری و قوانین آن دست مییابند و امکان پیشبینی و یا اصلاح اختلالات رفتاری فراهم میگردد، والا اگر رفتارهای منفرد افراد مد نظر باشد چیزی جز چند رفتار تصادفی و غیرقابل پیش بینی نخواهد بود. روش علمی(متدولوژی) که این تئوری در اختیار ما قرار میدهد، تغییر مقیاس در نگاه به وقایع است به گونهای که بتوان نظم ساختاری آن را کشف کرد. صد البته، نگاه جدید این منطق به نظم، بسیاری از جدالهای سنتی در مورد برهان نظم و … در فلسفه را نیز مورد چالش قرار میدهد.
موضوع جالب دیگری که در تئوری آشوب وجود دارد، تاکید آن بر وابستگی(یا حساسیت) به شرایط اولیه است. بدین معنی که تغییرات بسیار جزیی در مقادیر اولیه یک فرآیند میتواند منجر به اختلافات چشمگیری در سرنوشت فرآیند شود. مثال ساده زیر شاید جالب باشد:
اگر مسافری 10 ثانیه دیر به ایستگاه اتوبوس برسد نمیتواند سوار اتوبوسی شود که هر 10 دقیقه یک بار از این ایستگاه میگذرد و به سمت مترویی میرود که از آن هر ساعت یک بار قطاری به سوی فرودگاه حرکت میکند. برای مقصد مورد نظر این مسافر، فقط روزی یک پرواز انجام میشود و لذا تاخیر 10 ثانیهای این مسافر باعث از دست دادن یک روز کامل میشود. بسیاری از پدیدههای طبیعی دارای چنین حساسیتی به شرایط اولیه هستند. قلوه سنگی که در خط الراس یک کوه قرار دارد ممکن است تنها بر اساس اندکی تمایل به سمت چپ یا راست، به دره شمالی یا جنوبی بلغزد، در حالی که چند میلیون سال بعد، که توسط فرآیندهای زمین شناسی و تحت نیروهای باد و آب و … چند هزار کیلومتر انتقال مییابد، میتوان فهمید که آن تمایل اندک به راست و چپ به چه میزان در سرنوشت این قلوه سنگ تاثیرگذار بوده است. مثال بسیار آشنای دیگر، وابستگیهای جسمی و روانی انسانها به شرایط لقاح و مسائل ژنتیکی است[9].
اگر چه چنین وابستگی آشوبناک39 به شرایط اولیه را میتوان در بسیاری از وقایع جامعه شناسی(از جمله انقلابها) و روانشناسی و .. مشاهده کرد، لکن به جز یک حوزه(که جلوتر به آن اشاره خواهد شد)، تاکنون توجه خاصی بدین مسئله صورت نگرفته است. به این معنا که اغلب برای تمام طول حیات یک پدیده، وزن یکسانی از نظر تاثیرگذاری عوامل درونی و بیرونی در نظر گرفته میشود، در حالی که تئوری آشوب، نقش کلیدی را در شرایط و المانهای مرزی اولیه میداند. ادوارد لورنز، دانشمند مشهور هواشناسی، سالها پیش جمله مشهور خود را که بعدها به" اثر پروانه40 " مشهور شد، چنین عنوان کرده است: "در یک سیستم دینامیکی مانند اتمسفر زمین، آشفتگی بسیار کوچک ناشی از به هم خوردن بالهای یک پروانه میتواند منجر به طوفانهایی در مقیاس یک قاره بشود". در بسیاری از وقایع جامعه شناختی و سیاسی نیز میتوان به جای پیجویی عوامل بسیار پیچیده و نادیده گرفتن عوامل به ظاهر ساده، با جدی گرفتن عوامل به ظاهر بیارزش به تحلیل صحیحی نسبت به آن واقعه رسید.
پیشتر اشاره کردیم که در این مورد، در یک حوزه کار وسیعی صورت گرفته است. این حوزه، روانشناسی است و تئوری عظیم نابغه دنیای روانشناسی، فروید، دارای چنین رویکردی است. فروید ریشه تمامی رفتارهای انسانها در طول زندگی را متاثر از دوران کودکی(شرایط اولیه به زبان تئوری آشوب) میداند و با پیجویی این رفتارها تا دوران کودکی، به تحلیل این رفتارها میپردازد .علاوه بر مطالبی که ذکر شد، تئوری آشوب، با ارائه نظریه فرکتالها و ارائه مفهوم جدیدی از بعد فیزیکی و مفاهیمی مانند " خود تشابهی " و " خود تمایلی" ، دروازه جدیدی در کشف نظم در پدیدهها گشود.
اگرچه آشوب نظریه ای است که بر موضوعات گوناگون اجتماعی و سیاسی و اقتصادی نظر دارد، اما نیازمند زبانی برای تصویرسازی مفاهیم خود بود و این عرصهای بود که هندسه آشوب یا فرکتالها خلق کردند. بدین ترتیب یکی از خروجیهای نظریه آشوب هندسه فرکتالهاست.
هندسه فرکتالی وسیله و مفهومی نوین است که امکان توصیف ریختهای طبیعی را میسر کرده است. اشکال هندسی طبیعی همچون کرات آسمان و درخت کاج را به آسانی میتوان با کره و مخروط توصیف کرد ولی بسیاری دیگر از اشکال طبیعی به اندازه ای پیچیده هستند که حتی با ترکیبی از اشکال هندسه اقلیدسی قابل توصیف دقیق نیستند. شکل گل کلم، ریخت کوهها، رویه یک فلز در مقیاس های میکروسکوپی نمونه هایی از شکل های طبیعی هستند که توصیف آنها تنها توسط هندسه فرکتالی ممکن است.
کشف مفاهیم فرکتالی ابزاری نیرومند در اختیار دانشمندان برای همسنجی پدیده های پیچیده طبیعی قرار داد. برای نمونه با کاربرد مفاهیم برخالی میتوان شکل رودخانه های رشته کوه های البرز را با شکل رودخانه های کوه های زاگرس مقایسه کرد و یا میتوان تغییرات فعالیت های لکه های خورشیدی در زمان را توصیف و با تغییرات دمای جو زمین هم سنجید. مسلماً مقایسه طول رودخانه های البرز با درازای رودخانه های زاگرس توصیف دقیقی نخواهد بود زیرا تنها یک جنبه از هندسه پیچیده رودخانه های نامبرده را مورد مقایسه قرار می دهد. مقایسه همخوانی بسامدهای سازنده تغییرات تعداد لکه های خورشیدی در زمان با تغییرات دمای جو در زمان میتواند همبستگی این دو پدیده نامبرده را تا اندازه ای معین کند ولی نمیتواند معیاری یکتا که ارتباط میان بسامد های سازنده این دو پدیده را معین می کند ارائه دهد.

2-3) بررسی خصوصیات فرکتالها
هندسه فرکتالی یک مفهوم نوین است که حرکت اشکال در فضا را ثبت میکند و یا ناهمواری دنیا و انرژی و تغییرات دینامیک آن را نشان میدهد. این هندسه برای نخستین بار از سوی بنویت مندلبروت در سال 1980 معرفی گردید. بنیاد هندسه فرکتالی بر این فرض استوار است که اشکال طبیعی خود متشابه هستند و از تکرار قانونمند یک بلوک آغازین ایجاد گردیده اند. فرکتالها به دو دسته مصنوعی(ریاضی) و طبیعی تقسیم شده و به زبان ساده، دارای 3 خاصیت عمومی هستند:
I. خود متشابه 41
II. تشکیل از راه تکرار42
III. بعد کسری43

در زیر این خصوصیات را جداگانه شرح خواهیم داد :
I . خود متشابه : شیئی را دارای خاصیت خود متشابهی اکید میگوییم، هرگاه قسمتهایی از آن با یک مقیاس معلوم، یک نمونه از کل شیئی باشد[49].
میدانید که تشابه، در واقع یکسانی اشکال در عین متفاوت بودن اندازه آنهاست. به زبان سادهتر اگر بتوانید با بزرگ یا کوچک کردن دو شکل آنها را درست مثل هم کنید، آن دو متشابهاند. اما شکلهای خود متشابه کدامها هستند؟ اشکال زیادی وجود دارند که فرکتالی نیستند اما خود متشابهاند. به شکل(2-9) دقت کنید.

شکل کلی آن یک ذوزنقه است و خودش از ذوزنقههای کوچکتر کنار هم پدید آمده است. این یک مثال از اشکال خود متشابه است. چنین ساختارهایی که هر جز آن با کل مجموعه یکی است و فقط در مقیاس تفاوت دارند را ساختارهای خود متشابه میگویند. اگر تا به حال به یک برگ سرخس نگاه کرده باشید، میتوانید متوجه تشابه اجزای مختلف آن شوید. ساختار کل ساقه همانند یک برگ و ساختار یک برگ همانند یک جزء کوچک آن است[49].

شکل2-10: خود متشابهی در فرکتال کخ.

II . تشکیل از راه تکرار : مقصود از تشکیل از راه تکرار چیست؟
یعنی برای درست کردن یک فرکتال میتوانیم یک شکل معمولی هندسی، مثلاً یک خط، را برداریم و با آن یک شکل پیچیدهتر بسازیم. سپس با آن شکل به دست آمده شکل پیچیدهتری بسازیم و همین طور به این کار ادامه دهیم. شکل(2-11) طریقه تشکیل شکل(2-10) را که از راه تکرار بوده است را نشان میدهد. اشکال فرکتالی به این طریق به وجود میآیند و برنامههای کامپیوتری متعددی برای ایجاد آنها نوشته شده است. فرکتالها معروفی تا به حال ارائه شدهاند که به عنوان مثال میتوان به ساختارهای فرکتالی زیر اشاره کرد[48]:
> کانتور
> دانه برف کخ
> مثلث سرپینسکی
> فرش سرپینسکی
> اژدهای هرتر- های وی
> مجموعههای جولیا و مندلبروت
سادهترین نوع فرکتال، فرکتال کانتور است. پاره خطی به طول یک واحد در نظر بگیرید و طول آن را به سه قسمت تقسیم کرده و قسمت وسطی را حذف کنید. حالا دو خط داریم که طول آنها یک سوم طول اولیه است. همین عمل را با هر کدام از این پاره خطها انجام میدهیم. یعنی طول هر کدام را ثلث میکنیم و قسمت وسطی را حذف میکنیم. میتوان با کامپیوتر برنامهای نوشت که این عملیات را چندین بار پیاپی انجام دهد. اگر این عملیات را بیشمار بار انجام دهیم(کاری که از عهده کامپیوتر خارج است) شکلی بدست میآید که مجموعه کانتور نام دارد. اگر به کل شکل نگاه کنیم، ساختاری میبینیم که تا بینهایت ادامه دارد. اگر به سمت راست یا چپ خط دوم شکل نگاه کنیم، ساختاری میبینیم که باز هم تا بینهایت ادامه یافته و درعین حال، کاملا شبیه شکل کلی خود است.
یکی از مشهورترین انواع فرکتالها توسط"هلگ فون کخ" در سال 1904 طراحی شد، در این نوع فرکتال، ابتدا یک پاره خط به طول یک واحد در نظر میگیریم و آن را به سه قسمت تقسیم میکنیم. سپس به جای ضلع وسط دو ضلع مثلث متساوی الاضلاع را قرار میدهیم و این کار را همین طور ادامه میدهیم. فرکتال کخ نیز یک نوع فرکتال خود متشابه است.

شکل2-11: نحوه تشکیل فرکتال کخ از طریق تکرار

اگر این عمل را روی اضلاع یک مثلث متساوی الاضلاع انجام دهیم، شکل بسیار زیبایی پدید می آید که "دانه برف کخ " نام دارد.

شکل 2-12: ساختار فرکتالی دانه برف کخ.

مجموعه معروف مندلبرت که به عنوان اولین مجموعه فرکتال مطرح شد، به صورت شکل(2-13) است :
شکل2-13: مجموعه مندلبرت.

III . بعد کسری : این اجسام نه یک بعدیاند، نه دو بعدی و نه سه بعدی. اینها ابعادی کسری دارند؟ همانطور که میدانید، یک نقطه بعد ندارد، یک خط، شکلی یک بعدی است، یک صفحه دو بعد دارد. و در آخر شکلهای حجیم، سه بعد دارند.
اما فرکتالها میتوانند بعد کسری داشته باشند! مثلاً 1.6 یا 2.4 ! حتما از خود میپرسید که چطور چنین چیزی امکان دارد؟ بدین منظور لازم است که مفهوم بعد اشکال اقلیدسی را بررسی نماییم[3,9].
– مفهوم بعد:
اگر یک پاره خط را نصف کنیم چه پیش میآید؟

حالا دو خط داریم که درست مثل هم هستند.
اگر هر دو بعد یک مربع را نصف کنیم چطور؟ حالا چهار مربع هم اندازه داریم.

با نصف کردن هر سه بعد یک مکعب به هشت مکعب کوچکتر میرسیم.

به جدول زیر دقت کنید:
جدول2-1.
شکل
بعد
تعداد اشکال متشابه حاصله
پاره خط
1
21=2
مربع
2
22=4
مکعب
3
23=8

چه الگویی وجود دارد؟ به نظر میرسد که بعد، همان " توان " است. یعنی برای پیدا کردن تعداد اشکال حاصله باید 2 را به توان بعد آن شکل برسانیم.

سپس میتوانیم یک خط دیگر به این جدول اضافه کنیم:

جدول2-2.
شکل
بعد
تعداد اشکال متشابه حاصله
هر شکل خود متشابه
d
n=2d

بنابراین بعد هر جسم خود متشابه را میتوان اینگونه تعریف کرد: نسبت لگاریتم تعداد اشکال خود متشابه به لگاریتم عامل بزرگ نمایی.
بدین ترتیب مثلا در مجموعه کانتور، چون با دو مجموعه کانتور میتوان یک مجموعه کانتور با طول سه برابر مجموعههای اولی ساخت داریم:
D=log2 / log3=0.631
یعنی یک مجموعه کانتور موجودی 0.631 بعدی است. حال اگر به شکل مجموعه کانتور نگاه کنیم ما میبینیم که این مجموعه نه یک خط کامل است که بعد یک داشته باشد و نه یک نقطه که بعد صفر داشته باشد بلکه موجودی بین آن دو است.
برای فرکتال کخ که بیشتر از خط (بعد 1) و کمتر از صفحه(بعد 2) است، داریم:
D=log4/log3=1.262
یا برای فرکتال سرپینسکی که فضای بیشتری را نسبت به فرکتال کخ میپوشاند، اما به یک صفحه کامل نمیرسد، داریم:
D=log3/log2=1.58
در فرکتالها این بعد فرکتالی مهم است و نه مقیاس. زیرا در هر اندازهای، این بعد فرکتالی حفظ میشود و بیانگر خاصیت اصلی فرکتال است. همین امر کاربرد فرکتالها را در علم امروزی زیاد کرده است. در کیهان شناسی، ساختار یک کهکشان با یک خوشه کهکشانی(مجموعهای از هزاران کهکشان) و یک خوشه نیز با یک ابر خوشه(مجموعهای از هزاران خوشه کهکشانی) قابل قیاس است. رشد نمونههای میکروبیولوژیکی در محیطهای کشت و یا نحوه کارکرد پلیمرهای صنعتی(مثل لاستیکها) و پلیمرهای حیاتی(مثل DNA و پروتئینها) از مواردی هستند که دانش فرکتالها را میتوان در آنها به کار برد[9].
تا اینجا سعی کردیم مفهوم بعد فرکتالی را با زبانی ساده و برای ساختارهای ساده فرکتالی توضیح دهیم اما برای ساختارهای پیچیده چه باید کرد؟

2-4 ) روش تعیین بُعد ساختارهای فرکتالی:
در سال 1975 برای اولین بار تعریفی از " فرکتالها و ابعاد کسری آنها" در کتابی از مندلبروت تحت عنوان " اجسام فرکتالی، شکل، خط و بُعد" منتشر شد. فرکتال برخی ویژگیهای هندسی نامنظم اشکال و جامدات را که در تمام مقیاسها مشابه به نظر میرسند، تشریح میکند. بسیاری از اجسام محیط اطراف ما دارای چنان ساختار پیچیدهای هستند که اندازهگیری طول، مساحت یا حجم آنها به روشهای متداول غیر ممکن است. اما با وجود این، روشی برای اندازهگیری خواص هندسی آنها وجود دارد. این کار را میتوان با برآورد چگونگی افزایش طول، سطح یا حجم وقتی که اندازهگیری با دقت بهتری انجام میشود، انجام داد. فرض اصلی این است که دو کمیت؛ از یک طرف طول، سطح و یا حجم و از طرف دیگر میزان دقت اندازهگیری، به دلخواه تغییر نمیکنند، بلکه چنان تغییر میکنند که امکان تعیین بُعد فرکتالی D را فراهم میسازند[3].
بعد فرکتالی D(A) جسم A را میتوان به چند روش تعیین کرد. معلوم شده است بعد D ، که بعد جعبهای نامیده میشود، در دنیای اشیای واقعی کمیت مفیدی است. به منظور تعیینD ، میتوان جسمی یک بُعدی مانند بخشی از یک خط راست به طول L را در نظر گرفت. این پاره خط را میتوان با N(s) جعبه یک بُعدی به طول ضلع S کاملاً پوشاند.
(2-1)

در نتیجه داریم:

همین طور در حالت دو بعدی مربعی به ضلع L در نظر میگیریم، که میتوان آن را در
(2-2)

جعبه پوشاند. برای یک مکعب توان L برابر 3 است و به همین ترتیب برای ابعاد بالاتر.
بدیهی است که برای اجسامی با شکل منظم مانند پاره خط، مربع، مستطیل، مکعب و توپ، این توان یک عدد صحیح است.
همین قاعده را میتوان برای اشیایی با شکل نامنظم مانند یک لکه جوهر یا خط ساحلی نیز به کار برد. در این موارد مشاهده خواهیم کرد که نمای فوق، که همان بُعد فرکتالی شبه جعبهای است، میتواند مقداری کسری باشد. در حالت کلی داریم :
(2-3)

اگر از طرفین معادله(2-3)، لگاریتم بگیریم، خواهیم داشت:
(2-4)

و در حد s کوچک میتوان جمله شامل L را نادیده گرفت. بنابراین بعد شبه جعبهای به صورت زیر تعیین می شود:
(2-5)

درعمل برای تعیین بُعد فرکتالی جسم مورد نظر(یک بُعدی، دوبُعدی، و مانند آنها)، آن را با شبکهای با بُعد مناسب و مقدار ثابت S که به طور منظم تغییر میکند، میپوشانند. برای هر شبکه تعداد جعبههای N(s) که جسم مورد مطالعه را پوشانده است یا حداقل تا اندازهای آن را لمس میکنند، میشماریم. سپس نتایج شمارش را در دستگاه مختصات logN(s) بر حسب رسم میکنیم. با تقریب این نقاط با یک تابع خطی، به سادگی میتوان بُعد D را به عنوان شیب خط حاصل تعیین کرد( شکل 2-14).

D=ton α =

logN
log

log

log
log log

شکل2-14: روش تعیین بعد فرکتالی

فصل سوم

فشردهسازی تصاویر بر اساس تئوری فرکتالی

3-1) مقدمه
در فصل قبل به بررسی برخی روشهای موجود، که در گذشته برای فشردهسازی تصاویر ابداع شدهاند پرداختیم. هدف ما در این فصل، ارائه پایههای تئوریکی و مراحل عملی روشی جدید برای فشردهسازی تصاویر است. تکنیکهای مطرح شده در این فصل بر اساس پارهای از ایدههای موجود در روشهای پیاده شده قبلی و نکات شکل گرفته از تئوری فرکتال و هندسه فرکتالی و استفاده از سیستم توابع تکراری میباشد. در بخشهایی از فصلهای قبل به تشریح تئوری فرکتال پرداختیم. در این فصل براساس آنها یک روش عملی جهت فشردهسازی تصاویر ارائه میشود. همچنین در خاتمه فصل بررسی بازسازی تصاویر و نحوه ارزیابی پارامترهای مختلف خواهد آمد.

3-2) تولید فرکتالهای خطی با استفاده از ایده ماشین MRCM 44
در فصلهای قبل گفته شد که فرکتالهای خطی بر اساس تکرار یک سری تبدیلات خطی و معین ریاضی شکل میگیرند، که به صورت تکراری بر روی یک ورودی اولیه عمل میکنند تا خروجی نهایی که همواره یک شکل ثابت است تولید شود. دراین بخش در نظر داریم که برای بیان دقیقتر مراحل مختلف و نحوه عمل الگوریتمهای مربوط مطابق آنچه در اکثر منابع مربوط به فرکتالها مرسوم است، این تبدیلات تکراری را با ماشین فرضی مدل کنیم. این ماشین بنام ماشین کپی تقلیل چندگانه MRCM معروف است[11].
ماشین فرضی ما دارای چندین لنز است که هر کدام از آنها قادرند از تصویر اولیهای که در ماشین قرار میگیرند یک کپی تهیه کرده سپس آن را به نسبت معین کوچک نموده و تصویر کوچک شده را به اندازه مورد نیاز در حول هر یک از محورها چرخانده و نهایتا آن را در جای دلخواه در صفحه قرار دهند. میزان کاهش، دوران، انتقال و نیز تعداد لنزها(بسته به شکلی که میخواهیم تولید کنیم) توسط الگوریتم تعیین میشوند.
فرض کنید تصویر اولیه مثلثی باشد که بر روی یک صفحه کاغذ رسم شده است و ماشین دارای سه لنز جداگانه باشد که هر کدام از آنها تصویر ورودی را نسبت 2/1 کوچک میکنند، بدین ترتیب از نمونه اولیه سه مثلث با طول اضلاع نصف خواهیم داشت(شکل 3-1). در مرحله بعد این لنزها هر کدام تصویر مربوطه را چنان قرار میدهند که سه مثلث جدید به صورتی که در شکل خروجی دستگاه مشخص شده است هر کدام در یک راس مثلث قبلی قرار میگیرند. بدین ترتیب سطح مثلث قبلی دقیقا به چهار مثلث مساوی تقسیم میشوند که قسمت وسط به صورت یک شکاف خالی میباشد[11].
شکل (3-1 ) طرح سیستم MRCM.

سپس این تصویر تولید شده بعنوان ورودی دوباره به دستگاه، داده میشود و عمل مرحله قبل بر روی تصویر جدید تکرار میشود.
در شکل(3-2) سه مرحله از عملیات ماشین برای سه شکل اولیه متفاوت دیده میشود.

شکل (3-2) مستقل بودن MRCM از تصویر اولیه.
ماشین MRCM دارای یک خاصیت بسیار جالب است که آنرا با یک مثال نشان میدهیم. فرض کنید در ماشین فوق تصویر اولیه یک دایره باشد. برای جداکردن تصاویری که توسط لنزهای متفاوت تولید میشود از رنگهای متفاوت استفاده شده است. نتیجه جالبی که از این شکلها استنباط میشود این است که مستقل از آنکه چه شکل اولیهای به ماشین میدهیم دنبالهای از تصاویر حاصل میشوند که همیشه به سمت یک تصویر نهایی میل میکنند. به این تصویر نهایی، جذب کننده45 ماشین میگویند. نکته مهم دیگر آن است که در صورتی که تصویر اولیه جذب کننده ماشین باشد، تصاویر تولید شده در مراحل مختلف تفاوتی با تصویر اولیه ندارد. بنابراین میتوان گفت که جذب کننده، تغییر ناپذیر میماند. ماشین MRCM یک سیستم با فیدبک است که همواره به یک خروجی ثابت همگرا میشود و تنها پیش شرط لازم برای همگرا بودن آن این است که لنزهای ماشین، تصاویر را کوچک کنند.

3-3)تبدیلات آفینی انقباضی و کدهای IFS 46
در بخش قبل دیدیم که ماشین MRCM بر روی تصویر اولیه یک سری تبدیلات پایه ساده انجام میداد و به شرط آنکه مجموعه تبدیلات به صورتی بود که شکل حاصل از هر لنز کوچکتر از تصویر اولیه میشد به یک تصویر ثابت نهایی میرسیدیم. در این بخش نشان میدهیم که میتوان عملیات ماشین فرضی را با یک سری از تبدیلات ماتریسی مدل کرد. این تبدیلات بعنوان تبدیلات آفینی شناخته میشوند. با توجه به آنکه تبدیلات در ماشین به صورتی بودند که: اولا تصویر در هر مرحله کوچکتر میشد و ثانیا شکل تولید شده در هر مرحله توسط یک لنز، مشابه تصویر ورودی بود(مثلا تبدیل یافته یک دایره همیشه یک دایره است) این تبدیلات را تبدیلات آفینی انقباضی خطی نیز مینامند[50].
فرض کنید که صفحه شامل تصویر را با یک سیستم مختصات دکارتی نشان دهیم. سیستم دارای دو محورy,x میباشد و هر نقطه مفروض مانند P در صفحه xy را میتوان بوسیله مختصات آن یعنی P(x,y) معین نمود. یک نگاشت خطی F به تبدیلی گفته میشود که دارای دو خاصیت زیر باشد:
1- F(P1+P2) = F(P1) + F(P2)
2- F(SP) = SF(P)
که S یک عدد حقیقی و P2,P1 دو نقطه در صفحه مختصات میباشد. این تبدیل، نقطه P(x,y) را به نقطه F(P(x,y)) میگارد.
یک تبدیل آفینی خطی بصورت ساده، ترکیبی از یک تبدیل خطی ساده به اضافه یک انتقال میباشد. برای تبدیل آفینی W(P) ، داریم : W(P) = F(P) + Q که F یک تبدیل خطی و Q یک جفت عدد ثابت است که انتقال در x , y را نشان میدهد. اگر داشته باشیم که : P = (x,y) و W(P) = (u,v) آنگاه : v=cx+dy+f , u=ax+by+e یا بصورت معادل W(x,y)=(ax+by=e,cx+dy+f) که این تبدیل را میتوان به فرم ماتریسی زیر نشان داد. در شکل(3-3) اثر اعمال تبدیل به تصویر دیده میشود .
(3-1)

شکل3-3: تبدیل آفینی انقباضی.

ماتریس تبدیل آفینی انقباضی را میتوان به فرم مثلثاتی زیر نشان داد :

در این حالت r نسبت انقباض یا کوچک کردن در محورx و s انقباض در محور y و αدوران در محورx و β دوران در محور y خواهد بود. برای مثال به موارد زیر توجه کنید.
الف ) β=0 , α=II , 0<r<1, s=r نشانگر کاهش اندازه تصویر به اندازه r و معکوس کردن به نسبت محور y ها میباشد .
ب ) s=r >0 و'90 = α= β نشانگر کاهش اندازه تصویر با نسبتr و دوران در خلاف عقربههای ساعت به اندازه 90 درجه میباشد.
لنزهای سیستم MRCM را از نظر ریاضی میتوان با مجموعهای متشکل از N تبدیل آفین بصورت W1,…,WN توصیف نمود. برای یک تصویر اولیه داده شده به ماشین مانند A، کپیهای آفینی کوچک شده از آن W1(A),…,WN(A) تولید میشود و نهایتا ماشین این کپیها را بر روی هم قرار داده و یک تصویر خروجی ایجاد میکند که آنرا با W(A) نمایش میدهیم و داریم که:

W(A) = (A) U(A)U……U(A)
(3-5)

که در رابطه فوق U نمایانگر اجتماع است.
W بعنوان اپراتور هاکینسون47 شناخته میشود. عمل ماشین MRCM بر روی تصویر خروجی در حلقه فیدبک، معادل با اعمال کردن متوالی اپراتور W به تصویر تولید شده در هر مرحله برای تولید تصویر بعدی میباشد. این اساس سیستم توابع تکراری (IFS) میباشد. در این سیستمها با یک تصویر اولیه اختیاری A0 شروع میکنیم سپس دنباله A2=W(A1),A1=W(A0) الی آخر را بدست میآوریم. با توجه به مطالب فوق قضیه توابع تکراری را میتوان بصورت زیر خلاصه نمود.

قضیه :
فرض کنید w1,…,wN ، N تبدیل آفینی انقباضی و A یک مجموعه از نقاط در صفحات مختصات(در این جا ما A را بعنوان یک تصویر میشناسیم) و W(.) اپراتور هاکینسون باشد. دنباله را که با اعمال متوالی اپراتورW(.) حاصل میشود یک IFS مینامیم. این IFS دنبالهای از تصاویر تولید میکند که همیشه به سمت یک تصویر نهایی A∞ همگرا میشود که آن را جذب کننده کدهای IFS نامیده و این تصویر، تحت اعمال همان IFS تغییر ناپذیر میماند. یعنیW(A∞)= A∞ که ما آنرا نقطه ثابت48 اپراتور W مینامیم.
در این مرحله ممکن است برای خواننده چند سوال پیش آید. اول آنکه آیا همیشه یک سیستم IFS، تولید یک شکل فرکتالی خواهد نمود؟ دوم آنکه، تغییر دادن تعداد تبدیلات(بعنوان مثال عدد سه در شکل(3-1)) چه تاثیری دارد؟ و نهایتا آنکه، آیا همیشه خروجی یک سیستم IFS واحد، در شرایط مختلف یکسان خواهد بود؟
جواب سوال اول منفی است. بدین معنی که میتوان کدهای IFS متعددی داشت که شکلهای هندسی معمولی تولید میکنند. در این موارد بدیهی است که روش توصیف معمولی به مراتب سادهتر از توصیف با استفاده از کدهای IFS میباشد. در جواب سوال دوم، میتوان گفت که هر تغییر در هر تعداد کدهای IFS(یا بصورت معادل در تعداد لنزهای MRCM )، و نحوه تبدیلات هر کدام منجر به تولید خروجی متفاوت خواهد شد. درجواب سوال سوم، باید گفت که ریاضیدانانی مانند مندلبرات و مایکل بارنسلی نشان دادهاند که به شرط انقباضی بودن تبدیلات آفینی بکار رفته، مستقل از ورودی اولیه همواره سیستم به یک خروجی واحد همگرا خواهد شد. البته همگرائی به معیارهای سنجش فاصله از خروجی مطلوب بستگی دارد که در بخشهای بعد این مسئله را به صورت مشروحتری بررسی خواهیم نمود. در طول این بخش به کرات انقباضی بودن تبدیلات مورد تاکید قرار گرفت. بنابراین مناسب به نظر میرسد که آنرا بصورت ریاضی و دقیق تعریف کنیم.
فرض کنید که W1 تا WN تبدیلاتی باشند که بر روی نقطه zєR² عمل کرده و W(z)єR² را تولید میکنند. اگر فاصله دو نقطه z2 , z1 را با تابع d(z1.z2) نشان دهیم، تبدیلات W1 تا WN را انقباضی مینامیم اگر برای 0≤k<1 رابطه زیر برقرار باشد:

d(.) < K×d ()
(3-6)

3-4) کدهای IFS و تولید تصاویر خود متشابه
در بخش قبل با تعریف کدهای IFS آشنا شدیم. در این بخش هدف ما بررسی نحوه تولید تصاویر خود متشابه با استفاده از کدهای IFS میباشد. برای تولید هر شکل فرکتالی، بسته به اجزای تشکیل دهنده، تعداد تبدیلات بکار رفته متفاوت است و ضمنا نحوه قرار گرفتن اجزاء، پارامترهای هر تبدیل را تعیین میکند. برای تولید یک شکل با استفاده از کدهای IFS معمولا از الگوریتمی استفاده میشود که به الگوریتم تکرارتصادفی49 یا بازی آشوبی50 معروف است .در ادامه این بخش به توصیف این الگوریتم به زبانی ساده خواهیم پرداخت.
فرض کنید که یک کد IFS برای تولید تصویر مورد نظر شامل N تبدیل بصورت W1 تا WN باشد که هر یک از این تبدیلات وظیفه تولید بخشی از تصویر نهایی را بر عهده دارد. این اجزاء ممکن است از نظر اندازه یکسان نباشد. برای روشن شدن موضوع از یک مثال استفاده میکنیم. یکی از معروفترین شکلهای فرکتالی، برگ سرخس بارنسلی است که آنرا در شکل(3-4) نمایش دادهایم. برای تولید این تصویر به چهار تبدیل نیاز داریم که طرح
مقدماتی هر یک در شکل(3-4) آماده است. همچنانکه در شکل نشان داده شده، سطحی که هر کدامیک از این تبدیلات میپوشاند متفاوت است.

شکل نهایی اولین مرحله اعمال تبدیلات شکل اولیه
شکل3-4: برگ درخت بارنسلی.

یک روش ممکن برای تولید این تصویر آن است که از یک شکل اختیاری مثلا A0 در صفحه مختصات دکارتی شروع کرده ابتدا تبدیل W1 را بر آن اعمال کنیم، بدین ترتیب شکلW1(A0) بدست میآید. سپس W2 و به همین ترتیب، تبدیلهای W3 و W4 را اعمال کنیم و دوباره کار را با اعمال W1 از نو تکرار کنیم. نشان داده شده است که استفاده از این روش برای بدست آوردن یک شکل مطلوب ممکن است زمان فوقالعاده زیادی نیاز داشته باشد
(مثلا 10^10 سال). برای حل این مشکل همچنانکه قبلا اشاره شد الگوریتم بازی آشوبی پیشنهاد شده است که بطور خلاصه به توصیف آن میپردازیم. در این روش ابتدا با یک نقطه اولیه در صفحه مختصات شروع کرده و بصورت متوالی تبدیلات W1 تا WN را اعمال میکنیم. اعمال تبدیلات در هر مرحله به جای نقطه اولیه به نتیجه تبدیل قبل اعمال میشود. در این الگوریتم معمولا تعدادی از نقاط اولیه را نادیده میگیرند. دلیل این امر آن است که از همگرایی نقاط مطمئن شوند. یک اشکال این روش آن است که سطح بخشهای مختلف، یکسان پوشیده نمیشوند. بعنوان نمونه در شکل(3-4)، چون سطح W1 بمراتب بیشتر از تبدیلات دیگر است نقاط داخل آن پراکندهتر بنظر میرسند و شکل اصلی بدرستی بازسازی نمیشود. برای رفع این مشکل معمولا به هر یک از تبدیلات، احتمالی به صورت 0<Pi<1 نسبت میدهند که این احتمال متناسب با سطح زیر تصویر مربوط است. مجموع احتمالات مرتبط به همه تبدیلات باید برابر یک باشد. در این حالت بجای اعمال کردن متوالی تبدیلات، هر بار بصورت تصادفی یک تبدیل انتخاب میشود. هر چه پارامتر احتمال متناسب با آن تبدیل، بزرگتر باشد امکان انتخاب آن تبدیل بیشتر است. با توجه به آنکه پدیده انتخاب یک تبدیل و نقطهای که تبدیل به آن اعمال میشود تصادفی هستند. این روش را الگوریتم تکرار تصادفی یا بازی آشوبی مینامند. اینکه چگونه الگوریتم تکرار تصادفی، مستقل از نحوه ترتیب انتخابهای تصادفی همواره یک تصویر را ایجاد میکند ابتدا بوسیله شبیهسازی کامپیوتری و سپس توسط جان آلتون بصورت تئوریک اثبات شد. با استفاده از این الگوریتم میتوان در چند ثانیه تصویری بر روی مانیتور کامپیوتر تولید نمود که دارای ظاهر کاملا مطلوبی باشد. در جدول(3-1) چند دسته کد IFS و احتمالهای مربوطه نشان داده شدهاند.

جدول3-1: کد های IFS چند شکل معروف.

کدهای IFS برای یک سرخس
W a b c d e f p
1 0 0 0 0/16 0 0 0/01
2 0/2 -0/26 0/23 0/22 0 1/6 0/07
3 -0/15 0/28 0/26 0/24 0 0/44 0/07
4 0/85 0/04 0/04 0/85 0 1/6 0/85

کدهای IFS برای هر یک مثلث Sierpinski
W a b c d e f p
1 0/5 0 0 0/5 0 0 0/33
2 0/5 0 0 0/5 1 0 0/33
3 0/5 0 0 0/5 0/5 0/5 0/34

کدهای IFS برای یک درخت فراکتالی
W a b c d e f p
1 0 0 0 0/5 0 0 0/05
2 0/1 0 0 0/1 0 0/2 0/15
3 0/42 -0/42 0/42 0/42 0 0/2 0/4
4 0/4 0/42 -0/42 0/42 0 0/2 0/4

کدهای IFS برای یک مربع
W a b c d e f p
1 0/5 0 0 0/5 0 0 0/25
2 0/5 0 0 0/5 0/5 0 0/25
3 0/5 0 0 0/5 0 0/5 0/25
4 0/5 0 0 0/5 0/5 0/5 0/25

3-5) کد کردن تصاویر معمولی با استفاده از تئوری فراکتالها
در بخشهای قبل دیدیم که میتوان بوسیله مجموعهای از تبدیلات آفینی انقباضی(بصورت کدهای IFS ) تصاویر واقعی زیبا و جذابی را بوجود آورد. حال این سوال به ذهن میرسد که اگر قادر باشیم با استفاده از یک الگوریتم ساده و کد IFS مربوطه تصویری واقعی مانند برگ سرخس، کوه و یا ابر تولید کنیم، آیا میتوان روشی ابداع نمود که با استفاده از آن بتوان تصاویر پیچیده را بصورت کدهای IFS خلاصه نمود؟ مزیت این کار مشخص است زیرا در صورتی که بتوانیم با استفاده ازمجموعهای از کدهای IFS یک تصویر واقعی را دوباره ایجاد کنیم و یا حتی خطای قابل قبول آنرا تقریب بزنیم قادر خواهیم بود که تصاویر را با نسبت بسیار بالایی فشرده و کد کنیم. این همان مطلبی بود که نظر ریاضیدان معروف انسیتوی جورجیا مایکل بارنسلی را بخود معطوف کرد و در زمانی که اغلب افراد به دنبال پیدا کردن کدهای IFS برای تولید تصاویر جدید بودند تلاش کرد که تصاویر پیچیده واقعی را بوسیله کدهای IFS بازسازی51 کند.
علاوه بر فشردهسازی تصاویر، آنالیز تصاویر و تشخیص اجزای آن در بسیاری از کاربردهای صنعتی و نظامی حائز اهمیت است. در بسیاری از موارد جهت اتوماسیون یک روند، معمولا از شبیهسازی عملیات مغز انسان استفاده میشود. همچنانکه میدانیم سرعت مغز انسان در تشخیص تصاویر پیچیده برتر از هر کامپیوتری است. بعنوان مثال، مغز انسان قادر است در کسری از ثانیه تصاویر بسیار پیچیده مانند یک درخت بلوط را از یک درخت سیب تشخیص دهد. مشاهدات قبلی در زمینه فرکتالها ممکن است ما را به این نتیجه رهنمون کند که تصاویر فوق تنها با معیارهای هندسی معمول پیچیده هستند ولی ممکن است مغز انسان با استفاده از هندسه فرکتالی آنها را با مجموعه اطلاعات بسیار خلاصهای کد کند. بنابراین کدینگ فرکتالی ممکن است در آنالیز تصاویر نیز بتواند به ما کمک کند.
تصاویر سیاه و سفید چند سطحی که از این بخش به بعد مورد بررسی قرار میگیرند با تصاویر فرکتالی دو سطحی که تا به حال مورد نظر بودند تا اندازهای متفاوت هستند. تصاویری مانند برگ سرخس بارنسلی یا مثلث سیرپینسکی در واقع تصاویر سیاه و سفید دو سطحی بودند و علاوه بر آن همواره قادر بودیم که اجزایی در این تصاویر پیدا کنیم که تبدیل یافته کل تصویر اصلی باشند. در تصاویر سیاه و سفید چند سطحی علاوه بر مختصات y,x یک مشخصه دیگر که عبارت از سطح روشنایی است برای هر نقطه از تصویر وجود دارد. علاوه بر آن خود تشابهی با آن مفهوم قبلی در تصاویر واقعی وجود ندارد. در این بخش ما به توسعه ایدههای موجود جهت ارائه الگوریتمی که بتواند بصورت اتوماتیک تصاویر سیاه و سفید چند سطحی را فشرده کند خواهیم پرداخت[48].
3-5-1 ) خود تشابهی در تصاویر معمولی
در بخش قبل گفتیم که تصاویر چند سطحی با تصاویر سیاه و سفید که توسط IFS های معمول ایجاد میشدند متفاوتند. از دیدگاه فشردهسازی این تفاوت شامل دو جنبه مختلف است. در این بخش این موضوع را بیشتر مورد بررسی قرار میدهیم[49].
اولین جنبه تفاوت میان آنها این است که در تصاویر معمولی مانند منظره، تصویر انسان و یا تصویر یک ساختمان خود تشابهی به آن صورتیکه در مثلث سیرسپینکی یا برگ سرخس بارنسلی وجود داشت قابل تشخیص نمیباشد. یعنی نمیتوان تصویر را به اجزایی تقسیم نمود که تبدیل یافته آفینی کل شکل باشند. اما با کمی دقت، در هر تصویر اجزایی یافت میشود که تحت تبدیلات مناسب، قسمتهای کوچکتری از همان تصویر را بخوبی میپوشانند. این بدین معنی است که میتوان تبدیلاتی از بخشهایی از تصویر به قسمتهای دیگری از آن تعریف نمود که هر چند تصویر را دقیقا بازسازی نمیکنند اما با خطای قابل قبولی آنرا تقریب میزنند. حال این سئوال مطرح میشود که در چه دستهای از تصاویر میتوان این خود تشابهی محلی را مشاهده نمود؟ نتایج تجربی نشان میدهد که در اغلب تصاویری که انتظار آنها را داریم میتوان این خود تشابهیهای محلی را مشاهده نمود. تعیین این خود تشابهیها و پیشنهاد الگوریتمی برای کد کردن آنها موضوع بحث بخشهای بعدی میباشد.
دومین جنبه اختلاف بین تصاویر چند سطحی و تصاویر فرکتالی سیاه و سفید متفاوت بودن شدت روشنایی در نقاط مختلف تصویر است. بدین معنی که در تصویر مورد نظر ممکن است برخی نواحی یافت شوند که مثلا از نظر جهت لبهها با هم مشابه باشند ولی از نظر مشخصههای دیگر مانند شدت روشنایی52 و تفکیک یا کنتراست53 مانند هم نباشند. برای حل این مشکل تصاویر را میتوان بصورت توابع سه بعدی مدل نمود که دو بعد اول همان y,x نشانگر مختصات و بعد سوم Z=f(x,y) شدت روشنایی در نقاط مختلف تصویر میباشد و برای نگاشت نواحی مختلف به هم دیگر از تبدیلات آفینی سه بعدی استفاده نمود که علاوه بر تغییر مولفههای y,x روشنایی و کنتراست تصویر را نیز تحت تاثیر قرار میدهند. این تبدیلات بصورت مشروح در بخشهای بعد مورد بررسی قرارمیگیرد[49].
3-5-2) مدل کردن خود تشابهی در تصاویر بوسیله ماشین Partitiond-MRCM :
در این بخش ما به گسترش ایده ماشین کپی تقلیل چندگانه خواهیم پرداخت بصورتی که بتوانیم کد کردن تصاویر چند سطحی را بوسیله آن بیان کنیم. قبل از هر چیز به بیان مشخصههای این ماشین فرضی جدید میپردازیم[11].
1- ماشین مورد نظر بسته به تصویری که تولید میکند تعدادی لنز دارد.
2- ضریب کاهش هر لنز بطور جداگانه قابل تنظیم است.
3- ترکیب لنزها بصورتی است که میتواند کل تصویر اصلی را بپوشاند و هر لنز میتواند بر روی تصویر، تبدیلات ساده مورد نظر را انجام دهد. مشخصههای فوق همان چیزهایی است که برای MRCM قرار داده بودیم اما با اضافه کردن دو توانایی زیر آنرا از MRCM متمایز میکنیم :
4- هر لنز میتواند علاوه بر تبدیلات هندسی سادهای که قبلا با آنها آشنا شدیم روشنایی و کنتراست تصویر مربوطه را نیز تغییر دهد.
5- همراه هر لنز یک تابع ماسک نیز تعریف میشود که تعیین میکند هر لنز کدام قسمت از تصویر اولیه را کپی میکند.
دو مشخصه اضافه شده انتهایی جهت کد کردن تصاویر چند سطحی خیلی با ارزشند. بخصوص مشخصه پنجم که تصویر را به قطعاتی تقسیم میکند که هر کدام از آنها جداگانه تبدیل میشوند و به همین دلیل است که ما این ماشین را ماشین کپی تقلیل چندگانه تقسیم یافته54 مینامیم. با تقسیم تصویر به قطعات جداگانه امکان کدکردن تصاویری که به وسیله MRCM مشکل و یا حتی غیر ممکن بودند فراهم میشود.
اجازه بدهید آنچه را که بعد از قرار دادن یک تصویر اولیه در ماشین رخ میدهد به جزئیات بیشتری تشریح کنیم. هر لنز سیستم قسمتی از تصویر اولیه که ما آنرا با Di نمایش میدهیم انتخاب میکند و بعد از اعمال کردن تبدیلات(شامل تبدیلات روشنایی و کنتراست) آنرا به قسمتی از تصویر خروجی که با Ri نمایش داده میشود کپی میکند.Di ها را دامنه55 و Ri را برد56 مینامیم. برای آنکه تصویر نهایی بصورت مناسبی ایجاد شود بردها باید بصورتی باشند که کاملا سطح تصویر را بپوشانند و برای آنکه روشنایی و کنتراست نواحی مختلف بصورت تعیین شده تغییر کند نباید بردها همپوشانی57 داشته باشند. بر خلاف بردها در مورد دامنهها نیازی نیست که دو شرط فوق را داشته باشند. برای مثال یک سیستم با هشت عدد لنز را در نظر بگیرد. شکل(3-5 و الف) دو ناحیه را نشان میدهد که یکی با D1 = D2 = D3 = D4 و دیگری با D5= D6 = D7 = D8 مشخص شده است. این شکل دقیقا بیانگر همپوشانی دامنهها میباشد. هر کدام از لنزها، Di مربوطه را با نسبت کوچک کردن معینی به Ri مطابق با آن مینگارند. برای سادگی در این مثال فرض کردهایم که روشنایی و کنتراست تغییر نمیکند. در شکل(3-5 وب) سه مرحله از تکرار ماشین با دو ورودی اولیه متفاوت به همراه جذب کننده آن نمایش داده شده است. البته این شکل را میتوان با یک IFS ساده نیز ایجاد نمود و در اینجا تنها هدف نشان دادن نحوه عمل PMRCM است[21].

شکل3-5: نحوه انتخاب دامنه و برد در سیستم PMRCM.

در بخشهای قبل از مطرح کردن ایده MRCM و ریاضیات مرتبط با آن یعنی سیستم توابع تکراری(IFS) را تشریح کردیم. برای توصیف عملیات PMRCM باید روابط موجود را بسط دهیم تا عملیات آنرا بصورت ریاضی بیان کنیم که این موضوع در بخش بعد مورد بررسی قرار میگیرد.

3-5-3) قضیه کالج و تبدیلات آفینی سه بعدی
ریاضیدانان معروف، مایکل بارنزلی با مشاهداتی نظیر آنچه در بخش قبل نشان داده شد به این نتیجه رسید که میتوان تصاویر چند سطحی با خود تشابهی محلی را بوسیله دسته معینی از تبدیلات آفینی کد کرد. او نتایج کار خود را بصورت قضیهای معروف بنام قضیه کالج58 مطرح نمود. این قضیه بصورت زیر در آمده است[48]:
قضیه کالج : فرض کنید مجموعه{Wn : n=1,…,N} یک کد IFS مربوط به N عدد از تبدیلات آفینی انقباضی باشد، A یک ناحیه بسته در فضای R² و تبدیل Wn چنان انتخاب شده باشد که :

(4-7)

آنگاه

(4-8)

در رابطه فوق s عددی مثبت و کوچکتر از یک و ε نیز یک عدد مثبت و بمراتب کوچکتر از یک میباشد. h(.) تابع فاصله است که بارنسلی آن را به صورت فاصله هاسدروف59 تعریف نموده است. اما در تصاویر چند سطحی معمولا از فاصله مجموع مربعات یا همان خطای مجموع مربعات(MSE) استفاده میشود.A∞ نیز بیانگر جذب کنندهء کدهای IFS میباشد. این قضیه بیان میدارد که در صورتی که یک تصویر اولیه مانند A را بتوان بوسیله تبدیل آفینی باضریب انقباضی s تقریب زد به صورتی که خطای تقریب کمتر از ε باشد، آنگاه میتوان مطمئن بود فاصله بین جذب کنندهء این تبدیلات و تصویر اولیه ناچیز(مطابق رابطه (3-8 ) ) خواهد بود. در بخش قبل تبدیلاتی که PMRCM میتواند به یک زیر تصویر اعمال کند دقیقا بیان نشد. اکنون زمان آن فرا رسیده که نوع تبدیلات را معین کنیم. مطابق معمول از فرم ماتریسی استفاده میکنیم زیرا سادگی فراوانی به همراه دارد. تبدیلاتی که بکار میرود محدود به فرم استاندارد زیر هستند که در کارهای قبل از آنها استفاده شده است.

(3-9)

در واقع تبدیل فوق میتوان به دو بخش جداگانه تبدیل نمود. یکی بخش تبدیلات هندسی که مانند تبدیلات در تصاویر کاملا خود متشابه، شامل کوچک کردن، چرخش ویا انتقال تصویر میباشد و بخش دوم شامل تغییر در روشنایی و کنتراست تصویر میباشد. فرمول گذاری قبلی در مورد IFS های معمولی، تا حد زیادی در مورد ماشین PMRCM نیز صدق میکند زیرا تقسیم شدن تصویر در زیرنویس تابع تبدیل به صورت ضمنی بیان شده است.
بنابراین با داشتن یک تصویر اولیه مانند A0 و با اعمال اپراتور W که خود بصورت مجموعهای از N تبدیل مانند {Wi : i=1,…,N} میباشد یک تصویر جدید تولید میشود. بدین ترتیب که هر تبدیل بخشی از تصویر اولیه(دامنه) که آنرا با Di نشان میدهیم انتخاب کرده و پس از اعمال تبدیل، آنرا به ناحیهای از تصویر خروجی(برد) که ما آنرا با Ri نشان میدهیم کپی میکند. مجموع Riها بصورتی است که اشتراک آنها با هم تهی بوده و اجتماع آنها برابر تصویر تولید شده میباشد به عبارت دیگر :

for i,j if

(3-10)

for i= 1,2,………,N

(3-11)

از روابط فوق بخوبی پیداست که تعداد تبدیلات بستگی به تعداد بردها(Ri ها) دارد.با توجه به اصول تبدیلات انقباضی ثابت میشود بشرط آنکه تبدیلات فوق، انقباضی باشند با اعمال مکرر اپراتور W به تصویر تولید شده در مرحله قبل، به یک تصویر ثابت نهایی خواهیم رسید.
در این مرحله میتوان قدم را فراتر نهاد و حتی تبدیلاتی را که بصورت ضمنی انقباضی هستند مورد نظر قرار دارد و هنوز اطمینان داشت که در روند تکراری اعمال اپراتور W به تصویر هر چند ممکن است W برای کلیه Wiها قطعا انقباضی نباشند اما نهایتا سیستم به تصویر نهایی ثابتی همگرا شود. دلیل این امر آن است که هر چند ممکن است W انقباضی نباشد اما این امکان وجود دارد که Wm(m تعداد تکرارW) انقباضی باشد. میتوان بصورت زیر این مطلب را استدالال نمود که اپراتور W از اجتماع N تبدیل W1 تا WN تشکیل شده است که Wi ممکن است به ازای بعضی از مقادیرi انقباضی نباشد. وقتی در حلقه تکرار، اپراتور W را m بار به تصویر اعمال میکنیم میتوان گفت که Wm برابر اجتماعی از تبدیلاتی ترکیبی بفرم Wi1,…,Wim است که در Wij ، i نشانگر یکی از تبدیلات از 1,…, N و j نشانگر تعداد دفعات تکرار میباشد. بنابراین اگر در دنباله Wi1,Wi2,…,Win به تعداد کافی تبدیلات انقباضی وجود داشته باشند میتوان مطمئن بود که Wm در نهایت یک تبدیل انقباضی است و در نتیجه اعمال اپراتور W منجر به تولید یک شکل ثابت نهایی میشود.
در تصاویر چند سطحی وقتی از انقباضی بودن سخن به میان میآید، بیشتر انقباضی بودن در راستای مولفه سوم یعنی تغییر در مقدار تابع Z=f(x,y) مد نظر است. این تغییرات به صورت کم شدن روشنایی و کنتراست ظاهر میشود. در اینجا ممکن است این ابهام پیش آید که اعمال تبدیل به تصویر نهایتا منجر به تولید تصویری مبهم و تاریک میشود. بنابراین ضروری بنظر میرسد که این ابهام رفع شود، برخلاف آنچه تصور میشود تصاویر حاصل، از نظر کیفیت روشنایی و کنتراست بسیار عالی هستند. دلیل این امر در دو نکته نهفته است: یکی آنکه بخاطر استفاده از ضرایب متفاوت برای کاهش کنتراست بردهای متفاوت در نواحی مختلف تصویر، شدت روشناییهای متفاوت خواهیم داشت. دیگر آنکه چون معمولا تبدیلات بصورتی هستند که در راستای محورهای y,x نیز انقباضی میباشند در هر مرحله از اعمال تبدیل به تصویر علاوه بر ایجاد جزئیات، مقیاس پایینتر در داخل هر یک از بردها نیز بین نقاط مختلف آن کنتراست ایجاد میشود[48].
از مجموع مباحثی که تا به حال مطرح شد چنین برمیآید که در صورتی که قادر باشیم یک تصویر واقعی را بصورت مناسبی به تعداد معینی از بردهای غیر همپوشان(Ri) افراز کنیم و سپس بتوانیم دامنههای مناسبی همراه با تبدیلات مربوطه بیابیم که با تقریب خوبی به Riها نزدیک باشد، میتوان با ذخیره کردن ضرایب تبدیلات و مختصات و اندازه Di مربوطه به ازای هر Ri، تصویر را با مجموعهای از IFS ها کد نمود. این روش کد کردن، مزایای زیادی دربر خواهد داشت. اشارهای به مزایای این روش و نیز ارائه روش عملی و مناسب برای یافتن موارد فوقالذکر، مبحث بخشهای باقیمانده از این فصل را تشکیل میدهد.
3-6 ) چرا فشردهسازی با فرکتال؟
در این بخش میخواهیم به دو سوال اساسی پاسخ دهیم. اولین سئوال این است که به چه دلیل یا دلایلی ما روش خود را فشردهسازی فرکتال مینامیم؟ و دقیقا چه وجه اشتراکی بین مفهوم فرکتالها و این روش فشردهسازی مبتنی بر پردازش بلوکهای تصویر وجود دارد؟ در جواب این سئوال باید قبل از هر چیزی به این موضوع اشاره کرد که ما برای بازسازی تصاویر از تعدادی کدهایIFS استفاده میکنیم که خیلی شبیه به سیستم MRCM هستند. موضوع فوق میتواند بر جنبههای مختلفی دلالت کند که از جمله میتوان به جزئیات نامحدود در تصاویر اشاره نمود. بصورتی که اگر یک تصویر کد شده با این روش را در اندازهای بزرگتر(مثلا دو برابر اندازه تصویر کد شده) بازسازی کنیم جزئیات مورد نیاز بصورت اتوماتیک تولید میشوند و حالت کنگرهای60 در لبههای تصویر مشاهده نمیشود و لبهها بصورت مطلوبی پیوستگی خود را حفظ میکنند. اما اگر تصویر اصلی را بزرگ کنیم این خاصیت در تصویر بزرگ شده وجود ندارد. البته باید دقت نمود که منظور از جزئیات نامحدود این نیست که اگر یک تصویر فرکتالی را بزرگ کنیم بتوانیم مثلا پرز موی پالتوی یک شخص را در تصویر تشخیص دهیم. بلکه جزئیات نامحدود از همان دیدگاه فوق مد نظر است. این موضوع در شکل(3-6) نشان داده شده است. یکی دیگر از جنبههای مشترک این روش تئوری فرکتالهای همگرا شدن سیستم به یک خروجی نهایی به شرط انقباضی بودن تبدیلات میباشد[22].

تصویر بزرگ شده تصویر فرکتالی
مقایسه کیفیت لبه ها.

دومین سئوال این است که روش فشردهسازی فرکتالی چه مزایای نسبت به روشهای دیگر دارد؟ و یا اصولا چه برتریهایی آنرا به نسبت روشهای معمول مرجح میسازد؟ در پاسخ به این سئوال باید گفت که روش فشردهسازی فرکتالی ویژگیهای به خصوصی دارد که آن را از دیگر روشها متمایز میسازد. اولین ویژگی این روش آن است که مستقل از ابعاد تصویر فشرده شده میتوان آن را با اندازههای بزرگتر و یا کوچکتر بازسازی نمود. با توجه به آنکه دقت کارتهای گرافیکی روز بروز در حال تغییر است این یک مزیت عمده در نظر گرفته میشود[22]. دومین ویژگی این روش در آن است که مانند یک سیستم فراکتالی واقعی برای بازسازی تصویر اصلی میتوان با هر تصویر اولیهای شروع کرد و به نتیجه دلخواه رسید. این ویژگی میتواند باعث کاربردهای متنوع این روش در کارهای تلویزیونی و سینمایی جهت تغییر شکل61 و غیره شود. سومین ویژگی این روش کیفیت خوب بازسازی لبههای تصویر است که قبلا نیز به آن اشاره شد و در فصل دوم بیان شد که چشم انسان به تغییرات در لبهها حساس است بنابراین تصویر بازسازی شده با این روش از دید چشم انسان کیفیت بهتری دارند[10].
از ویژگیهای مهمی که در هر روش فشردهسازی مد نظر است نسبت فشردهسازی تصویر به فایل فشرده شده است. در روش فشردهسازی فرکتالی محاسبه نسبت فشردهسازی تا حدی گمراه کننده است. زیرا همانطوری که قبلا ذکر شد مستقل از اندازه تصویر کد شده، با استفاده از کدهای IFS میتوان تصویر را با هر اندازه دلخواهی بازسازی نمود. بنابراین اگر نسبت فایل کد شده به اندازه تصویر بازسازی شده را مورد نظر قرار دهیم ممکن است به نسبتهای بسیار بالایی برسیم. بارنسلی در موارد متعدد ادعا نموده است که روش ابداعی وی تصاویر را با نسبت ده هزار به یک، فشرده میکند. هر چند هیچگاه جزئیات روش خود را فاش ننموده است. اما برای فشردهسازی یک تصویر معمولی بر روی یک ایستگاه کاری، زمانی معادل 100 ساعت وقت صرف شده است که برای کاربردهای عملی غیر قابل قبول است. روشهای دیگری برای فشردهسازی فرکتالی معرفی شدهاند که در زمان محدودتری به نسبت فشردهسازی معقولی دست یافتهاند. در بخش بعد سعی خواهیم نمود که بر اساس ادغام ایدههای موجود در این زمینه و روشهای دیگر فشردهسازی الگوریتمی جدید برای فشردهسازی فرکتالی ارائه دهیم.

3-7 ) ارائه یک روش عملی برای فشردهسازی فرکتالی
فرض کنید که تصویر چند سطحی داده شده f را میخواهیم کد کنیم. این بدین معنی است که میخواهیم مجموعهای از تبدیلات w1 تا WN را که با نماد :

(3-12)

نشان میدهیم، پیدا کنیم بصورتی که f=|W| باشد یعنی f نقطه ثابت اپراتور هاکینسون باشد و داشته باشیم :

f=w(f) =
(3-13 )

آنچه قبلا پیش بینی کردیم این بود که با جستجوی تشابههای محلی در تصویر f، قطعاتی در تصویر را پیدا میکنیم که با اعمال تبدیلات wi دوباره خود تصویر f را تولید کنند. در حالت کلی این امر غیرممکن بنظر میرسد زیرا امکان پیدا کردن قطعاتی در تصویر که تحت تبدیلات آفینی بتوانند دقیقا تصویر را بازسازی کنند وجود ندارد. اما این امکان وجود دارد که تصویر دیگری مانندf′=|W| بدست آورد که خطای بین f و f′ که آنرا با (f, f′)δ نشان میدهیم کوچک باشد.
همچنان که قبلا نیز اشاره شد قطعاتی از تصویر که تبدیلات را به آنها اعمال میکنیم دامنه نامیده و با Di نمایش میدهیم و بخشهایی که تصویر نهایی را میپوشاند بعنوان برد میشناسیم و آنها را با Ri نمایش میدهیم. بنابراین محور اصلی مسئله فشردهسازی با استفاده از توابع تکراری عبارت است از:
الف ) نحوه تقسیم کردن تصویر اولیه به دامنههایی که میتوانند دارای روی هم افتادگی62 باشند و نیازی نیست که همه سطح تصویر را بپوشاند.
ب ) تعیین بردها بصورتی که علاوه بر پوشاندن کل سطح تصویر هیچ اشتراکی بین آنها وجود نداشته باشد.
ج ) یافتن مجموعهای از دامنه و تبدیل مناسب مربوطه، به ازای هر کدام از بلوکهای برد بصورتی که بتوانند با یک خطای قابل قبول تصویر را بپوشاند.
د ) یافتن تکنیکهای مناسب برای کلاسبندی بلوکهای دامنه و برد جهت کاستن از زمان فشردهسازی و بدست آوردن تقریب بهینه از تصویر ورودی.
ه ) نحوه ذخیره کدها و بازسازی تصویر با استفاده از آنها.
بلوک دیاگرام کلی روش پیشنهادی جهت فشردهسازی تصاویر با روش فرکتالی در شکل زیر دیده میشود[21]:

3-7-1) تقسیم بندی تصاویر63
وقتی از تقسیمبندی تصاویر سخن به میان میآید، قبل از آن باید معیارهایی که مبنای تقسیم بندی قرار میگیرند تعیین شود. در پردازش تصویر با توجه به خواص چشم انسان لبهها از اهمیت زیادی برخوردار هستند. لبههای اشکال در تصاویر معمولا خیلی پیچیده هستند. تکنیکهای متعددی بر اساس رشد نواحی در متون استاندارد پردازش تصاویر وجود دارد. کار کردن با این نواحی پیچیده، بسیار مشکل است. یک روش سادهتر آن است که تصویر را به تعدادی بلوک با اشکال هندسی معین مانند: مربع، مستطیل و یا مثلث تقسیم کنیم و سپس تحقیق کنیم که آیا در هر بلوک میتوان لبهای تشخیص داد.
همچنانکه میدانیم لبه هنگامی بوجود میآید که ما یک تغییر آنی در روشنایی پیکسلهای مجاور داشته باشیم. این تغییر میتواند از شدت روشنایی کم به روشنایی زیاد یا بالعکس باشد.
بر اساس وجود یا عدم وجود لبه و در مرحله بعد براساس جهت لبهها، بلوکها به کلاسها سپس به زیر کلاسهای بیشتری تقسیم میشود.
بنابراین در روش فشردهسازی فرکتالی ابتدا باید تصویر اولیه را به بلوکهای با اندازه K×K تقسیم نمود و هر کدام از بلوکها را به عنوان یک دامنه گرفت. درمرحله بعد تصویر را به بلوکها با اندازه L×L تقسیم نمود و آنها را بعنوان بردها در نظر گرفت.L باید کوچکتر از K (مثلا نصف K) باشد، تا انقباضی بودن تبدیلات ملحوظ شود. حال با معین بودن اندازه دامنه و برد در صورتیکه بتوانیم به ازای هر برد دامنه مناسبی پیدا کنیم که تحت تبدیلات متقارن هندسی تقریب مناسبی از آن باشد، کد نمودن تصویر مشکل چندانی نخواهد داشت. تعیین شکل، اندازه و تعداد دامنهها یکی از مسائل عمده در کدکردن تصاویر میباشد که بصورت مفصلتری آنها را مورد بررسی قرار میدهیم.
روش کد کردن فرکتالی مانند روشهای کدینگ تبدیل و کوانتیزاسیون برداری یک روش مبتنی بر پردازش بلوک است. در روش کدینگ تبدیل استفاده از تبدیلات متعامد سریع مانند تبدیل فوریه سریع ایجاب میکند که بلوکها به صورت مربعی و ابعاد آنها به صورت توان صحیحی از دو باشد. در روشهای کوانتیزاسیون برداری اولیه به دلیل حفظ سازگاری با روشهای کدینگ تبدیل، این روش ادامه یافته است. البته باید این نکته را تاکید نمود که در روشهای V.Q. مبتنی بر تکنیکهای کلاسبندی در حوزه فرکانس، ابعاد مربعی توان دو ضرورت دارد. بدیهی است که شکل بردها نیز پیرو شکل دامنهها خواهد بود. دومین مسئله در رابطه با دامنهها انتخاب تعداد دامنهها میباشد. زیرا دامنهها میتوانند بر روی هم افتادگی داشته باشند. بسته به مقدار آن، در یک تصویر میتوان تعداد متفاوتی بلوک دامنه در نظر گرفت. یک روش ممکن آن است که برای تولید بلوکهای دامنه از تکنیک پنجره لغزان که در هر مرحله به مقدار یک پیکسل به راست یا به پایین انتقال مییابد استفاده نمود. اما عیب عمده این روش در تعداد زیاد دامنههایی است که غالبا تفاوت نسبتا کمی با یکدیگر دارند. برای نقص این نقیصه در میتوان هر پنجره را به مقدار بیشتری(مثلا دو یا چهار پیکسل) به راست یا پایین لغزند[11].
آخرین مسئله، اندازه بلوکهای دامنه و برد میباشد. یک موضوع اساسی این است که باید ابعاد دامنهها بزرگتر از بردها باشد تا انقباضی بودن و در نتیجه همگرایی تبدیلات تضمین شود. مثلا دامنهها 8*8 و بردها 4*4 باشند. اما با توجه به ساختار تصاویر میتوان در بعضی از نواحی تصویر که تغییرات در پیکسلهای مجاور کم یا ناچیز است اندازه بلوکهای دامنه و در نتیجه بردها را بزرگتر انتخاب نمود و درجاهایی که جزئیات زیادی وجود دارد برای بدست آوردن تقریب بهتر، ابعاد بلوکها را کوچکتر انتخاب نمود، که این منجر به ضریب فشردهسازی بالاتری خواهد شد بدون آنکه کیفیت تصاویر بازسازی شده کاهش محسوسی بیابد. دخالت دادن خواص تصویر در تعیین اندازه بلوکها منجر به روشهای تقسیم بندی وفقی میشود.
البته ذکر این نکته ضروری است که استفاده از روشهای وفقی بر پیچیدگی مراحل کدینگ و دکدینگ میافزاید و نیز نیاز به اطلاعات اضافی برای مشخص نمودن اندازه بلوکها دارد. در ادامه به بررسی سه روش معمول برای تقسیم بندی وفقی تصاویر میپردازیم.

الف) روش تقسیم بندی درخت چهار تایی64
در این روش از حداکثر اندازه بلوک مثلا 32 شروع میکنیم. در صورتی که بر اساس روشهای کلاسبندی مشخص شود که بلوک شامل جزئیات میباشد آنرا به چهار بلوک با اندازه 16*16 تقسیم میکنیم و دوباره برای هرکدامیک از چهار زیر بلوک بدست آمده آزمایش مربوطه را تکرار میکنیم و هرگاه نیاز باشد به همان روال آنها را به زیر بلوک کوچکتر با ابعاد 8*8 تقسیم میکنیم. عمل تقسیم کردن به زیر بلوکهای کوچکتر تا جایی ادامه مییابد که به اندازه حداقل(مثلا 4*4) برسیم یا زیر بلوکی بدست آوریم که بر اساس معیارهای کلاسبندی بتوان آنرا بصورتی کلاسبندی نمود که بازسازی آن با خطای قابل قبول ممکن باشد. روش فوق یک روش سلسله مراتبی است و به سادگی و با نیاز به حداقل اطلاعات اضافی میتوان نواحی مختلف و اندازههای متفاوت را آدرسدهی نمود. بعنوان مثال فرض کنید که بزرگترین اندازه بلوکها 16*16 و کوچکترین اندازه بلوک 4*4 میباشد. شکل(3-8) نحوه تقسیم یک بلوک نمونه را نشان میدهد. ابتدا با اندازه 16*16 شروع میکنیم. اگر بلوک دارای جزئیات کم65 باشد تقسیم نشده باقی میماند و کد تک بیتی صفر تولید میشود که نشانگر عدم تقسیم بلوک است. در غیر این صورت بلوک اولیه مطابق شکل(3-8، الف) به چهار زیر بلوک 8*8 تقسیم میشود و کد یک تولید میشود که نشانگر تقسیم بلوک اصلی میباشد. در مرحله بعد دوباره هر زیر بلوکی که تقسیم شود به ازای آن کد یک و در غیر اینصورت کد صفر تولید میشود و تا رسیدن به اندازه حداقل، این روش تکرار میشود. در شکل(3-8) بلوکهای دارای جزئیات کم با (Lo) و بلوکهای دارای جزئیات زیاد با (Hi) نشان داده شده است.

2
1
4
3
LO
LO
LO
Hi
LO

Hi
LO
LO
Hi
Hi

(ب) (الف)

16×16
8×8

4×4

QC=

(ج)

شکل3-8: نمودار روش Quadtree.

در شکل(3-8 ، ب) تقسیمبندی نهایی بلوک اصلی و در قسمت (ج) ساختار درختی نحوه تقسیمبندی و کد مربوطه نشان داده شدهاند. اشکال سیاه نمایانگر بلوکهای دارای جزئیات بالا میباشند. بلوکهای تقسیم شده با دایره و بلوکهای تقسیم نشده با مربع نشان داده شدهاند.

ب ) روش تقسیم بندی افقی، عمودی HV 66
یکی از روش ضعفهای روش Quadtree در این است که در هر مرحله از تقسیم بلوکها به ازای هر بلوک، چهار زیر بلوک تولید میشود بدون آنکه محتوای زیر بلوکها بصورتی در روند تقسیمبندی دخالت داده شوند. یک راه چاره آن است که از روش تقسیم بندی افقی، عمودی استفاده کنیم. در این روش هرگاه نیاز به تقسیم یک بلوک باشد، بسته به جهت لبههای موجود در بلوک آنرا در جهت عمودی یا افقی تنها به دو زیر بلوک تقسیم میکنیم. بدین ترتیب دو بلوک مستطیلی ایجاد میشود و در صورتیکه نیاز باشد میتوان هر کدام را در جهت افقی یا عمودی دوباره به زیر بلوکهای بیشتری تقسیم نمود. در این حالت نیز تقسیم بندی تا جایی ادامه مییابد که معیارهای مورد نظر برآورده شود یا به اندازه حداقل برای بلوکها برسیم.
ج ) روش تقسیم بندی مثلثی67
در این روش تصویر اصلی بصورت قطری به دو مثلث تقسیم میشود. سپس هر کدام از این مثلثها بصورت برگشتی به چهار مثلث تقسیم میشود. این کار با وصل کردن وسط سه ضلع مثلث به همدیگر بدست میآیند. روش فوق مزایای عمدهای نسبت به روش قبل دارد که از آن جمله عدم ظاهر شدن پدیده کنگرهای شدن لبهها در تصویر بازسازی شده و امکان انتخاب جهتهای بیشتر برای بلوکها را میتوان نام برد. خاصیت اخیر باعث میشود بهتر بتوانیم خود تشابهی در تصاویر را مدل کنیم، ولی به دلیل آنکه محاسبات این روش بسیار پیچیده است در نتیجه باعث کم شدن سرعت فشردهسازی میشود. این روش هنوز قسمتی از زمینههای تحقیقاتی میباشد[11].

3-7-2 ) تکنیکهای کلاسبندی68
برای آنکه از زمان جستجوی دامنه مناسب برای تقریب زدن یک برد بکاهیم و علاوه بر آن کیفیت تصاویر بازسازی شده را از نظر معیارهای کیفی بهبود بخشیم نیاز به روشی داریم که بر اساس آن بتوانیم دامنهها و بردهای مختلف را کلاسبندی نماییم. موارد فوق اولین بار در کوانتیزاسیون برداری مورد توجه قرار گرفت. یکی از روشهای ممکن، کلاسبندی بر اساس متوسط انرژی مولفههای فرکانس بالا در یک بلوک است. در این روش هر بلوک به یکی از چهار دسته سایه69، حد متوسط70، لبهها71 و مخلوط72 تقسیم نموده است. در کلاس سایه، گرادیان تغییرات قابل توجه نیست، در کلاس دوم گرادیان در حد متوسط است، در کلاس لبه، گرادیان محسوسی در جهت گذر از لبه وجود دارد و نهایتا در کلاس آخر هر چند گرادیان قابل توجهی وجود دارد اما نمیتوان جهت خاصی را برای آن تعیین نمود.
علاوه بر موارد فوق، کلاس لبه به زیر کلاسهای لبه افقی، عمودی، 45 درجه و 135 درجه تقسیم میشوند. هر کدام از این زیر کلاسها نیز بر حسب محل لبه در بلوک و جهت تغییرات روشنایی یعنی نحوه تغییر از روشن به تاریک یا بالعکس به زیر دستههای کوچکتری تقسیم میشوند. وقتی بلوکها به اندازه کافی کوچک باشند میتوان لبهها را با خطوط مستقیم مدل نمود. بنابراین در صورتیکه لبهها را به آنچه در فوق آمده محدود کنیم خطای چندانی بوجود نمیآید. تشخیص لبهها در حوزه زمان مطابق روشهای بکار رفته علاوه بر نیاز به یک مرحله پیش پردازش بسیار پیچیده و وقتگیر است و نیاز به قرار دادن سطوح آستانهای متعددی برای تشخیص و جداکردن کلاسهای مختلف از همدیگر نیز دارد. اما به هر حال این روش بر مبنای کار ژاکوبین بوده است.
یک روش بمراتب سادهتر و کارآتر که بهبود قابل توجهی در کلاسبندی نیز پدید میآورد روش کلاسبندی در حوزه تبدیل کسینوسی گسسته(DCT) میباشد. با استفاده از مشخصههای بلوک تبدیل یافته میتوان به سادگی و با دقت بسیار بیشتر با نیاز به حداقل حافظه و در زمان به مراتب کمتری به نسبت روش قبل بلوکها را کلاسبندی نمود. استفاده از تبدیلDCT به دلیل اینکه قبلا در روشهای کدینگ تبدیل نیز بکار رفته است بیشتر جنبه تاریخی دارد[22].
کیفیت تصاویر بازسازی شده به دقت انتخاب دامنهای که برای تقریب زدن بردها بکار میبریم بستگی دارد و انتخاب دامنه و برد بستگی مستقیم با روش کلاسبندی دارد. در روش کلاسبندی، لازم است که تبدیل بلوکها بصورت توان صحیح دو باشد. بنابراین برای تقسیمبندی تصویر باید از روش کلاسبندی ثابت یا کلاسبندی وفقی به روش درخت چهارتایی استفاده نماییم. برای مثال جزئیات این روش را برای بلوکهای 4*4 ذکر مینماییم. در تحقیقات قبلی جداکردن کلاسهای باجزئیات کم73 از کلاسهای باجزئیات زیاد74 از تعدادی سطوح آستانه75 در حوزه زمان استفاده شده است و سپس کلاس لبهها با استفاده از مشخصههای حوزه تبدیل از همدیگر تفکیک شدهاند.

3-7-3 )انتخاب دامنههای مناسب
در بیشتر روشهای کدینگ که در فصل دوم معرفی شدند از مزایای همبستگی بین پیکسلهای مجاور برای فشردهسازی تصاویر استفاده میشود. علاوه بر آن بین بلوکهای مجاور نیز همبستگی زیادی وجود دارد که میتوان برای افزودن به نسبت فشردهسازی آن را نیز در نظر گرفت. اغلب روشهای فشردهسازی با استفاده از کدهای IFS شامل جستجو برای یافتن دامنه مناسب جهت تقریب زدن بردها میباشند. جستجوها بر روی گروه بزرگی از دامنه های متفاوت انجام میگیرد و اغلب مقایسهها بدون نتیجه و زاید است. برای حل این مشکل میتوان جستجو را به بلوکهایی که در اطراف بلوک مورد نظر هستند محدود کرد.
بدین ترتیب با استفاده از خاصیت همبستگی بین بلوکهای مجاور علاوه بر کاستن از زمان مورد نیاز برای یافتن دامنه مناسب، حافظه مورد نیاز برای ذخیره آدرس دامنهها نیز کاهش مییابد. بعنوان مثال میتوان برای هر بلوک برد 64 ، 128 ، و یا 256 بلوک اطراف آنرا برای یافتن مورد مناسب جستجو نمود و آدرس آنرا نیز بصورت فاصله نسبی از بلوک برد ذخیره نمود.

3-7-4)تبدیلات بلوکی فرکتالی76
در بخشهای قبل گفتیم که برای نگاشت بلوکهای دامنه به برد از تبدیلات فرکتالی استفاده میشود. بدلیل دیجیتالی بودن تصاویر، فرم ظاهری این تبدیلات کمی با آنچه در بخشهای قبل ذکر شد متفاوت است. در واقع این قسمت در شکل(3-7) خود شامل سه دسته از تبدیلاتی است که بصورت متوالی بر روی بلوک دامنه عمل میکنند تا یک بلوک برد را تقریب بزنند. این سه دسته، انقباض فضایی 77، تبدیلات ایزومتریک78 و تبدیلات تغییر سطح و مقیاسبندی روشنایی پیکسلها79 میباشند که در شکل(3-9) نشان داده شدهاند.

شکل3-9: بلوک دیاگرام تبدیلات بلوکی فرکتالی.

انقباض فضایی برای کاستن ابعاد بلوک دامنه از اندازه d×d به اندازه r×r که برابر با اندازه برد میباشد بکار میرود. اگر d مضرب صحیحی از r باشد بطور ساده اینکار را میتوان با گرفتن میانگین (d/r)² پیکسل مجاور در بلوک دامنه انجام داد.
تبدیلات ایزومتریک محل پیکسلها را در بلوک منقبض شده با روشهای از پیش تعیین شده تغییر میدهند. این تبدیلات بر جهت لبه در بلوک، اثر میگذارند بدون آنکه مقدار روشنایی پیکسلهای داخل آن را تغییر دهند. برای بلوکهای دامنه و برد به فرم مربعی از تبدیلات زیر استفاده میشود:
1- تبدیل همانی
2- معکوس کردن حول محور عمودی وسط بلوک
3- معکوس کردن حول محور افقی وسط بلوک
4- معکوس کردن حول قطر اصلی
5- معکوس کردن حول قطر فرعی
6- دوران 90+ درجه حول مرکز بلوک
7- دوران 180+ درجه حول مرکز بلوک
8- دوران 90- درجه حول مرکز بلوک
هشت تبدیل فوق با هم اصطلاحا " گروه " را تشکیل میدهند. منظور از " گروه " به این معنی است که هر تبدیل دارای یک معکوس میباشد که میتوان آنرا با ترکیب کردن دو یا چند تبدیل دیگر در همان "گروه" بدست آورد. به همین دلیل نیاز به در نظرگرفتن ترکیب بین تبدیلات وجود ندارد زیرا هر ترکیب ممکن، تبدیلی تولید میکند که قبلا در " گروه " وجود داشته است.
سرانجام تبدیل مقیاسبندی و انتقال، میزان روشنایی و کنتراست پیکسلها را تغییر میدهد بدون آنکه بر جهت لبه در بلوک تاثیر بگذارد. این تبدیل برای بلوک x بصورت زیر است:

x'=sx+tu

(3-15 )

که t,s به ترتیب ضرایب مقیاسبندی و انتقال میباشند . u نیز برداری است که میتواند همه یا تعدادی از اعضای آن که در راستای لبه خاصی قرار دارند یک باشد. در خلال کدینگ، مقادیر بهینه t,s به ازای هر ترکیب از دامنههای کوچک شده و تبدیلات ایزومتریک برای تقریب زدن بلوکهای برد محاسبه و در نهایت مناسبترین ضرایب در نظر گرفته میشوند. برای بلوک برد y و دامنه انقباض یافته x* این مقادیر بهینه از طریق حداقل کردن خطای MSE بصورت زیر محاسبه میشوند:

S =

(3-16)

t =

(3-17)

که در روابط فوق || . || و < . > به ترتیب نرم و حاصلضرب داخلی میباشند که بصورت زیر محاسبه میشوند. حاصلضرب داخلی به عنوان همبستگی نیز شناخته میشود:

(3-18 )

(3-19)

البته ژاکوین از روش متفاوتی برای بدست آوردن مقادیر t,s استفاده نموده است که در اینجا روش مورد استفاده او را نیز به اختصار شرح میدهیم. در این روش ابتدا مقادیر کمترین و بیشترین سطح روشنایی در بلوکهای برد و دامنه منقبض شده محاسبه شده و تفاوت این دو مقدار در هر بلوک به عنوان رنج دینامیکی80dr تغییرات روشنایی در نظرگرفته میشود. سپس مقادیر t,s بصورت زیر محاسبه میشوند:

S=

(3-20)

t= mean(R) – mean

(3-21)

3-8)فشردهسازی تصویر و نوشتن فایل فرمت فرکتالی تصویر
در این بخش ما بر اساس مطالب سه بخش قبل نحوه تولید فایل کدهای فرکتالی برای یک تصویر را بیان میکنیم.
اولین مرحله در فشردهسازی تصاویر با استفاده از تبدیلات فرکتالی تقسیم تصویر به دامنهها میباشد. این دامنه ها از بلوکهای برد بزرگترند و مقداری همپوشانی دارند. میزان این همپوشانی متغیر است و میتوان آنرا در ابتدای کار تعیین نمود. سپس کلیه این دامنهها را تحت تبدیل مورد استفاده قرار داده و با استفاده از مشخصههای بدست آمده در حوزه تبدیل آنها را کلاسبندی میکنیم و کد کلاسبندی آنها را در یک کتابخانه موقت قرار میدهیم[21].
بعد از دامنهها حال نوبت به بردها میرسد. اولین برد که در گوشه بالای سمت چپ تصویر قرار دارد شروع میکنیم.
تعداد بیتهای متفاوتی به عنوان کد فرکتالی بلوک، در فایل فرمت فراکتالی تصویر FIF 81 بعنوان خروجی نوشته میشود، و این روند تا پردازش آخرین بلوک برد، تکرار میگردد. این فایل دارای یک سرآیند82 است، که در آن اطلاعاتی راجع به نحوه انتخاب دامنه و برد و ابعاد آنها قرار دارد. به دنبال آن لیستی از ضرایب تبدیلات فراکتالی به صورت کد شده قرارمیگیرد. در این روش فایلی تولید میشود که اطلاعات آن مستقل از دقت تفکیک 83 تصویر است. در واقع فرمولی برای تصویر بدست آمده است، درست مانند خطی که آنرا با معادله y=ax+b نشان میدهیم. هرگاه مقادیر ضرایب b,a را داشته باشیم قادر هستیم که با هر دقت دلخواهی آنرا رسم کنیم. مشابه آن با در دست داشتن ضرایب تبدیلات فرکتالی به صورت یک فایل FIF میتوان یک جایگزین فرکتالی برای تصویر اولیه در هر دقت تفکیکی ارائه نمود که مشابه تصویر اولیه باشد.

3-9) بازسازی تصویر با استفاده از فایل فرمت فراکتالی تصویر
بازسازی تصویر از روی فایل کدهای فرکتالی، بصورت یک روند تکراری میباشد. ابتدا اطلاعات فایل فرمت فراکتالی تصویر خوانده شده و به دو تصویر اولیه با اندازههای مساوی حافظه مورد نیاز اختصاص داده میشوند. یکی از این تصاویر را دامنه و دیگری را برد مینامیم. سپس تصویر برد مطابق با اطلاعات ذخیره شده در فایل فرمت فرکتالی به بلوکهای غیر همپوشان برد تقسیم میشود. در مرحله بعد به ازای هر کدام از بردها کدهای IFS مربوطه از فایل ورودی خوانده شده و از روی آنها، محل دامنه و نوع تبدیل به کار رفته تعیین میشود. سپس محتوای این بلوک در تصویر تحت تبدیلات موجود در کد IFS به بلوک برد در تصویر دوم که تصویر برد است نگاشته میشود.

خواندن اطلاعات مربوط به تقسیم بندی بلوکهای
برد، آدرس دامنههای مربوط و تبدیلات بکار
رفته از فایل فرمت فراکتالی

اشاره به اولین بلوک برد

شکل 3- 10 : فلوچارت روشن دکد کردن فرکتالی.

بعد از آن در دومین مرحله تکرار، تصویر برد تولید شده در این مرحله بعنوان تصویر دامنه در نظر گرفته و با اعمال تبدیلات، یک تصویر برد جدید بدست میآوریم. این روند تا جایی ادامه مییابد که تفاوت دو تصویر برد و دامنه ناچیز باشد. معمولا بعد از شش تکرار، تصویر تولید شده تغییر چندانی نمیکند.
در صورتی که بخواهیم تصویر را با اندازه غیر از اندازه هنگام کد کردن، بازسازی کنیم این کار به سادگی ممکن است و تنها کافی است که اندازه بلوکهای دامنه و برد در ضریب مناسبی ضرب شده و مطابق با اندازه جدید، آدرس بلوکهای دامنه از روی آدرس ذخیره شده در فایل کدهای IFS محاسبه گردد[21].
روش فشردهسازی فرکتالی یک روش نامتقارن است. بدین معنی که زمان لازم برای فشردهسازی و بازسازی تصویر مساوی نیستند و بازسازی تصویر به مراتب سریعتر و سادهتر میباشد. به همین دلیل مشابه روشهای V.Q. در کاربردهایی که فقط یک بار تصویر فشرده میشود و ممکن است به تعداد زیاد و در جاهای متفاوت نیاز به بازسازی تصویر باشد صرفهجوی زیادی در وقت بوجود میآورد.

منابع و مراجع: References
[1] C.S.Tong, M.Pi,"Analysis of a hybrid fractal-predictive-coding compression scheme", Signal Processing: Image Communication 18, Feb 2003.
[2] L. Vences, I.Rudomin."Genetic Algorithms for Fractal Image and Image Sequence Compression", Comptacion Visual 1997.
[3] M. F. Barnsley, "Fractals everywhere", Academic Press, Boston, 1988.
[4] M.S.Wu, W.C.Teng, J.H.Jeng, J.G.Hsieh,"Spatial correlation genetic algorithm for fractal image compression", elsevier 28,pp. 497-510,Apr. 2006.
[5] Y.Zheng, G.Liu, X.Niu,"An Improved Fractal Image Compression Approach by Using Iterated Function System and Genetic Algorithm", elsevire Computers and Mathematics with Applications 51,pp. 1727-1740, 2006.
[6] B.Z.Peter,"MAXIMAL PROCESSOR UTILIZATION IN PARALLEL QUADTREE-BASED FRACTAL IMAGE COMPRESSION ON MIMD ARCHITECTURES", STUDIA UNIV. BABES,BOLYAI, INFORMATICA, Volume XLIX, Number 2, 2004.
[7] D. J.Jackson,W.MAhmoud, "Parallel Pipelined Fractal Image Compression using Quadtree Recomposition", The computer journal, vol. 39, no. 1, 1996.
[8] Y.Iano, F.S.d.Silva, A.L.M.Cruz,"A Fast and Efficient Hybrid Fractal-Wavelet Image Coder", IEEE Trans. Image Process., vol. 15 , no. 1, JAN 2006.
[9] B. B. Mandelbrot, "The Fractal Geometry of Nature", W.H. Freeman and Company, ISBN 0-7167-1186-9, 1983.
[10] B. Wohlberg and G. Jager. "A review of the Fractal Image Compression Literature". IEEE Trans. onImage Processing, Vol. 8, No. 12, pp. 1716-1729, Dec. 1999.
[11] M. Barnsley and L. Hurd. "Fractal Image Compression. on Image Processing", Mathematical Methods and Applications. pp. 183-210, Clarendon Press, Oxford, 1997
[12] M.Hassaballah, M.M.Makky, Y.B.Mahdy,"A Fast Fractal Image Compression Method Based Entropy", Electronic Letters on Computer Vision and Image Analysis 5(1):30-40,Feb 2005.
[13] X.Wu,D. J.Jackson, H.Chen,"A fast fractal image encoding method based on intelligent search of standard deviation", elsevir Computers and Electrical Engineering 31,402-421, Feb 2005.
[14] S.Furao, O.Hasegawa,"A fast no search fractal image coding method", elsevire, Signal Processing: Image Communication 19.393-404, Feb 2004.
[15] R.Distasi, MNappi, D.Riccio, "A Range/Domain Approximation Error-Based Approach for Fractal Image Compression", IEEE Trans. Image Process., vol. 15 , no. 1, JAN 2006.
[16] K.Belloulata, " Fast fractal coding of subbands using a non-iterative block clustering", Elsevier,Image R.16,p. 55-67, Feb 2004.
[17] S.K.Ghosh, J.Mukherjee, P.P. Das, " Fractal image compression: a randomized approach", elsrvir, Pattern Recognition Letters 25,p. 1013-1024,Mar 2004.
[18] C.j.He, G.Li, X.Shen, "Interpolation decoding method with variable parameters for fractal image compression", elsevir, Chaos, Solitons and Fractals 32 , p.1429-1439, Mar 2007.
[19] K.T. Sun, S.J. Lee, P.Y. Wu, " Neural network approaches to fractal image compression and decompression", elsevir , Neurocomputing 41,p. 91-107, Nov 2001.
[20] K.L.Chung, C.H.Hsu , "Novel prediction- and subblock-based algorithm for fractal image compression", elsevir, Chaos, Solitons and Fractals 29 ,p. 215-222, Ags 2006.
[21] Y. Fisher. "Fractal Image Compression: Theory and Applications", Springer-Verlag, New York, 1994.
[22] E.W. Jacobs, Y. Fisher, and R.D. Boss. "Image Compression: A study of the Iterated Transform Method". Signal Process, Vol. 29, pp. 251-263, 1992.
[23] R.Hamzaoui, D.Saupe, M.Hiller , "Distortion Minimization with Fast Local Search for Fractal Image Compression", Journal of Visual Communication and Image Representation 12, 450-468, sep 2001.
[24] K.Belloulata, J.Konrad, " Fractal Image Compression with Region-Based Functionality", IEEE Trans. Image Process., vol. 11 , no. 1, Apr 2002.
[25] Z.Zhang,Y.Zhao, " IMPROVING THE PERFORMANCE OF FRACTAL IMAGE CODING", International Journal of Innovative Computing, Information and Control Vol 2, Number 2, April 2006.
[26] S.K. Ghosh, J. Mukhopadhyay, V.M. Chowdary, A. Jeyaram. " Relative fractal coding and its application in satellite image compression", elsevir,Image and Vision Computing 24, Feb 2002.
[27] D.Saupe, M.Ruhl, "EVOLUTIONARY FRACTAL IMAGE COMPRESSION", IEEE International Conference on Image Processing (ICIP'96), Lausanne, Sept. 1996
[28] M. Ruhl, H.Hartenstein, D. Saupe. " ADAPTIVE PARTITIONINGS FOR FRACTAL IMAGE COMPRESSION", IEEE International Conference on Image Processing (ICIP'97), Santa Barbara, Oct. 1997.
[29] Y.C.Chang, B.K Shyu, J.S.Wang. " REGION-BASED FRACTAL IMAGE COMPRESSION WITH QUADTREE SEGMENTATION", International Conference on Image Processing (ICIP'97), Oct. 2000.
[30] K.Belloulata, J.Konrad, " Fractal Image Compression with Region-Based Functionality", IEEE Trans. Image Process., vol. 11 , no. 4, Apr 2002.
[31] S.C.Hsiung, J.H.Jeng, "Contrast Prediction for Fractal Image Compression", The 24th Workshop on Combinatorial Mathematics and Computation Theory, Apr 2004.
[32] M.Hassaballah, M.M.Makky, Y.B.Mahdy, " A Fast Fractal Image Compression Method Based Entropy", Electronic Letters on Computer Vision and Image Analysis 5(1):30-40, 2005.
[33] B.E.W.G.Jager, " On the reduction of fractal image compression encoding time", Appendix A, pp. 903-919, New York: Springer- Verlag, 1995.
[34] J.Zhong, R. Ning. " Image Denoising Based on Wavelets and Multifractals for Singularity Detection", IEEE Trans. Image Process., vol. 14 , no.10, Oct 2004.
[35] M.Ghazel, G.H. Freeman, E. R.Vrscay. " Fractal-Wavelet Image Denoising Revisited", IEEE Trans. Image Process., vol. 11 , no. 1, Sep 2006.
[36] C.S. Tong, and M. Pi. Fast Fractal Encoding Based on Adaptive Search. IEEE Trans. on Image Proc.10, No.9, pp.1269-1277, Sept. 2001.
[37] N.Ponomarenko1, K.Egiazarian2, V. Lukin. " IEEE Transactions on Image Processing, 8(12), pp.1716-1729, 2000.
[38] M.Mohamed, D.Aoued, "OPTIMIZATION OF FRACTAL IMAGE COMPRESSION BASED ON KOHONEN NEURAL NETWORKS".
[39] D. Saupe and R. Hamzaoui. "Complexity Reduction Methods for Fractal Image Compression". In I.M.A. Conf. Proc. on Image Processing; Mathematical methods and applications, Sept., J.M. Blackedge (ed.), 1994.
[40] A. Aggarwal, R.Kunal, " PARTITIONED FRACTAL IMAGE COMPRESSION FOR BINARY IMAGES USING GENETIC ALGORITHMS".
[41] J.Harbi, N.Adeeb. "Fractal Image Compression Using Block Indexing Technique" Journal of multimedia, vol. 2, NO. 3, June 2002.
[42] D.Saupe, M. Ruhl_, R. Hamzaoui_, L.Grandi_, D. Marin, " OPTIMAL HIERARCHICAL PARTITIONS FOR FRACTAL IMAGE COMPRESSION", IEEE International Conference on Image Processing (ICIP'98), Chicago, Oct. 1998.
[43] Y.R.song, S.Jun, "A Novel Fractal Image Compression Scheme with Hybrid Affine Transformations", Journal of Communication and Computer, ISSN1548-7709, USA, , Volume 2, No.9 (Serial No.10) Sep. 2005.
[44] C.T.Wang, T.S.Chen, S.H.He, "Detecting and restoring the tampered images based on iteration-free fractal compression", elsevir, The Journal of Systems and Software 67, p. 131-140, Apr 2002.
[45] M.Wang, C.H.Lai, " A Hybrid Fractal Video Compression Method", elsevir, Computers and Mathematms wzth Apphcatmns 50, p. 611-621, nov 2004.
[46] K.Belloulata, S.Zhu, " A New Object-Based System for Fractal Video Sequences Compression", Journal of multimedia, vol. 2, NO. 3, June 2007.
[47] A.F.Abate, R.Distasi, M.Nappi, D.Riccio, "Face authentication using speed fractal technique", elsevir,Image and Vision Computing 24,p. 977-986, Feb 2006
[48] M. Barnsley and A. Jacquin. "Application of recurrent iterated function system to images". SPIE Visual Communications and Image Processing, 1001:122-131, 1988.
[49] J. Hutchinson," Fractals and self-similarity", Indiana Univ. J. Math. 30 (1981), 713-747.
[50] M. F.Barnsley and S. G. Demko, "Iterated function systems and the global construction of fractals", Proc. Roy. Soc. London A399 (1985), 2433-275.
[51]. M.-H. Tayarani- N and M.- R. Akbarzadeh-T "A Sinusoid Size Ring Structure Quantum Evolutionary Algorithm". IEEE International Conference on Cybernetics and Intelligent Systems Robotics, Automation and Mechanics 2008.
[52] M.-H. Tayarani- N and M.- R. Akbarzadeh-T "Improvement of Quantum Evolutionary Algorithm with Functional Sized Population". WSC 2008 Online World Conference on Soft Computing in Industrial Applications 10th – 21st of November 2008.
[53] K. Han, J. Kim, "Quantum-inspired evolutionary algorithm for a class of combinatorial optimization," IEEE Trans. on Evolutionary Computation, vol. 6, no. 6, 2002.

1 – Variable – Length – Coding
2 – MSE (Mean-Square-Error)
3 – SNR (Signal-to-Noise-Ratio)
4 – PSNR(Peak – SNR)
5 – Gray Levels
6 – Predictive Coding
7 – Vector – Quantization
8 – Subband- Coding
9 – Redundancy
10 – Correlation
11 – Mapping
12 – Quantization
13 – Error – Tolerance
14 – Image-Fidelity
15 (Mean-Square-Error)
16 – Mean-Square-Signal-to-Noise-Ratio
17 – Peak-SNR
18 – Predictive-Coding
19 – Differential Pulse Code Modulation
20 – Polarity
21 – Adaptive Techniques
22 – Transform-Coding
23- Optimum
24 – Suboptimum
25 — Karhunen-Loeve-Transform)KLT)
26 -Haar
27- Slant
28 -Hadamard
29 – Zonal
30 – Threshold
31 – grains
32 – fraction
33 – Linear Fractals
34 – Non Linear Fractals
35 – Random Fractals
36 – Sierpinski
37 – julia
38 – Deterministic
39 – chaotic
40 – Butterfly Effect
41 – Self similarity
42 – Iterative formation
43 – Fractional dimension
44 – Multiple-Reduction-Copy-Machine
45 – Attractor
46 – Iterated Function System
47 – Hutchinson
48 – Fixed-Point
49 – Random Iteration
50 – Chaos Game
51 – Re-Create
52 – Brightness
53 – Contrast
54 – Partitioned- MRCM
55 – Domain
56 – Range
57 – Overlap
58 – Collage
59 – Hausdorff
60 – Blockness
61 – Morphing
62 – Overlap
63 – Image Segmentation
64 – Quadtree Partitioning
65 -Low-Detail
66 – Horizontal Vertical Partitiong
67 – Traingular Partitioning
68 – Classification Techniques
69 – Shade
70 – Midrange
71 – Edge
72 – Mixed
73 -Low-detail
74 – High-detail
75 – Thresholds
76 – Fractal Block Transforms
77 – Spatial Contraction
78 – Isometric
79 – Gray Level Scaling&Translation
80 – Dynamic Range
81 – Fractal Image Format
82 – Header
83 Resolution
—————

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

—————

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

4