The maximum flow algorithm for minimizing energy
functions of binary variables has become a standard tool in
computer vision. In many cases, unary costs of the energy
depend linearly on parameter $\lambda$. In this paper we study vision
applications for which it is important to solve the maxflow
problem for different $\lambda$’s. An example is a weighting
between data and regularization terms in image segmentation
or stereo: it is desirable to vary it both during training
(to learn $\lambda$ from ground truth data) and testing (to select
best $\lambda$ using high-knowledge constraints, e.g. user input).
We review algorithmic aspects of this parametric maximum
flow problem previously unknown in vision, such as
the ability to compute all breakpoints of $\lambda$ and corresponding
optimal configurations in finite time.
These results allow, in particular, to minimize the ratio
of some geometric functionals, such as flux of a vector field
over length (or area). Previously, such functionals were
tackled with shortest path techniques applicable only in 2D.
We give theoretical improvements for ``PDE cuts'' [5].
We present experimental results for image segmentation, 3D
reconstruction, and the cosegmentation problem.