|
#تغییرمسیر [[بخش‌بندی تصویر]]
{{سرشناسی|تاریخ=سپتامبر ۲۰۱۹}}
امروزه یکی از اهداف مهم در تجزیه و تحلیلی عکس و [[بینایی رایانه‌ای|بینایی کامپیوتر]]، قطعه‌بندی تصویر به معنی قسمت‌بندی عکس به تعدادی بخش است. به طور دقیق‌تر، segmentation عکس به معنی نسبت دادن یک برچسب یا label به هر پیکسل در تصویر است یه طوریکه پیکسل‌ها با برچسب یکسان، یک ویژگی یکسان را در تصویر به نمایش بگذارند. هدف از این کار ساده‌سازی عکس برای آنالیز است.
segmentation به کمک محاسبه برش کمینه در یک گراف، یکی از روش‌های جدید برای segmentation است.
=== graph cut ===
یک گراف بدون جهت یا[//en.wikipedia.org/wiki/Markov_random_field MRF] را می‌توان به صورت <G=<V,E نوشت به‌طوریکه V مجموعه گره‌ها و E مجموعه‌ی تمام یال‌ها در گراف است. گره‌های یک گراف را می‌توان در یک گراف مربوط به عکس به دو دسته تقسیم کرد. گره‌هایی که در همسایگی هم قرار دارند و درواقع همان پیکسل‌های تصویر هست و ۲ گره دیگر به نام S,T کهS در عکس ُ‌نماینده گره‌هاییست که شی موردنظر را نمایش می‌دهند و T نماینده پس‌زمینه است. این نوع گراف را گراف S,T هم می‌نامند.
در این گراف یال‌ها هم شامل چند دسته‌اند:nlink که یال‌ها بین پیکسل‌های همسایه هستند و tlink که گره t یا همان terminal را به گره‌های تصویر متصل م‌کند. در این نوع گراف‌ها وزن‌ها همواره غیر منفی درنظر گرفته می‌شوند. یک کات در گراف یک زیرمجموعه از یال‌هاست و با C معرفی میشود. هزینه هر کات معادل مجموع وزن یال‌هاییست که در آن کات واقع شده است. کات کمینه به برشی گفته میشود که این هزینه در آن برش مینیمم شود. پیدا کردن برش کمینه معادل پیدا کردن maxflow در گراف است. برای segmentation می‌توان به گره S برچسب ۱ و به گره‌های t که همان پس‌زمینه هستند برچسب۰ نسبت داد و عملیات segmentation را به صورت کمینه کردن انرژی در این MRF محاسبه کرد.
مسائل گراف کات در بینایی را می‌توان به صورت یک مسئله حداقل کردن انرژی درنظر گرفت. در اینجا ما به دنبال یافتن برچسب f هستیم که انرژی را به حداقل برساند.
{{چپ‌چین}}
<math> E(f)= E_{smooth}(f)+E_{data}(f)</math>
{{پایان چپ‌چین}}
ٍE<sub>smooth</sub> تشابه f با برچسب پیکسل‌های اطراف و E<sub>data</sub> اختلاف f با داده‌های مشاهده شده را نشان می‌دهد.
انرژی داده به روش‌های مختلفی محاسبه میشود اما درحالت کلی میزان شباهت پیکسل و برچسب آن برای محاسبه انرژی مورد بررسی قرار می‌گیرد.
انتخاب E<sub>smooth</sub> یک مسئله بحرانی است و انتخاب‌های زیادی هم برای آن وجود دارد مثلاً در بعضی روش‌ها همیشه f را شبیه همسایگان انتخاب می‌کنند که این باعث نتایج ضعیف در مرز بین شی‌های تصویر میشود. توابع انرژی که این مشکل را ندارند، توابع discontinuity preserving نامیده می‌شوند.
مشکل اصلی در اینجا هزینه محاسباتی بالاست به این دلیل که فضای انتخاب برچسب بسیار بزرگ است و دارای هزاران برچسب مختلف هستیم. از طرفی این مسئله دارای مینیمم‌های محلی زیادیست.
توابع انرژی که ما درنظر گرفتیم به صورت زیر است:
{{چپ‌چین}}
<math> E(f)= \sum_{p} D_p (f_p)+\sum_{N} V_{p,q} (f_p,f_q)</math>
{{پایان چپ‌چین}}
N مجموعه جفت پیکسل‌هایی که با هم در ارتباطند. معمولاً این ارتباطات بین دو پیکسل همسایه درنظر گرفته میشود، همچنین معمولاً مقدار D<sub>data</sub> غیر منفی است. مقدار هرکدام ازVها می‌تواند متفاوت باشد و بستگی به کاربرد دارد.
این دو الگوریتم مینیمم کردن انرژی را براساس دو دسته کلاس از V می‌توانند انجام دهند. کلاس‌های سمیمتریک و [[:en:Metric (mathematics)|metric]] که هردوی این کلاس‌ها باعث ایجاد توابعی که دارای خاصیت discontinuity preserving هستند، میشود.
== الگوریتم گسترش آلفا ==
ایده اصلی در الگوریتم گسترش آلفا، پیداکردن روش مناسب دسته‌بندی پیکسل‌ها بوسیله‌ی تنها دوبرچسب آلفا و غیرآلفا بااستفاده از الگوریتم گراف کات است. در این الگوریتم در هر مرحله، مقدار آلفا تغییر می‌کند تا تمام برچسب‌ها پوشش داده‌شوند.
ساختار این گراف که درواقع یک گراف s_t است در هر مرحله از الگوریتم، بوسیله‌ی برچسب آلفا مشخص میشود. در نتیجه این ساختار به صورت پویا درحال تغییر است. در ابتدا گراف بوسیله‌ی برچسب‌بندی اولیه‌ی f و مقدار آلفا ساخته میشود. سپس به کمک جدول موجود در شکل جدول وزن‌های مربوط به گسترش آلفا که نحوه وزن‌دهی به این گراف را مشخص می‌کند، برش‌های اولیه مشخص می‌شوند. برای هر آلفا برش‌بندی بهینه انتخاب شده و در مرحله‌ی بعدی به عنوان گراف ورودی آلفا بعد بررسی میشود. ساختار گراف توصیف شده در شکل گراف s-t برای الگوریتم آلفا قابل مشاهده است.
[[پرونده:AlphALGO.jpg|جایگزین=|بندانگشتی|400x400پیکسل]]
== الگوریتم مبادله آلفابتا ==
ایده اصلی در مبادله آلفابتا، برچسب زدن صحیح به‌وسیله‌ی αوβ است و در این الگوریتم تمامی حالت‌ها برای αوβ متفاوت محاسبه خواهند شد.در هر تکرار یکی زوج αوβ بررسی میشود و این روند تا زمانیکه segmentation همگرا شود، ادامه می‌یابد.
در هر تکرار، ناحیه‌ی مربوط به αوβ تعیین میشود ولی در این قسمت، گره‌هایی که مربوط به هیچکدام از αوβنباشند هم داریم. در این حالت وزن پیکسلی که عضو هیچکدام نیس، مجموع تمام لینک‌های بین این پیکسل و تمام همسایگانی است که به هیچکدام از
αوβ نیست.
== منابع ==
{{پانویس}}
Boykov, Yuri, Olga Veksler, and Ramin Zabih. "Fast approximate energy minimization via graph cuts." In Proceedings of the Seventh IEEE International Conference on Computer Vision, vol. 1, pp. 377–384. IEEE, 1999
[[رده:ویکی‌سازی رباتیک]]
| 