الگوریتم رشد ناحیه ای

Region Growing

 

مقدمه :

این مقاله در مورد الگوریتم رشد ناحیه ای به کمک الگوریتم ژنتیک هست، تقسیم بندی تصویر فرایند دادن برچسب به هر پیکسل در یک تصویر است به گونه ای که پیکسل ها با همان برچسب دارای برخی از ویژگی های بصری مانند رنگ ، شدت یا بافت هستند. خروجی تقسیم بندی تصویر مجموعه ای از بخش هایی است که به طور کلی کل تصویر، یا مجموعه ای از کانتورهای استخراج شده از تصویر را پوشش می دهد. هنگامی که بر روی یک مجموعه از تصاویر اعمال می شود ، می توان از خطوط خروجی پس از تقسیم تصویر برای ایجاد بازسازی های سه بعدی استفاده کرد. به طور عمده دو رویکرد برای تقسیم وجود دارد: تقسیم بندی لبه و تقسیم منطقه .در این مرحله صحت مراحل بعدی تحت تأثیر قرار می گیرد و از این رو مهمترین و دشوارترین گام است ، زیرا اشکال ، اندازه ها و رنگ های ضایعه به همراه انواع و بافت های مختلف پوست وجود دارد. برخی ضایعات نیز مرزهای نامتقارن دارند و بعضی اوقات بین ضایعه و پوست تغییر صافی وجود دارد.

 

رویکرد تفکیک مبتنی بر ژنتیک :

الگوریتم ژنتیکی یک کلاس از الگوریتم های بهینه سازی تصادفی تطبیقی ​​است که شامل فرایند جستجو و بهینه سازی است. مشکلات بهینه سازی را می توان به عنوان یک عمل ، فرآیند یا روش شناسی برای ساختن چیزی مانند یک طرح ، سیستم یا تصمیم تعریف کرد. تا حد امکان کامل ، کاربردی یا مؤثر است. الگوریتم های ژنتیکی یکی از بهترین راه حل ها است که شناخت کمی برای آن وجود دارد. آنها یک الگوریتم بسیار کلی هستند و از این رو در هر فضای جستجو به خوبی کار می کنند. الگوریتم های ژنتیکی از اصول انتخاب و تکامل برای تولید چندین راه حل برای یک مشکل معین استفاده می کنند. دلایل مختلفی برای انتخاب تناسب مبتنی بر الگوریتم ژنتیک در مقایسه با روشهای سنتی وجود دارد. آنها به وجود مشتقات توابع هدف و محدودیت احتیاج دارند و همچنین به عملکردهای عینی و محدودیتی که از نظر ریاضی به خوبی تعریف شده اند نیاز دارند. دست زدن به متغیرهای مختلط یک روش بسیار خسته کننده در روش های سنتی است.

 

الگوریتم ژنتیک :

جریان الگوریتم ژنتیک به شرح زیر توضیح داده شده است. تصویر RGB ابتدا به تصویر خاکستری تبدیل می شود. عملگرهای تصادفی مختلف مانند انتخاب ، تقطیع و جهش برای اجرای الگوریتم ژنتیک استفاده می شوند. در ابتدا جمعيت اوليه ، مقادير تناسب مورد ارزيابي قرار مي گيرد و سپس از مكانيسم هايی بنام تقطیع و جهش براي توليد و از اين رو آستانه بهينه استفاده مي شود. پروسه انتخاب برای اشخاص بهتر اعمال می شود. برای معیارهای توقف ، حداکثر تعداد نسل ها آغاز می شوند. وقتی نسل به پایان رسید ، نسبت اشخاص را محاسبه می کند. از این رو ، سه مرحله قابل توجه شامل الگوریتم های ژنتیکی هستند:

  • تعریف عملکرد هدف
  • تعریف و اجرای بازنمایی ژنتیکی
  • تعریف و اجرای عملگرهای ژنتیکی

 

پروسه انتخاب آستانه :

Otsu یا تابع نسبت از سطح خاکستری برای جدا سازی شی از پس زمینه استفاده می کند. Otsu به دنبال یک راه حل بهینه است.

 T آستانه بزرگتر شدن Otsu است. Otsu توسط فرمول های زیر آورده شده است:

 

