  Several supermodular losses have been shown to improve the perceptual quality
of image segmentation in a discriminative framework such as a structured output
support vector machine (SVM). These loss functions do not necessarily have the
same structure as the one used by the segmentation inference algorithm, and in
general, we may have to resort to generic submodular minimization algorithms
for loss augmented inference. Although these come with polynomial time
guarantees, they are not practical to apply to image scale data. Many
supermodular losses come with strong optimization guarantees, but are not
readily incorporated in a loss augmented graph cuts procedure. This motivates
our strategy of employing the alternating direction method of multipliers
(ADMM) decomposition for loss augmented inference. In doing so, we create a new
API for the structured SVM that separates the maximum a posteriori (MAP)
inference of the model from the loss augmentation during training. In this way,
we gain computational efficiency, making new choices of loss functions
practical for the first time, while simultaneously making the inference
algorithm employed during training closer to the test time procedure. We show
improvement both in accuracy and computational performance on the Microsoft
Research Grabcut database and a brain structure segmentation task, empirically
validating the use of several supermodular loss functions during training, and
the improved computational properties of the proposed ADMM approach over the
Fujishige-Wolfe minimum norm point algorithm.
