جزئیات پیاده­سازی الگوریتم
روش­های مبتنی بر برش­های گراف، به عنوان روش­هایی تعاملی و مبتنی بر تعیین نقاط شروع شناخته می­شوند، همانند الگوریتم هوشمند سیزرز، برش­های گراف تصویر را همانند گراف فرض می­ کنند که تفاوت مقدار پیکسل­ها به کمک وزن­دهی مشخص می­ شود. در این روش­ها کاربر نقاط پس­زمینه و پیش­زمینه را تا حدودی علامت گذاری می­ کند، سپس تصویر تحلیل می­ شود تا وزن­های کمینه بدست آیند. مزیت این روش­ها تولید تقطیع دلخواه از تصویر به کمک دخالت کافی کاربر و توسعه روش به فضای سه بعدی است. روش برش­های گرافی محدودیت­هایی دارد که به منظور رفع آن­ها روش­های جدیدی ارائه شده است. ممکن است برش­های گراف کوچک و تعداد آن­ها زیاد شود که سرعت روش را پایین می ­آورد. قبل از اعمال الگوریتم تحلیل گراف، تغییراتی در گراف بوجود می ­آید تا برش­های گراف بزرگتر شوند. در واقع تعداد رئوس گراف کاهش پیدا می­ کند. همچنین برای تقطیع رنگی تصاویر به کمک روش برش­های گراف یک واسطه کاربر به الگوریتم اضافه می­ شود تا کاربر دور شی مورد نظر پنجره­ای رسم کند و از مدل رنگ برای مشخص کردن تعدادی از نقاط شروع در پیش­زمینه استفاده کند. رسم پنجره میزان دخالت کاربر را در تقطیع تصویر کم می­ کند و استفاده از مدل رنگ به تقطیع تصویر رنگی کمک می­ کند هر چند باعث افزایش بار محاسباتی الگوریتم می­ شود.

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

