Learning discontinuous piecewise affine fitting functions using mixed integer programming over lattice

Ruobing Shen (), Bo Tang, Leo Liberti, Claudia D’Ambrosio and Stéphane Canu
Additional contact information
Ruobing Shen: Heidelberg University
Bo Tang: University of Toronto
Leo Liberti: Institut Polytechnique de Paris
Claudia D’Ambrosio: Institut Polytechnique de Paris
Stéphane Canu: Normandie Université

Journal of Global Optimization, 2021, vol. 81, issue 1, No 4, 85-108

Abstract: Abstract Piecewise affine functions are widely used to approximate nonlinear and discontinuous functions. However, most, if not all existing models, only deal with fitting a continuous function. In this paper, we investigate the problem of fitting a discontinuous piecewise affine function to a given function defined on an arbitrary subset of an integer lattice, where no restriction on the partition of the domain is enforced (i.e., its geometric shape can be nonconvex). This is useful for segmentation and denoising when the given function corresponds to a mapping from pixels of a bitmap image to their color depth values. We propose a novel Mixed Integer Program (MIP) formulation for the piecewise affine fitting problem, where binary edge variables determine the boundary between two partitions of the function domain. To obtain a consistent partitioning (e.g., image segmentation), we include multicut constraints in the formulation. The resulting problem is $$\mathcal {NP}$$ NP -hard, and two techniques are introduced to improve the computation. One is to adopt a cutting plane method to add the exponentially many multicut inequalities on-the-fly. The other is to provide initial feasible solutions using a tailored heuristic algorithm. We show that the MIP formulation on grid graphs is approximate, while on king’s graph, it is exact under certain circumstances. We conduct initial experiments on synthetic images as well as real depth images, and discuss the advantages and drawbacks of the two models.

Keywords: Piecewise affine fitting; Mixed integer programming; Cutting plane; Image processing (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01034-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:81:y:2021:i:1:d:10.1007_s10898-021-01034-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01034-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().