基于區(qū)域分離與聚合的分水嶺分割*

王 祥 羅素云

（上海工程技術(shù)大學(xué)機(jī)械與汽車(chē)工程學(xué)院 上海 201620）

1 引言

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

2 預(yù)處理濾波

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

在x方向上，有：

在y方向上，有：

所以，依據(jù)上述公式可推算兩個(gè)變量的拉普拉斯算子為

使用拉普拉斯微分算子進(jìn)行圖像增強(qiáng)的基本公式為

式（5）中的c當(dāng)模板w 中心系數(shù)為正時(shí)取1，否則取-1。

本文通過(guò)拉普拉斯濾波預(yù)處理，可以將待分割圖像區(qū)域邊界進(jìn)行銳化增強(qiáng)，作為最簡(jiǎn)單的各向同性微分算子，此過(guò)程具有旋轉(zhuǎn)不變性，同時(shí)盡可能地保留原始灰度圖像的灰度層次，較為適合本文圖像分割過(guò)程。

3 區(qū)域分離與聚合

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

條件1）表示分割必須完全；條件2）表示區(qū)域點(diǎn)必須連續(xù)；條件3）表示各個(gè)區(qū)域必須互不相交；條件4）表示區(qū)域內(nèi)像素點(diǎn)屬性相同；條件5）表示不同區(qū)域內(nèi)屬性不同。

選擇一種屬性P，對(duì)R 進(jìn)行分割處理的一種規(guī)則是逐次細(xì)分成四個(gè)象限區(qū)域，測(cè)試對(duì)于局部區(qū)域Ri有P（Ri）=TRUE。從整個(gè)區(qū)域開(kāi)始，如果P（R）=TRUE，我們把圖像分為四象限區(qū)域。若對(duì)于每個(gè)象限區(qū)域P 為FALSE，則將該象限區(qū)域再細(xì)分為四個(gè)子象限區(qū)域，以此類(lèi)推。這種特殊的分離技術(shù)可以形象地表示為四叉樹(shù)的形式，即每個(gè)節(jié)點(diǎn)都正好有四個(gè)后代，如圖1 所示（對(duì)應(yīng)一個(gè)四叉樹(shù)的節(jié)點(diǎn)的圖像有時(shí)稱(chēng)為四分區(qū)域或四分圖像）。其中，樹(shù)根可以代表待處理圖像，而其后每個(gè)節(jié)點(diǎn)可對(duì)應(yīng)于四個(gè)后支節(jié)點(diǎn)。在這種情況下，僅進(jìn)一步細(xì)分了R4。

圖1 四叉樹(shù)模型示意圖

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

上述過(guò)程可以總結(jié)如下：

1）將滿(mǎn)足條件的P（R）i=FALSE 的任何區(qū)域Ri分離為四個(gè)不相交的象限區(qū)域。

2）當(dāng)不能進(jìn)一步分離時(shí)，聚合滿(mǎn)足條件P(Ri∪Rj)=TRUE的任意兩個(gè)相鄰區(qū)域Ri和Rj。

3）當(dāng)不能進(jìn)一步聚合分區(qū)域時(shí)，停止分離與聚合操作。

算法終止條件是規(guī)定不能再執(zhí)行分裂的最小四象限區(qū)尺寸。

4 分水嶺變換

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

圖2 分水嶺示意圖

理解分水嶺變換時(shí)要求把灰度圖像視為一個(gè)拓?fù)浔砻妫砻嬷衒（x，y）的值被理解為高度。例如，圖2（a）中的簡(jiǎn)單圖像形象化為圖2（b）中的三維表面。假設(shè)雨水流淌在該表面區(qū)域，就會(huì)流入到兩個(gè)積水盆地中心，而正好處在脊線上的雨水會(huì)等概率地流向兩側(cè)。分水嶺變換則是需要找到灰度圖像的積水區(qū)域和脊線，在進(jìn)行圖像分割時(shí)，重點(diǎn)在于完成起始圖像轉(zhuǎn)換，轉(zhuǎn)換后圖像中的集水盆地就是要提取的區(qū)域。

分水嶺變換是一種基于區(qū)域和建立在數(shù)學(xué)形態(tài)學(xué)理論基礎(chǔ)之上的算法，但存在著對(duì)圖像中噪聲極其敏感而產(chǎn)生過(guò)分割和對(duì)低對(duì)比度圖像易丟失重要輪廓的缺點(diǎn)，主要有以下兩種算法：

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

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

4.1 模擬泛洪的算法

此類(lèi)算法是從模仿高低不平的地勢(shì)環(huán)境，洪水從各個(gè)區(qū)域極小值點(diǎn)開(kāi)始水位上溢，地勢(shì)較低各區(qū)域?qū)⒅饾u充滿(mǎn)積水。洪水上漲至各區(qū)域的邊緣，各低地勢(shì)點(diǎn)溢出的洪水便會(huì)交集。若在洪水交集的邊緣筑壩分割洪水，此時(shí)被分割的區(qū)域就形成了一個(gè)集合，這個(gè)集合區(qū)域就是圖像的一個(gè)分割區(qū)域，區(qū)域邊界處筑起的防水壩就稱(chēng)為分水嶺，這種模擬過(guò)程就叫做泛洪。模擬泛洪的分水嶺算法的工作原理如圖3所示。

