基于随机游走的使用色彩空间图形图像分割.doc

1、10基于随机游走的使用色彩空间图形图像分割摘要：图像分割是研究计算机视觉领域涉及最多的话题之一，已经吸引了大量研究人员的关注。图像分割的目的是改变图像的表示使其更有意义和更容易分析。在这个过程中一个图像被划分到多个分配标签分割，来表示图像的像素，以使像素共享分为多个分割相同的标签，并且可以被表征为一个存在与该图像的不同对象。同时为了分割图像，已经设计出一些自动和半自动的方法。在本文中，我们将重点放在由Leo Grady介绍的随机游走半自动方法上，我们将提供一些使分割图像变的更好的改进，来比较图像利用上述所涉及的思想。我们将使用图分区的色彩空间和理论方法来重新定义两个像素之间的距离，从而产生一种

2、改进的分割方法。关键词：图像分割;随机游走;组合Dirichlet问题;色彩空间图; LUV空间;拉普拉斯矩阵;拉普拉斯方程。1引言 半自动或交互式分割在图像处理中一直是一个巨大的研究项目，并获得了很多的从事计算机视觉研究的人员的兴趣。主要目标是将部分的图像分割成不同区域，每个区域对应于一个特定对象的帮助下感兴趣的用户交互。用户输入需要初始化分割算法（半自动）为一个图像划分为不同的区域。可以以许多方式来提供用户输入，其中最简单的是利益所概述的，用鼠标点击该用户的区域。半自动分割在对图像的编辑，医学成像，机器视觉广泛的应用，目标检测，识别任务，交通控制系统，视频监控等众多领域有着巨大的重要性。一

3、些算法迄今为止开发的通用半自动分割,可以有效结合域知识来解决域的分割问题。 其他方面的半自动分割的重要性是一个具有挑战性的问题,因为任务是由一组小的用户数据初始化过程开始,然后传播在整个图像的信息虽然半自动图像分割方法有很多。但我们的重点放在Grady L.所提出的随机游走上面，同时尝试对算法做出了一些改进，提供了更好的方法来分割图像。随机游走方法具有几个优点。一般来说任何分割方案的重点是将图像划分成两个区域，即背景和对象。另一方面随机游走方法为我们提供了分割的图像为对象的数目，用户想要分割图像中物体的任意数量的灵活性。随机游动方法假定图像为图，其中的节点或顶点在图中是一组像素。边的权重代表了

4、一个节点到另一个节点的转移概率。所以在给定的情况下，它的方式比较灵活，更容易通过遍布图像传播用户所提供的资料。1.1 .论文结构 本文的结构如下。在第2节，我们解释了半自动方面所做的相关工作分割。第3节给出了L. Grady的随机游走方法的具体想法，我们简短介绍改进。第4节规定了技术的算法和结果，应用的图像分割。第5节显示实现随机游走算法在L. Grady的原创性成果上的质量改进。最后，在第6节，总结了我们的论文。2 .相关作品正如前面提到的，一些工作已完成，几种算法已经为半自动图像设计并且细分到现在。我们在这里讨论一些在该项目进行的相关工作。首先，我们可以看看由Boykov及Jolly介绍用

5、图割的交互式分割中的做法 。在这种方法中，用户通过标记的背景和对象提供种子。能量函数由两个不同的型号色彩和连贯性配制。能量函数标签的背景和前景设成0和1 ，并在最后通过使用标准的最大流最小割解决最小化问题。图割方法进一步工作已经完成。 Li等人提出的是分水岭的组合分割和图切割的最小化方法。Nagahashi等人提出了基于多尺度平滑的图像分割方案迭代图割方法。当时的想法是对逐步分割的对象从全球到区域使用图切割和高斯平滑迭代局部分割。 Shi等人提出了基于在图像分割新的方法，被视为一个图划分问题归削减和分割归一化剪切技术，并且用于分割图像。Rother等介绍了随附抢切术一图割的一个额外层的方法，可

6、以有更好的色彩造型和局部极小。Mortensen和Barrett推出的智能剪刀的技术。智能剪刀允许一个对象数字图像可以快速，准确地提取。用户需要使用鼠标简单的围绕感兴趣的对象绘制曲线手势，用鼠标手势来定位接近的物体边缘，火线边界环绕的对象。由L. Grady介绍的比上面提到的技术更灵活的随机游走方法将是本文的重点，因为它具有容易处理任意数量对象的先天优势。在这种过程输入由用户给定的分别是“种子”和从种子中获得的被传播到整个图像的信息。在这种方法中，初始作品包括概率的随机游动从一个给定的象素到达种子像素的计算。在过渡概率是成反比的不像素之间的对比度已经足够的理解。随机游走方法已经有了很多伸展的作

