分水嶺算法

感覺網(wǎng)上的文字介紹寫的都太抽象了，自己根據(jù)維基百科和英文論文記一下自己原理方面的具體理解。

非常抽象的原理理解

參考鏈接：meduim上的一篇文章
大部分文章都用這段來進行抽象地比喻和解釋的
這段大意就是different valleys start to merge的位置修建barrier叮盘，就是分割線。

In any grayscale images, there are areas where the intensity is high and there are some where intensity is low. We can denote these high intensity areas to peaks while low intensity areas to valleys. Think of an image as a topography map, where each pixel’s intensity contributes to the topography map, either a local elevation or a depression. To separate objects in images, we will fill out each valley with water of different colors. Slowly, the water will rise up and to a point water from different valleys start to merge. This is when we build barriers on top of the peak to avoid having the peak underwater. Once the barriers are built out, the barriers constitutes the boundary of the object.

改進：基于標記的分水嶺算法

傳統(tǒng)分水嶺方法（在grayscale image上去找極小值，然后開始擴張）的不足：基于圖像梯度的分水嶺算法由于存在太多極小區(qū)域而產(chǎn)生許多小的集水盆地霉咨， 帶來的結(jié)果就是圖像過分割。
所以必須對分割相似的結(jié)果進行合并拍屑。 舉個例子如一個桌面的圖片途戒，由于光照、紋理等因素僵驰，桌面會有很多明暗變化喷斋，反映在梯度圖上就是一個個圈， 此時利用分水嶺算法就會出現(xiàn)很多小盆地蒜茴，從而分割出很多小區(qū)域星爪。但這顯而易見是不符合常識的。 因為桌面是一個整體矮男，應該屬于同一類移必，而不是因為紋理而分成不同的部分。

因此需要對分水嶺算法進行改進毡鉴。在OpenCV中采用的是基于標記的分水嶺算法崔泵。 水淹過程從預先定義好的標記圖像（像素）開始秒赤， 這樣可以減少很多極小值點盆地產(chǎn)生的影響。 較好的克服了過度分割的不足憎瘸。 本質(zhì)上講入篮，基于標記點的改進算法是利用先驗知識來幫助分割的一種方法。

圖示如下：

對比圖

舉例：opencv中基于標注的分水嶺算法

經(jīng)典的一個硬幣分割的例子幌甘，涉及到前景的標記marker

1. Otsu’s binarization二值化
2. 開閉運算：（容易理解的）

Erosion（腐蝕）：確保白色的部分都是foreground（sure foreground area）
另一種確定前景的方法是距離變換加上合適的閾值潮售。
代碼如下：

Dilation（膨脹）：確保黑色的部分都是background（sure background area）
剩下的不確定是前景還是背景的部分就需要watershed algorithm來解決。
Note1:
提取肯定是硬幣的區(qū)域(前景)锅风，可以使用腐蝕操作酥诽。腐蝕操作可以去除邊緣像素，剩下就可以肯定是硬幣了皱埠。 當硬幣之間沒有接觸時肮帐，這種操作是有效的。但是由于硬幣之間是相互接觸的边器， 我們就有了另外一個更好的選擇：距離變換再加上合適的閾值训枢。（代碼如下）
Note2:
注意對圖像可以取補集，因為這樣可以確保背景比前景暗（這樣看上去舒服一些）忘巧。

#這里的open就是二值化去噪后的圖像
distance_transform = cv2.distanceTransform(open, 1, 5)
ret, sure_fg = cv2.threshold(distance_transform, 0.7 * distance_transform.max(), 255, cv2.THRESH_BINARY)
>These areas are normally around the boundaries of coins where foreground and background meet (Or even two different coins meet). We call it border. 
*It can be obtained from subtracting sure_fg area from sure_bg area.*

圖像提取

watershed前的標記工作：

# Marker labelling 標記sure的前景
ret, markers = cv2.connectedComponents(sure_fg)

# Add one to all labels so that sure background is not 0, but 1 標記sure的背景
markers = markers+1

# Now, mark the region of unknown with zero 標記為止的部分
markers[unknown==255] = 0

watershed前的準備

3. 應用分水嶺算法找到分界線并把邊界加在原圖上

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

下面聊一聊具體算法實現(xiàn)吧恒界。
不錯的參考鏈接
沒有用到什么數(shù)學知識，就是根據(jù)上面的抽象理解來寫代碼：valley部分的連通區(qū)域的擴張砚嘴。

MATLAB二值化圖像的分水嶺算法

參考鏈接
在MATLAB里十酣，需要用到bwdist這個函數(shù)來求 the distance transform of the complement of the binary image。即valley中每個點（標記pixel value為0）到其對應最近的非零點的距離枣宫。（我的理解：這一步的作用是把二值圖像灰度化婆誓，這樣就有梯度了，有谷底也颤，從谷底開始擴張漲水位洋幻。）

distance transform的結(jié)果

不錯的實現(xiàn)代碼：
MATLAB分水嶺實現(xiàn)代碼