بخش‌بندی تصویر با الگوریتم Watershed

هدف#

در این فصل،

• یاد می‌گیریم که چگونه از بخش‌بندی تصویر مبتنی بر نشانگر (marker-based image segmentation) با استفاده از الگوریتم watershed استفاده کنیم.
• تابع زیر را خواهیم دید: cv.watershed()

تئوری#

هر تصویر خاکستری می‌تواند به عنوان یک سطح توپوگرافیک در نظر گرفته شود که در آن شدت روشنایی بالا نشان‌دهنده قله‌ها و تپه‌ها و شدت روشنایی پایین نشان‌دهنده دره‌ها است. شما شروع به پر کردن هر دره جداگانه (مینیمم‌های محلی) با آب‌های رنگی مختلف (برچسب‌ها) می‌کنید. با بالا آمدن آب، بسته به قله‌های (گرادیان‌های) نزدیک، آب‌های دره‌های مختلف با رنگ‌های متفاوت شروع به ترکیب شدن می‌کنند. برای جلوگیری از این اتفاق، در مکان‌هایی که آب‌ها با هم ترکیب می‌شوند دیوار می‌سازید. این کار پر کردن آب و ساخت دیوار را تا زمانی ادامه می‌دهید که همه قله‌ها زیر آب باشند. سپس دیوارهایی که ساختید نتیجه بخش‌بندی را به شما می‌دهند. این «فلسفه» پشت الگوریتم watershed است. می‌توانید از صفحه CMM درباره watershed برای درک آن با کمک انیمیشن‌هایی بازدید کنید.

اما این رویکرد به دلیل نویز یا سایر بی‌نظمی‌های موجود در تصویر، نتیجه‌ای با بخش‌بندی بیش از حد (oversegmented) به شما می‌دهد. بنابراین OpenCV یک الگوریتم watershed مبتنی بر نشانگر (marker-based) پیاده‌سازی کرده است که در آن مشخص می‌کنید کدام نقاط دره‌ها باید ادغام شوند و کدام‌ها نباید. این یک بخش‌بندی تعاملی (interactive) تصویر است. کاری که انجام می‌دهیم این است که برچسب‌های مختلفی به اشیایی که می‌شناسیم می‌دهیم. ناحیه‌ای که مطمئن هستیم پیش‌زمینه یا شیء است را با یک رنگ (یا شدت روشنایی) برچسب‌گذاری می‌کنیم، ناحیه‌ای که مطمئن هستیم پس‌زمینه یا غیر شیء است را با رنگ دیگری، و در نهایت ناحیه‌ای که از آن مطمئن نیستیم را با ۰ برچسب می‌زنیم. این نشانگر (marker) ما است. سپس الگوریتم watershed را اعمال می‌کنیم. آنگاه نشانگر ما با برچسب‌هایی که دادیم به‌روزرسانی می‌شود، و مرزهای اشیاء مقدار ۱- خواهند داشت.

کد#

در زیر مثالی می‌بینیم که چگونه از تبدیل فاصله (Distance Transform) همراه با watershed برای بخش‌بندی اشیایی که به هم لمس می‌کنند استفاده می‌شود.

تصویر سکه‌های زیر را در نظر بگیرید، سکه‌ها با یکدیگر در تماسند. حتی اگر آستانه‌گذاری هم انجام دهید، باز هم با یکدیگر تماس خواهند داشت.

ما با یافتن یک تخمین تقریبی از سکه‌ها شروع می‌کنیم. برای این کار، می‌توانیم از دودویی‌سازی Otsu استفاده کنیم.

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt

img = cv.imread('coins.png')
assert img is not None, "file could not be read, check with os.path.exists()"
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
ret, thresh = cv.threshold(gray,0,255,cv.THRESH_BINARY_INV+cv.THRESH_OTSU)

نتیجه:

حال باید هر نویز سفید کوچکی در تصویر را حذف کنیم. برای این کار می‌توانیم از عملیات ریخت‌شناسی باز کردن (morphological opening) استفاده کنیم. برای حذف هر حفره کوچکی در داخل شیء، می‌توانیم از عملیات ریخت‌شناسی بستن (morphological closing) استفاده کنیم. بنابراین اکنون مطمئن می‌دانیم که ناحیه نزدیک به مرکز اشیاء پیش‌زمینه و ناحیه دور از شیء پس‌زمینه است. تنها ناحیه‌ای که از آن مطمئن نیستیم ناحیه مرزی سکه‌ها است.

پس باید ناحیه‌ای را که مطمئن هستیم سکه هستند استخراج کنیم. فرسایش (Erosion) پیکسل‌های مرزی را حذف می‌کند. بنابراین هر چه باقی بماند مطمئن هستیم سکه است. این در صورتی کار می‌کند که اشیاء به هم لمس نکنند. اما از آنجا که با هم در تماسند، گزینه خوب دیگری این است که تبدیل فاصله (distance transform) را پیدا کنیم و یک آستانه مناسب اعمال کنیم. سپس باید ناحیه‌ای را پیدا کنیم که مطمئن هستیم سکه نیستند. برای این کار، نتیجه را گسترش (dilate) می‌دهیم. گسترش مرز شیء را به سمت پس‌زمینه افزایش می‌دهد. به این ترتیب، می‌توانیم مطمئن باشیم هر ناحیه‌ای که در نتیجه پس‌زمینه است واقعاً پس‌زمینه است، چرا که ناحیه مرزی حذف شده است. تصویر زیر را ببینید.

