一種程度可控的形態學多尺度梯度分水嶺算法

摘要:為解決分水嶺算法中的過分割現象，提出了一種基于多尺度形態學梯度的谷底填充算法，通過調整填充閾值的方式實現對分割區域數量的控制，同時利用Canny邊緣檢測算子獲取圖像邊緣信息，以此對梯度圖中的邊緣位置進行強化和修正，確保分割出的區域輪廓在谷底填充過程中盡可能地保持與目標邊緣擬合。仿真結果表明，此算法對于改善過分割現象有明顯效果，并且對分割程度具備可控能力，在適應不同場景需求方面存在一定的應用價值。

關鍵詞:圖像分割; 分水嶺算法; 邊緣檢測; 形態學多尺度梯度

中圖分類號:TP391.41文獻標志碼:A

文章編號:1001－3695(2008)02－0475－03

圖像分割在圖像內容分析和模式識別等領域具有極強的應用價值，是圖像處理領域的經典問題，多年來得到了廣泛和深入的研究。隨著MPEG－4等編碼標準的研究發展，其基于內容的編碼和對象的存取與操控技術日益得到人們的重視。而靜態圖像分割，作為視頻對象提取技術的核心基礎環節之一，也得到了更多的關注。圖像分割的最終目的是將感興趣的目標對象從背景中分離出來，以用于進一步的分析和操作。要實現目標對象的提取，最直觀的思想即尋找該目標的閉合邊緣輪廓。在圖像分割領域的眾多分割算法中，形態學分水嶺(watershed)[1]由于其獨特的區域邊緣定位和封閉輪廓提取能力，已成為近年來的研究熱點。

伴隨watershed各種優點而來的也有一個嚴重的缺陷:原圖像中均勻一致的區域通常會受噪聲和量化誤差的影響而被分割成多個零碎的小塊區域，即所謂的過分割現象。較為通常的應對辦法是在過分割之后再根據一定的聚類原則進行區域融合[2]，近年來也有一些文獻提出可以針對過分割的直接成因——梯度谷底，即局部梯度極小值作相應處理;盧官民[3]提出一種形態學膨脹和重構方法來消除谷底;王小鵬等人[4]從保持尺度對梯度谷底因果性關系的角度提出一種梯度修正方案。本文正是秉承此類方法的思路提出一種閾值可控的谷底填充算法，并在填充過程中引入經典的邊緣檢測算法對watershed分割出的區域輪廓的準確性加以保障與修正。

另一方面，對于圖像分割效果如何評定也是一個有待深入討論的問題，目前還沒有一種得到公認的客觀評定標準，所以現階段評價一幅圖像的分割效果主要還是依靠人的主觀意識。對于不同的應用需求，人們需要的分割程度不盡相同。例如，同樣是對一幅人物圖像作分割，如果是作為視頻對象提取的幀內分割，需要得到的是目標人物的最外層輪廓;但如果是作面部識別或是細節特征匹配，則除了需要得到外層輪廓之外還要有內部紋理細節。有鑒于此，本文的算法在填充谷底時留出了一個可控的閾值，用來引入主觀評判的督導，從而使分割結果能夠滿足不同應用場景的需要。

1基本原理

基于watershed變換的圖像分割方法，其性能在很大程度上依賴于用來計算待分割圖像梯度的算法。對于watershed而言，理想的梯度算子輸出應等于輸入的邊緣高度[3]，即邊緣兩邊之間的像素灰度差，而不是邊緣的斜率。自然圖像中一般很少出現理想的階躍邊緣，通常都是界限比較模糊的斜坡邊緣，對于這種邊緣類型，傳統的梯度算子輸出的是邊緣斜率，形態學梯度算子卻能夠輸出邊緣高度。有鑒于此，本文的算法采用了多尺度形態學梯度算子[3]來計算圖像梯度。

盡管多尺度形態學梯度算子比較適合于watershed變換，但其濾波的特性在去除噪聲的同時也對原始圖像中的邊緣信息產生了一定程度的削弱，從而縮短了邊緣與噪聲之間的落差，這在本文算法的谷底填充階段將會導致邊緣輪廓出現一定程度偏移甚至丟失的現象。為解決這一問題，可以考慮對被削弱的邊緣進行強化和修正。

