一種基于MRF與區(qū)域合并的圖像分割改進算法

王國良，任允帥

一種基于MRF與區(qū)域合并的圖像分割改進算法

王國良，任允帥

（遼寧石油化工大學(xué) 信息與控制工程學(xué)院，遼寧 撫順 113001）

針對現(xiàn)有基于馬爾科夫隨機場的圖像分割算法容易出現(xiàn)過分割、分割結(jié)果不理想等問題，提出了一種基于馬爾科夫隨機場與區(qū)域合并的圖像分割改進算法。該算法首先基于馬爾科夫隨機場與高斯混合模型理論的圖像分割算法得到初始分割結(jié)果；然后利用各個區(qū)域間的相鄰關(guān)系、顏色關(guān)系以及邊界情況等信息，給出各個區(qū)域間的距離；最后按照區(qū)域間的距離與區(qū)域合并前后的顏色散度變化率對初始分割結(jié)果進行區(qū)域合并，輸出最終的分割結(jié)果。使用伯克利標準圖像庫進行實驗仿真，采用Dice系數(shù)和Jaccard系數(shù)作為評價指標。仿真結(jié)果表明，相比于現(xiàn)有基于MRF理論的算法，本文算法具有更好的分割效果。

圖像分割； 馬爾科夫隨機場； 高斯混合模型； 區(qū)域合并

圖像分割是圖像處理領(lǐng)域的熱門問題，是計算機對圖像進一步處理的關(guān)鍵步驟[1]。圖像分割是將圖像劃分為多個具有某種特定性質(zhì)的子區(qū)域的過程，相同的子區(qū)域間具有相同或相似的物理特性。目前常用的圖像分割方法有閾值分割法、區(qū)域分割法、聚類分割法和基于某種特定理論的圖像分割算法等。

基于-means的圖像分割算法是一種聚類分割的算法，其原理簡單，容易實現(xiàn)，被廣泛應(yīng)用于圖像分割[2-4]。但是,這種無監(jiān)督聚類分析法在聚類時未考慮圖像的空間信息，分割結(jié)果易受噪聲點影響。為解決噪聲點的問題，通常加入特定的方法對-means算法進行約束[5]。馬爾科夫隨機場（MRF）模型[6-13]具有嚴格的理論基礎(chǔ)，在圖像分割領(lǐng)域得到廣泛的應(yīng)用。MRF理論本身不具有分割作用，但可以與特定的分割算法相結(jié)合。MRF理論的引入為-means算法帶來空間約束性，提高分割算法的抗噪性能。近年來，MRF理論在圖像分割領(lǐng)域快速發(fā)展。徐迪[12]提出使用模擬淬火法的馬爾科夫分割算法，解決馬爾科夫圖像分割算法的局部最優(yōu)解問題。祖成玉[13]提出基于鄰域統(tǒng)計的MRF圖像分割算法，通過改變馬爾科夫隨機場模型，一定程度上解決了圖像分割中的過分割現(xiàn)象，但也因此增加了分割算法的計算難度。

由于圖像中各個區(qū)域之間存在相似的物理特性，現(xiàn)有常用的基于-means和MRF理論的圖像分割算法極易受這些物理相似性的干擾，從而導(dǎo)致分割結(jié)果不夠理想。針對這個問題，本文提出了一種將MRF理論與區(qū)域合并相結(jié)合的圖像分割算法。首先基于MRF理論的分割算法得到初始分割結(jié)果，然后利用區(qū)域合并策略對初始分割結(jié)果進行修正，輸出最終的圖像分割結(jié)果。相較于對比算法，本文算法可以更好地處理圖像分割中的過分割問題，提高圖像的分割精度。

1 算法及原理

本文算法主要分為兩個部分：初始分割部分，使用帶有高斯混合模型的馬爾科夫最大后驗概率（MRF-MAP）算法得到；區(qū)域合并部分，綜合考慮各個區(qū)域間的相似程度和相鄰關(guān)系等信息，按照區(qū)域合并策略對初始分割結(jié)果進行區(qū)域合并，最后輸出最終的分割結(jié)果。

1.1 MRF-MAP算法概述

馬爾科夫隨機場是基于概率統(tǒng)計的圖像分割模型。使用馬爾科夫隨機場對圖像建模時，將直接觀察到的實際圖像設(shè)為觀測場，在實際圖像對應(yīng)的位置建立一個標簽場，標簽場中的標簽即是圖像分割的結(jié)果。

