Noname manuscript No. (will be inserted by the editor) Mutilabel MRFs with Label Adjacency Constraint: Globally Optimal Solutions and Applications

Abstract This work addresses the problem of optimally solv-ing Markov Random Fields(MRFs) in which labels obey a certain topology constraint. Utilizing prior information, such as domain knowledge about the appearance, shape, or spatial configuration of objects in a scene can greatly im-prove the accuracy of segmentation algorithms in the pres-ence of noise, clutter, and occlusion. Nowhere is this more evident than in the segmentation of biomedical images, where typically the spatial relationships among the image regions inherently reflect those of the anatomical structures being imaged. In this work, we propose a new methodology to segment a special class of images, which exhibit nested layer topologies often encountered in biomedical applications. The segmentation problem is modeled using multi-label Markov Random Fields with an additional label adjacency constraint (LAC). The multi-label MRF energy with LAC is transformed via boolean variables encoding into an equivalent function of binary variables. We show this boolean function is sub-modular, graph representable, and can be minimized exactly and efficiently with graph cut techniques. Our experimental results on both synthetic and real images demonstrate the utility of the proposed LAC segmentation algorithm