الگوریتم رشد ناحیه ای

 

که در آن  p0 p1 احتمال اهداف و g1 g2 به طور متوسط خاکستری هدف و پس زمینه هستند.

 

رشد منطقه :

رشد منطقه روشی برای جمع آوری پیکسل ها در تصویر تحت مشاهده است. این روش همچنین می تواند به عنوان روشی مبتنی بر خوشه بندی پیکسل های همسایه یک منطقه تعریف شود که فرضیات یا شرایط خاص را تأیید می کند. هدف نهایی ما این است که یک گروه پیکسل را fmd کرده و آنها را به عنوان دانه در نظر بگیریم ، و سپس از شباهت پیکسل ها برای اضافه کردن پیوند به دانه استفاده کنیم. آستانه ای در حالت اولیه انتخاب می شود تا لبه ها را بدون در نظر گرفتن نویز در تصویر فراهم کند. رشد منطقه را می توان به شرح زیر خلاصه کرد :

  • اولیه سازی یک منطقه Reo با یک یا چند پیکسل
  • گروه بندی مجدد کلیه پیکسل های همسایه که یک فرض یا شرایط خاص را تأیید می کنند
  • تکرار تا رسیدن به همگرایی ادامه دارد.

رشد منطقه دارای خواص زیر است :

  • ترتیب دانه های اولیه بر کیفیت خروجی تأثیر می گذارد
  • ترتیب خوشه بندی پیکسل بر خروجی تأثیر می گذارد
  • روش رشد منطقه نسبتاً ساده است و الگوریتم نسبتاً سریع است.

الگوریتم ژنتیک یکی از دو آستانه تعیین شده را برای تکمیل فرآیند تولید دانه انتخاب می کند. آستانه بالاتر برای تصاویری استفاده می شود که در آن اکثر مقادیر بطور باریک پخش می شوند در حالی که آستانه پایین برای تصاویری استفاده می شود که قسمت کوچکی از مقادیر بطور گسترده پخش می شود. تمام مناطق با سطح کم به عنوان دانه های اولیه بدست می آیند.

 

 

 

ادغام کردن منطقه :

روش ادغام منطقه یک روش تقسیم بندی سلسله مراتبی از پایین به بالا است. برای تشخیص مرز در تصاویر پوستی استفاده می شود. این مبتنی بر تصمیمات محلی بر روی ویژگی های ناحیه ای است. با شروع از یک پارتیشن اولیه یا از گروه بندی پیکسل ها ، مناطق به طور تکراری با هم ادغام می شوند تا رسیدن به یک معیار توقف. از این رو ، الگوریتم های ادغام منطقه با یک معیار ادغام مشخص می شوند و هزینه ادغام دو منطقه را تعیین می کنند. نظم ادغام ، یافتن نظمی که مناطق براساس معیار ادغام ترکیب می شوند. و یک الگوی منطقه ای که نحوه توصیف اتحادیه مناطق را تعیین می کند. عملیات ادغام منطقه با ادغام نواحی مجاور متعلق به همان شیء ، مرزهای نادرست و مناطق فریبنده را حذف می کند. ادغام با یک پارتیشن انجام می شود که شرایط زیر را برآورده می کند:

 

الگوریتم رشد ناحیه ای

 

آنها اطمینان حاصل می کنند که بر اساس شرایط زیر ادغام کردن تصویر مناطق ناحیه ای بطور آهسته انجام میشود.

 

الگوریتم رشد ناحیه ای

 

مراحل اساسی برای تقسیم از طریق ادغام منطقه به شرح زیر است :

  • تشکیل مناطق اولیه در تصویر
  • ساخت یک نمودار مجاور مناطق
  • ساخت یک نمودار مجاور مناطق
  • برای هر منطقه ، منطقه مجاور آن را یادداشت کنید و بررسی کنید که آیا آنها مشابه هستند یا خیر. اگر شبیه به هم باشند ، آنها را ادغام کنید و نمودار مجاورت منطقه اصلاح شود.
  • مرحله فوق را مجدداً تکرار کنید تا هیچ یک از مناطق با هم ادغام نشوند

