کنیم که تغییر مقادیر پیکسلها در تصویر را با وزن یالها مرتبط سازد. استفاده از این نوع توابع از ویژگیهای الگوریتمهای مبتنی بر گراف است. در الگوریتم پیمایشگر تصادفی از وزن گوسی استفاده شده است.
( 3-3) w_ij=exp(-β(g_i-g_j )^2 )

که gi مقدار پیکسل در پیکسل i را مشخص میکند. مقدار β تنها پارامتر آزاد الگوریتم را مشخص میکند. بهتر است که معادله بالا قبل از استفاده نرمالسازی شود. همچنین این معادله میتواند به منظور استفاده از اطلاعات بافت، ضرایب فیلتر و مشخصههای تصویر ویرایش شود.
3-4-2- مسئله دیریکله ترکیبی
در مقدمه عنوان کردیم که حل مسئله دیریکله ترکیبی برابر با احتمالهای پیمایشگر تصادفی دلخواه است. در این بخش نحوه یافتن حل مسئله دیریکله را مرور میکنیم. انتگرال دیریکله شامل فیلد U و ناحیه امگا است که مرتبط با انتقال گرما، الکتروستاتیک و پیمایشهای تصادفی میباشد. یک تابع هارمونیک تابعی است که معادله لاپلاس را ارضا کند . مسئله دیریکله در واقع یافتن یک تابع هارمونیک است که شرایط مرزی را ارضا میکند. تابع هارمونیک که شرایط مرزی را ارضا کند انتگرال دیریکله را کمینه میکند چرا که معادله لاپلاس معادله اویلر- لاگرانژ برای انتگرال دیریکله است. سپس ماتریس ترکیبی لاپلاس و ماتریس رویداد راس-یال تعریف میشود.

3-4-3- قیاس مداری
همانطور که توضیح داده شد میتوان به کمک مدارهای الکتریکی رفتار پیمایشگر تصادفی را شبیهسازی کرد. همانطور که در تصویر 1-3 نشان داده شده است، میتوان مساله را به کمک مدار، شبیهسازی کرد. سه اصل مهم در تئوری مدار شامل قانون اهم، ولت و کیرشهف را در نظر بگیرید:
(3-4) قانون جریان کیرشهف A_Z^T=f
(3-5) قانون اهم C_P=Z
(3-6) قانون ولتاژ کیرشهف P=A_x+b

این سه معادله را می توان در یک سیستم خطی ترکیب کرد:
(3-7) 〖 A〗^T CA_X+A^T Cb=f , L_x=f-A^T Cb