7、品。3 .随机游走方法的基本思想本节将介绍由L. Grady引入随机游走方法的细节。一个无向图可以表示为，其中和分别是一组顶点和该组的边缘。该组顶点的是一组存在于图像中的像素。顶点集可以划分为两个组顶点。一组是“标记顶点“，这是由用户标识的属于所述多个对象，即种子;和图像像素的其余部分是另一组或“未标记的顶点” 。该组的边缘的像素E由它们在图像中无论是使用标准4或8附近区域的邻居的对。视的灰度或彩色标度的强度之差在于这两个像素的边缘的权重可以表示为或。让，其中是灰度的任强度（标量）或彩色（ 3维向量），然后可表示为：其中，参数的值可以相应地调整。该区域中的边缘的权重(0,1);类似像素将具有接

8、近1的权重，而对于非常不同的像素的权重为接近0 。具有上述结构图在手，随机游走方法的思路如下。假定图像包括可能的对象k和属于这些对象的各一个标记顶点Vm。现在考虑一个加权边缘其端点e和以及的边的权重位于范围之内，并且可以被解释作为一个从一个顶点到另一个顶点随机游走的转换概率的测量。根据不同的权重边，如果和在颜色或强度很相似，随机游走很可能过渡形式就是从到，并且如果他们是非常不同的，不太可能做过渡。鉴于上述的转移概率，我们可以考虑一个特定的随机游动的曲线图。特别是，对于每个未标记的顶点，即一个随机游走开始于该顶点到达标记的顶点中的任一项的概率属于一个特定目的计算;此概率表示为数量。然后将图像分割

9、为根据这些概率进行。更具体地，对于任何顶点，如果同时，那我们将其归类为属于分割。注意图像中该边缘（如在图中相对的边缘）对应于低的转移概率，因为它们涉及颜色或强度的快速变化。因此，该算法将倾向于尊重图像边缘在执行分割。事实证明，概率可通过大型稀疏线性系统的解来计算。作为随机游走概率，该组合和Dirichlet问题有相同的解决方案。Dirichlet积分可以被定义为为一个字分割和区域。现在接下来的步骤是找到一个调和函数。调和函数的功能是满足拉普拉斯方程找到一个调和函数受其边界值的问题就是所谓的Dirichlet问题。由于拉普拉斯方程是Euler-Lagrange方程Dirichlet积分,谐波函数

10、满足边界条件最小化了Dirichlet积分。定义组合拉普拉斯矩阵其中由顶点被和索引。有了这些定义，我们就可以决定如何在发现相对可能性/潜力非种子节点，同时保持固定的种子节点的情况下去解决调和函数。Dirichlet积分的组合配方和一个组合谐波是一个函数，它最大限度地减少了积分。既然是半正定的，唯一的关键点会极小。分区的顶点分成两个集合， （标记/种子节点）和（非种子节点） ，使得和。需要注意的是包含所有种子点，不管他们的标签。我们可以假设无损失通用性，并在和节点进行排序，使得种子节点是第一个和非种子选手节点是第二个。因此，我们可以分解上述方程进其中和分别对应于种子和非种子节点的电位。对于区分并

11、找出临界点产量与未知数的线性方程系统。如果图是连通的，或者如果每个连接组件包含一个种子，那么这个方程将是非奇异的。通过为每个标签表示可能性（潜在的）假定节点。定义的标签设置为种子点作为一个函数，其中。在节点定义向量（其中表示基数）为每个标签，因此，对于标签，可通过求解发现并解决组合Dirichlet问题4.算法 对于许多现实生活的应用中，被分割感兴趣的对象是由多个颜色深浅从“远”的颜色光谱的地区。这就对随机游走一个不寻常的约束，如果两个像素之间的权重，是仅仅基于它们各自的色彩向量之间的欧几里得距离。例如，如果一个对象主要包括2颜色区域，其手段是和与作为一个较大的值“ ，那么任何对感兴趣的对象的

