بخشی از مقاله
چکیده
شبکههای مارکوفی، کلاس مهمی از مدلهای گرافی میباشند که کاربرد وسیعی در بینایی کامپیوتر، آنالیز تصاویر پزشکی، بخشبندی تصویر، نظریه اطلاعات و فیزیک آماری دارند. شبکههای مارکوفی شامل یک گراف غیرجهتدار و یک مجموعه گسسته از برچسبها هستند. مسئله استنباط MAP برای یک شبکه مارکوفی بهصورت پیدا کردن تخصیص بهینه برچسبها به رئوس گراف تعریف میشود، که هزینه تخصیص برچسبها مینیمم شود.
این مسئله استنباطی که یک مسئله عدد صحیح است، -NPسخت میباشد. ما به مطالعه روش تجزیه دوگان برای حل این مسئله میپردازیم. بهوسیله روش تجزیه دوگان ابتدا مسئله را به زیرمسئلههای قابل حل و آسانتر تجزیه کرده و سپس به کمک روش زیرگرادیان تصویر شده، تلاش میشود تا یک جواب برای مسئله اولیه بیابد. این روش، در صورت تعیین طول گام مناسب همواره به یک جواب همگراست که به خوبی جواب حاصل از آزادسازی خطی این مسئله است.
-1 مقدمه
شبکههای مارکوفی شامل یک گراف غیرجهتدار G= - V, - هستند که در آن هر رأس متناظر با یک متغیر تصادفی است و یالها، وابستگی بین متغیرها را نشان میدهند. فرض کنید L مجموعه گسسته از مقادیر - برچسبها - باشد که هر متغیر تصادفی مقادیر خود را از آن میگیرد. تابع فاکتور تابعی است که به ازای هر تخصیص از متغیرهای تصادفی موجود در قلمرو فاکتور، یک مقدار حقیقی نسبت میدهد. تابع توزیع توأم یک تابع فاکتور است که به ازای تمام مقادیری که متغیرهای تصادفی به خود میگیرند یک مقدار عددی بین 0 و 1 نسبت میدهد.
