من قبلا یک کد ansi c از الگوریتم MSER را به c++ تبدیل کرده بودم .کلیت عملکردش به صورت زیر هستش :
محاسبه هیستوگرام
محاسبه توزیع تجمعی هیستوگرام
مرتب سازی پیکسل ها با توزیع تجمعی :
برای مرتب سازی پیکسل ها استفاده کنیم که به آن bucketsort هم اطلاق میشه. تصویر را برحسب شدت نور به صورت صعودی مرتب می کنیم نقاطی که دارای شدت نور یکسان هستند به ترتیب از بالا به پایین و چپ به راست مرتب می شوند که از طریق آن آرایه اولویت متناظر با تصویر ساخته می شود. در این روش پیکسل ها به صورت یک بعدی از انتهای تصویر پردازش می شوند در هر مرحله با توجه به مقدار هر پیکسل به ستون تجمعی مورد نظر رفته و از مقدار آن ستون یک واحد کم کرده و مقدار بدست آمده را در آرایه اولویت در نقطه متناظر قرار می دهیم.
ایجاد و اتصال نواحی :
در هر مرحله به ازای هر پیکسل از idx متناظر در آرایه اولویت استفاده می کنیم.
کلیه پیکسل های تصویر را پردازش می کنیم:
در هر مرحله :
به ازای هر idx یک ناحیه اضافه می کنیم مساحت و عمق آن را یک قرار می دهیم . همچنین parent و shortcut آن را idx قرار میدیم.
-
بررسی تمامی نقاط همسایه :
هر پیکسل 8 همسایه داره .
شرایط همسایگی :
-
مختصات آنها داخل تصویر باشد.
-
از قبل ناحیه ای برای آنها ایجاد شده باشد
شرایط ترکیب نواحی :
تابع climb جهت محاسبه idx ریشه هر ناحیه مورد استفاده قرار می گیره که در ادامه به توضیح آن خواهیم پرداخت.
ریشه ناحیه جاری و ریشه ناحیه همسایه را با climb محاسبه می کنیم .
اگر idx ریشه ها نابرابر باشند آنگاه می توانیم عملیات ترکیب ریشه ها را انجام بدیم.
اگر idx ریشه همسایه با idx ناحیه جاری یکسان باشه و مقدار جاری از مقدار ریشه همسایه کمتر باشه آنگاه ریشه ناحیه جاری، فرزند ریشه همسایه میشه اگر هم شرط بالا برقرار نباشه ریشه همسایه ،فرزند ریشه ناحیه جاری میشه.
در عملیات ترکیب ، ناحیه ای ریشه ی که فرزند میشه، idx ناحیه ریشه مقابل را به عنوان parent و shortcut خود درنظر می گیرد.
مساحت فرزند به والد اضافه میشه
محاسبه عمق جدید والد به صورت زیر است :
ماکزیمم مقدار بین عمق فرزند یک واحد بیشتر و عمق والد
شمارنده ای به نام njoins داریم که از صفر شروع میشه. که به ازای هر عمیلات ترکیب یک واحد به آن اضافه میشه .
آرایه ای به نام joins داریم که idx فرزندان را در خود نگهداری می کنه .idx مورد نظر را در موقعیت njoins قرار می دهیم.
تابع climb :
برای بدست آوردن idx ریشه یک ناحیه از این تابع استفاده می کنیم .
این تابع از 2 بخش تشکیل شده است:
-
از طریق shortcut ناحیه به صورت متوالی به سمت بالا می رویم ه تا به ریشه برسیم.
در هر مرحله پس از استفاده از shortcut مقدار جدید آن را با ناحیه قبلی(پایینی) مقداردهی می کنیم.
-
shortcut را به حالت اولیه آن بر می گردانیم.
ایجاد نواحی extermal :
تا اینجا نواحی بدست آمدند در این مرحله قصد داریم نواحی extermal را ایجاد کنیم.
کلیه نواحی را پردازش می کنیم اگر ناحیه شرایط extermal داشته باشد یک ناحیه جدید به آرایه نواحی extermal اضافه می کنیم .
اتصال ناحیه به ناحیه extermal :
برای اتصال شاخص ناحیه extermal را در shortcut ناحیه قرار می دهیم.
اگر هم ناحیه ای دارای ناحیه extermal نباشد shortcut آن را void قرار می دهیم.
مقدار دهی ناحیه extermal:
index آن را idx ناحیه قرار می دهیم.
shortcut آن شاخص مربوط به ناحیه extermal قرار می دهیم.
از مقدار پیکسل و مساحت ناحیه ، برای ناحیه extermal استفاده می کنیم.
اتصال نواحی extermal به صورت درخت :
کلیه نواحی extermal موجود را پردازش می کنیم در هر مرحله :