(۳-۱)

که در آن c­_j مرکز خوشه j ام و از فاصله اقلیدسی برای محاسبه فاصله داده i ام از مرکز خوشه j ام استفاده می­ شود. الگوریتم K-means به وسیله به ­روز ­رسانی مراکز خوشه ­ها سعی در کمینه­سازی تابع هدف فوق دارد.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

۳-۳ الگوریتم رقابت استعماری
الگوریتم رقابت استعماری [۱۶] روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینه­سازی می‌پردازد. این الگوریتم با مدلسازی ریاضی فرایند تکامل اجتماعی- سیاسی، الگوریتمی برای حل مسائل ریاضی بهینه­سازی ارائه می‌دهد. همانند همه الگوریتم­های تکاملی، الگوریتم رقابت استعماری نیز مجموعه اولیه­ای از جواب­های احتمالی را تشکیل می­دهد. این جواب­های اولیه در الگوریتم ژنتیک با عنوان “کروموزوم"، در الگوریتم ازدحام ذرات با عنوان “ذره” و در الگوریتم رقابت استعماری نیز با عنوان “کشور” شناخته می­شوند. برای شروع الگوریتم، تعدادی کشور اولیه را ایجاد می‌کنیم و تعدادی از بهترین اعضای این جمعیت (کشورهای دارای کمترین مقدار تابع هزینه) را به عنوان استعمارگر انتخاب می‌کنیم. باقیمانده کشورها  مستعمراتی را تشکیل می‌دهند که هرکدام به یک امپراطوری تعلق دارند. برای تقسیم مستعمرات اولیه بین استعمارگرها، به هر استعمارگر، تعدادی از مستعمرات را که این تعداد، متناسب با قدرت آن است، می‌دهیم. سپس مستعمرات به سمت استعمارگری که در قلمرو آن واقع­اند، حرکت
می­ کنند. در راستای سیاست جذب، کشور مستعمره به اندازه x واحد در جهت خط واصل مستعمره به استعمارگر، حرکت کرده و به موقعیت جدید کشانده می‌شود که x عددی تصادفی با توزیع یکنواخت است و مستعمره هنگام حرکت کردن، انحرافی نیز به اندازه زاویه تصادفی از خط واصل داراست. مرحله بعدی اعمال عملگر انقلاب بر روی مستعمرات می­باشد که در الگوریتم رقابت استعماری، انقلاب با جابجایی تصادفی یک کشور مستعمره به یک موقعیت تصادفی جدید مدلسازی می­ شود. در حین حرکت مستعمرات به سمت کشور استعمارگر، ممکن است بعضی از این مستعمرات به موقعیتی بهتر از استعمارگر برسند (به نقاطی در تابع هزینه برسند که هزینه کمتری را نسبت به مقدار تابع هزینه در موقعیت استعمارگر، تولید می‌کنند.) که در این حالت، کشور استعمارگر و کشور مستعمره، جای خود را با همدیگر عوض می­ کنند. قدرت یک امپراطوری به صورت قدرت کشور استعمارگر، به اضافه درصدی از قدرت کل مستعمرات آن تعریف می‌شود. مرحله بعد رقابت استعماری بین استعمارگرهاست؛ یکی یا چند مورد از ضعیف‌ترین مستعمرات ضعیف‌ترین امپراطوری را برداشته و برای تصاحب این مستعمرات، رقابتی را میان کلیه استعمارگر‌ها ایجاد می‌کنیم. مستعمرات مذکور، لزوماً توسط قوی­ترین استعمارگر، تصاحب نخواهند شد، بلکه استعمارگر‌های قوی­تر، احتمال تصاحب بیشتری دارند. در نهایت استعمارگرهایی که تمامی مستعمرات خود را از دست داده­اند، خود به عنوان مستعمره یکی از استعمارگرهای دیگر انتخاب می­گردند. شکل۳-۳ کارنمای الگوریتم رقابت استعماری را نمایش می­دهد.
بلی
جابجایی استعمارگر و مستعمره
خیر
محاسبه هزینه کلی هر امپراتوری (مجموع هزینه استعمارگر و درصدی از هزینه­ های مستعمرات)
انتخاب کشورهای استعمارگر و تقسیم مستعمرات بین استعمارگرها
ضعیف­ترین مستعمره و یا مستعمرات مربوط به ضعیف­ترین امپراتوری را برداشته و آن را به امپراتوری که احتمال زیادی برای تصاحب مستعمره دارد، بده
حرکت مستعمرات به سمت استعمارگری که در قلمرو آن قرار دارند (با اتدازه و زاویه تصادفی)
انقلاب (تغییر ناگهانی در موقعیت مستعمرات)
آیا امپراتوری وجود دارد که مستعمره­ای نداشته باشد؟
آیا مستعمره­ای در یک امپراتوری وجود دارد که دارای هزینه بهتری نسبت به استعمارگر مربوطه­اش باشد؟
بلی
حذف استعمارگرهای بدون مستعمره
شکل ۳-۳: کارنمای الگوریتم رقابت استعماری [۱۶]
خیر
شرط خاتمه
۳-۴ خلاصه فصل
در این فصل تعریفی از پردازش تصویر و بخش­بندی تصویر ارائه شد. همچنین درباره لبه­های تصویر و آشکارسازی آنها نکاتی مطرح و یکی از روش­های معروف جهت تشخیص لبه­های تصویر معرفی گردید. در ادامه در مورد اطلاعات غیرمحلی تصویر و نحوه بهره­ گیری از آنها به منظور تخمین مقدار واقعی یک پیکسل بحث گردید. همچنین مروری بر الگوریتم خوشه­بندی K-means که یکی از ساده­ترین و معروف­ترین الگوریتم­ها جهت خوشه­بندی داده ­ها است، داشته و در ادامه با مراحل مختلف الگوریتم رقابت استعماری آشنا شدیم و در مورد هر کدام از مراحل این الگوریتم توضیح داده شد.
فصل ۴
راه­کارهای گذشته
در این فصل روش­های مختلف بخش­بندی تصاویر شرح داده شده و مزایا و معایب هر کدام از روش­ها بررسی می­گردند. هر کدام از روش­های قطعه­بندی یا بخش­بندی تصاویر مزایایی دارد؛ به عنوان مثال برخی از روش­ها نیازی به مشخص کردن تعداد ناحیه­های موجود در تصویر توسط کاربر نداشته و به صورت بدون­­ مربی عمل می­ کنند. استفاده از اطلاعات مکانی پیکسل­ها (روابط همسایگی پیکسل­)، باعث مقاوم شدن الگوریتم بخش­بندی­کننده در برابر نویز و غیریکنواختی­های موجود در تصویر ورودی می­گردد. بعضی از روش­های بخش­بندی تصاویر تنها بر اساس شباهت ویژگی­هایی مانند شدت روشنایی عمل می­ کنند و برخی دیگر علاوه بر ویژگی­های شدت روشنایی، رنگ، بافت و غیره، از اطلاعات مکانی تصویر استفاده می­ کنند.
۴-۱ استفاده از خوشه­بندی Cmeansفازی به همراه جمله جریمه برای بخش­بندی تصویر
وای یانگ^[۱۷] در سال ۲۰۰۷[۸] برای غلبه بر حساسیت الگوریتم FCM به نویز، الگوریتم FCM توسعه یافته برای بخش­بندی تصویر را پیشنهاد کرد. الگوریتم توسعه ­یافته به وسیله اصلاح تابع هدف الگوریتم FCM استاندارد به دست آمد. در الگوریتم مذکور تأثیر پیکسل­های همسایه بر پیکسل­ مرکزی همسایگی با افزودن جمله جریمه به تابع هدف الگوریتم FCM استاندارد اعمال گردید. در این روش وابستگی مکانی یک مجموعه داده با بهره گرفتن از ماتریس W که در آن w_ij در صورتی که داده ­های x_i و x_j مجاور باشند، یک بوده و در غیر این صورت صفر است، تعریف می­ شود. در تابع هدف الگوریتم FCM استاندارد از هیچ اطلاعات مکانی استفاده نشده است؛ یعنی فرایند خوشه­بندی مستقل از پیکسل­های تصویر، فقط به سطوح شدت پیکسل­ها بستگی دارد که این محدودیت باعث حساسیت FCM نسبت به نویز شده است. برای اعمال ساختار همسایگی به الگوریتم FCM از یک جمله جریمه در تابع هدف آن استفاده شده است. تابع هدف جدید در صفحه بعدی آمده است.