مناطق باقیمانده مناطقی هستند که هیچ ایده‌ای درباره آن‌ها نداریم، یعنی نمی‌دانیم سکه هستند یا پس‌زمینه. الگوریتم watershed باید آن‌ها را پیدا کند. این نواحی معمولاً اطراف مرزهای سکه‌ها هستند، جایی که پیش‌زمینه و پس‌زمینه با هم ملاقات می‌کنند (یا حتی دو سکه مختلف به هم می‌رسند). ما آن را مرز (border) می‌نامیم. می‌توان آن را با تفریق ناحیه sure_fg از ناحیه sure_bg به دست آورد.

# noise removal
kernel = np.ones((3,3),np.uint8)
opening = cv.morphologyEx(thresh,cv.MORPH_OPEN,kernel, iterations = 2)

# sure background area
sure_bg = cv.dilate(opening,kernel,iterations=3)

# Finding sure foreground area
dist_transform = cv.distanceTransform(opening,cv.DIST_L2,5)
ret, sure_fg = cv.threshold(dist_transform,0.7*dist_transform.max(),255,0)

# Finding unknown region
sure_fg = np.uint8(sure_fg)
unknown = cv.subtract(sure_bg,sure_fg)

نتیجه را ببینید. در تصویر آستانه‌گذاری‌شده، برخی مناطق سکه‌ها را که از آن‌ها مطمئن هستیم به دست می‌آوریم و اکنون از هم جدا شده‌اند. (در برخی موارد، شاید فقط به بخش‌بندی پیش‌زمینه علاقه‌مند باشید و نه به جداسازی اشیاء در تماس با هم. در آن صورت، نیازی به استفاده از تبدیل فاصله ندارید، فقط فرسایش کافی است. فرسایش فقط روش دیگری برای استخراج ناحیه مطمئن پیش‌زمینه است.)

حال مطمئن می‌دانیم کدام مناطق سکه‌ها هستند، کدام پس‌زمینه است و غیره. بنابراین نشانگر (marker) ایجاد می‌کنیم (آرایه‌ای با همان اندازه تصویر اصلی، اما با نوع داده int32) و مناطق داخل آن را برچسب‌گذاری می‌کنیم. مناطقی که از آن‌ها مطمئن هستیم (چه پیش‌زمینه چه پس‌زمینه) با اعداد صحیح مثبت اما متفاوت برچسب می‌زنیم، و مناطقی که از آن‌ها مطمئن نیستیم فقط صفر می‌مانند. برای این کار از cv.connectedComponents() استفاده می‌کنیم. این تابع پس‌زمینه تصویر را با ۰ و سایر اشیاء را با اعداد صحیح از ۱ به بالا برچسب می‌زند.

اما می‌دانیم اگر پس‌زمینه با ۰ علامت‌گذاری شود، الگوریتم watershed آن را به عنوان ناحیه ناشناخته در نظر خواهد گرفت. پس می‌خواهیم آن را با عدد صحیح متفاوتی علامت‌گذاری کنیم. در عوض، ناحیه ناشناخته را که با متغیر unknown تعریف شده، با ۰ علامت می‌زنیم.

# Marker labelling
ret, markers = cv.connectedComponents(sure_fg)

# Add one to all labels so that sure background is not 0, but 1
markers = markers+1

# Now, mark the region of unknown with zero
markers[unknown==255] = 0

نتیجه نمایش داده‌شده در نقشه رنگی JET را ببینید. ناحیه آبی تیره ناحیه ناشناخته را نشان می‌دهد. سکه‌های مطمئن با مقادیر مختلف رنگ‌آمیزی شده‌اند. ناحیه باقیمانده که مطمئناً پس‌زمینه است با آبی روشن‌تر نسبت به ناحیه ناشناخته نمایش داده می‌شود.

حالا نشانگر ما آماده است. زمان مرحله نهایی است، اعمال watershed. سپس تصویر نشانگر تغییر خواهد کرد. ناحیه مرزی با ۱- علامت‌گذاری می‌شود.

markers = cv.watershed(img,markers)
img[markers == -1] = [255,0,0]

نتیجه زیر را ببینید. برای برخی سکه‌ها، ناحیه‌ای که با هم لمس می‌کنند به درستی بخش‌بندی شده و برای برخی دیگر نه.

منابع اضافی#

1. صفحه CMM درباره تبدیل Watershed

تمرین‌ها#

1. نمونه‌های OpenCV شامل یک نمونه تعاملی برای بخش‌بندی watershed به نام watershed.py است. آن را اجرا کنید، از آن لذت ببرید، سپس آن را یاد بگیرید.