دو نکته زیر در ادغام منطقه ذکر شده است

  • در یک تکرار معین ، هر منطقه مورد توجه قرار می گیرد و دامنه سطح خاکستری آن توسط یک واحد یا پایین تر توسط یک واحد افزایش می یابد. انتخاب هر دو گزینه مشاهده شده است که هنگام ادغام با همسایگان ، بازده همگن تری می دهد
  • اگر منطقه B بتواند با منطقه A (منطقه اصلی) ادغام شود ، سپس همسایگان منطقه B نیز آزمایش و تأیید می شوند تا بررسی کنند که آیا آنها در محدوده منطقه اصلی A قرار دارند یا خیر.

 

 

 

رشد منطقه و افزودن دانه پویا :

کیفیت تکنیک های رشد منطقه بسیار وابسته به مکان هایی است که برای آغاز مراحل رشد به آن انتخاب شده است. ما یک فرایند متناوب را برای رشد منطقه پیشنهاد می کنیم که منحصراً به تعیین اولیه خوشه ها برای تقسیم بندی نهایی بستگی ندارد. این روش در مناطقی جستجو می کند که نقشه شیب هیچ لبه ای را نشان نمی دهد. مناطق انتخاب شده مجموعه اولیه دانه ها را برای تقسیم بندی تصویر تشکیل می دهند. روند رشد منطقه همچنین با شناسایی مناطق غیر قابل دسترسی در سطوح مختلف چگالی لبه ، مناطقی را نشان می دهد که مقادیر لبه ای مشابه را در سراسر خود نشان می دهند. شکل زیر فلوچارت این ماژول را نشان می دهد و در ادامه توضیحی مفصل آورده شده است

تولید آستانه سازگار : الگوریتم GSEG با تبدیل فضای رنگی تصویر ورودی از RGB به CIE آغاز می شود. این مرحله از اهمیت حیاتی برخوردار است ، زیرا حالت دوم الگوی بهتری برای درک بصری انسان است ، با توجیه این واقعیت که با توجه به دو رنگ ، اختلاف مقادیر عددی بین آنها متناسب با تفاوت درک شده است که توسط چشم انسان مشاهده می شود، یک ویژگی است که نمی تواند با فضای RGB همراه باشد. با استفاده از داده های به دست آمده ، میزان شیب میدان تصویر رنگ محاسبه می شود. تاریخچه این نقشه شیب برای تعیین سطوح اضافی دانه مورد استفاده برای افزودن دانه پویا استفاده می شود.

در ابتدا ، هدف انتخاب آستانه شروع فرایند تولید دانه است. در حالت ایده آل ، می توان مقدار آستانه را برای ارائه بیشترین لبه ها انتخاب کرد ، در حالی که نویز موجود در تصاویر را نادیده می گیرد. مسئله این است که ماهیت تصاویر اجازه این وضع را نمی دهد.

یک آستانه واحد که ممکن است مرز یک منطقه مشخص را به درستی مشخص کند ، ممکن است به سایر مناطق اجازه ندهد ادغام نادرست داشته باشند. با توجه به این عامل ، ما می خواهیم یکی از دو مقادیر آستانه تجربی تعیین شده برای شروع فرآیند تولید دانه را انتخاب کنید ، با تأیید اعتبار اینکه محتوای شیب کم و زیاد در تصویر تا چه حد از هم فاصله دارد ، در هیستوگرام مربوطه آن است. ایده اصلی این است که از آستانه اولیه بالا برای تصاویری استفاده شود که در آن درصد زیادی از مقادیر شیب در یک محدوده باریک پخش شود و مقدار آستانه اولیه پایین برای تصاویری استفاده شود که در آن درصد زیادی از مقادیر شیب در طیف گسترده ای پخش شود.