進而圖像分割問題轉(zhuǎn)化為式（3）最優(yōu)化問題：

式中，為所有雙點勢團的集合。

由式（4）、（5）和式（7）可得：

1.2 基于GMM的MRF-MAP算法概述

對式（11）取對數(shù)，得：

式（12）取得最大值時GMM的參數(shù)最優(yōu)，且滿足：

一般情況下使用EM算法估計GMM的參數(shù)。使用式（11）高斯混合模型代替單一高斯分布，式（10）可以更改為：

由式（2）、式（9）和式（14）可得：

對式（15）取對數(shù)，得：

最優(yōu)化問題被轉(zhuǎn)換成式（16）能量最小化問題。利用標簽場能量和觀測場能量間的約束關(guān)系，根據(jù)貝葉斯準則得到分割結(jié)果。

GMM的處理對象是觀測場的像素值，因此易受噪聲點干擾，MRF理論可以刻畫各種物理現(xiàn)象的空間相關(guān)性，兩個理論非常適于結(jié)合使用，MRF理論引入先驗知識，可以求解先驗概率。GMM可以求解似然概率，兩者借助貝葉斯理論結(jié)合使用。根據(jù)最大后驗概率求解，即可確定像素的所屬標簽。

使用MRF和GMM可以得到一個較為精確的分割結(jié)果，但是當(dāng)圖像中的干擾區(qū)域較大時，分割結(jié)果的過分割現(xiàn)象依然存在。單純改進MRF和GMM的相應(yīng)參數(shù)常會出現(xiàn)減少過分割現(xiàn)象的同時，也破壞了分割目標主體的情況。為此本文引入?yún)^(qū)域合并思想，從另一種角度來改進分割結(jié)果。

1.3 區(qū)域合并

區(qū)域合并是實現(xiàn)更加精細化圖像分割的一種方法，這種方法的優(yōu)點在于充分考慮區(qū)域間的空間位置關(guān)系，降低像素值對于圖像分割的約束。本文算法借鑒文獻[21]的層次合并法對初始分割進行區(qū)域合并。

1.3.1區(qū)域相似性 區(qū)域間的相似性是兩個區(qū)域進行合并的重要依據(jù)[22]，本文采用區(qū)域距離對區(qū)域之間的相似性進行量化。

在進行區(qū)域合并時，兩個區(qū)域是否可以合并需要考慮兩個區(qū)域是否相鄰，只有相鄰的區(qū)域才可以考慮合并；兩個區(qū)域的顏色是否接近，只有顏色接近的兩個區(qū)域才可能進行合并；兩個區(qū)域相鄰的位置是否存在邊界，沒有邊界的兩個區(qū)域才可能進行合并。本文依據(jù)上述條件來定義區(qū)域間的相似性。

（1）為了理清區(qū)域間的相鄰關(guān)系邏輯，建立合理的相鄰關(guān)系表達式。區(qū)域相鄰關(guān)系如圖1所示。

圖1　區(qū)域相鄰關(guān)系

圖1（a）為圖像實際區(qū)域相鄰關(guān)系圖，圖中區(qū)域A1與區(qū)域A2、A3、A4相鄰。使用短線相連表示區(qū)域相鄰，得到簡化相鄰關(guān)系如圖1（b）所示。當(dāng)A2和A5滿足合并條件，區(qū)域合并后可以得到新的相鄰關(guān)系如圖1（c）所示。

通過圖（1）中的相鄰關(guān)系，建立區(qū)域相鄰關(guān)系表達式：

（2）本文定義了一個顏色距離函數(shù)，使用顏色距離表明兩個區(qū)域顏色的接近程度，其表達式為：

（3）當(dāng)圖像的兩個區(qū)域間存在邊界時，邊界兩側(cè)的顏色有明顯變化。按照這個邏輯，建立一個邊界距離關(guān)系式為：

按照上述邏輯關(guān)系整合上述三個函數(shù)關(guān)系式，得到一個綜合的區(qū)域間距離關(guān)系式為：

區(qū)域間距離越小，表明兩個區(qū)域間的差異越小，合并的可能性就越大。

1.3.2區(qū)域合并策略 使用基于GMM的MRF-MAP算法得到一個初始的分割結(jié)果，在初始分割結(jié)果的基礎(chǔ)上進行區(qū)域合并。區(qū)域合并的步驟為：

