This paper addresses the problem of minimizing energy functions that arise in early vision tasks, such as image restoration, stereo, and motion estimation. The energy function is composed of a smoothness term, which ensures piecewise smoothness, and a data term, which measures the discrepancy between the estimated labels and observed data. The authors propose two algorithms that use graph cuts to find local minima of the energy function, even when large label changes are allowed. The first algorithm, based on $\alpha-\beta$-swap moves, generates a labeling where no swap move can decrease the energy. The second algorithm, based on $\alpha$-expansion moves, generates a labeling where no expansion move can decrease the energy, and it is shown that this solution is within a known factor of the global minimum. The key to these algorithms is the use of graph cuts to efficiently find the optimal move. For $\alpha-\beta$-swap moves, the graph is constructed based on the current labeling and the two labels being compared. For $\alpha$-expansion moves, the graph is constructed similarly but with additional auxiliary nodes to handle label changes. Experimental results demonstrate the effectiveness of these algorithms in various vision tasks, showing that they outperform simulated annealing in terms of both speed and solution quality. The paper also highlights the importance of choosing appropriate interaction potentials (semi-metrics and metrics) to ensure discontinuity-preserving properties and improve the overall performance.This paper addresses the problem of minimizing energy functions that arise in early vision tasks, such as image restoration, stereo, and motion estimation. The energy function is composed of a smoothness term, which ensures piecewise smoothness, and a data term, which measures the discrepancy between the estimated labels and observed data. The authors propose two algorithms that use graph cuts to find local minima of the energy function, even when large label changes are allowed. The first algorithm, based on $\alpha-\beta$-swap moves, generates a labeling where no swap move can decrease the energy. The second algorithm, based on $\alpha$-expansion moves, generates a labeling where no expansion move can decrease the energy, and it is shown that this solution is within a known factor of the global minimum. The key to these algorithms is the use of graph cuts to efficiently find the optimal move. For $\alpha-\beta$-swap moves, the graph is constructed based on the current labeling and the two labels being compared. For $\alpha$-expansion moves, the graph is constructed similarly but with additional auxiliary nodes to handle label changes. Experimental results demonstrate the effectiveness of these algorithms in various vision tasks, showing that they outperform simulated annealing in terms of both speed and solution quality. The paper also highlights the importance of choosing appropriate interaction potentials (semi-metrics and metrics) to ensure discontinuity-preserving properties and improve the overall performance.