基于形態學及區域合并的分水嶺圖像分割算法

李云紅，張秋銘，周小計，賈凱莉

西安工程大學 電子信息學院，西安710048

1 引言

圖像分割是圖像分析、圖像識別和圖像理解的基礎，圖像分割質量的好壞直接關系到后續圖像處理的效果，故圖像分割在圖像處理過程中占據著十分主要的地位。圖像分割是利用圖像的灰度、顏色、紋理、形狀等信息按照標準將圖像中具有特殊含義的不同區域分開。保證被分開的每個區域內部滿足一致性，區域與區域間滿足一定差異性。圖像分割可以從復雜場景中提取出人們感興趣的目標，然后進行下一步處理。

目前主流的圖像分割方法包括閾值分割、基于區域增長的分割、分水嶺分割[1-2]、聚類分割和神經網絡分割等。分水嶺算法是建立在數學形態學理論基礎上的基于區域的圖像分割方法。分水嶺算法起源于Digabel等對簡單二值圖像的分析，20 世紀70 年代末，Beucher 和Lantuejoul為增加模型的適用范圍提出應用分水嶺算法進行圖像分割，1991年Vincent等[3]提出了基于浸沉技術的分水嶺分割算法，為后續的分水嶺分割研究提供了基礎，但早期方法負擔重、耗時過長的問題尤為顯著。近幾年，對分水嶺算法的研究和改進也在進一步深入中。王棟等[4]提出一種基于分水嶺和FLICM 模糊聚類的圖像分割方法，能夠有效地解決過分割問題，但對于一般圖像噪聲的效果不明顯，易造成失真現象。陳潔等[5]通過提取標記點進行分水嶺圖像分割，但只能在一定程度下抑制過分割。林振榮等[6]使用形態學濾波對圖像平滑降噪，再對分割后圖像區域合并，有效保留了圖像的重要輪廓信息，但缺乏對復雜圖像的適用性。形態學分水嶺[7-11]由于其對區域邊緣定位和封閉輪廓提取具有較好的效果被廣泛應用在圖像分割中，但普遍存在過分割問題。基于標記的分水嶺分割算法[12-13]具有一定先驗性，分割結果依賴于標記選取，選取不同的標記與圖像分割的結果密切相關。

針對以上圖像分割算法存在的諸如對圖像細節噪聲敏感、分割過程出現過分割等問題，提出基于形態學標記及區域合并的分水嶺改進算法。該算法能夠有效抑制分水嶺的過分割，同時也能彌補傳統形態學標記的漏標記區域問題。

2 傳統分水嶺算法

傳統分水嶺原理圖如圖1所示，分水嶺算法（watershed）的基本思想是將圖像看作為地理學的拓撲地貌，將圖像想象成一個立體的地形表面。圖像中的每一個像素的灰度值作為該點的海拔高度，每一個局部極小值及它影響的區域被稱為集水盆，則集水盆的邊界就形成了分水嶺。分水嶺的概念和形成能夠通過模擬浸入的過程來說明，假設在每個區域極小值的位置刺穿一個小孔，從孔中向該區域不斷注水，則地勢較低的區域會首先被淹沒，在浸入加深的過程中，每一個局部極小值的影響域都處在慢慢擴展過程中，當水淹沒到一定高度時兩個集水盆會相連合并為同一個區域，此時應在兩個集水盆匯合處構筑“大壩”來阻止區域合并，最終形成分水嶺，這些“大壩”的邊界對應于分水嶺的分割線，同時也是由分水嶺算法提取出的連續邊界輪廓。

圖1 傳統分水嶺原理圖

2.1 分水嶺算法步驟

根據傳統分水嶺的原理，用M1,M2,…,MR表示分割圖像g(x,y)的最小值點的坐標集合，G(Mi)為一個點的坐標集合，這些點位于與Mi相關系的集水盆內。圖像g(x,y)的最小值和最大值分別用min 和max 來表示。

式中，T[n]表示坐標g(s,t)中點(s,t)的集合，這些點都位于平面g(x,y)=n 的下方。水位增加過程中，觀察xy平面會產生一幅二值圖像Cn(Mi)，可表示為：

算法初始選取C[min+1]=T[min+1]，隨后算法進行遞歸調用，假設C[n-1]已經建立，根據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]中至少一個連通分量。

當獲得一個最小值符合條件（1），此時將q 并入C[n-1]構成C[n]；q 位于最小值構成的集水盆中時，滿足條件（2），重復（1）中操作；滿足（3）條件C[n-1]時，q含有一些組成的元素，此時需在q 內建立一座水壩，防止單獨集水盆內溢流溢出。