（1）標記區(qū)域間的相鄰關(guān)系。根據(jù)相鄰關(guān)系式（19）可得不同區(qū)域間的相鄰情況。

（2）減少合并區(qū)域的數(shù)目。圖像經(jīng)初始分割后，分割結(jié)果中容易出現(xiàn)由噪聲點引起的面積很小的干擾區(qū)域。為減少運算量，可以通過設(shè)置一個面積閾值，將面積很小的區(qū)域合并到其相鄰區(qū)域。

（3）計算區(qū)域間的距離，合并區(qū)域間距離最小的兩個區(qū)域。區(qū)域的數(shù)目、區(qū)域間的相鄰關(guān)系和區(qū)域間的距離將會在區(qū)域合并后發(fā)生改變。因此，算法要重新返回到第一步和第二步。合并算法要在第一步到第三步間不斷循環(huán)，更新分割結(jié)果，直到分割算法達到合并截止的條件，結(jié)束循環(huán)輸出最終的分割結(jié)果。

1.3.3區(qū)域合并截止 設(shè)置合并策略后，還需要設(shè)置一個合并截止條件。本文使用顏色散度作為合并截止的條件，將圖片中不同區(qū)域間顏色不統(tǒng)一程度的總和定義為顏色散度，其表達式為：

區(qū)域合并會改變圖像的整體顏色散度。當(dāng)區(qū)域合并前后的顏色散度變化較大時，說明區(qū)域合并導(dǎo)致了區(qū)域之間的不統(tǒng)一程度加大，應(yīng)停止區(qū)域合并。

只使用顏色散度變化作為停止區(qū)域合并的條件不夠全面。為此，本文考慮將顏色散度與區(qū)域合并后區(qū)域的數(shù)目相結(jié)合，定義一個新的合并截止條件，即顏色散度變化率，其表達式為：

當(dāng)區(qū)域在合并前后顏色散度變化率出現(xiàn)明顯時，認為合并算法停止，輸出最終的分割結(jié)果。

本文算法流程如圖2所示。

圖2　本文算法流程

2 實驗與仿真

2.1 實驗結(jié)果對比分析

本文算法與-means算法[3]、傳統(tǒng)MRF算法[12]、基于GMM的MRF算法[19]進行仿真對比。海星、雙馬圖像不同算法的仿真結(jié)果如圖3所示。其中，人工分割為標準分割結(jié)果。

圖3（b）中，由于海星圖草地背景部分像素值接近海星主體，草地背景區(qū)出現(xiàn)較大誤判情況；圖3（c）結(jié)果相比于圖3（b）海星目標主體得到較為完整的分割，但分割結(jié)果中出現(xiàn)很多噪聲點，同時其右下角的草地背景過分割加重；圖3（d）海星目標主體邊緣更加清晰，背景區(qū)域的誤分割情況減弱，分割圖左側(cè)和下方仍有小塊區(qū)域過分割給海星；圖3（e）結(jié)果中，本文算法最大程度保證了目標區(qū)域的完整性，同時去掉了過分割區(qū)域，使分割結(jié)果更加趨向于標準結(jié)果。雙馬圖與海星圖分割結(jié)果相似，本文算法分割結(jié)果優(yōu)于其他算法。

使用背景復(fù)雜的圖像來進一步驗證算法的可行性。水牛、青蛇圖像不同算法的仿真結(jié)果如圖4所示。

從圖4可以看出，由于水牛、青蛇圖片背景較為復(fù)雜，使用-means算法得到的結(jié)果圖4（b）受到背景干擾像素的影響，出現(xiàn)了大片的誤分割區(qū)域。MRF理論的引入帶來了空間約束，一定程度降低了噪聲點影響，但在圖4（c）分割結(jié)果仍然存在面積較大的誤分割區(qū)域和較多的噪聲點。圖4（d）水牛、青蛇主體的連通性增強，誤分割情況減弱，但仍然存在大量難以去掉的誤分割區(qū)域。與其他算法相比，圖4（e）分割結(jié)果提高了分割目標主體連通性，去除了其他算法難以除去的噪聲點，與人工分割結(jié)果最為接近。本文算法結(jié)合了MRF和GMM的優(yōu)點，加入?yún)^(qū)域合并策略，利用圖像顏色散度等概念，進一步消除了圖像分割中的過分割區(qū)域，提升了算法的分割效果。