4.2 模擬降水的算法

模仿降水分割算法模擬：地勢(shì)不平的區(qū)域上，雨水會(huì)沿著地勢(shì)表面向下流淌，同一凹陷區(qū)域上雨水最終會(huì)流向相同局部最低地勢(shì)點(diǎn)，那么可以稱(chēng)這樣的雨水落點(diǎn)屬于同一區(qū)域，這個(gè)凹陷區(qū)域?yàn)橥瑓^(qū)域，而山頂上的雨水流入四周地勢(shì)的概率是相同的?？上攵?，雨水流向趨勢(shì)一致的落點(diǎn)形成一個(gè)區(qū)域即為圖像的一個(gè)分割區(qū)域，山頂點(diǎn)連接而成這個(gè)區(qū)域的邊界，即是分水嶺。模擬降水分水嶺算法的工作原理如圖4所示。

圖3 模擬泛洪示意圖

圖4 模擬降水示意圖

4.3 分水嶺分割算法

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

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

幾何學(xué)上來(lái)看，T［n］是g（x，y）中位于平面g（s，t）=n 下方的點(diǎn)的坐標(biāo)的集合。從模擬泛洪的過(guò)程來(lái)看，水位從min+1 到max+1 逐漸上升，圖像就會(huì)逐漸被水淹沒(méi)。在像素值等于n 時(shí)，分水嶺算法必須統(tǒng)計(jì)被淹沒(méi)像素點(diǎn)數(shù)量。理論上，算法將處在g（x，y）=n 平面以下的 T［n］中的坐標(biāo)區(qū)分為黑色點(diǎn)集，其他坐標(biāo)就區(qū)分為白色點(diǎn)集。在像素值平面增加到n 時(shí)向下觀察x-y 平面，就會(huì)得到T［n］二值圖像，圖像中的黑色點(diǎn)集就是平面g（x，y）=n 之下的區(qū)域。

記Cn（Mi）為集水區(qū)域中與淹沒(méi)階段n 的最小值Mi相對(duì)應(yīng)的點(diǎn)坐標(biāo)集，則Cn（Mi）可以看成由式（7）給出的二值圖像：

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

繼而，記C［n］表示在淹沒(méi)像素值n時(shí)集水區(qū)域的“并”：

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

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

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

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

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

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

通過(guò)C［n-1］構(gòu)建C［n］的過(guò)程取決于上述三個(gè)條件之一。新的極小值出現(xiàn)時(shí)，可能性1）就會(huì)發(fā)生，此時(shí)連通分量 q 并入C［n-1］中形成 C［n］?？赡苄?）中q位于某些局部最小值的集水區(qū)域，此時(shí)q 并入C［n-1］中形成C［n］。當(dāng)全部以及部分分割兩個(gè)以上集水區(qū)域山脊線出現(xiàn)時(shí)，可能性3）發(fā)生。繼續(xù)淹沒(méi)會(huì)導(dǎo)致集水區(qū)域水位聚合。所以，需要在q 內(nèi)構(gòu)筑一個(gè)水壩（如果涉及多個(gè)集水盆地，則要構(gòu)筑多個(gè)水壩）以阻止集水區(qū)域間的水位聚合。

本文是在預(yù)處理拉普拉斯濾波和區(qū)域分離與聚合的基礎(chǔ)上進(jìn)行的，并具有一定的可操作性和可行性。區(qū)域分離與聚合后的圖片能提前劃分小范圍區(qū)域，對(duì)后續(xù)分水嶺變換有一個(gè)預(yù)分割的作用。

5 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)本文提出的改進(jìn)分水嶺變換算法，本文作者在Windows 7 操作系統(tǒng)下，實(shí)驗(yàn)軟件為Matlab R2017 的實(shí)驗(yàn)條件下，進(jìn)行Matlab 編程仿真驗(yàn)證了多組圖片，實(shí)驗(yàn)結(jié)果如下。

由以上 A 組、B 組、C 組和 D 組的原始灰度圖像、傳統(tǒng)分水嶺分割圖像和本文提出改進(jìn)分水嶺分割圖像可以分析得到結(jié)論：本文提出的改進(jìn)分水嶺變換算法圖像分割可以很大程度上減輕傳統(tǒng)分水嶺圖像分割的過(guò)分割現(xiàn)象，圖像分割的準(zhǔn)確性得到明顯的提高。

圖5 A組分割效果對(duì)比圖

圖6 B組分割效果對(duì)比圖

圖7 C組分割效果對(duì)比圖

圖8 D組分割效果對(duì)比圖

6 結(jié)語(yǔ)

本文在對(duì)分水嶺變換算法進(jìn)行深入研究的基礎(chǔ)上，提出一種基于區(qū)域分離與聚合的改進(jìn)分水嶺變換分割算法。實(shí)驗(yàn)結(jié)果表明，本文所采取的改進(jìn)分水嶺變換圖像分割能一定程度上弱化過(guò)分割現(xiàn)象，能夠取得更好的圖像分割效果。但是，本文提及算法并不能解決低對(duì)比度圖像易丟失重要輪廓等問(wèn)題。因此，本文提及算法對(duì)于抑制圖像過(guò)分割現(xiàn)象具有一定的實(shí)際應(yīng)用價(jià)值。