شکل(۱-۴) الف) سرریز آب از آب‌گیر چپ به آب‌گیر راست و ساخته شدن یک سد کوتاه ب) نتیجه نهایی الگوریتم آب‌پخشان [۲]
با ادامه بالا آمدن آب، سرانجام از یک آب‌گیر آب‌ریز به آب‌گیر دیگری سرازیر می‌شود. اولین نشانه این حالت، در شکل(۱-۴) (الف) آمده است در این‌جا، آب از آب‌گیر چپ به آب‌گیر راست سرریز می‌کند و یک سد کوتاه (ازیک پیکسل) ساخته می‌شود. این شکل سد طویل‌تری را بین دو آب‌گیر آب‌ریز و سد دیگری در بخش بالایی آب‌گیر راست نشان می‌دهد. سد دومی برای جلوگیری از ادغام آب از آن آب‌گیر به‌کار می‌رود، به طوری که آب ناشی از ناحیه‌ها متناظر با پس‌زمینه است این فرایند ادامه می‌یابد تا به حداکثر سطح جریان برسد (متناظر با بزرگ‌ترین مقدار شدت روشنایی در تصویر). سدهای نهایی متناظر با خطوط آب‌پخشان هستند که نتیجه بخش‌بندی مطلوب هستند. به این خاصیت مهم توجه کنید که خطوط آب‌پخشان، مسیرهای متصلی را می‌سازند، لذا مرزهای متصلی بین ناحیه‌ها به وجود می‌آید. یکی از کاربردهای اصلی بخش‌بندی آب‌پخشان، استخراج اشیای تقریبا یک‌نواخت از پس‌زمینه است. ناحیه‌هایی که با تغییرات کوچکی در شدت روشنایی مشخص شدند، مقادیرگرادیان کوچکی دارند.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

