发布时间 : 星期日 文章基于预流推进的最小标号最大流算法更新完毕开始阅读9bd60880fd4ffe4733687e21af45b307e971f90c
在误差产生时，节点可以在修改距离标号的过程中参考出弧节点距离标号并自动修正。 5.6图像分割仿真实例
图像分割可以理解为从所给定的图像中分割出所需信息，如图7所示。本文图像分割实验中的能量函数构造使用Potts模型，并按第2章中的方法构造网络，实验中图像尺寸为75×50像素提升至600×400像素，由于图像像素众多，构造的网络规模十分庞大，因此在进行实验时使用分块构造方法，每块图像大小不超过50×50像素，图像的拆分与合并时间不计入算法执行时间中，实验结果如图8所示。由图8可知：预流推进算法在图像分割时较Dinic算法具有速度优势，而本文算法效果优于最高标号预流推进算法，性能提升超过50%。该实验与5.2节中实验结果存在差异的原因在于，通过四邻接方法构造的网络稀疏程度极高，无论是执行回溯过程还是判断回溯是否发生都占据了较高的执行时间比例。 6结语
在实际应用中如图像处理领域，大多数网络均为稀疏网络，本文算法能为这些领域提供较为高效的工具，提高衍生产品的实用价值。同时该算法的容错能力可以对网络的精确性适当放宽，特别是在动态网络中，容许一定概率错误，尽管这些错误有可能导致误差，但误差在可接受范围内。此外本文算法还可以嵌入最高标号预流推进中，兼顾了在复杂稀
疏网络上的执行效率。然而，该算法仍旧存在不足之处，如实际应用中的网络规模会远大于实验规模，尽管用稀疏矩阵或者哈希表作为容器能解决存储问题，分块运算能够在理论复杂度与精确度中找到平衡，但算法不具备实时运算功能，因此还需结合近似方法及收缩图方向展开深入研究。 参考文献： [1]
ARBELAEZ P， MAIRE M， FOWLKES C， et al. Contour detection and hierarchical image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（5）： 898-916. [2]
LI C， HUANG R， DING Z， et al. A level set method for image segmentation in the presence of intensity in
homogeneities with application to MRI [J]. IEEE Transactions on Image Processing， 2011， 20（7）： 2007-2016. [3] FULKERSON D R， DANTZIG G B. Computation of maximal flows in networks [J]. Naval Research Logistics Quarterly， 1955， 2（4）： 277-283. [4]
FORD L R， FULKERSON D R. A suggested computation for maximal multicommodity network flows [J]. Management
Science， 1958， 5（1）： 97-101. [5]
GOLDBERG A V. Recent developments in maximum flow algorithms[C]// Proceedings of the Algorithm Theory 一字线在英文中与前后字母间是否有空格？― SWAT98， LNCS 1432. Berlin： Springer， 1998： 1-10. [6]
EDMONDS J， KARP R M. Theoretical improvements in algorithmic efficiency for network flow problems [J]. Journal of the Association for Computing Machinery， 1972， 19（2）： 248-264. [7]
KARZANOV A V. Determining the maximal flow in a network by the method of preflows [J]. Soviet Mathematics Doklady， 1974， 15： 434-437. [8]
CHERKASSKY B V， GOLDBERG A V. On implementing the push ― relabel method for the maximum flow problem [J]. Algorithmica， 1997， 19（4）： 390-410.