2.2 分水嶺分割效果

按照傳統分水嶺圖像分割算法步驟對醫學CT圖像進行分割處理，CT 圖像如圖2 所示，處理結果如圖3 所示。發現傳統分水嶺算法雖對微弱的邊緣具有良好的響應，但對圖像中噪聲、物體表面細微的灰度變化比較敏感，噪聲會惡化圖像梯度進而造成分割結果輪廓偏移，通常的分割結果會出現嚴重的“過分割”現象。為得到更好的圖像分割效果，必須對分水嶺算法進行改進。

圖2 CT圖像原圖

圖3 傳統分水嶺分割

3 形態學區域合并的分水嶺算法

3.1 算法步驟

（1）形態學混合開閉重建運算

數學形態學是以結構元素為基礎對圖像進行數學分析的工具。在數學分析過程中利用具有一定形態結構的結構元素度量和提取圖像中的對應形狀，進一步達到對圖像識別和分析的目的，在圖像的處理過程中，有四種數學形態學的基本運算：膨脹，腐蝕，開運算和閉運算。

圖像腐蝕能夠使小于結構元素的物體，小的凸起或毛刺被去除，通過選取不同尺寸大小的結構元素，能夠在圖像中去掉不同大小的物體。膨脹操作能夠將圖像變大，填充物體內部的孔洞。

在形態學中，結構元素是最基本的概念。結構元素在形態變換中所起到的作用相當于信號處理中的“濾波窗口”。用B(x)代表結構元素，對于工作空間E 中的每一個點x，腐蝕和膨脹操作定義如式（3）、（4）所示：

對于圖像，腐蝕膨脹操作定義如式（5）、（6）所示。

其中，f(x,y)為輸入圖像，b(x,y)為結構元素。先腐蝕后膨脹的過程為開運算，用來平滑較大物體的邊界同時不改變物體面積。先膨脹后腐蝕的過程為閉運算，能夠填充物體內部孔洞連接鄰近物體，平滑邊界的同時不改變其面積。由于噪聲和細節可能位于目標信號的上方或下方，使用單一的腐蝕或膨脹操作，只能消除目標信號上方或下方的噪聲和細節，且平滑后的圖像總是位于原圖的上方或下方，因此會造成目標信息的位置偏移。構建形態學開閉混合運算，能夠在保持目標信息完整性和位置不變的前提下，達到消除圖像中細節噪聲的目的。此步驟能夠在后續處理之前，消除梯度圖像中由于非規則灰度擾動和噪聲引起的局部極值，保留目標物輪廓和信息。

（2）圖像增強，拉普拉斯銳化處理

進一步強調圖像的邊緣和細節，對圖像進行銳化，提高對比度。拉普拉斯銳化圖像與某個像素的周圍像素到此像素的突變程度相關，依據是像素的變化程度。根據二級微分能夠找到像素的過渡程度。當鄰域中心像素灰度低于它所在的鄰域的平均灰度值時，此中心像素的灰度也應隨之降低；當中心像素灰度值高于它所在鄰域平均灰度值，中心像素的灰度值應該升高。以這種方式來實現圖像的銳化。

二階微分和像素的關系如式（7）所示：

拉普拉斯重心掩模系數為：

可得到四鄰域矩陣模板（9）：

同理八鄰域的銳化過程如式（10）所示，矩陣模板：

將得到的值替換原(x,y)像素處的值，能夠得到類似邊界的地方，由式（12）得到銳化圖像：

（3）標記背景和目標物

在尋找標記時，目標物體相對較亮而背景對應暗區。若此時背景區域較暗，可以利用圖像二值化，找到背景的對應區域確保外部標記符能夠包含于背景中，由于目標物一般位于圖像其他物體的突出位置，故目標物可能為局部區域像素值的最大區域，可以通過尋找局部區域極大值作為目標物體的標記符。尋找內外標記符過程如圖4所示。

圖4 尋找內外標記符

首先對圖像進行基于重建的連續開閉操作產生圖片區域極大極小值，對極大值點作為目標物進行標記。再對圖像二值化對像素進行距離變換將像素點位置信息轉換為圖像的灰度信息。然后取出圖像相鄰區域的分界線構成背景標記，最后對圖像的梯度幅值圖像進行修正。

（4）基于最大相似度的區域合并（MSRM）

