一種圖像分割的快速不動點算法

李偉斌 易 賢 宋松和

?

一種圖像分割的快速不動點算法

李偉斌*①②易 賢②宋松和③

①(中國空氣動力研究與發展中心空氣動力學國家重點實驗室 綿陽 621000)②(中國空氣動力研究與發展中心計算空氣動力研究所 綿陽 621000)③(國防科學技術大學理學院 長沙 410073)

該文在去除背景便能獲得目標的分割思想之上，提出了一個凸的無約束最小化問題。證明了問題提出過程中添加懲罰項的合理性，并通過實驗驗證了證明結果。在最小化求解方面，應用次微分和近似算子的相關理論，構造了求解的不動點算子，進而結合Opial-averaged定理，給出了求解所提凸優化問題的不動點算法，并理論推導出了收斂條件，證明了算法的收斂性。與經典文獻方法的對比實驗表明所提方法分割結果更精確。同時實驗顯示該文算法比梯度下降法和分裂Bregman方法更快速。另外，所提算法對初始曲線和噪聲有較好的魯棒性。

圖像處理；圖像分割；凸優化問題；不動點算法

1 引言

圖像分割的任務是將一幅數字圖像劃分為多個互不相交的區域，每個區域具有某些視覺的共性，如顏色、亮度、紋理等。圖像分割通常是用來確定物體位置或邊界，已被廣泛應用于天文、軍事、醫學等方面。近年來，圖像分割方法層出不窮，且都取得了很好的分割效果。其中，變分方法憑借其理論的成熟性，更是成為了圖像分割方法研究的熱點。

變分圖像分割模型的主要做法是從一定的分割思想入手，構造相應的能量泛函，進而應用優化技術對其最小化，由最小化過程得到的最優解便可給出最終的圖像分割結果。大多數變分模型對應的能量函數是非凸構造的，這就導致分割結果過多地依賴于初始曲線的位置，有可能使得最終的演化曲線停留在離初始曲線較近、離目標較遠的位置，即產生局部極小值的問題。文獻[5]從Heaviside函數的近似入手，提出了一種凸的能量泛函，并應用梯度下降方法對其進行求解，實驗表明這種算法能準確得到圖像分割的全局解。針對凸能量泛函的最小化問題，各種優化方法層出不窮，應用最廣的當屬近年來出現的分裂Bregman方法[7]，該方法通過引入兩個變量，用來避開長度項的直接計算，從而達到快速演化的目的。2011年，Micchelli等人[8]提出了基于不動點算法的圖像去噪模型，并給出了算法的收斂性證明。

本文在文獻[5]基礎上，通過添加凸懲罰項，提出了一種改進的凸能量泛函，并證明了懲罰項加入的合理性。進而，結合次微分算子和近似算子相關理論，給出了最小化該凸能量泛函的不動點算法，證明了算法的收斂性。與經典模型和算法的對比實驗表明本文方法能更快速準確得到分割結果，且對噪聲和初始曲線具有較好的魯棒性。

2 模型的提出

2.1 背景知識

背景去除模型[5]是基于區域的分割模型，它對含有模糊邊界或噪聲的圖像具有更強魯棒性。背景去除模型關注的是背景區域，旨在從圖像中分離出背景區域。一般地，背景區域可以理解為圖像中由灰度值相同(或相近)的像素點組成的最大區域。從該角度出發，背景去除模型的主要任務就是找出在灰度值相同(或相近)前提下，面積盡可能大的區域。

自然圖像里各區域的灰度值很難達到同一化，因此式(1)中的約束條件很難滿足，應用Lagrange乘子法弱化該約束條件。引入水平集函數[9]，將外部區域表征為，同時再應用Heaviside函數：

便可結合Lagrange乘子法由問題式(1)得到背景去除模型的能量泛函：

2.2 凸能量函數的提出

在文獻[5]中，求解所提出的最小化問題式(3)使用的是較慢的梯度下降法。本文為了構造快速算法，在問題式(3)的基礎上，為了去掉限制條件，引入凸的懲罰項，得到最小化問題：

定理1 給定以下兩個迭代序列：

證明 證明主要分兩部分：(1)迭代序列存在極限；(2)定理結論。

最后是五六條家鄉的野魚——麥穗魚，不成風景，喧鬧地追來追去。我也沒在意，隔三差五，就有一條翻起白肚皮。兩個月后，水安靜了，也空了。

3 不動點算法

定義1[10]若函數是凸的，定義其在處的次微分算子為

為

這里使用到了次微分的鏈式法則[11]：，其中算子對應著散度算子。因為是凸函數，且是可導的，因此，記，則式(7)可以轉化為

證明 結論可以分別通過式(7)至式(11)的正推和逆推過程得到。