3-4-4- ارتباط روش با فرایند انتشار در بینایی ماشین
در بینایی ماشین عمل انتشار را میتوان به کمک پیمایشهای تصادفی توصیف کرد. در این بخش ارتباط بین فرایند انتشار و روش کنونی را بررسی میکنیم. تفاوت اصلی بین معادله انتشار و معادله لاپلاس این است که انتشار یک فرایند انتقال در زمان را نشان میدهد در حالیکه معادله لاپلاس یک توزیع حالت پایدار را توصیف میکند. علیرغم شباهت ریاضی معادلات لاپلاس با معادلات انتشار این دو الگوریتم با هم تفاوت زیادی دارند. بویژه فرایند انتشار معمولا بصورت یک الگوریتم بهبود تصویر به کار میرود بطوریکه مقادیرخاکستری اولیه پیکسلهای تصویر به عنوان شرایط اولیه مسئله در نظر گرفته میشوند و حل مسئله بعد از طی بازه زمانی از پیش تعیین شده متوقف میشود. در مقابل در این تحقیق یک الگوریتم تقطیع مبتنی بر نقاط شروع توصیف میشود که از شرایط اولیه استفاده نمیکند بلکه برای مشخص کردن مرزها از توزیع حالت پایدار پتانسیلها استفاده میکند. درالگوریتم پیمایش تصادفی برای تحلیل تصویر بدنبال یافتن وزنهای کمینه هستیم.
اگر xi احتمال پیکسل i مربوط به پیش زمینه (متعلق به دو بطن راست یا چپ) ، بخشبندی بطن چپ و راست میتوانند با به حداقل رساندن تابع هزینه بصورت زیر باشد:
(فرمول 3-8) E(X)=1/2 ∑_(c_ij ϵC_(I:I))▒〖w_ij (x_i-x_j )^2 〗
(3-9) w_ij≔{█(exp(-β(I_i-I_j ))@ O )┤ ( i,j connected)¦(O.W.)

کهβ مقدار ثابت مثبت میباشد، xi وxj احتمال پیکسل i و j هستند و در فرمول شماره 2 مقدار wij برابر صفر خواهد بود زمانیکه پیکسلها متصل نباشند. ما بدنبال مینیممکردن تابع هزینه هستیم، پیکسلهایی که از شدت روشنایی یکسان برخوردارند از احتمالهای یکسانی هم برخوردار خواهند بود و در این صورت وزن هم در فرمول 2 بزرگ خواهد بود و اگر وزن در فرمول 2 بزرگ باشد بنابراین زمانی فرمول 1 مینیمم خواهد بود که ترم (x_i-x_j )^2 کوچک باشد و احتمال پیکسلها شبیه هم باشد.
تابع هزینه در فرمول 3-8 با حل معادله خطی 3-10 می تواند بهینه شود.

(3- 10) (L_U+γA_U ) X_U= γΩ_B^T b_M+γΩ_U b_U-L_B^T X_M+γA_B^T X_M

که xu احتمال مجهول پیکسلهایی است که برچسبدار نشدهاند (وضعیت پیشزمینه یا پسزمینه بودنشان هنوز مشخص نشده است) و xM پیکسلهایی هستند که توسط کاربر تعیین وضعیت شدهاند و این احتمال برابر 1 است اگرمربوط به بطنها باشد و اگر ناحیه مربوط به پسزمینه باشد احتمال برابر 0 خواهد شد.
بردارهای bUو bMاحتمال آنها از قبل برای تصویر باینری (b) تعریف شده است.
ماتریسهای A , L وΩ ماتریس های تنک هستند و طبق فرمولهای زیر تعریف شده اند.
(3-11) Ω_ij=2ω_ij

(3-12) L_ij={█(L_i [email protected]_ij e_ij∈c_(I:I)@O e_ij∉c_(I:I) )┤ A_i=2∑_( e_ij∈c_(I:I))▒w_ij

(3-13) A_ij={█(A_i [email protected] O.W.)┤ A_i=∑_(e_ij∈c_(I∷R))▒ω_ij

تمام پیکسلهای تصویر در دو دسته قرار میگیرند، پیکسلهایبرچسبگذاری شده (نقاطی که توسط کاربر برچسب گذاری شدهاند) و پیکسلهایی که بدون برچسبند. پس کلیه نقاط تصویر را میتوان بصورت XT=[X_M^T X_U^T] نوشت که با جایگذاری در فرمول شماره 3-10 خواهیم داشت:
(3-14 ) E(x_U )=1/2 ([x_M^T x_U^T ][L_M¦(L_B^T ) L_B¦L_U ][x_M¦x_U ])=1/2(x_M^T L_M x_M
+2x_U^T B^T x_M+x_U^T L_U x_U)

فرمول شماره 3-14 همان فرمول پیمایش تصادفی میباشد و ما بدنبال بهینه کردن E(X)هستیم که با حل E(XU) از طریق معادله خطی اویلر لاگرانژ مقدار بهینه بدست میآید.
(3-15) L_U x_U=-L_B^T x_M

ماتریس L تنک و غیر صفر میباشد که بسته به نوع انتخاب شبکه و اتصال گرهها (اتصال 4 تایی، 5 تایی، 8 تایی، و 29 تایی) میزان تنک بودن و نویز کم یا زیاد خواهد شد. در این تحقیق از اتصال 4 تایی استفاده کردهایم.

3-4-5- روش پیمایش تصادفی بهبود داده شده
در روش پیمایش تصادفی که در این تحقیق ارائه شده است تغییراتی ایجاد شده است که باعث بهبود عملکرد این روش میشود ، که عبارتند از :
برچسب گذاری اولیه پیکسلها به صورت خودکار
ارائه تابع وزن جدید برای یالها
همانطور که در بخش 3-3 گفته شد از طریق بخش بندی با روش PSO برچسب گذاری اولیه پیکسلها به صورت خودکار انجام شد.
در این تحقیق برای بهبودعملکرد روش پیمایش تصادفی نسبت به نوع قدیمی آن تابع وزن جدیدی معرفی شده است . تابع وزن عبارت است از:
(3-16) w_(i,j)=exp(〖-β(g_i-g_j )〗^2 ).1/dist(i,j)

که در آن gi و gj شدت روشنایی پیکسلهای j , i و dist عبارت است از فاصله بین دو پیکسل j,i.
امتیاز تابع (3-16) این است که علاوه بر اینکه اختلاف شدت روشنایی دو پیکسل را محاسبه میکند. فاصله دو پیکسل نیز در تابع وزن به حساب می اید که تابع وزن یک نسبت معکوس با فاصله دو پیکسل دارد با توجه به این نکته که قرار گرفتن دو پیکسل با فاصله بیشتر از یکدیگر، احتمال یک تغییر در شدت روشنایی را افزایش میدهد. فاصلهای که در این تحقیق استفاده شده فاصله اقلیدسی40 میباشد.

3-4-6- خلاصه الگوریتم
مراحل زیر بطور خلاصه الگوریتم مورد نظر را ارائه میدهند:
به کمک (3-16) مقادیر و فاصلههای تصویر را به وزن یالها در لاتیس نگاشت کن.
مجموعهای به اندازه k از پیکسلهای علامت گذاری شده رابه صورت خودکار بدست آآور.
معادله 3-14 را برای پتانسیلها و یا معادله 3-13 را برای هر یک از برچسب ها به جز آخرین مورد حل کن و X_i^f=1-∑▒〖s به کمک انتساب برچسب متناظر به هر نود تقطیع نهایی را بدست آور.
همچنین می توان بر اساس پتانسیلها برچسبهای دیگری به هر پیکسل انتساب داد.

3-4-7- ویژگیهای الگوریتم از نظر تئوری
اگر چه روش جدیدی برای تقطیع تصویر ارائه شد لازم است که رفتار الگوریتم هم از لحاظ تئوری و هم عملی بررسی شود. در این بخش ویژگی الگوریتم را از نظر تئوری با بررسی رفتار مورد انتظار الگوریتم در حضور نویز بررسی میشود. بویژه نشان میدهیم که هر قطعه متصل است و الگوریتم به نویز مقاوم است. در ادامه روشهای معادلی برای یافتن چگونگی انتساب برچسب به نقاط توسط پیمایشگر تصادفی با در دست داشتن گراف وزندار را بررسی می کنیم:
اگر پیمایشگر تصادفی بعد از ترک پیکسل اولیه به احتمال زیاد اولین بار به پیکسلی میرسد که برچسب s دارد، برچسب پیکسل را s قرار بده.
اگر به جای نقاط از منابع ولتاژ واحد استفاده شد به پیکسل برچسبی را انتساب بده که نقطه متناظرش که در حال حاضر وضعیت روشن دارد بیشترین پتانسیل الکتریکی را تولید کند.
به پیکسل برچسبی را انتساب بده که نقطه متناظرش بیشترین جریان الکتریکی (یا کمترین مقاومت کارا) را دارد.
در بخش قبل ما تصویر را تا حدی بخشبندی نموده و نقاط برچسب دار را به صورت اتوماتیک تعیین نمودیم همانطور که در تصویر دیده میشود بخشبندی بطن راست به علت نازک بودن دیواره آن دقت از بالایی برخوردار نیست حال با اعمال روش پیمایشگر تصادفی بهبود داده شده در این قسمت بخشبندی نهایی را انجام میدهیم همانطور که در شکل دیده میشود بخشبندی بطن راست و چپ انجام شده است و مشاهده میشود بخشبندی در قسمت بطن راست خیلی دقیقتر میباشد..

الف

ب

Post your comment

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *