چکیدهبخشبندی تصویر یک فرآیند اساسی در بسیاری از کاربردهای پردازش تصویر و بینایی ماشین است که میتواند به عنوان اولین مرحله پردازش سطح پایین در پردازش تصاویر دیجیتالی در نظر گرفته شود. بخشبندی تصویر کاربردهای گوناگونی مانند پردازش تصاویر پزشکی، شناسایی چهره، سیستمهای کنترل ترافیک و غیره دارد.با توجه به اهمیت بخشبندی تصاویر دیجیتالی روشهای متعددی برای این منظور پیشنهاد شده است که به دو دسته کلی روشهای مبتنی بر ناحیه مانند خوشهبندی پیکسلهای تصویر و روشهای مبتنی بر تشخیص لبه تقسیم میگردد. بیشتر روشهای خوشهبندی تصاویر، پیکسلها را تنها بر اساس اطلاعات شدت روشنایی یا رنگ آنها دستهبندی میکنند و هیچگونه اطلاعات همسایگی یا مکانی پیکسلها را در روند خوشهبندی تصویر به کار نمیبرند که این عامل سبب کاهش دقت و کیفیت بخشبندی میگردد.با در نظر گرفتن اهمیت به کارگیری اطلاعات مکانی پیکسلها در جهت بهبود کیفیت بخشبندی تصویر، استفاده از اطلاعات پیکسلهای همسایه در پنجره همسایگی بزرگ سبب بهبود کیفیت بخشبندی میگردد. با توجه به اینکه خوشهبندی جزء مسائل چندجملهای غیرقطعی-سخت محسوب میشود، در این پژوهش ایده ترکیب الگوریتم خوشهبندی k-means و الگوریتم رقابت استعماری بهبودیافته جهت حل این مسئله پیشنهاد گردیده است. همچنین پیش از اعمال الگوریتم ترکیبی، تصویر جدیدی با استفاده از اطلاعات غیرمحلی پیکسلها ایجاد شده و سپس الگوریتم ترکیبی برای خوشهبندی پیکسلهای تصویر جدید به کار گرفته شده است. با مقایسه نتایج حاصل از اعمال روش مذکور بر روی تصاویر مختلف با سایر روشها، به این نتیجه رسیدیم که دقت بخشبندی اکثر تصاویر با روش پیشنهادی، بیشتر از سایر الگوریتمهای مطرح در این زمینه است. واژههای کلیدی: بخشبندی تصویر، خوشهبندی، الگوریتم رقابت استعماری بهبودیافته و اطلاعات غیرمحلی فهرست مطالبعنوان شماره صفحهفصل 1 مقدمه ............................................................................................................................. 1فصل 2 شرح مسئله ................................................................................................................... 52-1 بیان مسئله ............................................................................................................................................. 62-2 ورودی-فرضها-خروجی ..................................................................................................................... 72-3 هدف ........................................................................................................................................................ 82-4 معیار ارزیابی .......................................................................................................................................... 82-5 نتایج موردانتظار .................................................................................................................................. 92-6 خلاصه فصل ........................................................................................................................................ 10فصل 3 مفاهیم پایهای ............................................................................................................ 11 3-1 مفاهیم مربوط به پردازش تصویر و بخشبندی ............................................................................ 123-1-1 تشخیص لبه با استفاده از روش سوبل .................................................................................. 133-1-2 بخشبندی تصویر ...................................................................................................................... 133-1-3 تحلیل مؤلفههای اصلی ............................................................................................................ 143-1-4 اطلاعات محلی و مکانی پیکسلها ........................................................................................ 143-2 الگوریتم K-means............................................................................................................................ 153-3 الگوریتم رقابت استعماری ................................................................................................................. 153-4 خلاصه فصل ........................................................................................................................................ 17فصل 4 راهکارهای گذشته ..................................................................................................... 184-1 استفاده از خوشهبندی c-means فازی به همراه جمله جریمه برای بخشبندی تصویر ........ 194-2 بخشبندی تصویر با استفاده از الگوریتم ژنتیک مبتنی بر روش خوشهبندی فازی .............. 214-3 الگوریتم FCMS.................................................................................................................................. 224-4 الگوریتم EnFCM ............................................................................................................................... 224-5 الگوریتم FGFCM .............................................................................................................................. 234-6 الگوریتم خوشهبندی فازی مبتنی بر انتخاب بهینه و اطلاعات همسایگی سازگار ................ 234-7 خلاصه فصل ......................................................................................................................................... 24فصل 5 راهکار پیشنهادی ..................................................................................................... 255-1 جمعآوری اطلاعات غیرمحلی تصویر .............................................................................................. 275-1-1 محاسبه وزن در جمعآوری اطلاعات غیرمحلی .................................................................. 275-1-2 محاسبه مقدار ویژگی میانگین وزندار غیرمحلی .............................................................. 315-2 ترکیب الگوریتم رقابت استعماری و الگوریتم K-means........................................................... 315-3 الگوریتم رقابت استعماری بهبودیافته پیشنهادی برای بخشبندی تصویر ........................... 325-3-1 کدگذاری .................................................................................................................................... 325-3-2 عملگر جذب .............................................................................................................................. 335-3-3 عملگر انقلاب ............................................................................................................................ 345-3-4 عملگر جدید حرکت استعمارگرها ....................................................................................... 345-3-5 عملگر جدید جستجوی فضای اطراف قویترین استعمارگر .......................................... 355-3-6 تابع هزینه الگوریتم NLICA................................................................................................ 365-4 پسپردازش ساده .............................................................................................................................. 365-5 خلاصه فصل ....................................................................................................................................... 38فصل 6 ارزیابی و نتایج عملی ............................................................................................. 406-1 معرفی تصاویر محک ....................................................................................................................... 416-2 تحلیل نتایج الگوریتم NLICA ...................................................................................................... 436-2-1 تحلیل نتایج بخشبندی تصاویر مصنوعی ......................................................................... 446-2-2 تحلیل نتایج بخشبندی تصاویر طبیعی ............................................................................ 476-3 پایداری الگوریتم NLICA........................................................................................................... 526-4 همگرایی الگوریتم NLICA......................................................................................................... 566-5 آزمونهای آماری ........................................................................................................................... 576-5-1 نمودار چندک-چندک ........................................................................................................ 596-5-2 آزمون کولموگروف-اسمیرنوف .......................................................................................... 606-5-3 آزمون ویلکاکسون رتبهای ................................................................................................. 616-6 تحلیل کلی نتایج ......................................................................................................................... 636-7 خلاصه فصل ................................................................................................................................. 64فصل 7 نتیجهگیری و راهکارهای آتی .............................................................................. 647-1 نتیجهگیری ..................................................................................................................................... 657-2 راهکارهای آتی ................................................................................................................................ 66واژهنامه ............................................................................................................................. 67مراجع ............................................................................................................................... 72 فهرست شکلهاعنوان شماره صفحه شکل 2-1: تصویر بخشبندیشده تصویر روبرو [1]......................................................................................... 8شکل 2-2: تصویری از یک جاده [1]................................................................................................................... 8شکل 3-1: روند کلی فرآیند پردازش تصویر .................................................................................................... 12شکل 3-2: نقابهای افقی و عمودی سوبل ..................................................................................................... 13شکل 3-3: کارنمای الگوریتم رقابت استعماری[16] .................................................................................... 16شکل 5-1: کارنمای روش پیشنهادی ............................................................................................................... 26شکل 5-2: همسایگی محلی و غیرمحلی پیکسل مرکزی ............................................................................ 27شکل 5-3: نقاب میانگین 3*3 .......................................................................................................................... 28شکل 5-4: مراحل به دست آوردن مقادیر ویژه تکههای تصویر و تخمین واریانس نویز[30] ............. 29شکل 5-5: ساختار کشورها در الگوریتم NLICA......................................................................................... 32شکل 5-6: نمونهای از حرکت مستعمره به سمت استعمارگر در الگوریتم NLICA ................................. 33شکل 5-7: مثالی از عملگر انقلاب .................................................................................................................... 34شکل 5-8: حرکت استعمارگر به سمت قویترین استعمارگر .................................................................... 35شکل 5-9: تولید جوابهای کاندید در اطراف بهترین استعمارگر ............................................................ 35شکل 5-10: نمونهای از اعمال پسپردازش پیشنهادی بر روی قسمتی از تصویر بخشبندی شده .. 38شکل 5-11: شبه کد مرحله پسپردازش ...................................................................................................... 38شکل 6-1: تصاویر محک مصنوعی .................................................................................................................. 42شکل 6-2: تصویر محک #238011 (سمت راست) و تصویر بخشبندی شده مرجع (سمت چپ) .. 42شکل 6-3: تصویر محک #167062 (سمت راست) و تصویر بخشبندی شده مرجع (سمت چپ) ... 42شکل 6-4: تصویر محک #42049(سمت راست) و تصویر بخشبندی شده مرجع (سمت چپ) ...... 43شکل 6-5: تصاویر محک مصنوعی بخشبندی شده با الگوریتم NLICA............................................... 45شکل 6-6: تصویر بخشبندی شده تصویر محک #238011....................................................................... 48شکل 6-7: تصویر بخشبندی شده تصویر محک #167062....................................................................... 48شکل 6-8: تصویر بخشبندی شده تصویر محک #42049......................................................................... 49شکل 6-9: نتایج بخشبندی تصویر #238011 با روشهای مختلف ........................................................ 51شکل 6-10: نتایج بخشبندی تصویر #167062 با روشهای مختلف ..................................................... 53شکل 6-11: نتایج بخشبندی تصویر #42049 با روشهای مختلف ........................................................ 54شکل 6-12: نمودار پایداری الگوریتم NLICA............................................................................................ 55شکل 6-13: نمودار همگرایی الگوریتم NLICA......................................................................................... 56شکل 6-14: نمودار چندک-چندک برای تصاویر دارای انحراف معیار ................................................... 60فهرست جداولعنوان شماره صفحهجدول 6-1: تعداد خوشههای تصاویر محک طبیعی .................................................................................... 43جدول 6-2: پارامترهای الگوریتم NLICAبرای بخشبندی تصاویر ....................................................... 44جدول 6-3: نتایج اعمال الگوریتم NLICAبر روی تصاویر محک مصنوعی ......................................... 44جدول 6-4: مقایسه نتایج بخشبندی تصویر محک شماره 1 با روشهای مختلف .............................. 46جدول 6-5: مقایسه نتایج بخشبندی تصویر محک شماره 2 با روشهای مختلف .............................. 46جدول 6-6: مقایسه نتایج بخشبندی تصویر محک شماره 3 با روشهای مختلف .............................. 47جدول 6-7: نتایج بخشبندی تصاویر محک طبیعی با استفاده از الگوریتم NLICA .......................... 48جدول 6-8: نتایج بخشبندی تصاویر محک نویزدار با استفاده از الگوریتم NLICA.......................... 49جدول 6-9: مقایسه نتایج بخشبندی تصاویر محک با استفاده از الگوریتمهای مختلف ................... 50جدول 6-10: خلاصه اطلاعات جوابهای به دست آمده در اجراهای مختلف ..................................... 57جدول 6-11: نتایج آزمون ویلکاکسون رتبهای ........................................................................................... 61جدول 6-12: مقایسه روشهای مختلف بخشبندی تصویر ..................................................................... 63 فصل 1 مقدمهپردازش تصاویر[1] امروزه بیشتر به موضوع پردازش تصویر دیجیتال گفته میشود که شاخه‌ای از دانش رایانه است که با پردازش سیگنال دیجیتال که نماینده تصاویر برداشته شده با دوربین دیجیتال یا پویش شده توسط پویشگر هستند، سر و کار دارد. پردازش تصاویر دارای دو شاخه بهبود تصاویر[2] و بینایی ماشین[3] است. بهبود تصاویر روشهایی چون استفاده از صافی محوکننده و افزایش تضاد برای بهتر کردن کیفیت دیداری تصاویر و اطمینان از نمایش درست آنها در محیط مقصد (مانند چاپگر یا نمایشگر رایانه) است، در حالی که بینایی ماشین به روشهایی می‌پردازد که به کمک آنها میتوان معنی و محتوای تصاویر را درک کرد تا از آنها در کارهایی چون رباتیک استفاده شود. بخشبندی تصویر یکی از مهمترین مراحل اساسی در پردازش تصاویر دیجیتالی است. ناحیهبندی تصویر عبارت است از تفکیک پیکسلهای تصویر به نواحی مجزایی که بر حسب ویژگیهایی مانند شدت روشنایی، بافت و یا رنگ، یکسان هستند و یا تا حد ممکن همبستگی دارند. ناحیهبندی تصاویر در بسیاری از کارهای پردازشی بر روی تصاویر، چون تصاویر درمانی، بینایی ماشین، فشردهسازی تصویر، شیءشناسی، نیازی ضروری و مهم برای شروع پردازش بر روی شیء یا بافت موردنظر میباشد.بخشبندی تصویر به روشهای مختلفی انجام میپذیرد که به طور کلی میتوان آن را به دو دسته کلاسیک و شکلشناسی، تقسیم کرد. در روشهای کلاسیک و سنتی از تغییرات شدت روشنایی به منظور استخراج لبهها و ویژگی‌های محلی اشیاء مورد نظر، استفاده میگردد. نوع دیگری از الگوریتمهای کلاسیک، روشهای مبتنی بر الگوریتمهای آماری میباشد که در آنها تقسیمبندی بر اساس توزیع پیکسلها و یافتن آستانهی مناسب صورت میپذیرد. از آنجا که تصاویر اغلب دارای نویز، درهمریختگی[4]، انسداد، تأثیرپذیری از نورتابانی و موارد اینچنین میباشند، این روشها برای بسیاری از کاربردها غیرقابل استفاده میباشند. روشهای جدیدتری که امروزه مورد استفاده قرار میگیرند، با استفاده از کلاسبندی (خوشهبندی)، به ناحیهبندی و تقسیمبندی تصویر میپردازند. این الگوریتمها مانند الگوریتمهای خوشهبندی Fuzzy C-meansو K-means، الگوریتمهای شبکه عصبی چون آموزش رقابتی ساده[5]، درخت آموزشی ساده بیز و غیره میباشند. این روشها هرچند از دقت تشخیص خوبی برخوردار هستند، اما بسیار به مقداردهی اولیه (درK-meansمقداردهی اولیه مراکز خوشهها و درشبکههای عصبینرخ آموزشی) وابسته میباشند و میبایست بارها و بارها الگوریتم بر روی تصویر اعمال گردد تا جواب بهینه به دست آید. با این حال همگرایی در این روشها همواره تضمین شده نبوده و در بعضی موارد در بهینه محلی به دام میافتند. یافتن مراکز بهینه خوشههای تصویر جزء مسائل غیرچندجملهای سخت محسوب میگردد. از طرفی دیگر در اکثر روشها، خوشهبندی پیکسلها بر اساس ویژگیهایی مانند رنگ یا شدت روشنایی انجام میگیرد و از هیچگونه اطلاعات مکانی یا همسایگی پیکسلها استفاده نمیشود که این خود باعث میگردد این روشها در بخشبندی تصاویر نویزدار از کارایی لازم برخوردار نباشد. همچنین بر اساس این اصل که پیکسلهای همسایه در تصویر با هم همبسته میباشند و با توجه به این که بیشتر الگوریتمهای خوشهبندی پیکسلها بدون در نظرگرفتن تشابه بین پیکسلهای همسایه اقدام به بخشبندی پیکسلهای تصویر میکنند، تصویر به اصطلاح دچار بیش بخشبندی[6] میشود (به تعداد ناحیههای زیادی تقسیم میگردد.)بخشبندی تصویر با استفاده از خوشهبندی و بهرهگیری از اطلاعات همسایگی پیکسلها در سالهای اخیر مورد توجه پژوهشگران قرار گرفته است. احمد و همکارانش اطلاعات شدت روشنایی محلی را به وسیله اصلاح تابع هدف الگوریتم [7]FCM برای بخشبندی تصویر معرفی نمودند به طوری که برچسبگذاری پیکسلها تحت تأثیر همسایگی محلی آنها انجام گرفت [1]. چن و ژانگ دو نسخه جدید از الگوریتم FCM را معرفی کردند که جمله همسایگی پیش از اعمال خوشهبندی فازی، محاسبه میشد [2]. زیلاگی و همکارانش FCM بهبود یافته را به منظور تسریع بخشبندی تصویر معرفی کردند که یک تصویر مجموع وزندار خطی با استفاده از تصویر اصلی محاسبه شده و سپس الگوریتم خوشهبندی FCM بر روی هیستوگرام[8] تصویر ایجاد شده جدید اعمال گردید[3]. الگوریتم FGFCM[9] به وسیله کای و همکارانش پیشنهاد شد [4]. عملکرد این روش بر اساس ایجاد تصویر جدید با استفاده از معیار شباهتی که اطلاعات مکانی و اطلاعات محلی شدت روشنایی را ترکیب میکرد، استوار بود.هالدر و همکارانش رویکردی تکاملی برای بخشبندی بدونمربی تصویر ارائه دادند که هدف آن خوشهبندی پیکسلها بر اساس اطلاعات شدت روشنایی و روابط همسایگی پیکسلها، با استفاده از الگوریتم ژنتیک بود [5]. ایده استفاده از اطلاعات غیرمحلی پیکسلها که مبتنی بر فیلتر میانگین غیرمحلی بود، جهت خوشهبندی پیکسلهای تصویر نویزدار توسط ژائو و همکارانش مطرح گردید [6].در این پایاننامه الگوریتم خوشهبندی K-means که یکی از رایجترین روشهای خوشهبندی است، با الگوریتم رقابت استعماری بهبودیافته ترکیب میشود. از تابع هدف الگوریتم K-means در الگوریتم رقابت استعماری بهبودیافته به منظور پیداکردن مراکز بهینه خوشههای دادههای پیکسلهای تصویر استفاده میشود و یک مرحله پیشپردازش به منظور بهرهگیری از اطلاعات محلی و غیرمحلی پیکسلها قبل از اجرای الگوریتم رقابت استعماری، بر روی تصویر ورودی اعمال میگردد. ایده استفاده از اطلاعات غیرمحلی از فیلتر میانگین غیرمحلی که برای کاهش اثر نویز گوسی[10] پیشنهاد شده بود [10]، گرفته شده است. برای مشاهده کردن نتایج، الگوریتم پیشنهادی را بر روی تصاویر مصنوعی تخریبشده با نویز گوسین و همچنین بر روی تصاویر طبیعی اعمال کردیم.ادامه مطالب پایاننامه بدین شرح سازماندهی میشود، در فصل دوم شرح مسئله بیان میشود که بخشبندی تصویر معرفی شده و ورودی و خروجی مسئله و هدف از انجام بخشبندی بر روی تصاویر بررسی میگردد. در فصل سوم مفاهیم پایهای مطرح میشود و الگوریتم خوشهبندی K-means و رقابت استعماری بهبودیافته شرح داده شده و سپس با برخی مفاهیم پردازش تصویر و بینایی ماشین آشنا میشویم. در فصل چهارم بر اساس بررسیهای انجامشده به مروری بر کارهای گذشته در زمینه بخشبندی تصویر و بخشبندی تصاویر نویزدار خواهیم پرداخت. در فصل پنجم جزئیات روش پیشنهادی شامل بهبود الگوریتم رقابت استعماری و ترکیب آن با الگوریتم K-means، استفاده از اطلاعات غیرمحلی پیکسلها و بهبود ارائهشده جهت استفاده آن در بخشبندی تصویر بررسی میشود. در فصل ششم نتایج حاصل از بخشبندی تصاویر مختلف با الگوریتم پیشنهادی و مقایسه آن با روشهای دیگر، مورد تحلیل و بررسی قرار میگیرد و در نهایت در فصل هفتم، نتیجهگیری و بررسی مزایا و معایب روش پیشنهادی و راهکارهای آتی را خواهیم داشت.