傳統算法——分水嶺算法

分水嶺算法是一種基于區域分割的算法。它是基于地理形態的分析的圖像分割算法,模仿地理結構(比如山川、溝壑,盆地)來實現對不同物體的分類。

圖像的灰度空間很像地球表面的整個地理結構,每個像素的灰度值代表高度。其中的灰度值較大的像素連成的線可以看做山脊,也就是分水嶺。其中的水就是用于二值化的gray threshold level,二值化閾值可以理解為水平面,比水平面低的區域會被淹沒,剛開始用水填充每個孤立的山谷(局部最小值)。當水平面上升到一定高度時,水就會溢出當前山谷,可以通過在分水嶺上修大壩,從而避免兩個山谷的水匯集,這樣圖像就被分成2個像素集,一個是被水淹沒的山谷像素集,一個是分水嶺線像素集。最終這些大壩形成的線就對整個圖像進行了分區,實現對圖像的分割。在該算法中,空間上相鄰并且灰度值相近的像素被劃分為一個區域。

分水嶺算法的運行過程:

1. 把梯度圖像中的所有像素按照灰度值進行分類,并設定一個測地距離閾值。
   
2. 找到灰度值最小的像素點(默認標記為灰度值最低點),讓threshold從最小值開始增長,這些點為起始點。
   
3. 水平面在增長的過程中,會碰到周圍的鄰域像素,測量這些像素到起始點(灰度值最低點)的測地距離,如果小于設定閾值,則將這些像素淹沒,否則在這些像素上設置大壩,這樣就對這些鄰域像素進行了分類。
4. 隨著水平面越來越高,會設置更多更高的大壩,直到灰度值的最大值,所有區域都在分水嶺線上相遇,這些大壩就對整個圖像像素的進行了分區。

用上面的算法對圖像進行分水嶺運算,由于噪聲點或其它因素的干擾,可能會得到密密麻麻的小區域,即圖像被分得太細(over-segmented,過度分割),這因為圖像中有非常多的局部極小值點,每個點都會自成一個小區域。

其中的解決方法:

1. 對圖像進行高斯平滑操作,抹除很多小的最小值,這些小分區就會合并。
2. 不從最小值開始增長,可以將相對較高的灰度值像素作為起始點(需要用戶手動標記),從標記處開始進行淹沒,則很多小區域都會被合并為一個區域,這被稱為基于圖像標記(mark)的分水嶺算法。

下面三個圖分別是原圖,分水嶺過分割的圖以及基于標記的分水嶺算法得到的圖:

其中標記的每個點就相當于分水嶺中的注水點,從這些點開始注水使得水平面上升,但是如上圖所示,圖像中需要分割的區域太多了,手動標記太麻煩,我們可是使用距離轉換的方法進行標記,OpenCV中就是使用的這種方法。

OpenCV中分水嶺算法

在OpenCV中,我們需要給不同區域貼上不同的標簽。用大于1的整數表示我們確定為前景或對象的區域,用1表示我們確定為背景或非對象的區域,最后用0表示我們無法確定的區域。然后應用分水嶺算法,我們的標記圖像將被更新,更新后的標記圖像的邊界像素值為-1。

下面對相互接觸的硬幣應用距離變換和分水嶺分割。

圖6

先使用 Otsu's 二值化對圖像進行二值化。

import cv2import numpy as npimg = cv2.imread('coins.png')gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)ret, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)

圖7

先使用開運算去除圖像中的細小白色噪點,然后通過腐蝕運算移除邊界像素,得到的圖像中的白色區域肯定是真實前景,即靠近硬幣中心的區域(下面左邊的圖);膨脹運算使得一部分背景成為了物體到的邊界,得到的圖像中的黑色區域肯定是真實背景,即遠離硬幣的區域(下面中間的圖)。

剩下的區域(硬幣的邊界附近)還不能確定是前景還是背景?？赏ㄟ^膨脹圖減去腐蝕圖得到,下圖中的白色部分為不確定區域(下面右邊的圖)。