۱-۲-۵-بخش‌بندی بر اساس نظریه گراف^[۱۲]
سازگاری هزینه محاسباتی الگوریتم‌های مبتنی بر گراف با قدرت کامپیوتر‌های امروزی سبب شده است تا استفاده از نظریه گراف در کاربردهای مختلفی از پردازش تصویر نظیر پردازش و آنالیز تصاویر دو و سه‌بعدی، شناسایی و تشخیص هویت در سیستم‌های بیومتریک^[۱۳] و همچنین بخش‌بندی و دسته‌بندی تصاویر پزشکی کاربرد فراوانی داشته باشد.
در ادامه پس از بیان تعاریف لازم یکی از روش‌های اولیه بخش‌بندی تصویر توسط نظریه گراف ارائه می‌شود [۴].
تعریف۱) یک گراف ساده G با n راس و m یال متشکل از مجموعه راس‌هایV (G) = {,,..,} و مجموعه‌ی E (G) = {,,..,} است که در آن هر یال به صورت یک زوج نامرتب از راس‌ها بیان می‌شود.
تعریف ۲) گراف ساده^[۱۴] و گراف وزن‌دار^[۱۵]، گرافی است که به هر یال آن یک برچسب (وزن) نسبت داده شده‌است.
تعریف ۳) گراف ساده G، هم‌بند^[۱۶] است اگر به‌ازای هر جفت گره‌ی دلخواه یک مسیر بین آنها وجود داشته باشد.
تعریف ۴) درخت T، گراف هم‌بندی است که در آن مسیر بسته وجود ندارد.
تعریف ۵) درخت فراگیر^[۱۷] متناظر با گراف هم‌بند G، درختی است که شامل همه گره‌های G بوده و یال‌های آن زیرمجموعه یال‌های G باشد.
تعریف ۶) درخت فراگیر کمینه برای گراف هم‌بند G، درخت فراگیری است که مجموع وزن‌های نسبت داده شده به یال‌های آن، کمتر از این حاصل جمع در مورد سایر درخت‌های فراگیر ممکن برای گراف G باشد.
در الگوریتم‌های پردازش تصویر که بر پایه نظریه گراف استوارند، ابتدا تصویر ورودی به یک گراف وزن‌دار تبدیل می‌شود [۵]. به‌این ترتیب که هر پیکسل از تصویر به یک گره در گراف تبدیل شده و وجود و عدم وجود یال بین این دو گره‌ها در تصویر، مشخص می‌شود. این همسایگی می‌تواند به صورت همسایگی چهار^[۱۸] و یا همسایگی هشت^[۱۹] در نظر گرفته شود. وزن هر یال نیز، بر اساس نوع کاربرد و خصوصیات تصویر تعیین شده و معمولا برابر با قدر مطلق تفاضل بین سطوح روشنایی دو پیکسل متناظر با گره‌های انتهایی هر یال در نظر گرفته می‌شود. بنابراین یک تصویر دو‌بعدی توسط گراف ساده و وزن‌دار G (V,E) مشخص می‌شود که در آن پیکسل‌های v به گره‌های گراف نگاشته شده و پیکسل‌های مجاور () را می‌سازند.
یکی از اولین و ساده‌ترین روش‌های بخش‌بندی تصویر با بهره گرفتن از نظریه گراف بر پایه استفاده از درخت فراگیر کمینه است [۵]. درخت فراگیر کمینه متناظر با گراف وزن‌دار یک تصویر به‌دلیل شباهت سطوح روشنایی پیکسل‌های آن ناحیه دارای وزن‌های کوچکی خواهد بود، ولی در محل‌های بین دو ناحیه‌ی مجاور از تصویر دارای یال‌هایی با وزن بزرگتر خواهد بود. هر چقدر تفاوت سطوح روشنایی دو پیکسل انتهایی یک یال بیشتر باشد وزن آن یال نیز بزرگتر خواهد بود. بنابراین با حذف K عدد از بزرگترین یال‌ها در درخت فراگیر کمینه، گراف حاصل به K درخت مجزا تقسیم‌بندی می‌شود که در هر درخت، هر گره شباهت بیشتر به گره‌های مجاور خود و شباهت کمتری نسبت به گره‌های مجاورش در سایر درخت‌ها دارد. بنابراین با توجه به پیکسل‌های تشکیل‌دهنده هر درخت، تصویر دو بعدی ورودی به K ناحیه مستقل بخش‌بندی می‌شود. استفاده از این روش برای بخش‌بندی تصاویری مناسب است که بدون نویز هستند و ناحیه‌های تشکیل دهنده آن دارای اختلاف شدت روشنایی قابل قبولی باشند.
۱-۲-۶-خوشه‌بندی فازی^[۲۰]
در روش‌های سنتی خوشه‌بندی، افرازهایی تولید می‌شود که در هر یک از آنها، هر الگو فقط و فقط به یک خوشه تعلق دارد [۶]. این افراز‌‌‌بندی را خوشه‌بندی سخت می‌نامند. در خوشه‌بندی فازی، مفهوم تعلق هر نمونه به تمام خوشه‌ها با بهره گرفتن از تابع عضویت مطرح می‌شود. نتیجه الگوریتم‌های فازی یک خوشه‌بندی است نه یک افراز. در خوشه‌بندی فازی هر خوشه یک مجموعه فازی از تمام نمونه‌ها است. در زیر یک الگوریتم کلی از خوشه‌بندی فازی ارائه شده‌است:

1. 1. k خوشه تصادفی انتخاب می‌شود.

1. 1. ماتریس عضویت U با اندازه NK ساخته می‌شود. هر آرایه از این ماتریس نمایانگر درجه عضویت نمونه به خوشه است.

1. 1. با بهره گرفتن از ماتریس U مقدار تابع هدف برای هر خوشه محاسبه می‌شود. برای کاهش مقدار رابطه فوق مجددا نمونه‌ها را به خوشه‌ها انتساب داده و ماتریس U بروز رسانی می‌شود:

1. 1. تا زمانی‌که آرایه‌های U تغییرات زیادی نکنند مرحله ۳ تکرار می‌شود.

