Computer Vision

Image segmentation with Watershed algorithm

Xin chào, bài viết này sẽ giới thiệu về thuật toán Watershed dùng cho bài toán Image Segmentation, qua đó áp dụng để tìm Contour của các vật thể đơn giản nằm chồng chéo lên nhau.


WATERSHED ALGORITHM

Thuật toán Watershed cho phép người dùng đánh dấu những vùng hình ảnh chứa object, background và cả những vùng không chắc chắn. Sau khi thuật toán kết thúc, những vùng không chắc chắn sẽ được gắn nhãn foreground hoặc background, các đường ranh giới giữa các vùng cũng sẽ được phát hiện.

Đầu tiên, thuật toán Watershed xem bức ảnh chứa “Gradient of the Intensity” như là một tấm bản đồ địa hình, trong đó các vùng sáng là các ngọn núi, còn các vùng tối là các thung lũng, hình 1.

Hình 1 – Địa hình khi chưa bị ngập nước

Giả sử có một trận mưa cực lớn xuất hiện, ban đầu nước sẽ nhấn chìm toàn bộ các thung lũng, sau đó mực nước tăng dần để nhấn chìm từng ngọn núi, lúc này nước ở trong các thung lũng sẽ gặp nhau, vị trí mà chúng gặp nhau chính là watershed và đó cũng chính là ranh giới giữa các vùng mà chúng ta cần phân tách, hình 2, 3, 4. Nước lũ ở từng thung lũng được tô màu khác nhau để dễ hình dung.

Hình 2 – Bắt đầu cho ngập các thung lũng
Hình 3 – Vị trí của Watershed
Hình 4 – Xây dựng bức tường ngăn cách tại vị trí Watershed

Nếu những vùng bị nhấn chìm cùng nhau đã được đánh dấu cùng là foreground hoặc cùng là background từ trước thì chúng sẽ được kết nối với nhau. Ngược lại thì tại vị trí watershed, chúng ta cần xây dựng một bức tường để ngăn cản nước từ hai vùng khác biệt (foreground và background) hòa trộn với nhau, hình 5.

Hình 5 – Toàn bộ địa hình bị nhấn chìm

Sau khi toàn bộ địa hình đã bị nhấn chìm, chúng ta sẽ nhận được các vùng foreground, background và đường ranh giới giữa chúng.


WATERSHED IN OPENCV 3

OpenCV cung cấp function watershed để thực hiện Image Segmentation.

cv2.watershed(inputImage, markers)

Trong đó:
+ inputImage – ảnh input 8-bit, 3 channels;
+ markers – ảnh grayscale 32-bit có kích thước của input image chứa các markers của các vùng ảnh foreground, background và “unknown zone” (marker = 0).

Để dễ dàng nắm bắt cách sử dụng function cv2.watershed, chúng ta sẽ bắt đầu với ví dụ dưới đây.

Input image:

Hình 1 – coins.jpg

Tìm contour theo cách bình thường:

import cv2

image = cv2.imread("coins.jpg")

blur = cv2.GaussianBlur(image, (5,5), 0)
gray = cv2.cvtColor(blur, cv2.COLOR_BGR2GRAY)

thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY | cv2.THRESH_OTSU)[1]

cnts = cv2.findContours(thresh.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)[1]
cv2.drawContours(image, cnts, -1, (0, 255, 0), 2)
cv2.imshow("image", image)
cv2.waitKey(0)
Hình 2 – contour tìm được theo cách bình thường

Tìm contour với Watershed và Distance Transformation:

import numpy as np
import cv2
import imutils

image = cv2.imread("coins.jpg")

blur = cv2.GaussianBlur(image, (5,5), 0)

gray = cv2.cvtColor(blur, cv2.COLOR_BGR2GRAY)

cv2.imshow("Gray", gray)
thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY | cv2.THRESH_OTSU)[1]
thresh = cv2.dilate(thresh, None, iterations=3)
thresh = cv2.erode(thresh, None, iterations=3)
cv2.imshow("Thresh", thresh)

background = cv2.dilate(thresh, None, iterations=3)

distMap = cv2.distanceTransform(thresh, cv2.DIST_L2, 5)
cv2.normalize(distMap, distMap, 0.0, 255.0, cv2.NORM_MINMAX)
distMap = np.uint8(distMap)
cv2.imshow("distMap", distMap)
foreground = cv2.threshold(distMap, 100, 255, cv2.THRESH_BINARY)[1]
foreground = cv2.erode(foreground, None, 2)
cv2.imshow("foreground", foreground)

unknownZones = cv2.subtract(background, foreground)

ret, markers = cv2.connectedComponents(foreground, connectivity=8, ltype=cv2.CV_32S)
markers = markers + 1
markers[unknownZones == 255] = 0

markers = cv2.watershed(image, markers)

cnts = []

for m in np.unique(markers):
	if m < 2:
		continue

	mask = np.zeros(markers.shape, dtype="uint8")
	mask[markers == m] = 255

	c = cv2.findContours(mask, 
						cv2.RETR_EXTERNAL,
						cv2.CHAIN_APPROX_SIMPLE)[1]

	cnts.extend(c)

for (i, c) in enumerate(cnts):
	((x, y), r) = cv2.minEnclosingCircle(c)
	cv2.putText(image, "#{}".format(i + 1), (int(x) - 10, int(y)),
		cv2.FONT_HERSHEY_SIMPLEX, 0.6, (0, 0, 255), 2)
	cv2.drawContours(image, [c], -1, (0, 255, 0), 2)

cv2.imshow("Output", image)
cv2.waitKey(0)

Giải thích:
+ Dòng 13, 14: vì cần thực hiện Distance Transformation nên chúng ta cần loại bỏ các “blob” có trong thresholded image bằng cách áp dụng Closing Operator;
undefined
+ Dòng 17: áp dụng dilate để tách ra vùng chắc chắn là background của bức ảnh;
+ Dòng 19: thực hiện Distance Transformation, kết quả trả về là một bức ảnh 32-bit chứa khoảng cách của mỗi pixel đến pixel zero gần nó nhất;
undefined
+ Dòng 23, 24: áp dụng thresholding và erode để tách ra vùng foreground của bức ảnh từ distance map;
undefined
+ Dòng 27: vùng “unknown zone” được tách ra bằng cách trừ vùng foreground khỏi vùng background, vì đây là vùng chồng lấn giữa các vật thể nên ta gọi nó là “unknown zone”;
undefined
+ Dòng 29: tìm connected components (blob) của vùng foreground;
+ Dòng 30, 31: những vùng “unknown zones” sẽ được đánh dấu là 0, các phần foreground/background được đánh dấu bởi các số dương;
+ Dòng 33: áp dụng function watershed.

Kết quả:

Hình 3 – contour tìm được với thuật toán Watershed

Thêm 1 bức ảnh ví dụ:

Hình 4 – coins-2.jpg

Contours:


KẾT LUẬN

Như vậy chúng ta đã tìm hiểu về thuạt toán Watershed và function cv2.watershed mà OpenCV cung cấp để tìm contour của các vật thể đơn giản nằm sát nhau. Mặc dù kết quả nhận được đúng như mong đợi nhưng cần nhớ rằng, Watershed chỉ có thể áp dụng cho các vật thể đơn giản, đối với các trường hợp phức tạp hơn thì sân khấu là của Deep Learning.

Hình 5 – Deep Learning Image Segmentation

Cảm ơn các bạn đã theo dõi bài viết.
Thân ái và quyết thắng.


Reference:
[1] Watershed OpenCV.
[2] Watershed (image processing).
[3] Image Segmentation with Watershed Algorithm.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s