經過圖像分割領域多年研究，人們逐漸認識到現有的任何一種單獨的分割算法都難以對自然圖像取得令人滿意的分割效果[5]。于是，把各種方法綜合起來運用的思想成為近年來的研究熱點。針對上文提到的問題，若要強化邊緣，首先必須找到這些邊緣的準確位置，因而本文將經典的邊緣檢測算法結合到了基于區域的watershed變換中。

邊緣檢測[7]是根據區域邊緣上的像素灰度變化比較劇烈這一特征，通過檢測不同區域的邊緣來解決圖像分割問題。其優點是對于邊緣線的定位精度很高，而且計算復雜度較低。至于如何將邊緣檢測的準確定位能力結合到基于區域的watershed變換中來，這要從watershed的實現機理入手。

在圖像處理領域，計算分水嶺的算法有很多。其中:典型的一種方法是基于浸沒模擬(immersion simulation)[1]思想，即把待分割圖像的梯度圖視為地形表面，像素的梯度對應于地形高度，其局部最小值對應地形的谷底。設想將地形表面浸入一個湖中，從最小值開始，水會逐漸充滿各個不同的聚水盆地，當來自相鄰聚水盆地的水要合并時，若在該處建立一個堤壩，則浸沒結束時，所建立的堤壩就對應于區域的輪廓，而聚水盆地則對應分割區域。從這一原理上分析，要使邊緣檢測算子檢測出的邊緣能夠對區域分割的結果產生影響，就應當將這些邊緣映射到梯度圖像中堤壩的位置上。本文以此為據，提出一種梯度峰值增強的方法，使梯度計算中被削弱的邊緣輪廓重新得到修正和強化。

綜合以上分析，本文分割方案的基本流程如圖1所示，對圖像同時進行兩條路線的處理:第一條線路選用合適的邊緣檢測算法提取出原始彩色圖像中目標對象的邊緣信息;在另一條線路上對圖像的灰度信號使用多尺度形態學算子計算梯度，然后結合邊緣檢測結果對梯度圖進行包括谷底填充和峰值增強兩個步驟的梯度調整，最后對調整后的梯度圖使用watershed變換完成分割。

2彩色圖像邊緣提取

在現有的多種邊緣檢測算子中，本文選用經典的Canny算子[6]來完成圖像邊緣的提取。Canny邊緣檢測算子是一種局部極值邊緣檢測法，它通過高斯函數的導數求圖像灰度梯度，并將得到的梯度局部極值作為物體的邊緣。它通過兩個閾值來確定強邊緣和弱邊緣，而且只有當測得的弱邊緣與強邊緣相連時才認為它是邊緣。Canny算子是一種理論最優的邊緣檢測算子，它主要具有以下三個優點:a)高判別率，即盡可能少地將邊緣點漏判成非邊緣點，同時有效抑制虛假邊緣;b)定位精度高，能夠準確地把邊緣點定位在灰度變化最大的像素上;c)抗噪性能強，檢測出的邊緣連續性好，中斷較少，可以獲得相對完整的線段。

人的視覺系統對于亮度和顏色的敏感程度具有很大差異[8]，在一幅復雜圖像的任意一個點上，人眼只能識別幾十種灰度級，但可以識別成千上萬種不同的顏色，所以在很多情況下，單純利用灰度信息無法從圖像中提取出令人滿意的目標。在彩色圖像中，用于邊緣檢測的信息更加豐富，如具有相同亮度#65380;不同色調的邊緣同樣可以被檢測出來，在作圖像分割時可以充分利用這些有用的信息。

對于彩色圖像的處理，首先要選取一個合適的顏色空間，這里為了今后能更為方便地將圖像分割技術應用于視頻序列的對象提取，并且能夠很好地與灰度圖像兼容，故采用ITU規定的數字電視標準色彩空間YCbCr。該顏色空間通過把亮度與顏色信息分離，并對亮度值取更高的分辨率以更有效地表示顏色圖像。