از منظر اجرای عملی ، این تصمیم را گرفتیم که آستانه اولیه را با بدست آوردن نسبت درصد مقادیر شیب منطبق با 80٪ و 100٪ مساحت تحت منحنی هیستوگرام انتخاب کنیم. اگر مساحت 80٪ زیر منحنی هیستوگرام با یک مقدار شیب کمتر از 10٪ حداکثر مقدار شیب در تصویر ورودی باشد ، یک مقدار آستانه بالا انتخاب می شود ، در غیر این صورت مقدار آستانه اولیه پایین انتخاب می شود. با در نظر گرفتن مشکلات ناشی از تقسیم بندی بیش از حد و کمتر ، مقادیر آستانه کم و زیاد به ترتیب از نظر تجربی 5 و 10 انتخاب شدند. مورد قبلی با تصاویری مطابقت داشت که زمینه و پیش زمینه ، جزئیات شیب عمدتاً قابل تشخیص از یکدیگر ندارند. مورد دوم با تصاویر متشکل از یک پس زمینه به آرامی متفاوت با جزئیات شیب کمتر ، که از محتوای برجسته پیش زمینه متمایز است ، مطابقت داشت.

پس از به دست آوردن، تمام مناطق قابل توجه مسطح و مناطق همجوار آن در فواصل آستانه و با معیارهای اندازه متنوع تولید می شوند تا نقشه دانه اولیه را تشکیل دهند.

 

الگوریتم رشد ناحیه ای

 

هنگامی که آستانه شروع فرایند تقسیم بندی مشخص شد ، ما برای محاسبه فواصل آستانه برای بخش اضافه دانه پویا از روش رشد منطقه استفاده می کنیم. تولید دانه پویا نیاز به مجموعه ای از فواصل آستانه دارد که در آن دانه های اضافی به دانه های اولیه اضافه می شوند. مقادیر آستانه انتخاب شده برای افزودن بذرهای جدید با استفاده از مساحت زیر هیستوگرام شیب که در محدوده شیب دانه های اولیه قرار نمی گیرد ، به صورت انطباقی تعیین می شوند. آستانه اول برای افزودن بذر پویا (T1) با اضافه کردن 10٪ مساحت هیستوگرام بیشتر از حداکثر مقدار شیب دانه های اولیه ، به ناحیه تجمعی شناسایی شده و به دست آوردن مقدار شیب مربوط تعیین می شود. این فرآیند برای هر مرحله جدید از روش اضافه کردن بذر پویا ادامه دارد که در آن 10٪ افزایش سطح هیستوگرام بیشتر از حداکثر مقدار شیب مرحله قبلی مربوط به آن به ناحیه تصویر تجمعی تشخیص داده شده در انتهای آن مرحله قبلی اضافه می شود. تولید مقادیر آستانه به این ترتیب همیشه تضمین می کند که: 1) آنها تنظیم شده اند که برای از بین رفتن مقادیر شیب به حساب می آیند. 2) مناطق با اندازه قابل توجه در هر بازه به نقشه تقسیم بندی اضافه می شوند. 3) آنها در طول هیستوگرام قرار می گیرند و از احتمال راندمان محاسباتی از بین نمیروند.

تولید بذر اولیه : همانطور که قبلاً نیز گفته شد ، بذرهای اولیه با شناسایی تمام نواحی در تصویر ایجاد می شوند که مقدار شیب آن زیر آستانه های اولیه قرار می گیرد ، و اگر هیچ منطقه ای تحت این آستانه وجود نداشته باشد ، تا زمانی که مناطق شناسایی نشوند ، مقدار لبه افزایش می یابد. نسل اولیه بذر برای انتخاب بذر اولیه از الزامات اندازه خاص استفاده می کند تا از تولید چند بذر در مناطق همگن و متصل جلوگیری کند. شرط اول اجرا این است که هنگام جستجوی مناطقی که مقدار آستانه پایین تر از آنها باشد ، بذرها بزرگتر از 0.5٪ از تصویر شوند دلیل این قانون این است که غالباً زمینه ها حاوی حاشیه های غلط تولید شده توسط نور یا سایر عوامل متفاوت در این محدوده شیب هستند. شرط دوم اجرای بذرها برای اندازه گیری بیشتر از 0.25٪ از تصویر در محدوده است ، زیرا در این محدوده تغییرات ممکن است به اندازه کافی مهم باشد تا این مناطق متفاوت باشد. یکبار برای تمایز اهداف پیکسل های تشکیل دهنده هر بذر یک برچسب منحصر به فرد دریافت میکنند ، مجموعه ترکیبی از دانه های برچسب زده شده به عنوان دانه های والدین (PS) شناخته می شود.

  • رمزگذاری طول اجرا تصویر ورودی. 2) قوانین را اسکن کرده و برچسب های اولیه را در جدول معادل محلی اختصاص دهید. 3) کلاس های هم ارزی را حل کنید. 4) کارها را بر اساس کلاس معادل حل کنید.

 

 

