1、图图 像像 分分 割割 图像理解的基本构成图像理解的基本构成知识库知识库表示与描述表示与描述预处理预处理分割分割低级处理高级处理中级处理识别识别与与解释解释结果图像获取图像获取问题1.什么是图像分割什么是图像分割图像图像分割是将图像图像空间 R 划分为 n 个互不重叠的区域.)(,)(,1真真jiijiniiRRPRPRRRR其中 P(Ri)为作用于 Ri 中所有象素的相似性逻辑谓词。定义 实例1.2.3.4.2.图像分割的重要性和难度图像分割的重要性和难度 计算视觉低层视觉低层视觉高层视觉高层视觉中层视觉中层视觉图像分割图像分割 中层视觉：获得图像中物体的 2.5 维描述 低层视觉：获得要素
2、图（二维图像中的边缘点、直线段、曲线段、顶点、纹理等）高层视觉：获得图像中物体的三维描述 计算机视觉的其他领域1.医学图像处理2.遥感图像处理3.目标跟踪4.生物特征识别等等 分割依赖于高层视觉 分割依赖于低层视觉 分割依赖于高层视觉（续）v 图像分割是中层视觉中的最基本问题，也是计算视觉和图像图像理解中的最基本问题之一。它还是该领域国际学术界公认的将会长期存在的最困难的问题之一。v 图像分割之所以困难的一个重要原因是其并不完全属于图像特征提取问题，它还涉及到各种图像特征的知觉组织。v 从一般意义上来说，只有对图像内容的彻底理解，才能产生完美的分割。通过限制图像的类型，可以降低图像分割的难度。
3、图像分割的基本思路图像分割的基本思路从简到难，逐级分割；从简到难，逐级分割；控制背景环境，降低分控制背景环境，降低分割难度；割难度；把焦点放在增强感兴趣把焦点放在增强感兴趣对象，缩小不相干图像对象，缩小不相干图像成分的干扰上。成分的干扰上。l 从简到难，逐级分从简到难，逐级分割割 分割矩形区域分割矩形区域 定位牌照定位牌照 定位文字定位文字l 控制背景环境，控制背景环境，降低分割难度降低分割难度背景环境背景环境:路面、天空路面、天空l 把焦点放在增强感把焦点放在增强感兴趣对象，缩小不相兴趣对象，缩小不相干图像成分的干扰上干图像成分的干扰上 感兴趣的对象：感兴趣的对象：汽车牌照汽车牌照 不相干图
4、像成分：不相干图像成分：非矩形区域非矩形区域图像分割的基本策略图像分割的基本策略基于灰度值的两个基本特性：基于灰度值的两个基本特性：不连续性不连续性区域之间区域之间相似性相似性区域内部区域内部u根据图像像素灰度值的根据图像像素灰度值的不连续性不连续性：先找到点、线（宽度为先找到点、线（宽度为1）、边（不定宽度）、边（不定宽度）再确定区域。再确定区域。u根据图像像素灰度值的根据图像像素灰度值的相似性相似性：通过选择阈值，找到灰度值相似的区域通过选择阈值，找到灰度值相似的区域区域的外轮廓就是对象的边。区域的外轮廓就是对象的边。1)对图像图像特征空间做分类的方法 分割算法的大致分类（共五类）分割算法
5、的大致分类（共五类）2)基于区域的方法（区域生长等）4)基于函数优化的方法（Bayesian等）5)综合考虑边缘和区域信息的混合分割 方法3)基于边缘的方法（边缘检测/主动边 缘）自动阈值方法阈值方法的本质.),(,0,),(,1),(TjifTjifjig 阈值方法并不要求直方图必须同时 包含峰和谷。Pixelh?3.1 全局阈值方法 众数法（J.M.S.Prewitt,et al.,1966,Ann.New York Acad.Sci.）已知图像仅包含具有明显灰度差别的目标和背景。此时灰度直方图通常为双峰单谷型。取谷底点为阈值即可完成分割。Otsu法（N.Otsu,1979,IEEE T-
6、SMC）210102112002)()()()()()()()()(tttPtPttPttPtB在直方图上定义类内方差和类间方差2112002)()()(tPtPtW其中，Pi为第 i 类出现的概率，i为第 i 类的均值，为混合分布的均值。LiiTpi122)(总体方差为三个方差的关系为.)()(222TBWtt求使类间方差(分离度)尽量大而类内方差尽量小的阈值t。三者等价。取计算量最小的(t)：定义如下函数,)()(,)()(,)()()(222222TBWTWBttttttt),(maxarg)(maxarg2tttBttOtsu法可以应用于多维特征空间中。基于熵的方法 KSW法（J.N.
7、Kapur,et al.,1985,CVGIP）设直方图上阈值 t 两侧的分布分别为 pi、qi，以及,log)(0itiiopptH,log)(11iltiibqqtH选择满足下式的 t*作为分割阈值)()(maxarg*tHtHtbot上述熵的理论分析十分困难，分割意义也不十分明确。正因为如此，我们也可以)()(minarg*tHtHtbot 基于矩不变的方法（W.Tsai,1985,CVGIP）设图像 f 的第 i 阶矩为（i=1,2,3）jijjxyiizpyxfnm)(),(1其中 zj 为灰度直方图中的第 j 个灰度值。10)(jijjizpm设分割后图象 f 的第 i 阶矩为其中
8、 zj 为分割后灰度直方图中的第 j 个灰度值。此时只有两个灰度级。设iimm，i=1,2,3,有,)()(,)()(,)()(,)()(3311300221120011111000011000mzpzpmzpzpmzpzpmzpzp解上述方程组即得1010,zzpp。从而可以确定划分目标和背景的阈值。最小误分阈值法（Frank,et al.,1995）假设概率密度为混合Guassian：nigiiniiiiiePgpPgp12)(12221)()(最小均方拟合：102)()(1lgmsghgpne用优化方法（如共轭梯度法或牛顿法）求得Pi，i，i，即得 pi(g)。求交点 t：)()(11t
9、pPtpPiiii取对数，整理得：02cbtat去掉一个不适当的解即可得到解。11212221212ln4iiiiiiiiiiPPc)(22121iiiib212iia 近似最小误分阈值法（J.Kittler,et al.,1986,PR）,2,1,2,1,1,0,)()()()(,)()()(,)()(22iniTbiTiaTPghTgTTPgghTghTPibagiiibagibagi利用相对熵的概念定义Gaussian函数与直方图之间的距离：gTgghTJ),()()(设TgTgighTPTighghTgJgi21,)()(),|(log)(),(),|(Tigh为第 i 类的Guass
10、ian拟合函数。去掉常数项，整理得新的表达式这里,2,1),(log2)(log2)(),(2TgTgiTPTTgTgiiii).(minargTJTJ(T)越小，则两个Guassian函数的重叠面积就越小。于是求，使得 其他方法1)概率松弛法（A.Rosenfeld,et al.,1981）mjrijrijrijrijrijqpqpp1)()()()()1()1()1(这里，m是类数，r为已迭代次数，pij表示第 i 个象素属于第 j 类的概率，qij 是根据其它象素所属类别对 pij 的调整量。nihhmkrhkrijpkhjicnq11)()(),;,(11这里，n是象素个数，c(i,j
11、;h,k)是相容性函数，表示第 i 个象素属于第 j 类与第h个象素属于第k类的相容程度。)(rijq 体现了其它象素所属区域对第 i 个象素属于第 j 个区域的综合影响。)0(ijp 的设置（以两分分割为例）设 d 和 l 分别为原始图象中最黑和最亮的灰度，zi 为第 i 个象素的灰度，则.,)0(1,)0(0,dldzpdlzlpiiii相容性的设计？相容性的设计？相容性函数的例子：染色体图象海面云层图象坦克红外图象2)直方图变换法a.依据各个象素的局部特征对各象素灰度加权（如 1/(1+2),D.Mason,et al.,1975）。b.利用四分树法对目标和背景的灰度平滑后再建立直方图（
12、A.Y.Wu,et al.,1982）。目的：获得具有更深的谷和更尖锐的峰的直方图。3)引入二阶灰度统计量),(dM灰度共生矩阵中元素的含义mij表示在图象中灰度为 i 和 j、间距为 d 个象素、与水平方向夹角为 的象素对的数目。如 M(1,)中的元素 mij 表示4-邻域相邻象素中灰度分别为 i 和 j 的象素对的个数。a.N.Ahuja,et al,1975)23,1(),1()2,1()0,1(MMMMM构造两个新直方图：h1：对 M 对角线附近的元素，h2：对非 M 对角线附近的元素。在 h1 和 h2 的谷峰重叠处选择一个阈值。b.F.Deravi,et al,1983,)2,1(
13、)0,1(hvvhvhTTTMTMT,bdcaTx,111111001100 ltiltjijltitjijtiltjijtitjijTbTdTcTa这里，x 为 h 或 v 或 vh，Tij 是 Tx 的元素。,21)(,)(dbdcactPdcbadctPcj).(maxarg )(maxargtPtPctjt或最优阈值：可以认为，图像边缘附近（其灰度大多位于灰度直方图的谷底附近）应当具有最多的4-相邻的不同类象素对。于是有目标函数：全局阈值方法比较大量实验表明，基于简单统计量的方法往往可以获得较好的分割结果。而基于熵的方法应用于有噪声图象时结果一般较差。c.利用灰度和均值构造二维直方图，
14、并在其上定义统计量。3.2 局部阈值方法将图像分块，分别用全局阈值方法分割，最后再综合。3.3 递归阈值方法（R.Ohlander,1975）3.4 动态K-L变换阈值分割方法（Y.Ohta,et al,1980）以RGB三基色的K-L变换为特征，采用递归阈值方法分割彩色图像。设 S 为待分割区域，对其RGB做K-L变换，得到新的特征x1,x2,x3。利用它们对S分割。重要现象.42,2,3321BRGxBRxGBRx问题思考问题思考 找出上述方法中你认为缺陷最大的一个，找出上述方法中你认为缺陷最大的一个，并提出修改意见；并提出修改意见；比较各方法的优缺点，并指出各适合哪类比较各方法的优缺点，
15、并指出各适合哪类图像的分割；图像的分割；提出自己基于直方图的分割方法提出自己基于直方图的分割方法。4.基于边缘的方法4.1 边缘检测算子4.2 主动边缘模型 经典主动边缘模型（M.Kass,et al,1988）101022|)(|)|()(dqCIdqCCCE 测地线主动边缘模型（V.Caselles,et al,ICCV,1995）102102|)(|)(|)(dqqCIgdqqCCE一些其它的手工交互方法：一些其它的手工交互方法：Level Set Intelligent Paint Intelligent Scissors Matting(Poisson,Bayesian,etc.)I
16、mage Contour Editing Graph Cut(Grab Cut)Lazy snapping一些手工交互方法的比较一些手工交互方法的比较Active ContourIntelligent ScissorsGraph CutNURBS-HMM5.基于区域的方法 区域生长 a|b-c|da）原始X线探 伤图象b）种子区域c）生长结果d）缺陷区边缘 上页图a的直方图。种子区域由灰度为255的象素构成。从种子区域开始以8-邻域方式向外生长，只要一个象素的灰度g 与种子点的灰度差小于65(即g191)，即将该象素归入目标区。分裂与合并 R1R2R3R41R42R43R44RR1R2R3R4
17、R41R42R43R44 分水岭分割法标准步骤：1）将图象看作地形图；2）在每一个极小点处“打一个孔”；3）以一致的速率从小孔向外“喷水”，并始 终保持地形中所有的水位一致；4）不同盆地的水相遇时则筑坝，并且随着 水位的不断升高，坝也升高；5）当水位达到地形的最高点时算法终止。缺陷：可能出现“过度分割”问题。a|b 图a 为原始电泳图象，图b为标准分水岭分割法分割图 a 的梯度图象的结果。带标记的分水岭算法 “泉眼”的位置是(自动或手工)指定的，而不是由极小点确定的。这样可以避免“过度分割”问题。电泳图象的分割方法1）滤波；2）选择平缓的“盆地”底部作为标记(红斑)；3）调用分水岭算法确定分水
18、线(黄线)；4）在每个分水线分出的小区域内，利用前 述阈值法或分水岭法等完成分割。6.基于函数优化的方法1)基于成对方式聚类的纹理图像分割（T.Hofmann,et al,ICIP96,T-PAMI,1998）NiKNjijNkkjiiiDMMMMH10)(需优化的函数：其中，M=Miv(NK)为标记矩阵，Miv 表示象素 i 用 v 标记，Dij 为一对象素 i、j 间的纹理不相似性度量，N为象素个数，K 为标号个数（分类数），Ni 为象素 i 的邻域。，标记不用象素标记用象素viviMiv,0,1思考：思考：Dij的定义？的定义？公式中的()表示象素 i 的邻域中和 i 具有相同标号的象素
19、与 i 之间的平均不相似性。于是 H(M)就表示整幅图象上的不相似性。这种不相似性自然是越小越好。即求标记矩阵M，使得:)(minargMHM上式需要复杂的寻优算法来优化。实验结果2)基于 Bayesian 的图象分割方法设有定义在离散网格上的标量离散随机场)(,1.,1,0)(,),(xzLxzxxzz为随机变量。定义离散网格上的邻域系：,xNNx为x的邻域：jixjxixxxNxNxNxij,以及xN定义象素团(clique)：邻域和象素团(clique)的例子 如果 是单网格点，或是由两两相邻的网格点组成，则 C 是定义在上的一个象素团。C Markov随机场（MRF）一个随机场被称为关
20、于邻域),(xxzz系 N 的 Markov 随机场，如果.),(|)(),(|)(;,)(ixjjiijjiNxxzxzpxxxzxzpxxzp 0即只由 xi 的邻域决定。用局部条件概率描述 Markov 随机场很不方便。Gibbs 随机场（GRF）一个随机场被称为关于邻域),(xxzz系 N 的 Gibbs 随机场，如果)()(xzUTeQxzp11其中，,)(zxzUTeQ1.)|)(OCCCxxzVU这里，T 为温度参数，U 为Gibbs能量，VC 为象素团 C 的能量，O 为象素团集合。Markov随机场和Gibbs 随机场的等价性Hammersley-Clifford(H-C)定
21、理：设 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)设有含加性噪音的图象：)()()(xvxsxg 根据 Bayes 公式，希望下式左边取极大：)()|()|(zpzgpgzp 要求 p(z|g)极大，就要求条件概率 p(g|z)和先验概率 p(z)的积为极大。采用4-邻域来估计两个概率。假设图象服从卡片纸模型。1)先验概率模型
22、 p(z)的估计：)(exp)(xzUTQxzp11OCCCxxzVU)|)(CxpxzVlC,)(对于单个网格点的象素团，如果 z(x)=l，pl 是 l-th 类区域出现的先验概率，它反映了我们对于不同类区域出现概率的先验知识。pl 越小，先验概率越大。对于双网格点象素团，以如下方式强加象素团能量CxCxxzxzifCxCxxzxzifxzxzVjijijijijiC,),()(,),()(,)(),(其中 0。越大，平滑性约束就越强。2)条件概率模型 p(g|z)的估计：xxzxgTzgp22)(2)(1exp)|(设 l(x)（l=1,2,K）是 l-th 类区域的灰度均值，则有：对上
23、式利用模拟退火算法优化，求出最优分割标号集 z 和l(x)，这里 l=1,2,K。综合1)、2)所述，得后验概率xOCCxzCxxzVxgTzgp)|)()(exp)|()(22212)基于“均值移动”的图象分割方法 (D.Comaniciu et.al,ICCV99,T-PAMI,2002)a)均值移动（Mean Shift）思想核函数b)均值移动滤波实验结果c)均值移动分割实验结果1)通过区域均匀性和类不确定性最小化求取最优阈值(MHUE)（P.K.Saha,et al,T-PAMI,2001）7.综合考虑边缘和区域的方法假设A：在任何具有模糊边界的图像中，在利用最优阈值得到的区域划分中，
24、类不确定性高的象素出现在物体的边缘附近。a)基于灰度的类不确定性的确定 设 Fo,t 和 Fb,t 分别是阈值为 t 时的物体和背景象素集。假设物体和背景的灰度都服从Gaussian 分布，c 为一个象素，C为图象空间，|X|表示集合X元素个数。设),(1,|)(,tbttototFcPCFFcP 设 pt(g)是 c g的概率，即).()1()()(,gpgpgptbttott所以，由Bayes公式，具有灰度g的象素 c 属于物体的后验概率为,)()()(|(,gpgpgcfFcPttottot 设 po,t(g)和 pb,t(g)分别是作为物体和背景上的象素 c g 的概率，即).|)()
25、(),|)()(,tbtbtotoFcgcfPgpFcgcfPgp所以，若已知象素 c 具有灰度 g，则在阈值为 t 时对 c 分类的不确定性可由 Shannon 熵表示，即.)()()1(log)()()1()()(log)()()(,gpgpgpgpgpgpgpgpgHttbtttbtttotttott而具有灰度g的象素 c 属于背景的后验概率为.)()()1()(|(,gpgpgcfFcPttbttbt物体和背景上的象素 c g 的概率的定义b)区域均匀性的确定.),(),(),()(CdCddcdcdcc不相邻.与相邻与dcdcdc,0,1),(，这里，c、d 是两个象素，),(dc确
26、定 c 与 d 是否属于同一个区域。大，则表示 c 与 d 属于同一个区域。所以越大，则表示 c 及其邻域越均匀。注意，的计算与阈值 t 的选取无关。C、),(dc的定义可参阅P.K.Saha,et al,T-PAMI,2001).(1()(1()()()(ccfHccfHtEtCctc)最优阈值的确定)(minargtEttMHUEd)实验结果(c),(f)为MHUE 方法所得的分割结果。图(g)为MHUE中的类不确定性。e)定量比较实验结果三个不同的切片图，且所加 Gaussian 噪声自左至右递增。(a),(e),(i)分别对应上页三图的无噪声原图。第三列是本文方法的分割结果，第四列为“
27、最优”阈值的分割结果。和“最优”阈值所得结果相比，MHUE的结果最大误差为0.2%，平均误差为0.13%!作为一种阈值分割方法，MHUE方法的参数很少(只有一个，在计算区域均匀性时用到)，而且其结果似乎也很难再被其他阈值分割方法所超越。总结 在图象分割领域还没有出现对任意图象都可以分割的算法，需要根据问题的不同设计和采用不同的算法，还可能要考虑时空复杂度的可接受性。图像分割相关的一些研究方向：图像分割相关的一些研究方向：u 图像Matting目标目标：从I(x,y)中同时计算出a(x,y),F(x,y),B(x,y)典型方法：典型方法：J.Wang and M.F.Cohen.An itera
28、tive 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.BayesianApproach to Digital Matting.In Proc.of IEEE CVPR,pages264271,2001.A.R.Smith and J.F.Blinn.Blue screen matting.In Proceedings of ACM SI
29、GGRAPH,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
30、 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 an
31、d 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
32、 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 Maximi
33、ze the posterior probability which can be rewrite as the productions of prior and likelihood of each model Markov Chain Monte CarloSample 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,-IEE
34、E 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 textParsing image into curves,regions and curve groups总结 在图象分割领域还没有出现对任意图象都可以分割的算法，需要根据问题的不同设计和采用不同的算法，还可能要考虑时空复杂度的可接受性。谢谢！谢谢！
