基于马尔可夫随机场的图像分割研究
|
摘要
图像分割是计算机视觉中的关键技术之一。基于马尔可夫随机场(Markov RandomField,MRF)模型的图像分割方法,是一种基于统计的分割方法,具有能充分利用先验知识,能形成闭合的边界,模型参数少且易于和其他方法相结合等优点,所以此方法在图像分割领域中得到了广泛的应用。
本文研究了基于MRF的图像分割算法,重点研究了基于MRF的图像分割模型中的参数估计方法,以及MRF中的最大后验概率(Maximum A Posteriori,MAP)问题的求解方法。
首先,研究了MRF中MAP问题的求解方法。为提高传统的模拟退火(SimulatedAnnealing,SA)算法求解MAP问题的速度,在SA算法基础上提出了一种基于振动点的SA算法。在初始分割后,将图像的像素点分为两类:振动点和稳定点,并借助链表的数据结构存储振动点,每次迭代只对链表里面的振动点进行计算,以减少运算量。另外,本文还对SA算法的停步准则进行了改进,避免了全局能量的计算。实验表明这种基于振动点的改进SA算法在不影响分割效果的前提下,大幅度提高了计算效率。
其次,研究了MRF中的参数估计方法。介绍了两种传统的参数估计方法:样本训练法和EM算法,并对两种方法进行了数值模拟和对比。然后,结合四叉树分解提出了一种新的非均匀MRF的耦合系数估计方法。实验表明,本文的估计方法较为准确,将它应用到图像分割中,能增强图像分割的自适应性,改善分割效果。
Image segmentation is one of key issues in computer vision. The image segmentation based on MRF model has received much appreciation, such as the ability to make use of prior knowledge, the ability to generate connected boundary, less parameter, can easily combine with other segmentation method. So the algorithm has widely used in the image segmentation field.
Image segmentation algorithm based on MRF is studied in this thesis, and especially two problems are discussed, that is the parameter estimation in MRF and the solving of the MAP problem in MRF.
Firstly, the MAP problem in MRF is discussed. A new SA algorithm based on vibrant points is presented to increase the speed of the traditional SA algorithm in solving the MAP problem. After the pre-segmentation of the image, image pixels are divided into two classes: the stable points and the vibrant points. The vibrant points are stored by a linked list. Only the vibrant points are dealt with in each iteration to reduce computation load. And then, the stop rule of the SA algorithm is also improved to avoid the computation of global energy. The experiment results indicate that the improved SA algorithm based on vibrant points can greatly improve the computational efficiency while maintaining the segmentation effect.
Secondly, the parameter estimation method in MRF is studied. Two traditional parameter estimation algorithms are introduced: the sample training algorithm and the EM algorithm, and then numerical experiments are done to compare with the two algorithms. Afterward, a novel estimate method based on quad-tree decomposing is proposed to estimate the isomorphic coefficients in inhomogeneous markov random field. The experiment results show that the isomorphic coefficient estimated by this algorithm can significantly improve the effect of the segmentation and the adaptability of the image segmentation algorithm.
本文研究了基于MRF的图像分割算法,重点研究了基于MRF的图像分割模型中的参数估计方法,以及MRF中的最大后验概率(Maximum A Posteriori,MAP)问题的求解方法。
首先,研究了MRF中MAP问题的求解方法。为提高传统的模拟退火(SimulatedAnnealing,SA)算法求解MAP问题的速度,在SA算法基础上提出了一种基于振动点的SA算法。在初始分割后,将图像的像素点分为两类:振动点和稳定点,并借助链表的数据结构存储振动点,每次迭代只对链表里面的振动点进行计算,以减少运算量。另外,本文还对SA算法的停步准则进行了改进,避免了全局能量的计算。实验表明这种基于振动点的改进SA算法在不影响分割效果的前提下,大幅度提高了计算效率。
其次,研究了MRF中的参数估计方法。介绍了两种传统的参数估计方法:样本训练法和EM算法,并对两种方法进行了数值模拟和对比。然后,结合四叉树分解提出了一种新的非均匀MRF的耦合系数估计方法。实验表明,本文的估计方法较为准确,将它应用到图像分割中,能增强图像分割的自适应性,改善分割效果。
Image segmentation is one of key issues in computer vision. The image segmentation based on MRF model has received much appreciation, such as the ability to make use of prior knowledge, the ability to generate connected boundary, less parameter, can easily combine with other segmentation method. So the algorithm has widely used in the image segmentation field.
Image segmentation algorithm based on MRF is studied in this thesis, and especially two problems are discussed, that is the parameter estimation in MRF and the solving of the MAP problem in MRF.
Firstly, the MAP problem in MRF is discussed. A new SA algorithm based on vibrant points is presented to increase the speed of the traditional SA algorithm in solving the MAP problem. After the pre-segmentation of the image, image pixels are divided into two classes: the stable points and the vibrant points. The vibrant points are stored by a linked list. Only the vibrant points are dealt with in each iteration to reduce computation load. And then, the stop rule of the SA algorithm is also improved to avoid the computation of global energy. The experiment results indicate that the improved SA algorithm based on vibrant points can greatly improve the computational efficiency while maintaining the segmentation effect.
Secondly, the parameter estimation method in MRF is studied. Two traditional parameter estimation algorithms are introduced: the sample training algorithm and the EM algorithm, and then numerical experiments are done to compare with the two algorithms. Afterward, a novel estimate method based on quad-tree decomposing is proposed to estimate the isomorphic coefficients in inhomogeneous markov random field. The experiment results show that the isomorphic coefficient estimated by this algorithm can significantly improve the effect of the segmentation and the adaptability of the image segmentation algorithm.
引文
[1]章毓晋.图像工程(上册)[M].北京:清华大学出版社,2005.
[2]Yongyue Zhang,Stephen Smith,aMichael Brady.Hidden markov random field model and segmentation of brain MR Images[M].FMRIB Technical Report TR00YZ1 Oxford University.2000.
[3]罗希平等.图像分割方法综述[J].模式识别与人工智能,1999,12(3):300-312.
[4]章毓晋.图像分割[M].北京:科学出版社,2001.
[5]张亶,陈刚.基于偏微分方程的图像处理[M].北京:高等教育出版社,2004.
[6]高秀娟.图像分割的理论、方法及应用[D].长春:吉林大学,2006.
[7]吴学明.图象分割的算法研究[D].成都:成都理工大学,2006.
[8]魏弘博,吕振肃等.图像分割技术纵览[[J].甘肃科学学报.2004,16(2):19-24.
[9]张兴峰,沈兰荪.图像分割技术研究[J].电路与系统学报.2004,9(2):92-99.
[10]赵荣椿,迟耀斌,朱重光.图像分割技术进展[J].中国体视学与图像分析.1998,3(3):121-128.
[11]杨新,李俊等.图像偏微分方程的原理与应用[M].上海:上海交通大学出版社,2003.
[12]Adalsteinsson D,Sethian J A.A fast level set method for propagating interface[J].Journal of Computational Physics,1995,118:269-277.
[13]Sethian J A.A fast marching'level set method for monotonically advancing fronts[J].In Proc.Nat.Ac.Science,1996,93:1591-1694.
[14]Malladi R,Sethian J A,Uemuri B C.Shape modeling with front propagation:a Level Set approach[J].IEEE Trans.On PAMI,1995,17(2):158-175.
[15]Alvarez L,Lions P L,Morel J M.Image selective smoothing and edge detection by nonlinear diffusion Ⅱ[J].SIAM Journal on Numerical Analysis,1992,29(3):849-866.
[16]Nikos Pamgios,Rachid Deriche.Geodesic Active Contours and Level Sets for the Detection and Tracking of Moving Objects[J].IEEE Trans.on pattern analysis and machine intelligence,2000,22(3):266-280.
[17]J.M.Hammersley,P.Clifford.Markov field on finite graphs and lattices.Unpublished manuscript,1971.
[18]曹健农.基于可分解马尔科夫网的图像分割方法研究[D].武汉:武汉大学,2005.
[19]G.R.Cross and A.K.Jain,Markov Random Field Texture Models[J].IEEE Trans.On Pattern Analysis and Machine Intelligence,1983,5:25-39.
[20]S.Geman.,D.Geman.Stochastic relaxation,Gibbs distribution,and Bayesian restoration of images[J].IEEE Trans,on Pattern analysis and Machine Intelligence,1984,6:721-741.
[21]黄宁,朱敏慧,张守融.一种采用高斯马尔可夫随机场模型的遥感图像分类方法[J].电子与信息学报,2003,25(1):50-53.
[22]E.Dubois,J.Konrad."Estimation of 2-D motion fields from image sequences with application to motion-compensated processing," in Motion Analysis and Image Sequence Processing[M].(M.Sezan and R.Lagendijk,eds.),Kluwer Academic Publishers,1993.
[23]H.Derin,W.Cole.Segmentation of textured images using Gibbs random fields[J].Computer Vision Graphics and Image Process,1986,35:72-98.
[24]Besag,J.Spatial interaction and the statistical analysis of lattice systems[J].Journal of the Royal Statistical Society,Series B,1985,36:192-236.
[25]Chellappa,R.Two-dimensional discrete Gaussian Markov random field models for image processing[C].(Kanal,L.N.and Rosenfeld,A.,eds.)Progress in Pattem Recognition,1985,2:79-112.
[26]J.Mao,AK Jain.Texture classification and segmentation using multiresolution simultaneous autoregressive models[J].Pattern Recognition,1992,25(2):173-188.
[27]E.Ising.Beitrag zur Theorie des Ferromagnetismus[J].Z.Phys.1925,31:253-258.
[28]Derin H,Elliott H.Modeling and segmentation of noisy and textured images using Gibbs random fields.IEEE Trans[J].Pattern Anal.Machine Intell,1987,9(1):39-55.
[29]Fwe J,Djuric P.Unsupervised vector image segmentation by a tree stucture-ICM algorithm[J].IEEE Trans.on Medical Imaging,MI,1996,15(6):871-881.
[30]Kirkpatrick S,Gelatt G D Jr,Vecchi M P.Optimization by simulated annealing[J].Science,1983,220(4598):671-680.
[31]McLachlan G J,Krishnan T.The EM Algorithm and Extensions[M].New York:Wiley,1997
[32]刘伟强,陈鸿,夏德深.基于马尔可夫随机场的快速图像分割[J].中国图像图形学报,2001,6A(3):228-233.
[33]M.Pawan Kumar,P.H.S.Torr,A.Zisserman.Solving Markov Random Fields using Second Cone Programming Relaxations[C].Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
[34]张鹏.Markov随机场在图像处理中应用的研究[D].武汉:华中科技大学,2005.
[35]张翠,郦苏丹,王正志.基于MRF场的SAR图像分割方法[J].遥感技术与应用,2001,16(1):66-68.
[36]J.Besag,On the Statistical Analysis of Dirty Pictures[J].Journal of the Royal Statistical Society,Series B 1986,6:259-302.
[37]刘岩.模拟退火算法的背景和单调升温的模拟退火算法.计算机研究与发[J].1996,33(1):4-10.
[38]李乔祥.数据结构与算法[M].北京:冶金工业出版社,2004.
[39]Bilmes J A.A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models[R].International Compute Science Institute,1997.
[40]D.B.Gu,J.X.Sun.EM image segmentation algorithm based on an inhomogeneous hidden MRF model[J].IEE Proc.-Vis.Image Signal Process,2005,152(2):184-190.
[41]程兵,王莹,郑南宁等.基于Markov随机场和FRAME模型的无监督图像分割[J].中国科学E辑, 2004,34(4):391-400.
[42]李水根.分形[M].北京:高等教育出版社,2005.
[43]D.E.Melas,S.P.Wilson.Double Markov random fields and Bayesian image segmentation[J].IEEE Trans.Signal Process.2002,50(2):357-365.
[44]Yong Xia,Dagan Feng,Rongchun Zhao.Adaptive Segmentation of Textured Images by Using the Coupled Markov Random Field Model[J].IEEE Transactions On Image Processing,2006,15(11):3559-3565.
[45]F.C.Jeng,J.W.Woods.Compound Gauss-Markov random fields for image segmentation[J].IEEE Trans.Signal Process,1991,39(3),683-697.
[46]R.Molina,Mateos,A.Katsaggelos,M.Vega.Bayesian multichannel image restoration using compound Gauss-Markov random fields[J].IEEE Trans.Image Process,2003,12(12):1642-1654.
[2]Yongyue Zhang,Stephen Smith,aMichael Brady.Hidden markov random field model and segmentation of brain MR Images[M].FMRIB Technical Report TR00YZ1 Oxford University.2000.
[3]罗希平等.图像分割方法综述[J].模式识别与人工智能,1999,12(3):300-312.
[4]章毓晋.图像分割[M].北京:科学出版社,2001.
[5]张亶,陈刚.基于偏微分方程的图像处理[M].北京:高等教育出版社,2004.
[6]高秀娟.图像分割的理论、方法及应用[D].长春:吉林大学,2006.
[7]吴学明.图象分割的算法研究[D].成都:成都理工大学,2006.
[8]魏弘博,吕振肃等.图像分割技术纵览[[J].甘肃科学学报.2004,16(2):19-24.
[9]张兴峰,沈兰荪.图像分割技术研究[J].电路与系统学报.2004,9(2):92-99.
[10]赵荣椿,迟耀斌,朱重光.图像分割技术进展[J].中国体视学与图像分析.1998,3(3):121-128.
[11]杨新,李俊等.图像偏微分方程的原理与应用[M].上海:上海交通大学出版社,2003.
[12]Adalsteinsson D,Sethian J A.A fast level set method for propagating interface[J].Journal of Computational Physics,1995,118:269-277.
[13]Sethian J A.A fast marching'level set method for monotonically advancing fronts[J].In Proc.Nat.Ac.Science,1996,93:1591-1694.
[14]Malladi R,Sethian J A,Uemuri B C.Shape modeling with front propagation:a Level Set approach[J].IEEE Trans.On PAMI,1995,17(2):158-175.
[15]Alvarez L,Lions P L,Morel J M.Image selective smoothing and edge detection by nonlinear diffusion Ⅱ[J].SIAM Journal on Numerical Analysis,1992,29(3):849-866.
[16]Nikos Pamgios,Rachid Deriche.Geodesic Active Contours and Level Sets for the Detection and Tracking of Moving Objects[J].IEEE Trans.on pattern analysis and machine intelligence,2000,22(3):266-280.
[17]J.M.Hammersley,P.Clifford.Markov field on finite graphs and lattices.Unpublished manuscript,1971.
[18]曹健农.基于可分解马尔科夫网的图像分割方法研究[D].武汉:武汉大学,2005.
[19]G.R.Cross and A.K.Jain,Markov Random Field Texture Models[J].IEEE Trans.On Pattern Analysis and Machine Intelligence,1983,5:25-39.
[20]S.Geman.,D.Geman.Stochastic relaxation,Gibbs distribution,and Bayesian restoration of images[J].IEEE Trans,on Pattern analysis and Machine Intelligence,1984,6:721-741.
[21]黄宁,朱敏慧,张守融.一种采用高斯马尔可夫随机场模型的遥感图像分类方法[J].电子与信息学报,2003,25(1):50-53.
[22]E.Dubois,J.Konrad."Estimation of 2-D motion fields from image sequences with application to motion-compensated processing," in Motion Analysis and Image Sequence Processing[M].(M.Sezan and R.Lagendijk,eds.),Kluwer Academic Publishers,1993.
[23]H.Derin,W.Cole.Segmentation of textured images using Gibbs random fields[J].Computer Vision Graphics and Image Process,1986,35:72-98.
[24]Besag,J.Spatial interaction and the statistical analysis of lattice systems[J].Journal of the Royal Statistical Society,Series B,1985,36:192-236.
[25]Chellappa,R.Two-dimensional discrete Gaussian Markov random field models for image processing[C].(Kanal,L.N.and Rosenfeld,A.,eds.)Progress in Pattem Recognition,1985,2:79-112.
[26]J.Mao,AK Jain.Texture classification and segmentation using multiresolution simultaneous autoregressive models[J].Pattern Recognition,1992,25(2):173-188.
[27]E.Ising.Beitrag zur Theorie des Ferromagnetismus[J].Z.Phys.1925,31:253-258.
[28]Derin H,Elliott H.Modeling and segmentation of noisy and textured images using Gibbs random fields.IEEE Trans[J].Pattern Anal.Machine Intell,1987,9(1):39-55.
[29]Fwe J,Djuric P.Unsupervised vector image segmentation by a tree stucture-ICM algorithm[J].IEEE Trans.on Medical Imaging,MI,1996,15(6):871-881.
[30]Kirkpatrick S,Gelatt G D Jr,Vecchi M P.Optimization by simulated annealing[J].Science,1983,220(4598):671-680.
[31]McLachlan G J,Krishnan T.The EM Algorithm and Extensions[M].New York:Wiley,1997
[32]刘伟强,陈鸿,夏德深.基于马尔可夫随机场的快速图像分割[J].中国图像图形学报,2001,6A(3):228-233.
[33]M.Pawan Kumar,P.H.S.Torr,A.Zisserman.Solving Markov Random Fields using Second Cone Programming Relaxations[C].Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.
[34]张鹏.Markov随机场在图像处理中应用的研究[D].武汉:华中科技大学,2005.
[35]张翠,郦苏丹,王正志.基于MRF场的SAR图像分割方法[J].遥感技术与应用,2001,16(1):66-68.
[36]J.Besag,On the Statistical Analysis of Dirty Pictures[J].Journal of the Royal Statistical Society,Series B 1986,6:259-302.
[37]刘岩.模拟退火算法的背景和单调升温的模拟退火算法.计算机研究与发[J].1996,33(1):4-10.
[38]李乔祥.数据结构与算法[M].北京:冶金工业出版社,2004.
[39]Bilmes J A.A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models[R].International Compute Science Institute,1997.
[40]D.B.Gu,J.X.Sun.EM image segmentation algorithm based on an inhomogeneous hidden MRF model[J].IEE Proc.-Vis.Image Signal Process,2005,152(2):184-190.
[41]程兵,王莹,郑南宁等.基于Markov随机场和FRAME模型的无监督图像分割[J].中国科学E辑, 2004,34(4):391-400.
[42]李水根.分形[M].北京:高等教育出版社,2005.
[43]D.E.Melas,S.P.Wilson.Double Markov random fields and Bayesian image segmentation[J].IEEE Trans.Signal Process.2002,50(2):357-365.
[44]Yong Xia,Dagan Feng,Rongchun Zhao.Adaptive Segmentation of Textured Images by Using the Coupled Markov Random Field Model[J].IEEE Transactions On Image Processing,2006,15(11):3559-3565.
[45]F.C.Jeng,J.W.Woods.Compound Gauss-Markov random fields for image segmentation[J].IEEE Trans.Signal Process,1991,39(3),683-697.
[46]R.Molina,Mateos,A.Katsaggelos,M.Vega.Bayesian multichannel image restoration using compound Gauss-Markov random fields[J].IEEE Trans.Image Process,2003,12(12):1642-1654.