  We propose a novel segmentation method based on energy minimization of
higher-order potentials. We introduce higher-order terms into the energy to
incorporate prior knowledge on the shape of the segments. The terms encourage
certain sets of pixels to be entirely in one segment or the other. The sets can
for instance be smooth curves in order to help delineate pulmonary vessels,
which are known to run in almost straight lines. The higher-order terms can be
converted to submodular first-order terms by adding auxiliary variables, which
can then be globally minimized using graph cuts. We also determine the weight
of these terms, or the degree of the aforementioned encouragement, in a
principled way by learning from training data with the ground truth. We
demonstrate the effectiveness of the method in a real-world application in
fully-automatic pulmonary artery-vein segmentation in CT images.
