-
- در هر ناحیه باید شباهت برقرار باشد.
در شرطهای بالا P معیاری برای سنجش نزدیکی معیار شباهت مانند شدت روشنایی پیکسلهای متعلق به یک ناحیه است. پس از انجام خوشهبندی بر روی پیکسلهای تصویر، فاصله بین پیکسلهای متعلق به یک ناحیه در فضای ویژگیها باید کمینه و فاصله بین پیکسلهای متعلق به خوشههای مختلف، بیشترین مقدار را داشته باشد. در تابع هدف الگوریتم K-means، یکی از اهداف اشاره شده بهینه می شود؛ یعنی مراکز خوشه ها طوری انتخاب میگردند که فاصله تکتک پیکسلها از مرکز خوشه مربوطه کمترین مقدار را داشته باشد. در برخی از مقالات هر دو هدف مورد توجه قرار گرفته و بهینه شده اند. برای مثال در معیار Turi که به صورت:
(۲-۱) |
است، هر دو معیار بهینه میشوند. در فرمول فوق، intra برابر با میانگین فاصله پیکسلها از مرکز خوشهشان و inter برابر با فاصله نزدیکترین مراکز خوشه ها است. Y هم برابر با c*N(2,1) که در آن c ثابت و N(2,1) توزیع نرمال با میانگین ۲ و واریانس ۱ میباشد که متغیر تصادفی تعداد خوشه ها است. از این معیار اعتبار خوشهبندی در بخشبندی خودکار تصاویر استفاده میشود که علاوه بر بهینهسازی اهداف ذکر شده، از انتخاب تعداد خوشههای کم جلوگیری می کند.
۲-۲ ورودی، فرضها و خروجی
ورودی الگوریتم پیشنهادی تصویر مقیاس خاکستری با ابعاد M*N (تعداد سطرهای M و تعداد ستونهای N) و تعداد ناحیههای تصویر ورودی است. هر پیکسل تصویر ورودی دارای شدت روشنایی مشخصی بوده و اکثر موارد شدت روشنایی در بازه ۰ تا ۲۵۵ انتخاب می شود که ۰ به مفهوم سیاه مطلق و ۲۵۵ بیشترین مقدار بازه یا به عنوان سفید مطلق در نظر گرفته می شود. البته در بعضی موارد مقدار شدت روشنایی
پیکسلها نرمالیزه می شود که در روش پیشنهادی مقادیر پیکسلهای تصویر ورودی پس از اعمال
پیشپردازش، به بازه ]۱و۰[ نگاشت میشوند و خوشهبندی بر روی پیکسلهای با مقادیر نرمال شده انجام
میگردد. توسط فرمول زیر میتوان مقدار شدت روشنایی پیکسل را نرمالیزه کرد:
(۲-۲) |
اگرچه تعیین تعداد دقیق ناحیههای موجود در تصویر کار دشواری است ولی به وسیله هیستوگرام تصویر میتوان تعداد نواحی را مشخص نمود؛ البته تعیین تعداد دقیق ناحیههای تصاویر نویزدار بدون انجام عملیات پیچیده امکان پذیر نیست. پس از اعمال الگوریتم خوشهبندی بر روی تصویر، پیکسلهای متعلق به یک خوشه یا ناحیه تصویر، با مقدار شدت روشنایی یکسانی (معمولاً شدت روشنایی مراکز خوشه ها) برچسب خورده و در تصویر خروجی نمایش داده میشوند. بنابراین تصویر خروجی شامل مقادیر شدت روشنایی برابر با تعداد ناحیهها یا بخشهای موجود در تصویر است.
۲-۳ هدف
اولین مرحله درتحلیل تصاویر، قطعهبندی یا بخشبندی میباشد. بخشبندی فرآیندی است که تصویر را به قسمت های اصلی سازندهاش تقسیم می کند. بدین معنی که اشیاء مختلف موجود در تصویر، با توجه به کاربرد موردنظر، از هم جدا میشوند تا تحلیل تصویر در مراحل بعدی راحتتر انجام بگیرد. از جمله موارد کاربردی بخشبندی در پردازش تصویر است که امروزه در اکثر شاخه های علمی و صنعتی مورد توجه بوده و در
بسیاری از شاخهها شناسایی اجزای اصلی سازنده تصویر دارای اهمیت زیادی است. به عنوان مثال تشخیص و رهگیری خودکار اهداف متحرک در کاربردهای نظامی و تفکیک محصولات مختلف در کاربردهای صنعتی را میتوان برخی از کاربردهای بخشبندی تصویر نام برد. در شکل ۲-۱ نمونه ای از بخشبندی تصویر نشان داده شده است.
شکل ۲-۱: تصویر بخشبندی شده تصویر روبرو [۱] شکل ۲-۲: تصویری از یک جاده [۱]
بخشبندی تصویر فرایند تخصیص برچسب به پیکسلها میباشد که پیکسلهای دارای برچسب یکسان، ویژگیهای مشابه و مشخصی دارند. بنابراین هدف از بخشبندی، تقسیم تصویر ورودی به ناحیههای مختلف به طوری که پیکسلهای درون یک ناحیه مشابه و پیکسلهای متعلق به نواحی مختلف، متفاوت از هم باشند، است.
۲-۴ معیار ارزیابی
کیفیت تصویر بخشبندی شده به میزان مشخص بودن اشیاء تصویر ورودی، در تصویر بخشبندی شده بستگی دارد. اشیاء یا ناحیههای تصویر معمولاً توسط اشخاص خبره و به وسیله کشیدن مرز پیرامون هر ناحیه یا برچسبگذاری پیکسلهای تصویر به صورت دستی توسط فرد خبره مشخص میگردند. به تصویر
برچسبگذاری شده به وسیله افراد متخصص، تصویر مرجع[۱۱] یا تصویر به صورت دستی بخشبندی شده[۱۲] گویند. یکی از معروفترین معیارهای مقایسه بخشبندی تصاویر ، معیار دقت[۱۳] است که میزان دقت به وسیله مقایسه تصویر بخشبندی شده با روش مورد ارزیابی و تصویر مرجع محاسبه میگردد. میزان دقت به وسیله مقایسه پیکسلهای تصویر ورودی که با الگوریتم موردنظر برچسبگذاری شده اند با برچسب پیکسل متناظرشان در تصویر مرجع و شمارش تعداد پیکسلهایی از تصویر بخشبندی شده به وسیله روش
مورد بررسی که با توجه به تصویر مرجع درست برچسب خوردهاند، محاسبه میگردد. میزان دقت به صورت زیر به دست می آید:
(۲-۳) |
روشی که میزان دقت بخشبندی بالایی داشته باشد، خطای کمتری نیز خواهد داشت و روش مناسبی جهت بخشبندی تصویر به شمار میرود. معمولاً الگوریتمهایی که میزان دقت بالای ۹۰ درصد داشته باشند، روش خوبی برای بخشبندی تصویر خواهند بود. میزان دقت معیار مناسبی به منظور محاسبه کارآیی
روشهای بخشبندی تصاویر نویزدار میباشد و در اکثر مقالات از این معیار جهت ارزیابی الگوریتمهای بخشبندی استفاده شده است. ما نیز در این پژوهش از معیار دقت برای ارزیابی و مقایسه روش پیشنهادی بهره بردهایم.
۲-۵ نتایج مورد انتظار
الگوریتم رقابت استعماری یکی از جدیدترین و قویترین الگوریتمها در حوزه محاسبات تکاملی محسوب
می شود که در حل بسیاری از مسائل به کار گرفته شده است. اما در مواردی که ابعاد مسئله زیاد است، این الگوریتم تعداد تکرارهای بیشتری نیاز دارد تا به جواب بهینه سراسری همگرا شود یا در بعضی مواقع در بهینه محلی تابع هدف به دام میافتد. بنابراین ایجاد بهبود در نحوه حرکت استعمارگرها و مستعمرات و ایجاد امکان برای استعمارگرها جهت بررسی فضای اطرافشان، باعث کمک به همگرایی سریع الگوریتم به جواب بهینه سراسری میگردد. الگوریتم خوشهبندی K-means یکی از معروفترین روشهای خوشهبندی داده ها است که با کمینهسازی تابع هدف، داده ها را دستهبندی می کند. در این پژوهش این الگوریتم و الگوریتم رقابت استعماری بهبود یافته با هم ترکیب شده اند و با توجه به ترکیب الگوریتم K-means و الگوریتم رقابت استعماری بهبود یافته انتظار میرود مراکز خوشه بهینه مربوط به پیکسلهای تصویر ورودی به دست آید. همچنین به دلیل استفاده از اطلاعات همسایگی پیکسلها روش پیشنهادی نسبت به نویز مقاوم بوده و