在上一步的標記結束后，仍存在部分遺漏的未標記區域。此方法能夠合并遺留的區域到目標區域或背景區域中。MSRM分為兩個階段，第一階段為采樣迭代方式，未標記區域集合中與背景集合相似度較大區域與背景集合合并。直到在背景集合中不再有新區域與未標記集合的某個區域合并為止。在每個迭代步驟中，背景集合和未標記集合不斷更新，背景集合擴張未標記區域集合收縮。第二階段專注在處理第一階段完成后剩余的區域，未標記區域集合中根據區域最大相似度先進行集合內區域合并，合并后區域屬于目標物或者背景交由下一輪完成。兩個階段不斷相繼執行，直到沒有新的區域合并為止。

①A 是B 的相鄰區域，用SA=表示A的鄰近區域，且B ∈

3.2 算法流程圖

綜上，算法流程圖如圖5所示。首先將獲取的彩色圖像轉換為灰度圖像，對灰度圖像進行形態學開閉操作去除圖像細小噪聲，再用拉普拉斯強化輪廓。然后以圖像區域的亮暗程度為前提標記圖像目標物和背景區域，并對修正后的梯度幅值圖像分水嶺分割。最后利用MSRM對分割圖像區域合并，將漏標記區域合并到目標物或背景區域中，直到沒有新的區域合并成功算法結束。

圖5 算法流程圖

4 實驗結果

為進一步測試改進分水嶺算法的分割效果，實驗在Intel 酷睿i7-7500U CPU，8 GB RAM 計算機完成。實驗所用工具為MATLAB2016。對圖6中Cameraman、Lena、Coin 經典圖像和醫學圖像采用聚類圖像分割算法，Hminima標記的分水嶺算法[10]，Otsu類間最大距離分割算法和本文改進后的分水嶺算法進行分割結果比較，圖7為在Lableme中標記的GT圖像，比較結果如圖8～11所示。

圖6 原始圖像

圖7 GT圖像

圖8 Cameraman圖像分割結果比較

圖9 Lena圖像分割結果比較

圖10 Coin圖像分割結果比較

圖11 醫學圖像分割結果比較

為進一步評價算法的分割效果，采用分割交并比（Intersection-over-Union，IoU）、精確度precision、召回率recall進行評價，分割交并比原理如圖12所示，計算方法如式（13）所示。精確度，召回率計算方法如式（14）所示。

圖12 IoU計算示意圖

從圖8～11 可以看出，本文算法對比聚類算法、Hminima標記的分水嶺算法和Otsu類間距最大距離分割方法在圖像細節的分割效果上具有一定優勢。采用算法平均分割時間和分割交并比，精確度和召回率對幾種算法進行量化比較，結果如表1～3所示。本文算法平均分割時間為2.63 ms，對比基于H-minima 標記的分水嶺[14]、k 均值聚類[15]、Otsu 分割方法分別提升3.86 ms，2.88 ms，5.64 ms。如表2 所示分割交并比IoU 平均為96.42%，比其他算法平均值高出12.65%，2.77%和3.07%。算法平均精確度和平均召回率為0.921和0.922，對比其他算法針對4種圖像的分割精確度平均值高出0.081，召回率高出0.088。

表1 算法平均分割時間對比 ms

表2 分割交并比IoU對比表 %

表3 精確度、召回率對比表

為了驗證算法在復雜背景圖片中的分割效果，又選取了幾幅具有復雜背景的圖像進行測試，原始圖片13（a）、（b）、（c）來源Berkeley Segmentation Dataset[16]，圖14 為在Lableme中標記的GT圖像。分割結果與基于H-minima標記的分水嶺算法、聚類分割和Otsu類間最大距離分割算法進行比較，比較結果如圖15～17所示。經驗證得出本文分割算法不僅適用于簡單背景的常規圖片，對具有復雜背景圖像也具有較好的分割效果。通過觀察輪廓提取結果，分割效果對比形態學標記分水嶺分割有明顯提升。

5 結論

圖13 原始圖像

圖14 GT圖像

圖15 BSDS376001圖像分割結果對比

圖16 BSDS300091圖像分割結果對比

圖17 BSDS101087圖像分割結果對比

基于形態學的連續開閉操作能夠消除圖像的細節噪聲，再利用拉普拉斯銳化強化圖像邊界，使圖像邊界更加清晰。然后在此基礎上標記圖像目標物與背景并修正梯度幅值圖像，對得到的梯度幅值圖像進行分水嶺分割。最后將初步分割結果進行MSRM 區域合并，使遺漏的標記區域合并到目標物或背景區域中。實驗結果表明，改進后的算法對比聚類分割、Otsu 類間最大距離分割方法和增強細節的分水嶺三種算法在分割精確度和平均算法分割時間上具有明顯優勢，且對于復雜背景圖片的分割具有一定適用性，是一種有效的圖像分割算法。