رشد منطقه :

در بین هر مرحله ، بذرهای والدین موجود با افزایش آستانه به طور همزمان ، از 20 تا 21 رشد می کنند. پس از هر مرحله ، شناسایی مناطق جدید یا بذر کودک که در زیر آستانه جدید قرار دارند ، رخ می دهد ، همانطور که در شکل زیر مشاهده می شود. این دانه های کودک را باید به دانه های مجاور موجود یا غیر طبقه بندی کرد. دانه های غیرجذاب دور ریخته می شوند ، زیرا ، فقط در آغاز هر مرحله آستانه تطبیقی می توان اضافه کرد. به منظور کارایی روند رشد منطقه ، شناختن بذر والدین که کودک در مجاورت آن است ، بسیار مهم است. هدف این است که بتوانیم تمام دانه های کودک مجاور را با رویکرد بردار پردازش کنیم. برای دستیابی به این کار ، ابتدا سعی می کنیم لبه های بیرونی نقشه را با استفاده از فیلتر مکانی غیرخطی تشخیص دهیم. این فیلتر بر روی پیکسل های یک  3 در 3  کار می کند و خروجی آن به پیکسل مرکزی اختصاص می یابد. این فیلتر در زیر آورده شده است.

 

 

نتیجه استفاده از این فیلتر ماسکی است که حاشیه های نقشه را نشان می دهد. دانه های کودک شناسایی شده و برچسب زده شده بذر کودک را تشکیل می دهند. گرفتن تمام پیکسل های موجود در نقشه بذر کودک که با این برچسب ها مطابقت دارد ، نقشه بذر کودک مجاور را مطابق شکل زیر ایجاد می کند. برای افزودن مناسب دانه های کودک مجاور ، لازم است تفاوت های رنگ فردی آنها را با والدین خود مقایسه کنید تا از یک تقسیم همگن اطمینان کنید برای مقایسه همه دانه های مجاور تولید شده از نظر محاسباتی گران خواهد بود. در عوض تمام دانه هایی که اندازه آنها کوچکتر است ، مستقیماً با دانه والدین مجاور ادغام می شوند. اندازه بذر کودک با استفاده از تکنیک های ذخیره سازی ماتریس پراکنده محاسبه می شود تا امکان ایجاد ماتریس های بزرگ با هزینه کم حافظه فراهم شود. ماتریس های پراکنده فقط عناصر غیر صفر یک ماتریس را به همراه مکان آنها در ماتریس پراکنده ذخیره می کنند. برای ادغام مناطق ، ارتباط بین دانه های کودک و والدین آنها لازم است. یک جدول دو ستونی ، اولین ستون که توسط برچسب های بذر بچه ها اشغال شده است و دوم ، توسط برچسب های والدین مربوطه کودک ، این انجمن را فراهم می کند. تعداد ردیف های این جدول برابر با تعداد پیکسل های کودک مجاور خواهد بود ستون اول از مقادیر غیر صفر کشف شده پس از انجام ضرب عنصر به عنصر دانه های کودک و ماسک مرزی بذر والدین جمع می شود.

 

 

