一種自適應標記分水嶺算法的研究

汪 梅，何高明，賀 杰，郭 慧，陳 佳

（1.2.3.5.梧州學院 計算機科學系，廣西 梧州 543002；

4.梧州學院 電子信息工程系，廣西 梧州 543002）

一種自適應標記分水嶺算法的研究

汪 梅1，何高明2，賀 杰3，郭 慧4，陳 佳5

（1.2.3.5.梧州學院 計算機科學系，廣西 梧州 543002；

4.梧州學院 電子信息工程系，廣西 梧州 543002）

介紹了分水嶺算法的基本概念和原理，針對分水嶺算法出現的過分割問題，提出了一種改進的標記提取的分水嶺算法。該算法首先使用形態學梯度，并使用梯度重建技術，較好地增強了圖像對比度，同時使用改進的標記提取方法對區域最小值進行標定，使用分水嶺算法。從實驗結果來看，該方法能有效地控制分水嶺算法的過分割問題。

分水嶺；標記提取；形態學

1 分水嶺算法原理

分水嶺算法，也被稱為水線算法，20世紀70年代末由C.Digabel和H.Lantuejoul引入到圖像處理領域的，最初僅用于對簡單二值圖像的處理。但由于分水嶺算法的計算復雜度過高，所以一直沒有得到學者們的重視。分水嶺思想的真正發展始于20世紀90年代初，建立在LucVincent和S.Beucher以及同PierreSoille的共同研究的基礎上，Vincent對原始分水嶺算法的改進使它的計算速度提高了一個數量級，其思想及實現至今仍是廣大學者關注的研究熱點。分水嶺變換的經典實現算法有很多[1-2]，分水嶺分割算法是一種基于拓撲理論和數學形態學的分割方法。其思想來源于地形學，顧名思義，就是根據分水嶺的構成來考慮圖像的分割，采用地形學作為其描述方法。假設把圖像當成是一幅地形地貌圖，圖像中我們可以利用灰度和地貌的相似性來研究圖像的灰度在空間上的變化。把圖像中的每個像素的灰度值當成地形中的高度，并用這個灰度值代表該點在地形中的海拔。如果灰度值大，則海拔高。另外用集水盆表示圖像中局部極小區域，即灰度的極小值。在采用分水嶺方法進行分割時，首先確定這個地形圖中的所有局部極小點，并在每個局部極小點處，或者是盆地的最低處刺穿一個小孔，使水慢慢上升，隨著時間的變化，水將勻速地浸入一個集水盆中。為了防止兩個不同的局部最小點對應的聚水盆匯合到一起，需要在它們的相接處建筑起一個水壩，當地形完全被浸沒在集水盆以下時，所有的水壩就構成了分水嶺。這一過程可以用圖1來說明。

圖1 分水嶺示意圖

2 分水嶺算法存在的問題

標準的分水嶺變換算法是建立在梯度圖像區域極小值基礎上進行的分割，由于圖像噪聲或其他原因的影響，在實際應用場合中，梯度圖像中會出現很多的區域極小值，進而造成過分割現象。圖像分割的結果是要將圖像中感興趣的目標區域分割出來，但過分割造成的后果卻往往使分割的結果變得毫無用處。因此，在實際應用中，直接運用標準的分水嶺變換算法往往難以得到滿意的分割結果。

如何解決分水嶺算法帶來的過分割問題，一直是眾多專家學者研究的熱點問題。杜嘯曉等人[3]提出了一種保持邊界的圖像分割方法，該方法引入了非線性擴散的方法，即先對圖像進行平滑去噪，從而有效地減少了梯度圖中的最小區域的個數，然后使用區域灰度相似性和層次融合方法，較好地解決了分水嶺算法中的過分割問題。這種方法能提供較為精確的區域輪廓線。盧官明[4]提出的圖像分割方法，不是對梯度圖像進行的分水嶺分割，而是直接將分水嶺運用在原圖像上，避免了信息的丟失，并采用了分形隊列結構對圖像進行掃描，將此算法應用在運動圖像上也有較好的效果。

3 自適應標記提取的分水嶺算法

3.1 算法描述

