در بخش بندی تصویر هدف جدا سازی تصویر به نواحی مجزا و همگن است و در حالت ایده آل باید نتیجه بدست آمده با نواحی حاصل از بخش بندی ذهن انسان منطبق باشد. در رابطه با بخش بندی تصویر، الگوریتم های متعددی تا به امروز ارائه شده اند. از جمله این روشها می توان به روشهای مبتنی بر گراف اشاره کرد که روشهای مبتنی بر گراف برروی تصاویر با نواحی همگن نتایج مناسبی دارند.و علاوه بر آن اطلاعات مکانی و فضای ویژگی پیکسلها به طور همزمان برای بخش بندی تصویر با یکدیگر ترکیب می شوند. چهارچوب کلی این روشها به این صورت است که هر پیکسل تصویر را به عنوان یک گره از گراف در نظر گرفته و وزن یال بین دو گره بر اساس یک معیار شباهت بین دو پیکسل متناظر با این دو گره در تصویر تعریف می شود و بخش بندی گراف ساخته شده بر اساس یک معیار خاص انجام می گیرد.
مساله بخش بندی گره های یک گراف برای کاربردهای گوناگون با فرمول بندی های مختلفی مورد مطالعه قرار گرفته است و الگوریتم های دقیق یا تقریبی ای برای برخی از این فرمول بندی ها پیشنهاد شده است. در این پایان نامه ابتدا به مرور برخی از این فرمول بندی ها و الگوریتم های کارآمد پرداخته است.همچنین فرمول بندی مناسب برای یک کاربرد خاص در پردازش تصویر یعنی بخش بندی تصویر را بیان کرده و در انتها با ارائه یک الگوریتم جدید برای بخش بندی گراف های وزن دار و مقایسه آن با چند الگوریتم مشابه، کارآیی آن را نشان داده است.سپس به منظور بررسی کارآیی الگوریتم با فرمول بندی مساله بخش بندی تصویر به صورت یک مساله بخش بندی گراف، نتایج عملکرد آن را روی پایگاه تصاویر برکلی آورده است.
منبع پایان نامه
http://library.sharif.ir/parvan/resource/293209