2.2 算法性能對比分析

為更加客觀地評價本文分割算法的分割性能，使用定量的指標給出精確評價。由于目前圖像分割的評價方法尚不統(tǒng)一，本文選用Dice系數(shù)[23]和Jaccard系數(shù)[24]作為評價本文算法分割性能的指標。

Dice系數(shù)是一種集合相似度度量指標，用于計算兩個集合間的相似度，取值為0～1。分割結(jié)果最佳時取1，結(jié)果最差時取0。Dice系數(shù)的表達式為：

Jaccard系數(shù)是衡量兩個集合之間區(qū)分度的度量指標，與Dice系數(shù)相似，Jaccard系數(shù)越大，兩個樣本就越相似。Jaccard系數(shù)的表達式為：

海星、雙馬圖像不同算法的評價結(jié)果如表1所示。從表1可以看出，-means算法得到的結(jié)果與人工分割結(jié)果（Dice系數(shù)、Jaccard系數(shù)均為1.000 0）相差最大，分割效果最差。使用MRF理論與高斯混合模型的圖像分割算法，Dice指標和Jaccard指標相比-means算法都有較大的提升，這也說明了MRF理論和高斯混合模型結(jié)合使用對于圖像分割起到了重要的作用。加入?yún)^(qū)域合并策略的本文算法與其他算法相比，無論是Dice系數(shù)還是Jaccard系數(shù)都是所有分割算法中最高的，這說明本文算法得到的分割結(jié)果與人工分割結(jié)果最為接近，分割效果最好。

表1　海星、雙馬圖像不同算法的評價結(jié)果

水牛、青蛇圖像不同算法的評價結(jié)果如表2所示。從表2可以看出，除本文算法外其他算法都不能很好地將目標主體從背景中分離，本文算法的Dice系數(shù)和Jaccard系數(shù)最大，相比其他算法，本文算法的Dice和Jaccard數(shù)據(jù)增幅明顯。這表明本文算法的分割效果優(yōu)于其他算法。

3 結(jié) 論

基于馬爾科夫隨機場與區(qū)域合并的圖像分割改進算法，使用高斯混合模型的高斯分量進行像素值擬合，對觀測場建模；使用馬爾科夫模型求解先驗概率，對標簽場建模。利用貝葉斯準則將高斯混合模型與馬爾科夫模型相結(jié)合，得到初始分割結(jié)果。利用區(qū)域合并的思想對初始分割結(jié)果進行更新修正，輸出最終的分割結(jié)果。由于Markov和區(qū)域合并的空間約束性，一定程度上改進了現(xiàn)有MRF算法的過分割現(xiàn)象。該算法的分割結(jié)果與人工分割結(jié)果最為接近，這也驗證了本文算法的可行性。

表2　水牛、青蛇圖像不同算法的評價結(jié)果

［1］陶啟放.基于Markov隨機場的機器視覺設(shè)計及應(yīng)用［D］.成都：電子科技大學(xué)，2018．

［2］劉長齊，邵堃，霍星，等.基于加權(quán)質(zhì)量評價函數(shù)的-means圖像分割算法［J］.計算機科學(xué)，2019，46（S1）：158-160．

［3］Moftah H M，Azar A T， et al . Adaptive-means clustering algorithm for MR breast image segmentation［J］. Neural Computing and Applications， 2014， 24（8）：1917-1928.

［4］Macqueen J. Some methods for classification and analysis of multivariate observations［C］//Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. California： University of California Press， 1967.

［5］彭代強，李家強，林幼權(quán).基于模糊隸屬度空間約束的FCM圖像分割［J］.計算機科學(xué)，2010，37（10）：257-259．

［6］朱瑤.基于馬爾科夫隨機場模型的圖像分割算法研究［D］.哈爾濱：哈爾濱工程大學(xué)，2014．

［7］肖然，侯進.基于馬爾科夫模型的多分辨率圖像分割算法［J］.計算機工程，2012，38（16）：223-232．

［8］徐勝軍，韓九強，劉光輝.基于馬爾科夫隨機場的圖像分割方法綜述［J］.計算機應(yīng)用研究，2013，30（9）：2576-2582．

［9］劉磊，石志國，宿浩茹，等.基于高階馬爾科夫隨機場的圖像分割［J］.計算機研究與發(fā)展，2013，50（9）：1933-1941．