12、像素，这是 a)身体与相邻 b）的颜色值，分别将权重的边缘进行连接。此值将接近0 ，这将在这些像素之间禁止“转型”随机游走。这造成在目标分割的情况下，一个独特的问题。我们在这样做的动机只是解决因这种性质的障碍物的挑战。4.1 .基于图表的权重 在2中，概率分布为基础的权重已被用来解决这个问题。然而，在文献 2规定随机游走基于分割前应先基于过分割过程的均值漂移。基于均值漂移方法增加了算法的复杂性，我们调查，如果任何分割程序可以实现这种意愿与图像的过度分割基于预处理做掉。 注意，若是半监督分割的，用户拥有先验信息的“种子”的形式给了我们一些关于对象的更新的重要信息。用户通常感兴趣的对象上的“划痕”

13、，这给出了用户对颜色光谱构成该物体的区域的概念。理想情况下，如果一个对象包含聚集的地区色彩光谱，其手段是这样的，随机的步行者必须允许高转移概率，而穿越两个像素与来自该组颜色值。一种实现这一点的一种方法是通过预先指定（1）和之间的距离，并应被视为0和（2 ）接近的颜色矢量和之间具有小的距离。 一个实现上述的方法是通过可视化的颜色空间作为全连通图。在数字图像处理，我们通常与离散颜色值工作，所以可以想像每个颜色矢量作为一个完全连通图的一个节点。该重连接的颜色值和以及一个边缘的给出。最初，我们准备这种性质的图并指定权重同上。现在，一旦用户指定的种子信息可在该组中，用户的形式简单地分配到0连接的任何边的

14、权重。现在，我们应用任意两点间最短路径算法（Floyd-Warshall算法）到这个修正图中，这将给出任何2颜色 值之间的最短距离。我们现在准备在这两个节点和之间的距离和给定为新的图形和之间的最短路径的权重和英寸。需要注意的是这样的制剂同时满足要求（1）和（2） 。4.2 .使用LUV空间 不同于标准的RGB空间的工作，我们使用的CIE 1976 （L*，U*，V*已知的感知）颜色空间比RGB更有意义，L*，U*，V*的通常值在范围之间。这给出了一个总的节点的英寸。由于Floyd-Warshall算法具有计算的复杂性是顶点的数目这导致了我们的算法，变成了不可行的运行时间。所以，我们把每个颜色分

15、量L*，U*，V*分别放在8个箱里。当：令一个箱子为L轴。这样就产生了箱中的颜色空间，并将用为节点英寸的距离。均值之间的距离将是每个容器的颜色矢量的欧几里得距离。现在从该种子信息获取之后，用户需要从判断为是与属于并分配到零的那些箱之间边的权重的回收箱内得到2值和。那么Floyd-Warshall算法被执行，并且如前面所定义的构造。4.3 .使用随机游走 我们假设手头的任务是提供一种用于该用户已经提供种子信息中的形式分割对象套，其中代表标签。对于每一个我们做以下步骤A. 构建的曲线图，其中顶点是图像的像素。如果对应的像素4连接，那么两个顶点通 过边相连。B. 关于颜色空间构建图形和利用该组构建体

16、。颜色和之间在远处被表示 为。C. 如果且这两个顶点和相连接，并有颜色值，那么边的权重可以写做。D. 构造元素的拉普拉斯算子给出如下：其中：E.作为普通的随机游走方法1我们解决系统其中，当是顶点属于顶点集的标签的概率时，被定义为。对于任意一个顶点，如果以及那么我们可以把分类到分割中5. 结 本节显示了定性实验评价的算法。我们检查了我们的算法在50的图片，一些图像的分割结果如图1所示。我们与普通随机游动方法比较了我们的结果1。在图1中,我们取了四列的(a)列显示原始图像;(b)列显示标记(种子)形象;(c)列显示普通的分割结果随机游走方法1和(d)列显示我们的方法的分割结果。我们已经在两个区域分

17、割图像,对象和背景,即这里是两个的对象数。 在我们去解释我们的结果前有几个值得注意的点。在我们的实验中,用户输入是以“划痕”的形式，用户感兴趣的对象上的划痕与纯红色而背景与纯绿色的颜色。我们使用上面描述的LUV颜色空间部分。每种颜色组件在LUV的空间分为8箱。使用我们的方法进行图像分割后输出的原始图像显示了对象的兴趣颜色是黑色和使用普通随机游走分割后的输出图像的原始图像,也显示了对象的兴趣黑色。我们的方法应用于示例的输出图像图1比普通随机游走的输出方法拥有大量定性的改进。 现在我们集中的分析结果。在图1中,最上面一行显示的图像分割场景是海洋和一个坚实的草地。使用随机游走图在颜色空间上的分割比普

