图象分割方法.ppt

模 式 识 别 国 家 重 点 实 验 室,中 国 科 学 院 自 动 化 研 究 所,National Laboratory of Pattern Recognition,Institute of Automation,Chinese Academy of Sciences,图像理解的基本构成,知识库,表示与描述,预处理,分割,低级处理,高级处理,中级处理,识别,与,解释,结果,图像获取,问题,1.什么是图像分割,图像,分割是将,图像,空间,R,划分为,n,个互不重叠的区域,其中,P,(,R,i,)为作用于,R,i,中所有象素的相似性逻辑谓词。,定义,实例,1.,2.,3.,4.,计算机视觉的其他领域,医学图像处理,遥感图像处理,目标跟踪,生物特征识别,等等,分割依赖于高层视觉,分割依赖于低层视觉,分割依赖于高层视觉（续）,图像分割是中层视觉中的最基本问题，也是计算视觉和,图像,理解中的最基本问题之一,。它还,是该领域国际学术界公认的将会长期存在的最困难的问题之一。,图像分割之所以困难的一个重要原因是其并不完全属于图像特征提取问题，它还涉及到各种图像特征的知觉组织。,从一般意义上来说，只有对图像内容的彻底理解，才能产生完美的分割。,通过限制图像的类型，可以降低图像分割的难度。,图像分割的基本思路,从简到难，逐级分割；,控制背景环境，降低分割难度；,把焦点放在增强感兴趣对象，缩小不相干图像成分的干扰上。,从简到难，逐级分割,分割矩形区域,定位牌照,定位文字,控制背景环境，降低分割难度,背景环境,:,路面、天空,把焦点放在增强感兴趣对象，缩小不相干图像成分的干扰上,感兴趣的对象：,汽车牌照,不相干图像成分：,非矩形区域,图像分割的基本策略,基于灰度值的两个基本特性：,不连续性,区域之间,相似性,区域内部,根据图像像素灰度值的,不连续性,：,先找到点、线（宽度为,1,）、边（不定宽度）,再确定区域。,根据图像像素灰度值的,相似性,：,通过选择阈值，找到灰度值相似的区域,区域的外轮廓就是对象的边。,对,图像,特征空间做分类的方法,分割算法的大致分类（共五类）,基于区域的方法（区域生长等）,基于函数优化的方法（,Bayesian,等）,综合考虑边缘和区域信息的混合分割,方法,基于边缘的方法（边缘检测,/,主动边,缘）,自动阈值方法,阈值方法的本质,阈值方法并不要求直方图必须同时,包含峰和谷。,Pixel,h,?,3.1,全局阈值方法,众数法（,J.M.S.Prewitt,et al.,1966,Ann.New York Acad.,Sci,.,）,已知图像仅包含具有明显灰度差别的目标和背景。此时灰度直方图通常为双峰单谷型。取谷底点为阈值即可完成分割。,Otsu,法（,N.Otsu,1979,IEEE T-SMC,）,在直方图上定义类内方差和类间方差,其中，,P,i,为第,i,类出现的概率,，,i,为第,i,类的均值,，,为混合分布的均值,。,总体方差为,三个方差的关系为,求使类间方差(分离度)尽量大而类内方差尽量小的阈值,t,。,三者等价。取计算量最小的,(,t,)：,定义如下函数,Otsu,法可以应用于多维特征空间中。,基于熵的方法,KSW,法（,J.N.,Kapur,et al.,1985,CVGIP,）,设直方图上阈值,t,两侧的分布分别为,p,i,、,q,i,，以及,选择满足下式的,t*,作为分割阈值,上述熵的理论分析十分困难，分割意义也不十分明确。正因为如此，我们也可以,基于矩不变的方法（,W.Tsai,1985,CVGIP,）,设图像,f,的第,i,阶矩为（,i=1,2,3,）,其中,z,j,为灰度直方图中的第,j,个灰度值。,设分割后图象,f,的第,i,阶矩为,其中,z,j,为分割后灰度直方图中的第,j,个灰度值。此时只有两个灰度级。,设,，,i=,1,2,3,有,解上述方程组即得,。从而,可以确定划分目标和背景的阈值。,最小误分阈值法（,Frank,et al.,1995,）,假设概率密度为混合Guassian：,最小均方拟合：,用优化方法（如共轭梯度法或牛顿法）求得,P,i，,i,，,i,，,即得,p,i,(,g,)。,求交点,t,：,取对数，整理得：,去掉一个不适当的解即可得到解。,近似最小误分阈值法（,J.Kittleret al.,1986,PR,）,利用相对熵的概念定义Gaussian函数与直方图之间的距离：,设,为第,i,类的Guassian拟合函数。,去掉常数项，整理得新的表达式,这里,J,(,T,)越小，则两个Guassian函数的重叠面积就越小。于是求,，使得,其他方法,1)概率松弛法（A.Rosenfeld,et al.,1981）,这里，,m,是类数，,r,为已迭代次数，,p,ij,表示第,i,个象素属于第,j,类的概率，,q,ij,是根据其它象素所属类别对,p,ij,的调整量。,这里，,n,是象素个数，,c,(,i,j,;,h,k,)是相容性函数，表示第,i,个象素属于第,j,类与,第,h个象素属于第,k,类的相容程度。,体现了其它象素所属区域对第,i,个象素属于第,j,个区域的综合影响。,的设置（以两分分割为例）,设,d,和,l,分别为原始图象中最黑和最亮的灰度，,z,i,为第,i,个象素的灰度，则,相容性的设计？,相容性函数的例子：,染色体图象,海面云层图象,坦克红外图象,2)直方图变换法,a.依据各个象素的局部特征对各象素灰度加权（如 1/(1+,2,),D.Mason,et al.,1975,）。,b.利用四分树法对目标和背景的灰度平滑后再建立直方图（A.Y.Wu,et al.,1982）。,目的：获得具有更深的谷和更尖锐的峰的直方图。,3)引入二阶灰度统计量,灰度共生矩阵,中元素的含义,m,ij,表示在图象中灰度为,i,和,j,、,间距为,d,个象素、与水平方向夹角为,的象素对的数目。,如,M,(1,),中的元素,m,ij,表示,4-,邻域相邻象素中灰度分别为,i,和,j,的象素对的个数。,a.N.Ahuja,et al,1975,构造两个新直方图：,h,1,：对,M,对角线附近的元素，,h,2,：对非,M,对角线附近的元素。,在,h,1,和,h,2,的谷峰重叠处选择一个阈值。,b.F.Deravi,et al,1983,这里，,x,为,h,或,v,或,vh,，,T,ij,是,T,x,的元素。,最优阈值,：,可以认为，图像边缘附近（其灰度大多位于灰度直方图的谷底附近）应当具有最多的,4,-相邻的不同类象素对。于是有目标函数：,全局阈值方法比较,大量实验表明，基于简单统计量的方法往往可以获得较好的分割结果。而基于熵的方法应用于有噪声图象时结果一般较差。,c.利用灰度和均值构造二维直方图，并在其上定义统计量。,3.2 局部阈值方法,将图像分块，分别用,全局阈值方法,分割，最后再综合。,3.3 递归阈值方法（R.Ohlander,1975）,3.4 动态K-L变换阈值分割方法（Y.Ohta,et al,1980）,以RGB三基色的K-L变换为特征，采用递归阈值方法分割彩色图像。,设,S,为待分割区域，对其RGB做K-L变换，得到新的特征,x,1,x2,x,3,。利用它们对,S,分割。,重要现象,问题思考,找出上述方法中你认为缺陷最大的一个，并提出修改意见；,比较各方法的优缺点，并指出各适合哪类图像的分割；,提出自己基于直方图的分割方法,。,4.基于边缘的方法,4.1 边缘检测算子,4.2 主动边缘模型,经典主动边缘模型（,M.,Kass,et al,1988,）,测地线主动边缘模型（,V.,Caselles,et al,ICCV,1995,）,一些其它的手工交互方法：,Level Set,Intelligent Paint,Intelligent Scissors,Matting(Poisson,Bayesian,etc.),Image Contour Editing,Graph Cut(Grab Cut),Lazy snapping,一些手工交互方法的比较,Active Contour,Intelligent Scissors,Graph Cut,NURBS-HMM,5.基于区域的方法,区域生长,a|b,-,c|d,a）,原始X线探,伤图象,b）,种子区域,c）,生长结果,d）,缺陷区边缘,上页图,a,的直方图。种子区域由灰度为,255,的象素构成。,从种子区域开始以,8,-邻域方式向外生长，只要一个象素的灰度,g,与种子点的灰度差小于,65(即,g,191),，即将该象素归入目标区。,分裂与合并,R,1,R,2,R,3R,41,R,42,R,43,R,44,R,R,1,R,2,R,3,R,4,R,41,R,42,R,43,R,44,分水岭分割法,标准步骤：,1）,将图象看作地形图；,2）,在每一个极小点处“打一个孔”；,3）,以一致的速率从小孔向外“喷水”，并始,终保持地形中所有的水位一致；,4）,不同盆地的水相遇时则筑坝，并且随着,水位的不断升高，坝也升高；,5）当水位达到地形的最高点时算法终止。,缺陷：可能出现“过度分割”问题。,a|b,图,a,为原始电泳图象，图,b,为标准分水岭分割法分割图,a,的梯度图象的结果。,带标记的分水岭算法 “泉眼”的位置是(自动或手工)指定的，而不是由极小点确定的。这样可以避免“过度分割”问题。,电泳图象的分割方法,1）滤波；,2）选择平缓的“盆地”底部作为标记(红斑)；,3）调用分水岭算法确定分水线(黄线)；,4）在每个分水线分出的小区域内，利用前,述阈值法或分水岭法等完成分割。,6.基于函数优化的方法,基于成对方式聚类的纹理图像分割（,T.Hofmann,et al,ICIP,96,T-PAMI,1998,）,需优化的函数：,其中，,M,=,M,iv,(,N,K,),为标记矩阵，,M,iv,表示象素,i,用,v,标记，,D,ij,为一对象素,i,、,j,间的纹理不相似性度量,，,N,为象素个数,，,K,为标号个数（分类数）,，,N,i,为象素,i,的邻域思考：Dij的定义？,公式中的,()表示象素,i,的邻域中和,i,具有相同标号的象素与,i,之间的平均不相似性。于是,H,(,M,)就表示整幅图象上的不相似性。这种不相似性自然是越小越好。,即求标记矩阵,M,，使得:,上式需要复杂的寻优算法来优化。,实验结果,2)基于 Bayesian 的图象分割方法,设有定义在离散网格,上的标量离散随机场,为随机变量。,定义离散网格,上的,邻域系,：,为,x,的邻域：,定义象素团(clique)：,邻域和象素团,(clique),的例子,如果 是单网格点，或是由两两相邻的网格点组成，则,C,是定义在,上的一个象素团。,Markov,随机场（,MRF,）一个随机场,被称为关于邻域,系,N,的 Markov 随机场，如果,即只由,x,i,的邻域决定。,用局部条件概率描述 Markov 随机场很不方便。,Gibbs,随机场（,GRF,）,一个随机场,被称为关于邻域,系,N,的 Gibbs 随机场，如果,其中，,这里，,T,为温度参数，,U,为Gibbs能量，,V,C,为象素团,C,的能量，,O,为象素团集合。,Markov,随机场和,Gibbs,随机场的等价性,Hammersley-Clifford(H-C)定理：,设,N,是邻域系。,z,(,x,),是关于,N,的Markov随机场，当且仅当,z,(,x,)是关于,N,的 Gibbs 随机场。希望得到一个分割标号随机场,z,，,z,(,x,)=,l,表示象素,x,属于,l,-th,类。这里，,l,=1,K,。,基于,Bayesian,的分割方法,maximum,a posteriori,probability(MAP),设有含加性噪音的图象：,根据 Bayes 公式，希望下式左边取极大：,要求,p,(,z,|,g,)极大，就要求条件概率,p,(,g,|,z,)和先验概率,p,(,z,)的积为极大。,采用4-邻域来估计两个概率。假设图象服从卡片纸模型。,1)先验概率模型,p,(,z,)的估计：,对于,单个网格点,的象素团，如果,z,(,x,)=,l,，,p,l,是,l,-th,类区域出现的先验概率，它反映了我们对于不同类区域出现概率的先验知识。,p,l,越小，先验概率越大。,对于,双网格点,象素团，以如下方式强加象素团能量,其中,0,。,越大，平滑性约束就越强。,2)条件概率模型,p,(,g,|,z,)的估计：,设,l,(,x,),（,l,=1,2,K,）是,l,-th,类区域的灰度均值，则有：,对上式利用模拟退火算法优化，求出最优分割标号集,z,和,l,(,x,)，,这里,l,=1,2,K,。,综合1)、2)所述，得后验概率,2)基于“均值移动”的图象分割方法,(D.Comaniciu et.al,ICCV,99,T-PAMI,2002),a)均值移动（Mean Shift）思想,核函数,b)均值移动滤波,实验结果,c)均值移动分割,实验结果,1)通过区域均匀性和类不确定性最小化求取最优阈值(MHUE)（P.K.Saha,et al,T-PAMI,2001）,7.综合考虑边缘和区域的方法,假设A：,在任何具有模糊边界的图像中，在利用最优阈值得到的区域划分中，类不确定性高的象素出现在物体的边缘附近。,a)基于灰度的类不确定性的确定,设,F,o,t,和,F,b,t,分别是阈值为,t,时的物体和背景象素集。假设物体和背景的灰度都服从Gaussian 分布，,c,为一个象素，,C,为图象空间，|X|表示集合X元素个数。设,设,p,t,(,g,),是,c,g,的概率即,所以，由Bayes公式，具有灰度,g,的象素,c,属于物体的后验概率为,设,p,o,t,(,g,),和,p,b,t,(,g,),分别是作为物体和背景上的象素,c,g,的概率，即,所以，若已知象素,c,具有灰度,g,，则在阈值为,t,时对,c,分类的不确定性可由 Shannon 熵表示，即,而具有灰度,g,的象素,c,属于背景的后验概率为,物体和背景上的象素,c,g,的概率的定义,b)区域均匀性的确定,这里，,c,、,d,是两个象素，,确定,c,与,d,是否属于同一个区域。,大，则表示,c,与,d,属于同一个区域。所以,越大，则表示,c,及其邻域越均匀。,注意，,的计算与阈值,t,的选取无关,。,C、,的定义可参阅,P.K.Saha,et al,T-PAMI,2001,c)最优阈值的确定,d)实验结果,(c),(f),为,MHUE,方法所得的分割结果。图,(g)为MHUE,中的类不确定性。,e)定量比较实验结果,三个不同的切片图，且所加,Gaussian,噪声自左至右递增。,(a),(e),(i),分别对应上页三图的无噪声原图。第三列是本文方法的分割结果，第四列为“最优”阈值的分割结果。,和“最优”阈值所得结果相比，MHUE的结果最大误差为0.2%，平均误差为0.13%!,作为一种阈值分割方法，MHUE方法的参数很少(只有一个，在计算区域均匀性时用到)，而且其结果似乎也很难再被其他阈值分割方法所超越。,总结,在图象分割领域还没有出现对任意图象都可以分割的算法，需要根据问题的不同设计和采用不同的算法，还可能要考虑时空复杂度的可接受性。,图像分割相关的一些研究方向：,图像,Matting,目标,：,从I(x,y)中同时计算出a(x,y),F(x,y),B(x,y),典型方法：,J.Wang and M.F.Cohen.An iterative optimization approach for unified image segmentation and matting.In,Proc.of IEEE ICCV,pages II:936943,2005.,Y.Y.Chuang,B.Curless,D.Salesin,and,R.Szeliski,.Bayesian,Approach to Digital Matting.In,Proc.of IEEE CVPR,pages,264271,2001.,A.R.Smith,and,J.F.Blinn,.Blue screen matting.In,Proceedings of ACM SIGGRAPH,pages 259268,Aug 1996.,J.Sun,J.Y.Jia,C.K.Tang,and,H.Y.Shum,.Poisson matting.,In,Proc.of ACM SIGGRAPH,pages 315321,2004.,一些结果：,纹理分割和纹理合成：,纹理分割的目标,：,To compare texture samples and decide if they belong to the same family,纹理合成的目标：,从样本纹理合成出相似的大纹理（,giving a small patch of sample texture,generating a large texture,）,C.Palm and T.M.,Lehmann,Classification of Color Textures by,Gabor,Filtering,Computer Graphics and Vision vol.11,no.2/3,2002,pp.195-219.,典型文章：,M.,Varma,and A.,Zisserman,Texture Classification:Are Filter Banks Necessary?,In Proceedings of CVPR,2003.,X.Liu and D.Wang,A Spectral Histogram Model For,Texton,Modeling And Texture Discrimination,Vision Research 42(2002),pp.2617-2634.,D,Heeger,and J Bergen,Pyramid-based Texture Analysis/Synthesis,In Proc ACM SIGGRAPH,August 1995.,纹理分割的一些结果：,纹理合成的一些结果：,图像解析（Image Parsing）,目标：,Parsing image into several parts,each parts modeled one of the specified models with different models,Models can be high level models such as face and text,or low level models such as region and curve,Bayesian Framework,Each model has a prior probability,；,Each model has a likelihood probability,w.r.t,.Image,Maximize the posterior probability which can be rewrite as the productions of prior and likelihood of each model,Markov Chain Monte Carlo,Sample the posterior probability by reversible jumps on Markov chain,基本方法,典型文章：,Image Segmentation by,Data-Driven Markov Chain Monte Carlo,-Z.W.,Tu,and S.C.Zhu,-,IEEE Trans on Pattern Analysis and Machine Intelligence,vol.24,no.5,pp.657-673,May,2002.,Image parsing,:unifying segmentation,detection and recognition-Z.W.,Tu,X.R.Chen,A.L.,Yuille,and S.C.Zhu,-,Intl J.of Computer Vision,63(2),113-140,2005.,Parsing Images into Regions,Curves,and,Curve Groups,-Z.W.,Tu,and S.C.Zhu,-Intl Journal of Computer Vision,(Accepted).,一些结果,Parsing image into regions,faces,and text,Parsing image into curves,regions and curve groups,总结,在图象分割领域还没有出现对任意图象都可以分割的算法，需要根据问题的不同设计和采用不同的算法，还可能要考虑时空复杂度的可接受性。,谢谢！,