این مطلب برای حل تمرین Lableing Connected Component خیلی کارساز است!
یکی از دوستان خوبمان لطف کردند و یافته ی خود را در خصوص حل تمرینی که باید از الگوریتم Connected Component Labeling برای آن استفاده کرد
کامنت گذاشتند و خواستند که دیگر دوستان از آن مطلع باشند.
به نوبه ی خودم از ایشان متشکرم
همچنین مراجعه به این لینک نیز می تواند مفید باشد
++++++++++++++
برچسب زنی اجزای متصل
یکی از مهمترین مراحل در بخش بندی تصویر جداسازی اشیاء مختلف برروی تصویر به صورت تصاویر مجزا از هریک است. به عنوان مثال تصویر زیر شامل 16 شی مجزا است که هریک از این اشیا را یک جز متصل می گوییم.
روش های مختلفی برای این منظور وجود دارد، در این مقاله ما به بررسی سه روش زیر خواهیم پرداخت :
· برچسب زنی به روش تکراری
· برچسب زنی به روش بازگشتی
· برچسب زنی به روش پیمایش سطحی
· برچسب زنی به روش پیمایش عمقی
از میان روش های فوق برچسب زنی به روش عمقی ایده آل ترین روش برچسب زنی است، هر دو پارامتر یک الگوریتم کارآمد را با خود دارد. بدین معنی که الگوریتم برچسب زنی اجزای متصل به روش عمقی هم سریع بوده و هم از حافظه بسیار کمی برای این منظور استفاده می کند.
برچسب زنی به روش سطحی نیز از نظر سرعت اجرا با سرعت اجرای برچسب زنی عمقی تقریبا برابر است، پیچیدگی مکانی (فضای حافظه مورد نیاز) آن دو نیز بر حسب اینکه شی پهنای بیشتری داشته باشد یا از عمق بیشتری برخوردار باشد نسبت به هم دیگر متفاوت است. برچسب زنی بازگشتی و تکراری نسبت به دو روش دیگر از کارآیی پایین تری برخوردارند و مطرح کردن آن ها در اینجا صرفا جهت آشنایی خوانندگان با این روش ها است.
توجه:
در همه روش های فوق برچسب زنی اجزای متصل را بر روی تصویر دو سطحی انجام می دهیم. همچنین در همه این روش ها تصویر را از بالا به پایین و از چپ به راست پیمایش می کنیم.
برچسب زنی اجزای متصل به روش تکراری
برچسب زنی به روش تکراری یک روش دو مرحله ای است که در مرحله اول با پیمایش تصویر از بالا به پایین و از چپ به راست به هر پیکسل شی ای، بر اساس شرایط زیر برچسبی را انتساب می دهیم:
1. در همسایگی 4 گانه پیکسل p(i,j) ، اگر پیکسل بالایی p(i-1,j) و پیکسل سمت چپی p(i,j-1) دارای برچسب X باشند، پیکسل p(i,j) نیز برچسب X خواهد داشت
2. در همسایگی 4 گانه پیکسل p(i,j) ، اگر پیکسل بالایی p(i-1,j) یا پیکسل سمت چپی p(i,j-1) دارای برچسب X باشند، پیکسل p(i,j) نیز برچسب X خواهد داشت
3. در همسایگی 4 گانه پیکسل p(i,j) ، اگر پیکسل بالایی p(i-1,j) برچسب X و پیکسل سمت چپی p(i,j-1) دارای برچسب Y باشند ( X و Y باهم برابر نیستند)، برچسب پیکسل p(i,j) را برابر X قرار داده و در جدول معادل ها X و Y را وارد می کنیم
4. در همسایگی 4 گانه پیکسل p(i,j) ، اگر پیکسل بالایی p(i-1,j) و پیکسل سمت چپی p(i,j-1) هیچیک دارای برچسب نباشند ، به پیکسل p(i,j) برچسب جدیدی برابر Z قرار می دهیم.
هنگام انتساب برچسب به پیکسل ها معمولا از مقادیر عددی استفاده می کنیم. جدول معادل ها نیز شامل همه برچسب های معادل هم خواهد بود. در مرحله دوم برچسب های معادل با هم ادغام شده و برچسب منحصربفردی را برای هریک از اشیا تولید می کند. اگر X و Y دو برچسب معادل از جدول معادل ها باشند، زمانی که X<Y باشد همه برچسب های Y را برابر X قرار می دهیم و در نتیجه به هریک از اجزای متصل برچسب منحصربفردی منتسب می شود.
برچسب زنی اجزای متصل به روش بازگشتی
در برچسب زنی به روش بازگشتی همگام با پیمایش تصویر از بالا به پایین و از چپ به راست ، با رسیدن به یک پیکسل شی ای، با استفاده از یک الگوریتم بازگشتی هریک از همسایه های 8-گانه این پیکسل که نشان دهنده یک پیکسل شی ای باشند را تا رسیدن به یک پیکسل زمینه به طور جداگانه پیمایش می کنیم.
یکی از بزرگترین عیب های این روش وابستگی به ماشین این روش است. همانطور که می دانید هنگام فراخوانی های بازگشتی یک تابع، اطلاعات تابع در پشته ذخیره می شود. اندازه پشته نیز در هر ماشین متفاوت می باشد. از این رو در صورتی که اندازه شی بر روی تصویر بزرگ باشد، ممکن است به علت فراخوانی ها زیاد تابع بازگشتی، سرریزی در پشته روی دهد. در همین حال ممکن است همین شی بر روی ماشین دیگر بدون بروز خطای سرریزی پشته اجرا شود. همچنین فراخوانی بازگشتی تابع باعث کاهش سرعت اجرای الگوریتم می شود.
و....
+++++++++++