18、通随机游走算法分割更准确。在我们的方法中，两个对象的分离可以非常准确，而普通随机游走分割在分离这两个地区上有许多错误。第二行是一个动画形象和更稳定的背景期中应用了两个算法。在这种情况下,我们的方法确实能够很好的分割对象，而普通随机游走方法未能实现按照需要进行分割。 第三和第四行显示一只鹰和一只狗的图像以及稳定的背景。很明显,我们的分割方案给出了完美的分割图像达到了普通方法无法达到的精度。 第五个蛇是有复杂背景的形象。我们的基于颜色空间图技术产生一个完美的分割对象的沃克(蛇),但普通的随机方法几乎完全失败。类似的结果是第八行它显示了另一个蛇的分割图像。 第六行有一匹野马的形象。结果普通随机游走分

19、割方法忽略了一些对象的一部分,而我们的方法比前者准确得多。同样由第七行是复杂背景和一匹马,一个对象。我们的方法的分割结果也非常准确，普通的方法产生的结果和其他几幅图的结果一样。这两个输出分割使用我们的方法和普通的方法完成图像和第九行显示的飞行鹰在本质上是类似的。 示例图像用于第十和第十一行显示一群人(还有一种动物)与复杂背景以及皇家孟加拉虎藏在草丛中。我们的分割方案应用于这些图像输出的图像完全比普通的准确。6 .结论 本文展示了一种可以提高随机游走半自动分割方法的性能的技术。我们的方法比普通随机游走方案有两个显著变化。首先，我们考虑了图中一个完全连通图的颜色空间。之后当用户提供有用的种子信息后

20、，我们将其指派给该连接属于该组种子载体中的边缘为0的权重。在图的节点上我们使用随机漫步解决了方程的系统，来获取有关新图的转移概率图。在这个新的图上应用随机漫步比普通随机游走更加稳健，并有大幅度改善了分割图像的对象。参考文献：1 Leo Grady, Random walks for Image segmentation. IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL.28, NO. 11, NOV. 20062 Daniel Freedman, An improved Image Graph for Sem

21、i-Automatic Segmentation. Signal, Image and Video Processing 6(4): 533-545 (2012).3 T. Nagahashi, H. Fujiyoshi, T. Kanade: Image Segmentation Using Iterated Graph Cut Based on Multi-scale Smoothing. Computer Vision ACCV-2007. Lecture Notes in Computer Science Volume 4844, 2007, pp 806-816.4 J Shi, J

22、 Malik, Normalise Cuts and Image Segmentation. IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,VOL. 22, NO. 8, AUGUST 2000.5 O Sener, K Ugur, A. A. Alatan, Error-tolerant Intaractive Image Segmentation using Dynamic and Iterated Graph-Cuts. IMMPD12, November2,2012, Nara, Japan. Copyrig

23、ht 2012 ACM 978-1-4503-1595-1/12/11.6 Y. Boykov and M.-P. Jolly. Interactive organ segmentation using graph cuts. In Proceedings of the International Conference on Medical ImageComputing and Computer Assisted Intervention (MICCAI), pages 276286, 2000.7 Y. Boykov and M.-P. Jolly. Interactive graph cu

24、ts for optimal boundary and region segmentation of objects in N-D images. In Proceedings of IEEEInternational Conference on Computer Vision (ICCV), volume 1, pages 105112, 2001.8 Y. Li, J. Sun, C.K. Tang, and H.Y. Shum. Lazy snapping. In Proceedings of the International Conference on Computer Graphi

25、cs and InteractiveTechniques (SIGGRAPH), volume 23, pages 303308, 2004.9 C. Rother, V. Kolmogorov, and A. Blake. Grabcut: Interactive foreground extraction using iterated graph cuts. In Proceedings of the InternationalConference on Computer Graphics and Interactive Techniques (SIGGRAPH), pages 30931

26、4, 2004.10 E.N. Mortensen and W.A. Barrett. Intelligent scissors for image composition. In Proceedings of the International Conference on Computer Graphicsand Interactive Techniques (SIGGRAPH), pages 191198, 1995.11 W.A. Barrett and E.N. Mortensen. Fast, accurate, and reproducible live-wire boundary

27、 extraction. Lecture Notes in Computer Science, 1131:183192,1996.12 E.N. Mortensen and W.A. Barrett. Toboggan-based intelligent scissors with a four-parameter edge model. In Proceedings of the IEEE Conference onComputer Computer Vision and Pattern Recognition (CVPR), volume 2, pages 452458, 1999.13

