وبلاگ

بخش‌بندی تصویر با بهره گرفتن از روش‌ها‌ی بهینه‌سازی نیز انجام می‌شود. از جمله الگوریتم‌های بهینه‌سازی مهم می‌توان به الگوریتم‌های تکاملی، الگوریتم ژنتیک، الگوریتم کلونی مورچه والگوریتم حرکت دسته جمعی پرندگان اشاره کرد.
۱-۲-۱-مبانی بخش‌بندی
فرض کنید R کل ناحیه مکانی اشغال شده توسط تصویر را نشان می‌دهد [۲]. می‌توان بخش‌بندی تصویر را فرآیندی دانست که R را به n زیرناحیه R_n، …،R₂، R₁ تقسیم می‌کند، به‌طوری‌که:
الف.
ب. R_i مجموعه متصل است، برای n، …،۲،i=1

پ.  به ازای هرj، i که
ت.  به ازای n، …،۲،۱ = i
ث.  برای هر ناحیه هم‌جوار R_i و R_i.
در این‌جا،  یک فرمول منطقی است که روی نقاط مجموعه R_K تعریف شد و  مجموعه تهی است. نمادهای  به ترتیب، اجتماع، اشتراک مجموعه‌اند. دوناحیه R_iو R_j درصورتی هم‌جوار هستند که اجتماع آنها تشکیل مجموعه متصل را بدهد.
شرط (الف) نشان می‌دهدکه بخش‌بندی باید کامل باشد [۲]، یعنی دو پیکسل باید در یک ناحیه باشند، شرط (ب) نیازمند این است که نقاط موجود در یک ناحیه باید براساس قواعد از پیش تعریف شده‌ای متصل باشند (مثلاً، نقاط باید اتصال ۴‌تایی یا ۸تایی داشته باشند. شرط (پ) نشان می‌دهد که ناحیه‌ها باید از هم جدا باشند. شرط (ت) با خواصی سروکار دارد که باید توسط پیکسل‌های موجود در ناحیه بخش‌بندی شده برآورده شوند. شرط (ث) نشان می‌دهد که دو ناحیه همجوار R_i و R_j باید با توجه به فرمول، متفاوت باشند.
بنابراین، مسئله اصلی دربخش‌بندی، تقسیم تصویر به‌ناحیه‌هایی است که شرایط قبلی را برآورده نماید. الگوریتم‌های بخش‌بندی برای تصاویر خاکستری معمولاً براساس یکی از دو دسته‌ای هستند که با مقادیر شدت روشنایی مثل ناپیوستگی و شباهت سروکار دارند. در بخش‌بندی براساس ناپیوستگی‌ها فرض بر این است که مرزهای ناحیه‌ها به‌طور کامل متفاوت از هم و متفاوت از پس‌زمینه‌ هستند، درنتیجه تشخیص مرز براساس ناپیوستگی‌های محلی در شدت‌روشنایی امکان‌پذیر است. بخش‌بندی مبتنی برلبه، روش اصلی مورد استفاده در این دسته است. روش‌های بخش‌بندی مبتنی برناحیه، مبتنی برتقسیم‌بندی تصویر به ناحیه‌هایی است که براساس مجموعه‌ای از معیار از پیش تعریف شده، مشابه‌ هستند.
۱-۲-۲-تشخیص لبه^[۴]
در این بخش بر روش‌های بخش‌بندی تاکید می‌شود که مبتنی بر تشخیص تغییرات محلی تیز در شدت‌ روشنایی هستند [۲]. پیکسل‌های لبه، پیکسل‌هایی هستند که در آنها شدت روشنایی تصویر به‌شدت تغییر می‌کند. تشخیص دهنده‌های لبه، از روش‌های پردازش تصویر هستند که برای تشخیص پیکسل‌های لبه طراحی شده‌اند. خط را می‌توان به‌عنوان یک لبه دانست که در آن، شدت روشنایی پس‌زمینه در هر دو طرف خط، خیلی بالاتر یا خیلی کمتر از شدت روشنایی پیکسل‌های خط است. منظور از خط، ساختار‌های باریک است و معمولاً ضخامت آنها یک پیکسل است. از تشخیص لبه غالباً برای بخش‌بندی تصاویر براساس تغییرات سریع در شدت روشنایی استفاده می‌شود. لبه شامل گذری بین دو سطح شدت روشنایی است که به‌طور ایده‌آل روی فاصله‌ی یک پیکسلی رخ می‌دهد. اندازه مشتق اول می‌تواند برای تشخیص لبه در ناحیه‌ای از تصویر به‌کار ‌رود. از تکنیک‌های پیشرفته‌تر برای لبه‌یابی، می‌توان به تشخیص‌دهنده لبه مار-هیلدرث^[۵] و تشخیص‌دهنده لبه به روش تبدیل کافی^[۶] اشاره کرد.
۱-۲-۳-آستانه‌گیری^[۷]
به دلیل خواص شهودی، سهولت پیاده‌سازی و سرعت محاسبات، آستانه‌گیری تصویر نقش مهمی در بخش‌بندی تصویر دارد. در این بخش، تکنیک‌هایی را براساس مقادیر شدت روشنایی و یا خواص این مقادیر، برای تقسیم‌بندی مستقیم تصاویر به چند ناحیه بحث می‌شود.
فرض کنید هیستوگرام شدت روشنایی متناظر با تصویر (f(x,y شامل اشیای روشن روی پس‌زمینه سیاه است، به‌طوری که پیکسل‌های شی و پس زمینه دارای مقادیر شدت روشنایی هستند که به دو دسته‌ی غالب تقسیم می‌شوند [۳]. یک روش بدیهی برای استخراج اشیا از پس‌زمینه، انتخاب آستانه T است.
هر پیکسل (x,y) در تصویر که T<(f(x,y است، قسمتی از شی است وگرنه، آن پیکسل قسمتی از پس‌زمینه است. به‌عبارت دیگر، تصویر بخش‌بندی شده (g (x,y به‌صورت زیر مشخص می‌شود:
(۱-۱ )
اگر T ثابتی باشد که روی کل تصویر قابل اعمال باشد، فرایند موجود در این معادله را آستانه‌گیری سراسری می‌نامند. اگر مقدار T روی تصویر تغییر ‌کند، از واژه آستانه‌گیری متغیر استفاده می‌شود. واژه آستانه‌گیری محلی یا ناحیه‌ای نیز گاهی آستانه‌گیری متغیر را مشخص می‌کند که در آن، مقدار T در هر نقطه (x,y) در یک تصویر، به خواص همسایه (x,y) بستگی دارد. اگر T به خود مختصات مکانی بستگی داشته باشد، آنگاه آستانه‌گیری متغیر را آستانه‌گیری پویا یا تطبیقی می‌نامند.
۱-۲-۳-۱-آستانه‌گیری سراسری بهینه با بهره گرفتن از روش آتسو^[۸]
آستانه‌گیری را می‌توان مسئله تئوری تصمیم آماری دانست که هدف آن کمینه کردن میانگین خطای ناشی از تخصیص پیکسل‌ها به دو یا چند گروه است. این مسئله راه‌حل بسته‌ای به‌نام قانون تصمیم بیز^[۹] دارد این راه‌حل مبتنی بر دو پارامتراست، تابع چگالی احتمال^[۱۰] مربوط به سطوح شدت روشنایی هر گروه و احتمالی که هر گروه می‌تواند رخ دهد. متاسفانه تخمین تابع چگالی احتمال کار ساده‌ای نیست، لذا این مسئله با انجام فرض‌هایی راجع به تابع چگالی احتمال ساده‌ترشده است ( مثل این فرض که آنها توابع گوسی‌اند).
روش بحث‌شده در این بخش، که روش آتسو نام دارد جایگزین جالبی است [۲]. این روش، از این نظر بهینه است که واریانس بین گروه را ماکزیمم می‌کند، که معیار معروفی در تحلیل دقیق آماری است. ایده اصلی این است که گروه‌هایی با آستانه‌گیری خوب، از نظر مقادیر شدت روشنایی پیکسل‌های آنها مجزا باشند، و برعکس، آستانه‌ای که بهترین جدایی را بین گروه‌ها براساس مقادیر شدت روشنایی آنها ارائه می‌کند، بهترین آستانه (آستانه بهینه) خواهد‌بود. علاوه بر بهینگی آن، روش آتسو دارای این خاصیت مهم است که کاملاً مبتنی بر محاسباتی است که روی هیستوگرام تصویر اجرا شده و به‌آسانی از آرایه یک بعدی به‌دست می‌آید.
۱-۲-۴-بخش‌بندی مبتنی برناحیه
هدف بخش‌بندی تقسیم کردن تصویر به ناحیه‌ها است. در این بخش، تکنیک‌های بخش‌بندی مبتنی بریافتن مستقیم ناحیه‌ها بحث می‌شود.
۱-۲-۴-۱-رشد ناحیه
رشد دادن رویه‌ای است که پیکسل‌ها یا زیرناحیه‌ها را براساس معیار از پیش تعریف شده برای رشد، به ناحیه‌های بزرگ‌تر گروه‌بندی می‌کند [۲]. روش اصلی، با مجموعه‌ای از نقاط شروع و ناحیه‌های رشد توسط افزودن پیکسل‌هایی از آن همسایگی به هر نقطه که خواص از پیش تعریف شده‌ی مشابه با آن نقطه را دارند ایجاد می‌شوند (مثل بازه‌های خاصی از شدت روشنایی یا رنگ).
انتخاب مجموعه‌ای از یک یا چند نقطه شروع، اغلب می‌تواند براساس ماهیت مسئله باشد. وقتی اطلاعات قبلی وجود ندارد، باید مجموعه یکسانی از خواص در هر نقطه محاسبه شود که این خواص برای اختصاص پیکسل‌ها به ناحیه‌ها در حین فرایند رشد به‌کار می‌روند. نتیجه‌ی این محاسبات، خوشه‌هایی از مقادیر هستند.
انتخاب معیار شباهت نه‌ تنها به مسئله مورد نظر، بلکه به نوع داده‌های موجود در تصویر نیز بستگی دارد. به‌عنوان مثال، تحلیل تصویر ماهواره برای استفاده در زمین، بستگی زیادی به استفاده از رنگ دارد. حل این مسئله بدون اطلاعات موجود در تصاویر رنگی، بسیار دشوار یا غیرممکن خواهد‌بود. وقتی تصاویر تک‌رنگ باشند، تحلیل ناحیه باید با مجموعه‌ای از توصیف‌گرها براساس سطوح شدت روشنایی و خواص مکانی (مثل گشتاورها) انجام شود.
مسئله دیگر در رشد ناحیه فرمول‌بندی قانون توقف است. وقتی دیگر پیکسلی برای قرارگرفتن درناحیه‌ای نباشند، رشد ناحیه باید متوقف شود. استفاده از مفهوم اندازه، شباهت بین پیکسل کاندید و پیکسل‌هایی که تاکنون رشد کرده‌اند (مثل مقایسه شدت روشنایی پیکسل کاندید و میانگین شدت روشنایی ناحیه رشد یافته) معیار دیگری است که به قدرت الگوریتم رشد ناحیه می‌افزاید.
۱-۲-۴-۲-بخش‌بندی با بهره گرفتن از الگوریتم آب‌پخشان^[۱۱]
بخش‌بندی توسط آب‌پخشان، بسیاری از مفاهیم سایر روش‌ها را در‌بر می‌گیرد و بخش‌بندی پایدار‌تری را تولید می‌کند [۲]. مفهوم آب‌پخشان، مبتنی بر مجسم کردن تصویر در سه بعد است، دو مختصات مکانی در مقابل شدت روشنایی. در یک تفسیر توپوگرافی سه نوع نقطه را درنظر می‌گیریم (الف) نقاط متعلق به مینیمم ناحیه‌ای (ب) نقاطی که در آنها قطره‌ای از آب، اگر در مکانی از هر یک از نقاط گذاشته شود به یک مینیمم می‌افتد (پ) نقاطی که در آنها آب با احتمال یکسان به بیش از یک چنین مینیممی می‌ریزد. برای یک مینیمم ناحیه‌ای خاص، مجموعه‌ای از نقاط برآورده کننده شرط (ب) آبگیر آبریز یا آب‌پخشان آن مینیمم نام دارد. نقاط برآورد‌کننده شرط (پ) خطوط راس را روی سطح توپوگرافی تشکیل می‌دهند و خطوط تقسیم یا خطوط آب‌پخشان نام‌گذاری می‌شوند.
شکل(۱-۱) تفسیر توپوگرافی a )نقاط متعلق به مینیمم ناحیه‌ای( b(نقاط روی تپه( c (نقاط روی آب‌پخشان) [۲]
هدف اصلی الگوریتم‌های بخش‌بندی مبتنی بر این مفاهیم، یافتن خطوط آب‌پخشان است. ایده‌ی اصلی ساده است. فرض کنید سوراخی در هر مینیمم ناحیه‌ای ایجاد شده است و کل توپوگرافی از زیر جریان می‌باید و اجازه می‌دهد که آب از طریق سوراخ با نرخ یک‌نواختی به طرف بالا بیاید. وقتی آب بالارونده در آب‌گیرریز نزدیک به ادغام شدن است سدی ساخته می‌شود تا از ادغام جلوگیری شود. سرانجام وقتی جریان سیل به مرحله‌ای می‌رسد که فقط بالای سد‌ها در بالای خطوط آب قابل مشاهده باشد، مرزهای سد، متناظر با خطوط تقسیم آب‌پخشان است. لذا آنها مرزهای (متصل) استخراج شده توسط الگوریتم آب‌پخشان هستند.
این ایده‌ها را می‌توان به‌کمک شکل (۱-۲) بیشتر توصیف کرد. شکل (۱-۲) (الف) یک تصویر خاکستری را نشان می‌دهد و شکل (۱-۲) (ب) نمای توپوگرافی است که درآن ارتفاع کوه‌ها متناسب با مقادیر شدت روشنایی در تصویر ورودی است.
الف
ب
شکل(۱-۲) الف)تصویر اصلی ب)نمای توپوگرافی [۲]
توپولوژی کلی نمایش سه بعدی مورد نظر برای جلوگیری از ریزش آب از لبه‌های تصویر است، فرض می‌کنیم محیط کل تصویر توپولوژی توسط سد‌هایی با ارتفاع بیش از بلندترین کوه ممکن احاطه شده است که مقدار آن توسط بیشترین مقدار شدت روشنایی ممکن در تصویر ورودی تعیین می‌شود.
فرض کنید سوراخی در هر مینیمم ناحیه‌ای (که با ناحیه‌های سیاه درشکل (۱-۲) (ب) نشان داده شده است) ایجاد شده و کل توپوگرافی از زیر جاری شده‌است، به‌طوری که اجازه داده شده آب با نرخ یک‌نواختی از طریق سوراخ‌ها بالا بیاید.

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