بخشی از مقاله
چکیده
یکی از مباحث مهم و مطرح در پردازش تصویر، شناسایی و تفکیک تصویر به اجزای سازندهاش - قطعهبندی - است که موفقیت یا شکست نهایی روشهای تحلیل تصویر را تعیین میکند. بااینحال یک روش کلی برای قطعهبندی موفق همه تصاویر وجود ندارد.
یکی از مسائل بسیار مهم در قطعهبندی تصویر پیدا کردن بهترین طبقهبندی برای پیکسلها هست. ازآنجاییکه یک راهحل مستقیم برای به دست آوردن بهترین طبقهبندی وجود ندارد، پس میتوان از الگوریتمهای فرا اکتشافی همچون الگوریتم ژنتیک - GA - و الگوریتم بهینهسازی ازدحام ذرات - PSO - ، برای پیدا کردن یک راهحل بهینه کلی - سراسری - بجای یک راه حل بهینه محلی استفاده کرد.
هدف اصلی این مقاله بررسی و مقایسه استفاده از دو الگوریتم ژنتیک و بهینهسازی ازدحام ذرات در قطعهبندی تصویر است. آزمایشات انجام گرفته نشان از عملکرد مناسب رویکرد پیشنهادی دارد.
-1 مقدمه
اولین مرحله در اغلب مسایل تحلیل تصاویر، قطعهبندی تصویر است. قطعهبندی فرآیندی است که تصویر را به قسمتهای اصلی سازندهاش تقسیم میکند. بدین معنی که اشیاء مختلف موجود در تصویر، با توجه به کاربرد موردنظر، از هم جدا میشوند تا تحلیل تصویر در مراحل بعدی راحتتر انجام گیرد. بهعنوان مثال، در کاربردهای رهگیری وسیله نقلیه از هوا، قبل از هر چیز شناسایی جاده و سپس تشخیص وسیله نقلیه مورد علاقه انجام میشود . با وجود اینکه الگوریتمهای زیادی در زمینه قطعهبندی تصویر مطرح شدهاند هنوز یک روش کلی برای قطعهبندی همه تصاویر وجود ندارد.
برای قطعهبندی تصویر روشهای مختلفی وجود دارد که میتوان آنها را به سه دسته، روشهای مبتنی بر لبه - [3,4] - ، روشهای مبتنی بر هیستوگرام - [5,6] - و روشهای مبتنی بر خوشهبندی - [7,8] - تق سیم کرد. در روشهای مبتنی بر هیستوگرام، تق سیمبندی ت صاویر برا ساس توزیع پیک سلها صورت میگیرد. قدم ا صلی در این روشها، یافتن آستانهای مناسب برای اعمال به تصویر است. در مواردی که هیستوگرام دارای مینیمم محلی است، این روشها ضعیف عمل میکنند یا حتی با شک ست مواجه می شوند.
در چنین مواردی میتوان از روشهای فازی استفاده کرد اما کارایی این روشها نیز به عواملی همچون کیفیت نور، نویز، فرض اولیه بستگی دارد. در سالهای اخیر تکنیکهای شناسایی لبه برای تحلیل و استخراج ویژگی تصویر بسیار مورداستفاده قرارگرفتهاند و از آن در کاربردهایی مثل قطعهبندی، شناسایی شی و ترمیم شی استفادهشده است. روشهای شناسایی لبه از تغییرات شدت سطح خاک ستری برای تعیین نقاطی که لبه ه ستند، استفاده میکنند.
یکی از روشها تعریف تابع عضویت است که درجه لبه را در هر همسایگی نشان میدهد. با استفاده از قوانین فازی مناسب، لبههای خاص یا کلی در یک همسایگی از پیش تعیینشده، تعریف میشوند. روشهای شناسایی لبه از اطلاعات محلی اختلاف سطح خاکستری برای تعیین نقاطی که لبه هستند، استفاده میکنند، درنتیجه، این الگوریتمها، فقط به تغییر سطوح خاکستری حساس میباشند و کارایی آنها در پردازش تصویر به عواملی مثل کیفیت نور و نویز بستگی دارد.
شکل - 1 - بهو ضوح تأثیر نویز بر روی روشهای ت شخیص لبه را ن شان میدهد.
شکل - a : - 1 - تصویر اصلی، - b تصویر با اعمال نویز speckle ، - c لبه یابی با استفاده از الگوریتم canny
در روشهای مبتنی بر خوشهبندی برای گروهبندی کردن دادهها از شباهتها و روابط موجود بین خوشهها استفاده میشود.در این روش، دادههایی که دارای بی شترین شباهت به هم ه ستند، در یک گروه قرار میگیرند.
الگوریتم های فرا اکتشافی[ 1] نوعی از الگوریتمهای تصادفی هستند که برای یافتن پاسخ بهینه به کار میروند. الگوریتمهای فرا اکت شافی دارای راهکارهای برونرفت از نقاط بهینه محلی ه ستند و قابلیت کاربرد در طیف گستردهای از مسائل را دارند.
فارمر و شوگارس [20] الگوریتمهای ژنتیک استفاده شده برای قطعهبندی تصویر را به دو دسته عمده تقسیم کردند:
1. قطعهبندی در سطح پیکسل با استفاده از الگوریتم ژنتیک
2. انتخاب پارامتر در الگوریتمهای قطعهبندی موجود با استفاده از الگوریتم ژنتیک
در پردازش سطح پیکسل، الگوریتم ژنتیک برای برچسب زدن ناحیهای استفاده میشود که در آن هر پیکسل به یکی از نواحی، براساس همگنی رنگ، سطح خاکستری، بافت و غیره اختصاص داده میشود.
در انتخاب پارامتر، پارامترهای کنترلی برای الگوریتم قطعه بندی با استفاده از الگوریتم ژنتیک بهبود داده میشوند تا یک محدودیت همگن درون نواحی برقرار شود.
همچنین در زمینه پیدا کردن حد آ ستانه در قطعهبندی ت صویر با استفاده از الگوریتم ازدحام ذرات، میتوان منابع - [17-19] - را مورد بررسی قرار داد.
این مقاله دو الگوریتم فرا اکتشافی ژنتیک و بهینهسازی ازدحام ذرات را در زمینه قطعهبندی تصویر مقایسه و بررسی میکند. ادامه مقاله به شرح زیر است:
ابتدا تعریفی از قطعهبندی ارائه داده میشود - بخش . - 2 سپس در بخش 3 - موارد و روشهای پی شنهادی - رویکردهای فرا اکت شافی پی شنهادی برای مسئله قطعهبندی ارائه میشوند. در این بخش جزئیات هر دو الگوریتم شرح و تابع برازندگی مشخص شده است. بخش 4 آزمایشها و جداول موردنیاز برای مقای سه و بحث میان دو الگوریتم قرار داده شده است. بخش 5 و پایانی مربوط به نتیجهگیری است.
-2 قطعهبندی تصویر
بهطورکلی مسئله قطعهبندی شامل تقسیم یک تصویر به تعدادی قطعههای همگن هست، بهطوری که، اجتماع هر دو قطعه همسایه، یک قطعه ناهمگن را حاصل کند. در خروجی این مرحله، هر شیء از تصویر، به وسیله یک مجموعه از پیکسلها نمایش داده میشود و از بقیه صحنه جدا می شود. قطعهبندی یکی از م شکلترین کارها در پردازش ت صویر ا ست، زیرا این مرحله از پردازش ا ست که شک ست یا موفقیت احتمالی تحلیل تصویر را تعیین میکند. درواقع با یک قطعهبندی نامنا سب ممکن ا ست به یک جواب پذیرفتنی نر سیم. درنتیجه باید به افزایش احتمال قطعهبندی مناسب بسیار توجه کرد. سطح جزییاتی که در قطعهبندی انجام می شود، به م سئلهای که باید حل شود، ب ستگی دارد. یعنی قطعهبندی وقتی باید متوقف شود که اشیا یا ناحیههای موردنظر در کاربرد، شناسایی شوند.
در این مقاله از رابطهی بین واریانس داخل هر قطعه با قطعات دیگر، برای ایجاد تمایز استفادهشده است. برای مقایسه دقیقتر الگوریتمها، از تابع برازندگی یکسانی استفادهشده است.
-3 مواد و روشهای پیشنهادی
در این بخش رویکردهای فرا اکتشافی پیشنهادی برای مسئله قطعهبندی ارائه میشوند. جزئیات مربوط به طراحی دو الگوریتم ژنتیک و بهینهسازی ازدحام ذرات در زیربخشهای جداگانه ارائه میشوند.
در هر دو الگوریتم تصویر موردنظر ابتدا از حالت ماتریسی به حالت برداری تبدیل میشود. سپس عملیات موردنظر بر روی بردار حاصل انجام و حدآستانهها استخراج میشوند. در آخر، تصویر قطعهبندی شده - که هر قطعه دارای مقادیر پیکسل یکسان است - نمایش داده میشود.
-1-3 الگوریتم ژنتیک
الگوریتم ژنتیک - GA - یک روش بهینهسازی است که از اصول انتخاب طبیعی داروین برای حل م سئله بهینه سازی ا ستفاده میکند. الگوریتم ژنتیک نوع خاصی از الگوریتمهای فرا اکتشافی است. فرآیند انتخاب طبیعی برای اثربخشی گروهی از راه حلهای ممکن برای یافتن یک بهینه محیطی ا ستفاده می شود. هلند در دهه هفتاد الگوریتم ژنتیک را بهعنوان بر نا مه های کامپیوتری که از فرآی ند ت کا مل طبیعی تقل ید میکرد، ارائه کرد . دی جونگ الگوریتم ژنتیک را برای بهینهسازی تابعی بهبود داد و مدل ریاضی دقیقی از الگوریتم ژنتیک توسط گلدبرگ ارائه شد
در این م قا له الگوریتم ژنت یک برای یافتن حد آس تا نه - حد آستانههای - بهینه برای قطعهبندی تصویر استفاده میشود.
فرآیند الگوریتم ژنتیک:
شکل - 2 - فرآیند الگوریتم ژنتیک را در یک فلوچارت نشان میدهد. در ابتدا الگوریتم، جمعیت اولیه را تولید میکند. جمعیت اولیه به صورت تصادفی و با توجه به تعداد حد آستانه مشخصشده توسط کاربر، تولید می شود - برای سرعت بخ شیدن به الگوریتم در پیدا کردن نقاط بهینه، از اعداد تصادفی با توزیع یکنواخت استفاده شده است - .
هر حد آستانه نشاندهنده تعدادی ژن - تعداد ژن وابسته به تعداد سطح تصویر است - در کروموزوم - هر عضو جمعیت - در نظر گرفته شده است
شکل : - 3 - نمایی از یک کروموزوم با دو حد آستانه
شکل : - 2 - فرآیند الگوریتم ژنتیک
هر ژن دارای مقادیری متناسب با سطح تصویر هست - مثلاً در تصاویر با 256 سطح، 8 بیت برای نشان دادن مقادیر دودویی ژن نیاز است - .
مرحله دوم ارزیابی میزان برازندگی هر موجودیت در جمعیت است. این کار توسط تابع برازندگی انجام میگیرد - با توجه به اینکه، هر دو الگوریتم از یک نوع تابع برازندگی استفاده میکنند و برای جلوگیری از تکرار در نوشتار، تابع برازندگی هر دو الگوریتم در آخر این بخش ارائه میشود - . در هر تکرار تابع برازندگی محاسبه میشود.
مرحله سوم انتخاب مناسبترین موجودیتها برای جمعیت است - میتوان با توجه به میزان برازندگی هر موجودیت، احتمالی به آن نسبت داد و با روشهایی همچون چرخ رولت جمعیت جدید را انتخاب کرد - . هدف اصلی همگرایی سریعتر به جواب بهینه است.
الگوریتم ژنتیک برای جلوگیری از به دام افتادن در بهینه محلی، از دو عملگر ترکیب و جهش استفاده میکند. مرحله چهارم اعمال عملگرهای ترکیب و جهش است که در ادامه شرح داده میشوند - مرحله جفتگیری - .