本文的方案是在YCbCr的三個分量圖上分別進行Canny檢測，然后將得到的三個檢測結果作“或”運算，從而最大程度地提取各個顏色分量包含的邊緣信息。

3多尺度形態學梯度算子

數學形態學是一種廣泛應用于圖像處理和模式識別領域的方法，其基本思想是用具有一定形態的結構元素去度量和提取圖像中的對應形狀以達到對圖像分析和識別的目的。利用數學形態學的幾個基本概念和運算，將結構元素靈活地組合分解，應用形態變換可以達到分析的目的。

大多數的形態學濾波器都是基于兩個最基本的操作[9]，即膨脹和腐蝕，其定義分別為

腐蝕:

其中:SEi表示大小為(2i+1)×(2i+1)的正方形結構元素。

對圖像使用這一算子將得到反映所有邊緣高度的梯度圖像，由于使用了多種尺寸的結構元素并取其平均的操作，該算子具備相對較強的抗噪聲性能和很強的抗邊緣間相互影響能力。

4特定區域梯度調整

通過前面幾個步驟，已經提取出圖像中目標的邊緣信息以及反映各像素邊緣高度的梯度圖像。按照watershed的原理，將整幅梯度圖像看做地形圖，圖上各像素的梯度值就是該點的海拔高度。局部梯度極大的像素對應于山峰，局部梯度極小值則對應于谷底。下面分別從谷底和山峰兩個方面對梯度圖像進行調整，以獲取最佳的watershed結果。

1)谷底填充梯度谷底是watershed分割出一個區域的直接成因。圖像盡管通過一系列形態學算子的濾波，從某種程度上降低了噪聲的干擾，但不可避免地還是會因為原始圖像中一些灰度的小幅波動或量化誤差而在梯度圖像中產生一些低落差的小塊谷底，造成watershed結果中的過分割現象。針對這些虛假谷底與周邊像素梯度落差較低這一特性，本文的方案根據谷底落差選擇性地填充某些谷底，從而減少梯度圖中的谷底數量。具體算法如下:

a)尋找梯度圖像中所有的谷底Vi，記錄每個谷底與周圍像素的梯度落差Fi(其中i為谷底序號)。

b)選取填充閾值T，對于所有符合Fi≤T的Vi進行梯度填充，將Vi的梯度值提高Fi，使其與周圍像素梯度值持平，即此谷底被完全填平。

這樣填充閾值取得越大，被填平的谷底越多，每填平一個谷底就相當于在watershed的結果中減少一個對應的區域塊(實際上該對應區域塊是被融入周圍的其他區域塊)，從而實現了用設定閾值的方法控制最終分割區域塊數量的目的。同時，由于谷底梯度被填平后就不再增加，不會因為原谷底梯度值的提高而使其周邊產生新的小塊谷底。當然，由于虛假谷底的幅度與真實谷底的幅度值并沒有嚴格界限，當填充閾值逐漸提高時不可避免地會有些有意義的區域被誤消除，反映到分割結果中則表現為某些邊緣輪廓的偏移或缺失，這一問題可以從另一方面來加以緩解，即對梯度峰值的操作。

2)峰值增強圖像經過形態學算子運算后，在濾除噪聲的同時雖然憑借形態學算子的特性能夠在一定程度上保留圖像中的部分邊緣信息，并將之反映在梯度圖像的山峰部分，但無可避免地削弱甚至消除了這些邊緣與周圍非邊緣像素的梯度落差。在填補谷底的過程中，一旦與山峰鄰近的谷底被填平，極有可能使原已受到削弱的山峰被完全淹沒在周圍的像素中從而造成watershed結果中對應邊緣線的偏移甚至缺失。鑒于Canny算子更為準確和完備的邊緣檢測能力，可以知道之前用Canny算子檢測出的邊緣圖實際上標注出了梯度圖像中山峰的理想位置分布。本文的方案就以此邊緣圖為參照大幅度提高梯度圖像中對應山峰像素的梯度值，即前文所說的在邊緣位置上建立起極高的堤壩。這樣一來，原來的局部極大值變為全局極大值，無論怎樣提高谷底的梯度值，這些山峰均不會輕易被淹沒，反映在最終的watershed分割結果中就是山峰對應的邊緣線會被盡可能穩固地保留成為區域輪廓，從而保證了區域輪廓和目標邊緣的精確擬合。