۱-۲-۷-ماتریس هم رخداد
هارلیک^[۲۱]، ماتریس هم رخداد^[۲۲] را برای بررسی ساختار بافت‌های مختلف ویژگی‌هایی را بر‌اساس ماتریس هم‌جواری پیشنهاد کرد که از موفق‌ترین روش‌های بررسی خواص بافت‌های مختلف است [۷]. در این روش ابتدا ماتریس‌های هم‌رخداد برای فواصل و جهت‌های مختلف محاسبه می‌شوند و سپس برای هر یک از ماتریس‌ها تعدادی ویژگی محاسبه می‌شود. در این شیوه تصویر به یک ماتریس دو بعدی تبدیل می‌شود که هر درایه آن با احتمال قرار گرفتن شدت روشنایی (i,j)، در همسایگی به فاصله d و زاویه‌ای به اندازه بیان می‌شود. در نهایت با بهره گرفتن از توابعی که بر این ماتریس تعریف شده‌است، مشخصه‌هایی استخراج شده و با مقایسه آنها کلاس‌بندی انجام می‌شود. با بهره گرفتن از ماتریس هم‌رخداد، ما می‌توانیم ویژگی‌های مختلف از جمله احتمالات، آنتروپی، انرژی، واریانس، گشتاور معکوس و غیره را استخراج کنیم.
۱-۲-۸- کلاس‌بندی ماشین بردار پشتیبان^[۲۳]
ماشین بردار پشتیبان در واقع یک طبقه‌بندی‌کننده دودویی است که دو کلاس را با بهره گرفتن از یک مرز خطی از هم جدا می‌کند. در این روش با بهره گرفتن از تمامی باند‌ها و یک الگوریتم بهینه‌سازی، نمونه‌هایی که مرزهای کلاس‌ها را تشکیل می‌دهند به‌دست می‌آیند [۸]. این نمونه‌ها را بردارهای پشتیبان گویند. تعدادی از نقاط آموزشی که کم‌ترین فاصله تا مرز تصمیم‌گیری را دارند می‌توانند به‌عنوان زیر مجموعه‌ای برای تعریف مرزهای تصمیم‌گیری و به‌عنوان بردار پشتیبان در نظر گرفته ‌شوند. فرض کنید داده‌ها از دو کلاس تشکیل شده و کلاس‌ها در مجموع دارای، (i=1,..,L) نقطه آموزشی باشند که یک بردار است. این دو کلاس با برچسب زده می‌شوند. برای محاسبه مرز تصمیم‌گیری دو کلاس کاملا جدا از هم، از روش حاشیه بهینه استفاده می‌شود. در این روش مرز خطی بین دو کلاس به‌گونه‌ای محاسبه می‌شود که تمام نمونه‌های کلاس ۱+ در یک طرف مرز و تمام نمونه‌های کلاس ۱- در طرف دیگر مرز واقع شوند.
مرز تصمیم‌گیری باید به‌گونه‌ای باشد که فاصله نزدیک‌ترین نمونه‌های آموزشی هر دو کلاس از یک‌دیگر در راستای عمود بر مرز تصمیم‌گیری تا جایی که ممکن است حداکثر شود. یک مرز تصمیم‌گیری خطی را در حالت کلی می‌توان به‌صورت زیر نوشت:
(۱-۷) w. x +b =۰
x یک نقطه روی مرز تصمیم‌گیری و wیک بردارn بعدی عمود بر مرز تصمیم‌گیری است. فاصله مبدأ تا مرز تصمیم‌گیری و w. x بیانگر ضرب داخلی دو بردار x و w است. از آنجا که با ضرب یک ثابت در دو طرف باز هم تساوی برقرار خواهد بود، برای تعریف یکتای مقدار w و b شرایط زیر بر روی آنها اعمال می‌شود.

اولین مرحله برای محاسبه مرز تصمیم‌گیری بهینه، پیدا کردن نزدیک‌ترین نمونه‌های آموزشی دو کلاس است. در مرحله بعد فاصله آن نقاط از هم در راستای عمود بر مرزهایی که دو کلاس را به‌طورکامل جدا می‌کنند محاسبه می‌شود. مرز تصمیم‌گیری بهینه، مرزی است که حداکثر حاشیه را داشته باشد. مرز تصمیم‌گیری بهینه با حل مسئله بهینه‌سازی زیر محاسبه می‌شود:
max min
W,b i=1,…,L
(۱-۹)
با انجام یک‌سری عملیات ریاضی، رابطه بالا به رابطه زیر تبدیل می‌شود.
(۱-۱۰)
حل کردن مسئله بهینه‌سازی کار مشکلی است. برای ساده‌تر کردن آن با بهره گرفتن از روش ضرایب نامعین لاگرانژ این مسئله بهینه‌سازی را می‌توان به فرم زیر تبدیل کرد که ها ضرایب لاگرانژ می‌باشند.