(۴-۱)

که در آن w_kj برای بررسی همسایه بودن x_j و x_k می­باشد و گاما تأثیر جمله جریمه را تنظیم می­نماید، است. جمله جریمه زمانی که عضویت یک پیکسل و پیکسل­های همسایه­اش در کلاس مشخصی بزرگ باشد، کمینه می­ شود و اگر عضویت پیکسل در کلاسی بیشتر ولی عضویت همسایه­هایش در همان کلاس کوچک باشد، افزایش می­یابد. در واقع جمله جریمه محدودیت شباهت مقدار عضویت پیکسل و پیکسل­های
همسایه­اش در یک کلاس را اعمال می­ کند. تابع هدف جریمه شده می ­تواند با روش مشابهی به الگوریتم FCM استاندارد کمینه شود. الگوریتمی تکراری به وسیله ارزیابی مراکز خوشه و عضویت­ها برای ارضای شرط گرادیان صفر به دست می ­آید. با اعمال این محدودیت که مجموع عضویت یک داده در تمام کلاس­ها برابر یک باشد، به تابع هدف جریمه شده و با گرفتن مشتق جزئی از این عبارت نسبت به u_ik و با مساوی صفر قرار دادن حاصل عبارت جدیدی برای u_ik (درجه عضویت دادهkام درخوشه i) به صورت:

(۴-۲)