［10］ Kumar M P， Torr P， Zisserman A. Solving markov random fields using second order cone programming relaxations ［C］//2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR'06）. New York： IEEE Presss， 2006.

［11］ 劉光輝，任慶昌，孟月波，等.自適應(yīng)先驗馬爾可夫隨機場模型的圖像分割算法［J］.西安交通大學(xué)學(xué)報，2013，47（10）：62-67.

［12］ 徐迪.馬爾科夫隨機場在圖像分割方法中的應(yīng)用研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2013．

［13］ 祖成玉.基于鄰域統(tǒng)計特征MRF的圖像分割算法［D］.大連：大連海事大學(xué)，2018．

［14］ Smith G B. Stochastic relaxation， gibbs distributions and the bayesian restoration of images［J］.IEEE Trans. Pattern Anal.1984， 26（9）：721-741．

［15］ Zhang Y， Smith S， Brady M. Hidden markov random field model and segmentation of brain MR images［J］. Proceedings of SPIE-The International Society for Optical Engineering， 2000， 20：45-57.

［16］ 楊俊，李娜，李遲遲，等.基于高斯混合模型和馬爾科夫隨機場的腦MR圖像分割［J］.解剖學(xué)研究，2018，40（5）：425-429．

［17］ Melas D，Wilson S. Double markov random fields and bayesian image segmentation［J］. IEEE Trans.on Signal Processing， 2002， 50： 357-365．

［18］ 柴五一，楊豐，袁紹鋒，等.用于圖像分割的多分類高斯混合模型和基于鄰域信息的高斯混合模型［J］.計算機科學(xué)，2018，45（11）：272-277．

［19］ Wang Q. Implementation of the hidden markov random field model and its expectation-maximization algorithm［EB/OL］. （2012-12-18）［2020-07-30］. http：//export.arxiv.org/pdf/1207.3510.pdf，

［20］ 標本，梁愷彬，管一弘.高斯馬爾科夫隨機場的人腦MR圖像分割方法［J］.計算機技術(shù)與發(fā)展，2017，27（7）：180-184．

［21］ 吳倩倩.基于聚類與區(qū)域合并的彩色圖像分割算法的研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2017.

［22］ 胡學(xué)剛，段瑤，嚴思奇.基于區(qū)域合并的FCM圖像分割改進算法［J］.小型微型計算機系統(tǒng)，2018，39（9）：2077-2080．

［23］ Dice L R. Measures of the amount of ecologic association between species［J］. Ecology， 1945， 26（3）： 297-302.

［24］ Jaccard P. The distribution of the flora in the alpine zone［J］. New Phytologist， 1912， 11（2）： 37-50.

An Improved Image Segmentation Algorithm Based on MRF and Region Merging

Wang Guoliang， Ren Yunshuai

（School of Information and Control Engineering，Liaoning Petrochemical University，F(xiàn)ushun Liaoning 113001，China）

The existing image segmentation algorithms based on Markov random field are prone to over segmentation and the segmentation results are not ideal. This paper presents an improved image segmentation algorithm based on Markov random field and region merging. First, the algorithm uses the image segmentation algorithm based on the theory of Markov random field and Gaussian mixture model to get the initial segmentation results; second, the region distance between each region is given by using the adjacent relationship, color relationship and boundary condition of each region; finally, the initial segmentation is performed according to the distance between regions and the change rate of color divergence after region merging. The final image segmentation results are output by region merging. In this paper, Berkeley standard image library is used for experimental simulation, and the Dice and Jaccard coefficients are used as the evaluation index of this paper. The experimental simulation shows that the proposed algorithm has better segmentation effect than the existing algorithm based on MRF theory.

Image segmentation； Markov random field； Gaussian mixture model； Region merging

TP37

A

10.3969/j.issn.1672-6952.2021.04.013

1672-6952（2021）04-0078-07

http：//journal.lnpu.edu.cn

2020-07-30

2020-09-18

國家自然科學(xué)基金項目（62073158、61473140）；遼寧省“興遼人才”支持計劃項目（XLYC1807030）；遼寧省“高校創(chuàng)新人才”計劃項目（LR2017029）；遼寧省教育廳科研基金項目（L2016024）。

王國良（1981-），男，博士，教授，從事Markov隨機過程的建模及應(yīng)用方面的研究；E-mail：glwang@lnpu.edu.cn。

（編輯 陳 雷）