5仿真結果

本文使用MATLAB 7.1進行仿真實驗，原始彩色測試圖片如圖2所示，隨機抽取自MPEG測試視頻序列foreman，為原序列第115幀。

對原始彩色圖像的Y#65380;Cb#65380;Cr三個分量分別作Canny檢測的結果以及最終相與得到的邊緣圖如圖3所示。可以看出，圖像的任何一個分量均存在一定程度的邊緣缺失，最終合成圖的邊緣信息則相對完整。

提取彩色圖像的Y分量作為形態學梯度運算的輸入灰度圖像，如圖4所示。

在峰值增強步驟之后，進一步進行谷底填充操作(這里取閾值15)，如圖5所示。圖5(a)(b)中谷底被標注為白色區域，原本零碎散亂的谷底在填充操作之后逐漸融合，反映到最終的watershed分割結果見圖5(c)(d)。通過對比可以看出，如果直接對前面得到的梯度圖像進行watershed變換，則過分割現象十分嚴重，基本上無法看出原圖像中的目標輪廓，而在谷底填充后，過分割現象得到明顯改善，分割出的各區域已基本具備語義學含義。

圖6顯示谷底填充閾值為5#65380;15#65380;25時的分割結果，(a)~(c)三幅未作峰值增強，(d)~(f)為對應峰值增強后的結果。隨著填充閾值的提高，無論是否經過峰值增強，分割塊數均呈逐漸減少態勢。相同閾值條件下，可以看出圖中在安全帽左邊緣#65380;右側肩部上沿以及人物五官等部位，未作峰值增強的結果明顯出現關鍵輪廓的偏離或缺失現象，而經過峰值增強后的結果則較好地保留住了這些峰值對應的輪廓。

6結束語

從實驗結果可以看出，本文的方案通過對梯度圖像進行谷底填充和峰值增強等步驟的調整，使watershed分割結果中的過分割現象得到明顯改善，分割出的區域輪廓與目標邊緣的擬合程度也得到了一定程度的提高。與此同時，本方案還通過調整谷底填充閾值達到了控制最終分割區域塊數的目的，這一特性為分割過程中對分割效果的控制留出了人工干預接口，可以人為地調整分割深度以適用于不同的應用場合。另外，在特定應用場景中，若需要實現脫離人工督導的完全自動分割，還需要根據圖片的尺寸#65380;復雜程度等信息，引入機器學習理論實現填充閾值的自適應調整，這將是本文后續工作中需要進一步深入研究的課題。

參考文獻:

[1]VINCENT L， SOILLE P. Watersheds in digital spaces: an efficient algorithm based on immersion simulations[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1991，13(6):583－598.

[2]WANG De－min. Unsupervised video segmentation based on watersheds and temporal tracking[J]. IEEE Trans on Circuits and Systems for Video Technology， 1998，8(5):539－546.

[3]盧官明.一種計算圖像形態梯度的多尺度算法[J].中國圖象圖形學報，2001，6(3):214－218.

[4]王小鵬，郝重陽，樊養余.基于形態學尺度空間和梯度修正的分水嶺分割[J].電子與信息學報，2006，28(3):485－489.

[5]羅希平，田捷，諸葛嬰.圖像分割方法綜述[J].模式識別與人工智能，1999，12(3):300－312.

[6]CANNY J. A computational approach to edge detection[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1986，8(6):678－698.

[7]NAJWA V S. On detecting edges[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1986，8(6):699－714.

[8]林開顏，吳軍輝，徐立鴻.彩色圖像分割方法綜述[J].中國圖象圖形學報，2005，10(1):1－10.

[9]TANCHAROEN D， JITAPUNKUL S. Spatial segmentation based on modified morphological tools[J]. IEEE Conference Information Technology， 2001，9(1):478－482.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”