證畢

4 數值實驗

這一節將本文方法與經典文獻中的方法進行了對比實驗，并將所提不動點算法與梯度下降法、分裂Bregman算法進行了比較。另外，還討論了本文方法對初始曲線魯棒性和噪聲圖像的適用性，同時驗證了定理1的結論。為了便于參數設置，本文將測試圖像的灰度值域由[0,255]線性變換為[0,1]，參數默認選取為,和，其他參數在每個實驗中獨立給出。

圖1是對文獻[13~15]與本文方法的分割結果對比。測試圖像均取自Weizmann圖像庫[16]，其中第1列為該數據庫中的人工分割結果，第2至4列分別為文獻[13~15]的分割結果，第5列為本文方法分割結果。從圖1(a)的標準可以看出，最理想的結果是將圖像中兩個宏觀目標全部完整從背景中分割出去。從圖中對比結果可知，文獻[13~15]的方法并未能完整地給出正確結果，比如船槳、人形、牛額頭和犄角等，這是由于這3種分割方法太過依賴圖像的灰度信息，忽視了區域的完整性。而本文方法旨在從圖像中分離背景區域，從而得到分割結果，因此給出了較準確的結果。從上至下，本文方法的參數為和。

圖2是文獻[5]與本文方法在特定步的分割結果對比，并且給出了相應的CPU時間。兩種方法均采用同樣的初始曲線，第1行和第2行分別是文獻[5]和本文方法的分割結果。從第1列和第2列可以看出，當迭代進行10步之內時，文獻[5]方法的演化曲線變化較小，而本文方法已給出較準確的分割結果；同時從第3列對比結果可以得出，本文方法在30步之前就已收斂，而文獻[5]的分割結果中還有較多由噪聲影響產生的小曲線。另外，從迭代步數所用的CPU時間可以看出，本文方法每一迭代步所用的時間較短。綜上，本文方法相比于文獻[5]可以在較短時間、較少迭代步數內取得正確分割結果，具有較高的分割效率。

為了驗證不動點算法的快速準確性，本文將其與梯度下降方法和分裂Bregman方法進行對比試驗。其中，梯度下降方法、分裂Bregman方法和不動點算法分別對式(2)，式(3)和式(4)進行最小化求解，而式(3)和式(4)均是基于式(2)提出的，因此它們的最小化問題是相同的。圖3中的實驗圖像仍然選自Weizmann圖像庫，對比參數為迭代所用CPU時間和分割指標DSC(Dice Similarity Coefficient)，DSC是衡量分割準確度的測度，它的表達式為：

圖1 自然圖像分割結果對比

圖2 文獻[5](第1行)與本文方法(第2行)特定迭代步分割結果比較

圖3 梯度下降方法、分裂Bregman方法和不動點算法對比

為了構造本文的快速算法，在由提出能量泛函時，加入了凸的懲罰項，用于去掉的約束條件。定理1中已給出了情況下，加入該懲罰項的合理性。為了更進一步說明懲罰項加入的正確性，從實驗角度對其進行驗證。主要驗證的是定理1的兩個結論：對于任意的，有;。考慮圖4(a)的初始情況，在圖5(a)中給出了最大值和最小值關于迭代步數的曲線圖，從圖中可以看出，其始終滿足的論斷，即本文加入懲罰項的凸能量泛函隱含著的約束條件，這就使得問題的本質(式(3))沒有發生變化。圖5(b)中給出了迭代500步后的直方圖，從直方圖可以看出其大部分取值集中在0附近，也就是說近似滿足的論斷，沒有全部為0的主要原因是定理給出的是長度項權重情況下的證明，而該實驗中。

圖4 不同初始曲線下的分割結果

圖6中給出了本文算法對噪聲圖像的分割結果，其中第1行是添加了0均值Gauss噪聲的圖像，標準差分別為，第2行是對應的分割結果。從圖6(a)可以看出，本文算法準確給出了兩個物體的邊緣，由于圖像中不含噪聲，曲線長度項系數選擇較小，即為默認。從圖6(b)到6(d)可以看出，針對噪聲圖像，本文算法仍然取得了較好的分割結果，但是隨著噪聲的增強，長度項系數變大，這使得算法不能較精確地給出小目標的邊緣位置，如圖6(d)左上角的分割結果。

圖5 圖4(a)情況定量分析

圖6 噪聲圖像分割結果

5 結束語

本文在前期的工作基礎之上，通過添加凸的懲罰項，提出了一個不帶約束條件的凸最小化問題，并證明了該問題與原問題的等價性，在實驗部分，定量驗證了等價性結論。在求解方面，本文應用次微分和近似算子的相關理論，給出了最小化所提問題的不動點算法，并證明了算法的收斂性。實驗表明本文分割方法快速準確，對初始曲線選擇無依賴，具有一定的抗噪性。

