基于區域分離與聚合的分水嶺分割*

王 祥 羅素云

（上海工程技術大學機械與汽車工程學院 上海 201620）

1 引言

圖像分割是按照某種設定的規則，將一幅待處理圖像劃分成為若干互不相交的、有明顯邊緣區分的局部區域過程，同時這也是圖像處理研究領域的重要分析方法。分水嶺變換則是基于數學形態學的一種圖像分割算子，可將待處理圖像分割成若干不重合的區域，它與傳統依據邊界梯度的圖像分割技術（如Canny 算子和Laplace 算子）相比，分水嶺算法能夠獲得像素寬的、連續的邊界，但是它也存在著分割速度慢和過分割等問題。目前已提出了各種在分水嶺變換基礎上進行改進的圖像分割方式，文獻［1］提出一種邊緣走向自適應的多尺度分水嶺遙感圖像分割算法，采用多尺度標記算法進行標記分水嶺分割；文獻［2］提出一種先求形態梯度圖像的浮點活動圖像，再進行分水嶺變換的圖像分割方法；文獻［3］提出了一種基于粒子群和區域生長的改進分水嶺算法；文獻［4］提出了一種根據梯度圖像的多尺度信息，構造相似性函數的改進的快速分水嶺變換算法；文獻［5］提出了一種改進的基于標記提取的分水嶺算法，改進后的算法由平滑濾波、彩色梯度計算、標記提取和分水嶺變換組成；文獻［6］提出了一種先進行分水嶺變換再用Normalized Cut 方法在區域之間進行分割，產生最終所分割的圖像；文獻［7］提出一種自適應梯度重建分水嶺分割算法，該方法首先利用PCA技術對彩色圖像降維，然后計算降維后的梯度圖像并采用自適應重建算法修正梯度圖像，對修正梯度圖像采用分水嶺變換完成對彩色待處理圖像的合理分割；文獻［8］提出在Normalized Cut 方法基礎上利用合并-分裂方式，合并顏色紋理相似區域，并對部分區域繼續做Normalized Cut分割；文獻［9］提出將RGB彩色圖像轉化至新的彩色空間，并利用形態學開閉重構，標記后將梯度圖像分水嶺變換進行分割；文獻［10］提出多尺度形態濾波器對輸入噪聲圖像及濾波后的梯度圖像進行平滑處理，實現消除噪聲和優化待處理圖像，然后快速區域合并算法優化分割。為了抑制分水嶺變換的過分割問題，本文提出了一種先進行拉普拉斯濾波和區域分離與聚合再進行分水嶺變換的圖像分割方法。理論分析和實驗結果證明了該方法的可行性。

2 預處理濾波

待分割原始灰度圖像在分水嶺變換之前，可以先利用二維線性空間濾波器，通過fspecial函數，選擇一個合適的濾波模板w，本文選擇一個大小為3×3 的拉普拉斯濾波器算子，該算子定義為?2f(x，y)：

在x方向上，有：

在y方向上，有：

所以，依據上述公式可推算兩個變量的拉普拉斯算子為

使用拉普拉斯微分算子進行圖像增強的基本公式為

式（5）中的c當模板w 中心系數為正時取1，否則取-1。

本文通過拉普拉斯濾波預處理，可以將待分割圖像區域邊界進行銳化增強，作為最簡單的各向同性微分算子，此過程具有旋轉不變性，同時盡可能地保留原始灰度圖像的灰度層次，較為適合本文圖像分割過程。

3 區域分離與聚合

令R 表示整幅圖像區域，可將分割視為把R 分為n個子區域R1，R2，··· ，Rn的處理，即：

條件1）表示分割必須完全；條件2）表示區域點必須連續；條件3）表示各個區域必須互不相交；條件4）表示區域內像素點屬性相同；條件5）表示不同區域內屬性不同。

選擇一種屬性P，對R 進行分割處理的一種規則是逐次細分成四個象限區域，測試對于局部區域Ri有P（Ri）=TRUE。從整個區域開始，如果P（R）=TRUE，我們把圖像分為四象限區域。若對于每個象限區域P 為FALSE，則將該象限區域再細分為四個子象限區域，以此類推。這種特殊的分離技術可以形象地表示為四叉樹的形式，即每個節點都正好有四個后代，如圖1 所示（對應一個四叉樹的節點的圖像有時稱為四分區域或四分圖像）。其中，樹根可以代表待處理圖像，而其后每個節點可對應于四個后支節點。在這種情況下，僅進一步細分了R4。