在對分水嶺算法的改進算法中，標記提取方法與區域合并方法目前被一些學者廣泛使用，因為這兩種方法能較好地消除分水嶺的過分割問題，以及圖像中包含的噪聲問題。另一種改進是對原圖像進行預處理，例如采用濾波方式，但它只能作為一種輔助工具，但是本質上沒有對分水嶺算法起到實質性的幫助。為了解決分水嶺的過分割問題，本文仍然使用標記提取方法。在傳統的形態分割方法的基礎上，先對圖像采用形態學的方法求取梯度，并進行梯度重建，以增強梯度圖像的對比度，然后對前景和背景分別進行標記提取，從而能抑制噪聲所引起的過分割。但是本文做的改進是在原有的標記提取方法上采用自適應的標記提取方法來提取內外標記，并進行梯度重建，避免了傳統的H-minima標記提取方法中對于閾值的盲目選取，而本文改進算法中能根據圖像的統計特征選取閾值。最后以形態梯度圖像的浮點活動圖像進行分水嶺變換，使過分割現象減輕，而且邊緣定位更加精確。具體的算法可以用圖2來表示。

圖2 本文算法流程圖

3.2 算法實現

3.2.1 梯度計算

由于通過分水嶺變換得到的圖像是輸入圖像的集水盆圖像，分水嶺也就是指集水盆之間的邊界點。顯然，分水嶺在圖像中對應的是輸入圖像的極大值點。因此為得到圖像的邊緣信息，通常把梯度圖像作為輸入圖像，即

上式中，f（x,y）表示原始圖像，grad表示梯度運算。由于梯度圖能較好地反映圖像的變化情況，在原圖像的梯度圖上進行分水嶺變換能取得更好的效果，分割后的結果更加準確。本文中采用形態學梯度的方法來求取梯度，因為形態學梯度能使輸入圖像灰度級變化更大，與前面介紹過的采用模板求取梯度的方法相比，形態學梯度方法對邊緣的方向性依賴更小。最終的分水嶺變換將在被標記圖像修改后的梯度圖像上進行，以此獲得最終的分割結果。常見形態學邊緣檢測算子包含膨脹型、腐蝕型、膨脹腐蝕型。下面是對這幾種算子的介紹。

上面式（2）、式（3）、式（4）中，X為圖像集合，B為結構元素，+為膨脹運算符， I為腐蝕運算符。

3.2.2 形態學重構

在求得梯度圖后，如果直接采用分水嶺算法，梯度圖中每個獨立的局部谷底都被劃分為不同區域，這樣會導致圖像區域的過分割。由于圖像中包含有許多彼此連通但是大小不同的對象，為使得通過分水嶺變換后得到的低谷數目最小，即區域極小值最少，通常的做法是對圖像進行變換，使我們感興趣的目標對象的對比度達到最大，即對比度增強。一個常用的方法是應用高帽（top－hat）變換和低帽（bottom-hat）變換。Top-hat變換定義為：

其中·為形態學閉運算，X為原圖像，B為結構元素。

分水嶺分割通過從圖像中提取區域極小值，進而確定該極小值對應的分界線。分界線反映的是圖像中強度劇烈變化的分界線，在提取區域極值時，通常先對圖像進行對比度增強處理，以突出圖像中的明暗變化。圖像增強變換定義為：

3.2.3 自適應的標記提取方法

標記概念的提出主要是為了控制分水嶺中的過度分割。由于在實際應用中，標記點的選取往往是從得到的區域極小值點中間選擇，但是由于噪聲的影響，為了能達到滿意的分割效果，需要消除因此產生的一些區域極小值點，采取的方法往往是對梯度圖像進行修正或平滑等預處理。Soille提出的強制最小技術已經被廣泛用于分水嶺分割的標記提取[5]。而標記提取方法的基本思想是對輸入圖像的梯度圖設置一個閾值，如果梯度值小于該閾值的點，則將該點作為標記點，這樣可以減少分水嶺分割后的區域數，能較好地抑制分水嶺的過分割現象。文獻[5]使用了一種H-minima標記技術來提取標記。H-minima變換是一種有效提取標記的方法，H-minima變換的表達式如下：

H-minima變換的原理是給定一個閾值h，通過與h比較，消除那些深度低于h的局部極小值，提取滿足條件的極小值，最終得到標記圖像。這種方法的優點是可以直接給定閾值，但這同時也是它的缺點，就是因為H-minima方法給定的閾值是固定的，提取標記后的圖像結果僅僅依賴于此預先設定的閾值，而沒有將集水盆尺度聯系起來。但是實際上，根據分水嶺算法的原理，圖像中的極小值點的深度為某區域極大值點與該極小值點之間的差值，而給定的閾值主要是用來限制由于灰度值的微小變化而引起的過度分割問題，所以這個閾值應該與該區域的極大值點和極小值點有聯系[6]。也就是說可以根據極大值點和局部極小值點的相關特性來確定相應的閾值。本文的做法如下。

