بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
قطعه بندي تصاوير رنگي با استفاده از اتوماتاي يادگير سلولي
چکيده : قطعه بندي به عنوان يک فاز مهم در پردازش تصوير مطرح ميباشد و تاکنون پيشرفت هاي زيادي در زمينه قطعه بندي تصاوير خاکستري حاصل شده است اما براي تصاوير رنگي اين پيشرفت به اندازه تصاوير خاکستري نمي باشد. در اين مقاله يک الگوريتم قطعه بندي براي تصاوير رنگي با استفاده از اتوماتاي يادگير سلولي پيشنهاد مي شود. اتوماتاي يادگير سلولي داراي کاربردهاي زيادي در پردازش تصوير است زيرا به راحتي مي توان يک تصوير را به اتوماتاي يادگير سلولي نگاشت داد و از قابليت هاي آن استفاده نمود. الگوريتم پيشنهادي سعي مي کند تا در يک روند تکراري فاصله موجود بين پيکسل هاي واقع در يک قطعه در فضاي رنگي را کاهش دهد. براي نيل به اين هدف ، علاوه بر طراحي مولفه هاي اتوماتاي يادگير سلولي نياز است تا از تکنيک هاي پردازش تصوير در حين اجراي الگوريتم استفاده شود. نتايج حاصل شده بيانگر کارايي الگوريتم پيشنهادي در قطعه بندي تصاوير رنگي هستند.
کلمات کليدي : اتوماتاي سلولي ، اتوماتاي يادگير، اتوماتاي يادگير سلولي ، قطعه بندي ، فضاي رنگي RGB، فيلتر گوسي .
١- مقدمه
قطعه بندي ١ تصوير و ويدئو به عنوان يک پيش پردازش براي اعمالي نظير پيداکردن ناحيه دلخواه ٢ در يک صحنه ، تفسير داده ها و بازيابي تصاوير٣ محسوب مي شود. همچنين استاندارد 4-MPEG، از قطعه بندي براي کدکردن ويدئو استفاده مي کند. در اين فرآيند، ت وير به تعدادي ناحيه جدا از هم تقسيم و در هر ناحيه مجموعه اي از پيکسل ها که از لحاظ چند معيار به يکديگر شبيه هستند، قرار مي گيرند. تاکنون روش ه ي زيادي از قبيل روش هاي مبتني بر مدل سازي آماري [٧,١٣,١٥]، انتشار انرژي [١٠] ، افراز گراف [١٤] و قطعه بندي بدون ناظر [٨] براي قطعه بندي تصاوير مطرح شدهاند.
بسياري از روش ه ي قطعه بن ي موجود مانند خوشه بن ي٥ پيکسل ها در فضاي رنگي ، بر روي نواحي همگن به خوبي عمل مي کنند اما از آنجا که تصاوير طبيعي از تنوع رنگ و بافت ٦ بالايي برخوردار هستند، در مجموع کارايي اين روش ها پايين ميباشد. روش هاي مبتني بر بافت ، که به عنوان يک روش براي قطعه بندي مطرح شده اند، نياز به تخمين پارامترهاي مدل بافت دارند. تخمين اين پارامترها پيچيده بوده و در اغلب اوقات تخمين مناسب پارامترها نيازمند وجود نواحي همگن در تصوير ميباشد.
اتوماتاي يادگير سلولي ٧ به عنوان يک مدل براي سيستمهايي که از اجزاء ساده اي تشکيل شده اند، مطرح شده است . در اين مدل رفتار هر جزء بر اساس رفتار همسايگانش و نيز تجربيات گذشته اش تعيين و اصلاح مي شود. اجزاء ساده تشکيل دهنده اين مدل از طريق کنش و واکنش با يکديگر مي توانند رفتار پيچيده اي از خود نشان دهند.
تاکنون کاربردهاي زيادي از اتوماتاي يادگير سلولي مطرح شده است . يکي از زمينه هايي که در آن اتوماتاي يادگير سلولي بسيار زياد مورد استفاده قرار گرفته است ، زمينه پردازش تصوير ميباشد. از جمله اين کاربردها ميتوان به بازيابي تصاوير [٢] ، الگوگذاري تصاوير[٤]، قسمت بندي تصاوير خاکستري [٣] و تشخيص لبه [٥] اشاره کرد.
همچنين در زمينه هايي از قبيل شبيه سازي پديدههاي اجتماعي مانند انتشار شايعه [٢٠]، خوشه بندي ٨ دادهها [١٩] و جايابي مدارهاي متراکم [٦] از اتوماتاي يادگير سلولي استفاده شده است .
در اين مقاله يک الگوريتم براي قطعه بندي تصاوير رنگي با استفاده از اتوماتاي يادگير سلولي معرفي ميشود. در بسياري از الگوريتم ه ي قطعه بندي موجود، براي پيدا کردن نواحي تصوير يک سري معيار تعريف و سپس بر اساس اين معيارها و تشابه پيکسل هاي واقع در يک همسايگي ، تعلق هر کدام از پيکسل ها به يک دسته تعيين مي شود. هر کدام از دو جزء ياد شده (تعريف معيار و همسايگي ) مي توانند به راحتي توسط يک اتوماتاي يادگير سلولي پياده سازي شوند. براي بررسي تشابه پيکسل هاي واقع در يک همسايگي مي توان از رابطه همسايگي موجود در اتوماتاي يادگير سلولي بهره گرفت و براي تعريف معيار مي توان يک قانون مناسب طراحي نمود.
اتوماتاي يادگير سلولي از يک الگوريتم تکراري براي رسيدن به خروجي مناسب استفاده مي کند. از آنجايي که در قطعه بن ي تصاوير، خروجي الگوريتم بايد يک تصوير قطعه بندي شده باشد، بنابراين از چند مرحله پيش پردازش و پس پردازش براي الگوريتم مبتني بر اتوماتاي يادگير سلولي استفاده مي کنيم . اين عمليات باعث تسريع همگرايي اتوماتاي يادگير سلولي خواهند شد.
ادامه مقاله به صورت زير تدوين شده است : در بخش هاي ٢ و ٣ به ترتيب اتوماتاي سلولي و اتوماتاي يادگير معرفي مي شوند. از ترکيب اين دو اتوماتا، اتوماتاي يادکير سلولي حاصل مي شود که در بخش ٤ به بررسي آن خواهيم پرداخت . در بخش ٥، الگوريتم پيشنهادي براي قطعه بندي تصوير شرح داده مي شود. در بخش ٦ نت يج به دست آمده بيان مي گردد و در بخش ٧ به جمع بندي و کارهاي آينده پرداخته مي شود.
٢- اتوماتاي سلولي
اتوماتاي سلولي ٩ به عنوان يک ابزار مناسب براي سنتز سيستم هاي پيچيده است . اين سيستم ها از چندين مولفه ساده تشکيل شدهاند که هر کدام از اين مولفه ها به يک واحد به نام سلول نگاشت مي يابند. اين سلول ها در يک شبکه منظم قرار مي گيرند و تحت يک رابطه همسايگي تعريف شده با يکديگر در ارتباط هستند. هر سلول ميتواند k مقدار مختلف را به خود بگيرد و براي تعيين مقدار سلول در هر مرحله ، از يک قانون محلي استفاده ميشود. اين قانون با توجه به مقدار يک سلول و همسايه هاي آن در مرحله فعلي ، مقدار سلول را در مرحله بعد تعيين مي کند.
براي نگاشت تصوير به يک اتوماتاي سلولي ، فرض مي شود که هر پيکسل تصوير به يک سلول نگاشت مي شود و اين سلول ها در يک شبکه دو بعدي منظم قرار گرفته اند. با توجه به کاربرد و خروجي که بايد از تصوير ورودي حاصل شود، رابطه همسايگي و قانون اين اتوماتاي سلولي دوبعدي تعريف مي شود. شکل (۱) يک اتوماتاي سلولي دوبعدي و دو رابطه همسايگي فون يومن ١٠ و مور در ين اتوماتا را نشان مي دهد.
در اين شکل سلول هاي خاکستري همسايه سلول سياه رنگ هستند.
٣- اتوماتاي يادگير
اتوماتاي يادگير١١ يک مدل انتزاعي است که مي تواند تعداد محدودي عمل را انجام دهد. در هر مرحله يک عمل انتخاب شده و به محيط اعمال مي گردد. اين عمل توسط محيط ارزيابي شده و پاسخي به اتوماتاي يادگير داده مي شود. اتوماتاي يادگير از اين پاسخ استفاده نموده و ساختار داخلي خود را به هنگام مي کند و سپس عمل بعدي را انتخاب مي کند. در شکل (٢) اين تعامل نشان داده شده است .
محيط را مي توان توسط سه تايي نشان داد که در آن مجموعه ورودي ها ي محيط و خروجي هاي اتوماتا، {١ ,٠} = β مجموعه خروجي هاي محيط و ورودي هاي اتوماتا و مجموعه احتمالهاي جريمه ميباشد. هر گاه β مجموعه دو عضوي باشد ، محيط از نوع P مي باشد.
در چنين محيطي ١ =βo به عنوان جريمه و ٠ =β1 به عنوان پاداش در نظر گرفته ميشود.
اتوماتاهاي يادگير به دو دسته کلي با ساختار ثابت و متغير تقسيم مي شوند. اتوماتاي يادگير با ساختار ثابت توسط ٥ تائي {α, β, F, G, φ} نشان داده مي شود که در آن مجموعه عمل هاي اتوماتا، مجموعه ورودي هاي اتوماتا، . مجموعه وضعيتهاي داخلي اتوماتا، تابع توليد وضعيت جديد اتوماتا و تابع خروجي که وضعيت کنوني را به خروجي بعدي مي نگارد، مي باشد.
نمونه اي از اتوماتاي يادگير با ساختار ثابت است . اين اتوماتا داراي N2 حالت و دو عمل است . براي حالت هاي ١ تا N عمل و براي حالت هاي عمل انتخاب مي شود. در شکل (٣) نمودار تغيير وضعيت اين اتوماتا نشان داده شده است .
از جمله ديگر اتوماتاهاي يادگير با ساختار ثابت مي توان از ، Krylov،Krinsky [٩] نام برد.
اتوماتاي يادگير با ساختار متغير توسط چهار تائي {α, β, p, T} = E نشان داده مي شود که در آن
مجموعه عمل هاي اتوماتا،{١ , ٠} = β مجموعه ورودي هاي اتوماتا، بردار احتمال انتخاب هر يک از عمل ها و الگوريتم يادگيري مي باشد.
فرض کنيد که در مرحله n-ام عمل انتخاب شود. اين انتخاب بر اساس بردار احتمال عمل ها صورت گيرد. پس از اعمال عمل بر روي محيط تصادفي ، پاسخ محيط دريافت مي شود. چنانچه محيط به عمل انتخاب شده پاداش دهد، احتمال انتخاب عمل αi در مرحله بعد افزايش و احتمال انتخاب ساير عمل ها کاهش مي يابند. اما اگر پاسخ محيط به اين عمل جريمه باشد، احتمال انتخاب عمل αi در مرحله بعد کاهش و احتمال انتخاب ساير عمل ها افزايش مي يابند. نکته اي که بايد مورد توجه قرار گيرد اين است که p يک بردار احتمال است و بنابراين بايد مجموع احتمال عمل ها در هر مرحله مساوي يک باشد. روابط (١) و (٢) نحوه به هنگام سازي بردار احتمال p (الگوريتم يادگيري ) را مشخص مي کنند:
در روابط (١) و (٢) a پارامتر پاداش و b پارامتر جريمه هستند و ميزان تغييرات در احتمال عمل ها را مشخص مي کنند. با توجه به مقادير a و b سه حالت را مي توان در نظر گرفت زماني که a و b با هم برابر باشند، الگوريتم راLRP مي ناميم . زماني که b از a خيلي کوچکتر باشد، الگوريتم مي ناميم . زماني که b مساوي صفر باشد، الگوريتم را LRi مي ناميم .
٤- اتوماتاي يادگير سلولي
اتوماتاي يادگير سلولي يک اتوماتاي سلولي است که در هر سلول آن يک يا چند اتوماتاي يادگير قرار گرفته است . اتوماتاهاي يادگير هر سلول يکي از اعمال خود را انتخاب مي کنند و در نتيجه وضعيت هر سلول با عمل هاي اتوماتاهاي يادگير واقع در آن تعيين مي شود. در نتيجه در اصلاح رفتار يک سلول علاوه بر رفتار سلول هاي همسايه ، تجربه گذشته آن سلول نيز تاثيرگذار خواهد بود. همانند اتوماتاي سلولي ، يک قانون محلي بر محيط حاکم است و اين قانون تعيين مي کند که آيا عمل انتخاب شده توسط اتوماتاي يادگير در يک سلول بايستي پاداش داده شود و يا جريمه شود. عمل دادن پاداش و يا جريمه منجر به بروز در آوردن ساختار اتوماتاي يادگير سلولي به منظور رسيدن به خروجي موردنظر مي گردد.
عملکرد اتوماتاي يادگير سلولي به صورت زير است : در هر لحظه هر اتوماتاي يادگير در اتوماتاي يادگير سلولي يک عمل از مجموعه اعمال خود را انتخاب مي کند. اين عمل ميتواند بر اساس مشاهدات قبلي و يا به صورت تصادفي انتخاب شود. عمل انتخاب شده با توجه به اعمال انتخاب شده توسط سلولهاي همسايه و قانون حاکم بر اتوماتاي يادگير سلولي پاداش داده و يا جريمه مي شود. با توجه به اينکه عمل انتخاب شده توسط يک اتوماتا پاداش گرفته و يا جريمه شده است اتوماتا رفتار خود را تصحيح کرده و ساختار داخلي خود را به هنگام کند.
عمل به هنگام سازي تمام اتوماتاها به صورت همزمان انجام مي شود.
بعد از به هنگام سازي ، هر اتوماتا در اتوماتاي يادگير سلولي دوباره يک عمل از مجموعه اعمال خود را انتخاب کرده و انجام مي دهد. فرايند انتخاب عمل و دادن پاداش و يا جريمه تا زماني که سيستم به حالت پايدار برسد و يا يک معيار از قبل تعريف شده اي بر قرار شود ادامه مي يابد. عمل بهنگام سازي ساختار اتوماتاهاي موجود در اتوماتاي يادگير سلولي توسط الگوريتم يادگيري انجام ميشود.
٥- الگوريتم پيشنهادي براي قطعه بندي تصاوير رنگي
در اين بخش يک الگوريتم مبتني بر اتوماتاي يادگير سلولي جهت قطعه بندي تصاوير رنگي ارائه مي شود. براي انجام اين کار، فرض مي کنيم که هر پيکسل تصوير به يک سلول در اتوماتا نگاشت مي يابد و رابطه همسايگي سلول ها از نوع همسايگي مور است . بنابراين هر پيکسل با پيکسل هاي واقع در همسايگي ٣×٣ آن همس يه است . در هر سلول يک اتوماتاي يادگير با ساختار متغير از نوع قرار مي گيرد.
به ازاي هر پيکسل همسايه ، يک عمل براي اتوماتاي يادگير واقع در يک سلول تعريف مي شود و بنابراين اتوماتاي موجود در هر سلول داراي ٨ عمل است . در هر مرحله احتمال انتخاب عمل هاي مجاز در يک سلول با توجه به خروجي قانون به کارگرفته شده (پاداش يا ج يمه ) توسط روابط (١) و (٢) تغيير ميکنند. شکل (٤) نحوه تع يف عمل هاي اتوماتاي يادگير واقع در سلول مرکزي را نشان مي دهد.
هر عمل بيانگر اين است که پيکسل واقع در يک سلول با کدام يک از پيکسل هاي همسايه آن، در يک قطعه قرار مي گيرند. از آنجا که يک پيکسل به تنهايي نمي تواند يک قطعه را تشکيل دهد و اين چنين پيکسلي نويز محسوب مي شود براي سلول مرکزي واقع در شکل (٤) عملي تعريف نمي شود.
براي اينکه احتمال اوليه انتخاب عمل ها در هر سلول تعيين شوند، ابتدا فاصله پيکسل واقع در آن سلول با پيکسل هاي سلول هاي همسايه در فضاي رنگي RGB محاسبه مي شود. براي تعيين اين فاصله ها از رابطه زير استفاده ميکنيم .
که مختصات همسايه شماره i پيکسل (x,y) و I تصوير ورودي است . فاصله بين پيکسل (x,y) تا همسايه i-ام آن را نشان ميدهد. سپس با استفاده از معکوس اين فواصل ، احتمال انتخاب عمل ها تعن يشود. روابط زير نحوه تعريف اين احتمال ها را نشان مي دهند
که احتمال انتخاب عمل i-ام است . قانوني که براي پاداش يا جريمه کردن يک عمل استفاده مي شود، به صورت زير است : ابتدا فاصله پيکسل واقع در يک سلول را تا تمامي سلول هاي همسايه را با استفاده از رابطه (٣) محاسبه مي کنيم و ميانگين اين فواصل را به دست مي آوريم و با نشان مي دهيم . فرض کنيد که اين سلول عمل i را انتخاب کند. بنابراين فاصله پيکسل اين سلول را تا پيکسل واقع در i- امين سلول همسايه آن محاسبه مي شود و آنرا را با نشان مي دهيم . قانوني که براي اين سلول به کار گرفته مي شود، در رابطه (٦) نشان داده شده است .
که c يک ضريب ثابت نزديک يک است . از آنجا که در هر مرحله ، بايد پيکسل هاي واقع در يک قطعه در فضاي رنگي به هم نزديک شوند، بنابراين نياز به الگوريتمي جهت پخش رنگ در يک قطعه است . اين الگوريتم با استفاده از تصوير ورودي ، يک تصوير ايجاد مي کند که در آن پيکسل هاي واقع در يک قطعه از لحاظ رنگي به يکديگر نزديک مي شوند.
فرض کنيد که تصوير ورودي الگوريتم را با I و تصوير خروجي را با ’I نشان دهيم . براي تعيين مقدار پيکسل ها در تصوير ’I، ابتدا يک زنجيره از پيکسل ها با شروع از مختصات (x,y) استخراج مي گردد. شبه کد مربوط به اين عمل در شکل (٥) نشان داده شده است . در اين شبه کد LA بيانگر اتوماتاي يادگير يک سلول است و زنجيره استخراج شده براي مختصات (x,y) در pixels_list نگه داشته ميشود. مطابق الگوريتم شکل (٥)، ابتدا ليست پيکسل ها خالي است و سلول فعلي (x,y) است . ابتدا سلول فعلي به ليست پيکسل ها اضافه سلول فعلي است ، تعيين ميگردد. سپس سلول فعلي برابر با سلول ميشود و سپس سلول همسايه اي که مطابق با عمل انتخاب شده در همسايه قرار ميگيرد تا تکرارهاي بعدي با اين سلول ادامه يابد. مراحل ذکر شده تا زماني که قانون تعريف شده سلول فعلي را جريمه کند و يا اينکه سلول فعلي در ليست پيکسل ها وجود داشته باشد، تکرار ميشوند.
براي هر کدام از مختصات (x,y) تصوير ورودي يک ليست محاسبه ميشود که در آن عنصر ابتدايي مختصات (x,y) است . اگر قانون تعريف شده براي اتوماتاي سلولي براي يک مختصات جريمه را انتخاب کند، آنگاه ليست آن مختصات تنها داراي يک عضو که خود مختصات است ، خواهد بود. بنابراين هر ليست حداقل يک عضو خواهد داشت .