圖1 四叉樹模型示意圖

如果只采用分離的方式處理，只會得到具有相同屬性的相鄰區域。然而通過聚合與分離的改進方式，可以克服這個弊端。前提是滿足上述提出分割約束條件1）～5），則僅要求聚合其組合像素滿足屬性P 的相鄰區域。也就是說，兩個相鄰的區域Ri和 Rj僅當P(Ri∪Rj)=TRUE時才能聚合。

上述過程可以總結如下：

1）將滿足條件的P（R）i=FALSE 的任何區域Ri分離為四個不相交的象限區域。

2）當不能進一步分離時，聚合滿足條件P(Ri∪Rj)=TRUE的任意兩個相鄰區域Ri和Rj。

3）當不能進一步聚合分區域時，停止分離與聚合操作。

算法終止條件是規定不能再執行分裂的最小四象限區尺寸。

4 分水嶺變換

分水嶺可以形象成為山脊，通過山脊的不同方向的水系來形成集水盆地。集水盆地在地理上是指把水排入河流或水庫的區域。分水嶺變換則是類比于這些概念，推廣到灰度圖像處理過程中，以期解決圖像分割問題。

圖2 分水嶺示意圖

理解分水嶺變換時要求把灰度圖像視為一個拓撲表面，表面中f（x，y）的值被理解為高度。例如，圖2（a）中的簡單圖像形象化為圖2（b）中的三維表面。假設雨水流淌在該表面區域，就會流入到兩個積水盆地中心，而正好處在脊線上的雨水會等概率地流向兩側。分水嶺變換則是需要找到灰度圖像的積水區域和脊線，在進行圖像分割時，重點在于完成起始圖像轉換，轉換后圖像中的集水盆地就是要提取的區域。

分水嶺變換是一種基于區域和建立在數學形態學理論基礎之上的算法，但存在著對圖像中噪聲極其敏感而產生過分割和對低對比度圖像易丟失重要輪廓的缺點，主要有以下兩種算法：

1）自下而上式模擬泛洪的算法。

2）自上而下式模擬降水的算法。

4.1 模擬泛洪的算法

此類算法是從模仿高低不平的地勢環境，洪水從各個區域極小值點開始水位上溢，地勢較低各區域將逐漸充滿積水。洪水上漲至各區域的邊緣，各低地勢點溢出的洪水便會交集。若在洪水交集的邊緣筑壩分割洪水，此時被分割的區域就形成了一個集合，這個集合區域就是圖像的一個分割區域，區域邊界處筑起的防水壩就稱為分水嶺，這種模擬過程就叫做泛洪。模擬泛洪的分水嶺算法的工作原理如圖3所示。

4.2 模擬降水的算法

模仿降水分割算法模擬：地勢不平的區域上，雨水會沿著地勢表面向下流淌，同一凹陷區域上雨水最終會流向相同局部最低地勢點，那么可以稱這樣的雨水落點屬于同一區域，這個凹陷區域為同區域，而山頂上的雨水流入四周地勢的概率是相同的。可想而知，雨水流向趨勢一致的落點形成一個區域即為圖像的一個分割區域，山頂點連接而成這個區域的邊界，即是分水嶺。模擬降水分水嶺算法的工作原理如圖4所示。

圖3 模擬泛洪示意圖

圖4 模擬降水示意圖

4.3 分水嶺分割算法

本文采用的分水嶺分割方法如下所示。

記M1，M2，…，MR是待處理圖像g（x，y）局部區域極小值坐標集。記C（Mi）是區域極小值Mi相對應的雨水流勢相同坐標集合（任何集水盆地中的點都形成一個連通分量）。符號min 和max 將用于表示g（x，y）的最小值和最大值。最后，令T［n］表示滿足g（s，t）＜n的坐標（s，t）的集合，即：