والدین مربوطه هر کودک در ستون اول با استفاده از یک روش دو مرحله ای تشخیص داده می شوند. ابتدا ، یک فیلتر ، که حداکثر مقدار 3 در  3را به هر مکان پیکسلی ، که بر روی نقشه اعمال می شود ، بازگرداند ، تا مرزهای هر بذر والدین را گسترش می دهد. مرحله دوم استفاده از مکانهای پیکسل کودک مجاور به عنوان ماسک روی نقشه گسترده PS برای استخراج برچسب والدین در هر مکان کودک است. همانطور که در شکل زیر میبینید. توجه به این نکته ضروری است که فیلترهای غیرخطی اطلاعاتی را در مورد بذرها ارائه می دهند ، اما برای دستکاری مستقیم تصویر لازم نیست. بنابراین ، نتیجه نهایی هیچ اثر تغییر شکل را نشان نمی دهد.

 

 

نتایج و بحث :

براي تشخيص از روش هاي تقسيم بندي رشد منطقه و ادغام منطقه استفاده شده و شبيه سازي شده است. ارزیابی براساس معیارهای عملکرد است. خروجی ها با استفاده از تصویر زمین آزمایش و تأیید شدند و از این رو کارآیی الگوریتم پیشنهادی بررسی می شود.

تصویر ملانوما بدخیم از پایگاه داده انتخاب می شود. در خروجی تقسیم شده ، مناطق سفید منطقه آلوده و منطقه سیاه را مشخص می کنند و یا لکه ها منطقه غیر آلوده ضایعه را مشخص می کنند. در حالی که در تصویر زمین ، مناطق سفید منطقه آلوده به ضایعه و منطقه سیاه یا نقاط مشخص منطقه غیر آلوده را مشخص می کنند.

 

بخش بندی تصویر با استفاده از رشد ناحیه ای

 

بخش بندی نهایی تصویر با استفاده از ادغام ناحیه ای

 

تصویر Ground Truth

 

رویکرد تقسیم بندی بر اساس ژنتیک پیشنهادی ، یک قطعه تقسیم بندی را ایجاد می کند که نزدیک به تصویر زمین در شکل سوم است. خروجی تقسیم بندی با تصویر زمین و پارامترهای مختلف یعنی ضریب تشابه ، همپوشانی مکانی و خطای مثبت و منفی مقایسه و بررسی وسپس ارزیابی می شوند.

ضریب تشابه با ارزش 0.998 به وضوح نزدیک بودن خروجی تقسیم شده با تصویر حقیقت زمین را نشان می دهد. در بین بهترین خطای مثبت و منفی غلط حاصل از روش تقسیم بندی ژنتیکی ، خطای مثبت غلط بدترین نوع خطای بدست آمده است. از این رو رویکرد تقسیم بندی مبتنی بر ژنتیک مناسب ترین و قابل توجه ترین معیار از نظر بالینی است.

 

نتیجه گیری :

ترکیب الگوریتم های ژنتیک و رشد منطقه از بروز مشکلات ناشی از استفاده از یک روش واحد جلوگیری می کند. مزایای استفاده از الگوریتم ژنتیک شامل سریع بودن با عملیات باینری ساده و طرح جستجوی موازی است. روند رشد منطقه از لبه هدف اشتباه خلاص می شود و هدف را کامل و دقیق تر می کند. روش ادغام منطقه به ریشه کن کردن مشکل وجود مناطق زیادی در بخش های مختلف کمک می کند.

 

لطفا از مطلب ما در مورد بینایی ماشین نیز دیدن فرمایید.

 

نویسنده: مهندس محمد طالبی

 

 

 

منابع و مراجع :

 

  1. Lei Zhang, David Zhang (2011), “Automatic Image

Segmentation by Dynamic Region Merging”, IEEE

Transactions, image process, volume 18, No.10.

 

  1. IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 18, NO. 10, OCTOBER 2009

“Automatic Image Segmentation by Dynamic Region Growth and Multiresolution Merging”

 

  1. Ganster, P. Pinz, R.Rohnen, E.Wilding and H.

Kittler(2001), “Automated Melanoma Recognition”,

IEEE Transactions, Medical Imaging. Volume 20,

pages 233-239.

 

  1. Shih F Y, Cheng Shouxian (2005), “Automatic Seeded

Region Growing for Color Image Segmentation”,

Image and Vision Computing, volume 23, No.10, pages

877-886