1.找出梯度圖像中的極大值點與極小值點集合。根據梯度計算方法求取原圖像的梯度圖像，并找出每個區域的極大值與極小值，構成兩個集合Imax和Imin。

2.求出極大值點集合的平均值與極小值點集合的平均值，以及其方差。分別求出Imax和Imin的平均值與方差。

3.消除較弱的極大值點，并重新計算均值，主要方法是如果這些極大值點集合中有灰度值小于其均值的，就將其消除，再用此均值與方差計算得到最終閾值。通過確定的閾值能將某區域中的極大值與極小值聯系起來，并且能限制過度分割問題。

4.利用第3步得到的閾值，再采用H-minima標記提取方法對圖像進行標記，得到標記圖像。

使用上述方法后再進行分水嶺算法時，首先對梯度圖中的區域極小值進行標定，然后以這個極小值作為山谷，搜索這個極小值的鄰域像素點，如果其灰度值相近，則把它設置為背景或前景。如果相鄰的兩個極小值點所對應的區域像素相遇，就將這兩個點當成區域輪廓的像素點。使用此方法進行迭代，分割結束時所有的區域極小值對應的輪廓像素點全部被確定和標記。

3 實驗結果及分析

為了驗證本章算法的可行性，本實驗選取了幾幅有代表性的圖像，用Matlab進行仿真，下頁圖3是實驗結果圖。

圖3 實驗結果分析圖

從上面的實驗圖可以看出，在原圖上直接運用標準分水嶺變換，存在明顯的過分割現象，導致分割后的結果幾乎無意義。本文通過局部極大值平均值與極小值點集合方差計算出來的閾值來消除一些偽區域，并獲得更加適量的區域。該文獻中預先設定了進行標記提取前的閾值T為50，當然這一數值可以改變，本文分別選取了閾值50、80即200進行實驗，該算法的不足也體現出來，即當閾值不同時，經過分水嶺計算后結果也不同，閾值越大，分割區域越大，區域數目越少，但是細節體現得越不明顯。而本文算法中，不用預先設定閾值，在標記提取時，會自動根據圖像的特性統計出閾值。和文獻[7]的方法對比，本文算法得到的結果圖中偽區域個數更少，能較為正確地將目標從背景中分離出來，因此本文算法效果更好。

[1]廖毅.基于顯著性分析的分水嶺分割算法[J].系統仿真學報,2007,19（2）：232-237.

[2]Gonzalez C R,Woods R E．Digital Image Processing[M].Seconded ition.Beijing：Publishing House of Electronics Industry,2002：618-626.

[3]杜嘯曉,楊新,施鵬飛.一種新的基于區域和邊界的圖象分割方法[J].中國圖象圖形學報,2001,6（8）：755-759.

[4]盧官明.區域生長型分水嶺算法及其在圖像序列分割中的應用[J].維普資訊,2000,20（3）：51-54.

[5]Sonka M,H lavacV Boyle R.Image processing,analysi,and machine vision（2nded）[M].Books／Cole Publishing,1999：576-577.

[6]譚洪波.基于自適應標記提取的分水嶺彩圖分割算法[J].計算機工程,2010,36（19）：229-231.

[7]王國權,周小紅.基于分水嶺算法的圖像分割方法研究[J].計算機仿真,2009,26（5）：255-258.

O243

A

1673-8535（2012）01-0059-06

2011－12-08

汪梅（1981-），女，湖北洪湖人，梧州學院計算機科學系講師，廣西師范大學研究生，研究方向：計算機應用技術、圖像處理。

何高明（1980-），男，湖北通城人，梧州學院計算機科學系講師，廣西師范大學研究生，研究方向：嵌入式系統。

賀杰（1982-），男，湖南桃江人，梧州學院計算機科學系講師，廣西師范大學研究生，研究方向：圖像處理。

郭慧（1981-），女，廣西梧州人，梧州學院電子信息工程系講師，廣西師范大學研究生，研究方向：圖像處理。

陳佳（1982-），女，重慶大足人，梧州學院計算機科學系講師，廣西師范大學研究生，研究方向：圖像處理。

覃華巧）