An ILP model for multi-label MRFs with connectivity constraints

• Verfasst von: Shen, Ruobing [VerfasserIn]
• Verfasst von: Tang, Bo [VerfasserIn]
• Verfasst von: Lodi, Andrea [VerfasserIn]
• Verfasst von: Tramontani, Andrea [VerfasserIn]
• Verfasst von: Ben Ayed, Ismail [VerfasserIn]
• Titel: An ILP model for multi-label MRFs with connectivity constraints
• Verf.angabe: Ruobing Shen, Bo Tang, Andrea Lodi, Andrea Tramontani, Ismail Ben Ayed
• E-Jahr: 2020
• Jahr: 27 May 2020
• Umfang: 9 S.
• Fussnoten: Gesehen am 27.08.2020
• Titel Quelle: Enthalten in: Institute of Electrical and Electronics EngineersIEEE transactions on image processing
• Ort Quelle: New York, NY : IEEE, 1992
• Jahr Quelle: 2020
• Band/Heft Quelle: 29(2020), Seite 6909-6917
• ISSN Quelle: 1941-0042
• DOI: doi:10.1109/TIP.2020.2995056
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: Computational modeling
• Sach-SW: Computer vision
• Sach-SW: energy minimization
• Sach-SW: Image segmentation
• Sach-SW: integer programming
• Sach-SW: Labeling
• Sach-SW: Machine learning
• Sach-SW: Markov random fields
• Sach-SW: markov random-fields
• Sach-SW: Optimization
• Sach-SW: Particle separators
• Sach-SW: Semantics
• K10plus-PPN: 172791516X

Abstract

Integer Linear Programming (ILP) formulations of multi-label Markov random fields (MRFs) models with global connectivity priors were investigated previously in computer vision. In these works, only Linear Programming (LP) relaxations [1] or simplified versions [2] of the problem were solved. This paper investigates the ILP of MRF with exact connectivity priors via a branch-and-cut method, which provably finds globally optimal solutions. It 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 be applied as a post-processing method on top of any existing multi-label segmentation approach. As it provides globally optimal solution, it can be used off-line to serve as quality check for any fast on-line algorithm. Furthermore, the scribble based model presented in this paper could be potentially used to generate ground-truth proposals for any deep learning based segmentation. We demonstrate the power and usefulness of our model by extensive experiments on the BSDS500 and PASCAL VOC dataset. The experiments show that our proposed model achieves great performance, yielding provably global optimum in most instances and that provably good optimization solutions also provide good segmentation accuracy, even with the limited computing time of few seconds.