randomwalk.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials,Leo Grady,Gareth,Funka,-Lea,ECCV04 Workshop on CVAMIA&MMBIA,Outlines,背景简述,随机游走理论,基于随机游走的图像分割,相关扩展,Background,医学图像中的器官分割对诊断有重要意义,常用方法：,WaterShed,Snake,Levelset,Graphcut,局限：,无法充分交互,复杂边界,漏边界,同时分割多区域,Random Walker,一维图随机游走,二维图随机游走,加权图随机游走,1D Random Walker,目的地,陷阱,从某点出发,随机向左右移动,移动概率相同,到达,0,点或,N,点则不能移动,求此点到达目的地,N,点的概率,N,1D Random Walker,目的地,陷阱,N,1D Random Walker,目的地,陷阱,N,2D Random Walker,Weighted Random Walker,P=0.6,P=0.2,P=0.05,P=0.15,Image Segmentation,将图像考虑成一张图,(Graph),像素对应,G,上节点,根据亮度差值定义节点间权重,用户指定确定的前景背景标签（红色箭头）,Consider As A Graph,标记点,标记点,标记点,权重,Calculation,到达,L1,的概率,到达,L2,的概率,到达,L3,的概率,L2,L3,L1,Result,Segmentation Solver,Dirichlet,边界条件问题,共轭梯度法可解,求解有冗余,一种效率更高的解法：,L.Grady,et al,Anisotropic interpolation on graphs:The combinatorial,Dirichlet,problem.,（示意）,Discrete,Laplacian,Matrix,离散拉普拉斯矩阵,设标记点,M,和未标记点,U,分类，矩阵可分解为：,和,相邻,其它情况,Sparse Linear Systems,离散拉普拉斯矩阵,令,对于每个标记点,合记为,Algorithm Summary,用户指定标记点,V,M,将图像映射为图,G,，边权重由前所示,求解每一个未标记节点,i,随机游走到每一个标记点的概率,节点属于的类为 ，由此完成图像分割,Advantages,速度快,无须迭代,可以,GPU,加速,效果好,充分利用了用户输入的信息,一次性划分多个区域,降低了漏边界的风险,Boundary Leak,弱边界,边界处对比度,噪声污染,Weak Boundaries,泄漏概率仅,1/4,A,B,4,3,5,C,Weak Boundary Result,Experiments,Experiments,Further Improvements,用,GPU,求解,RW,L.Grady,Random Walks for Interactive Organ Segmentation in Two and Three Dimensions:Implementation and Validation,MICAI05,先验模型引导,RW,L.Grady,et al,Multilabel,RandomWalker,Image Segmentation Using Prior Models,CVPR05,用,RW,做,alpha,扣图,L.Grady,et al,Randomwalks,For Interactive Alpha-Matting,VIIP05,Prior Model,Why?,原图,标准,RW,使用先验模型,Prior Model,How?,Alpha Matting,原始图,Trimap,Poisson,Grabcut,RW,LPP Space,Locality Preserving Projections,X.He,and,P.Niyogi,Locality preserving projections,NIPS03,比,RGB,空间能够更好的识别边界信息,Thanks,