数字图像处理第8讲

1、第八讲 图像分割（3） 李衷怡 华中科技大学数字化工程与仿真中心 局部区域内呈现不规则性，在整 体上表现出某种规律性 分形：各个部分组成的形态，每个部分 以某种方式与整体相似 Sierpinski填料的形成（长大过程） 分形物体D分形物体D 海岸线1D1.3人肺2.17 山地表面2.1D2.9血管2.3 河流水系1.1D1.85人脑表面2.73D2.79 云1.35人的脑电图1.9D2.4 金属裂纹1.25D1.29 D NM)()( D s RRM)( R 盒子法： ji rr jinN , ),( 1),(lkjinr )/1log(logrN r Msr/ ss k l R. M. Ha

2、ralick. Statistical and Structural Approaches to Texture. Proc. IEEE, 1979, 67: 786-804 A. C. David,丫P. Zhao. Rapid Extraction of Image Texture by Co-occurrence Using a Hybrid Data Structure. Computers and Geosciences, 2002, 28(6): 763-774 V. S. John. Structural Analysis of Flow-related Textures in

3、Lavas. Earth-science Review, 2002, 57(3): 279-297 1 0.5 T1T2 )()()( 2 1 ( 2 1 exp( )()( 2 1 exp( ) 1 10 1(0 ),( 2 2 2 1 21212211 ogqgpgf qgpgf ffqpe ； ：定义在相邻像素之间的连边上 f1：邻近像素灰度值的相似程度； f2：邻近像素与目标像素之间的相似程度； 1、2为权重，一般取0.5 ),(min),( ),(max),( ),(),( ),(),( qpedc dcdc dcqpe dcPdc 模糊连接度描述像素间连接紧密程度的全局关系 考察像

4、素间所有路径 每条路径的强弱程度由连接最薄弱处决定 选择局部连接程度最强的路径 | ),(Icoc o 由连接紧密程度决定x=x,1 像素o的强度为x的模糊连接对象满足 条件： 1),(ocx 1. 初始化Q，L为空 2. 计算局部模糊关系(epq) 3. 置o(o)=1其它像素p的o(p) = 4. 从Q中移出一个像素c并置入L 5. 求o(c)=maxmino(d)，(ecd) 6. if (ecd)0且d不在L中将d置入Q 7. 如果 Q不为空，转4 )()( )()(),( 11 2 ik T ikikij N j C i ij m ijm vxAvxd dW vx VU U：模糊隶属

5、度集合（CN） V：聚类中心集合 ij：j像素在i类中隶属度 dij：像素与聚类中心的距离 m：模糊加权指数，1,) Wm：在某种差异性定义下类内紧致度 N k m ik N k k m iki uxuv 11 )(/)( 1. 初始化U0, m, A, C, T 2. 由Un计算Vn 3. 由Vn计算Un+1 4. | Un+1 -Un|T，转第2步，否则结束 0;1 | 0 )/(/1 1 )1/(2 ikk C j k m jkik ik dCiiI else Idd u Rosenfeld A. The fuzzy geometry of image subsets, Pattern

6、Recognition Letters, 1984, 2 (5): 311 317. Udupa J. K, Samarasekera S. Fuzzy connectedness and object definition: Theory, algorithm and applications in image segmentation, Graphical Models and Image Processing, 1996, 58 (3): 246 261. Saha P. K., Udupa J. K., Odhner D. Scale-Based fuzzy connected ima

7、ge segmentation: Theory, algorithms, and validation, Computer Vision and Image Understanding, 2000, 77 (9): 145 174. 全局最小值：全图最小 局部最小：邻域最小 下降路径：后面点灰度不大于前面点的路径 下降坡：下降路径集合 区域最小：下降坡最小 测地距离：连通区域内最小距离 测地影像区：与区域测地距离最近的点的集合 (a) Nc=0 (b) Nc=1(c) Nc1 1、初始化Cmin+1=Tmin+1 2、根据Cn-1求 Cn 情况(a)： Cn= Cn-1q 情况(b)： Cn=

8、 Cn-1q 情况(c)：在q处建水坝 3、n=max+1时终止 1. 排序 2. 浸水模拟 I. 将与已标记汇水盆地相邻的像素，修改其标 记并送入先进先出（FIFO）队列 II. 依次处理FIFO队列，修改像素的领域并送 入FIFO队列 III.FIFO队列为空时结束 3. 该层未处理的像素赋予新的标记 对图像进行预处理，如平滑，去噪 分割时添加约束，如标记，阈值 对分割结果进行后处理，如区域融合 基本思想：从标记指定的区域浸水 TBhandTAh minmin TRR ji )()( TpGrad N lstr lp )( 1 )( 作用：分割相接触目标 流程： 计算距离图 计算最终腐蚀集

9、合 从种子开始生长但不使各区域相连 XBA; 反复条件膨胀 XBAXBA)(;条件膨胀 最终腐蚀 m k k kkkk k YY ABAAY kBAA 1 1 );( end ; 0to1Do 1 n k nn nnn mm ATWW WYW mn YW L. Vincent and P. Soille. Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transaction, Patern Analysis and Machine Intelligence, 1

10、991, 13(6): 583-598. D. Wang. A multi-scale gradient algorithm for image segmentation using watershed. Patern Recognition, 1997, 678: 2043-2052. K. Haris, et al. Hybrid Image Segmentation Using Watersheds and Fast Region Merging. IEEE Transaction, Image Processing, 1998, 7(12): 1684-1699. 给定任意接近目标轮

11、廓的曲线 将曲线变形并移动使 其接近目标轮廓 输出目标轮廓 s snake dssvEsvEvE)()()( extint 活动轮廓：寻找能量最小的曲线 1 , 0)(),()(ssysxsv s sss dssvssvs EEvE 22 BendingElasticint )()()()( 2 1 )( EElastic：弹性势能，反抗轮廓的拉伸 EBending：弯曲势能，反抗轮廓的弯曲 2 2 ) 1()()()(ipipdavgsvs 22 )1()(2)1()(ipipipsv ss s dssvEvE)()( Imageext 2 Image | ),(|),(yxIyxE 2 I

12、mage |),(),(|),(yxIyxGyxE EImage：外部约束能量，将曲线移往低能量方向 s sss dsvEvvvE)()( 2 1 )( Image 22 snake 0 Image Evv ssssss 总能量 能量极小条件 1、给定初始轮廓 2、计算初始轮廓的能量 3、对每个点，取其领域，计算能量，并移动到局部能 量最小位置 4、计算变形后轮廓的能量 5、如果移动后轮廓的能量与移动前能量小于某阈值则 结束，否则转步骤3 对初始轮廓敏感 l 捕获区间小 l 是否收敛取决于初始轮廓 不容易收缩到角点位置 0Vvv ssssss 无散场无旋场:;: ),(),(),( vu yx

13、vyxuyxV 0)( 0)( 22 2 22 2 yxy yxx fffvv fffuu Kass M. Snake : active contour models. International Journal of Computer Vision, 1988,(1) :321 - 331. Cohen L D. On active contour models and balloons. CVGIP: Image Understand , 1991,53(3) :211 - 218. Seok - Woo Jang. Shaking snakes using color edge for

14、contour extraction. Proceedings International Conference on Image Processing ,2002 , 9(2) :817 - 820. V Caselles ,R Kimmel ,G Sapiro. Geodesic active contours. Fifth International Conference on Computer Vision , 1995 ,(3) :694 - 699. 基本思想：基本思想： 1. 1. 将图像用图的方式表示，顶点表示像素，边将图像用图的方式表示，顶点表示像素，边 表示像素之间的关系。

15、图像分割对应图的割集。表示像素之间的关系。图像分割对应图的割集。 2. 2. 确定图中边的权值，使图像分割目标（能量确定图中边的权值，使图像分割目标（能量 最小化）对应图的最小割。最小化）对应图的最小割。 3. 3. 用最大流算法求解最小割问题。用最大流算法求解最小割问题。 a b Source Sink 2 4 1 5 3 ,EVG 有源节点（s）和终 节点（t） 每条边有一个非负 的容量Cap(i,j) 对于不存在的边， 其容量为0 2 4 1 5 3 s t 2/2 3/4 1/1 4/5 3/3 s t 最大流：s-t图中最大可能的从s流向t的流量 割：将s-t图分成两个子集S和T s

16、-t割：当且仅当s属于S，t属于T 2 4 1 5 3 s t 2 4 1 5 3 s t s-t割 非s-t割 TjSiEji jiCapTSCap , ),(),( 2 4 1 5 3 s t 最小割：s-t图中容量最小的s-t割 2 4 1 5 3 s t 0 2 1 5 3 s t 0 2 1 2 0 s t 0 1 0 1 0 s t Pp tpspNE tsPV , , )|Pr(ln)bkg( )|Pr(ln)obj( ),( 1 2 )( exp, ,max1 2 2 , : BIR OIR qpdist II qpB qpBK pp pp qp Nqpq Pp “growth”：生长树S，T到两者接触即找到s-t路径 “augmentation”：扩张路径 “adoption”：修改树S，T Y. Boykov and M.-P Jolly. Interactive graph cuts for optimal boundary & region segmentation of objects in N- D images. In ICCV, vol. I, pp.105112, 2001. Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/