بخشی از مقاله
چکیده -
در این مقاله با استفاده از خوشه بندی توسط الگوریتم رقابت استعماری، روشی جدید و هوشمند برای کاهش رنگ تصاویر ارائه شده است. فرایند کاهش رنگ میتواند به عنوان یک مسئله خوشه بندی در نظر گرفته شود که هدف اصلی آن یافتن خوشه هایی است که مراکز آن ها به بهترین شکل، گروهی از رنگ های موجود در تصویر را تقریب میزنند. طبیعتا ارائه روشی کارامد برای تقریب رنگ ها ارتباط مستقیمی با کیفیت تصویر خروجی دارد.
کاهش رنگ دارای دو مرحله اصلی است. در مرحله اول رنگ های تصویر، خوشه بندی می شوند. مرحله دوم شامل ساخت تصویر خروجی با نگاشت مراکز خوشه ها در تصویر اولیه می باشد. در اینجا به منظور خوشه بندی پیکسل های تصویر از الگوریتم رقابت استعماری استفاده شده است. روش ارائه شده را میتوان در زمینه های بینایی ماشین، فشرده سازی تصاویر، ناحیه بندی، نمایش و ارسال تصاویر رنگی استفاده نمود.
-1 مقدمه
کاهش رنگ یکی از تکنیک های پردازش تصویر است که هدف آن نمایش یک تصویر با تعداد رنگ هایی کم تر از تصویر اصلی است. در کد گذاری های معمول تصاویر، برای نمایش رنگ هر پیکس از 24 بیت اطلاعاتی استفاده میشود. جمعا هر پیکسل توانایی نمایش 2 24 رنگ را دارد. در بسیاری از کاربرد ها رنگ عامل مهمی در شناسایی و تشخیص اشیاء است اما به دلیل هزینه زیاد محاسباتی، استفاده از آن مقرون به صرفه نیست. کاهش رنگ باعث ساده تر شدن پردازش و درک تصویر میگردد.
فرایند کاهش رنگ باعث محدود شدن رنگ ها به میزان دلخواه - معمولا بین 8 تا 256 رنگ - میگردد که این امر باعث ساده تر شدن پردازش ها و کاهش حجم تصویر می شود. نکته کلیدی در این مبحث حفظ کیفیت تصویر در حد مطلوب و استاندارد است از این رو ارائه روشی هوشمند که بتواند رنگ ها را در تصویر با دقت بالایی تقریب بزند نقش بسزایی در کیفیت تصویر خروجی دارد. برای این منظور تاکنون روش هایی ازجمله ، استفاده از شبکه های عصبی [1,2,3] ، روش های مبتنی بر الگوریتم های تکاملی [4,5,6] و همچنین روش های مبتنی بر منطق فازی [7] ارائه شده است .
از لحاظ تئوری کاهش رنگ میتواند به یک مسئله بهینه سازی و خوشه بندی تبدیل شود که هدف آن مشخص کردن خوشه هایی از رنگ هاست که مرکز آن ها به بهترین صورت رنگ های درون یک خوشه را تقریب میزنند پس میتوانیم دو مرحله اصلی برای انجام کار در نظر بگیریم: -1 انتخاب k خوشه رنگی در تصویر اصلی. -2 ساخت تصویر خروجی با نگاشت مراکز خوشه ها در تصویر اولیه
در این مقاله با استفاده از الگوریتم رقابت استعماری روشی جدید و کارآمد برای کاهش رنگ ارائه شده است.
بخش دوم این مقاله روش ارائه شده را بررسی میکند و در بخش سوم نتایج تجربی نشان داده شده است.
-2 روش ارائه شده
در این بخش ابتدا تئوری مسئله کاهش رنگ از لحاظ ریاضی مورد بحث قرار میگیرد. در ادامه روش کلی و الگوریتم استفاده شده در قالب بخش های مختلف معرفی میگردد.
-1-2 تعریف ریاضی مسئله
اگر یک پیکسل با x مشخص شود، یک تصویر میتواند حاوی n پیکسل باشد. پس میتوانیم پیکسل های موجود در یک تصویر را بصورت xi نماد گذاری کنیم که i={1,2,...,n} است.
در خوشه بندی پیکسل ها میخواهیم k نقطه شاخص cj درون xi تعریف کنیم بصورتی که معادله - - 1 مینیمم گردد. این معادله در واقع همان تابع هدف است.
نقاط شاخص cj همان مراکز خوشه هاست. که هر مرکز نماینده تمامی رنگ های موجود در یک خوشه است. همچنین cj جزو مجهولات مسئله به حساب می آید و باید محاسبه شوند.
با کنترل متغیر k میتوانیم تعداد رنگ های تصویر حاصل پس از کاهش رنگ را کنترل کنیم. برای مثال اگر k برابر با 25 باشد، الگوریتم خوشه بندی 25 کلاستر با مراکز آن هارا محاسبه میکند. این کنترل باعث انعطاف پذیری بیش تر در مسئله میگردد.
در اینجا مقدار بتا ثابت است. r مقداری راندوم است که بین صفر و یک است که باعث میشود کشور ها جهات مختلفی برای جستجو انتخاب کنند.
-2-3-2 عملگر انقلاب
با فرضه این که متغیر های ما بین xmin و xmax هستند و طی فرایند انقلاب میخواهیم x را به x' تبدیل کنیم. برای عملگر انقلاب داریم:
-2-2 روند کلی فرایند کاهش رنگ
فرایند کاهش رنگ توسط خوشه بندی دارای مراحل زیر است :
- 1 خوشه بندی تمام پیکسل های موجود در تصویر به تعداد k گروه از پیش تعیین شده.
-2 محاسبه مراکز خوشه ها cj و ایجاد یک رنگ نماینده برای هر گروه
-3 جایگزین کردن هر رنگ در تصویر اصلی با مراکز خوشه مربوط به آن
-3-2 خوشه بندی پیکسل ها
در این مقاله برای خوشه بندی پیکسل ها از الگوریتم رقابت استعماری استفاده شده است. این الگوریتم در سال 2007 توسط اقایان آتشپز و کارل لوکس معرفی گردیده است.[10] ایده اصلی این الگوریتم از شبیه سازی فرایند اجتماعی سیاسی استعمار است.
-3 نتایج تجربی
در این قسمت نتایج حاصل از اعمال روش ارائه شده بر روی تصاویر استاندارد papers,Mandrill و coloredchips نشان داده شده است. به منظور ارائه مقایسه ای بهتر، الگوریتم معروف کاهش رنگ فازی FCM نیز پیاده سازی گردیده[11] و نتایج حاصل از اعمال آن بر روی تصاویر یاد شده ارائه گردیده است.
زمان پردازش روش ارائه شده در این مقاله بر روی تصاویر مختلف با توجه به ابعاد و رنگ های تصاویر متفاوت است ،طبیعتا زمان اجرای الگوریتم کاهش رنگ به روش فازی FCM نیز به نوع تصویر و ابعاد آن و همچنین فاکتور های دیگر بستگی دارد، از این رو معیار مقایسه عملکرد روش ها را بر اساس کیفیت تصاویر خروجی آن ها قرار داده ایم.
