Integer Linear Programming (ILP) formulations of Markov random fields (MRFs) models with global connectivity priors were investigated previously in computer vision, e.g., globalinter,globalconn . In these works, only Linear Programming (LP) relaxations globalinter,globalconn or simplified versions graphcutbase of the problem were solved. This paper investigates the ILP of multi-label MRF with exact connectivity priors via a branch-and-cut method, which provably finds globally optimal solutions. The method enforces connectivity priors iteratively by a cutting plane method, and provides feasible solutions with a guarantee on sub-optimality even if we terminate it earlier. The proposed ILP can also be applied as a post-processing method on top of any existing multi-label segmentation approach. We demonstrate the power and usefulness of our model by several experiments on the BSDS500 image dataset, as well as on medical images with trained probability maps.
Exact global connectivity potentials are formulated as an ILP in @cite_3 , where connected subgraph polytopes are introduced. Due to the high computational cost of solving the corresponding @math -hard problem, the work in @cite_3 examined only LP relaxations of the ensuing ILP. Although the general formulation works for multi-label MRFs, the authors applied it only to binary MRF problems. In @cite_22 , the authors optimized exactly a linear (unary-potential) objective subject to connectivity constraint in a binary segmentation problem. It solves two instances of medical benchmark datasets to optimality for the first time. However, the model does not apply to the general multi-label pairwise MRF objective in , which is of wide interest in vision applications. Finally, it is worth mentioning that the subgraph connectivity problem also plays an important role in the operations research community, and has been applied, for instance, to the forest planning problem @cite_10 , where each subregion of the forest is constrained to be connected.
@cite_10 @cite_22 @cite_3
2150408365 2465405228
Connectivity requirements are a common component of forest planning models, with important examples arising in wildlife habitat protection. In harvest scheduling models, one way of addressing preservation concerns consists of requiring that large contiguous patches of mature forest are maintained. In the context of nature reserve design, it is common practice to select a connected region of forest, as a reserve, in such a way as to maximize the number of species and habitats protected. Although a number of integer programming formulations have been proposed for these forest planning problems, most are impractical in that they fail to solve reasonably sized scheduling instances. We present a new integer programming methodology and test an implementation of it on five medium-sized forest instances publicly available in the Forest Management Optimization Site repository. Our approach allows us to obtain near-optimal solutions for multiple time-period instances in fewer than four hours. Several important tasks in medical image analysis can be stated in the form of an optimization problem whose feasible solutions are connected subgraphs. Examples include the reconstruction of neural or vascular structures under connectedness constraints.