发布时间 : 星期六 文章基于预流推进的最小标号最大流算法更新完毕开始阅读9bd60880fd4ffe4733687e21af45b307e971f90c
满足：d（t）=0，d（i）≤d（j）+1，（i， j）∈E（G），则称该距离标号是有效的。
定义4E（i， j）为允许弧当且仅当d（i）=d（j）+1，（i， j）∈E（G）。
定义5给一种完全规则网络，若网络中的所有节点v都以某个给定数量k与其邻居节点相连接，则这种网络被称为最邻近偶和网络，其中k决定了网络的稀疏程度。 定义6若网络中的所有节点对都以p概率相连接，则这种网络被称为ER（Erdos and Renyi）随机网络[15]，其中p决定了网络的稀疏程度。
2基于能量函数最小化的图像分割 文献[12]中给定能量函数：
E（L）=∑p∈PDp（Lp）+∑（p，q）∈NVp，q（Lp，Lq） 其中：L表示像素点V的某种属性如灰度；∑p∈PDp（Lp）表示似然能；∑（p，q）∈NVp，q（Lp，Lq）表示先验能；N表示像素中所有节点对，基于能量函数的图像分割可通过能量函数最小化实现，最小割/最大流方法是求解这项最优化问题的可行方法之一。
文献[16]给出的Potts模型中似然项Dp（Lp）表示为：-ln（P（I（p））。其中：I表示选中像素p的灰度，P为选取的前景和背景种子节点的预测直方图。若像素p更接近于前景，P则选取前景直方图；否则选取背景直方图。 平滑项Vp，q
（Lp，Lq）表示为：T（I（p）≠I（q））?K（p，q），其中：T表示p像素和q像素灰度是否一致，一致时为0，不一致时为1；K是某种惩罚函数，与p像素和q像素的不一致性成反比例关系。
在图论方法中，被选取的种子像素根据灰度特征不同可划分为前景（foreground）和背景（background），其中起点s对应着前景，收点t对应着背景，且网络中的节点与图像中的像素一一对应。网络的构造分为两部分：第一部分是对能量函数似然项的构造，构造方法是计算节点vi与前景背景的相似程度，若与前景更相似，则构造一条从起点s到vi的弧，反之构造一条从vi到收点t的弧，弧的容量为似然项能量；第二部分是对平滑项的构造，本文采用了四邻接构造方法，即对vi的周围4个节点分别构造一条弧，弧的容量通过平滑项函数计算，网络图构造的过程如图1所示，节点对之间弧的方向用短线标注，从短线末端到与弧的交点为正方向。 箭头是有指向的，目前图中的只是个短线，且短线是如何表示方向，是指向哪个方向，这种表述方式是否是该研究领域比较通用的方式还是自己这么表示的？目前的短线不能称之为箭头，且不知道指如何表述方向，请说明其中连接节点直线上的箭头表示弧的方向
在使用最小割/最大流算法进行图像分割时，网络的两个割集分别为前景集合与背景集合中的所有像素点，即将图像
的前景与背景分离。该过程中，最大流算法的速度决定着完成图像分割的快慢，而图像分割的质量与精确度由能量函数的构造决定，故本文实验仅验证算法执行速度。 3预流推进算法
3.1预流推进算法的框架与活跃节点选取规则 预流推进算法突破了传统增广链算法每进行一次流量调整就需重新选择一条增广链的思想，引入了“伪流”概念，并分为以下3步：1）从收点t开始采用反向宽度优先算法[17]构距离标号并将起点标号置为节点数n，从起点s向其出弧节点执行一次饱和推进，并更新剩余网络；2）判断网络中是否存在活跃节点，如果不存在则算法结束，否则选取某个活跃节点vi执行预流推进；3）寻找vi的允许弧，若能将vi盈余流量全部推进则转第2）步，若vi没有允许弧或不能将vi盈余流量全部推进，则置vi距离标号为：min{d（j）+1|（i， j）∈G′（M）}，转第2）步。可见预流推进算法相比传统增广链算法更为简洁高效。增广链算法的核心是增广链的选取方法，预流推进算法的核心则是活跃节点的选取。预流推进算法的复杂度上界为O（mn2），同时也是增广链算法复杂度的下界。列队预流推进亦为先进先出预流推进，其活跃节点选取遵循先进先出原则，最高标号预流推进（Highest Label Preflow Push， HLPP）算法的活跃节点选取总是遵循最高距离标号原则。最高标号思想认为，每次选择
最高标号活跃点，将大幅度降低活跃节点的寿命，从而达到降低时间复杂度的目的，如引言中描述，最高标号预流推进算法理论时间复杂度远低于普通预流推进算法。 3.2预流推进算法的优势与劣势
传统增广链算法在找到增广路径并进行饱和推进后，需重新选择一条增广路径，因此执行过程中存在冗余操作，以图2为例，使用增广链算法需分别找到s-a1-b1-c1-d1-e1-t、s-a1-b2-c2-d2-e2-t、s-a1-b3-c3-d3-e3-t三条路并分别执行一次饱和推进，因此执行过程是串行的，而在使用预流推进算法计算时，盈余点会从s转移至a1，然后沿b1、b2、b3三个方向同时转移，执行过程是并行的，当s和a1之间存在一条很长的单链时，预流推进不寻找重复路线的优势就得到体现。 然而，预流推进也存在劣势，图2网络实例中所有的流量均能从发点s流至收点t，但并非所有网络都能够达到图2中的理想状态，如图3中的网络所示。在图3（b）中，d组节点的盈余不能向e组节点完全输送，这就必然导致回溯现象发生；根据最高标号预流推进的方法执行后，位于图3（c）中e处的盈余流量不会立即输送到t得到最终结果，而是首先选择距离标号较高的d组节点，并将其位势升高到4以完成向c组节点的推进；只有当回溯过程结束后，如图3（d）所示，e组节点的盈余才能够流向收点t并完成计算，因此，当回溯现象存在时，HLPP算法会花费较长时间完成这一过程，