# noise removalkernel = cv2.getStructuringElement(cv2.MORPH_RECT, (3,3))opening = cv2.morphologyEx(thresh, cv2.MORPH_OPEN, kernel, iterations=2)sure_bg = cv2.dilate(opening, kernel, iterations=2)  # sure background areasure_fg = cv2.erode(opening, kernel, iterations=2)  # sure foreground areaunknown = cv2.subtract(sure_bg, sure_fg)  # unknown area

圖8

剩下的區域不確定是硬幣還是背景,這些區域通常在前景和背景接觸的區域(或者兩個不同硬幣接觸的區域),我們稱之為邊界。通過分水嶺算法應該能找到確定的邊界。

由于硬幣之間彼此接觸,我們使用另一個確定前景的方法,就是帶閾值的距離變換。

下面左邊的圖為得到的距離轉換圖像,其中每個像素的值為其到最近的背景像素(灰度值為0)的距離,可以看到硬幣的中心像素值最大(中心離背景像素最遠)。對其進行二值處理就得到了分離的前景圖(下面中間的圖),白色區域肯定是硬幣區域,而且還相互分離,下面右邊的圖為之前的膨脹圖減去中間這個表示前景的圖。

# Perform the distance transform algorithmdist_transform = cv2.distanceTransform(opening, cv2.DIST_L2, 5)# Normalize the distance image for range = {0.0, 1.0}cv2.normalize(dist_transform, dist_transform, 0, 1.0, cv2.NORM_MINMAX)# Finding sure foreground arearet, sure_fg = cv2.threshold(dist_transform, 0.5*dist_transform.max(), 255, 0)# Finding unknown regionsure_fg = np.uint8(sure_fg)unknown = cv2.subtract(sure_bg,sure_fg)

圖9

現在我們可以確定哪些是硬幣區域,哪些是背景區域。然后創建標記(marker,它是一個與原始圖像大小相同的矩陣,int32數據類型),表示其中的每個區域。分水嶺算法將標記的0的區域視為不確定區域,將標記為1的區域視為背景區域,將標記大于1的正整數表示我們想得到的前景。

我們可以使用 cv2.connectedComponents() 來實現這個功能,它是用0標記圖像的背景,用大于0的整數標記其他對象。所以我們需要對其進行加一,用1來標記圖像的背景。

cv2.connectedComponents() 將傳入圖像中的白色區域視為組件(前景)。

# Marker labellingret, markers = cv2.connectedComponents(sure_fg)# Add one to all labels so that sure background is not 0, but 1markers = markers+1# Now, mark the region of unknown with zeromarkers[unknown==255] = 0

注意:得到的markers矩陣的元素類型為 int32,要使用 imshow() 進行顯示,需要將其轉換為 uint8 類型( markers=np.uint8(markers) )。

我們對得到的markers進行顯示:

markers_copy = markers.copy()markers_copy[markers==0] = 150  # 灰色表示背景markers_copy[markers==1] = 0    # 黑色表示背景markers_copy[markers>1] = 255   # 白色表示前景markers_copy = np.uint8(markers_copy)

圖10

標記圖像已經完成了,最后應用分水嶺算法。然后標記圖像將被修改,邊界區域將被標記為-1。

# 使用分水嶺算法執行基于標記的圖像分割,將圖像中的對象與背景分離markers = cv2.watershed(img, markers)img[markers==-1] = [0,0,255]  # 將邊界標記為紅色

經過分水嶺算法得到的新的標記圖像和分割后的圖像如下圖所示:

圖11

任何兩個相鄰連接的組件不一定被分水嶺邊界(-1的像素)分開;例如在傳遞給 watershed 函數的初始標記圖像中的物體相互接觸。

總結

我們通過一個例子介紹了分水嶺算法的整個過程,主要分為以下幾步:

1. 對圖進行灰度化和二值化得到二值圖像
2. 通過膨脹得到確定的背景區域,通過距離轉換得到確定的前景區域,剩余部分為不確定區域
3. 對確定的前景圖像進行連接組件處理,得到標記圖像
4. 根據標記圖像對原圖像應用分水嶺算法,更新標記圖像

參考鏈接https://zhuanlan.zhihu.com/p/67741538