幾何學上來看，T［n］是g（x，y）中位于平面g（s，t）=n 下方的點的坐標的集合。從模擬泛洪的過程來看，水位從min+1 到max+1 逐漸上升，圖像就會逐漸被水淹沒。在像素值等于n 時，分水嶺算法必須統計被淹沒像素點數量。理論上，算法將處在g（x，y）=n 平面以下的 T［n］中的坐標區分為黑色點集，其他坐標就區分為白色點集。在像素值平面增加到n 時向下觀察x-y 平面，就會得到T［n］二值圖像，圖像中的黑色點集就是平面g（x，y）=n 之下的區域。

記Cn（Mi）為集水區域中與淹沒階段n 的最小值Mi相對應的點坐標集，則Cn（Mi）可以看成由式（7）給出的二值圖像：

換句話說，如果（x，y）∈ C（Mi）和（x，y）∈ T［n］進行“與”邏輯運算，則在位置（x，y）處有Cn（Mi）=1，否則Cn（Mi）=0，可以理解成在淹沒像素值n 時只需要使用“與”（AND）算子將T［n］中的二值圖像提取出來即可。

繼而，記C［n］表示在淹沒像素值n時集水區域的“并”：

然后，記C［max+1］表示集水區域的“并”：

執行算法時，不會替換Cn（Mi）和T［n］中的元素，淹沒像素值n 增大時，Cn（Mi）和T［n］中的元素的數量要么增加，要么保持相同。簡言之，C［n-1］其實就是C［n］的子集。根據式（7）和式（8）可以得出，C［n］是T［n］的子集，C［n-1］也就屬于 T［n］。由此可以得出結論，T［n］的一個連通分量包含C［n-1］中的每一個連通分量。

分水線算法初始化條件為C［min+1］=T［min+1］，依次進行遞歸處理，通過C［n-1］計算得到C［n］。通過 C［n-1］計算 C［n］的過程：記 Q 表示 T［n］中的連通分量集合，對于每個連通分量q∈Q［n］，有如下三種可能性：

1）q∩C[n-1]為空集。

2）q∩C[n-1]包含C［n-1］的一個連通分量。

3）q∩C[n-1]包含C［n-1］的一個以上的連通分量。

通過C［n-1］構建C［n］的過程取決于上述三個條件之一。新的極小值出現時，可能性1）就會發生，此時連通分量 q 并入C［n-1］中形成 C［n］。可能性2）中q位于某些局部最小值的集水區域，此時q 并入C［n-1］中形成C［n］。當全部以及部分分割兩個以上集水區域山脊線出現時，可能性3）發生。繼續淹沒會導致集水區域水位聚合。所以，需要在q 內構筑一個水壩（如果涉及多個集水盆地，則要構筑多個水壩）以阻止集水區域間的水位聚合。

本文是在預處理拉普拉斯濾波和區域分離與聚合的基礎上進行的，并具有一定的可操作性和可行性。區域分離與聚合后的圖片能提前劃分小范圍區域，對后續分水嶺變換有一個預分割的作用。

5 實驗結果與分析

為了檢驗本文提出的改進分水嶺變換算法，本文作者在Windows 7 操作系統下，實驗軟件為Matlab R2017 的實驗條件下，進行Matlab 編程仿真驗證了多組圖片，實驗結果如下。

由以上 A 組、B 組、C 組和 D 組的原始灰度圖像、傳統分水嶺分割圖像和本文提出改進分水嶺分割圖像可以分析得到結論：本文提出的改進分水嶺變換算法圖像分割可以很大程度上減輕傳統分水嶺圖像分割的過分割現象，圖像分割的準確性得到明顯的提高。

圖5 A組分割效果對比圖

圖6 B組分割效果對比圖

圖7 C組分割效果對比圖

圖8 D組分割效果對比圖

6 結語

本文在對分水嶺變換算法進行深入研究的基礎上，提出一種基于區域分離與聚合的改進分水嶺變換分割算法。實驗結果表明，本文所采取的改進分水嶺變換圖像分割能一定程度上弱化過分割現象，能夠取得更好的圖像分割效果。但是，本文提及算法并不能解決低對比度圖像易丟失重要輪廓等問題。因此，本文提及算法對于抑制圖像過分割現象具有一定的實際應用價值。