بخش‌بندی تصویر
روش تقسیم کردن گراف > Markov random fields > بخش‌بندی با نظارت با استفاده از MRF و MAP

در زمینه بخش‌بندی، تابعی که الگوریتم MRF به دنبال ماکزیمم کردن آن است، احتمال تشخیص یک طرح برچسب گذاری با توجه به مجموعه از ویژگی هاست شناسایی شده در تصویر، می‌باشد. این موضوع بیان دیگری از روش برآوردگر بیشینه‌گر احتمال پسین است.
همسایگی MRF برای یک پیکسل مشخص
مراحل الگوریتم ژنتیک برای یخش بندی تصویر با استفاده از MAP در زیر آورده شده است:
همسایگی هر ویژگی را تعریف کنید. در حالت کلی این مجاورت شامل هماسیگی‌های مرتبه اول و دوم می‌شود.
احتمال اولیه P(fi) برای هر ویژگی را تعیین کنید
که در آن fi ∈ Σ مجموعه‌هایی هستند که شامل ویژگی‌های استخراج شده برای پیکسل i ام می‌باشند و کلاس‌های اولیه را تعریف می‌کنند.
با استفاده از دیتای آموزشی میانگین (μli) و واریانس (σli) برای هر پیکسل قابل محاسبه خواهد بود.
تابع احتمال حاشیه‌ای P(fi|li) را با استفاده از تئوری بیز، برای هر طرح برچسب گذاری محاسبه کنید. مدل گوسین زیر برای محاسبه احتمال حاشیه ای مورد استفاده قرار می‌گیرد.
 {\frac {1}{\sigma (l_{i}){\sqrt {2\pi }}}}e^{-{\frac {(f_{i}-\mu (l_{i}))^{2}}{2\sigma (l_{i})^{2}}}}
احتمال برچسب هر کلاس را با توجه به همسایگی تعریف شده در مراحل قبل، محاسبه کنید
احتمالات پیشین جدید را تکرار کنید و کلاس‌ها را به نحوی بازتعریف کنید که مقادیر این احتمالات ماکزیمم شود. این مرحله با استفاده از بسیاری از الگوریتم‌های بهینه‌ساز قابل اجرا خواه بود.
زمانی که مقادیر توابع احتمال ماکزیمم شد و برچسب هیچ کلاسی تغییر نکرد، عملیات را متوقف کنید.
یک گراف بدون جهت یا مارکوفی را می‌توان به صورت <G=<V,E نوشت به‌طوریکه V مجموعه گره‌ها و E مجموعهٔ تمام یال‌ها در گراف است. گره‌های یک گراف را می‌توان در یک گراف مربوط به عکس به دو دسته تقسیم کرد. گره‌هایی که در همسایگی هم قرار دارند و درواقع همان پیکسل‌های تصویر هست و ۲ گره دیگر به نام S,T کهS در عکسُ نماینده گره‌هاییست که شی موردنظر را نمایش می‌دهند و T نماینده پس‌زمینه است. این نوع گراف را گراف S,T هم می‌نامند.
در این گراف یال‌ها هم شامل چند دسته‌اند:nlink که یال‌ها بین پیکسل‌های همسایه هستند و tlink که گره t یا همان terminal را به گره‌های تصویر متصل م‌کند. در این نوع گراف‌ها وزن‌ها همواره غیر منفی درنظر گرفته می‌شوند. یک کات در گراف یک زیرمجموعه از یال‌هاست و با C معرفی می‌شود. هزینه هر کات معادل مجموع وزن یال‌هاییست که در آن کات واقع شده است. کات کمینه به برشی گفته می‌شود که این هزینه در آن برش مینیمم شود. پیدا کردن برش کمینه معادل پیدا کردن maxflow در گراف است. برای segmentation می‌توان به گره S برچسب ۱ و به گره‌های t که همان پس‌زمینه هستند برچسب۰ نسبت داد و عملیات segmentation را به صورت کمینه کردن انرژی در این MRF محاسبه کرد.
مسائل گراف کات در بینایی را می‌توان به صورت یک مسئله حداقل کردن انرژی درنظر گرفت. در اینجا ما به دنبال یافتن برچسب f هستیم که انرژی را به حداقل برساند.
E(f)=E_{smooth}(f)+E_{data}(f)
ٍEsmooth تشابه f با برچسب پیکسل‌های اطراف و Edata اختلاف f با داده‌های مشاهده شده را نشان می‌دهد.
انرژی داده به روش‌های مختلفی محاسبه می‌شود اما درحالت کلی میزان شباهت پیکسل و برچسب آن برای محاسبه انرژی مورد بررسی قرار می‌گیرد.
انتخاب Esmooth یک مسئله بحرانی است و انتخاب‌های زیادی هم برای آن وجود دارد مثلاً در بعضی روش‌ها همیشه f را شبیه همسایگان انتخاب می‌کنند که این باعث نتایج ضعیف در مرز بین شی‌های تصویر می‌شود. توابع انرژی که این مشکل را ندارند، توابع discontinuity preserving نامیده می‌شوند.
مشکل اصلی در اینجا هزینه محاسباتی بالاست به این دلیل که فضای انتخاب برچسب بسیار بزرگ است و دارای هزاران برچسب مختلف هستیم. از طرفی این مسئله دارای مینیمم‌های محلی زیادیست.
توابع انرژی که ما درنظر گرفتیم به صورت زیر است:
E(f)=\sum _{p}D_{p}(f_{p})+\sum _{N}V_{p,q}(f_{p},f_{q})
N مجموعه جفت پیکسل‌هایی که با هم در ارتباطند. معمولاً این ارتباطات بین دو پیکسل همسایه درنظر گرفته می‌شود، همچنین معمولاً مقدار Ddata غیر منفی است. مقدار هرکدام ازVها می‌تواند متفاوت باشد و بستگی به کاربرد دارد.
این دو الگوریتم مینیمم کردن انرژی را براساس دو دسته کلاس از V می‌توانند انجام دهند. کلاس‌های سمیمتریک و متریک (ریاضیات) که هردوی این کلاس‌ها باعث ایجاد توابعی که دارای خاصیت discontinuity preserving هستند، می‌شود.