[1] Zhu W, Tai X, and Chan T. Image segmentation using Euler’s Elastica as the regularization[J]., 2013, 15(2): 414-438.

[2] Yuan J, Bae E, Tai X,.. A spatially continuous max-flow and min-cut framework for binary labeling problems[J]., 2014, 126(3): 559-587.

[3] 張澤均, 水鵬朗. 一種新的基于網格編碼和區域合并的SAR圖像快速分割算法[J]. 電子與信息學報, 2014, 36(4): 974-980.

Zhang Ze-jun and Shui Peng-lang. A new fast SAR image segmentation algorithm based on grid coding and region merging[J].&, 2014, 36(4): 974-980.

[4] 趙雪梅, 李玉, 趙泉華. 結合高斯回歸模型和隱馬爾可夫隨機場的模糊聚類圖像分割[J]. 電子與信息學報, 2014, 36(11): 2730-2736.

Zhao Xue-mei, Li Yu, and Zhao Quan-hua. Image segmentation by fuzzy clustering algorithm combining hidden Markov random field and Gaussian regression model[J].&, 2014, 36(11): 2730-2736.

[5] 李偉斌, 高二, 宋松和. 一種全局最小化的圖像分割方法[J]. 電子與信息學報, 2013, 35(4): 791-796.

Li Wei-bin, Gao Er, and Song Song-he. A global minimization method for image segmentation[J].&, 2013, 35(4): 791-796.

[6] Li Wei-bin, Song Song-he, and Luo Feng. Fast image segmentation by convex minimisation and split Bregman method[J]., 2013, 49(17): 1073-1074.

[7] Goldstein T and Osher S. The split Bregman method for 1 regularized problems[J]., 2008, 2(2): 323-343.

[8] Micchelli C, Shen L, and Xu Y. Proximity algorithms for image models: denosing[J]., 2011, 27(4): 45009-45038.

[9] Osher S and Fedkiw R. Level Sset Methods and Dynamic Implicit Surfaces[M]. New York: Springer Verlag, 2002: 4-22.

[10] Bertsekas D. Nonlinear Programming[M]. Belmont: Athena Scientific, 2003: 209-210.

[11] Z?linescu C. Convex Analysis in General Vector Spaces[M]. River Edge: World Scientific, 2002: 79-88.

[12] Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings[J]., 1967, 73: 591-597.

[13] Chan T, Esedoglu S, and Nikolova M. Algorithms for finding global minimizers of image segmentation and denoising models[J]., 2006, 66(5): 1632-1648.

[14] Bresson X, Esedoglu S, Vandergheynst P,..Fast global minimization of the active contour/snake models[J]., 2007, 28(2): 151-167.

[15] Goldstein T, Bresson X, and Osher S. Geometric applications of the split Bregman method: segmentation and surface reconstruction[J]., 2010, 45(1-3): 272-293.

[16] Alpert S, Galun M, Basri R,. Image segmentation by probabilistic bottom-up aggregation and cue integration[C]. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, 2007: 1-8.

Fast Fixed-point Algorithm for Image Segmentation

Li Wei-bin①②Yi Xian②Song Song-he③

①(,,621000,)②(,,621000,)③(,,410073,)

Based on the idea that objects in a given image can be segmented by -----removing the background part, an unconstrained convex minimization problem is proposed. The penalization term added in the construction procedure of the proposed problem is proven to be viable, which is demonstrated by the experiment. At the computational level, a fixed-point operator and the corresponding algorithm are proposed by applying the theory of subdifferential and proximity operators, and Opial-averaged theorem. And then the convergence proof of the algorithm is given. Comparisons with other classical models show that the proposed segmentation model is more accurate. And the experiments also demonstrate that the fixed-point algorithm is faster than the gradient descent method and the split Bregman method. Moreover, the algorithm is robust to the initial curve and noise.

Image processing; Image segmentation; Convex optimization; Fixed-point algorithm

TN911.73

A

1009-5896(2015)10-2390-07

10.11999/JEIT150112

2015-01-20；改回日期：2015-05-11；

2015-07-06

李偉斌 liweibin@nudt.edu.cn

國家自然科學基金(11172314)

The National Natural Science Foundation of China (11172314)

李偉斌： 男，1985年生，實習研究員，博士，主要研究方向為圖像分割、變分方法和PDE方法.

易 賢： 男，1977年生，副研究員，主要研究方向為飛機結冰數值模擬和試驗技術.

宋松和： 男，1965年生，教授，博士生導師，主要研究方向為PDE方法、圖像處理和辛算法.