 Journal of Image and Signal Processing 图像与信号处理, 2013, 2, 19-23 http://dx.doi.org/10.12677/jisp.2013.22003 Published Online April 2013 (http://www.hanspub.org/journal/jisp.html) Progress of Max-Flow Method in Image Denoising and Segmentation Xiaohuan Wang, Xiaoyi Yang, Jinping Song School of Mathematics and Information Sciences, Henan University, Kaifeng Email: wangxiaohuan861113@163.com, yxy@henu.edu.cn, songjp@henu.edu.cn Received: Jan. 20th, 2013; revised: Feb. 2nd, 2013; accepted: Mar. 14th, 2013 Copyright © 2013 Xiaohuan Wang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: In recent years, image denoising and segmentation model based on energy functional received widely atten- tion. Max-flow method is one of the most powerful tools to solve this kind of model. Discrete and continuous max-flow methods are introduced, they both include the basic steps in which energy functional minimization problem transformed to max-flow problem, and the solutions of the corresponding max-flow problem are also reviewed. In addition, the de- velopment of max-flow method are also discussed. Keywords: Max-Flow; Image Denoising; Image Segmentation 最大流方法在图像去噪和分割中的研究进展 王小欢，杨晓艺，宋锦萍 河南大学数学与信息科学学院，开封 Email: wangxiaohuan861113@163.com, yxy@henu.edu.cn, songjp@henu.edu.cn 收稿日期：2013 年1月20 日；修回日期：2013 年2月2日；录用日期：2013 年3月14 日 摘 要：近年来，基于能量泛函的图像去噪和分割模型得到广泛的关注，解决这类模型的有力工具之一是最大 流方法。本文分别介绍离散的和连续的最大流方法，包括能量泛函最小化问题转化为最大流问题的基本步骤， 以及相应最大流问题的求解方法，并展望最大流方法的发展前景。 关键词：最大流；图像去噪；图像分割 1. 引言 最大流方法是基于图论的一种全局最优方法，该 方法应用于图像去噪或分割问题的主要思路[1]是：将 图像映射为加权图，把图像像素看作图的顶点，邻接 像素之间的关系看作图的边，邻接像素之间的相似性 看作边的权值，根据边的权值设计能量函数，通过最 小化能量函数完成对图的分割，从而实现图像的去噪 或分割。该方法的优点在于：1) 图论是一门研究比较 早而且已经发展成熟的学科，具有较好的数学基础； 2) 图像和图之间非常类似，在图像映射为图之后，可 利用图论中的各种理论和数学工具进行分析和处理。 3) 最大流方法能够求解非凸模型的全局最优解，克服 多数方法只能找到逼近解的缺点。 最大流方法解决图像去噪或分割中能量泛函最 小化模型的一般框架[2]：1) 根据能量最小化模型构造 能量函数，从而将原问题转化为能量函数最小化问 题；2) 根据图像构造图，使能量与图论中图的割相对 应，从而将能量最小化问题转化为图论中图的最小割 问题；3) 根据最大流与最小割之间的等价关系(这种 等价关系又称为最大流/最小割原理)，将图的最小割 Copyright © 2013 Hanspub 19  最大流方法在图像去噪和分割中的研究进展 问题转化为最大流问题；4) 通过求解最大流问题，求 得图的最小割，从而获得图像去噪或分割问题的解。 最大流方法有多种分类方法，包括连续性和离散 性方法、确定性和随机性方法、全局和局部方法等。 本文分别介绍离散的最大流方法与连续的最大流方 法的步骤及其主要应用的模型，并对其特点进行分 析。 2. 离散的最大流方法 Greig 等于 20 世纪 80 年代末首次将最大流理论 应用于图像处理领域[3]，同时他最早提出使用组合优 化理论中的最小割/最大流算法来最小化计算机视觉 中的能量函数。20 世纪 90 年代末 Boykov 等[4]将该理 论应用到图像分割领域，提出了基于图割的交互式图 像分割方法。Gurholt 等在[5]中，在基于Mumfor d- shah 模型进行图像分割时采用水平集图割最小化方法。与 传统求解欧拉–拉格朗日方程的方法相比，这种方法 的优势在于不需要求解任何偏微分方程，而仅仅需要 在一个特别设定的图中计算出最小割。算法对于初值 非常稳定并且几乎是无参数的，能够快速地解决像素 点较多的分割问题。Bae等人在[6]中用能量最小化的 图割方法，这种方法仅仅是将去噪问题转化为一系列 简单的图表示问题，其与能量函数的梯度流相联系， 并且收敛于一个最小点。这种方法能够保持平滑的视 觉效果且能够保存图像中的尖锐特征。 2.1. 基于能量泛函的图像去噪模型 图像去噪的一般模型为 2du fx u 0 1 min2 uBV Du (1) 其中 表示理想图像，f表示观测图像， ， BV 为Banach 空间。其中的范数定义如下： :dxDu :0, M d us uu 函数 J称为是离散的全变分，如果对于任意的非 负凸函数 满足离散的共面积公式： J J uJXs (2) 其中 M 表示 M 维向量空间， s 是积分变量。 0,1 M us 0, if 1, if us i us i i i X表示向量，且满足： X us X us M 定理 1 若 J 是一个离散的全变分及 f，假 设 M u 是 2 1 min 2 M u J uuf 0 (3) ssEu 和的唯一解。则对于s，超水平集 s Eus 0,11 minM M ii i 的特征函数分别是 J sf (4) 的最大解与最小解。 由定理 1知，求解问题(1)等价于求解问题(4)。 2.2. 图的构造及割集容量 J如果(4)式中的 仅仅具有两两的相互作用， (4)式为 Pichard等在[7]中提出的二元伊辛能量，一般 形式为 , ,ijiji i ij i (5) ,0,, 0,1 ij i i ii 。 其中 这个模型能够在图上表示且可以由最大流算法 进行最小化。首先令 s f , , ,, 0, , ij ij ij ij 相邻 不相邻 ，及 ,GV 如下： 构造有向权图 1) 点集合 1, ,STSVM ，结点 和T 分为“源”和“汇”。 ,Si ， ,iT ,ij 1,ij M和 ，其中2) 有向边 。 它们的容量分别设为： , ,,1,, ,,1,, ,,1, i i ij cSi i M ciTi M ciji jM (6) max 0, ii 其中 max 0, ii ， ii i ， 。 3) 边集合 表示具有非零容量的边集。 在图上定义一个“割”将 分成两个集合 D和E， 并且 SD 和TE ， ,DE为割集。割集容量指满 足始点在源边，终点在汇边的所有边的容量之和： Copyright © 2013 Hanspub 20  最大流方法在图像去噪和分割中的研究进展 CDE , , ,, DE c 然后，若令 0,1 M 是 1, ,的 , 1 1 ijij j M i i SM特征函数，则 最小割问题为： 1, , ,1 1 ,1 MM ii ii ii MM ijiji i ij i CDE ,,ij ji 如果 ，上式与(5)式仅仅相差一个常数。 基于上述分析，图像去噪问题(1)可转化为问题 (5)，而求解问题(5)等价于求解最小割问题(7)，由最 大流算法可以对最小割问题进行求解，进而得到图像 去噪问题的解。 2.3. 离散的最大流算法 离散的最大流算法主要包括两大类[8]：推进重标 记算法和增广路径算法。 推进重标记算法[9,10]沿着非饱和边给一个到汇的 距离的低界估计。然后，面向具有到汇最小估计距离 的顶点来推进剩余的流。随着推进操作，边逐渐饱和， 距离逐渐增加。该算法易于并行实现，通常采用GPU 加速实现来提高效率。 Ford 和Fulkerson 的标号算法是基于增广路径的 方法[11]，通过标号不断生长一棵树，直到找不到关于 可行流的增广路径为止。这种算法的计算复杂性和网 络的节点数或边数无关，而与边上的权值有关。为了 避免求最大流时计算复杂度依赖于边的权值大小的 缺点，Dinic 设计了一种分层算法[12]。为了进一步提 高最大流算法的效率，Boykov 等提出了基于增广路径 的新算法[13]，该算法在图像去噪和分割的应用非常广 泛。其核心是建立两棵搜索树 S和T，S以源点 s为 根，T以汇点 t为根。树 S中所有父结点到子结点的 边都是不饱和的。树 S中的结点分为主动结点和被动 结点，主动结点可以通过从树T获得新的后代来使得 搜索树“生长”，被动结点不能生长。算法重复以下 三个阶段： 1) 生长阶段：搜索树S、T生长，直到找 到汇点；2) 扩展阶段：扩展路径，搜索树变成森林； 3) 收养阶段：收养孤立结点，恢复搜索树。 离散的最大流方法的一个缺点是存在网格偏倚。 两两的相互作用位势比其他方法惩罚的空间方向多， 这会在最终的结果中产生不需要的视觉效应，这种情 况通常被称为度量误差。而减少这样的视觉效应会导 致额外的存储和计算负担[14]。另一个缺点是离散的最 大流算法一般不能并行执行。 3. 连续的最大流方法 3.1. 连续的最大流方法的应用与发展 近些年来，连续的图割由于其度量误差小，而且 可以并行执行的优点受到了广泛的关注。其中 G. strang 在[15,16]最先在连续的区域中研究了最大流/最 小割相关的优化问题。其中在[15]中研究了在平面域 , x 里由向量场 y 来描述的网络流。其中的容量 约束条件类似于离散的网络流中的容量约束条件，为 ,cxy nf ，并且源和汇在边界上满足 div = ， 在内部满足 F ，G. S trang在其中证明了最大 的 (最大流)是由最小割决定的。离散的情况下对偶 问题的求解结果，是由最小割的特征函数得出的 0~1 解。在[16]中连续问题的求解依赖于有界变分函数的 共面积公式。G. Strang在[16]中研究了在容量约束 12 ,x,yvv c v ,VtFxy S 下，连续的最大流问题可以通过找到 t 的最大值，使得di 成立。其对偶问题可 以通过找到最小割 来求解，进一步得到原始问题的 解。目前这种模型已经在医学图像中有很广泛的应 用，但是在连续的最大流下的显流线，以及类似于有 向图的约束条件都需要进一步的研究。 Appleton 等在[17,18]提出了用一种连续的最小曲 面方法来分割维和 3维物体，并且用 PDE(Partial Differential Equation，简称偏微分方程)对它进行求解， 其具体模型构造如下： 2 P t F (8) FP t (9) 约束条件为 F g (10) 其中 g是流 F的容量上限。(9)式通过标量场 P的梯度 导出了流 F，并且(8)式和(9)式构成了一个简单的波动 方程系统。它们可以看作是描述具有压强 P和速度 F 的理想流体动力学的Navier-Stokes方程线性化形式。 Copyright © 2013 Hanspub 21  最大流方法在图像去噪和分割中的研究进展 (10)式是对流速 F大小的约束。这种方法已经成功地 运用到了医学图像的分割以及立体图像对的3维重 构，并且 维中的结果与现有的平面最小曲面算法结 果一致，在 3维图像分割和重构中的结果展示了这种 新的方法不存在网格偏倚。 2 1dxfxx Chan在[19]中提出了一种用凸方法来对连续的图 像区域进行分割的方法，主要是在求解连续的最小割 问题时： 0,1 2 min 1 d x x fxx TV x 0, 1x 将分拆函数 的二值约束松弛为凸集 0, 1x 。 Chan 证明出通过简单地设定阈值 0, 1x 2 R 会 产生一系列的全局二值最优解，即产生本原非凸分块 问题的全局最优二值解的集合。这种模型一般被看做 是没有先验监督的连续最小割模型。 Chan 的模型在[2 0-22 ]中被扩展到超过两个区域， 在其中提出了在连续的情况下多向割的方法并且应 用于多重标号问题。其中Bae 等在[20]中求解基于连 续的 Potts 模型条件的多重标号问题时，首先提出了 一种新的对偶模型，然后构造了一种基于对偶性的方 法，并且证明新的对偶模型的最优解等价于原始非凸 Potts 模型的最优解。对于处理不平滑的对偶问题，采 取的是基于对数函数的平滑方法。其算法在处理多重 标号问题时，效率相对较高。Lellmann 等在[21]中证 明多级标号这种组合问题可以通过凸优化方法解决， 并提出一种新的基于多维全变分公式的泛函，其优化 过程是通过 Douglas-Rachford 分裂在算子分裂框架中 实现的。这种方法可以用于解决ROF 类型子问题且 具有较高的效率，并且这种方法在应用到单一和多波 段图像时效果显著。T. Pock等在[22]在计算最小分块 问题时用一种凸松弛方法将Potts 模型改写为与之等 价的原始对偶全变分泛函，基于此提出了一种有效的 原始对偶投影梯度算法，其算法可以实现并行执行。 这种凸松弛方法在现有的松弛方法中优势明显，并且 在一些多重标号图像分割和立体问题中效果显著。但 是存在的缺点是这种方法不能保证得到 Potts 模型的 全局最优解。 3.2. 连续的最大流图像分割模型 Yuan 在[23]中提出了连续的最大流方法，基本思 想是先通过建立连续的最大流模型，并证明它是连续 的最小割问题的对偶问题，然后通过求解连续的最大 流问题，得到对应的连续的最小割的解。具体过程如 下： 令 x 为闭区域，s，t分别表示源点和汇点。 px，设经过点 x的空间流为；从 s到x的 有向源流为 s px ；从 x到t的有向汇流为 t px ,, max d st s ppp pxx 。则 连续的最大流模型为 (12) .,,, div 0 sstt st s tpxCxpx Cxpx Cx pxpxp x x 对上述模型中的等式约束引入乘子函数 ，连 续的最大流模型可以转化为与它等价的原始对偶模 型： ,, max min1 +div pd st st x ppp x px xpx xxx (13) .,, sstt s tpx CxpxCxpxCx 由最大最小定理， 对原始对偶问题的对偶变量 x 进行优化等价于对连续最大流模型(12)式进行 优化。同样地，对原始对偶模型(13)式中的流变量 , ss pxpx和 px 进行优化产生与它等价的对偶 模型： 0,1 min 1 d st x x Cx xCx Cxx x (14) x 可以证明，由(14)式 的最优解 可得原始非凸分 割问题的全局二值解。 3.3. 连续的最大流图像分割模型算法 000 ,, st pp ，令 ； 0k第一步：选取初值 第二步：通过求解 1argmax, ,, kkkk cst pCx pLppp ： 11 arg max,,, ss kkkk scst pxCx pLppp (15a) ： (15b) Copyright © 2013 Hanspub 22  最大流方法在图像去噪和分割中的研究进展 Copyright © 2013 Hanspub 23 11 ,, , kkk st ppp 1 arg max tt k tc pxCx pL ： 111kk st pp (15c) [3] D. Greig, B. Porteous and A. Ssheult. Exact maximum a poste- riori estimation for binary images. Journal of the Royal Statisti- cal Society, Series B, 1989, 51(2): 271-279. [4] Y. Bovkov, M. P. Jolly. Interactive organ segmentation using graph cuts. Proceeding of the 3rd International Conference on Medical Image Computing and Computer-Assisted Intervention, Pittsburgh: Springer, 2000: 276-286. 1 div kk k cp (15d) 第三步：若 1 1 kk k = k err ，则终止算法， [5] T. P. Gurholt, X.-C. Tai. 3D multiphase piecewise constant level set method based on graph cut minimization. Numerical Mathe- matic s: T he or y, Methods and A pplications, 2009, 2: 403-420. 得出解 。否则令 ，返回执行第二步。 1kk [6] E. Bae, J. Shi and X. -C. Tai. Graph cuts for curvature based image denoising. IEEE Transactions on Image Processing, 2009: 1-30. 连续的最大流可以克服网格偏倚的缺点，并且可 以去除或减少不需要的视觉效应。 [7] J. C. Picard, H. D. Ratliff. Minimum cuts and related problems. Networks, 1975, 5(4): 357-370. [8] Y. Bovkov, O. Veksler. Graph cuts in vision and graphics: Theo- ries and applications. Handbook of Mathematical Models in Computer Vision, NewYork: Springer, 2006: 79-96. 4. 结束语 [9] B. V. Cherkassky, A. V. Goldberg. On implementing the pushre- label method for the maximum flow prob- lem.Algorithmica,1997,19(4):390-410. 最大流方法的优点非常明显：1) 在全局最优的框 架下进行去噪或分割，保证了能量函数的全局最优 解； 2) 同时利用了图像的像素灰度信息和区域边界信 息，使去噪或分割效果有所提高。根据 Ford 和 Fulkerson 的对偶定理，在离散的和连续的情况下，均 已有许多快速算法。最大流方法由于能够避免其他优 化方法固有局部最优的缺点已被广泛应用于计算机 视觉中极小化能量函数，为进一步的图像分析与图像 理解奠定基础。虽然最大流方法可以得到全局最优解 或逼近最优解，计算效率高。但是其缺点是只能应用 到某类能量函数。需要扩展应用到更多的能量函数， 而这一点需要更多的研究工作。 [10] Goldberg A V,Tarjan R E.A new approach to the maximum-flow problem.Journal of the ACM,1988,35(4):921-940. [11] Ford L,Fulkerson D.Flows in Networks.Princeton:Princeton University Press, 1962. [12] Dinic E A. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics- Doklady, 1970, 11(5): 1277-1280. [13] Y. Boykov, O. Veksler and R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Ana- lysis and Machine Intelligence, 2001, 23(11): 1222-1239. [14] V. Kolmogorov. What metrics can be approximated by geo-cuts or global optimization of length/area and flux. ICCV, 2005: 564- 571. [15] G. Strang. Maximal flow through a domain. Mathematics Pro- gramming, 1983, 26: 123-143. [16] G. Strang. Maximum flows and minimum cuts in the plane. Advances in Mechanics and Mathematics, 2008, III: 1-11. [17] B. Appleton, H. Talbot. Globally optimal surfaces by continuous maximal flows. Digital Image Computing: Techniques and Ap- plications, 2003: 987-996. [18] B. Appleton, H. Talbot. Globally minimal surfaces by continu- ous maximal flows. IEEE PAMI, 2006: 28. 5. 致谢 [19] T. Chan, S. Esedoglu and M. Nikolova. Algoritms for finding global minimizers of image segmentation and denoising models. SIAM Journal on Applied Mathematics, 2006, 66(5): 1632-1648. 河南大学数学与信息科学学院的庞志锋副教授 对本文提供了非常有益的帮助，特此致谢。同时感谢 国家自然科学基金(11001075)和河南省 教育厅自 然科 学基础研究基金(2009B110006)对本文提供的资助。 [20] E. Bae, J. Yuan and X.-C. Tai. Convex relaxation for multiparti- tioning problems using a dual approach. Technical Report CAM 09-75, UCLA, CAM, 2009 September. [21] J. Lellmann, J. Kappes, J. Yuan, F. Becker and C. Schnorr. Con- vex multi-class image labeling by simplex-constrained total va- riation. Technical Report, HIC, IWR, University Heidelberg, 2008 November. [22] T. Pock, A. Chambolle, H. Bischof and D. Cremers. A convex relaxation approach for computing minimal partitions. CVPR, Miami, 2009. 参考文献 (References) [1] 刘松涛, 殷福亮. 基于图割的图像分割方法及其新进展[J]. 自动化学报, 2012, 38(6): 911-922. [23] J. Yuan, E. Bae and X.-C. Tai. A study on continuous max-flow and min-cut approaches. IEEE, 2010: 2217-2224. [2] 杨建功, 汪西莉. 一种结合图割与双水平集的图像分割方法 [J]. 计算机工程与应用, 2012, 48(3): 195-197. |