الگوریتم افراز گراف از پیمایش­های تصادفی استفاده می­ کند بطوریکه زمان­های برخورد از کلیه رئوس به راس مورد نظر محاسبه می­شوند سپس مقادیر زمان­ها آستانه­گذاری می­ شود بطوریکه ویژگی­های دلخواه برای افراز بوجود آید. از این روش اخیرا برای تقطیع تصویر استفاده شده است. در این روش راس دلخواه تصادفی انتخاب می­ شود و افراز بصورت بازگشتی انجام می­ شود و افراز بصورت بازگشتی انجام می­ شود تا زمانیکه از یک معیار سنجش کیفیت افراز نقض شود (۷۷).
۳-۴-۱) وزن یال­ها
شرح کامل الگوریتم را با توصیف دقیق گراف آغاز می­کنیم. گراف شامل رئوس و یالهاست بطوریکه هر یال به دو راس متصل است. در گراف وزن­دار هر یال دارای وزنی مشخص می­باشد. درجه هر راس برابر مجموع وزن یال­های متصل به آن راس می­باشد. وزن کلیه یال­ها در گراف مورد نظر مثبت است. همچنین گراف متصل و یال­ها بدون جهت هستند.
برای نمایش تصویر توسط پیمایش­گر تصادفی باید تابعی تعریف کنیم که تغییر مقادیر پیکسل­ها در تصویر را با وزن یال­ها مرتبط سازد. استفاده از این نوع توابع از ویژگی­های الگوریتم­های مبتنی بر گراف است. در الگوریتم پیمایشگر تصادفی از وزن گوسی استفاده شده است.
( ۳-۳)
که g_i مقدار پیکسل در پیکسل i را مشخص می­ کند. مقدار β تنها پارامتر آزاد الگوریتم را مشخص می­ کند. بهتر است که معادله بالا قبل از استفاده نرمال­سازی شود. همچنین این معادله می ­تواند به منظور استفاده از اطلاعات بافت، ضرایب فیلتر و مشخصه­های تصویر ویرایش شود.
۳-۴-۲- مسئله دیریکله ترکیبی
در مقدمه عنوان کردیم که حل مسئله دیریکله ترکیبی برابر با احتمال­های پیمایشگر تصادفی دلخواه است. در این بخش نحوه یافتن حل مسئله دیریکله را مرور می­کنیم. انتگرال دیریکله شامل فیلد U و ناحیه امگا است که مرتبط با انتقال گرما، الکتروستاتیک و پیمایش­های تصادفی می­باشد. یک تابع هارمونیک تابعی است که معادله لاپلاس را ارضا کند . مسئله دیریکله در واقع یافتن یک تابع هارمونیک است که شرایط مرزی را ارضا می­ کند. تابع هارمونیک که شرایط مرزی را ارضا کند انتگرال دیریکله را کمینه می­ کند چرا که معادله لاپلاس معادله اویلر- لاگرانژ برای انتگرال دیریکله است. سپس ماتریس ترکیبی لاپلاس و ماتریس رویداد راس-یال تعریف می­ شود.
۳-۴-۳- قیاس مداری
همانطور که توضیح داده شد می­توان به کمک مدارهای الکتریکی رفتار پیمایشگر تصادفی را شبیه­سازی کرد. همانطور که در تصویر ۱-۳ نشان داده شده است، می­توان مساله را به کمک مدار، شبیه­سازی کرد. سه اصل مهم در تئوری مدار شامل قانون اهم، ولت و کیرشهف را در نظر بگیرید:
(۳-۴) قانون جریان کیرشهف
(۳-۵) قانون اهم
(۳-۶) قانون ولتاژ کیرشهف
این سه معادله را می توان در یک سیستم خطی ترکیب کرد:
(۳-۷)
۳-۴-۴- ارتباط روش با فرایند انتشار در بینایی ماشین
در بینایی ماشین عمل انتشار را می­توان به کمک پیمایش­های تصادفی توصیف کرد. در این بخش ارتباط بین فرایند انتشار و روش کنونی را بررسی می­کنیم. تفاوت اصلی بین معادله انتشار و معادله لاپلاس این است که انتشار یک فرایند انتقال در زمان را نشان می­دهد در حالیکه معادله لاپلاس یک توزیع حالت پایدار را توصیف می­ کند. علی­رغم شباهت ریاضی معادلات لاپلاس با معادلات انتشار این دو الگوریتم با هم تفاوت زیادی دارند. بویژه فرایند انتشار معمولا بصورت یک الگوریتم بهبود تصویر به کار می­رود بطوریکه مقادیرخاکستری اولیه پیکسل­های تصویر به عنوان شرایط اولیه مسئله در نظر گرفته می­شوند و حل مسئله بعد از طی بازه زمانی از پیش تعیین شده متوقف می­ شود. در مقابل در این تحقیق یک الگوریتم تقطیع مبتنی بر نقاط شروع توصیف می­ شود که از شرایط اولیه استفاده نمی­کند بلکه برای مشخص کردن مرزها از توزیع حالت پایدار پتانسیل­ها استفاده می­ کند. درالگوریتم پیمایش تصادفی برای تحلیل تصویر بدنبال یافتن وزن­های کمینه هستیم.
اگر xi احتمال پیکسل i مربوط به پیش زمینه (متعلق به دو بطن راست یا چپ) ، بخش­بندی بطن چپ و راست می­توانند با به حداقل رساندن تابع هزینه بصورت زیر باشد:
(فرمول ۳-۸)
(۳-۹)
کهβ مقدار ثابت مثبت می­باشد، x_i وx_j احتمال پیکسل i و j هستند و در فرمول شماره ۲ مقدار w_ij برابر صفر خواهد بود زمانیکه پیکسل­ها متصل نباشند. ما بدنبال مینیمم­کردن تابع هزینه هستیم، پیکسل­هایی که از شدت روشنایی یکسان برخوردارند از احتمال­های یکسانی هم برخوردار خواهند بود و در این صورت وزن هم در فرمول ۲ بزرگ خواهد بود و اگر وزن در فرمول ۲ بزرگ باشد بنابراین زمانی فرمول ۱ مینیمم خواهد بود که ترم کوچک باشد و احتمال پیکسل­ها شبیه هم باشد.
تابع هزینه در فرمول ۳-۸ با حل معادله خطی ۳-۱۰ می تواند بهینه شود.
(۳- ۱۰)
که x_u احتمال مجهول پیکسل­هایی است که برچسب­دار نشده­اند (وضعیت پیش­زمینه یا پس­زمینه بودنشان هنوز مشخص نشده است) و x_M پیکسل­هایی هستند که توسط کاربر تعیین وضعیت شده ­اند و این احتمال برابر ۱ است اگرمربوط به بطن­ها باشد و اگر ناحیه مربوط به پس­زمینه باشد احتمال برابر ۰ خواهد شد.
بردارهای b_Uو b_Mاحتمال آن­ها از قبل برای تصویر باینری (b) تعریف شده است.
ماتریس­های A , L وΩ ماتریس های تنک هستند و طبق فرمول­های زیر تعریف شده اند.
(۳-۱۱)
(۳-۱۲)
(۳-۱۳)
تمام پیکسل­های تصویر در دو دسته قرار می­گیرند، پیکسل­های­برچسب­گذاری شده (نقاطی که توسط کاربر برچسب گذاری شده ­اند) و پیکسل­هایی که بدون برچسبند. پس کلیه نقاط تصویر را می­توان بصورت XT=[] نوشت که با جایگذاری در فرمول شماره ۳-۱۰ خواهیم داشت:
(۳-۱۴ )
فرمول شماره ۳-۱۴ همان فرمول پیمایش تصادفی می­باشد و ما بدنبال بهینه کردن E(X)هستیم که با حل E(X_U) از طریق معادله خطی اویلر لاگرانژ مقدار بهینه بدست می ­آید.
(۳-۱۵)
ماتریس L تنک و غیر صفر می­باشد که بسته به نوع انتخاب شبکه و اتصال گره­ها (اتصال ۴ تایی، ۵ تایی، ۸ تایی، و ۲۹ تایی) میزان تنک بودن و نویز کم یا زیاد خواهد شد. در این تحقیق از اتصال ۴ تایی استفاده کرده­ایم.
۳-۴-۵- روش پیمایش تصادفی بهبود داده شده
در روش پیمایش تصادفی که در این تحقیق ارائه شده است تغییراتی ایجاد شده است که باعث بهبود عملکرد این روش می­ شود ، که عبارتند از :
برچسب گذاری اولیه پیکسل­ها به صورت خودکار
ارائه تابع وزن جدید برای یال­ها
همانطور که در بخش ۳-۳ گفته شد از طریق بخش بندی با روش PSO برچسب گذاری اولیه پیکسل­ها به صورت خودکار انجام شد.
در این تحقیق برای بهبودعملکرد روش پیمایش تصادفی نسبت به نوع قدیمی آن تابع وزن جدیدی معرفی شده است . تابع وزن عبارت است از:
(۳-۱۶)
که در آن g_i و g_j شدت روشنایی پیکسل­های j , i و dist عبارت است از فاصله بین دو پیکسل j,i.
امتیاز تابع (۳-۱۶) این است که علاوه بر اینکه اختلاف شدت روشنایی دو پیکسل را محاسبه می­ کند. فاصله دو پیکسل نیز در تابع وزن به حساب می اید که تابع وزن یک نسبت معکوس با فاصله دو پیکسل دارد با توجه به این نکته که قرار گرفتن دو پیکسل با فاصله بیشتر از یکدیگر، احتمال یک تغییر در شدت روشنایی را افزایش می­دهد. فاصله­ای که در این تحقیق استفاده شده فاصله اقلیدسی^[۴۰] می­باشد.
۳-۴-۶- خلاصه الگوریتم
مراحل زیر بطور خلاصه الگوریتم مورد نظر را ارائه می­ دهند:
به کمک (۳-۱۶) مقادیر و فاصله­های تصویر را به وزن یال­ها در لاتیس نگاشت کن.