该文章中提出两种算法来解决以下能量最小化问题：

其中p,q为像素坐标，f为像素标记，V表示互动势能(interactive potential/energy)，D表示单点势能(unary potential)，也可以称为保真度，即该标记与其对应像素的契合程度。

其中alpha和beta表示两类标号，V表示两类标签之间的惩罚函数。第一个条件表示只有相同类别之间的连接惩罚（代价）为0；第二个条件表示改惩罚函数不具有方向异性，即从alpha节点到beta节点的连接和从beta到alpha节点之间的连接相同，切惩罚值为非负；第三个条件表明惩罚函数满足三角形边长的几何特性，即任意两类标记之间的惩罚函数值小于等于这两类标号与第三类之间惩罚值之和。只满足前两个条件，不满足第三个条件的惩罚函数称为具有Semimetric性质。

该文中针对具有Metric和Semimetric性质的能量最小化问题，分别提出了两种不同的算法来进行优化：

其中Fig. 3中的第一种算法是基于alpha-beta交换算法，该算法适用于互动势能V具有“半度量”(Semimetric)性质的情况；第二种alpha扩张算法适用于V具有“度量”（Metric）性质的情况。针对多标签标记的能量优化问题，这两种算法的步骤大致相似，都是从随机标签开始，然后采用迭代的方式，逐渐更新类标签来对能量函数进行最小化；其中第一种算法每次迭代时尝试交换两类中的若干标签的使得能量函数减小，而第二种算法每次迭代对尝试扩大任意一类的标签使得能量函数减小。这两类算法中的第3步中都涉及一个子优化问题。

alpha-beta交换算法的子问题是在一次alpha-beta交换构成的标记取值空间内找出具有使能量函数最小的新的标记，即找出最优的单步alpha-beta交换动作；alpha扩张算法的子问题是在一次alpha扩张构成的标记取值空间内找到使得能量函数最小的新的标记，即找出最优的alpha扩张动作。文中指出这两类问题都可以通过构建图模型，采用图割(graph cuts)的方法进行优化求解。

为了用graph cuts获取标记场中任意两个标签alpha和beta之间的最佳交换动作，需要首先构造相应的图模型，该图模型由当前标记场f、待优化标签alpha和beta决定。图模型由节点和连接构成。其中，待构造的图模型的节点分为两部分，一部分成为终端节点(terminal nodes)，包含与alpha和beta对应的两个节点，另一部分为与像素对应的标记节点，包括当前标记场中所有被标记为alpha和beta的像素对应的标记节点；待构造的图模型的连接也分为两类，一类为标号节点与终端节点之间的连接，每个标签节点都与alpha和beta的终端节点连接，这些连接简称为t连接，另一类连接是标记节点之间的连接，这类连接只存在部分标记节点之间。如果在原标记场f中f_p和f_q是相邻(neighbour)的，那么这两个标记节点之间存在连接e_pq，反之，则二者之间不存在连接，这些连接简称为n连接。

除了图模型拓扑结构的构造外，还应为图模型的各个连接赋予权重，不同类型的连接的权重计算如下表所示

3.2最优alpha扩张动作获取

文中第四和第五节中通过理论证明得出，单步迭代的最优解为通过以上两种方法构造出的图的最小割(Minimum Cut). 记图模型为G=（V,E），其中V为包含两个特殊的终端节点的节点集合，E为图模型中所有连接的集合。图模型的最小割就是要找到一个属于E的子集C，使得两个终端节点终端节点通过E-C中的任意个连接无法连接在一起，同时使得割集C的代价最小，即割集C中所有连接的权重之和最小。最小割问题已经可以有很多不同的求解方法，作者在下列文献中提出了一种近似线性复杂度的快速求解方法：

Y. Boykov and V. Kolmogorov, ªAn Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision,º Proc. Int'l Workshop Energy Minimization Methods in Computer Vision and Pattern Recognition, pp. 359-374, Sept. 2001.