28、L. Grady and G. Funka-Lea. Multi-label image segmentation for medical applications based on graph-theoretic electrical potentials. Lecture Notes inComputer Science, pages 230245, 2004.14 L. Grady. Multilabel random walker image segmentation using prior models. In Proceedings of the IEEE Conference o

29、n Computer Computer Visionand Pattern Recognition (CVPR), volume 1, pages 763770, 2005.15 D.M. Greig, B.T. Porteous, and A.H. Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society.Series B (Methodological), 51(2):271279, 1989.16 H. Lombaert, Y. Su

30、n, L. Grady, and C. Xu. A multilevel banded graph cuts method for fast image segmentation. In Proceedings of IEEE InternationalConference on Computer Vision (ICCV), volume 1, pages 259265, 2005.17 D. Freedman and T. Zhang. Interactive graph cut based segmentation with shape priors. In Proceedings of

31、 the IEEE Conference on ComputerComputer Vision and Pattern Recognition (CVPR), volume 1, pages 755762, 2005.18 O. Juan and Y. Boykov. Active graph cuts. In Proceedings of the IEEE Conference on Computer Computer Vision and Pattern Recognition (CVPR),volume 1, pages 10231029, 2006.19 N. Xu, N. Ahuja

32、, and R. Bansal. Object segmentation using graph cuts based active contours. Computer Vision and Image Understanding,107(3):210224, 2007.20 Y. Zeng, D. Samaras, W. Chen, and Q. Peng. Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in NDimages. Computer Vision a

33、nd Image Understanding, 112(1):8190, 2008.21 L. Grady and A.K. Sinop. Fast approximate Random Walker segmentation using eigenvector precomputation. In Proceedings of the IEEE Conferenceon Computer Computer Vision and Pattern Recognition (CVPR), pages 18, 2008.22 D. Singaraju, L. Grady, and R. Vidal.

34、 Interactive image segmentation via minimization of quadratic energies on directed graphs. In Proceedings of theIEEE Conference on Computer Computer Vision and Pattern Recognition (CVPR), pages 18, 2008.23 A.K. Sinop and L. Grady. A seeded image segmentation framework unifying graph cuts and random

35、walker which yields a new algorithm. InProceedings of IEEE International Conference on Computer Vision (ICCV), pages 18, 2007.24 C. Couprie, L. Grady, L. Najman, and H. Talbot. Power watersheds: A new image segmentation framework extending graph cuts, random walker andoptimal spanning forest. In Pro

36、ceedings of IEEE International Conference on Computer Vision (ICCV), pages 731738, 2009.25 A. Protiere and G. Sapiro. Interactive image segmentation via adaptive weighted distances. IEEE Transactions on Image Processing, 16(4):10461057, 2007.26 L. Vincent and P. Soille. Watersheds in digital spaces:

37、 an efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysisand Machine Intelligence, 13(6):583598, 1991.27 O. Duchenne, J.Y. Audibert, R. Keriven, J. Ponce, and F. S egonne. Segmentation by transduction. In Proceedings of the IEEE Conference onComputer Vision and Pa

38、ttern Recognition (CVPR), pages 18, 2008.28 S. Kakutani, “Markov processes and the Dirichlet problem,” Proc. Jap. Acad., vol. 21, pp. 227233, 1945.29 N. Biggs, “Algebraic potential theory on graphs,” Bulletin of London Mathematics Society, vol. 29, pp. 641682, 1997.30 J. Shi and J. Malik, “Normalize

39、d cuts and image segmentation,” IEEE PAMI, vol. 22, no. 8, pp. 888905, Aug. 2000.31 V. B. Eckmann, “Harmonische Funktionen und Randwertaufgaben in einem Komplex,” Commentarii Math. Helvetici, vol. 17, pp. 240255, 1945.32 W. T. Tutte, “How to draw a graph,” Proc. London Math. Soc., vol. 13, no. 3, pp

40、. 743768, 1963.33 X. Zhu, J. Lafferty, and Z. Ghahramani, “Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions,” inProceedings of the ICML 2003 workshop on The Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining, 2003, pp. 5865.34 J. Dodziuk, “Difference equations, isoperimetric inequality and the transience of certain random walks,” Transactions of the American MathematicalSoceity, vol. 284, pp. 787794, 1984.10